Robust Multi-Agent Bandits over Undirected Graphs

Daniel Vial, Sanjay Shakkottai, R. Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a multi-agent multi-armed bandit setting in which n honest agents collaborate over a network to minimize regret but m malicious agents can disrupt learning arbitrarily. Assuming the network is the complete graph, existing algorithms incur O((m + K/n) log (T) / ") regret in this setting, where K is the number of arms and Δis the arm gap. For m << K, this improves over the single-agent baseline regret of O(K log(T)/"). In this work, we show the situation is murkier beyond the case of a complete graph. In particular, we provide an instance for which honest agents using the state-of-the-art algorithm suffer (nearly) linear regret until time is doubly exponential in n. In light of this negative result, we propose a new algorithm for which the i-th agent has regret O((dmal (i) + K/n) log(T)/") on any connected and undirected graph, where dmal (i) is the number of i's neighbors who are malicious. Thus, we generalize existing regret bounds beyond the complete graph and show the effect of malicious agents is entirely local.

Original languageEnglish (US)
Title of host publicationSIGMETRICS 2023 - Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
PublisherAssociation for Computing Machinery
Pages67-68
Number of pages2
ISBN (Electronic)9798400700743
DOIs
StatePublished - Jun 19 2023
Event2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2023 - Orlando, United States
Duration: Jun 19 2023Jun 23 2023

Publication series

NameSIGMETRICS 2023 - Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

Conference

Conference2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2023
Country/TerritoryUnited States
CityOrlando
Period6/19/236/23/23

Keywords

  • malicious agents
  • multi-armed bandits

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Hardware and Architecture
  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'Robust Multi-Agent Bandits over Undirected Graphs'. Together they form a unique fingerprint.

Cite this