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

Hamish Flynn, David Reeb, Melih Kandemir, Jan Peters

Research output: Contribution to journalJournal articleResearchpeer-review


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.

Original languageEnglish
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Number of pages20
Publication statusE-pub ahead of print - 18. Aug 2023

Bibliographical note

Publisher Copyright:


  • Approximation algorithms
  • Clinical trials
  • Machine learning algorithms
  • Picture archiving and communication systems
  • Probability distribution
  • Surveys
  • Upper bound


Dive into the research topics of 'PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison'. Together they form a unique fingerprint.

Cite this