Thompson Sampling: Probabilistic Exploration

Every UPI payment app you use — PhonePe, Google Pay, Paytm — does not send your transaction to a single bank server. Behind the scenes, the app's payment orchestrator can usually route a transaction through several competing payment gateways (say, three different bank-hosted UPI switches), because any single gateway can be slow, overloaded, or intermittently failing at 9 PM when half of India is settling a Swiggy order at once. The orchestrator's job is to pick, for each incoming transaction, the gateway most likely to complete successfully within the few hundred milliseconds a user will tolerate before the "Payment Failed, Retry?" screen appears. The catch: nobody knows the current true success rate of each gateway. It drifts by the minute — a gateway that was 92% reliable five minutes ago might be degrading right now because a partner bank's server is under load. The orchestrator has to learn which gateway is best while simultaneously using that knowledge to route live traffic, and it has to do this thousands of times a second with real money on the line. This is a multi-armed bandit problem, and Thompson Sampling is the algorithm many real payment and ad-serving systems use to solve it.

From bandits to belief: restating the problem

Recall the multi-armed bandit setup: you have k arms (here, gateways A, B, C), each arm i has an unknown true probability p_i of producing a reward of 1 (transaction succeeds) versus 0 (transaction fails) when pulled, and at each round you must choose one arm, observe only that arm's outcome, and update your beliefs before the next round. This is reinforcement learning stripped to its simplest case: one state, one step, no transitions to plan over — which is exactly why the bandit setting is the right place to isolate the exploration-exploitation trade-off before you tackle full sequential RL with state transitions.

Two exploration strategies you have likely already met handle this trade-off crudely. Epsilon-greedy picks the best-known arm with probability 1−ε and a uniformly random arm with probability ε — exploration is a coin flip, blind to how much you actually know about each arm. UCB1 (Upper Confidence Bound) is smarter: it picks the arm maximizing mean_i + sqrt(2 ln t / n_i), an explicit "optimism bonus" that shrinks as an arm gets pulled more (n_i grows) and grows as time t passes without pulling it. Both are deterministic given the data so far — same history, same decision, every time.

Thompson Sampling takes a different philosophical stance: instead of computing a single confidence-adjusted score per arm, it maintains a full probability distribution over what each arm's true success rate could be, and decides by literally drawing one random guess from each distribution and going with whichever guess is highest. The randomness is not a hack bolted onto a deterministic rule — it is the entire mechanism. This is Bayesian reasoning in its most operational form: your uncertainty about a gateway's reliability is represented as a distribution, and you act by sampling from your own uncertainty.

The Beta-Bernoulli machine

To make this concrete you need a distribution over "probability of success," and the Beta distribution is the natural choice because a success/failure outcome is a Bernoulli trial, and the Beta distribution is the conjugate prior to the Bernoulli likelihood — meaning that after you fold in one observation, the posterior belief is again a Beta distribution, just with updated parameters. No numerical integration, no approximation, an exact closed-form update.

The Beta distribution Beta(α, β) is defined on the interval [0, 1] — exactly the range a probability lives in — with density proportional to θ^α−1(1−θ)^β−1. Read α as "1 + number of observed successes" and β as "1 + number of observed failures." With no data at all, α = β = 1 and Beta(1, 1) is the uniform distribution on [0, 1] — every success rate from 0 to 1 is considered equally plausible, which is the honest starting belief when you know nothing about a new gateway.

The update rule follows directly from Bayes' theorem. If your prior belief about a gateway's true success rate θ is Beta(α, β), and you observe one Bernoulli outcome r (r = 1 for success, r = 0 for failure), then:

P(θ | r) ∝ P(r | θ) · P(θ)
         = θ^r (1-θ)^(1-r) · θ^(α-1) (1-θ)^(β-1)
         = θ^(α+r-1) (1-θ)^(β+(1-r)-1)

which is exactly the un-normalised density of Beta(α + r, β + 1 − r). In plain terms: a success bumps α up by 1, a failure bumps β up by 1, nothing else changes. This is the entire "learning" step of Thompson Sampling for Bernoulli rewards — one integer increment, no gradient descent, no learning rate to tune.

