Exploration and multi-armed bandits: ε-greedy, UCB and Thompson sampling

Before this lesson: lesson 01 (actions and rewards); foundations 08 (means and randomness). The proofs use Hoeffding's inequality (probability 07) and Beta–Bernoulli updating (probability 10); we restate both here. Time: about 70 minutes, plus the notebook.

---

Why this matters #

Lesson 01 assumed that we know the rewards and transitions of the MDP. From now on the agent learns from samples, and then it must explore. A bandit is an MDP with one state, so it isolates this problem: there are no transitions and no delayed rewards, only the choice between trying and using.

• Every RL agent explores. DQN uses ε-greedy (lesson 05 and lesson 06); policy-gradient methods and SAC add an entropy bonus (lesson 08); Monte Carlo tree search in AlphaGo and AlphaZero chooses moves with a UCB-type rule at every node (lesson 10).
• Bandits are used directly. Adaptive A/B tests, news and product recommendation (LinUCB for the Yahoo! front page, Li et al. 2010), ad placement, adaptive clinical trials, and the choice of the next experiment in Bayesian optimization (GP-UCB).
• Hyperparameter search. Successive halving and Hyperband treat each configuration as an arm and stop the bad ones early.

1. Predict first #

2. The picture #

One state, K arms #

A $K$-armed bandit has arms $a = 1, \dots, K$. Pulling arm $a$ gives a random reward in $[0, 1]$ with an unknown mean $\mu_a$. Rewards of different pulls are independent. In our examples the arms are Bernoulli: arm $a$ pays 1 with probability $\mu_a$ and 0 otherwise.

• The best mean is $\mu^* = \max_a \mu_a$.
• The gap of arm $a$ is $\Delta_a = \mu^* - \mu_a \ge 0$. The best arm has gap 0.
• In round $t$ the agent pulls arm $a_t$ and receives the reward $r_t$.
• $n_a(t)$ is the number of pulls of arm $a$ in the first $t$ rounds.

Estimating a mean, one sample at a time #

The natural estimate of $\mu_a$ is the sample mean of the rewards of arm $a$. We do not need to store all rewards. Let $Q_k$ be the mean of the first $k$ rewards $x_1, \dots, x_k$. Then

1. $k\, Q_k = x_1 + \dots + x_k = (k-1) Q_{k-1} + x_k$;
2. divide by $k$: $Q_k = Q_{k-1} - \frac{1}{k} Q_{k-1} + \frac{1}{k} x_k$, that is,

Read it as new estimate = old estimate + step size × (target − old estimate). The same form returns in TD learning (lesson 04) and in Q-learning (lesson 05).

With a constant step size $\alpha \in (0, 1]$ instead of $1/k$, unrolling the update gives

The weights add up to 1 (including the weight $(1-\alpha)^k$ of the start value $Q_0$), and they shrink geometrically for older samples. This exponential recency-weighted average follows a mean that changes over time (a nonstationary problem), but it never settles: it keeps moving with the newest samples. The step sizes $1/k$ satisfy the conditions $\sum_k \alpha_k = \infty$ and $\sum_k \alpha_k^2 < \infty$ (Robbins–Monro), which give convergence to the true mean; a constant $\alpha$ does not.

Greedy can lock onto a bad arm #

The greedy rule pulls the arm with the largest estimate. Take two Bernoulli arms with $\mu = (0.3, 0.8)$, estimates that start at 0, and ties broken at random.

• While every observed reward is 0, both estimates are 0 and the agent picks an arm at random.
• In such a round, the first reward 1 comes from arm 1 with probability $0.5 \cdot 0.3 = 0.15$ and from arm 2 with probability $0.5 \cdot 0.8 = 0.4$.
• So with probability $0.15 / (0.15 + 0.4) = 3/11 \approx 0.27$, arm 1 pays first. From then on its sample mean is above 0 for ever (it contains at least one 1), while arm 2's estimate is 0. Greedy never pulls arm 2 again and loses $0.8 - 0.3 = 0.5$ per round, for ever.

