Multi-armed bandit

A multi-armed bandit is a sequential decision problem in which a learner repeatedly picks one action from a fixed set, receives a random reward for that action only, and tries to accumulate as much reward as possible. The learner never observes what the actions it passed over would have paid, so every round forces a choice between taking the option that currently looks best and sampling an option it knows less about. That tension is the exploration-exploitation tradeoff, and the bandit is its simplest formal model ^[5][7].

In the basic stochastic version, a K-armed bandit is defined by random variables for each arm, where successive plays of arm i return rewards drawn independently from an unknown distribution with unknown mean. An allocation strategy chooses the next arm from the history of past plays and rewards. Performance is measured by regret: the expected shortfall between the reward of always playing the best arm and the reward the strategy actually collected ^[5]. Bandit problems sit inside machine learning as the boundary case of reinforcement learning in which actions have no lasting consequences.

The model is used well beyond theory. Major technology companies run bandit algorithms to configure web interfaces, recommend news and place adverts ^[7], bandit selection rules sit inside Monte Carlo planning ^[17], and the reward structure that language-model alignment pipelines optimize is formally a bandit environment ^[18].

Origins and the name

William R. Thompson introduced the problem in a 1933 Biometrika paper, motivated by medical trials and by the ethical cost of running a trial blindly instead of shifting patients toward the treatment that appears to be working ^[1][7]. Thompson gave only hand-calculated empirical evidence and restricted his attention to Bernoulli rewards with two arms ^[7].

The gambling name arrived later. In the 1950s Frederick Mosteller and Robert Bush studied animal learning using mice in a T-shaped maze, then commissioned a two-armed machine so humans could face a comparable choice between two levers with unknown payoff distributions. The machine was named in homage to the one-armed bandit, an old term for a lever-operated slot machine, so called because it takes your money ^[7].

Herbert Robbins put the problem on a formal footing in a 1952 Bulletin of the American Mathematical Society paper on the sequential design of experiments ^[2]. Two later results shaped everything that followed. John C. Gittins showed in 1979 that a particular index rule solves the Bayesian discounted version exactly ^[4], and T. L. Lai and Robbins proved in 1985 that regret must grow at least logarithmically in the number of plays, while exhibiting policies that attain that rate asymptotically ^[3].

Regret and what is achievable

Regret comes in two flavors that are easy to confuse. The instance-dependent form asks how a policy performs on one particular set of reward distributions, and its size is governed by the suboptimality gaps, the differences between each arm's mean and the best mean. The minimax form asks how a policy performs against the worst environment in a class, and gaps disappear from the answer.

Lai and Robbins established the instance-dependent limit: for suitable families of reward distributions, any allocation strategy must play a suboptimal arm j at least (ln n) / D(p_j, p*) times asymptotically, where D is the Kullback-Leibler divergence between the reward density of arm j and that of the best arm. Their own policies match this rate ^[3][5]. The bound explains why logarithmic regret is the target for stochastic bandits: it is not a convenient benchmark but the floor.

The worst-case picture is different. For k-armed Gaussian bandits with unit variance, whatever policy is chosen there exists a mean vector in the unit interval on which its regret is at least one twenty-seventh of the square root of (k - 1)n, for every k greater than 1 and every horizon n at least k - 1 ^[7]. A policy can be logarithmic on every fixed instance and still incur regret of that square-root order when the gaps are allowed to shrink with the horizon; the two statements describe different questions, not a contradiction.

Core algorithms

Epsilon-greedy

The epsilon-greedy rule plays the arm with the highest empirical mean with probability 1 minus epsilon and a uniformly random arm otherwise. A constant epsilon produces linear rather than logarithmic regret, because the algorithm keeps paying a fixed exploration tax forever. Auer, Cesa-Bianchi and Fischer showed that letting the exploration probability decay at rate 1/n recovers a logarithmic bound, in their variant called epsilon-n-greedy. The catch is that the tuning constant depends on a lower bound for the smallest gap, which is exactly the quantity an experimenter does not know in advance, and the paper's own experiments show performance degrading rapidly when the parameter is off ^[5].

Upper confidence bounds

UCB algorithms follow the optimism principle: estimate each arm's mean as high as the data plausibly allow, then play the arm with the highest estimate. The index is an empirical mean plus an exploration bonus that shrinks as the arm is sampled more. For rewards in the unit interval, Bubeck and Cesa-Bianchi give the family as an index equal to the empirical mean plus the square root of the quantity (alpha times ln t) divided by (2 times the number of pulls of that arm), where alpha is a tuning parameter ^[8].

