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

Zirui Xu; Vasileios Tzoumas

eess.SYFeb 22, 2026

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

Authors: Zirui Xu, Vasileios Tzoumas

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

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.

Figures & tables

Fig. 1: Information Access Matters: A Multi-Camera Area Monitoring Example. Consider a multi-camera area monitoring task where four cameras must coordinate their fields of view (FOVs) via distributed communication to maximize total coverage. As shown in (a), suppose that cameras 1–3 have already fixed their FOVs (soft orange), and camera 4 must select its FOV from three predefined options (dark red). While the optimal choice for camera 4 depends on the FOVs of all other three, its communication bandwidth allows it to receive information from at most two of them at any current time. The three possible communication neighborhood configurations and the corresponding FOV selections are demonstrated in (b)–(d), among which the design in (c) yields the highest coverage and therefore the optimal FOV decision. This example illustrates that intelligent information access—enabled by active neighborhood design (possibly over multiple time steps)—can optimize action coordination performance in distributed settings with limited communication resources.

Fig. 2: Asymptotic approximation bounds of Anaconda . As

\mathchar 29012\mathchar 12833\mathchar 561

, the bounds provided by Theorems 1 , 2 and 3 are shown with varying ranges of

\mathchar 28948_{\mathchar 29030}

and achieved

\mathchar 28940

(defined in eq. 18 ). The a priori bound (red) varies with the sum of all agents’ VoC ; the a posteriori bound (orange) decreases as

\mathchar 28940

increases; and the combined bound (blue) takes the maximum of the a priori lower bound and the a posteriori bound.

Fig. 3: Comparison of neighbor selection strategies with varying network density. Across 20 MC trials each with 2000 decision rounds, we compare NeiSel with two benchmark strategies, Nearest Neighbors and Random Neighbors. We tune the network density by varying the map area while fixing the network size at 20 agents: as the camera density grows, the network becomes sparser.

Panel of Figure 4 — Fig. 4: Comparison of neighbor selection strategies in a structured environment. Three algorithms are compared with the same action selection strategy ActSel but different neighbor selection strategies ( NeiSel vs. nearest neighbors vs. random neighbors) in the same structured environment.

Metric	Nearest Neighbors	Random Neighbors	Ours
Mean $\mathchar 8710$ Std (%)	56.53 $\mathchar 8710$ 4.57	64.47 $\mathchar 8710$ 6.07	71.89 $\mathchar 8710$ 7.36
Min (%)	35.56 ( $\mathchar 29044{\mathchar 12349}\mathchar 28721$ )	37.94 ( $\mathchar 29044{\mathchar 12349}\mathchar 28721\mathchar 28721\mathchar 28723$ )	39.72 ( $\mathchar 29044{\mathchar 12349}\mathchar 28721\mathchar 28726\mathchar 28729$ )
Max (%)	71.09 ( $\mathchar 29044{\mathchar 12349}\mathchar 28722\mathchar 28724\mathchar 28728\mathchar 28724$ )	72.56 ( $\mathchar 29044{\mathchar 12349}\mathchar 28728\mathchar 28729\mathchar 28725$ )	77.25 ( $\mathchar 29044{\mathchar 12349}\mathchar 28726\mathchar 28721\mathchar 28729$ )

TABLE I: Comparison of coverage performance (%) in the urban scenario as in Fig. 4 with different neighbor selection strategies. The best coverage performance is in bold .

Fig. 5: Comparison of Anaconda , DFS-SG , and DFS-BSG for area monitoring without computation and communication delays. Cameras select their FOV directions using Anaconda with maximum communication neighborhood sizes in $\{\mathchar 28720\mathchar 24891\dots\mathchar 24891\mathchar 28725\}$ , or using DFS-SG or DFS-BSG . From (a) to (d), the communication range $\mathchar 29027_{\mathchar 29033}$ for all cameras $\mathchar 29033\mathchar 12850{\cal\mathchar 29006}$ increases from 10 to 16 to 20 to 80, and thus expanding each camera’s coordination neighborhood ${\cal\mathchar 29005}_{\mathchar 29033}$ growing from a small locality to the full set ${\cal\mathchar 29006}\mathchar 8814\{\mathchar 29033\}$ . DFS-SG is executed for a single decision round, whereas the other algorithms are run for 4000 rounds. Results are averaged over 20 Monte Carlo trials.

