Beyond A/B Testing: Thompson Sampling and UCB

Multi-Armed Bandits: Part 1: Thompson Sampling and UCB · Part 2: Running a Bandit in Production

Welcome to the bandit chapters of our A/B Testing series: this post, its second part on running a bandit in production, and the contextual-bandits post, before a short GLM epilogue closes the series. The earlier posts built the machinery for estimating an effect: p-values and confidence intervals, the classical tests, sample-size planning, causal inference. Today we change the objective itself, from estimating an effect to maximizing reward while we learn. That is the world of Multi-Armed Bandits (MAB). This post asks one question: how do we learn the best action while minimizing the reward we sacrifice along the way? Part 2 asks what happens when the answer meets real traffic: rewards that arrive late, the inference a bandit quietly breaks, and how to measure regret when nobody knows the best arm. The contextual-bandits post then asks the follow-up: how do we learn the best action for this particular context?

1. Why a Bandit Is Not Simply a Better A/B Test

In a traditional fixed-horizon A/B test, we follow a strict sequence:

1. Allocate traffic (e.g., 50/50) between variants.
2. Wait until the pre-specified sample size is reached - the fixed horizon we powered the test for. (We do not stop the first moment a p-value dips below 0.05; that is peeking, which inflates false positives. A valid early stop needs a sequential test.)
3. Estimate the effect with its uncertainty, and decide under a pre-specified rule: ship the variant, keep the baseline, or gather more evidence. (“Declare a winner” is only one possible outcome; inconclusive and practically-equivalent are valid endings too.)
4. Act on the decision with 100% of future traffic.

The cost? Traffic stays split evenly regardless of how the variants perform; if the arms genuinely differ, uniform allocation carries an expected opportunity cost growing with the gap - visible only in hindsight, but real.

Calling a bandit a “better A/B test” hides the real distinction: a bandit optimizes a different objective. An A/B test estimates an effect; a bandit maximizes cumulative reward while learning - and, as later sections show, makes clean inference much harder to recover. Different tools for different questions:

Goal	Better starting design
Estimate a stable causal effect with interpretable uncertainty	Randomized A/B test
Identify the single best arm after a fixed budget	Best-arm identification
Maximize cumulative reward during learning	Multi-armed bandit
Personalize the action to each user’s context	Contextual bandit (later in the series)

Multi-Armed Bandits solve this via the Explore-Exploit dilemma: instead of waiting for a test to finish, the algorithm continuously shifts traffic toward whatever looks better, while occasionally re-checking the rest. The benefits: faster value realization (the apparent winner earns immediately), less reward sacrificed on bad variants, and continuous operation with no fixed end date, which suits settings where deciding once and freezing is awkward (news feeds, ad rotation). That last benefit leans hardest on the stationarity assumption in section 2’s teaching model: a drifting environment needs extra machinery (sliding windows, discounting, change-point detection), or the bandit locks onto yesterday’s winner.

The Origin: Why “Multi-Armed Bandits”?

A casino slot machine is a “one-armed bandit”: one lever to pull, and it reliably robs us. A row of machines with different, unknown payout probabilities is a multi-armed bandit, and playing it well means balancing exploration (learning payout rates) against exploitation (milking the best machine found so far). The mapping: an arm is a variant, pulling it routes a user there, and the payout is a click, sign-up, or purchase.

---

2. The Bandit Problem, on One Running Example

Everything in this post plays out on one toy environment, so the algorithms can be compared decision by decision.

The setup. An ad campaign with three creatives - Ad A, Ad B, Ad C - whose true click-through rates are:

Arm	True CTR (unknown to the learner)
Ad A	10%
Ad B	20%
Ad C	35%

Each incoming impression is one round $t$: we (the policy) pick one arm, show that ad, and observe a binary reward (click = 1, no click = 0). The learner never sees the table above; it only sees its own clicks. We chose well-separated rates so the exploration patterns stay visually legible; nearly-tied arms are discussed in section 5.

The teaching model, stated once. Each arm produces independent Bernoulli rewards with a fixed (stationary) mean, and only the selected arm’s reward is observed. Every guarantee in this post - Hoeffding bounds, Beta-Bernoulli updates, regret rates - is a statement about this model. Real traffic routinely violates it (repeated users, novelty effects, interference, time trends, ad fatigue, shifting mix); those violations are what contextual, non-stationary, delayed-feedback, and reinforcement-learning formulations exist to handle.

The Baseline: $\epsilon$-Greedy

The simplest way to balance exploring and exploiting is to explore randomly a fixed percentage of the time. We pick a small fraction, $\epsilon$ (epsilon), say 0.10:

• 90% of the time (Exploit): show the ad with the highest historical CTR so far.
• 10% of the time (Explore): show a completely random ad to gather more data.

It is trivially simple, and it is the baseline the smarter algorithms must beat. Its flaw: it explores blindly - even when 99.9% sure Ad C is the winner, it stubbornly sends 10% of traffic to losing ads, forever.

Measuring Success: Regret (More Precisely, Pseudo-Regret)

To evaluate how bad that “wasted money” is, we compare against a perfect oracle who knew the best ad from day one and only played it. That needs a little notation, all of it on the running example:

• $\mu_i$ is arm $i$’s true click rate: $\mu_A = 0.10$, $\mu_B = 0.20$, $\mu_C = 0.35$. The best of them is $\mu^\ast = \max_i \mu_i = 0.35$.
• $\Delta_i = \mu^\ast - \mu_i$ is arm $i$’s gap: the expected reward we give up, per round, whenever we play arm $i$ instead of the best one. Here $\Delta_A = 0.25$, $\Delta_B = 0.15$, and $\Delta_C = 0$: playing the best arm costs nothing.
• $a_t$ is the arm the policy picks in round $t$, and $r_t \in \{0, 1\}$ is the reward it then observes: 1 for a click, 0 otherwise.

$r_t$ is a random variable twice over. The click itself is a coin flip, $r_t \sim \text{Bernoulli}(\mu_{a_t})$. And the arm $a_t$ is random too, because the policy chose it using earlier rewards, which were themselves coin flips (Thompson Sampling adds its own random draws on top). So “how many clicks did the policy collect?” has no single answer; it has a distribution, and the only way to compare a policy with the oracle, who collects $T\mu^\ast$ clicks in expectation over $T$ rounds, is to average over all of that chance. That is why the definition carries an expectation:

\[R_T = T\mu^\ast - \mathbb{E}\left[\sum_{t=1}^T r_t\right]\]

The expected regret $R_T$ is the number of clicks the oracle expects minus the number our policy expects: the expected price of not knowing the best arm from day one.

The same quantity, written in terms of decisions. The definition is about clicks; the form the analysis actually uses is about which arms got pulled, and getting from one to the other takes three steps:

1. Replace each reward by its expectation. Given that round $t$ played arm $a_t$, the click is a $\text{Bernoulli}(\mu_{a_t})$ flip, so $\mathbb{E}[r_t \mid a_t] = \mu_{a_t}$. Averaging over which arm was chosen, $\mathbb{E}[r_t] = \mathbb{E}[\mu_{a_t}]$: the coin flips drop out and only the chosen arm’s true mean remains.
2. Group rounds by arm. Let $N_i(T)$ be the number of times arm $i$ was pulled in the first $T$ rounds, so that $N_A(T) + N_B(T) + N_C(T) = T$. Adding up true means round by round is the same as adding them up arm by arm: $\sum_{t=1}^T \mu_{a_t} = \sum_i \mu_i \, N_i(T)$. The oracle’s total splits the same way, $T\mu^\ast = \sum_i \mu^\ast N_i(T)$, because the $N_i(T)$ sum to $T$.
3. Subtract arm by arm. $\sum_i \mu^\ast N_i(T) - \sum_i \mu_i N_i(T) = \sum_i (\mu^\ast - \mu_i) N_i(T) = \sum_i \Delta_i N_i(T)$.

Taking the expectation of that last line gives the second form:

\[R_T = T\mu^\ast - \mathbb{E}\left[\sum_{t=1}^T r_t\right] = \sum_i \Delta_i \, \mathbb{E}[N_i(T)]\]

Expected regret is each arm’s gap times how often we expect to pull it. On our example, every pull of Ad A costs 0.25 expected clicks, every pull of Ad B costs 0.15, and pulls of Ad C are free, so a policy’s regret is nothing more than its expected pull counts on the two losing arms, weighted by their gaps.

The quantity inside that expectation, the gap-weighted pull count of one particular run, is what our simulations later plot. It is called the pseudo-regret:

\[\widetilde{R}_T = \sum_i \Delta_i \, N_i(T) = \sum_{t=1}^T \Delta_{a_t}\]

the sum of the gaps of the arms actually chosen, one term per round (the two forms are the same grouping trick as step 2). Its expectation is exactly $R_T$. Three honesty notes:

• Pseudo-regret grades the decisions, not the luck. Suppose the policy plays Ad A in some round and the user happens to click. The realized reward that round is 1, more than the oracle’s 0.35 expectation, but it was still the wrong decision, and pseudo-regret charges it $\Delta_A = 0.25$ no matter how the coin landed. Realized reward would credit the lucky click, and over a short stretch a policy can genuinely out-earn the oracle on luck alone. Pseudo-regret strips that noise out and asks only: how much expected reward did each choice throw away? Concretely, playing Ad A for 100 rounds has pseudo-regret $100 \times 0.25 = 25$ on every run, while the realized shortfall against the oracle’s 35 expected clicks moves with the coin flips: a lucky 14 clicks leaves a shortfall of 21, an unlucky 6 leaves 29. Both average to 25; pseudo-regret is simply the less noisy way to see it.
• Neither is observable in production. Both use the true arm means, which only a simulator knows. Regret is an analysis tool, not a dashboard metric.
• Fixed-$\epsilon$ greedy has linear regret. It never stops exploring blindly, so its regret grows at a steady rate forever: $O(\epsilon T)$. On our example, once it has settled on Ad C, the 10% of rounds spent exploring are split evenly across the three arms, so each losing arm keeps receiving a third of them, and the policy throws away $\tfrac{0.10}{3}(0.25 + 0.15) \approx 0.013$ expected clicks every round: about 267 over the 20,000-round horizon of section 5’s simulation, which measures 275. (A decaying schedule behaves much better; that simulation includes one.) The two algorithms introduced next bend the curve to logarithmic growth; their exact guarantees follow.

Two dominant algorithms achieve that bending curve, representing two fundamental statistical philosophies:

1. Thompson Sampling (the Bayesian view): models uncertainty as probability distributions, updating prior beliefs with evidence.
2. Upper Confidence Bound, UCB (the frequentist view): builds deterministic optimistic bounds from concentration inequalities.

Both come with proven regret guarantees under the teaching model. Writing $K$ for the number of arms and summing over the losing arms only (those with $\Delta_i > 0$):

Policy	Gap-dependent bound (fixed, separated arms)	Worst-case bound (nothing assumed about the gaps)
UCB1 (Auer et al., 2002)	$R_T \le \sum_i \frac{8 \ln T}{\Delta_i} + \left(1 + \frac{\pi^2}{3}\right) \sum_i \Delta_i$	$O(\sqrt{KT \ln T})$
Thompson Sampling, Beta-Bernoulli (Kaufmann et al., 2012; Agrawal and Goyal, 2013)	$R_T \le (1+\varepsilon) \sum_i \frac{\Delta_i \ln T}{\mathrm{KL}(\mu_i, \mu^\ast)} + C_\varepsilon$, for any $\varepsilon > 0$	$O(\sqrt{KT \ln T})$

Here $\mathrm{KL}(\mu_i, \mu^\ast)$ is the Kullback-Leibler divergence between a losing arm’s Bernoulli click distribution and the winner’s,

\[\mathrm{KL}(p, q) = p \ln\frac{p}{q} + (1-p) \ln\frac{1-p}{1-q}\]

a measure of how distinguishable the two arms are from their clicks alone; $C_\varepsilon$ is a constant that does not grow with $T$ (the proof’s $\varepsilon$ is a bookkeeping knob, unrelated to $\epsilon$-greedy’s exploration rate). Three things to read off:

