Analysis of Thompson Sampling for Graphical Bandits Without the Graphs

Fang Liu, Zizhan Zheng, Ness Shroff
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:12-21, 2018.

Abstract

We study multi-armed bandit problems with graph feedback, in which the decision maker is allowed to observe the neighboring actions of the chosen action, in a setting where the graph may vary over time and is never fully revealed to the decision maker. We show that when the feedback graphs are undirected, the original Thompson Sampling achieves the optimal (within logarithmic factors) regret $\tilde{}$O (p $\beta$0(G)T ) over time horizon T, where $\beta$0(G) is the average independence number of the latent graphs. To the best of our knowl- edge, this is the first result showing that the original Thompson Sampling is optimal for graphical bandits in the undirected setting. A slightly weaker regret bound of Thompson Sampling in the directed setting is also pre- sented. To fill this gap, we propose a variant of Thompson Sampling, that attains the opti- mal regret in the directed setting within a log- arithmic factor. Both algorithms can be im- plemented efficiently and do not require the knowledge of the feedback graphs at any time.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-liu18a, title = {Analysis of {T}hompson Sampling for Graphical Bandits Without the Graphs}, author = {Liu, Fang and Zheng, Zizhan and Shroff, Ness}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {12--21}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/liu18a/liu18a.pdf}, url = {https://proceedings.mlr.press/r16/liu18a.html}, abstract = {We study multi-armed bandit problems with graph feedback, in which the decision maker is allowed to observe the neighboring actions of the chosen action, in a setting where the graph may vary over time and is never fully revealed to the decision maker. We show that when the feedback graphs are undirected, the original Thompson Sampling achieves the optimal (within logarithmic factors) regret $\tilde{}$O (p $\beta$0(G)T ) over time horizon T, where $\beta$0(G) is the average independence number of the latent graphs. To the best of our knowl- edge, this is the first result showing that the original Thompson Sampling is optimal for graphical bandits in the undirected setting. A slightly weaker regret bound of Thompson Sampling in the directed setting is also pre- sented. To fill this gap, we propose a variant of Thompson Sampling, that attains the opti- mal regret in the directed setting within a log- arithmic factor. Both algorithms can be im- plemented efficiently and do not require the knowledge of the feedback graphs at any time.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Analysis of Thompson Sampling for Graphical Bandits Without the Graphs %A Fang Liu %A Zizhan Zheng %A Ness Shroff %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-liu18a %I PMLR %P 12--21 %U https://proceedings.mlr.press/r16/liu18a.html %V R16 %X We study multi-armed bandit problems with graph feedback, in which the decision maker is allowed to observe the neighboring actions of the chosen action, in a setting where the graph may vary over time and is never fully revealed to the decision maker. We show that when the feedback graphs are undirected, the original Thompson Sampling achieves the optimal (within logarithmic factors) regret $\tilde{}$O (p $\beta$0(G)T ) over time horizon T, where $\beta$0(G) is the average independence number of the latent graphs. To the best of our knowl- edge, this is the first result showing that the original Thompson Sampling is optimal for graphical bandits in the undirected setting. A slightly weaker regret bound of Thompson Sampling in the directed setting is also pre- sented. To fill this gap, we propose a variant of Thompson Sampling, that attains the opti- mal regret in the directed setting within a log- arithmic factor. Both algorithms can be im- plemented efficiently and do not require the knowledge of the feedback graphs at any time. %Z Reissued by PMLR on 04 October 2026.
APA
Liu, F., Zheng, Z. & Shroff, N.. (2018). Analysis of Thompson Sampling for Graphical Bandits Without the Graphs. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:12-21 Available from https://proceedings.mlr.press/r16/liu18a.html. Reissued by PMLR on 04 October 2026.

Related Material