English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits

Seldin, Y., Cesa-Bianchi, N., Auer, P., Laviolette, F., & Shawe-Taylor, J. (2012). PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits. In C. Glowacka, L. Dorata, & J. Shawe-Taylor (Eds.), Workshop on On-line Trading of Exploration and Exploitation 2, 02 July 2011, Bellevue, Washington, USA (pp. 98-111). Madison, WI, USA: International Machine Learning Society.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-B7EC-F Version Permalink: https://hdl.handle.net/21.11116/0000-0001-ACA6-2
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
http://proceedings.mlr.press/v26/seldin12a/seldin12a.pdf (Publisher version)
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Seldin, Y1, Author           
Cesa-Bianchi, N, Author
Auer, P, Author
Laviolette, F, Author
Shawe-Taylor, J, Author
Affiliations:
1Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, Max Planck Society, DE, ou_1497647              

Content

show
hide
Free keywords: -
 Abstract: 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).

Details

show
hide
Language(s):
 Dates: 2012-04
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: SeldinCALS2011
 Degree: -

Event

show
hide
Title: Workshop on On-line Trading of Exploration and Exploitation 2
Place of Event: Bellevue, WA, USA
Start-/End Date: 2011-07-02

Legal Case

show

Project information

show

Source 1

show
hide
Title: Workshop on On-line Trading of Exploration and Exploitation 2, 02 July 2011, Bellevue, Washington, USA
Source Genre: Proceedings
 Creator(s):
Glowacka, C, Editor
Dorata, L, Editor
Shawe-Taylor , J, Editor
Affiliations:
-
Publ. Info: Madison, WI, USA : International Machine Learning Society
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 98 - 111 Identifier: -

Source 2

show
hide
Title: JMLR Workshop and Conference Proceedings
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 26 Sequence Number: - Start / End Page: - Identifier: -