• Both are logarithmic in $T$. Fixed-$\epsilon$ greedy pays the same toll every round; these pay a toll that shrinks. Doubling the horizon adds a constant to the regret instead of doubling it.
• Both charge more for close arms. Each term grows like $1/\Delta_i$ (for Thompson, $\mathrm{KL}(\mu_i, \mu^\ast) \ge 2\Delta_i^2$ makes the term at most $1/(2\Delta_i)$ per unit of $\ln T$): a nearly tied arm is expensive because telling it apart from the winner takes many pulls. Section 5 returns to this.
• Thompson Sampling’s constant is the best possible. Lai and Robbins (1985) proved that any policy that does well on every bandit instance, rather than being lucky on one, must accumulate at least $\sum_i \Delta_i \ln T / \mathrm{KL}(\mu_i, \mu^\ast)$ regret in the long run. Thompson Sampling meets that floor; UCB1’s $8/\Delta_i$ is at least sixteen times looser, which is part of why it trails in section 5’s shoot-out (sharper frequentist variants such as KL-UCB close the gap). On our running example the floor’s constant is $0.25/\mathrm{KL}(0.10, 0.35) + 0.15/\mathrm{KL}(0.20, 0.35) \approx 1.49 + 2.77 = 4.26$, so past the initial learning phase every tenfold stretch of the horizon costs the best possible policy only about $4.26 \ln 10 \approx 10$ more expected clicks.

One caution before trusting any of these numbers: they are guarantees about scaling, not predictions of level. The UCB1 bound at section 5’s horizon of $T = 20{,}000$ allows about 845 expected clicks of regret; the simulation’s median is 154. And Thompson’s median there, 23, sits below the $4.26 \ln 20{,}000 \approx 42$ the floor would suggest, which is no contradiction either: the floor constrains the slope as $T \to \infty$, not the height at any finite horizon. All of these results assume the stationary bounded-reward teaching model above (see Lattimore and Szepesvári for the full landscape).

Let’s watch each of them make one real decision.

---

3. Thompson Sampling, One Decision at a Time

Thompson Sampling models each ad’s unknown CTR as a probability distribution, and its decision rule fits in one sentence: sample one plausible CTR from each arm’s posterior and play the arm whose sample is largest.

3.a) One Decision, by Hand

Nine impressions have been served (starting from uniform priors), and the click history is:

Arm	Clicks	Non-clicks	Posterior	Posterior mean
Ad A	1	3	Beta(2, 4)	0.333
Ad B	2	2	Beta(3, 3)	0.500
Ad C	0	1	Beta(1, 2)	0.333

Round 10 begins. One complete Thompson decision:

1. Draw one value from each posterior. Our draws come out: $\tilde{p}_A = 0.126$, $\tilde{p}_B = 0.268$, $\tilde{p}_C = 0.635$.
2. Select the largest draw. Ad C wins this round - despite zero clicks and the joint-lowest posterior mean. Its posterior rests on a single impression, so it is extremely wide, and wide distributions sometimes produce large draws: exploration happening by itself.
3. Observe the reward. We show Ad C; suppose the user clicks.
4. Update only the selected arm. Ad C’s posterior becomes Beta(2, 2). The other two arms are untouched.

Had we instead played the arm with the highest posterior mean, nothing would guarantee C another look: a greedy rule revisits a fallen arm only if the leader’s average happens to sink, so early bad luck can permanently starve an arm. The random draw removes that fragility - it gives uncertain arms their chance by construction, in exact proportion to how plausible their optimality still is.

Repeat this loop thousands of times and the posteriors sharpen and separate. The best arm’s posterior drifts right and narrows; occupying the highest ground, it wins the sampling contest more and more often, and the algorithm glides from exploration into exploitation with no explicit switch:

By round 1,000 in this run, Ad C has received 941 of the 1,000 impressions and its posterior sits in a tight spike over the true 35%. Note the honest side effect: the two losing arms got so little traffic that their posteriors are still wide - we’ll pay for that in part 2.

3.b) The Math: Beta Distributions

Because click-through rates are probabilities (bounded between 0 and 1), we model our beliefs with the Beta distribution, which has two positive shape parameters $\alpha$ and $\beta$:

\[f(x; \alpha, \beta) \propto x^{\alpha-1}(1-x)^{\beta-1}\]

Under Beta-Bernoulli conjugacy (derived next), these behave like pseudo-counts: observed clicks add to $\alpha$, non-clicks to $\beta$ - each parameter is its prior pseudo-count plus observed successes or failures.