The cause: greedy only learns about the arm it pulls. An arm that looked bad once is never checked again. This is the exploration–exploitation trade-off: to be sure about the best arm, you must sometimes pull arms that look worse.

Interactive figure: loading…

3. Definitions and main results #

Regret #

Definition (pseudo-regret). After $T$ rounds,

It is the expected loss compared with pulling the best arm in every round. It uses the true means $\mu_{a_t}$, not the observed rewards: since $\mathbb E[r_t \mid a_t] = \mu_{a_t}$, the observed rewards have the same expectation, but the true means remove the reward noise.

Lemma (regret decomposition). $\bar R(T) = \sum_a \Delta_a \, \mathbb E[n_a(T)]$.

Proof.

1. Group the rounds by arm: $\sum_{t=1}^T \mu_{a_t} = \sum_a \mu_a \, n_a(T)$.
2. Every round pulls exactly one arm, so $T = \sum_a n_a(T)$ and $T\mu^* = \sum_a \mu^* n_a(T)$.
3. Subtract: $T\mu^* - \sum_a \mu_a n_a(T) = \sum_a (\mu^* - \mu_a)\, n_a(T) = \sum_a \Delta_a n_a(T)$.
4. Take expectations. $\blacksquare$

So a good algorithm pulls each bad arm rarely, and the arms with large gaps most rarely. Example: means $(0.2, 0.5, 0.7)$ and pull counts $(10, 20, 70)$ give regret $0.5 \cdot 10 + 0.2 \cdot 20 + 0 = 9$.

ε-greedy #

ε-greedy: in each round, with probability $\varepsilon$ pull an arm chosen uniformly at random; otherwise pull the arm with the largest estimate.

Theorem (fixed ε gives linear regret). For a fixed $\varepsilon > 0$, $\bar R(T) \ge \frac{\varepsilon T}{K} \sum_a \Delta_a$.

Proof. In each round, arm $a$ is chosen by the random part with probability $\varepsilon / K$, so $\mathbb E[n_a(T)] \ge \varepsilon T / K$ for every arm. Put this into the regret decomposition. $\blacksquare$

The bound grows like $T$ as long as some arm has $\Delta_a > 0$. Because every arm is pulled infinitely often, the estimates converge to the true means, so the greedy part soon picks the best arm, and the regret per step tends to exactly $\frac{\varepsilon}{K}\sum_a \Delta_a$.

Two repairs.

• Decaying ε. With $\varepsilon_t = \min(1, c/t)$, the expected number of random pulls up to $T$ is $\sum_{t \le T} \min(1, c/t) \le c\,(1 + \ln T)$, so the exploration cost grows like $\log T$. With $c$ chosen from the smallest gap, Auer et al. (2002) prove $O(\log T)$ regret for this rule. The catch: you must know (a bound on) the gaps to choose $c$.
• Optimistic initial values. Start every estimate far above any possible mean, e.g. $Q_0 = 5$ for rewards in $[0, 1]$ with a constant step $\alpha = 0.1$ (Sutton & Barto §2.6). Then even the greedy rule tries every arm: each pull lowers the estimate of that arm, so another arm now looks better. This explores only at the start, so it does not help when the means change later. With the sample mean ($\alpha = 1/k$) the first reward replaces $Q_0$ completely, so the optimism lasts only one pull per arm.

Both ideas point to one principle: optimism in the face of uncertainty. UCB1 makes it precise.

UCB1: optimism from Hoeffding's inequality #

Hoeffding's inequality. Let $x_1, \dots, x_n$ be independent, with values in $[0, 1]$ and mean $\mu$, and let $\hat\mu_n$ be their sample mean. Then for every $c > 0$,

The sample mean is rarely far from $\mu$, and "far" shrinks like $1/\sqrt n$.

