Introduction
In standard reinforcement learning (RL), a single agent maximizes an expected sum of stage rewards, which depend on the agent’s current state and action. Extending the single-agent formulation, cooperative multi-agent reinforcement learning (MARL) studies a team of agents that coordinate their actions to maximize a common objective. Each stage reward then depends on the agents’ current joint state and action. A further simplifying assumption is that each stage reward is a sum of the agents’ local rewards [19 ] . These two forms of additivity separate rewards over time and across agents, respectively. However, in many cooperative applications, the objective is not additive over time or across agents. Without these forms of additivity, an optimal policy may depend on the history of all agents.
In this paper, we consider a common monotone submodular reward defined over the visits along the trajectories of all agents. A visit is a time-state pair ( t , s ) (t, s) ( t , s ) indicating that at least one agent is in state s s s at time t t t . Submodularity captures diminishing returns both across agents and over time. This setting is relevant to informative sensing and path planning [10 , 22 ] , cooperative coverage and biodiversity monitoring [16 ] , and multi-agent persistent monitoring [2 , 5 , 20 ] . Traffic monitoring with multiple unmanned aerial vehicles (UAVs) [9 , 12 , 15 ] is a form of persistent monitoring that we use as a running example. In this example, monitoring a road adds less value if it was monitored recently or if another UAV monitors it at the same time. To study such rewards, we formulate a submodular multi-agent Markov decision process (MDP) with decoupled dynamics, in which the next state of each agent depends only on its own current state and action.
Emails: {yasaman.zolfimoselo, nikolas.geroliminis, maryam.kamgarpour}@epfl.ch
Related Work
Submodular maximization and path planning. The greedy algorithm achieves a ( 1 − 1 / e ) (1 - 1/e) ( 1 − 1/ e ) -approximation for maximizing a monotone submodular set function under a cardinality constraint [14 ] . This guarantee improves when the function has total curvature c < 1 c < 1 c < 1 [6 ] . These results were extended to settings where the objective function depends on the order of selection [13 , 23 , 25 ] . In all these works, removing elements from a feasible selection leaves it feasible. In our setting, visits must form trajectories consistent with the dynamics, so removing a visit can make a feasible selection infeasible. Informative path planning maximizes submodular objectives under such constraints [3 , 21 ] . For multiple robots, sequential allocation yields a team guarantee when each robot’s marginal problem under fixed predecessor policies is solved optimally or with an approximation guarantee [1 , 21 , 22 ] . These planning models assume deterministic transition dynamics. Under stochastic dynamics, agents must optimize policies that account for uncertain next states.
Submodular RL. Submodular RL extends these planning models to stochastic dynamics. In this setting, an agent maximizes an expected monotone submodular reward over visits along its trajectory [17 , 24 ] . Global RL generalizes submodular RL to broader classes of trajectory rewards and proposes semi-gradient methods for their optimization [7 ] . For submodular rewards, constant-factor approximation is generally intractable [17 ] , but a ( 1 − c ) (1-c) ( 1 − c ) -factor approximation is possible with total curvature c < 1 c < 1 c < 1 [7 , 17 ] . These results are limited to a single agent. Treating a team as one agent makes the joint state space exponential in the number of agents. Moreover, diminishing returns across agents at the same time step can make the ( 1 − c ) (1-c) ( 1 − c ) guarantee vacuous even for time-additive rewards, as we show in § 3.1 .
Submodular MARL. In the multi-agent setting, Chen et al. [4 ] consider time-additive rewards that are monotone submodular across agents at each stage. Under known decoupled dynamics, they optimize the policies sequentially and obtain a 1 2 \frac{1}{2} 2 1 -approximation in time polynomial in the number of agents. Liu et al. [11 ] study stage rewards defined as marginal gains of a submodular trajectory reward, but their guarantee requires every choice to remain feasible regardless of earlier actions. Hence, the guarantees of Chen et al. [4 ] and Liu et al. [11 ] do not cover rewards with diminishing returns over time when the dynamics constrain future visits.
Multi-agent persistent monitoring. Persistent monitoring coordinates mobile agents to revisit important locations [2 , 5 ] . Closest to our setting, Rezazadeh and Kia [20 ] consider rewards that grow with the time since the last visit and plan over a receding horizon under deterministic dynamics. Their 1 2 \frac{1}{2} 2 1 -factor approximation is relative to the optimum within each planning horizon, not to the full-horizon optimal return.
To our knowledge, no prior work gives a polynomial-time algorithm with a curvature-dependent guarantee for MARL with submodular trajectory rewards when stochastic dynamics constrain future visits. Our formulation addresses this setting under decoupled dynamics and contains the settings of Chen et al. [4 ] and Prajapat et al. [17 ] as special cases, as Remark 1 shows.
Contributions
Building on the above past work, our contributions are summarized as follows.
We introduce a new notion of curvature called pre-window curvature c m c_m c m , which measures the maximum relative reduction in marginal gains caused by visits before an m m m -step window.
Using this notion of curvature, we modify the objective so that stage rewards depend only on the visits of all agents in the last m + 1 m+1 m + 1 steps. Jointly maximizing this objective yields a policy that achieves a ( 1 − c m ) (1-c_m) ( 1 − c m ) -approximation of the optimal return.
We develop Greedy Windowed Policy Optimization (GWPO), which sequentially optimizes each agent’s policy using marginal rewards based on complete predecessor trajectories and its own m m m -step history. For fixed m m m , it runs in polynomial time and achieves the 1 − c m 2 − c m \frac{1-c_m}{2-c_m} 2 − c m 1 − c m approximation guarantee of Theorem 2 relative to the optimal global history-dependent return.
We formulate multi-UAV traffic monitoring as a submodular multi-agent MDP, capturing diminishing returns from repeated monitoring across UAVs and time, and we evaluate GWPO in this setting.
Problem Setting
In this section, we first introduce the notation. We then recall submodularity and curvature, which our analysis builds on. Finally, we define the submodular multi-agent MDP and the optimization problem, and illustrate the framework through traffic monitoring.
Notation
Throughout the paper, we write [ n ] = { 1 , … , n } [n]=\{1,\ldots,n\} [ n ] = { 1 , … , n } for n ≥ 1 n \ge1 n ≥ 1 , and [ 0 ] = ∅ [0]=\emptyset [ 0 ] = ∅ . Bold symbols denote joint quantities over the N N N agents. For example, x \boldsymbol{x} x denotes ( x 1 , … , x N ) (x_1,\ldots,x_N) ( x 1 , … , x N ) . For a function g g g on a product set X × Y \mathcal{X}\times\mathcal{Y} X × Y and z = ( x , y ) \boldsymbol{z}=(x,y) z = ( x , y ) , we write g ( z ) g(\boldsymbol{z}) g ( z ) and g ( x , y ) g(x,y) g ( x , y ) interchangeably. Let P ( X ) \mathcal{P}(\mathcal{X}) P ( X ) denote the probability simplex over a finite set X \mathcal{X} X . Fix a set S \mathcal{S} S . For a set B ⊆ { 0 , 1 , 2 , … } × S B \subseteq\{0,1,2,\ldots\}\times\mathcal{S} B ⊆ { 0 , 1 , 2 , … } × S and integers t t t and t ′ t' t ′ , let
B t : t ′ = { ( u , s ) ∈ B : t ≤ u ≤ t ′ } . (1) B_{t:t'}=\{(u,s)\in B:t\leq u\leq t'\}. \tag*{(1)} B t : t ′ = {( u , s ) ∈ B : t ≤ u ≤ t ′ } . (1)
For t ′ = t t'=t t ′ = t , we write B B B for B t : t B_{t:t} B t : t . For a set B i B_i B i of agent i i i , we write B i , t : t ′ B_{i,t:t'} B i , t : t ′ , and for a tuple B = ( B 1 , … , B N ) \boldsymbol{B}=(B_1,\ldots,B_N) B = ( B 1 , … , B N ) of such sets, we apply this definition componentwise, B t : t ′ = ( B 1 , t : t ′ , … , B N , t : t ′ ) \boldsymbol{B}_{t:t'}=(B_{1,t:t'},\ldots,B_{N,t:t'}) B t : t ′ = ( B 1 , t : t ′ , … , B N , t : t ′ ) .
Submodularity and Curvature
We recall monotone submodular functions and their total curvature.
Definition 1 (Monotone submodular function). Let V \mathcal{V} V be a finite ground set and let F : 2 V → R ≥ 0 F:2^{\mathcal{V}}\to\mathbb{R}_{\ge0} F : 2 V → R ≥ 0 satisfy F ( ∅ ) = 0 F(\varnothing)=0 F ( ∅ ) = 0 . For X , B ⊆ V X,B\subseteq\mathcal{V} X , B ⊆ V , the marginal gain of X X X given B B B is
Δ ( X ∣ B ) = F ( X ∪ B ) − F ( B ) , \Delta(X\mid B)=F(X\cup B)-F(B), Δ ( X ∣ B ) = F ( X ∪ B ) − F ( B ) , abbreviated as Δ ( x ∣ B ) \Delta(x\mid B) Δ ( x ∣ B ) when X = { x } X=\{x\} X = { x } . The function F F F is monotone if Δ ( x ∣ B ) ≥ 0 \Delta(x\mid B)\ge0 Δ ( x ∣ B ) ≥ 0 for every B ⊆ V B\subseteq\mathcal{V} B ⊆ V and x ∈ V x\in\mathcal{V} x ∈ V . It is submodular if
Δ ( x ∣ B ) ≥ Δ ( x ∣ B ′ ) \Delta(x\mid B)\ge\Delta(x\mid B') Δ ( x ∣ B ) ≥ Δ ( x ∣ B ′ ) whenever B ⊆ B ′ B\subseteq B' B ⊆ B ′ and x ∈ V x\in\mathcal{V} x ∈ V .
Submodularity states that marginal gains decrease as B B B grows, but it does not quantify how much Δ ( x ∣ B ) \Delta(x\mid B) Δ ( x ∣ B ) can decrease relative to Δ ( x ∣ ∅ ) = F ( { x } ) \Delta(x\mid\varnothing)=F(\{x\}) Δ ( x ∣ ∅ ) = F ({ x }) . Total curvature measures this worst-case relative decrease.
Definition 2 (Total curvature). The total curvature of a normalized monotone submodular function F F F is
c = 1 − min B ⊆ V , x ∈ V ∖ B F ( { x } ) > 0 Δ ( x ∣ B ) F ( { x } ) . c=1-\min_{\substack{B\subseteq\mathcal{V},\ x\in\mathcal{V}\setminus B\\F(\{x\})>0}}\frac{\Delta(x\mid B)}{F(\{x\})}. c = 1 − B ⊆ V , x ∈ V ∖ B F ({ x }) > 0 min F ({ x }) Δ ( x ∣ B ) . For every B ⊆ V B\subseteq\mathcal{V} B ⊆ V and x ∈ V ∖ B x\in\mathcal{V}\setminus B x ∈ V ∖ B , Δ ( x ∣ B ) ≥ ( 1 − c ) F ( { x } ) \Delta(x\mid B)\ge(1-c)F(\{x\}) Δ ( x ∣ B ) ≥ ( 1 − c ) F ({ x }) , including when F ( { x } ) = 0 F(\{x\})=0 F ({ x }) = 0 . An additive function has c = 0 c=0 c = 0 . At the other extreme, c = 1 c=1 c = 1 occurs exactly when some element with F ( { x } ) > 0 F(\{x\})>0 F ({ x }) > 0 has zero marginal gain in the presence of a set of other elements.
Submodular Multi-Agent MDP
With submodularity and curvature defined, we now introduce the submodular multi-agent MDP on which our method builds.
Definition 3 (Submodular multi-agent MDP). A submodular multi-agent MDP is specified by the tuple
⟨ N , H , S , A , { P i } i ∈ [ N ] , { ρ i } i ∈ [ N ] , F ⟩ , \langle N,H,\mathcal{S},\mathcal{A},\{P_i\}_{i\in[N]},\{\rho_i\}_{i\in[N]},F\rangle, ⟨ N , H , S , A , { P i } i ∈ [ N ] , { ρ i } i ∈ [ N ] , F ⟩ , where N N N denotes the number of agents and H H H is the horizon length. The finite state space of each agent is S \mathcal{S} S , also called the local state space. The joint state space is S = S N \mathcal{S}=\mathcal{S}^{N} S = S N . The finite action space of each agent is A \mathcal{A} A , and the joint action space is A = A N \mathcal{A}=\mathcal{A}^{N} A = A N . The transition dynamics of agent i i i are P i = ( P i , 0 , … , P i , H − 1 ) P_i=(P_{i,0},\ldots,P_{i,H-1}) P i = ( P i , 0 , … , P i , H − 1 ) , where P i , t : S × A → D ( S ) P_{i,t}:\mathcal{S}\times\mathcal{A}\to\mathcal{D}(\mathcal{S}) P i , t : S × A → D ( S ) and P i , t ( ⋅ ∣ s , a ) P_{i,t}(\cdot\mid s,a) P i , t ( ⋅ ∣ s , a ) is the distribution of its state at time t + 1 t+1 t + 1 . The transition dynamics are decoupled, so the joint transition dynamics P = ( P 1 , … , P N ) \mathbf{P}=(P_1,\ldots,P_N) P = ( P 1 , … , P N ) give the joint next-state distribution
P t ( s ′ ∣ s , a ) = ∏ i ∈ [ N ] P i , t ( s i ′ ∣ s i , a i ) . P_t(s'\mid s,a)=\prod_{i\in[N]}P_{i,t}(s_i'\mid s_i,a_i). P t ( s ′ ∣ s , a ) = i ∈ [ N ] ∏ P i , t ( s i ′ ∣ s i , a i ) . The initial state distribution of agent i i i is ρ i ∈ D ( S ) \rho_i\in\mathcal{D}(\mathcal{S}) ρ i ∈ D ( S ) . Initial states are independent, so ρ = ∏ i ∈ [ N ] ρ i \rho=\prod_{i\in[N]}\rho_i ρ = ∏ i ∈ [ N ] ρ i . The common reward is a monotone submodular function F : 2 V → R ≥ 0 F:2^{\mathcal{V}}\to\mathbb{R}_{\ge0} F : 2 V → R ≥ 0 over trajectories . Its ground set V = { 0 , … , H } × S \mathcal{V}=\{0,\ldots,H\}\times\mathcal{S} V = { 0 , … , H } × S contains all possible visits, with V t : t ′ \mathcal{V}_{t:t'} V t : t ′ defined as in (1). We assume that the reward function satisfies F ( B ) > 0 F(B)>0 F ( B ) > 0 for at least one B ⊆ V B\subseteq\mathcal{V} B ⊆ V .
Agent i i i ’s trajectory is the set of its visits,
τ i = { ( t , s i , t ) : 0 ≤ t ≤ H } ⊆ V , \tau_i=\{(t,s_{i,t}):0\le t\le H\}\subseteq\mathcal{V}, τ i = {( t , s i , t ) : 0 ≤ t ≤ H } ⊆ V , and the joint trajectory is τ = ( τ 1 , … , τ N ) \tau=(\tau_1,\ldots,\tau_N) τ = ( τ 1 , … , τ N ) . In set operations we identify a tuple of trajectories with the union of its components. Using the notation in (1), this gives
F ( τ t : t ′ ) : = F ( ⋃ i ∈ [ N ] τ i , t : t ′ ) . F(\tau_{t:t'}) := F\left(\bigcup_{i\in[N]}\tau_{i,t:t'}\right). F ( τ t : t ′ ) := F i ∈ [ N ] ⋃ τ i , t : t ′ . For example, if τ 1 = { ( 0 , s 1 ) } \tau_1=\{(0,s_1)\} τ 1 = {( 0 , s 1 )} and τ 2 = { ( 0 , s 2 ) } \tau_2=\{(0,s_2)\} τ 2 = {( 0 , s 2 )} , then τ = ( τ 1 , τ 2 ) \tau=(\tau_1,\tau_2) τ = ( τ 1 , τ 2 ) is treated as { ( 0 , s 1 ) , ( 0 , s 2 ) } \{(0,s_1),(0,s_2)\} {( 0 , s 1 ) , ( 0 , s 2 )} whenever it appears in a set operation.
The formulation and analysis extend to monotone submodular rewards on the ground set { 0 , … , H − 1 } × S × A \{0,\ldots,H-1\}\times\mathcal{S}\times\mathcal{A} { 0 , … , H − 1 } × S × A by including actions in the trajectories. For simplicity, we present the results using V = { 0 , … , H } × S \mathcal{V}=\{0,\ldots,H\}\times\mathcal{S} V = { 0 , … , H } × S .
Histories and policies. For a memory length m ∈ { 0 , … , H } m\in\{0,\ldots,H\} m ∈ { 0 , … , H } and a time t ∈ { 0 , … , H } t\in\{0,\ldots,H\} t ∈ { 0 , … , H } , the m m m -step history of agent i i i is
h i , t m = ( s i , max ( t − m , 0 ) , … , s i , t − 1 ) ∈ H t m , h^m_{i,t}=(s_{i,\max(t-m,0)},\ldots,s_{i,t-1})\in\mathcal{H}^m_t, h i , t m = ( s i , m a x ( t − m , 0 ) , … , s i , t − 1 ) ∈ H t m ,
where H t m = S min ( t , m ) \mathcal{H}^m_t=\mathcal{S}^{\min(t,m)} H t m = S m i n ( t , m ) . It contains up to m m m states of agent i i i before time t t t . The joint m m m -step history is h t m = ( h 1 , t m , … , h N , t m ) ∈ H t m \mathbf{h}^m_t=(h^m_{1,t},\ldots,h^m_{N,t})\in\mathcal{H}^m_t h t m = ( h 1 , t m , … , h N , t m ) ∈ H t m , where H t m = ( H t m ) N \mathcal{H}^m_t=(\mathcal{H}^m_t)^N H t m = ( H t m ) N . For m = H m=H m = H , the current state s i , t s_{i,t} s i , t and the history h i , t H h^H_{i,t} h i , t H together form the full history ( s i , 0 , … , s i , t ) (s_{i,0},\ldots,s_{i,t}) ( s i , 0 , … , s i , t ) .
For a fixed length m m m , a global policy of agent i i i is a sequence π i = ( π i , 0 , … , π i , H − 1 ) \pi_i=(\pi_{i,0},\ldots,\pi_{i,H-1}) π i = ( π i , 0 , … , π i , H − 1 ) with π i , t : S × H t m → D ( A ) \pi_{i,t}:\mathcal{S}\times\mathcal{H}^m_t\to\mathcal{D}(\mathcal{A}) π i , t : S × H t m → D ( A ) , and Π m \Pi_m Π m denotes the class of such policies. Here, π i , t ( a ∣ s t , h t m ) \pi_{i,t}(a\mid s_t,h^m_t) π i , t ( a ∣ s t , h t m ) denotes the probability that agent i i i takes action a ∈ A a\in\mathcal{A} a ∈ A at time t t t given s t s_t s t and h t m h^m_t h t m . A local policy of agent i i i instead depends only on its local state and m m m -step history ( s i , t , h i , t m ) (s_{i,t},h^m_{i,t}) ( s i , t , h i , t m ) , with π i , t : S × H t m → D ( A ) \pi_{i,t}:\mathcal{S}\times\mathcal{H}^m_t\to\mathcal{D}(\mathcal{A}) π i , t : S × H t m → D ( A ) . We denote the class of such policies by Π m l o c \Pi^{\mathrm{loc}}_m Π m loc . A joint policy is denoted by π = ( π 1 , … , π N ) \boldsymbol{\pi}=(\pi_1,\ldots,\pi_N) π = ( π 1 , … , π N ) , where π i \pi_i π i is a global or local policy of agent i i i . The joint policy at time t t t is π t = ( π 1 , t , … , π N , t ) \boldsymbol{\pi}_t=(\pi_{1,t},\ldots,\pi_{N,t}) π t = ( π 1 , t , … , π N , t ) , and the actions of the agents are denoted given ( s t , h t m ) (s_t,h^m_t) ( s t , h t m ) ,
π t ( a ∣ s t , h t m ) = ∏ i ∈ [ N ] π i , t ( a i ∣ s t , h t m ) . (2) \boldsymbol{\pi}_t(a\mid s_t,h^m_t)=\prod_{i\in[N]}\pi_{i,t}(a_i\mid s_t,h^m_t). \tag*{(2)} π t ( a ∣ s t , h t m ) = i ∈ [ N ] ∏ π i , t ( a i ∣ s t , h t m ) . (2)
We use the notation Π m \Pi_m Π m and Π m l o c \Pi^{\mathrm{loc}}_m Π m loc for the sets of joint global and joint local policies with memory m m m , respectively. The cases m = 0 m=0 m = 0 and m = H m=H m = H give global Markov and global history-dependent policies.
Problem statement. Given a submodular multi-agent MDP, our goal is to find a joint policy π ∈ Π H \boldsymbol{\pi} \in\Pi_H π ∈ Π H that maximizes the expected reward:
J ( π ) = E π , ρ , P [ F ( τ ) ] , π ∗ ∈ arg max π ∈ Π H J ( π ) . (3) J(\boldsymbol{\pi}) = \mathbb{E}_{\boldsymbol{\pi},\rho,\mathbf{P}}[F(\boldsymbol{\tau})], \qquad\boldsymbol{\pi}^{*} \in\arg\max_{\boldsymbol{\pi}\in\Pi_H} J(\boldsymbol{\pi}). \tag*{(3)} J ( π ) = E π , ρ , P [ F ( τ )] , π ∗ ∈ arg π ∈ Π H max J ( π ) . (3)
The expectation is taken over joint trajectories τ \boldsymbol{\tau} τ induced by the policy π \boldsymbol{\pi} π under the initial distribution ρ \rho ρ and the transition dynamics P \mathbf{P} P . We abbreviate the expectation as E τ ∼ π \mathbb{E}_{\boldsymbol{\tau}\sim\boldsymbol{\pi}} E τ ∼ π in the rest of the paper. Similarly, E τ i ∼ π i \mathbb{E}_{\tau_i\sim\pi_i} E τ i ∼ π i denotes expectation under agent i i i ’s local policy π i \pi_i π i , with P i P_i P i and ρ i \rho_i ρ i implicit. We write J ∗ = J ( π ∗ ) J^{*}=J(\boldsymbol{\pi}^{*}) J ∗ = J ( π ∗ ) for the optimal value of (3). Restricting π \boldsymbol{\pi} π to the product form (2) does not reduce J ∗ J^{*} J ∗ , because an optimal policy of this form exists (Lemma 2).
In this work, we assume known transition dynamics { P i } i ∈ [ N ] \{P_i\}_{i\in[N]} { P i } i ∈ [ N ] and initial distributions { ρ i } i ∈ [ N ] \{\rho_i\}_{i\in[N]} { ρ i } i ∈ [ N ] . During policy optimization, we also assume that F ( B ) F(B) F ( B ) can be evaluated exactly for every B ⊆ V B\subseteq\mathcal{V} B ⊆ V .
Remark 1. For N = 1 N=1 N = 1 , our formulation reduces to reinforcement learning with a submodular reward over the agent’s trajectory [17 ] . Chen et al. [4 ] instead consider a multi-agent setting, but their objective is a sum of monotone submodular stage rewards f : 2 S × A → R ≥ 0 f:2^{\mathcal{S}\times\mathcal{A}}\to\mathbb{R}_{\geq0} f : 2 S × A → R ≥ 0 , each evaluated on the state-action pairs of all agents at one time step. Their setting is the special case of our framework with ground set { 0 , … , H − 1 } × S × A \{0,\ldots,H-1\}\times\mathcal{S}\times\mathcal{A} { 0 , … , H − 1 } × S × A and
F ( B ) = ∑ t = 0 H − 1 f ( { ( s , a ) : ( t , s , a ) ∈ B t } ) . F(B)=\sum_{t=0}^{H-1}f\left(\{(s,a):(t,s,a)\in B_t\}\right). F ( B ) = t = 0 ∑ H − 1 f ( {( s , a ) : ( t , s , a ) ∈ B t } ) .
Traffic-Monitoring Example
We illustrate the submodular multi-agent MDP with a traffic-monitoring example used throughout the paper. In this example, the N N N agents are moving UAVs that monitor an urban road network over a horizon of H H H time steps. The network is an M × L M\times L M × L grid with road set E \mathcal{E} E . The local state s ∈ S s\in\mathcal{S} s ∈ S of each UAV is its position at a grid node, and its actions move it to an adjacent node or keep it in place. The transition dynamics and initial state distributions of the UAVs are decoupled, since the UAVs move independently and their initial positions are drawn independently. From position s s s , a UAV monitors the set C ( s ) ⊆ E C(s)\subseteq\mathcal{E} C ( s ) ⊆ E of roads connected to $s. Figure 1 shows C ( s ) C(s) C ( s ) for five positions.
Figure 1. Part of the road grid with five UAV positions s 1 , … , s 5 s_1,\ldots,s_5 s 1 , … , s 5 . For i ≤ 4 i\leq4 i ≤ 4 , the roads C ( s i ) C(s_i) C ( s i ) monitored from s i s_i s i share the color of s i s_i s i . Each dashed road in C ( s 5 ) C(s_5) C ( s 5 ) is colored, so it is also monitored from one of s 1 , … , s 4 s_1,\ldots,s_4 s 1 , … , s 4 .
Monitoring each road e ∈ E e\in\mathcal{E} e ∈ E provides information such as its traffic density and occupancy [12 ] . We call the added value of this information the importance of the road. Before road e e e is first monitored, its importance takes its maximum value w e ≥ 0 w_e\geq0 w e ≥ 0 . When a UAV monitors a road e e e , the importance of the road drops to zero. Its importance then recovers over time as the information becomes outdated. After ℓ \ell ℓ time steps, its
importance is w e α ℓ w_e\alpha_\ell w e α ℓ , where α ℓ = 1 − e − β ℓ \alpha_\ell=1-e^{-\beta\ell} α ℓ = 1 − e − β ℓ and β > 0 \beta>0 β > 0 is the recovery rate.
For a set B ⊆ V B\subseteq\mathcal{V} B ⊆ V and a road e ∈ E e\in\mathcal{E} e ∈ E , the set of times at which road e e e is monitored by visits in B B B is
T e ( B ) = { t : ( t , s ) ∈ B for some s ∈ S with e ∈ C ( s ) } . T_e(B)=\{t:(t,s)\in B\text{ for some }s\in\mathcal{S}\text{ with }e\in C(s)\}. T e ( B ) = { t : ( t , s ) ∈ B for some s ∈ S with e ∈ C ( s )} .
For t ∈ T e ( B ) t\in T_e(B) t ∈ T e ( B ) , let ℓ e ( t ) = t − max { t ′ ∈ T e ( B ) : t ′ < t } \ell_e(t)=t-\max\{t'\in T_e(B):t'<t\} ℓ e ( t ) = t − max { t ′ ∈ T e ( B ) : t ′ < t } be the number of time steps since road e e e was previously monitored. If t t t is the first time in T e ( B ) T_e(B) T e ( B ) , we set ℓ e ( t ) = ∞ \ell_e(t)=\infty ℓ e ( t ) = ∞ and α ∞ = 1 \alpha_\infty=1 α ∞ = 1 . The traffic-monitoring reward is
F ( B ) = ∑ e ∈ E ∑ t ∈ T e ( B ) w e α ℓ e ( t ) . (4) F(B)=\sum_{e\in\mathcal{E}}\sum_{t\in T_e(B)}w_e\alpha_{\ell_e(t)}. \tag*{(4)} F ( B ) = e ∈ E ∑ t ∈ T e ( B ) ∑ w e α ℓ e ( t ) . (4)
Thus, F ( τ ) F(\boldsymbol{\tau}) F ( τ ) is the total value of the information collected by the fleet along its joint trajectory τ \boldsymbol{\tau} τ , and F F F has diminishing returns across agents and over time. For example, when two UAVs monitor a road at the same time, the second UAV adds no new information about that road. To complete the formulation, we show in Appendix C that the reward (4) is monotone submodular for a general class of recovery profiles α ℓ \alpha_\ell α ℓ , and this class includes α ℓ = 1 − e − β ℓ \alpha_\ell=1-e^{-\beta\ell} α ℓ = 1 − e − β ℓ for every β > 0 \beta>0 β > 0 .
Hardness and Curvature
To further motivate our results, we first explain why finding a policy that maximizes J ( π ) J(\boldsymbol{\pi}) J ( π ) in (3) is computationally hard. This hardness justifies restricting the class of rewards to obtain constant-factor guarantees. We then introduce pre-window curvature c m c_m c m , a property of the reward function that our approximation guarantees depend on.
Computational Hardness
Maximizing J J J poses two computational challenges. First, the single-agent case N = 1 N=1 N = 1 admits no constant-factor approximation in polynomial time under standard complexity assumptions, even with deterministic dynamics [17 Theorem 1] . For stochastic dynamics, optimal policies of this case may require history dependence, and representing an arbitrary history-dependent policy can require space exponential in the horizon [17 ] . Second, the joint state and action spaces of N N N agents have sizes ∣ S ∣ N |\mathcal{S}|^{N} ∣ S ∣ N and ∣ A ∣ N |\mathcal{A}|^{N} ∣ A ∣ N , so optimizing directly over them takes time exponential in N N N .
Constant-factor guarantees therefore require further restricting the class of rewards. For a single agent, existing algorithms achieve a ( 1 − c ) (1-c) ( 1 − c ) -approximation for submodular trajectory rewards with total curvature c < 1 c<1 c < 1 [7 , 17 ] . For multiple agents under decoupled dynamics, Chen et al. [4 ] obtain a 1 / 2 1/2 1/2 -approximation for time-additive rewards without any curvature assumption. Our framework contains both settings, so we seek a single curvature condition that yields an approximation guarantee for our problem and recovers or improves the known guarantees when specialized to either setting.
Total curvature does not achieve this goal in the multi-agent setting, since simultaneous visits can make c = 1 c=1 c = 1 even for time-additive rewards. Consider Figure 1 with the reward (4) and w e > 0 w_e>0 w e > 0 for every road e ∈ E e\in E e ∈ E . The visits ( t , s 1 ) , … , ( t , s 4 ) (t,s_1),\ldots,(t,s_4) ( t , s 1 ) , … , ( t , s 4 ) monitor every road in C ( s 5 ) C(s_5) C ( s 5 ) . Thus, x = ( t , s 5 ) x=(t,s_5) x = ( t , s 5 ) has zero marginal gain given these four visits although F ( { x } ) = ∑ e ∈ C ( s 5 ) w e > 0 F(\{x\})=\sum_{e\in C(s_5)}w_e>0 F ({ x }) = ∑ e ∈ C ( s 5 ) w e > 0 , so c = 1 c=1 c = 1 regardless of the choice of α ℓ \alpha_\ell α ℓ in the reward (4). We therefore seek a condition that limits the effect of visits long before the current time on marginal gains.
Pre-Window Curvature
We quantify how visits before an m m m -step window decrease the marginal gain of a current visit. For the ground set V \mathcal{V} V of Definition 3, the m m m -step window at time t t t is V t − m : t − 1 ⊆ V \mathcal{V}_{t-m:t-1}\subseteq\mathcal{V} V t − m : t − 1 ⊆ V (Figure 4 in Appendix B). For fixed x t ∈ V t x_t\in\mathcal{V}_t x t ∈ V t and Z ⊆ V Z\subseteq\mathcal{V} Z ⊆ V , adding visits B ⊆ V 0 : t − m − 1 B\subseteq\mathcal{V}_{0:t-m-1} B ⊆ V 0 : t − m − 1 to Z Z Z changes the marginal gain from Δ ( x t ∣ Z ) \Delta(x_t\mid Z) Δ ( x t ∣ Z ) to Δ ( x t ∣ B ∪ Z ) \Delta(x_t\mid B\cup Z) Δ ( x t ∣ B ∪ Z ) . We measure this decrease relative to Δ ( x t ∣ Z ) \Delta(x_t\mid Z) Δ ( x t ∣ Z ) and exclude cases with Δ ( x t ∣ Z ) = 0 \Delta(x_t\mid Z)=0 Δ ( x t ∣ Z ) = 0 , since monotonicity and submodularity then give Δ ( x t ∣ B ∪ Z ) = 0 \Delta(x_t\mid B\cup Z)=0 Δ ( x t ∣ B ∪ Z ) = 0 . We define pre-window curvature as the largest relative decrease over all such x t x_t x t , Z Z Z , and B B B .
Figure 4. The m m m -step window moving from time t t t to time t + 1 t+1 t + 1 . Each row is the trajectory of one agent, and the arrows are transitions under its dynamics. (a) At time t t t , the window covers times t − m t-m t − m to t − 1 t-1 t − 1 , and earlier visits form the pre-window part. (b) After the transition to time t + 1 t+1 t + 1 , the window shifts by one step, and the visits at time t − m t-m t − m join the pre-window part. Pre-window curvature c m c_m c m bounds how much pre-window visits, of any agent, reduce the marginal gain of a current visit.
Definition 4 (Pre-window curvature). For m ∈ { 0 , … , H } m\in\{0,\ldots,H\} m ∈ { 0 , … , H } , the pre-window curvature of F F F is
c m = 1 − min t , x t , B , Z Δ ( x t ∣ Z ) > 0 Δ ( x t ∣ B ∪ Z ) Δ ( x t ∣ Z ) , (5) c_m=1-\min_{\substack{t,x_t,B,Z\\ \Delta(x_t\mid Z)>0}}\frac{\Delta(x_t\mid B\cup Z)}{\Delta(x_t\mid Z)}, \tag*{(5)} c m = 1 − t , x t , B , Z Δ ( x t ∣ Z ) > 0 min Δ ( x t ∣ Z ) Δ ( x t ∣ B ∪ Z ) , (5)
where the minimum ranges over times t ∈ { 0 , … , H } t\in\{0,\ldots,H\} t ∈ { 0 , … , H } , visits x t ∈ V t x_t\in\mathcal{V}_t x t ∈ V t , and sets B ⊆ V 0 : t − m − 1 B\subseteq\mathcal{V}_{0:t-m-1} B ⊆ V 0 : t − m − 1 and Z ⊆ V Z\subseteq\mathcal{V} Z ⊆ V .
Pre-window curvature satisfies 0 ≤ c m ≤ c 0\leq c_m\leq c 0 ≤ c m ≤ c and is nonincreasing in m m m , with c H = 0 c_H=0 c H = 0 . Moreover, c m = 0 c_m=0 c m = 0 whenever F F F is additive over time, even if overlap across agents makes c c c equal one. We prove these properties in Appendix B.
Returning to the example of Section 2.4, we show that the reward (4) has pre-window curvature c m < 1 c_m<1 c m < 1 for every β > 0 \beta>0 β > 0 . Proposition 3 in Appendix C.2 gives the explicit expression c m = e − β ( m + 1 ) c_m=e^{-\beta(m+1)} c m = e − β ( m + 1 ) for 0 ≤ m < H 0\leq m<H 0 ≤ m < H . Without recovery (β = 0 \beta=0 β = 0 ), the reward (4) values only the first monitoring of each road and has c m = c = 1 c_m=c=1 c m = c = 1 for every m < H m<H m < H . In summary, c m < 1 c_m<1 c m < 1 describes rewards in which visits before an m m m -step window have a limited effect on the marginal gain of a current visit.
Algorithms and Analysis
To address the challenges of Section 3.1, we first approximate the objective J J J by the expected sum of stage rewards that depend only on the current joint state and the joint m m m -step history. The error of this approximation is controlled by the pre-window curvature c m c_m c m , and the maximizer of this approximated objective achieves at least ( 1 − c m ) J ∗ (1-c_m)J^* ( 1 − c m ) J ∗ . However, maximizing this objective over joint policies is still exponential in the number of agents N N N . In Section 4.3, we therefore exploit the decoupled dynamics to optimize the policies of the agents sequentially in polynomial time for fixed m m m . The resulting policies achieve a 1 − c m 2 − c m \frac{1-c_m}{2-c_m} 2 − c m 1 − c m guarantee up to estimation error.
History-Augmented State
We introduce the history-augmented state used to define the finite-horizon MDPs in the next two subsections. We fix a memory length m ∈ { 0 , … , H } m\in\{0,\ldots,H\} m ∈ { 0 , … , H } and write h i , t = h i , t m h_{i,t}=h^m_{i,t} h i , t = h i , t m for the histories of Section 2. At time t t t , the history-augmented state of agent i i i is the pair s ~ i , t = ( s i , t , h i , t ) \tilde{s}_{i,t}=(s_{i,t},h_{i,t}) s ~ i , t = ( s i , t , h i , t ) , which lies in the augmented state space S ~ t = S × H t m \widetilde{\mathcal{S}}_t=\mathcal{S}\times\mathcal{H}_t^m S t = S × H t m . By definition, policies in Π l o c m \Pi_{\mathrm{loc}}^m Π loc m and Π m \Pi_m Π m are Markov policies on s ~ i , t \tilde{s}_{i,t} s ~ i , t and s ~ t ∈ S ~ t = S ~ t N \tilde{s}_t\in\widetilde{\mathcal{S}}_t=\widetilde{\mathcal{S}}_t^N s ~ t ∈ S t = S t N , respectively. For π i ∈ Π l o c m \pi_i\in\Pi_{\mathrm{loc}}^m π i ∈ Π loc m , the state space has ∣ S ~ t ∣ = ∣ S ∣ min ( t , m ) + 1 ≤ ∣ S ∣ m + 1 |\widetilde{\mathcal{S}}_t|=|\mathcal{S}|^{\min(t,m)+1}\leq|\mathcal{S}|^{m+1} ∣ S t ∣ = ∣ S ∣ m i n ( t , m ) + 1 ≤ ∣ S ∣ m + 1 values, compared with ∣ S ∣ t + 1 |\mathcal{S}|^{t+1} ∣ S ∣ t + 1 values for a full history.
The augmented transition dynamics are Markov and remain decoupled across agents. In particular, the next state s i , t + 1 ∼ P i , t ( ⋅ ∣ s i , t , a i , t ) s_{i,t+1}\sim P_{i,t}(\cdot\mid s_{i,t},a_{i,t}) s i , t + 1 ∼ P i , t ( ⋅ ∣ s i , t , a i , t ) depends only on the state and action of agent i i i . The history updates deterministically by appending s i , t s_{i,t} s i , t to h i , t h_{i,t} h i , t , and dropping the oldest entry if its length exceeds m m m . Figure 6 in Appendix D.3 illustrates this update.
Figure 6. History-augmented state of agent i i i with memory length m m m , for t ≥ m t \ge m t ≥ m . The augmented state s ~ i , t \tilde{s}_{i,t} s ~ i , t contains the history h i , t h_{i,t} h i , t (blue) and the current state s i , t s_{i,t} s i , t (orange). The next state s i , t + 1 s_{i,t+1} s i , t + 1 is drawn from P i , t P_{i,t} P i , t , and the history appends s i , t s_{i,t} s i , t and drops the oldest state s i , t − m s_{i,t-m} s i , t − m (dashed).
Since the reward function F F F is defined on sets of visits, we map each history to the visits it determines. The map ν t : H t m → 2 V \nu_t:\mathcal{H}_t^m\to2^{\mathcal{V}} ν t : H t m → 2 V assigns to each history h = ( s max ( t − m , 0 ) , … , s t − 1 ) ∈ H t m h=(s_{\max(t-m,0)},\ldots,s_{t-1})\in\mathcal{H}_t^m h = ( s m a x ( t − m , 0 ) , … , s t − 1 ) ∈ H t m the set of visits
ν t ( h ) = { ( ℓ , s ℓ ) : max ( t − m , 0 ) ≤ ℓ ≤ t − 1 } . \nu_t(h)=\{(\ell,s_\ell):\max(t-m,0)\leq\ell\leq t-1\}. ν t ( h ) = {( ℓ , s ℓ ) : max ( t − m , 0 ) ≤ ℓ ≤ t − 1 } .
For a joint history, ν t ( h t ) = ⋃ i ∈ [ N ] ν t ( h i , t ) \nu_t(h_t)=\bigcup_{i\in[N]}\nu_t(h_{i,t}) ν t ( h t ) = ⋃ i ∈ [ N ] ν t ( h i , t ) . Along a trajectory, ν t ( h i , t ) = τ i , t − m : t − 1 \nu_t(h_{i,t})=\tau_{i,t-m:t-1} ν t ( h i , t ) = τ i , t − m : t − 1 and ν t ( h t ) = τ t − m : t − 1 \nu_t(h_t)=\tau_{t-m:t-1} ν t ( h t ) = τ t − m : t − 1 .
Windowed Objective
Our goal is to approximate Problem (3) by a finite-horizon MDP with additive stage rewards on the joint augmented states. We therefore need stage rewards r t ( s ~ t ) r_t(\tilde{s}_t) r t ( s ~ t ) that depend only on the joint augmented state and whose expected sum under each policy π \pi π approximates J ( π ) J(\pi) J ( π ) . Adding the team visits one time step at a time decomposes F F F over time as
F ( τ ) = ∑ t = 0 H Δ ( τ t ∣ τ 0 : t − 1 ) . (6) F(\tau)=\sum_{t=0}^{H}\Delta(\tau_t\mid\tau_{0:t-1}). \tag*{(6)} F ( τ ) = t = 0 ∑ H Δ ( τ t ∣ τ 0 : t − 1 ) . (6)
The term at time t t t is the marginal gain of the current team visits τ t \tau_t τ t given all earlier visits τ 0 : t − 1 \tau_{0:t-1} τ 0 : t − 1 . The augmented state s ~ t \tilde{s}_t s ~ t determines only the part τ t − m : t − 1 \tau_{t-m:t-1} τ t − m : t − 1 of these earlier visits, so this term is not always a stage reward on the augmented states. We therefore define the stage reward r t : S ~ t → R ≥ 0 r_t:\tilde{\mathcal{S}}_t\to\mathbb{R}_{\ge0} r t : S ~ t → R ≥ 0 as the marginal gain of the current team visits given only the visits ν t ( h t ) \nu_t(h_t) ν t ( h t ) within the m m m -step window,
r t ( s ~ t ) = Δ ( { ( t , s i , t ) : i ∈ [ N ] } ∣ ν t ( h t ) ) . (7) r_t(\tilde{s}_t)=\Delta(\{(t,s_{i,t}):i\in[N]\}\mid\nu_t(h_t)). \tag*{(7)} r t ( s ~ t ) = Δ ({( t , s i , t ) : i ∈ [ N ]} ∣ ν t ( h t )) . (7)
Along a trajectory, r t ( s ~ t ) = Δ ( τ t ∣ τ t − m : t − 1 ) r_t(\tilde{s}_t)=\Delta(\tau_t\mid\tau_{t-m:t-1}) r t ( s ~ t ) = Δ ( τ t ∣ τ t − m : t − 1 ) . Replacing each term of Equation (6) by r t ( s ~ t ) r_t(\tilde{s}_t) r t ( s ~ t ) and taking the expectation gives the windowed objective ,
Φ m ( π ) = E τ ∼ π [ ∑ t = 0 H r t ( s ~ t ) ] . \Phi_m(\pi)=\mathbb{E}_{\tau\sim\pi}\left[\sum_{t=0}^{H}r_t(\tilde{s}_t)\right]. Φ m ( π ) = E τ ∼ π [ t = 0 ∑ H r t ( s ~ t ) ] .
Maximizing Φ m \Phi_m Φ m is thus a finite-horizon MDP problem on the augmented states. This problem has a deterministic optimal policy that lies in Π m \Pi_m Π m [18 ] . Algorithm 2 in Appendix D.3 computes such a policy. It remains to show that Φ m \Phi_m Φ m approximates J J J .
Lemma 1. For every policy π \pi π ,
( 1 − c m ) Φ m ( π ) ≤ J ( π ) ≤ Φ m ( π ) (1-c_m)\Phi_m(\pi)\le J(\pi)\le\Phi_m(\pi) ( 1 − c m ) Φ m ( π ) ≤ J ( π ) ≤ Φ m ( π ) .
Proof sketch. The upper bound holds by submodularity, since r t r_t r t considers only τ t − m : t − 1 ⊆ τ 0 : t − 1 \tau_{t-m:t-1}\subseteq\tau_{0:t-1} τ t − m : t − 1 ⊆ τ 0 : t − 1 . The lower bound holds by the definition of c m c_m c m .
Theorem 1. Let π ′ ∈ arg max π ∈ Π H Φ m ( π ) \pi^\prime\in\arg\max_{\pi\in\Pi_H}\Phi_m(\pi) π ′ ∈ arg max π ∈ Π H Φ m ( π ) . Then
J ( π ′ ) ≥ ( 1 − c m ) J ∗ J(\pi^\prime)\ge(1-c_m)J^* J ( π ′ ) ≥ ( 1 − c m ) J ∗ .
Proof sketch. The guarantee follows from Lemma 1 and the optimality of π ′ \pi^\prime π ′ for Φ m \Phi_m Φ m . We prove both results in Appendix D.2.
For a single agent with m = 0 m=0 m = 0 , the windowed objective is the expected modular reward ∑ x ∈ τ F ( { x } ) \sum_{x\in\tau}F(\{x\}) ∑ x ∈ τ F ({ x }) of Prajapat et al. [17 Proposition 3] , and our proof follows their argument with the factor 1 − c 0 ≥ 1 − c 1-c_0\ge1-c 1 − c 0 ≥ 1 − c . For m = H m=H m = H , c H = 0 c_H=0 c H = 0 and Φ H = J \Phi_H=J Φ H = J , so the theorem yields an optimal policy. However, the MDP has up to ∣ S ∣ N ( m + 1 ) |\mathcal{S}|^N(m+1) ∣ S ∣ N ( m + 1 ) joint augmented states per time step and ∣ A ∣ N |\mathcal{A}|^N ∣ A ∣ N joint actions. This exponential dependence on N N N motivates the sequential policy optimization introduced next.
Sequential Policy Optimization
We adopt the sequential policy optimization approach of prior work [4 , 21 ] to avoid joint optimization. This approach optimizes the policy of one agent at a time while holding predecessor policies fixed. However, the guarantee of Chen et al. [4 ] cannot be applied directly to Φ m \Phi_m Φ m . The reason is that an added agent’s visits within the window can reduce current marginal gains, which violates the required monotonicity assumption. We illustrate this violation with an example in Appendix D.4.
Instead, we sequentially construct local stage rewards using complete predecessor trajectories and each agent’s own m m m -step history. We then use pre-window curvature c m c_m c m to bound the relative overestimate caused by ignoring the agent’s visits before the window, which allows a guarantee relative to the optimal global history-dependent return J ∗ J^* J ∗ .
We optimize the policies of the agents in the order 1 , … , N 1,\ldots,N 1 , … , N . For agent i i i , we fix the predecessor policies π ˉ [ i − 1 ] = ( π ˉ 1 , … , π ˉ i − 1 ) \bar{\pi}_{[i-1]}=(\bar{\pi}_1,\ldots,\bar{\pi}_{i-1}) π ˉ [ i − 1 ] = ( π ˉ 1 , … , π ˉ i − 1 ) computed so far. Even with fixed policies, predecessor trajectories τ [ i − 1 ] \tau_{[i-1]} τ [ i − 1 ] can be random because of stochastic dynamics or random initial states. We therefore take the expectation over τ [ i − 1 ] ∼ π ˉ [ i − 1 ] \tau_{[i-1]}\sim\bar{\pi}_{[i-1]} τ [ i − 1 ] ∼ π ˉ [ i − 1 ] to define the local stage reward r ˉ i , t π ˉ [ i − 1 ] : S ~ t → R ≥ 0 \bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}:\tilde{\mathcal{S}}_t\to\mathbb{R}_{\ge0} r ˉ i , t π ˉ [ i − 1 ] : S ~ t → R ≥ 0 as
r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) = E [ Δ ( ( t , s i , t ) ∣ ν t ( h i , t ) ∪ τ [ i − 1 ] ) ] . (8) \bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})=\mathbb{E}\left[\Delta((t,s_{i,t})\mid\nu_t(h_{i,t})\cup\tau_{[i-1]})\right]. \tag*{(8)} r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) = E [ Δ (( t , s i , t ) ∣ ν t ( h i , t ) ∪ τ [ i − 1 ] ) ] . (8)
For i = 1 i=1 i = 1 , the reward r ˉ 1 , t π ˉ [ 0 ] ( s ~ 1 , t ) = Δ ( ( t , s 1 , t ) ∣ ν t ( h 1 , t ) ) \bar{r}^{\bar{\pi}_{[0]}}_{1,t}(\tilde{s}_{1,t})=\Delta((t,s_{1,t})\mid\nu_t(h_{1,t})) r ˉ 1 , t π ˉ [ 0 ] ( s ~ 1 , t ) = Δ (( t , s 1 , t ) ∣ ν t ( h 1 , t )) is the stage reward (7) with N = 1 N=1 N = 1 . For a policy π i \pi_i π i of agent i i i , the local objective is the expected sum of the rewards r ˉ i , t π ˉ [ i − 1 ] \bar{r}^{\bar{\pi}_{[i-1]}}_{i,t} r ˉ i , t π ˉ [ i − 1 ] along the trajectory τ i \tau_i τ i induced by π i \pi_i π i ,
G ˉ i π ˉ [ i − 1 ] ( π i ) = E τ i ∼ π i [ ∑ t = 0 H r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] . (9) \bar{G}^{\bar{\pi}_{[i-1]}}_i(\pi_i)=\mathbb{E}_{\tau_i\sim\pi_i}\left[\sum_{t=0}^{H}\bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})\right]. \tag*{(9)} G ˉ i π ˉ [ i − 1 ] ( π i ) = E τ i ∼ π i [ t = 0 ∑ H r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] . (9)
As in Section 4.2, maximizing G ˉ i π ˉ [ i − 1 ] \bar{G}^{\bar{\pi}_{[i-1]}}_i G ˉ i π ˉ [ i − 1 ] is an MDP problem on the augmented states of agent i i i . This problem has a deterministic optimal policy that lies in Π m l o c \Pi_m^{\mathrm{loc}} Π m loc .
The exact evaluation of (8) may require summing over up to ∣ S ∣ ( i − 1 ) ( H + 1 ) |\mathcal{S}|^{(i-1)(H+1)} ∣ S ∣ ( i − 1 ) ( H + 1 ) predecessor trajectories. For each agent i ≥ 2 i\ge2 i ≥ 2 , we therefore estimate this expectation using K K K trajectories τ [ i − 1 ] 1 , … , τ [ i − 1 ] K \tau^1_{[i-1]},\ldots,\tau^K_{[i-1]} τ [ i − 1 ] 1 , … , τ [ i − 1 ] K sampled independently under π ˉ [ i − 1 ] \bar{\pi}_{[i-1]} π ˉ [ i − 1 ] ,
r ˉ ^ i , t π ˉ [ i − 1 ] ( s ~ i , t ) = 1 K ∑ k = 1 K Δ ( ( t , s i , t ) ∣ ν t ( h i , t k ) ∪ τ [ i − 1 ] k ) . (10) \hat{\bar{r}}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})=\frac{1}{K}\sum_{k=1}^{K}\Delta((t,s_{i,t})\mid\nu_t(h^k_{i,t})\cup\tau^k_{[i-1]}). \tag*{(10)} r ˉ ^ i , t π ˉ [ i − 1 ] ( s ~ i , t ) = K 1 k = 1 ∑ K Δ (( t , s i , t ) ∣ ν t ( h i , t k ) ∪ τ [ i − 1 ] k ) . (10)
Replacing r ˉ i , t π ˉ [ i − 1 ] \bar{r}^{\bar{\pi}_{[i-1]}}_{i,t} r ˉ i , t π ˉ [ i − 1 ] with r ˉ ^ i , t π ˉ [ i − 1 ] \hat{\bar{r}}^{\bar{\pi}_{[i-1]}}_{i,t} r ˉ ^ i , t π ˉ [ i − 1 ] in (9) defines the empirical local objective G ˉ ^ i π ˉ [ i − 1 ] \hat{\bar{G}}^{\bar{\pi}_{[i-1]}}_i G ˉ ^ i π ˉ [ i − 1 ] . For agent 1, no sampling is required and G ˉ ^ 1 = G ˉ 1 \hat{\bar{G}}_1=\bar{G}_1 G ˉ ^ 1 = G ˉ 1 .
Algorithm 1 GWPO
Require: submodular multi-agent MDP; memory length $m \in \{0,\ldots,H\}$; number of samples $K \ge 1$
1: for $i \in [N]$ do
2: if $i = 1$ then
3: $\bar{r}^{\bar{\pi}[0]}_{1,t}(\tilde{s}_{1,t}) = \Delta((t,s_{1,t}) \mid \nu_t(h_{1,t})) \quad \forall t,\tilde{s}_{1,t}$
4: else
5: $\tau^{1}_{[i-1]},\ldots,\tau^{K}_{[i-1]} \sim \bar{\pi}_{[i-1]}$
6: Estimate $\bar{r}^{\bar{\pi}[i-1]}_{i,t}(\tilde{s})$ by $\hat{r}^{\bar{\pi}[i-1]}_{i,t}(\tilde{s})$ in (10) $\forall t,\tilde{s}$
7: end if
8: $\bar{\pi}_i \leftarrow$ Algorithm 2$(\mathcal{S},\mathcal{A},m,P_i,\hat{r}^{\bar{\pi}[i-1]}_{i,t})$
9: end for
10: return $\bar{\pi} = (\bar{\pi}_1,\ldots,\bar{\pi}_N)$
Greedy Windowed Policy Optimization (GWPO), stated in Algorithm 1, solves each agent’s augmented MDP in turn with any exact finite-horizon MDP solver, such as Algorithm 2. For agent i i i , it maximizes G ^ i π ˉ [ i − 1 ] \hat{G}^{\bar{\pi}[i-1]}_i G ^ i π ˉ [ i − 1 ] given the fixed predecessors’ policies π ˉ [ i − 1 ] \bar{\pi}_{[i-1]} π ˉ [ i − 1 ] , and then fixes π ˉ i \bar{\pi}_i π ˉ i before proceeding to agent i + 1 i+1 i + 1 . During centralized training, GWPO samples the trajectories of the predecessors and evaluates F F F exactly, as assumed in § 2 . Execution is decentralized, since each agent’s policy depends only on its own augmented state.
The guarantee of GWPO depends on the number of agents. For N = 1 N=1 N = 1 , GWPO exactly maximizes Φ m \Phi_m Φ m , so Theorem 1 gives J ( π ˉ ) ≥ ( 1 − c m ) J ∗ J(\bar{\pi}) \ge(1-c_m)J^* J ( π ˉ ) ≥ ( 1 − c m ) J ∗ . For N ≥ 2 N \ge2 N ≥ 2 , the following theorem bounds J ( π ˉ ) J(\bar{\pi}) J ( π ˉ ) relative to J ∗ J^* J ∗ in terms of c m c_m c m and the reward-estimation error.
Theorem 2. Let N ≥ 2 N \ge2 N ≥ 2 and fix m ∈ { 0 , … , H } m \in\{0,\ldots,H\} m ∈ { 0 , … , H } . For ϵ > 0 \epsilon> 0 ϵ > 0 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , choose the number of sampled predecessor trajectories K K K such that
K ≥ R 2 2 ϵ 2 ln 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 δ , (11) K \ge\frac{R^2}{2\epsilon^2}\ln\frac{2(N-1)(H+1)|\mathcal{S}|^{m+1}}{\delta}, \tag*{(11)} K ≥ 2 ϵ 2 R 2 ln δ 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 , (11) where R = max v ∈ V F ( { v } ) R=\max_{v\in V}F(\{v\}) R = max v ∈ V F ({ v }) is the largest reward of a single visit. Then, with probability at least 1 − δ 1-\delta 1 − δ , the joint policy π ˉ \bar{\pi} π ˉ returned by Algorithm 1 satisfies
J ( π ˉ ) ≥ 1 − c m 2 − c m ( J ∗ − 2 ( N − 1 ) ( H + 1 ) ϵ ) . (12) J(\bar{\pi}) \ge\frac{1-c_m}{2-c_m}\left(J^* - 2(N-1)(H+1)\epsilon\right). \tag*{(12)} J ( π ˉ ) ≥ 2 − c m 1 − c m ( J ∗ − 2 ( N − 1 ) ( H + 1 ) ϵ ) . (12)
The approximation factor 1 − c m 2 − c m \frac{1-c_m}{2-c_m} 2 − c m 1 − c m is positive for c m < 1 c_m<1 c m < 1 , equals 1 2 \frac{1}{2} 2 1 at c m = 0 c_m=0 c m = 0 , and is zero at c m = 1 c_m=1 c m = 1 . The additive error comes from GWPO optimizing the estimated rewards r ^ i , t π ˉ [ i − 1 ] \hat{r}^{\bar{\pi}[i-1]}_{i,t} r ^ i , t π ˉ [ i − 1 ] instead of the rewards r i , t π ˉ [ i − 1 ] r^{\bar{\pi}[i-1]}_{i,t} r i , t π ˉ [ i − 1 ] for each agent i ≥ 2 i \ge2 i ≥ 2 and time t t t . By (11), the sample size K K K grows only logarithmically in N N N , H H H , and 1 / δ 1/\delta 1/ δ .
For rewards additive over time, Proposition 1(iv) shows that c m = 0 c_m=0 c m = 0 for every m m m . Therefore, the factor equals 1 2 \frac{1}{2} 2 1 , as in Chen et al. [4, Theorem 1]. The factor 1 − c m 2 − c m \frac{1-c_m}{2-c_m} 2 − c m 1 − c m has the form q 1 + q \frac{q}{1+q} 1 + q q of sequential allocation [22 Theorem 4] with q = 1 − c m q=1-c_m q = 1 − c m . Their theorem assumes a q q q -approximation for the marginal reward of each agent and uses the same policy classes for the returned policies and the optimum. We do not assume such an approximation, and we compare our local policies with the optimal global history-dependent policy.
Proof sketch of Theorem 2. The proof addresses two challenges that do not arise in the time-additive setting [4 ] . First, the optimal policy π ∗ ∈ Π H \pi^* \in\Pi_H π ∗ ∈ Π H may depend on the full joint history, while the policy π ˉ ∈ Π m l o c \bar{\pi} \in\Pi^{\mathrm{loc}}_m π ˉ ∈ Π m loc returned by GWPO uses only the current state and m m m -step history of each agent. Second, the return J ( π ˉ ) J(\bar{\pi}) J ( π ˉ ) is not the sum of the objectives that GWPO maximizes, since the objective of each agent ignores its visits prior to the m m m -step window. To address the first challenge, we consider an arbitrary joint policy π ∈ Π H \pi\in\Pi_H π ∈ Π H and an arbitrary agent i i i . We show that there exists a local policy in Π m l o c \Pi^{\mathrm{loc}}_m Π m loc that reproduces the distribution of the augmented state of agent i i i under π \pi π at every time step. For the second, we use pre-window curvature to lower bound J ( π ˉ ) J(\bar{\pi}) J ( π ˉ ) by the objectives that GWPO maximizes.
The proof proceeds in three steps. First, the optimality gap J ∗ − J ( π ˉ ) J^* - J(\bar{\pi}) J ∗ − J ( π ˉ ) is bounded by the sum of the maximum local objectives of the agents. Second, we bound the suboptimality of maximizing the local objective of each agent by the errors of reward estimation. Following Chen et al. [4 ] , Hoeffding’s inequality and a union bound keep all these errors below ϵ \epsilon ϵ with probability at least 1 − δ 1-\delta 1 − δ . Finally, pre-window curvature lower bounds J ( π ˉ ) J(\bar{\pi}) J ( π ˉ ) by 1 − c m 1-c_m 1 − c m times the sum of the attained local objectives. Together, these three bounds imply (12). Appendix E gives the full proof. □
GWPO achieves the guarantee of Theorem 2 in polynomial time for fixed m m m . We count oracle evaluations and transition samples as unit-cost operations and first consider the cost for a single agent i i i . Sampling K K K trajectories of its at most N − 1 N-1 N − 1 predecessors costs O ( N K H ) O(NKH) O ( N K H ) . Estimating the rewards (10) at all times and augmented states costs O ( H ∣ S ∣ m + 1 K ) O(H|\mathcal{S}|^{m+1}K) O ( H ∣ S ∣ m + 1 K ) . Solving the MDP of agent i i i on its augmented states with Algorithm 2 costs O ( H ∣ S ∣ m + 2 ∣ A ∣ ) O(H|\mathcal{S}|^{m+2}|\mathcal{A}|) O ( H ∣ S ∣ m + 2 ∣ A ∣ ) . Summing over the N N N agents gives the computation time of Algorithm 1,
O ( N H ∣ S ∣ m + 1 ( K + ∣ S ∣ ∣ A ∣ ) + N 2 K H ) . O\left(NH|\mathcal{S}|^{m+1}(K+|\mathcal{S}||\mathcal{A}|)+N^2KH\right). O ( N H ∣ S ∣ m + 1 ( K + ∣ S ∣∣ A ∣ ) + N 2 K H ) .
Numerical Experiments
We empirically studied the return and computation time of GWPO with memory length m m m on the traffic-monitoring example of Section 2.4. Our instance used a 20 × 20 20 \times20 20 × 20 road grid, the horizon H = 20 H=20 H = 20 , and initial positions of the agents sampled independently and uniformly. We first studied how memory affected the return and the computation time of GWPO, and then compared its performance with two baselines. The baselines were Greedy Policy Optimization (GPO) [4 ] and Submodular Policy Optimization (SubPO) [17 ] . GPO optimizes a time-additive objective, and SubPO optimizes global policies by policy gradient. We used SubPO with Markov (SubPO-M) and history-dependent (SubPO-NM) policies. SubPO-NM encodes the history with a recurrent neural network. We evaluated all policies under the reward (4) on 10,000 common initial joint states. Appendix § 13 gives further experimental details.
Figure 2 shows how the memory length affects the return and computation time of GWPO. For N = 20 N = 20 N = 20 agents, increasing memory improved returns over GPO for the non-additive rewards in Figure 2 (a). For the recovery rule α ℓ = 1 − e − β ℓ \alpha_\ell= 1 - e^{-\beta\ell} α ℓ = 1 − e − β ℓ , smaller β \beta β means that road importance recovers more slowly after a visit. Longer memory helped more when recovery was slower, while GWPO approximately matched GPO in the time-additive case α ℓ = 1 \alpha_\ell= 1 α ℓ = 1 . Figure 2 (b) shows that these gains came with higher computation time.
Figure 2. Performance improvement and computational cost of memory in GWPO. (a) Return improvement of GWPO with different memory lengths m m m over GPO [4 ] for N = 20 N = 20 N = 20 agents and different recovery rules. (b) Computation time for different numbers of agents N N N , comparing GWPO with m = 0 , 3 m = 0, 3 m = 0 , 3 and GPO at β = 0.4 \beta= 0.4 β = 0.4 .
Figure 3 compares return gaps relative to GWPO across the number of agents and computation times. With T N T_N T N , GWPO and SubPO achieved comparable returns for N ≤ 6 N \le6 N ≤ 6 , while GWPO achieved higher returns for N ≥ 10 N \ge10 N ≥ 10 . With 20 T N 20T_N 20 T N , both SubPO variants achieved up to 6% higher returns than GWPO for N ≤ 15 N \le15 N ≤ 15 , but lower returns at N = 30 N = 30 N = 30 . Appendix § 13 .§ 4 reports results over five SubPO seeds and their confidence intervals.
Conclusion
We introduced pre-window curvature to quantify how visits before an m m m -step window affect marginal gains in submodular rewards over trajectories. Using this notion, we developed GWPO, which exploits decoupled dynamics to sequentially optimize local policies. For fixed m m m , its computation time is polynomial in the number of agents and the horizon. We established a 1 − c m 2 − c m \frac{1-c_m}{2-c_m} 2 − c m 1 − c m approximation guarantee relative to the optimal global history-dependent return, up to estimation error. We formulated multi-agent traffic monitoring as a submodular multi-agent MDP and evaluated GWPO against the time-additive baseline GPO and SubPO, which optimizes global policies by policy gradient.
Acknowledgements
This work was supported as a part of NCCR Automation, a National Centre of Competence in Research, funded by the Swiss National Science Foundation (grant number 51NF40_225155).
AI use statement
In this work, we used generative AI tools for providing feedback on experimental design, checking proofs and suggesting minor corrections, and assisting with implementing and editing code for numerical experiments. We have not used generative AI tools for developing theoretical models or conceptual frameworks, formulating mathematical claims, providing critical ingredients for proofs, proposing or refining hypotheses, or interpreting results. Generating synthetic datasets, cleaning or reformatting datasets, qualitative or thematic data analysis, and translation are not applicable to this work. Additionally, we used generative AI tools for creating and modifying figures, editing text to improve readability, and finding additional related work. We have reviewed all AI outputs used in the activities mentioned above. LLM-generated code was verified and tested for correctness by the authors. All related work identified using AI tools was read and checked by the authors. The authors checked all AI-edited text and AI-suggested revisions. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI.
Correlated Policies
The class Π H \Pi_H Π H uses the product action distributions in (2) with m = H m = H m = H . We show that allowing joint action distributions that do not factor in this way does not improve the optimal expected reward. The following lemma applies the standard existence result for deterministic optimal policies in finite-horizon MDPs [18 Proposition 4.4.3] to the augmented state ( s t , h t H ) (s_t,h_t^H) ( s t , h t H ) .
Lemma 2. There exists a deterministic policy π ∗ ∈ Π H \pi^* \in\Pi_H π ∗ ∈ Π H that is optimal among all global history-dependent joint policies, including those with correlated actions. Consequently, allowing correlated action distributions does not increase J ∗ J^* J ∗ .
Proof. At each time t ∈ { 0 , … , H − 1 } t \in\{0,\ldots,H-1\} t ∈ { 0 , … , H − 1 } , allow an arbitrary joint action distribution
q t : S × H t H → D ( A ) . q_t : \mathcal{S} \times\mathcal{H}_t^H \to\mathcal{D}(\mathcal{A}). q t : S × H t H → D ( A ) .
For every joint history ( s t , h t H ) (s_t,h_t^H) ( s t , h t H ) , this means that
q t ( a ∣ s t , h t H ) ≥ 0 for all a ∈ A , ∑ a ∈ A q t ( a ∣ s t , h t H ) = 1. q_t(a \mid s_t,h_t^H) \ge0 \quad\text{for all } a \in\mathcal{A}, \qquad\sum_{a \in\mathcal{A}} q_t(a \mid s_t,h_t^H) = 1. q t ( a ∣ s t , h t H ) ≥ 0 for all a ∈ A , a ∈ A ∑ q t ( a ∣ s t , h t H ) = 1.
The joint action distribution q t q_t q t does not necessarily factor across agents as in (2). Taking ( s t , h t H ) (s_t,h_t^H) ( s t , h t H ) as the state yields a finite-horizon MDP. The transition dynamics of this MDP draw the next joint state from P t ( ⋅ ∣ s t , a t ) P_t(\cdot\mid s_t,a_t) P t ( ⋅ ∣ s t , a t ) and update the history by appending s t s_t s t . Its reward is zero at intermediate stages and equals F ( τ ) F(\tau) F ( τ ) at time H H H , when the augmented state determines the full joint trajectory.
Fix optimal policies at time steps t + 1 , … , H − 1 t+1,\ldots,H-1 t + 1 , … , H − 1 . At each joint state and history, the expected return is linear in q t ( ⋅ ∣ s t , h t H ) q_t(\cdot\mid s_t,h_t^H) q t ( ⋅ ∣ s t , h t H ) . Its maximum over the probability simplex D ( A ) \mathcal{D}(\mathcal{A}) D ( A ) is therefore attained at a vertex, which assigns probability one to a single joint action. Backward induction thus yields a deterministic joint policy that is optimal under any initial distribution, including ρ \rho ρ .
Let a t ∗ ( s t , h t H ) a_t^*(s_t,h_t^H) a t ∗ ( s t , h t H ) denote the joint action selected by backward induction, and let a i , t ∗ ( s t , h t H ) a_{i,t}^*(s_t,h_t^H) a i , t ∗ ( s t , h t H ) denote its i i i -th component. For each agent i ∈ [ N ] i \in[N] i ∈ [ N ] , define
π i , t ∗ ( a i ∣ s t , h t H ) = 1 { a i = a i , t ∗ ( s t , h t H ) } . \pi_{i,t}^*(a_i \mid s_t,h_t^H) = \mathbb{1}\{a_i = a_{i,t}^*(s_t,h_t^H)\}. π i , t ∗ ( a i ∣ s t , h t H ) = 1 { a i = a i , t ∗ ( s t , h t H )} .
The product of these policies assigns probability one to the selected joint action. Hence, this optimal policy belongs to Π H \Pi_H Π H , and allowing correlated action distributions does not increase J ∗ J^* J ∗ .
Properties of Pre-Window Curvature
Figure 4 illustrates the m m m -step window and the pre-window part on the trajectories of two agents.
Properties of the Pre-Window Curvature
Proposition 1. For every m ∈ { 0 , … , H } m \in\{0,\ldots,H\} m ∈ { 0 , … , H } :
Proof. i. We first show c m ≥ 0 c_m \ge0 c m ≥ 0 and c ≤ 1 c \le1 c ≤ 1 , and then show c m ≤ c c_m \le c c m ≤ c . Definition 4 restricts the minimum to x t x_t x t and Z Z Z with Δ ( x t ∣ Z ) > 0 \Delta(x_t \mid Z) > 0 Δ ( x t ∣ Z ) > 0 , so every ratio is well defined. Since Z ⊆ B ∪ Z Z \subseteq B \cup Z Z ⊆ B ∪ Z , submodularity gives Δ ( x t ∣ B ∪ Z ) ≤ Δ ( x t ∣ Z ) \Delta(x_t \mid B \cup Z) \le\Delta(x_t \mid Z) Δ ( x t ∣ B ∪ Z ) ≤ Δ ( x t ∣ Z ) , so every ratio is at most 1 and c m ≥ 0 c_m \ge0 c m ≥ 0 . In Definition 2, monotonicity makes the numerator of every ratio nonnegative, so every ratio is at least 0 and c ≤ 1 c \le1 c ≤ 1 .
To show c m ≤ c c_m \le c c m ≤ c , we prove that every ratio in (5) is at least 1 − c 1-c 1 − c . Fix t t t , x t ∈ V t x_t \in\mathcal{V}_t x t ∈ V t , B ⊆ V 0 : t − m − 1 B \subseteq\mathcal{V}_{0:t-m-1} B ⊆ V 0 : t − m − 1 , and Z ⊆ V Z \subseteq\mathcal{V} Z ⊆ V with Δ ( x t ∣ Z ) > 0 \Delta(x_t \mid Z) > 0 Δ ( x t ∣ Z ) > 0 . The element x t x_t x t does not lie in Z Z Z , since otherwise Δ ( x t ∣ Z ) = 0 \Delta(x_t \mid Z) = 0 Δ ( x t ∣ Z ) = 0 . It does not lie in B B B either, since every element of B B B has a time index l < t − m ≤ t l < t-m \le t l < t − m ≤ t . Moreover, submodularity with ∅ ⊆ Z \varnothing\subseteq Z ∅ ⊆ Z and F ( ∅ ) = 0 F(\varnothing) = 0 F ( ∅ ) = 0 gives
F ( { x t } ) = Δ ( x t ∣ ∅ ) ≥ Δ ( x t ∣ Z ) > 0. F(\{x_t\}) = \Delta(x_t \mid\varnothing) \ge\Delta(x_t \mid Z) > 0. F ({ x t }) = Δ ( x t ∣ ∅ ) ≥ Δ ( x t ∣ Z ) > 0.
Hence x t ∈ V ∖ ( B ∪ Z ) x_t \in\mathcal{V} \setminus(B \cup Z) x t ∈ V ∖ ( B ∪ Z ) and F ( { x t } ) > 0 F(\{x_t\}) > 0 F ({ x t }) > 0 . The ratio Δ ( x t ∣ B ∪ Z ) / F ( { x t } ) \Delta(x_t \mid B \cup Z)/F(\{x_t\}) Δ ( x t ∣ B ∪ Z ) / F ({ x t }) is therefore one of the ratios minimized in Definition 2, so it is at least 1 − c 1-c 1 − c . Since 1 − c ≥ 0 1-c \ge0 1 − c ≥ 0 and F ( { x t } ) ≥ Δ ( x t ∣ Z ) F(\{x_t\}) \ge\Delta(x_t \mid Z) F ({ x t }) ≥ Δ ( x t ∣ Z ) , we obtain
Δ ( x t ∣ B ∪ Z ) Δ ( x t ∣ Z ) ≥ ( 1 − c ) F ( { x t } ) Δ ( x t ∣ Z ) ≥ 1 − c . \frac{\Delta(x_t \mid B \cup Z)}{\Delta(x_t \mid Z)} \ge(1-c)\frac{F(\{x_t\})}{\Delta(x_t \mid Z)} \ge1-c. Δ ( x t ∣ Z ) Δ ( x t ∣ B ∪ Z ) ≥ ( 1 − c ) Δ ( x t ∣ Z ) F ({ x t }) ≥ 1 − c .
The minimum in (5) is therefore at least 1 − c 1-c 1 − c , so c m ≤ c c_m \le c c m ≤ c .
ii. Since V 0 : t − m − 2 ⊆ V 0 : t − m − 1 \mathcal{V}_{0:t-m-2} \subseteq\mathcal{V}_{0:t-m-1} V 0 : t − m − 2 ⊆ V 0 : t − m − 1 , replacing m m m by m + 1 m+1 m + 1 shrinks the set of admissible B B B while the rest of the minimization is unchanged. The minimum over a smaller set can only increase, so c m + 1 ≤ c m c_{m+1} \le c_m c m + 1 ≤ c m .
iii. For m = H m = H m = H and any t ∈ { 0 , … , H } t \in\{0,\ldots,H\} t ∈ { 0 , … , H } , we have t − H ≤ 0 t-H \le0 t − H ≤ 0 , so V 0 : t − H − 1 = ∅ \mathcal{V}_{0:t-H-1} = \varnothing V 0 : t − H − 1 = ∅ and B = ∅ B = \varnothing B = ∅ . Every ratio then equals 1, and c H = 0 c_H = 0 c H = 0 .
iv. Suppose F ( X ) = ∑ t = 0 H f t ( X ∩ V t ) F(X) = \sum_{t=0}^{H} f_t(X \cap\mathcal{V}_t) F ( X ) = ∑ t = 0 H f t ( X ∩ V t ) . Adding x t ∈ V t x_t \in\mathcal{V}_t x t ∈ V t changes only the term f t f_t f t , which depends on X ∩ V t X \cap\mathcal{V}_t X ∩ V t . Since B ⊆ V 0 : t − m − 1 B \subseteq\mathcal{V}_{0:t-m-1} B ⊆ V 0 : t − m − 1 is disjoint from V t \mathcal{V}_t V t , we have ( B ∪ Z ) ∩ V t = Z ∩ V t (B \cup Z) \cap\mathcal{V}_t = Z \cap\mathcal{V}_t ( B ∪ Z ) ∩ V t = Z ∩ V t . Hence Δ ( x t ∣ B ∪ Z ) = Δ ( x t ∣ Z ) \Delta(x_t \mid B \cup Z) = \Delta(x_t \mid Z) Δ ( x t ∣ B ∪ Z ) = Δ ( x t ∣ Z ) , every ratio equals one, and c m = 0 c_m = 0 c m = 0 .
Traffic-Monitoring Reward Properties
Proposition 2 gives sufficient conditions on α ℓ \alpha_\ell α ℓ under which the reward (4) of § 2.4 is monotone submodular and has c m < 1 c_m < 1 c m < 1 . Corollary 1 shows that the exponential profile α ℓ = 1 − e − β ℓ \alpha_\ell= 1 - e^{-\beta\ell} α ℓ = 1 − e − β ℓ satisfies these conditions, so the traffic-monitoring reward is monotone submodular. Proposition 3 then computes c m c_m c m in closed form for this profile.
Discretely Concave Recovery Profiles
We call the sequence α = ( α 0 , … , α H ) \alpha= (\alpha_0, \ldots, \alpha_H) α = ( α 0 , … , α H ) the recovery profile. In this subsection, α \alpha α is general rather than α ℓ = 1 − e − β ℓ \alpha_\ell= 1 - e^{-\beta\ell} α ℓ = 1 − e − β ℓ . We call α \alpha α discretely concave if
α ℓ + 1 − α ℓ ≤ α ℓ − α ℓ − 1 , 1 ≤ ℓ < H . (13) \alpha_{\ell+1} - \alpha_\ell\le\alpha_\ell- \alpha_{\ell-1}, \qquad1 \le\ell< H. \tag*{(13)} α ℓ + 1 − α ℓ ≤ α ℓ − α ℓ − 1 , 1 ≤ ℓ < H . (13)
Each passing time step therefore recovers no more than the step before it. The concavity is strict when every inequality is strict.
Proposition 2. Suppose α 0 = 0 \alpha_0 = 0 α 0 = 0 , α ℓ ∈ [ 0 , 1 ] \alpha_\ell\in[0,1] α ℓ ∈ [ 0 , 1 ] for 1 ≤ ℓ ≤ H 1 \le\ell\le H 1 ≤ ℓ ≤ H , and α \alpha α is nondecreasing and discretely concave. Then the reward in (4) is monotone submodular. If α 1 > 0 \alpha_1 > 0 α 1 > 0 and the concavity is strict, then c m < 1 c_m < 1 c m < 1 for every m < H m < H m < H .
Proof. Fix B ⊆ V B \subseteq\mathcal{V} B ⊆ V and consider adding ( t , s ) (t,s) ( t , s ) . The reward (4) is a sum over roads, and each term depends on B B B only through the monitoring times T e ( B ) T_e(B) T e ( B ) . Adding ( t , s ) (t,s) ( t , s ) leaves T e ( B ) T_e(B) T e ( B ) unchanged for e ∉ C ( s ) e \notin C(s) e ∈ / C ( s ) , and replaces it by T e ( B ) ∪ { t } T_e(B) \cup\{t\} T e ( B ) ∪ { t } otherwise. Hence
Δ ( ( t , s ) ∣ B ) = ∑ e ∈ C ( s ) Δ e ( t ∣ B ) , \Delta((t,s)\mid B) = \sum_{e\in C(s)} \Delta_e(t\mid B), Δ (( t , s ) ∣ B ) = e ∈ C ( s ) ∑ Δ e ( t ∣ B ) ,
where Δ e ( t ∣ B ) \Delta_e(t\mid B) Δ e ( t ∣ B ) is road e e e ’s contribution. This contribution is zero if t ∈ T e ( B ) t \in T_e(B) t ∈ T e ( B ) . Otherwise, let p p p and q q q be the nearest monitoring times in T e ( B ) T_e(B) T e ( B ) before and after t t t , when they exist. If p p p exists, let ℓ − = t − p \ell_- = t-p ℓ − = t − p ; if q q q exists, let ℓ + = q − t \ell_+ = q-t ℓ + = q − t . The four cases are
Δ e ( t ∣ B ) = w e { 1 , p , q do not exist , α ℓ − , only p exists , α ℓ + , only q exists , α ℓ − + α ℓ + − α ℓ − + ℓ + , p , q both exist . (14) \Delta_e(t\mid B) = w_e
\begin{cases}
1, & p,q\text{ do not exist},\\
\alpha_{\ell_-}, & \text{only }p\text{ exists},\\
\alpha_{\ell_+}, & \text{only }q\text{ exists},\\
\alpha_{\ell_-}+\alpha_{\ell_+}-\alpha_{\ell_-+\ell_+}, & p,q\text{ both exist}.
\end{cases} \tag*{(14)} Δ e ( t ∣ B ) = w e ⎩ ⎨ ⎧ 1 , α ℓ − , α ℓ + , α ℓ − + α ℓ + − α ℓ − + ℓ + , p , q do not exist , only p exists , only q exists , p , q both exist . (14)
When both p p p and q q q exist, adding ( t , s ) (t,s) ( t , s ) replaces the gap ℓ − + ℓ + \ell_-+\ell_+ ℓ − + ℓ + with the gaps ℓ − \ell_- ℓ − and ℓ + \ell_+ ℓ + .
Since the increments of α \alpha α are nonincreasing by (13) , α ℓ − + ℓ + − α ℓ + ≤ α ℓ − − α 0 = α ℓ − \alpha_{\ell_-+\ell_+}-\alpha_{\ell_+} \le\alpha_{\ell_-}-\alpha_0 = \alpha_{\ell_-} α ℓ − + ℓ + − α ℓ + ≤ α ℓ − − α 0 = α ℓ − . Moreover, α \alpha α is nondecreasing, so α ℓ − + ℓ + ≥ max { α ℓ − , α ℓ + } \alpha_{\ell_-+\ell_+} \ge\max\{\alpha_{\ell_-},\alpha_{\ell_+}\} α ℓ − + ℓ + ≥ max { α ℓ − , α ℓ + } . These inequalities give
0 ≤ α ℓ − + α ℓ + − α ℓ − + ℓ + ≤ min { α ℓ − , α ℓ + } . (15) 0 \le\alpha_{\ell_-}+\alpha_{\ell_+}-\alpha_{\ell_-+\ell_+} \le\min\{\alpha_{\ell_-},\alpha_{\ell_+}\}. \tag*{(15)} 0 ≤ α ℓ − + α ℓ + − α ℓ − + ℓ + ≤ min { α ℓ − , α ℓ + } . (15)
The lower bound shows that the contribution in the last case of (14) is nonnegative. The upper bound shows that it is no greater than the corresponding contribution when only p p p or only q q q exists.
The four cases in (14) differ only in which neighboring monitoring times exist. The convention α ∞ = 1 \alpha_\infty= 1 α ∞ = 1 of § 2.4 removes this distinction. Set ℓ − = ∞ \ell_- = \infty ℓ − = ∞ when p p p does not exist and ℓ + = ∞ \ell_+ = \infty ℓ + = ∞ when q q q does not exist, so that α ℓ − + ℓ + = 1 \alpha_{\ell_-+\ell_+} = 1 α ℓ − + ℓ + = 1 whenever a gap is infinite. Every case of (14) then reads
Δ e ( t ∣ B ) = w e h ( ℓ − , ℓ + ) , h ( ℓ 1 , ℓ 2 ) = α ℓ 1 + α ℓ 2 − α ℓ 1 + ℓ 2 , (16) \Delta_e(t\mid B) = w_e h(\ell_-,\ell_+), \qquad h(\ell_1,\ell_2) = \alpha_{\ell_1}+\alpha_{\ell_2}-\alpha_{\ell_1+\ell_2}, \tag*{(16)} Δ e ( t ∣ B ) = w e h ( ℓ − , ℓ + ) , h ( ℓ 1 , ℓ 2 ) = α ℓ 1 + α ℓ 2 − α ℓ 1 + ℓ 2 , (16)
since h ( ∞ , ∞ ) = 1 h(\infty,\infty)=1 h ( ∞ , ∞ ) = 1 , h ( ℓ 1 , ∞ ) = α ℓ 1 h(\ell_1,\infty)=\alpha_{\ell_1} h ( ℓ 1 , ∞ ) = α ℓ 1 , and h ( ∞ , ℓ 2 ) = α ℓ 2 h(\infty,\ell_2)=\alpha_{\ell_2} h ( ∞ , ℓ 2 ) = α ℓ 2 . The contribution of road e e e therefore depends on B B B only through the two gaps.
The function h h h is nondecreasing in each argument over its domain. For finite ℓ 1 , ℓ 2 \ell_1,\ell_2 ℓ 1 , ℓ 2 with ℓ 1 + ℓ 2 + 1 ≤ H \ell_1+\ell_2+1 \le H ℓ 1 + ℓ 2 + 1 ≤ H ,
h ( ℓ 1 + 1 , ℓ 2 ) − h ( ℓ 1 , ℓ 2 ) = ( α ℓ 1 + 1 − α ℓ 1 ) − ( α ℓ 1 + ℓ 2 + 1 − α ℓ 1 + ℓ 2 ) ≥ 0 h(\ell_1+1,\ell_2)-h(\ell_1,\ell_2) = (\alpha_{\ell_1+1}-\alpha_{\ell_1})-(\alpha_{\ell_1+\ell_2+1}-\alpha_{\ell_1+\ell_2}) \ge0 h ( ℓ 1 + 1 , ℓ 2 ) − h ( ℓ 1 , ℓ 2 ) = ( α ℓ 1 + 1 − α ℓ 1 ) − ( α ℓ 1 + ℓ 2 + 1 − α ℓ 1 + ℓ 2 ) ≥ 0
by discrete concavity. When ℓ 2 = ∞ \ell_2=\infty ℓ 2 = ∞ , h ( ℓ 1 + 1 , ℓ 2 ) − h ( ℓ 1 , ℓ 2 ) ≥ 0 h(\ell_1+1,\ell_2)-h(\ell_1,\ell_2) \ge0 h ( ℓ 1 + 1 , ℓ 2 ) − h ( ℓ 1 , ℓ 2 ) ≥ 0 follows from h ( ℓ 1 , ∞ ) = α ℓ 1 h(\ell_1,\infty)=\alpha_{\ell_1} h ( ℓ 1 , ∞ ) = α ℓ 1 and the monotonicity of α \alpha α . Moreover, h ( ℓ 1 , ℓ 2 ) ≤ α ℓ 2 = h ( ∞ , ℓ 2 ) h(\ell_1,\ell_2) \le\alpha_{\ell_2}=h(\infty,\ell_2) h ( ℓ 1 , ℓ 2 ) ≤ α ℓ 2 = h ( ∞ , ℓ 2 ) , since α ℓ 1 ≤ α ℓ 1 + ℓ 2 \alpha_{\ell_1} \le\alpha_{\ell_1+\ell_2} α ℓ 1 ≤ α ℓ 1 + ℓ 2 . The argument for ℓ 2 \ell_2 ℓ 2 is symmetric.
Monotonicity. By (15) , h ≥ 0 h \ge0 h ≥ 0 for finite gaps, and h ( ℓ 1 , ∞ ) = α ℓ 1 ≥ 0 h(\ell_1,\infty)=\alpha_{\ell_1} \ge0 h ( ℓ 1 , ∞ ) = α ℓ 1 ≥ 0 . Hence Δ ( ( t , s ) ∣ B ) ≥ 0 \Delta((t,s)\mid B) \ge0 Δ (( t , s ) ∣ B ) ≥ 0 , and F F F is monotone.
Submodularity. Let B ⊆ B ′ B \subseteq B' B ⊆ B ′ and ( t , s ) ∉ B ′ (t,s) \notin B' ( t , s ) ∈ / B ′ , and fix e ∈ C ( s ) e \in C(s) e ∈ C ( s ) . If t ∈ T e ( B ′ ) t \in T_e(B') t ∈ T e ( B ′ ) , then Δ e ( t ∣ B ′ ) = 0 ≤ Δ e ( t ∣ B ) \Delta_e(t\mid B')=0 \le\Delta_e(t\mid B) Δ e ( t ∣ B ′ ) = 0 ≤ Δ e ( t ∣ B ) . Otherwise t ∉ T e ( B ) t \notin T_e(B) t ∈ / T e ( B ) as well, since T e ( B ) ⊆ T e ( B ′ ) T_e(B) \subseteq T_e(B') T e ( B ) ⊆ T e ( B ′ ) . Let ( ℓ − , ℓ + ) (\ell_-,\ell_+) ( ℓ − , ℓ + ) and ( ℓ − ′ , ℓ + ′ ) (\ell'_-,\ell'_+) ( ℓ − ′ , ℓ + ′ ) be the gaps under T e ( B ) T_e(B) T e ( B ) and T e ( B ′ ) T_e(B') T e ( B ′ ) . Additional monitoring times can only move the nearest monitoring time on each side closer to t t t , and can only turn an absent neighbor into a present one, so ℓ − ′ ≤ ℓ − \ell'_- \le\ell_- ℓ − ′ ≤ ℓ − and ℓ + ′ ≤ ℓ + \ell'_+ \le\ell_+ ℓ + ′ ≤ ℓ + . By (16) and the monotonicity of h h h ,
Δ e ( t ∣ B ′ ) = w e h ( ℓ − ′ , ℓ + ′ ) ≤ w e h ( ℓ − , ℓ + ) = Δ e ( t ∣ B ) . \Delta_e(t\mid B') = w_e h(\ell'_-,\ell'_+) \le w_e h(\ell_-,\ell_+) = \Delta_e(t\mid B). Δ e ( t ∣ B ′ ) = w e h ( ℓ − ′ , ℓ + ′ ) ≤ w e h ( ℓ − , ℓ + ) = Δ e ( t ∣ B ) .
Summing over e ∈ C ( s ) e \in C(s) e ∈ C ( s ) proves that F F F is submodular.
Curvature. Suppose α 1 > 0 \alpha_1 > 0 α 1 > 0 and the concavity is strict. Since α \alpha α is nondecreasing, α ℓ ≥ α 1 > 0 \alpha_\ell\ge\alpha_1 > 0 α ℓ ≥ α 1 > 0 for every positive gap ℓ \ell ℓ . For positive finite gaps ℓ 1 , ℓ 2 \ell_1,\ell_2 ℓ 1 , ℓ 2 with ℓ 1 + ℓ 2 ≤ H \ell_1+\ell_2 \le H ℓ 1 + ℓ 2 ≤ H , strict discrete concavity gives α ℓ 1 + ℓ 2 − α ℓ 2 < α ℓ 1 − α 0 = α ℓ 1 \alpha_{\ell_1+\ell_2}-\alpha_{\ell_2}<\alpha_{\ell_1}-\alpha_0=\alpha_{\ell_1} α ℓ 1 + ℓ 2 − α ℓ 2 < α ℓ 1 − α 0 = α ℓ 1 . Hence the contribution when both p p p and q q q exist is also positive.
Consider a ratio in (5) with Δ ( x t ∣ Z ) > 0 \Delta(x_t\mid Z)>0 Δ ( x t ∣ Z ) > 0 , where x t = ( t , s ) x_t=(t,s) x t = ( t , s ) . At least one road e ∈ C ( s ) e \in C(s) e ∈ C ( s ) has a positive contribution under Z Z Z . Elements of B B B occur before time t − m t-m t − m , so they cannot add t t t to the monitoring times of road e e e . By (14) , this road still has a positive contribution under B ∪ Z B\cup Z B ∪ Z . Thus, the numerator is positive whenever the denominator is positive. The number of admissible ratios is finite, so their minimum is positive. Therefore, c m < 1 c_m<1 c m < 1 .
Remark. Non-strict discrete concavity alone does not guarantee c m < 1 c_m<1 c m < 1 , even when α 1 > 0 \alpha_1>0 α 1 > 0 . Fix m ≤ H − 2 m\le H-2 m ≤ H − 2 and suppose
α ℓ + 1 − α ℓ = α 1 > 0 , 0 ≤ ℓ ≤ m + 1. \alpha_{\ell+1}-\alpha_\ell=\alpha_1>0,\qquad0\le\ell\le m+1. α ℓ + 1 − α ℓ = α 1 > 0 , 0 ≤ ℓ ≤ m + 1.
Set t = m + 1 t=m+1 t = m + 1 , Z = { ( t + 1 , s ) } Z=\{(t+1,s)\} Z = {( t + 1 , s )} , and B = { ( 0 , s ) } B=\{(0,s)\} B = {( 0 , s )} , where s s s monitors at least one road with w e > 0 w_e>0 w e > 0 . Since t − m = 1 t-m=1 t − m = 1 , B ⊆ V 0 B\subseteq V_0 B ⊆ V 0 is admissible. The marginal gain under Z Z Z is positive. Under B ∪ Z B\cup Z B ∪ Z , the contribution of each road in C ( s ) C(s) C ( s ) is
w e ( α m + 1 + α 1 − α m + 2 ) = 0. w_e(\alpha_{m+1}+\alpha_1-\alpha_{m+2})=0. w e ( α m + 1 + α 1 − α m + 2 ) = 0.
Hence the ratio in (5) is zero, and c m = 1 c_m=1 c m = 1 .
For the exponential profile of § 2.4 , Proposition 2 gives the following result.
Corollary 1. For every β > 0 \beta>0 β > 0 , the traffic-monitoring reward (4) is monotone submodular.
Proof. The exponential profile α ℓ = 1 − e − β ℓ \alpha_\ell=1-e^{-\beta\ell} α ℓ = 1 − e − β ℓ satisfies α 0 = 0 \alpha_0=0 α 0 = 0 , is nondecreasing, and takes values in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Its increments
α ℓ + 1 − α ℓ = e − β ℓ ( 1 − e − β ) \alpha_{\ell+1}-\alpha_\ell=e^{-\beta\ell}(1-e^{-\beta}) α ℓ + 1 − α ℓ = e − β ℓ ( 1 − e − β )
are strictly decreasing in ℓ \ell ℓ , so α \alpha α is strictly discretely concave. Proposition 2 gives the claim.
Pre-Window Curvature of the Exponential Profile
Proposition 3. For every β > 0 \beta>0 β > 0 , the traffic-monitoring reward (4) has pre-window curvature
c m = e − β ( m + 1 ) , 0 ≤ m < H . (17) c_m=e^{-\beta(m+1)},\qquad0\le m<H. \tag*{(17)} c m = e − β ( m + 1 ) , 0 ≤ m < H . (17)
Proof. We first show that every ratio Δ ( x t ∣ B ∪ Z ) / Δ ( x t ∣ Z ) \Delta(x_t\mid B\cup Z)/\Delta(x_t\mid Z) Δ ( x t ∣ B ∪ Z ) /Δ ( x t ∣ Z ) in (5) is at least α m + 1 \alpha_{m+1} α m + 1 , and then show that this bound is attained. Fix x t = ( t , s ) x_t=(t,s) x t = ( t , s ) and a road e ∈ C ( s ) e\in C(s) e ∈ C ( s ) . Let ℓ − \ell_- ℓ − and ℓ + \ell_+ ℓ + be the gaps to the nearest monitoring times of e e e in Z Z Z before and after t t t , and let ℓ B \ell_B ℓ B be the gap to the nearest monitoring time of e e e in B B B . Set a gap to infinity when the corresponding monitoring time does not exist. Since B B B contains only elements before time t − m t-m t − m , ℓ B ≥ m + 1 \ell_B\ge m+1 ℓ B ≥ m + 1 . Thus, adding B B B changes ℓ − \ell_- ℓ − to min { ℓ − , ℓ B } \min\{\ell_-,\ell_B\} min { ℓ − , ℓ B } and leaves ℓ + \ell_+ ℓ + unchanged. Figure 5 illustrates these monitoring times.
Figure 5. Monitoring times of road e e e around the added element x t = ( t , s ) x_t=(t,s) x t = ( t , s ) . Filled circles denote monitoring times from Z Z Z , the open square denotes the nearest monitoring time from B B B , and the cross denotes x t x_t x t . Elements of B B B occur before time t − m t-m t − m , so adding B B B changes the earlier gap from ℓ − \ell_- ℓ − to min { ℓ − , ℓ B } \min\{\ell_-,\ell_B\} min { ℓ − , ℓ B } and leaves the later gap ℓ + \ell_+ ℓ + unchanged.
For finite gaps ℓ − \ell_- ℓ − and ℓ + \ell_+ ℓ + , the exponential profile satisfies
α ℓ − + α ℓ + − α ℓ − + ℓ + = ( 1 − e − β ℓ − ) ( 1 − e − β ℓ + ) = α ℓ − α ℓ + . \alpha_{\ell_-}+\alpha_{\ell_+}-\alpha_{\ell_-+\ell_+}=(1-e^{-\beta\ell_-})(1-e^{-\beta\ell_+})=\alpha_{\ell_-}\alpha_{\ell_+}. α ℓ − + α ℓ + − α ℓ − + ℓ + = ( 1 − e − β ℓ − ) ( 1 − e − β ℓ + ) = α ℓ − α ℓ + .
With the convention α ∞ = 1 \alpha_\infty=1 α ∞ = 1 , the four cases of (14) for t ∉ T e ( Z ) t\notin T_e(Z) t ∈ / T e ( Z ) can therefore be written as
Δ e ( t ∣ Z ) = w e α ℓ − α ℓ + . (18) \Delta_e(t\mid Z)=w_e\alpha_{\ell_-}\alpha_{\ell_+}. \tag*{(18)} Δ e ( t ∣ Z ) = w e α ℓ − α ℓ + . (18)
Consider any admissible ( t , x t , B , Z ) (t,x_t,B,Z) ( t , x t , B , Z ) in Definition 4, so that Δ ( x t ∣ Z ) > 0 \Delta(x_t\mid Z)>0 Δ ( x t ∣ Z ) > 0 . For each road with Δ e ( t ∣ Z ) > 0 \Delta_e(t\mid Z)>0 Δ e ( t ∣ Z ) > 0 , (18) gives
Δ e ( t ∣ B ∪ Z ) Δ e ( t ∣ Z ) = α min { ℓ − , ℓ B } α ℓ − = { 1 , ℓ B ≥ ℓ − , α ℓ B / α ℓ − , ℓ B < ℓ − . \frac{\Delta_e(t\mid B\cup Z)}{\Delta_e(t\mid Z)}
=\frac{\alpha_{\min\{\ell_-,\ell_B\}}}{\alpha_{\ell_-}}
=\begin{cases}
1, & \ell_B\ge\ell_-,\\
\alpha_{\ell_B}/\alpha_{\ell_-}, & \ell_B<\ell_-.
\end{cases} Δ e ( t ∣ Z ) Δ e ( t ∣ B ∪ Z ) = α ℓ − α m i n { ℓ − , ℓ B } = { 1 , α ℓ B / α ℓ − , ℓ B ≥ ℓ − , ℓ B < ℓ − .
Both cases are at least α m + 1 \alpha_{m+1} α m + 1 : the first follows from α m + 1 ≤ 1 \alpha_{m+1}\le1 α m + 1 ≤ 1 , and the second from α ℓ − ≤ 1 \alpha_{\ell_-}\le1 α ℓ − ≤ 1 and α ℓ B ≥ α m + 1 \alpha_{\ell_B}\ge\alpha_{m+1} α ℓ B ≥ α m + 1 .
To extend this bound to the complete marginal gain, let E + = { e ∈ C ( s ) : Δ e ( t ∣ Z ) > 0 } E^+=\{e\in C(s):\Delta_e(t\mid Z)>0\} E + = { e ∈ C ( s ) : Δ e ( t ∣ Z ) > 0 } . A road with zero contribution under Z Z Z also has zero contribution under B ∪ Z B\cup Z B ∪ Z . Therefore,
Δ ( x t ∣ B ∪ Z ) Δ ( x t ∣ Z ) = ∑ e ∈ E + Δ e ( t ∣ B ∪ Z ) ∑ e ∈ E + Δ e ( t ∣ Z ) ≥ min e ∈ E + Δ e ( t ∣ B ∪ Z ) Δ e ( t ∣ Z ) ≥ α m + 1 . (19) \frac{\Delta(x_t\mid B\cup Z)}{\Delta(x_t\mid Z)}
=\frac{\sum_{e\in E^+}\Delta_e(t\mid B\cup Z)}{\sum_{e\in E^+}\Delta_e(t\mid Z)}
\ge\min_{e\in E^+}\frac{\Delta_e(t\mid B\cup Z)}{\Delta_e(t\mid Z)}
\ge\alpha_{m+1}. \tag*{(19)} Δ ( x t ∣ Z ) Δ ( x t ∣ B ∪ Z ) = ∑ e ∈ E + Δ e ( t ∣ Z ) ∑ e ∈ E + Δ e ( t ∣ B ∪ Z ) ≥ e ∈ E + min Δ e ( t ∣ Z ) Δ e ( t ∣ B ∪ Z ) ≥ α m + 1 . (19)
Hence every admissible ratio is at least α m + 1 \alpha_{m+1} α m + 1 , and c m ≤ 1 − α m + 1 c_m\le1-\alpha_{m+1} c m ≤ 1 − α m + 1 .
For m < H m<H m < H , set t = m + 1 t=m+1 t = m + 1 , Z = ∅ Z=\varnothing Z = ∅ , and B = { ( 0 , s ) } B=\{(0,s)\} B = {( 0 , s )} , where s s s monitors at least one road with w e > 0 w_e>0 w e > 0 . Since t − m = 1 t-m=1 t − m = 1 , the set B ⊆ V 0 B\subseteq V_0 B ⊆ V 0 is admissible. Under Z Z Z , x t = ( t , s ) x_t=(t,s) x t = ( t , s ) is the first monitoring of every road in C ( s ) C(s) C ( s ) , whereas under B B B it follows the previous monitoring by m + 1 m+1 m + 1 time steps. Thus
Δ ( x t ∣ B ) Δ ( x t ∣ Z ) = α m + 1 . \frac{\Delta(x_t\mid B)}{\Delta(x_t\mid Z)}=\alpha_{m+1}. Δ ( x t ∣ Z ) Δ ( x t ∣ B ) = α m + 1 .
The lower bound is attained, so
c m = 1 − α m + 1 = e − β ( m + 1 ) . c_m=1-\alpha_{m+1}=e^{-\beta(m+1)}. c m = 1 − α m + 1 = e − β ( m + 1 ) .
At m = H m=H m = H , no visit can occur before the H H H -step window, and c H = 0 c_H=0 c H = 0 .
Analysis of the Windowed Objective
Set Form of the Pre-Window Curvature Inequality
Definition 4 bounds the effect of visits prior to the window on the marginal gain of a single visit x t ∈ V t x_t\in V_t x t ∈ V t given a set Z Z Z . The proof of Lemma 1 needs the same bound for a set of visits at time t t t , so we extend it to any set X t ⊆ V t X_t\subseteq V_t X t ⊆ V t .
Lemma 3. For every m , t ∈ { 0 , … , H } m,t\in\{0,\ldots,H\} m , t ∈ { 0 , … , H } , X t ⊆ V t X_t\subseteq V_t X t ⊆ V t , B ⊆ V 0 : t − m − 1 B\subseteq V_{0:t-m-1} B ⊆ V 0 : t − m − 1 , and Z ⊆ V Z\subseteq V Z ⊆ V ,
Δ ( X t ∣ B ∪ Z ) ≥ ( 1 − c m ) Δ ( X t ∣ Z ) . \Delta(X_t\mid B\cup Z)\ge(1-c_m)\Delta(X_t\mid Z). Δ ( X t ∣ B ∪ Z ) ≥ ( 1 − c m ) Δ ( X t ∣ Z ) .
Proof. Elements of X t ∩ Z X_t\cap Z X t ∩ Z add zero marginal gain on both sides, so it suffices to consider the elements of X t ∖ Z X_t\setminus Z X t ∖ Z , enumerated as x 1 , … , x q x_1,\ldots,x_q x 1 , … , x q . No element of X t X_t X t lies in B B B , since X t ⊆ V t X_t\subseteq V_t X t ⊆ V t while B B B contains only elements of earlier times. Let Z j = Z ∪ { x 1 , … , x j − 1 } Z_j = Z \cup\{x_1, \ldots, x_{j-1}\} Z j = Z ∪ { x 1 , … , x j − 1 } collect the elements added before x j x_j x j . Both marginal gains then decompose into single-element gains whose j j j -th terms differ only in the presence of the set B B B :
Δ ( X t ∣ B ∪ Z ) = ∑ j = 1 q Δ ( x j ∣ B ∪ Z j ) , \Delta(X_t \mid B \cup Z) = \sum_{j=1}^{q} \Delta(x_j \mid B \cup Z_j), Δ ( X t ∣ B ∪ Z ) = j = 1 ∑ q Δ ( x j ∣ B ∪ Z j ) ,
Δ ( X t ∣ Z ) = ∑ j = 1 q Δ ( x j ∣ Z j ) . \Delta(X_t \mid Z) = \sum_{j=1}^{q} \Delta(x_j \mid Z_j). Δ ( X t ∣ Z ) = j = 1 ∑ q Δ ( x j ∣ Z j ) .
Each pair of terms is an instance of (5) with x t = x j x_t = x_j x t = x j , the same B B B , and Z = Z j Z = Z_j Z = Z j . Hence Δ ( x j ∣ B ∪ Z j ) ≥ ( 1 − c m ) Δ ( x j ∣ Z j ) \Delta(x_j \mid B \cup Z_j) \ge(1-c_m)\Delta(x_j \mid Z_j) Δ ( x j ∣ B ∪ Z j ) ≥ ( 1 − c m ) Δ ( x j ∣ Z j ) . When Δ ( x j ∣ Z j ) = 0 \Delta(x_j \mid Z_j) = 0 Δ ( x j ∣ Z j ) = 0 , submodularity and Z j ⊆ B ∪ Z j Z_j \subseteq B \cup Z_j Z j ⊆ B ∪ Z j force Δ ( x j ∣ B ∪ Z j ) = 0 \Delta(x_j \mid B \cup Z_j) = 0 Δ ( x j ∣ B ∪ Z j ) = 0 , so the inequality holds trivially. Summing over j j j proves the lemma.
Proofs of Lemma 1 and Theorem 1
We first prove Lemma 1, restated below.
Lemma 1. For every policy π \pi π ,
( 1 − c m ) Φ m ( π ) ≤ J ( π ) ≤ Φ m ( π ) . (1-c_m)\Phi_m(\pi) \le J(\pi) \le\Phi_m(\pi). ( 1 − c m ) Φ m ( π ) ≤ J ( π ) ≤ Φ m ( π ) .
Proof. Fix a realized joint trajectory τ \tau τ . Telescoping its marginal gains in chronological order gives
F ( τ ) = ∑ t = 0 H Δ ( τ t ∣ τ 0 : t − 1 ) . F(\tau) = \sum_{t=0}^{H} \Delta(\tau_t \mid\tau_{0:t-1}). F ( τ ) = t = 0 ∑ H Δ ( τ t ∣ τ 0 : t − 1 ) .
For every t t t , the full past decomposes as τ 0 : t − 1 = τ 0 : t − m − 1 ∪ τ t − m : t − 1 \tau_{0:t-1} = \tau_{0:t-m-1} \cup\tau_{t-m:t-1} τ 0 : t − 1 = τ 0 : t − m − 1 ∪ τ t − m : t − 1 , where τ 0 : t − m − 1 \tau_{0:t-m-1} τ 0 : t − m − 1 is empty when t ≤ m t \le m t ≤ m . For the lower bound, we apply Lemma 3 with X t = τ t ⊆ V t X_t = \tau_t \subseteq V_t X t = τ t ⊆ V t , B = τ 0 : t − m − 1 ⊆ V 0 : t − m − 1 B = \tau_{0:t-m-1} \subseteq V_{0:t-m-1} B = τ 0 : t − m − 1 ⊆ V 0 : t − m − 1 , and Z = τ t − m : t − 1 Z = \tau_{t-m:t-1} Z = τ t − m : t − 1 . Since B ∪ Z = τ 0 : t − 1 B \cup Z = \tau_{0:t-1} B ∪ Z = τ 0 : t − 1 , this gives
Δ ( τ t ∣ τ 0 : t − 1 ) ≥ ( 1 − c m ) Δ ( τ t ∣ τ t − m : t − 1 ) . \Delta(\tau_t \mid\tau_{0:t-1}) \ge(1-c_m)\Delta(\tau_t \mid\tau_{t-m:t-1}). Δ ( τ t ∣ τ 0 : t − 1 ) ≥ ( 1 − c m ) Δ ( τ t ∣ τ t − m : t − 1 ) .
For the upper bound, submodularity and τ t − m : t − 1 ⊆ τ 0 : t − 1 \tau_{t-m:t-1} \subseteq\tau_{0:t-1} τ t − m : t − 1 ⊆ τ 0 : t − 1 give
Δ ( τ t ∣ τ 0 : t − 1 ) ≤ Δ ( τ t ∣ τ t − m : t − 1 ) . \Delta(\tau_t \mid\tau_{0:t-1}) \le\Delta(\tau_t \mid\tau_{t-m:t-1}). Δ ( τ t ∣ τ 0 : t − 1 ) ≤ Δ ( τ t ∣ τ t − m : t − 1 ) .
Summing both bounds over t t t and taking expectations under π \pi π proves the lemma. The left-hand sides give J ( π ) J(\pi) J ( π ) by the telescoping identity above, and the terms Δ ( τ t ∣ τ t − m : t − 1 ) = r t ( s ~ t ) \Delta(\tau_t \mid\tau_{t-m:t-1}) = r_t(\tilde{s}_t) Δ ( τ t ∣ τ t − m : t − 1 ) = r t ( s ~ t ) give Φ m ( π ) \Phi_m(\pi) Φ m ( π ) .
We then prove Theorem 1, restated below.
Theorem 1. Let π ′ ∈ arg max π ∈ Π H Φ m ( π ) \pi' \in\arg\max_{\pi\in\Pi_H} \Phi_m(\pi) π ′ ∈ arg max π ∈ Π H Φ m ( π ) . Then
J ( π ′ ) ≥ ( 1 − c m ) J ∗ . J(\pi') \ge(1-c_m)J^*. J ( π ′ ) ≥ ( 1 − c m ) J ∗ .
Proof. Applying Lemma 1 to π ∗ \pi^* π ∗ and π ′ \pi' π ′ , and using the optimality of π ′ \pi' π ′ for Φ m \Phi_m Φ m , gives
( 1 − c m ) J ∗ ≤ ( 1 − c m ) Φ m ( π ∗ ) ≤ ( 1 − c m ) Φ m ( π ′ ) ≤ J ( π ′ ) . \begin{aligned}
(1-c_m)J^* &\le(1-c_m)\Phi_m(\pi^*) \\
&\le(1-c_m)\Phi_m(\pi') \le J(\pi').
\end{aligned} ( 1 − c m ) J ∗ ≤ ( 1 − c m ) Φ m ( π ∗ ) ≤ ( 1 − c m ) Φ m ( π ′ ) ≤ J ( π ′ ) .
The guarantee does not require an exact maximizer of Φ m \Phi_m Φ m . Suppose that a policy π \pi π satisfies Φ m ( π ) ≥ Φ m ( π ′ ) − η \Phi_m(\pi) \ge\Phi_m(\pi')-\eta Φ m ( π ) ≥ Φ m ( π ′ ) − η for some η ≥ 0 \eta\ge0 η ≥ 0 . Combining the first two steps above with the lower bound of Lemma 1 for π \pi π gives
( 1 − c m ) J ∗ ≤ ( 1 − c m ) Φ m ( π ′ ) ≤ ( 1 − c m ) ( Φ m ( π ) + η ) ≤ J ( π ) + ( 1 − c m ) η , (1-c_m)J^* \le(1-c_m)\Phi_m(\pi') \le(1-c_m)(\Phi_m(\pi)+\eta) \le J(\pi)+(1-c_m)\eta, ( 1 − c m ) J ∗ ≤ ( 1 − c m ) Φ m ( π ′ ) ≤ ( 1 − c m ) ( Φ m ( π ) + η ) ≤ J ( π ) + ( 1 − c m ) η ,
so J ( π ) ≥ ( 1 − c m ) ( J ∗ − η ) J(\pi) \ge(1-c_m)(J^*-\eta) J ( π ) ≥ ( 1 − c m ) ( J ∗ − η ) .
Algorithm 2 Backward Induction on the Augmented State Space
Require: spaces S , A \mathcal{S}, \mathcal{A} S , A ; memory length m m m ; dynamics P = ( P 0 , … , P H − 1 ) P = (P_0, \ldots, P_{H-1}) P = ( P 0 , … , P H − 1 ) ; rewards r t r_t r t
V H ( s ~ ) ← r H ( s ~ ) ∀ s ~ ∈ S ~ H V_H(\tilde{s}) \gets r_H(\tilde{s}) \quad\forall\tilde{s} \in\tilde{\mathcal{S}}_H V H ( s ~ ) ← r H ( s ~ ) ∀ s ~ ∈ S ~ H
for t = H − 1 , … , 0 t = H - 1, \ldots, 0 t = H − 1 , … , 0 do
for all s ~ = ( s , h ) ∈ S ~ t \tilde{s} = (s,h) \in\tilde{\mathcal{S}}_t s ~ = ( s , h ) ∈ S ~ t and a ∈ A a \in\mathcal{A} a ∈ A do
Q t ( s ~ , a ) ← r t ( s ~ ) + E s ′ ∼ P t ( ⋅ ∣ s , a ) [ V t + 1 ( s ′ , ϕ ( h , s ) ) ] Q_t(\tilde{s},a) \gets r_t(\tilde{s}) + \mathbb{E}_{s' \sim P_t(\cdot\mid s,a)}[V_{t+1}(s',\phi(h,s))] Q t ( s ~ , a ) ← r t ( s ~ ) + E s ′ ∼ P t ( ⋅ ∣ s , a ) [ V t + 1 ( s ′ , ϕ ( h , s ))]
end for
V t ( s ~ ) ← max a Q t ( s ~ , a ) ∀ s ~ ∈ S ~ t V_t(\tilde{s}) \gets\max_a Q_t(\tilde{s},a) \quad\forall\tilde{s} \in\tilde{\mathcal{S}}_t V t ( s ~ ) ← max a Q t ( s ~ , a ) ∀ s ~ ∈ S ~ t
π t ( s ~ ) ∈ arg max a Q t ( s ~ , a ) ∀ s ~ ∈ S ~ t \pi_t(\tilde{s}) \in\arg\max_a Q_t(\tilde{s},a) \quad\forall\tilde{s} \in\tilde{\mathcal{S}}_t π t ( s ~ ) ∈ arg max a Q t ( s ~ , a ) ∀ s ~ ∈ S ~ t
end for
return π = ( π 0 , … , π H − 1 ) \pi= (\pi_0, \ldots, \pi_{H-1}) π = ( π 0 , … , π H − 1 )
Backward Induction on the Augmented State Space
Algorithm 2 solves a finite-horizon MDP on the history-augmented states by backward induction [18 ] . The expectation is over the next state, while the history updates deterministically through the map ϕ : H t m × S → H t + 1 m \phi: \mathcal{H}^m_t \times\mathcal{S} \to\mathcal{H}^m_{t+1} ϕ : H t m × S → H t + 1 m , which appends a state to a history and drops the first entry if the result has more than m m m entries. Figure 6 illustrates this update for one agent. Section 4.2 applies the algorithm to the joint augmented states, with S \mathcal{S} S and A \mathcal{A} A replaced by S N \mathcal{S}^N S N and A N \mathcal{A}^N A N . Section 4.3 applies it once per agent, with the estimated rewards r ^ i , t π ˉ [ i − 1 ] \hat{r}^{\bar{\pi}[i-1]}_{i,t} r ^ i , t π ˉ [ i − 1 ] .
Backward induction on the joint augmented MDP computes a Q Q Q -value for each of the at most ∣ S ∣ N ( m + 1 ) ∣ A ∣ N |\mathcal{S}|^{N(m+1)}|\mathcal{A}|^N ∣ S ∣ N ( m + 1 ) ∣ A ∣ N pairs in S ~ t × A \tilde{\mathcal{S}}_t \times\mathcal{A} S ~ t × A at every stage. Each Q Q Q -value sums over at most ∣ S ∣ N |\mathcal{S}|^N ∣ S ∣ N next joint physical states, since the histories update deterministically through ϕ \phi ϕ . Over H H H stages, the total computation time is O ( H ∣ S ∣ N ( m + 2 ) ∣ A ∣ N ) O(H|\mathcal{S}|^{N(m+2)}|\mathcal{A}|^N) O ( H ∣ S ∣ N ( m + 2 ) ∣ A ∣ N ) .
Non-Monotonicity of the Windowed Stage Reward
Adding an agent can decrease the windowed objective even when F F F is monotone submodular and c m < 1 c_m < 1 c m < 1 . Consider a reward of the form (4) on two states a a a and b b b with a single road e e e of maximum importance w e = 1 w_e = 1 w e = 1 , where C ( a ) = { e } C(a) = \{e\} C ( a ) = { e } and C ( b ) = ∅ C(b) = \varnothing C ( b ) = ∅ . Set H = 2 H = 2 H = 2 , m = 1 m = 1 m = 1 , and β = ln ( 4 / 3 ) \beta= \ln(4/3) β = ln ( 4/3 ) , so that α 1 = 1 / 4 \alpha_1 = 1/4 α 1 = 1/4 and α 2 = 7 / 16 \alpha_2 = 7/16 α 2 = 7/16 . By Corollary 1, the reward is monotone submodular, and (17) gives c 1 = 9 / 16 c_1 = 9/16 c 1 = 9/16 . Each agent can move between a a a and b b b deterministically, and two agents with fixed initial states follow the trajectories
τ 1 = { ( 0 , a ) , ( 1 , b ) , ( 2 , a ) } , τ 2 = { ( 0 , b ) , ( 1 , a ) , ( 2 , b ) } . \tau_1 = \{(0,a),(1,b),(2,a)\}, \qquad\tau_2 = \{(0,b),(1,a),(2,b)\}. τ 1 = {( 0 , a ) , ( 1 , b ) , ( 2 , a )} , τ 2 = {( 0 , b ) , ( 1 , a ) , ( 2 , b )} .
shown in Figure 7 . Since the dynamics and initial states are deterministic, the windowed objective of the policies that generate these trajectories equals the sum of the stage rewards r t ( s ~ t ) r_t(\tilde{s}_t) r t ( s ~ t ) along them.
Figure 7. Adding an agent lowers the windowed objective in the example of Appendix § 11 .§ 4 . Shaded nodes are visits to state a a a , which monitors road e e e . The gray region denotes the window at time 2, and the values below the axis are the stage rewards, which sum to the windowed objective. (a) With agent 1 alone, the window at time 2 contains no visit to a a a . (b) With both agents, the window at time 2 contains the visit ( 1 , a ) (1,a) ( 1 , a ) of agent 2. This visit lowers the stage reward at time 2, although the true reward F F F increases.
With agent 1 alone, its visit at time 0 lies outside the window at time 2. The stage rewards are then r 0 ( s ~ 0 ) = 1 r_0(\tilde{s}_0) = 1 r 0 ( s ~ 0 ) = 1 , r 1 ( s ~ 1 ) = 0 r_1(\tilde{s}_1) = 0 r 1 ( s ~ 1 ) = 0 , and r 2 ( s ~ 2 ) = 1 r_2(\tilde{s}_2) = 1 r 2 ( s ~ 2 ) = 1 , which sum to 2. With both agents, road e e e is monitored at every time. The stage rewards are then r 0 ( s ~ 0 ) = 1 r_0(\tilde{s}_0) = 1 r 0 ( s ~ 0 ) = 1 , r 1 ( s ~ 1 ) = α 1 r_1(\tilde{s}_1) = \alpha_1 r 1 ( s ~ 1 ) = α 1 , and r 2 ( s ~ 2 ) = α 1 r_2(\tilde{s}_2) = \alpha_1 r 2 ( s ~ 2 ) = α 1 , which sum to 3 / 2 3/2 3/2 . Adding agent 2 thus lowers the stage reward at time 2 from 1 to 1 / 4 1/4 1/4 , because its visit ( 1 , a ) (1,a) ( 1 , a ) enters the window at time 2. The true reward instead increases, from F ( τ 1 ) = 1 + α 2 = 23 / 16 F(\tau_1)=1+\alpha_2=23/16 F ( τ 1 ) = 1 + α 2 = 23/16 to F ( τ 1 ∪ τ 2 ) = 3 / 2 F(\tau_1\cup\tau_2)=3/2 F ( τ 1 ∪ τ 2 ) = 3/2 . Hence, the stage rewards of Φ m \Phi_m Φ m are not monotone in the set of agents, and the condition required by the guarantee of Chen et al. [4 ] fails.
Analysis of Sequential Policy Optimization
We prove Theorem 2, restated below.
Theorem 2. Let N ≥ 2 N\ge2 N ≥ 2 and fix m ∈ { 0 , … , H } m\in\{0,\ldots,H\} m ∈ { 0 , … , H } . For ϵ > 0 \epsilon>0 ϵ > 0 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , choose the number of sampled predecessor trajectories K K K such that
K ≥ R 2 2 ϵ 2 ln 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 δ , (20) K \ge\frac{R^2}{2\epsilon^2}\ln\frac{2(N-1)(H+1)|\mathcal{S}|^{m+1}}{\delta}, \tag*{(20)} K ≥ 2 ϵ 2 R 2 ln δ 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 , (20) where R = max v ∈ V F ( { v } ) R=\max_{v\in V}F(\{v\}) R = max v ∈ V F ({ v }) is the largest reward of a single visit. Then, with probability at least 1 − δ 1-\delta 1 − δ , the joint policy π ˉ \bar{\pi} π ˉ returned by Algorithm 1 satisfies
J ( π ˉ ) ≥ 1 − c m 2 − c m ( J ∗ − 2 ( N − 1 ) ( H + 1 ) ϵ ) . (21) J(\bar{\pi})\ge\frac{1-c_m}{2-c_m}\left(J^*-2(N-1)(H+1)\epsilon\right). \tag*{(21)} J ( π ˉ ) ≥ 2 − c m 1 − c m ( J ∗ − 2 ( N − 1 ) ( H + 1 ) ϵ ) . (21)
Throughout this section, we use the following notation. For a joint policy π \pi π and a local policy π i \pi_i π i of agent i i i , let d i , t π , d i , t π i ∈ D ( S ~ t ) d^{\pi}_{i,t},d^{\pi_i}_{i,t}\in\mathcal{D}(\widetilde{\mathcal{S}}_t) d i , t π , d i , t π i ∈ D ( S t ) denote the distributions of the augmented state of agent i i i at time t t t ,
d i , t π ( s ~ ) = Pr τ ∼ π ( s ~ i , t = s ~ ) , d i , t π i ( s ~ ) = Pr τ i ∼ π i ( s ~ i , t = s ~ ) , d^{\pi}_{i,t}(\widetilde{s})=\Pr_{\tau\sim\pi}(\widetilde{s}_{i,t}=\widetilde{s}),\qquad d^{\pi_i}_{i,t}(\widetilde{s})=\Pr_{\tau_i\sim\pi_i}(\widetilde{s}_{i,t}=\widetilde{s}), d i , t π ( s ) = τ ∼ π Pr ( s i , t = s ) , d i , t π i ( s ) = τ i ∼ π i Pr ( s i , t = s ) ,
for every s ~ ∈ S ~ t \widetilde{s}\in\widetilde{\mathcal{S}}_t s ∈ S t . With this notation, the local objective (9) takes the equivalent form
G i π ˉ [ i − 1 ] ( π i ) = ∑ t = 0 H E s ~ i , t ∼ d i , t π i [ π ˉ i , t [ i − 1 ] ( s ~ i , t ) ] . (22) G_i^{\bar{\pi}_{[i-1]}}(\pi_i)=\sum_{t=0}^{H}\mathbb{E}_{\widetilde{s}_{i,t}\sim d^{\pi_i}_{i,t}}\left[\bar{\pi}_{i,t}^{[i-1]}(\widetilde{s}_{i,t})\right]. \tag*{(22)} G i π ˉ [ i − 1 ] ( π i ) = t = 0 ∑ H E s i , t ∼ d i , t π i [ π ˉ i , t [ i − 1 ] ( s i , t ) ] . (22)
Proof of Theorem 2
Proof. The argument has three steps. Step 1 bounds the optimality gap by the sum of the maximum local objectives of the agents. Step 2 bounds each maximum by the attained local objective, up to the reward-estimation error. Step 3 bounds the attained local objectives by the return J ( π ˉ ) J(\bar{\pi}) J ( π ˉ ) through c m c_m c m .
The policy π ˉ \bar{\pi} π ˉ returned by Algorithm 1 depends on the sampled predecessor trajectories. Throughout the proof, we treat π ˉ \bar{\pi} π ˉ as fixed. Since each π ˉ i \bar{\pi}_i π ˉ i is deterministic, an expectation over τ ∼ π ˉ \tau\sim\bar{\pi} τ ∼ π ˉ is then taken over the initial states and the transitions only.
Step 1 (bounding the optimality gap by the maximum local objectives). For τ ∗ ∼ π ∗ \tau^* \sim\pi^* τ ∗ ∼ π ∗ and τ ∼ π ˉ \tau\sim\bar{\pi} τ ∼ π ˉ sampled independently, with π ∗ \pi^* π ∗ an optimal global history-dependent policy of (3) and π ˉ ∈ Π m l o c \bar{\pi} \in\Pi_m^{\mathrm{loc}} π ˉ ∈ Π m loc the policy returned by Algorithm 1, we have
J ∗ = E τ ∗ ∼ π ∗ [ F ( τ ∗ ) ] ≤ E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ F ( τ ∗ ∪ τ ) ] = E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ F ( τ ) + Δ ( τ ∗ ∣ τ ) ] = E τ ∼ π ˉ [ F ( τ ) ] + E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ Δ ( τ ∗ ∣ τ ) ] = J ( π ˉ ) + E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ Δ ( τ ∗ ∣ τ ) ] . J^* = \mathbb{E}_{\tau^* \sim\pi^*}[F(\tau^*)] \le\mathbb{E}_{\tau^* \sim\pi^*,\tau\sim\bar{\pi}}[F(\tau^* \cup\tau)] = \mathbb{E}_{\tau^* \sim\pi^*,\tau\sim\bar{\pi}}[F(\tau) + \Delta(\tau^* \mid\tau)]
= \mathbb{E}_{\tau\sim\bar{\pi}}[F(\tau)] + \mathbb{E}_{\tau^* \sim\pi^*,\tau\sim\bar{\pi}}[\Delta(\tau^* \mid\tau)]
= J(\bar{\pi}) + \mathbb{E}_{\tau^* \sim\pi^*,\tau\sim\bar{\pi}}[\Delta(\tau^* \mid\tau)]. J ∗ = E τ ∗ ∼ π ∗ [ F ( τ ∗ )] ≤ E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ F ( τ ∗ ∪ τ )] = E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ F ( τ ) + Δ ( τ ∗ ∣ τ )] = E τ ∼ π ˉ [ F ( τ )] + E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ Δ ( τ ∗ ∣ τ )] = J ( π ˉ ) + E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ Δ ( τ ∗ ∣ τ )] .
where the inequality holds by monotonicity, and the equalities use the definition of the marginal gain, linearity of expectation, and the definition of the return (3). For every fixed realization of τ \tau τ and τ ∗ \tau^* τ ∗ , the pairs τ i , t ∗ \tau^*_{i,t} τ i , t ∗ of τ ∗ \tau^* τ ∗ are added to τ \tau τ one at a time in lexicographic order of ( i , t ) (i,t) ( i , t ) , meaning τ [ i − 1 ] ∗ ∪ τ i , 0 : t − 1 ∗ \tau^*_{[i-1]} \cup\tau^*_{i,0:t-1} τ [ i − 1 ] ∗ ∪ τ i , 0 : t − 1 ∗ is the set of elements added before τ i , t ∗ \tau^*_{i,t} τ i , t ∗ . Telescoping these marginal gains gives
Δ ( τ ∗ ∣ τ ) = ∑ i ∈ [ N ] ∑ t = 0 H Δ ( τ i , t ∗ ∣ τ ∪ τ [ i − 1 ] ∗ ∪ τ i , 0 : t − 1 ∗ ) . \Delta(\tau^* \mid\tau) = \sum_{i \in[N]} \sum_{t=0}^{H} \Delta(\tau^*_{i,t} \mid\tau\cup\tau^*_{[i-1]} \cup\tau^*_{i,0:t-1}). Δ ( τ ∗ ∣ τ ) = i ∈ [ N ] ∑ t = 0 ∑ H Δ ( τ i , t ∗ ∣ τ ∪ τ [ i − 1 ] ∗ ∪ τ i , 0 : t − 1 ∗ ) .
where a term whose pair already lies in its given set, τ i , t ∗ ⊆ τ ∪ τ [ i − 1 ] ∗ ∪ τ i , 0 : t − 1 ∗ \tau^*_{i,t} \subseteq\tau\cup\tau^*_{[i-1]} \cup\tau^*_{i,0:t-1} τ i , t ∗ ⊆ τ ∪ τ [ i − 1 ] ∗ ∪ τ i , 0 : t − 1 ∗ , contributes 0, since Δ ( x ∣ B ) = 0 \Delta(x \mid B) = 0 Δ ( x ∣ B ) = 0 whenever x ∈ B x \in B x ∈ B . The set τ ∪ τ [ i − 1 ] ∗ ∪ τ i , 0 : t − 1 ∗ \tau\cup\tau^*_{[i-1]} \cup\tau^*_{i,0:t-1} τ ∪ τ [ i − 1 ] ∗ ∪ τ i , 0 : t − 1 ∗ given in each term contains τ i , t − m : t − 1 ∗ ∪ τ [ i − 1 ] \tau^*_{i,t-m:t-1} \cup\tau_{[i-1]} τ i , t − m : t − 1 ∗ ∪ τ [ i − 1 ] , because τ [ i − 1 ] ∗ ⊆ τ \tau^*_{[i-1]} \subseteq\tau τ [ i − 1 ] ∗ ⊆ τ and τ i , t − m : t − 1 ∗ ⊆ τ i , 0 : t − 1 ∗ \tau^*_{i,t-m:t-1} \subseteq\tau^*_{i,0:t-1} τ i , t − m : t − 1 ∗ ⊆ τ i , 0 : t − 1 ∗ . By submodularity, the marginal gain of τ i , t ∗ \tau^*_{i,t} τ i , t ∗ does not decrease when the given set shrinks to τ i , t − m : t − 1 ∗ ∪ τ [ i − 1 ] \tau^*_{i,t-m:t-1} \cup\tau_{[i-1]} τ i , t − m : t − 1 ∗ ∪ τ [ i − 1 ] , so
Δ ( τ ∗ ∣ τ ) ≤ ∑ i ∈ [ N ] ∑ t = 0 H Δ ( τ i , t ∗ ∣ τ i , t − m : t − 1 ∗ ∪ τ [ i − 1 ] ) . \Delta(\tau^* \mid\tau) \le\sum_{i \in[N]} \sum_{t=0}^{H} \Delta(\tau^*_{i,t} \mid\tau^*_{i,t-m:t-1} \cup\tau_{[i-1]}). Δ ( τ ∗ ∣ τ ) ≤ i ∈ [ N ] ∑ t = 0 ∑ H Δ ( τ i , t ∗ ∣ τ i , t − m : t − 1 ∗ ∪ τ [ i − 1 ] ) .
It remains to take the expectation of this bound over the two runs. Along the optimal run, the augmented state s ~ i , t ∗ = ( s i , t ∗ , h i , t ∗ ) \tilde{s}^*_{i,t} = (s^*_{i,t}, h^*_{i,t}) s ~ i , t ∗ = ( s i , t ∗ , h i , t ∗ ) determines τ i , t ∗ \tau^*_{i,t} τ i , t ∗ and τ i , t − m : t − 1 ∗ = ν t ( h i , t ∗ ) \tau^*_{i,t-m:t-1} = \nu_t(h^*_{i,t}) τ i , t − m : t − 1 ∗ = ν t ( h i , t ∗ ) , so each term depends on agent i i i ’s trajectory only through s ~ i , t ∗ \tilde{s}^*_{i,t} s ~ i , t ∗ . Since s ~ i , t ∗ ∼ d i , t π ∗ \tilde{s}^*_{i,t} \sim d^{\pi^*}_{i,t} s ~ i , t ∗ ∼ d i , t π ∗ is independent of the predecessors’ set τ [ i − 1 ] \tau_{[i-1]} τ [ i − 1 ] , the expectation of each term splits into an outer expectation over s ~ i , t ∗ \tilde{s}^*_{i,t} s ~ i , t ∗ and an inner expectation over τ [ i − 1 ] \tau_{[i-1]} τ [ i − 1 ] :
E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ Δ ( τ i , t ∗ ∣ τ i , t − m : t − 1 ∗ ∪ τ [ i − 1 ] ) ] = E s ~ i , t ∗ ∼ d i , t π ∗ [ E τ [ i − 1 ] ∼ π ˉ [ i − 1 ] [ Δ ( ( t , s i , t ∗ ) ∣ ν t ( h i , t ∗ ) ∪ τ [ i − 1 ] ) ] ] = E s ~ i , t ∗ ∼ d i , t π ∗ [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ∗ ) ] . \mathbb{E}_{\tau^* \sim\pi^*,\tau\sim\bar{\pi}}\left[\Delta(\tau^*_{i,t} \mid\tau^*_{i,t-m:t-1} \cup\tau_{[i-1]})\right]
= \mathbb{E}_{\tilde{s}^*_{i,t} \sim d^{\pi^*}_{i,t}}\left[\mathbb{E}_{\tau_{[i-1]} \sim\bar{\pi}_{[i-1]}}\left[\Delta((t,s^*_{i,t}) \mid\nu_t(h^*_{i,t}) \cup\tau_{[i-1]})\right]\right]
= \mathbb{E}_{\tilde{s}^*_{i,t} \sim d^{\pi^*}_{i,t}}\left[\bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}^*_{i,t})\right]. E τ ∗ ∼ π ∗ , τ ∼ π ˉ [ Δ ( τ i , t ∗ ∣ τ i , t − m : t − 1 ∗ ∪ τ [ i − 1 ] ) ] = E s ~ i , t ∗ ∼ d i , t π ∗ [ E τ [ i − 1 ] ∼ π ˉ [ i − 1 ] [ Δ (( t , s i , t ∗ ) ∣ ν t ( h i , t ∗ ) ∪ τ [ i − 1 ] ) ] ] = E s ~ i , t ∗ ∼ d i , t π ∗ [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ∗ ) ] .
where the second equality applies the definition (8) of the reward. The occupancy d i , t π ∗ d^{\pi^*}_{i,t} d i , t π ∗ is induced under the global history-dependent policy π ∗ \pi^* π ∗ , whereas the algorithm optimizes over local Markov policies. The following lemma closes this gap.
Lemma 4. Fix an agent i i i and any π ∈ Π H \pi\in\Pi_H π ∈ Π H . There is a policy π i ′ ′ ∈ Π m l o c \pi_i^{\prime\prime} \in\Pi_m^{\mathrm{loc}} π i ′′ ∈ Π m loc with d i , t π i ′ ′ = d i , t π d^{\pi_i^{\prime\prime}}_{i,t} = d^\pi_{i,t} d i , t π i ′′ = d i , t π for every t t t .
Applying Lemma 4 to π ∗ \pi^* π ∗ gives a local policy π i ′ ′ ∈ Π m l o c \pi_i^{\prime\prime} \in\Pi_m^{\mathrm{loc}} π i ′′ ∈ Π m loc with the same distributions d i , t π i ′ ′ = d i , t π ∗ d^{\pi_i^{\prime\prime}}_{i,t} = d^{\pi^*}_{i,t} d i , t π i ′′ = d i , t π ∗ of the augmented state of agent i i i . By (20), it follows that ∑ t = 0 H E s ~ i , t ∗ ∼ d i , t π ∗ [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ∗ ) ] = G i π ˉ [ i − 1 ] ( π i ′ ′ ) ≤ max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) \sum_{t=0}^{H} \mathbb{E}_{\tilde{s}^*_{i,t} \sim d^{\pi^*}_{i,t}}[\bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}^*_{i,t})] = G_i^{\bar{\pi}_{[i-1]}}(\pi_i^{\prime\prime}) \le\max_{\pi_i \in\Pi_m^{\mathrm{loc}}} G_i^{\bar{\pi}_{[i-1]}}(\pi_i) ∑ t = 0 H E s ~ i , t ∗ ∼ d i , t π ∗ [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ∗ )] = G i π ˉ [ i − 1 ] ( π i ′′ ) ≤ max π i ∈ Π m loc G i π ˉ [ i − 1 ] ( π i ) . Hence,
J ∗ ≤ J ( π ˉ ) + ∑ i ∈ [ N ] max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) . (23) J^* \le J(\bar{\pi}) + \sum_{i \in[N]} \max_{\pi_i \in\Pi_m^{\mathrm{loc}}} G_i^{\bar{\pi}_{[i-1]}}(\pi_i). \tag*{(23)} J ∗ ≤ J ( π ˉ ) + i ∈ [ N ] ∑ π i ∈ Π m loc max G i π ˉ [ i − 1 ] ( π i ) . (23)
Step 2 (bounding the maximum local objectives by the attained ones). Hoeffding’s inequality and a union bound over the at most ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 (N-1)(H+1)|\mathcal{S}|^{m+1} ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 estimated rewards give the following guarantee.
Lemma 5. Under (11), with probability at least 1 − δ 1-\delta 1 − δ ,
∣ r ^ i , t π ˉ [ i − 1 ] ( s ~ ) − r ˉ i , t π ˉ [ i − 1 ] ( s ~ ) ∣ ≤ ϵ \left|\widehat{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}) - \bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s})\right| \le\epsilon r i , t π ˉ [ i − 1 ] ( s ~ ) − r ˉ i , t π ˉ [ i − 1 ] ( s ~ ) ≤ ϵ
for all i ≥ 2 i \ge2 i ≥ 2 , t t t , and s ~ ∈ S ~ t \tilde{s} \in\tilde{\mathcal{S}}_t s ~ ∈ S ~ t .
For the rest of the proof, we assume that the bound of Lemma 5 holds for all i ≥ 2 i \ge2 i ≥ 2 , t t t , and s ~ ∈ S ~ t \tilde{s} \in\tilde{\mathcal{S}}_t s ~ ∈ S ~ t , which happens with probability at least 1 − δ 1-\delta 1 − δ . The algorithm maximizes G ^ i π ˉ [ i − 1 ] \widehat{G}_i^{\bar{\pi}_{[i-1]}} G i π ˉ [ i − 1 ] rather than G i π ˉ [ i − 1 ] G_i^{\bar{\pi}_{[i-1]}} G i π ˉ [ i − 1 ] . The next lemma bounds the resulting gap.
Lemma 6. Let π ˉ i ∈ arg max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) \bar{\pi}_i \in\arg\max_{\pi_i \in\Pi_m^{\mathrm{loc}}} G_i^{\bar{\pi}_{[i-1]}}(\pi_i) π ˉ i ∈ arg max π i ∈ Π m loc G i π ˉ [ i − 1 ] ( π i ) . If ∣ r ~ i , t π ˉ [ i − 1 ] ( s ~ ) − r i , t π ˉ [ i − 1 ] ( s ~ ) ∣ ≤ ϵ \left|\tilde{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s})-r_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s})\right|\leq\epsilon r ~ i , t π ˉ [ i − 1 ] ( s ~ ) − r i , t π ˉ [ i − 1 ] ( s ~ ) ≤ ϵ for all t t t and s ~ ∈ S ~ t \tilde{s}\in\widetilde{\mathcal{S}}_t s ~ ∈ S t , then
G i π ˉ [ i − 1 ] ( π ˉ i ) ≥ max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) − 2 ( H + 1 ) ϵ . G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i)\geq\max_{\pi_i\in\Pi_m^{\mathrm{loc}}}G_i^{\bar{\pi}_{[i-1]}}(\pi_i)-2(H+1)\epsilon. G i π ˉ [ i − 1 ] ( π ˉ i ) ≥ π i ∈ Π m loc max G i π ˉ [ i − 1 ] ( π i ) − 2 ( H + 1 ) ϵ .
For i = 1 i=1 i = 1 , π ˉ 1 \bar{\pi}_1 π ˉ 1 attains the maximum exactly.
Applying Lemma 6, each term max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) \max_{\pi_i\in\Pi_m^{\mathrm{loc}}}G_i^{\bar{\pi}_{[i-1]}}(\pi_i) max π i ∈ Π m loc G i π ˉ [ i − 1 ] ( π i ) in (23) satisfies max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) ≤ G i π ˉ [ i − 1 ] ( π ˉ i ) + 2 ( H + 1 ) ϵ \max_{\pi_i\in\Pi_m^{\mathrm{loc}}}G_i^{\bar{\pi}_{[i-1]}}(\pi_i)\leq G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i)+2(H+1)\epsilon max π i ∈ Π m loc G i π ˉ [ i − 1 ] ( π i ) ≤ G i π ˉ [ i − 1 ] ( π ˉ i ) + 2 ( H + 1 ) ϵ for i ≥ 2 i\geq2 i ≥ 2 , while max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) = G i π ˉ [ i − 1 ] ( π ˉ i ) \max_{\pi_i\in\Pi_m^{\mathrm{loc}}}G_i^{\bar{\pi}_{[i-1]}}(\pi_i)=G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i) max π i ∈ Π m loc G i π ˉ [ i − 1 ] ( π i ) = G i π ˉ [ i − 1 ] ( π ˉ i ) for i = 1 i=1 i = 1 . Summing these bounds over the N N N agents, only the N − 1 N-1 N − 1 agents with i ≥ 2 i\geq2 i ≥ 2 carry the error term, so
J ∗ ≤ J ( π ˉ ) + ∑ i ∈ [ N ] G i π ˉ [ i − 1 ] ( π ˉ i ) + 2 ( N − 1 ) ( H + 1 ) ϵ . (24) J^*\leq J(\bar{\pi})+\sum_{i\in[N]}G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i)+2(N-1)(H+1)\epsilon. \tag*{(24)} J ∗ ≤ J ( π ˉ ) + i ∈ [ N ] ∑ G i π ˉ [ i − 1 ] ( π ˉ i ) + 2 ( N − 1 ) ( H + 1 ) ϵ . (24)
Step 3 (bounding the attained local objectives by the return). It remains to relate the sum of the attained local objectives to the achieved return J ( π ˉ ) J(\bar{\pi}) J ( π ˉ ) . The following lemma provides this connection and is the only step in which pre-window curvature enters.
Lemma 7. For the policy π ˉ \bar{\pi} π ˉ returned by Algorithm 1,
( 1 − c m ) ∑ i ∈ [ N ] G i π ˉ [ i − 1 ] ( π ˉ i ) ≤ J ( π ˉ ) ≤ ∑ i ∈ [ N ] G i π ˉ [ i − 1 ] ( π ˉ i ) . (1-c_m)\sum_{i\in[N]}G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i)\leq J(\bar{\pi})\leq\sum_{i\in[N]}G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i). ( 1 − c m ) i ∈ [ N ] ∑ G i π ˉ [ i − 1 ] ( π ˉ i ) ≤ J ( π ˉ ) ≤ i ∈ [ N ] ∑ G i π ˉ [ i − 1 ] ( π ˉ i ) .
If c m = 1 c_m=1 c m = 1 , the claimed bound reads J ( π ˉ ) ≥ 0 J(\bar{\pi})\geq0 J ( π ˉ ) ≥ 0 , which holds because F F F is monotone with F ( ∅ ) = 0 F(\varnothing)=0 F ( ∅ ) = 0 . Assume c m < 1 c_m<1 c m < 1 . The lower bound in Lemma 7 gives
J ( π ˉ ) ≥ ( 1 − c m ) ∑ i ∈ [ N ] G i π ˉ [ i − 1 ] ( π ˉ i ) , (25) J(\bar{\pi})\geq(1-c_m)\sum_{i\in[N]}G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i), \tag*{(25)} J ( π ˉ ) ≥ ( 1 − c m ) i ∈ [ N ] ∑ G i π ˉ [ i − 1 ] ( π ˉ i ) , (25)
so ∑ i ∈ [ N ] G i π ˉ [ i − 1 ] ( π ˉ i ) ≤ J ( π ˉ ) / ( 1 − c m ) \sum_{i\in[N]}G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i)\leq J(\bar{\pi})/(1-c_m) ∑ i ∈ [ N ] G i π ˉ [ i − 1 ] ( π ˉ i ) ≤ J ( π ˉ ) / ( 1 − c m ) . Substituting into (24) ,
J ∗ ≤ J ( π ˉ ) + J ( π ˉ ) 1 − c m + 2 ( N − 1 ) ( H + 1 ) ϵ = 2 − c m 1 − c m J ( π ˉ ) + 2 ( N − 1 ) ( H + 1 ) ϵ , \begin{aligned}
J^*&\leq J(\bar{\pi})+\frac{J(\bar{\pi})}{1-c_m}+2(N-1)(H+1)\epsilon\\
&=\frac{2-c_m}{1-c_m}J(\bar{\pi})+2(N-1)(H+1)\epsilon,
\end{aligned} J ∗ ≤ J ( π ˉ ) + 1 − c m J ( π ˉ ) + 2 ( N − 1 ) ( H + 1 ) ϵ = 1 − c m 2 − c m J ( π ˉ ) + 2 ( N − 1 ) ( H + 1 ) ϵ ,
which rearranges to (12). Since the bound of Lemma 5 holds with probability at least 1 − δ 1-\delta 1 − δ , so does (12). □ \square □
Proof of Lemma 4
Lemma 4. Fix an agent i i i and any π ∈ Π H \pi\in\Pi_H π ∈ Π H . There is a policy π i ′ ′ ∈ Π m l o c \pi_i''\in\Pi_m^{\mathrm{loc}} π i ′′ ∈ Π m loc with d i , t π i ′ ′ = d i , t π d_{i,t}^{\pi_i''}=d_{i,t}^{\pi} d i , t π i ′′ = d i , t π for every t t t .
Proof. Fix an agent i i i and any π ∈ Π H \pi\in\Pi_H π ∈ Π H . Let d i , t π d_{i,t}^{\pi} d i , t π and q i , t π q_{i,t}^{\pi} q i , t π denote the distributions of agent i i i ’s augmented state and of its (augmented state, action) pair at time t t t :
d i , t π ( s ~ ) = Pr π ( s ~ i , t = s ~ ) , 0 ≤ t ≤ H , d_{i,t}^{\pi}(\tilde{s})=\Pr_{\pi}(\tilde{s}_{i,t}=\tilde{s}),\qquad0\leq t\leq H, d i , t π ( s ~ ) = π Pr ( s ~ i , t = s ~ ) , 0 ≤ t ≤ H ,
q i , t π ( s ~ , a ) = Pr π ( s ~ i , t = s ~ , a i , t = a ) , 0 ≤ t < H , q_{i,t}^{\pi}(\tilde{s},a)=\Pr_{\pi}(\tilde{s}_{i,t}=\tilde{s},a_{i,t}=a),\qquad0\leq t<H, q i , t π ( s ~ , a ) = π Pr ( s ~ i , t = s ~ , a i , t = a ) , 0 ≤ t < H ,
so that ∑ a q i , t π ( s ~ , a ) = d i , t π ( s ~ ) \sum_a q_{i,t}^{\pi}(\tilde{s},a)=d_{i,t}^{\pi}(\tilde{s}) ∑ a q i , t π ( s ~ , a ) = d i , t π ( s ~ ) for 0 ≤ t < H 0\leq t<H 0 ≤ t < H . We now construct a policy π i ′ ′ ∈ Π m l o c \pi_i''\in\Pi_m^{\mathrm{loc}} π i ′′ ∈ Π m loc and show by induction on t t t that d i , t π i ′ ′ = d i , t π d_{i,t}^{\pi_i''}=d_{i,t}^{\pi} d i , t π i ′′ = d i , t π . Define the local policy π i ′ ′ = ( π i , 0 ′ ′ , … , π i , H − 1 ′ ′ ) \pi_i''=(\pi_{i,0}'',\ldots,\pi_{i,H-1}'') π i ′′ = ( π i , 0 ′′ , … , π i , H − 1 ′′ ) . When d i , t π ( s ~ ) > 0 d_{i,t}^{\pi}(\tilde{s})>0 d i , t π ( s ~ ) > 0 , set
π i , t ′ ′ ( a ∣ s ~ ) = q i , t π ( s ~ , a ) d i , t π ( s ~ ) . \pi_{i,t}''(a\mid\tilde{s})=\frac{q_{i,t}^{\pi}(\tilde{s},a)}{d_{i,t}^{\pi}(\tilde{s})}. π i , t ′′ ( a ∣ s ~ ) = d i , t π ( s ~ ) q i , t π ( s ~ , a ) .
When d i , t π ( s ~ ) = 0 d_{i,t}^{\pi}(\tilde{s})=0 d i , t π ( s ~ ) = 0 , choose π i , t ′ ′ ( ⋅ ∣ s ~ ) ∈ D ( A ) \pi_{i,t}''(\cdot\mid\tilde{s})\in\mathcal{D}(\mathcal{A}) π i , t ′′ ( ⋅ ∣ s ~ ) ∈ D ( A ) arbitrarily.
Base case. At t = 0 t=0 t = 0 , the history h i , 0 h_{i,0} h i , 0 is empty and s i , 0 ∼ ρ i s_{i,0}\sim\rho_i s i , 0 ∼ ρ i . Hence, d i , 0 π i ′ ′ ( s , h i , 0 ) = d i , 0 π ( s , h i , 0 ) = ρ i ( s ) d_{i,0}^{\pi_i''}(s,h_{i,0})=d_{i,0}^{\pi}(s,h_{i,0})=\rho_i(s) d i , 0 π i ′′ ( s , h i , 0 ) = d i , 0 π ( s , h i , 0 ) = ρ i ( s ) for every s ∈ S s\in\mathcal{S} s ∈ S , independently of the policy. Inductive step. Assume 0 ≤ t < H 0 \le t < H 0 ≤ t < H and the inductive hypothesis d i , t π ′ ′ = d i , t π d^{\pi''}_{i,t}=d^{\pi}_{i,t} d i , t π ′′ = d i , t π , and write q i , t π ′ ′ q^{\pi''}_{i,t} q i , t π ′′ for agent i i i ’s (augmented state, action) distribution under π i ′ ′ \pi''_i π i ′′ . If d i , t π ′ ′ ( s ~ ) = 0 d^{\pi''}_{i,t}(\tilde{s})=0 d i , t π ′′ ( s ~ ) = 0 , both state–action occupancies are zero by the hypothesis and the identity ∑ a q i , t π ( s ~ , a ) = d i , t π ( s ~ ) \sum_a q^{\pi}_{i,t}(\tilde{s},a)=d^{\pi}_{i,t}(\tilde{s}) ∑ a q i , t π ( s ~ , a ) = d i , t π ( s ~ ) . Otherwise, the hypothesis and the definition of π i ′ ′ \pi''_i π i ′′ give
q i , t π ′ ′ ( s ~ , a ) = d i , t π ′ ′ ( s ~ ) π i , t ′ ′ ( a ∣ s ~ ) = d i , t π ( s ~ ) q i , t π ( s , a ) d i , t π ( s ~ ) = q i , t π ( s ~ , a ) . q^{\pi''}_{i,t}(\tilde{s},a)=d^{\pi''}_{i,t}(\tilde{s})\pi''_{i,t}(a\mid\tilde{s})=d^{\pi}_{i,t}(\tilde{s})\frac{q^{\pi}_{i,t}(s,a)}{d^{\pi}_{i,t}(\tilde{s})}=q^{\pi}_{i,t}(\tilde{s},a). q i , t π ′′ ( s ~ , a ) = d i , t π ′′ ( s ~ ) π i , t ′′ ( a ∣ s ~ ) = d i , t π ( s ~ ) d i , t π ( s ~ ) q i , t π ( s , a ) = q i , t π ( s ~ , a ) .
It remains to prove the equality at time t + 1 t+1 t + 1 . Write s ~ = ( s , h ) \tilde{s}=(s,h) s ~ = ( s , h ) . Under decoupled dynamics, agent i i i moves to s ′ s' s ′ with probability P i , t ( s ′ ∣ s , a ) P_{i,t}(s'\mid s,a) P i , t ( s ′ ∣ s , a ) , and its augmented state becomes ( s ′ , φ ( h , s ) ) (s',\varphi(h,s)) ( s ′ , φ ( h , s )) . Both depend on the joint state only through agent i i i ’s own pair ( s , a ) (s,a) ( s , a ) . For an augmented state ( s ′ , h ′ ) (s',h') ( s ′ , h ′ ) at time t + 1 t+1 t + 1 , summing over the pairs that lead to it therefore gives
d i , t + 1 π ( s ′ , h ′ ) = ∑ ( ( s , h ) , a ) : φ ( h , s ) = h ′ q i , t π ( ( s , h ) , a ) P i , t ( s ′ ∣ s , a ) . d^{\pi}_{i,t+1}(s',h')=\sum_{\substack{((s,h),a):\\ \varphi(h,s)=h'}}q^{\pi}_{i,t}((s,h),a)P_{i,t}(s'\mid s,a). d i , t + 1 π ( s ′ , h ′ ) = (( s , h ) , a ) : φ ( h , s ) = h ′ ∑ q i , t π (( s , h ) , a ) P i , t ( s ′ ∣ s , a ) .
The same relation holds for π i ′ ′ \pi''_i π i ′′ with q i , t π q^{\pi}_{i,t} q i , t π replaced by q i , t π ′ ′ q^{\pi''}_{i,t} q i , t π ′′ . Since q i , t π ′ ′ = q i , t π q^{\pi''}_{i,t}=q^{\pi}_{i,t} q i , t π ′′ = q i , t π , we obtain d i , t + 1 π ′ ′ = d i , t + 1 π d^{\pi''}_{i,t+1}=d^{\pi}_{i,t+1} d i , t + 1 π ′′ = d i , t + 1 π , completing the induction.
By (20) and d i , t π ′ ′ = d i , t π d^{\pi''}_{i,t}=d^{\pi}_{i,t} d i , t π ′′ = d i , t π , for every predecessor policy π ˉ [ i − 1 ] \bar{\pi}_{[i-1]} π ˉ [ i − 1 ] ,
G i π ˉ [ i − 1 ] ( π i ′ ′ ) = ∑ t = 0 H E s ~ i , t ∼ d i , t π ′ ′ [ r ˉ i , t π [ i − 1 ] ( s ~ i , t ) ] = ∑ t = 0 H E s ~ i , t ∼ d i , t π [ r ˉ i , t π [ i − 1 ] ( s ~ i , t ) ] . G^{\bar{\pi}_{[i-1]}}_i(\pi''_i)=\sum_{t=0}^{H}\mathbb{E}_{\tilde{s}_{i,t}\sim d^{\pi''}_{i,t}}\left[\bar{r}^{\pi_{[i-1]}}_{i,t}(\tilde{s}_{i,t})\right]=\sum_{t=0}^{H}\mathbb{E}_{\tilde{s}_{i,t}\sim d^{\pi}_{i,t}}\left[\bar{r}^{\pi_{[i-1]}}_{i,t}(\tilde{s}_{i,t})\right]. G i π ˉ [ i − 1 ] ( π i ′′ ) = t = 0 ∑ H E s ~ i , t ∼ d i , t π ′′ [ r ˉ i , t π [ i − 1 ] ( s ~ i , t ) ] = t = 0 ∑ H E s ~ i , t ∼ d i , t π [ r ˉ i , t π [ i − 1 ] ( s ~ i , t ) ] .
Proof of Lemma 5
Lemma 5. Under (11), with probability at least 1 − δ 1-\delta 1 − δ ,
∣ r ˉ i , t π ˉ [ i − 1 ] ( s ~ ) − r i , t π ˉ [ i − 1 ] ( s ~ ) ∣ ≤ ϵ \left|\bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s})-r^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s})\right|\le\epsilon r ˉ i , t π ˉ [ i − 1 ] ( s ~ ) − r i , t π ˉ [ i − 1 ] ( s ~ ) ≤ ϵ
for all i ≥ 2 i\ge2 i ≥ 2 , t t t , and s ~ ∈ S ~ t \tilde{s}\in\tilde{\mathcal{S}}_t s ~ ∈ S ~ t .
Proof. We adapt the concentration argument of Chen et al. [4 ] . Fix an agent i ≥ 2 i\ge2 i ≥ 2 , a time t t t , and a history-augmented state s ~ i , t ∈ S ~ t \tilde{s}_{i,t}\in\tilde{\mathcal{S}}_t s ~ i , t ∈ S ~ t . The empirical reward
r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) = 1 K ∑ k = 1 K Δ ( ( t , s i , t ) ∣ ν t ( h i , t ) ∪ τ [ i − 1 ] k ) \bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})=\frac{1}{K}\sum_{k=1}^{K}\Delta\left((t,s_{i,t})\mid\nu_t(h_{i,t})\cup\tau^{k}_{[i-1]}\right) r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) = K 1 k = 1 ∑ K Δ ( ( t , s i , t ) ∣ ν t ( h i , t ) ∪ τ [ i − 1 ] k )
is an average of marginal gains over K K K newly sampled predecessor trajectories. Conditional on the previously computed policies π ˉ [ i − 1 ] \bar{\pi}_{[i-1]} π ˉ [ i − 1 ] , these trajectories are independent and each marginal gain has mean r i , t π ˉ [ i − 1 ] ( s ~ i , t ) r^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t}) r i , t π ˉ [ i − 1 ] ( s ~ i , t ) . By monotonicity and submodularity, each marginal gain lies in [ 0 , R ] [0,R] [ 0 , R ] , where R = max v ∈ V F ( { v } ) R=\max_{v\in V}F(\{v\}) R = max v ∈ V F ({ v }) . Applying Hoeffding’s inequality (Lemma 8) conditionally gives
Pr ( ∣ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) ∣ > ϵ ∣ π ˉ [ i − 1 ] ) ≤ 2 exp ( − 2 K ϵ 2 R 2 ) . \Pr\left(\left|\bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})-r^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})\right|>\epsilon\mathrel{\big|}\bar{\pi}_{[i-1]}\right)\le2\exp\left(-\frac{2K\epsilon^2}{R^2}\right). Pr ( r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) > ϵ π ˉ [ i − 1 ] ) ≤ 2 exp ( − R 2 2 K ϵ 2 ) .
The bound holds for every realization of the predecessor policies. Averaging over the randomness used to compute these policies gives the same bound unconditionally.
Pr ( max i , t , s ~ i , t ∣ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) ∣ > ϵ ) ≤ ∑ i , t , s ~ i , t Pr ( ∣ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) ∣ > ϵ ) \Pr\left(\max_{i,t,\tilde{s}_{i,t}}\left|\bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})-r^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})\right|>\epsilon\right)\le\sum_{i,t,\tilde{s}_{i,t}}\Pr\left(\left|\bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})-r^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})\right|>\epsilon\right) Pr ( i , t , s ~ i , t max r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) > ϵ ) ≤ i , t , s ~ i , t ∑ Pr ( r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) > ϵ )
≤ 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 exp ( − 2 K ϵ 2 R 2 ) . \le2(N-1)(H+1)|\mathcal{S}|^{m+1}\exp\left(-\frac{2K\epsilon^2}{R^2}\right). ≤ 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 exp ( − R 2 2 K ϵ 2 ) .
This right-hand side is at most δ \delta δ if and only if 2 K ϵ 2 R 2 ≥ ln 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 δ \frac{2K\epsilon^2}{R^2}\ge\ln\frac{2(N-1)(H+1)|\mathcal{S}|^{m+1}}{\delta} R 2 2 K ϵ 2 ≥ ln δ 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 , that is, if and only if K K K satisfies (11). Therefore, with probability at least 1 − δ 1-\delta 1 − δ , ∣ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) ∣ ≤ ϵ \left|\bar{r}^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})-r^{\bar{\pi}_{[i-1]}}_{i,t}(\tilde{s}_{i,t})\right|\le\epsilon r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) ≤ ϵ for all i , t , s ~ i , t i,t,\tilde{s}_{i,t} i , t , s ~ i , t .
Proof of Lemma 6
Lemma 6. Let π ˉ i ∈ arg max π i ∈ Π m l o c G ^ i π ˉ [ i − 1 ] ( π i ) \bar{\pi}_i \in\arg\max_{\pi_i \in\Pi_m^{\mathrm{loc}}} \widehat{G}_i^{\bar{\pi}_{[i-1]}}(\pi_i) π ˉ i ∈ arg max π i ∈ Π m loc G i π ˉ [ i − 1 ] ( π i ) . If ∣ r ^ i , t π ˉ [ i − 1 ] ( s ~ ) − r ˉ i , t π ˉ [ i − 1 ] ( s ~ ) ∣ ≤ ϵ \left|\widehat{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s})-\bar{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s})\right|\le\epsilon r i , t π ˉ [ i − 1 ] ( s ~ ) − r ˉ i , t π ˉ [ i − 1 ] ( s ~ ) ≤ ϵ for all t t t and s ~ ∈ S ~ t \tilde{s}\in\widetilde{S}_t s ~ ∈ S t , then
G i π ˉ [ i − 1 ] ( π ˉ i ) ≥ max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) − 2 ( H + 1 ) ϵ . G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i)\ge\max_{\pi_i\in\Pi_m^{\mathrm{loc}}}G_i^{\bar{\pi}_{[i-1]}}(\pi_i)-2(H+1)\epsilon. G i π ˉ [ i − 1 ] ( π ˉ i ) ≥ π i ∈ Π m loc max G i π ˉ [ i − 1 ] ( π i ) − 2 ( H + 1 ) ϵ . For i = 1 i=1 i = 1 , π ˉ 1 \bar{\pi}_1 π ˉ 1 attains the maximum exactly.
Proof. Fix the predecessor policies π ˉ [ i − 1 ] \bar{\pi}_{[i-1]} π ˉ [ i − 1 ] . For any π i ∈ Π m l o c \pi_i\in\Pi_m^{\mathrm{loc}} π i ∈ Π m loc , the exact objective (22) is
G i π ˉ [ i − 1 ] ( π i ) = ∑ t = 0 H E s ~ i , t ∼ d i , t π i [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] . G_i^{\bar{\pi}_{[i-1]}}(\pi_i)=\sum_{t=0}^{H}\mathbb{E}_{\tilde{s}_{i,t}\sim d_{i,t}^{\pi_i}}\left[\bar{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})\right]. G i π ˉ [ i − 1 ] ( π i ) = t = 0 ∑ H E s ~ i , t ∼ d i , t π i [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] .
Algorithm 1 maximizes the estimated objective
G ^ i π ˉ [ i − 1 ] ( π i ) = ∑ t = 0 H E s ~ i , t ∼ d i , t π i [ r ^ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] , \widehat{G}_i^{\bar{\pi}_{[i-1]}}(\pi_i)=\sum_{t=0}^{H}\mathbb{E}_{\tilde{s}_{i,t}\sim d_{i,t}^{\pi_i}}\left[\widehat{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})\right], G i π ˉ [ i − 1 ] ( π i ) = t = 0 ∑ H E s ~ i , t ∼ d i , t π i [ r i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] ,
obtained from G ^ i π ˉ [ i − 1 ] \widehat{G}_i^{\bar{\pi}_{[i-1]}} G i π ˉ [ i − 1 ] by replacing the reward r ˉ i , t π ˉ [ i − 1 ] \bar{r}_{i,t}^{\bar{\pi}_{[i-1]}} r ˉ i , t π ˉ [ i − 1 ] with its estimate r ^ i , t π ˉ [ i − 1 ] \widehat{r}_{i,t}^{\bar{\pi}_{[i-1]}} r i , t π ˉ [ i − 1 ] . The state marginal d i , t π i d_{i,t}^{\pi_i} d i , t π i is identical in both objectives, since it is determined by agent i i i ’s dynamics and policy alone and does not depend on the reward. We bound the difference between the true and estimated objectives:
∣ G i π ˉ [ i − 1 ] ( π i ) − G ^ i π ˉ [ i − 1 ] ( π i ) ∣ = ∣ ∑ t = 0 H E s ~ i , t ∼ d i , t π i [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r ^ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] ∣ (linearity of expectation) ≤ ∑ t = 0 H E s ~ i , t ∼ d i , t π i [ ∣ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r ^ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ∣ ] (triangle inequality) ≤ ∑ t = 0 H ϵ = ( H + 1 ) ϵ . ( ∣ r ^ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ∣ ≤ ϵ ) \begin{aligned}
\left|G_i^{\bar{\pi}_{[i-1]}}(\pi_i)-\widehat{G}_i^{\bar{\pi}_{[i-1]}}(\pi_i)\right|
&=\left|\sum_{t=0}^{H}\mathbb{E}_{\tilde{s}_{i,t}\sim d_{i,t}^{\pi_i}}\left[\bar{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})-\widehat{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})\right]\right| \quad\text{(linearity of expectation)}\\
&\le\sum_{t=0}^{H}\mathbb{E}_{\tilde{s}_{i,t}\sim d_{i,t}^{\pi_i}}\left[\left|\bar{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})-\widehat{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})\right|\right] \quad\text{(triangle inequality)}\\
&\le\sum_{t=0}^{H}\epsilon=(H+1)\epsilon. \quad\left(\left|\widehat{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})-\bar{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})\right|\le\epsilon\right)
\end{aligned} G i π ˉ [ i − 1 ] ( π i ) − G i π ˉ [ i − 1 ] ( π i ) = t = 0 ∑ H E s ~ i , t ∼ d i , t π i [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] (linearity of expectation) ≤ t = 0 ∑ H E s ~ i , t ∼ d i , t π i [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] (triangle inequality) ≤ t = 0 ∑ H ϵ = ( H + 1 ) ϵ . ( r i , t π ˉ [ i − 1 ] ( s ~ i , t ) − r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ≤ ϵ )
Since the upper bound does not depend on π i \pi_i π i , removing the absolute value yields two inequalities that hold for all π i ∈ Π m l o c \pi_i\in\Pi_m^{\mathrm{loc}} π i ∈ Π m loc :
G ^ i π ˉ [ i − 1 ] ( π i ) − ( H + 1 ) ϵ ≤ G i π ˉ [ i − 1 ] ( π i ) , (26) \widehat{G}_i^{\bar{\pi}_{[i-1]}}(\pi_i)-(H+1)\epsilon\le G_i^{\bar{\pi}_{[i-1]}}(\pi_i), \tag*{(26)} G i π ˉ [ i − 1 ] ( π i ) − ( H + 1 ) ϵ ≤ G i π ˉ [ i − 1 ] ( π i ) , (26)
G i π ˉ [ i − 1 ] ( π i ) − ( H + 1 ) ϵ ≤ G ^ i π ˉ [ i − 1 ] ( π i ) . (27) G_i^{\bar{\pi}_{[i-1]}}(\pi_i)-(H+1)\epsilon\le\widehat{G}_i^{\bar{\pi}_{[i-1]}}(\pi_i). \tag*{(27)} G i π ˉ [ i − 1 ] ( π i ) − ( H + 1 ) ϵ ≤ G i π ˉ [ i − 1 ] ( π i ) . (27)
Because π ˉ i ∈ arg max π i ∈ Π m l o c G ^ i π ˉ [ i − 1 ] ( π i ) \bar{\pi}_i\in\arg\max_{\pi_i\in\Pi_m^{\mathrm{loc}}}\widehat{G}_i^{\bar{\pi}_{[i-1]}}(\pi_i) π ˉ i ∈ arg max π i ∈ Π m loc G i π ˉ [ i − 1 ] ( π i ) ,
G ^ i π ˉ [ i − 1 ] ( π i ) ≤ G ^ i π ˉ [ i − 1 ] ( π ˉ i ) for all π i ∈ Π m l o c . (28) \widehat{G}_i^{\bar{\pi}_{[i-1]}}(\pi_i)\le\widehat{G}_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i)\quad\text{for all }\pi_i\in\Pi_m^{\mathrm{loc}}. \tag*{(28)} G i π ˉ [ i − 1 ] ( π i ) ≤ G i π ˉ [ i − 1 ] ( π ˉ i ) for all π i ∈ Π m loc . (28)
Subtracting ( H + 1 ) ϵ (H+1)\epsilon ( H + 1 ) ϵ from both sides of (25) gives the left inequality below. Combining (26) with (24) at π ˉ i \bar{\pi}_i π ˉ i gives the right one. Hence, for all π i ∈ Π m l o c \pi_i\in\Pi_m^{\mathrm{loc}} π i ∈ Π m loc ,
G i π ˉ [ i − 1 ] ( π i ) − 2 ( H + 1 ) ϵ ≤ G ^ i π ˉ [ i − 1 ] ( π i ) − ( H + 1 ) ϵ ≤ G i π ˉ [ i − 1 ] ( π ˉ i ) . G_i^{\bar{\pi}_{[i-1]}}(\pi_i)-2(H+1)\epsilon\le\widehat{G}_i^{\bar{\pi}_{[i-1]}}(\pi_i)-(H+1)\epsilon\le G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i). G i π ˉ [ i − 1 ] ( π i ) − 2 ( H + 1 ) ϵ ≤ G i π ˉ [ i − 1 ] ( π i ) − ( H + 1 ) ϵ ≤ G i π ˉ [ i − 1 ] ( π ˉ i ) .
Taking the maximum of the left-hand side over π i ∈ Π m l o c \pi_i\in\Pi_m^{\mathrm{loc}} π i ∈ Π m loc gives the desired result:
max π i ∈ Π m l o c G i π ˉ [ i − 1 ] ( π i ) − 2 ( H + 1 ) ϵ ≤ G i π ˉ [ i − 1 ] ( π ˉ i ) . \max_{\pi_i\in\Pi_m^{\mathrm{loc}}}G_i^{\bar{\pi}_{[i-1]}}(\pi_i)-2(H+1)\epsilon\le G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i). π i ∈ Π m loc max G i π ˉ [ i − 1 ] ( π i ) − 2 ( H + 1 ) ϵ ≤ G i π ˉ [ i − 1 ] ( π ˉ i ) .
For i = 1 i=1 i = 1 the reward r ˉ 1 , t π ˉ [ 0 ] \bar{r}_{1,t}^{\bar{\pi}_{[0]}} r ˉ 1 , t π ˉ [ 0 ] is computed exactly, so G ^ 1 π ˉ [ 0 ] = G 1 π ˉ [ 0 ] \widehat{G}_1^{\bar{\pi}_{[0]}}=G_1^{\bar{\pi}_{[0]}} G 1 π ˉ [ 0 ] = G 1 π ˉ [ 0 ] , the error terms vanish, and π ˉ 1 \bar{\pi}_1 π ˉ 1 attains the maximum exactly.
Proof of Lemma 7
Lemma 7. For the policy π ˉ \bar{\pi} π ˉ returned by Algorithm 1,
( 1 − c m ) ∑ i ∈ [ N ] G i π ˉ [ i − 1 ] ( π ˉ i ) ≤ J ( π ˉ ) ≤ ∑ i ∈ [ N ] G i π ˉ [ i − 1 ] ( π ˉ i ) . (1-c_m)\sum_{i\in[N]}G_i^{\bar{\pi}[i-1]}(\bar{\pi}_i)\leq J(\bar{\pi})\leq\sum_{i\in[N]}G_i^{\bar{\pi}[i-1]}(\bar{\pi}_i). ( 1 − c m ) i ∈ [ N ] ∑ G i π ˉ [ i − 1 ] ( π ˉ i ) ≤ J ( π ˉ ) ≤ i ∈ [ N ] ∑ G i π ˉ [ i − 1 ] ( π ˉ i ) .
Proof. Fix a realization of the returned policy π ˉ \bar{\pi} π ˉ and a joint trajectory τ \tau τ generated under it. The trajectory determines the visited pairs τ i , t \tau_{i,t} τ i , t and the sets τ i , t − m : t − 1 \tau_{i,t-m:t-1} τ i , t − m : t − 1 , τ i , 0 : t − 1 \tau_{i,0:t-1} τ i , 0 : t − 1 , and τ [ i − 1 ] \tau_{[i-1]} τ [ i − 1 ] . Every relation up to the final expectation step holds for each such τ \tau τ separately, and all expectations below are over the initial states and the transition dynamics with π ˉ \bar{\pi} π ˉ held fixed. Adding the visits in lexicographic order of ( i , t ) (i,t) ( i , t ) gives
F ( τ ) = ∑ i ∈ [ N ] ∑ t = 0 H Δ ( τ i , t ∣ τ i , 0 : t − 1 ∪ τ [ i − 1 ] ) . (29) F(\tau)=\sum_{i\in[N]}\sum_{t=0}^{H}\Delta(\tau_{i,t}\mid\tau_{i,0:t-1}\cup\tau_{[i-1]}). \tag*{(29)} F ( τ ) = i ∈ [ N ] ∑ t = 0 ∑ H Δ ( τ i , t ∣ τ i , 0 : t − 1 ∪ τ [ i − 1 ] ) . (29)
For each agent i i i and time t t t , apply Lemma 3 with X t = τ i , t ⊆ V t X_t=\tau_{i,t}\subseteq\mathcal{V}_t X t = τ i , t ⊆ V t , B = τ i , 0 : t − m − 1 B=\tau_{i,0:t-m-1} B = τ i , 0 : t − m − 1 , and Z = τ i , t − m : t − 1 ∪ τ [ i − 1 ] Z=\tau_{i,t-m:t-1}\cup\tau_{[i-1]} Z = τ i , t − m : t − 1 ∪ τ [ i − 1 ] . Since B ∪ Z = τ i , 0 : t − 1 ∪ τ [ i − 1 ] B\cup Z=\tau_{i,0:t-1}\cup\tau_{[i-1]} B ∪ Z = τ i , 0 : t − 1 ∪ τ [ i − 1 ] , we obtain
Δ ( τ i , t ∣ τ i , 0 : t − 1 ∪ τ [ i − 1 ] ) ≥ ( 1 − c m ) Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) . \Delta(\tau_{i,t}\mid\tau_{i,0:t-1}\cup\tau_{[i-1]})\geq(1-c_m)\Delta(\tau_{i,t}\mid\tau_{i,t-m:t-1}\cup\tau_{[i-1]}). Δ ( τ i , t ∣ τ i , 0 : t − 1 ∪ τ [ i − 1 ] ) ≥ ( 1 − c m ) Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) .
while submodularity ( τ i , t − m : t − 1 ⊆ τ i , 0 : t − 1 ) (\tau_{i,t-m:t-1}\subseteq\tau_{i,0:t-1}) ( τ i , t − m : t − 1 ⊆ τ i , 0 : t − 1 ) gives
Δ ( τ i , t ∣ τ i , 0 : t − 1 ∪ τ [ i − 1 ] ) ≤ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) . \Delta(\tau_{i,t}\mid\tau_{i,0:t-1}\cup\tau_{[i-1]})\leq\Delta(\tau_{i,t}\mid\tau_{i,t-m:t-1}\cup\tau_{[i-1]}). Δ ( τ i , t ∣ τ i , 0 : t − 1 ∪ τ [ i − 1 ] ) ≤ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) .
For every joint trajectory τ \tau τ , summing the preceding inequalities over i ∈ [ N ] i\in[N] i ∈ [ N ] and t ∈ { 0 , … , H } t\in\{0,\ldots,H\} t ∈ { 0 , … , H } and using (27) yields
( 1 − c m ) ∑ i ∈ [ N ] ∑ t = 0 H Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ≤ F ( τ ) ≤ ∑ i ∈ [ N ] ∑ t = 0 H Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) . (1-c_m)\sum_{i\in[N]}\sum_{t=0}^{H}\Delta(\tau_{i,t}\mid\tau_{i,t-m:t-1}\cup\tau_{[i-1]})\leq F(\tau)\leq\sum_{i\in[N]}\sum_{t=0}^{H}\Delta(\tau_{i,t}\mid\tau_{i,t-m:t-1}\cup\tau_{[i-1]}). ( 1 − c m ) i ∈ [ N ] ∑ t = 0 ∑ H Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ≤ F ( τ ) ≤ i ∈ [ N ] ∑ t = 0 ∑ H Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) .
Taking expectations over τ ∼ π ˉ \tau\sim\bar{\pi} τ ∼ π ˉ gives E [ F ( τ ) ] = J ( π ˉ ) \mathbb{E}[F(\tau)]=J(\bar{\pi}) E [ F ( τ )] = J ( π ˉ ) , as defined in (3). By linearity of expectation, each expected sum of marginal gains equals the sum of the corresponding expectations, yielding
( 1 − c m ) ∑ i ∈ [ N ] ∑ t = 0 H E τ ∼ π ˉ [ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ] ≤ J ( π ˉ ) ≤ ∑ i ∈ [ N ] ∑ t = 0 H E τ ∼ π ˉ [ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ] . (30) (1-c_m)\sum_{i\in[N]}\sum_{t=0}^{H}\mathbb{E}_{\tau\sim\bar{\pi}}\left[\Delta(\tau_{i,t}\mid\tau_{i,t-m:t-1}\cup\tau_{[i-1]})\right]\leq J(\bar{\pi})\leq\sum_{i\in[N]}\sum_{t=0}^{H}\mathbb{E}_{\tau\sim\bar{\pi}}\left[\Delta(\tau_{i,t}\mid\tau_{i,t-m:t-1}\cup\tau_{[i-1]})\right]. \tag*{(30)} ( 1 − c m ) i ∈ [ N ] ∑ t = 0 ∑ H E τ ∼ π ˉ [ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ] ≤ J ( π ˉ ) ≤ i ∈ [ N ] ∑ t = 0 ∑ H E τ ∼ π ˉ [ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ] . (30)
For each agent i i i and time t t t , the marginal gain in (28) depends only on the augmented state s ~ i , t \tilde{s}_{i,t} s ~ i , t and the predecessors’ visited set τ [ i − 1 ] \tau_{[i-1]} τ [ i − 1 ] , since s ~ i , t \tilde{s}_{i,t} s ~ i , t determines τ i , t \tau_{i,t} τ i , t and τ i , t − m : t − 1 = ν t ( h i , t ) \tau_{i,t-m:t-1}=\nu_t(h_{i,t}) τ i , t − m : t − 1 = ν t ( h i , t ) . Under the fixed policy π ˉ ∈ Π m l o c \bar{\pi}\in\Pi_m^{\mathrm{loc}} π ˉ ∈ Π m loc , independent initial states and decoupled dynamics imply that s ~ i , t \tilde{s}_{i,t} s ~ i , t and τ [ i − 1 ] \tau_{[i-1]} τ [ i − 1 ] are independent. The expectation therefore decomposes as
E τ ∼ π ˉ [ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ] = E s ~ i , t ∼ d i , t π ˉ i [ E τ [ i − 1 ] ∼ π ˉ [ i − 1 ] [ Δ ( ( t , s i , t ) ∣ ν t ( h i , t ) ∪ τ [ i − 1 ] ) ] ] = E s ~ i , t ∼ d i , t π ˉ i [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] , \begin{aligned}
\mathbb{E}_{\tau\sim\bar{\pi}}\left[\Delta(\tau_{i,t}\mid\tau_{i,t-m:t-1}\cup\tau_{[i-1]})\right]=\mathbb{E}_{\tilde{s}_{i,t}\sim d_{i,t}^{\bar{\pi}_i}}\left[\mathbb{E}_{\tau_{[i-1]}\sim\bar{\pi}_{[i-1]}}\left[\Delta((t,s_{i,t})\mid\nu_t(h_{i,t})\cup\tau_{[i-1]})\right]\right] \\
&=\mathbb{E}_{\tilde{s}_{i,t}\sim d_{i,t}^{\bar{\pi}_i}}\left[\bar{r}_{i,t}^{\bar{\pi}_{[i-1]}}(\tilde{s}_{i,t})\right],
\end{aligned} E τ ∼ π ˉ [ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ] = E s ~ i , t ∼ d i , t π ˉ i [ E τ [ i − 1 ] ∼ π ˉ [ i − 1 ] [ Δ (( t , s i , t ) ∣ ν t ( h i , t ) ∪ τ [ i − 1 ] ) ] ] = E s ~ i , t ∼ d i , t π ˉ i [ r ˉ i , t π ˉ [ i − 1 ] ( s ~ i , t ) ] ,
where the second equality follows from the definition of the local stage reward in (8). Summing over t ∈ { 0 , … , H } t\in\{0,\ldots,H\} t ∈ { 0 , … , H } and using (20) gives
∑ t = 0 H E τ ∼ π ˉ [ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ] = G i π ˉ [ i − 1 ] ( π ˉ i ) . \sum_{t=0}^{H}\mathbb{E}_{\tau\sim\bar{\pi}}\left[\Delta(\tau_{i,t}\mid\tau_{i,t-m:t-1}\cup\tau_{[i-1]})\right]=G_i^{\bar{\pi}_{[i-1]}}(\bar{\pi}_i). t = 0 ∑ H E τ ∼ π ˉ [ Δ ( τ i , t ∣ τ i , t − m : t − 1 ∪ τ [ i − 1 ] ) ] = G i π ˉ [ i − 1 ] ( π ˉ i ) .
Substituting this equality for each i ∈ [ N ] i\in[N] i ∈ [ N ] into (28) establishes the claimed bounds.
Hoeffding's Inequality
For completeness, we recall the concentration inequality used in the proof of Lemma 5.
Lemma 8 (Hoeffding’s inequality [8 ] ). Let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n be independent random variables with X l ∈ [ a , b ] X_l\in[a,b] X l ∈ [ a , b ] , and let X ˉ = 1 n ∑ l = 1 n X l \bar{X}=\frac{1}{n}\sum_{l=1}^{n}X_l X ˉ = n 1 ∑ l = 1 n X l with mean μ = E [ X ˉ ] \mu=\mathbb{E}[\bar{X}] μ = E [ X ˉ ] . Then for every ϵ > 0 \epsilon>0 ϵ > 0 ,
Pr ( ∣ X ˉ − μ ∣ ≥ ϵ ) ≤ 2 exp ( − 2 n ϵ 2 ( b − a ) 2 ) . \Pr\left(|\bar{X}-\mu|\geq\epsilon\right)\leq2\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right). Pr ( ∣ X ˉ − μ ∣ ≥ ϵ ) ≤ 2 exp ( − ( b − a ) 2 2 n ϵ 2 ) .
Experimental Details
Environment and Evaluation
The traffic-monitoring instance uses a 20 × 20 20 \times20 20 × 20 grid and horizon H = 20 H = 20 H = 20 . Each UAV moves deterministically to an adjacent node or hovers. An action that leaves the grid keeps the UAV in place. Initial positions in the reported comparisons are sampled independently and uniformly over grid nodes.
The road map is generated with seed 17 and fixed across methods and algorithm seeds. Road importance is not uniform across the grid. As in real urban networks, a few congested regions require more frequent monitoring than the rest. We model this pattern with two regions of high-importance roads. For roads outside these regions, the maximum importance w e w_e w e is sampled from N ( 1.5 , 1 2 ) \mathcal{N}(1.5, 1^2) N ( 1.5 , 1 2 ) and clipped to [ 0 , 3.5 ] [0, 3.5] [ 0 , 3.5 ] . For roads inside these regions, w e w_e w e is sampled from N ( 3.5 , 0.5 2 ) \mathcal{N}(3.5, 0.5^2) N ( 3.5 , 0. 5 2 ) and clipped to [ 2.5 , 5.5 ] [2.5, 5.5] [ 2.5 , 5.5 ] .
Road importance recovers according to α ℓ = 1 − e − β ℓ \alpha_\ell= 1 - e^{-\beta\ell} α ℓ = 1 − e − β ℓ . In the time-additive case, α ℓ = 1 \alpha_\ell= 1 α ℓ = 1 for every positive gap. Returns are divided by ∑ e ∈ E w e \sum_{e\in E} w_e ∑ e ∈ E w e , the sum of the maximum importances of all roads. Repeated visits after recovery can contribute additional reward, so the normalized horizon return can exceed one.
Policy evaluation. Every policy is evaluated by its return J J J on 10,000 common initial joint states. During evaluation, SuBPO selects the action with the highest probability for each UAV, while GWPO and GPO return deterministic policies. All reported confidence intervals are computed across algorithm seeds using Student’s t t t -distribution at the 95% confidence level, with a fixed map and evaluation states.
The memory comparison in Figure 2 (a) uses N = 20 N = 20 N = 20 , m ∈ { 0 , 1 , 2 , 3 } m \in\{0, 1, 2, 3\} m ∈ { 0 , 1 , 2 , 3 } , and five algorithm seeds. For each seed, we express the return improvement of GWPO over GPO as a percentage of the GPO return, and then average these percentages across seeds. In Figure 3 , each SuBPO variant uses five training seeds, while GWPO with m = 3 m = 3 m = 3 and GPO each use a single seed. In the figure, each return gap is measured relative to the GWPO return from this single seed. The confidence intervals of the gaps therefore reflect only the variation across SuBPO seeds.
Figure 3. Return gap between each baseline and GWPO with m = 3 m = 3 m = 3 at β = 0.4 \beta= 0.4 β = 0.4 , as a percentage of the GWPO return. Negative values indicate higher returns for GWPO. SubPO-M and SubPO-NM are allowed computation times of (a) T N T_N T N , (b) 5 T N 5T_N 5 T N , and (c) 20 T N 20T_N 20 T N , where T N T_N T N is the computation time of GWPO for N N N agents.
Algorithm Settings and Hyperparameter Selection
GWPO and GPO. GWPO estimates local stage rewards using (10) and optimizes each local policy by backward induction on the augmented states. GPO uses the same number of sampled trajectories as GWPO with m = 0 m = 0 m = 0 . GWPO computes marginal gains given full predecessor trajectories and the agent’s own m m m -step history, whereas GPO uses only predecessor visits at the current time. Thus, the two methods differ even when m = 0 m = 0 m = 0 . Table 1 reports the pre-window curvature and the multiplicative factor in Theorem 2. These factors exclude the additive error term.
Table 1. Pre-window curvature c m = e − β ( m + 1 ) c_m = e^{-\beta(m+1)} c m = e − β ( m + 1 ) and the approximation factor ( 1 − c m ) / ( 2 − c m ) (1 - c_m)/(2 - c_m) ( 1 − c m ) / ( 2 − c m ) of Theorem 2 for the traffic-monitoring reward at the listed recovery rates β \beta β and memory lengths m m m .
Number of sampled trajectories. We fix δ = 10 − 6 \delta= 10^{-6} δ = 1 0 − 6 . For each sample count K K K , the sample-size bound (11) then gives the tolerance
ϵ = R 1 2 K ln 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 δ . \epsilon= R\sqrt{\frac{1}{2K}\ln\frac{2(N-1)(H+1)|\mathcal{S}|^{m+1}}{\delta}}. ϵ = R 2 K 1 ln δ 2 ( N − 1 ) ( H + 1 ) ∣ S ∣ m + 1 .
Here R ≈ 0.0105 R \approx0.0105 R ≈ 0.0105 for the reward.
Table 2 reports the return J J J for five sample counts at each N = 6 N = 6 N = 6 and N = 20 N = 20 N = 20 . We used GWPO with m = 3 m = 3 m = 3 , β = 0.4 \beta= 0.4 β = 0.4 , and uniform initial state distributions. Each setting was run with seeds { 1 , 2 , 3 } \{1, 2, 3\} { 1 , 2 , 3 } , and all policies were
Table 2. Sample counts K K K , associated ϵ \epsilon ϵ , and returns J J J for GWPO with m = 3 m = 3 m = 3 , β = 0.4 \beta= 0.4 β = 0.4 , and uniform initial state distributions. We fix δ = 10 − 6 \delta= 10^{-6} δ = 1 0 − 6 . Each return is the mean over seeds { 1 , 2 , 3 } \{1, 2, 3\} { 1 , 2 , 3 } with its 95% confidence interval. The second row gives the counts used in the remaining experiments.
evaluated on the same 10,000 initial joint states. As increasing K K K did not noticeably change the return, we ran the remaining experiments with ϵ ≈ 3.8 × 10 − 3 \epsilon\approx3.8 \times10^{-3} ϵ ≈ 3.8 × 1 0 − 3 for all N N N to reduce computation.
SubPO architectures. Both SubPO variants receive one-hot encodings of the joint state and time. SubPO-M processes these inputs with a feedforward ReLU network, while SubPO-NM uses a ReLU encoder followed by a single-layer GRU with the same hidden width as the encoder. Both networks output a probability distribution over the actions of each UAV.
SubPO hyperparameter selection. For each team size and SubPO variant, we considered networks with { 1 , 2 } \{1, 2\} { 1 , 2 } ReLU layers, hidden widths { 256 , 512 } \{256, 512\} { 256 , 512 } , and learning rates { 10 − 3 , 3 × 10 − 4 } \{10^{-3}, 3 \times10^{-4}\} { 1 0 − 3 , 3 × 1 0 − 4 } . For SubPO-NM, these layers precede the GRU. Batch sizes were 128 for SubPO-M and 256 for SubPO-NM. An epoch is one gradient update on a fresh batch of trajectories. Table 3 reports the selected hyperparameters.
Table 3. Selected neural network architectures and hyperparameters for SubPO. Depth denotes the number of ReLU layers; the recurrent policy additionally uses one GRU layer.
Hyperparameter selection used β = 0.1 \beta= 0.1 β = 0.1 and independent nonuniform initial distributions concentrated around a fixed grid node for each UAV. Each configuration was trained for 10,000 epochs and evaluated every 500 epochs on 4,000 fixed validation initial joint states.
For each team size and variant, we selected the configuration with the highest validation return and used it for all comparisons with uniform initial positions and β ∈ { 0.1 , 0.4 , 0.8 } \beta\in\{0.1, 0.4, 0.8\} β ∈ { 0.1 , 0.4 , 0.8 } . Hyperparameter selection time is excluded from the computation-time budgets.
Computation-Time Budgets and Policy Selection
Computation-time budgets. Let T N T_N T N be the measured computation time of GWPO with m = 3 m = 3 m = 3 for N N N agents. GWPO and GPO run one job at a time on one AMD Ryzen 9 9950X3D CPU core, while SubPO uses an NVIDIA RTX PRO 6000 GPU with one CPU thread per run. For all methods, the computation time covers algorithm setup and policy optimization. For GWPO and GPO, it includes trajectory sampling and reward estimation, as well as building the augmented state spaces for GWPO. For SubPO, it includes training and the validations during training. Environment initialization and final test evaluation are excluded. The GWPO and GPO policies are held fixed across the budgets T N T_N T N , 5 T N 5T_N 5 T N , and 20 T N 20T_N 20 T N .
We train several SubPO runs in parallel, so the elapsed time of each run may overstate its computation time. We therefore convert each computation-time budget into a number of epochs, using separate calibration runs executed one at a time. For each team size and variant, the calibration process uses three seeds at β = 0.4 \beta=0.4 β = 0.4 . Using the number of epochs completed by T N T_N T N , we estimate the counts at 5 T N 5T_N 5 T N and 20 T N 20T_N 20 T N by extrapolating the number of epochs completed between T N / 2 T_N/2 T N /2 and T N T_N T N . We take the largest estimate across calibration seeds and add a 10% allowance. We use the same epoch budgets for all training seeds and recovery rates, assuming that the cost of an epoch does not change across recovery rates or over training.
Training and policy selection. During each SubPO training run, we evaluated the greedy policy every 500 epochs on a fixed validation set of 4,000 uniformly sampled initial joint states, generated independently of the test set. We used these validation returns both to decide when to stop training and to select a policy for each epoch budget. After at least 10,000 epochs, training stopped once ten consecutive validations showed no significant improvement. An improvement was significant if the return exceeded J r e f J_{\mathrm{ref}} J ref by more than max { 10 − 4 , 10 − 3 ∣ J r e f ∣ } \max\{10^{-4},10^{-3}|J_{\mathrm{ref}}|\} max { 1 0 − 4 , 1 0 − 3 ∣ J ref ∣ } . Each such improvement updated J r e f J_{\mathrm{ref}} J ref and reset the counter.
For each computation-time budget, we selected the policy with the highest validation return reached within that budget. If a run stopped early because of the stopping criterion, we used its policy with the highest validation return for every larger budget. The selected policies were then evaluated on the test set.
Additional Results
Figure 8 and Table 4 report returns J J J at β = 0.4 \beta=0.4 β = 0.4 corresponding to the return gaps in Figure 3 .
Figure 8. (a) Time budget T N T_N T N (b) Time budget 5 T N 5T_N 5 T N (c) Time budget 20 T N 20T_N 20 T N . Returns of GWPO with m = 3 m=3 m = 3 , GPO, and the two SubPO variants at β = 0.4 \beta=0.4 β = 0.4 . From left to right, the allowed computation times for SubPO are T N T_N T N , 5 T N 5T_N 5 T N , and 20 T N 20T_N 20 T N . SubPO curves show means over five training seeds with 95% confidence intervals. GWPO and GPO each use a single seed.
Table 4. Returns of the selected policies at β = 0.4 \beta= 0.4 β = 0.4 with uniform initial state distributions. The SubPO budgets use the isolated timing calibration and 10% allowance described above. Each SubPO entry is the mean over five training seeds ± the half-width of its 95% confidence interval. GWPO with m = 3 m = 3 m = 3 uses seed 1. Intervals describe training-seed variation on the fixed map and evaluation states.
Figure 9 extends the comparison of Figure 3 to β = 0.1 \beta=0.1 β = 0.1 and β = 0.8 \beta=0.8 β = 0.8 .
Figure 9. Return differences between each baseline and GWPO with m = 3 m = 3 m = 3 , expressed as percentages of the GWPO return, at β = 0.1 \beta= 0.1 β = 0.1 (top) and β = 0.8 \beta= 0.8 β = 0.8 (bottom). Negative values indicate higher returns for GWPO. From left to right, the allowed computation times for SubPO are T N T_N T N , 5 T N 5T_N 5 T N , and 20 T N 20T_N 20 T N . SubPO curves show means over five training seeds with 95% confidence intervals. GWPO and GPO each use a single seed.
Figure 10 shows the training curves. Among the runs shown, all except SubPO-NM at N = 20 N=20 N = 20 stopped before the 20 T N 20T_N 20 T N budget.
Figure 10. Training of SubPO-M and SubPO-NM at β = 0.4 \beta= 0.4 β = 0.4 . Curves show the highest validation return reached by each epoch, averaged over five training runs with 95% confidence intervals. A curve ends when all five runs have stopped. Markers indicate the epoch budgets corresponding to T N T_N T N , 5 T N 5T_N 5 T N , and 20 T N 20T_N 20 T N that fall within each curve. The horizontal line shows the test return of GWPO with m = 3 m = 3 m = 3 .