3.c) The Beta-Bernoulli Posterior Update (and Why It Is Not MAP)

The refinement above is Bayesian posterior updating, applied online: each click or non-click updates the belief about the arm’s true CTR through Bayes’ rule:

\[P(\text{parameter} \mid \text{data}) \propto P(\text{data} \mid \text{parameter}) \cdot P(\text{parameter})\]

Let’s derive the Beta-Bernoulli bridge:

1. Prior: $P(p) \propto p^{\alpha - 1} (1-p)^{\beta - 1}$
2. Likelihood (Bernoulli trial): we observe outcome $x$ (1 for click, 0 for no click). $P(x \vert p) = p^x (1-p)^{1-x}$
3. Posterior: $P(p \vert x) \propto [p^x (1-p)^{1-x}] \cdot [p^{\alpha - 1} (1-p)^{\beta - 1}]$

Combining terms by adding exponents gives us:

\[P(p | x) \propto p^{(\alpha + x) - 1} (1-p)^{(\beta + 1 - x) - 1}\]

This is exactly a new Beta distribution with parameters $\alpha’ = \alpha + x$ and $\beta’ = \beta + 1 - x$. Concretely, a click sends $\alpha \to \alpha + 1$ and a non-click sends $\beta \to \beta + 1$: prior counts plus observed successes and failures.

A common but important error is to call this MAP estimation. Maximum A Posteriori estimation collapses the posterior to its peak; Thompson Sampling does the opposite, drawing a random sample from the entire posterior for every decision. That distinction is the exploration mechanism - the hand-worked decision above turned entirely on it. A MAP-style policy would stop exploring the instant one arm edged ahead and could lock onto a false winner; sampling from the full posterior means a wide (uncertain) distribution occasionally produces a high draw and earns another look, while a narrow (confident) one rarely does. Thompson Sampling is posterior sampling, not posterior maximization.

3.d) Why the Beta Distribution? (Conjugate Priors)

Why use Beta and not a Normal distribution?

1. Boundedness: Normal distributions span to infinity; probabilities cannot exceed $[0, 1]$.
2. Conjugacy: the Beta distribution is the conjugate prior for the Bernoulli distribution. When we multiply a Beta prior by a Bernoulli likelihood, the posterior is guaranteed to remain a Beta distribution. Conjugacy makes the posterior update analytic: the distribution’s parameters change by simple addition (add 1 to $\alpha$ or $\beta$), with no numerical machinery required.

3.e) Using Historical Evidence - and the Danger of Overconfident Priors

One genuine advantage of Thompson Sampling is the ability to start from evidence rather than ignorance. Initializing with $\alpha = 1, \beta = 1$ gives $\text{Beta}(1,1)$: the uniform distribution, treating a 99% CTR as exactly as likely as 1%. It is commonly called “uninformative,” though the label is loose - a flat prior is still a definite (and here, silly) assumption. When a year of data already pins a baseline near 5%, a prior that says so is better evidence handling, not a trick.

A compact example, with its assumptions on the table. Testing a new checkout button (B) against a legacy one (A) whose conversion rate a year of data pins at 5%, we could give A a strong prior $\text{Beta}(5000, 95000)$ and B a weak, industry-informed $\text{Beta}(4, 96)$. B then cannot steal the traffic off two lucky clicks. But the strong prior makes real commitments: it assumes historical and current traffic are exchangeable (no seasonality shift, no redesign since), and it carries $\alpha + \beta = 100{,}000$ pseudo-observations of effective sample size, so real data needs on the order of 100k trials to move it - if the “known” 5% is stale, the bandit clings to it long after it stopped being true. Sensible hygiene: discount the historical count (e.g., $\text{Beta}(500, 9500)$, a tenth of the nominal evidence) to allow for drift, and compare results under weaker priors.

And one boundary to respect: a prior should encode evidence, not policy. If the actual requirement is “protect the legacy baseline,” that is a safety constraint, and it belongs in explicit machinery - traffic caps, guardrail metrics, a constrained rollout (part 2, section 3) - not in a deliberately distorted belief: encoding rules as fake certainty makes both the rule and the inference harder to audit.

3.f) Python Implementation

The complete algorithm, seeded for reproducible output:

import numpy as np