The idea. Do not use the estimate itself. Use an optimistic value: the largest mean that is still plausible given the data. An arm with few pulls has a wide range of plausible means, so its optimistic value is high, and it gets pulled. If it is really bad, a few pulls shrink its range and it stops being pulled. If it is good, pulling it was right. In both cases we lose little.

Deriving the bonus, step by step.

1. We want a number $\hat\mu_a + c$ that is above the true mean $\mu_a$ with high probability. By Hoeffding, it fails (that is, $\mu_a > \hat\mu_a + c$) with probability at most $e^{-2nc^2}$, where $n = n_a$.
2. Let the failure probability shrink with time $t$: choose $e^{-2nc^2} = t^{-4}$. The power 4 is large enough that the failures, summed over all rounds and all possible counts, stay bounded (see the proof below).
3. Take logarithms: $-2nc^2 = -4 \ln t$, so $c^2 = 2 \ln t / n$ and

4. UCB1 (Auer, Cesa-Bianchi and Fischer, 2002): pull every arm once. Then, in every round, pull

where $t$ is the number of pulls made so far and $n_a$ the number of pulls of arm $a$. The value in brackets is the index of arm $a$, and $\sqrt{2 \ln t / n_a}$ is the exploration bonus.

The bonus shrinks like $1/\sqrt{n_a}$ when the arm is pulled, and it grows slowly, like $\sqrt{\ln t}$, when it is not. So no arm is abandoned for ever, but bad arms are tried less and less often. The first round of pulls is needed because the bonus is undefined for $n_a = 0$.

Interactive figure: loading…

Theorem (UCB1 regret, Auer et al. 2002). For rewards in $[0, 1]$ and every arm with $\Delta_a > 0$,

So, by the regret decomposition,

The regret grows like $\log T$, and arms with small gaps cost the most.

Proof sketch of the UCB1 bound

Think of the rewards of each arm as a list of independent samples drawn in advance; $\hat\mu_{a,s}$ is the mean of the first $s$ entries of arm $a$'s list. Write $c_{t,s} = \sqrt{2 \ln t / s}$. Fix a bad arm $a$ and let $\ell = \lceil 8 \ln T / \Delta_a^2 \rceil$.

1. Arm $a$ is pulled at most $\ell$ times while $n_a < \ell$. So $n_a(T) \le \ell + \#\{t : a_t = a \text{ and } n_a(t) \ge \ell\}$.
2. Suppose UCB1 pulls $a$ at time $t$ with $n_a = s \ge \ell$, and the best arm has $s^*$ pulls. Then $\hat\mu_{a,s} + c_{t,s} \ge \hat\mu_{*,s^*} + c_{t,s^*}$. This forces at least one of three events: (i) $\hat\mu_{*,s^*} \le \mu^* - c_{t,s^*}$ (the best arm is underestimated by more than its bonus); (ii) $\hat\mu_{a,s} \ge \mu_a + c_{t,s}$ (arm $a$ is overestimated by more than its bonus); (iii) $\mu^* < \mu_a + 2 c_{t,s}$. Indeed, if all three fail, then $\hat\mu_{*,s^*} + c_{t,s^*} > \mu^* \ge \mu_a + 2c_{t,s} > \hat\mu_{a,s} + c_{t,s}$, so arm $a$ would not be chosen.
3. Event (iii) is impossible: $s \ge \ell \ge 8 \ln T / \Delta_a^2$ gives $c_{t,s} \le \sqrt{2 \ln T \cdot \Delta_a^2 / (8 \ln T)} = \Delta_a / 2$, so $\mu_a + 2c_{t,s} \le \mu^*$.
4. By Hoeffding, for fixed $s^*$ and $s$, each of (i) and (ii) has probability at most $e^{-2 s c_{t,s}^2} = t^{-4}$. The counts are random, so take a union bound over all $s^*, s \in \{1, \dots, t\}$: the probability that arm $a$ is pulled at time $t$ with $n_a \ge \ell$ is at most $2 t^2 \cdot t^{-4} = 2 t^{-2}$.
5. Summing over $t$: $\mathbb E[n_a(T)] \le \ell + \sum_{t \ge 1} 2 t^{-2} = \ell + \pi^2/3 \le 8 \ln T / \Delta_a^2 + 1 + \pi^2/3$. Multiply by $\Delta_a$ and sum over the bad arms to get the regret bound. $\blacksquare$

