Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper establishes the theory for quantifying the sensitivity of a class of Bayesian bandit algorithms under misspecified prior, with Thompson sampling being a special case. It is also shown that the sensitivity bound is tight in the worst-case sense. Using the sensitivity analysis, the paper studies the sample complexity of Bayesian meta-learning in two special cases (Beta prior+Bernoulli reward and Gaussian prior+Gaussian reward). Finally, the aforementioned theory is generalized to the more general setting, the Bayesian POMDPs.


main_review: This is a well-written paper with clear exposition, rigorous proof, and extensive simulations. My question is as follows:

- the authors claim that the theory is designed for meta-learning problems with short task horizons, but the lower bound seems to hold in a large-horizon regime. Is that correct? 

limitations_and_societal_impact: A discussion on the potential negative societal impact of the work may be added.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: In this paper, the authors study how prior mis-specification would impact the performance of bayesian bandit algorithms. In particular, the authors provide an upper and a lower bound for a wide class of algorithms, which include Thompson sampling algorithms as a special case. The results are complemented by applications in meta learning and numerical experiments.
main_review: The results in this paper are novel to the best of my knowledge. Prior sensitivity is a relatively open area in the analysis of Bayesian bandit algorithms. Since Thompson sampling algorithm, a particular Bayesian bandit algorithm, is widely used in many applications such as ads display and dynamic pricing, the results in this paper could be of broad interest.

Some comments for improvement. It looks like the key step in showing the upper bound is Proposition 3.4, it would thus be helpful if the proof sketch/intuition of this Proposition could be clearly provided.

Also, the coupling Q plays an important role in the proof of upper bound because the history of the two versions (one with correct prior one without) of the algorithm could have different history. I would suggest the authors to deliver a more constructive way to establish Q in appendix B.
limitations_and_societal_impact: N.A.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focus on the performance of the Thompson sampling algorithm under the misspecification of the prior distribution. The authors propose a general family of n-Monte Carlo algorithm, which contains the canonical TS algorithm as a special case. The authors then proceed to show that the regret difference of a misspecified prior up to horizon H of an n-MC algorithm is of order H^2*eps, where eps is the amount of misspecification measured by the total variation distance. The results are applied to the meta-learning setting, in which one also aims to learn the prior. The paper concludes by a synthetic numerical experiment to show the benefit of meta-learning.
main_review: - The paper is well-written. The exposition is clear and easy to follow. I appreciate that the authors provide enough explanation and sketch of the proof for me to follow the main text.
- The submission is particularly long (48 pages) and I could not go through all the details of the proof in the appendix. However, through a superficial read of the proof, I am inclined that the results are correct.
- I would appreciate if the authors can also discuss and contrast the (prior) misspecification bounds in this paper with the (model) misspecification bounds for the UCB algorithm (and other non-Bayesian algorithms).
- Can the authors provide any theoretical justification for the efficiency of learning the prior in the meta-learning setting (compared to using a uniform prior)?
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the effect of prior misspecification in Thompson sampling (TS) and related posterior sampling bandit algorithms. They are able to show that the regret due to such algorithms using a misspecified prior incurs additional regret that is linear in the total variation distance between the improper and true prior.

Additionally, the paper considers estimating such priors in a meta-learning setting, where an agent interacts sequentially with multiple bandit instances whose model parameters are sampled from the same unknown prior. The authors provide bounds on the total variation distance for the estimated priors when the prior is Beta or Gaussian.

main_review: The paper considers an important problem in Thompson sampling with a misspecified prior. To my knowledge, this is a novel consideration in bandit literature, as prior work in studying TS algorithms always assumes the true prior is given. The authors are able to show that TS with a misspecified prior incurs regret that scales with its total variation distance from the unknown, true prior, which is an original result. The paper also considers meta-learning a prior using sequential interactions across multiple bandit episodes, and derives bounds on the total variation distance for Beta and Gaussian priors. They also demonstrate empirically that meta-learning the prior can outperform using an uninformative prior in various bandit settings. 

Overall, I thought that the paper was organized clearly and made a solid and original contribution to Bayesian bandit literature. I do question the practicality of the proposed meta-learning approach as it relies on instances of forced exploration in order to estimate the prior parameters. I would have liked to see a theoretical result that showed that the total regret across multiple episodes outperforms not refining the prior across episodes but avoiding the need for forced exploration, i.e. show that meta-learning can achieve regret that is sub-linear in the number of episodes. In addition, I would be interested in some discussion on whether the sensitivity bounds can lead to new TS algorithms when the prior is misspecified, such as increasing the covariance of the misspecified prior can lead. Nevertheless, I believe the paper is a solid submission and recommend that it be accepted.

limitations_and_societal_impact: The paper is primarily theoretical, providing a novel sensitivity bound that shows how regret of TS algorithms changes when the prior is misspecified. As alluded to earlier, I believe the impact of the paper would be greater if the authors were able to use the result to propose new TS algorithms that would be more robust to such misspecification. The authors point to this as a potential avenue for future research.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This article presents some very nice results on posterior-sampling-based bandit algorithms with mis-specified priors. The algorithms are those like Thompson sampling, in which the actions selected are functions of draws from the posterior distribution to date (an approximation of knowledge gradient is also analysed as part of a wider class of posterior-sample-based decision algorithms, and this is shown to be an improvement on TS). Results apply both to standard bandit settings and to meta-learning settings in which a series of short episodes are attempted. Theory and experiments are impressive.
main_review: The article presents a nice general framework for learning, and a method for analysing performance when the prior used by the learning algorithm is not the same as the distribution that the environment "uses". There are philosophical considerations as to whether the environmental "prior" is a meaningful construct, but mis-specified priors are definitely worth considering. I like the generality of the framework and of the methods that are developed. The article is very nicely written, especially in the way it makes it clear that the mathematics can be used in a suite of related problems. I have minor comments on the presentation:
- It's slightly bizarre at the start of Theorem 4.1 to suddenly have "there exists an algorithm explore(t)", when the previous paragraph is describing an explicit exploration algorithm. Noting the relationship between the presented strategy and the strategy of the theorem would be better.
- It is somewhat disappointing that the strategies being deployed in the meta-learning are all purely exploitative. This feels like we are therefore solving the "wrong" problem in some sense. Some discussion of this would be useful.

I have not checked the proofs. I am afraid that begin expected to review 36 pages of appendix in the timeframe of a conference submission is not reasonable. I actually recommend that the article should not be published here only because of this, and instead submitted to a journal where proper review can be carried out.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: Thank you to the authors and the reviewers for their contributions to the conference! This paper introduces a novel sensitivity analysis of Bayesian bandit algorithms such as Thompson Sampling under misspecified priors. Misspecification is clearly an important problem in practice, and the review team unanimously appreciated the paper. I am happy to recommend acceptance.
Decision: Accept (Spotlight)