Auer and colleagues proved the first finite-time guarantee for such a policy. Their UCB1 achieves expected regret after n plays of at most 8 times the sum over suboptimal arms of (ln n) divided by the gap, plus (1 + pi squared over 3) times the sum of all gaps, for arbitrary reward distributions supported on the unit interval and with no prior knowledge of those distributions ^[5]. The proof bounds the expected number of pulls of a suboptimal arm by 8 ln(n) divided by the squared gap plus a small constant, a leading constant the authors note is worse than the 1/D of Lai and Robbins; a more elaborate variant, UCB2, brings that constant arbitrarily close to 1 divided by twice the squared gap, at the cost of an additive term that diverges as its tuning parameter shrinks. The paper also introduces UCB1-TUNED, which uses a variance estimate and beat plain UCB1 in essentially all of the authors' experiments, and which they explicitly could not prove a regret bound for ^[5]. Modern treatments state the result with cleaner constants: with confidence parameter 1/n squared on a 1-subgaussian problem, regret is bounded by 3 times the sum of the gaps plus the sum over positive gaps of 16 log(n) divided by the gap ^[7].

Thompson sampling

Thompson's 1933 rule maintains a posterior over the environment, samples one environment from that posterior each round, and plays the action that would be optimal if the sample were true ^[1][7]. Exploration comes from the randomization: a diffuse posterior produces variable samples and frequent exploration, and the rate falls automatically as the posterior concentrates. For Bernoulli rewards with Beta priors the implementation is a few lines of code, which is much of its appeal.

The method was then largely ignored for decades. Chapelle and Li reopened the case in 2011, calling it "one of oldest heuristic to address the exploration / exploitation trade-off, but it is surprisingly not very popular in the literature," and arguing from simulated and real data that it belongs among the standard baselines ^[9]. Theory followed quickly. Agrawal and Goyal gave the first logarithmic regret bounds for the classical problem in 2012 ^[10], and Kaufmann, Korda and Munos produced a finite-time analysis matching the Lai and Robbins asymptotic rate for Bernoulli rewards in the same year ^[11]. Daniel Russo and co-authors later wrote a 96-page tutorial covering the algorithm's applications and the question of when it is and is not effective ^[12]. Thompson sampling is also known as posterior sampling, and it connects the bandit literature to Bayesian inference more broadly.

Adversarial bandits and Exp3

The stochastic model assumes each arm's rewards are drawn i.i.d. from a fixed probability distribution. The adversarial model drops that assumption entirely and lets an opponent fix the reward sequence in advance. Auer, Cesa-Bianchi, Freund and Schapire solved this setting with Exp3, short for exponential-weight algorithm for exploration and exploitation, which maintains importance-weighted reward estimates and samples arms in proportion to their exponentiated totals ^[6]. With the learning rate set to the square root of the quantity 2 log(k)/(nk), its expected regret over n rounds with k arms is bounded by the square root of 2nk log(k) ^[7].

The Gittins index

Gittins attacked the Bayesian version with geometric discounting over an infinite horizon. His index, sometimes called the fair charge, is the smallest retirement payment at which a learner would be indifferent between stopping and continuing to play a given arm from its current state. The celebrated theorem is that always playing the arm of largest index is Bayes-optimal for the discounted objective ^[4][7]. This is a genuinely strong result: it decomposes a k-armed problem into k separate one-armed calculations. It is also narrow. The finite-horizon Bayesian optimal policy is generally not an index policy at all, computing the index is its own research area, and Peter Whittle's restless bandit variant, in which every arm's state evolves whether or not it is played, is far harder and has produced few positive results ^[7][24].

Scroll sideways for more →

Contextual bandits

In a contextual bandit the learner sees side information before choosing. The plain formulation cannot express the fact that a user who just bought climbing shoes is a better target for a harness than an arbitrary visitor, so context is what makes the model useful for personalization ^[7].

LinUCB, introduced by Lihong Li, Wei Chu, John Langford and Robert Schapire at WWW 2010, assumes the expected payoff of an arm is linear in a feature vector describing the context and that arm. It estimates the coefficient vector by ridge regression and adds a confidence term proportional to the square root of the predictive variance, which gives a closed-form upper confidence bound rather than a general and expensive one. Computation is linear in the number of arms and at most cubic in the number of features. The paper gives a disjoint version, where each arm has its own coefficients, and a hybrid version that shares some coefficients across arms ^[13].