The full algorithm, per round, is only three steps:

1. For every arm i, draw one random sample θ̂_i from its current posterior Beta(α_i, β_i).
2. Pull the arm with the largest sampled value: arm = argmax_i θ̂_i.
3. Observe the reward r and update that arm only: α_arm += r, β_arm += (1 − r).

Worked example: routing five transactions by hand

Follow this by hand, with no library calls, using a fact about order statistics: if you draw n independent Uniform(0, 1) numbers and take the k-th smallest, that value follows Beta(k, n − k + 1). This means Beta(1, 1) is a single uniform draw, Beta(2, 1) is the maximum of two uniform draws, and Beta(1, 2) is the minimum of two uniform draws — a shortcut that lets us hand-simulate exact Beta samples for the small integer parameters that appear in the first few rounds. (Production code does not do this — it calls a dedicated Beta sampler, as the verified code below does — but the identity is exact and it is the cleanest way to trace the algorithm by hand.)

Start all three gateways at Beta(1, 1). Use this fixed sequence of "random" uniform draws, consumed left to right, so every step below is fully reproducible: 0.62, 0.35, 0.81, 0.44, 0.91, 0.28, 0.53, 0.77, 0.15, 0.68, 0.39, 0.86.

Round 1 — all three arms are Beta(1, 1), so each sample is just the next uniform draw: A = 0.62, B = 0.35, C = 0.81. Argmax is C. Route to C; the transaction fails (r = 0). Update: C becomes Beta(1, 2).

Round 2 — A, B are still Beta(1, 1): A = 0.44, B = 0.91. C is now Beta(1, 2) = min of two draws: min(0.28, 0.53) = 0.28. Argmax is B (0.91). Route to B; success (r = 1). Update: B becomes Beta(2, 1).

Round 3 — A is still Beta(1, 1): A = 0.77. B is Beta(2, 1) = max of two draws: max(0.15, 0.68) = 0.68. C is Beta(1, 2) = min(0.39, 0.86) = 0.39. Argmax is A (0.77). Route to A; success (r = 1). Update: A becomes Beta(2, 1).

Notice what just happened in Round 1: A, B and C all had the identical posterior mean (0.5, since Beta(1,1) has mean α/(α+β) = 1/2), yet the algorithm confidently routed to C. This is the mechanism in action, not a bug — with no data, the sampled draw is the only source of variation, so routing is effectively a fair, randomized trial across untested arms. That is exploration, achieved without any separate ε parameter.

By the start of Round 4, the state is A = Beta(2, 1), B = Beta(2, 1), C = Beta(1, 2). The diagram below illustrates one such decision cycle at exactly this posterior state, using a fresh set of sampled values — not a continuation of the specific 12-draw sequence traced above, which is fully consumed by the end of Round 3 (see the verified 10-round simulation below for the actual full trajectory).

Diagram: one full decision cycle

The two shaded triangles for A and B are not stylised — Beta(2, 1) has exact density f(θ) = 2θ, a straight line from 0 at θ = 0 to 2 at θ = 1, so the "curve" in the diagram is mathematically exact, not an artist's sketch. Beta(1, 2) is its mirror image, f(θ) = 2(1 − θ). Wider, flatter shapes (like the Beta(1,1) uniform seen in Round 1) mean more uncertainty and a higher chance the sample lands far from the mean; the two triangles here are already narrower and pulled toward high θ because each arm has one real success behind it.

This illustrative cycle confirms the pattern: Round 4 routes to B (success, B becomes Beta(3, 1)). A further illustrative round — sampling A = max(0.66, 0.82) = 0.82, B = max of three draws (0.11, 0.59, 0.95) = 0.95, C = min(0.27, 0.44) = 0.27 — again routes to B, which succeeds again, making B Beta(4, 1). Five rounds in, no arm has been abandoned, but traffic is visibly concentrating on the arm that keeps winning — precisely the exploration-to-exploitation shift Thompson Sampling is supposed to produce, achieved without an explicit schedule or a hand-tuned ε.

