Algorithms for multi-armed bandit problems

Abstract

Although many algorithms for the multi-armed bandit problem are well-understood theoretically, empirical confirmation of their effectiveness is generally scarce. This paper presents a thorough empirical study of the most popular multi-armed bandit algorithms. Three important observations can be made from our results. Firstly, simple heuristics such as epsilon-greedy and Boltzmann exploration outperform theoretically sound algorithms on most settings by a significant margin. Secondly, the performance of most algorithms varies dramatically with the parameters of the bandit problem. Our study identifies for each algorithm the settings where it performs well, and the settings where it performs poorly. Thirdly, the algorithms' performance relative each to other is affected only by the number of bandit arms and the variance of the rewards. This finding may guide the design of subsequent empirical evaluations. In the second part of the paper, we turn our attention to an important area of application of bandit algorithms: clinical trials. Although the design of clinical trials has been one of the principal practical problems motivating research on multi-armed bandits, bandit algorithms have never been evaluated as potential treatment allocation strategies. Using data from a real study, we simulate the outcome that a 2001-2002 clinical trial would have had if bandit algorithms had been used to allocate patients to treatments. We find that an adaptive trial would have successfully treated at least 50% more patients, while significantly reducing the number of adverse effects and increasing patient retention. At the end of the trial, the best treatment could have still been identified with a high level of statistical confidence. Our findings demonstrate that bandit algorithms are attractive alternatives to current adaptive treatment allocation strategies.

Cited by in corpus (58)

• Estimation-Action-Reflection: Towards Deep Interaction Between Conversational and Recommender Systems
• A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
• Multi-Task Learning for Contextual Bandits
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
• Boltzmann Exploration Done Right
• Preference-based Online Learning with Dueling Bandits: A Survey
• Nonparametric Pricing Analytics with Customer Covariates
• A Survey on Cost Types, Interaction Schemes, and Annotator Performance Models in Selection Algorithms for Active Learning in Classification
• On Reinforcement Learning for the Game of 2048
• Optimistic Temporal Difference Learning for 2048
• Multi-Armed Bandit Strategies for Non-Stationary Reward Distributions and Delayed Feedback Processes
• A Survey of Latent Factor Models in Recommender Systems
• contextual: Evaluating Contextual Multi-Armed Bandit Problems in R
• Empirical Bayes Regret Minimization
• Active Reinforcement Learning with Monte-Carlo Tree Search
• Differentiable Bandit Exploration
• Diversifying Database Activity Monitoring with Bandits
• Meta-Learning Bandit Policies by Gradient Ascent
• Single-partition adaptive Q-learning
• Data Poisoning Attacks in Contextual Bandits
• Learning to Communicate Functional States with Nonverbal Expressions for Improved Human-Robot Collaboration
• Combining Offline Causal Inference and Online Bandit Learning for Data Driven Decision
• Meta-Thompson Sampling
• Explore-Exploit: A Framework for Interactive and Online Learning
• Optimising Individual-Treatment-Effect Using Bandits
• Learning Modular Safe Policies in the Bandit Setting with Application to Adaptive Clinical Trials
• On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems
• Be Greedy in Multi-Armed Bandits
• RLOC: Neurobiologically Inspired Hierarchical Reinforcement Learning Algorithm for Continuous Control of Nonlinear Dynamical Systems
• Multi-Statistic Approximate Bayesian Computation with Multi-Armed Bandits
• Scalable Multiagent Coordination with Distributed Online Open Loop Planning
• Hybrid Transactional Replication: State-Machine and Deferred-Update Replication Combined
• Boltzmann Exploration Expectation-Maximisation
• Lifelong Learning in Multi-Armed Bandits
• Data-Efficient Policy Selection for Navigation in Partial Maps via Subgoal-Based Abstraction
• MOLTE: a Modular Optimal Learning Testing Environment
• Active Algorithms For Preference Learning Problems with Multiple Populations
• Compliance-Aware Bandits
• Statistically Model Checking PCTL Specifications on Markov Decision Processes via Reinforcement Learning
• Practical Adversarial Combinatorial Bandit Algorithm via Compression of Decision Sets
• Hawkes Process Multi-armed Bandits for Disaster Search and Rescue
• Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack
• ALE: A Simulation-Based Active Learning Evaluation Framework for the Parameter-Driven Comparison of Query Strategies for NLP
• No Regrets for Learning the Prior in Bandits
• A PAC algorithm in relative precision for bandit problem with costly sampling
• A Batched Multi-Armed Bandit Approach to News Headline Testing
• An Opportunistic Bandit Approach for User Interface Experimentation
• Intrinsic Exploration as Multi-Objective RL
• Learning Policies for Multilingual Training of Neural Machine Translation Systems
• Doubly Robust Off-Policy Learning on Low-Dimensional Manifolds by Deep Neural Networks
• Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess
• Statistical Consequences of Dueling Bandits
• A new soft computing method for integration of expert's knowledge in reinforcement learn-ing problems
• How to select the largest k elements from evolving data?
• Exploring Offline Policy Evaluation for the Continuous-Armed Bandit Problem
• Learning Orthogonal Projections in Linear Bandits
• Delegating via Quitting Games
• On Adaptive Estimation for Dynamic Bernoulli Bandits