Feedback graph regret bounds for Thompson Sampling and UCB

Thodoris Lykouris, Éva Tardos, Drishti Wali
Proceedings of the 31st International Conference on Algorithmic Learning Theory, PMLR 117:592-614, 2020.

Abstract

We study the stochastic multi-armed bandit problem with the graph-based feedback structure introduced by Mannor and Shamir. We analyze the performance of the two most prominent stochastic bandit algorithms, Thompson Sampling and Upper Confidence Bound (UCB), in the graph-based feedback setting. We show that these algorithms achieve regret guarantees that combine the graph structure and the gaps between the means of the arm distributions. Surprisingly this holds despite the fact that these algorithms do not explicitly use the graph structure to select arms; they observe the additional feedback but do not explore based on it. Towards this result we introduce a layering technique highlighting the commonalities in the two algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v117-lykouris20a, title = {Feedback graph regret bounds for Thompson Sampling and UCB}, author = {Lykouris, Thodoris and Tardos, \'Eva and Wali, Drishti}, booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory}, pages = {592--614}, year = {2020}, editor = {Kontorovich, Aryeh and Neu, Gergely}, volume = {117}, series = {Proceedings of Machine Learning Research}, month = {08 Feb--11 Feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v117/lykouris20a/lykouris20a.pdf}, url = {https://proceedings.mlr.press/v117/lykouris20a.html}, abstract = {We study the stochastic multi-armed bandit problem with the graph-based feedback structure introduced by Mannor and Shamir. We analyze the performance of the two most prominent stochastic bandit algorithms, Thompson Sampling and Upper Confidence Bound (UCB), in the graph-based feedback setting. We show that these algorithms achieve regret guarantees that combine the graph structure and the gaps between the means of the arm distributions. Surprisingly this holds despite the fact that these algorithms do not explicitly use the graph structure to select arms; they observe the additional feedback but do not explore based on it. Towards this result we introduce a layering technique highlighting the commonalities in the two algorithms.} }
Endnote
%0 Conference Paper %T Feedback graph regret bounds for Thompson Sampling and UCB %A Thodoris Lykouris %A Éva Tardos %A Drishti Wali %B Proceedings of the 31st International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Aryeh Kontorovich %E Gergely Neu %F pmlr-v117-lykouris20a %I PMLR %P 592--614 %U https://proceedings.mlr.press/v117/lykouris20a.html %V 117 %X We study the stochastic multi-armed bandit problem with the graph-based feedback structure introduced by Mannor and Shamir. We analyze the performance of the two most prominent stochastic bandit algorithms, Thompson Sampling and Upper Confidence Bound (UCB), in the graph-based feedback setting. We show that these algorithms achieve regret guarantees that combine the graph structure and the gaps between the means of the arm distributions. Surprisingly this holds despite the fact that these algorithms do not explicitly use the graph structure to select arms; they observe the additional feedback but do not explore based on it. Towards this result we introduce a layering technique highlighting the commonalities in the two algorithms.
APA
Lykouris, T., Tardos, É. & Wali, D.. (2020). Feedback graph regret bounds for Thompson Sampling and UCB. Proceedings of the 31st International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 117:592-614 Available from https://proceedings.mlr.press/v117/lykouris20a.html.

Related Material