upper confidence bound
In plain wordsA 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.
A family of banditmulti-armed bandit, n.: A 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. algorithms implementing 'optimism in the face of uncertainty': each arm is scored by an upper confidence bound on its mean 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. — its empirical average plus a bonus that shrinks as the arm is tried more — and the arm with the highest bound is played. An arm is chosen either because it looks good or because it is uncertain, and trying it either confirms its value or tightens its bound, so exploration is directed rather than random. The classic UCB1 bonus is √(2 ln t / n_k), where n_k counts the pulls of arm k after t rounds; it guarantees logarithmic 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. without prior knowledge. Variants include KL-UCB, LinUCB for contextual bandits and UCRL for MDPs. Applied recursively to game trees as UCT, and in the PUCT form used by AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs., it is the selection rule 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..
UCB tried the new arm repeatedly at first because its confidence interval was so wide.
Origin
Tze Leung Lai and Herbert Robbins (1985) built the first index policies based on upper confidence bounds; Rajeev Agrawal (1995) simplified them, and Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer's 'Finite-time Analysis of the Multiarmed Bandit Problem' (Machine Learning, 2002) introduced the widely used UCB1. Levente Kocsis and Csaba Szepesvári's UCT (2006) carried the idea into tree search.
Usage note
In RL papers 'UCB' almost always means this algorithm or its exploration bonus, not merely the upper end of a confidence interval.
Related
- multi-armed banditmulti-armed bandit, n.: A 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.
- 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.
- 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.
- 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.
- 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.
- intrinsic motivationintrinsic motivation, n.: Giving an AI agent an inner drive — such as curiosity about surprising things — so it keeps exploring and learning even when the task itself offers no reward yet.
- 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.
Sources
- Auer, P., Cesa-Bianchi, N. & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47, 235–256.
- Lai, T. L. & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6(1), 4–22.
Mentioned in
Bayesian optimizationBayesian optimization, n.: A smart way to tune settings when each test is expensive: build a statistical guess of how settings affect results, then try whichever setting that guess says is most promising next., 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., 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., multi-armed banditmulti-armed bandit, n.: A 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., 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.