What is Upper Confidence Bound?
Upper Confidence Bound is an optimism-based action-selection principle that chooses the option with the largest plausible reward, usually an empirical estimate plus an uncertainty bonus.
Quick Facts
| Specification | Official Specification |
|---|
How It Works
Optimism converts uncertainty into directed exploration
A common stochastic-bandit index is an empirical mean plus a radius that grows with log(t) and shrinks with the arm's pull count. Untried or poorly measured actions therefore receive attention without a separate random-exploration coin. Auer, Cesa-Bianchi, and Fischer gave finite-time analysis for UCB1 and related policies with bounded, stationary rewards.
The guarantee belongs to a specific model
UCB1's logarithmic instance-dependent regret assumes independent draws from fixed bounded reward distributions. Heavy tails, changing means, dependence, delayed attribution, censored feedback, contextual misspecification, or a tuned bonus can invalidate that conclusion. KL-UCB uses distribution-aware divergence, UCB-V uses variance information, and LinUCB builds a linear contextual confidence region; their formulas and guarantees are not interchangeable.
Validate the confidence mechanism, not only reward
Track empirical means, bonuses, pull counts, action gaps, realized reward, pseudo-regret in simulation, unsafe selections, and recovery after a controlled change. Run repeated seeds and compare with greedy, epsilon-greedy, and Thompson Sampling under the same horizon and delay process. Bubeck and Cesa-Bianchi distinguish instance-dependent and minimax analyses, preventing one favorable asymptotic rate from becoming a universal performance claim.
Key Characteristics
- Scores each action by estimated value plus an exploration bonus
- Uses optimism to direct exploration toward plausible high-value actions
- Shrinks uncertainty as relevant observations accumulate
- Has variants for bounded, variance-aware, contextual, and kernel settings
- Requires confidence assumptions that match reward and noise behavior
- Can be deterministic after initialization and tie-breaking are specified
Common Use Cases
- Allocating traffic among bounded stationary alternatives
- Exploring recommendations with uncertainty-aware scores
- Selecting contextual actions with a validated linear reward model
- Choosing expensive evaluations with a Gaussian Process surrogate
- Building an auditable exploration baseline for online experiments
Example
Loading code...Frequently Asked Questions
How does Upper Confidence Bound balance exploration and exploitation?
The estimated mean favors actions that have performed well, while the uncertainty bonus favors actions with limited evidence. The policy chooses the largest sum. As an action is observed more often, its bonus usually shrinks, so unsupported possibilities are tested without permanent uniform exploration.
Is a UCB score a calibrated confidence interval?
Only when the estimator, radius, probability level, and data assumptions justify that interpretation. Many implementations tune a UCB-like bonus as a heuristic. Calling such a score a statistical confidence bound without checking boundedness, dependence, adaptivity, and multiple-round coverage is misleading.
What is the difference between UCB and Thompson Sampling?
UCB chooses an optimistic upper estimate, often deterministically after tie-breaking. Thompson Sampling draws a plausible model from a posterior and acts optimally for that draw. Both use uncertainty, but their assumptions, randomization, diagnostics, and failure modes differ.
How should UCB handle an arm with zero observations?
The formula must not divide by zero. Common implementations pull every eligible arm once, assign an infinite initial index, or use a prior or regularized model. The choice affects cold-start exposure and must still respect safety and eligibility constraints.
Does UCB work when rewards drift over time?
Classical UCB1 assumes fixed arm means. Under drift, old observations can make the estimate and confidence radius misleading. Sliding-window, discounted, change-detection, or explicitly nonstationary variants may help, but they require a new comparator and validation against the expected drift process.