Course contentsShow
← Machine Learning and Deep Learning
Lesson 2190 of 3,53847. Reinforcement Learning: Temporal Difference MethodsFree lesson

UCB Formula and Confidence Intervals

Deriving the UCB formula with logarithmic bonus terms that balance value estimates and uncertainty.

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.