Header logo is ei

PAC-Bayesian Analysis of Contextual Bandits

2011

Conference Paper

ei


We derive an instantaneous (per-round) data-dependent regret bound for stochastic multiarmed bandits with side information (also known as contextual bandits). The scaling of our regret bound with the number of states (contexts) $N$ goes as $\sqrt{N I_{\rho_t}(S;A)}$, where $I_{\rho_t}(S;A)$ is the mutual information between states and actions (the side information) used by the algorithm at round $t$. If the algorithm uses all the side information, the regret bound scales as $\sqrt{N \ln K}$, where $K$ is the number of actions (arms). However, if the side information $I_{\rho_t}(S;A)$ is not fully used, the regret bound is significantly tighter. In the extreme case, when $I_{\rho_t}(S;A) = 0$, the dependence on the number of states reduces from linear to logarithmic. Our analysis allows to provide the algorithm large amount of side information, let the algorithm to decide which side information is relevant for the task, and penalize the algorithm only for the side information that it is using de facto. We also present an algorithm for multiarmed bandits with side information with computational complexity that is a linear in the number of actions.

Author(s): Seldin, Y. and Auer, P. and Laviolette, F. and Shawe-Taylor, J. and Ortner, R.
Book Title: Advances in Neural Information Processing Systems 24
Pages: 1683-1691
Year: 2011
Day: 0
Editors: J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger

Department(s): Empirical Inference
Research Project(s): Reinforcement Learning
Bibtex Type: Conference Paper (inproceedings)

Digital: 0
Event Name: Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS 2011)
Event Place: Granada, Spain

Links: PDF
PDF
Web

BibTex

@inproceedings{SeldinALSO2011,
  title = {PAC-Bayesian Analysis of Contextual Bandits },
  author = {Seldin, Y. and Auer, P. and Laviolette, F. and Shawe-Taylor, J. and Ortner, R.},
  booktitle = {Advances in Neural Information Processing Systems 24},
  pages = {1683-1691},
  editors = {J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger},
  year = {2011}
}