A collision-only coordinated distributed algorithm for max-min fair multi-agent bandits achieves O(N^3 f(log T) log T) regret while preserving local reward privacy.
Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We consider the non-stochastic version of the (cooperative) multi-player multi-armed bandit problem. The model assumes no communication 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, under the feedback model where collisions are announced to the colliding players. Such a bound was not known even for the simpler stochastic version. We also prove the first sublinear guarantee for the feedback model where collision information is not available, namely $T^{1-\frac{1}{2m}}$ where $m$ is the number of players.
fields
cs.LG 1years
2023 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Bandits
A collision-only coordinated distributed algorithm for max-min fair multi-agent bandits achieves O(N^3 f(log T) log T) regret while preserving local reward privacy.