class ThompsonSampling:
    def __init__(self, n_arms, rng):
        self.rng = rng
        self.alpha = np.ones(n_arms)  # Beta shape a: prior pseudo-count of clicks
        self.beta = np.ones(n_arms)   # Beta shape b: prior pseudo-count of non-clicks

    def select_arm(self):
        # Sample once from each posterior, play the largest draw
        return int(np.argmax(self.rng.beta(self.alpha, self.beta)))

    def update(self, arm, reward):
        # Conjugate update: touch only the played arm
        if reward == 1:
            self.alpha[arm] += 1
        else:
            self.beta[arm] += 1

rng = np.random.default_rng(42)
true_ctrs = [0.10, 0.20, 0.35]      # unknown to the learner
bandit = ThompsonSampling(len(true_ctrs), rng)

for step in range(10_000):
    arm = bandit.select_arm()
    reward = 1 if rng.random() < true_ctrs[arm] else 0
    bandit.update(arm, reward)

shown = bandit.alpha + bandit.beta - 2   # subtract the Beta(1,1) prior counts
est = bandit.alpha / (bandit.alpha + bandit.beta)
for name, n, e, t in zip("ABC", shown, est, true_ctrs):
    print(f"Ad {name}: shown {int(n):>5} times | estimated CTR {e:.3f} (true {t})")

# Ad A: shown    55 times | estimated CTR 0.158 (true 0.1)
# Ad B: shown   129 times | estimated CTR 0.229 (true 0.2)
# Ad C: shown  9816 times | estimated CTR 0.341 (true 0.35)

The output tells the whole story: the best arm absorbs 98% of traffic, and the starved arms’ estimates sit visibly off their true rates (0.158 vs 0.10) - part 2’s inference warning in miniature.

---

4. UCB, One Decision at a Time

UCB solves the explore-exploit dilemma with the philosophy of optimism under uncertainty: score every arm by the best it could plausibly be, then play the highest score. The score for arm $i$ at round $t$ is:

\[\text{UCB}_i = \underbrace{\hat{\mu}_i}_{\text{Exploitation}} + \underbrace{\sqrt{\frac{2 \ln t}{n_i}}}_{\text{Exploration Bonus}}\]

• $\hat{\mu}_i$: current average reward of arm $i$.
• $n_i$: number of times arm $i$ was pulled.
• $t$: total rounds so far.

4.a) One Decision, by Hand

Same three ads. Twenty observations are in the books ($t = 20$, the pull counts below sum to 20), and we are choosing the arm for round 21. The history so far:

Arm	Pulls $n_i$	Empirical CTR $\hat{\mu}_i$	Exploration bonus $\sqrt{2\ln t / n_i}$	UCB score
Ad A	6	1/6 = 0.167	0.999	1.166
Ad B	11	4/11 = 0.364	0.738	1.102
Ad C	3	1/3 = 0.333	1.413	1.747 ✓

(Using $\ln 20 = 3.00$, so the bonus is $\sqrt{6/n_i}$.)

Ad B has the highest empirical CTR, but UCB plays Ad C: with only 3 pulls, C’s uncertainty is so large that its optimistic best case towers over everything - the highest complete score wins, even when it does not currently look best on averages.

Two things are worth staring at in that table. First, the bonuses (0.7 to 1.4) dwarf the empirical means (0.17 to 0.36) - early on, UCB is almost pure exploration. And the score is an optimism index, not a probability: its value can exceed 1 even though a CTR cannot, and only its ordering determines the selected arm. Second, the mechanism that shrinks the bonus is per-arm sample size: by round 5,000 of an actual seeded run, the picture inverts - the empirical means dominate and the bonuses are slivers:

That late-round panel shows a classic UCB signature: the three scores end up nearly equal ($\approx 0.41$) even though the means are far apart - UCB pulls a suboptimal arm exactly until its optimistic bound falls to the leader’s level, then leaves it alone until the growing $\ln t$ nudges it back.

Why the logarithm? The slowly growing $\ln t$ is a revival mechanism: if an arm’s count stays fixed while time passes, its bonus slowly rises until the arm earns another check. Each new pull then increases $n_i$ and shrinks the bonus back down. The tug-of-war between the two terms means no arm is ever abandoned forever, but re-checks become rarer as evidence accumulates.

