UCB Exploration Index Causal Trace

In multi-armed bandit problems, a greedy algorithm may get stuck on a suboptimal arm simply because its early pulls were unlucky. The Upper Confidence Bound (UCB) algorithm adds an exploration bonus that scales with the natural logarithm of the round number divided by the number of times an arm has been pulled. This ensures all arms are eventually explored while still favoring historically high-reward arms.

Worked Example

Consider three arms with predetermined reward streams. In the first three rounds, the algorithm deterministically tries each arm once to establish initial counts. Suppose after round 4, the history is:

Arm 1: pulled twice, rewards [1, 0]. Mean = 0.5.
Arm 2: pulled once, reward [0]. Mean = 0.
Arm 3: pulled once, reward [0]. Mean = 0.

At round 5, we compute the UCB score for Arm 1 using a bonus multiplier of 1. The formula is:

UCB_1 = mean_1 + 1 * sqrt(2 * ln(5) / 2) = 0.5 + sqrt(2 * 1.609 / 2) = 0.5 + sqrt(1.609) = 0.5 + 1.268 = 1.768

This elevated score means Arm 1 could be chosen again, or if its mean was lower, an unexplored arm might temporarily exceed it.

Experiment

In the interactive module, you can trace this exact behavior step-by-step.

Select Reward streams to "Early trap" to establish a scenario where the first option starts poorly.
Set the Bonus multiplier to 1, and set Pulls to 4 to observe the exact behavior seen in the worked example.
Observe the Arm one pull count and Arm one UCB score for next round which evaluate to 2 and approximately 1.7686, respectively.
Changing the bonus multiplier to 0 demonstrates how the algorithm fails to explore effectively without the bonus term.

Limitations

This causal trace uses fixed, finite sequences of rewards to illustrate path-dependence and step-by-step logic. It is not a numerical proof of the UCB1 algorithm's logarithmic regret bound, which applies to independent identically distributed stochastic environments. These hand-picked streams demonstrate the mechanics of the bonus term but offer no artificial regret guarantees.

References

Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem.Machine Learning, 47, 235-256.

UCB Exploration Index Causal Trace