Panel of Figure 7 — Fig. 6: Comparison of Anaconda vs. DFS-SG vs. DFS-BSG for real-time coverage performance under computation and communication delays. Cameras select their FOV directions using Anaconda with maximum communication neighborhood sizes in $\{\mathchar 28720\mathchar 24891\dots\mathchar 24891\mathchar 28725\}$ , or using DFS-SG or DFS-BSG . From (a) to (b) to (c), the time $\mathchar 28956_{\mathchar 29030}$ for one function evaluation increases relative to the delay $\mathchar 28956_{\mathchar 29027}$ for transmitting one action through a communication link, with the ratio $\mathchar 28956_{\mathchar 29030}\delimiter 68408078\mathchar 28956_{\mathchar 29027}$ taking values $\mathchar 28721\delimiter 68408078\mathchar 28723$ , $\mathchar 28721$ , and $\mathchar 28723$ . DFS-SG is executed for a single decision round, whereas the other algorithms are run for a fixed duration of $\mathchar 28723\mathchar 28720\mathchar 28720$ seconds. Under different delay configurations, the algorithms complete different numbers of decision rounds within this time window. Results are averaged over 20 Monte Carlo trials.

Algorithm	Coverage (%)
Algorithm	$\mathchar 28956_{\mathchar 29030}{\mathchar 12349}\mathchar 314\mathchar 28720\mathchar 28721\mathchar 29043$ , $\mathchar 28956_{\mathchar 29027}{\mathchar 12349}\mathchar 314\mathchar 28720\mathchar 28723\mathchar 29043$	$\mathchar 28956_{\mathchar 29030}{\mathchar 12349}\mathchar 314\mathchar 28720\mathchar 28723\mathchar 29043$ , $\mathchar 28956_{\mathchar 29027}{\mathchar 12349}\mathchar 314\mathchar 28720\mathchar 28723\mathchar 29043$	$\mathchar 28956_{\mathchar 29030}{\mathchar 12349}\mathchar 314\mathchar 28720\mathchar 28729\mathchar 29043$ , $\mathchar 28956_{\mathchar 29027}{\mathchar 12349}\mathchar 314\mathchar 28720\mathchar 28723\mathchar 29043$
DFS-BSG	42.19 $\mathchar 8710$ 1.83	41.96 $\mathchar 8710$ 1.98	42.30 $\mathchar 8710$ 2.20
Anaconda-0n	47.33 $\mathchar 8710$ 1.84	46.52 $\mathchar 8710$ 1.92	46.78 $\mathchar 8710$ 1.77
Anaconda-1n	58.27 $\mathchar 8710$ 1.22	56.13 $\mathchar 8710$ 1.77	52.17 $\mathchar 8710$ 1.68
Anaconda-2n	58.75 $\mathchar 8710$ 1.18	56.75 $\mathchar 8710$ 1.28	51.68 $\mathchar 8710$ 1.90
Anaconda-3n	59.05 $\mathchar 8710$ 0.89	57.10 $\mathchar 8710$ 1.04	51.73 $\mathchar 8710$ 0.91

TABLE II: Comparison of average coverage performance (%) within

\mathchar 28723\mathchar 28720\mathchar 28720

s across three scenarios with different delay configurations (Fig. 6 ). The highest value in each scenario is highlighted in bold .

Fig. 7: Comparison of Anaconda-5n vs. DFS-BSG in real-time coverage performance with scaling network. Cameras select their FOV directions using Anaconda-5n or DFS-BSG , across five scenarios with different network and map sizes. To keep the camera density constant, the map size scales linearly from $\mathchar 28722\mathchar 28723\mathchar 8706\mathchar 28722\mathchar 28723$ to $\mathchar 28725\mathchar 28720\mathchar 8706\mathchar 28725\mathchar 28720$ as the network size ranges from $\mathchar 28721\mathchar 28720$ to $\mathchar 28725\mathchar 28720$ . Results are averaged over 20 Monte Carlo trials, each with a fixed $\mathchar 28723\mathchar 28720\mathchar 28720$ s time window under delays $\delimiter 67273472\mathchar 28956_{\mathchar 29030}\mathchar 24891\mathchar 28956_{\mathchar 29027}\delimiter 84054785\mathchar 12349\delimiter 67273472\mathchar 314\mathchar 28720\mathchar 28721\text{s}\mathchar 24891\mathchar 314\mathchar 28720\mathchar 28721\text{s}\delimiter 84054785$ .

Explore similar work

Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays
Apr 7, 2026Pranjal Sharma, Zirui Xu, Vasileios TzoumasSubmodular Optimization Distributed Optimization
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109, USA
Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach
Mar 29, 2026Zirui Xu, Vasileios TzoumasSubmodular Optimization Multi-Agent Coordination
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA
Distributed Equilibrium-Seeking in Target Coverage Games via Self-Configurable Networks under Limited Communication
Mar 18, 2026Jayanth Bhargav, Zirui Xu, Vasileios Tzoumas +2Multi-Agent Coordination Nash Equilibrium Computation
Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907 USA · Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

Apr 7, 2026J/K move · Enter open · S save

Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays

Pranjal Sharma, Zirui Xu, Vasileios Tzoumas

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

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays

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

Distributed Equilibrium-Seeking in Target Coverage Games via Self-Configurable Networks under Limited Communication