Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach

• URL: http://arxiv.org/abs/2603.27803v1
• Date: Sun, 29 Mar 2026 18:35:22 GMT
• Title: Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach
• Abstract summary: 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.
• Score: 6.522338519818377
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a distributed online algorithm for multi-agent submodular maximization under communication delays. We are motivated by the future distributed information-gathering tasks in unknown and dynamic environments, where utility functions naturally exhibit the diminishing-returns property, i.e., submodularity. Existing approaches for online submodular maximization either rely on sequential multi-hop communication, resulting in prohibitive delays and restrictive connectivity assumptions, or restrict each agent's coordination to its one-hop neighborhood only, thereby limiting the coordination performance. To address the issue, we provide the Distributed Online Greedy (DOG) algorithm, which integrates tools from adversarial bandit learning with delayed feedback to enable simultaneous decision-making across arbitrary network topologies. We provide the approximation performance of DOG against an optimal solution, capturing the suboptimality cost due to decentralization as a function of the network structure. Our analyses further reveal a trade-off between coordination performance and convergence time, determined by the magnitude of communication delays. By this trade-off, DOG spans the spectrum between the state-of-the-art fully centralized online coordination approach [1] and fully decentralized one-hop coordination approach [2].

Related papers

• MA-HEAD-Net: Adaptive Rule-Guided Multi-Agent DRL for AoI Minimization in UAV-Assisted Emergency Networks [71.01350912967922]
  In post-disaster scenarios, unmanned aerial vehicles (UAVs) are critical for establishing emergency communication networks.<n>This paper investigates age of information (AoI) minimization for UAV-assisted emergency communications with heterogeneous emergency services.<n>We develop MA-HEAD-Net, an adaptive rule-guided multi-agent deep reinforcement learning framework.
  arXiv  Detail & Related papers  (2026-08-02T10:05:50Z)
• A Token/KV-Cache Communication Media Selection and Resource Allocation Strategy for Multi-Agent Collaboration [9.576234748631647]
  We propose a joint design that integrates communication-media selection with wireless resource allocation.<n>We show that neither token-based transmission nor key-value ( KV) cache-based transmission is uniformly optimal across operating regimes.<n> numerically results confirm that, by adaptively coordinating the interaction media and bandwidth allocation over heterogeneous links, the proposed scheme markedly reduced E2E latency.
  arXiv  Detail & Related papers  (2026-05-25T04:50:45Z)
• Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization [6.522338519818377]
  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.
  arXiv  Detail & Related papers  (2026-02-22T22:36:37Z)
• Distributed Online Convex Optimization with Nonseparable Costs and Constraints [7.671875264854638]
  We study a group of agents, networked via a communication graph, that collectively select actions to minimize a sequence of nonseparable global cost functions.<n>We propose a distributed online primal-dual belief consensus algorithm, where each agent maintains and updates a local belief of the global collective decisions.
  arXiv  Detail & Related papers  (2026-02-11T02:46:53Z)
• Cluster-Based Multi-Agent Task Scheduling for Space-Air-Ground Integrated Networks [60.085771314013044]
  Low-altitude economy holds significant potential for development in areas such as communication and sensing.<n>We propose a Clustering-based Multi-agent Deep Deterministic Policy Gradient (CMADDPG) algorithm to address the multi-UAV cooperative task scheduling challenges in SAGIN.
  arXiv  Detail & Related papers  (2024-12-14T06:17:33Z)
• 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)
• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  We consider the task of minimizing the sum of convex functions stored in a decentralized manner across the nodes of a communication network. Lower bounds on the number of decentralized communications and (sub)gradient computations required to solve the problem have been established. We develop the first optimal algorithm that matches these lower bounds and offers substantially improved theoretical performance compared to the existing state of the art.
  arXiv  Detail & Related papers  (2024-05-28T10:28:45Z)
• Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications [9.045332526072828]
  This paper focuses on a multi-agent zeroth-order online optimization problem in a federated learning setting for target tracking. The proposed solution is further analyzed in terms of errors and errors in two relevant applications.
  arXiv  Detail & Related papers  (2023-06-09T03:51:45Z)
• Decentralized Federated Reinforcement Learning for User-Centric Dynamic TFDD Control [37.54493447920386]
  We propose a learning-based dynamic time-frequency division duplexing (D-TFDD) scheme to meet asymmetric and heterogeneous traffic demands. We formulate the problem as a decentralized partially observable Markov decision process (Dec-POMDP) In order to jointly optimize the global resources in a decentralized manner, we propose a federated reinforcement learning (RL) algorithm named Wolpertinger deep deterministic policy gradient (FWDDPG) algorithm.
  arXiv  Detail & Related papers  (2022-11-04T07:39:21Z)
• Predictive GAN-powered Multi-Objective Optimization for Hybrid Federated Split Learning [56.125720497163684]
  We propose a hybrid federated split learning framework in wireless networks. We design a parallel computing scheme for model splitting without label sharing, and theoretically analyze the influence of the delayed gradient caused by the scheme on the convergence speed.
  arXiv  Detail & Related papers  (2022-09-02T10:29:56Z)
• Semantic-Aware Collaborative Deep Reinforcement Learning Over Wireless Cellular Networks [82.02891936174221]
  Collaborative deep reinforcement learning (CDRL) algorithms in which multiple agents can coordinate over a wireless network is a promising approach. In this paper, a novel semantic-aware CDRL method is proposed to enable a group of untrained agents with semantically-linked DRL tasks to collaborate efficiently across a resource-constrained wireless cellular network.
  arXiv  Detail & Related papers  (2021-11-23T18:24:47Z)
• Low-Latency Federated Learning over Wireless Channels with Differential Privacy [142.5983499872664]
  In federated learning (FL), model training is distributed over clients and local models are aggregated by a central server. In this paper, we aim to minimize FL training delay over wireless channels, constrained by overall training performance as well as each client's differential privacy (DP) requirement.
  arXiv  Detail & Related papers  (2021-06-20T13:51:18Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

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.