Upper Confidence Bound

The multi-armed bandit problem models a scenario where an agent chooses repeatedly among ${\displaystyle K}$ options ("arms"), each yielding stochastic rewards, with the goal of maximizing the sum of collected rewards over time. The main challenge is the exploration–exploitation trade-off: the agent must explore lesser-tried arms to learn their rewards, yet exploit the best-known arm to maximize payoff.^[3] Traditional ${\displaystyle \varepsilon }$-greedy or softmax strategies use randomness to force exploration; UCB algorithms instead use statistical confidence bounds to guide exploration more efficiently.^[2]

UCB1, the original UCB method, maintains for each arm ${\displaystyle i}$:

• the empirical mean reward ${\displaystyle {\hat {\mu }}_{i}}$,
• the count ${\displaystyle n_{i}}$ of times arm ${\displaystyle i}$ has been played.

At round ${\displaystyle t}$, it selects the arm maximizing:

${\displaystyle \mathrm {UCB1} _{i}(t)={\hat {\mu }}_{i}+{\sqrt {\frac {2\ln t}{n_{i}}}}}$

Arms with ${\displaystyle n_{i}=0}$ are initially played once. The bonus term ${\displaystyle {\sqrt {2\ln t/n_{i}}}}$ shrinks as ${\displaystyle n_{i}}$ grows, ensuring exploration of less-tried arms and exploitation of high-mean arms.^[1]

for each arm i:
    n[i] ← 0; Q[i] ← 0
for t from 1 to T do:
    for each arm i do
        if n[i] = 0 then
            select arm i
        else
            index[i] ← Q[i] + sqrt((2 * ln t) / n[i])
    select arm a with highest index[a]
    observe reward r
    n[a] ← n[a] + 1
    Q[a] ← Q[a] + (r - Q[a]) / n[a]

Auer et al. proved that UCB1 achieves logarithmic regret: after ${\displaystyle n}$ rounds, the expected regret ${\displaystyle R(n)}$ satisfies

${\displaystyle R(n)=O{\Bigl (}\sum _{i:\Delta _{i}>0}{\frac {\ln n}{\Delta _{i}}}{\Bigr )},}$

where ${\displaystyle \Delta _{i}}$ is the gap between the optimal arm’s mean and arm ${\displaystyle i}$’s mean. Thus, average regret per round tend to ${\displaystyle 0}$ as ${\displaystyle n\to +\infty }$, and UCB1 is near-optimal against the Lai-Robbins lower bound.^[1][4]

Several extensions improve or adapt UCB to different settings:

UCB algorithms’ simplicity and strong guarantees make them popular in:

• Online advertising & A/B testing: adaptively allocate traffic to maximize conversion rates without fixed split ratios.^[3]
• Monte Carlo Tree Search: UCT uses UCB1 at each tree node to guide exploration in games like Go.^[9][10]
• Adaptive clinical trials: assign patients to treatments with highest upper confidence on success, improving outcomes over randomization.^[11]
• Recommender systems: personalized content selection under uncertainty.
• Robotics & control: efficient exploration of unknown dynamics.

• Multi-armed bandit
• Reinforcement learning
• Monte Carlo tree search