Upper Confidence Bound

Upper Confidence Bound (UCB)

Class	Multi-armed bandit; Reinforcement learning
Data structure	Sequential reward observations
Worst-case performance	O(K) per round (K = number of arms)
Average performance	O(K)
Worst-case space complexity	O(K)

The Upper Confidence Bound (UCB) family of algorithms in machine learning and statistics is used to address the multi-armed bandit problem and the exploration-exploitation trade-off. UCB methods select actions based on optimistic estimates of their expected rewards, combining the empirical mean reward of each action with a confidence bonus that reflects uncertainty. This approach encourages exploration of less-sampled actions while exploiting those known to perform well.

The theoretical foundation for confidence-bound methods in stochastic bandits was established by Tze Leung Lai and Herbert Robbins in 1985, who derived logarithmic regret bounds. A widely used algorithm, UCB1, was later introduced by Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer in 2002.

UCB algorithms and their variants are widely applied in reinforcement learning, online advertising, recommender systems, clinical trials, and Monte Carlo tree search.

Background

The multi-armed bandit problem models a scenario where an agent chooses repeatedly among $K$ options ("arms"), each yielding stochastic rewards, with the goal of maximising 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 maximise payoff. Traditional $\epsilon$-greedy or SoftMax strategies use randomness to force exploration; UCB algorithms instead use statistical confidence bounds to guide exploration more efficiently.

The UCB1 algorithm

Behaviour of an UCB algorithm on a bandit run

UCB1 is a widely used bounded-reward variant of UCB introduced by Auer, Cesa-Bianchi and Fischer (2002). It maintains for each arm $i$:

• the empirical mean reward ${\hat{\mu }}_i$
• the count $n_i$ of times arm $i$ has been played.

At round $t$, it selects the arm maximising:

${\mathrm{U}\mathrm{C}\mathrm{B}\mathrm{1}}_i(t)={\hat{\mu }}_i+\sqrt{\frac{2\ln t}{n_i}}$

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

Pseudocode

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]

Theoretical properties

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

$R(n)=O\left(\sum _{i:{\mathrm{\Delta }}_i>0}\frac{\ln n}{{\mathrm{\Delta }}_i}\right),$

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

Variants

UCB2

Introduced in the same paper as UCB1, UCB2 divides plays into epochs controlled by a parameter $\alpha$, reducing the constant in the regret bound at the cost of more complex scheduling.

UCB1-Tuned

Incorporates empirical variance $V_i$ to tighten the bonus: ${\hat{\mu }}_i+\sqrt{\frac{\ln t}{n_i}\min \{1/4,V_i\}}.$ This often outperforms UCB1 in practice but lacks a simple regret proof.

KL-UCB

Replaces Hoeffding’s bound with a Kullback–Leibler divergence condition, yielding asymptotically optimal regret (constant = $1$) for Bernoulli rewards.

Bayesian UCB (Bayes-UCB)

Computes the $(1-\delta )$-quantile of a Bayesian posterior (e.g. Beta for Bernoulli) as the index. Proven asymptotically optimal under certain priors.

Contextual UCB (e.g., LinUCB)

Extends UCB to contextual bandits by estimating a linear reward model and confidence ellipsoids in parameter space.

Applications

• Online advertising & A/B testing: instead of sticking to a fixed traffic split, they gradually send more users toward better-performing options, which can improve conversion rates over time.

• Monte Carlo Tree Search: in UCT, UCB1 is applied at each node to help decide which branches to explore next, something that has been key in game-playing systems like Go.

• Adaptive clinical trials: patients tend to be assigned more often to treatments that are showing better results so far, often leading to improved outcomes compared to pure random assignment.

• Recommender systems: helps in choosing personalised content while still handling uncertainty in user preferences.

• Robotics & control: supports efficient exploration when the system is dealing with unknown or changing dynamics.

See also

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

References

This article "Upper Confidence Bound" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Upper Confidence Bound. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---