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

Abstract

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.

49 pages, 1 figure

References in corpus (8)

• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Algorithms for multi-armed bandit problems
• On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
• A Survey on Contextual Multi-armed Bandits
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• An Entropy Search Portfolio for Bayesian Optimization
• Thompson sampling with the online bootstrap
• Cold-start Problems in Recommendation Systems via Contextual-bandit Algorithms

Cited by in corpus (10)

• Adapting multi-armed bandits policies to contextual bandits scenarios
• Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
• An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization
• Multi-Armed Bandits with Fairness Constraints for Distributing Resources to Human Teammates
• Debiasing Samples from Online Learning Using Bootstrap
• Existence conditions for hidden feedback loops in online recommender systems
• Productization Challenges of Contextual Multi-Armed Bandits
• Reannealing of Decaying Exploration Based On Heuristic Measure in Deep Q-Network
• DORB: Dynamically Optimizing Multiple Rewards with Bandits
• Odds-Ratio Thompson Sampling to Control for Time-Varying Effect