Verified simulation

Hand order-statistics tricks only work for the tiny integer parameters seen early on; a real system calls a Beta random-variate generator directly. Here is a minimal, complete implementation, followed by its actual captured output over ten rounds against hidden true success rates p_A = 0.55, p_B = 0.75, p_C = 0.35 (unknown to the algorithm, seeded for reproducibility):

import random

class ThompsonBandit:
    def __init__(self, n_arms):
        self.alpha = [1] * n_arms
        self.beta = [1] * n_arms

    def select_arm(self):
        samples = [random.betavariate(self.alpha[i], self.beta[i])
                   for i in range(len(self.alpha))]
        return samples.index(max(samples))

    def update(self, arm, reward):
        if reward == 1:
            self.alpha[arm] += 1
        else:
            self.beta[arm] += 1

random.seed(7)
true_p = [0.55, 0.75, 0.35]
labels = ['A', 'B', 'C']
bandit = ThompsonBandit(3)
for t in range(1, 11):
    arm = bandit.select_arm()
    reward = 1 if random.random() < true_p[arm] else 0
    bandit.update(arm, reward)
    print(f"t={t:2d} routed={labels[arm]} reward={reward} alpha={bandit.alpha} beta={bandit.beta}")

Run exactly as written (Python 3, random.seed(7)), this produces:

t= 1 routed=B reward=1 alpha=[1, 2, 1] beta=[1, 1, 1]
t= 2 routed=A reward=1 alpha=[2, 2, 1] beta=[1, 1, 1]
t= 3 routed=B reward=1 alpha=[2, 3, 1] beta=[1, 1, 1]
t= 4 routed=C reward=1 alpha=[2, 3, 2] beta=[1, 1, 1]
t= 5 routed=B reward=1 alpha=[2, 4, 2] beta=[1, 1, 1]
t= 6 routed=B reward=1 alpha=[2, 5, 2] beta=[1, 1, 1]
t= 7 routed=B reward=1 alpha=[2, 6, 2] beta=[1, 1, 1]
t= 8 routed=B reward=0 alpha=[2, 6, 2] beta=[1, 2, 1]
t= 9 routed=C reward=1 alpha=[2, 6, 3] beta=[1, 2, 1]
t=10 routed=A reward=0 alpha=[2, 6, 3] beta=[2, 2, 1]
final success-rate estimates: [0.5, 0.75, 0.75]

By t = 10, B — the truly best gateway at p = 0.75 — has been routed 6 of 10 times and its posterior mean (α/(α+β) = 6/8 = 0.75) already sits almost exactly on the true value. C still gets an occasional exploratory pull (t = 4, t = 9) precisely because its posterior, built from only a few observations, stays wide enough to occasionally produce a high sample — exploration that fades on its own as evidence accumulates, with no ε to decay by hand.

Common misconception

Students who have just learned about posterior means from the Beta-Bernoulli update often assume Thompson Sampling picks the arm with the highest posterior mean — in other words, that it is just "greedy on the average belief." This is wrong, and Round 1 of the worked example is the direct counter-example: A, B and C all had identical posterior mean 0.5 (all Beta(1,1)), yet the algorithm still had to pick one arm, and it picked C — not by tie-breaking on the mean (there was a three-way tie) but by drawing an actual random number from each distribution and comparing the draws. Two arms can even have different means where the lower-mean arm still wins a given round, if its distribution is wide enough that an unlucky-for-the-leader, lucky-for-the-follower draw occurs — exactly what "exploring an uncertain option even though its average looks worse" means in practice. The mean tells you where a distribution is centred; Thompson Sampling cares about the whole shape, because the whole shape is what determines how often a sample from it beats a sample from a tighter, higher-mean rival.

Why the randomness is not wasted effort