Lower bound (Lai and Robbins, 1985). No reasonable algorithm can do better than $\log T$. Call an algorithm consistent if its regret is $o(T^p)$ for every $p > 0$ on every bandit of the class. For Bernoulli arms, every consistent algorithm satisfies

for every arm with $\Delta_a > 0$. So $\log T$ is the best possible order; only the constant can improve. Example: $\mu_a = 0.5$, $\mu^* = 0.7$ gives $\mathrm{KL} = 0.0872$, so at least about $11.5 \ln T$ pulls of arm $a$ are needed, while the UCB1 bound allows $8/\Delta_a^2 \cdot \ln T = 200 \ln T$. UCB1 has the right order with a large constant. KL-UCB and Thompson sampling reach the Lai–Robbins constant for Bernoulli arms.

A bound that does not depend on the gaps

The bound $8 \ln T / \Delta_a$ blows up for tiny gaps, but tiny gaps also cost little per pull. Split the bad arms at a threshold $\delta$. Arms with $\Delta_a < \delta$ cost at most $\delta T$ in total. Arms with $\Delta_a \ge \delta$ cost at most $8 K \ln T / \delta$ (plus a constant). Choose $\delta = \sqrt{8 K \ln T / T}$ to balance the two terms: $\bar R(T) \le 2\sqrt{8 K T \ln T}$ plus a term that does not grow with $T$. So UCB1's worst-case regret is $O(\sqrt{KT \log T})$, and the minimax lower bound for any algorithm is of order $\sqrt{KT}$ (Lattimore and Szepesvári, ch. 15).

Thompson sampling #

Beta–Bernoulli updating. Put a prior $\mathrm{Beta}(\alpha, \beta)$ on the unknown mean $\theta$ of a Bernoulli arm. Its density is proportional to $\theta^{\alpha-1}(1-\theta)^{\beta-1}$, and its mean is $\alpha / (\alpha + \beta)$. After $k$ successes and $m$ failures, Bayes' rule multiplies the prior by the likelihood $\theta^k (1-\theta)^m$:

so the posterior is $\mathrm{Beta}(\alpha + k, \beta + m)$. The Beta family is conjugate to the Bernoulli likelihood: the posterior stays in the family, and the update is two counters. Its variance $\frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)}$ shrinks like $1/n$ as data comes in. The prior $\mathrm{Beta}(1, 1)$ is uniform on $[0, 1]$.

Thompson sampling (Thompson, 1933) for Bernoulli arms, with $\mathrm{Beta}(1, 1)$ priors. In every round:

1. for every arm, draw one sample $\theta_a \sim \mathrm{Beta}(\alpha_a, \beta_a)$ from its posterior;
2. pull $a_t = \arg\max_a \theta_a$ and observe $r_t \in \{0, 1\}$;
3. update that arm: $\alpha_{a_t} \leftarrow \alpha_{a_t} + r_t$ and $\beta_{a_t} \leftarrow \beta_{a_t} + 1 - r_t$.

Why it explores: probability matching. The samples $\theta_a$ are one draw of all the arm means from their posterior. The pulled arm is the one that is best in this draw. So

each arm is pulled with exactly the posterior probability that it is the best arm. An arm with few pulls has a wide posterior, so it sometimes draws the largest sample and gets pulled. As data comes in, the posteriors narrow, and an arm that is clearly worse almost never wins the draw. The exploration comes from the randomness of the posterior, not from a parameter.

