Upper Confidence Bound (UCB) Action Selection
What You'll Learn
You'll learn how UCB balances exploration and exploitation by selecting actions based on optimistic estimates that systematically favor uncertain options.
The Core Idea
While epsilon-greedy explores randomly, Upper Confidence Bound (UCB) is smarter: it explores actions strategically based on how uncertain we are about their value.
UCB adds an "exploration bonus" to each action's estimated value. Actions we've tried fewer times get a larger bonus, making them more attractive. As we gather more samples, the bonus shrinks, and we exploit what we've learned.
The UCB formula for action selection is:
A_t = argmax[Q(a) + c * sqrt(ln(t) / N(a))]
Where:
Q(a)is the current estimated value of actionaN(a)is how many times we've selected actionatis the total number of steps so farcis a confidence level parameter (typically √2)
How It Works
Think of UCB like choosing which restaurant to try. You have:
- Restaurant A: You've been 10 times, average rating 8/10
- Restaurant B: You've been once, rating 7/10
Epsilon-greedy would mostly pick A, occasionally B randomly. But UCB says: "B might actually be better—I'm just very uncertain because I've only tried it once. Let me add an 'optimism bonus' for my uncertainty and give it another shot."
As you visit B more, its uncertainty shrinks, and you naturally converge toward the truly better option.
Why UCB Matters
UCB eliminates wasteful random exploration. It explores actions with potential to be optimal, reducing the exploration-exploitation tradeoff to principled mathematics with provable guarantees.
Key Takeaway: UCB selects actions by adding an uncertainty bonus that decreases with experience, ensuring systematic exploration of promising but under-sampled actions without random waste.