The elegance of sample-then-argmax is that exploration and exploitation are not two separate mechanisms bolted together (as in epsilon-greedy, where a coin flip decides which mode you're in this round) — they emerge from one Bayesian rule applied consistently. An arm pulled rarely has a wide posterior (few observations means little concentration), so its samples are noisy and occasionally spike high enough to win a round even against a stronger-mean rival — that spike is exploration. An arm pulled often has a narrow posterior tightly concentrated near its true rate, so its samples cluster near that rate and rarely lose to noise — that stability is exploitation. Both behaviors fall out of the same three-line update rule; nothing needs to be scheduled or annealed.

This is not just an appealing story — it has been proved rigorously. Agrawal and Goyal (2012), and independently Kaufmann, Korda and Munos (2012), showed that for Bernoulli bandits, Thompson Sampling achieves regret (cumulative gap versus always having pulled the best arm) growing only as O(log T) with the number of rounds T, matching the Lai–Robbins lower bound that no algorithm can beat asymptotically. UCB1 achieves the same asymptotic order but with looser constants in practice; empirically, Thompson Sampling tends to accumulate less regret in the early rounds, which matters enormously in a payment-routing system where "early rounds" are not a toy simulation but real transactions with real users waiting.

Active recall

Attempt each question before reading its answer.

1. An arm's prior is Beta(3, 2). Before any sampling, what is its posterior mean?
2. In one round, the sampler draws θ̂_X = 0.41 from arm X's Beta(5, 5) and θ̂_Y = 0.63 from arm Y's Beta(2, 8). Which arm is routed, and why does this outcome look surprising if you only compare posterior means?
3. An arm starts at Beta(2, 2) and then accumulates 3 successes and 7 failures. What is its posterior after these ten observations?
4. In one sentence, explain why Thompson Sampling needs no separate exploration-rate parameter (no ε, no decay schedule), unlike epsilon-greedy.
5. True or false, with justification: as the number of rounds T grows without bound, Thompson Sampling will pull the single best arm on almost every round.
6. What distribution does the 2nd smallest value among 4 independent Uniform(0, 1) draws follow, and why is that identity useful when hand-tracing a Beta-Bernoulli bandit?

Answers.

1. Mean of Beta(α, β) is α/(α+β) = 3/(3+2) = 0.6.

2. Arm Y is routed — 0.63 > 0.41. It looks surprising because Y's posterior mean is only 2/(2+8) = 0.2, far below X's mean of 5/(5+5) = 0.5. Thompson Sampling never compares means directly; it compares one random draw per arm, and Y's wider, less-informed posterior (fewer effective observations relative to its shape) was capable of producing a value far out in its tail. This is exploration happening exactly when it is supposed to: on the arm we know less about.

3. α = 2 + 3 = 5, β = 2 + 7 = 9, so the posterior is Beta(5, 9).

4. The posterior's own spread already encodes how much exploration is warranted — a barely-tested arm has a wide posterior that samples noisily (naturally explorative), and a heavily-tested arm has a narrow posterior that samples consistently (naturally exploitative) — so no external knob is needed to trade one off against the other.

5. True. As pulls of the best arm accumulate, its posterior concentrates (shrinking variance) around its true, highest success rate; every other arm's posterior likewise concentrates around its own, lower true rate. The probability that a sample from a suboptimal arm's tightening, lower-centred distribution exceeds a sample from the best arm's tightening, higher-centred distribution shrinks to zero, so in the long run the best arm is chosen almost every round — this convergence is exactly what the O(log T) regret bound formalises.

6. Beta(2, 4 − 2 + 1) = Beta(2, 3), by the order-statistic identity: the k-th smallest of n i.i.d. Uniform(0, 1) values follows Beta(k, n − k + 1). It is useful because it lets you generate an exact sample from a small-integer-parameter Beta distribution using only ordinary uniform random numbers and a sort — precisely the trick used to hand-trace Rounds 1–3 of the gateway-routing example above, before the parameters grew large enough that a dedicated Beta sampler (as in the verified Python code) becomes the practical choice.

Think About It

Think about this: How would you explain thompson sampling: probabilistic exploration to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind thompson sampling: probabilistic exploration, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.