PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits
By Yevgeny Seldin, Nicolò Cesa-Bianchi, Peter Auer, François Laviolette, John Shawe-Taylor. 2011
29 citations recorded by the source corpus.
We develop a new tool for data-dependent analysis of the exploration-exploitation trade-off in learning under limited feedback. Our tool is based on two main ingredients. The first ingredient is a new concentration inequality that makes it possible to control the concentration of weighted averages of multiple (possibly uncountably many) simultaneously evolving and interdependent martingales. The second ingredient is an application of this inequality to the exploration-exploitation trade-off via importance weighted sampling. We apply the new tool to the stochastic multiarmed bandit problem, however, the main importance of this paper is the development and understanding of the new tool rather than improvement of existing algorithms for stochastic multiarmed bandits. In the follow-up work we demonstrate that the new tool can improve over state-of-the-art in structurally richer problems, such as stochastic multiarmed bandits with side information (Seldin et al., 2011a).
Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Electrical and Electronic Engineering
In Management Science and Operations Research
Citations in the corpus
- User-friendly introduction to PAC-Bayes bounds (2021, background): “Some authors derived strategies or regret bounds directly from PAC-Bayes bounds [174, 175].”