On Explore-Then-Commit Strategies

Abstract

We study the problem of minimising regret in two-armed bandit problems with Gaussian rewards. Our objective is to use this simple setting to illustrate that strategies based on an exploration phase (up to a stopping time) followed by exploitation are necessarily suboptimal. The results hold regardless of whether or not the difference in means between the two arms is known. Besides the main message, we also refine existing deviation inequalities, which allow us to design fully sequential strategies with finite-time regret guarantees that are (a) asymptotically optimal as the horizon grows and (b) order-optimal in the minimax sense. Furthermore we provide empirical evidence that the theory also holds in practice and discuss extensions to non-gaussian and multiple-armed case.

Cited by in corpus (15)

• What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Online Influence Maximization under Linear Threshold Model
• Probabilistic design of optimal sequential decision-making algorithms in learning and control
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• Regret Minimization in Partially Observable Linear Quadratic Control
• Double Explore-then-Commit: Asymptotic Optimality and Beyond
• Online Competitive Influence Maximization
• Issues concerning realizability of Blackwell optimal policies in reinforcement learning
• Bandits with many optimal arms
• The Survival Bandit Problem
• Efficient Algorithms for Stochastic Repeated Second-price Auctions
• Tuning Confidence Bound for Stochastic Bandits with Bandit Distance
• Minimal Expected Regret in Linear Quadratic Control
• Sequential Choice Bandits with Feedback for Personalizing users' experience