mlsanityData to 7 Oct 2026

PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison

arXiv 2211.16110 ↗First posted 29 Nov 2022cs.LG stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

PAC-Bayes has recently re-emerged as an effective theory with which one can derive principled learning algorithms with tight performance guarantees. However, applications of PAC-Bayes to bandit problems are relatively rare, which is a great misfortune. Many decision-making problems in healthcare, finance and natural sciences can be modelled as bandit problems. In many of these applications, principled algorithms with strong performance guarantees would be very much appreciated. This survey provides an overview of PAC-Bayes bounds for bandit problems and an experimental comparison of these bounds. On the one hand, we found that PAC-Bayes bounds are a useful tool for designing offline bandit algorithms with performance guarantees. In our experiments, a PAC-Bayesian offline contextual bandit algorithm was able to learn randomised neural network polices with competitive expected reward and non-vacuous performance guarantees. On the other hand, the PAC-Bayesian online bandit algorithms that we tested had loose cumulative regret bounds. We conclude by discussing some topics for future work on PAC-Bayesian bandit algorithms.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 48 of its 130 references that are in the map. First posted on arXiv 29 Nov 2022.

Builds on

48 of 130 references.

References · 48

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2016Variational Inference: A Review for Statisticianscited by 1,466
  5. 2015Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)cited by 1,061
  6. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 659
  7. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  8. 2014OpenML: networked science in machine learningcited by 523
  9. 2015Variational Dropout and the Local Reparameterization Trickcited by 489
  10. 2019Introduction to Multi-Armed Banditscited by 475
  11. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  12. 2021User-friendly introduction to PAC-Bayes boundscited by 234
36 more
  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  2. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  3. 2015Doubly Robust Policy Evaluation and Optimizationcited by 158
  4. 2019A Primer on PAC-Bayesian Learningcited by 130
  5. 2015Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networkscited by 121
  6. 2020Tighter risk certificates for neural networkscited by 112
  7. 2020PACOH: Bayes-Optimal Meta-Learning with PAC-Guaranteescited by 85
  8. 2017Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priorscited by 81
  9. 2017Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theorycited by 76
  10. 2013A PAC-Bayesian bound for Lifelong Learningcited by 69
  11. 2020PAC-Bayes Analysis Beyond the Usual Boundscited by 63
  12. 2019Normalized Flat Minima: Exploring Scale Invariant Definition of Flat Minima for Neural Networks using PAC-Bayesian Analysiscited by 58
  13. 2016A Strongly Quasiconvex PAC-Bayesian Boundcited by 54
  14. 2015On Markov chain Monte Carlo methods for tall datacited by 50
  15. 2015Fast rates in statistical and online learningcited by 47
  16. 2013A PAC-Bayesian Tutorial with A Dropout Boundcited by 43
  17. 2019Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networkscited by 38
  18. 2020Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weightingcited by 38
  19. 2019PAC-Bayes with Backpropcited by 36
  20. 2018Bayesian Counterfactual Risk Minimizationcited by 28
  21. 2016Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayescited by 27
  22. 2018Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Boundscited by 24
  23. 2021How Tight Can PAC-Bayes be in the Small Data Regime?cited by 24
  24. 2021Meta-Learning Reliable Priors in the Function Spacecited by 23
  25. 2022PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingalescited by 23
  26. 2018PAC-Bayes bounds for stable algorithms with instance-dependent priorscited by 21
  27. 2021Learning PAC-Bayes Priors for Probabilistic Neural Networkscited by 21
  28. 2019Fast-rate PAC-Bayes Generalization Bounds via Shifted Rademacher Processescited by 20
  29. 2018Low-Rank Bandit Methods for High-Dimensional Dynamic Pricingcited by 17
  30. 2019Efron-Stein PAC-Bayesian Inequalitiescited by 15
  31. 2020Transfer Meta-Learning: Information-Theoretic Bounds and Information Meta-Risk Minimizationcited by 14
  32. 2021Progress in Self-Certified Neural Networkscited by 10
  33. 2021Meta-strategy for Learning Tuning Parameters with Guaranteescited by 6
  34. 2014PAC-Bayes Mini-tutorial: A Continuous Union Boundcited by 4
  35. 2022PAC-Bayesian Lifelong Learning For Multi-Armed Banditscited by 4
  36. 2015PAC-Bayes Iterated Logarithm Bounds for Martingale Mixturescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 3; 2026: 2.

7 papers.

  1. 2024Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learningcited by 16
  2. 2023Importance-Weighted Offline Learning Done Rightcited by 15
  3. 2025Koopman-Based Generalization of Deep Reinforcement Learning With Application to Wireless Communicationscited by 1
  4. 2025Refined PAC-Bayes Bounds for Offline Banditscited by 0
  5. 2025Information Theory in Open-world Machine Learning Foundations, Frameworks, and Future Directioncited by 0
  6. 2026PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structurecited by 0
  7. 2026Maximin Robust Bayesian Experimental Designcited by 0