summaries: 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. 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.   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. 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.  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.
abstractText: 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 Õ(Hε) from TS with a well-specified prior, where ε 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 MonteCarlo 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.
authors.name: Max Simchowitz
authors.name: Christopher Tosh
authors.name: Akshay Krishnamurthy
authors.name: Daniel Hsu
authors.name: Thodoris Lykouris
authors.name: Miroslav Dudík
authors.name: Robert Schapire
references.authors: Shipra Agrawal Navin Goyal
references.title: Analysis of thompson sampling for the multi-armed bandit problem
references.venue: Conference on Learning Theory,
references.authors: Marc Abeille Alessandro Lazaric
references.title: Linear thompson sampling revisited
references.venue: International Conference on Artificial Intelligence and Statistics,
references.authors: Marc Abeille Alessandro Lazaric
references.title: Improved regret bounds for thompson sampling in linear quadratic control problems
references.venue: International Conference on Machine Learning,
references.authors: Mohammad Gheshlaghi Azar Alessandro Lazaric Emma Brunskill
references.title: Sequential transfer in multi-armed bandit with finite set of models
references.venue: Advances in Neural Information Processing Systems,
references.authors: Yasin Abbasi-Yadkori Csaba Szepesvári
references.title: Bayesian optimal control of smoothly parameterized systems
references.venue: Conference on Uncertainty in Artificial Intelligence,
references.authors: Jonathan Baxter. Theoretical models of learning to learn
references.title: In Learning to learn
references.venue: Springer,
references.authors: Jonathan Baxter
references.title: A model of inductive bias learning
references.venue: Journal of Artificial Intelligence Research,
references.authors: Omar Besbes Yonatan Gur Assaf Zeevi
references.title: Stochastic multi-armed-bandit problem with non-stationary rewards
references.venue: Advances in Neural Information Processing Systems,
references.authors: Arindam Banerjee Srujana Merugu Inderjit S Dhillon Joydeep Ghosh John Lafferty
references.title: Clustering with bregman divergences
references.venue: Journal of Machine Learning Research,
references.authors: Lawrence D Brown
references.title: Fundamentals of Statistical Exponential Families with Applications in Statistical Decision Theory
references.venue: Institute of Mathematical Statistics,
references.authors: Hamsa Bastani David Simchi-Levi Ruihao Zhu
references.title: Meta dynamic pricing: Transfer learning across experiments
references.venue: Available at SSRN 3334629,
references.authors: Leonardo Cella Alessandro Lazaric Massimiliano Pontil
references.title: Meta-learning with stochastic linear bandits
references.venue: International Conference on Machine Learning,
references.authors: Wang Chi Cheung David Simchi-Levi Ruihao Zhu
references.title: Hedging the drift: Learning to optimize under non-stationarity
references.venue: Available at SSRN 3261050,
references.authors: Simon S Du Sham M Kakade Ruosong Wang
references.title: and Lin F Yang
references.venue: Is a good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations,
references.authors: Yan Duan John Schulman Xi Chen Peter L Bartlett Ilya Sutskever Pieter Abbeel
references.title: RL2: Fast reinforcement learning via slow reinforcement learning
references.venue: arXiv:1611.02779,
references.authors: Dylan J Foster Claudio Gentile Mehryar Mohri Julian Zimmert
references.title: Adapting to misspecification in contextual bandits
references.venue: Advances in Neural Information Processing Systems,
references.authors: Anupam Gupta Tomer Koren Kunal Talwar
references.title: Better algorithms for stochastic bandits with adversarial corruptions
references.venue: Conference on Learning Theory,
references.authors: Aurélien Garivier Eric Moulines
references.title: On upper-confidence bound policies for switching bandit problems
references.venue: Conference on Algorithmic Learning Theory,
references.authors: Aditya Gopalan Shie Mannor Yishay Mansour
references.title: Thompson sampling for complex online problems
references.venue: International Conference on Machine Learning,
references.authors: Mohammad Ghavamzadeh Shie Mannor Joelle Pineau Aviv Tamar
references.title: Bayesian reinforcement learning: A survey
references.venue: Foundations and Trends® in Machine Learning,
references.authors: Jiachen Hu Xiaoyu Chen Chi Jin Lihong Li Liwei Wang
references.title: Near-optimal representation learning for linear bandits and linear RL
references.venue: International Conference on Machine Learning,
references.authors: Jan Humplik Alexandre Galashov Leonard Hasenclever Pedro A Ortega Yee Whye Teh Nicolas Heess
references.title: Meta reinforcement learning as task inference
references.venue: International Conference on Learning Representations,
references.authors: Sepp Hochreiter A Steven Younger Peter R Conwell
references.title: Learning to learn using gradient descent
references.venue: International Conference on Artificial Neural Networks,
references.authors: Sham Machandranath Kakade. On the sample complexity of reinforcement learning
references.title: PhD thesis
references.venue: University College London,
references.authors: Emilie Kaufmann Nathaniel Korda Rémi Munos
references.title: Thompson sampling: An asymptotically optimal finite-time analysis
references.venue: International Conference on Algorithmic Learning Theory,
references.authors: Branislav Kveton Mikhail Konobeev Manzil Zaheer Chih-wei Hsu Martin Mladenov Craig Boutilier Csaba Szepesvari
references.title: Meta-thompson sampling
references.venue: arXiv:2102.06129,
references.authors: Torgny Lindvall
references.title: Lectures on the Coupling Method
references.venue: Courier Corporation,
references.authors: Che-Yu Liu Lihong Li
references.title: On the prior sensitivity of thompson sampling
references.venue: International Conference on Algorithmic Learning Theory,
references.authors: Thodoris Lykouris Vahab Mirrokni Renato Paes Leme
references.title: Stochastic bandits robust to adversarial corruptions
references.venue: Symposium on Theory of Computing,
references.authors: Tor Lattimore Csaba Szepesvari Gellert Weisz
references.title: Learning with good feature representations in bandits and in rl with a generative model
references.venue: International Conference on Machine Learning,
references.authors: Kevin P Murphy
references.title: Machine learning: a probabilistic perspective
references.venue: MIT press,
references.authors: Ian Osband Benjamin Van Roy
references.title: Why is posterior sampling better than optimism for reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: My Phan Yasin Abbasi Yadkori Justin Domke
references.title: Thompson sampling and approximate inference
references.venue: Advances in Neural Information Processing Systems,
references.authors: Ilya O Ryzhov Warren B Powell Peter I Frazier
references.title: The knowledge gradient algorithm for a general class of online learning problems
references.venue: Operations Research,
references.authors: Daniel Russo
references.title: Simple bayesian algorithms for best arm identification
references.venue: Conference on Learning Theory,
references.authors: Daniel Russo Benjamin Van Roy
references.title: An information-theoretic analysis of thompson sampling
references.venue: The Journal of Machine Learning Research,
references.authors: Malcolm Strens
references.title: A bayesian framework for reinforcement learning
references.venue: International Conference on Machine Learning,
references.authors: Songsak Sriboonchita Wing-Keung Wong Sompong Dhompongsa Hung T Nguyen. Stochastic dominance applications to finance
references.title: risk and economics
references.venue: CRC Press,
references.authors: Ram C. Tripathi Ramesh C. Gupta John Gurland
references.title: Estimation of parameters in the beta binomial model
references.venue: Annals of the Institute of Statistical Mathematics,
references.authors: William R Thompson
references.title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
references.venue: Biometrika,
references.authors: Sebastian Thrun
references.title: Explanation-based neural network learning: A lifelong learning approach
references.venue: Springer,
references.authors: Sebastian Thrun. Lifelong learning algorithms
references.title: In Learning to learn
references.venue: Springer,
references.authors: Roman Vershynin
references.title: High-dimensional probability: An introduction with applications in data science
references.venue: Cambridge University Press,
references.authors: Benjamin Van Roy Shi Dong
references.title: Comments on the du-kakade-wang-yang lower bounds
references.venue: arXiv:1911.07910,
references.authors: Jane X Wang Zeb Kurth-Nelson Dhruva Tirumala Hubert Soyer Joel Z Leibo Remi Munos Charles Blundell Dharshan Kumaran Matt Botvinick
references.title: Learning to reinforcement learn
references.venue: Annual Meeting of the Cognitive Science Society,
references.authors: Chen-Yu Wei Haipeng Luo
references.title: Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach
references.venue: Conference on Learning Theory,
references.authors: Jiaqi Yang Wei Hu Jason D Lee Simon S Du
references.title: Impact of representation learning in linear bandits
references.venue: International Conference on Learning Representations,
references.authors: Julian Zimmert Yevgeny Seldin
references.title: Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits
references.venue: Journal of Machine Learning Research,
sections.heading: 1 Introduction
sections.text: 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 priors. However, in practical applications, any chosen prior is at best an approximation of the true environment in which the algorithm is deployed. This raises a critical question:
  How sensitive are Bayesian decision-making algorithms to prior misspecification?
  For decision-making problems with a very large horizon, it suffices that the misspecified prior places a vanishingly small probability mass on the ground truth environment; this condition is referred to informally as a “grain of truth.” This is because, in the large-horizon limit, Bayesian algorithms (like many non-Bayesian methods) should converge to the optimal policy.
  ∗Massachusetts Institute of Technology, msimchow@mit.edu †Columbia University ‡Microsoft Research NYC §Massachusetts Institute of Technology
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  But in many practical settings, decision-making takes place on shorter time scales. Consider a news recommendation website that, when presented with a new user, sequentially offers a selection of currently trending articles. Such a system may only have a few opportunities to make recommendations 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-learning paradigm, where a single learning agent must complete multiple disparate-though-related 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 [LL16, KKZ+21]. However, these recent works focus on particular classes of priors and/or reward models, as well as on the Thompson sampling algorithm specifically. Notably, this leaves open questions about the extent to which prior sensitivity is determined by properties of the Bayesian decision-making algorithm, the reward model, and the prior itself.
sections.heading: 1.1 Our Contributions
sections.text: Motivated by meta-learning problems with short task horizons, we establish general, distributionindependent, 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” µ 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 a 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 P .
  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 is 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 on the prior means are satisfied, a 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 an unknown prior distribution. Motivated by our sensitivity analysis we 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 a Bayesian decision-maker with the learned prior. We formally consider two instantiations of this setup: (1) the Beta-Bernoulli 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 Gaussian-Gaussian setting was recently studied in [KKZ+21] but only for the diagonal covariance setting.
  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-making. As a consequence, our results extend seamlessly to both contextual bandits and the most general Bayesian decision-making 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 E.
  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
  algorithms like the Knowledge Gradient [RPF12] over Thompson sampling when faced with structured environments.
