ε-greedy, UCB & Thompson Sampling
Solving the classic Exploration vs Exploitation trade-off in decision systems, recommendation feeds, and multi-armed bandits.
The Exploration-Exploitation Dilemma
THE DECISION DILEMMA
┌───────────────────────────────────────┬───────────────────────────────────────┐
│ EXPLOITATION │ EXPLORATION │
├───────────────────────────────────────┼───────────────────────────────────────┤
│ Pick action with highest known reward.│ Pick under-sampled action to gain │
│ Maximizes short-term revenue. │ new information. │
│ Risk: Misses hidden optimal action! │ Risk: Wastes short-term user clicks. │
└───────────────────────────────────────┴───────────────────────────────────────┘
Three Core Exploration Strategies
1. $\epsilon$-Greedy
- With probability $1 - \epsilon$: Exploit ($\arg\max_a \hat{Q}(a)$).
- With probability $\epsilon$: Explore (Sample uniformly at random across all $|A|$ arms).
Drawback: Explores all suboptimal arms equally, even those known to be terrible.
2. Upper Confidence Bound (UCB1)
Principle: Optimism in the Face of Uncertainty.
$$a_t = \arg\max_{a \in A} \left[ \hat{Q}(a) + c \cdot \sqrt{\frac{\ln N}{N_a}} \right]$$
- $\hat{Q}(a)$: Empirical mean reward of arm $a$.
- $N$: Total steps taken so far.
- $N_a$: Number of times arm $a$ has been pulled.
- As $N_a \to 0$, uncertainty term explodes $\to \infty$, forcing exploration!
Arm A (Sampled 100 times): Mean = 0.70, Bonus = 0.05 ──► Upper Bound = 0.75
Arm B (Sampled 2 times): Mean = 0.50, Bonus = 0.40 ──► Upper Bound = 0.90 (WINNER -> Explore B!)
3. Thompson Sampling (Bayesian Posterior Sampling)
Maintains Beta distribution $\text{Beta}(\alpha_a, \beta_a)$ prior for each binary arm $a$:
- For each arm $a$, sample $\theta_a \sim \text{Beta}(\alpha_a, \beta_a)$.
- Pull arm $a^* = \arg\max_a \theta_a$.
- Observe reward $r \in {0, 1}$. Update: $\alpha_{a^} \leftarrow \alpha_{a^} + r$, $\beta_{a^} \leftarrow \beta_{a^} + (1-r)$.
Strategy Comparison Matrix
| Strategy | Exploration Type | Regret Bound | Best Use Case |
|---|---|---|---|
| $\epsilon$-Greedy | Random Uniform | Linear $O(T)$ (unless $\epsilon_t \to 0$) | Simple baseline, low-overhead systems |
| UCB1 | Deterministic Optimism | Logarithmic $O(\ln T)$ | Cold-start news / ad ranking feeds |
| Thompson Sampling | Bayesian Probability Matching | Logarithmic $O(\ln T)$ | E-commerce recommendations, A/B testing |
Say this out loud
"Exploration vs Exploitation balances short-term reward against long-term learning. ε-greedy explores via uniform random sampling. UCB1 implements 'Optimism in the face of uncertainty', adding an upper confidence bound bonus c√(ln N / N_a) to under-sampled arms. Thompson Sampling samples from Bayesian posterior distributions Beta(α,β), offering state-of-the-art logarithmic regret in production recommendation engines."
Follow-ups to expect
- What is Cumulative Regret? The total loss in reward incurred by playing suboptimal arms compared to playing the true optimal arm continuously: $\text{Regret}(T) = T \cdot \mu^* - \sum_{t=1}^T \mathbb{E}[\mu_{a_t}]$.
- How does Thompson Sampling handle continuous contextual features? Use LinUCB or Neural Thompson Sampling, where a linear regression or neural network predicts reward distributions conditioned on user context vectors $x$.
Check yourself
What is the core principle of the Upper Confidence Bound (UCB1) algorithm?