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

Computer Science > Machine Learning arXiv:2603.27803 (cs) [Submitted on 29 Mar 2026] Title:Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach Authors:Zirui Xu, Vasileios Tzoumas View a PDF of the paper titled Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach, by Zirui Xu and 1 other authors View PDF HTML (experimental) 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 rev...