  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 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.
