Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays

Pranjal Sharma; Zirui Xu; Vasileios Tzoumas

eess.SYApr 7, 2026

Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays

Authors: Pranjal Sharma, Zirui Xu, Vasileios Tzoumas

Organizations: Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109, USA

Abstract

We study asynchronous distributed decision-making for scalable multi-agent bandit submodular maximization. We are motivated by distributed information-gathering tasks in unknown environments and under heterogeneous inter-agent communication delays. To enable scalability despite limited communication delays, existing approaches restrict each agent to coordinate only with its one-hop neighbors. But these approaches assume homogeneous communication delays among the agents and a synchronous global clock. In practice, however, delays are heterogeneous, and agents operate with mismatched local clocks. That is, each agent does not receive information from all neighbors at the same time, compromising decision-making. In this paper, we provide an asynchronous coordination algorithm to overcome the challenges. We establish a provable approximation guarantee against the optimal synchronized centralized solution, where the suboptimality gap explicitly depends on communication delays and clock mismatches. The bounds also depend on the topology of each neighborhood, capturing the effect of distributed decision-making via one-hop-neighborhood messages only. The clock-mismatch penalty is expressed through a bounded oscillation of the reward in the execution times, which, unlike a Lipschitz condition, is available for discrete-valued rewards such as target monitoring. We validate the approach through numerical simulations on multi-camera target monitoring through the lenses of two different reward structures and simulation setups.

Figures & tables

Fig. 1 : Simulation layout and sample snapshot of camera (black vertices) and target (black crosses) configuration. $\mathchar 28721\mathchar 28726$ cameras are placed on a $\mathchar 28724\mathchar 8706\mathchar 28724$ grid over a $\mathchar 28721\mathchar 28720\mathchar 28720\mathchar 8706\mathchar 28721\mathchar 28720\mathchar 28720$ workspace. Each camera has a sector FOV with half-angle $\mathchar 28723\mathchar 28720^{\mathchar 8718}$ and sensing range of $\mathchar 28722\mathchar 28720$ units (light gray wedges show the selected heading of each camera). Colored edges denote the one-hop communication links between grid neighbors, with warmer colors representing higher delays.

Panel of Figure 2 — Fig. 2 : Coverage over time (mean $\mathchar 8710\mathchar 28729\mathchar 28725\%$ CI, $\mathchar 29038\mathchar 12349\mathchar 28722\mathchar 28720$ runs, running average over $\mathchar 28725\mathchar 28720$ time steps) for DOG-IU and DOG under increasing maximum one-hop delay $\bar{\mathchar 29028}$ on a $\mathchar 28721\mathchar 28720\mathchar 28720\mathchar 8706\mathchar 28721\mathchar 28720\mathchar 28720$ workspace with $\mathchar 28721\mathchar 28726$ grid-placed cameras, $\mathchar 28728$ headings, and $\mathchar 28728\mathchar 28720$ clustered targets (8 clusters). The gap widens as delay increases, illustrating the benefit of intermediate updates under more severe communication delays.

Fig. 3 : Layout and sample snapshot of the information-gathering simulation. $\mathchar 28721\mathchar 28726$ agents (black squares) are fixed at the vertices of a $\mathchar 28724\mathchar 8706\mathchar 28724$ grid over a $\mathchar 28721\mathchar 28720\mathchar 28720\mathchar 8706\mathchar 28721\mathchar 28720\mathchar 28720$ workspace, each orienting a $\mathchar 28724\mathchar 28725^{\mathchar 8718}$ sensing sector. Gray shading indicates sensing accuracy: it tapers smoothly across the sector edge to the floor $\mathchar 29031_{\mathrm{\mathchar 29039\mathchar 29045\mathchar 29044}}$ and decays with range, rather than terminating at a hard field-of-view boundary, which is what makes the reward continuous in the execution times. $\mathchar 28727\mathchar 28722$ targets (black crosses) in $\mathchar 28728$ clusters follow linear-Gaussian dynamics with continuous-time maneuvers. Colored edges denote the one-hop communication links, with warmer colors representing higher delays.

Panel of Figure 4 — Fig. 4 : Preliminary results on the information-gathering task; shaded bands are $\mathchar 28729\mathchar 28725\%$ confidence intervals and are narrower than the plot markers throughout. (a) Mean reward against the maximum one-hop delay $\bar{\mathchar 29028}$ ( $\mathchar 29038\mathchar 12349\mathchar 28722\mathchar 28720$ seed-paired runs): DOG-IU is essentially unaffected by delay, whereas DOG degrades monotonically, so the advantage of intermediate updates grows with $\bar{\mathchar 29028}$ and reaches $\mathchar 28721\mathchar 28724\mathchar 314\mathchar 28728\mathchar 28721\%$ at $\bar{\mathchar 29028}\mathchar 12349\mathchar 28723\mathchar 28720$ . (b) Reward relative to synchronous execution against the timing mismatch bound $\mathchar 28954$ ( $\mathchar 29038\mathchar 12349\mathchar 28721\mathchar 28720$ seed-paired runs): degradation is smooth and close to proportional in $\mathchar 28954$ , and the curves at $\bar{\mathchar 29028}\mathchar 12349\mathchar 28720$ and $\bar{\mathchar 29028}\mathchar 12349\mathchar 28721\mathchar 28720$ coincide, indicating that communication delay and clock mismatch act as separate cost channels.

Explore similar work

Mar 29, 2026

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

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].

Zirui Xu, Vasileios Tzoumas

Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

Submodular Optimization Multi-Agent Coordination

Ask PDF

Feb 22, 2026

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

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.

Zirui Xu, Vasileios Tzoumas

Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

Multi-Agent Coordination Submodular Optimization Graph Bandits Combinatorial Multi-Armed Bandits

Ask PDF

Oct 13, 2026

Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

Motivated by applications to cognitive radio networks, multi-player multi-armed bandits (MMAB) have attracted considerable attention in recent years. The asynchronous variant, in which players are active only at a fraction of timesteps, better reflects real-world decentralized networks, where devices are not permanently active. Despite its practical relevance, this setting remains relatively understudied. Existing work on asynchronous MMAB has focused on homogeneous players, who share the same activation probability, a setting in which the optimal centralized allocation can be easily characterized. In contrast, efficiently computing the optimal allocation in the heterogeneous setting, where players have different activation probabilities, has remained an open problem. In this work, we investigate this problem and first establish its NP-hardness. We then turn to the greedy algorithm, which runs in polynomial time, and prove that it achieves a

\frac{1}{e}

-approximation of the optimal allocation. Furthermore, when players are processed in decreasing order of their activation probabilities, the approximation guarantee improves to

\frac{1}{\sqrt{e}}

. Overall, our results establish the greedy algorithm as an efficient approximation to the optimal allocation, providing a practical oracle baseline for the design of online algorithms for heterogeneous asynchronous multi-player bandits.

Sacha Arroues-Paykin, Etienne Boursier, Vianney Perchet

Ecole Polytechnique · INRIA, LMO, Université Paris-Saclay · CREST, ENSAE

Multi-Armed Bandits Approximation Algorithms Combinatorial Optimization

Ask PDF