Thompson Sampling for Bernoulli Bandits

MediumML Coding

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 of k samples) and return the index of the largest (lowest index on ties).

thompson_update(alphas, betas, arm, reward)

  • Update the arrays in place: add 1 to alphas[arm] on a reward of 1, to betas[arm] on a reward of 0. Return nothing.

run_thompson(true_probs, steps, rng)

  • Start from Beta(1, 1) on every arm. Each step: select, then draw the reward as rng.random() < true_probs[arm], then update. Return a dict with rewards (a list of the rewards), counts (pulls per arm as a list) and regret, the expected regret steps * max(true_probs) - sum(true_probs[arm chosen]) as a float.

run_epsilon_greedy(true_probs, steps, epsilon, rng)

  • Estimates start at 0 with zero counts. Each step: draw u = rng.random(); if u < epsilon pull rng.integers(len(true_probs)), else the arm with the highest estimate (lowest index on ties); then draw the reward as rng.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