1. The Multi-Armed Bandit Problem

  • Imagine a row of slot machines (arms).
  • Each arm $i$ has an unknown reward distribution with mean $\mu_i$​.
  • Goal: maximize total reward over time by balancing:
    • Exploration: try arms to learn their payoffs.
    • Exploitation: play the arm that looks best so far.

2. Bayesian View

  • For each arm, maintain a posterior distribution over its reward probability (or mean).
  • Example: Bernoulli rewards (success/failure):
    • Prior for arm $i$: $p_i \sim \text{Beta}(\alpha_i, \beta_i)$.
    • After observing successes/failures, update to posterior.

3. Thompson Sampling Algorithm

At each round:

  1. For each arm iii, sample a parameter value $\hat{\mu}_i$ from its posterior.
  2. Select the arm with the highest sampled value.
  3. Play that arm, observe reward $r$.
  4. Update posterior of that arm using Bayes’ rule.

Repeat.

Intuition:

  • If you’re uncertain about an arm, samples will sometimes be high → forces exploration.
  • If you’re confident an arm is bad, samples rarely win → less wasted time.

4. Example: Bernoulli Bandit

  • Suppose arm $i$ gives reward 1 with probability $p_i$​.
  • Prior: $p_i \sim \text{Beta}(1,1)$ (uniform).
  • After sss successes and $f$ failures:
    • $p_i \mid \text{data} \sim \text{Beta}(1+s, 1+f)$
  • Each round:
    • Sample $\tilde{p}_i \sim \text{Beta}(1+s, 1+f)$.
    • Pick arm with largest $\tilde{p}_i$.

5. Why It Works

  • Exploration vs. exploitation is handled automatically by sampling.
  • Arms with higher uncertainty keep getting explored.
  • Arms with strong evidence dominate as posteriors concentrate.

6. Performance

  • Regret (difference between expected reward of optimal arm vs chosen arm) is close to logarithmic in time ($O(\log T)$), which is near-optimal.
  • Simple, elegant, and works well in practice (ads, recommendation, clinical trials).

7. Extensions

  • Contextual Thompson Sampling:
    Uses covariates $x$ (e.g., user features) with Bayesian linear/logistic regression.
  • General reward models:
    Can use Gaussian posteriors for continuous rewards, Dirichlet for categorical, etc.
  • Parallel Thompson Sampling:
    For distributed settings (e.g., multiple users simultaneously).

Summary:
Thompson Sampling picks arms by sampling from their posterior reward distributions.
It balances exploration and exploitation naturally, without manually tuning an exploration rate (like in $\epsilon$-greedy).