Shi Dong
An Information-Theoretic Analysis for Thompson Sampling with Many Actions
Shi Dong, Benjamin Van Roy
Neural Information Processing Systems http://nips.cc/
An Information-Theoretic Analysis for Thompson Sampling with Many Actions
Shi Dong, Benjamin Van Roy
However, this dependence is through entropy, which can become arbitrarily large as the number of actions increases. We establish new bounds that depend instead on a notion of rate-distortion. Among other things, this allows us to recover through information-theoretic arguments a near-optimal bound for the linear bandit. We also offer a bound for the logistic bandit that dramatically improves on the best previously available, though this bound depends on an information-theoretic statistic that we have only been able to quantify via computation.