Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 34

Bandits: learning while earning

Each round the agent pulls one arm of a Bernoulli bandit and gets a reward 1 with the arm's unknown probability. The regret of a round is the gap between the best arm's mean and the pulled arm's mean; the cumulative regret is what a policy pays for not knowing. Five policies play the same random rewards: greedy on the empirical means, ε-greedy, UCB1 (index \(\hat\mu+\sqrt{2\ln t/n}\)), a Bayesian UCB (Beta posterior mean plus \(c\) posterior standard deviations) and Thompson sampling (play the arm whose sampled mean is largest). Greedy and fixed-ε policies have regret that grows linearly; UCB and Thompson sampling grow logarithmically, the best rate possible (the Lai-Robbins bound).

Arms true success probabilities

Horizon T

ε for ε-greedy

Bayesian UCB multiplier c

Runs averaged

Time axis / policy shown below

Try these

Mean over the runs of the pseudo-regret \(\sum_t(\mu^*-\mu_{a_t})\); the same reward table is used by every policy within a run. The dashed line has the slope \(C=\sum_a\Delta_a/\mathrm{KL}(\mathrm{Ber}(\mu_a)\|\mathrm{Ber}(\mu^*))\) of the Lai-Robbins bound per unit of \(\ln t\), anchored at the Thompson curve at \(t=T/10\); the bound holds asymptotically, not at every finite time. Each policy first pulls every arm once. Beta priors are \(\mathrm{Beta}(1,1)\).

In the lecture notes