upper confidence bound (UCB)

UCB makes optimism precise. For each action it adds two things: the action's estimated value, plus a bonus that is large when the action has been tried only a few times and shrinks as evidence accumulates. The agent then simply picks the action with the highest sum. Early on the bonus dominates and drives the agent to sample everything; later the values dominate and it exploits the genuine best.

The bonus is an upper confidence interval on the value — roughly, the best the action could plausibly be given how little we have seen of it. By always choosing the action with the highest plausible value, UCB explores exactly where it might be wrong and stops once it is confident. In the bandit setting this earns it tight, near-optimal regret guarantees; extending it to full reinforcement learning with large state spaces is harder, which is what count-based and pseudo-count bonuses try to approximate.