An Information-Theoretic Analysis for Thompson Sampling with Many Actions

Shi Dong, Benjamin Van Roy

Information-theoretic Bayesian regret bounds of Russo and Van Roy capture the dependence of regret on prior uncertainty. However, this dependence is through entropy, which can beco…