Why $\sqrt{n_i}$ in the denominator? This connects directly to the standard error. The variance of a sample mean is proportional to $1/n$, so its standard deviation shrinks like $1/\sqrt{n}$. The UCB exploration bonus mimics exactly that behavior: more data on an arm, proportionally smaller uncertainty bonus. One caution on vocabulary: the bonus is a concentration-based optimistic bound, not an ordinary 95% confidence interval - its width is chosen to make the regret analysis work (via the $\delta = 2t^{-4}$ failure-probability schedule below), not to give calibrated coverage for reporting.

4.b) Where Does the Bonus Formula Come From? (Hoeffding’s Inequality)

We know the bonus acts like a standard error, but where do the exact terms inside the square root come from? Classical confidence intervals need a variance estimate; in an online bandit we want a strict, worst-case guarantee without one.

Enter Hoeffding’s inequality. For random variables in a known range (like our CTR, which sits in $[0,1]$), it bounds the probability that a sample mean ($\hat{\mu}$) deviates from the true mean ($\mu$), with the bound dropping exponentially in the sample size ($n$):

\[P(|\hat{\mu}_i - \mu_i| \ge \epsilon) \le 2 \exp\left( - 2n_i\epsilon^2 \right)\]

Keep the two error-related symbols distinct: $\epsilon$ is the margin of error (how far our estimate may sit from reality), $\delta$ the probability of failure (the chance it is off by more than that margin). Because the right-hand side is the maximum failure probability, we set it equal to our target $\delta$ and solve for the margin $\epsilon$:

\[2 e^{-2 n_i \epsilon^2} = \delta\] \[\Rightarrow -2 n_i \epsilon^2 = \ln(\delta/2)\] \[\Rightarrow \epsilon = \sqrt{\frac{\ln(2/\delta)}{2 n_i}}\]

In bandits we want the guarantee to strengthen over time, so we let $\delta$ decay: $\delta = 2t^{-4}$. Substituting gives exactly the UCB term:

\[\epsilon = \sqrt{\frac{2 \ln t}{n_i}}\]

4.c) Python Implementation

import numpy as np

class UCB:
    def __init__(self, n_arms):
        self.n_arms = n_arms
        self.counts = np.zeros(n_arms)   # n_i
        self.values = np.zeros(n_arms)   # mu_hat
        self.t = 0

    def select_arm(self):
        # Play every arm once before trusting the formula
        for i in range(self.n_arms):
            if self.counts[i] == 0:
                return i
        scores = self.values + np.sqrt(2 * np.log(self.t) / self.counts)
        return int(np.argmax(scores))    # ties: lowest index wins

    def update(self, arm, reward):
        self.t += 1
        self.counts[arm] += 1
        # Incremental mean update
        self.values[arm] += (reward - self.values[arm]) / self.counts[arm]

rng = np.random.default_rng(42)
true_ctrs = [0.10, 0.20, 0.35]
bandit = UCB(len(true_ctrs))

for step in range(10_000):
    arm = bandit.select_arm()
    reward = 1 if rng.random() < true_ctrs[arm] else 0
    bandit.update(arm, reward)

for name, n, e, t in zip("ABC", bandit.counts, bandit.values, true_ctrs):
    print(f"Ad {name}: shown {int(n):>5} times | estimated CTR {e:.3f} (true {t})")

# Ad A: shown   188 times | estimated CTR 0.085 (true 0.1)
# Ad B: shown   440 times | estimated CTR 0.193 (true 0.2)
# Ad C: shown  9372 times | estimated CTR 0.355 (true 0.35)

On the same seed, UCB gave the losing arms several times more traffic than Thompson (188 and 440 pulls vs 55 and 129) and correspondingly got their estimates closer to the truth: exploration spent and estimation accuracy are two sides of one coin.

---

5. All the Policies on the Same Simulation

Now the shoot-out. We run fixed-$\epsilon$ greedy (0.10), a decaying-$\epsilon$ greedy ($\epsilon_t = t^{-1/3}$), UCB, and Thompson Sampling against the same three-arm environment for 20,000 rounds - and, crucially, we repeat the race across 200 seeded simulations and report medians with 10th-90th percentile bands, since a single trajectory can flatter or damn any algorithm through early luck.

