mlsanityData to 7 Oct 2026

Algorithms for multi-armed bandit problems

arXiv 1402.6028 ↗First posted 25 Feb 2014cs.AI cs.LGcited by 63

Not on the map. Why?

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.

Key facts. Cited by 63 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Feb 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 8; 2023: 7; 2024: 12; 2025: 14; 2026: 6.

63 papers.

Sort:

By area:

  1. 2023Automatic Prompt Optimization with "Gradient Descent" and Beam Searchcited by 628
  2. 2021Meta-Thompson Samplingcited by 62
  3. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  4. 2021No Regrets for Learning the Prior in Banditscited by 29
  5. 2024Do Large Language Models Perform the Way People Expect? Measuring the Human Generalization Functioncited by 24
  6. 2025Rollout Roulette: A Probabilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methodscited by 18
  7. 2021A Survey on Cost Types, Interaction Schemes, and Annotator Performance Models in Selection Algorithms for Active Learning in Classificationcited by 17
  8. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  9. 2022Meta-Learning for Simple Regret Minimizationcited by 10
  10. 2025GAAPO: Genetic Algorithmic Applied to Prompt Optimizationcited by 10
  11. 2025Exploring Exploration in Bayesian Optimizationcited by 8
  12. 2021Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learningcited by 7
38 more
  1. 2024GRAD-SUM: Leveraging Gradient Summarization for Optimal Prompt Engineeringcited by 7
  2. 2021Be Greedy in Multi-Armed Banditscited by 6
  3. 2022Active Inference for Autonomous Decision-Making with Contextual Multi-Armed Banditscited by 6
  4. 2023Adversarial Attacks on Adversarial Banditscited by 6
  5. 2023Multi-Source Test-Time Adaptation as Dueling Bandits for Extractive Question Answeringcited by 6
  6. 2021We Know What You Want: An Advertising Strategy Recommender System for Online Advertisingcited by 5
  7. 2022Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexitycited by 5
  8. 2025Generalization Bounds and Stopping Rules for Learning with Self-Selected Datacited by 5
  9. 2021Extreme Bandits using Robust Statisticscited by 4
  10. 2021Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chesscited by 4
  11. 2023Bayesian Reinforcement Learning with Limited Cognitive Loadcited by 4
  12. 2024Improving the interpretability of GNN predictions through conformal-based graph sparsificationcited by 4
  13. 2024MapTune: Advancing ASIC Technology Mapping via Reinforcement Learning Guided Library Tuningcited by 4
  14. 2024Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problemcited by 4
  15. 2024Variance-Aware Linear UCB with Deep Representation for Neural Contextual Banditscited by 3
  16. 2025Tabular Feature Discovery With Reasoning Type Explorationcited by 3
  17. 2025AUPO -- Abstracted Until Proven Otherwise: A Reward Distribution Based Abstraction Algorithmcited by 3
  18. 2021Neurogenetic Programming Framework for Explainable Reinforcement Learningcited by 2
  19. 2021Active Inference Tree Search in Large POMDPscited by 2
  20. 2021Optimistic Temporal Difference Learning for 2048cited by 2
  21. 2022Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demandcited by 2
  22. 2023Dynamic Exploration-Exploitation Trade-Off in Active Learning Regression with Bayesian Hierarchical Modelingcited by 2
  23. 2023ALE: A Simulation-Based Active Learning Evaluation Framework for the Parameter-Driven Comparison of Query Strategies for NLPcited by 2
  24. 2025KernelBand: Steering LLM-based Kernel Optimization via Hardware-Aware Multi-Armed Banditscited by 2
  25. 2026Efficient Adversarial Attacks on High-dimensional Offline Banditscited by 2
  26. 2021Learning Policies for Multilingual Training of Neural Machine Translation Systemscited by 1
  27. 2022Maximum entropy exploration in contextual bandits with neural networks and energy based modelscited by 1
  28. 2024Causal Contextual Bandits with Adaptive Contextcited by 1
  29. 2024Batch-Instructed Gradient for Prompt Evolution:Systematic Prompt Optimization for Enhanced Text-to-Image Synthesiscited by 1
  30. 2025Online Location Planning for AI-Defined Vehicles: Optimizing Joint Tasks of Order Serving and Spatio-Temporal Heterogeneous Model Fine-Tuningcited by 1
  31. 2025Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budgetcited by 1
  32. 2025Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learningcited by 1
  33. 2021A new soft computing method for integration of expert's knowledge in reinforcement learn-ing problemscited by 0
  34. 2021An Analysis of Reinforcement Learning for Malaria Controlcited by 0
  35. 2021Statistical Consequences of Dueling Banditscited by 0
  36. 2022Modelling Cournot Games as Multi-agent Multi-armed Banditscited by 0
  37. 2022MetaNet: Automated Dynamic Selection of Scheduling Policies in Cloud Environmentscited by 0
  38. 2022Sample Complexity of an Adversarial Attack on UCB-based Best-arm Identification Policycited by 0

50 most cited of 63 All 63 (JSON)