PAC-Bayes-Bernstein Inequality for Martingales and its Application to 
Multiarmed Bandits

Seldin, Y; Cesa-Bianchi, N; Auer, P; Laviolette, F; Shawe-Taylor, J

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits

MPS-Authors

/persons/resource/persons84206

Seldin, Y
Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, Max Planck Society;

External Resource

http://proceedings.mlr.press/v26/seldin12a/seldin12a.pdf
(出版社版)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/11858/00-001M-0000-0013-B7EC-F

要旨

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).