ε-greedy, UCB & Thompson Sampling

Solving the classic Exploration vs Exploitation trade-off in decision systems, recommendation feeds, and multi-armed bandits.

🟡 intermediate5 min readrlbandits

Exploration vs Exploitation is the fundamental dilemma in Reinforcement Learning and recommendation systems: should the agent Exploit the current best-known action to maximize short-term reward, or Explore unknown actions to discover potentially higher long-term rewards? Key strategies include ε-greedy (random uniform exploration), Upper Confidence Bound (UCB - Optimism in the face of uncertainty), and Thompson Sampling (Bayesian posterior probability matching).

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

Question 1 of 3

What is the core principle of the Upper Confidence Bound (UCB1) algorithm?

More in Reinforcement Learning

See all →

Value-Based vs Policy-Based Methods5 min Multi-Armed Bandits4 min Proximal Policy Optimization5 min