UCB Exploration Index Causal Trace
An exploration bonus can revisit an option that looked bad early, while the greedy policy keeps trusting its first impressions.
Free theory articleAn exploration bonus can revisit an option that looked bad early, while the greedy policy keeps trusting its first impressions.
Concept & interpretation
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.
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.