Bayesian decision-making under misspecified priors with applications to meta-learning
Authors: Max Simchowitz
Christopher Tosh
Akshay Krishnamurthy
Daniel Hsu
Thodoris Lykouris
Miroslav Dudík
Robert E. Schapire
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Thompson Sampling
Bayesian Bandits
Bayesian Decision Making
Meta-Learning

Abstract: Thompson sampling and other Bayesian sequential decision-making algorithms are among the most popular approaches to tackle explore/exploit trade-offs in (contextual) bandits.  The choice of prior in these algorithms offers flexibility to encode domain knowledge but can also lead to poor performance when misspecified.  In this paper, we demonstrate that performance degrades gracefully with misspecification.  We prove that the expected reward accrued by Thompson sampling (TS) with a misspecified prior differs by at most $\tilde{O}(H^2 \epsilon)$ from TS with a well-specified prior, where $\epsilon$ is the total-variation distance between priors and $H$ is the learning horizon.  

Our bound does not require the prior to have any parametric form.  For priors with bounded support, our bound is independent of the cardinality or structure of the action space, and we show that it is tight up to universal constants in the worst case.

Building on our sensitivity analysis, we establish generic PAC guarantees for algorithms in the recently studied Bayesian meta-learning setting and derive corollaries for various families of priors.  Our results generalize along two axes: (1) they apply to a broader family of Bayesian decision-making algorithms, including a Monte-Carlo implementation of the knowledge gradient algorithm (KG), and (2) they apply to Bayesian POMDPs, the most general Bayesian decision-making setting, encompassing contextual bandits as a special case. Through numerical simulations, we illustrate how prior misspecification and the deployment of one-step look-ahead (as in KG) can impact the convergence of meta-learning in multi-armed and contextual bandits with structured and correlated priors.

Bayesian decision-making under misspecified priors with applications to meta-learning
Max Simchowitz' Thodoris Lykouris
Christopher Tosh
Akshay Krishnamurthyf
Daniel Hsu
Miroslav Dudik
Robert Schapiret
Abstract
Thompson sampling and other Bayesian sequential decision makinng algorithms are among the most popular approaches tackle explore/exploit trade-offs in (con- textual) bandits. The choice prior in these algorithms offers flexibility to encode domain knowledge but can also lead poor performance when misspecified. In this paper, we demonstrate that performance degrades gracefully with misspecifica- tion. We prove that the expected reward accrued by Thompson sampling (TS) with a misspecified prior differr by at most (H)² from TS with well-specified prior, where c the total-variation distance between priors and H is the learning horizon.
Our bound does not require the prior to have any parametric form. For priors with bounded support, our bound is independent of the cardinality structure of the action space, and we show that is tight up to universal constants in the worst case.
sensitivity analysis, establish generic PAC guarantees for algo- rithms in the recently studied Bayesian meta- mecaa-eerrnng setting and derive corollaries for various families of priors. Our results generalize along two axes: (1) they apply to a broader family of Bayesian decision-making algorithms, including a Monte- Carlo implementation of the knowledge gradient algorithm (KG), and (2) they apply to Bayesian POMDPs, the most general Bayesian decision- meaiiinnnmmainnggg setting, encompassing contextual bandits as special case. Through numerical simula- tions, we illustrate how prior misspecification and the deployment of one-step look-ahead (as in KG) can impact the convergence of meta-learning in multi-armed and contextual bandits with structured and correlated priors.
Building
1 Introduction
Bayesian Decision-making algorithms are widely popular, due to both strong empirical performance and the flexibility afforded by incorporating inductive biases and domain knowledge through pri- ors. However, in practical applications, any chosen prior is at best approximation of the true environment which the algorithm deployed. This raises a critical question:
How sensitive are Bayesian decision-making algorithms prior misspecification?
For drecision-maiing problems with very large horizon, it suffices that the misspecified prior places a vamishingly small probability mass on the ground truth environment; this condition is referred to informally "grain of truth." This is because, in the large- trgge-horzoon limit, Bayesian algorithms (like many non- non-Bayesian methods) should converge to the optimal policy.
"Massachusetts Institute of Technology, ms msimchowmit..ed
CColumiia University
1 Mierosoot Research NYC
Massachusetts Institute of Technology
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

