When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits

• URL: http://arxiv.org/abs/2110.04396v1
• Date: Fri, 8 Oct 2021 22:30:43 GMT
• Title: When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits
• Authors: Udari Madhushani and Naomi Leonard
• Abstract summary: In cooperative bandits, a framework that captures essential features of collective sequential decision making, agents can minimize group regret, and thereby improve performance. Existing cooperative bandit algorithms obtain optimal performance when agents share information with their neighbors at textitevery time step, i.e., full communication. We propose textitComEx, a novel cost-effective communication protocol in which the group achieves the same order of performance as full communication while communicating only $O(log T)$ number of messages.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In cooperative bandits, a framework that captures essential features of collective sequential decision making, agents can minimize group regret, and thereby improve performance, by leveraging shared information. However, sharing information can be costly, which motivates developing policies that minimize group regret while also reducing the number of messages communicated by agents. Existing cooperative bandit algorithms obtain optimal performance when agents share information with their neighbors at \textit{every time step}, i.e., full communication. This requires $\Theta(T)$ number of messages, where $T$ is the time horizon of the decision making process. We propose \textit{ComEx}, a novel cost-effective communication protocol in which the group achieves the same order of performance as full communication while communicating only $O(\log T)$ number of messages. Our key step is developing a method to identify and only communicate the information crucial to achieving optimal performance. Further we propose novel algorithms for several benchmark cooperative bandit frameworks and show that our algorithms obtain \textit{state-of-the-art} performance while consistently incurring a significantly smaller communication cost than existing algorithms.

Related papers

• Communication Learning in Multi-Agent Systems from Graph Modeling Perspective [62.13508281188895]
  We introduce a novel approach wherein we conceptualize the communication architecture among agents as a learnable graph. We introduce a temporal gating mechanism for each agent, enabling dynamic decisions on whether to receive shared information at a given time.
  arXiv  Detail & Related papers  (2024-11-01T05:56:51Z)
• Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs [46.068883750876886]
  This paper presents a simple yet effective communication policy and integrates it into a learning algorithm for cooperative bandits. Our algorithm achieves the best of both paradigms: optimal individual regret and constant communication costs.
  arXiv  Detail & Related papers  (2023-08-08T15:02:50Z)
• RGMComm: Return Gap Minimization via Discrete Communications in Multi-Agent Reinforcement Learning [33.86277578441437]
  Communication is crucial for solving cooperative Multi-Agent Reinforcement Learning tasks in partially observable Markov Decision Processes. We propose the Return-Gap-Minimization Communication (RGMComm) algorithm, which is a surprisingly simple design of discrete message generation functions. Evaluations show that RGMComm significantly outperforms state-of-the-art multi-agent communication baselines.
  arXiv  Detail & Related papers  (2023-08-07T07:26:55Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Towards True Lossless Sparse Communication in Multi-Agent Systems [1.911678487931003]
  Communication enables agents to cooperate to achieve their goals. Recent work in learning sparse individualized communication suffers from high variance during training. We use the information bottleneck to reframe sparsity as a representation learning problem.
  arXiv  Detail & Related papers  (2022-11-30T20:43:34Z)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We prove that the regret of textttFedLinUCB is bounded by $tildeO(dsqrtsum_m=1M T_m)$ and the communication complexity is $tildeO(dM
  arXiv  Detail & Related papers  (2022-07-07T06:16:19Z)
• Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost [48.288452411283444]
  We study distributed contextual linear bandits with contexts, where $N$ agents act cooperatively to solve a linear bandit-optimization problem with $d$-dimensional features. We propose a distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB, where the agents share information among each other through a central server. We prove that over $T$ rounds ($NT$ actions in total) the communication cost of DisBE-LUCB is only $tildemathcalO(dN)$ and its regret is at most $tildemathcalO
  arXiv  Detail & Related papers  (2022-05-26T05:56:23Z)
• Multi-agent Communication with Graph Information Bottleneck under Limited Bandwidth (a position paper) [92.11330289225981]
  In many real-world scenarios, communication can be expensive and the bandwidth of the multi-agent system is subject to certain constraints. Redundant messages who occupy the communication resources can block the transmission of informative messages and thus jeopardize the performance. We propose a novel multi-agent communication module, CommGIB, which effectively compresses the structure information and node information in the communication graph to deal with bandwidth-constrained settings.
  arXiv  Detail & Related papers  (2021-12-20T07:53:44Z)
• Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
  This work examines adaptive distributed learning strategies designed to operate under communication constraints. We consider a network of agents that must solve an online optimization problem from continual observation of streaming data.
  arXiv  Detail & Related papers  (2021-12-03T19:23:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.