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

Abstract

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.

arXiv comment32 pages, 8 figures

References in corpus (22)

• Variational Inference: A Review for Statisticians
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Trust Region Policy Optimization
• OpenML: networked science in machine learning
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• On Markov chain Monte Carlo methods for tall data
• Doubly Robust Policy Evaluation and Optimization
• A PAC-Bayesian bound for Lifelong Learning
• A Note on the PAC Bayesian Theorem
• Tighter risk certificates for neural networks
• A Strongly Quasiconvex PAC-Bayesian Bound
• PAC-Bayes bounds for stable algorithms with instance-dependent priors
• PAC-Bayes Mini-tutorial: A Continuous Union Bound
• PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits
• PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
• PAC-Bayesian Lifelong Learning For Multi-Armed Bandits
• Learning PAC-Bayes Priors for Probabilistic Neural Networks
• A unified recipe for deriving (time-uniform) PAC-Bayes bounds
• Meta-strategy for Learning Tuning Parameters with Guarantees
• PAC-Bayes Iterated Logarithm Bounds for Martingale Mixtures
• Progress in Self-Certified Neural Networks