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

Area of Science:

• Machine Learning
• Decision Theory
• Reinforcement Learning

Background:

• PAC-Bayes (Probably Approximately Correct - Bayesian) theory provides a framework for deriving learning algorithms with performance guarantees.
• Bandit problems, prevalent in healthcare and finance, require principled decision-making algorithms.
• Applications of PAC-Bayes to bandit problems are underexplored despite their potential.

Purpose of the Study:

• To survey PAC-Bayes bounds for bandit problems.
• To experimentally compare the performance of PAC-Bayesian bounds in bandit settings.
• To investigate the utility of PAC-Bayes for designing algorithms with performance guarantees.

Main Methods:

• Literature survey of PAC-Bayes bounds applied to bandit problems.
• Experimental evaluation of PAC-Bayesian offline contextual bandit algorithms.
• Experimental evaluation of PAC-Bayesian online bandit algorithms.

Main Results:

• PAC-Bayes bounds are effective for designing offline bandit algorithms with performance guarantees.
• A PAC-Bayesian offline contextual bandit algorithm achieved competitive rewards and non-vacuous guarantees using randomized neural network policies.
• Tested PAC-Bayesian online bandit algorithms exhibited loose cumulative regret bounds.

Conclusions:

• PAC-Bayes is a valuable tool for developing offline bandit algorithms with strong theoretical guarantees.
• Further research is needed to improve PAC-Bayesian online bandit algorithms and their regret bounds.