Does UCB1 require a Bayesian prior?

No. The standard algorithm uses empirical means, counts and a concentration-based bonus.

What happens to an untried action?

It must be explored before applying the usual formula, which would otherwise divide by zero.

Is it a contextual bandit algorithm?

The basic version does not condition its action values on features of the current user or situation.

AI Glossary / Graphs and symbolic AI / Advanced

UCB1

Definition

UCB1 is a multi-armed bandit algorithm that selects an action using its average observed reward plus an exploration bonus. The bonus favors actions with fewer observations. It balances using apparently good options with gathering evidence about options that remain uncertain.

What it means

A bandit problem repeatedly offers several actions but reveals a reward only for the action chosen. Early outcomes can be misleading. Always choosing the currently best average can abandon an option after an unlucky beginning, while uniform exploration can waste opportunities after differences become clear.

UCB1 uses optimistic scores to address this tradeoff. Its classic analysis assumes a stationary stochastic setting with independent rewards and a known bounded range, conventionally zero to one. The result concerns expected cumulative regret under those assumptions, not a guarantee of selecting the best action on every round.

The name refers to an upper-confidence-bound approach. Its selection index is not a probability that an action is best, and it can exceed one even when all observed rewards lie between zero and one.

How it works

Initially try every action so that each has an observation. Thereafter, keep each action's count n_i and sample mean m_i. Let n be the total number of completed selections. A standard UCB1 index for the next selection is m_i + sqrt(2 ln(n)/n_i), using the natural logarithm.

Choose an action with the largest index, observe its reward and update its count and mean. The mean rewards exploitation. The bonus is larger for a less-tested action and shrinks as its own count grows, while the total-count term prevents neglected actions from being forgotten indefinitely.

The classic guarantee uses bounded stationary reward distributions. Changing rewards, delayed observations, user-specific contexts or unbounded values require additional treatment and may call for a different method. Rescaling rewards also requires consistent treatment of the exploration term; arbitrary units should not be inserted into the standard formula without thought.

Three practical examples

A simulation allocates repeated trials among fixed strategies whose reward distributions are deliberately held stationary.
A teaching recommendation experiment compares UCB1 with a greedy rule to illustrate the effect of early unlucky outcomes.
A search researcher uses UCB1 as a starting point for understanding bandit-based action selection inside a tree-search method.

Think of it this way

Think of trying several unfamiliar routes and keeping both their average performance and how little experience you have with them in mind. A route with limited evidence may deserve another trial even when its current average is lower.

The analogy assumes a stable comparison. Traffic changing by hour or different destinations would violate a simple stationary-route model. UCB1 does not automatically infer those contexts or turn an exploration bonus into a forecast.

Worked example

Selecting a less-tested option

Suppose twenty trials have been completed. Action A was selected sixteen times with total reward ten, so its mean is 10/16=0.625. Action B was selected four times with total reward two, so its mean is 2/4=0.5.

Using ln(20)≈2.996, A's bonus is sqrt(2×2.996/16)≈0.612. Its index is approximately 1.237. B's bonus is sqrt(2×2.996/4)≈1.224, giving an index of approximately 1.724.

UCB1 therefore chooses B next despite its lower observed mean. The reason is its larger exploration bonus. The indices above one are valid selection scores, not estimated success probabilities.

If B then receives reward one, its updated count is five and total reward is three, giving a new mean of 0.6. The next calculation uses twenty-one completed trials and the updated counts; it does not reuse the old score unchanged.

Illustrative case study

Fictional Alder Experiments tests alternative scheduling heuristics in a controlled simulator. It uses UCB1 to allocate runs, with rewards mapped consistently into zero to one and the simulator's conditions held fixed.

Later, the team changes the workload halfway through an experiment. It recognizes that the accumulated averages now mix different reward conditions, so the original stationary interpretation no longer directly applies. It separates the evaluation of changing workloads rather than attributing every outcome to the classic guarantee.

The fictional case illustrates assumption checking. It contains no reported commercial uplift and does not establish that UCB1 is the best allocation method for the team's eventual deployment.

Common misconceptions and mistakes

UCB1 always chooses the highest observed average. A larger uncertainty bonus can make another action preferable.
Its index is a success probability. It is an optimistic selection score and can exceed the reward range.
Logarithmic regret means no bad selections occur. The bound describes expected cumulative performance under assumptions, including purposeful exploration.

Business use

UCB1 is useful as a transparent baseline for sequential allocation when the feedback and stability assumptions reasonably fit. It makes the exploration decision explicit and requires only simple action statistics.

Define the reward carefully and inspect whether it reflects the objective. Keep track of missing or delayed outcomes and changes in the environment. Compare cumulative performance and learning behavior under representative conditions. A theoretical regret guarantee does not replace evaluation of the actual application, especially when the available actions or reward distributions change.

Check your understanding

Two actions have the same observed mean, but one has been tried much less often. Which has the higher UCB1 index, with the same total count?

Answer: The less-tested action, because its smaller denominator produces a larger exploration bonus.

Related terms

Upper confidence bound
Regret
Sample mean
Thompson sampling
UCT
Multi-armed bandit
exploration and exploitation
contextual bandit

Learn next

Read multi-armed bandits and regret. Recalculate the worked example after several new rewards and separate changes in the empirical mean from changes in the exploration bonus.

Sources

Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, 2002: https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf

Levente Kocsis and Csaba Szepesvári, Bandit based Monte-Carlo Planning, Section 2.2 restating UCB1: https://aima.cs.berkeley.edu/~russell/classes/cs294/s11/readings/Kocsis%2BSzepesvari%3A2006.pdf

Relevant original assumptions, selection formula and regret statements were read. The twenty-trial calculation is original and rounded for readability; no experimental run or unrestricted performance guarantee is claimed.

Previous: U-Net Next: UCT