The same paper made a second contribution that matters as much in practice: it showed that any bandit algorithm can be evaluated offline on logged data collected under random traffic. Applying that replay method to a Yahoo! Front Page Today Module dataset of more than 33 million events, LinUCB produced a 12.5% click lift over a context-free bandit baseline, with a larger advantage when data were scarce ^[13].

Production systems followed. Microsoft's Decision Service, described by Alekh Agarwal, John Langford, Alex Slivkins and colleagues, wrapped contextual bandit learning in four abstractions that connect in a loop (explore, log, learn, deploy), of which the explore and log abstractions exist to ensure the system produces correct, unbiased data, and reported click-through improvements of 25-30% on two live content recommendation deployments and an 18% revenue lift on a landing page ^[14]. Azure AI Personalizer packaged the same idea as a cloud service with Rank and Reward APIs and a configurable exploration percentage; Microsoft closed it to new resources in September 2023 and set its retirement for 1 October 2026, pointing users to the open-source learning-loop project instead ^[15]. Netflix described using contextual bandits to choose which single artwork represents each title, naming epsilon-greedy with uniform randomness alongside Thompson sampling, LinUCB and Bayesian methods, and reported a significant lift in its core metrics in an online test ^[16].

Relation to full reinforcement learning

The clean way to state the relationship is that in a bandit the learner never needs to plan for the future. The standing assumption is that today's choices do not change tomorrow's available actions or rewards. Problems that do require that kind of planning belong to reinforcement learning proper ^[7].

A Markov decision process adds the missing machinery: the learner observes a state, rewards depend on the state, and the chosen action determines which state comes next. Bandits are the degenerate case with a single state, which is why they are usually taught first and why bandit techniques reappear inside RL algorithms. Monte Carlo tree search is the clearest example. Levente Kocsis and Csaba Szepesvári set out the approach in a 2006 paper titled Bandit Based Monte-Carlo Planning ^[17], and the resulting family of algorithms became widely known through AlphaGo ^[7].

The connection runs the other way too. Alignment pipelines built on RLHF are usually bandit problems rather than sequential control problems. The InstructGPT paper states it directly: "The environment is a bandit environment which presents a random customer prompt and expects a response to the prompt. Given the prompt and response, it produces a reward determined by the reward model and ends the episode" ^[18]. One prompt, one action (the whole response), one reward from the reward model, then termination. That is why PPO in this setting is doing something much closer to contextual bandit optimization than to long-horizon credit assignment. Preference data pushes the analogy further: learning a policy from pairwise comparisons rather than scalar rewards is the dueling bandit problem, formalized by Yisong Yue, Josef Broder, Robert Kleinberg and Thorsten Joachims ^[19], and the DPO paper places its method against that contextual dueling bandit literature explicitly ^[20].

Applications

Scroll sideways for more →

Two entries deserve expansion. Hyperband, by Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh and Ameet Talwalkar, formulates hyperparameter search as a pure-exploration non-stochastic infinite-armed bandit in which a resource such as training iterations or data samples is allocated adaptively across randomly sampled configurations, with early stopping for the losers. The authors report over an order-of-magnitude speedup against a set of Bayesian optimization competitors on deep learning and kernel problems ^[23]. Pure exploration differs from the standard formulation because there is no price for exploring: the objective is the simple regret of the single arm recommended at the end, not the reward accumulated along the way ^[7].

Clinical trials are the oldest motivation and the weakest track record. Sofía Villar, Jack Bowden and James Wason reviewed the Bayesian Bernoulli bandit models for treatment allocation and observed that "little of the resulting theory has ever been used in the actual design and analysis of clinical trials." Their evaluation found real advantages, in that bandit rules assign more patients to better treatments, alongside severe limitations in the statistical power of the resulting trial; they proposed a modified allocation rule aimed at removing that barrier ^[21].

Limitations

Adaptive allocation breaks standard statistical inference. The sample mean is biased on data collected by an adaptive design, and inverse propensity weighting estimators, the usual fix, become skewed and heavy-tailed as propensity scores decay toward zero. Vitor Hadad, David Hirshberg, Ruohan Zhan, Stefan Wager and Susan Athey developed adaptively reweighted estimators specifically to restore asymptotically correct coverage on bandit-collected data ^[22]. Anyone treating a bandit deployment as a source of clean effect estimates should read that literature first.

