upper confidence bound

Exploration by optimism: act greedily with respect to the value estimate plus an uncertainty bonus.

$$A_t\doteq \underset{a}{\mathrm{argmax}}\left[Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}\right]$$

$Q_t(a)$ … current value estimate of action $a$
$N_t(a)$ … number of times $a$ has been selected so far
$c$ … controls the degree of exploration

The square-root term measures the uncertainty in $a$‘s value estimate. Each time $a$ is selected, $N_t(a)$ grows and its uncertainty (and degree of exploration) shrinks; each step $a$ is not selected, $t$ grows while $N_t(a)$ stays put, so its bonus slowly rises until it gets tried again.

The use of the natural logarithm means that the increases get smaller over time, but are unbounded; all actions will eventually be selected, but actions with lower value estimates, or that have already been selected frequently, will be selected with decreasing frequency over time.

---

exploration vs exploitation