rl
The two slot machines
It is 1952, and the clinical-trial version of this problem keeps a statistician awake: two treatments, unknown success rates, and each patient assigned is both a data point and a life. Strip it to its essence — two arms, unknown payout rates, 100 pulls. Every pull spent learning about the worse arm is a cost paid in outcomes; every pull committed too early to a leader is a bet that the evidence was enough. Balance exploring against exploiting with provable regret bounds: not folklore about when to switch, but a guarantee on how much the best strategy must lose to ignorance. This little problem is the atom of sequential decision-making; solve it wrong and every adaptive trial, ad allocation, and dose-finding design downstream inherits the error.
Who this problem belongs to
The two figures whose methods fit it best, out of 35 in contention.
Sequential analysis is Wald's invention: the 1943-45 sequential probability ratio test was built for wartime inspection where every observation had a price, and his posthumous Statistical Decision Functions (1950) supplies the frame — loss, risk, admissibility, minimax — inside which regret analysis lives. The 1952 clinical-trial framing is his home terrain; Robbins's 1952 bandit paper explicitly extends the sequential-design tradition Wald founded. The gap is real: the SPRT decides between hypotheses with sampling cost external to the loss, while the bandit makes sampling itself the loss, and Wald never produced an allocation index or a finite-time regret bound before his death in 1950. But no toolkit in this batch sits closer to the problem as posed — sequential, decision-theoretic, minimax-minded, and mortally serious about the cost of each observation.
The k-armed bandit opens Sutton and Barto's Reinforcement Learning (1998) as Chapter 2 precisely because it isolates the explore-exploit tension with no state to hide behind, and Sutton's incremental sample-average update — new estimate equals old estimate plus step-size times error — is exactly the cheap online machinery a 100-pull problem wants. Epsilon-greedy, optimistic initialization, and upper-confidence action selection are all treated there as the atoms of his larger program. The honest gap: Sutton's contributions are algorithms and the temporal-difference principle, not finite-time regret theorems — the Lai-Robbins asymptotics and Auer-style UCB proofs the problem demands came from the sequential-statistics and learning-theory communities, which he draws on rather than extends. Still, few carriers have spent more decades on what a pull spent learning actually costs.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
35 figures are scored on this problem. Draw it in a battle to see where you land.