But in many practical settings, decision decision-making takes place on shorter time scales. Consider news recommendation website that, when presented with a new user, sequentially offers selection of currently trending articles. Such system may only have a few opportunities to make recommen- dations before the user decides to navigate away, leaving little time to correct for misspecified or underspecified prior knowledge. Such examples are described more broadly by the meta- meta-learning paradigm, where a single learning agent must complete multiple Hesparate-though-rrlatdd tasks.
In meta-learning problems, and in short-horizon problems more broadly, the "grain of truth" argument paints a rather uninformative picture. Consequently, recent work has begun to explore sensitivity bounds in applications with shorter horizons [L KKZ However, these recent works focus on particular classes of priors and/or reward models, as well on the Thompson sampling algorithm specifically. Notably, this leaves open questions about the extent to which prior sensitivity is deter- mined by properties of the Bayesian decision- maniing algorithm, the reward model, and the prior itself.
1.1 Our Contributions
Motivated by meta-learning problems with short task horizons, we establish general, distribution- independent, and worst-case optimal bounds on the sensitivity of Bayesian algorithms to prior misspecification. We focus on the Bayesian bandit setting, where a mean-vector "environment" f is drawn from a distribution P, and rewards for each action are drawn in accordance with μ.. We study the performance of Bayesian algorithms which operate according to misspecified prior P'.
Sensitivity of Thompson Sampling and Related Bayesian Bandit Algorithms. As a concrete example, we consider the expected reward obtained by Thompson sampling with misspecified prior p' under environments drawn from true prior
When the mean rewards lie in the range [0, 1]. as in the Bernoulli reward setting, we show that the difference in expected reward between Thompson sampling with P' and with P at most twice the total variation distance between P and P' multiplied by the square of the horizon length. We prove a lower bound demonstrating that, for worst-case priors, this result is tight up to constants. Moreover, our upper bound holds for any two priors P and P' and suffers no dependence on the complexity of the decision space.
We extend this result in two directions. First, we remove the boundedness requirement on the mean reward range, showing that so long as certain tail probability conditions the prior means are satisfied, similar result holds. Second, we generalize beyond Thompson sampling, bounding the prior sensitivity of a broad class of Bayesian bandit algorithms, which we term n-Monte Carlo algorithms. Our lower bounds extend to this class, verifying sharp dependence on the parameter n.
Sample Complexity of Bayesian Meta-Learning. We apply our prior sensitivity results to the Bayesian bandit meta-learning setting, in which a meta-learner iteratively interacts on bandit instances that are sampled from unknown prior distribution. Motivated by sensitivity analysis describe a generic algorithmic recipe for Bayesian meta-learning, in which the meta-learner explores for several episodes to estimate the prior and then exploits by instantiating Bayesian the learned prior. We formally consider two instantiations of this setup: (1) the Beta- -errnoull setting where the rewards are Bernoulli and the prior is a product of Beta distributions and (2) the Gaussian-Gaussian setting where the rewards are Gaussian and the prior is a Gaussian (with arbitrary covariance structure) over the means. We note that the but only for the diagonal covariance setting.
eeciision-mkee with
setting was recently studied
in IKZZ 21
Bayesian Decision-Making Beyond the Bandit Setting. A striking feature of our proof is that it makes no explicit reference to the structure of bandit decision decision-making. As a consequence, our results extend seamlessly to both contextual bandits and the most general Bayesian decision-makiin problem: Bayesian POMDPs. While our sensitivity bounds hold almost verbatim in these settings, we note that estimating the prior may be statistically much more challenging in these scenarios, so there is no free lunch. To facilitate readability of the paper, we defer all further discussion and formal results to Appendix
Experimental results. We complement our meta-learning theory with synthetic experiments in multi-armed and contextual bandit settings. Our experiments show the benefits of (a) meta-learning broadly, (b) estimating higher-order moments of the prior distribution, and (c) using less myopic
2

---

algorithms like the Knowledge Gradient [RPF12] over Thompson sampling when faced with structured environments.
1.2 Related Work
Bayesian Decision-Making, Bayesian decision-makee making broadly refers class of algorithms that use Bayesian methods to estimate various problem parameters, and then derive decision/al rules from these estimates. The study of Bayesian decision-making began with the seminal work of TThomson [Th33]] who introduced the Thompson sampling algorithm for adaptive experi- ment design in clinical trials. Thompson sampling later gained popularity in the reinforcement learning community as a means to solve multi-armed bandit and tabular reinforcement learning problems [Str00 (VR17), and has been extended in many directions AL17 AL GMM14) Re- cent years have seen the proliferation of other Bayesian decision-making and learning algorithms, including Information Directed Sampling [RRR6)) Two Thompson Sampling [Rus66] and Knowledge Gradient [RPF12].
Sensitivity Analysis and Frequentist Regret. The field of robust Bayesian analysis examines the sensitivity of Bayesian inference to prior and model misspecification (c.f., [BMP+94] 94)). These approaches typically do not consider secision-maaing. so they do not account for multi-step adaptive sampling inherent in our setting. More recent works study frequentist regret for Thompson sampling [AG12 KKM12). These guarantees can be interpreted as controlling the sensitivity to arbitrary degrees of prior misspecification, but consequently, they do provide a precise picture of how misspecification affects performance. Moreover, frequentist guarantees for Thompson sampling focus on relatively long learning horizons, so they are less relevant in the context of meta-learning with many short-horizon tasks.
Short-Horize Sensitivity. Most closely related to our paper are two previous works on sensitivity of Thompson sampling to small amounts of misspecification in short-horizon settings. (LL16] study the sensitivity of Thompson sampling for two-armed bandits when the prior has finite support. More recently, KKZ*+21 study meta-leaming with Thompson sampling and derive sensitivity bounds for Thompson sampling in multi-armed bandits with Gaussian rewards and independent-across- Gaussian priors. In contrast both of these works, the bounds presented in this work apply to arbitrary families of priors, more general decision-making problems, and to more general families of decision-makinnn algorithms. Further, as illustrated in Remark 2 our bounds are also tighter than those achieved by [K] when specialized to their precise setting. Finally, our lower bounds demonstrate that the square- horizon factor incurred in 2K unavoidable for worst-case priors (though perhaps not for their special case).
[BSZZ19] study sensitivity of general Bayesian algorithms in dynamic pricing context. Their approach requires "sufficiently random" reward noise and applies only to algorithms with a non- adaptive initial exploration phase (unlike true Thompson Sampling); under these conditions, they show that the trajectories under a well-specified and misspecified Bayesian decision maker can be coupled so that the two algorithms maintain the same posteriors with good probability. In contrast, our analysis applies only to Bayesian decision-making algorithms which have sufficient "internal randomness" (e.g., Thompson sampling, and more generally, the n-Monte Carlo algorithms). Our approach obviates assumptions about reward noise and initial exploration at the expense of slightly restricting the class of algorithms which our guarantees apply.
Meta- Meta-llarnnig and Meta-RL. Meta-learning is classical learning paradigm in which a learner faces many distinct- buttincttbu-relltee tasks [Th99 Thr98 Bax98 Bax00, HYCO1]. While the classical work primarily considered supervised learning tasks, recent, predominantly empirical work has focused on meta-reinforcement learning RL), where each task is itself a decision-making problem (c.f., [WKNT+ 17 DSC+16). This includes some Bayesian approaches (HGH+20) While there have been some theoretical results on Meta-RI. [ALB3]] CLP20 (HLD21 HCI+21I, apart are not aware of other theoretical treatments with Bayesian flavor.
from KKZ*211 21
Learning under model misspecification. This work studies specific notion of misspecification: running Bayesian decision-making algorithms with inexact approximations of true underlying prior. Numerous other types of mispecification have been considered by the learning theory community more
3

---

broadly, although typically in the absence of meta-learning and in frequentist settings. These include models where rewards may be changing with time [GMITBGZI4] CSLZZ8
WL21] or adversarially corrupted [[MPLI8 GKTT9 [S21]. or where simple function class (e.g.. linear models) is used to approximate more complex reward function [DWW Y20 VRD19 LSW20 FGMZ20). The Bayesian analog of these models is that the likelihood is misspecified, which is quite different from the prior misspecification considered here. Translating these notions of misspecification to Bayesian decision-making and unifying these lines of work remains an exciting direction for future research.
BGZ14
Setting and Notation
Throughout, use bold v to denote vectors and non-bold Va to denote scalars. When the vector va. has a subscript, th,e denotes its coordinates.
Bayesian Bandit Learning under Misspecification. A Bayesian bandit learning instance is speci- fied by (a) abstract action space A, (b) parametric family of priors Po indexed parameters E è over mean vectors μ E R- with coordinates Pa, and (c) function
R - A A mapping mean vectors μ distributions over reward vectors E RR- such that the expected reward under D(1) is i.e., Ey=D(H) [r] yu Note that this general setup allows the prior Po to encode complex dependencies between the mean rewards Paa of actions a E A.
We consider an episodic bandit protocol with horizon H. First, μl ~ Pe is drawn from the prior. Then, at each time step h 1, 2, ... H. the learner's ' policy, specified by algorithm alg, selects an action O₁ A. Simultancously, a reward vector ra is drawn independently from D(u). and the learner observes reward Th Th.an. The choice of action a₁ may depend the partial trajectory Tn-1 = (01, r.,.... a4-14 1h-1). We let Po.a denote the joint law over μa and the full trajectory TH- while expectations are denoted Eg,alg- We abbreviate the full trajectory T TH. We denote the cumulative reward
R(6, alg) Eo,alg
H E Th
Egg,alg
E Man
Bayesian Learning Algorithms. We study a class of algorithms alg(0) also parameterized by 0 E O. For concreteness, the reader may think of alg(() as corresponding to Thompson sampling, where the learner internally computes posteriors using Pa as its prior. More general classes of Bayesian algorithms
defined in Section 3.1] We are interested in the consequences of misspecifi- cation; that is, interacting with μ ~ Pp. but executing alg(8") for some other 8' + 9. Note that our notation for the induced law on the trajectory is Po Po.alg(0")-
Episodic Bayesian Meta-Learning. We apply the above framework the problem of Bayesian meta-learning. Let 0* E be a ground-truth parameter. At each episode t == 1,,,..... T, a mean parameter (*) is drawn i.i.d. from Pa.. Simultaneooully, the learner commits to a (potentially non- Bayesian) exploration strategy explore()) and collects the induced trajectory T(t)_ At the end of T episodes, the learner selects a parameter E θ as a function of !) , ((7), The learner's performance is evaluated on the expected reward of the plug-in algorithm on 0: R(0', alg(()).
Further notation. Given two probability distributions P and Q over the same probability space F), we denote their total variation TV Q) == sups [ - Q[E]| and Kullback-Leibler divergence KL(P) Q). If P is joint distribution of random variables (X, Y, Z,...), -), P(X) denotes the marginal of under P. and P(Y]X) the conditional distribution (as function of random variable X). We define the diameter of
vector diam(H) supae A Ma infae.A Ma, which is a random variable when μ is drawn from Pp. Throughout, log(-) denotes the natural logarithm. Given a space X, we let ((X)) be the set of probability distributions on X; see Appendix B. for measure-theorcen considerations.
"In fact, our analysis extends to more general cases where the reward distribution is parameterized by more than just the vectors, but restrict ourselves to the current setting for ease of exposition.