Regret. For Bernoulli arms, Thompson sampling has logarithmic regret with the optimal Lai–Robbins constant (Agrawal and Goyal 2012; Kaufmann, Korda and Munos 2012). In practice it is often better than UCB1, and it works well with delayed or batched feedback, because random draws spread the pulls over the arms even when the posteriors are not updated after every pull.

Interactive figure: loading…

The methods side by side #

Interactive figure: loading…

What the simulation shows (mean of 100 runs, $T = 5000$): greedy about 1240, fixed ε-greedy about 166, UCB1 about 107, decaying ε about 48 and Thompson sampling about 20. Two lessons follow. First, the order wins in the long run, but constants matter: UCB1 is worse than ε-greedy until about $t = 2300$, because its constant is large. Second, the decaying-ε rule does well here only because its constant $c = 20$ suits these gaps; with other gaps it can explore too little or too much.

Method	Parameters	Regret	Notes
greedy	none	linear (can lock onto a bad arm)	never checks an arm again
ε-greedy, fixed ε	$\varepsilon$	linear: $\ge \frac{\varepsilon T}{K}\sum_a \Delta_a$	simple; default in deep RL
ε-greedy, $\varepsilon_t = \min(1, c/t)$	$c$ (needs the gaps)	$O(\log T)$ with a good $c$	explores at random, also bad arms
optimistic start	$Q_0$, $\alpha$	explores only at the start	not for changing means
UCB1	none	$O(\sum_a \log T / \Delta_a)$	deterministic; large constant
Thompson sampling	prior	$O(\log T)$, optimal constant (Bernoulli)	needs a posterior; often best in practice

Beyond the basic bandit #

• Contextual bandits. Before each round the agent sees a feature vector $x_{t,a}$ (user, item, time). LinUCB (Li et al., 2010) models the reward as linear, $\mathbb E[r] = x_{t,a}^\top \theta_a$, fits $\hat\theta_a$ by ridge regression, $\hat\theta_a = A_a^{-1} b_a$ with $A_a = I + \sum x x^\top$ and $b_a = \sum r\, x$ over the pulls of $a$, and pulls the arm with the largest $x_{t,a}^\top \hat\theta_a + \alpha \sqrt{x_{t,a}^\top A_a^{-1} x_{t,a}}$. The bonus is large in feature directions with little data.
• Exploration in MDPs is harder, because an action also changes the next state. The ideas carry over: ε-greedy in Q-learning and DQN (lesson 05), optimism and count-based bonuses, entropy bonuses in policy methods (lesson 08), and UCB applied at every node of a search tree (UCT and PUCT in lesson 10).

Answers to section 1. (1) No. With probability $\varepsilon$ it still pulls a random arm, also arms it knows are bad, so the regret per step tends to $\frac{\varepsilon}{K}\sum_a \Delta_a > 0$, not 0. The regret grows linearly. (2) Through the randomness of the posterior. An arm with few pulls has a wide posterior, so it sometimes draws the largest sample $\theta_a$ and gets pulled (probability matching).

4. Worked example #

(a) UCB1 at $t = 50$. Arm 1 has $n = 30$ pulls with mean 0.7; arm 2 has $n = 15$ with mean 0.6; arm 3 has $n = 5$ with mean 0.0. First, $2 \ln 50 = 2 \cdot 3.912 = 7.824$. Then

• arm 1: $0.7 + \sqrt{7.824 / 30} = 0.7 + \sqrt{0.2608} = 0.7 + 0.511 = 1.211$;
• arm 2: $0.6 + \sqrt{7.824 / 15} = 0.6 + \sqrt{0.5216} = 0.6 + 0.722 = 1.322$;
• arm 3: $0.0 + \sqrt{7.824 / 5} = 0.0 + \sqrt{1.5648} = 0.0 + 1.251 = 1.251$.

