Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
arXiv:1507.07880
Abstract
I present the first algorithm for stochastic finite-armed bandits that simultaneously enjoys order-optimal problem-dependent regret and worst-case regret. Besides the theoretical results, the new algorithm is simple, efficient and empirically superb. The approach is based on UCB, but with a carefully chosen confidence parameter that optimally balances the risk of failing confidence intervals against the cost of excessive optimism.
26 pages
References in corpus (6)
- Further Optimal Regret Bounds for Thompson Sampling
- Algorithms for multi-armed bandit problems
- lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
- A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
- Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
- Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit
Cited by in corpus (9)
- Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
- Conservative Bandits
- Regret Analysis of the Anytime Optimally Confident UCB Algorithm
- The Pareto Regret Frontier for Bandits
- MOTS: Minimax Optimal Thompson Sampling
- Bandit Algorithms for Precision Medicine
- Accelerated learning from recommender systems using multi-armed bandit
- Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
- Thompson Sampling Guided Stochastic Searching on the Line for Deceptive Environments with Applications to Root-Finding Problems