Graphical Models for Bandit Problems

Kareem Amin, Michael Kearns, Umar Syed
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:18-27, 2011.

Abstract

We introduce a rich class of graphical models for multi-armed bandit problems that permit both the state or context space and the action space to be very large, yet succinctly specify the payoffs for any context-action pair. Our main result is an algorithm for such models whose regret is bounded by the number of parameters and whose running time depends only on the treewidth of the graph substructure induced by the action space.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-amin11a, title = {Graphical Models for Bandit Problems}, author = {Amin, Kareem and Kearns, Michael and Syed, Umar}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {18--27}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/amin11a/amin11a.pdf}, url = {https://proceedings.mlr.press/r9/amin11a.html}, abstract = {We introduce a rich class of graphical models for multi-armed bandit problems that permit both the state or context space and the action space to be very large, yet succinctly specify the payoffs for any context-action pair. Our main result is an algorithm for such models whose regret is bounded by the number of parameters and whose running time depends only on the treewidth of the graph substructure induced by the action space.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Graphical Models for Bandit Problems %A Kareem Amin %A Michael Kearns %A Umar Syed %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-amin11a %I PMLR %P 18--27 %U https://proceedings.mlr.press/r9/amin11a.html %V R9 %X We introduce a rich class of graphical models for multi-armed bandit problems that permit both the state or context space and the action space to be very large, yet succinctly specify the payoffs for any context-action pair. Our main result is an algorithm for such models whose regret is bounded by the number of parameters and whose running time depends only on the treewidth of the graph substructure induced by the action space. %Z Reissued by PMLR on 04 October 2026.
APA
Amin, K., Kearns, M. & Syed, U.. (2011). Graphical Models for Bandit Problems. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:18-27 Available from https://proceedings.mlr.press/r9/amin11a.html. Reissued by PMLR on 04 October 2026.

Related Material