Paper deep dive
Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays
Pranjal Sharma, Zirui Xu, Vasileios Tzoumas
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 93%
Last extracted: 4/10/2026, 1:59:34 AM
Summary
This paper introduces an asynchronous distributed coordination algorithm for multi-agent bandit submodular maximization, addressing challenges posed by heterogeneous communication delays and mismatched local clocks. The authors provide theoretical approximation guarantees and convergence rates, demonstrating that the suboptimality gap is influenced by communication topology, delay bounds, and clock synchronization errors. The approach is validated through multi-camera target-tracking simulations.
Entities (5)
Relation Signals (3)
Asynchronous Distributed Bandit Submodular Maximization → addresses → Heterogeneous communication delays
confidence 95% · We provide a distributed multi-agent decision-making framework that enables near-optimal action coordination in unknown environments under heterogeneous communication delays
Asynchronous Distributed Bandit Submodular Maximization → addresses → Mismatched local clocks
confidence 95% · and asynchronous local clocks.
Asynchronous Distributed Bandit Submodular Maximization → validatedby → Multi-camera area monitoring
confidence 90% · We verify the algorithm's performance through multi-camera target-tracking simulations
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study asynchronous distributed decision-making for scalable multi-agent bandit submodular maximization. We are motivated by distributed information-gathering tasks in unknown environments and under heterogeneous inter-agent communication delays. To enable scalability despite limited communication delays, existing approaches restrict each agent to coordinate only with its one-hop neighbors. But these approaches assume homogeneous communication delays among the agents and a synchronous global clock. In practice, however, delays are heterogeneous, and agents operate with mismatched local clocks. That is, each agent does not receive information from all neighbors at the same time, compromising decision-making. In this paper, we provide an asynchronous coordination algorithm to overcome the challenges. We establish a provable approximation guarantee against the optimal synchronized centralized solution, where the suboptimality gap explicitly depends on communication delays and clock mismatches. The bounds also depend on the topology of each neighborhood, capturing the effect of distributed decision-making via one-hop-neighborhood messages only. We validate the approach through numerical simulations on multi-camera area monitoring.
Tags
Links
- Source: https://arxiv.org/abs/2604.06430v1
- Canonical: https://arxiv.org/abs/2604.06430v1
Trouble viewing inline? Open PDF directly →
Full Text
179,948 characters extracted from source content.
Expand or collapse full text
Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays Pranjal Sharma, Zirui Xu, Vasileios Tzoumas† †Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109, USA spranjal,ziruixu,vtzoumas@umich.edu Abstract We study asynchronous distributed decision-ma- king for scalable multi-agent bandit submodular maximization. We are motivated by distributed information-gathering tasks in unknown environments and under heterogeneous inter-agent communication delays. To enable scalability despite limited communication delays, existing approaches restrict each agent to coordinate only with its one-hop neighbors. But these approaches assume homogeneous communication delays among the agents and a synchronous global clock. In practice, however, delays are heterogeneous, and agents operate with mismatched local clocks. That is, each agent does not receive information from all neighbors at the same time, compromising decision-making. In this paper, we provide an asynchronous coordination algorithm to overcome the challenges. We establish a provable approximation guarantee against the optimal synchronized centralized solution, where the suboptimality gap explicitly depends on communication delays and clock mismatches. The bounds also depend on the topology of each neighborhood, capturing the effect of distributed decision-making via one-hop-neighborhood messages only. We validate the approach through numerical simulations on multi-camera area monitoring. I Introduction Multi-agent systems of the future will increasingly rely on agent-to-agent communication to coordinate tasks such as target tracking [34], environmental mapping [1], and area monitoring [3]. These tasks are often modeled as 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) [15, 27, 31, 1, 11, 19, 12, 3, 26, 5, 24, 25, 33]. In resource allocation and information gathering applications, ft 29030 _ 29044 is submodular [8], a diminishing-returns property [15]. 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 [7], 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 [8], which guarantees a 1/2 28721 68408078 28722 -approximation ratio. SG and its variants have been widely adopted in the controls, machine learning, and robotics literature [15, 27, 31, 1, 11, 12, 3, 26, 18, 25, 24, 13, 14, 33]. In this paper, we consider settings where the dynamics of the environment are unknown and partially observable. This requires agents to optimize actions based on retrospective rewards only (bandit optimization [17]). For example, in target tracking with unknown target motion [28], agents cannot evaluate ft 29030 _ 29044 in advance and instead rely on bandit feedback [17], observing only the rewards of executed actions. This severely limits information reuse and complicates coordination. To address this, prior work extends sequential greedy to the bandit setting [37, 34], leveraging tools from online learning such as tracking the best expert (e.g., EXP3-SIX [21]) to obtain suboptimality guarantees relative to time-varying optimal actions in hindsight. However, the approaches above, similar to their offline counterparts [15, 27, 31, 1, 11, 12, 3, 26, 18, 25, 24, 13, 14], where ft 29030 _ 29044 is assumed known a priori, rely on sequential multi-hop communication over connected networks, leading to prohibitive delays under realistic communication constraints [33]. Specifically, their communication complexity scales quadratically or cubically with the number of agents, and convergence typically requires a quadratic number of decision rounds. For instance, Bandit Sequential Greedy (BSG ) [34] incurs cubic communication per round and quadratic rounds to converge, resulting in quintic time complexity in the worst case [36, Theorem 6]. To improve scalability, recent distributed approaches restrict coordination to one-hop neighbors and operate over arbitrary network topologies, achieving linear-time scaling. For example, Resource-Aware distributed Greedy (RAG ) [33] matches centralized performance offline under full connectivity but incurs topology-dependent suboptimality otherwise. [36] extends RAG to the online setting and actively designs each agent’s communication neighborhood to maximize the overall optimization performance. Moreover, multi-hop communication is leveraged in [35] such that the coordination performance can be improved without sacrificing much decision speed. But all works above make two key assumptions: (i) they assume homogeneous one-hop communication delays among all agents, and (i) they assume synchronized global clocks for all agents. These assumptions are crucial in enabling both the algorithms and theoretical guarantees for the prior works. But in practice, delays are generally heterogeneous across neighbors because of nonuniform communication hardware and local channel conditions; hence, information arrives at different times and decisions may have to be made before all information arrives. Moreover, the agents’ local clocks are generally mismatched, and the multi-agent system cannot reliably maintain strict global synchronization. After incorporating these two limitations, the following research question arises: How does each agent perform scalable coordination with others using partial-neighborhood information and under asynchronous local clocks? Contributions. We provide a distributed multi-agent decision-making framework that enables near-optimal action coordination in unknown environments under heterogeneous communication delays and asynchronous local clocks. Our approach leverages heterogeneous delays to allow each agent to incorporate partial neighborhood information as it arrives, allowing agents to learn near-optimal actions and adapt to dynamic environments faster. To this end, we develop tools for adversarial bandit with delayed feedback and asynchronous distributed submodular maximization. The approach is fully distributed: each agent has its own pace of action selection under asynchronous local clocks. We verify the algorithm’s performance through multi-camera target-tracking simulations, showing that it increasingly outperforms the baseline as delays increase. The algorithm has the following properties: Approximation Performance The algorithm enjoys a suboptimality bound against the optimal solution of eq.˜1. In the synchronous setting, the bound captures the suboptimality gap against the optimal synchronized centralized solution, where the gap explicitly depends on communication delays and the topology of each neighborhood, capturing the effect of distributed decision-making via one-hop-neighborhood messages only (Theorem˜2). In the asynchronous setting, given a timing mismatch bound of ρ 28954 , these guarantees remain valid up to an additive mismatch term of order O(ρ||2) 29007 67273472 28954 69640972 29006 69640972 28722 84054785, which explicitly captures the degradation caused by asynchronous local clocks (Theorem˜4). Convergence Rate The algorithm enables the agents to achieve epsilon-convergence after O~(||2|¯|M¯t/ε2) 29007 \! 67273472 69640972 29006 69640972 28722 69640972 29014 69640972 29005 _ 29044 68408078 28962 28722 84054785 rounds, assuming the delays are bounded due to sufficient communication bandwidth. I Distributed Online Submodular Maximization Under Heterogeneous Communication Delays We present the problem formulation. To this end, we use the following 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 through one-hop communication is denoted by i 29006 _ 29033 , agent i 29033 ’s neighborhood. We assume i 29006 _ 29033 to remain 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 and communication data rate. Communication delay. For information sent from agent j 29034 to agent i 29033 at round t 29044 , let di,tj 29028 _ 29033 24891 29044 29034 denote the communication delay. These delays may vary across neighbors j∈i 29034 12850 29006 _ 29033 and across time, reflecting heterogeneous communication conditions. Hence, agent i 29033 can evaluate the reward of its round-t 29044 action only after receiving the required neighbor actions, i.e., after a delay of maxj∈idi,tj _ 29034 12850 29006 _ 29033 29028 _ 29033 24891 29044 29034 . We also define an upper bound on the delays for agent i 29033 as d¯i≜maxt(maxj∈i(di,tj)) 29028 _ 29033 _ 29044 67273472 _ 29034 12850 29006 _ 29033 67273472 29028 29034 _ 29033 24891 29044 84054785 84054785 and an upper bound on delays throughout the network as d¯≜maxt(maxi∈(maxj∈idi,tj)) 29028 _ 29044 67273472 _ 29033 12850 29006 67273472 _ 29034 12850 29006 _ 29033 29028 29034 _ 29033 24891 29044 84054785 84054785. To this end, we also assume sufficient bandwidth for each communication channels such that the delays are bounded instead of accumulating. Arrival of information. Since the delays di,tj 29028 _ 29033 24891 29044 29034 may differ across j∈i 29034 12850 29006 _ 29033 , the round-t 29044 neighbor actions received by agent i 29033 may arrive in K 29003 batches, where 1≤K≤|i| 28721 12820 29003 12820 69640972 29006 _ 29033 69640972. Ri,t(k) 29010 _ 29033 24891 29044 67273472 29035 84054785 :=j: aj,t info. has arrived by batch k, 12346 12349 \ 29034 12346 $ 29025 _ 29034 24891 29044 $ info. has arrived by batch 29035 \ 24891 (2) Ri,t(Γ) 29010 _ 29033 24891 29044 672734720 84054785 :=∅, 12346 12349 571 24891 (3) Mi,t(k) 29005 _ 29033 24891 29044 67273472 29035 84054785 :=i ,t(k),k∈1,…,K. 12346 12349 29006 _ 29033 8814 29010 _ 29033 24891 29044 67273472 29035 84054785 24891 29035 12850 \ 28721 24891 … 24891 29003 \ 314 (4) Reward Estimation. The agents may build estimates of neighbors’ missing actions Mi,t(k) 29005 67273472 29035 84054785_ 29033 24891 29044 based on the neighbors’ past actions and states. This allows the agents to estimate each round’s reward before the true value can be computed. In our simulations, all agents use the last known neighbor actions as estimates for missing actions. Theorem˜1 also covers regret guarantees for worst case estimates, which is when the difference between estimated and true reward is the maximum. This is possible since we assume the reward function to be bounded: such a conservative bound is available based on knowledge of worst case dynamics of the agents and the environment, a typical assumption for bandit learning [30]. Definition 1 (Normalized and Non-Decreasing Submodular Set Function [8]). 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 . Definition 2 (2nd-order Submodular Set Function [4, 9]). 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 (5) for any disjoint ,ℬ,⊆ 28993 24891 28994 24891 28995 12818 29014 (∩ℬ∩=∅) 67273472 28993 8796 28994 8796 28995 12349 571 84054785 and s∈ 29043 12850 29014 . Problem 1 (Distributed Online Submodular Maximization under Communication Delays). At each time step t∈[T] 29044 12850 67482370 29012 84267779, each agent i∈ 29033 12850 29006 , given its neighborhood i 29006 _ 29033 , 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 24891 (6) where ft:2→ℝ 29030 _ 29044 12346 28722 29014 29006 12833 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,tj,∀⊆ai,t∪aj,tj∈i 29044 8235 29028 29034 _ 29033 24891 29044 24891 \, 568 28993 12818 \ 29025 _ 29033 24891 29044 \ 8795 \ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 . ˜1 is the same as the one presented in [35] with an additional consideration for when the action data from an agent’s neighbors is received. ˜1 also highlights a tradeoff: larger coordination neighborhoods can improve action quality, but they also increase the delay before an agent can evaluate its reward, since that reward depends on neighbors’ round-t 29044 actions. To avoid waiting for all missing information, we adopt an estimation-correction approach in which each agent forms intermediate reward estimates using the currently received neighbor actions and refines them as additional information arrives. This motivates the delayed-bandit formulation in the next section. I Distributed Online Greedy with Intermediate Updates Algorithm (DOG-IU ) 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 bound d¯i 29028 _ 29033 . 0: Agent i 29033 ’s action ai,t 29025 _ 29033 24891 29044 , ∀t∈[T] 568 29044 12850 67482370 29012 84267779. 1: ηi←log|i|/((|i|+d¯i)T) 28945 _ 29033 12832 69640972 29014 _ 29033 69640972 68408078 67273472 67273472 69640972 29014 _ 29033 69640972 8235 29028 _ 29033 84054785 29012 84054785; 2: w1←[w|,1,…,w|i|,1]⊤ 29047 _ 28721 12832 67482370 29047 _ 69640972 24891 28721 24891 … 24891 29047 _ 69640972 29014 _ 29033 69640972 24891 28721 84267779 574 with w|,1=1 29047 _ 69640972 24891 28721 12349 28721 , ∀a∈i 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 to one-hop neighbors; 7: receive neighbors’ actions aj,sj∈i,s\ 29025 _ 29034 24891 29043 \_ 29034 12850 29006 _ 29033 24891 29043 for all s∈t≜s:s+di,sj=t 29043 12850 29011 _ 29044 \ 29043 12346 29043 8235 29028 29034 _ 29033 24891 29043 12349 29044 \; 8: form estimates ZΓt and Zkss,∀s∈t 29018 29044 _0 and 29018 29043 _ 29035 _ 29043 24891 568 29043 12850 29011 _ 29044 ; 9: r^a,s(Zkss)←1−(ai,s=a)pa,s(1−Zkss), 29042 _ 29025 24891 29043 67273472 29018 29043 _ 29035 _ 29043 84054785 12832 28721 8704 28721 67273472 29025 _ 29033 24891 29043 12349 29025 84054785 29040 _ 29025 24891 29043 67273472 28721 8704 29018 29043 _ 29035 _ 29043 84054785 24891 ∀a∈i,∀s∈t∪t 568 29025 12850 29014 _ 29033 24891 568 29043 12850 29011 _ 29044 8795 \ 29044 \; 110: form corrections Δa,s,∀a∈i,∀s∈t∪t 28673 _ 29025 24891 29043 24891 \; 568 29025 12850 29014 _ 29033 24891 568 29043 12850 29011 _ 29044 8795 \ 29044 \; 11: wa,t+1←wa,texp(∑s∈t∪tΔa,s),∀a∈i 29047 _ 29025 24891 29044 8235 28721 12832 29047 _ 29025 24891 29044 67273472 4944 _ 29043 12850 29011 _ 29044 8795 \ 29044 \ 28673 _ 29025 24891 29043 84054785 24891 \; 568 29025 12850 29014 _ 29033 ; 12: store all Zkss 29018 29043 _ 29035 _ 29043 ; 13: end for Algorithm 1 Distributed Online Greedy with Intermediate Updates (DOG-IU ) for Agent i 29033 We present the Distributed Online Greedy with Intermediate Updates algorithm (DOG-IU ) for ˜1. Particularly, ˜1 takes the form of adversarial bandit problems with delayed feedback. However, we also need to enable intermediate updates using partial information (from a subset of an agent’s neighborhood). Therefore, we generalize the adversarial bandit with delayed feedback problem formulation to allow for intermediate updates (Section˜I-A), and then present the main algorithm (Section˜I-B). I-A Per-Agent Adversarial Bandit with Delayed Feedback and Intermediate Updates 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 [30]. 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 , which in our case is a submodular function marginal. In other words, the agent’s reward is the marginal gain of its action |t 69640972_ 29044 given the actions of its neighbors; • dt 29028 _ 29044 is the number of delayed time steps for the reward of selecting action |t 69640972_ 29044 at t 29044 to be received. In our case, the agent will know the actions of all of its neighbors and be able to calculate r|t,t 29042 _ 69640972_ 29044 24891 29044 at t+dt 29044 8235 29028 _ 29044 ; • Intermediate estimates: From t 29044 until t+dt 29044 8235 29028 _ 29044 , the agent will form estimates of the round t 29044 reward as it receives more round t 29044 information. Problem 2 (Adversarial Bandit with Delayed Feedback and Intermediate Updates). Consider a horizon of T 29012 time steps. At each time step t∈[T] 29044 12850 67482370 29012 84267779, the agent i 29033 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 (7) is minimized, where no actions’ rewards are known a priori, and only the selected action’s true 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 , with partial information about the reward becoming available in multiple batches at intermediate rounds between t 29044 and t+dt 29044 8235 29028 _ 29044 . This problem is a more general version of the delayed bandit feedback problem tackled by the Delayed Exponential Weights (DEW ) algorithm in [30] as it allows for intermediate updates based on estimates of missing rewards using partial information. In the case of all of the delayed information for a round arriving at the same time, ˜2 reduces to the delayed bandit feedback problem discussed in [30]. The goal of solving Problem 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. I-B DOG-IU Algorithm We enable agents in the distributed setting to solve ˜1 by making them simultaneously solve their own instance of ˜2. Intuitively, our goal is for each agent i 29033 at each time step to efficiently select an action ai,t 29025 _ 29033 24891 29044 that maximizes the marginal gain ft(ai,t|aj,tj∈i) 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 from the perspective of agent i 29033 . Thus, DOG-IU aims to efficiently minimize the following quantification: Definition 3 (Static Regret for Each Agent i 29033 ). Given that agent i 29033 has a neighborhood i 29006 _ 29033 , and at each time step t 29044 , 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 ≜maxa∈i∑t=1Tft(a|aj,tj∈i) _ 29025 12850 29014 _ 29033 \ 4944 _ 29044 12349 28721 29012 29030 _ 29044 \! 67273472 29025 12906 \ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 (8) −∑t=1Tft(ai,t|aj,tj∈i). 8704 4944 _ 29044 12349 28721 29012 29030 _ 29044 \! 67273472 29025 _ 29033 24891 29044 12906 \ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 314 Because the neighbors’ round-t 29044 actions arrive with heterogeneous delays, agent i 29033 cannot evaluate the true reward rai,t≜ft(ai,t|aj,tj∈i) 29042 _ 29025 _ 29033 24891 29044 29030 _ 29044 67273472 29025 _ 29033 24891 29044 \, 69640972\,\ 29025 _ 29034 24891 29044 \_ 29034 12850 29006 _ 29033 84054785 immediately after selecting ai,t 29025 _ 29033 24891 29044 . Instead, DOG-IU forms an intermediate estimate of this reward using the actions already received for round t 29044 together with estimates of the still-missing neighbor actions: Zkt≜f(ai,t|ajj∈Ri,t(k)∪a~jj∈Mi,t(k)), 29018 29044 _ 29035 29030 67273472 29025 _ 29033 24891 29044 \; 69640972\; \ 29025 _ 29034 \_ 29034 12850 29010 _ 29033 24891 29044 67273472 29035 84054785 8795 \ 29025 _ 29034 \_ 29034 12850 29005 _ 29033 24891 29044 67273472 29035 84054785 84054785 24891 (9) where k∈Γ,1,…,K 29035 12850 \0 24891 28721 24891 … 24891 29003 \ is the number of information batches for round t 29044 received so far. In particular, ZKt=rai,t,t 29018 _ 29003 29044 12349 29042 _ 29025 _ 29033 24891 29044 24891 29044 once all neighbors’ round-t 29044 actions have arrived. Following the standard EXP3 approach, agent i 29033 uses the importance weighted estimate r^a,t(x)≜1−(a=ai,t)pa,t(1−x), 29042 _ 29025 24891 29044 67273472 29048 84054785 28721 8704 28721 67273472 29025 12349 29025 _ 29033 24891 29044 84054785 29040 _ 29025 24891 29044 67273472 28721 8704 29048 84054785 24891 (10) where x 29048 is either an intermediate estimate Ztk 29018 _ 29044 29035 or the true reward. At round t 29044 , agent i 29033 maintains, for each unresolved past round s 29043 , the currently received and still-missing neighbor sets, and refines its estimate whenever new information for that round arrives. Let ks 29035 _ 29043 denote the number of batches for round s 29043 received up to round t 29044 . DOG-IU then applies Δa,t=ȷir^a,t(Z^Γt), 28673 _ 29025 24891 29044 12349 28945 _ 29033 \, 29042 _ 29025 24891 29044 67273472 29018 29044 _0 84054785 24891 (11) Δa,s=ȷi[r^a,s(Zkss)−r^a,s(Zks−1s)], 28673 _ 29025 24891 29043 12349 28945 _ 29033 67482370 29042 _ 29025 24891 29043 67273472 29018 29043 _ 29035 _ 29043 84054785 8704 29042 _ 29025 24891 29043 67273472 29018 29043 _ 29035 _ 29043 8704 28721 84054785 84267779 24891 (12) ∀a∈i,s∈t−d¯i,…,t−1, 568 29025 12850 29014 _ 29033 24891 29043 12850 \ 29044 8704 29028 _ 29033 24891 … 24891 29044 8704 28721 \ 24891 where ηi 28945 _ 29033 is the learning rate. Δa,t 28673 _ 29025 24891 29044 is the update made after agent i 29033 acts at round t 29044 , while Δa,s 28673 _ 29025 24891 29043 is a correction applied when additional round s 29043 neighbor information arrives and refines the reward estimate for that round. Algorithm˜1 implements this procedure online. It initializes the learning rate and action weights (lines 1–2). Then at each round it computes the sampling distribution and draws an action (lines 4–5), broadcasts chosen action and receives newly arrived delayed neighbor actions (lines 6–7), forms updated reward estimates for the current and unresolved past rounds (line 8), converts them into importance-weighted estimates and corrections (lines 9–10), and finally updates the weights (line 11) before storing the new estimates (line 12). IV Guarantees We present the static regret bound of DOG-IU ’s per-agent solution to Problem 2. Then, we present the suboptimality bound of DOG-IU at the network level. The bound compares DOG-IU ’s solution to the optimal solution of ˜1. Leveraging the concept of coin (Definition˜6) that captures the suboptimality cost of distributed communication and computation, the bound covers the spectrum of DOG-IU ’s approximation performance from when the network is fully centralized (all agents communicating with all) to fully decentralized (all agents communicating with none). Finally, we present the convergence analysis of DOG-IU . Definition 4 (Cumulative Error). For each round t 29044 , we define the cumulative error of DOG-IU ’s reward estimates compared to the true rewards for rounds s∈t−d¯i+1,…,t 29043 12850 \ 29044 8704 29028 _ 29033 8235 28721 24891 … 24891 29044 \ as εa,ti≜∑s=t−d¯i+1tr^a,s(Zkss)−r^a,s(rai,s), 28962 _ 29025 24891 29044 29033 4944 _ 29043 12349 29044 8704 29028 _ 29033 8235 28721 29044 29042 _ 29025 24891 29043 67273472 29018 29043 _ 29035 _ 29043 84054785 8704 29042 _ 29025 24891 29043 67273472 29042 _ 29025 _ 29033 24891 29043 84054785 24891 (13) where rai,s 29042 _ 29025 _ 29033 24891 29043 is the true reward for agent i 29033 ’s action for round s 29043 and Zkss 29018 29043 _ 29035 _ 29043 is i 29033 ’s current estimate of the round s 29043 reward. We also define the maximum cumulative error over the action set as Mti≜maxa∈i|εa,ti|. 29005 _ 29044 29033 _ 29025 12850 29014 _ 29033 \, 69640972 28962 29033 _ 29025 24891 29044 69640972 314 (14) Mti 29005 29033 _ 29044 is the worst-case absolute error (across actions) in the cumulative loss estimates at round t 29044 . Definition 5 (Average Maximum Cumulative Error). For a horizon of T 29012 rounds, define M¯Ti≜1T∑t=1T[Mti]. 29005 _ 29012 29033 28721 29012 4944 _ 29044 12349 28721 29012 28997 67482370 29005 _ 29044 29033 84267779 314 (15) M¯Ti 29005 _ 29012 29033 is a measure of how far DOG-IU ’s internal model of rewards deviates from the true importance weighted rewards on average over the horizon for agent i 29033 . Theorem 1 (Per-Agent Adversarial Bandit with Delayed Feedback and Intermediate Updates). The per-agent regret of Algorithm˜1 with a learning rate η=ln|i||i|T(1+M¯Ti/4) 28945 12349 69640972 29014 _ 29033 69640972 69640972 29014 _ 29033 69640972 29012 67273472 28721 8235 29005 _ 29012 29033 68408078 28724 84054785 against an oblivious adversary satisfies [RegT]T≤O~(|i|M¯TiT), 28997 67482370 29010 29029 29031 _ 29012 84267779 29012 12820 29007 67273472 69640972 29014 _ 29033 69640972 29005 _ 29012 29033 29012 84054785 24891 (16) where M¯Ti 29005 _ 29012 29033 is defined in eq.˜15. In the worst case of reward estimates being as far from the truth as possible, by bounding [Mti]≤|i|d¯i 28997 67482370 29005 _ 29044 29033 84267779 12820 69640972 29014 _ 29033 69640972 29028 _ 29033 , for η=ln|i||i|T(1+|i|d¯i/4) 28945 12349 69640972 29014 _ 29033 69640972 69640972 29014 _ 29033 69640972 29012 67273472 28721 8235 69640972 29014 _ 29033 69640972 29028 _ 29033 68408078 28724 84054785, it holds true [RegT]T≤O~(|i|d¯iT). 28997 67482370 29010 29029 29031 _ 29012 84267779 29012 12820 29007 67273472 69640972 29014 _ 29033 69640972 29028 _ 29033 29012 84054785 314 (17) The bound provided by [30] for the DEW algorithm is [RegTDEW]T≤O~(|i|+d¯iT). 28997 67482370 29010 29029 29031 DEW_ 29012 84267779 29012 12820 29007 67273472 69640972 29014 _ 29033 69640972 8235 29028 _ 29033 29012 84054785 314 (18) This means that even in the worst case of DOG-IU ’s missing action estimates resulting in the worst reward estimates, DOG-IU ’s regret has an extra ||2 69640972 29014 69640972 28722 factor in front of the delay term. However, we can see how DOG-IU ’s regret is controlled by the expected maximum cumulative regret M¯Ti 29005 _ 29012 29033 . This means having better estimates for neighbors’ actions reduces the regret. For example, assume that |i|=4 69640972 29014 _ 29033 69640972 12349 28724 and that for each round in the window s∈t−d¯+1,…,t 29043 12850 \ 29044 8704 29028 8235 28721 24891 … 24891 29044 \ agent i 29033 ’s reward estimates are within Γ.250 314 28722 28725 of the true reward estimates for all actions on average, i.e., |r^a,s(Zkss)−r^a,s(rai,s)|≤Γ.25 69640972 29042 _ 29025 24891 29043 67273472 29018 29043 _ 29035 _ 29043 84054785 8704 29042 _ 29025 24891 29043 67273472 29042 _ 29025 _ 29033 24891 29043 84054785 69640972 12820 0 314 28722 28725 . Then we get an average maximum cumulative error of M¯Ti=d¯i/4 29005 _ 29012 29033 12349 29028 _ 29033 68408078 28724 and the regret term becomes better than DEW ’s regret. Definition 6 (Centralization of Information [33]). 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 (19) 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. Definition 7 (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 (20) κ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\. Theorem 2 (DOG-IU ’s Approximation Performance). Over t∈[T] 29044 12850 67482370 29012 84267779, given the communication network ii∈\ 29006 _ 29033 \_ 29033 12850 29006 , DOG-IU instructs each agent i∈ 29033 12850 29006 to select actions ai,tt∈[T]\ 29025 _ 29033 24891 29044 \_ 29044 12850 67482370 29012 84267779 • If the network is fully centralized, i.e., i=\i 29006 _ 29033 12349 29006 8814 \ 29033 \, [ft(t)]≥11+ˇf[ft()]−~(|||¯|M¯T/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 29005 _ 29012 68408078 29012 84054785_ 28958 67273472 29012 84054785 314 (21) • If the network is fully decentralized, i.e., i=∅ 29006 _ 29033 12349 571 , [ft(t)]≥(1−κf)[ft()]−~(|||¯|M¯T/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 29005 _ 29012 68408078 29012 84054785_ 28959 67273472 29012 84054785 314 (22) • If the network is anything in between fully centralized and fully decentralized, i.e., i⊆\i 29006 _ 29033 12818 29006 8814 \ 29033 \, [ft(t)]≥ 28997 67482370 29030 _ 29044 67273472 28993 _ 29044 84054785 84267779 12821 11+ˇf[ft()] 28721 28721 8235 28948 _ 29030 \, 28997 67482370 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 84267779 (23) −ˇf1+ˇf∑i∈[ft,i(i)]−~(|||¯|M¯T/T)⏟ ̵(T). -42.67912pt 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 29005 _ 29012 68408078 29012 84054785_ 28960 67273472 29012 84054785 314 Particularly, the expectation is due to DOG-IU ’s internal randomness, and O~(⋅) 29007 67273472 8705 84054785 hides log terms and |¯|=maxi∈|i| 69640972 29014 69640972 12349 _ 29033 12850 29006 69640972 29014 _ 29033 69640972 along with M¯T=maxi∈M¯Ti 29005 _ 29012 12349 _ 29033 12850 29006 29005 _ 29012 29033 . As T→∞ 29012 12833 561 , the error terms ϕ(T) 28958 67273472 29012 84054785, χ(T) 28959 67273472 29012 84054785, and ψ(T) 28960 67273472 29012 84054785 in eqs.˜21, 22 and 23 vanish, so the approximation quality of DOG-IU is asymptotically governed by curvature and network structure. The fully connected case achieves the centralized factor 1/(1+κf) 28721 68408078 67273472 28721 8235 28948 _ 29030 84054785, whereas partial decentralization incurs the additional penalty that depends on ft,i 29027 29039 29033 29038 _ 29030 _ 29044 24891 29033 , capturing the loss from limited coordination. Thus, larger coordination neighborhoods improve steady-state performance, while ϕ(T),χ(T),ψ(T) 28958 67273472 29012 84054785 24891 28959 67273472 29012 84054785 24891 28960 67273472 29012 84054785 only describe transient learning error. 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 (6) is 1−κf/e 28721 8704 28948 _ 29030 68408078 29029 [29].111The 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 . Finally, we present the convergence analysis of DOG-IU . Theorem 3 (DOG-IU ’s Convergence Time). DOG-IU achieves ε 28962 -convergence to near-optimal actions after O~(||2|¯|M¯T/ε2) 29007 \! 67273472 69640972 29006 69640972 28722 69640972 29014 69640972 29005 _ 29012 68408078 28962 28722 84054785 rounds. Proof O~(||2|¯|M¯T/ε2) 29007 \! 67273472 69640972 29006 69640972 28722 69640972 29014 69640972 29005 _ 29012 68408078 28962 28722 84054785 rounds are needed to ensure ϕ(T),χ(T),ψ(T)<ε 28958 67273472 29012 84054785 24891 28959 67273472 29012 84054785 24891 28960 67273472 29012 84054785 12604 28962 . ∎ V Asynchronous Formulation We now consider asynchronous agents that run on their own clocks. Particularly, time is indexed by an ideal global (logical) clock t∈[T] 29044 12850 67482370 29012 84267779, but each agent i 29033 runs on its own local clock Ci(⋅) 28995 _ 29033 67273472 8705 84054785, which is a strictly increasing function of physical time, following standard models of distributed systems and clock synchronization [16, 10]. Furthermore, let τi(t)∈ℝ≥Γ 28956 _ 29033 67273472 29044 84054785 12850 29010 _ 12821 0 denote the physical time at which agent i 29033 executes the update associated with logical round t 29044 . Since agents operate on distinct local clocks, the collection τi(t)i=1n\ 28956 _ 29033 67273472 29044 84054785\_ 29033 12349 28721 29038 will never be identical. To this end, we assume a uniform bound on the resulting timing mismatch between the agents: |τi(t)−τj(t)|≤ρ,∀i,j∈,∀t≥1. 69640972 28956 _ 29033 67273472 29044 84054785 8704 28956 _ 29034 67273472 29044 84054785 69640972 12820 28954 24891 568 29033 24891 29034 12850 29006 24891 \ 568 29044 12821 28721 314 (24) This is a reasonable assumption as in distributed systems, local hardware clocks are typically modeled as having bounded drift, while synchronization mechanisms are designed to keep the induced logical-clock skew bounded despite uncertainty in communication latency [16, 32, 6, 10]. Also, similar bounded-clock-error assumptions appear in prior decentralized reachability-based control for distributed CPS [22]. In our asynchronous setting, agent i 29033 receives the round-t 29044 actions of its neighbors at physical times τj(t)+δij(t) 28956 _ 29034 67273472 29044 84054785 8235 28942 29034 _ 29033 67273472 29044 84054785 where τj(t) 28956 _ 29034 67273472 29044 84054785 is the physical time at which agent j∈i 29034 12850 29006 _ 29033 executes its round-t 29044 action and δij(t) 28942 29034 _ 29033 67273472 29044 84054785 is the communication delay for the round t 29044 information transmitted from agent j 29034 to agent i 29033 . Since all agents are running their own clocks, for each t 29044 , every agent will likely execute its action at a different time. Thus, the global objective as in eq.˜6 will lose its meaning. To this end, we define a new version of the time-varying submodular function and a corresponding global objective that accurately represents the asynchronous setting. Definition 8 (Time-Stamped Reward Function). The time-stamped reward function is defined as F:ℝ≥Γ× 2×ℝ≥Γ−→ℝ≥Γ. 28998 \; 24634 \; 29010 _ 12821 0\; 8706 \; 28722 29014 8706 29010 _ 12821 0\; $ 512 $ -3.0mu 545 \; 29010 _ 12821 0 314 (25) F 28998 maps an evaluation time τ∈ℝ≥Γ 28956 12850 29010 _ 12821 0 and a deployment schedule D=(a1,τ1),…,(ak,τk) 28996 12349 \ 67273472 29025 _ 28721 24891 28956 _ 28721 84054785 24891 … 24891 67273472 29025 _ 29035 24891 28956 _ 29035 84054785\, where each aj∈V 29025 _ 29034 12850 29014 is an action deployed at time τj 28956 _ 29034 , to a non-negative reward. Intuitively, because the environment evolves in continuous time and agents execute their actions at different physical times, the reward now depends on two distinct temporal aspects: when the system is observed and when each action took effect. The evaluation time τ 28956 specifies the instant at which the reward is measured, while the deployment timestamps τ1,…,τk 28956 _ 28721 24891 … 24891 28956 _ 29035 inside D 28996 record when each action became active. For example, in target monitoring, F(τ;D) 28998 67273472 28956 24635 28996 84054785 captures the number of targets covered at the instant τ 28956 by cameras that were reoriented at their respective execution times τ1,…,τk 28956 _ 28721 24891 … 24891 28956 _ 29035 . In the synchronous setting where all agents act simultaneously, both aspects collapse to a single time and F 28998 reduces to the standard set function ft 29030 _ 29044 (Remark˜1). To make this reward consistent with the synchronous setting, and to allow for regret analysis, we also have the following submodularity and time-lipschitzness conditions. Assumption 1 (Submodularity). For every fixed evaluation time τ 28956 and fixed deployment times τ1,…,τk 28956 _ 28721 24891 … 24891 28956 _ 29035 , the function F(τ;(a1,τ1),…,(ak,τk)) 28998 67273472 28956 24635 \ 67273472 29025 _ 28721 24891 28956 _ 28721 84054785 24891 … 24891 67273472 29025 _ 29035 24891 28956 _ 29035 84054785\ 84054785 is monotone submodular in the action set a1,…,ak\ 29025 _ 28721 24891 … 24891 29025 _ 29035 \; that is, for any action sets ⊆ℬ⊆ 28993 12818 28994 12818 29014 and any element e∈\ℬ 29029 12850 29014 8814 28994 , F(ø;ℬ∪(e,øe))−F(ø;ℬ) 28998 67273472 28956 24635 \, 28996 _ 28994 8795 \ 67273472\ 29029 \ 24891 28956 _ 29029 84054785\ 84054785 8704 28998 67273472 28956 24635 \, 28996 _ 28994 84054785 (26) ≤F(ø;∪(e,øe))−F(ø;), -116.65646pt 12820 \; 28998 67273472 28956 24635 \, 28996 _ 28993 8795 \ 67273472\ 29029 \ 24891 28956 _ 29029 84054785\ 84054785 8704 28998 67273472 28956 24635 \, 28996 _ 28993 84054785 24891 where 28996 _ 28993 and ℬ 28996 _ 28994 are deployment schedules whose action-set unions equal 28993 and ℬ 28994 respectively, with common actions having the same fixed deployment times. Assumption 2 (Evaluation-Time Lipschitzness). There exists Le>Γ 29004 _ 29029 12606 0 such that for every deployment schedule 28996 and all τ,τ′≥Γ 28956 24891 28956 560 12821 0, |F(τ;)−F(τ′;)|≤Le|τ−τ′|. 69640972 28998 67273472 28956 24635 \, 28996 84054785 8704 28998 67273472 28956 560 24635 \, 28996 84054785 69640972\; 12820 \; 29004 _ 29029 \, 69640972 28956 8704 28956 560 69640972 314 Assumption 3 (Deployment-Time Lipschitzness). There exists Ld>Γ 29004 _ 29028 12606 0 such that if D 28996 and D′ 28996 560 differ only in the deployment time of a single action (i.e., one pair (aj,τj) 67273472 29025 _ 29034 24891 28956 _ 29034 84054785 is replaced by (aj,τj′) 67273472 29025 _ 29034 24891 28956 _ 29034 560 84054785), then for every evaluation time τ 28956 , |F(τ;)−F(τ;′)|≤Ld|τj−τj′|. 69640972 28998 67273472 28956 24635 \, 28996 84054785 8704 28998 67273472 28956 24635 \, 28996 560 84054785 69640972\; 12820 \; 29004 _ 29028 \, 69640972 28956 _ 29034 8704 28956 _ 29034 560 69640972 314 Definition 9 (Asynchronous Global Reward). Fix a global round t 29044 . Without loss of generality, assume that the agents are ordered by execution time, i.e., τ1(t)≤τ2(t)≤⋅≤τ||(t) 28956 _ 28721 67273472 29044 84054785 12820 28956 _ 28722 67273472 29044 84054785 12820 513 513 513 12820 28956 _ 69640972 29006 69640972 67273472 29044 84054785, with ties broken arbitrarily. The cumulative deployment schedule is defined as Γ=ϕ,k=(aj,t,τj(t))j=1k,k=1,…,||, 28996 _0 12349 28958 24891 28996 _ 29035 12349 \ 67273472 29025 _ 29034 24891 29044 24891 \; 28956 _ 29034 67273472 29044 84054785 84054785 \_ 29034 12349 28721 29035 24891 29035 12349 28721 24891 … 24891 69640972 29006 69640972 24891 and the asynchronous global reward for round t 29044 is ft(ai,t,τii∈)≜∑k=1||[F(τk(t);k)−F(τk(t);k−1)], 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 24891 28956 _ 29033 \_ 29033 12850 29006 84054785 4944 _ 29035 12349 28721 69640972 29006 69640972 67482370 28998 67273472 28956 _ 29035 67273472 29044 84054785 24635 \; 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29035 67273472 29044 84054785 24635 \; 28996 _ 29035 8704 28721 84054785 84267779 24891 (27) where F(τ1(t);Γ)=Γ 28998 67273472 28956 _ 28721 67273472 29044 84054785 24635 28996 _0 84054785 12349 0. Each summand is the marginal value of agent k 29035 ’s action, evaluated at its execution time τk(t) 28956 _ 29035 67273472 29044 84054785, against the deployment schedule of all previously executed actions for that round. Remark 1 (Reduction to the Synchronous Setting). If all agents act synchronously, i.e., τi(t)=τ¯(t) 28956 _ 29033 67273472 29044 84054785 12349 28956 67273472 29044 84054785 for all i∈ 29033 12850 29006 , then every deployment schedule k 28996 _ 29035 has all deployment times equal to τ¯(t) 28956 67273472 29044 84054785, and F 28998 reduces to the standard set function ft 29030 _ 29044 . We define the physical time corresponding to the ideal global clock tick as τ¯(t) 28956 67273472 29044 84054785. In this case, (27) telescopes: ft(ai,t, 29030 _ 29044 67273472\,\ 29025 _ 29033 24891 29044 24891 øii∈)=F(ø¯(t);||)−F(ø¯(t);∅) 28956 _ 29033 \_ 29033 12850 29006 84054785 12349 28998 67273472 28956 67273472 29044 84054785 24635 \, 28996 _ 69640972 29006 69640972 84054785 8704 28998 67273472 28956 67273472 29044 84054785 24635 \, 84054785 (28) =ft(ai,ti∈)−ft(∅)=ft(ai,ti∈). 12349 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 8704 29030 _ 29044 67273472 84054785 12349 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 314 recovering the standard global reward. Assumption 4 (Time-Stamped Reward Evaluation). For each global round t 29044 and each agent i∈ 29033 12850 29006 , the marginal reward contributed by agent i 29033 ’s action ai,t 29025 _ 29033 24891 29044 is realized and recorded at the single instant τi(t) 28956 _ 29033 67273472 29044 84054785 at which the action is executed. That is, the asynchronous global reward Rt 29010 _ 29044 (Definition˜9) evaluates each marginal contribution as a snapshot of the time-stamped reward function F 28998 at the executing agent’s clock time, rather than as an accumulation of value over a time interval. Figure 1: Simulation layout and sample snapshot of camera (black vertices) and target (black crosses) configuration. 16 28721 28726 cameras are placed on a 4×4 28724 8706 28724 grid over a 1ΓΓ×1ΓΓ 28721 00 8706 28721 00 workspace. Each camera has a sector FOV with half-angle 3Γ∘ 28723 0 8718 and sensing range of 2Γ 28722 0 units (light gray wedges show the selected heading of each camera). Colored edges denote the one-hop communication links between grid neighbors, with warmer colors representing higher delays. Theorem 4 (Asynchrony Gap Bound). Fix a global round t 29044 and let ft(ai,ti∈) 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 denote the synchronous reward for that round, corresponding to all actions being executed at τ¯t≜maxi∈τi(t) 28956 _ 29044 _ 29033 12850 29006 28956 _ 29033 67273472 29044 84054785. Under Assumptions˜2, 3 and 4, we have |ft(ai,t,øii∈)−ft 69640972 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 24891 28956 _ 29033 \_ 29033 12850 29006 84054785 8704 29030 _ 29044 (ai,ti∈)| 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 69640972 (29) ≤(2Le||+Ld||2)æ. 12820 67273472 28722 \, 29004 _ 29029 \, 69640972 29006 69640972\; 8235 \; 29004 _ 29028 \, 69640972 29006 69640972 28722 84054785\, 28954 314 (a) d¯=1 29028 12349 28721 (b) d¯=5 29028 12349 28725 (c) d¯=1Γ 29028 12349 28721 0 (d) d¯=15 29028 12349 28721 28725 (e) d¯=2Γ 29028 12349 28722 0 (f) d¯=3Γ 29028 12349 28723 0 Figure 2: Coverage over time (mean ±95% 8710 28729 28725 \% CI, n=2Γ 29038 12349 28722 0 runs, running average over 5Γ 28725 0 time steps) for DOG-IU and DOG under increasing maximum one-hop delay d¯ 29028 on a 1ΓΓ×1ΓΓ 28721 00 8706 28721 00 workspace with 16 28721 28726 grid-placed cameras, 8 28728 headings, and 8Γ 28728 0 clustered targets (8 clusters). The gap widens as delay increases, illustrating the benefit of intermediate updates under more severe communication delays. Corollary 1 (Approximation Performance of DOG-IU ). The approximation guarantees of Theorem˜2 continue to hold in the asynchronous setting after replacing the synchronous reward ft(At) 29030 _ 29044 67273472 28993 _ 29044 84054785 by the asynchronous reward ft((ai,t,τi(t))i∈) 29030 _ 29044 67273472\ 67273472 29025 _ 29033 24891 29044 24891 28956 _ 29033 67273472 29044 84054785 84054785\_ 29033 12850 29006 84054785 and subtracting the mismatch term Γæ≜(2Le||+Ld||2)ρ 28672 _ 28954 \; \; 67273472 28722 29004 _ 29029 69640972 29006 69640972 8235 29004 _ 29028 69640972 29006 69640972 28722 84054785 28954 from the right hand side of the bounds. That is, each bound in eqs.˜21, 22 and 23 remains valid with [ft(At)] 28997 67482370 29030 _ 29044 67273472 28993 _ 29044 84054785 84267779 replaced by [ft((ai,t,τi(t))i∈)] 28997 \! 67482370 29030 _ 29044 \! 67273472\ 67273472 29025 _ 29033 24891 29044 24891 28956 _ 29033 67273472 29044 84054785 84054785\_ 29033 12850 29006 84054785 84267779 and with an additional loss of Γæ 28672 _ 28954 that is subtracted from the right-hand side of the bounds. The approximation performance of DOG-IU in the asynchronous setting is identical to its performance in the synchronous setting (where all agents act at the same physical time according to a global logical clock) except the extra Γæ=O(ρ||2) 28672 _ 28954 12349 29007 67273472 28954 69640972 29006 69640972 28722 84054785 term. This term encapsulates the effect of coordination mismatch between the agents. In Definition˜9, the reward is a sum of sequential marginals over agents ordered by execution time. Hence, a timing offset in one agent’s action can perturb not only its own marginal term, but also the context used in the marginal terms of later agents. Assuming a worst-case scenario where this perturbation in one agent’s action affects every other agent’s marginal gain, the asynchrony mismatch term (Γæ 28672 _ 28954 ) would grow with ||2 69640972 29006 69640972 28722 . VI Simulations We evaluate DOG-IU in the asynchronous setting, against the baseline DOG in the synchronous setting, under increasing communication delays, on a target-monitoring task. DOG applies the same EXP3 -style update as DOG-IU but defers all weight updates for round t 29044 until the actions of all neighbors for that round have been received. Setup. We consider ||=16 69640972 29006 69640972 12349 28721 28726 cameras placed on a 1ΓΓ×1ΓΓ 28721 00 8706 28721 00 workspace as shown in Figure˜1. Each camera selects one of |i|=8 69640972 29014 _ 29033 69640972 12349 28728 discrete headings per round. The communication graph connects each agent to its immediate grid neighbors (colored edges in Figure˜1). We restrict the cameras to one-hop communication. Targets. To induce a non-stationary coverage landscape, 8Γ 28728 0 targets are organized into 8 28728 clusters. Each cluster shares a velocity vector of magnitude 1.Γ 28721 314 0 units/step whose heading is resampled every 3Γ 28723 0 steps; individual targets receive i.i.d. Gaussian noise (σ=Γ.ΓΓ5 28955 12349 0 314 00 28725 ) and are reflected at boundaries. Delays and Learning Rate. Communication delays are sampled from a uniform distribution for each round, i.e., delays are i.i.d. di,tj∼UnifΓ,…,d¯ 29028 29034 _ 29033 24891 29044 12824 29013 29038 29033 29030 \0 24891 … 24891 29028 \; e.g., for d¯=1Γ 29028 12349 28721 0, the average delay for any given communication link will be 5 rounds. Both algorithms use a learning rate of ηi=cln|Vi|/((|Vi|+d¯)T) 28945 _ 29033 12349 29027 69640972 29014 _ 29033 69640972 68408078 67273472 67273472 69640972 29014 _ 29033 69640972 8235 29028 84054785 29012 84054785. Since M¯T 29005 _ 29012 cannot generally be known a priori, we use the learning rate of DEW /DOG , which is of a similar order. Additionally, a scaling factor of c=14 29027 12349 28721 28724 amplifies the per-update weight shift, benefiting DOG-IU because its estimation-correction scheme provides more opportunities to react to changes in the environment. This scaling factor is required to make both algorithms adapt to the fast-changing environment. Asynchrony. We run DOG-IU in Asynchronous mode with a timing mismatch bound of ρ=Γ.3 28954 12349 0 314 28723 , that is, the difference between the measurement/action execution times of any two agents will be within Γ.30 314 28723 of the round duration. In terms of the simulation, we run a global clock Tglobal 29012 _ 29031 29036 29039 29026 29025 29036 and for each agent uniformly sample τi∼(tglobal−Γ.15,tglobal+Γ.15) 28956 _ 29033 12824 67273472 29044 _ 29031 29036 29039 29026 29025 29036 8704 0 314 28721 28725 24891 29044 _ 29031 29036 29039 29026 29025 29036 8235 0 314 28721 28725 84054785. Action Estimation. Each agent estimates the missing action for a neighbor as that neighbor’s last known action. Results. Each configuration is evaluated over n=2Γ 29038 12349 28722 0 Monte Carlo runs with T=2ΓΓΓ 29012 12349 28722 000, using the same environment realization (random seed) for both algorithms. Figure 2 reports coverage trajectories (mean ± 95% 8710 \, 28729 28725 \% CI). For d¯=1 29028 12349 28721 (Figure˜2a), DOG-IU and DOG perform identically, confirming that even at small delays DOG-IU matches DOG . As the delays increase to d¯=5 29028 12349 28725 and beyond (Figure˜2b-f), a gap emerges between the two algorithms. At d¯=1Γ 29028 12349 28721 0, DOG defers each round’s update by up to 1Γ 28721 0 steps, during which the target cluster locations can change substantially (1Γ 28721 0 units of displacement). DOG-IU begins updating immediately using reward estimates conditioned on the full neighborhood and corrects as true actions arrive. At d¯=2Γ 29028 12349 28722 0 and d¯=3Γ 29028 12349 28723 0 (Figure˜2e-f), we see that DOG is effectively not able to learn, while DOG-IU is still able to maintain a performance gap of 3-5 targets, which is a roughly 2Γ% 28722 0\% advantage. DOG ’s updates lag by up to 1% 28721 \% of the horizon, while DOG-IU ’s early estimates, despite being potentially incorrect for some rounds, steer the policy toward better actions before the environment shifts. Although Theorem˜4 predicts an additive mismatch penalty due to asynchronous execution, this effect is not pronounced in our current monitoring setup because the environment evolves slowly relative to the bounded timing offset ρ 28954 . When target dynamics are made substantially faster, both DOG-IU and DOG suffer from the limited adaptability of vanilla EXP3 -style updates, making it difficult to isolate the effect of timing mismatch alone. VII Conclusion This paper introduces a distributed online optimization framework for submodular coordination under heterogeneous communication delays and asynchronous local clocks. The key capability provided by DOG-IU is that agents can learn from partial neighborhood information as it arrives, instead of waiting for complete delayed feedback. This reduces the effective delay between acting and learning, enabling more timely coordination in dynamic environments while preserving provable network-level approximation guarantees. The simulations validate our approach. DOG-IU performs similarly to DOG under small delays, but increasingly outperforms DOG on larger delays by adapting earlier to changing conditions. Thus, the advantage of DOG-IU is improved decision quality under delayed communication, rather than a fundamentally different asymptotic convergence rate. Our future work will focus on leveraging adaptive bandit algorithms, such as Optimistic Hedge [23], to improve responsiveness to rapidly changing environments. 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: §IV, Definition 7. [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. [6] R. Fan and N. Lynch (2004) Gradient clock synchronization. In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC ’04, p. 320–327. External Links: Document Cited by: §V. [7] 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. [8] 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, Definition 1. [9] 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. [10] N. M. Freris, S. R. Graham, and P. Kumar (2010) Fundamental limits on synchronizing clocks over networks. IEEE Transactions on Automatic Control (TAC) 56 (6), p. 1352–1364. Cited by: §V, §V. [11] 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. [12] 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. [13] 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. [14] A. Krause and D. Golovin (2012) Submodular function maximization. Tractability: Practical Approaches to Hard Problems 3. Cited by: §I, §I. [15] 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. [16] L. Lamport (1978) Time, clocks, and the ordering of events in a distributed system. Communications of the ACM. Cited by: §V, §V. [17] T. Lattimore and C. Szepesvári (2020) Bandit algorithms. Cambridge University Press. Cited by: Appendix A, Appendix A, §I. [18] 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. [19] 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. [20] P. Nair (2026) Softmax is 1/2 28721 68408078 28722 -lipschitz: a tight bound across all ℓp 352 _ 29040 norms. Transactions on Machine Learning Research. Note: External Links: ISSN 2835-8856, Link Cited by: Appendix A. [21] G. Neu (2015) Explore no more: improved high-probability regret bounds for non-stochastic bandits. Adv. Neu. Info. Proc. Sys. 28. Cited by: §I. [22] L. V. Nguyen, H. Tran, T. T. Johnson, and V. Gupta (2023) Decentralized safe control for distributed cyber-physical systems using real-time reachability analysis. IEEE Transactions on Control of Network Systems 10 (3), p. 1234–1244. Cited by: §V. [23] A. Rakhlin and K. Sridharan (2013) Online learning with predictable sequences. In Conference on Learning Theory, p. 993–1019. Cited by: §VII. [24] 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. [25] 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. [26] 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. [27] 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. [28] 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. [29] 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: §IV. [30] 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: §I, §I-A, §I-A, §IV. [31] 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. [32] J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans (1986) Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control 31 (9), p. 803–812. External Links: Document Cited by: §V. [33] 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, Definition 6. [34] 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. [35] Z. Xu and V. Tzoumas (2026) Distributed online submodular maximization under communication delays: a simultaneous decision-making approach. arXiv preprint:2603.27803. Cited by: §I, §I. [36] Z. Xu and V. Tzoumas (2026) Self-configurable mesh-networks for scalable distributed submodular bandit optimization. arXiv preprint:2602.19366. Cited by: §I. [37] 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. Appendix A Proof of Theorem˜1 We prove the main result by establishing how far off p^t 29040 _ 29044 of DOG-IU is from the reference distribution ptExp3 29040 ^Exp3_ 29044 corresponding to the standard EXP3 bandit algorithm without delays (for the nonstochastic case)[17]. To that end, we choose to work with losses instead of rewards and define the loss and the importance weighted loss estimate as: la,t=1−ra,t,l~a,t=a=atp^a,tlat,t. 29036 _ 29025 24891 29044 12349 28721 8704 29042 _ 29025 24891 29044 24891 29036 _ 29025 24891 29044 12349 28721 \ 29025 12349 29025 _ 29044 \ 29040 _ 29025 24891 29044 29036 _ 29025 _ 29044 24891 29044 314 (30) We also define the cumulative loss up to round t 29044 as L~a,t=∑s=1tl~a,t. 29004 _ 29025 24891 29044 12349 4944 _ 29043 12349 28721 29044 29036 _ 29025 24891 29044 314 (31) Now in our setting, the algorithm uses approximate per-round loss estimates l^a,s(t) 29036 _ 29025 24891 29043 67273472 29044 84054785 for each action i 29033 and past round s≤t 29043 12820 29044 where l^a,t−d¯(t)=l~a,t−d¯, 29036 67273472 29044 84054785_ 29025 24891 29044 8704 29028 12349 29036 _ 29025 24891 29044 8704 29028 24891 (32) that is, our algorithm maintains accurate losses to rounds up to t−d¯ 29044 8704 29028 where d¯ 29028 is the maximum delay for agent i 29033 receiving its neighbors’ information. For action a 29025 , round s 29043 , and current round t≥s 29044 12821 29043 , we define the per-round estimation error as ea,s(t)=l^a,s(t)−l~a,s(t) 29029 67273472 29044 84054785_ 29025 24891 29043 12349 29036 67273472 29044 84054785_ 29025 24891 29043 8704 29036 67273472 29044 84054785_ 29025 24891 29043 (33) where ea,s(t)=Γ 29029 67273472 29044 84054785_ 29025 24891 29043 12349 0 for s≤t−d¯ 29043 12820 29044 8704 29028 . We also define the loss formulation equivalent of the cumulative error (eq.˜13) as εa,t=L^a,t−L~a,t=∑s=t−d¯+1tea,s(t). 28962 _ 29025 24891 29044 12349 29004 _ 29025 24891 29044 8704 29004 _ 29025 24891 29044 12349 4944 _ 29043 12349 29044 8704 29028 8235 28721 29044 29029 67273472 29044 84054785_ 29025 24891 29043 314 (34) Now, we recall the definition of probability distributions for both DOG-IU and the reference as p^a,t 29040 _ 29025 24891 29044 =exp(`a)∑kexp(`k), 12349 67273472 28946 _ 29025 84054785 4944 _ 29035 67273472 28946 _ 29035 84054785 24891 pa,tExp3 29040 _ 29025 24891 29044 ^Exp3 =exp(`a′)∑kexp(`k′), 12349 67273472 28946 _ 29025 560 84054785 4944 _ 29035 67273472 28946 _ 29035 560 84054785 24891 (35) where θa=−ηL^a,t−1 28946 _ 29025 12349 8704 28945 29004 _ 29025 24891 29044 8704 28721 and θa′=−ηL~a,t−1 28946 _ 29025 560 12349 8704 28945 29004 _ 29025 24891 29044 8704 28721 . We also know that the softmax function has a 1/2 28721 68408078 28722 -lipschitz bound irrespective of the lp 29036 _ 29040 norm [20], then we have ‖σ(x)−σ(y)‖1≤12‖x−y‖1. 69640972 69640972 28955 67273472 29048 84054785 8704 28955 67273472 29049 84054785 69640972 69640972_ 28721 12820 28721 28722 69640972 69640972 29048 8704 29049 69640972 69640972_ 28721 314 (36) Combining this inequality with eqs.˜34 and 35 results in ‖p^t(`)−ptExp3(`′)‖1 69640972 69640972 29040 _ 29044 67273472 28946 84054785 8704 29040 _ 29044 ^Exp3 67273472 28946 560 84054785 69640972 69640972_ 28721 ≤12‖ȷL^t−1−ȷL~t−1‖1 12820 28721 28722 69640972 69640972 28945 29004 _ 29044 8704 28721 8704 28945 29004 _ 29044 8704 28721 69640972 69640972_ 28721 (37) ≤ȷ2∑a|”a,t−1|. 12820 28945 28722 4944 _ 29025 69640972 28962 _ 29025 24891 29044 8704 28721 69640972 314 (38) To bound the term above we define Mt≜maxa∈1,…,|||εa,t|=maxa|L^a,t−L~a,t|, 29005 _ 29044 _ 29025 12850 \ 28721 24891 … 24891 69640972 29014 69640972\ 69640972 28962 _ 29025 24891 29044 69640972 12349 _ 29025 69640972 29004 _ 29025 24891 29044 8704 29004 _ 29025 24891 29044 69640972 24891 (39) which is equivalent to the reward based definition of the maximum cumulative loss in eq.˜14. Now we can further bound the expectation of |εa,t| 69640972 28962 _ 29025 24891 29044 69640972 in the worst case, by assuming all estimates of losses are as far from the truth as possible, [|”a,t|] 28997 67482370 69640972 28962 _ 29025 24891 29044 69640972 84267779 =[|∑s=t−d¯+1tea,s(t)|] 12349 28997 67482370 69640972 4944 _ 29043 12349 29044 8704 29028 8235 28721 29044 29029 67273472 29044 84054785_ 29025 24891 29043 69640972 84267779 (40) ≤∑s=t−d¯+1t[|ea,s(t)|] 12820 4944 _ 29043 12349 29044 8704 29028 8235 28721 29044 28997 67482370 69640972 29029 67273472 29044 84054785_ 29025 24891 29043 69640972 84267779 (41) ≤∑s=t−d¯+1t[|l^a,sraw,(t)−la,s|p^a,sa=as] 12820 4944 _ 29043 12349 29044 8704 29028 8235 28721 29044 28997 67482370 69640972 29036 ^raw 24891 67273472 29044 84054785_ 29025 24891 29043 8704 29036 _ 29025 24891 29043 69640972 29040 _ 29025 24891 29043 28721 \ 29025 12349 29025 _ 29043 \ 84267779 (42) ≤∑s=t−d¯+1t[a=asp^a,s] 12820 4944 _ 29043 12349 29044 8704 29028 8235 28721 29044 28997 67482370 28721 \ 29025 12349 29025 _ 29043 \ 29040 _ 29025 24891 29043 84267779 (43) =∑s=t−d¯+1t[[a=asp^a,s|ℱs−1]]=d¯, 12349 4944 _ 29043 12349 29044 8704 29028 8235 28721 29044 28997 67482370 28997 67482370 28721 \ 29025 12349 29025 _ 29043 \ 29040 _ 29025 24891 29043 69640972\, 28998 _ 29043 8704 28721 84267779 84267779 12349 29028 24891 (44) where eq.˜43 comes from the worst case bound due to la,s,l^a,sraw∈[Γ,1] 29036 _ 29025 24891 29043 24891 29036 ^raw_ 29025 24891 29043 12850 674823700 24891 28721 84267779 and eq.˜44 results from applying the law of total expectation and [a=as]=p^a,s 28997 67482370 28721 \ 29025 12349 29025 _ 29043 \ 84267779 12349 29040 _ 29025 24891 29043 with ℱs−1 28998 _ 29043 8704 28721 being the σ 28955 -algebra of all information available to the agent up to round s−1 29043 8704 28721 . We can now bound [Mt] 28997 67482370 29005 _ 29044 84267779 in the worst case as [Mt]=[maxa∈|εa,t|]≤∑a=1||[|εa,t|]≤||d¯. 28997 67482370 29005 _ 29044 84267779 12349 28997 67482370 _ 29025 12850 29014 \, 69640972 28962 _ 29025 24891 29044 69640972 84267779 12820 4944 _ 29025 12349 28721 69640972 29014 69640972 28997 67482370 69640972 28962 _ 29025 24891 29044 69640972 84267779 12820 69640972 29014 69640972 29028 314 (45) Now we express the per-agent regret as RegT=∑t=1Tlat,t−mina∈∑t=1Tla,t. 29010 29029 29031 _ 29012 12349 4944 _ 29044 12349 28721 29012 29036 _ 29025 _ 29044 24891 29044 8704 _ 29025 12850 29014 4944 _ 29044 12349 28721 29012 29036 _ 29025 24891 29044 314 (46) Taking expectation and using lat,t=∑a∈at=ala,t, 29036 _ 29025 _ 29044 24891 29044 12349 4944 _ 29025 12850 29014 28721 \ 29025 _ 29044 12349 29025 \\, 29036 _ 29025 24891 29044 24891 together with the law of total expectation yields [RegT] 28997 67482370 29010 29029 29031 _ 29012 84267779 =∑t=1T[lat,t]−mina∈∑t=1Tla,t 12349 4944 _ 29044 12349 28721 29012 28997 67482370 29036 _ 29025 _ 29044 24891 29044 84267779 8704 _ 29025 12850 29014 4944 _ 29044 12349 28721 29012 29036 _ 29025 24891 29044 (47) =∑t=1T[[∑a∈at=ala,t|ℱt−1]]−mina∈∑t=1Tla,t -30.00005pt 12349 4944 _ 29044 12349 28721 29012 28997 \! 67482370 28997 \! 67482370 4944 _ 29025 12850 29014 28721 \ 29025 _ 29044 12349 29025 \ 29036 _ 29025 24891 29044 \, 69640972\, 28998 _ 29044 8704 28721 84267779 84267779 8704 _ 29025 12850 29014 4944 _ 29044 12349 28721 29012 29036 _ 29025 24891 29044 =∑t=1T[∑a∈pa,tla,t]−mina∈∑t=1Tla,t, -30.00005pt 12349 4944 _ 29044 12349 28721 29012 28997 \! 67482370 4944 _ 29025 12850 29014 29040 _ 29025 24891 29044 29036 _ 29025 24891 29044 84267779 8704 _ 29025 12850 29014 4944 _ 29044 12349 28721 29012 29036 _ 29025 24891 29044 24891 where pa,t=ℙ(at=a|ℱt−1) 29040 _ 29025 24891 29044 12349 29008 67273472 29025 _ 29044 12349 29025 12906 28998 _ 29044 8704 28721 84054785 and ℱt−1 28998 _ 29044 8704 28721 is the σ 28955 -algebra of all information available to the agent up to round t−1 29044 8704 28721 . Taking the difference between the expected regret of DOG-IU ’s and Exp3 and applying eq.˜47 results in [RegT−RegTExp3]=[RegT]−[RegTExp3] 28997 67482370Reg_ 29012 8704 _ 29012 ^Exp3 84267779 12349 28997 67482370Reg_ 29012 84267779 8704 28997 67482370Reg_ 29012 ^Exp3 84267779 =∑t=1T[∑a∈p^a,tla,t]−∑t=1T[∑a∈pa,tExp3la,t] 12349 aligned & 4944 _ 29044 12349 28721 29012 28997 67482370 4944 _ 29025 12850 29014 29040 _ 29025 24891 29044 \, 29036 _ 29025 24891 29044 84267779 8704 4944 _ 29044 12349 28721 29012 28997 67482370 4944 _ 29025 12850 29014 29040 _ 29025 24891 29044 ^Exp3\, 29036 _ 29025 24891 29044 84267779 aligned (48) =∑t=1T[⟨p^t−ptExp3,lt⟩] 12349 4944 _ 29044 12349 28721 29012 28997 67482370 69632778 29040 _ 29044 8704 29040 ^Exp3_ 29044 24891 \, 29036 _ 29044 86414091 84267779 (49) ≤∑t=1T[‖p^t−ptExp3‖1] 12820 4944 _ 29044 12349 28721 29012 28997 67482370 69645069 29040 _ 29044 8704 29040 ^Exp3_ 29044 69645069_ 28721 84267779 (50) ≤12∑t=1Tȷ||2[Mt−1] 12820 28721 28722 4944 _ 29044 12349 28721 29012 28945 69640972 29014 69640972 28722 28997 67482370 29005 _ 29044 8704 28721 84267779 (51) where we used ra,t∈[Γ,1] 29042 _ 29025 24891 29044 12850 674823700 24891 28721 84267779 for all a,t 29025 24891 29044 to obtain equation eq.˜50 and used equation eq.˜38 and eq.˜39 to obtain equation eq.˜51. Substituting the regret bound of the standard Exp3 without delays from [17], we the following regret bound for DOG-IU [RegT]≤ln(||)ȷ+η||T+η||T4M¯T, 28997 67482370Reg_ 29012 84267779 12820 67273472 69640972 29014 69640972 84054785 28945 8235 28945 69640972 29014 69640972 29012 8235 28945 69640972 29014 69640972 29012 28724 29005 _ 29012 24891 (52) where M¯T 29005 _ 29012 is defined in eq.˜15. With a learning rate of η=ln||||T(1+M¯T/4) 28945 12349 69640972 29014 69640972 69640972 29014 69640972 29012 67273472 28721 8235 29005 _ 29012 68408078 28724 84054785, we have an average expected regret of [RegT]T≤O((||(1+M¯T/4))ln||T). 28997 67482370 29010 29029 29031 _ 29012 84267779 29012 12820 29007 \! 67273472 67273472 69640972 29014 69640972 67273472 28721 8235 29005 _ 29012 68408078 28724 84054785 84054785 69640972 29014 69640972 29012 84054785 314 (53) Substituting the worst case bound of [Mt] 28997 67482370 29005 _ 29044 84267779 from eq.˜45 and using a learning rate of η=ln||||T(1+d¯/4) 28945 12349 69640972 29014 69640972 69640972 29014 69640972 29012 67273472 28721 8235 29028 68408078 28724 84054785 results in an average expected regret of [RegT]T≤O((||(1+||d¯/4))ln||T), 28997 67482370 29010 29029 29031 _ 29012 84267779 29012 12820 29007 \! 67273472 67273472 69640972 29014 69640972 67273472 28721 8235 69640972 29014 69640972 29028 68408078 28724 84054785 84054785 69640972 29014 69640972 29012 84054785 24891 (54) completing the proof the theorem. Appendix B Proof of Theorem˜2 We prove the result in Theorem˜2 as follows: ∑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 (55) ≤∑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 (56) ≤∑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 +∑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 (57) ≤∑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 (58) =(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 +ˇ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 (59) ≤(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 (60) ≤(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 (61) where eq.˜55 holds by telescoping the sum, eq.˜56 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˜7, eq.˜57 holds from submodularity, eq.˜58 holds from Equation˜8, eq.˜60 holds since ft 29030 _ 29044 is 2nd-order submodular, and eq.˜61 holds from Definition˜6. Reorganizing eq.˜61 and leveraging theorem˜1, we prove eq.˜23 by the following, [ft()]=1T∑t=1Tft() 28997 67482370 29030 _ 29044 67273472 28993 29007 29008 29012 84054785 84267779 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~(||T[|¯|(1+[Mt]/4)]). 8235 29007 \! 67273472 69640972 29006 69640972 29012 67482370 69640972 29014 69640972 67273472 28721 8235 28997 67482370 29005 _ 29044 84267779 68408078 28724 84054785 84267779 84054785 314 (62) 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.˜21 is proved. Finally, in the fully decentralized case where i=∅ 29006 _ 29033 12349 571 , per eq.˜58, [ft(t)] -5.0pt 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~(||T|¯|(1+[Mt]/4)) 8704 29007 \! 67273472 69640972 29006 69640972 29012 69640972 29014 69640972 67273472 28721 8235 28997 67482370 29005 _ 29044 84267779 68408078 28724 84054785 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~(||T|¯|(1+[Mt]/4)). 8704 29007 \! 67273472 69640972 29006 69640972 29012 69640972 29014 69640972 67273472 28721 8235 28997 67482370 29005 _ 29044 84267779 68408078 28724 84054785 84054785 314 (63) and thus eq.˜22 is proved. ∎ Appendix C Proof of Theorem˜4 and Corollary˜1 Fix a global round t 29044 and define the reference global clock physical time τ¯t≜maxi∈τi(t). 28956 _ 29044 _ 29033 12850 29006 28956 _ 29033 67273472 29044 84054785 314 (64) Let M≜|| 29005 69640972 29006 69640972 and order the agents by execution time so that τ1(t)≤τ2(t)≤⋅≤τM(t), 28956 _ 28721 67273472 29044 84054785 12820 28956 _ 28722 67273472 29044 84054785 12820 513 513 513 12820 28956 _ 29005 67273472 29044 84054785 24891 (65) as in Definition˜9. Define Dk≜(aj,t,τj(t))j=1k,D¯k≜(aj,t,τ¯t)j=1k,DΓ=D¯Γ=∅ 28996 _ 29035 \ 67273472 29025 _ 29034 24891 29044 24891 28956 _ 29034 67273472 29044 84054785 84054785\_ 29034 12349 28721 29035 24891 28996 _ 29035 \ 67273472 29025 _ 29034 24891 29044 24891 28956 _ 29044 84054785\_ 29034 12349 28721 29035 24891 28996 _0 12349 28996 _0 12349 571 . Then, by Definition˜9, ft((ai,t,τi)i∈)=∑k=1M(F(τk(t);Dk)−F(τk(t);Dk−1)), 29030 _ 29044 67273472\ 67273472 29025 _ 29033 24891 29044 24891 28956 _ 29033 84054785\_ 29033 12850 29006 84054785 12349 4944 _ 29035 12349 28721 29005 67273472 28998 67273472 28956 _ 29035 67273472 29044 84054785 24635 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29035 67273472 29044 84054785 24635 28996 _ 29035 8704 28721 84054785 84054785 24891 (66) and by Remark˜1, ft(ai,ti∈)=∑k=1M(F(τ¯t;D¯k)−F(τ¯t;D¯k−1)). 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 12349 4944 _ 29035 12349 28721 29005 67273472 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 84054785 314 (67) Hence, |ft((ai,t,øi)i∈)−ft(ai,ti∈)| 69640972 29030 _ 29044 67273472\ 67273472 29025 _ 29033 24891 29044 24891 28956 _ 29033 84054785\_ 29033 12850 29006 84054785 8704 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 69640972 ≤∑k=1M|(F(øk;Dk)−F(øk;Dk−1)) -100.00015pt 12820 4944 _ 29035 12349 28721 29005 \! 69640972 67273472 28998 67273472 28956 _ 29035 24635 28996 _ 29035 84054785\! 8704 \! 28998 67273472 28956 _ 29035 24635 28996 _ 29035 8704 28721 84054785 84054785 −(F(ø¯t;D¯k)−F(ø¯t;D¯k−1))|. -70.0001pt 8704 67273472 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785\! 8704 \! 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 84054785 69640972 314 (68) Fix any k 29035 . By the triangle inequality, |(F(øk;Dk)−F(øk;Dk−1))−(F(ø¯t;D¯k)−F(ø¯t;D¯k−1))| 69640972 67273472 28998 67273472 28956 _ 29035 24635 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29035 24635 28996 _ 29035 8704 28721 84054785 84054785 8704 67273472 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 84054785 69640972 ≤|F(øk;Dk)−F(ø¯t;Dk)|+|F(øk;Dk−1)−F(ø¯t;Dk−1)| 12820 69640972 28998 67273472 28956 _ 29035 24635 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785 69640972 8235 69640972 28998 67273472 28956 _ 29035 24635 28996 _ 29035 8704 28721 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 69640972 +|F(ø¯t;Dk)−F(ø¯t;D¯k)|+|F(ø¯t;Dk−1)−F(ø¯t;D¯k−1)|. 8235 69640972 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785 69640972 8235 69640972 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 69640972 314 (69) By Assumption˜2 and the timing mismatch assumption |τk(t)−τ¯t|≤ρ 69640972 28956 _ 29035 67273472 29044 84054785 8704 28956 _ 29044 69640972 12820 28954 , |F(øk;Dk)−F(ø¯t;Dk)| 69640972 28998 67273472 28956 _ 29035 24635 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785 69640972 ≤Leæ, 12820 29004 _ 29029 28954 24891 (70) |F(øk;Dk−1)−F(ø¯t;Dk−1)| 69640972 28998 67273472 28956 _ 29035 24635 28996 _ 29035 8704 28721 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 69640972 ≤Leæ. 12820 29004 _ 29029 28954 314 (71) Next, Dk 28996 _ 29035 and D¯k 28996 _ 29035 differ only in the deployment times of the first k 29035 single-action sets. Applying Assumption˜3 gives |F(ø¯t;Dk)−F(ø¯t;D¯k)|≤∑j=1kLd|øj−ø¯t|≤kLdæ, 69640972 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 84054785 69640972 12820 4944 _ 29034 12349 28721 29035 29004 _ 29028 69640972 28956 _ 29034 8704 28956 _ 29044 69640972 12820 29035 29004 _ 29028 28954 24891 (72) |F(ø¯t;Dk−1)−F(ø¯t;D¯k−1)|≤(k−1)Ldæ. 69640972 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 8704 28998 67273472 28956 _ 29044 24635 28996 _ 29035 8704 28721 84054785 69640972 12820 67273472 29035 8704 28721 84054785 29004 _ 29028 28954 314 (73) Therefore, the k 29035 summand is bounded by 2Leρ+(2k−1)Ldρ. 28722 29004 _ 29029 28954 8235 67273472 28722 29035 8704 28721 84054785 29004 _ 29028 28954 314 (74) Summing over k=1,…,M 29035 12349 28721 24891 … 24891 29005 yields |ft((ai,t,øi)i∈)−ft(ai,ti∈)| 69640972 29030 _ 29044 67273472\ 67273472 29025 _ 29033 24891 29044 24891 28956 _ 29033 84054785\_ 29033 12850 29006 84054785 8704 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 69640972 ≤∑k=1M(2Leæ+(2k−1)Ldæ)=2LeMæ+LdM2æ. 12820 4944 _ 29035 12349 28721 29005 67273472 28722 29004 _ 29029 28954 8235 67273472 28722 29035 8704 28721 84054785 29004 _ 29028 28954 84054785 12349 28722 29004 _ 29029 29005 28954 8235 29004 _ 29028 29005 28722 28954 314 (75) Since M=|| 29005 12349 69640972 29006 69640972, we obtain |ft((ai,t,τi)i∈)−ft(ai,ti∈)|≤(2Le||+Ld||2)ρ. 69640972 29030 _ 29044 67273472\ 67273472 29025 _ 29033 24891 29044 24891 28956 _ 29033 84054785\_ 29033 12850 29006 84054785 8704 29030 _ 29044 67273472\ 29025 _ 29033 24891 29044 \_ 29033 12850 29006 84054785 69640972 12820 67273472 28722 29004 _ 29029 69640972 29006 69640972 8235 29004 _ 29028 69640972 29006 69640972 28722 84054785 28954 314 (76) and thus Theorem˜4 is proved. By Theorem˜4, for every round t 29044 , ft((ai,t,τi(t))i∈)≥ft(At)−Γæ. 29030 _ 29044 \! 67273472\ 67273472 29025 _ 29033 24891 29044 24891 28956 _ 29033 67273472 29044 84054785 84054785\_ 29033 12850 29006 84054785\; 12821 \; 29030 _ 29044 67273472 28993 _ 29044 84054785 8704 28672 _ 28954 314 Taking expectations and combining with the corresponding synchronous bound in Theorem˜2 yields the result of Corollary˜1.