Better Algorithms for Stochastic Bandits with Adversarial Corruptions

Anupam Gupta; Tomer Koren; Kunal Talwar

Better Algorithms for Stochastic Bandits with Adversarial Corruptions

Anupam Gupta, Tomer Koren, Kunal Talwar

Computer Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount of corruption with virtually no degradation in performance.

Original language	English (US)
Pages (from-to)	1562-1578
Number of pages	17
Journal	Proceedings of Machine Learning Research
Volume	99
State	Published - 2019
Event	32nd Conference on Learning Theory, COLT 2019 - Phoenix, United States Duration: Jun 25 2019 → Jun 28 2019

ASJC Scopus subject areas

Artificial Intelligence
Software
Control and Systems Engineering
Statistics and Probability

Cite this

@article{0eb5c221388f48adafd20a9c5b7c773a,

title = "Better Algorithms for Stochastic Bandits with Adversarial Corruptions",

abstract = "We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount of corruption with virtually no degradation in performance.",

author = "Anupam Gupta and Tomer Koren and Kunal Talwar",

note = "Publisher Copyright: {\textcopyright} 2019 A. Gupta, T. Koren & K. Talwar.; 32nd Conference on Learning Theory, COLT 2019 ; Conference date: 25-06-2019 Through 28-06-2019",

year = "2019",

language = "English (US)",

volume = "99",

pages = "1562--1578",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

publisher = "ML Research Press",

}

TY - JOUR

T1 - Better Algorithms for Stochastic Bandits with Adversarial Corruptions

AU - Gupta, Anupam

AU - Koren, Tomer

AU - Talwar, Kunal

PY - 2019

Y1 - 2019

N2 - We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount of corruption with virtually no degradation in performance.

AB - We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount of corruption with virtually no degradation in performance.

UR - http://www.scopus.com/inward/record.url?scp=85160843794&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85160843794&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85160843794

SN - 2640-3498

VL - 99

SP - 1562

EP - 1578

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 32nd Conference on Learning Theory, COLT 2019

Y2 - 25 June 2019 through 28 June 2019

ER -

Better Algorithms for Stochastic Bandits with Adversarial Corruptions

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this