← All Cracked ML projects
PL-B01NOT STARTEDBEGINNERMLPYTHONIMPACT ★☆☆☆☆

Bandit arena vs the Lai–Robbins bound

Pit your bandit algorithms against the proven lower limit on regret, and against arms whose payouts drift over time.

EST.5 h
REWARD+200 XP
AFTERLattimore & Szepesvári

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
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
GOAL · 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
The Lai–Robbins bound, as given in Lattimore & Szepesvári, Bandit Algorithms · measured locally by mlarena bench—
no results yet
YOUR RESULTS

Your recorded results appear here.

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

  1. 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).
  2. 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.