Each round a recommender shows one item and observes whether it is clicked; the click probabilities are unknown. An item that is never shown never gets a chance to prove itself, so the data are a consequence of the policy that collected them. The regret is the total click probability lost against always showing the best item. Four policies play the same random clicks (the same random numbers for every policy, so the comparison is fair): greedy shows the item with the highest observed click rate; ε-greedy shows a random item with probability ε; UCB1 adds an optimism bonus \(\sqrt{2\ln t/n_a}\); Thompson sampling shows the item whose sampled click probability, drawn from its Beta posterior, is largest.
Common random numbers: in every run, the click that item a would produce in round t is fixed in advance, whatever the policy shows. Runs use the seeds 100, 101, … . “Starved” means that the best item received less than half of the rounds. The regret is the pseudo-regret, the sum over rounds of (best click probability) − (click probability of the item shown).
code/ch22_recommender_systems.py (Mulberry, bandit_run, bandit_curves, ips_experiment).