The reproducibility recipe: the policies are sections 3.f and 4.c’s implementations plus the two $\epsilon$-greedy variants (every arm played once first; ties break to the lowest index); run $s$ uses default_rng(1000 + s); each policy consumes its own random stream, rewards drawn at pull time. The left panel plots each run’s cumulative pseudo-regret $\sum_t \Delta_{a_t}$ (computable only because the simulator knows the true CTRs); the right panel is the cross-run mean of the “pulled the best arm” indicator, smoothed over a 500-round rolling window.

Reading the left panel:

• Fixed-$\epsilon$ greedy is a straight line (median final pseudo-regret $\approx 275$): constant slope, exploring at a fixed 10% rate forever. Linear regret, exactly as predicted.
• Decaying-$\epsilon$ greedy delivers on section 2’s promise: shrinking $\epsilon_t = t^{-1/3}$ bends the curve (median $\approx 151$), halving the fixed schedule’s regret. But it still explores blindly, spreading its shrinking budget uniformly instead of aiming at the uncertain arms; theory reflects the crudeness ($O(T^{2/3})$: sub-linear, short of logarithmic), and by the end of the horizon it has only just caught up to UCB.
• Thompson Sampling’s curve bends almost immediately and grows very slowly thereafter (median $\approx 23$): its posteriors concentrate fast, and its share of pulls on Ad C (right panel) reaches 99.9% - what “smoothly transitioning from exploration to exploitation” looks like operationally.
• UCB bends too (median $\approx 154$), but notice something the asymptotic theory doesn’t advertise: UCB’s pseudo-regret is above fixed-$\epsilon$ greedy’s for roughly the first 9,000 rounds. Its formula front-loads forced exploration; the logarithmic curve only wins after that investment pays off. “Sub-linear beats linear” is a statement about the long run, not every horizon. (And no logarithmic curve ever truly flattens: it keeps growing, just increasingly slowly.)

The right panel asks one operational question of all four policies: how often is the best arm actually served? Fixed-$\epsilon$ greedy hits a hard structural ceiling at 0.933 - once converged, it serves Ad C only when exploiting (90%) plus when exploration happens to draw it (10%/3) - while the others keep climbing: decaying-$\epsilon$ 0.975, UCB 0.988, Thompson 0.999.

One honest caveat the whole picture depends on: the gaps between arms matter. We used well-separated CTRs. When arms are nearly tied (say 5.0% vs 5.5%), the constant inside every gap-dependent guarantee blows up: UCB over-explores near-identical arms for a very long time, and over practical horizons its pseudo-regret can trail even $\epsilon$-greedy. The ranking depends on the gaps, the horizon, and the tuning - it is not a fixed leaderboard.

That is the whole of the algorithms: two policies, one decision each by hand, and a race. Part 2 takes them out of the simulator: how to choose between them on engineering grounds, what breaks when rewards arrive days late, the clean inference a bandit quietly gives up, and how to measure regret when nobody knows the best arm.

---

Resources

• Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002), “Finite-time Analysis of the Multiarmed Bandit Problem”, Machine Learning, 47, 235-256 - the paper behind section 4’s UCB formula and the UCB1 bound in section 2.
• Lai, T. L. and Robbins, H. (1985), “Asymptotically Efficient Adaptive Allocation Rules”, Advances in Applied Mathematics, 6, 4-22 - the lower bound every regret guarantee in section 2 is measured against.
• Kaufmann, E., Korda, N., and Munos, R. (2012), “Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis”, ALT - the first proof that Thompson Sampling meets the Lai-Robbins rate for Bernoulli rewards.
• Agrawal, S. and Goyal, N. (2013), “Further Optimal Regret Bounds for Thompson Sampling”, AISTATS, PMLR 31 - the finite-time Thompson Sampling bound quoted in section 2.
• Russo, D., Van Roy, B., Kazerouni, A., Osband, I., and Wen, Z. (2018), “A Tutorial on Thompson Sampling”, Foundations and Trends in Machine Learning, 11(1), 1-96.
• Lattimore, T. and Szepesvári, C. (2020), Bandit Algorithms, Cambridge University Press - the comprehensive, freely available reference for section 2’s regret landscape.