Upper Confidence Bound

[WARNING] Could not convert TeX math \mathrm{UCB1}_i(t) = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}}, rendering as TeX [WARNING] Could not convert TeX math \sqrt{2 \ln t / n_i}, rendering as TeX [WARNING] Could not convert TeX math R(n) = O\Bigl(\sum_{i:\Delta_i>0} \frac{\ln n}{\Delta_i}\Bigr),, rendering as TeX: R(n) = O\Bigl(\sum_{i:\Delta_i>0} \frac{ ^ unexpected control sequence \Bigl expecting "%", "\\label", "\\tag", "\\nonumber", whitespace or "\\allowbreak" [WARNING] Could not convert TeX math \hat\mu_i + \sqrt{\frac{\ln t}{n_i}\min\{1/4,\,V_i\}}., rendering as TeX

The Upper Confidence Bound (UCB) family of algorithms in machine learning and statistics is used to solve the multi-armed bandit problem and deal with the exploration-exploitation trade-off. UCB methods choose what to do by figuring out how likely each action is to get a reward, which balances trying out new options with taking advantage of ones that have worked well in the past. Confidence-bound methods for stochastic bandits originated from the research of Tze Leung Lai and Herbert Robbins in 1985, with the inaugural UCB algorithm developed by Lai in 1987. UCB and its variations have become common methods 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 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. Traditional ε-greedy or SoftMax strategies use randomness to force exploration; UCB algorithms instead use statistical confidence bounds to guide exploration more efficiently.

The UCB1 algorithm

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 μ̂_i,
• the count n_i of times arm i has been played.

At round t, it selects the arm maximizing:

$\mathrm{UCB1}_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\Bigl(\sum_{i:\Delta_i>0} \frac{\ln n}{\Delta_i}\Bigr),$

where Δ_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 →  + ∞, and UCB1 is near-optimal against the Lai-Robbins lower bound.

UCB2

Introduced in the same paper as UCB1, UCB2 divides plays into epochs controlled by a parameter α, 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−δ)-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 personalized 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