multi-armed bandit
In plain wordsA puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others.
A sequential decision problem of allocating a series of trials among K options ('arms') whose rewardreward, n.: The score an AI system receives after an action, telling it how good the outcome was. Reinforcement learning trains the system to collect as much reward as possible over time. distributions are unknown, so as to maximize the total reward collected or, equivalently, to minimize regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying. relative to always choosing the best arm. It is the simplest setting that exhibits the exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one.: a reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time. problem with a single statestate, n.: A snapshot of the situation an AI agent is in — for a chess program, the arrangement of pieces and whose turn it is — containing what it needs to decide what to do next., whose actions have no lasting consequences. Standard algorithms include ε-greedyepsilon-greedy, adj.: A simple rule for balancing trying new things against using what works: most of the time take the best-known option, but a small fraction of the time pick at random., UCBupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance. and Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far.; the Gittins index solves the discounted Bayesian version exactly. Variants include contextual bandits, in which the best arm depends on observed features such as a user or query, and adversarial, dueling and combinatorial bandits. Bandits drive adaptive clinical trials, ad and news selection, recommendationsrecommender system, n.: Software that guesses which songs, products, posts or jobs you are most likely to want and shows those first, as when a video app lines up the next clip or a shop suggests an add-on., adaptive A/B testingA/B testing, n.: Comparing two versions of something — two models, two prompts, two designs — by randomly showing each to different groups of real users and measuring which works better., hyperparameter tuninghyperparameter tuning, n.: Trying out different settings for a model's training, such as learning speed or model size, and keeping the combination that performs best on data held back for checking. and the selection step of Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average..
Instead of a fixed A/B test, we ran a contextual bandit that shifted traffic to the better headline within hours.
Origin
Herbert Robbins posed the modern formulation in 'Some Aspects of the Sequential Design of Experiments' (1952), after William Thompson's 1933 work on comparing two unknown probabilities. The name alludes to slot machines, nicknamed one-armed bandits; 'two-armed bandit' appears in 1950s learning-theory research. John Gittins's index theorem (1979) and Tze Leung Lai and Robbins's regret bound (1985) founded the theory.
Usage note
The problem's reputation for difficulty is old: Peter Whittle recalled that Allied analysts in the Second World War found it so draining that someone suggested dropping it over Germany as a form of intellectual sabotage.
Related
- exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one.
- regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.
- Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far.
- upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.
- epsilon-greedyepsilon-greedy, adj.: A simple rule for balancing trying new things against using what works: most of the time take the best-known option, but a small fraction of the time pick at random.
- A/B testingA/B testing, n.: Comparing two versions of something — two models, two prompts, two designs — by randomly showing each to different groups of real users and measuring which works better.
- recommender systemrecommender system, n.: Software that guesses which songs, products, posts or jobs you are most likely to want and shows those first, as when a video app lines up the next clip or a shop suggests an add-on.
Sources
- Robbins, H. (1952). Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society 58(5), 527–535.
- Lai, T. L. & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6(1), 4–22.
- Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
Mentioned in
A/B testingA/B testing, n.: Comparing two versions of something — two models, two prompts, two designs — by randomly showing each to different groups of real users and measuring which works better., active learningactive learning, n.: A way to train a model with fewer labeled examples by letting it choose which unlabeled examples a person should label next, usually the ones it is most unsure about., cold start problemcold start problem, n.: The trouble a recommendation system has with brand-new users or items: with no history to learn from, it has little basis for good suggestions., epsilon-greedyepsilon-greedy, adj.: A simple rule for balancing trying new things against using what works: most of the time take the best-known option, but a small fraction of the time pick at random., exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one., online learningonline learning, n.: Learning from data that arrive one piece at a time, updating the model after each new example instead of training once on a fixed collection, as a spam filter does while emails stream in., HyperbandHyperband, n.: A tuning method that starts many candidate settings on small budgets, keeps only the most promising ones, and gives the survivors more training time, so effort isn't wasted on losers., regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying., Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far., upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.