Thompson Sampling for Bernoulli Bandits
Problem statement
Explore by Sampling Your Beliefs
Each of k arms pays a reward of 1 with an unknown probability. Thompson sampling keeps a Beta posterior over each arm's probability, draws one sample from every posterior, and pulls the arm with the largest sample. Implement it and compare it with epsilon-greedy on the same problem.
thompson_select(alphas, betas, rng)
- Draw
rng.beta(alphas, betas)once (a vector ofksamples) and return the index of the largest (lowest index on ties).
thompson_update(alphas, betas, arm, reward)
- Update the arrays in place: add
1toalphas[arm]on a reward of1, tobetas[arm]on a reward of0. Return nothing.
run_thompson(true_probs, steps, rng)
- Start from
Beta(1, 1)on every arm. Each step: select, then draw the reward asrng.random() < true_probs[arm], then update. Return a dict withrewards(a list of the rewards),counts(pulls per arm as a list) andregret, the expected regretsteps * max(true_probs) - sum(true_probs[arm chosen])as a float.
run_epsilon_greedy(true_probs, steps, epsilon, rng)
- Estimates start at
0with zero counts. Each step: drawu = rng.random(); ifu < epsilonpullrng.integers(len(true_probs)), else the arm with the highest estimate (lowest index on ties); then draw the reward asrng.random() < true_probs[arm]and update the running mean. Return the same dict.
compare(true_probs, steps, epsilon, seed)
- Run both with independent
np.random.default_rng(seed)generators and return{'thompson': regret, 'epsilon_greedy': regret}rounded to 2 decimals.
Notes
- The order of random draws is part of the contract: the Beta vector first, then the reward; for epsilon-greedy the exploration coin first, then the arm index if exploring, then the reward.
Example
Input:
run_thompson([0.2, 0.5], 1000, np.random.default_rng(0))['counts']
Output:
[13, 987]
Reasoning: Thompson sampling keeps trying the worse arm only while its posterior still overlaps the better one's, so almost all pulls go to the 0.5 arm.
Show hint
Which distribution is conjugate to a Bernoulli reward, and how do its two parameters change after one observation?
Relevant roles: Data Scientist, Applied Scientist, ML Engineer and Research Scientist.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium