Exploration with Upper Confidence Bounds

UCB explores by acting optimistically under uncertainty: prefer actions whose value might still be high.

Optimism in the face of uncertainty

The exploration-exploitation dilemma asks whether to take the currently best-looking action or try an uncertain one that might be better. Upper Confidence Bound (UCB) methods resolve it with a principle: act as if each action's value is at the top of its plausible range, so under-tried actions are automatically favored until their uncertainty shrinks.

The UCB1 rule

In the multi-armed bandit, UCB1 selects the arm maximizing mean_i + sqrt(2 ln t / n_i), where mean_i is the empirical mean, n_i the number of pulls, and t the total steps. The bonus is large for rarely pulled arms and decays as evidence accumulates. This yields logarithmic regret, provably near-optimal for stochastic bandits.

import math

def ucb1(means, counts, t):
    scores = []
    for i in range(len(means)):
        if counts[i] == 0:
            return i               # try every arm once
        bonus = math.sqrt(2*math.log(t)/counts[i])
        scores.append(means[i] + bonus)
    return scores.index(max(scores))

From bandits to full RL

The same optimism extends to sequential decisions. UCB drives the selection rule in Monte Carlo Tree Search (as UCT). Model-based RL algorithms build optimistic value functions by adding exploration bonuses to rewards for under-visited state-action pairs, giving formal regret bounds (UCRL, UCBVI). In deep RL, pseudo-count bonuses approximate the same idea in large state spaces.

Trade-offs

• Deterministic and principled, with strong regret guarantees in the bandit setting
• Requires a usable uncertainty estimate, which is hard in deep function approximation
• Sensitive to the exploration-bonus scale, the analog of the constant in UCB1

UCB and Thompson sampling are the two canonical answers to bandit exploration; UCB is frequentist and optimistic, Thompson sampling is Bayesian and randomized. Both aim at the same target: explore enough to find the best action, no more.