Upper Confidence Bound

AI and Machine Learning · Reinforcement Learning · 2002 · also: UCB, UCB1 · upper-confidence-bound.yaml

Pick the arm with the highest optimistic estimate: its mean plus a term that grows the less it has been tried. Exploration follows from uncertainty rather than from a coin flip, and the regret grows with the logarithm of time where a fixed exploration rate makes it linear.

• supersedescorrects · extends
• classifiesspecializes · part-of
• substitutes forapproximates · alternative-to
• depends onrequires · validates

Colour is the family; a dashed line is the second member of it.

This node

• correctsfixes a defect in Epsilon-Greedyuniform exploration keeps re-trying arms already measured as bad
• part-ofis a subtopic of Multi-Armed Bandit

Referenced by

• requiresMonte Carlo Tree Search does not work without thisevery node of the tree is its own bandit problem

References

• Finite-time Analysis of the Multiarmed Bandit Problem — Auer, Cesa-Bianchi, Fischer — 2002 · link