Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization
Dec 6, 2021
Speakers
About
Despite the significant interests and many progresses in decentralized multi-player multi-armed bandits (MP-MAB) problems in recent years, the regret gap to the natural centralized lower bound in the heterogeneous MP-MAB setting remains open. In this paper, we propose BEACON – Batched Exploration with Adaptive COmmunicatioN – that closes this gap. BEACON accomplishes this goal with novel contributions in implicit communication and efficient exploration. For the former, we propose a novel adaptive differential communication (ADC) design that significantly improves the implicit communication efficiency. For the latter, a carefully crafted batched exploration scheme is developed to enable incorporation of the combinatorial upper confidence bound (CUCB) principle. We then generalize the existing linear-reward MP-MAB problems, where the system reward is always the sum of individually collected rewards, to a new MP-MAB problem where the system reward is a general (nonlinear) function of individual rewards. We extend BEACON to solve this problem and prove a regret of O(log(T)). BEACON bridges the algorithm design and regret analysis of combinatorial MAB (CMAB) and MP-MAB, two largely disjointed areas in MAB, and the results in this paper suggest that this previously ignored connection is worth further investigation.Despite the significant interests and many progresses in decentralized multi-player multi-armed bandits (MP-MAB) problems in recent years, the regret gap to the natural centralized lower bound in the heterogeneous MP-MAB setting remains open. In this paper, we propose BEACON – Batched Exploration with Adaptive COmmunicatioN – that closes this gap. BEACON accomplishes this goal with novel contributions in implicit communication and efficient exploration. For the former, we propose a novel adaptiv…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
SyMetric: Measuring the Quality of Learnt Hamiltonian Dynamics Inferred from Vision
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A Theoretical Analysis of Fine-tuning with Linear Teachers
Watch later
Gal Shachaf, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Pushing Scientific Frontiers with AI Technologies
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Panel Discussion 2
Watch later
Moritz Hardt, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
Watch later
Beidi Chen, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Choice, Automation and Performance in ML Deployment with Apache TVM and OctoML
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%