Thompson Sampling: how explore meets exploit

Every system that makes repeated decisions under uncertainty faces the same question: do I go with what I already know works, or do I try something new that might be better?

This is the exploration-exploitation tradeoff. It shows up everywhere. Which ad to show. Which treatment to assign. Which message to send a user at 3pm on a Tuesday. Thompson Sampling is one of the most elegant solutions to this class of problem. Not the only one, but one worth understanding deeply.

I built a bomber game to make the intuition tangible. But this article is about the algorithm itself, where it shines, and where the real complexity lives.

The problem: multi-armed bandits

Imagine you're in a casino with K slot machines. Each machine pays out with some unknown probability. You have N pulls. You want to maximize your total winnings.

If you always pull the machine that's paid best so far (greedy), you might miss a better one you haven't tried enough. If you spend too many pulls exploring, you waste them on machines you already know are bad.

This is the multi-armed bandit problem. It captures a huge class of real-world decisions: which variant to show, which campaign to send, which model to route a request to.

Why naive approaches fail

A greedy algorithm picks the arm with the highest observed mean reward. The problem: early observations are noisy. If arm A pays out once and arm B doesn't on your first pull of each, greedy locks onto A forever, even if B is actually better. You've exploited too early.

Epsilon-greedy fixes this by exploring randomly with probability epsilon (say, 10% of the time). Better, but wasteful. It explores arms you already know are bad just as often as promising ones. And the 10% never stops. Even after 10,000 observations, you're still burning 10% on random exploration.

UCB (Upper Confidence Bound) is smarter. It picks the arm with the highest upper confidence bound, which naturally favors uncertain arms. Good, but deterministic. It always picks the same arm given the same state. No randomness means no probability matching.

Thompson Sampling takes a different path entirely.

Beta distributions as beliefs

Here's the Bayesian insight: instead of tracking a single number (average reward) per arm, track a distribution that represents your full uncertainty about that arm's true quality.

For binary outcomes (hit or miss, click or ignore), the natural choice is the Beta distribution, parameterized by alpha and beta:

• alpha = number of successes + 1
• beta = number of failures + 1
• Start with Beta(1, 1) = uniform over [0, 1] = "I have no idea"

After 3 hits and 7 misses, your belief is Beta(4, 8). The mean is 4/12 = 0.33, but the shape tells you more: you're fairly confident this arm pays about a third of the time.

After 30 hits and 70 misses, your belief is Beta(31, 71). Same mean, but the distribution is much narrower. You're very confident now.

The width of the distribution IS your uncertainty. This is the key insight that makes Thompson Sampling work.

Thompson Sampling in four lines

The algorithm:

for each arm i:
  draw x_i ~ Beta(alpha_i, beta_i)

choose the arm with the highest draw
observe the outcome

if success:
  alpha_i += 1
else:
  beta_i += 1

That's it. No epsilon parameter to tune. No confidence bound formula. Just sample from your beliefs and act on the sample.

Why does this work? An arm with high uncertainty (wide distribution) will occasionally produce a very high sample, winning the draw and getting explored. An arm with high confidence and high mean will consistently produce high samples, getting exploited. Arms that are both well-understood and bad will produce consistently low samples and get ignored.

The algorithm automatically balances exploration and exploitation through the width of the distributions. The more uncertain you are, the more you explore. The more confident you are, the more you exploit. And the balance shifts naturally as evidence accumulates.

This property is called probability matching: the probability of choosing an arm is proportional to the probability that it's actually the best arm. Exactly the right amount of exploration, by construction.

Learning from neighbors: kernel smoothing

In practice, arms often have structure. If arm 12 (60% power) works well, arm 11 (55%) and arm 13 (65%) probably work too. Pure Thompson Sampling doesn't know this. It updates only the exact arm that was chosen.

A practical extension is kernel-smoothed updates: when an arm succeeds, neighboring arms also get partial credit, weighted by a Gaussian curve centered on the chosen arm. The total credit is normalized so one success equals one failure in magnitude, but the success spreads while the failure stays precise.

This creates a natural bell curve in the posterior beliefs as the algorithm converges on a region rather than a single point. In the bomber game, you can see this forming in the AI's belief chart as it zeros in on the right power range.

