# Algorithms for multi-armed bandit problems

arXiv: https://arxiv.org/abs/1402.6028 · HTML: https://mlsanity.com/paper/1402.6028/

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2014.

## Built on by (most cited first, 30 of 64)

- [Automatic Prompt Optimization with "Gradient Descent" and Beam Search](https://mlsanity.com/paper/2305.03495/) (2023)
- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [No Regrets for Learning the Prior in Bandits](https://mlsanity.com/paper/2107.06196/) (2021)
- [Do Large Language Models Perform the Way People Expect? Measuring the Human Generalization Function](https://mlsanity.com/paper/2406.01382/) (2024)
- [Rollout Roulette: A Probabilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methods](https://mlsanity.com/paper/2502.01618/) (2025)
- [A Survey on Cost Types, Interaction Schemes, and Annotator Performance Models in Selection Algorithms for Active Learning in Classification](https://mlsanity.com/paper/2109.11301/) (2021)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [GAAPO: Genetic Algorithmic Applied to Prompt Optimization](https://mlsanity.com/paper/2504.07157/) (2025)
- [Meta-Learning for Simple Regret Minimization](https://mlsanity.com/paper/2202.12888/) (2022)
- [Exploring Exploration in Bayesian Optimization](https://mlsanity.com/paper/2502.08208/) (2025)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2107.01689/) (2021)
- [GRAD-SUM: Leveraging Gradient Summarization for Optimal Prompt Engineering](https://mlsanity.com/paper/2407.12865/) (2024)
- [Active Inference for Autonomous Decision-Making with Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2209.09185/) (2022)
- [Adversarial Attacks on Adversarial Bandits](https://mlsanity.com/paper/2301.12595/) (2023)
- [Multi-Source Test-Time Adaptation as Dueling Bandits for Extractive Question Answering](https://mlsanity.com/paper/2306.06779/) (2023)
- [We Know What You Want: An Advertising Strategy Recommender System for Online Advertising](https://mlsanity.com/paper/2105.14188/) (2021)
- [Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity](https://mlsanity.com/paper/2211.07092/) (2022)
- [Generalization Bounds and Stopping Rules for Learning with Self-Selected Data](https://mlsanity.com/paper/2505.07367/) (2025)
- [Extreme Bandits using Robust Statistics](https://mlsanity.com/paper/2109.04433/) (2021)
- [Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess](https://mlsanity.com/paper/2110.01810/) (2021)
- [Bayesian Reinforcement Learning with Limited Cognitive Load](https://mlsanity.com/paper/2305.03263/) (2023)
- [Improving the interpretability of GNN predictions through conformal-based graph sparsification](https://mlsanity.com/paper/2404.12356/) (2024)
- [MapTune: Advancing ASIC Technology Mapping via Reinforcement Learning Guided Library Tuning](https://mlsanity.com/paper/2407.18110/) (2024)
- [Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem](https://mlsanity.com/paper/2412.14382/) (2024)
- [Variance-Aware Linear UCB with Deep Representation for Neural Contextual Bandits](https://mlsanity.com/paper/2411.05979/) (2024)
- [Tabular Feature Discovery With Reasoning Type Exploration](https://mlsanity.com/paper/2506.20357/) (2025)
- [AUPO -- Abstracted Until Proven Otherwise: A Reward Distribution Based Abstraction Algorithm](https://mlsanity.com/paper/2510.23214/) (2025)
- [Neurogenetic Programming Framework for Explainable Reinforcement Learning](https://mlsanity.com/paper/2102.04231/) (2021)

## Abstract (arXiv)

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.