Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without

Sébastien Bubeck, Yuanzhi Li, Yuval Peres, Mark Sellke
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:961-987, 2020.

Abstract

We consider the non-stochastic version of the (cooperative) multi-player multi-armed bandit problem. The model assumes no communication and no shared randomness at all between the players, and furthermore when two (or more) players select the same action this results in a maximal loss. We prove the first $\sqrt{T}$-type regret guarantee for this problem, assuming only two players, and under the feedback model where collisions are announced to the colliding players. We also prove the first sublinear regret guarantee for the feedback model where collision information is not available, namely $T^{1-\frac{1}{2m}}$ where $m$ is the number of players.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-bubeck20c, title = {Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without}, author = {Bubeck, S\'ebastien and Li, Yuanzhi and Peres, Yuval and Sellke, Mark}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {961--987}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/bubeck20c/bubeck20c.pdf}, url = {https://proceedings.mlr.press/v125/bubeck20c.html}, abstract = { We consider the non-stochastic version of the (cooperative) multi-player multi-armed bandit problem. The model assumes no communication and no shared randomness at all between the players, and furthermore when two (or more) players select the same action this results in a maximal loss. We prove the first $\sqrt{T}$-type regret guarantee for this problem, assuming only two players, and under the feedback model where collisions are announced to the colliding players. We also prove the first sublinear regret guarantee for the feedback model where collision information is not available, namely $T^{1-\frac{1}{2m}}$ where $m$ is the number of players.} }
Endnote
%0 Conference Paper %T Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without %A Sébastien Bubeck %A Yuanzhi Li %A Yuval Peres %A Mark Sellke %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-bubeck20c %I PMLR %P 961--987 %U https://proceedings.mlr.press/v125/bubeck20c.html %V 125 %X We consider the non-stochastic version of the (cooperative) multi-player multi-armed bandit problem. The model assumes no communication and no shared randomness at all between the players, and furthermore when two (or more) players select the same action this results in a maximal loss. We prove the first $\sqrt{T}$-type regret guarantee for this problem, assuming only two players, and under the feedback model where collisions are announced to the colliding players. We also prove the first sublinear regret guarantee for the feedback model where collision information is not available, namely $T^{1-\frac{1}{2m}}$ where $m$ is the number of players.
APA
Bubeck, S., Li, Y., Peres, Y. & Sellke, M.. (2020). Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:961-987 Available from https://proceedings.mlr.press/v125/bubeck20c.html.

Related Material