A decentralized policy for heterogeneous multiplayer bandits is claimed to achieve O(log^{1+δ}T + W) regret under adversarial zero-reward attacks using one-bit communication.
Multi-Player Bandits Robust to Adversarial Collisions
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Motivated by cognitive radios, stochastic Multi-Player Multi-Armed Bandits has been extensively studied in recent years. In this setting, each player pulls an arm, and receives a reward corresponding to the arm if there is no collision, namely the arm was selected by one single player. Otherwise, the player receives no reward if collision occurs. In this paper, we consider the presence of malicious players (or attackers) who obstruct the cooperative players (or defenders) from maximizing their rewards, by deliberately colliding with them. We provide the first decentralized and robust algorithm RESYNC for defenders whose performance deteriorates gracefully as $\tilde{O}(C)$ as the number of collisions $C$ from the attackers increases. We show that this algorithm is order-optimal by proving a lower bound which scales as $\Omega(C)$. This algorithm is agnostic to the algorithm used by the attackers and agnostic to the number of collisions $C$ faced from attackers.
citation-role summary
background 1
citation-polarity summary
fields
stat.ML 1years
2025 1verdicts
REJECT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Heterogeneous Multi-Player Multi-Armed Bandits Robust To Adversarial Attacks
A decentralized policy for heterogeneous multiplayer bandits is claimed to achieve O(log^{1+δ}T + W) regret under adversarial zero-reward attacks using one-bit communication.