Minimax policies for adversarial and stochastic bandits

2004-01-01otherHAL330 citationsgreen

No readable copy stored yet — this record is metadata only.

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Optimization and Search Problems

Abstract

We fill in a long open gap in the characterization of the minimax rate for the multi-armed bandit problem. Concretely, we remove an extraneous logarithmic factor in the previously known upper bound and propose a new family of randomized algorithms based on an implicit normalization, as well as a new analysis. We also consider the stochastic case, and prove that an appropriate modification of the upper confidence bound policy UCB1 (Auer et al., 2002) achieves the distribution-free optimal rate while still having a distribution-dependent rate logarithmic in the number of plays. 1

Citations in this library

Stored only when both papers are in the corpus — 330 citations exist upstream.

References

2002Finite-time Analysis of the Multiarmed Bandit Problem

2006Prediction, Learning, and Games

2002The Nonstochastic Multiarmed Bandit Problem

1952Some aspects of the sequential design of experiments

2002Gambling in a rigged casino: The adversarial multi-armed bandit problem

Cited by

2012Combinatorial bandits

2012Further Optimal Regret Bounds for Thompson Sampling

2010UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem

2012The K-armed dueling bandits problem

2014From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning

2013Regret in Online Combinatorial Optimization

2011Multi-armed bandits with episode context

2010Regret bounds for sleeping experts and bandits