Brief
In NumPy, implement four strategies for the multi-armed bandit problem (you repeatedly pick one of several slot-machine 'arms' whose payout rates you do not know). ε-greedy picks the best arm so far but explores a random arm with probability ε. UCB1 picks the arm with the highest upper-confidence estimate, so arms you know little about get the benefit of the doubt. KL-UCB (an upper-confidence rule that uses KL divergence to decide how optimistic to be) is a tighter version of the same idea. Thompson sampling draws a plausible payout rate for each arm from its posterior and plays the highest draw. Then implement sliding-window and discounted Thompson sampling, which forget or down-weight old rewards so they can cope with non-stationary arms (arms whose payout rates change). The harness runs 200 seeds and plots cumulative regret (the total reward you lost compared with always playing the best arm) against the Lai–Robbins asymptotic lower bound (the smallest regret any algorithm can achieve in the long run). The twist: half the benchmark is piecewise-stationary (payout rates stay fixed for a while, then jump), and there textbook Thompson sampling fails.
VICTORY CONDITIONS
- Thompson sampling reaches ≤ 1.3× the bound and KL-UCB ≤ 1.5×; on the drifting suite, sliding-window TS (Thompson sampling) cuts regret by ≥ 30% vs stationary TS (cumulative regret at T=10^5 steps ÷ the Lai–Robbins lower bound, on a 10-arm Bernoulli bandit (each arm pays 1 or 0 with a fixed probability), over 200 seeds; plus regret on a piecewise-stationary suite).
- A public repository with a README that shows your result and how to reproduce it.
Terms in plain words
- Regret
- How much total reward you lost by not always playing the best arm, which you did not know in advance.
- Lai–Robbins lower bound
- A proven minimum on how slowly regret can grow, so no algorithm can beat it in the long run.
- Thompson sampling
- Keep a probability distribution over each arm's payout rate, draw one sample per arm, and play the arm with the highest sample.
- Piecewise-stationary
- The payout rates stay fixed for a stretch of time, then suddenly change, then stay fixed again.
Why it rates ★☆☆☆☆
A textbook exercise done carefully. It shows rigour, not novelty.