mlsanityData to 7 Oct 2026

Bayesian decision-making under misspecified priors with applications to meta-learning

arXiv 2107.01509 ↗First posted 3 Jul 2021cs.LG math.ST stat.MLcited by 43

Not on the map. Why?

Abstract (arXiv)

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 tildeO(H2 ε) 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 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.

Key facts. Cited by 43 papers in the map (data through 7 Oct 2026). Builds on 23 of its 54 references that are in the map. First posted on arXiv 3 Jul 2021.

Builds on

23 of 54 references.

References · 23

  1. 2016RL2: Fast Reinforcement Learning via Slow Reinforcement Learningcited by 490
  2. 2016Learning to reinforcement learncited by 369
  3. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  4. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  5. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  6. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  7. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  8. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  9. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  10. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  11. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  12. 2019Meta reinforcement learning as task inferencecited by 75
11 more
  1. 2021Meta-Thompson Samplingcited by 62
  2. 2020Impact of Representation Learning in Linear Banditscited by 51
  3. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
  4. 2020Meta-learning with Stochastic Linear Banditscited by 45
  5. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  6. 2013Thompson Sampling for Complex Bandit Problemscited by 43
  7. 2019Meta Dynamic Pricing: Transfer Learning Across Experimentscited by 41
  8. 2013Sequential Transfer in Multi-armed Bandit with Finite Set of Modelscited by 38
  9. 2019Comments on the Du-Kakade-Wang-Yang Lower Boundscited by 16
  10. 2019Thompson Sampling with Approximate Inferencecited by 15
  11. 2015On the Prior Sensitivity of Thompson Samplingcited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 11; 2023: 11; 2024: 8; 2025: 8; 2026: 1.

43 papers.

Sort:

By area:

  1. 2023Supervised Pretraining Can Learn In-Context Reinforcement Learningcited by 137
  2. 2024Can large language models explore in-context?cited by 75
  3. 2021Hierarchical Bayesian Banditscited by 33
  4. 2021Metadata-based Multi-Task Bandits with Bayesian Hierarchical Modelscited by 24
  5. 2022Multi-task Representation Learning with Stochastic Linear Banditscited by 20
  6. 2023Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delaycited by 17
  7. 2021Metalearning Linear Bandits by Prior Updatecited by 15
  8. 2025Toward Efficient Exploration by Large Language Model Agentscited by 15
  9. 2022Mixed-Effect Thompson Samplingcited by 14
  10. 2023Leveraging Demonstrations to Improve Online Learning: Quality Matterscited by 13
  11. 2025Step-DAD: Semi-Amortized Policy-Based Bayesian Experimental Designcited by 12
  12. 2022Meta-Learning for Simple Regret Minimizationcited by 10
31 more
  1. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  2. 2022Multi-Task Off-Policy Learning from Bandit Feedbackcited by 9
  3. 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
  4. 2023Thompson Sampling with Diffusion Generative Priorcited by 7
  5. 2024Meta Clustering of Neural Banditscited by 7
  6. 2022Meta Reinforcement Learning with Finite Training Tasks -- a Density Estimation Approachcited by 6
  7. 2024reBandit: Random Effects based Online RL algorithm for Reducing Cannabis Usecited by 6
  8. 2022Gaussian Imagination in Bandit Learningcited by 5
  9. 2022Meta-Learning Hypothesis Spaces for Sequential Decision-makingcited by 5
  10. 2022Meta-Learning Adversarial Banditscited by 5
  11. 2023Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learningcited by 5
  12. 2023Bayesian Active Learning in the Presence of Nuisance Parameterscited by 5
  13. 2024Diffusion Models Meet Contextual Banditscited by 5
  14. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  15. 2025Contextual Thompson Sampling via Generation of Missing Datacited by 5
  16. 2021Safe Data Collection for Offline and Online Policy Learningcited by 4
  17. 2024Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Banditscited by 4
  18. 2025Best Arm Identification with Possibly Biased Offline Datacited by 4
  19. 2022Tractable Optimality in Episodic Latent MABscited by 3
  20. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 3
  21. 2024A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Liftingcited by 3
  22. 2025Contextual Online Pricing with (Biased) Offline Datacited by 3
  23. 2024Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regretcited by 1
  24. 2025A Classification View on Meta Learning Banditscited by 1
  25. 2022Online Bayesian Meta-Learning for Cognitive Tracking Radarcited by 0
  26. 2023Sequential Best-Arm Identification with Application to Brain-Computer Interfacecited by 0
  27. 2023Finite-Time Logarithmic Bayes Regret Upper Boundscited by 0
  28. 2023Interactive Graph Convolutional Filteringcited by 0
  29. 2025Priors Matter: Addressing Misspecification in Bayesian Deep Q-Learningcited by 0
  30. 2025An Information-Theoretic Analysis of OOD Generalization in Meta-Reinforcement Learningcited by 0
  31. 2026Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shiftcited by 0