multi-arm bandit problem.

imagine you just moved to a new city with five pizza places nearby. you want to eat the best pizza most often, but you don't yet know which one is best.

two extreme strategies:

• always go to your current favorite — you might miss out on a better place you haven't tried.
• always pick a random place — you'll learn a lot, but waste many meals on bad pizza.

epsilon-greedy says: most of the time, go to the place you currently think is best. occasionally (with probability ε), pick a random place — just to keep an open mind. that "occasionally" is the whole trick.

let:

• K = number of arms
• ε = a small number between 0 and 1, e.g. 0.1
• μ̂ₐ = current estimated mean reward for arm a

at each time step:

p = random()

if p < ε:
  explore — pick a random arm uniformly from all K arms
else:
  exploit — pick the arm with the highest current μ̂

observe the reward
update μ̂ for the chosen arm (running average)

two lines of real logic. that simplicity is its main appeal.

main weakness — it explores uniformly, even when it's already very confident some arms are bad. it never stops exploring unless you decay ε over time. you'll see this below: even after thousands of impressions, the three losing anime keep getting surfaced around 2.5% of the time each (a third of ε).

ucb's philosophy fits in a phrase: be optimistic about arms you haven't tried much.

think about it like hiring. you have:

• candidate A: interviewed 50 times. average score 7.5/10. you're confident she's a 7.5.
• candidate B: interviewed only 2 times. average score 7.0/10. but B could actually be a 9. or a 4. you're not sure.

a greedy algorithm would always pick A (higher mean). but B has more uncertainty — and that uncertainty might hide a much better candidate. ucb says: give B the benefit of the doubt. assume the optimistic case until proven otherwise.

this solves the explore/exploit dilemma without needing a random ε. exploration emerges naturally from uncertainty itself.

for each arm a at time step t, compute its ucb score:

UCB_a(t) = μ̂_a + √(2 · ln t / n_a)

then pick the arm with the highest ucb score.

breaking it down:

• μ̂_a — current estimated mean reward of arm a (the "exploit" term)
• n_a — number of times arm a has been pulled
• t — total number of pulls so far across all arms
• √(2 · ln t / n_a) — the exploration bonus, or confidence radius

intuition for the bonus term:

• smaller n_a → bonus is larger → arm gets more attractive. uncertainty calls for optimism.
• larger n_a → bonus shrinks → arm's score approaches its true average.
• larger t (more total time) → bonus grows slowly, logarithmically — keeps a small exploration impulse alive.

in words: estimated value + uncertainty bonus = optimistic estimate.

regret bounds are logarithmic in the number of pulls, which is provably optimal up to constants. unlike ε-greedy, ucb stops exploring losing arms once it's confident — anime that nobody adds to their list get nudged less and less, instead of forever.

a wine tasting analogy. imagine three wine bottles. after a few sips of each, you have:

• bottle A: pretty sure it's around 7/10 (tried 50 sips)
• bottle B: maybe 6/10? but could be 8 or 4 (tried 5 sips)
• bottle C: no idea — maybe 5? (tried 1 sip)

for each bottle, in your head, you draw a plausible rating given your current uncertainty:

• A: "i'd guess 7.1" — narrow distribution, sampled value close to 7
• B: "i'd guess 7.8 today" — wide distribution, today's sample came out high
• C: "i'd guess 4.2" — very wide, today's sample came out low

you pick B for your next sip — not because B's average is best, but because today's imagined draw was highest. tomorrow you might draw A: 7.0, B: 5.5, C: 8.0 — and try C instead. this naturally balances exploring uncertain arms with exploiting confident winners.

how it works

thompson sampling is bayesian. for each arm, maintain a posterior distribution over its true mean — initially wide (weak prior), narrowing as evidence accumulates.

on each round:

for each arm a:
  draw θ_a ~ posterior(a)

pull arg max θ_a

observe reward r
update posterior(arg max θ_a) with r

it explores more when posteriors are wide (early on) and exploits more as they sharpen. arms with high uncertainty occasionally produce optimistic samples and get pulled — but only as long as their posteriors stay wide.

for bernoulli rewards (success/failure), beta priors make the math trivial. each arm is a Beta(α, β) where:

• α = 1 + number of successes
• β = 1 + number of failures

drawing from Beta(α, β) is one line in any stats library. empirically, thompson sampling usually beats ucb. theoretically, it has the same logarithmic regret bound — provably optimal up to constants.