Conference proceeding
Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, Vol.139, pp.6142-6151
Proceedings of Machine Learning Research
01/01/2021
Abstract
In this work, we develop linear bandit algorithms that automatically adapt to different environments. By plugging a novel loss estimator into the optimization problem that characterizes the instance-optimal strategy, our first algorithm not only achieves nearly instance-optimal regret in stochastic environments, but also works in corrupted environments with additional regret being the amount of corruption, while the state-of-the-art (Li et al., 2019) achieves neither instance-optimality nor the optimal dependence on the corruption amount. Moreover, by equipping this algorithm with an adversarial component and carefully-designed testings, our second algorithm additionally enjoys minimax-optimal regret in completely adversarial environments, which is the first of this kind to our knowledge. Finally, all our guarantees hold with high probability, while existing instance-optimal guarantees only hold in expectation.
Details
- Title: Subtitle
- Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
- Creators
- Chung-Wei Lee - Univ Southern Calif, Los Angeles, CA 90089 USAHaipeng Luo - Univ Southern Calif, Los Angeles, CA 90089 USAChen-Yu Wei - Univ Southern Calif, Los Angeles, CA 90089 USAMengxiao Zhang - Univ Southern Calif, Los Angeles, CA 90089 USAXiaojin Zhang - Chinese University of Hong Kong
- Contributors
- M Meila (Editor)T Zhang (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- INTERNATIONAL CONFERENCE ON MACHINE LEARNING, Vol.139, pp.6142-6151
- Publisher
- JMLR-JOURNAL MACHINE LEARNING RESEARCH
- Series
- Proceedings of Machine Learning Research
- ISSN
- 2640-3498
- eISSN
- 2640-3498
- Number of pages
- 10
- Grant note
- IIS-1755781; IIS-1943607 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2021
- Academic Unit
- Business Analytics
- Record Identifier
- 9984701732702771
Metrics
1 Record Views