2015

A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit

Burtini, Giuseppe, Loeppky, Jason, Lawrence, Ramon

Understand

Adaptive and sequential experiment design is a well-studied area in numerous domains.

We survey and synthesize the work of the online statistical learning paradigm referred to as multi-armed bandits integrating the existing research as a resource for a certain class of online experiments.
We first explore the traditional stochastic model of a multi-armed bandit, then explore a taxonomic scheme of complications to that model, for each complication relating it to a specific requirement or consideration of the experiment design context.
Finally, at the end of the paper, we present a table of known upper-bounds of regret for all studied algorithms providing both perspectives for future theoretical work and a decision-making tool for practitioners looking for theoretical guarantees.

Built on

Hierarchical exploration for accelerating contextual bandits
Yue, Y · 1902
Earlier work this paper cites.
Risk, uncertainty and profit
Knight, F. H · 1921
Earlier work this paper cites.
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
Thompson, W. R · 1933
Earlier work this paper cites.
Sequential Analysis
Wald, A · 1947
Earlier work this paper cites.
Bayes and minimax solutions of sequential decision problems
Arrow, K. J · 1949
Earlier work this paper cites.
On information and sufficiency
Kullback, S · 1951
Earlier work this paper cites.
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations
Chernoff, H · 1952
Earlier work this paper cites.
Adaptive Monte Carlo via bandit allocation
Neufeld, J · 1952
Earlier work this paper cites.
Some aspects of the sequential design of experiments
Robbins, H · 1952
Earlier work this paper cites.
Continuous inspection schemes
Page, E · 1954
Earlier work this paper cites.
Factors influencing rate and extent of learning in the presence of misinformative feedback
Morin, R. E · 1955
Earlier work this paper cites.
The perceptron: a probabilistic model for information storage and organization in the brain
Rosenblatt, F · 1958
Earlier work this paper cites.
Sequential medical trials
Armitage, P · 1960
Earlier work this paper cites.
Sequential medical trials
Anscombe, F · 1963
Earlier work this paper cites.
A model for selecting one of two medical treatments
Colton, T · 1963
Earlier work this paper cites.
Probability inequalities for sums of bounded random variables
Hoeffding, W · 1963
Earlier work this paper cites.
Two-stage designs for clinical trials
Day, N · 1969
Earlier work this paper cites.
Inference about the change-point in a sequence of random variables
Hinkley, D. V · 1970
Earlier work this paper cites.
The randomized play-the-winner rule in medical trials
Wei, L · 1978
Earlier work this paper cites.
Bootstrap methods: another look at the Jackknife
Efron, B · 1979
Earlier work this paper cites.
Bandit processes and dynamic allocation indices
Gittins, J. C · 1979
Earlier work this paper cites.
A dynamic allocation index for the discounted multiarmed bandit problem
Gittins, J. C · 1979
Earlier work this paper cites.
A one-armed bandit problem with a concomitant variable
Woodroofe, M · 1979
Earlier work this paper cites.
Multi-armed bandits and the Gittins index
Whittle, P · 1980
Earlier work this paper cites.
Heuristics: intelligent search strategies for computer problem solving
Pearl, J · 1984
Earlier work this paper cites.
A theory of the learnable
Valiant, L. G · 1984
Earlier work this paper cites.
Disappointment in decision making under uncertainty
Bell, D. E · 1985
Earlier work this paper cites.
Bandit Problems: Sequential Allocation of Experiments
Berry, D · 1985
Earlier work this paper cites.
Asymptotically efficient adaptive allocation rules
Lai, T. L · 1985
Earlier work this paper cites.
The multi-armed bandit problem: decomposition and computation
Katehakis, M. N · 1987
Earlier work this paper cites.
Detecting changes in signals and systems: a survey
Basseville, M · 1988
Earlier work this paper cites.
Learning from delayed rewards
Watkins, C. J. C. H · 1989
Earlier work this paper cites.
Statistical approaches to interim monitoring of medical trials: A review and commentary
Jennison, C · 1990
Earlier work this paper cites.
Integrated architectures for learning, planning, and reacting based on approximating dynamic programming
Sutton, R. S · 1990
Earlier work this paper cites.
On the Gittins index for multiarmed bandits
Weber, R · 1992
Earlier work this paper cites.
On adjusting p-values for multiplicity
Westfall, P. H · 1993
Earlier work this paper cites.
A course in game theory
Osborne, M. J · 1994
Earlier work this paper cites.
A short proof of the Gittins index theorem
Tsitsiklis, J. N · 1994
Earlier work this paper cites.
Sample mean based index policies with O(log n) regret for the multi-armed bandit problem
Agrawal, R · 1995
Earlier work this paper cites.
Decision-making under uncertainty: Capturing dynamic brand choice processes in turbulent consumer goods markets
Erdem, T · 1996
Earlier work this paper cites.
Multiple Comparisons: Theory and Methods
Hsu, J · 1996
Earlier work this paper cites.
Coping with uncertainty: A naturalistic decision-making analysis
Lipshitz, R · 1997
Earlier work this paper cites.
On-line learning with malicious noise and the closure algorithm
Auer, P · 1998
Earlier work this paper cites.
Finite-time regret bounds for the multiarmed bandit problem
Cesa-Bianchi, N · 1998
Earlier work this paper cites.
Randomized play-the-winner clinical trials: review and recommendations
Rosenberger, W. F · 1999
Earlier work this paper cites.
Learning and planning in structured worlds
Dearden, R. W · 2000
Earlier work this paper cites.
Finite-time analysis of the multiarmed bandit problem
Auer, P · 2002
Earlier work this paper cites.

