All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD2-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.