Upper Confidence Bound

Upper Confidence Bound (UCB)

UCB Action Selection

$A_t=\arg {\max }_a\left[Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}\right]$

where:

• $Q_t(a)$ — estimated value (exploitation term)
• $c\sqrt{\frac{\ln t}{N_t(a)}}$ — exploration bonus (decreases as action $a$ is tried more)
• $N_t(a)$ — number of times action $a$ has been selected
• $c>0$ — controls degree of exploration

Optimism in the Face of Uncertainty

UCB adds a bonus to actions that haven’t been tried much. The less you know about an action, the higher its bonus. As you try it more, the bonus shrinks. This systematically explores uncertain options before settling on the best.

More principled than Epsilon-Greedy Policy — preferentially explores uncertain actions rather than exploring uniformly at random.

Appears In

• RL-L01 - Intro, MDPs & Bandits, RL-Book Ch2 - Multi-Armed Bandits