Paper deep dive
Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach
Zirui Xu, Vasileios Tzoumas
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 3/31/2026, 1:28:58 AM
Summary
The paper introduces the Distributed Online Greedy (DOG) algorithm to address multi-agent submodular maximization under communication delays. By integrating adversarial bandit learning with delayed feedback, DOG enables simultaneous decision-making across arbitrary network topologies, balancing coordination performance and convergence time while outperforming existing sequential and one-hop decentralized approaches.
Entities (5)
Relation Signals (3)
DOG → addresses → Communication Delays
confidence 95% · we provide a distributed online algorithm for multi-agent submodular maximization under communication delays.
DOG → integrates → Adversarial Bandit Learning
confidence 95% · DOG algorithm, which integrates tools from adversarial bandit learning with delayed feedback
DOG → outperforms → BSG
confidence 90% · DOG is up to |N|^3 faster than BSG [28]
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We provide a distributed online algorithm for multi-agent submodular maximization under communication delays. We are motivated by the future distributed information-gathering tasks in unknown and dynamic environments, where utility functions naturally exhibit the diminishing-returns property, i.e., submodularity. Existing approaches for online submodular maximization either rely on sequential multi-hop communication, resulting in prohibitive delays and restrictive connectivity assumptions, or restrict each agent's coordination to its one-hop neighborhood only, thereby limiting the coordination performance. To address the issue, we provide the Distributed Online Greedy (DOG) algorithm, which integrates tools from adversarial bandit learning with delayed feedback to enable simultaneous decision-making across arbitrary network topologies. We provide the approximation performance of DOG against an optimal solution, capturing the suboptimality cost due to decentralization as a function of the network structure. Our analyses further reveal a trade-off between coordination performance and convergence time, determined by the magnitude of communication delays. By this trade-off, DOG spans the spectrum between the state-of-the-art fully centralized online coordination approach [1] and fully decentralized one-hop coordination approach [2].
Tags
Links
- Source: https://arxiv.org/abs/2603.27803v1
- Canonical: https://arxiv.org/abs/2603.27803v1
Trouble viewing inline? Open PDF directly →
Full Text
94,661 characters extracted from source content.
Expand or collapse full text
Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach Zirui Xu, Vasileios Tzoumas† †Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA; ziruixu,vtzoumas@umich.eduThis work was supported by NSF CAREER Award No. 2337412 and ARO Early Career Program Award W911NF-25-1-0280. Abstract We provide a distributed online algorithm for multi-agent submodular maximization under communication delays. We are motivated by the future distributed information-gathering tasks in unknown and dynamic environments, where utility functions naturally exhibit the diminishing-returns property, i.e., submodularity. Existing approaches for online submodular maximization either rely on sequential multi-hop communication, resulting in prohibitive delays and restrictive connectivity assumptions, or restrict each agent’s coordination to its one-hop neighborhood only, thereby limiting the coordination performance. To address the issue, we provide the Distributed Online Greedy (DOG) algorithm, which integrates tools from adversarial bandit learning with delayed feedback to enable simultaneous decision-making across arbitrary network topologies. We provide the approximation performance of DOG against an optimal solution, capturing the suboptimality cost due to decentralization as a function of the network structure. Our analyses further reveal a trade-off between coordination performance and convergence time, determined by the magnitude of communication delays. By this trade-off, DOG spans the spectrum between the state-of-the-art fully centralized online coordination approach [28] and fully decentralized one-hop coordination approach [29]. I Introduction Multi-agent systems of the future will increasingly rely on agent-to-agent communication to coordinate tasks such as target tracking [28], environmental mapping [1], and area monitoring [3]. These tasks are often modeled as maximization problems of the form maxai,t∈i,∀i∈ft(ai,ti∈),t=1,2,…, -1.42262pt _ 29025 _ 29033 24891 29044 \, 12850 \, 29014 _ 29033 24891 \, 568 \, 29033 \, 12850 \, 29006 \ 29030 _ 29044 67273472\,\ 29025 _ 29033 24891 29044 \_ 29033 \, 12850 \, 29006 \, 84054785 24891 \;\;\; 29044 12349 28721 24891 28722 24891 … 24891 -1.42262pt (1) across the robotics, control, and machine learning communities, where 29006 denotes the set of agents, ai,t 29025 _ 29033 24891 29044 denotes agent i 29033 ’s chosen action at time t 29044 , i 29014 _ 29033 denotes agent i 29033 ’s set of available actions, and ft:2∏i∈i↦→ℝ 29030 _ 29044 24634 28722 4945 _ 29033 12850 29006 29014 _ 29033 567 545 29010 denotes the objective function that captures the task utility (global objective) [13, 22, 26, 1, 9, 16, 10, 3, 21, 5, 18, 19, 27]. In resource allocation and information gathering applications, ft 29030 _ 29044 is submodular [7], a diminishing-returns property [13]. For example, in target monitoring with multiple reorientable cameras, 29006 is the set of cameras, i 29014 _ 29033 represents the possible orientations of each camera, and ft 29030 _ 29044 measures the number of distinct targets observed within the joint field of view. The optimization problem in eq.˜1 is NP-hard [6], but polynomial-time algorithms with provable approximation guarantees exist when the ft 29030 _ 29044 is submodular. A classical example is the Sequential Greedy (SG ) algorithm [7], which guarantees a 1/2 28721 68408078 28722 -approximation ratio. Many multi-agent tasks, including target tracking, collaborative mapping, and monitoring, can be cast as submodular coordination problems. Consequently, SG and its variants have been widely adopted in the controls, machine learning, and robotics literature [13, 22, 26, 1, 9, 10, 3, 21, 15, 19, 18, 11, 12, 27]. In this paper, we focus on applications where the environment is unpredictable and partially observable, and where the agents must solve the optimization problem in eq.˜1 via agent-to-agent communication, e.g., via mesh networks. Such optimization settings are challenging since, respectively: (i) ft(⋅) 29030 _ 29044 67273472 8705 84054785 is unknown a priori, necessitating online optimization approaches where the agents jointly plan actions using only retrospective feedback (bandit feedback) [28]; and (i) the state-of-the-art agent-to-agent communication speeds are slow compared to wired connections or 5G [20], necessitating novel decentralized optimization paradigms that rigorously sacrifice near-optimality for scalability [27]. In such challenging optimization settings, SG and its variants offer no performance guarantees [28]. In more detail, the related work on submodular maximization in unpredictable and partially observable environments, and in the decentralized optimization context of limited communication speeds, is as follows: Online submodular optimization In unpredictable settings, such as target tracking with maneuvering targets whose intentions are unknown [23], drones cannot forecast the future to evaluate ft 29030 _ 29044 in advance. Instead, they must coordinate actions online using retrospective feedback. The challenge deepens under partial observability: with limited sensing (e.g., drones tracking targets within a restricted field of view), drones can evaluate only the reward of executed actions but not the alternative rewards of unselected ones. This bandit feedback [14] prevents agents from fully exploiting past information, thus hindering the design of near-optimal coordination strategies in such environments. To this end, sequential coordination algorithms leveraging online feedback have been proposed in [30, 28], which provide guaranteed suboptimality against robots’ optimal time-varying actions in hindsight. These algorithms extend SG to the bandit setting, expanding tools from the literature on tracking the best expert (e.g., the EXP3-SIX algorithm [17]) to the multi-agent setting upon accounting for the submodular structure of the optimization problem. Online submodular optimization under low communication speeds But online sequential algorithms [30, 28], similar to their offline sequential greedy counterparts [13, 22, 26, 1, 9, 10, 3, 21, 15, 19, 18, 11, 12], cannot scale under real-world communication conditions [27]. Since they perform sequential multi-hop communication over (strongly) connected networks to enable near-optimality, they can cause excessive communication delays between consecutive time steps t 29044 and t+1 29044 8235 28721 [27]. In particular, for these state-of-the-art algorithms (offline and online variants), the communication delays increase quadratically or even cubically as the number of agents increases [27]. For example, the Bandit Sequential Greedy (BSG ) algorithm in [28] requires: (i) a communication complexity that is cubic in the number of agents at each time step (decision round) over a worst-case directed network, such that all agents can obtain the feedback of their selected actions, and (i) the number of decision rounds being quadratic in the number of agents such that the algorithm can converge. That is, it takes up to a quintic time in the number of agents for BSG to achieve near-optimal coordination performances [29, Theorem 6]. To address the communication issues above, novel distributed optimization algorithms have been proposed that achieve linear time complexity in the number of agents. To this end, for example, they (i) require each agent to coordinate with one-hop neighbors only, and (i) operate over arbitrary network topologies. Such an algorithm is the Resource-Aware distributed Greedy (RAG ) algorithm [27]. While RAG matches the performance of Sequential Greedy in fully centralized networks, for arbitrary network topologies, it suffers a suboptimality cost, as a function of the network topology. However, RAG applies to offline optimization only, where ft(⋅) 29030 _ 29044 67273472 8705 84054785 is know a priori, instead of online. Another example is the ActSel subroutine proposed in [29], which extends RAG to the online settings While the online approach ActSel enables simultaneous decisions by avoiding sequential communication and yet still provides an asymptotically the same suboptimality guarantee as RAG , it has even larger potentials: the reliance on strictly local information limits the coordination performance, as agents cannot access broader information from beyond their immediate neighbors. Therefore, the following research question arises: Under communication delays, how does each agent coordinate with others beyond its immediate neighborhood to maximize action coordination performance without sacrificing decision speed? Contributions. In this paper, we develop an online optimization algorithm that allows agents to exploit multi-hop communication in order to leverage information from beyond immediate neighbors, such that the performance gap between distributed and centralized coordination can be minimized. To address the inevitable multi-hop communication delays, we leverage techniques from bandit learning with delayed feedback [25], enabling agents to select asymptotically near-optimal actions despite outdated feedback. The algorithm has the following properties: Approximation Performance The algorithm provides a suboptimality bound against an optimal solution to eq.˜1. Particularly, the bound captures the suboptimality cost due to decentralization, as a function of each agent’s multi-hop coordination neighborhood. For example, as long as the network is connected (not necessarily fully connected), then the algorithm’s approximation bound is 1/2 28721 68408078 28722 because every agent can receive information from all others via multi-hop communication. In particular, DOG ’s bound is lower than BSG ’s 1/(1+κf) 28721 68408078 67273472 28721 8235 28948 _ 29030 84054785 due to decentralization, and better than ActSel ’s 1/(1+κf)−∑i∈(i(1)) 28721 68408078 67273472 28721 8235 28948 _ 29030 84054785 8704 4944 _ 29033 12850 29006 29027 29039 29033 29038 67273472 29006 _ 29033 67273472 28721 84054785 84054785 since multi-hop communication enlarges the coordination neighborhood, where i(1) 29006 _ 29033 67273472 28721 84054785 denotes i 29033 ’s one-hop neighborhood (Section˜IV). Convergence Time The algorithm enables agents to simultaneously select actions for every (2τf+τcd¯) 67273472 28722 28956 _ 29030 8235 28956 _ 29027 \, 29028 84054785 time, where τf 28956 _ 29030 and τc 28956 _ 29027 are the times for one function evaluation and transmitting one action for one-hop communication, respectively among all i∈ 29033 12850 29006 . The convergence time of DOG is O~[(τf+τcd¯)||2maxi∈(|i|+di)/ϵ] 29007 67482370 67273472 28956 _ 29030 8235 28956 _ 29027 \, 29028 84054785\, 69640972 29006 69640972 28722 \, _ 29033 12850 29006 \, 67273472 69640972 29014 _ 29033 69640972\, 8235 \, 29028 _ 29033 84054785\, 68408078\, 28943 84267779, slower than the ActSel subroutine in [29] by a factor of d¯2 29028 28722 , while up to ||3 69640972 29006 69640972 28723 faster than BSG [28] (Section˜V). I Distributed Online Submodular Maximization Under Communication Delays We present the problem formulation, using 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 use the following framework about the agents’ communication network and their global objective f 29030 . Communication network. The distributed communication network =,ℰ 28999 12349 \ 29006 24891 28997 \ can be directed and even disconnected, where ℰ 28997 is the set of communication channels. When 28999 is fully connected (all agents receive information from all others), we call it fully centralized. In contrast, when 28999 is fully disconnected (all agents are isolated, receiving information from no other agent), we call it fully decentralized. Communication neighborhood. When a communication channel exists from agent j 29034 to i 29033 , i.e., (j→i)∈ℰ 67273472 29034 12833 29033 84054785 12850 28997 , i 29033 can receive, store, and process information from j 29034 . The set of all agents from which i 29033 can receive information, possibly through multi-hop communication, is denoted by i 29006 _ 29033 . Thus, i 29006 _ 29033 represents agent i 29033 ’s ∞ 561 -hop in-neighborhood. For simplicity, we refer to i 29006 _ 29033 as agent i 29033 ’s neighborhood and assume it remains constant over [T] 67482370 29012 84267779. Information originating from different neighbors j∈i 29034 12850 29006 _ 29033 may take varying amounts of time to reach i 29033 , depending on the message size, communication data rate, and the number of hops from j 29034 to i 29033 . Communication delay. The communication delay is determined by the radius of agent i 29033 ’s neighborhood, i.e., the number of edges from the furthest multi-hop neighbor to i 29033 . We denote this delay by di 29028 _ 29033 . In particular, di 29028 _ 29033 is also the delay for agent i 29033 to receive the reward of selecting action ai,t 29025 _ 29033 24891 29044 at t 29044 . That is, the value of rai,t,t 29042 _ 29025 _ 29033 24891 29044 24891 \, 29044 will be available at t+di 29044 8235 29028 _ 29033 . Definition 1 (Normalized and Non-Decreasing Submodular Set Function [7]). 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 [4, 8]). 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 Online Submodular Maximization under Communication Delays). At each time step t∈[T] 29044 12850 67482370 29012 84267779, given the multi-hop neighborhood i 29006 _ 29033 , each agent i∈ 29033 12850 29006 needs to select an action ai,t 29025 _ 29033 24891 29044 to jointly solve maxai,t∈i,∀i∈∑t=1Tft(ai,ti∈) _ 29025 _ 29033 24891 29044 12850 29014 _ 29033 24891 568 \, 29033 12850 29006 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472\,\ 29025 _ 29033 24891 29044 \_ 29033 \, 12850 \, 29006 \, 84054785 (3) where ft:2↦→ℝ 29030 _ 29044 24634 28722 29014 _ 29006 567 545 29010 is a normalized, non-decreasing submodular, and 2nd-order submodular set function, and each agent i 29033 can access the value of ft() 29030 _ 29044 67273472\, 28993 \, 84054785 only after it has selected ai,t 29025 _ 29033 24891 29044 at time t 29044 and received aj,tj∈i\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 at time t+di 29044 8235 29028 _ 29033 , ∀⊆ai,t∪aj,tj∈i 568 \, 28993 12818 \ 29025 _ 29033 24891 29044 \ 8795 \ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 . ˜1 is a generalization to the problem in [28] by considering (i) the impact of communication delays, and (i) an arbitrary rather than a connected communication network. Moreover, ˜1 differs from [27] by (i) addressing unknown environments, and (i) allowing for multi-hop instead of merely one-hop communications. The action coordination performance in ˜1 highly depends on the network ii∈\ 29006 _ 29033 \_ 29033 12850 29006 : it will improve as the network becomes more centralized (from all agents coordinating with none to all agents coordinating with all). For example, consider the target monitoring scenario with multiple reorientable cameras: as the cameras become more centralized, they can each coordinate with more others to avoid covering the same targets, thus improving the total number of covered targets. Therefore, in this paper, we propose to adopt multi-hop communication to maximize each agent’s information access over the distributed communication network. To mitigate the influence of communication delays to the action coordination frequency, we leverage tools from bandit learning with delayed feedback, which will be shown in the next section. I Distributed Online Greedy Algorithm (DOG ) 0: Number of time steps T 29012 , agent i 29033 ’s action set i 29014 _ 29033 , agent i 29033 ’s in-neighborhood i 29006 _ 29033 , communication delay di 29028 _ 29033 . 10: Agent i 29033 ’s action ai,t 29025 _ 29033 24891 \, 29044 , ∀t∈[T] 568 29044 12850 67482370 29012 84267779. 1: ηi←log|i|/[(|i|+di)T] 28945 _ 29033 12832 69640972 29014 _ 29033 69640972\, 68408078\, 67482370 67273472 69640972 29014 _ 29033 69640972 8235 29028 _ 29033 84054785 29012 84267779; 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 ; 6: broadcast ai,t 29025 _ 29033 24891 29044 potentially via multi-hop communication; 7: receive neighbors’ actions aj,sj∈i\ 29025 _ 29034 24891 29043 \_ 29034 12850 29006 _ 29033 for s:s+di=t\ 29043 12346 29043 8235 29028 _ 29033 12349 29044 \; 28: rai,s,s←fs(ai,s|aj,sj∈i) 29042 _ 29025 _ 29033 24891 29043 24891 29043 12832 29030 _ 29043 67273472\, 29025 _ 29033 24891 29043 \, 69640972\,\ 29025 _ 29034 24891 29043 \_ 29034 12850 29006 _ 29033 \, 84054785 and normalize rai,s,s 29042 _ 29025 _ 29033 24891 29043 24891 29043 to [Γ,1] 674823700 24891 28721 84267779; 9: r^a,s←1−(ai,s=a)pa,s(1−rai,s,s) 29042 _ 29025 24891 29043 12832 28721 8704 28721 67273472 29025 _ 29033 24891 29043 \, 12349 \, 29025 84054785 29040 _ 29025 24891 29043 67273472 28721 \, 8704 \, 29042 _ 29025 _ 29033 24891 29043 24891 29043 84054785, ∀a∈i 568 29025 12850 29014 _ 29033 ; 10: wa,t+1←wa,texp(ηir^a,s),∀a∈i 29047 _ 29025 24891 29044 8235 28721 12832 29047 _ 29025 24891 29044 67273472 28945 _ 29033 \, 29042 _ 29025 24891 29043 84054785 24891 568 29025 12850 29014 _ 29033 ; 11: end for Algorithm 1 Distributed Online Greedy (DOG ) for Agent i 29033 We present the Distributed Online Greedy algorithm (DOG ) for ˜1. Particularly, ˜1 takes the form of adversarial bandit problems with delayed feedback. Therefore, in the following, we first present the problem formulation of adversarial bandit with delayed feedback (Section˜I-A) and then the main algorithm (Section˜I-B). I-A Adversarial Bandit with Delayed Feedback The adversarial bandit with delayed feedback problem involves an agent selecting a sequence of actions to maximize the total reward over a given number of time steps [25]. The challenges are: (i) at each time step t 29044 , no action’s reward is known to the agent a priori, and (i) after an action is selected, only the selected action’s reward will become known with a time delay dt 29028 _ 29044 , which is assumed to be known a priori. We present the problem in the following using the notation: • 29014 denotes the available action set; • |t∈ 69640972_ 29044 12850 29014 denotes the agent’s selected action at 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 t 29044 ; • dt 29028 _ 29044 is the delay for the reward of selecting action |t 69640972_ 29044 at t 29044 to be received. That is, the value of r|t,t 29042 _ 69640972_ 29044 24891 \, 29044 will be known by the agent at t+dt 29044 8235 29028 _ 29044 . Problem 2 (Adversarial Bandit with Delayed Feedback [25]). Consider 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 selected action’s reward r|t,t∈[Γ,1] 29042 _ 69640972_ 29044 24891 \, 29044 12850 674823700 24891 28721 84267779 will become known at t+dt 29044 8235 29028 _ 29044 . 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]. I-B DOG Algorithm We introduce the Distributed Online Greedy (DOG ) algorithm (Algorithm˜1). DOG enables agents to solve ˜1 by simultaneously solving their own instance of ˜2. To describe the algorithm, we use the notation: • 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∈∑t=1Tft(aii∈) 28993 29007 29008 29012 12850 _ 29025 _ 29033 12850 29014 _ 29033 24891 \, 568 \, 29033 12850 29006 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472\ 29025 _ 29033 \_ 29033 12850 29006 84054785 is the optimal actions for agents 29006 that solve ˜1. Intuitively, our goal is for each agent i 29033 at each time step t 29044 to efficiently select an action ai,t 29025 _ 29033 24891 29044 that maximizes the marginal gain ft(a|aj,tj∈i) 29030 _ 29044 67273472\, 29025 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 \, 84054785. That is, DOG aims to efficiently minimize the following quantification: Definition 3 (Static Regret for Each Agent i 29033 ). Given that agent i 29033 has multi-hop coordination neighborhood i 29006 _ 29033 . 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 RegT(ai,tt∈[T])≜ 29010 29029 29031 _ 29012 67273472\,\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779\, 84054785 (5) maxa∈i∑t=1Tft(a|aj,tj∈i)−∑t=1Tft(ai,t|aj,tj∈i). _ 29025 12850 29014 _ 29033 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472\, 29025 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 \, 84054785 8704 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472\, 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 \, 84054785 314 Ideally, the agents select actions simultaneously, unlike offline algorithms such as SG [7]. But if the agents aim to select actions simultaneously, aj,tj∈i\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 will become known only after agent i 29033 selects ai,t 29025 _ 29033 24891 29044 and communicates with i 29006 _ 29033 . Therefore, computing the marginal gain is possible only in hindsight, after all agents’ decisions have been finalized for time step t 29044 . Moreover, after ai,t 29025 _ 29033 24891 29044 is selected, the feedback aj,tj∈i\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 cannot be transmitted to agent i 29033 until after a delay di 29028 _ 29033 , due to potentially multi-hop communication. Thus, ˜1 aligns with the framework of ˜2 at the single-agent level, where the reward of selecting ai,t∈i 29025 _ 29033 24891 29044 12850 29014 _ 29033 at time t 29044 , i.e., rai,t,t≜ft(ai,t|aj,tj∈i) 29042 _ 29025 _ 29033 24891 29044 24891 29044 29030 _ 29044 67273472\, 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 \, 84054785, will not be known by agent i 29033 until time t+di 29044 8235 29028 _ 29033 . DOG starts by initializing a learning rate ηi 28945 _ 29033 and a weight vector wt 29047 _ 29044 for all available actions a∈i 29025 12850 29014 _ 29033 (Algorithm˜1’s lines 1–2). Then, at each t∈[T] 29044 12850 67482370 29012 84267779, it sequentially executes the following steps: • Compute probability distribution pt 29040 _ 29044 using wt 29047 _ 29044 (lines 3–4); • Select action ai,t∈i 29025 _ 29033 24891 29044 12850 29014 _ 29033 by sampling from pt 29040 _ 29044 (line 5); • Send ai,t 29025 _ 29033 24891 29044 to out-neighbors and relay in-neighbors’ actions if possible (line 6); • Receive in-neighbors’ past actions aj,sj∈i\ 29025 _ 29034 24891 29043 \_ 29034 12850 29006 _ 29033 for s:s+di=t\ 29043 12346 29043 8235 29028 _ 29033 12349 29044 \, where di 29028 _ 29033 is the time for all aj,sj∈i\ 29025 _ 29034 24891 29043 \_ 29034 12850 29006 _ 29033 to reach i 29033 , i.e., the communication delay (line 7); • Compute reward rai,s,s 29042 _ 29025 _ 29033 24891 29043 24891 29043 , estimate reward r^a,s 29042 _ 29025 24891 29043 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 8–11).111The coordination algorithms in [5, 18, 19] instruct the agents to select actions simultaneously at each time step as DOG, but they lift the coordination problem to the continuous domain and require each agent to know/estimate the gradient of the multilinear extension of ft 29030 _ 29044 , which leads to a decision time at least one order higher than DOG [27]. IV Approximation Guarantees We present the suboptimality bound of DOG . The bound compares DOG ’s solution to the optimal solution of ˜1. Leveraging the concept of coin (Definition˜4) that captures the suboptimality cost of decentralization, the bound covers the spectrum of DOG ’s approximation performance from when the network is fully centralized (all agents communicating with all) to fully decentralized (all agents communicating with none). Definition 4 (Centralization of Information [27]). For each time step t∈[T] 29044 12850 67482370 29012 84267779, consider a function ft:2↦→ 29030 _ 29044 12346 28722 29014 _ 29006 567 545 ℝ 29010 and a communication network ii∈\ 29006 _ 29033 \_ 29033 \, 12850 \, 29006 where each agent i∈ 29033 12850 29006 has selected an action ai,t 29025 _ 29033 24891 29044 . Then, at time t 29044 , agent i 29033 ’s centralization of information is defined as ft,i(i)≜ft(ai,t)−ft(ai,t|aj,tj∈ic). 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 67273472 29006 _ 29033 84054785 29030 _ 29044 67273472 29025 _ 29033 24891 29044 84054785 8704 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 \, 12850 \, 29006 _ 29033 29027 84054785 314 (6) ft,i 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 measures how much ai,t 29025 _ 29033 24891 29044 can overlap with the actions of agent i 29033 ’s non-neighbors. In the best scenario, where ai,t 29025 _ 29033 24891 29044 does not overlap with other actions at all, i.e., ft(ai,t|aj,tj∈ic)=ft(ai,t) 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 \, 12850 \, 29006 _ 29033 29027 84054785 12349 29030 _ 29044 67273472 29025 _ 29033 24891 29044 84054785, then ft,i=Γ 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 12349 0. In the worst case instead where ai,t 29025 _ 29033 24891 29044 is fully redundant, i.e., ft(ai,t|aj,tj∈ic)=Γ 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 \, 12850 \, 29006 _ 29033 29027 84054785 12349 0, then ft,i=ft(ai,t) 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 12349 29030 _ 29044 67273472 29025 _ 29033 24891 29044 84054785. We also need the following definition to present the approximation performance of DOG . Definition 5 (Curvature [2]). 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 67482370 29030 67273472 29014 84054785 8704 29030 67273472 29014 8814 \ 69640972\ 84054785 84267779 68408078 29030 67273472 69640972 84054785 314 (7) κf 28948 _ 29030 measures how far f 29030 is from modularity. When κf=Γ 28948 _ 29030 12349 0, we have f()−f(\|)=f(|) 29030 67273472 29014 84054785 8704 29030 67273472 29014 8814 \ 69640972\ 84054785 12349 29030 67273472 69640972 84054785 for all |∈ 69640972 12850 29014 , i.e., the marginal contribution of each element is independent of the presence of other elements, and thus f 29030 is modular. In contrast, κf=1 28948 _ 29030 12349 28721 in the extreme case where there exists some |∈ 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\. Theorem 1 (Approximation Performance). Over t∈[T] 29044 12850 67482370 29012 84267779, given the communication network ii∈\ 29006 _ 29033 \_ 29033 12850 29006 , DOG instructs each agent i∈ 29033 12850 29006 to select actions ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 that guarantee [ft(t)]≥11+ˇf[ft()] 28997 67482370 29030 _ 29044 67273472 28993 _ 29044 84054785 84267779 12821 28721 28721 8235 28948 _ 29030 \, 28997 67482370 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 84267779 −ˇf1+ˇf∑i∈[ft,i(i)]−O~(||||+d¯/T)⏟ ̵(T), 8704 28948 _ 29030 28721 8235 28948 _ 29030 4944 _ 29033 12850 29006 28997 67482370 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 67273472 29006 _ 29033 84054785 84267779 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972\, 8235 \, 29028 \, 68408078\, 29012 84054785_ 28960 67273472 29012 84054785 24891 (8) where κf≜maxt∈[T]κft 28948 _ 29030 _ 29044 12850 67482370 29012 84267779 28948 _ 29030 _ 29044 , ||+d¯≜maxi∈(|i|+di) 69640972 29014 69640972\, 8235 \, 29028 _ 29033 12850 29006 \, 67273472 69640972 29014 _ 29033 69640972\, 8235 \, 29028 _ 29033 84054785, d¯≜maxi∈di 29028 _ 29033 12850 29006 29028 _ 29033 , the expectation is due to DOG ’s internal randomness, and O~(⋅) 29007 67273472 8705 84054785 hides log terms. In particular, when the network is fully centralized, i.e., i≡\i 29006 _ 29033 12817 29006 8814 \ 29033 \, [ft(t)]≥11+ˇf[ft()]−O~(||||+d¯/T)⏟Œ(T). 28997 67482370 29030 _ 29044 67273472 28993 _ 29044 84054785 84267779 12821 28721 28721 8235 28948 _ 29030 \, 28997 67482370 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 84267779 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972\, 8235 \, 29028 \, 68408078\, 29012 84054785_ 28958 67273472 29012 84054785 314 (9) When the network is fully decentralized, i.e., i≡∅ 29006 _ 29033 12817 571 , [ft(t)]≥(1−κf)[ft()]−O~(||||+d¯/T)⏟Ø(T). 28997 67482370 29030 _ 29044 67273472 28993 _ 29044 84054785 84267779 12821 67273472 28721 8704 28948 _ 29030 84054785\, 28997 67482370 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 84267779 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972\, 8235 \, 29028 \, 68408078\, 29012 84054785_ 28959 67273472 29012 84054785 314 (10) In all, as T→∞ 29012 12833 561 , DOG enables asymptotically near-optimal action coordination. Particularly, Theorem˜1 quantifies both the convergence speed of DOG and the suboptimality of DOG due to decentralization: • Convergence time: ϕ,χ,ψ 28958 24891 28959 24891 28960 in eqs.˜9, 10 and 8 capture the time needed for action selection to converge to near-optimality and its impact to the suboptimality bound. They vanish as T→∞ 29012 12833 561 , having no impact on the suboptimality bound anymore, and its vanishing speed captures how fast the agents converge to near-optimal actions. • Decentralization: After ψ 28960 vanishes as T→∞ 29012 12833 561 , the bound in eq.˜8 depends on ft,i 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 capturing the suboptimality due to decentralization: the larger is i 29006 _ 29033 for each i∈ 29033 12850 29006 , the smaller is ft,i 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 , and the higher is DOG ’s approximation performance. That is, eqs.˜9, 10 and 8 imply DOG ’s suboptimality will improve if the agents have larger multi-hop coordination neighborhoods. Importantly, the 1/(1+κf) 28721 68408078 67273472 28721 8235 28948 _ 29030 84054785 suboptimality bound with a fully connected network recovers the bound in [2] and is near-optimal as the best possible bound for (3) is 1−κf/e 28721 8704 28948 _ 29030 68408078 29029 [24].222The bounds 1/(1+κf) 28721 68408078 67273472 28721 8235 28948 _ 29030 84054785 and 1−κf/e 28721 8704 28948 _ 29030 68408078 29029 become 1/2 28721 68408078 28722 and 1−1/e 28721 8704 28721 68408078 29029 when, in the worst case, κf=1 28948 _ 29030 12349 28721 . V Runtime Analysis We present the runtime of DOG by analyzing its computation and communication complexity (accounting for message length). We use the notation and observations: • τf 28956 _ 29030 is the time required for one evaluation of f 29030 ; • τc 28956 _ 29027 is the time for transmitting the information about one action from an agent directly to another agent; • ϵ 28943 is the convergence error after T 29012 iterations: T≥||2/ϵ 29012 12821 69640972 29006 69640972 28722 \, 68408078\, 28943 is required for ϕ(T),χ(T),ψ(T)≤ϵ 28958 67273472 29012 84054785 24891 28959 67273472 29012 84054785 24891 28960 67273472 29012 84054785 12820 28943 per eqs.˜9, 10 and 8. Proposition 1 (Computational Complexity). At each t∈[T] 29044 12850 67482370 29012 84267779, DOG requires each agent i 29033 to execute 2 28722 function evaluations of ft 29030 _ 29044 and O(|i|) 29007 67273472 69640972 29014 _ 29033 69640972 84054785 additions and multiplications. Proof. At each t∈[T] 29044 12850 67482370 29012 84267779, DOG requires 2 28722 function evaluations To compute the marginal gain (Algorithm˜1’s line 8), along with O(|i|) 29007 67273472 69640972 29014 _ 29033 69640972 84054785 additions and multiplications (Algorithm˜1’s lines 4 and 9–10), and thus Proposition˜1 holds. ∎ Proposition 2 (Communication Complexity). At each t∈[T] 29044 \, 12850 \, 67482370 29012 84267779, DOG requires O(τcd¯) 29007 67273472 28956 _ 29027 \, 29028 84054785 communication time such that each agent can transmit enough actions throughout its coordination neighborhood without information congestion. Proof. Proposition˜2 holds since, at each t∈[T] 29044 12850 67482370 29012 84267779, if the communication volume is less than O(di) 29007 67273472 29028 _ 29033 84054785 actions for agent i 29033 , then there will be newly selected actions congesting in the network, leading to an increasing amount of feedback delays (Algorithm˜1’s lines 6–7). ∎ Theorem 2 (Convergence Time). DOG achieves ϵ 28943 -convergence to near-optimal actions in O~[(τf+τcd¯)||+d¯||2/ϵ] 29007 67482370 67273472 28956 _ 29030 8235 28956 _ 29027 \, 29028 84054785\, 69640972 29014 69640972\, 8235 \, 29028 \, 69640972 29006 69640972 28722 \, 68408078\, 28943 84267779. Proof. Theorem˜2 holds by combining Propositions˜1 and 2, along with the definition of ϵ 28943 above, upon ignoring the time needed for additions and multiplications. ∎ Remark 1 (Trade-off Between Coordination Performance and Convergence Time). We observe this trade-off from Theorems˜1 and 2, determined by the magnitude of communication delays. Incorporating delayed information from larger multi-hop neighborhoods improves approximation performance yet increasing also the convergence time, while restricting communication to one-hop neighbors only accelerates convergence at the expense of lower coordination performance. In the fully centralized case, i.e., the delay takes the largest value ||−1 69640972 29006 69640972 8704 28721 , DOG will recover BSG ’s approximation bound of 1/(1+κf) 28721 68408078 67273472 28721 8235 28948 _ 29030 84054785, while converging faster than BSG by O(||) 29007 67273472 69640972 29006 69640972 84054785. In the one-hop coordination case, DOG will recover ActSel ’s approximation bound with the same convergence time. VI Conclusion We presented the Distributed Online Greedy (DOG ) algorithm for multi-agent submodular maximization under communication delays. Leveraging tools from adversarial bandit with delayed feedback, DOG enables agents to make simultaneous online decisions while incorporating delayed feedback information from multi-hop neighbors, maximizing each agent’s coordination neighborhood. We provided the approximation guarantees that capture the suboptimality cost of network decentralization and showed that DOG enables agents to select asymptotically near-optimal actions. The analyses of approximation bounds and convergence time that revealed a trade-off between coordination performance and convergence time: as the communication delay decreases, DOG covers the spectrum between fully centralized coordination and one-hop coordination. Future work. We will extend this work to enable the agents to actively address the trade-off of coordination performance and convergence rate, by tuning their admissible communication delays. 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. [2] 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: 2nd item, Definition 5. [3] 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: §I, §I, §I, §I. [4] 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. [5] 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 1. [6] 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. [7] 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, Definition 1. [8] 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. [9] 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. [10] 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. [11] 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: §I, §I. [12] A. Krause and D. Golovin (2012) Submodular function maximization. Tractability: Practical Approaches to Hard Problems 3. Cited by: §I, §I. [13] 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, §I. [14] T. Lattimore and C. Szepesvári (2020) Bandit algorithms. Cambridge University Press. Cited by: §I. [15] J. Liu, L. Zhou, P. Tokekar, and R. K. Williams (2021) Distributed resilient submodular action selection in adversarial environments. IEEE Robotics and Automation Letters 6 (3), p. 5832–5839. Cited by: §I, §I. [16] 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. [17] G. Neu (2015) Explore no more: improved high-probability regret bounds for non-stochastic bandits. Adv. Neu. Info. Proc. Sys. 28. Cited by: §I. [18] 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, footnote 1. [19] 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, footnote 1. [20] B. M. Sadler, F. T. Dagefu, J. N. Twigg, G. Verma, P. Spasojevic, R. J. Kozick, and J. Kong (2024) Low frequency multi-robot networking. IEEE Access 12, p. 21954–21984. Cited by: §I. [21] 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. [22] 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, §I. [23] M. Sun, M. E. Davies, I. Proudler, and J. R. Hopgood (2020) A gaussian process based method for multiple model tracking. In Sensor Signal Processing for Defence Conference (SSPD), p. 1–5. Cited by: §I. [24] M. Sviridenko, J. Vondrák, and J. Ward (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. of Operations Research 42 (4), p. 1197–1218. Cited by: 2nd item. [25] T. S. Thune, N. Cesa-Bianchi, and Y. Seldin (2019) Nonstochastic multiarmed bandits with unrestricted delays. Advances in Neural Information Processing Systems (NeurIPS) 32. Cited by: Appendix A, §I, §I-A, §I-A, Problem 2. [26] 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, §I. [27] 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, Definition 4, footnote 1. [28] 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: §I, §I, §I, §I, §I, §I. [29] Z. Xu and V. Tzoumas (2026) Self-configurable mesh-networks for scalable distributed submodular bandit optimization. arXiv preprint:2602.19366. Cited by: §I, §I, §I. [30] 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. Appendix A Proof of Theorem˜1 We prove the main result: ∑t=1Tft() 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 =∑t=1Tft(∪t)−∑t=1T∑i∈ft(ai,t|∪aj,tj∈[i−1]) 12349 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 29007 29008 29012 8795 28993 _ 29044 84054785 8704 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\, 28993 29007 29008 29012 8795 \ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 84054785 (11) ≤∑t=1Tft(t)+∑t=1T∑i∈ft(ai|t) 12820 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 _ 29044 84054785 8235 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 _ 29044 67273472 29025 _ 29033 29007 29008 29012 \, 69640972\, 28993 _ 29044 84054785 −(1−ˇf)∑t=1T∑i∈ft(ai,t|aj,tj∈i) 8704 67273472 28721 8704 28948 _ 29030 84054785 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 (12) ≤∑t=1Tft(t)+ˇf∑t=1T∑i∈ft(ai,t|aj,tj∈i) 12820 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 _ 29044 84054785 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 (13) +∑i∈∑t=1T[ft(ai|aj,tj∈i)−ft(ai,t|aj,tj∈i)] 8235 4944 _ 29033 12850 29006 4944 _ 29044 12349 28721 29012 67482370 29030 _ 29044 67273472 29025 _ 29033 29007 29008 29012 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 8704 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 84267779 ≤∑t=1Tft(t)+∑i∈RegT(ai,tt∈[T]) 12820 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 _ 29044 84054785 8235 4944 _ 29033 12850 29006 29010 29029 29031 _ 29012 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 +ˇf∑t=1T∑i∈ft(ai,t|aj,tj∈i) 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 (14) =(1+ˇf)∑t=1Tft(t)+∑i∈RegT(ai,tt∈[T]) 12349 67273472 28721 8235 28948 _ 29030 84054785 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 _ 29044 84054785 8235 4944 _ 29033 12850 29006 29010 29029 29031 _ 29012 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 (15) +ˇf∑t=1T∑i∈[ft(ai,t|aj,tj∈i)−ft(ai,t|aj,tj∈[i−1])] 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 67482370 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 8704 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 84054785 84267779 ≤(1+ˇf)∑t=1Tft(t)+∑i∈RegT(ai,tt∈[T]) 12820 67273472 28721 8235 28948 _ 29030 84054785 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 _ 29044 84054785 8235 4944 _ 29033 12850 29006 29010 29029 29031 _ 29012 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 +ˇf∑t=1T∑i∈[ft(ai,t)−ft(ai,t|aj,tj∈[i−1] )] 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 67482370 29030 _ 29044 67273472 29025 _ 29033 24891 29044 84054785 8704 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 8814 29006 _ 29033 84054785 84267779 (16) ≤(1+ˇf)∑t=1Tft(t)+∑i∈RegT(ai,tt∈[T]) 12820 67273472 28721 8235 28948 _ 29030 84054785 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 _ 29044 84054785 8235 4944 _ 29033 12850 29006 29010 29029 29031 _ 29012 67273472\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 84054785 +ˇf∑t=1T∑i∈[ft(ai,t)−ft(ai,t|aj,tj∈ic)]⏟ft,i(i), 8235 28948 _ 29030 4944 _ 29044 12349 28721 29012 4944 _ 29033 12850 29006 67482370 29030 _ 29044 67273472 29025 _ 29033 24891 29044 84054785 8704 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 29027 84054785 84267779_ 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 67273472 29006 _ 29033 84054785 24891 (17) where eq.˜11 holds by telescoping the sum, eq.˜12 holds since f 29030 is submodular and since 1−κf≤ft(ai,t|aj,tj∈\i)ft(ai,t)≤ft(ai,t|∪aj,tj∈[i−1])ft(ai,t|aj,tj∈i) 28721 8704 28948 _ 29030 12820 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 8814 \ 29033 \ 84054785 29030 _ 29044 67273472 29025 _ 29033 24891 29044 84054785 12820 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\, 28993 29007 29008 29012 8795 \ 29025 _ 29034 24891 29044 \_ 29034 12850 67482370 29033 8704 28721 84267779 84054785 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 per Definition˜5, eq.˜13 holds from submodularity, eq.˜14 holds from Definition˜3, eq.˜16 holds since ft 29030 _ 29044 is 2nd-order submodular, and eq.˜17 holds from Definition˜4. Reorganizing eq.˜17 and leveraging [25, Theorem 1], we prove eq.˜8 by the following, [ft()] 28997 67482370 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 84267779 =1T∑t=1Tft() 12349 28721 29012 4944 _ 29044 12349 28721 29012 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 ≤(1+ˇf)[ft(t)]+ˇf∑i∈[ft,i(i)] 12820 67273472 28721 8235 28948 _ 29030 84054785 28997 67482370 29030 _ 29044 67273472 28993 _ 29044 84054785 84267779 8235 28948 _ 29030 4944 _ 29033 12850 29006 28997 67482370 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 67273472 29006 _ 29033 84054785 84267779 +O~(||||+d¯/T). 8235 29007 67273472 69640972 29006 69640972 69640972 29014 69640972\, 8235 \, 29028 \, 68408078\, 29012 84054785 314 (18) In the fully centralized scenario, we have i=\i 29006 _ 29033 12349 29006 8814 \ 29033 \. Thus, ft,i(i)=Γ 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 67273472 29006 _ 29033 84054785 12349 0, and thus eq.˜9 is proved. Finally, in the fully decentralized case where i=∅ 29006 _ 29033 12349 571 , per eq.˜14, [ft(t)] 28997 67482370 29030 _ 29044 67273472 28993 _ 29044 84054785 84267779 ≥[ft()]−ˇf∑i∈[ft(ai,t)] 12821 28997 67482370 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 84267779 8704 28948 _ 29030 4944 _ 29033 12850 29006 28997 67482370 29030 _ 29044 67273472 29025 _ 29033 24891 29044 84054785 84267779 −O~(||||+d¯/T) 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972\, 8235 \, 29028 \, 68408078\, 29012 84054785 ≥[ft()]−ˇf1−ˇf∑i∈[ft(ai,t)] 12821 28997 67482370 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 84267779 8704 28948 _ 29030 28721 8704 28948 _ 29030 4944 _ 29033 12850 29006 28997 67482370 29030 _ 29044 67273472 29025 _ 29033 24891 29044 84054785 84267779 −O~(||||+d¯/T). 8704 29007 67273472 69640972 29006 69640972 69640972 29014 69640972\, 8235 \, 29028 \, 68408078\, 29012 84054785 314 (19) and thus eq.˜10 is proved. ∎