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

• URL: http://arxiv.org/abs/2211.16110v2
• Date: Sun, 16 Jul 2023 10:12:01 GMT
• Title: PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison
• Abstract summary: PAC-Bayes has recently re-emerged as an effective theory with which one can derive principled learning algorithms with tight performance guarantees. Many decision-making problems in healthcare, finance and natural sciences can be modelled as bandit problems. This survey provides an overview of PAC-Bayes bounds for bandit problems and an experimental comparison of these bounds.
• Score: 38.76324445090305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Towards Efficient Contrastive PAC Learning [6.209600119671225]
  We study contrastive learning under the PAC learning framework. In this paper, we consider contrastive learning of the fundamental concept of linear representations. We establish guarantees based on Rademacher complexity, and connect it to PAC guarantees under certain contrastive large-margin conditions.
  arXiv  Detail & Related papers  (2025-02-21T21:51:01Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED) is a highly effective approach to the multi-armed bandit problem. It has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. We present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms.
  arXiv  Detail & Related papers  (2024-05-24T04:11:58Z)
• Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
  We propose a Thompson sampling algorithm, named FGTS.CDB, for linear contextual dueling bandits. At the core of our algorithm is a new Feel-Good exploration term specifically tailored for dueling bandits. Our algorithm achieves nearly minimax-optimal regret, i.e., $tildemathcalO(dsqrt T)$, where $d$ is the model dimension and $T$ is the time horizon.
  arXiv  Detail & Related papers  (2024-04-09T04:45:18Z)
• Concentrated Differential Privacy for Bandits [11.086440815804227]
  This paper contributes to the understanding of Differential Privacy (DP) in bandits with a trusted centralised decision-maker. We propose three private algorithms, namely AdaC-UCB, AdaC-GOPE and AdaC-OFUL, for three bandit settings.
  arXiv  Detail & Related papers  (2023-09-01T16:08:00Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  We provide a simple method to combine bandit algorithms. Our approach is based on a "meta-UCB" procedure that treats each of $N$ individual bandit algorithms as arms in a higher-level $N$-armed bandit problem.
  arXiv  Detail & Related papers  (2020-12-24T05:36:29Z)
• Approximation Theory Based Methods for RKHS Bandits [9.391375268580806]
  The RKHS bandit problem is an online optimization problem of non-linear functions with noisy feedback. There is no general algorithm for the adversarial RKHS bandit problem. We propose efficient algorithms for the RKHS bandit problem and the first general algorithm for the adversarial RKHS bandit problem.
  arXiv  Detail & Related papers  (2020-10-23T05:14:21Z)
• A Limitation of the PAC-Bayes Framework [32.24251308425503]
  We present a limitation for the PAC-Bayes framework. We demonstrate an easy learning task that is not amenable to a PAC-Bayes analysis.
  arXiv  Detail & Related papers  (2020-06-24T06:36:00Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  We show that the regret of the corralling algorithms is no worse than that of the best algorithm containing the arm with the highest reward. We show that the gap between the highest reward and other rewards depends on the gap between the highest reward and other rewards.
  arXiv  Detail & Related papers  (2020-06-16T15:33:12Z)
• Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
  We study the conservative learning problem in the contextual linear bandit setting and introduce a novel algorithm, the Conservative Constrained LinUCB (CLUCB2) We derive regret bounds for CLUCB2 that match existing results and empirically show that it outperforms state-of-the-art conservative bandit algorithms in a number of synthetic and real-world problems.
  arXiv  Detail & Related papers  (2020-02-08T19:35:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.