# bandits-lab Small, readable, CPU-only Python implementations of stochastic bandit algorithms, the Lai–Robbins lower bound, multiplayer bandits without communication, and a practical **A/B-test planner** that compares a fixed split with Thompson sampling and top-two Thompson sampling. Everything is numpy + scipy + matplotlib. Policies run a whole batch of independent Monte Carlo runs at once (state arrays of shape `(runs, K)`), so 100 runs × 20 000 rounds take seconds. ## Install ```bash pip install -r requirements.txt # numpy, scipy, matplotlib, pytest ``` ## Commands ```bash python experiments/run_experiments.py --quick # smoke run, ~10-20 s python experiments/run_experiments.py # all figures, ~1.5 min on a shared 2-CPU box python tools/ab_test_planner.py --baseline 0.05 --lifts 0.05,0.10 \ --traffic 2000 --days 28 --sims 300 --plot out/ab_plan.png python -m pytest -q # 20 tests, ~10 s ``` Runtimes are wall-clock on a 2-CPU machine that was shared with other jobs; CPU time was about a third of that. Nothing uses more than one process. ## The theory in plain language **Bandits.** You repeatedly choose one of K options ("arms") with unknown average payoffs and see only the payoff of the arm you chose. Regret is how much you lose compared with always playing the best arm. Exploring costs regret now; not exploring risks being stuck on a bad arm forever. **Lai–Robbins lower bound (Lai & Robbins, 1985).** For any policy that is good on every instance ("uniformly efficient"), regret must grow at least like `C · log T` with `C = Σ_{i suboptimal} Δ_i / KL(μ_i, μ*)`: an arm is costly to rule out when its gap Δ is large *and* it is hard to distinguish from the best arm (small KL). This is asymptotic: at finite T a good policy's curve can sit above or below `C log T`; the claim is about the slope as T → ∞. **Algorithms implemented** (`bandits/algorithms.py`): | policy | idea | regret | |---|---|---| | ε-greedy (fixed / decaying) | explore at random with probability ε | linear (fixed ε); log T with a decaying schedule tuned to the gap | | explore-then-commit | m pulls per arm, then commit | needs m tuned to the gap and horizon | | UCB1 (Auer, Cesa-Bianchi & Fischer, 2002) | optimism: mean + √(2 log t / n) | O(Σ log T / Δ), not optimal constant | | KL-UCB (Garivier & Cappé, 2011) | largest q with n·KL(μ̂, q) ≤ log t | matches the Lai–Robbins constant for Bernoulli arms | | Thompson sampling, Beta / Gaussian | play the arm that is best under a posterior sample | asymptotically optimal for Bernoulli arms (Kaufmann, Korda & Munos 2012; Agrawal & Goyal 2012/2013) | The KL-UCB index is computed with a vectorised bisection, cross-checked in the tests against a scalar Newton solver. **Multiplayer bandits without communication** (`bandits/multiplayer.py`). M players share K arms. If two players pull the same arm they *collide* and both get 0, and they observe the collision. Nobody can send messages. The goal is for the team to spread over the M best arms. * *Selfish UCB*: every player runs UCB1 on its own data; collisions are just zeros. No coordination at all. It worked on this instance, but selfish play is not guaranteed to: Boursier & Perchet (2019) discuss instances where it fails. * *Musical chairs* (Rosenski, Shamir & Szlak, 2016): explore uniformly for T0 rounds, estimate M from how often you collide (`P(no collision) = (1 − 1/K)^{M−1}`), then pick random arms among your estimated top M until you land on one without a collision, and stay there. Its regret is about linear in T0, and T0 has to be set from the gap. * *SIC-style, simplified* (in the spirit of SIC-MMAB, Boursier & Perchet, 2019): the key insight of SIC-MMAB is that **collisions are a communication channel**. A player who deliberately collides with another sends it one bit. The implemented protocol: 1. orthogonalise with musical chairs on all K arms; 2. roll call: for each pair of seats (a, b), the player on a visits b, and a collision means b is occupied. Everyone learns M and a distinct rank; 3. collision-free sequential hopping over the candidate arms (2^p pulls per arm per player in phase p); 4. followers send their exact success counts to the leader in binary, one collision per 1-bit; 5. the leader eliminates arms that have M arms confidently above them and broadcasts one bit per arm; 6. when M arms remain, each player commits to its own arm. **What is simplified compared with SIC-MMAB:** statistics are gathered at a single leader instead of all-to-all quantised broadcasts; arms are not "accepted" early, so everyone explores until exactly M candidates remain; ranks come from O(K²) pairwise probes instead of SIC's O(K) sequential hopping; and exact integer counts are sent instead of quantised means. If orthogonalisation fails (probability ≤ 1/T by construction), the run is charged maximal regret for the rest of the horizon instead of being silently dropped. There were no failures in our runs. ## Expected output (actual numbers from our runs) `python experiments/run_experiments.py` (Bernoulli means 0.9/0.8/0.7/0.6/0.5, T = 20 000, 100 runs; ± is the standard error): ``` eps-greedy(0.1) regret@T = 418.9 ± 3.9 eps-greedy(c=5.0) regret@T = 103.9 ± 33.7 ETC(m=50) regret@T = 366.0 ± 72.4 UCB1 regret@T = 278.0 ± 2.5 KL-UCB regret@T = 46.7 ± 1.2 TS-Beta regret@T = 28.2 ± 1.1 [lower bound] Lai-Robbins constant C = 5.30 (C log T at T=20000: 52.5) UCB1 slope of regret vs log t over [T/10, T] = 69.83 (ratio to C: 13.17) KL-UCB slope of regret vs log t over [T/10, T] = 7.63 (ratio to C: 1.44) TS-Beta slope of regret vs log t over [T/10, T] = 3.52 (ratio to C: 0.66) [gaussian] means [1.0, 0.5, 0.0], C = 6.0 UCB1 regret@T = 53.1 TS-Gaussian regret@T = 41.4 [multiplayer] K=6, M=3, means [0.9, 0.8, 0.7, 0.5, 0.4, 0.3], T=50000, runs=30 selfish UCB collective regret@T = 977.2 (median 948.3), collisions/run 742 musical chairs (T0=1000) collective regret@T = 1159.5 (median 1163.1), collisions/run 929 SIC-style (simplified) collective regret@T = 812.1 (median 810.7), protocol failures 0 ``` How to read these numbers: * The slope of TS against log t being *below* C at T = 20 000 does not contradict Lai–Robbins. The bound is asymptotic, and the local slope over [2 000, 20 000] is still rising toward C. Finite-time regret curves of optimal algorithms usually look like this. * UCB1's constant is far from optimal here because its √(2 log t/n) bonus ignores that Bernoulli arms near 0.9 have small variance. KL-UCB exploits that. * Multiplayer: all three methods ended on the best 3 arms in the final round of every run. SIC-style regret is flat after about 3 000 rounds (its regret grows only with log T: 683 → 793 → 888 for T = 5k/50k/200k, 20 runs). Musical chairs pays roughly linearly in T0. Selfish UCB keeps colliding and its regret is still growing. Figures in `out/`: `single_player_regret.png`, `lai_robbins.png` (regret vs log t with the `C log t` line), `gaussian_ts.png`, `multiplayer.png`, `ab_plan.png`. ## The A/B test planner (`tools/ab_test_planner.py`) Given a baseline conversion rate, plausible lifts, traffic per day and a horizon, the planner simulates the future under three policies: * **fixed split A/B.** Equal traffic until a pre-registered sample size is reached (two-proportion z-test, Bonferroni over variants, chosen power and MDE). Then ship a variant only if it is significantly better, otherwise keep control. This gives clean, unbiased inference and the highest exploration cost. * **Thompson sampling.** Daily batches split in proportion to P(arm is best) under Beta posteriors. This minimises lost conversions. * **top-two Thompson sampling** (Russo, 2016; β = ½). Built for *identifying* the best arm. It stops and ships once P(best) ≥ 0.95. It reports expected lost conversions (regret), P(final choice is the true best), and the time to a confident decision, and saves a 3-panel plot. ``` $ python tools/ab_test_planner.py --baseline 0.05 --lifts 0.05,0.10 --traffic 2000 --days 28 --sims 300 --plot out/ab_plan.png Fixed test plan: n = 147,889/arm for MDE +5.0% (alpha 0.05, power 0.8, Bonferroni) -> 222 days [LONGER THAN HORIZON: underpowered] strategy lost conv. (mean ± sd) P(pick best) decided by end median day* fixed split A/B 140.0 ± 0.5 49.0% forced@end >28 Thompson sampling 70.1 ± 40.0 86.3% 37% 11 top-two TS (stop+ship) 84.0 ± 40.9 83.7% 51% 11 $ python tools/ab_test_planner.py --baseline 0.05 --lifts 0.05,0.10 --traffic 20000 --days 28 --sims 200 Fixed test plan: ... -> 23 days fixed split A/B 1150.1 ± 1.3 100.0% planned 23 Thompson sampling 200.4 ± 157.1 99.5% 98% 6 top-two TS (stop+ship) 224.8 ± 169.0 99.5% 100% 5 ``` (Runtime is about 6–8 s per call. If `--lifts` is omitted, lifts are drawn U[−max, +max] per simulation, so the report averages over plausible worlds.) **The trade-off, stated honestly:** * Bandits (TS) *minimise regret*: they shift traffic to the winner while learning. * Pure exploration (TTTS) *identifies the best arm* fastest at a given confidence and then exploits. * Fixed A/B gives *valid inference*: controlled error rates, unbiased effect sizes and simple confidence intervals. * "Confident" for TS/TTTS means posterior P(best) ≥ 0.95 under a flat prior. With data-dependent stopping, this is **not** a frequentist 5 % error guarantee. Trust the simulated P(pick best) instead. * After adaptive allocation, naive conversion-rate estimates and t-tests are biased. Use the bandit to allocate traffic, and keep a fixed holdout if you need a clean effect size. * The model assumes stationary conversion rates, independent visitors and immediate conversions. Real traffic has weekday effects, novelty effects and delayed conversions. ## Ideas for turning this into a tool * Wrap `ab_test_planner` in a small web form (FastAPI or Streamlit) that product managers can use *before* starting a test: "with your traffic, a 5 % lift needs 222 days. Consider a bandit, or a bigger MDE." * Add delayed conversions and weekday seasonality to the simulator, plus a "holdout" arm for unbiased effect estimation. * Add an always-valid inference option (mixture SPRT / confidence sequences) so that peeking at a fixed split becomes legitimate. * Generalise the multiplayer code into a simulator for decentralised channel access (Wi-Fi/cognitive radio) or for distributed job schedulers, where collisions are real and nobody wants a coordinator. * Expose the vectorised policies behind a `select/update` service API for live recommendation experiments. ## File layout ``` bandits-lab/ ├── README.md ├── requirements.txt ├── pytest.ini ├── bandits/ │ ├── __init__.py │ ├── algorithms.py # environments, ε-greedy, ETC, UCB1, KL-UCB, TS (Beta/Gaussian), simulate() │ ├── lower_bound.py # Lai–Robbins constant, regret-vs-log-t plot, slope fit │ └── multiplayer.py # collision model, selfish UCB, musical chairs, SIC-style protocol ├── tools/ │ └── ab_test_planner.py # CLI: fixed A/B vs TS vs top-two TS ├── experiments/ │ └── run_experiments.py # reproduces all figures (--quick available) ├── tests/ │ ├── test_algorithms.py # KL-UCB index, posterior updates, sublinear regret, LR constants │ ├── test_multiplayer.py# collision rules, M estimation, musical chairs, SIC protocol │ └── test_ab_planner.py # top-two allocation, sample size, end-to-end └── out/ # generated PNGs ```