An Information-Theoretic Analysis for Thompson Sampling with Many Actions
Information-theoretic Bayesian regret bounds of Russo and Van Roy [8]  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.
POST REBUTTAL:  Thanks for the response. My scores stay the same. Of course I encourage the authors to try and relax the assumptions for the generalized linear models and prove the conjecture.  Summary.  The paper provides a Bayesian regret-analysis of Thompson sampling for linear bandits with large action spaces. Previous bounds depended on the number of actions, which is known to be suboptimal when the number of actions is super-exponential in the dimension. Existing Bayesian analysis for this case relied on the conversion from frequentist bounds, which is (a) excessively complicated and (b) leads to looser bounds.  The authors give a simple and rather intuitive analysis based on the observation that the learner only needs to learn the unknown parameter up to some epsilon and so the entropy of the unknown parameter should be replaced by the entropy of a partitioning random variable.  The new analysis is applied to the standard linear bandit model where O(d sqrt(T log(T))) bounds are provided that improve on the state-of-the-art by a factor of sqrt(log(T)). The bounds are also applied to generalized linear bandits. More comments on this to follow.  Major comments.  I think this is a nice paper. Some questions/comments. First, there is an assumption that the rewards are bounded and this seems quite important for the proofs. For the standard frequentist analysis, however, one assumes the rewards are subgaussian. Of course you can apply a union bound over all the observed rewards, but I think a log(T) factor in the regret will sneak in if you do this. Do you know how to relax the assumption on the noise to (say) conditionally subgaussian?  Assumptions 1 and 3 both seem quite unreasonable. In applications of GLMs that I know of the rewards are almost always Bernoulli and the expected rewards are almost always very small. Eg., the probability that a user clicks on something. Can you say more about whether or not these assumptions can be relaxed?  Clarity.  The paper is mostly well written. I think some discussion of the assumptions is appropriate and there are a few typos (see below).  Quality.  The proofs seem to be correct. The problem is interesting.  Originality.  This is the weakest part of the paper. The idea to use a discretization is quite an obvious one and the analysis does not change that much from previous work in this area.  Significance.  I think there will be plenty of interest in this paper. The paper would be more significant if the assumptions for generalized linear models were more realistic.  Overall.  A good paper. Perhaps the authors 'stopped early' because there are lots of unresolved questions and the boat is not pushed too much further. Still, I prefer to see it accepted.  Minors.  * Is \mathcal Y finite? Measurability of g? Almost sure qualifications on conditional expectations.  * Why not mention in (1) that I(. ; . | . ) is the conditional mutual information?  * Both H_t and ~H_t generate different sigma-algebras, but the extra information in ~H_t does not change the conditional measure (which is just the posterior - though this is not unique... measurability, brr). Anyways, is there some subtle reason behind this change or do you just want to emphasize the view of sampling thetas?  * In (d) of Eq. (6) should ~H_T be ~H_{T-1}?  * L137. p^* should be theta^*?  * You could be consistent about the order of theta^* and psi in (6) and the display after, though of course it is symmetric.  * L158. \in -> \subset  * L160. Did you mean to say that the action set and parameter space or dual to each other? Otherwise I don't see where you actually assume the inner product is bounded. The 'normalizing factor' of 1/2 is nonstandard. Why not just let mu(a, theta) =  and assume || <= 1/2 for all a, theta?  * Assumption 1 is quite restrictive. One reason to introduce GLMs in the first place is to behave well with Bernoulli noise.  * Assumption 3 is also quite restrictive.