# Regret Analysis of the Anytime Optimally Confident UCB Algorithm

arXiv: https://arxiv.org/abs/1603.08661 · HTML: https://mlsanity.com/paper/1603.08661/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2016.

## Built on by (most cited first, 2 of 2)

- [Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain](https://mlsanity.com/paper/2109.06668/) (2021)
- [Tuning Confidence Bound for Stochastic Bandits with Bandit Distance](https://mlsanity.com/paper/2110.02690/) (2021)

## Abstract (arXiv)

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.