UCB1 pulls arm 2. It is not the arm with the best mean (arm 1) and not the least-pulled arm (arm 3): arm 2 has a good mean and a medium bonus. Arm 3 has the largest bonus, but its observed mean 0.0 pulls its index below arm 2's.

(b) Thompson sampling. Arm 1 has 5 successes and 1 failure: posterior $\mathrm{Beta}(1+5, 1+1) = \mathrm{Beta}(6, 2)$, mean $6/8 = 0.75$. Arm 2 has 2 and 2: $\mathrm{Beta}(3, 3)$, mean 0.5. Thompson sampling pulls arm 1 with probability

where $p_1$ is the density of $\mathrm{Beta}(6, 2)$ and $F_2$ the distribution function of $\mathrm{Beta}(3, 3)$: arm 1 must be the larger one, so we integrate its density times the probability that arm 2 is below. Arm 2 is still pulled about 15% of the time: it has only 4 observations, and a mean above 0.75 is still plausible for it.

(c) ε-greedy. Means $(0.2, 0.5, 0.7)$, $\varepsilon = 0.1$, $K = 3$. The gaps are $(0.5, 0.2, 0)$. In the long run the regret per step is $\frac{\varepsilon}{K}\sum_a \Delta_a = \frac{0.1}{3}(0.5 + 0.2 + 0) = 0.0233$, and the regret after $T = 1000$ rounds is at least $0.0233 \cdot 1000 = 23.3$.

5. In code #

SciPy checks the numbers above. The notebook implements the algorithms.

import numpy as np
from scipy import integrate, stats

# Hoeffding vs the exact tail: 20 fair coin flips, deviation c = 0.2
n, c = 20, 0.2
print(round(stats.binom.sf(13, n, 0.5), 4))     # 0.0577  exact P(mean >= 0.7) = P(X >= 14)
print(round(np.exp(-2 * n * c**2), 4))          # 0.2019  Hoeffding bound

# UCB1 indices of the worked example (t = 50 pulls so far)
t = 50
for n_a, mean in [(30, 0.7), (15, 0.6), (5, 0.0)]:
    print(round(mean + np.sqrt(2 * np.log(t) / n_a), 3))   # 1.211, 1.322, 1.251

# Thompson sampling: P(theta_1 > theta_2) for Beta(6, 2) and Beta(3, 3)
p = integrate.quad(lambda x: stats.beta.pdf(x, 6, 2) * stats.beta.cdf(x, 3, 3), 0, 1)[0]
print(round(p, 4), round(28 / 33, 4))           # 0.8485 0.8485
rng = np.random.default_rng(0)
theta1, theta2 = rng.beta(6, 2, 100_000), rng.beta(3, 3, 100_000)
print(np.mean(theta1 > theta2))                 # 0.84825  (Monte Carlo estimate)

# epsilon-greedy: limit of the regret per step, means (0.2, 0.5, 0.7), eps = 0.1
mu = np.array([0.2, 0.5, 0.7])
print(round(0.1 * np.mean(mu.max() - mu), 4))   # 0.0233

Hoeffding is loose here (0.20 against 0.06), but it holds for every distribution on $[0, 1]$, and that is what UCB1 needs.

6. Where it shows up #

• Deep RL exploration. DQN on Atari uses ε-greedy with $\varepsilon$ decayed from 1 to 0.1 (later 0.01) over the first million frames: decaying ε, as in section 3.
• MCTS and AlphaZero. UCT (Kocsis and Szepesvári, 2006) applies UCB1 to choose a child at every node of the search tree; AlphaGo and AlphaZero use the PUCT variant with a prior from the policy network (lesson 10).
• Online experiments and recommenders. Thompson sampling and UCB move traffic between variants (ads, layouts, prompts, news articles) while they learn which is best. They waste fewer users on bad variants than a fixed A/B split, but the data is no longer a simple random sample, so classical tests need care.
• Bayesian optimization for science. GP-UCB chooses the next experiment, simulation or hyperparameter setting by the posterior mean plus a multiple of the posterior standard deviation of a Gaussian process: UCB with a smooth model over a continuous set of arms. It is used in materials and drug discovery and in tuning simulators.
• LLMs. Choosing among prompts or models online, and sampling several answers and keeping the best, are bandit problems; the "best-of-$n$" trade-off is again exploration against cost.