Similar

The nonstochastic multiarmed bandit problem
Auer, P · 2002
Cited alongside, same era.
Optimal learning and experimentation in bandit problems
Brezzi, M · 2002
Cited alongside, same era.
One-armed bandit problems with covariates
Sarkar, J · 2002
Cited alongside, same era.
Using confidence bounds for exploitation-exploration trade-offs
Auer, P · 2003
Cited alongside, same era.
A perspective on judgment and choice: mapping bounded rationality
Kahneman, D · 2003
Cited alongside, same era.
On Hoeffding’s inequalities
Bentkus, V · 2004
Cited alongside, same era.
Multi-armed bandit algorithms and empirical evaluation
Vermorel, J · 2005
Cited alongside, same era.
Bandit problems with side observations
Wang, C.-C · 2005
Cited alongside, same era.
Prediction, learning, and games
Cesa-Bianchi, N · 2006
Cited alongside, same era.
Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
Even-Dar, E · 2006
Cited alongside, same era.
Modification of UCT with patterns in Monte Carlo Go
Gelly, S · 2006
Cited alongside, same era.
Multi-armed bandit, dynamic environments and meta-bandits
Hartland, C · 2006
Cited alongside, same era.

Then

The KL-UCB algorithm for bounded stochastic bandits and beyond
Garivier, A · 2011
Later among the works it cites.
A two-armed bandit based scheme for accelerated decentralized learning
Granmo, O.-C · 2011
Later among the works it cites.
A finite-time analysis of multi-armed bandits problems with Kullback-Leibler divergences
Maillard, O.-A · 2011
Later among the works it cites.
Analysis of Thompson sampling for the multi-armed bandit problem
Agrawal, S · 2012
Later among the works it cites.
A survey of Monte Carlo tree search methods
Browne, C · 2012
Later among the works it cites.
Regret analysis of stochastic and nonstochastic multi-armed bandit problems
Bubeck, S · 2012
Later among the works it cites.
The best of both worlds: Stochastic and adversarial bandits
Bubeck, S · 2012
Later among the works it cites.
Algorithms for learning regression trees and ensembles on evolving data streams
Ikonomovska, E · 2012
Later among the works it cites.
On Bayesian upper confidence bounds for bandit problems
Kaufmann, E · 2012
Later among the works it cites.
Thompson sampling: An asymptotically optimal finite-time analysis
Kaufmann, E · 2012
Later among the works it cites.
On the uniform asymptotic validity of subsampling and the bootstrap
Romano, J. P · 2012
Later among the works it cites.
Some properties of the randomized play the winner rule
Tolusso, D · 2012
Later among the works it cites.
Further optimal regret bounds for Thompson sampling
Agrawal, S · 2013
Later among the works it cites.
Online learning with switching costs and other adaptive adversaries
Cesa-Bianchi, N · 2013
Later among the works it cites.
Four proofs of Gittins’ multiarmed bandit theorem
Frostig, E · 2013
Later among the works it cites.
Thompson sampling in switching environments with Bayesian online change detection
Mellor, J · 2013
Later among the works it cites.
(More) efficient reinforcement learning via posterior sampling
Osband, I · 2013
Later among the works it cites.
The multi-armed bandit problem with covariates
Perchet, V · 2013
Later among the works it cites.
Modeling human decision-making in multi-armed bandits
Reverdy, P · 2013
Later among the works it cites.
Optimal foraging and multi-armed bandits
Srivastava, V · 2013
Later among the works it cites.
Continuum armed bandit problem of few variables in high dimensions
Tyagi, H · 2013
Later among the works it cites.
Taming the monster: A fast and simple algorithm for contextual bandits
Agarwal, A · 2014
Later among the works it cites.
A neural networks committee for the contextual bandit problem
Allesiardo, R · 2014
Later among the works it cites.
Notes on randomized algorithms
Aspnes, J · 2014
Later among the works it cites.
Sub-sampling for multi-armed bandits
Baransi, A · 2014
Later among the works it cites.
Contextual bandit for active learning: Active Thompson sampling
Bouneffouf, D · 2014
Later among the works it cites.
Unimodal bandits: Regret lower bounds and optimal algorithms
Combes, R · 2014
Later among the works it cites.
Thompson sampling with the online bootstrap
Original
Eckles, D · 2014
Later among the works it cites.
Thompson sampling for complex online problems
Gopalan, A · 2014
Later among the works it cites.
Stochastic regret minimization via Thompson sampling
Guha, S · 2014
Later among the works it cites.
Optimality of Thompson sampling for Gaussian Bandits depends on priors
Honda, J · 2014
Later among the works it cites.
Algorithms for multi-armed bandit problems
Original
Kuleshov, V · 2014
Later among the works it cites.
From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning
Munos, R · 2014
Later among the works it cites.
Cold-start problems in recommendation systems via contextual-bandit algorithms
Original
Nguyen, H. T · 2014
Later among the works it cites.
Markov decision processes: discrete stochastic dynamic programming
Puterman, M. L · 2014
Later among the works it cites.
Learning to optimize via posterior sampling
Russo, D · 2014
Later among the works it cites.
An entropy search portfolio for Bayesian optimization
Original
Shahriari, B · 2014
Later among the works it cites.
Adaptive clinical trial designs for Phase I cancer studies
Sverdlov, O · 2014
Later among the works it cites.
On two continuum armed bandit problems in high dimensions
Tyagi, H · 2014
Later among the works it cites.
Multi-objective χ \chi -armed bandits
Van Moffaert, K · 2014
Later among the works it cites.
Exp3 with drift detection for the switching bandit problem
Allesiardo, R · 2015
Closest in time.
Simple regret for infinitely many armed bandits
Carpentier, A · 2015
Closest in time.
Optimal regret analysis of Thompson Sampling in stochastic multi-armed bandit problem with multiple plays
Junpei Komiyama, J. H · 2015
Closest in time.
The use of Thompson sampling to increase estimation precision
Kaptein, M · 2015
Closest in time.
A multiple-play bandit algorithm applies to recommender systems
Louëdec, J · 2015
Closest in time.
A survey on contextual multi-armed bandits
Original
Zhou, L · 2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…