Regret Analysis of the Anytime Optimally Confident UCB Algorithm

By Tor Lattimore. 2016

28 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

The Uncertainty Bellman Equation and Exploration (2017, background): “However, apart from the simple ‘multi-armed bandit’ setting with only one state, there is still a significant gap between the upper and lower bounds for these algorithms (Lattimore, 2016; Jaksch et al., 2010; Osband & Van Roy, 2016).”
Learning the distribution with largest mean: two bandit frameworks (2017, background): “…to a variant sometimes termed kl-UCB + which has a slightly better empirical performance, but also minimax guarantees that plain UCB algorithms do not enjoy (for a discussion and related ideas, see the OCUCB algorithm of [Lattimore, 2016], [Ménard and Garivier, 2017] and the references therein).”