---

3 Prior Sensitivity in Bayesian Learning
This section states sensitivity bounds for various Bayesian bandit algorithms and families of priors, starting with the concrete instance of Thompson sampling under priors with bounded-range means. Our results extend almost verbatim more general decision-making tasks such contextual bandits; see Appendix L for further details. Throughout, we use the fact that the posterior distribution of the mean 1l given trajectories TA does not depend on the choice of learning algorithm alg; hence, we denote these posteriors Pol. 1
Recall the classical Thompson sampling algorithm: at each step h, (S(@) draws mean j4g Pol: TA-1] and selects the reward-maximizing action dĄ E arg max, MM We say that the prior Po is B-bounded if Po(diam(1u)) - B] For Thompson sampling under B-bounded priors, we have the following result:
Corollary 3.1. Let Po be B-bounded. Then, the suboptimality of misspecified Thompson sampling TS' on instance is at most
|R0 TS(O)) R(B, TS( S 2H2 2 || Po.) B.
Corollary 3.1 follows directly from Theorem 3.2 which we state in Section 3.2] and which generalizes the statement of the corollary along two axes: to more general family of Bayesian algorithms that we call "n-Monte Carlo" and to less restrictive conditions on the behavior of diam such as sub-Gausee Gaussian tails. Due to lack of space, we focus on the first such generalization; the second direction is more technical in nature, and we leave its exposition to Appendix B.2
3.1 n-Monte Carlo algorithms
Unfortunately, for arbitrary Bayesian bandit algorithms, the behavior under two different priors cannot always be controlled in terms of the total variation distance of their priors. Indeed, consider an algorithm that always pulls a particular arm a* if the prior places any probability mass on a mean for which a* is best; clearly, this algorithm's behavior is not robust small changes in its prior distribution. However, many important Bayesian bandit algorithms, such as Thompson sampling, not arbitrary functions of their priors; rather, they select actions based on their internal posterior distribution in a relatively stable manner. We call such algorithms n-Monte Carlo algorithms.
Definition 3.1 (n-Monte Carlo algorithm). Given
0, we say that a family of algorithms alg(-) parameterized by 0 E θ is n-Monte Carlo if, for any 0, 0', step h 2 1, and partial trajectory Th-1.
TV [V (an Th-1) Palg(or) (as Th-1)) S (VP Th-1) Par TT-1)).
In words, n-Monte Carlo algorithms are those Bayesian algorithms for which small changes in the posterior distribution result in small changes (up to a multiplicative factor of n)) in the distribution over actions. Note that on the left-hand side, we do not need to specify the true 0*, because each algorithm's choice of an action can only depend on Tạ The nomenclature arises because any algorithm that selects actions based exclusively n n-Monte Carlo. However, the definition is more general and in Appendix C we describe various algorithms that satisfy the n-Monte Carlo property, summarizing key insights here:
samples from its posterior Po Tn-1) is
We show that (S(0) is 1-Monte Carlo.
We introduce generalization of Thompson sampling, which we call k-shot Thompson sampling (k-TSS00), that samples i means ju,,...; fa i..dd. from the posterior Po Th-1], and selects the action an E arg max, (ax...in...........
}. We show that (-)) is k-Monte Carlo.
We introduce Monte Carlo approximation of the knowledge gradient algorithm (RPF12), which we call two-step Receding Horizon Control (2-RHC(8)) This algorithm non non-myopic in that chooses an action that maximizes the expected value at the subsequent time (according to its own posterior updates). We show that when finite, 2-RHC(0) n-Monte Carlo for some n that is polynomial in [A| and the number of Monte Carlo samples it draws from its posterior.
'Note that whenever Ty lies in the support of Po, the posterior Po Th-1] well-defined and unique, even Ta-1 was generated by interacting with mean μ Py for some 8' + When T does not lie in the support of Pa. we allow Polm Tn-1] 1] to be any distribution over fu (for concreteness, one may default to (=(m)). Note, however, that although Po[p T may not be uniquely defined, Po Pa (T TT uniquely defined and independent of 0.
44 is always
5

---

3.2 General Sensitivity Upper and Lower Bounds
We are now ready to state general prior sensitivity bound for n-Monte Carlo algorithms. For
simplicity, we state our bounds for B-bounded priors, that is, P& 22 (p) _ B 1, and under
natural sub-Guub Gaussian tail condition stated formally Appendix (Theorem B.2).
Theorem 3.2. Let alg(-) be n-Monte Carlo family of algorithms horizon H N. and let 8, E è. Setting e = TV || P J. we have the following guarantees.
(a) If Po is B-bounded, then [R(8, alg(()) R(0, alg( 2nH B.
(b) If Pe is coordinate-wise Saus-aaasnan then
R(0, alg(0)) - R(0, alg( 2
(diam(Eola)) + 8 B log min (1,
Next, we complement our upper bound with a lower bound that matches Theorem 3.2 a) for n-shot Thompson sampling (an n-Monte Carlo algorithm) up to a multiplicative constant:
Theorem 3.3 (Lower Bound, Informal). For any parameter n E N, horizon H > 1, number of arms
N |A| H, and separation < 1/nH, there exist priors Po and Py over bounded means E [o, 1j such that (Po || Por) and
(1 o(1)) nH?e
R(0, where the o(1) decays to zero as 1/H, H/N, enH + O.
See Theorem D.I for precise, quantitative statement and Appendix for full proof.
Remark (Comparison to Ö(vH) regret guarantees). first glance, Theorem 3.3 appears incon- sistent with known upper bounds for Thompson sampling which show that regret re relative to the best action in hindsight scales sublinearly as Ó ((V[A ([AH) in the horizon H. Notice however that our lower bound requires the number of actions |A] to scale at least linearly in H, so the bound applies in regime where regret upper bounds are in fact vacuous. Instead, the purpose of our lower bound to quantify the influence of the misspecified prior for fixed horizons, but where the magnitude (V(P Per) of the misspecification may be arbitrarily small.
Proof ideas. One of the key ingredients the proof Theorem 3.2 and result which may of independent interest, is the following bound on the total variation of the trajectory of an algorithm run with the true prior and the same algorithm run with an incorrect prior.
Proposition 3.4. Let alg(.) be an n-Monte Carlo family of algorithms horizon H N. Then,
TV(P P2) S 2nH (Po Por),
where PH (o. TH) and Pt Po.alg(0))(p,, TH).
A full proof is given in Appendix B.6 and relies on careful coupling argument between the two trajectories detailed therein. As a concrete warmup, we illustrate this coupling for Gaussian bandit instance in Appendix B.5. The factor of H arises from telescoping argument (Lemmal B.9 based on the performance-differeee
lemma [ak03
For B-bounded priors, Proposition 3.4 directly translates into the sensitivity bound Theorem 3.2 a), where the difference in rewards can be bounded BH times the probability that the trajectory of alg(f) differs from the trajectory of alg(6'). Addressing more general tail conditions like sub- Gaussianity requires more care; see Appendix for details.
4 Meta-learning
In this section, we apply the above prior sensitivity guarantees to episodic Bayesian meta-learning and obtain sample-efficiency guarantees for canonical Bayesian bandit setups.
Suppose an episodic Bayesian meta-learner uses an exploration strategy explore in T episodes and computes an estimate / = ((T(1),.. -(²)) of the ground-truth parameter 0* Suppose further that, for any s, E (0, 1), with probability at least 8 over the realizations of the episodes and internal

---

randomization of the meta-learner, the estimate 0 satisfies TV Pb) S e. Then, Theorem 3.2 implies that, for any n-Monte Carlo algorithm alg(-), the relative performance of alg(0) compared to (0*) is (essentially) bounded as O( over horizon H.
Our task of designing meta-learners is thus reduced to that of designing estimators (and exploration strategies) for O* that enjoy convergence guarantees in TV distance. This is quite general recipe that can produce concrete meta-learmin algorithmss in many Bayesian bandit settings. We explain how to do in two setups: (1) Pe- is product of Beta distributions, and the rewards are Berouuli;; (2) Pa- is multivariate Gaussian and the rewards are Gaussian.
4.1 Beta Priors and Bernoulli Rewards
We first consider the situation where the prior distribution a product of Beta distributions Pa-
X Beta( (*) and the reward distribution is product of Bernoulli distributions D(z)
X a (ern( Recall that Beta(a, () for > 0 and 3 >> 0 is continuous probability distribution
supported on (0, 1), and hence our parameter space θ is the (strictly) positive orthant in 22
Our approach is to directly estimate the parameters 0* (3* from the observed rewards in the T episodes. Since the family Beta distributions is am exponential family [Bro86] (with (a. 3) being the natural parameters), can appeal to general statistical theory to bound the total variation distance between two such distributions in terms of their parameter distance.
Suppose we adopt the exploration strategy where arm 1 is selected in the first n rounds in each of the first A/| episodes, arm 2 in the next T/| episodes, and so on. (We assume the horizon and satisfy H 2 n 2 2.) We focus on the estimation of (1), as the exact same approach works for all the arms. Let X, denote the cumulative reward collected in the first n rounds of episode t. Then, the random variables XI,..., XT/LA/ |la are i.i.d. draws from Beta- Binomial distribution with parameters (ai 37, n),, where n denotes the number of trials of the binomial component. The first and second moments of X, are
na 0j + 3
na + a5) + B (ai + (1 + aj + BB)
m = [[,]]]
and m. = [[
These moments uniquely determine of and 8j as long as n 2 2. Therefore, we can estimate (af 3t) using plug-in estimates of the first two moments (m, m²) via the method of moments [TGG94). Using this approach, we obtain the following sample complexity guarantee for estimating the prior distribution:
Theorem 4.1. The exploration strategy and estimator described above enjoy the following guarantee. If Pe- = BaEA (Bet( PT) and D(u) = 8ae Bern(pa), then there is constant C depending only on (8"))) such that, for any e, 5 E (0, 1), if H 2 2 and
T C |A log (A158)
2²
then (P || Pb) $ 2--8 8.
The proof of the theorem given Appendix
F.
4.2 Gaussian Priors and Gaussian Rewards
We now consider the situation where the prior distribution is multivariate Gaussian Pe- N(p., ..) in R-A,, and the reward distribution a spherical Gaussian distribution D(μ) OT). Note that such prior distribution is able to capture correlations between the arms' mean rewards in an episode, which cannot be captured by the product- priors in the previous subsection (nor in previous work KKZ*
We again directly estimate the parameters
(M., V..) using simple exploration strategy and the method of moments. In each episode (which we assume to have H 2 2), we select independent and uniformly random actions the first two rounds. Let a, and b, denote the actions taken in episode I, and let re and s, denote the corresponding observed rewards. Our estimates for v, and L, based on
7

---

Caussian MAB, A-B, Hm
Uinea
OrackeTS
Gredett
2750
Figure I: Learning curves for Gaussian MAB and linear CB experiments. We run 100 replicates per algorithm and visualize standard errors with bands. For meta-learners we the number of exploration rounds and display the performance of the best configuration at each point, which we call the upper envelope.
the information collected in I episodes ard
A T
LAi2 T
D
reea and
Σ
rest (ea, 0/ eb, 0%a,) DD.
For these estimators, we have the following theorem.
Theorem 4.2. The exploration strategy and estimator described above enjoy the following guarantee. If Po. (V,,, v.) and (()) N (1, o I)), then there constant depending only on (vx, V.)
and o² such that, for any 5 E (0, 1), if H 2 2 and
T C (IAI + | log(1/5))
E2
then PPTV Pp) sd 8.
The proof of the theorem and the precise dependence on v., v. and 0² are given in Appendix F.2 The quartic dependence |A| is due to estimating v. it improves to |A|2 if v, is known.
Remark 2 (Comparison to 2 KKZ*+1|
study the case where Po. = (Nv,, of. which product-form prior over means fe with known og For ē |AI 1lv 2 2o oo they show that
RRO, TS(O)) R(O, TS(O)) SO (112 oo too (l/(
H2E
On the other hand, Theorem 3.2 applied to the 1-Monte Carlo Thompson Sampling algorithm
(and bounding diam(v.) v.) < P. lloo) yields the same inequality, but with replaced by TV of )) || Ni (1 [|p 0112/00. Note that always larger than by a fac- tor of least VIAl: thus, our result strictly sharper.
Experiments
We demonstrate the generality of our results in three distinct meta-learning experimental settings. First, we study a simple multi-armed bandit scenario with Gaussian prior and Gaussian rewards, where demonstrate how meta-learinng higher-order moments of the prior significantly improve performance. Next, we consider a Gaussian linear contextual bandits scenario, to demonstrate the generality of Bayesian meta-learning. Finally, we study problem with discrete priors, where, in addition to the value of meta-learning, we see that look-ahead algorithms substantially outperform Thompson sampling. Additional experimental details presented in Appendix A
interesting multi-armed bandit
Gaussian MAB. Our first scenario is multi-armed bandit problem with Gaussian prior and Gaussian reward. The instance has [A| = 6 arms and each episode has horizon H = 10. The prior M(,,, V.) where v, [0.5, 0, O, 1, 0, 0] and v, has block structure so that arms 1,
This estimator can he generalized to explore more of episode use more the observed rewards. 'The following optimizes Lemma 5 of [KZ 21 over its free parameter 8 0 for small.

---

Algurihi performance
Arm rewards each task
(2.0223))
(3
T4 (0-21)
DracketG
T5 (0.01)
VodaKo
(6(0.01)
Dracents
0.66
T8(0.91)
(9.00)))
193
292
T10 (0.00.
T11 (0.05)
(0.00.))
Didribution of the first ar pulled by wath woorthhm
(0.00.
T14 (0.00)
T15 (0.01)
6.20
T16 (0.01)
A6
A30
A1
A1
A20
Mrrals
Figure 2: Synthetic experiments with discrete MAB for |A| 20 and H = 10. Left: visualization of the instance showing the reward for each of the arms each of the 16 possible tasks along with the prior distribution over tasks (probabilities rounded, actual values are 9/40 and 1/120). Top right: learning curves for algorithms (100 replicates, error bands tune the number of exploration rounds and plot upper envelopes for meta- leamnse. Bottom right: empirical distribution of the first arm pulled in each episode by each algorithm. Note that the color scale is non-linear.
standard errors, we
highly correlated, and analogously for arms 4,5,6. The rewards are Gaussian with variance 1, which known all learners.
We run four algorithms. Two are nnn-meta-learning Thompson sampling algorithms: OracleTS, which uses the correct prior, and MisTS, which uses the misspecified prior NN, I). We also run MetaTS: : no-cov which only attempts to meta-learn the prior mean P4 and assumes that the prior co- variance matrix is the identity (this algorithm is essentially the one studied in KKK=2111 Finally, our algorithm MetaTS: full which meta-learns both the prior mean and covariance. Both meta-learners in explore-ther thallorrmthe--oomii fashion where the first To episodes used for exploration
In Figure [ we plot the cumulative average per-episode reward for each algorithm, where for the meta- learners we sweep
many choices of To and display the pointwise best (i.e., the upper envelope). The experiment clearly shows the value of meta-learning as both
and MetaTS: full quickly outperform misspecified TS. Additionally, we also see the importance of learning the covari- ance matrix, even though it can require many samples. Indeed, the final performance of MetaTS: full with To 5K, ignoring the regret incurred due to exploration, is competitive with OracleTS, while MetaTS: no- cov asymptotes to much lower performance (see Figure B in Appendix A)
Gaussian linear contextual bandits. Our second experiment concerns Gaussian linear contextual bandits. Here we run OracleTS, MisTS, and MetaTS: full, on a synthetic linear contextual bandit problem where there are |A|] = 6 actions each with a d 6 dimensional action feature (generated stochastically at each time step), and with horizon H 20. The prior is over the linear parameter μ that determines the reward for action-feature x Rd r(a) (M1( , 1). We set the prior as (1, V.)) where V, is scaled-down version of the block diagonal matrix used in the previous experiment. In the right panel of Figure [ we again see that by meta-learning the prior, we quickly outperform the misspecified approach and asymptotically achieve the oracle performance. This demonstrates that Bayesian meta-learning is quite broadly applicable and highlights the importance of our general theoretical development.
Discrete bandits. Finally, we study a synthetic MAB setting with |A| = 20 arms and a prior sup- ported on finite set of 16 reward distributions (tasks), under each of which rewards are deterministic. The instance is visualized in the left panel of Figure 2 It is constructed so that each task has a unique optimal arm and there are four arms that can quickly identify which task the agent is in (arms A1, A6,
For MetaTS:no-cow we follow [KKZ 21) exploration, switching to TS with the current prior estimate for the rest of the episode. On the other hand, MetaTS: full explores for all time steps in the first To episodes.
and only use the first step of each exploration episode for

---

AI1, A16), so that it can infer the optimal arm. Additionally, the prior is concentrated on the first four tasks, so that pulling the first identifying arm almost always reveals the current task.
We evaluate 6 algorithms: Oracle, Misspecified, and Meta-learning each with TS and Monte-Cart Knowledge Gradient (an instantiation of the 2-RHC(0) algorithm detailed in Appendix C as the base learners, and we visualize the results in the top right panel of Figure 2 Perhaps more revealing the bottom right panel of Figure 2 where we visualize the empirical distribution over the first arm pull in each episode for each algorithm. We see that OracleTS typically plays uniformly over arms A2-A5 in the first round as these are highly likely be the optimal arm under the prior, while MisTS plays uniformly over the 16 plausibly optimal arms. MetaTS quickly learns to play uniformly over arms A2-A5 and is asymptotically competitive with OracleTS.
The interesting property of this instance is that playing the identifying arms is crucial for optimal behavior. However, since TS is myopic and these arms never produce large rewards, TS will never play them. Thus, to achieve optimal behavior, we must use a less myopic base learner like Knowledge Gradient. As can be seen, both OracleKG and MisKG first play the identifying arms, where the oracle almost always pulls the first one while MisKG plays them uniformly. The performance of OraclekG is much better than all TS configurations. Finally, the meta-learning configuration of Knowledge Gradient quickly learns to pull the first identifying arm and competes with OracleKG.
6 Discussion
In our simulations, we demonstrated the superiority of more expressive prior families (e.g.. modeling means and covariances) and non-myopic base algorithms (e.g., Knowledge Gradient) over less expressive priors (e.g.. product measures) and greedy base learners (e.g.. Thompson sampling). Notably, the generality and flexibility of our theoretical contributions ensure robustness to prior misspecificatioon even for these richer priors and sophisticated base learners.
Still, theory and experiments alike point to tradeoff: despite the potential for improved performance, richer prior families are harder to learn, and some base learners (e.g., n--Mote Carlo algorithms for large n) can be more sensitive to incorrect priors. It is exciting direction for future work to investigate the joint problems of model selection (over priors) and algorithm selection (over base learners) in order to optimally navigate these tradeoffs. Perhaps model and algorithm selection can be coupled so that certain base learners exhibit improved performance, or greater robustness, over certain classes of priors. We would like further understand how these tradeoffs interface with computational burdens of using certain priors and base learners, and whether our sensitivity analysis extends to computationally efficient approximations of sampling-based based decision-making algorithms (e.g., via Laplace approximations, MCMC, Gibbs Sampling, and Variational Methods; the long-horizon performance of Thompson sampling under approximate inference has already been studied [PAYDI9)). Finally, we hold hope that a more instance-dependent analysis may improve our sensitivity bounds for certain families of priors, which may in turn inform more clever exploration strategies that circumvent worst-case tradeoffs.
Acknowledgements
The authors thank Wen Sun for many discussions that helped shape the current paper. At the time of writing. Max Simchowitz was generously supported by Open Philanthropy Al Fellowship, and the research was initiated during his internship at MSR New York and PhD at UC Berkeley. Research was initiated during Thodoris Lykouris" postdoc at MSR New York. Daniel Hsu is supported by NSF grants CCF-1740833, DMREF- 1534910, JUS-1563785, a Bloomberg Data Science Research Grant, a JP Morgan Faculty Award, and Sloan Research Fellowship; Christoper Tosh is also supported by NSF grant CCF-1740837 and Daniel Hsu's JP Morgan Faculty Award.
References
[AG12] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, 2012.
[AL17] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In International Conference on Artificial Intelligence and Statistics, 2017.
10

---

[AL18] Mare Abeille and Alessandro Lazaric. Improved regret bounds for thompson sampling in linear quadratic control problems. International Conference on Machine Learning. 2018.
[ALB13] Mohammad Gheshlaghi Azar, Alessandro Lazarie, and Emma Brunskill. Sequential transfer in multi-armed bandit with finite set of models. In Advances in Neural Information Processing Systems, 2013.
[AYS15] Yasin Abbasi-Yadkori and Csaba Szepesvári. Bayesian optimal control of smoothly parameterized systems. In Conference on Uncertainty in Artificial Intelligence, 2015.
[Bax98] Jonathan Baxter. Theoretical models of learning to learn. In Learning to learn. Springer, 1998.
[Bax00] Jonathan Baxter. model of inductive bias learning. Journal of Artificial Intelligence Research, 2000.
[BGZ14] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armedt bandit problem with non-stationary rewards. Advances in Neural Information Processing Systems, 2014.
[BMD+05] Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with bregman divergences. Journal of Machine Learning Research, 2005.
[BMP+94] James O Berger, Elías Moreno, Luis Raul Pericchi, M Jesús Bayarri, José M Bernardo, Juan A Cano, Julián De la Horra, Jacinto Martín, David Ríos-Insúa, Bruno Betrò, A. Dasgupta, Paul Gustafson, Larry Wasserman, Joseph B. Kadane, Cid Srinivasan, Michael Lavine, Anthony O'Hagan, Wolfgang Polasek, Christian P. Robert, Constanti- nos Goutis, Fabrizio Ruggeri, Gabriella Salinetti, and Siva Sivaganesan. An overview of robust bayesian analysis. Test, 1994.
[Bro86]
Lawrence D Brown. Fundamentals of Statistical Exponential Families with Applica- lions in Statistical Decision Theory. Institute of Mathematical Statistics, 1986.
[BSLZ19] Hamsa Bastani, David Simchi-Levi, and Ruihao Zhu. Meta dynamic pricing: Transfer learning across experiments. Available at SSRN 3334629, 2019.
[CLP20) Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. In International Conference Machine Learning, 2020.
[CSLZI8] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Hedging the drift: Learning to optimize under non non-stationarity. Available at SSRN 3261050, 2018
[DKWY20] Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is a good representa- tion sufficient for sample efficient reinforcement learnin?? In International Conference on Learning Representations, 2020.
[DSC 16] Yan Duan, John Schulman, Xi Chen, Peter L Bartlett, Ilya Sutskever, and Pieter Abbeel. 2L Fast reinforcement learning via slow reinforcement learning. arXiv:1611.02779 2016.
[FGMZ20] Dylan J Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. In Advances in Neural Information Processing Systems, 2020.
[GKT19] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, 2019.
[GM11] Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switch- ing bandit problems. In Conference on Algorithmic Learning Theory, 2011.
[GMM14] Aditya Gopalan, Shie Mannor, and Yishay Mansour. Thompson sampling for complex online problems. In International Conference Machine Learning, 2014.
11

---

[GMPT15] Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian reinforcement learning: survey. Foundations and Trends in Machine Learning. 2015.
[HCJ+21] Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal repre- sentation learning for linear bandits and linear RL. In International Conference on Machine Learning, 2021.
[HGH+20] Jan Humplik, Alexandre Galashov, Leonard Hasenclever, Pedro A Ortega, Yee Whye Teh, and Nicolas Heess. Meta reinforcement learning task inference. In International Conference on Learning Representations, 2020.
[HYC01] Sepp Hochreiter, A Steven Younger, and Peter R Conwell. Learning to learn using gradient descent. In International Conference on Artificial Neural Networks, 2001.
[Kak03] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University College London, 2003.
[KKM12] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International Conference on Algorith- mic Learning Theory, 2012.
[KK*+21] Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-wei Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvari. Meta-thompson sampling. arXiv: 102.0:2002.06129 2021.
[Lin02] Torgny Lindvall. Lectures on the Coupling Method. Courier Corporation, 2002.
[LL16] Che-Yu Yu Liu and Lihong Li. On the prior sensitivity of thompson sampling. In International Conference on Algorithmic Learning Theory, 2016.
[MPL18] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust adversarial corruptions. In Symposium Theory of Computing, 2018. 8.
[LSW20] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature rep- resentations in bandits and in rl with generative model. In International Conference on Machine Learning, 2020.
[Mur12] Kevin Murphy. Machine learning: a probabilistic perspective. MIT press, 2012.
[OVR17] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning, 2017.
[PAYD19] My Phan, Yasin Abbasi Yadkori, and Justin Domke. Thompson sampling and approxi- mate inference. Advances in Neural Information Processing Systems, 2019.
[RPF12] Ilya O Ryzhov, Warren B Powell, and Peter Frazier. The knowledge gradient algorithm for general class of online learning problems. Operations Research, 2012.
[Rus16] Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, 2016.
[RVR16] Daniel Russo and Benjamin Van Roy. An information-thhorctie analysis of thompson sampling. The Journal of Machine Learning Research, 2016.
[Str00] Malcolm Strens. A bayesian framework for reinforcement learning. In International Conference on Machine Learning, 2000.
[SWDN09] Songsak Sriboonchita, Wing-Keung Wong, Sompong Dhompongsa, and Hung T Nguyen. Stochastic dominance and applications to finance, risk and economics. CRC Press, 2009.
[TGG94] Ram C. Tripathi, Ramesh C. Gupta, and John Gurland. Estimation of parameters in the beta binomial model. Annals of the Institute of Statistical Mathematics, 1994.
12

---

[Tho33] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
[Thr96] Sebastian Thrun. Explanation-basel neural network learning: A lifelong learning approach. Springer, 1996.
[Thr98] Sebastian Thrun. Lifelong learning algorithms. In Learning learn. Springer, 1998.
[Ver18] Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge University Press, 2018.
[VRD19] Benjamin Van Roy and Shi Dong. Comments on the kwk.ak-waaaggaaeeeee.ee yang lower bounds. 1rXiv:1911.070000 1.099100 2019.
[WKNT+17] 17] Jane Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning to reinforcement learn. In Annual Meeting of the Cognitive Science Society, 2017.
[WL21] Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Conference Learning Theory, 2021.
[YHLD21] Jiaqi Yang. Wei Hu, Jason D Lee, and Simon S Du. Impact of representation learning in linear bandits. In International Conference on Learning Representations, 2021.
[ZS21] Julian Zimmert and Yevgeny Seldin. Tsallis-nff: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 2021.
13


Reviews:
[{"review_id": "qVUUHc-Zx7m", "reviewer": "Reviewer_A8Q1", "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.\n\nAdditionally, 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nOverall, 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "ioT6dIE60Ft", "reviewer": "Reviewer_BAyg", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n- 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.\n- 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.\n\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "bsOVoAjB2yq", "reviewer": "Reviewer_Du9Y", "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.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a well-written paper with clear exposition, rigorous proof, and extensive simulations. My question is as follows:\n\n- 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? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A discussion on the potential negative societal impact of the work may be added.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "bq2cXVfy-U", "reviewer": "Reviewer_2kq1", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n- 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.\n- 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).\n- 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)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "X9LUh38mJi0", "reviewer": "Reviewer_Dwdc", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nSome 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.\n\nAlso, 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

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)