Prior-free and prior-dependent regret bounds for Thompson Sampling
We consider the stochastic multi-armed bandit problem with a prior distribution on the reward distributions. We are interested in studying prior-free and priordependent regret bounds, very much in the same spirit than the usual distributionfree and distribution-dependent bounds for the non-Bayesian stochastic bandit. We first show that Thompson Sampling attains an optimal prior-free bound in the sense that for any prior distribution its Bayesian regret is bounded from above by 14 √ nK. This result is unimprovable in the sense that there exists a prior distribution such that any algorithm has a Bayesian regret bounded from below by 1 20 √ nK. We also study the case of priors for the setting of Bubeck et al. [2013]   (where the optimal mean is known as well as a lower bound on the smallest gap) and we show that in this case the regret of Thompson Sampling is in fact uniformly bounded over time, thus showing that Thompson Sampling can greatly take advantage of the nice properties of these priors.
Paper summary: -------------- The paper 
      provides an analysis Bayesian regret of Thompson sampling (where Bayesian 
      regret is defined as an average regret weighted according to a prior 
      distribution over the parameters) and regret bounds for Thompson sampling 
      in the setting of the paper of Bubeck, Perchet, and Rigollet 2013, where 
      it is assumed that the mean reward of the best arm and the gap to the 
      second-best arm are known, but the identity of the best arm is unknown. In 
      this setting the authors improve the upper bound by a log(log(1/epsilon)) 
      factor, thus closing the gap with the lower bound down to a constant. 
      Quality, clarity, originality, and significance: 
      ------------------------------------------------ The paper is very 
      technical and impractical. Most of the paper is devoted to technical 
      proofs that could be moved into appendices, whereas no motivation 
      whatsoever is provided for the model studied. Main criticism: 
      --------------- As already said, my main criticism is about lack 
      of motivation behind studying the model studied by the authors. In the 
      first setting considered the authors assume that a prior over parameters 
      (arm biases) is provided and study the performance of the model with 
      respect to this prior. It would be good to have some examples, where this 
      assumption and evaluation measure are plausible. In the second and third 
      settings the authors go into further extreme and assume that the bias of 
      the best arm and the gap to the second-best arm are known and only the 
      identity of the best arm is unknown. Once again, there are no examples, 
      where this assumption is satisfied. There are also no examples or 
      discussion of how the results of the paper could be useful for solving 
      some other theoretical problems. So we have neither practical nor 
      theoretical motivation. From looking at the details of the proofs (which 
      are the main part of the paper) it is hard to see whether any of the ideas 
      could be reused in some other settings. ======================== 
      Response to the rebuttal ======================== I thank the 
      authors for their response. I would like to point out that providing the 
      reader a motivation why to read your paper is not called "waste of time 
      and space". Going straight to the formulas could probably be considered 
      marginally acceptable at COLT (although I would criticize it there as 
      well), but at NIPS you have a much broader audience and not everybody is 
      dealing with your specific problem on a daily basis. I would like to point 
      out that none of my questions were actually addressed. I asked to give at 
      least one specific example (out of "hundreds of papers written since the 
      70s"), where evaluation of an algorithm with respect to a known prior over 
      the parameters would be a reasonable thing to do, but got none. I asked to 
      give some motivation for your study of the BPR setting - you are referring 
      me for an example to the review of Reviewer_7, but Reviewer_7 just says 
      that it "can be useful in real applications" and provides no example, so I 
      cannot consider it as a satisfactory answer to my question. I have read 
      the BPR paper and it provides very clear motivation for studying the model 
      in the setting they study it; they have very clear proofs with ideas that 
      are easy to reuse; and they have a lot of results that go far beyond the 
      BPR model, such as lower bounds. But even after reading the BPR paper I 
      see no motivation to study the problem in the setting you study it and it 
      is your job to explain why is it interesting. And it is not explained on 
      page 2 you are referring me to. And one more point - you did not 
      discuss how your analysis of Thompson sampling in the Bayesian setting 
      relates to Bayes-UCB.