Paper deep dive
Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization
Zirui Xu, Vasileios Tzoumas
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/20/2026, 8:03:34 PM
Summary
The paper introduces Anaconda, a distributed multi-agent framework for scalable submodular bandit optimization under realistic communication constraints. It enables near-optimal coordination by limiting information relays to one-hop communication and optimizing agents' communication neighborhoods online via distributed bandit optimization. The approach defines a Value of Coordination (VoC) metric and provides theoretical suboptimality bounds, validated through simulations showing superior scalability and performance compared to benchmarks.
Entities (6)
Relation Signals (6)
Anaconda → solves → Submodular Bandit Optimization
confidence 95% · We provide a distributed multi-agent decision-making framework that enables both scalable and near-optimal action coordination... in unknown environments... This paper extends our preliminary work... to include new theoretical results... for distributed submodular bandit optimization.
Anaconda → uses → One-hop Communication
confidence 92% · Our approach enables scalability by (i) limiting information relays to only one-hop communication
Anaconda → optimizes → Communication Neighborhoods
confidence 90% · our approach enables near-optimal action coordination by optimizing the agents' communication neighborhoods over time, through distributed online bandit optimization
Value of Coordination → quantifies → Benefit of Information Access
confidence 90% · we define the Value of Coordination (VoC), an information-theoretic metric that quantifies for each agent the benefit of information access to its neighbors.
Anaconda → validatedin → Multi-camera Area Monitoring
confidence 88% · We validate in simulations the scalability and near-optimality of our approach... multi-camera area monitoring.
Anaconda → outperforms → Sequential Greedy
confidence 85% · it is observed to converge faster, outperform benchmarks for bandit submodular coordination
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2602.19366v1
- Canonical: https://arxiv.org/abs/2602.19366v1
Trouble viewing inline? Open PDF directly →
Full Text
223,798 characters extracted from source content.
Expand or collapse full text
.,;:!?)’ Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization Zirui Xu, Vasileios Tzoumas† †Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA; ziruixu,vtzoumas@umich.edu 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 (i) 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. I Introduction In the future, large-scale teams of distributed agents will be executing sensing-driven tasks such as target tracking [47], environmental mapping [1], and area monitoring [8]. These collaborative tasks require the distributed agents to share their local observations—expand information access—to improve coordination performance. However, expanding information access is challenging due to the limited communication, computing, and sensing capabilities onboard each agent, and the above tasks often operate in unknown, unstructured, and dynamic environments. In more detail, several challenges to scalability and optimality appear: (a) Limited communication bandwidth: Each agent can communicate with only a limited number of peers at a time, rather than with all physically reachable ones [20, 31]. (b) Finite data rate: Communication occurs via onboard radio modules with restricted data rates, ranging from as low as 0.25 Mbps (e.g., Digi XBee 3 Zigbee 3 [10]) to around 100 Mbps (e.g., Silvus Tech SL5200 [39]), far below the 0.8–1.5 Gbps commonly available in everyday Wi-Fi 6 systems [19]. (c) Unguaranteed network connectivity: Agents may receive information only from those within a fixed communication range or line of sight, meaning the communication graph is not guaranteed to remain connected [21]. (d) Unstructured environment: The environment may be unknown a priori and partially observable. Thus, the informational value of each observation becomes known only once the observation is made. This optimization setting corresponds to the bandit feedback model [25]. Figure 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. These challenges motivate distributed optimization problems in bandit settings [25] for large-scale tasks in robotics, control, and machine learning. Such joint optimization problems often take the form of maxai,t∈i,∀i∈,∀t∈[T]∑t=1Tf(ai,ti∈), _ 29025 _ 29033 24891 29044 \, 12850 \, 29014 _ 29033 24891 568 \, 29033 \, 12850 \, 29006 24891 \, 568 \, 29044 \, 12850 \, 67482370 29012 84267779 4944 _ 29044 12349 28721 29012 \, 29030 67273472\,\ 29025 _ 29033 24891 29044 \_ 29033 \, 12850 \, 29006 \, 84054785 24891 (1) where T 29012 is the operation time-horizon, and at each time step t∈[T] 29044 12850 67482370 29012 84267779, the agents 29006 need to each select an action ai,t 29025 _ 29033 24891 29044 from its available action set i 29014 _ 29033 to collaboratively maximize the unknown a priori objective function f:2∏i∈i↦→ℝ 29030 24634 28722 4945 _ 29033 12850 29006 29014 _ 29033 567 545 29010 that captures the task utility [24, 40, 44, 1, 15, 28, 17, 8, 37, 11, 34, 36, 46]. In information-gathering tasks, f 29030 is often submodular [13]: submodularity is a diminishing returns property, and it emanates due to the possible information overlap among the information gathered by the agents [24]. For example, in target monitoring with multiple cameras at fixed locations, 29006 is the set of cameras, i 29014 _ 29033 is the available directions the camera can choose, and f 29030 is the number of targets covered by the cameras’ collective field of view (FOV). The cameras have no prior knowledge of target locations and can observe them only when they fall within the cameras’ collective FOV; targets that remain uncovered are therefore unknown to the cameras. As a result, the cameras can accurately evaluate only the utility of the FOVs they actually choose, which corresponds to the bandit feedback setting [25]. The optimization problem in eq.˜1 is NP-hard even in known environments [12]. Polynomial-time algorithms with provable approximation guarantees exist. A classical example is the Sequential Greedy (SG) algorithm [13], which achieves a 1/2 28721 68408078 28722 -approximation ratio. Since many multi-agent tasks, such as target tracking, collaborative mapping, and area monitoring, can be formulated as submodular coordination problems, SG and its variants have been widely adopted across the controls, machine learning, and robotics communities [24, 40, 44, 1, 15, 17, 8, 37, 26, 36, 34, 22, 23, 46]. In unknown environments instead, online variants of SG are proposed [42, 41, 43, 16, 5, 50, 49, 47], providing guaranteed suboptimality over the horizon T 29012 . Continuous-domain optimization techniques have also been leveraged in the bandit setting by first using the multilinear extension [4], to lift the discrete submodular function f 29030 to the continuous domain, then applying gradient/consensus-based techniques, and finally rounding back to the discrete domain to obtain a near-optimal solution [30, 50, 6, 51, 36]. However, the algorithms above cannot scale as the network grows when challenges (a)–(d) exist simultaneously. In particular, current distributed approaches, based on either sequential communication in the discrete domain [1, 49, 47] or repeated consensus iterations in the continuous domain [42, 41, 43, 16, 5, 30, 50, 6, 36, 26, 51], assume instantaneous agent-to-agent communication, i.e., infinite data rates. But if accounting for the limited data rates of onboard radio modules, per challenge (b), decision times of these methods can scale cubically in network size or even more [46, Table 1]. This is due to: • Message size: The size of communication messages can scale proportionally with the number of agents. • Information relay: Distributed agents use multi-hop relays to expand information access. In sum, under challenges (a)–(d), where instantaneous communication is infeasible and the environment is unknown, achieving both scalability and optimality requires restricting information access intelligently, via limiting message size and/or information relay, to balance the trade-off between decision time and decision optimality. Methods in [35, 18] leverage communication quantization to shorten messages and evaluate its effect on optimality. The framework in [3] reduces communication overhead by exploiting the sparsity of the underlying information dependence among agents and omitting information sharing between agents with low dependence accordingly. It also establishes the necessary conditions for convergence. However, the approaches in [35, 18, 3] focus on convex optimization. In discrete submodular optimization, the focus of this paper, current works [15, 28, 17] only perform f 29030 -agnostic communication restriction, i.e., the topology designed will remain the same, independently of the f 29030 specified by the application. In more detail, [15, 28, 17] study a variant of SG with restricted information relay where each agent i 29033 receives information from only a subset rather than all of 1,…,i−1\ 28721 24891 … 24891 29033 8704 28721 \ as in the classical SG.111In discrete submodular optimization, agents perform sequential communication, where message complexity depends on the network topology. For example, in a line network, a message from agent i−1 29033 8704 28721 to i 29033 may aggregate information from all preceding agents 1,…,i−1\ 28721 24891 … 24891 29033 8704 28721 \, whereas in a complete network it contains only agent i−1 29033 8704 28721 ’s data, with other information transmitted through separate links. These works derive suboptimality bounds that scale inversely with the independence number of the resulting information-sharing topology,222This information-sharing topology is the Directed Acyclic Graph (DAG) derived from the communication network. and further propose a centralized information-sharing topology design method based on these bounds [17]. The recent algorithm in [46] restricts information access within one-hop neighbors, thus prohibiting relays and having each agent-to-agent message to contain information only about the agent that transmits it. It also enables partially parallelized action selection to reduce communication latency. Although [46] characterizes f 29030 -specific coordination performance, the bound is intractable to optimize even in hindsight, and therefore cannot support intelligent information access restriction. Contributions. We provide a distributed multi-agent decision-making framework that enables both scalable and near-optimal action coordination in unknown environments under realistic communication constraints in bandwidth, data rate, and connectivity. Our approach enables scalability by (i) limiting information relays to only one-hop communication and (i) keeping inter-agent messages small, having each agent transmit only its own action information. Despite these information-access restrictions, our approach improves the near-optimality bound of action coordination by optimizing the agents’ communication neighborhoods over time, through distributed online bandit optimization (subject to the agents’ bandwidth constraints)—the necessity for such information access optimization is demonstrated in Fig. 1. To our knowledge, this is the first rigorous approach that enables multi-agent networks to scale near-optimal coordination by actively optimizing the restricted information access through active communication topology self-configuration. The approach is fully distributed: each agent jointly selects its action and designs its local communication neighborhood subject to its coordination neighborhood and bandwidth constraints. The algorithm has the following properties: Scalability Anaconda enjoys improved scalability under communication constraints by having a convergence time of O(||2) 29007 67273472 69640972 29006 69640972 28722 84054785 in sparse networks, accounting for information relay in multi-hop communication (Section˜V). This is faster than existing methods even though they only consider known environments [46, Table I]. In practice, the algorithm can convergence even faster, e.g., only sublinearly in || 69640972 29006 69640972 in the area monitoring simulations (Section˜VII-D). Anytime Self-Configuration with Arbitrary Topologies Anaconda enables each agent to adapt its communication neighborhood online according to the given f 29030 , resulting in coordination over a directed, time-varying, and potentially disconnected network. The fully distributed self-configuration mechanism further allows agents to join or leave the system without disrupting the co-optimization process. Our prior work [46], instead, does not optimize the network; [17] performs network design centrally without leveraging f 29030 ; and [1, 8, 37, 26, 36, 34, 22, 47, 49] require connected networks. Approximation Performance Anaconda enjoys anytime, strictly positive, f 29030 -specific suboptimality bounds against an optimal solution of eq.˜1 (Section˜IV). The bounds capture the benefit of information access for each agent and thus remain valid under arbitrarily optimized communication topologies, regardless of global connectivity. In particular, Theorem˜1, along with our numerical evaluations, validates that coordination performance improves through network optimization, and Theorems˜2 and 3 ensure that Anaconda achieves strictly positive performance guarantees at all times. The bounds in [17, 15, 28] are instead f 29030 -agnostic; the bound in our prior work [46] does not support network optimization; and [1, 8, 37, 26, 36, 34, 22, 47, 49] provide suboptimality guarantees only under connected network assumptions. Numerical evaluations. We validate Anaconda through simulations of multi-camera area monitoring. The results first show that the proposed information-driven neighbor selection strategy outperforms typical baselines (nearest and random neighbors) in robotics and controls [52, 27, 46], with particularly large gaps in certain structured environments (Section˜VI). Then, comparisons with state-of-the-art centralized and sequential methods (DFS-SG and DFS-BSG) under both idealized and realistic delay settings reveal a fundamental trade-off between coordination optimality and convergence speed, and highlight the importance of delay-aware evaluation for real-time performance. Although the benchmarks require relaxed versions of the problem in eq.˜1 to be applicable, Anaconda still achieves competitive or better coverage (Sections˜VII-A, VII-B and VII-C). Finally, large-scale simulations confirm the scalability of Anaconda: while benchmarks such as DFS-BSG incur prohibitive communication delays, Anaconda maintains a constant time per decision round and can scale sublinearly in network size in practice (Section˜VII-D). We ran all simulations using Python 3.11.7 on a Windows PC with an Intel Core i9-14900KF CPU @ 3.20 GHz and 64 GB RAM. The code is available at https://github.com/UM-iRaL/Self-configurable-network. Comparison with preliminary work [48, 46]. This paper extends our preliminary work [48] to include new theoretical results, extensive evaluations, and proofs of all claims. We introduce a tighter a priori bound (Theorem˜1), a strictly positive a posteriori bound (Theorem˜2), and a strictly positive asymptotic bound (Theorem˜3), and we comprehensively evaluate the proposed algorithm across coordination performance, neighborhood design, and scalability metrics in area monitoring scenarios (Section˜VI). This paper also extends the formulation in prior work [46] where communication neighborhoods are fixed and constructed heuristically (e.g., via nearest neighbors). Here, we perform network optimization and demonstrate that the resulting configurations outperform nearest neighbors in area monitoring scenarios (Section˜VI). I Distributed Coordination and Network Co-Optimization We present the problem formulation of Distributed Coordination and Network Co-Optimization. We use the notation: • ≜∏i∈i 29014 _ 29006 4945 _ 29033 \, 12850 \, 29006 \, 29014 _ 29033 is the cross product of sets ii∈\ 29014 _ 29033 \_ 29033 \, 12850 \, 29006 . • [T]≜1,…,T 67482370 29012 84267779 \ 28721 24891 … 24891 29012 \ for any positive integer T 29012 . • f(a|)≜f(∪a)−f() 29030 67273472\, 29025 \, 69640972\, 28993 \, 84054785 29030 67273472\, 28993 8795 \ 29025 \\, 84054785 8704 29030 67273472\, 28993 \, 84054785 is the marginal gain of set function f:2↦→ℝ 29030 12346 28722 29014 567 545 29010 for adding a∈ 29025 12850 29014 to ⊆ 28993 12818 29014 . • || 69640972 28993 69640972 is the cardinality of a discrete set 28993 . We also lay down the following framework about the agents’ communication network and the objective function f 29030 . Communication network. The agents’ communication network t=(,ℰt) 28999 _ 29044 12349 67273472 29006 24891 28997 _ 29044 84054785, ∀t 568 29044 is undetermined a priori, where ℰt 28997 _ 29044 is the set of (directed) communication edges among agents 29006 at time t 29044 . The goal of this work is for the agents to jointly optimize ℰt 28997 _ 29044 to enable convergence to a near-optimal solution to (1) despite distributed coordination. The network optimized by 29006 can be directed and even disconnected. We refer to the case where every agent receives information from all others as fully centralized, and the case where no agent receives information from any other as fully decentralized. Communication neighborhood. When a communication channel exists from agent j 29034 to agent i 29033 at time t 29044 , i.e., (j→i)∈ℰt 67273472 29034 12833 29033 84054785 12850 28997 _ 29044 , then i 29033 can receive, store, and process information sent by j 29034 , and the set of all such j 29034 is i 29033 ’s communication neighborhood, denoted as i,t 29006 _ 29033 24891 29044 . Communication constraints. Each agent i 29033 can receive information from up to αi 28939 _ 29033 other agents at the same time due to onboard bandwidth constraints, i.e., |i,t|≤αi 69640972 29006 _ 29033 24891 29044 69640972\; 12820 28939 _ 29033 , ∀t 568 29044 . Also, we denote as ℳi⊆\i 29005 _ 29033 12818 29006 8814 \ 29033 \ the set of agents that can potentially send information to agent i 29033 —not all \i 29006 8814 \ 29033 \ can reach agent i 29033 due to distance or obstacles: agent i 29033 can pick its neighbors by choosing at most αi 28939 _ 29033 agents from ℳi 29005 _ 29033 . We refer to ℳi 29005 _ 29033 as agent i 29033 ’s coordination neighborhood (i,t⊆ℳi 29006 _ 29033 24891 29044 12818 29005 _ 29033 , ∀t 568 29044 ). Definition 1 (Normalized and Non-Decreasing Submodular Set Function [13]). A set function f:2↦→ℝ 29030 12346 28722 29014 567 545 29010 is normalized and non-decreasing submodular if and only if • (Normalization) f(∅)=Γ 29030 67273472 571 84054785 12349 0; • (Monotonicity) f()≤f(ℬ) 29030 67273472 28993 84054785 12820 29030 67273472 28994 84054785, ∀⊆ℬ⊆ 568 \, 28993 12818 28994 12818 29014 ; • (Submodularity) f(s|)≥f(s|ℬ) 29030 67273472 29043 \, 69640972\, 28993 84054785 12821 29030 67273472 29043 \, 69640972\, 28994 84054785, ∀⊆ℬ⊆ 568 \, 28993 12818 28994 12818 29014 and s∈ 29043 12850 29014 . Intuitively, if f() 29030 67273472 28993 84054785 captures the number of targets tracked by a set 28993 of sensors, then the more sensors are deployed, more or the same targets are covered; this is the non-decreasing property. Also, the marginal gain of tracked targets caused by deploying a sensor s 29043 drops when more sensors are already deployed; this is the submodularity property. Definition 2 (2nd-order Submodular Set Function [9, 14]). f:2↦→ℝ 29030 12346 28722 29014 567 545 29010 is 2nd-order submodular if and only if f(s|)−f(s|∪)≥f(s|ℬ∪)−f(s|∪ℬ∪), 29030 67273472 29043 \, 69640972\, 28995 84054785 8704 29030 67273472 29043 \, 69640972\, 28993 8795 28995 84054785 12821 29030 67273472 29043 \, 69640972\, 28994 8795 28995 84054785 8704 29030 67273472 29043 \, 69640972\, 28993 8795 28994 8795 28995 84054785 24891 (2) for any disjoint ,ℬ,⊆ 28993 24891 28994 24891 28995 12818 29014 (∩ℬ∩=∅ 28993 8796 28994 8796 28995 12349 571 ) and s∈ 29043 12850 29014 . Intuitively, if f() 29030 67273472 28993 84054785 captures the number of targets tracked by a set 28993 of sensors, then marginal gain of the marginal gains drops when more sensors are already deployed. Problem 1 (Distributed Coordination and Network Co-Optimization). At each t∈[T] 29044 12850 67482370 29012 84267779, each agent i∈ 29033 12850 29006 selects a communication neighborhood i,t 29006 _ 29033 24891 29044 of size up to αi 28939 _ 29033 and an action ai,t 29025 _ 29033 24891 29044 to solve the optimization problem maxi,t⊆ℳi,|i,t|≤ffi∀i∈,∀t∈[T]maxai,t∈i∀i∈,∀t∈[T]∑t=1Tf(ai,ti∈), _ 29043 29045 29026 29025 29042 29042 29025 29049 29027 29006 _ 29033 24891 29044 \, 12818 \, 29005 _ 29033 24891 \, 69640972 29006 _ 29033 24891 29044 69640972\, 12820 \, 28939 _ 29033 \\ 568 \, 29033 \, 12850 \, 29006 24891 \, 568 \, 29044 \, 12850 \, 67482370 29012 84267779 29043 29045 29026 29025 29042 29042 29025 29049 \, _ 29043 29045 29026 29025 29042 29042 29025 29049 29027 29025 _ 29033 24891 29044 \, 12850 \, 29014 _ 29033 \\ 568 \, 29033 \, 12850 \, 29006 24891 \, 568 \, 29044 \, 12850 \, 67482370 29012 84267779 29043 29045 29026 29025 29042 29042 29025 29049 4944 _ 29044 12349 28721 29012 \, 29030 67273472\,\ 29025 _ 29033 24891 29044 \_ 29033 \, 12850 \, 29006 \, 84054785 24891 (3) where (i) each agent i 29033 can coordinate with its neighbors only, without any information about non-neighbors, (i) f:2↦→ℝ 29030 24634 28722 29014 _ 29006 567 545 29010 is a normalized, non-decreasing submodular, and 2nd-order submodular, and (i) f 29030 is known via bandit feedback, in particular, each agent i 29033 can access the value of f(t) 29030 67273472 28993 _ 29044 84054785 only, ∀t⊆ai,t∪aj,tj∈i,t 568 \, 28993 _ 29044 12818 \ 29025 _ 29033 24891 29044 \ 8795 \ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 , once the agent has selected ai,t 29025 _ 29033 24891 29044 and received aj,tj∈i,t\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 from neighbors. ˜1 captures the intrinsic coupling between coordination performance and information access, as illustrated by the example in Figure˜1. The objective of this paper is to design the communication network topology that maximizes action coordination performance through solving ˜1. I Alternating Coordination and Network-Design Algorithm (Anaconda) 0: Time horizon T 29012 ; agent i 29033 ’s coordination neighborhood ℳi 29005 _ 29033 ; agent i 29033 ’s communication bandwidth αi 28939 _ 29033 . 10: Action ai,t 29025 _ 29033 24891 29044 and communication neighborhood i,t 29006 _ 29033 24891 29044 , ∀t∈[T] 568 29044 12850 67482370 29012 84267779. 1: i,Γ←∅,∀i∈ 29006 _ 29033 24891 0 12832 571 24891 568 29033 12850 29006 ; 2: for each time step t∈[T] 29044 12850 67482370 29012 84267779 do 3: ai,t←ActSel([T],i) 29025 _ 29033 24891 29044 12832 ActSel 67273472 67482370 29012 84267779 24891 29014 _ 29033 84054785; 4: i,t←NeiSel(ai,t,[T],ℳi,αi) 29006 _ 29033 24891 29044 12832 NeiSel 67273472 29025 _ 29033 24891 29044 24891 67482370 29012 84267779 24891 29005 _ 29033 24891 28939 _ 29033 84054785; 25: receive neighbors’ actions aj,tj∈i,t\ 29025 _ 29034 24891 29044 \_ 29034 \, 12850 \, 29006 _ 29033 24891 29044 and update ActSel (per lines 6-8) and NeiSel (per lines 6-11); 6: end for Algorithm 1 AlterNAting COordination and Network Design Algorithm (Anaconda) for Agent i 29033 We present Anaconda. Anaconda approximates a solution to ˜1 by alternating the optimization for action coordination and communication neighborhood design. Since both action coordination and communication neighborhood design take the form of adversarial bandit problems, we present first the adversarial bandit (Section˜I-A), then the algorithms ActSel (Section˜I-B) and NeiSel (Section˜I-C). I-A Adversarial Bandit Problem The adversarial bandit problem involves an agent selecting a sequence of actions to maximize the total reward over a given number of time steps [25]. The challenge is that, at each time step, no action’s reward is known to the agent a priori, and after an action is selected, only the selected action’s reward will become known. To present the problem, we have: • 29014 denotes the available action set; • |t∈ 69640972_ 29044 12850 29014 denotes the agent’s selected action at time t 29044 ; • r|t,t∈[Γ,1] 29042 _ 69640972_ 29044 24891 \, 29044 12850 674823700 24891 28721 84267779 denotes the reward of selecting |t 69640972_ 29044 at time t 29044 . Problem 2 (Adversarial Bandit [25]). Assume a horizon of T 29012 time steps. At each time step t∈[T] 29044 12850 67482370 29012 84267779, the agent needs to select an action |t∈ 69640972_ 29044 12850 29014 such that the regret RegretT≜max|∈∑t=1Tr|,t−∑t=1Tr|t,t, 29010 29029 29031 29042 29029 29044 _ 29012 _ 69640972\, 12850 \, 29014 \; 4944 _ 29044 12349 28721 29012 \; 29042 _ 69640972 24891 \, 29044 \; 8704 \; 4944 _ 29044 12349 28721 29012 \; 29042 _ 69640972_ 29044 24891 \, 29044 24891 (4) is minimized, where no actions’ rewards are known a priori, and only the reward r|t,t∈[Γ,1] 29042 _ 69640972_ 29044 24891 \, 29044 12850 674823700 24891 28721 84267779 becomes known to the agent after |t 69640972_ 29044 is selected. The goal of solving ˜2 is to achieve a sublinear RegretT 29010 29029 29031 29042 29029 29044 _ 29012 , i.e., RegretT/T→Γ 29010 29029 29031 29042 29029 29044 _ 29012 68408078 29012 12833 0 for T→∞ 29012 12833 561 , since this implies that the agent asymptotically chooses optimal actions even though the rewards are unknown a priori [25]. The most classical adversarial bandit algorithm Exp3 [2] achieves the goal above by obtaining a regret bound of O~(||T) 29007 67273472 69640972 29014 69640972 29012 84054785, where O~(⋅) 29007 67273472 8705 84054785 hides log terms. During the past two decades, several refined adversarial bandit algorithms have emerged, including Exp3-IX for high-probability regret bounds via implicit exploration [32], Exp3++ for adaptation between stochastic and adversarial regimes [38], and Tsallis-INF for minimax-optimal regret with improved adaptivity through Tsallis entropy regularization [53]. In this paper, we will formulate both action coordination and neighbor selection problems in the form of ˜2, and employ Exp3 as the bandit solver without loss of generality. Alternative methods such as those mentioned above are also applicable (e.g., Exp3-IX was used in [48]). I-B Action Coordination 0: Time horizon T 29012 and agent i 29033 ’s action set i 29014 _ 29033 . 10: Agent i 29033 ’s action ai,t 29025 _ 29033 24891 29044 , ∀t∈[T] 568 29044 12850 67482370 29012 84267779. 1: ηia←2log|i|/(|i|T) 28945 _ 29033 29025 12832 28722 69640972 29014 _ 29033 69640972\, 68408078\, 67273472 69640972 29014 _ 29033 69640972 29012 84054785; 2: w1←[w1,1,…,w|i|,1]⊤ 29047 _ 28721 12832 67482370 29047 _ 28721 24891 28721 24891 … 24891 29047 _ 69640972 29014 _ 29033 69640972 24891 28721 84267779 574 with w|,1=1,∀a∈i 29047 _ 69640972 24891 28721 12349 28721 24891 568 29025 12850 29014 _ 29033 ; 3: for each time step t∈[T] 29044 12850 67482370 29012 84267779 do 4: get distribution pt←wt/‖wt‖1 29040 _ 29044 12832 29047 _ 29044 \, 68408078\, 69645069 29047 _ 29044 69645069_ 28721 ; 5: draw action ai,t∈i 29025 _ 29033 24891 29044 12850 29014 _ 29033 from pt 29040 _ 29044 ; 26: input ai,t 29025 _ 29033 24891 29044 to NeiSel and receive neighbors’ actions aj,tj∈i,t\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 ; 37: rai,t,t←f(ai,t|aj,tj∈i,t) 29042 _ 29025 _ 29033 24891 29044 24891 29044 12832 29030 67273472\, 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 \, 84054785 and normalize rai,t,t 29042 _ 29025 _ 29033 24891 29044 24891 29044 to [Γ,1] 674823700 24891 28721 84267779; 8: r^a,t←1−(ai,t=a)pa,t(1−rai,t,t) 29042 _ 29025 24891 \, 29044 12832 28721 8704 28721 67273472 29025 _ 29033 24891 29044 \, 12349 \, 29025 84054785 29040 _ 29025 24891 29044 67273472 28721 \, 8704 \, 29042 _ 29025 _ 29033 24891 29044 24891 29044 84054785, ∀a∈i 568 29025 12850 29014 _ 29033 ; 9: wa,t+1←wa,texp(ηinr^a,t),∀a∈i 29047 _ 29025 24891 29044 8235 28721 12832 29047 _ 29025 24891 29044 67273472 28945 _ 29033 29038 \, 29042 _ 29025 24891 29044 84054785 24891 568 29025 12850 29014 _ 29033 ; 10: end for Algorithm 2 ActSel for Agent i 29033 We introduce the ActSel algorithm and establish its performance guarantees. To this end, we first define the coordination problem that ActSel addresses and relate it to ˜2 for each agent. • t≜ai,ti∈ 28993 _ 29044 \ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 is the set of all agents’ actions at t 29044 ; • ∈argmaxai∈i,∀i∈f(aii∈) 28993 29007 29008 29012 12850 _ 29025 _ 29033 12850 29014 _ 29033 24891 \, 568 \, 29033 12850 29006 29030 67273472\ 29025 _ 29033 \_ 29033 12850 29006 84054785 is the optimal actions for agents 29006 that solve eq.˜1. Intuitively, each agent i 29033 ’s goal at each time step t 29044 is to efficiently select an action ai,t 29025 _ 29033 24891 29044 that solves maxai,t∈if(ai,t|aj,tj∈i,t), _ 29025 _ 29033 24891 29044 12850 29014 _ 29033 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 24891 (5) To enable efficiency, the agents should ideally select actions simultaneously, unlike offline algorithms such as Sequential Greedy [13] and Resource-Aware distributed Greedy [46] that employ (partially parallelized) sequential operations. But if they want to select actions simultaneously, aj,tj∈i,t\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 will become known only after agent i 29033 selects ai,t 29025 _ 29033 24891 29044 and communicates with i,t 29006 _ 29033 24891 29044 . Therefore, computing the marginal gain is possible only in hindsight, once all agents’ decisions have been finalized for time step t 29044 . Thus, action selection for each agent aligns with the framework of ˜2, where the reward of selecting ai,t∈i 29025 _ 29033 24891 29044 12850 29014 _ 29033 is rai,t,t≜f(ai,t|aj,tj∈i,t) 29042 _ 29025 _ 29033 24891 29044 24891 29044 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785, which becomes available only after choosing ai,t 29025 _ 29033 24891 29044 . ActSel starts by initializing a learning rate ηia 28945 _ 29033 29025 and a weight vector wt 29047 _ 29044 for all available actions a∈i 29025 12850 29014 _ 29033 (Algorithm˜2’s lines 1-2). Then, at each t∈[T] 29044 12850 67482370 29012 84267779, it sequentially executes the following steps: 1. Compute probability distribution pt 29040 _ 29044 using wt 29047 _ 29044 (lines 3-4); 2. Select action ai,t∈i 29025 _ 29033 24891 29044 12850 29014 _ 29033 by sampling from pt 29040 _ 29044 (line 5); 3. Send ai,t 29025 _ 29033 24891 29044 to NeiSel and receive neighbors’ actions aj,tj∈i,t\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 (line 6); 4. Compute reward rai,t,t 29042 _ 29025 _ 29033 24891 29044 24891 29044 , estimate reward r^a,t 29042 _ 29025 24891 29044 of each a∈ 29025 12850 29014 , and update weight wa,t+1 29047 _ 29025 24891 29044 8235 28721 of each a∈i 29025 12850 29014 _ 29033 (lines 7-9).333The coordination algorithms in [11, 34, 36] instruct the agents to select actions simultaneously at each time step as ActSel, but they lift the coordination problem to the continuous domain and require each agent to know/estimate the gradient of the multilinear extension of f 29030 , which leads to a decision time at least one order higher than ActSel [46]. We introduce the novel quantification that evaluates the benefit of information access in solving ˜1. Definition 3 (Value of Coordination (VoC)). Consider t∈[T] 29044 12850 67482370 29012 84267779 and agent i∈ 29033 12850 29006 with action ai,t 29025 _ 29033 24891 29044 and coordination neighborhood ℳi 29005 _ 29033 . Agent i 29033 ’s Value of Coordination is defined as: VoCf,t(ai,t;i,t)≜f(ai,t)−f(ai,t|aj,tj∈i,t), VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 29030 67273472 29025 _ 29033 24891 29044 84054785 8704 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 24891 (6) where i,t⊆ℳi 29006 _ 29033 24891 29044 12818 29005 _ 29033 is the communication neighborhood that i 29033 chooses to receive information from, |i,t|≤αi 69640972 29006 _ 29033 24891 29044 69640972 12820 28939 _ 29033 . VoCf,t(ai,t;i,t) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 is thus an information theory metric similar to mutual information yet over the set function f 29030 . It represents the overlap between agent i 29033 and its communication neighbors’ actions. Particularly, ∑t=1TVoCf,t(ai,t;i,t) 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 evaluates agent i 29033 ’s benefit in coordinating with i,t 29006 _ 29033 24891 29044 over the horizon T 29012 . The larger is this value, the more related is the received information to the selected actions. Definition 4 (Curvature [7]). The curvature of a normalized submodular function f:2↦→ℝ 29030 24634 28722 29014 567 545 29010 is defined as κf≜1−min|∈f()−f(\|)f(|). 28948 _ 29030 28721 8704 _ 69640972 12850 29014 29030 67273472 29014 84054785 8704 29030 67273472 29014 8814 \ 69640972\ 84054785 29030 67273472 69640972 84054785 314 (7) Intuitively, κf 28948 _ 29030 measures how far f 29030 is from modularity: if κf=Γ 28948 _ 29030 12349 0, then f()−f(\|)=f(|) 29030 67273472 29014 84054785 8704 29030 67273472 29014 8814 \ 69640972\ 84054785 12349 29030 67273472 69640972 84054785, ∀|∈ 568 69640972 12850 29014 , i.e., f 29030 is modular. In contrast, κf=1 28948 _ 29030 12349 28721 in the extreme case where there exist |∈ 69640972 12850 29014 such that f()=f(\|) 29030 67273472 29014 84054785 12349 29030 67273472 29014 8814 \ 69640972\ 84054785, i.e., | 69640972 has no contribution in the presence of \| 29014 8814 \ 69640972\. Proposition 1 (Approximation Performance of ActSel). Over t∈[T] 29044 12850 67482370 29012 84267779, agents 29006 can use ActSel to select actions tt∈[T]\ 28993 _ 29044 \_ 29044 12850 67482370 29012 84267779 such that ∑t=1Tf(t)≥ 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 12821 (1−ˇf)∑t=1T[f()+∑i∈VoCf,t(ai,t;i,t)] 67273472 28721 8704 28948 _ 29030 84054785 4944 _ 29044 12349 28721 29012 67482370 29030 67273472 28993 29007 29008 29012 84054785 8235 4944 _ 29033 12850 29006 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 84267779 −O~(|||¯|T). 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 29012 84054785 314 (8) where |¯|≜maxi∈|i| 69640972 29014 69640972 _ 29033 12850 29006 69640972 29014 _ 29033 69640972. Proposition˜1 implies that ActSel’s performance increases for neighborhoods i,ti∈\ 29006 _ 29033 24891 29044 \_ 29033 12850 29006 with higher VoCf,t(ai,t;i,t) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785. The proof appears in Appendix A. Lemma 1 (Monotonicity and Submodularity of VoC). Given an action a∈i 29025 12850 29014 _ 29033 and a non-decreasing and 2nd-order submodular function f:2↦→ℝ 29030 24634 28722 29014 _ 29006 567 545 29010 , then VoCf,t(a;⋅) VoC_ 29030 24891 29044 67273472 29025 24635 \, 8705 84054785 is non-decreasing and submodular in the second argument. NeiSel will next leverage Lemma˜1 to enable each agent to individually select its communication neighborhood that optimizes the approximation bound of ActSel (Proposition˜1). I-C Neighbor Selection 0: Time horizon T 29012 ; agent i 29033 ’s coordination neighborhood ℳi 29005 _ 29033 ; agent i 29033 ’s communication bandwidth αi 28939 _ 29033 . 10: Agent i 29033 ’s communication neighborhood i,t 29006 _ 29033 24891 29044 , ∀t∈[T] 568 29044 12850 67482370 29012 84267779. 1: ηin←2log|ℳi|/(|ℳi|T) 28945 _ 29033 29038 12832 28722 69640972 29005 _ 29033 69640972\, 68408078\, 67273472 69640972 29005 _ 29033 69640972 29012 84054785; 2: z1(k)←[z1, 1(k),…,zffi,1(k)]⊤ 29050 _ 28721 67273472 29035 84054785 12832 67482370 29050 _ 28721 24891 \, 28721 67273472 29035 84054785 24891 … 24891 29050 _ 28939 _ 29033 24891 28721 67273472 29035 84054785 84267779 574 with zj,1(k)=1 29050 _ 29034 24891 28721 67273472 29035 84054785 12349 28721 , ∀|∈ℳi,∀k∈[αi] 568 69640972 12850 29005 _ 29033 24891 568 29035 12850 67482370 28939 _ 29033 84267779; 3: for each time step t∈[T] 29044 12850 67482370 29012 84267779 do 4: receive action ai,t 29025 _ 29033 24891 29044 from ActSel; 5: for k=1,…,αi 29035 12349 28721 24891 … 24891 28939 _ 29033 do 6: get distribution qt(k)←zt(k)/‖zt(k)‖1 29041 _ 29044 67273472 29035 84054785 12832 29050 _ 29044 67273472 29035 84054785\, 68408078\, 69645069 29050 _ 29044 67273472 29035 84054785 69645069_ 28721 ; 7: draw agent jt(k)∈ℳi 29034 _ 29044 67273472 29035 84054785 12850 29005 _ 29033 from qt(k) 29041 _ 29044 67273472 29035 84054785; 8: receive action ajt(k),t 29025 _ 29034 _ 29044 67273472 29035 84054785 24891 29044 from jt(k) 29034 _ 29044 67273472 29035 84054785; 29: rjt(k),t←VoCf,t(ai,t;ajt(1),t,…,ajt(k),t)− 29042 _ 29034 _ 29044 67273472 29035 84054785 24891 29044 12832 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \,\ 29025 _ 29034 _ 29044 67273472 28721 84054785 24891 29044 24891 … 24891 29025 _ 29034 _ 29044 67273472 29035 84054785 24891 29044 \ 84054785 8704 3 VoCf,t(ai,t;ajt(1),t,…,ajt(k−1),t) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \,\ 29025 _ 29034 _ 29044 67273472 28721 84054785 24891 29044 24891 … 24891 29025 _ 29034 _ 29044 67273472 29035 8704 28721 84054785 24891 29044 \ 84054785 and normalize rjt(k),t 29042 _ 29034 _ 29044 67273472 29035 84054785 24891 29044 to [Γ,1] 674823700 24891 28721 84267779; 10: r^j,t(k)←1−(jt(k)=j)qj,t(k)(1−rjt(k),t) 29042 _ 29034 24891 29044 67273472 29035 84054785 12832 28721 8704 28721 67273472 29034 _ 29044 67273472 29035 84054785\, 12349 \, 29034 84054785 29041 _ 29034 24891 29044 67273472 29035 84054785 67273472 28721 \, 8704 \, 29042 _ 29034 _ 29044 67273472 29035 84054785 24891 29044 84054785, ∀j∈ℳi 568 29034 12850 29005 _ 29033 ; 11: zj,t+1(k)←zj,t(k)exp(ηinr^j,t(k)) 29050 _ 29034 24891 29044 8235 28721 67273472 29035 84054785 12832 29050 _ 29034 24891 \, 29044 67273472 29035 84054785 67273472 28945 _ 29033 29038 \, 29042 _ 29034 24891 29044 67273472 29035 84054785 84054785, ∀j∈ℳi 568 29034 12850 29005 _ 29033 ; 12: end for 13: i,t←jk,tk∈[ffi] 29006 _ 29033 24891 29044 12832 \ 29034 _ 29035 24891 29044 \_ 29035 12850 67482370 28939 _ 29033 84267779; 14: end for Algorithm 3 NeiSel for Agent i 29033 We now present the NeiSel algorithm and its performance guarantees for maximizing VoC. Particularly, we introduce the neighbor-selection problem that NeiSel enables agents to solve in parallel and demonstrate that it aligns with ˜2. Since the suboptimality bound of ActSel in eq.˜8 improves as VoCf,t(ai,t;i,t) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 increases, NeiSel aims to enable each agent i 29033 to choose neighbors by solving the following cardinality-constrained maximization problem: maxi,t⊆ℳi,|i,t|≤ffi∑t=1TVoCf,t(ai,t;i,t), _ 29006 _ 29033 24891 29044 \, 12818 \, 29005 _ 29033 24891 \, 69640972 29006 _ 29033 24891 29044 69640972\, 12820 \, 28939 _ 29033 4944 _ 29044 12349 28721 29012 \; VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 24891 (9) where ai,t 29025 _ 29033 24891 29044 is given by ActSel. This is a submodular maximization problem since we show in Lemma˜1 that VoCf,t(ai,t;i,t) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 is submodular in i,t 29006 _ 29033 24891 29044 . But VoCf,t(ai,t;i,t) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 is computable in hindsight only: aj,tj∈i,t\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 become known only after agent i 29033 has selected and communicated with i,t 29006 _ 29033 24891 29044 . Therefore, eq.˜9 takes the form of cardinality-constrained bandit submodular maximization [50, 29, 47], which is an extension of ˜2 to the multi-agent submodular setting. Solving eq.˜9 using algorithms for ˜2 will lead to exponential-running-time algorithms due to an exponentially large 29014 per eq.˜4 [29]. Therefore, NeiSel instead extends [29, Algorithm 2], which can solve eq.˜9 in the full-information setting, to the bandit setting [47]. Specifically, NeiSel decomposes eq.˜9 to αi 28939 _ 29033 instances of ˜2, and separately solves each of them using Exp3. NeiSel starts by initializing a learning rate ηin 28945 _ 29033 29038 and αi 28939 _ 29033 weight vectors zt(k),∀k∈[αi] 29050 _ 29044 67273472 29035 84054785 24891 568 29035 12850 67482370 28939 _ 29033 84267779, each determining the k 29035 -th selection in i,t 29006 _ 29033 24891 29044 (Algorithm˜3’s lines 1-2). Then, at each t∈[T] 29044 12850 67482370 29012 84267779, it sequentially executes the following steps: 1. Receive action ai,t 29025 _ 29033 24891 29044 by ActSel (lines 3-4); 2. Compute distribution qt(k) 29041 _ 29044 67273472 29035 84054785 using zt(k),∀k∈[αi] 29050 _ 29044 67273472 29035 84054785 24891 568 29035 12850 67482370 28939 _ 29033 84267779 (lines 5-6); 3. Select agent jt(k)∈ℳi 29034 _ 29044 67273472 29035 84054785 12850 29005 _ 29033 as neighbor by sampling from qt(k) 29041 _ 29044 67273472 29035 84054785, and receive its action ajt(k),t,∀k∈[αi] 29025 _ 29034 _ 29044 67273472 29035 84054785 24891 29044 24891 568 29035 12850 67482370 28939 _ 29033 84267779 (lines 7-8); 4. For each k∈[αi] 29035 12850 67482370 28939 _ 29033 84267779, compute reward rjt(k),t 29042 _ 29034 _ 29044 67273472 29035 84054785 24891 29044 associated with each jt(k) 29034 _ 29044 67273472 29035 84054785, estimate reward r~j,t(k) 29042 _ 29034 24891 29044 67273472 29035 84054785 of each j∈ℳi 29034 12850 29005 _ 29033 , and update weight zj,t+1(k) 29050 _ 29034 24891 29044 8235 28721 67273472 29035 84054785 of each j∈ℳi 29034 12850 29005 _ 29033 (lines 9-12). IV Suboptimality Guarantees We show that Anaconda’s approximation performance against the optimal solution to eq.˜1 improves with the sum of all agents’ VoC, and is strictly positive anytime, even before convergence. To this end, we begin with an a priori bound validating that NeiSel indeed improves Anaconda’s performance bound (Section˜IV-A). We then provide an anytime strictly positive a posteriori bound (Section˜IV-B). Combining the first two results, we finally present an asymptotic bound (Section˜IV-C). All proofs appear in Appendix A. IV-A A Priori Bound To present the a priori bound, we first present the following definitions and lemmas that measure the performances of ActSel and NeiSel. We use the following notation: • κI,i≜maxt∈[T]κI,i,t 28948 _ 29001 24891 29033 _ 29044 12850 67482370 29012 84267779 28948 _ 29001 24891 29033 24891 29044 , where κI,i,t 28948 _ 29001 24891 29033 24891 29044 is the curvature of VoCf,t(ai,t;⋅) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 8705 84054785, ∀t∈[T] 568 29044 12850 67482370 29012 84267779. κI,i 28948 _ 29001 24891 29033 is independent of κf 28948 _ 29030 ; • ρ(κ,α)≜κ−1[1−(1−κ/α)ff] 28954 67273472 28948 24891 28939 84054785 28948 8704 28721 67482370 28721 8704 67273472 28721 8704 28948 68408078 28939 84054785 28939 84267779, where κ∈[Γ,1] 28948 12850 674823700 24891 28721 84267779 and α∈ℕ 28939 12850 29006 . Notice that 1≥κ−1[1−(1−κ/α)ff]>ff→∞κ−1(1−e−ˇ)≥ˇ→11−e−1 28721 12821 28948 8704 28721 67482370 28721 8704 67273472 28721 8704 28948 68408078 28939 84054785 28939 84267779 28939 12833 561 12606 28948 8704 28721 67273472 28721 8704 29029 8704 28948 84054785 28948 12833 28721 12821 28721 8704 29029 8704 28721 . The performances of ActSel and NeiSel are measured by the following quantities: Definition 5 (Static Regret of Action Selection). Given agent i 29033 has neighbors i,tt∈[T]\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 over the horizon [T] 67482370 29012 84267779. At each time step t 29044 , suppose agent i 29033 selects an action ai,t 29025 _ 29033 24891 29044 . Then, the static regret of ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 is defined as A−RegT(ai,tt∈[T])≜ 28993 8704 29010 29029 29031 _ 29012 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 maxa∈i∑t=1Tf(a|aj,tj∈i,t)−∑t=1Tf(ai,t|aj,tj∈i,t). _ 29025 12850 29014 _ 29033 4944 _ 29044 12349 28721 29012 29030 67273472 29025 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 8704 4944 _ 29044 12349 28721 29012 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 314 (10) Definition 6 (ρ(κI,i,αi) 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785-Approximate Static Regret of Neighbor Selection). Given agent i 29033 has actions ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 over horizon [T] 67482370 29012 84267779. At each time step t 29044 , suppose agent i 29033 selects a set of neighbors i,t⊆ℳi 29006 _ 29033 24891 29044 12818 29005 _ 29033 , |i,t|≤αi 69640972 29006 _ 29033 24891 29044 69640972 12820 28939 _ 29033 . Then, the ρ(κI,i,αi) 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785-approximate static regret of i,tt∈[T]\ 29006 _ 29033 24891 29044 \_ 29044 \, 12850 \, 67482370 29012 84267779 is defined as N−Regai,tt∈[T]æ(ˇI,i,ffi)(i,tt∈[T]) 29006 8704 29010 29029 29031 _\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 67273472\,\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779\, 84054785 ≜æ(ˇI,i,ffi)maxi,t⊆ℳi,|i,t|≤ffi∑t=1TVoCf,t(ai,t;i,t) 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 _ 29006 _ 29033 24891 29044 12818 29005 _ 29033 24891 69640972 29006 _ 29033 24891 29044 69640972 12820 28939 _ 29033 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 −∑t=1TVoCf,t(ai,t;i,t). 8704 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 314 (11) Definition˜6 evaluates the suboptimality of i,tt∈[T]\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 against the optimal communication neighborhood that would have been selected if VoCf,t(ai,t;⋅) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 8705 84054785 had been known a priori, ∀t∈[T] 568 29044 12850 67482370 29012 84267779. The optimal value in eq.˜11 is discounted by ρ(κI,i,αi) 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 since the problem in eq.˜9 is NP-hard to solve with an approximation factor greater than ρ(κI,i,αi) 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 even when VoCf,t(ai,t;⋅) VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 8705 84054785 is known a priori [7]. Lemma 2 (Suboptimality Guarantee of ActSel). Consider horizon [T] 67482370 29012 84267779. If agent i 29033 has a sequence of neighbors i,tt∈[T]\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779, regardless of how they are selected, then using ActSel, agent i 29033 can choose actions ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 such that A−RegT(ai,tt∈[T])≤O~(|i|T), 28993 8704 29010 29029 29031 _ 29012 67273472\,\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779\, 84054785 12820 29007 67273472 69640972 29014 _ 29033 69640972 29012 84054785 24891 (12) given the learning rate is set as ηia=2log|i|/(|i|T) 28945 _ 29033 29025 12349 28722 69640972 29014 _ 29033 69640972\, 68408078\, 67273472 69640972 29014 _ 29033 69640972 29012 84054785. Lemma 3 (Suboptimality Guarantee of NeiSel). Consider horizon [T] 67482370 29012 84267779. If agent i 29033 has a sequence of actions ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779, regardless of how they are selected, then using NeiSel, agent i 29033 can choose neighbors i,tt∈[T]\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 such that N−Regai,tt∈[T]æ(ˇI,i,ffi)(i,tt∈[T])≤O~(αi|ℳi|T), 29006 8704 29010 29029 29031 _\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 67273472\,\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779\, 84054785 12820 29007 67273472 28939 _ 29033 69640972 29005 _ 29033 69640972 29012 84054785 24891 (13) given the learning rate set as ηin=2log|ℳi|/(|i|T) 28945 _ 29033 29038 12349 28722 69640972 29005 _ 29033 69640972\, 68408078\, 67273472 69640972 29014 _ 29033 69640972 29012 84054785. Now we present the a priori bound of Anaconda. Theorem 1 (A Priori Approximation Performance). Using Anaconda, each agent i 29033 selects actions ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 and communication neighborhoods i,tt∈[T]\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 that guarantee: [f(t)]≥(1−ˇf)f() 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12821 67273472 28721 8704 28948 _ 29030 84054785\, 29030 67273472 28993 29007 29008 29012 84054785 +ˇf(1−ˇf)æ(ˇI,ff¯) 8235 28948 _ 29030 \, 67273472 28721 8704 28948 _ 29030 84054785\, 28954 67273472 28948 _ 29001 24891 28939 84054785 ×∑i∈[VoCf,t(ai,t;i⋆(ai,tt∈[T];ffi,ℳi))] 39.83368pt 8706 4944 _ 29033 12850 29006 28997 67482370 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 8511 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 24635 28939 _ 29033 24891 29005 _ 29033 84054785 84054785 84267779 −O~(||(ff¯2|ℳ¯|+|¯|)/T), 8704 29007 67273472 69640972 29006 69640972 67273472 28939 28722 \, 69640972 29005 69640972\, 8235 \, 69640972 29014 69640972 84054785 68408078 29012 84054785 24891 (14) where κI≜maxi∈κI,i 28948 _ 29001 _ 29033 12850 29006 28948 _ 29001 24891 29033 , α¯≜maxi∈αi 28939 _ 29033 12850 29006 28939 _ 29033 , |¯|≜maxi∈|i| 69640972 29014 69640972 _ 29033 12850 29006 69640972 29014 _ 29033 69640972, |ℳ¯|≜maxi∈|ℳi| 69640972 29005 69640972 _ 29033 12850 29006 69640972 29005 _ 29033 69640972, κf,κI∈[Γ,1] 28948 _ 29030 24891 28948 _ 29001 12850 674823700 24891 28721 84267779, ρ(κI,α¯)∈[1−1/e,1] 28954 67273472 28948 _ 29001 24891 28939 84054785 12850 67482370 28721 8704 28721 68408078 29029 24891 28721 84267779, and i⋆(ai,tt∈[T];αi,ℳi)⊆ℳi 29006 _ 29033 8511 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 24635 28939 _ 29033 24891 29005 _ 29033 84054785 12818 29005 _ 29033 is the optimal communication neighborhood that solves eq.˜9 given ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 subject to αi 28939 _ 29033 . The expectation is due to the algorithm’s internal randomness. Theorem˜1 implies that as T→∞ 29012 12833 561 , the a priori approximation ratio spans the interval between fully centralized and fully decentralized coordination in accordance to VoC, and the spectrum is depicted in red in Fig. 2. In particular, when the network is fully centralized with all agents listening to all others, i.e., i,t≡\i 29006 _ 29033 24891 29044 12817 29006 8814 \ 29033 \, [f(t)]≥11+ˇff()−O~(|||¯|/T), 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12821 28721 28721 8235 28948 _ 29030 \, 29030 67273472 28993 29007 29008 29012 84054785 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 24891 (15) where the guaranteed 1/(1+κf) 28721 68408078 67273472 28721 8235 28948 _ 29030 84054785 bound is near-optimal [7]. When the network is fully decentralized with no agent listening to any others, i.e., i,t≡∅ 29006 _ 29033 24891 29044 12817 571 , [f(t)]≥(1−κf)f()−O~(|||¯|/T), 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12821 67273472 28721 8704 28948 _ 29030 84054785\, 29030 67273472 28993 29007 29008 29012 84054785 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 24891 (16) where 1−κf 28721 8704 28948 _ 29030 is the worst-case bound achieved by Anaconda. Figure 2: Asymptotic approximation bounds of Anaconda. As T→∞ 29012 12833 561 , the bounds provided by Theorems˜1, 2 and 3 are shown with varying ranges of κf 28948 _ 29030 and achieved β 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 β 28940 increases; and the combined bound (green) takes the maximum of the a priori lower bound and the a posteriori bound. IV-B A Posteriori Bound We provide an a posteriori bound for Anaconda that is strictly positive, even for finite T 29012 . Theorem 2 (A Posteriori Approximation Performance). Using Anaconda, each agent i∈ 29033 12850 29006 selects ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 and i,tt∈[T]\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 that guarantee: [f(t)]≥11+fiˇf+O~(|||¯|/T)f(), 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12821 28721 28721 8235 28940 28948 _ 29030 8235 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785\, 29030 67273472 28993 29007 29008 29012 84054785 24891 (17) where β≜[∑i∈f(ai,t|aj,tj∈i,t)][f(t)]∈[Γ,∞) 28940 28997 67482370 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 84267779 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12850 674823700 24891 561 84054785 (18) is computable after Anaconda terminates. The expectation is due to the algorithm’s internal randomness. The bound is depicted in Fig. 2 in orange for varying ranges of β 28940 . Since [f(t)]>Γ 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12606 0, then β<∞ 28940 12604 561 , and Theorem˜2 implies that Anaconda always achieves a strictly positive asymptotic approximation ratio: [f(t)]≥T→∞11+fiˇff()>Γ. 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 29012 12833 561 12821 28721 28721 8235 28940 28948 _ 29030 29030 67273472 28993 29007 29008 29012 84054785 12606 0 314 (19) Moreover, if β=Γ 28940 12349 0, i.e., each agent’s selected action fully overlaps with its neighbors’ selected actions, then Anaconda is asymptotically optimal: [f(t)]≥T→∞f(). 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 29012 12833 561 12821 29030 67273472 28993 29007 29008 29012 84054785 314 (20) Finally, if Γ≤β≤10 12820 28940 12820 28721 , then Anaconda asymptotically outperforms the bound of Sequential Greedy [13]: [f(t)]≥T→∞11+fiˇff()≥11+ˇff(). 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 29012 12833 561 12821 28721 28721 8235 28940 28948 _ 29030 29030 67273472 28993 29007 29008 29012 84054785 12821 28721 28721 8235 28948 _ 29030 29030 67273472 28993 29007 29008 29012 84054785 314 (21) This last scenario is guaranteed to occur when, e.g., there exists an order of the agents such that [i−1]⊆i,t,∀i,∀t 67482370 29033 8704 28721 84267779 12818 29006 _ 29033 24891 29044 24891 568 29033 24891 568 29044 . IV-C Combined Asymptotic Bound Combining Theorems˜1 and 2, we get: Theorem 3 (Asymptotic Approximation Performance). Anaconda asymptotically achieves: [f(t)]f()≥T→∞max(1−κf,11+fiˇf)>Γ, 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 29030 67273472 28993 29007 29008 29012 84054785 29012 12833 561 12821 67273472 28721 8704 28948 _ 29030 24891 28721 28721 8235 28940 28948 _ 29030 84054785 12606 0 24891 (22) where κf∈[Γ,1] 28948 _ 29030 12850 674823700 24891 28721 84267779 and β∈[Γ,∞) 28940 12850 674823700 24891 561 84054785. The bound is depicted in Fig. 2 in green. V Decision Time Analysis We present the convergence time of Anaconda by analyzing its computation and communication complexity, accounting for the delays due to function evaluation and the transmission of messages under realistic communications. • τf 28956 _ 29030 is the time required for one evaluation of f 29030 ; • τc 28956 _ 29027 is the time for agent i 29033 to transmit the information about one action to agent j 29034 , without loss of generality, for all (i→j)∈ℰt,∀t 67273472 29033 12833 29034 84054785 12850 28997 _ 29044 24891 568 29044 . Theorem 4 (Convergence Time). Anaconda converges in O[(τfα¯+τc)(α¯2|ℳ¯|+|¯|)||2/ϵ] 29007 67482370 67273472 28956 _ 29030 \, 28939 \, 8235 \, 28956 _ 29027 \, 84054785\, 67273472 28939 28722 \, 69640972 29005 69640972\, 8235 \, 69640972 29014 69640972 84054785\, 69640972 29006 69640972 28722 \, 68408078\, 28943 84267779 time. In sparse networks, the following corollary holds: Corollary 1 (Convergence Time for Sparse Networks). In sparse networks, where |ℳi|=o(||),∀i∈ 69640972 29005 _ 29033 69640972\, 12349 29039 67273472 69640972 29006 69640972 84054785 24891 568 29033 12850 29006 , Anaconda converges in O[(τfα¯+τc)|¯|||2/ϵ] 29007 67482370\, 67273472 28956 _ 29030 \, 28939 \, 8235 \, 28956 _ 29027 \, 84054785\, 69640972 29014 69640972\, 69640972 29006 69640972 28722 \, 68408078\, 28943 \, 84267779 time. The proof appears in Appendix B. VI Necessity for Network Optimization: Numerical Evaluation in Area Monitoring Figure 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. In this section, we demonstrate that optimizing the network topology, per Anaconda, leads to improved coordination performance compared to heuristics for network design, such as the nearest and random selection that are typically used in controls and robotics [52, 27, 46]. In particular, we compare the proposed NeiSel (Algorithm˜3) with two heuristic strategies, Nearest Neighbors and Random Neighbors, in simulated 2D area-monitoring scenarios. The results show that NeiSel consistently outperforms the benchmarks across different network densities (Fig. 3), and that while nearest-neighbor heuristic is quite misleading in certain structured environments, NeiSel can configure the optimal communication neighborhood (Fig. 4). We defer the description of the former simulations to Appendix V and describe the latter below. In more detail, eight cameras are deployed to monitor four street blocks as shown in Fig. 4. Under αi=1 28939 _ 29033 12349 28721 for all i∈ 29033 12850 29006 , the optimal neighbor for each camera is the one positioned opposite its corresponding street block so as to minimize FOV overlap. The results, shown in Fig. 4 and Table˜I, indicate that NeiSel outperforms the two heuristic baselines by 27.2% 28722 28727 314 28722 \% and 11.5% 28721 28721 314 28725 \% in mean coverage, respectively. We next describe the simulation setup, compared algorithms, and results. (a) ActSel + Nearest neighbors. (b) ActSel + Random neighbors. (c) ActSel + NeiSel (Anaconda). Figure 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. Setup. Environment: The environment is a 11Γ×4Γ 28721 28721 0 8706 28724 0 map with four 2Γ×4Γ 28722 0 8706 28724 0 street blocks to monitor, as in Fig. 4. Agents: Eight cameras are located on the boundaries of street blocks with locations (Γ,2Γ) 672734720 24891 28722 0 84054785, (2Γ,2Γ) 67273472 28722 0 24891 28722 0 84054785, (3Γ,2Γ) 67273472 28723 0 24891 28722 0 84054785, (5Γ,2Γ) 67273472 28725 0 24891 28722 0 84054785, (6Γ,2Γ) 67273472 28726 0 24891 28722 0 84054785, (8Γ,2Γ) 67273472 28728 0 24891 28722 0 84054785, (9Γ,2Γ) 67273472 28729 0 24891 28722 0 84054785, and (11Γ,2Γ) 67273472 28721 28721 0 24891 28722 0 84054785. They all have large enough communication ranges ci 29027 _ 29033 such that ℳi=\i,∀i∈ 29005 _ 29033 12349 29006 8814 \ 29033 \ 24891 568 29033 12850 29006 . Actions: All cameras i∈ 29033 12850 29006 have FOV radius ri=2Γ 29042 _ 29033 12349 28722 0 and AOV θi=π/2 28946 _ 29033 12349 28953 68408078 28722 , with direction ai,t 29025 _ 29033 24891 29044 chosen from the 16 cardinal directions, ∀t 568 29044 . Each camera i 29033 is considered unaware of j,j∈\i 29014 _ 29034 24891 29034 12850 29006 8814 \ 29033 \. Thus, the cameras have to communicate to know about one another’s action information. Communication Network: The emergent time-varying communication network t 28999 _ 29044 can be directed and disconnected. At each decision round t 29044 , each camera i 29033 will first find its coordination neighborhood ℳi≜j‖xj−xi‖≤ci,j∈\i 29005 _ 29033 \ 29034 \_ 69645069 29048 _ 29034 8704 29048 _ 29033 69645069 12820 29027 _ 29033 24891 \, 29034 \, 12850 \, 29006 8814 \ 29033 \, where ci 29027 _ 29033 is i 29033 ’s communication range. Then, it will select communication neighborhood i,t 29006 _ 29033 24891 29044 from ℳi 29005 _ 29033 , following a strategy that will be determined by different compared algorithms. Once i,t 29006 _ 29033 24891 29044 is configured by all i∈ 29033 12850 29006 , then t 28999 _ 29044 is defined. Objective Function: f(ai,ti∈) 29030 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 is the total area of interest covered by the cameras 29006 when they select ai,ti∈\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 as their FOV directions. f 29030 is proved to be submodular [8]. 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. Metric Nearest Neighbors Random Neighbors Ours Mean ± 8710 Std (%) 56.53 ± 8710 4.57 64.47 ± 8710 6.07 71.89 ± 8710 7.36 Min (%) 35.56 (t=1 29044 12349 28721 ) 37.94 (t=113 29044 12349 28721 28721 28723 ) 39.72 (t=169 29044 12349 28721 28726 28729 ) Max (%) 71.09 (t=2484 29044 12349 28722 28724 28728 28724 ) 72.56 (t=895 29044 12349 28728 28729 28725 ) 77.25 (t=619 29044 12349 28726 28721 28729 ) Performance Metrics. We evaluate the achieved coverage of street blocks of the algorithms over 3000 decision rounds. Compared Algorithms. We evaluate the following benchmarks, all selecting one neighbor per camera at each decision round, i.e., αi=1 28939 _ 29033 12349 28721 for all i∈ 29033 12850 29006 : (i) Anaconda: Our algorithm will follow the process described in Section˜I. That is, at each round, the agents will each first sample its action ai,t∈i 29025 _ 29033 24891 29044 12850 29014 _ 29033 per ActSel and neighbors i,t⊆ℳi 29006 _ 29033 24891 29044 12818 29005 _ 29033 per NeiSel. Then, they will each communicate with i,t 29006 _ 29033 24891 29044 and use the received information to update the two bandit algorithms. (i) ActSel + Nearest Neighbors: Action selection follows Anaconda, while each camera i 29033 will always have the same closest agent j∈ℳi 29034 12850 29005 _ 29033 as its neighbor. (i) ActSel + Random Neighbors: Action selection follows Anaconda, while each camera i 29033 will uniformly resample its neighbor from ℳi 29005 _ 29033 at each decision round. Results. We observe that network optimization via NeiSel increases both coverage performance and convergence speed, as shown in Fig. 4. In particular, Anaconda outperforms the two benchmarks in all aspects of mean, minimum, and maximum coverage. It improves the benchmarks by (71.89%/56.53%−1=)27.2% 67273472 28727 28721 314 28728 28729 \% 68408078 28725 28726 314 28725 28723 \% 8704 28721 12349 84054785 28722 28727 314 28722 \% and (71.89%/64.47%−1=)11.5% 67273472 28727 28721 314 28728 28729 \% 68408078 28726 28724 314 28724 28727 \% 8704 28721 12349 84054785 28721 28721 314 28725 \% in the mean coverage, respectively (Table˜I). Moreover, NeiSel converges to the optimal network configuration after ∼ 12824 1000 rounds, and then ActSel also converges to the optimal coverage performance (77.25%) after ∼ 12824 1800 rounds (Fig. 4(c)). In contrast, we do not observe any convergence for the nearest neighbor selection (Fig. 4(a)), and the convergence appears slower for random neighbor selection after ∼ 12824 2400 rounds, with a suboptimal coverage performance (72.56%). The reason why random neighbor selection performs better than nearest neighbor selection is that the latter will always select the same neighbors, thus never choose the optimal configuration. In contrast, random selection can happen to pick the optimum by chance, thus providing better performance. VII Numerical Evaluation in Area Monitoring While much of the distributed optimization literature analyzes computation and communication complexities, it rarely considers how the resulting delays influence the algorithm’s practical optimality over time. In time-critical applications, however, the ability to make rapid decisions is essential, and computation and communication delays directly decide how many coordination rounds can be completed within a finite time horizon. As a result, an algorithm with a lower theoretical bound but higher decision frequency may outperform another with a higher bound but lower frequency, and thus delay-aware evaluation is crucial for revealing such effects. To this end, in the section, we demonstrate the benefits of Anaconda by comparing it with benchmarks under two settings, i.e., with and without communication and computation delays. In particular, Anaconda outperforms because it runs fast under delays. The simulation results, summarized in Figs. 5–7 and Table˜I, highlight the following insights: • Anaconda achieves competitive or improved performances to benchmarks, with and without delays, even though the benchmarks are tasked with easier versions of the problem that Anaconda solves and have higher performance bounds (Sections˜VII-B, VII-C and VII-D). • Anaconda is observed to scale sublinearly in || 69640972 29006 69640972 under delays, in contrast to the benchmark that has almost no benefit in network growth. (Section˜VII-D). The common simulation setup is the same as Section˜VI. We next detail the benchmark algorithms (Section˜VII-A) and comparison results without delays (Section˜VII-B), with delays (Section˜VII-C), and scalability under delays (Section˜VII-D). VII-A Compared Algorithms We compare the following three algorithms. Anaconda with different communication neighborhood sizes We test Anaconda varying the maximum communication neighborhood size |i,t|≤αi 69640972 29006 _ 29033 24891 29044 69640972 12820 28939 _ 29033 , namely Anaconda-αi 28939 _ 29033 n, where αi∈Γ,…,5 28939 _ 29033 12850 \0 24891 … 24891 28725 \. DFS-SG that requires a (strongly) connected network and a known environment [22] We test DFS-SG in terms of its achieved objective value after one round of multi-agent decisions. The offline algorithm is an implementation with communication specifications of SG for submodular maximization, which uses a DFS-based method to distributively determine the next agent over the (strongly) connected communication network. Therefore, the problem solved by DFS-SG is a relaxed version of ˜1 where f 29030 is known and a connected communication network is given. DFS-SG enjoys the same 1/(1+κf) 28721 68408078 67273472 28721 8235 28948 _ 29030 84054785 suboptimality bound as SG [13] and has a worst-case O(τc||3) 29007 67273472 28956 _ 29027 \, 69640972 29006 69640972 28723 84054785 decision time. The proof of decision time appears in Appendix C. DFS-BSG that requires a (strongly) connected network We test DFS-BSG in terms of its achieved objective value and convergence speed across multiple rounds of multi-agent decisions. The bandit algorithm is an implementation with communication specifications of BSG [47] that, similarly to Anaconda, also decomposes multi-agent online decision-making into single-agent problems. But different from Anaconda, per DFS-BSG, (i) each agent i 29033 ’s action selection reward is f(ai,t|aj,tj∈[i−1]) 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 84054785 instead of f(ai,t|aj,tj∈i,t) 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785, ∀t 568 29044 , and (i) computating rewards is enabled by the sequential communication over all agents in a DFS-based order.444In [47], the BSG algorithm uses Exp3⋆-SIX as the single-agent algorithm that provides bounded tracking regret in dynamic environments. In this paper, although we instead consider static regret and adopt Exp3, the sequential communication scheme and decision time of BSG are not altered. The problem solved by DFS-BSG is a relaxed version of ˜1 where a connected communication network is given. DFS-BSG enjoys the same suboptimality bound as Anaconda in the fully centralized case per Theorem˜1, and thus upon convergence, DFS-BSG has the same guarantee as DFS-SG. It requires O[(τf|¯|||2+τc||5)|¯|/ϵ] 29007 67482370 67273472 28956 _ 29030 \, 69640972 29014 69640972\, 69640972 29006 69640972 28722 \, 8235 \, 28956 _ 29027 \, 69640972 29006 69640972 28725 84054785\, 69640972 29014 69640972\, 68408078\, 28943 84267779 time to converge in a directed network. The proofs of suboptimality guarantees and decision time appear in Appendix D. When implementing the algorithms above in each MC trial, we first let each agent i 29033 construct ℳi 29005 _ 29033 within the given communication range ci 29027 _ 29033 . Then, while each agent actively selects neighbors i,t⊆ℳi 29006 _ 29033 24891 29044 12818 29005 _ 29033 with Anaconda, it will directly take i,t≡ℳi,∀t 29006 _ 29033 24891 29044 12817 29005 _ 29033 24891 568 29044 with DFS-SG and DFS-BSG. Although Anaconda can accommodate arbitrary networks, we need to choose a not too small ci 29027 _ 29033 to ensure the resulting network is connected for DFS-SG and DFS-BSG. Figure 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 Γ,…,5\0 24891 … 24891 28725 \, or using DFS-SG or DFS-BSG. From (a) to (d), the communication range ci 29027 _ 29033 for all cameras i∈ 29033 12850 29006 increases from 10 to 16 to 20 to 80, and thus expanding each camera’s coordination neighborhood ℳi 29005 _ 29033 growing from a small locality to the full set 29006 8814 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. VII-B Comparison with No Delays: Coverage vs. Decision Round To demonstrate the benefit of information access to the suboptimality of Anaconda, we evaluate the above algorithms omitting computation and communication delays across four scenarios. (Fig. 5). Each scenario is assessed over 20 MC trials, where DFS-SG is executed for a single decision round and all other algorithms are run for 4000 rounds. Setup. Environment: A static 5Γ×5Γ 28725 0 8706 28725 0 map. Agents: There exist 5Γ 28725 0 cameras. The communication ranges ci∈1Γ,16,3Γ,8Γ 29027 _ 29033 12850 \ 28721 0 24891 28721 28726 24891 28723 0 24891 28728 0\ across the four scenarios. In each MC trial, the location xi 29048 _ 29033 of each camera i∈ 29033 12850 29006 is uniformly sampled in [Γ,5Γ]2 674823700 24891 28725 0 84267779 28722 . Actions: Direction ai,t 29025 _ 29033 24891 29044 is chosen from the 16 cardinal directions, ∀t 568 29044 , with FOV radius ri=8 29042 _ 29033 12349 28728 and AOV θi=π/3 28946 _ 29033 12349 28953 68408078 28723 . Results. The simulation results are presented in Fig. 5, where we observe a trade-off of Anaconda between centralization and decentralization, where increasing αi 28939 _ 29033 or ci 29027 _ 29033 generally improves coverage after convergence but at the cost of more decision rounds. Both parameters follow the principle of diminishing marginal returns due to the submodularity of VoC: while larger αi 28939 _ 29033 and ci 29027 _ 29033 values enhance the agents’ information access, the gains eventually become incremental. Furthermore, larger ci 29027 _ 29033 values significantly increase the number of decision rounds required to converge, meaning that highly centralized configurations may underperform compared to the benchmarks in shorter time horizons. Moreover, Anaconda consistently achieves improved asymptotic coverage over these benchmarks as long as αi 28939 _ 29033 or ci 29027 _ 29033 are not too small, suggesting that intermediate parameter values, such as ci=16 29027 _ 29033 12349 28721 28726 , offer the most effective balance between real-time convergence and long-term performance. We conjecture that Anaconda ’s improved performance arises from richer information mixing enabled by the time-varying communication neighborhoods, as opposed to the benchmarks’ sequential information passing. (a) τf=.Γ1 28956 _ 29030 12349 314 0 28721 , τc=.Γ3 28956 _ 29027 12349 314 0 28723 . (b) τf=.Γ3 28956 _ 29030 12349 314 0 28723 , τc=.Γ3 28956 _ 29027 12349 314 0 28723 . (c) τf=.Γ9 28956 _ 29030 12349 314 0 28729 , τc=.Γ3 28956 _ 29027 12349 314 0 28723 . Figure 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 Γ,…,5\0 24891 … 24891 28725 \, or using DFS-SG or DFS-BSG. From (a) to (b) to (c), the time τf 28956 _ 29030 for one function evaluation increases relative to the delay τc 28956 _ 29027 for transmitting one action through a communication link, with the ratio τf/τc 28956 _ 29030 68408078 28956 _ 29027 taking values 1/3 28721 68408078 28723 , 1 28721 , and 3 28723 . DFS-SG is executed for a single decision round, whereas the other algorithms are run for a fixed duration of 3ΓΓ 28723 00 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. VII-C Comparison with Delays: Coverage vs. Actual Time We compare Anaconda with DFS-SG and DFS-BSG in 20 MC trials under three delay configurations (τf,τc)∈(.Γ1s,.Γ3s),(.Γ3s,.Γ3s),(.Γ9s,.Γ3s) 67273472 28956 _ 29030 24891 28956 _ 29027 84054785 12850 \ 67273472 314 0 28721 24891 314 0 28723 84054785 24891 67273472 314 0 28723 24891 314 0 28723 84054785 24891 67273472 314 0 28729 24891 314 0 28723 84054785\, capturing different computation and communication capabilities. Each trial is carried out over a fixed 3ΓΓ 28723 00s time horizon. Setup. The setup is identical to that in Fig. 5(b), with the communication range ci=16 29027 _ 29033 12349 28721 28726 for all cameras i∈ 29033 12850 29006 . Results. The simulation results are presented in Fig. 6 and Table˜I where we observe the following for Anaconda: Anaconda demonstrates a better performance than DFS-BSG and can outperform DFS-SG after convergence. The reason is that Anaconda decides actions much faster than DFS-BSG in large networks, which means much more decision rounds in a fixed time horizon. Increasing the neighborhood size αi 28939 _ 29033 presents a trade-off for Anaconda: although larger neighborhoods theoretically offer higher asymptotic coverage, they also increase computation time per round, resulting in fewer decision cycles within a fixed time horizon. For example, in Fig. 6(a)–(c), the best-performing communication neighborhood sizes within the 300s window are αi=5,3, 28939 _ 29033 12349 28725 24891 28723 24891 and 1 28721 , respectively, rather than always 5 28725 (Table˜I). This “no free neighbor” dynamic, characterized by a cubic growth in convergence time relative to αi 28939 _ 29033 , means that smaller neighborhood sizes can yield better performance in a fixed horizon. VII-D Scalability We finally compare the real-time coverage performance of Anaconda-5n and DFS-BSG over 20 MC trials as the network size scales across five scenarios with varying numbers of cameras and map sizes. Each trial is executed over a fixed time horizon of 3ΓΓ 28723 00s with (τf,τc)=(Γ.Γ1s,Γ.Γ1s) 67273472 28956 _ 29030 24891 28956 _ 29027 84054785 12349 672734720 314 0 28721 24891 0 314 0 28721 84054785. TABLE I: Comparison of average coverage performance (%) within 3ΓΓ 28723 00s across three scenarios with different delay configurations (Fig. 6). The highest value in each scenario is highlighted in bold. Algorithm Coverage (%) τf=.Γ1s 28956 _ 29030 12349 314 0 28721 29043 , τc=.Γ3s 28956 _ 29027 12349 314 0 28723 29043 τf=.Γ3s 28956 _ 29030 12349 314 0 28723 29043 , τc=.Γ3s 28956 _ 29027 12349 314 0 28723 29043 τf=.Γ9s 28956 _ 29030 12349 314 0 28729 29043 , τc=.Γ3s 28956 _ 29027 12349 314 0 28723 29043 DFS-BSG 42.19 ± 8710 1.83 41.96 ± 8710 1.98 42.30 ± 8710 2.20 Anaconda-0n 47.33 ± 8710 1.84 46.52 ± 8710 1.92 46.78 ± 8710 1.77 Anaconda-1n 58.27 ± 8710 1.22 56.13 ± 8710 1.77 52.17 ± 8710 1.68 Anaconda-2n 58.75 ± 8710 1.18 56.75 ± 8710 1.28 51.68 ± 8710 1.90 Anaconda-3n 59.05 ± 8710 0.89 57.10 ± 8710 1.04 51.73 ± 8710 0.91 Anaconda-4n 59.08 ± 8710 0.82 56.20 ± 8710 1.57 50.12 ± 8710 0.93 Anaconda-5n 59.12 ± 8710 1.01 55.72 ± 8710 1.32 49.99 ± 8710 1.73 Setup. The five scenarios contain 1Γ,2Γ,3Γ,4Γ,5Γ\ 28721 0 24891 28722 0 24891 28723 0 24891 28724 0 24891 28725 0\ cameras deployed in maps of sizes 232,322,392,452,5Γ2\ 28722 28723 28722 24891 28723 28722 28722 24891 28723 28729 28722 24891 28724 28725 28722 24891 28725 0 28722 \, respectively. These configurations maintain an approximately constant camera density, with each camera covering roughly 5Γ 28725 0 square units on average. Across all scenarios, the communication range is fixed at ci=16 29027 _ 29033 12349 28721 28726 for all cameras i∈ 29033 12850 29006 . Results. Anaconda scales despite imperfect communication; DFS-BSG does not. Per Fig. 7, when the network size increases from 10 to 50 agents, Anaconda consistently executes 2142 rounds, owing to its fixed per-round computation and communication load (Proposition˜5), and the convergence time grows from 100s to 200s, which is a sublinear growth in || 69640972 29006 69640972. In contrast, the number of rounds completed by DFS-BSG declines from 493 to just 15, because each round requires sequential communication across the entire network. Figure 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 23×23 28722 28723 8706 28722 28723 to 5Γ×5Γ 28725 0 8706 28725 0 as the network size ranges from 1Γ 28721 0 to 5Γ 28725 0. Results are averaged over 20 Monte Carlo trials, each with a fixed 3ΓΓ 28723 00s time window under delays (τf,τc)=(.Γ1s,.Γ1s) 67273472 28956 _ 29030 24891 28956 _ 29027 84054785 12349 67273472 314 0 28721 24891 314 0 28721 84054785. VIII Conclusion We presented Anaconda, a scalable framework for distributed submodular coordination in multi-agent systems operating in unknown environments under realistic communication constraints. Anaconda achieves scalability while maintaining near-optimal action coordination by intelligently limiting communication, regardless of global connectivity. We introduced a novel metric, VoC, that quantifies the benefit of information access for coordination. By optimizing VoC, the framework enables intelligent information limitation through communication neighborhood design. The suboptimality guarantees showed that Anaconda’s coordination performance improves with the sum of all agents’ VoC, and is anytime non-trivial even prior to convergence. Extensive simulations in multi-camera area monitoring against state-of-the-art benchmarks supported the theoretical analysis and illustrated Anaconda’s benefit in coordination performance, neighborhood design, and scalability, together with a fundamental trade-off between coordination optimality and convergence speed under realistic communication latency. Future work. While Anaconda demonstrates improvement in decision time compared to benchmarks for unknown environments, for mobile-robot applications, we will work to accelerate it to O(||) 29007 67273472 69640972 29006 69640972 84054785 decision time, leveraging the tools in [33]. Moreover, while the coordination neighborhood ℳi 29005 _ 29033 is currently considered static, it can be dynamic for mobile robots. To this end, we will also handle dynamic coordination neighborhoods, i.e., ℳi,t 29005 _ 29033 24891 29044 , with guaranteed performances. References [1] N. Atanasov, J. Le Ny, K. Daniilidis, and G. J. Pappas (2015) Decentralized active information acquisition: Theory and application to multi-robot SLAM. In IEEE Inter. Conf. Rob. Auto. (ICRA), p. 4775–4782. Cited by: §I, §I, §I, §I, §I, §I. [2] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire (2002) The nonstochastic multiarmed bandit problem. SIAM Journal on Computing 32 (1), p. 48–77. Cited by: Appendix A, Appendix A, Appendix D, §I-A. [3] M. Bianchi and S. Grammatico (2024) The END: Estimation network design for games under partial-decision information. IEEE Transactions on Control of Network Systems (TCNS) 11 (4), p. 2200–2212. Cited by: §I. [4] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40 (6), p. 1740–1766. Cited by: §I. [5] L. Chen, H. Hassani, and A. Karbasi (2018) Online continuous submodular maximization. In International Conference on Artificial Intelligence and Statistics (AISTATS), p. 1896–1905. Cited by: §I, §I. [6] L. Chen, M. Zhang, H. Hassani, and A. Karbasi (2020) Black box submodular maximization: discrete and continuous settings. In Inter. Conf. Arti. Intel. Stats. (AISTATS), p. 1058–1070. Cited by: §I, §I. [7] M. Conforti and G. Cornuéjols (1984) Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete Applied Mathematics 7 (3), p. 251–274. Cited by: §IV-A, §IV-A, Definition 4. [8] M. Corah and N. Michael (2018) Distributed submodular maximization on partition matroids for planning on large sensor networks. In IEEE Conference on Decision and Control (CDC), p. 6792–6799. Cited by: Appendix E, §I, §I, §I, §I, §I, §VI. [9] Y. Crama, P. L. Hammer, and R. Holzman (1989) A characterization of a cone of pseudo-boolean functions via supermodularity-type inequalities. In Quantitative Methoden in den Wirtschaftswissenschaften, p. 53–55. Cited by: Definition 2. [10] Digi International (2025)XBee 3 Zigbee 3 RF Module Specifications(Website) Note: Accessed: Dec. 2025 External Links: Link Cited by: §I. [11] B. Du, K. Qian, C. Claudel, and D. Sun (2022) Jacobi-style iteration for distributed submodular maximization. IEEE Transactions on Automatic Control (TAC) 67 (9), p. 4687–4702. Cited by: §I, footnote 3. [12] U. Feige (1998) A threshold of ln(n) 29036 29038 67273472 29038 84054785 for approximating set cover. Journal of the ACM (JACM) 45 (4), p. 634–652. Cited by: §I. [13] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey (1978) An analysis of approximations for maximizing submodular set functions–I. In Polyhedral combinatorics, p. 73–87. Cited by: §I, §I, §I-B, §IV-B, §VII-A, Definition 1. [14] S. Foldes and P. L. Hammer (2005) Submodularity, supermodularity, and higher-order monotonicities of pseudo-boolean functions. Mathematics of Operations Research 30 (2), p. 453–461. Cited by: Definition 2. [15] B. Gharesifard and S. L. Smith (2017) Distributed submodular maximization with limited information. IEEE Transactions on Control of Network Systems (TCNS) 5 (4), p. 1635–1645. Cited by: §I, §I, §I, §I. [16] D. Golovin, A. Krause, and M. Streeter (2014) Online submodular maximization under a matroid constraint with application to learning assignments. arXiv preprint:1407.1082. Cited by: §I, §I. [17] D. Grimsman, M. S. Ali, J. P. Hespanha, and J. R. Marden (2019) The impact of information in distributed submodular maximization. IEEE Trans. Ctrl. Netw. Sys. (TCNS) 6 (4), p. 1334–1343. Cited by: §I, §I, §I, §I, §I. [18] J. Hu, K. H. Johansson, and A. I. Rikos (2025) Distributed quantized average consensus in open multi-agent systems with dynamic communication links. arXiv preprint:2508.05895. Cited by: §I. [19] T. F. Internet (2025)WiFi 6 vs wifi 6e: unlocking faster, more reliable connectivity(Website) Note: Accessed: Dec. 2025 External Links: Link Cited by: §I. [20] A. Jadbabaie, J. Lin, and A. Morse (2003) Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control (TAC) 48 (6), p. 988–1001. Cited by: §I. [21] Y. Kantaros, M. Guo, and M. M. Zavlanos (2019) Temporal logic task planning and intermittent connectivity control of mobile robot networks. IEEE Transactions on Automatic Control (TAC) 64 (10), p. 4105–4120. Cited by: §I. [22] R. Konda, D. Grimsman, and J. R. Marden (2022) Execution order matters in greedy algorithms with limited information. In American Control Conference (ACC), p. 1305–1310. Cited by: 2nd item, Appendix C, §I, §I, §I, §VII-A. [23] A. Krause and D. Golovin (2012) Submodular function maximization. Tractability: Practical Approaches to Hard Problems 3. Cited by: §I. [24] A. Krause, A. Singh, and C. Guestrin (2008) Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. Jour. Mach. Learn. Res. (JMLR) 9, p. 235–284. Cited by: §I, §I. [25] T. Lattimore and C. Szepesvári (2020) Bandit algorithms. Cambridge University Press. Cited by: §I, §I, §I, §I-A, §I-A, Problem 2. [26] J. Liu, L. Zhou, P. Tokekar, and R. K. Williams (2021) Distributed resilient submodular action selection in adversarial environments. IEEE Robotics and Automation Letters (RAL) 6 (3), p. 5832–5839. Cited by: §I, §I, §I, §I. [27] X. Liu, J. Lei, A. Prabhu, Y. Tao, I. Spasojevic, P. Chaudhari, N. Atanasov, and V. Kumar (2025) SlideSLAM: Sparse, lightweight, decentralized metric-semantic slam for multirobot navigation. IEEE Transactions on Robotics (TRO) 41, p. 6529–6548. Cited by: §I, §VI. [28] J. R. Marden (2017) The role of information in distributed resource allocation. IEEE Transactions on Control of Network Systems (TCNS) 4 (3), p. 654–664. Cited by: §I, §I, §I. [29] T. Matsuoka, S. Ito, and N. Ohsaka (2021) Tracking regret bounds for online submodular optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), p. 3421–3429. Cited by: Appendix A, §I-C, §I-C. [30] A. Mokhtari, H. Hassani, and A. Karbasi (2018) Decentralized submodular maximization: bridging discrete and continuous settings. In International Conference on Machine Learning (ICML), p. 3616–3625. Cited by: §I, §I. [31] A. Nedic and A. Ozdaglar (2009) Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control (TAC) 54 (1), p. 48–61. Cited by: §I. [32] G. Neu (2015) Explore no more: improved high-probability regret bounds for non-stochastic bandits. Adv. Neu. Info. Proc. Sys. 28. Cited by: §I-A. [33] A. Rakhlin and K. Sridharan (2013) Online learning with predictable sequences. In Conference on Learning Theory (COLT), p. 993–1019. Cited by: §VIII. [34] N. Rezazadeh and S. S. Kia (2023) Distributed strategy selection: a submodular set function maximization approach. Automatica 153, p. 111000. Cited by: §I, §I, §I, §I, footnote 3. [35] A. I. Rikos, W. Jiang, T. Charalambous, and K. H. Johansson (2023) Asynchronous distributed optimization via admm with efficient communication. In IEEE Conference on Decision and Control (CDC), p. 7002–7008. Cited by: §I. [36] A. Robey, A. Adibi, B. Schlotfeldt, H. Hassani, and G. J. Pappas (2021) Optimal algorithms for submodular maximization with distributed constraints. In Learn. for Dyn. & Cont. (L4DC), p. 150–162. Cited by: §I, §I, §I, §I, §I, footnote 3. [37] B. Schlotfeldt, V. Tzoumas, and G. J. Pappas (2021) Resilient active information acquisition with teams of robots. IEEE Transactions on Robotics (TRO) 38 (1), p. 244–261. Cited by: §I, §I, §I, §I. [38] Y. Seldin and A. Slivkins (2014) One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning (ICML), p. 1287–1295. Cited by: §I-A. [39] Silvus Technologies (2025)StreamCaster Lite 5200 (SL5200) MANET Radio Specifications(Website) Note: Accessed: Dec. 2025 External Links: Link Cited by: §I. [40] A. Singh, A. Krause, C. Guestrin, and W. J. Kaiser (2009) Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research (JAIR) 34, p. 707–755. Cited by: §I, §I. [41] M. Streeter, D. Golovin, and A. Krause (2009) Online learning of assignments. Adv. Neu. Info. Proc. Sys. (NeurIPS) 22. Cited by: §I, §I. [42] M. Streeter and D. Golovin (2008) An online algorithm for maximizing submodular functions. Adv. Neu. Inf. Proc. Sys. 21. Cited by: §I, §I. [43] D. Suehiro, K. Hatano, S. Kijima, E. Takimoto, and K. Nagano (2012) Online prediction under submodular constraints. In International Conf. on Algorithmic Learning Theory (ALT), p. 260–274. Cited by: §I, §I. [44] P. Tokekar, V. Isler, and A. Franchi (2014) Multi-target visual tracking with aerial robots. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 3067–3072. Cited by: §I, §I. [45] V. Tzoumas, K. Gatsis, A. Jadbabaie, and G. J. Pappas (2017) Resilient monotone submodular function maximization. In IEEE Conference on Decision and Control (CDC), p. 1362–1367. Cited by: Appendix A. [46] Z. Xu, S. S. Garimella, and V. Tzoumas (2025) Communication- and computation-efficient distributed submodular optimization in robot mesh networks. IEEE Transactions on Robotics (TRO). Cited by: §I, §I, §I, §I, §I, §I, §I, §I, §I, §I, §I-B, §VI, footnote 3. [47] Z. Xu, X. Lin, and V. Tzoumas (2023) Bandit submodular maximization for multi-robot coordination in unpredictable and partially observable environments. In Robotics: Science and Systems (RSS), Cited by: Appendix D, §I, §I, §I, §I, §I, §I-C, §I-C, §VII-A, footnote 4. [48] Z. Xu and V. Tzoumas (2024) Performance-aware self-configurable multi-agent networks: a distributed submodular approach for simultaneous coordination and network design. In IEEE Conference on Decision and Control (CDC), p. 5393–5400. Cited by: §I, §I, §I-A. [49] Z. Xu, H. Zhou, and V. Tzoumas (2023) Online submodular coordination with bounded tracking regret: theory, algorithm, and applications to multi-robot coordination. IEEE Robotics and Automation Letters (RAL) 8 (4), p. 2261–2268. Cited by: §I, §I, §I, §I. [50] M. Zhang, L. Chen, H. Hassani, and A. Karbasi (2019) Online continuous submodular maximization: from full-information to bandit feedback. Adv. Neu. Info. Proc. Sys. (NeurIPS) 32. Cited by: §I, §I, §I-C. [51] Q. Zhang, Z. Wan, Y. Yang, L. Shen, and D. Tao (2025) Near-optimal online learning for multi-agent submodular coordination: tight approximation and communication efficiency. arXiv preprint:2502.05028. Cited by: §I, §I. [52] B. Zhou, H. Xu, and S. Shen (2023) Racer: rapid collaborative exploration with a decentralized multi-uav system. IEEE Transactions on Robotics (TRO) 39 (3), p. 1816–1835. Cited by: §I, §VI. [53] J. Zimmert and Y. Seldin (2021) Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research (JMLR) 22 (28), p. 1–49. Cited by: §I-A. Appendix A Suboptimality Guarantees of Anaconda We will first prove Lemmas˜1, 2 and 3, then Proposition˜1 and Theorems˜1, 2 and 3. Proof of Lemma˜1. Consider VoCf,t(a;)=f(a)−f(a|ajj∈) VoC_ 29030 24891 29044 67273472 29025 24635 \, 29002 84054785 12349 29030 67273472 29025 84054785 8704 29030 67273472 29025 \, 69640972\,\ 29025 _ 29034 \_ 29034 \, 12850 \, 29002 84054785, where ⊆ℳi⊆\i 29002 12818 29005 _ 29033 12818 29006 8814 \ 29033 \, a∈i 29025 12850 29014 _ 29033 is fixed, and f:2↦→ℝ 29030 24634 28722 29014 _ 29006 567 545 29010 is non-decreasing and 2nd-order submodular. Also, with a slight abuse of notation, denote f(a|ajj∈) 29030 67273472 29025 \, 69640972\,\ 29025 _ 29034 \_ 29034 \, 12850 \, 29002 84054785 by f(a|) 29030 67273472 29025 \, 69640972\, 29002 84054785. To prove the monotonicity of VoCf,t(a;⋅) VoC_ 29030 24891 29044 67273472 29025 24635 \, 8705 84054785, consider 1,2⊆ℳi 28993 _ 28721 24891 28993 _ 28722 12818 29005 _ 29033 that are disjoint. Then, VoCf,t(a;1∪2)−VoCf,t(a;1)=−f(a|1∪2)+f(a|1)≥Γ VoC_ 29030 24891 29044 67273472 29025 24635 \, 28993 _ 28721 8795 28993 _ 28722 84054785 8704 VoC_ 29030 24891 29044 67273472 29025 24635 \, 28993 _ 28721 84054785 12349 8704 29030 67273472 29025 \, 69640972\, 28993 _ 28721 8795 28993 _ 28722 84054785 8235 29030 67273472 29025 \, 69640972\, 28993 _ 28721 84054785 12821 0 since f 29030 is submodular. Thus, VoCf,t(a;⋅) VoC_ 29030 24891 29044 67273472 29025 24635 \, 8705 84054785 is non-decreasing. To prove the submodularity of VoCf,t(a;⋅) VoC_ 29030 24891 29044 67273472 29025 24635 \, 8705 84054785, consider ,ℬ1,ℬ2⊆ 28993 24891 28994 _ 28721 24891 28994 _ 28722 12818 29014 , where ℬ1 28994 _ 28721 and ℬ2 28994 _ 28722 are disjoint, then: VoCf,t(a;|ℬ1)−VoCf,t(a;|ℬ1∪ℬ2) -4.2679pt VoC_ 29030 24891 29044 67273472 29025 24635 \, 28993 \, 69640972\, 28994 _ 28721 84054785 8704 VoC_ 29030 24891 29044 67273472 29025 24635 \, 28993 \, 69640972\, 28994 _ 28721 8795 28994 _ 28722 84054785 =VoCf,t(a;∪ℬ1)−VoCf,t(a;ℬ1) -5.69054pt 12349 VoC_ 29030 24891 29044 67273472 29025 24635 \, 28993 8795 28994 _ 28721 84054785 8704 VoC_ 29030 24891 29044 67273472 29025 24635 \, 28994 _ 28721 84054785 −VoCf,t(a;∪ℬ1∪ℬ2)+VoCf,t(a;ℬ1∪ℬ2) -5.69054pt 42.67912pt 8704 VoC_ 29030 24891 29044 67273472 29025 24635 \, 28993 8795 28994 _ 28721 8795 28994 _ 28722 84054785 8235 VoC_ 29030 24891 29044 67273472 29025 24635 \, 28994 _ 28721 8795 28994 _ 28722 84054785 =−f(a|∪ℬ1)+f(a|ℬ1) -5.69054pt 12349 8704 29030 67273472 29025 \, 69640972\, 28993 8795 28994 _ 28721 84054785 8235 29030 67273472 29025 \, 69640972\, 28994 _ 28721 84054785 +f(a|∪ℬ1∪ℬ2)−f(a|ℬ1∪ℬ2)≥Γ, -5.69054pt 42.67912pt 8235 29030 67273472 29025 \, 69640972\, 28993 8795 28994 _ 28721 8795 28994 _ 28722 84054785 8704 29030 67273472 29025 \, 69640972\, 28994 _ 28721 8795 28994 _ 28722 84054785 12821 0 24891 (23) where the inequality holds since f 29030 is 2nd-order submodular (Definition˜2). Therefore, VoCf,t(a;⋅) VoC_ 29030 24891 29044 67273472 29025 24635 \, 8705 84054785 is submodular. ∎ Proof of Lemma˜2. According to [2, Theorem 3.1], we have A−RegT(ai,tt∈[T])≤2T|i|log|i| 28993 8704 29010 29029 29031 _ 29012 67273472\,\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779\, 84054785 12820 28722 \, 29012 \, 69640972 29014 _ 29033 69640972\, 69640972 29014 _ 29033 69640972. ∎ Proof of Lemma˜3. Given Definition˜6, we have N−Regai,tt∈[T]æ(ˇI,i,ffi)(i,tt∈[T]) 29006 8704 29010 29029 29031 _\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 67273472\,\ 29006 _ 29033 24891 29044 \_ 29044 \, 12850 \, 67482370 29012 84267779\, 84054785 =æ(ˇI,i,ffi)maxi,t⊆ℳi,|i,t|≤ffi∑t=1TVoCf,t(ai,t;i,t) 12349 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 _ 29006 _ 29033 24891 29044 12818 29005 _ 29033 24891 69640972 29006 _ 29033 24891 29044 69640972 12820 28939 _ 29033 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 −∑t=1TVoCf,t(ai,t;i,t) 8704 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 ≤æ(ˇI,i,ffi)∑t=1T(−ffirjk,t,t+∑k=1ffirjk,t,t) 12820 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 4944 _ 29044 12349 28721 29012 67273472 8704 28939 _ 29033 \, 29042 _ 29034 _ 29035 24891 29044 24891 29044 8235 4944 _ 29035 12349 28721 28939 _ 29033 29042 _ 29034 _ 29035 24891 29044 29007 29008 29012 24891 29044 84054785 (24) =æ(ˇI,i,ffi)∑k=1ffi[∑t=1T(rjk,t,t−rjk,t,t⊤qk,t)] 12349 28954 67273472 28948 _ 29001 24891 29033 24891 28939 _ 29033 84054785 4944 _ 29035 12349 28721 28939 _ 29033 28997 67482370 4944 _ 29044 12349 28721 29012 67273472 29042 _ 29034 _ 29035 24891 29044 29007 29008 29012 24891 29044 8704 29042 _ 29034 _ 29035 24891 29044 24891 29044 574 \, 29041 _ 29035 24891 29044 84054785 84267779 (25) ≤O~(ffi|ℳi|T), 12820 29007 67273472 28939 _ 29033 69640972 29005 _ 29033 69640972 29012 84054785 24891 (26) where eq.˜24 follows from [29, Theorem 3], eq.˜25 follows from the linearity of expectation, and eq.˜26 follows by applying [2, Theorem 3.1]. ∎ Proofs of Proposition˜1 and Theorem˜1. We have: ∑t=1Tf() 4944 _ 29044 12349 28721 29012 29030 67273472 28993 29007 29008 29012 84054785 =∑t=1Tf(∪t)−∑t=1T∑i∈f(ai,t|∪aj,tj∈[i−1]) 12349 4944 _ 29044 12349 28721 29012 29030 67273472 28993 29007 29008 29012 8795 28993 _ 29044 84054785 8704 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\, 28993 29007 29008 29012 8795 \ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 84054785 (27) ≤∑t=1Tf(t)+∑t=1T∑i∈f(ai|t) 12820 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 8235 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 29007 29008 29012 \, 69640972\, 28993 _ 29044 84054785 −(1−ˇf)∑t=1T∑i∈f(ai,t|aj,tj∈i,t) 8704 67273472 28721 8704 28948 _ 29030 84054785 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 (28) ≤∑t=1Tf(t)+ˇf∑t=1T∑i∈f(ai,t|aj,tj∈i,t) 12820 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 +∑i∈∑t=1T[f(ai|aj,tj∈i,t)−f(ai,t|aj,tj∈i,t)] 8235 4944 _ 29033 12850 29006 4944 _ 29044 12349 28721 29012 67482370 29030 67273472 29025 _ 29033 29007 29008 29012 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 8704 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 84267779 (29) ≤∑t=1Tf(t)+ˇf∑t=1T∑i∈f(ai,t|aj,tj∈i,t) 12820 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 +∑i∈A−RegT(ai,tt∈[T]) 8235 4944 _ 29033 12850 29006 28993 8704 29010 29029 29031 _ 29012 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 (30) =∑t=1Tf(t)−ˇf∑i∈∑t=1TVoCf,t(ai,t;i,t) 12349 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 8704 28948 _ 29030 4944 _ 29033 12850 29006 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 24891 29044 84054785 +ˇf∑t=1T∑i∈f(ai,t)+∑i∈A−RegT(ai,tt∈[T]) 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 84054785 8235 4944 _ 29033 12850 29006 28993 8704 29010 29029 29031 _ 29012 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 (31) ≤∑t=1Tf(t)+ˇf1−ˇf∑t=1T∑i∈f(ai,t|aj,tj∈[i−1]) 12820 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 8235 28948 _ 29030 28721 8704 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 84054785 −ˇfæ(ˇI,ff¯)∑i∈∑t=1TVoCf,t(ai,t;i⋆(ai,tt∈[T];ffi,ℳi)) 8704 28948 _ 29030 \, 28954 67273472 28948 _ 29001 24891 28939 84054785 4944 _ 29033 12850 29006 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 8511 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 24635 28939 _ 29033 24891 29005 _ 29033 84054785 84054785 +ˇf∑i∈N−Regai,tt∈[T]æ(ˇI,ff¯)(i,tt∈[T]) 8235 28948 _ 29030 4944 _ 29033 12850 29006 29006 8704 29010 29029 29031 _\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 28954 67273472 28948 _ 29001 24891 28939 84054785 67273472\ 29006 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 +∑i∈A−RegT(ai,tt∈[T]) 8235 4944 _ 29033 12850 29006 28993 8704 29010 29029 29031 _ 29012 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 (32) ≤∑t=1Tf(t)+ˇf1−ˇf∑t=1Tf(t) 12820 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 8235 28948 _ 29030 28721 8704 28948 _ 29030 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 −ˇfæ(ˇI,ff¯)∑i∈∑t=1TVoCf,t(ai,t;i⋆(ai,tt∈[T];ffi,ℳi)) 8704 28948 _ 29030 \, 28954 67273472 28948 _ 29001 24891 28939 84054785 4944 _ 29033 12850 29006 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 8511 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 24635 28939 _ 29033 24891 29005 _ 29033 84054785 84054785 +O~(|||¯|T)+O~(||ff¯|ℳ¯|T), 8235 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 29012 84054785 8235 29007 67273472 69640972 29006 69640972 28939 69640972 29005 69640972 29012 84054785 24891 (33) where eq.˜27 holds by telescoping the sum, eq.˜28 holds since f 29030 is submodular and since 1−κf≤f(ai,t|aj,tj∈\i)f(ai,t)≤f(ai,t|∪aj,tj∈[i−1])f(ai,t|aj,tj∈i,t) 28721 8704 28948 _ 29030 12820 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 8814 \ 29033 \ 84054785 29030 67273472 29025 _ 29033 24891 29044 84054785 12820 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\, 28993 29007 29008 29012 8795 \ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 84054785 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 per Definition˜4, eq.˜29 holds from submodularity, eq.˜30 holds from Definition˜5; eq.˜31 holds from Definition˜3, eq.˜32 holds from Definition˜6, and eq.˜33 holds from Lemmas˜2 and 3. Simplifying eq.˜33, we have f()=1T∑t=1Tf() 29030 67273472 28993 29007 29008 29012 84054785 12349 28721 29012 4944 _ 29044 12349 28721 29012 29030 67273472 28993 29007 29008 29012 84054785 ≤11−ˇf[f(t)] 12820 28721 28721 8704 28948 _ 29030 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 −ˇfæ(ˇI,ff¯)∑i∈∑t=1TVoCf,t(ai,t;i⋆(ai,tt∈[T];ffi,ℳi)) 8704 28948 _ 29030 \, 28954 67273472 28948 _ 29001 24891 28939 84054785 4944 _ 29033 12850 29006 4944 _ 29044 12349 28721 29012 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 8511 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 24635 28939 _ 29033 24891 29005 _ 29033 84054785 84054785 +O~(||(ff¯2|ℳ¯|+|¯|)/T). 8235 29007 67273472 69640972 29006 69640972 67273472 28939 28722 \, 69640972 29005 69640972\, 8235 \, 69640972 29014 69640972 84054785 68408078 29012 84054785 314 (34) Therefore, [f(t)]≥(1−ˇf)f() 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12821 67273472 28721 8704 28948 _ 29030 84054785\, 29030 67273472 28993 29007 29008 29012 84054785 +ˇf(1−ˇf)æ(ˇI,ff¯) 8235 28948 _ 29030 \, 67273472 28721 8704 28948 _ 29030 84054785\, 28954 67273472 28948 _ 29001 24891 28939 84054785 ×∑i∈[VoCf,t(ai,t;i⋆(ai,tt∈[T];ffi,ℳi))] 42.67912pt 8706 4944 _ 29033 12850 29006 28997 67482370 VoC_ 29030 24891 29044 67273472 29025 _ 29033 24891 29044 24635 \, 29006 _ 29033 8511 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 24635 28939 _ 29033 24891 29005 _ 29033 84054785 84054785 84267779 −O~(||(ff¯2|ℳ¯|+|¯|)/T), 8704 29007 67273472 69640972 29006 69640972 67273472 28939 28722 \, 69640972 29005 69640972\, 8235 \, 69640972 29014 69640972 84054785 68408078 29012 84054785 24891 (35) and, thus, eq.˜14 is proved. To prove eq.˜15, where i,t≡ℳi=\i 29006 _ 29033 24891 29044 12817 29005 _ 29033 12349 29006 8814 \ 29033 \: [f(t)]≥f() 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12821 29030 67273472 28993 29007 29008 29012 84054785 −ˇf∑i∈[f(ai,t|t\ai,t)]−O~(|||¯|/T) 8704 28948 _ 29030 4944 _ 29033 12850 29006 28997 67482370 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\, 28993 _ 29044 8814 \ 29025 _ 29033 24891 29044 \ 84054785 84267779 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 (36) ≥f()−ˇf[f(t)]−O~(|||¯|/T), 12821 29030 67273472 28993 29007 29008 29012 84054785 8704 28948 _ 29030 \, 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 24891 (37) where eq.˜36 holds from eq.˜30, and eq.˜37 holds from [45, Eq. (15)]. Thereby, [f(t)]≥11+ˇff()−O~(|||¯|/T). 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12821 28721 28721 8235 28948 _ 29030 29030 67273472 28993 29007 29008 29012 84054785 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 314 (38) To prove eq.˜16, where i,t≡∅ 29006 _ 29033 24891 29044 12817 571 , per eq.˜30, [f(t)] -2.84526pt 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 ≥f()−ˇf∑i∈[f(ai,t)]−O~(|||¯|/T) -2.84526pt 12821 29030 67273472 28993 29007 29008 29012 84054785 8704 28948 _ 29030 4944 _ 29033 12850 29006 28997 67482370 29030 67273472 29025 _ 29033 24891 29044 84054785 84267779 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 ≥f()−ˇf1−ˇf[f(t)]−O~(|||¯|/T). -2.84526pt 12821 29030 67273472 28993 29007 29008 29012 84054785 8704 28948 _ 29030 28721 8704 28948 _ 29030 \, 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 314 (39) Therefore, [f(t)]≥(1−κf)f()−O~(|||¯|/T). -2.84526pt 28997 67482370 29030 67273472 28993 _ 29044 84054785 84267779 12821 67273472 28721 8704 28948 _ 29030 84054785 29030 67273472 28993 29007 29008 29012 84054785 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 314 (40) ∎ Proofs of Theorems˜2 and 3. Dividing both sides of eq.˜30 by ∑t=1Tf(t) 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785, we have ∑t=1Tf()∑t=1Tf(t) 4944 _ 29044 12349 28721 29012 29030 67273472 28993 29007 29008 29012 84054785 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 ≤1+ˇf∑t=1T∑i∈f(ai,t|aj,tj∈i,t)∑t=1Tf(t) 12820 28721 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 +O~(|||¯|/T) 8235 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 (41) =1+fiˇf+O~(|||¯|/T), 12349 28721 8235 28940 28948 _ 29030 8235 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 24891 (42) and thus Theorem˜2 holds. In particular, if at any time t 29044 there exists an agent ordering such that [i−1]⊆i,t,∀i 67482370 29033 8704 28721 84267779 12818 29006 _ 29033 24891 29044 24891 568 29033 , then Γ≤fi 0 12820 28940 =∑t=1T∑i∈f(ai,t|aj,tj∈i,t)∑t=1Tf(t) 12349 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 84054785 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 ≤∑t=1T∑i∈f(ai,t|aj,tj∈[i−1])∑t=1Tf(t)=1 12820 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 84054785 4944 _ 29044 12349 28721 29012 29030 67273472 28993 _ 29044 84054785 12349 28721 (43) holds due to submodularity. Finally, combining eqs.˜16 and 19, Theorem˜3 holds. ∎ Appendix B Decision Time of Anaconda We will first present and prove the following propositions and then prove Theorem˜4. Proposition 2 (Convergence Rate). Anaconda’s convergence error takes T 29012 iterations to be within ϵ 28943 where • If NeiSel is not involved, i.e., ∀i 568 29033 , αi=Γ 28939 _ 29033 12349 0 or αi≥|ℳi| 28939 _ 29033 12821 69640972 29005 _ 29033 69640972, T≥|¯|||2/ϵ, 29012 12821 69640972 29014 69640972 69640972 29006 69640972 28722 \, 68408078\, 28943 24891 (44) • If NeiSel is involved, i.e., ∃i∈ 569 29033 12850 29006 , Γ<αi<|ℳi|0 12604 28939 _ 29033 12604 69640972 29005 _ 29033 69640972, T≥(α¯2|ℳ¯|+||¯)||2/ϵ. 29012 12821 67273472 28939 28722 \, 69640972 29005 69640972\, 8235 \, 69640972 29014 69640972 84054785\, 69640972 29006 69640972 28722 \, 68408078\, 28943 314 (45) Proof Proposition˜2 holds from Lemmas˜2 and 3. ∎ Proposition 3 (Computational Complexity). At each t∈[T] 29044 12850 67482370 29012 84267779, Anaconda requires each agent i 29033 to execute 2αi+3 28722 28939 _ 29033 8235 28723 evaluations of f 29030 and O(|i|+αi|ℳi|) 29007 67273472 69640972 29014 _ 29033 69640972 8235 28939 _ 29033 69640972 29005 _ 29033 69640972 84054785 additions/multiplications. Proof At each t∈[T] 29044 12850 67482370 29012 84267779, ActSel requires 2 28722 function evaluations (Algorithm˜2’s line 7), along with O(|i|) 29007 67273472 69640972 29014 _ 29033 69640972 84054785 additions and multiplications (Algorithm˜2’s lines 4 and 8). Also, NeiSel requires 2αi+1 28722 28939 _ 29033 8235 28721 function evaluations (Algorithm˜3’s line 9), along with O(αi|ℳi|) 29007 67273472 28939 _ 29033 69640972 29005 _ 29033 69640972 84054785 additions and multiplications (Algorithm˜3’s lines 6 and 9-11). ∎ Proposition 4 (Communication Complexity). At each t∈[T] 29044 \, 12850 \, 67482370 29012 84267779, Anaconda requires one communication round where each agent i 29033 only transmits its own action to its out-neighbors. Proof At each t∈[T] 29044 12850 67482370 29012 84267779, Anaconda requires one (multi-channel) communication round where each agent i 29033 shares ai,t 29025 _ 29033 24891 29044 with and simultaneously receives aj,tj∈i,t\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 24891 29044 from i,t 29006 _ 29033 24891 29044 (Algorithm˜1’s line 5). Proposition 5 (Per-Round Decision Time). One round of Anaconda takes τf(2αi+3)+τc 28956 _ 29030 \, 67273472 28722 28939 _ 29033 8235 28723 84054785\, 8235 \, 28956 _ 29027 time to complete. Proof Proposition˜5 holds because of Propositions˜3 and 4, ignoring the time for additions and multiplications. ∎ Finally, we prove Theorem˜4: Proof of Theorem˜4. Theorem˜4 holds because of Propositions˜2 and 5. ∎ Appendix C Worst-Case Decision Time of Sequential Communication in Directed Networks We prove that DFS-SG has a O(τc||3) 29007 67273472 28956 _ 29027 \, 69640972 29006 69640972 28723 84054785 worst-case communication time on a strongly connected directed graph. The proof extends [22, Section I-D] by taking also the size of each inter-agent communication message into consideration since the larger the size the more time it will take for the message to be transmitted. We use the notation: • dir=,ℰdir 28999 _ 29028 29033 29042 12349 \ 29006 24891 28997 _ 29028 29033 29042 \ is a strongly connected directed graph; • π:1,…,||↦→1,…,|| 28953 24634 \ 28721 24891 … 24891 69640972 29006 69640972\ 567 545 \ 28721 24891 … 24891 69640972 29006 69640972\ denotes the order of action selection for agent i∈ 29033 12850 29006 given by the DFS approach in [22]; • d(i,j) 29028 67273472 29033 24891 29034 84054785 denotes the length of the shortest path from agent i 29033 to j 29034 on dir 28999 _ 29028 29033 29042 . Suppose p=(|1,…,|l) 29040 12349 67273472 69640972_ 28721 24891 … 24891 69640972_ 29036 84054785 is the longest path of dir 28999 _ 29028 29033 29042 , where l=|p| 29036 12349 69640972 29040 69640972. If l=|| 29036 12349 69640972 29006 69640972, then p 29040 is a spanning walk on dir 28999 _ 29028 29033 29042 with π(i)=i,∀i=1,…,|| 28953 67273472 29033 84054785 12349 29033 24891 568 29033 12349 \ 28721 24891 … 24891 69640972 29006 69640972\ and maxdirTmin(dir)=∑i= 1||−1iøc×d(i,i+1) _ 28999 _ 29028 29033 29042 29012 _ 29037 29033 29038 67273472 28999 _ 29028 29033 29042 84054785 12349 4944 _ 29033 \, 12349 \, 28721 69640972 29006 69640972 8704 28721 29033 28956 _ 29027 8706 29028 67273472 29033 24891 29033 8235 28721 84054785 =∑i= 1||−1iøc×1=øc||(||−1)/2≤O(øc||3). 12349 4944 _ 29033 \, 12349 \, 28721 69640972 29006 69640972 8704 28721 29033 28956 _ 29027 8706 28721 12349 28956 _ 29027 \, 69640972 29006 69640972\, 67273472 69640972 29006 69640972 8704 28721 84054785 68408078 28722 12820 29007 67273472 28956 _ 29027 \, 69640972 29006 69640972 28723 84054785 314 (46) Otherwise, the worst-case dir 28999 _ 29028 29033 29042 should have |l 69640972_ 29036 being the first vertex of p 29040 that is adjacent to a vertex |¯∈p 69640972 12850 29040 , Then we have maxdirTmin(dir) _ 28999 _ 29028 29033 29042 29012 _ 29037 29033 29038 67273472 28999 _ 29028 29033 29042 84054785 =∑i= 1l−1iøc×d(i,i+1)+∑i=l||−1iøc×d(i,i+1) 12349 4944 _ 29033 \, 12349 \, 28721 29036 8704 28721 29033 28956 _ 29027 8706 29028 67273472 29033 24891 29033 8235 28721 84054785 8235 4944 _ 29033 \, 12349 \, 29036 69640972 29006 69640972 8704 28721 29033 28956 _ 29027 8706 29028 67273472 29033 24891 29033 8235 28721 84054785 ≤∑i= 1l−1iøc×1+∑i=l||−1iøc×(l−1) 12820 4944 _ 29033 \, 12349 \, 28721 29036 8704 28721 29033 28956 _ 29027 8706 28721 8235 4944 _ 29033 \, 12349 \, 29036 69640972 29006 69640972 8704 28721 29033 28956 _ 29027 8706 67273472 29036 8704 28721 84054785 (47) =12øc[l(l−1)+(l−1)(||+l−1)(||−l)] 12349 28721 28722 28956 _ 29027 \, 67482370 29036 67273472 29036 8704 28721 84054785 8235 67273472 29036 8704 28721 84054785 67273472 69640972 29006 69640972 8235 29036 8704 28721 84054785 67273472 69640972 29006 69640972 8704 29036 84054785 84267779 (48) =O(øc||3), 12349 29007 67273472 28956 _ 29027 \, 69640972 29006 69640972 28723 84054785 24891 where eq.˜47 holds since no path in dir 28999 _ 29028 29033 29042 is longer than p 29040 , and the maximum of eq.˜48 is taken when l=⌈3||2−3||+3/3⌉ 29036 12349 69616390 28723 69640972 29006 69640972 28722 8704 28723 69640972 29006 69640972 8235 28723 68408078 28723 86397703. In all, DFS-SG has a O(τc||3) 29007 67273472 28956 _ 29027 \, 69640972 29006 69640972 28723 84054785 worst-case communication time. ∎ Appendix D Guarantees on Approximation Performance and Decision Time of DFS-BSG Theorem 5 (Approximation Performance of DFS-BSG). DFS-BSG enjoys the suboptimality performance, [f(t-)]≥11+ˇff()−O~(|||¯|/T). 28997 67482370 29030 67273472 28993 _ 29044 28996 28998 29011 - 28994 29011 28999 84054785 84267779 12821 28721 28721 8235 28948 _ 29030 \, 29030 67273472 28993 29007 29008 29012 84054785 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972 68408078 29012 84054785 314 (49) Proof Eq. (49) holds by replacing the bound of Exp3⋆-SIX in [47, Theorem 2] with that of Exp3 [2]. ∎ Theorem 6 (Convergence Time of DFS-BSG). DFS-BSG requires O[(τf|¯|||2+τc||5)|¯|/ϵ] 29007 67482370 67273472 28956 _ 29030 \, 69640972 29014 69640972\, 69640972 29006 69640972 28722 \, 8235 \, 28956 _ 29027 \, 69640972 29006 69640972 28725 84054785\, 69640972 29014 69640972\, 68408078\, 28943 84267779 time to converge in a directed network, and O[(τf|¯|||2+τc||4)|¯|/ϵ] 29007 67482370 67273472 28956 _ 29030 \, 69640972 29014 69640972\, 69640972 29006 69640972 28722 \, 8235 \, 28956 _ 29027 \, 69640972 29006 69640972 28724 84054785\, 69640972 29014 69640972\, 68408078\, 28943 84267779 time in an undirected network. Proof Since the algorithm requires O(|¯|||2/ϵ) 29007 67273472 69640972 29014 69640972\, 69640972 29006 69640972 28722 \, 68408078\, 28943 84054785 rounds to converge per eq.˜49, and that in the worst case, each round requires O(τf|¯|+τc||3) 29007 67273472 28956 _ 29030 \, 69640972 29014 69640972\, 8235 \, 28956 _ 29027 \, 69640972 29006 69640972 28723 84054785 time for a directed network and O(τf|¯|+τc||2) 29007 67273472 28956 _ 29030 \, 69640972 29014 69640972\, 8235 \, 28956 _ 29027 \, 69640972 29006 69640972 28722 84054785 time for an undirected network, Theorem˜6 holds. ∎ Appendix E Comparison of NeiSel with Nearest and Random Neighbor Selection: From Sparse to Dense Networks We also compare Anaconda with the heuristic benchmarks for neighbor selection (Nearest Neighbors and Random Neighbors) in 10 scenarios with different network densities. We adjust the network density by deploying the identical 20 cameras to cover areas of 10 different sizes. The results are presented in Fig. 3, where we observe a consistent improvement of Anaconda across all tested network densities. Setup. Environment: The environment is static and square with areas ranging in 2ΓΓ,4ΓΓ,…,2ΓΓΓ\ 28722 00 24891 28724 00 24891 … 24891 28722 000\. Agents: There exist 2Γ 28722 0 cameras. In each trial, the location xi 29048 _ 29033 of each camera i∈ 29033 12850 29006 is uniformly sampled on the map. They all have the same communication range ci=16 29027 _ 29033 12349 28721 28726 . Actions: All cameras i∈ 29033 12850 29006 have an FOV of radius ri=8 29042 _ 29033 12349 28728 and AOV θi=π/3 28946 _ 29033 12349 28953 68408078 28723 , with direction ai,t 29025 _ 29033 24891 29044 chosen from the 16 cardinal directions i 29014 _ 29033 , ∀t 568 29044 . Objective Function: f(ai,ti∈) 29030 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 is the total area of interest covered by the cameras 29006 when they select ai,ti∈\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 as their FOV directions. f 29030 is proved to be submodular [8]. Performance Metrics. We evaluate the achieved objective value of the algorithms over 2000 decision rounds. Results. We observe the improved coordination performance provided by network optimization via NeiSel (Fig. 3). In particular, Anaconda is comparable or better to the two heuristic benchmarks across all presented network densities. The performance gaps compared to the benchmarks first increase then decrease as the network becomes denser. The reason is that when the network is very sparse, all potential neighbors ℳi 29005 _ 29033 are not informative enough to make a difference; when the network is too dense, multiple potential neighbors in ℳi 29005 _ 29033 can be informative enough and thus all strategies perform similarly well.