PAC-Bayesian Inequalities for Martingales
Yevgeny Seldin, Francois Laviolette, Nicolo Cesa-Bianchi, John Shawe-Taylor, Peter Auer
We present a set of high-probability inequalities that control the concentration of weighted averages of multiple (possibly uncountably many) simultaneously evolving and interdependent martingales. Our results extend the PAC-Bayesian analysis in learning theory from the i.i.d. setting to martingales opening the way for its application in reinforcement learning and other interactive learning domains, as well as many other domains in probability theory and statistics, where martingales are encountered. We also present a comparison inequality that bounds the expectation of a convex function of a martingale difference sequence shifted to the [0; 1] interval by the expectation of the same function of independent Bernoulli variables. This inequality is applied to derive a tighter analog of Hoeding-Azuma's inequality. For the complete paper see Seldin et al. (2012).
PDF Link: /papers/12/p12-seldin.pdf
AUTHOR = "Yevgeny Seldin
and Francois Laviolette and Nicolo Cesa-Bianchi and John Shawe-Taylor and Peter Auer",
TITLE = "PAC-Bayesian Inequalities for Martingales",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "12--12"