7. Common mistakes #

• Regret with observed rewards. The pseudo-regret uses the true means $\mu_{a_t}$. Observed rewards add noise and can even make the "regret" negative.
• UCB without the first round. With $n_a = 0$ the bonus is undefined (division by zero). Pull each arm once first, or give unpulled arms index $+\infty$.
• $\log_{10}$ instead of $\ln$. The bonus $\sqrt{2 \ln t / n}$ uses the natural logarithm, which comes from solving $e^{-2nc^2} = t^{-4}$.
• Swapped Beta update. A success increases $\alpha$, a failure increases $\beta$.
• "ε-greedy converges, so its regret is fine." Its estimates converge, but with a fixed $\varepsilon$ it keeps pulling bad arms at rate $\varepsilon / K$, so the regret is linear.
• Optimism with sample means. With the step $1/k$, the first reward replaces the optimistic $Q_0$; optimistic initial values need a constant step size or a pseudo-count.
• Ties with argmax. np.argmax always returns the first maximum. With estimates that start equal, this means "always arm 0", not a random choice. Break ties at random.

8. Check yourself #

1. Write the pseudo-regret as a sum over arms, and compute it for gaps $(0.3, 0.1, 0)$ and pull counts $(5, 20, 75)$.
   Answer

   $\bar R(T) = \sum_a \Delta_a\, \mathbb E[n_a(T)]$ with $\Delta_a = \mu^* - \mu_a$. Here $0.3 \cdot 5 + 0.1 \cdot 20 + 0 = 3.5$.
2. Which failure probability gives the bonus $\sqrt{2 \ln t / n}$, and why does it shrink with $t$?
   Answer

   $t^{-4}$: solving $e^{-2nc^2} = t^{-4}$ gives $c = \sqrt{2 \ln t / n}$. It shrinks with $t$ so that the failures, summed over all rounds and all possible counts (a union bound gives $2t^{-2}$ per round), have a finite total, $\pi^2/3$.
3. Why does Thompson sampling keep pulling an arm with few observations now and then?
   Answer

   Its posterior is wide, so it sometimes draws the largest sample $\theta_a$. Each arm is pulled with the posterior probability that it is the best (probability matching), and for an arm with little data this probability is not small.
4. Arm 1 has 40 pulls with mean 0.5; arm 2 has 10 pulls with mean 0.45; $t = 50$. Which arm does UCB1 pull?
   Answer

   $2 \ln 50 = 7.824$. Arm 1: $0.5 + \sqrt{7.824/40} = 0.5 + 0.442 = 0.942$. Arm 2: $0.45 + \sqrt{7.824/10} = 0.45 + 0.885 = 1.335$. UCB1 pulls arm 2: its lower mean is outweighed by its larger bonus.
5. What is the best possible order of the regret, and which result says so?
   Answer

   $\log T$. The Lai–Robbins lower bound: every consistent algorithm pulls each bad arm at least about $\ln T / \mathrm{KL}(\mu_a, \mu^*)$ times. UCB1 and Thompson sampling reach this order; Thompson sampling also reaches the constant for Bernoulli arms.
6. Why do optimistic initial values not help when the arm means change over time?
   Answer

   The optimism is used up at the start: after a few pulls every estimate is close to its arm's mean, and the greedy rule stops exploring. When a mean changes later, nothing makes the agent try that arm again.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What is the pseudo-regret of a bandit algorithm, as a sum over arms?

   Show answer

