English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  PAC-Bayesian Analysis of Martingales and Multiarmed Bandits

Seldin, Y., Laciolette, F., Shaw-Taylor, J., Peters, J., & Auer, P.(2011). PAC-Bayesian Analysis of Martingales and Multiarmed Bandits. Tübingen, Germany: Max Planck Institute for Biological Cybernetics.

Item is

Files

show Files
hide Files
:
TR-2011-Seldin.pdf (Any fulltext), 235KB
Name:
TR-2011-Seldin.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show
hide
Locator:
http://arxiv.org/abs/1105.2416 (Publisher version)
Description:
-

Creators

show
hide
 Creators:
Seldin, Y1, 2, Author              
Laciolette, F, Author
Shaw-Taylor, J, Author
Peters, J.1, 2, Author              
Auer, P, Author
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 Abstract: We present two alternative ways to apply PAC-Bayesian analysis to sequences of dependent random variables. The first is based on a new lemma that enables to bound expectations of convex functions of certain dependent random variables by expectations of the same functions of independent Bernoulli random variables. This lemma provides an alternative tool to Hoeffding-Azuma inequality to bound concentration of martingale values. Our second approach is based on integration of Hoeffding-Azuma inequality with PAC-Bayesian analysis. We also introduce a way to apply PAC-Bayesian analysis in situation of limited feedback. We combine the new tools to derive PAC-Bayesian generalization and regret bounds for the multiarmed bandit problem. Although our regret bound is not yet as tight as state-of-the-art regret bounds based on other well-established techniques, our results significantly expand the range of potential applications of PAC-Bayesian analysis and introduce a new analysis tool to reinforcement learning and many other fields, where martingales and limited feedback are encountered.

Details

show
hide
Language(s):
 Dates: 2011-05
 Publication Status: Published in print
 Pages: 13
 Publishing info: Tübingen, Germany : Max Planck Institute for Biological Cybernetics
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: SeldinLSPA2011
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Technical Reports of the Max Planck Institute for Biological Cybernetics
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -