| Paper ID | D2-S1-T3.2 |
| Paper Title |
An Attackability Perspective on No-Sensing Adversarial Multi-player Multi-armed Bandits |
| Authors |
Chengshuai Shi, Cong Shen, University of Virginia, United States |
| Session |
D2-S1-T3: Bandits |
| Chaired Session: |
Tuesday, 13 July, 22:00 - 22:20 |
| Engagement Session: |
Tuesday, 13 July, 22:20 - 22:40 |
| Abstract |
In this work, we study the no-sensing adversarial multi-player multi-armed bandits problem. A new dimension of hardness, called attackability, is introduced, which is orthogonal to the hardness of multiple players. All adversaries can be categorized based on the attackability and we introduce Adversary-Adaptive Collision-Communication (A2C2), a family of algorithms with forced-collision communications among players. Information-theoretic tools of the Z-channel model, error-correction/detection coding, and randomized communication are utilized to address the challenge of implicit communication without collision information in an adversarial environment. Theoretical analysis proves that asymptotic attackability-dependent sublinear regrets can be achieved, which do not have an exponential dependence on the number of players and as a result reveal a fundamental tradeoff between the two dimensions of hardness in this problem.
|