2. Why does ε-greedy with a fixed $\varepsilon$ have linear regret?

   Show answer

3. Write the incremental update of a sample mean.

   Show answer

4. An arm has mean estimate 0.6 after 4 pulls; the 5th reward is 1. Give the new sample mean.

   Show answer

5. Write the UCB1 index of arm $a$.

   Show answer

6. Where does the UCB1 bonus $\sqrt{2\ln t / n}$ come from?

   Show answer

7. What is the best possible order of the regret, and who proved it?

   Show answer

8. How does Thompson sampling update a Beta posterior after a Bernoulli reward $r$?

   Show answer

9. What is probability matching in Thompson sampling?

   Show answer

10. How do optimistic initial values make a greedy agent explore, and what is their limit?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Explain exploration vs exploitation." — To find the best action you must try actions that look worse. Measure the cost with regret; show that greedy can lock onto a bad arm.
• "UCB or Thompson sampling?" — UCB: deterministic optimism from a confidence bound, no prior, easy to analyze, large constant. Thompson: randomized probability matching, needs a posterior, usually better in practice, robust to delayed or batched feedback.
• "Why can a fixed ε be a bad idea?" — Linear regret: it keeps exploring arms it knows are bad. Decay $\varepsilon$, or use UCB or Thompson sampling.
• "Derive the UCB bonus." — Hoeffding, failure probability $t^{-4}$, solve for $c$: $\sqrt{2 \ln t / n}$.
• "What regret is possible?" — $\Theta(\log T)$ per instance (Lai–Robbins); $\Theta(\sqrt{KT})$ in the worst case over instances, up to log factors for UCB1.
• "How would you run an A/B test with a bandit, and what is the catch?" — Thompson sampling over variants; the catch is that adaptive allocation biases naive estimates and p-values.

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. pseudo_regret: the cumulative regret from the true means and the chosen arms.
2. epsilon_greedy: fixed and decaying $\varepsilon$, with random tie-breaking; see linear regret.
3. ucb1: pull every arm once, then the largest index; check the bound on bad-arm pulls.
4. thompson_bernoulli: Beta posteriors; check the final counts.
5. Regret curves on a 10-armed testbed over many seeds; check that UCB1's regret divided by $\ln T$ stays bounded while fixed ε-greedy's grows.

11. Watch and read #

Multi-Armed Bandit : Data Science Conceptsritvikmath · 12 min

A short first look at the problem, ε-greedy and UCB.

RL Course by David Silver - Lecture 9: Exploration and ExploitationGoogle DeepMind · David Silver's RL course · 1 h 39 min

Regret, the Lai–Robbins bound, UCB and Thompson sampling, then exploration in MDPs.

DeepMind x UCL RL Lecture Series - Exploration & Control [2/13]Google DeepMind · Hado van Hasselt · 2 h 10 min

A careful treatment of bandits: regret, UCB with its proof idea, and Thompson sampling.

The Multi-Armed Bandit Problem and Thompson SamplingMicrosoft Research · 37 min

Thompson sampling and the ideas behind its regret analysis.

• Sutton and Barto, Reinforcement Learning: An Introduction, 2nd edition, free PDF: chapter 2 (incremental means, ε-greedy, optimistic initial values, UCB).
• Lattimore and Szepesvári, Bandit Algorithms, free PDF: ch. 4 (regret decomposition), 5 (concentration), 7 (UCB), 16 (lower bounds), 36 (Thompson sampling).
• Auer, Cesa-Bianchi and Fischer, Finite-time analysis of the multiarmed bandit problem (2002): UCB1 and its proof.
• Russo, Van Roy, Kazerouni, Osband and Wen, A Tutorial on Thompson Sampling: §3–4 for Bernoulli bandits.
• Li, Chu, Langford and Schapire, A contextual-bandit approach to personalized news article recommendation (2010): LinUCB.