The practical obstacles are just as real. Available actions change from round to round, feedback can be delayed by many rounds, and the measured reward is rarely the actual objective, which typically involves user satisfaction, diversity, freshness and fairness alongside clicks ^[7]. Non-stationarity is a standing problem: the restless bandit model that captures it properly has resisted efficient algorithms with meaningful guarantees ^[7][24]. And bandits are silent on anything requiring foresight, since their defining assumption is that today's action does not constrain tomorrow's ^[7].

Bandits and large language models

Since 2025 the bandit and large language model literatures have converged from both directions, and dedicated surveys now map the intersection. Djallel Bouneffouf and Raphael Feraud surveyed how bandit algorithms improve LLM fine-tuning and prompt optimization and how LLMs supply contextual understanding to bandit policies ^[25]. Siguang Chen, Chunli Lv and Miao Xie published a component-based survey in January 2026 covering the span from pre-training through retrieval-augmented generation and personalization ^[26].

A prominent application is model routing. Choosing which model should answer a given query is a contextual bandit problem in the textbook sense: a context arrives, one arm is pulled, one noisy reward comes back. Recent systems include OrcaRouter, which pairs a LinUCB-style contextual bandit (one ridge regressor per arm) with a hybrid offline-online learning protocol ^[28], and formulations that add hard budget and soft latency constraints to the standard objective ^[29]. Prompt selection has been recast as a multi-objective pure-exploration bandit problem, with theoretical guarantees on the identification error in the linear case, in work published at ICLR 2026 ^[27]. The classical theory continues to develop in parallel. In July 2026 Mark Sellke and Gregory Valiant proved that in Bayesian bandit models whose arms are independent and evolve only when played, Thompson sampling makes at most twice the expected number of suboptimal selections of any other policy, confirming a 2014 conjecture of Guha and Munagala in which the factor of 2 is already best possible ^[30].

See also

• Reinforcement learning
• Markov decision process (MDP)
• Monte Carlo tree search
• A/B testing
• Recommender system
• Online learning

References

