Foundations of Reinforcement Learning IX: Posterior Sampling Has Bayesian Regret at Most Textbook
A learner repeatedly chooses one of decisions and sees a noisy reward for that decision only. In the Bayesian version of this multi-armed bandit problem, the unknown reward distributions are drawn from a known prior. Posterior sampling, also called Thompson sampling or probability matching, plays each decision with the probability that it is optimal given…