UCB Formula and Confidence Intervals
You'll learn how the UCB formula mathematically balances exploitation and exploration using confidence intervals.
The Core Idea
Upper Confidence Bound (UCB) action selection doesn't just pick actions randomly (like epsilon-greedy). Instead, it assigns each action an optimistic value estimate by adding a bonus term that represents uncertainty. Actions tried fewer times get larger bonuses, encouraging exploration of under-sampled options.
The standard UCB formula is:
UCB(a) = Q(a) + c * sqrt(ln(t) / N(a))
Where:
- Q(a) = current value estimate for action a (exploitation term)
- c = exploration constant controlling the confidence level
- t = total number of steps taken so far
- N(a) = number of times action a has been selected
Why This Works
Think of the bonus term as a "benefit of the doubt." If you've only tried an action once or twice, you're very uncertain about its true value—so the algorithm gives it an optimistic boost. The sqrt(ln(t) / N(a)) term:
- Grows as total time t increases (more exploration opportunity)
- Shrinks as N(a) increases (less uncertainty about this action)
- Uses logarithmic growth to balance exploration without being too aggressive
The confidence interval interpretation: UCB essentially constructs an upper confidence bound on the true action value, then picks whichever action has the highest upper bound—optimism in the face of uncertainty.
Key Takeaway: The UCB formula adds a mathematically principled exploration bonus that automatically decreases as actions are sampled more, creating a confidence-interval-driven balance between trying promising actions and exploring uncertain ones.