Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization

• URL: http://arxiv.org/abs/2602.19366v1
• Date: Sun, 22 Feb 2026 22:36:37 GMT
• Title: Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization
• Abstract summary: We study how to scale distributed bandit submodular coordination under realistic communication constraints in bandwidth, data rate, and connectivity.<n>Our approach enables near-optimal action coordination by optimizing the agents' communication neighborhoods over time.<n>It is observed to converge faster, outperform benchmarks for bandit submodular coordination, and can even outperform benchmarks that are privileged with a priori knowledge of the environment.
• Score: 6.522338519818377
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study how to scale distributed bandit submodular coordination under realistic communication constraints in bandwidth, data rate, and connectivity. We are motivated by multi-agent tasks of active situational awareness in unknown, partially-observable, and resource-limited environments, where the agents must coordinate through agent-to-agent communication. Our approach enables scalability by (i) limiting information relays to only one-hop communication and (ii) keeping inter-agent messages small, having each agent transmit only its own action information. Despite these information-access restrictions, our approach enables near-optimal action coordination by optimizing the agents' communication neighborhoods over time, through distributed online bandit optimization, subject to the agents' bandwidth constraints. Particularly, our approach enjoys an anytime suboptimality bound that is also strictly positive for arbitrary network topologies, even disconnected. To prove the bound, we define the Value of Coordination (VoC), an information-theoretic metric that quantifies for each agent the benefit of information access to its neighbors. We validate in simulations the scalability and near-optimality of our approach: it is observed to converge faster, outperform benchmarks for bandit submodular coordination, and can even outperform benchmarks that are privileged with a priori knowledge of the environment.

Related papers

• SACHI: Structured Agent Coordination via Holistic Information Integration in Multi-Agent Reinforcement Learning [7.702487800530373]
  Multi-agent reinforcement learning agents that act on partial local observations face a fundamental information bottleneck.<n>We propose textitstructured agent coordination via holistic information integration, or SACHI, in which graph transformer convolutions over an inter-agent coordination graph enrich each agent's representation with content-dependent signals from teammates prior to action selection.<n>SACHI consistently matches or outperforms the best baseline on every task, and rigorous aggregate statistical analyses, including normalized metrics with bootstrap confidence intervals, Friedman ranking, and performance profiling, confirm that this advantage is statistically significant, robust across environments, and not attributable to increased model capacity
  arXiv  Detail & Related papers  (2026-05-08T19:00:34Z)
• Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach [6.522338519818377]
  We are motivated by the future distributed information-gathering tasks in unknown and dynamic environments.<n> approaches for online submodular either rely on sequential multi-hop communication, resulting in prohibitive delays.<n>We provide the Distributed Online Greedy (DOG) algorithm, which integrates tools from adversarial learning with delayed feedback to enable simultaneous decision-making.
  arXiv  Detail & Related papers  (2026-03-29T18:35:22Z)
• AnyMAC: Cascading Flexible Multi-Agent Collaboration via Next-Agent Prediction [77.62279834617475]
  We propose a new framework that rethinks multi-agent coordination through a sequential structure rather than a graph structure.<n>Our method focuses on two key directions: (1) Next-Agent Prediction, which selects the most suitable agent role at each step, and (2) Next-Context Selection, which enables each agent to selectively access relevant information from any previous step.
  arXiv  Detail & Related papers  (2025-06-21T18:34:43Z)
• 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)
• Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design [3.5527561584422465]
  We present AlterNAting COordination and Network-Design Algorithm (Anaconda) Anaconda is a scalable algorithm that also enjoys near-optimality guarantees. We demonstrate in simulated scenarios of area monitoring and compare it with a state-of-the-art algorithm.
  arXiv  Detail & Related papers  (2024-09-02T18:11:33Z)
• Networked Communication for Mean-Field Games with Function Approximation and Empirical Mean-Field Estimation [59.01527054553122]
  Decentralised agents can learn equilibria in Mean-Field Games from a non-episodic run of the empirical system.<n>We introduce function approximation to the existing setting, drawing on the Munchausen Online Mirror Descent method.<n>We show theoretically that exchanging policy information helps networked agents outperform both independent and even centralised agents in function-approximation settings.
  arXiv  Detail & Related papers  (2024-08-21T13:32:46Z)
• Asynchronous Message-Passing and Zeroth-Order Optimization Based Distributed Learning with a Use-Case in Resource Allocation in Communication Networks [11.182443036683225]
  Distributed learning and adaptation have received significant interest and found wide-ranging applications in machine learning signal processing.<n>This paper specifically focuses on a scenario where agents collaborate towards a common task.<n>Agents, acting as transmitters, collaboratively train their individual policies to maximize a global reward.
  arXiv  Detail & Related papers  (2023-11-08T11:12:27Z)
• Compressed Regression over Adaptive Networks [58.79251288443156]
  We derive the performance achievable by a network of distributed agents that solve, adaptively and in the presence of communication constraints, a regression problem. We devise an optimized allocation strategy where the parameters necessary for the optimization can be learned online by the agents.
  arXiv  Detail & Related papers  (2023-04-07T13:41:08Z)
• Depthwise Convolution for Multi-Agent Communication with Enhanced Mean-Field Approximation [9.854975702211165]
  We propose a new method based on local communication learning to tackle the multi-agent RL (MARL) challenge. First, we design a new communication protocol that exploits the ability of depthwise convolution to efficiently extract local relations. Second, we introduce the mean-field approximation into our method to reduce the scale of agent interactions.
  arXiv  Detail & Related papers  (2022-03-06T07:42:43Z)
• 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)
• One More Step Towards Reality: Cooperative Bandits with Imperfect Communication [15.440053226788562]
  We study cooperative bandit learning under three typical real-world communication scenarios. We propose decentralized algorithms that achieve competitive performance. We present an improved delayed-update algorithm that outperforms the existing state-of-the-art on various network topologies.
  arXiv  Detail & Related papers  (2021-11-24T13:19:11Z)

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.