sections.heading: 1.2 Related Work
sections.text: Bayesian Decision-Making. Bayesian decision-making broadly refers to a class of algorithms that use Bayesian methods to estimate various problem parameters, and then derive decision/allocation rules from these estimates. The study of Bayesian decision-making began with the seminal work of Thompson [Tho33], who introduced the Thompson sampling algorithm for adaptive experiment 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, OVR17], and has been extended in many directions [AL17, AL18, GMM14]. Recent years have seen the proliferation of other Bayesian decision-making and learning algorithms, including Information Directed Sampling [RVR16], Top-Two Thompson Sampling [Rus16], 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]). These approaches typically do not consider decision-making, 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 not 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-Horizon 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-learning with Thompson sampling and derive sensitivity bounds for Thompson sampling in multi-armed bandits with Gaussian rewards and independent-across-arm Gaussian priors. In contrast to 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-making algorithms. Further, as illustrated in Remark 2, our bounds are also tighter than those achieved by [KKZ+21] when specialized to their precise setting. Finally, our lower bounds demonstrate that the square-horizon factor incurred in [KKZ+21] is unavoidable for worst-case priors (though perhaps not for their special case).
  [BSLZ19] study sensitivity of general Bayesian algorithms in a dynamic pricing context. Their approach requires “sufficiently random” reward noise and applies only to algorithms with a nonadaptive 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 to which our guarantees apply.
  Meta-learning and Meta-RL. Meta-learning is a classical learning paradigm in which a learner faces many distinct-but-related tasks [Thr96, Thr98, Bax98, Bax00, HYC01]. While the classical work primarily considered supervised learning tasks, recent, predominantly empirical work has focused on meta-reinforcement learning (Meta-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-RL [ALB13, CLP20, YHLD21, HCJ+21], apart from [KKZ+21] we are not aware of other theoretical treatments with a Bayesian flavor.
  Learning under model misspecification. This work studies a specific notion of misspecification: running Bayesian decision-making algorithms with inexact approximations of a true underlying prior. Numerous other types of mispecification have been considered by the learning theory community more
  broadly, although typically in the absence of meta-learning and in frequentist settings. These include models where rewards may be changing with time [GM11, BGZ14, CSLZ18, WL21] or adversarially corrupted [LMPL18, GKT19, ZS21], or where a simple function class (e.g., linear models) is used to approximate a more complex reward function [DKWY20, 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.
sections.heading: 2 Setting and Notation
sections.text: Throughout, we use bold v to denote vectors and non-bold va to denote scalars. When the vector vh has a subscript, vh,a denotes its coordinates.
  Bayesian Bandit Learning under Misspecification. A Bayesian bandit learning instance is specified by (a) an abstract action space A, (b) a parametric family of priors Pθ indexed by parameters θ ∈ Θ over mean vectors µ ∈ RA with coordinates µa, and (c) a function D : RA → ∆(RA) mapping mean vectors µ to distributions over reward vectors r ∈ RA such that the expected reward under D(µ) is µ, i.e., Er∼D(µ)[r] = µ.5 Note that this general setup allows the prior Pθ to encode complex dependencies between the mean rewards µa of actions a ∈ A. We consider an episodic bandit protocol with horizon H . First, µ ∼ Pθ is drawn from the prior. Then, at each time step h = 1, 2, . . . ,H , the learner’s policy, specified by an algorithm alg, selects an action ah ∈ A. Simultaneously, a reward vector rh is drawn independently from D(µ), and the learner observes reward rh = rh,ah . The choice of action ah may depend on the partial trajectory τh−1 = (a1, r1, . . . , ah−1, rh−1). We let Pθ,alg denote the joint law over µ and the full trajectory τH , while expectations are denoted Eθ,alg. We abbreviate the full trajectory τ = τH . We denote the cumulative reward
  R(θ, alg) := Eθ,alg [∑H h=1 rh ] = Eθ,alg [∑H h=1 µah ] .
  Bayesian Learning Algorithms. We study a class of algorithms alg(θ) also parameterized by θ ∈ Θ. For concreteness, the reader may think of alg(θ) as corresponding to Thompson sampling, where the learner internally computes posteriors using Pθ as its prior. More general classes of Bayesian algorithms are defined in Section 3.1. We are interested in the consequences of misspecification; that is, interacting with µ ∼ Pθ, but executing alg(θ′) for some other θ′ ̸= θ. Note that our notation for the induced law on the trajectory is Pθ,alg(θ′).
  Episodic Bayesian Meta-Learning. We apply the above framework to the problem of Bayesian meta-learning. Let θ⋆ ∈ Θ be a ground-truth parameter. At each episode t = 1, 2, . . . , T , a mean parameter µ(t) is drawn i.i.d. from Pθ⋆ . Simultaneously, the learner commits to a (potentially nonBayesian) exploration strategy explore(t) and collects the induced trajectory τ(t). At the end of T episodes, the learner selects a parameter θ̂ ∈ Θ as a function of τ(1), . . . , τ(T ). The learner’s performance is evaluated on the expected reward of the plug-in algorithm on θ̂: R(θ⋆, alg(θ̂)).
  Further notation. Given two probability distributions P and Q over the same probability space (Ω,F), we denote their total variation TV(P ∥ Q) := supE∈F |P [E ]−Q[E ]| and Kullback-Leibler divergence KL(P ∥ Q). If P is a joint distribution of random variables (X,Y, Z, . . . ), P (X) denotes the marginal of X under P , and P (Y |X) the conditional distribution (as a function of random variable X). We define the diameter of a mean vector as diam(µ) := supa∈A µa− infa∈A µa, which is a random variable when µ is drawn from Pθ. Throughout, log(·) denotes the natural logarithm. Given a space X , we let ∆(X ) be the set of probability distributions on X ; see Appendix B.1 for measure-theoretic considerations.
  5In fact, our analysis extends to more general cases where the reward distribution is parameterized by more than just the mean vectors, but we restrict ourselves to the current setting for ease of exposition.
sections.heading: 3 Prior Sensitivity in Bayesian Learning
sections.text: 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 to more general decision-making tasks such as contextual bandits; see Appendix E for further details. Throughout, we use the fact that the posterior distribution of the mean µ given trajectories τh does not depend on the choice of learning algorithm alg; hence, we denote these posteriors Pθ[· | τh−1].6
  Recall the classical Thompson sampling algorithm: at each step h, TS(θ) draws a mean µ̃h ∼ Pθ[· | τh−1] and selects the reward-maximizing action ah ∈ argmaxa µ̃h,a. We say that the prior Pθ is B-bounded if Pθ[diam(µ) ≤ B] = 1. For Thompson sampling under B-bounded priors, we have the following result: Corollary 3.1. Let Pθ be B-bounded. Then, the suboptimality of misspecified Thompson sampling TS(θ′) on instance θ is at most
  |R(θ,TS(θ))−R(θ,TS(θ′))| ≤ 2H2 · TV(Pθ ∥ Pθ′) ·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 a 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-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 to small changes in its prior distribution. However, many important Bayesian bandit algorithms, such as Thompson sampling, are 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 n > 0, we say that a family of algorithms alg(·) parameterized by θ ∈ Θ is n-Monte Carlo if, for any θ, θ′, step h ≥ 1, and partial trajectory τh−1,
  TV(Palg(θ)(ah | τh−1) ∥ Palg(θ′)(ah | τh−1)) ≤ n · TV(Pθ(µ | τh−1) ∥ Pθ′(µ | τh−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 θ⋆, because each algorithm’s choice of an action can only depend on τh−1. The nomenclature arises because any algorithm that selects actions based exclusively on n samples from its posterior Pθ(µ | τh−1) is 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:
  • We show that TS(θ) is 1-Monte Carlo. • We introduce a generalization of Thompson sampling, which we call k-shot Thompson sampling
  (k-TS(θ)), that samples k means µ̃1, . . . , µ̃k i.i.d. from the posterior Pθ[· | τh−1], and selects the action ah ∈ argmaxa max{µ̃1,a, . . . , µ̃k,a}. We show that k-TS(θ) is k-Monte Carlo. • We introduce a Monte Carlo approximation of the knowledge gradient algorithm [RPF12], which we call two-step Receding Horizon Control (2-RHC(θ)). This algorithm is non-myopic in that it chooses an action that maximizes the expected value at the subsequent time (according to its own posterior updates). We show that when A is finite, 2-RHC(θ) is n-Monte Carlo for some n that is polynomial in |A| and the number of Monte Carlo samples it draws from its posterior.
  6Note that whenever τh lies in the support of Pθ , the posterior Pθ[µ | τh−1] is well-defined and unique, even if τh−1 was generated by interacting with mean µ ∼ Pθ′ for some θ′ ̸= θ. When τh−1 does not lie in the support of Pθ , we allow Pθ[µ | τh−1] to be any distribution over µ (for concreteness, one may default to Pθ[µ]). Note, however, that although Pθ[µ | τh−1] may not be uniquely defined, Pθ,alg[τh−1 | µ] is always uniquely defined and independent of θ.
sections.heading: 3.2 General Sensitivity Upper and Lower Bounds
sections.text: We are now ready to state a general prior sensitivity bound for n-Monte Carlo algorithms. For simplicity, we state our bounds for B-bounded priors, that is, Pθ[diam(µ) ≤ B] = 1, and under a natural sub-Gaussian tail condition stated formally in Appendix B.2 (Theorem B.2). Theorem 3.2. Let alg(·) be an n-Monte Carlo family of algorithms on horizon H ∈ N, and let θ, θ′ ∈ Θ. Setting ε = TV(Pθ ∥ Pθ′), we have the following guarantees.
  (a) If Pθ is B-bounded, then |R(θ, alg(θ))−R(θ, alg(θ′))| ≤ 2nH2ε ·B. (b) If Pθ is coordinate-wise σ2-sub-Gaussian, then
  |R(θ, alg(θ))−R(θ, alg(θ′))| ≤ 2nH2ε ( diam(Eθ[µ]) + σ ( 8 + 5 √ log ( |A|2 min{1,2nHϵ} ))) .
  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 ∈ N, horizon H ≫ 1, number of arms N = |A| ≫ H , and separation ϵ≪ 1/nH , there exist two priors Pθ and Pθ′ over bounded means µ ∈ [0, 1]N such that TV(Pθ ∥ Pθ′) = ϵ and
  R(θ, n-TS(θ)) ≥ R(θ, n-TS(θ′)) + (1− o(1)) · nH 2ϵ
  2 ,
  where the o(1) decays to zero as 1/H , H/N , ϵnH → 0.
  See Theorem D.1 for a precise, quantitative statement and Appendix D for a full proof. Remark 1 (Comparison to Õ( √ H) regret guarantees). At first glance, Theorem 3.3 appears inconsistent with known upper bounds for Thompson sampling which show that regret relative to the best action in hindsight scales sublinearly as Õ( √ |A|H) 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 a regime where regret upper bounds are in fact vacuous. Instead, the purpose of our lower bound is to quantify the influence of the misspecified prior for fixed horizons, but where the magnitude TV(Pθ ∥ Pθ′) of the misspecification may be arbitrarily small.
  Proof ideas. One of the key ingredients in the proof of Theorem 3.2, and a result which may be 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 on horizon H ∈ N. Then,
  TV(PH ∥ P ′H) ≤ 2nH · TV(Pθ ∥ Pθ′),
  where PH = Pθ,alg(θ)(µ, τH) and P ′H = Pθ,alg(θ′)(µ, τH).
  A full proof is given in Appendix B.6 and relies on a careful coupling argument between the two trajectories detailed therein. As a concrete warmup, we illustrate this coupling for a Gaussian bandit instance in Appendix B.5. The factor of H arises from a telescoping argument (Lemma B.9) based on the performance-difference lemma [Kak03].
  For B-bounded priors, Proposition 3.4 directly translates into the sensitivity bound in Theorem 3.2(a), where the difference in rewards can be bounded as BH times the probability that the trajectory of alg(θ) differs from the trajectory of alg(θ′). Addressing more general tail conditions like subGaussianity requires more care; see Appendix B for details.
sections.heading: 4 Meta-learning
sections.text: 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(t) in T episodes and computes an estimate θ̂ = θ̂(τ(1), . . . , τ(T )) of the ground-truth parameter θ⋆. Suppose further that, for any ε, δ ∈ (0, 1), with probability at least 1− δ over the realizations of the episodes and internal
  randomization of the meta-learner, the estimate θ̂ satisfies TV(Pθ⋆ ∥ Pθ̂) ≤ ε. Then, Theorem 3.2 implies that, for any n-Monte Carlo algorithm alg(·), the relative performance of alg(θ̂) compared to alg(θ⋆) is (essentially) bounded as Õ(nH2ε) over horizon H .
  Our task of designing meta-learners is thus reduced to that of designing estimators (and exploration strategies) for θ⋆ that enjoy convergence guarantees in TV distance. This is quite a general recipe that can produce concrete meta-learning algorithms in many Bayesian bandit settings. We explain how to do so in two setups: (1) Pθ⋆ is a product of Beta distributions, and the rewards are Bernoulli; (2) Pθ⋆ is a multivariate Gaussian and the rewards are Gaussian.
sections.heading: 4.1 Beta Priors and Bernoulli Rewards
sections.text: We first consider the situation where the prior distribution is a product of Beta distributions Pθ⋆ =⊗ a∈A Beta(α ⋆ a, β ⋆ a) and the reward distribution is a product of Bernoulli distributions D(µ) =⊗
  a∈A Bern(µa). Recall that Beta(α, β) for α > 0 and β > 0 is a continuous probability distribution supported on (0, 1), and hence our parameter space Θ is the (strictly) positive orthant in R2|A|. Our approach is to directly estimate the parameters θ⋆ = (α⋆,β⋆) from the observed rewards in the T episodes. Since the family of Beta distributions is an exponential family [Bro86] (with (α, β) being the natural parameters), we 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 T/|A| episodes, arm 2 in the next T/|A| episodes, and so on. (We assume the horizon H and n satisfy H ≥ n ≥ 2.) We focus on the estimation of (α⋆1, β⋆1), as the exact same approach works for all of the arms. Let Xt denote the cumulative reward collected in the first n rounds of episode t. Then, the random variables X1, . . . , XT/|A| are i.i.d. draws from a Beta-Binomial distribution with parameters (α⋆1, β ⋆ 1 , n), where n denotes the number of trials of the binomial component. The first and second moments of Xt are
  m⋆1 = E[Xt] = nα⋆1
  α⋆1 + β ⋆ 1
  and m⋆2 = E[X2t ] = nα⋆1(n(1 + α ⋆ 1) + β ⋆ 1)
  (α⋆1 + β ⋆ 1)(1 + α ⋆ 1 + β ⋆ 1)
  .
  These moments uniquely determine α⋆1 and β ⋆ 1 as long as n ≥ 2. Therefore, we can estimate (α⋆1, β⋆1) using plug-in estimates of the first two moments (m⋆1,m ⋆ 2) 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 Pθ⋆ = ⊗ a∈A Beta(α ⋆ a, β ⋆ a) and D(µ) = ⊗ a∈A Bern(µa), then there is a constant C depending only on (α⋆,β⋆) such that, for any ε, δ ∈ (0, 1), if H ≥ 2 and
  T ≥ C · |A| 2 log(|A|/δ) ε2 ,
  then P[TV(Pθ⋆ ∥ Pθ̂) ≤ ε] ≥ 1− δ.
  The proof of the theorem is given in Appendix F.1.
sections.heading: 4.2 Gaussian Priors and Gaussian Rewards
sections.text: We now consider the situation where the prior distribution is a multivariate Gaussian Pθ⋆ = N (ν⋆,Ψ⋆) in RA, and the reward distribution is a spherical Gaussian distribution D(µ) = N (µ, σ2I). Note that such a prior distribution is able to capture correlations between the arms’ mean rewards in an episode, which cannot be captured by the product-form priors in the previous subsection (nor in previous work [KKZ+21]).
  We again directly estimate the parameters θ⋆ = (ν⋆,Ψ⋆) using a simple exploration strategy and the method of moments. In each episode (which we assume to have H ≥ 2), we select independent and uniformly random actions in the first two rounds. Let at and bt denote the actions taken in episode t, and let rt and st denote the corresponding observed rewards. Our estimates for ν⋆ and Ψ⋆ based on
  the information collected in T episodes are7
  ν̂ := |A| T T∑ t=1 rteat and Ψ̂ := |A|2 T T∑ t=1 rtst ( eate T bt + ebte T at ) − ν̂ν̂T.
  For these estimators, we have the following theorem. Theorem 4.2. The exploration strategy and estimator described above enjoy the following guarantee. If Pθ⋆ = N (ν⋆,Ψ⋆) andD(µ) = N (µ, σ2I), then there is a constant C depending only on (ν⋆,Ψ⋆) and σ2 such that, for any ε, δ ∈ (0, 1), if H ≥ 2 and
  T ≥ C · (|A| 4 + |A|3 log(1/δ))
  ε2 ,
  then P[TV(Pθ⋆ ∥ Pθ̂) ≤ ε] ≥ 1− δ.
  The proof of the theorem and the precise dependence on ν⋆, Ψ⋆, and σ2 are given in Appendix F.2. The quartic dependence on |A| is due to estimating Ψ⋆; it improves to |A|2 if Ψ⋆ is known. Remark 2 (Comparison to [KKZ+21]). [KKZ+21] study the case where Pθ⋆ = N (ν⋆, σ20I), which is a product-form prior over means µ with known σ20 . For ϵ̃ = |A| · ∥ν⋆ − ν̂∥∞/σ0, they show that8
  |R(θ,TS(θ))−R(θ,TS(θ̂))| ≤ O ( ∥ν⋆∥∞ + σ0 √ log(H/ϵ̃) ) ·H2ϵ̃.
  On the other hand, Theorem 3.2 applied to the 1-Monte Carlo Thompson Sampling algorithm (and bounding diam(ν⋆) ≤ ∥ν⋆∥∞) yields the same inequality, but with ϵ̃ replaced by ϵ = TV(N (ν⋆, σ20I) ∥ N (ν̂, σ20I)) ≤ ∥ν⋆ − ν̂∥2/σ0. Note that ϵ̃ is always larger than ϵ by a factor of at least √ |A|; thus, our result is strictly sharper.
sections.heading: 5 Experiments
sections.text: 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 we demonstrate how meta-learning higher-order moments of the prior can significantly improve performance. Next, we consider a Gaussian linear contextual bandits scenario, to demonstrate the generality of Bayesian meta-learning. Finally, we study a more interesting multi-armed bandit problem with discrete priors, where, in addition to the value of meta-learning, we see that look-ahead algorithms can substantially outperform Thompson sampling. Additional experimental details are presented in Appendix A.
  Gaussian MAB. Our first scenario is a 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 is N (ν⋆,Ψ⋆) where ν⋆ = [0.5, 0, 0, 0.1, 0, 0] and Ψ⋆ has block structure so that arms 1, 2, 3 are
  7This estimator can be generalized to explore for more of the episode and use more of the observed rewards. 8The following optimizes Lemma 5 of [KKZ+21] over its free parameter δ > 0 for ϵ̃ small.
  highly correlated, and analogously for arms 4, 5, 6. The rewards are Gaussian with variance 1, which is known to all learners.
  We run four algorithms. Two are non-meta-learning Thompson sampling algorithms: OracleTS, which uses the correct prior, and MisTS, which uses the misspecified prior N (0, I). We also run MetaTS:no-cov which only attempts to meta-learn the prior mean µ0 and assumes that the prior covariance matrix is the identity (this algorithm is essentially the one studied in [KKZ+21]). Finally, our algorithm is MetaTS:full which meta-learns both the prior mean and covariance. Both meta-learners are run in an explore-then-commit fashion where the first T0 episodes are used for exploration.9
  In Figure 1, we plot the cumulative average per-episode reward for each algorithm, where for the metalearners we sweep over many choices of T0 and display the pointwise best (i.e., the upper envelope). The experiment clearly shows the value of meta-learning as both MetaTS:no-cov and MetaTS:full quickly outperform misspecified TS. Additionally, we also see the importance of learning the covariance matrix, even though it can require many samples. Indeed, the final performance of MetaTS:full with T0 = 5K, ignoring the regret incurred due to exploration, is competitive with OracleTS, while MetaTS:no-cov asymptotes to a much lower performance (see Figure 3 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 xa ∈ Rd as r(a) ∼ N (⟨µ,xa⟩, 1). We set the prior as N (1,Ψ⋆) where Ψ⋆ is a scaled-down version of the block diagonal matrix used in the previous experiment. In the right panel of Figure 1 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 supported on a 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,
  9For MetaTS:no-cov, we follow [KKZ+21] and only use the first step of each exploration episode for 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 T0 episodes.
  A11, 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-Carlo Knowledge Gradient (an instantiation of the 2-RHC(θ) 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 is 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 to 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.
sections.heading: 6 Discussion
sections.text: 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 misspecification even for these richer priors and sophisticated base learners.
  Still, theory and experiments alike point to a tradeoff: despite the potential for improved performance, richer prior families are harder to learn, and some base learners (e.g., n-Monte Carlo algorithms for large n) can be more sensitive to incorrect priors. It is an 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 to 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 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 [PAYD19]). 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.
sections.heading: Acknowledgements
sections.text: 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 an Open Philanthropy AI 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, IIS-1563785; a Bloomberg Data Science Research Grant, a JP Morgan Faculty Award, and a Sloan Research Fellowship; Christoper Tosh is also supported by NSF grant CCF-1740833 and Daniel Hsu’s JP Morgan Faculty Award.
title: Bayesian decision-making under misspecified priors with applications to meta-learning