The asymmetry is deliberate. Successes generalize (nearby powers probably work too). Failures are precise (this specific power didn't work here). This means the algorithm unlearns bad choices fast while building broad confidence in good regions.

Contextual bandits: when the best choice depends on the situation

Standard Thompson Sampling assumes the reward probabilities are fixed. In practice, the best arm almost always depends on context.

Which message works best depends on who the user is, when you're reaching them, and what they did recently. The optimal campaign variant at 9am for an active user is different from the optimal one at 9pm for a lapsed user.

This is a contextual bandit. The solution is conceptually simple: maintain separate Beta distributions per context. When the context is "active user, morning", sample from that context's distributions. When it's "lapsed user, evening", sample from those instead.

The bomber game demonstrates this concretely. Turn on wind shifting and the AI faces three conditions: headwind, calm, tailwind. The optimal power level is different for each. The Knowledge Surface heatmap shows how the AI builds separate beliefs per wind context, with peaks forming at different power levels for different winds.

The principle scales to any number of context dimensions, though the engineering gets harder. More contexts means sparser data per context, which means slower convergence per cell. This is where techniques like hierarchical priors, context embedding, and transfer learning come in. The simple version in the game uses three wind buckets. Production systems might have thousands of context combinations.

When the world changes: non-stationarity

The real world isn't stationary. User preferences shift. Seasons change. A campaign that worked last month may not work today.

Thompson Sampling handles this more gracefully than most approaches because the Beta distributions can be "decayed" over time. By periodically shrinking alpha and beta toward their priors, you can make the algorithm forget old observations and re-explore. The rate of decay controls the tradeoff between stability and adaptability.

In the bomber game, non-stationarity comes from three sources: you move between turns, wind shifts each turn (when enabled), and craters reshape the terrain. When conditions change, the AI's previously-learned optimal power breaks. The attempt log shows this: "Exploited 65%, missed, confidence drops." The belief drops, exploration resumes, and the AI converges on a new optimum.

The configurable penalty strength in the game controls how fast unlearning happens. This mirrors a real design decision: how much should new evidence override old beliefs? Too fast and you overreact to noise. Too slow and you're stuck on stale knowledge.

Where Thompson Sampling fits in the real world

Thompson Sampling is one of many tools for sequential decision-making under uncertainty. It's not always the right choice, but it excels in specific conditions:

Where it shines:

• Binary or bounded reward signals (click/no-click, open/ignore)
• Many arms with limited data per arm (cold start, long tail)
• Non-stationary environments where you need continuous adaptation
• Systems where you want automatic exploration without manual rules

Where other tools may be better:

• When you need deterministic behavior (UCB variants)
• When reward distributions are complex or continuous (Gaussian process bandits)
• When you have rich feature information about arms (linear contextual bandits, neural approaches)
• When the action space is combinatorial (reinforcement learning)

In agentic personalisation systems like Aampe, Thompson Sampling sits at a specific decision point: given a user context, which campaign variant should we send right now? The framing maps directly:

• Arms = message templates, campaigns, action groups
• Context = user attributes, recency, engagement patterns, time of day
• Reward = did the user engage? open? convert?

For each user at decision time, we sample from each campaign's Beta distribution conditioned on that user's context, and select the highest draw. After observing the outcome, we update.

This is sometimes called beta-draw selection. It gives us:

• Automatic personalization without explicit segmentation rules
• Continuous exploration of underperforming options in case conditions change
• Principled exploitation of what works, proportional to confidence
• No A/B test tax: unlike a traditional A/B test that locks a fixed percentage into a control, Thompson Sampling naturally reduces exploration as it learns

The system uses different weights for different signal types, context-dependent normalization, decay functions for non-stationarity, and hierarchical priors that transfer learning across similar contexts. The core principle is the same. The engineering complexity is in the tuning.

The sparse feedback problem

Here's what makes this hard in practice: you rarely see the full picture. You don't know why a user ignored a message. Was it the wrong message, the wrong time, or did they just not open their phone? The signal is sparse and noisy.

Thompson Sampling is unusually well-suited to this because it doesn't need rich feedback. A binary signal (success/failure) is enough. The uncertainty is encoded in the distribution width, and the algorithm explores proportionally to that uncertainty.

Try the Play Fair mode in the bomber game. You can't see the enemy, your projectile disappears past the boundary, and you only get distance feedback after each shot. You're solving the same problem the AI solves systematically: learning from sparse signals, no full picture. This is the norm in production systems, not the exception.

The code

The Beta sampling implementation from the game uses a Marsaglia-Tsang gamma sampler (since Beta(a,b) = Gamma(a) / (Gamma(a) + Gamma(b))):

function betaSample(a: number, b: number): number {
  const x = gammaSample(a);
  const y = gammaSample(b);
  return x / (x + y);
}

// Thompson draw for one context
function tsDraw(ts: TSState, ctxIdx: number) {
  let best = -1, bestBucket = 0;
  for (let i = 0; i < N_POWER; i++) {
    const s = betaSample(ts.alpha[ctxIdx][i], ts.beta[ctxIdx][i]);
    if (s > best) { best = s; bestBucket = i; }
  }
  // Jitter within bucket for sub-bucket precision
  const center = (bestBucket + 1) * 5;
  const power = Math.max(5, Math.min(100, center + (Math.random() - 0.5) * 5));
  return { bucket: bestBucket, power };
}

The state persists in sessionStorage. Close the tab and the AI starts fresh. Keep playing and watch it converge. Move, and watch it re-explore.