The UCB Algorithm

The upper-confidence-bound algorithm handles the explore-exploit trade-off by playing the arm with the highest optimistic estimate of its reward.

Optimism in the face of uncertainty

UCB is built on a simple principle: act as if each arm is as good as its data plausibly allow. For each arm it forms an upper confidence bound, the sample mean plus a term that grows when the arm has been tried few times. It then plays the arm with the largest bound. An arm is attractive either because its observed mean is high (exploitation) or because it is under-explored and its bound is wide (exploration).

The bound

The standard UCB1 index for arm a after t rounds is the empirical mean of arm a plus sqrt( 2 ln t / n_a ), where n_a is the number of times arm a has been pulled. The added term is a confidence radius from a concentration inequality: it shrinks as n_a grows and widens (through ln t) as time passes without pulling the arm. This automatic bookkeeping means no explicit exploration schedule is needed.

import numpy as np

def ucb1(pull, K, T):
    counts = np.zeros(K); values = np.zeros(K)
    for a in range(K):                    # one pull of each arm first
        r = pull(a); counts[a]=1; values[a]=r
    for t in range(K, T):
        ucb = values + np.sqrt(2*np.log(t)/counts)
        a = int(np.argmax(ucb))
        r = pull(a); counts[a]+=1
        values[a] += (r-values[a])/counts[a]
    return values

Guarantee

UCB1 achieves regret that grows as O(ln T), matching the Lai-Robbins lower bound up to constants, so it is asymptotically optimal for stochastic bandits. The proof shows that any suboptimal arm is pulled only O(ln T) times before its confidence bound reliably falls below the best arm's mean. Crucially UCB is deterministic given the data and needs no tuning parameter, unlike epsilon-greedy.

Extensions

The optimism principle generalizes far beyond the basic bandit. LinUCB handles contextual bandits with linear reward models by maintaining confidence ellipsoids over parameters. UCT applies UCB to the nodes of a search tree and is the exploration rule inside Monte Carlo tree search, which powered strong game-playing programs. Wherever sequential decisions meet uncertainty, optimism-based confidence bounds are a reliable default.