Thompson Sampling (Bernoulli-Beta)

Background

Thompson sampling balances exploration and exploitation for the multi-armed bandit problem. For each arm, sample a posterior estimate of its true rate; pick the arm with the highest sampled estimate. Bernoulli rewards + Beta priors are the canonical conjugate pair.

Problem statement

Implement thompson_choose(arm_successes, arm_failures, prior_alpha=1.0, prior_beta=1.0, seed=0). For each arm $k$, draw a single sample from $\text{Beta}(\alpha_0 + s_k, \beta_0 + f_k)$. Return the index of the arm with the highest sample.

Input

• arm_successes, arm_failures - arrays of integers, same length $K$.
• prior_alpha, prior_beta - Beta hyperparameters (default $1, 1$).
• seed - RNG seed.

Output

• int, chosen arm index.

Examples

Input: successes=[10, 3], failures=[0, 7]
Output: 0 (almost always)    # arm 0's posterior is concentrated near 1

Constraints

• Same seed -> same chosen arm.
• Lengths must match. Empty input raises ValueError.

Notes

• Why Thompson. The probability of picking each arm equals the posterior probability it's best - automatically allocates exploration in proportion to uncertainty. Tighter regret bounds than UCB in many practical settings.