Regret Analysis of the Anytime Optimally Confident UCB Algorithm

Abstract

I introduce and analyse an anytime version of the Optimally Confident UCB (OCUCB) algorithm designed for minimising the cumulative regret in finite-armed stochastic bandits with subgaussian noise. The new algorithm is simple, intuitive (in hindsight) and comes with the strongest finite-time regret guarantees for a horizon-free algorithm so far. I also show a finite-time lower bound that nearly matches the upper bound.

16 pages

References in corpus (3)

• Informational Confidence Bounds for Self-Normalized Averages and Applications
• Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits

Cited by in corpus (6)

• Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain
• The Uncertainty Bellman Equation and Exploration
• KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints
• Bandits with Side Observations: Bounded vs. Logarithmic Regret
• Accelerated learning from recommender systems using multi-armed bandit
• Tuning Confidence Bound for Stochastic Bandits with Bandit Distance