Upper Confidence Bound Bandit Algorithm

UCB is an algorithm built around the idea of “Optimism in the face of uncertainty”, i.e. we estimate uncertainty of a value, and we prefer to explore states/actions with highest uncertainty.

https://towardsdatascience.com/the-upper-confidence-bound-ucb-bandit-algorithm-c05c2bf4c13f

$A_t={\text{argmax}}_a\left[Q_t(a)+c\sqrt{\frac{\log t}{N_t(a)}}\right]$

• the number $c>0$ controls the degree of exploration
• $N_t(a)$ will be very small for the actions that haven’t been tried much, so this is how the agent is encouraged to try various actions until all actions have been tried enough times

Intuitively, the square-root term is a measure of the uncertainty or variance in the estimate of $a$’s value.

Next

• Thompson Sampling
• UCT