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).
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)\).
code/ch34_decision_making.py (simulate_bandit, lai_robbins_const, bayes_optimal_two_arm).