1. ^Thompson, W. R. "On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples." Biometrika 25(3-4):285-294, 1933. doi.org/...25.3-4.285
2. ^Robbins, H. "Some aspects of the sequential design of experiments." Bulletin of the American Mathematical Society 58(5):527-535, 1952. doi.org/...S0002-9904-1952-09620-8
3. ^Lai, T. L. and Robbins, H. "Asymptotically efficient adaptive allocation rules." Advances in Applied Mathematics 6(1):4-22, 1985. doi.org/...0196-8858(85)90002-8
4. ^Gittins, J. C. "Bandit Processes and Dynamic Allocation Indices." Journal of the Royal Statistical Society Series B 41(2):148-164, 1979. doi.org/...j.2517-6161.1979.tb01068.x
5. ^Auer, P., Cesa-Bianchi, N. and Fischer, P. "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning 47(2-3):235-256, 2002. doi.org/...A:1013689704352 (full text: cesa-bianchi.di.unimi.it/...ml-02.pdf)
6. ^Auer, P., Cesa-Bianchi, N., Freund, Y. and Schapire, R. E. "The Nonstochastic Multiarmed Bandit Problem." SIAM Journal on Computing 32(1):48-77, 2002. doi.org/...S0097539701398375
7. ^Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, 2020. tor-lattimore.com/...book.pdf and cambridge.org/...8E39FD004E6CE036680F90DD0C6F09FC
8. ^Bubeck, S. and Cesa-Bianchi, N. "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems." arXiv:1204.5721, 2012. arxiv.org/...1204.5721
9. ^Chapelle, O. and Li, L. "An Empirical Evaluation of Thompson Sampling." Advances in Neural Information Processing Systems 24 (NIPS 2011). papers.nips.cc/...8c28872a4505bdb51db06dc-Abstract
10. ^Agrawal, S. and Goyal, N. "Analysis of Thompson Sampling for the multi-armed bandit problem." arXiv:1111.1797, 2011-2012. arxiv.org/...1111.1797
11. ^Kaufmann, E., Korda, N. and Munos, R. "Thompson Sampling: An Asymptotically Optimal Finite Time Analysis." arXiv:1205.4217, 2012. arxiv.org/...1205.4217
12. ^Russo, D., Van Roy, B., Kazerouni, A., Osband, I. and Wen, Z. "A Tutorial on Thompson Sampling." Foundations and Trends in Machine Learning 11(1):1-96, 2018. arxiv.org/...1707.02038
13. ^Li, L., Chu, W., Langford, J. and Schapire, R. E. "A Contextual-Bandit Approach to Personalized News Article Recommendation." Proceedings of the 19th International Conference on World Wide Web (WWW 2010), 661-670. arxiv.org/...1003.0146 and doi.org/...1772690.1772758
14. ^Agarwal, A., Bird, S., Cozowicz, M., Hoang, L., Langford, J., Lee, S., Li, J., Melamed, D., Oshri, G., Ribas, O., Sen, S. and Slivkins, A. "Making Contextual Decisions with Low Technical Debt." arXiv:1606.03966, 2016-2017. arxiv.org/...1606.03966
15. ^Microsoft. "What is Personalizer?", "How Personalizer Works" and "Reinforcement Learning." Microsoft Learn. learn.microsoft.com/...what-is-personalizer and learn.microsoft.com/...how-personalizer-works and learn.microsoft.com/...epts-reinforcement-learning
16. ^Chandrashekar, A., Amat, F., Basilico, J. and Jebara, T. "Artwork Personalization at Netflix." Netflix Technology Blog, 7 December 2017. netflixtechblog.com/...ersonalization-c589f074ad76
17. ^Kocsis, L. and Szepesvári, C. "Bandit Based Monte-Carlo Planning." Machine Learning: ECML 2006, Lecture Notes in Computer Science, 282-293. doi.org/...11871842_29
18. ^Ouyang, L., Wu, J., Jiang, X., Almeida, D. et al. "Training language models to follow instructions with human feedback." arXiv:2203.02155, 4 March 2022. arxiv.org/...2203.02155
19. ^Yue, Y., Broder, J., Kleinberg, R. and Joachims, T. "The K-armed dueling bandits problem." Journal of Computer and System Sciences 78(5):1538-1556, 2012. doi.org/...j.jcss.2011.12.028
20. ^Rafailov, R., Sharma, A., Mitchell, E., Ermon, S., Manning, C. D. and Finn, C. "Direct Preference Optimization: Your Language Model is Secretly a Reward Model." arXiv:2305.18290, 2023-2024. arxiv.org/...2305.18290
21. ^Villar, S. S., Bowden, J. and Wason, J. "Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges." Statistical Science 30(2):199-215, 2015. doi.org/...14-STS504 and arxiv.org/...1507.08025
22. ^Hadad, V., Hirshberg, D. A., Zhan, R., Wager, S. and Athey, S. "Confidence intervals for policy evaluation in adaptive experiments." Proceedings of the National Academy of Sciences 118(15):e2014602118, 2021. doi.org/...pnas.2014602118 and arxiv.org/...1911.02768
23. ^Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A. and Talwalkar, A. "Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization." Journal of Machine Learning Research 18:1-52, 2018. arxiv.org/...1603.06560
24. ^Whittle, P. "Restless bandits: activity allocation in a changing world." Journal of Applied Probability 25(A):287-298, 1988. doi.org/...3214163
25. ^Bouneffouf, D. and Feraud, R. "Survey: Multi-Armed Bandits Meet Large Language Models." arXiv:2505.13355, May 2025. arxiv.org/...2505.13355
26. ^Chen, S., Lv, C. and Xie, M. "A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits." arXiv:2601.12945, January 2026. arxiv.org/...2601.12945
27. ^Li, D., Shi, C., Ou, W., Shen, C. and Yang, J. "Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits." ICLR 2026; arXiv:2605.14553. arxiv.org/...2605.14553
28. ^Bao, Z., Tian, F., Zhang, C., Chen, Z., Ma, X. and Shi, Y. "OrcaRouter: A Production-Oriented LLM Router with Hybrid Offline-Online Learning." arXiv:2605.30736, May 2026. arxiv.org/...2605.30736
29. ^Huang, Y., Liu, Q. and Xu, J. "Online LLM Selection via Constrained Bandits with Time-Varying Demand." arXiv:2606.17489, June 2026. arxiv.org/...2606.17489
30. ^Sellke, M. and Valiant, G. "Thompson Sampling Is 2-Competitive for Mistakes." arXiv:2607.12389, 14 July 2026. arxiv.org/...2607.12389