Paper deep dive
Submodular Policy Learning for Distributed Task Allocation in Open Multi-Agent Systems
Jing Liu, Luca Ballotta, Yangyang Yang, Fangfei Li, Yang Tang, Ruggero Carli
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/17/2026, 3:41:42 AM
Summary
This paper introduces SubMAPL, a policy learning method for distributed task allocation in open multi-agent systems (OMAS) where agents join and leave dynamically. The authors address the mismatch between standard continuous relaxations of submodular functions (based on Bernoulli sampling) and decentralized categorical policies by proposing the Partition Multilinear Extension (PME). SubMAPL uses a centralized-training decentralized-execution framework with KL-mirror updates to maximize the PME, which serves as an unbiased estimator for the gradient of the stage utility. The method includes mechanisms for open policy migration and KL tracking to handle agent arrivals and departures, with theoretical guarantees on dynamic regret and cumulative utility.
Entities (8)
Relation Signals (6)
Jing Liu → affiliatedwith → East China University of Science and Technology
confidence 95% · Jing Liu and Yangyang Yang are with the School of Mathematics, East China University of Science and Technology
Luca Ballotta → affiliatedwith → University of Padova
confidence 95% · Luca Ballotta and Ruggero Carli are with the Department of Information Engineering, University of Padova
SubMAPL → appliesto → Open Multi-Agent Systems
confidence 95% · This paper studies policy learning for distributed task allocation in open multi-agent systems ... we design SubMAPL
SubMAPL → uses → Partition Multilinear Extension
confidence 95% · SubMAPL ... uses local marginal gains as stochastic PME gradients during training.
SubMAPL → employs → KL-mirror updates
confidence 90% · SubMAPL, a centralized-training decentralized-execution KL-mirror policy-learning method
Partition Multilinear Extension → solvesmismatchwith → categorical policies
confidence 90% · To solve this mismatch, we propose the partition multilinear extension (PME), a policy-based relaxation whose continuous support matches feasible actions under categorical policies.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This paper studies policy learning for distributed task allocation in open multi-agent systems, where agents may join and leave in a time-varying fashion, with submodular stage team utilities. At each time, the active agents select actions from local categorical policies such that the feasible joint agent-action pairs form a partition matroid. Standard continuous relaxations of submodular set functions are based on independent Bernoulli sampling, making them inconsistent with agents' this http URL solve this mismatch, we propose the \emph{partition multilinear extension} (PME), a policy-based relaxation whose continuous support matches feasible actions under categorical this http URL prove that the marginal gains of the stage utility provide an unbiased estimator of the gradient of the PME and that maximizing the PME over action distributions is equivalent to maximizing the stage utilities over agent actions, which are critical to devise principled policy this http URL on this, we design \emph{SubMAPL}, a centralized-training decentralized-execution KL-mirror policy-learning method that uses local marginal gains as stochastic PME gradients during training. KL-mirror updates preserve categorical feasibility without Euclidean this http URL the case where agents run tabular-softmax policies, we introduce open policy migration and an open-system KL tracking variation to handle agent arrivals and departures. Using dynamic regret analysis, we establish a lower bound on the cumulative utility which accounts for the openness of the environment and for the gap between optimal stage-wise and global utilities. Simulations on multi-agent coverage demonstrate that SubMAPL outperforms policy-gradient and online-learning baselines.
Tags
Links
- Source: https://arxiv.org/abs/2608.14390v1
- Canonical: https://arxiv.org/abs/2608.14390v1
Trouble viewing inline? Open PDF directly →
Full Text
106,057 characters extracted from source content.
Expand or collapse full text
Submodular Policy Learning for Distributed Task Allocation in Open Multi-Agent Systems Jing Liu Luca Ballotta Yangyang Yang Fangfei Li Yang Tang and Ruggero Carli Thanks: This work is supported by the Program of China Scholarship Council under Grant 202506740033, the National Key R&D Program of China under Grant 2025YFA1016504, the National Natural Science Foundation of China under Grants 62233005, 62573198, U2441245, U25B6002, 62403141, the National Key Laboratory of Space Target Awareness under Grant STA2025ZCB0208, in part by the Shanghai Institute for Mathematics and Interdisciplinary Sciences (SIMIS) under Grant SIMIS-ID-2025-SP. (Corresponding authors: Fangfei Li and Yang Tang.) Thanks: Jing Liu and Yangyang Yang are with the School of Mathematics, East China University of Science and Technology, Shanghai 200237, China (e-mail: y20220091@mail.ecust.edu.cn; y20250091@mail.ecust.edu.cn). Thanks: Luca Ballotta and Ruggero Carli are with the Department of Information Engineering, University of Padova, 35131 Padova, Italy (e-mail: luca.ballotta@unipd.it; ruggero.carli@unipd.it). Thanks: Fangfei Li is with the School of Mathematics and the Key Laboratory of Smart Manufacturing in Energy Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China (e-mail: li_fangfei@163.com, lifangfei@ecust.edu.cn). Thanks: Yang Tang is with the Key Laboratory of Smart Manufacturing in Energy Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China (e-mail: yangtang@ecust.edu.cn). Abstract This paper studies policy learning for distributed task allocation in open multi-agent systems, where agents may join and leave in a time-varying fashion, with submodular stage team utilities. At each time, the active agents select actions from local categorical policies such that the feasible joint agent-action pairs form a partition matroid. Standard continuous relaxations of submodular set functions are based on independent Bernoulli sampling, making them inconsistent with agents’ policies. To solve this mismatch, we propose the partition multilinear extension (PME), a policy-based relaxation whose continuous support matches feasible actions under categorical policies. We prove that the marginal gains of the stage utility provide an unbiased estimator of the gradient of the PME and that maximizing the PME over action distributions is equivalent to maximizing the stage utilities over agent actions, which are critical to devise principled policy gradient. Building on this, we design SubMAPL, a centralized-training decentralized-execution KL-mirror policy-learning method that uses local marginal gains as stochastic PME gradients during training. KL-mirror updates preserve categorical feasibility without Euclidean projection. In the case where agents run tabular-softmax policies, we introduce open policy migration and an open-system KL tracking variation to handle agent arrivals and departures. Using dynamic regret analysis, we establish a lower bound on the cumulative utility which accounts for the openness of the environment and for the gap between optimal stage-wise and global utilities. Simulations on multi-agent coverage demonstrate that SubMAPL outperforms policy-gradient and online-learning baselines. Index Terms: Open multi-agent systems, submodular optimization, multi-agent reinforcement learning, distributed task allocation, policy learning. I Introduction Multi-agent task allocation in open multi-agent systems (OMAS) arises in dynamic target tracking, active sensing, and coverage, where agents must coordinate local decisions under time-varying participation, limited communication, and non-additive team utilities. In long-duration deployments, agents may enter, leave, fail, or recover due to hardware malfunctions, battery recharging, or mission-level reconfiguration [38, 36, 10]. A central feature of such tasks is that utility functions are rarely additive across agents. For instance, overlapping field-of-views capture redundant information in coverage tasks. This so-called diminishing-returns structure is naturally modeled by monotone submodular set functions [13, 33, 35]. Submodularity has been extensively used in combinatorial optimization because it enables approximation guarantees for greedy selection under matroid constraints [23, 11, 36, 20] and the use of continuous relaxations such as the multilinear extension (MLE) with rounding [5, 42]. While these approaches are mostly tailored to static centralized optimization and task allocation and require dense communication graphs for consensus, the benefits of submodularity in learning data-driven multi-agent policies are underexplored. Multi-agent reinforcement learning (MARL) is widespread to learn decentralized agent policies under partial observability and dynamical environment [38, 22, 37]. Although the interplay between MARL and submodularity has been studied, existing results are limited to centralized settings [26, 9, 8]. On the other hand, OMASs have garnered attention in the online learning literature, where submodularity-based methods enable suboptimality quantification of online optimization algorithms rather than learnable policies [36, 42, 41]. Incorporating submodular utilities into the learning of distributed policies is challenging. Static submodular problems are NP-hard in general and admit approximation guarantees rather than exact polynomial-time solutions [23, 11, 5]. The data-driven and dynamic nature of multi-agent policy learning introduces additional challenges compared to static optimization. First, the gradient feedback signal used in training must be consistent with decentralized categorical policies. However, classical multilinear relaxations rely on independent Bernoulli sampling and rounding, and therefore do not represent factorized categorical policies executed by agents [5, 42]. Moreover, the combinatorial difficulty is coupled with sequential state evolution, decentralized information, and exponentially growing joint action space which demands careful credit assignment [38, 22, 37]. Existing submodular RL formulations target centralized policies rather than fully distributed decision-making [26, 9, 8]. Contribution Building on the PME and its gradient characterization introduced in our preliminary work [21], we propose three main contributions to bridge the above mentioned gaps. (1) We formulate distributed online submodular coordination as Markov decision process (MDP) in an OMAS and develop SubMAPL, a KL-mirror policy-learning method for decentralized submodular task allocation. Unlike sampled-action difference-reward policy gradients and counterfactual credit-assignment methods [12, 6, 21], SubMAPL uses a stochastic local gradient that evaluates every feasible local action of each active agent under the same sampled actions of the other agents. We show that this vector is an unbiased estimator of the PME coordinate gradient, thereby providing a principled first-order interpretation of marginal-contribution feedback. (2) We introduce an open policy-migration mechanism to handle agent arrivals and departures, and define an open-system KL tracking variation that measures changes in both the stagewise optimal comparator and the time-varying policy domain. Our preliminary work [21] establishes guarantees for idealized Euclidean projected dynamics that directly update the PME marginals. However, the standard softmax policy-gradient implementation updates the logits, and the resulting marginal change depends on the softmax Jacobian and agrees with PME ascent only to first order. SubMAPL admits an exact equivalence between its KL-mirror policy update and an additive tabular-logit update. This removes the first-order mismatch between the analyzed policy-space dynamics and the implemented parameter update, allowing us to establish open-system guarantees directly for the policy sequence generated under agent arrivals and departures. (3) By leveraging dynamic regret analysis in conjunction with DR-submodularity and monotonicity of the PME, we establish a lower bound on the cumulative utility within a 1/21/2-approximation factor from the optimum. We further establish a 1/31/3-factor bound in the case where the stage utilities are themselves marginal gains of a utility function capturing performance through the whole horizon, including scenarios such as coverage of static maps. These results complement previous analysis on stability and adaptability of open systems [10, 2]. Our analysis significantly improves our preliminary work [21], which derives a stagewise bound on the PME and a regret bound on the cumulative PME without formal guarantees on the original finite-horizon cumulative utility. Organization Section I formulates distributed submodular coordination as an MDP in OMAS. Section I introduces the PME and its properties. Section IV presents SubMAPL and Section V derives its suboptimality bound. Section VI reports simulations, and Section VII concludes the paper. Notation We use ℕN to denote the set of positive integers and define [T]=1,…,T[T]=\1,…,T\ for any T∈ℕT . For a finite set S, |S||S| denotes its cardinality and 2S2^S denotes its power set. For sets A and B, A∖BA B, A∪BA∪ B, and A∩BA∩ B denote set difference, union, and intersection, respectively. For a scalar z, [z]+=maxz,0[z]_+= \z,0\. For vectors x and y, x≤yx≤ y denotes componentwise inequality and ⟨x,y⟩ x,y denotes the Euclidean inner product. We use ∇f(x)∇ f(x) and ∂f/∂xi∂ f/∂ x_i for gradients and partial derivatives, respectively. Expectations and probabilities are denoted by [⋅]E[·] and Pr(⋅) (·). The Kullback–Leibler divergence is denoted by DKL(⋅∥⋅)D_ KL(·\|·). Standard asymptotic notation is denoted by O(⋅)O(·) and o(⋅)o(·). Table I summarizes the main paper-specific notation. Table I: Main notation in the paper. Symbol Meaning ℳM Markov decision process in OMAS. tN_t Set of active agents at time t. ℛtR_t Set of agents active at both times t−1t-1 and t. tinN_t in Set of agents arriving at time t. toutN_t out Set of agents departing at time t. S Global state space. sts_t Global state at time t. iA_i Local action space of agent i. oi,to_i,t Local observation of agent i at time t. ai,ta_i,t Local action selected by agent i at time t. ta_t Joint action tuple (ai,t)i∈t(a_i,t)_i _t. Ωt _t Active agent-action space at time t. Ωi,t _i,t Local agent-action space of agent i at time t. ℐtI_t Partition-matroid feasible family on Ωt _t. AtA_t Set of agent-action pairs executed at time t. Ft(At,st)F_t(A_t;s_t) Stage utility at time t. πiπ^i Local categorical policy of agent i. π Sequence of factorized policies with active agents. pπp^π Distribution of state-action trajectory under π. J(π)J(π) Expected cumulative utility under π. xtπ(st)x_t^π(s_t) Policy-induced action marginal vector at state sts_t. (ℐt)P(I_t) Partition-matroid polytope at time t. ℱtF_t Categorical-policy face of (ℐt)P(I_t). f~t(⋅,st) f_t(·;s_t) Partition multilinear extension of Ft(⋅,st)F_t(·;s_t). t(⋅∣x)D_t(· x) Partition sampling distribution induced by x. t−i(⋅∣x)D_t^-i(· x) Sampling distribution over all agents except i. g^t g_t Stochastic estimator of ∇f~t(xt,st)∇ f_t(x_t;s_t). ℋtH_t Pre-sampling history at time t. xt⋆x_t PME maximizer at time t. TopenV_T open Open-system KL tracking variation. RegT1/2Reg_T^1/2 Dynamic 1/21/2-approximation regret. I System Setup and Problem Formulation Figure 1: Open multi-agent task allocation with time-varying agent participation, dynamic tasks, and limited communication and sensing. We study decentralized task allocation in open MDPs [26, 10]. At each time step, the active agents locally observe the state of the environment and execute actions aiming to maximize a non-additive submodular global utility. Active agents and utilities may change over time, reflecting agent arrivals and departures, dynamic tasks, or an evolving environment [29], as shown in Figure 1. Our goal is to efficiently learn effective decentralized policies by leveraging the submodularity of team utilities. I-A Markov Decision Process in OMAS Let t∈[T]=1,…,Tt∈[T]=\1,…,T\ denote the time step and tN_t the set of active agents at time t. We model the task-allocation process as a finite-horizon partially observed open multi-agent Markov decision process ℳ=⟨,,,,F,μ1⟩M= ,A,O,P,F, _1 , where S is the global state space, A denotes the collection of feasible local action sets, =Ott∈[T]O=\O_t\_t∈[T] is the sequence of local observation maps, =Ptt∈[T]P=\P_t\_t∈[T] is the sequence of controlled transition kernels, F=Ftt∈[T]F=\F_t\_t∈[T] is the sequence of stage-utility set functions, and μ1 _1 is the initial-state distribution on S. For each agent i that may be active during the horizon, let iO_i denote its finite local observation space. Here, Ot=(Oi,t)i∈tO_t=(O_i,t)_i _t, where Oi,t:→iO_i,t:S _i and oi,t=Oi,t(st)o_i,t=O_i,t(s_t). The initial state is sampled as s1∼μ1s_1 _1 [27, 10, 8]. Each active agent i∈ti _t receives a local observation oi,to_i,t and selects an action ai,ta_i,t from a finite nonempty feasible action set iA_i. The global state st∈s_t characterizes the environment, including the tasks to be completed. Given the joint action t=(ai,t)i∈ta_t=(a_i,t)_i _t, the transition kernel PtP_t governs the state evolution as st+1∼Pt(⋅∣st,t)s_t+1 P_t(· s_t,a_t). The ground set of agent-action pairs available at time t is Ωt=(i,a):i∈t,a∈i _t= \(i,a):i _t,\ a _i \. For each active agent, define the local actions Ωi,t=(i,a):a∈i,i∈t _i,t= \(i,a):a _i \,\ i _t. The feasible subsets of agent-action pairs are described by the partition matroid (Ωt,ℐt)( _t,I_t) with ℐt=A⊆Ωt:|A∩Ωi,t|≤1,∀i∈tI_t= \A _t:|A∩ _i,t|≤ 1,\ ∀ i _t \. The executed joint action induced by the local choices is At=(i,ai,t):i∈t∈ℐtA_t=\(i,a_i,t):i _t\ _t [5]. To describe changes in the open-system domain, let 0=∅N_0= and define ℛt=t∩t−1,tin=t∖t−1,tout=t−1∖tR_t=N_t _t-1,N_t in=N_t _t-1,N_t out=N_t-1 _t. Here ℛtR_t, tinN_t in, and toutN_t out denote the remaining, arriving, and departing agents at time t, respectively. Moreover, we assume the agent arrivals and departures are independent of the agents’ local policies and the state transitions [10]. I-B Decentralized Categorical Policies Each active agent i∈ti _t processes a local observation oi,t=Oi,t(st)o_i,t=O_i,t(s_t), where Oi,t:→iO_i,t:S _i is a deterministic observation map modeling local sensing and communication with neighbors, and selects an action ai,t∈ia_i,t _i. A policy πiπ^i assigns a categorical distribution over iA_i given o∈io _i such that, at time t, active agent i∈ti _t computes its action as a realization ai,t∼πi(⋅∣oi,t)a_i,t π^i(· o_i,t). Let t=(oi,t)i∈to_t=(o_i,t)_i _t denote the joint observation vector. We consider factorized categorical policies [24, 38] πt(t∣t)=∏i∈tπi(ai,t∣oi,t). _t(a_t _t)= _i _tπ^i(a_i,t o_i,t). (1) The factorized policy πt _t is time dependent as a consequence of time-varying active agent sets tN_t. The factorization in (1) governs decentralized execution during deployment; since the distributions πi(⋅∣oi,t)i∈t\π^i(· o_i,t)\_i _t are conditioned on local observations oi,to_i,t, the agents sample their actions independently. I-C Submodular Team Utility and Problem Statement At each time step t, the team performance is measured by a set function Ft(⋅,st):2Ωt→ℝ≥0F_t(·\,;s_t):2 _t _≥ 0 defined over subsets of the current agent-action ground set Ωt _t. Definition 1 (Normalized monotone submodular set function [18]). Let Ω be a finite ground set. For any A⊆ΩA and e∈Ω∖Ae∈ A, define the marginal gain of adding e to A as F(e∣A)=F(A∪e)−F(A)F(e A)=F(A∪\e\)-F(A). A set function F:2Ω→ℝ≥0F:2 _≥ 0 is normalized, monotone, and submodular if it respectively satisfies the following properties: 1. F(∅)=0F( )=0. 2. for any sets A⊆A′⊆ΩA A , F(A)≤F(A′)F(A)≤ F(A ). 3. for any sets A⊆A′⊆ΩA A and element e∈Ω∖A′e∈ A , F(e∣A)≥F(e∣A′)F(e A)≥ F(e A ). Assumption 1 (Utility and Feasibility Conditions). For every time step t∈[T]t∈[T], the following holds. (i) For every state sts_t, the team utility Ft(⋅,st):2Ωt→ℝ≥0F_t(·\,;s_t):2 _t _≥ 0 is normalized, monotone, and submodular. (i) Each active agent has a nonempty local feasible action set, i.e., i≠∅A_i≠ for all i∈ti _t. 1 means that adding an agent-action pair can increase the team utility but its marginal gain decreases when more agent-action pairs have already been selected. This diminishing-returns structure captures redundancy among agent contributions [36]. Problem 1 (Open-System Submodular Policy Learning). Given the open multi-agent MDP, find a decentralized categorical policy π=πtt=1Tπ=\ _t\_t=1^T, with πt=∏i∈tπi _t= _i _tπ^i, that maximizes the expected cumulative submodular utility maxπ=πtt=1T _π=\ _t\_t=1^T J(π)=τ∼pπ[∑t=1TFt(At,st)] J(π)=E_τ p^π [ _t=1^TF_t(A_t;s_t) ] (2) s.t. .t. ai,t∼πi(⋅∣oi,t),∀i∈t,∀t∈[T], a_i,t π^i(· o_i,t),\ ∀ i _t,\ ∀ t∈[T], At∈ℐt,∀t∈[T]. A_t _t,\ ∀ t∈[T]. Here, τ=(s1,1,s2,…,sT,T,sT+1)τ=(s_1,a_1,s_2,…,s_T,a_T,s_T+1) and pπp^π denotes the trajectory distribution induced by π and the transition kernels Ptt=1T\P_t\_t=1^T. Even for a single time step, 1 reduces to monotone submodular maximization under a partition matroid constraint, which is NP-hard in general [23, 5]. Over a finite horizon, this combinatorial difficulty is exacerbated by action-dependent state evolution and time-varying agent participation. Since directly optimizing the cumulative utility (i.e., the return) is intractable [26], we adopt a stagewise approach and leverage the submodularity of stage utilities to learn the decentralized policies. The next section develops a continuous relaxation of stage utilities that formally supports our stagewise policy learning framework. I Partition Multilinear Extension A standard approach to combinatorial submodular maximization is to replace the discrete set problem with a continuous relaxation that is amenable to continuous optimization methods, particularly under matroid constraints [32, 5]. The standard multilinear extension is based on independent Bernoulli sampling over ground-set elements [7]. Under the partition constraint induced by ℐtI_t, this sampling rule may select multiple elements from the same agent action subset Ωi,t _i,t, creating a formal mismatch with the policy in (1) which selects one feasible action per agent. This motivates the continuous relaxation defined in the following to support training of factorized categorical policies in a principled fashion. Building on our preliminary work [21], we use the partition multilinear extension (PME), a continuous relaxation of utilities FtF_t whose sampling distribution matches the factorized categorical execution under the partition matroid. At each time step t, policy (1) at observations oi,ti∈t\o_i,t\_i _t induces a marginal vector xtπ(st)∈[0,1]|Ωt|x_t^π(s_t)∈[0,1]^| _t| over agent-action pairs, with coordinates x(i,a),tπ(st)=πi(a∣oi,t),(i,a)∈Ωt.x_(i,a),t^π(s_t)=π^i(a o_i,t),\ (i,a)∈ _t. (3) For readability, we denote a generic marginal vector by x. Each coordinate x(i,a),tπ(st)x_(i,a),t^π(s_t) is the probability that agent i∈ti _t executes action a at the current state sts_t under policy πiπ^i. I-A Definition and Policy Equivalence The partition matroid polytope associated with (Ωt,ℐt)( _t,I_t) is [5] (ℐt)=x∈[0,1]|Ωt|:∑a∈ix(i,a)≤1,∀i∈t.P(I_t)= \x∈[0,1]^| _t|: _a _ix_(i,a)≤ 1,\ ∀ i _t \. (4) For x∈(ℐt)x (I_t), let t(⋅∣x)D_t(· x) denote the partition sampling distribution over ℐtI_t. Under this distribution, each agent i∈ti _t selects element (i,a)(i,a) with probability x(i,a)x_(i,a), and selects no element with probability 1−∑a∈ix(i,a)1- _a _ix_(i,a). The choices are independent across agents. Definition 2 (Partition Multilinear Extension [21]). Given the current state sts_t and open-system domain, the partition multilinear extension of Ft(⋅,st)F_t(·;s_t) is the function f~t(⋅,st):(ℐt)→ℝ≥0 f_t(·;s_t):P(I_t) _≥ 0 defined by f~t(x,st) f_t(x;s_t) =A∼t(⋅∣x)[Ft(A;st)] =E_A _t(· x) [F_t(A;s_t) ] (5) =∑A∈ℐtFt(A,st)∏i∈tpi(A,x), = _A _tF_t(A;s_t) _i _tp_i(A;x), (6) where pi(A,x)=x(i,a),if A∩Ωi,t=(i,a),1−∑a′∈ix(i,a′),if A∩Ωi,t=∅.p_i(A;x)= casesx_(i,a),&if A∩ _i,t=\(i,a)\,\\[3.0pt] 1- _a _ix_(i,a ),&if A∩ _i,t= . cases (7) The categorical-policy face of (ℐt)P(I_t) is ℱt=x∈(ℐt):∑a∈ix(i,a)=1,∀i∈t.F_t= \x (I_t): _a _ix_(i,a)=1,\ ∀ i _t \. (8) For each i∈ti _t, define the local categorical simplex ℱi=xi∈[0,1]|i|:∑a∈ix(i,a)=1F_i= \x_i∈[0,1]^|A_i|: _a _ix_(i,a)=1 \. Then ℱt=∏i∈tℱiF_t= _i _tF_i. For any x∈ℱtx _t, the probability of selecting no action is zero in (7). Hence, the distribution induced by the PME respects the partition structure of Ωt _t since it selects exactly one agent-action pair from each Ωi,t _i,t w.p.1, matching the categorical action-selection model in (1). Remark 1. At a fixed time step, the PME is closely related to the policy-based continuous extension in [41] and the Multinoulli Extension in [40]. The former considers online coordination over fixed agent and action sets, whereas the latter addresses static subset selection under fixed partition constraints. Since these formulations do not model controlled Markovian dynamics or changes in the active-agent set, they cannot capture the coupling among current decisions, future states, and utilities. Our formulation extends the PME to finite-horizon decentralized policy learning for an OMAS and establishes exact equivalence with both the expected stage utility and the finite-horizon policy objective. Lemma 1 (Policy-PME Objective Equivalence [21]). Let πt=∏i∈tπi _t= _i _tπ^i be a factorized categorical policy, and let xtπ(st)x_t^π(s_t) be defined by (3). Then, for any fixed sts_t, At∼πt[Ft(At,st)∣st]=f~t(xtπ(st),st).E_A_t _t [F_t(A_t;s_t) s_t ]= f_t (x_t^π(s_t);s_t ). (9) Proof. Consider the current state sts_t and the current open-system domain. Then the local observations oi,ti∈t\o_i,t\_i _t are fixed, and each agent samples independently from πi(⋅∣oi,t)π^i(· o_i,t). Hence, the executed set is At=(i,ai,t):i∈t,ai,t∼πi(⋅∣oi,t)A_t=\(i,a_i,t):i _t\,\ a_i,t π^i(· o_i,t). By definition of xtπ(st)x_t^π(s_t), the per-agent factor in (7) satisfies pi(A,xtπ(st))=πi(a∣oi,t)if A∩Ωi,t=(i,a)p_i(A;x_t^π(s_t))=π^i(a o_i,t)\ if A∩ _i,t=\(i,a)\. Moreover, since πi(⋅∣oi,t)π^i(· o_i,t) is a categorical distribution, ∑a∈ix(i,a),tπ(st)=1 _a _ix^π_(i,a),t(s_t)=1, the probability of selecting no action in (7) is zero for every active agent. Therefore, under t(⋅∣xtπ(st))D_t(· x_t^π(s_t)), positive probability is assigned only to feasible sets that select exactly one action per active agent, and this probability equals the product of the corresponding local categorical probabilities. Thus, for any feasible A∈ℐtA _t, Pr(At=A∣st)=∏i∈tpi(A,xtπ(st)) (A_t=A s_t)= _i _tp_i(A;x_t^π(s_t)). Substituting this identity into the conditional expectation gives At∼πt[Ft(At,st)∣st] _A_t _t [F_t(A_t;s_t) s_t ] =∑A∈ℐtFt(A,st)Pr(At=A∣st) = _A _tF_t(A;s_t) (A_t=A s_t) =∑A∈ℐtFt(A,st)∏i∈tpi(A,xtπ(st)) = _A _tF_t(A;s_t) _i _tp_i(A;x_t^π(s_t)) =f~t(xtπ(st),st), = f_t (x_t^π(s_t);s_t ), which proves (9). ∎ Let t−i(⋅∣x)D_t^-i(· x) denote the joint distribution induced by x over the local action blocks of all agents except i, namely Ωj,tj∈t∖i\ _j,t\_j _t \i\. Lemma 2 (PME Coordinate Gradient [21]). For any (i,a)∈Ωt(i,a)∈ _t and x∈(ℐt)x (I_t), ∂f~t∂x(i,a)(x;st)=A−i∼t−i(⋅∣x)[Ft((i,a)∣A−i;st)], ∂ f_t∂ x_(i,a)(x;s_t)=E_A^-i _t^-i(· x) [F_t ((i,a) A^-i;s_t ) ], (10) where Ft((i,a)∣A−i;st)=Ft(A−i∪(i,a),st)−Ft(A−i,st)F_t ((i,a) A^-i;s_t )=F_t (A^-i∪\(i,a)\;s_t )-F_t(A^-i;s_t) denotes the marginal gain of adding the agent-action pair (i,a)(i,a) to A−iA^-i at state sts_t. Proof. Consider an arbitrary (i,a)∈Ωt(i,a)∈ _t. In the sum representation in (6), the coordinate x(i,a)x_(i,a) appears only in the local factor pi(A,x)p_i(A;x). There are three cases. If A∩Ωi,t=(i,a)A∩ _i,t=\(i,a)\, then ∂pi(A,x)/∂x(i,a)=1∂ p_i(A;x)/∂ x_(i,a)=1. If A∩Ωi,t=(i,a′)A∩ _i,t=\(i,a )\ for some a′≠a ≠ a, then ∂pi(A,x)/∂x(i,a)=0∂ p_i(A;x)/∂ x_(i,a)=0. If A∩Ωi,t=∅A∩ _i,t= , then ∂pi(A,x)/∂x(i,a)=−1∂ p_i(A;x)/∂ x_(i,a)=-1. Applying the product rule to (6) gives ∂f~t∂x(i,a)(x,st) ∂ f_t∂ x_(i,a)(x;s_t) =∑A:(i,a)∈AFt(A;st)∏k≠ipk(A;x) = _A:(i,a)∈ AF_t(A;s_t) _k≠ ip_k(A;x) −∑A:A∩Ωi,t=∅Ft(A;st)∏k≠ipk(A;x). - _A:A∩ _i,t= F_t(A;s_t) _k≠ ip_k(A;x). Every set in the first sum can be written uniquely as A−i∪(i,a)A^-i∪\(i,a)\, while every set in the second sum can be identified with the same partial joint action A−iA^-i of all agents except i. Moreover, ∏k≠ipk(A,x) _k≠ ip_k(A;x) is exactly the probability of A−iA^-i under t−i(⋅∣x)D_t^-i(· x). Hence ∂f~t∂x(i,a)(x,st) ∂ f_t∂ x_(i,a)(x;s_t) =∑A−iPrt−i(⋅∣x)(A−i)[Ft(A−i∪(i,a);st)−Ft(A−i;st)] = _A^-i _D_t^-i(· x)(A^-i) [F_t(A^-i∪\(i,a)\;s_t)-F_t(A^-i;s_t) ] =A−i∼t−i(⋅∣x)[Ft((i,a)∣A−i;st)]. =E_A^-i _t^-i(· x) [F_t ((i,a) A^-i;s_t ) ]. This proves (10). ∎ Lemma 2 shows that partial derivative of PME is the expected marginal gain of the corresponding agent-action pair under the current categorical sampling distribution of the other agents. This identity provides the first-order information used by the counterfactual marginal-gain estimator in Section IV. Proposition 1 (Properties of the PME [21]). Under 1, f~t(⋅,st) f_t(·;s_t) satisfies the following properties on (ℐt)P(I_t): 1. f~t(0,st)=0 f_t(0;s_t)=0. 2. f~t(x,st)≥0 f_t(x;s_t)≥ 0 for all x∈(ℐt)x (I_t). 3. f~t(⋅,st) f_t(·\,;s_t) is a multilinear polynomial and hence is smooth. 4. ∇f~t(x,st)≥0∇ f_t(x;s_t)≥ 0 componentwise for all x∈(ℐt)x (I_t). 5. For any x,y∈(ℐt)x,y (I_t) with x≤yx≤ y componentwise, ∇f~t(x,st)≥∇f~t(y,st)∇ f_t(x;s_t)≥∇ f_t(y;s_t) componentwise. Consequently, f~t(⋅,st) f_t(·\,;s_t) is monotone and DR-submodular on (ℐt)P(I_t). Proof. We prove the properties in order. 1) When x=0x=0, each agent selects no element with probability one under t(⋅∣0)D_t(· 0). Therefore, the only set with nonzero probability is ∅ , and f~t(0,st)=Ft(∅,st)=0 f_t(0;s_t)=F_t( ;s_t)=0. 2) By nonnegativity of FtF_t and by the fact that all factors pi(A,x)p_i(A;x) are valid probabilities for x∈(ℐt)x (I_t), every term in (6) is nonnegative. Thus, f~t(x,st)≥0 f_t(x;s_t)≥ 0. 3) For each fixed set A∈ℐtA _t, every factor pi(A,x)p_i(A;x) is affine in the coordinates x(i,a):a∈i\x_(i,a):a _i\. Since these coordinate sets are disjoint across agents, the product ∏i∈tpi(A,x) _i _tp_i(A;x) is multilinear in the variables associated with different agents. Hence f~t(⋅,st) f_t(·\,;s_t) is a finite sum of multilinear polynomials and is smooth. 4) By Lemma 2, for any (i,a)∈Ωt(i,a)∈ _t, ∂f~t∂x(i,a)(x;st)=A−i∼t−i(⋅∣x)[Ft((i,a)∣A−i;st)] ∂ f_t∂ x_(i,a)(x;s_t)=E_A^-i _t^-i(· x) [F_t ((i,a) A^-i;s_t ) ]. For every realization A−iA^-i in the support of t−i(⋅∣x)D_t^-i(· x), we have A−i⊆A−i∪(i,a)A^-i A^-i∪\(i,a)\. Since Ft(⋅,st)F_t(·\,;s_t) is monotone, Ft((i,a)∣A−i;st)=Ft(A−i∪(i,a),st)−Ft(A−i,st)≥0F_t ((i,a) A^-i;s_t )=F_t (A^-i∪\(i,a)\;s_t )-F_t(A^-i;s_t)≥ 0. Taking expectation preserves the inequality, and hence ∂f~t∂x(i,a)(x,st)≥0,(i,a)∈Ωt ∂ f_t∂ x_(i,a)(x;s_t)≥ 0,\ (i,a)∈ _t. Therefore, ∇f~t(x,st)≥0∇ f_t(x;s_t)≥ 0 componentwise. 5) We prove the DR property by showing that the gradient is componentwise nonincreasing. For each agent i, the PME is affine in the local coordinates x(i,a):a∈i\x_(i,a):a _i\, because the per-agent factor pi(A,x)p_i(A;x) in (7) is affine in these coordinates and no product contains two coordinates associated with the same agent. Hence, all second partial derivatives with respect to two coordinates of the same agent are zero: ∂2f~t∂x(i,a)∂x(i,b)(x,st)=0,a,b∈i. ∂^2 f_t∂ x_(i,a)∂ x_(i,b)(x;s_t)=0,\ a,b _i. (11) Consider two distinct agents i≠ui≠ u and actions a∈ia _i and b∈ub _u. Let t−i,u(⋅∣x)D_t^-\i,u\(· x) denote the product distribution induced by x over all agents in t∖i,uN_t \i,u\. By Lemma 2, ∂f~t∂x(i,a)(x;st)=A−i∼t−i(⋅∣x)[Ft((i,a)∣A−i;st)]. ∂ f_t∂ x_(i,a)(x;s_t)=E_A^-i _t^-i(· x) [F_t ((i,a) A^-i;s_t ) ]. (12) To differentiate this expression with respect to x(u,b)x_(u,b), separate the random choice of agent u from the choices of the other agents. For any fixed realization A−i,uA^-\i,u\ of the agents other than i and u, the contribution of agent u to (12) is (1−∑c∈ux(u,c))Ft((i,a)∣A−i,u;st) (1- _c _ux_(u,c) )F_t ((i,a) A^-\i,u\;s_t ) +∑c∈ux(u,c)Ft((i,a)∣A−i,u∪(u,c);st). + _c _ux_(u,c)F_t ((i,a) A^-\i,u\∪\(u,c)\;s_t ). (13) Differentiating (13) with respect to x(u,b)x_(u,b) gives ∂2f~t∂x(u,b)∂x(i,a)(x,st) ∂^2 f_t∂ x_(u,b)∂ x_(i,a)(x;s_t) (14) =A−i,u∼t−i,u(⋅∣x)[Ft((i,a)∣A−i,u∪(u,b);st) =E_A^-\i,u\ _t^-\i,u\(· x) [F_t ((i,a) A^-\i,u\∪\(u,b)\;s_t ) −Ft((i,a)∣A−i,u;st)]. -F_t ((i,a) A^-\i,u\;s_t ) ]. Since A−i,u⊆A−i,u∪(u,b)A^-\i,u\ A^-\i,u\∪\(u,b)\, submodularity of Ft(⋅,st)F_t(·\,;s_t) implies Ft((i,a)∣A−i,u∪(u,b);st)−Ft((i,a)∣A−i,u;st)≤0F_t ((i,a) A^-\i,u\∪\(u,b)\;s_t )-F_t ((i,a) A^-\i,u\;s_t )≤ 0. Taking expectation in (14) yields ∂2f~t∂x(u,b)∂x(i,a)(x,st)≤0,i≠u. ∂^2 f_t∂ x_(u,b)∂ x_(i,a)(x;s_t)≤ 0,\ i≠ u. (15) Equations (11) and (15) show that each coordinate derivative of f~t f_t is nonincreasing in every coordinate. Therefore, for any x,y∈(ℐt)x,y (I_t) with x≤yx≤ y componentwise, ∇f~t(x,st)≥∇f~t(y,st)∇ f_t(x;s_t)≥∇ f_t(y;s_t) componentwise. This establishes DR-submodularity on (ℐt)P(I_t). ∎ Proposition 1 shows that the PME is a smooth, monotone, DR-submodular objective on (ℐt)P(I_t) while preserving the per-agent categorical sampling structure required for decentralized execution [4, 16]. I-B Problem Equivalence In this section, we relate the PME to 1. First, we relate the continuous PME optimum to the discrete stagewise submodular optimum. Then, we extend the equivalence to the finite-horizon objective J(π)J(π). Although f~t(⋅,st) f_t(·;s_t) is defined over the partition-matroid polytope (ℐt)P(I_t), monotonicity implies that an optimal solution can be chosen on the categorical-policy face ℱtF_t. Lemma 3 (PME Exactness on the Categorical Face). Under 1, the following stagewise identity holds at each time step t and state sts_t: maxx∈(ℐt)f~t(x,st)=maxx∈ℱtf~t(x,st)=maxA∈ℐtFt(A,st). _x (I_t) f_t(x;s_t)= _x _t f_t(x;s_t)= _A _tF_t(A;s_t). (16) Proof. We first show that the optimum of ft(⋅,st)f_t(·;s_t) over (ℐt)P(I_t) is attained on ℱtF_t. Let x⋆∈argmaxx∈(ℐt)f~t(x,st)x ∈ _x (I_t) f_t(x;s_t). If x⋆∈ℱtx _t, the claim is immediate. Otherwise, there exists an agent i∈ti _t for which the corresponding partition constraint is nonactive: ρi=1−∑a∈ix(i,a)⋆>0 _i=1- _a _ix _(i,a)>0. Choose any action ai∈ia_i _i and define x′=x⋆+ρie(i,ai)x =x + _ie_(i,a_i), where e(i,ai)e_(i,a_i) is the canonical vector with nonzero coordinate (i,ai)(i,a_i). Then x′∈(ℐt)x (I_t) and the i-th partition constraint becomes tight. By monotonicity of f~t f_t from Proposition 1, f~t(x′,st)≥f~t(x⋆,st) f_t(x ;s_t)≥ f_t(x ;s_t). Repeating this operation for every agent i such that ∑a∈ix(i,a)⋆<1 _a _ix _(i,a)<1 yields a point x¯∈ℱt x _t with f~t(x¯,st)≥f~t(x⋆,st) f_t( x;s_t)≥ f_t(x ;s_t). Since x⋆x is optimal over (ℐt)P(I_t), equality holds. Thus, maxx∈(ℐt)f~t(x,st)=maxx∈ℱtf~t(x,st) _x (I_t) f_t(x;s_t)= _x _t f_t(x;s_t). It remains to relate the optimum over ℱtF_t to the discrete optimum over ℐtI_t. The set ℱtF_t is a product of local categorical simplices. Fix the local marginals of all agents except i. Then the PME is affine in the local vector xi∈ℱix_i _i. Therefore, optimizing f~t f_t over xix_i admits an optimal solution at an extreme point of ℱiF_i. Applying this argument successively to all active agents, there exists a maximizer of f~t f_t over ℱtF_t that is an extreme point of every local categorical simplex. Such a point assigns probability one to exactly one action for each active agent and therefore corresponds to a deterministic feasible set in ℐtI_t. Conversely, let A⋆∈argmaxA∈ℐtFt(A,st)A ∈ _A _tF_t(A;s_t). If A⋆A omits an active agent, monotonicity of FtF_t allows us to add any action from that agent’s local action set without decreasing the utility. Repeating this step gives a feasible set A¯⋆∈ℐt A _t that selects exactly one action per active agent and satisfies Ft(A¯⋆,st)≥Ft(A⋆,st)F_t( A ;s_t)≥ F_t(A ;s_t). The indicator vector A¯⋆1_ A lies in ℱtF_t, and by the PME definition at deterministic vertices, f~t(A¯⋆,st)=Ft(A¯⋆,st) f_t(1_ A ;s_t)=F_t( A ;s_t). Therefore the continuous optimum over ℱtF_t and the discrete optimum over ℐtI_t have the same value. ∎ Lemma 3 shows that, for monotone utilities, the PME admits an optimal solution on the categorical-policy face ℱtF_t. Therefore, restricting to factorized categorical policies does not reduce the optimal value. The stagewise equivalence in Lemma 1 yields an exact reformulation of the finite-horizon objective in 1. The following corollary shows that the original expected cumulative submodular utility is equal to the cumulative PME objective evaluated along the trajectory induced by the factorized categorical policy sequence. Corollary 1 (Problem Equivalence). Under the factorized categorical policy sequence π=πtt=1Tπ=\ _t\_t=1^T, the finite-horizon objective in 1 is exactly equal to the expected cumulative PME objective evaluated along the induced state trajectory: J(π)=τ∼pπ[∑t=1Tf~t(xtπ(st),st)],J(π)=E_τ p^π [ _t=1^T f_t (x_t^π(s_t);s_t ) ], (17) where pπp^π is the trajectory distribution induced by π and the transition kernels Ptt=1T\P_t\_t=1^T. Proof. By the definition of the finite-horizon objective, J(π)=τ∼pπ[∑t=1TFt(At,st)]J(π)=E_τ p^π [ _t=1^TF_t(A_t;s_t) ], where the trajectory distribution pπp^π is induced by the policy sequence π and the transition kernels Ptt=1T\P_t\_t=1^T. By linearity of expectation, J(π)=∑t=1Tτ∼pπ[Ft(At,st)]J(π)= _t=1^TE_τ p^π [F_t(A_t;s_t) ]. For each time step t, applying the tower property of conditional expectation with respect to the state sts_t gives τ∼pπ[Ft(At,st)]=τ∼pπ[At∼πt[Ft(At,st)∣st]]E_τ p^π [F_t(A_t;s_t) ]=E_τ p^π [E_A_t _t [F_t(A_t;s_t) s_t ] ]. Conditional on sts_t, the local observations oi,ti∈t\o_i,t\_i _t are fixed, and the action set AtA_t is sampled from the factorized categorical policy πt _t. Therefore, by Lemma 1, At∼πt[Ft(At,st)∣st]=f~t(xtπ(st),st)E_A_t _t [F_t(A_t;s_t) s_t ]= f_t (x_t^π(s_t);s_t ). Substituting this identity into the preceding display yields τ∼pπ[Ft(At,st)]=τ∼pπ[f~t(xtπ(st),st)]E_τ p^π [F_t(A_t;s_t) ]=E_τ p^π [ f_t (x_t^π(s_t);s_t ) ]. Summing over t=1,…,Tt=1,…,T gives J(π)=τ∼pπ[∑t=1Tf~t(xtπ(st),st)],J(π)=E_τ p^π [ _t=1^T f_t (x_t^π(s_t);s_t ) ], which proves (17). ∎ IV Submodular Multi-Agent Policy Learning This section describes our policy-learning method, Submodular Multi-Agent Policy Learning (SubMAPL). By Corollary 1, policy learning for 1 can be carried out through the PME objectives evaluated along the induced state trajectory. The main challenge is to construct tractable first-order feedback and update the local categorical policies without violating their simplex constraints. Mirror ascent is a standard first-order method for constrained optimization that replaces Euclidean projection with a Bregman-divergence regularization [3, 17]. For categorical distributions, the KL divergence is particularly suitable because the resulting mirror step admits a multiplicative update that preserves nonnegativity and normalization without Euclidean projection [28, 42]. Motivated by this geometry, and in contrast to the Euclidean projected-gradient and policy-gradient framework studied in our preliminary work [21], SubMAPL uses this PME representation to construct local marginal-gain feedback during training and updates local categorical policies through a KL-mirror step. SubMAPL follows the centralized training-decentralized execution (CTDE) paradigm [22, 12]. In the training phase, the stage utility Ft(⋅,st)F_t(·\,;s_t) is evaluated on feasible sets that differ only in one agent’s action to construct the stochastic local gradient estimator used in the KL-mirror update. In execution, each active agent applies its learned local policy using observations oi,to_i,t. IV-A Tabular Categorical Policies For each active agent i∈ti _t, SubMAPL uses a tabular softmax parameterization of the local categorical policy. Here, “tabular” means that a separate trainable logit is maintained for each local observation-action entry [31, 25, 1]. Let θi(o,a)∈ℝθ^i(o,a) denote the logit of agent i for observation o∈io _i and action a∈ia _i. Given the local observation oi,to_i,t, the policy is πi(a∣oi,t)=exp(θi(oi,t,a))∑b∈iexp(θi(oi,t,b)),a∈i.π^i(a o_i,t)= (θ^i(o_i,t,a) ) _b _i (θ^i(o_i,t,b) ),\ a _i. (18) The logits θi(o,a)o∈i,a∈i\θ^i(o,a)\_o _i,\,a _i parameterize the tabular policy πiπ^i. Equation (18) evaluates this policy at the current observation oi,to_i,t. The induced marginal vector satisfies x(i,a),tπ(st)=πi(a∣oi,t),(i,a)∈Ωtx_(i,a),t^π(s_t)=π^i (a o_i,t ),\ (i,a)∈ _t. In open systems, the active-agent set tN_t may vary over time. The logits of remaining agents are inherited across consecutive open-system domains. Each arriving agent is initialized using finite logits. Departing agents are excluded from the active policy domain. Hence, every feasible action of each active agent has strictly positive probability under the local softmax policy. IV-B Marginal-Gain Feedback and KL-Mirror Update At time t, condition on the current state sts_t. For each active agent i∈ti _t and a∈ia _i, define the local PME gradient coordinate by gi,a,t(πt,st)=∂f~t∂x(i,a)(xtπ(st),st),(i,a)∈Ωt.g_i,a,t( _t;s_t)= ∂ f_t∂ x_(i,a)(x_t^π(s_t);s_t),\ (i,a)∈ _t. (19) By Lemma 2, this coordinate admits the marginal-gain representation gi,a,t(πt,st)=[Ft((i,a)∣A−i;st)]g_i,a,t( _t;s_t)=E [F_t((i,a) A^-i;s_t) ], where the actions in A−iA^-i are sampled independently according to πj(⋅∣oj,t)π^j(· o_j,t) for j∈t∖ij _t \i\. After the joint action At=(i,ai,t):i∈tA_t=\(i,a_i,t):i _t\ is sampled, let At−i=At∖(i,ai,t)A_t^-i=A_t \(i,a_i,t)\. SubMAPL constructs the local marginal-gain estimator g^i,a,t=Ft((i,a)∣At−i;st),a∈i. g_i,a,t=F_t((i,a) A_t^-i;s_t),\ a _i. (20) The vector g^i,⋅,t g_i,·,t evaluates every feasible action of agent i under the same sampled actions of the other agents. Conditional on πt _t and sts_t, the actions in At−iA_t^-i are sampled independently according to πj(⋅∣oj,t)π^j(· o_j,t) for j∈t∖ij _t \i\. Therefore, [g^i,a,t∣πt,st]=gi,a,t(πt;st)=∂f~t∂x(i,a)(xtπ(st);st).E [ g_i,a,t _t,s_t ]=g_i,a,t( _t;s_t)= ∂ f_t∂ x_(i,a)(x_t^π(s_t);s_t). (21) Thus, g^i,⋅,t g_i,·,t is an unbiased stochastic estimator of the local PME gradient evaluated at the current policy. The estimator in (20) provides first-order information with respect to the local action probabilities. A direct additive probability update would require projection onto the probability simplex [3, 17]. SubMAPL instead applies KL-regularized mirror ascent, which preserves the simplex constraint without Euclidean projection and can be implemented through tabular softmax logits. Let πi,+π^i,+ denote the tabular policy of agent i after the KL-mirror update at time t and before open-system migration. Given the current local policy πi(⋅∣oi,t)π^i(· o_i,t) and the stochastic local gradient estimator g^i,⋅,t g_i,·,t, the local policy distribution at the current observation is updated as [3] πi,+(⋅∣oi,t)∈argmaxp∈ℱiη⟨g^i,⋅,t,p⟩−DKL(p∥πi(⋅∣oi,t)),π^i,+(· o_i,t)∈ _p _i \η g_i,·,t,p -D_ KL (p\|π^i(· o_i,t) ) \, (22) where η>0η>0 is the step size. For two local categorical distributions p,q∈ℱip,q _i, define DKL(p∥q)=∑a∈ipalogpaqa,D_ KL(p\|q)= _a _ip_a p_aq_a, (23) with the convention 0log(0/qa)=00 (0/q_a)=0. For two tabular policies π and π′π defined on the current open-system domain, define DKL,t(π∥π′)=∑i∈t∑o∈iDKL(πi(⋅∣o)∥π′i(⋅∣o)).D_ KL,t(π\|π )= _i _t _o _iD_ KL (π^i(· o)\|π i(· o) ). (24) The first-order optimality condition yields πi,+(a∣oi,t)=πi(a∣oi,t)exp(ηg^i,a,t)∑b∈iπi(b∣oi,t)exp(ηg^i,b,t),a∈i.π^i,+(a o_i,t)= π^i(a o_i,t) (η g_i,a,t) _b _iπ^i(b o_i,t) (η g_i,b,t),\ a _i. (25) For all other observations, the local policy distributions remain unchanged: πi,+(⋅∣o)=πi(⋅∣o),o∈i∖oi,t.π^i,+(· o)=π^i(· o),\ o _i \o_i,t\. (26) Hence, πi,+(⋅∣oi,t)∈ℱiπ^i,+(· o_i,t) _i. Since the KL-mirror step changes only the row associated with oi,to_i,t, all other terms in the tabular-policy KL divergence remain unchanged. Under the tabular softmax parameterization (18), (25) is implemented by the additive logit update θi,+(oi,t,a)=θi(oi,t,a)+ηg^i,a,t,a∈i,θ^i,+(o_i,t,a)=θ^i(o_i,t,a)+η g_i,a,t,\ a _i, (27) where all other logit entries remain unchanged: θi,+(o,a)=θi(o,a),o∈i∖oi,t,a∈i.θ^i,+(o,a)=θ^i(o,a),\ o _i \o_i,t\,\ a _i. (28) Substituting (27) into the softmax parameterization yields πi,+(a∣oi,t) π^i,+(a o_i,t) =exp(θi(oi,t,a)+ηg^i,a,t)∑b∈iexp(θi(oi,t,b)+ηg^i,b,t) = (θ^i(o_i,t,a)+η g_i,a,t ) _b _i (θ^i(o_i,t,b)+η g_i,b,t ) (29) =exp(θi(oi,t,a))exp(ηg^i,a,t)∑b∈i(exp(θi(oi,t,b))exp(ηg^i,b,t)) = (θ^i(o_i,t,a) ) (η g_i,a,t) _b _i ( (θ^i(o_i,t,b) ) (η g_i,b,t) ) =(i)πi(a∣oi,t)exp(ηg^i,a,t)∑b∈iπi(b∣oi,t)exp(ηg^i,b,t),a∈i, (i)= π^i(a o_i,t) (η g_i,a,t) _b _iπ^i(b o_i,t) (η g_i,b,t),\ a _i, where (i)(i) follows by dividing the numerator and denominator by ∑b∈iexp(θi(oi,t,b)) _b _i (θ^i(o_i,t,b)). Thus, the additive logit update exactly implements the KL-mirror update in (25). The post-update active joint policy before migration is defined by πt+(t∣t)=∏i∈tπi,+(ai∣oi,t). _t^+(a_t _t)= _i _tπ^i,+(a_i o_i,t). (30) Therefore, SubMAPL performs a local full-action KL-mirror step on the current local observation of each active agent’s tabular policy and implements this policy-space update through an additive logit update. IV-C Open Policy Migration The transition from time step t to t+1t+1 involves the remaining agents ℛt+1R_t+1, the arriving agents t+1inN_t+1 in, and the departing agents t+1outN_t+1 out. After the KL-mirror update at time t, let πt+ _t^+ denote the post-update active joint policy on the current agent domain tN_t. Open policy migration retains the updated local policies of the remaining agents, assigns policies to the arriving agents, and excludes the departing agents from the next active policy domain. Definition 3 (Open Policy Migration). Given the post-update active joint policy πt+ _t^+, the open policy migration map ℳtM_t constructs πt+1=ℳt(πt+) _t+1=M_t( _t^+) according to (πt+1)i(⋅∣o)=πi,+(⋅∣o),i∈ℛt+1,πi,0(⋅∣o),i∈t+1in,( _t+1)^i(· o)= casesπ^i,+(· o),&i _t+1,\\[5.69054pt] π^i,0(· o),&i _t+1 in, cases (31) where πi,0π^i,0 is the categorical policy assigned to an arriving agent i. It is represented by finite logits θi,0∈ℝ|i|×|i|θ^i,0 ^|O_i|×|A_i|, so that πi,0(a∣o)>0,o∈i,a∈iπ^i,0(a o)>0,o _i,a _i. Agents in t+1outN_t+1 out do not appear in the next active joint-policy domain. Algorithm 1 Submodular Multi-Agent Policy Learning (SubMAPL) 1: Input: horizon T, step size η, initial active parameter collection Θ1=θi,0:i∈1 _1=\θ^i,0:i _1\, finite-logit migration rule for arriving agents, and stage-utility evaluators Ftt=1T\F_t\_t=1^T 2: for t=1,…,Tt=1,…,T do 3: for each active agent i∈ti _t do 4: Receive the local observation oi,to_i,t 5: Form πi(⋅∣oi,t)π^i(· o_i,t) using (18) 6: Sample ai,t∼πi(⋅∣oi,t)a_i,t π^i(· o_i,t) 7: end for 8: Form At=(i,ai,t):i∈tA_t=\(i,a_i,t):i _t\ 9: for each active agent i∈ti _t do 10: Set At−i=At∖(i,ai,t)A_t^-i=A_t \(i,a_i,t)\ 11: for each feasible action a∈ia _i do 12: Evaluate g^i,a,t g_i,a,t using (20) at the pre-transition state sts_t 13: Update θi(oi,t,a)←θi(oi,t,a)+ηg^i,a,tθ^i(o_i,t,a)←θ^i(o_i,t,a)+η g_i,a,t 14: end for 15: end for 16: Execute AtA_t 17: Sample the next state st+1∼Pt(⋅∣st,t)s_t+1 P_t(· s_t,a_t) 18: if t<Tt<T then 19: Observe the next active-agent set t+1N_t+1 20: Apply the open policy migration in Definition 3 21: end if 22: end for 23: Output: the online policy sequence πtt=1T\ _t\_t=1^T and the final post-update policy πT+ _T^+ The complete training procedure is summarized in Algorithm 1. At each time step, SubMAPL evaluates the marginal gain of every feasible action of each active agent while keeping the sampled actions of the other agents fixed. The learned policy remains decentralized at execution time, because each active agent samples from its own categorical policy using only its local observation. V Performance Analysis This section establishes performance guarantees for SubMAPL as a PME-based KL-mirror policy-learning method in OMAS. The analysis is conducted along the state sequence generated by Algorithm 1. At each time step, the current state and open-system domain define a conditional stagewise PME objective over the current categorical-policy face. We first collect the basic gradient and mirror-ascent inequalities used in the analysis, then derive a bound on the finite-horizon objective in 1 through regret analysis, and finally specialize the general bound to a tighter one when the finite-horizon objective J(π)J(π) is itself submodular. V-A Analysis of KL-Mirror and Stagewise Bound Assumption 2 (Bounded Marginal Gains [39]). There exists a constant B<∞B<∞ such that, for every t∈[T]t∈[T] and state sts_t, 0≤Ft(e∣A;st)≤B,∀A⊆Ωt,e∈Ωt∖A.0≤ F_t(e A;s_t)≤ B,\ ∀ A _t,\ e∈ _t A. (32) Let g^t=(g^i,a,t)(i,a)∈Ωt∈ℝ|Ωt| g_t=( g_i,a,t)_(i,a)∈ _t ^| _t| denote the stochastic marginal-gain vector used by SubMAPL, where g^i,a,t g_i,a,t is defined in (20). Let ℋtH_t denote the information available before action sampling at time t, including the past trajectory, the current state sts_t, the current open-system domain (t,ii∈t)(N_t,\A_i\_i _t), and the current tabular policy πt _t. Since xt=xtπ(st)x_t=x_t^π(s_t), conditional on ℋtH_t, the quantities πt _t, xtx_t, sts_t, and the current open-system domain are fixed. By (21), we have [g^i,a,t∣ℋt]=∂f~t∂x(i,a)(xt,st),(i,a)∈Ωt.E [ g_i,a,t _t ]= ∂ f_t∂ x_(i,a)(x_t;s_t),\ (i,a)∈ _t. (33) Equivalently, [g^t∣ℋt]=∇f~t(xt,st).E [ g_t _t ]=∇ f_t(x_t;s_t). (34) 2 also gives a uniform bound on the stochastic feedback. Indeed, for every (i,a)∈Ωt(i,a)∈ _t, we have (i,a)∉At−i(i,a)∉ A_t^-i. Hence 2 can be applied with e=(i,a)e=(i,a) and A=At−iA=A_t^-i, which yields 0≤g^i,a,t=Ft((i,a)∣At−i;st)≤B,(i,a)∈Ωt0≤ g_i,a,t=F_t((i,a) A_t^-i;s_t)≤ B,\ (i,a)∈ _t . Consequently, for each active agent i∈ti _t, maxa∈i|g^i,a,t|≤B _a _i| g_i,a,t|≤ B. For any vector g∈ℝ|Ωt|g ^| _t| indexed by the current agent-action ground set Ωt _t, define the per-agent mixed norm by ∥g∥∞,22=∑i∈t(maxa∈i|gi,a|)2. g _∞,2^2= _i _t ( _a _i|g_i,a| )^2. (35) The norm ∥⋅∥∞,2 · _∞,2 is always understood with respect to the current open-system domain (t,ii∈t)(N_t,\A_i\_i _t). Then ∥g^t∥∞,22=∑i∈t(maxa∈i|g^i,a,t|)2≤∑i∈tB2=|t|B2. g_t _∞,2^2= _i _t ( _a _i| g_i,a,t| )^2≤ _i _tB^2=|N_t|B^2. (36) Let Nmax=maxt∈[T]|t|N_ = _t∈[T]|N_t|. Then ∥g^t∥∞,22≤NmaxB2,t∈[T]. g_t _∞,2^2≤ N_ B^2,\ t∈[T]. (37) Lemma 4 (Auxiliary Inequalities). Consider a time step t, a state sts_t, and the open-system domain at time t. Let f~t(⋅,st) f_t(·\,;s_t) be the PME of a normalized, monotone, submodular utility Ft(⋅,st)F_t(·\,;s_t). Then the following inequalities hold. 1. Categorical-face first-order bound [4]: For any x,y∈ℱtx,y _t, 12f~t(y,st)−f~t(x,st)≤12⟨∇f~t(x,st),y−x⟩. 12 f_t(y;s_t)- f_t(x;s_t)≤ 12 ∇ f_t(x;s_t),y-x . (38) 2. KL mirror-ascent inequality [3]: Suppose x∈ℱtx _t satisfies x(i,a)>0x_(i,a)>0 for all i∈ti _t and a∈ia _i. Let x+∈ℱtx^+ _t be generated by x+∈argmaxz∈ℱtη⟨g,z⟩−DKL(z∥x),x^+∈ _z _t \η g,z -D_ KL(z\|x) \, (39) where η>0η>0 and DKL(z∥x)=∑i∈t∑a∈iz(i,a)logz(i,a)x(i,a).D_ KL(z\|x)= _i _t _a _iz_(i,a) z_(i,a)x_(i,a). Then, for any u∈ℱtu _t, ⟨g,u−x⟩≤DKL(u∥x)−DKL(u∥x+)η+η2∥g∥∞,22. g,u-x ≤ D_ KL(u\|x)-D_ KL(u\|x^+)η+ η2 g _∞,2^2. (40) Proof. (1) Let A∼t(⋅∣x)A _t(· x) and Y∼t(⋅∣y)Y _t(· y) be sampled independently. Since x,y∈ℱtx,y _t, both A and Y select exactly one agent-action pair for each active agent. Define A=ei:i∈tA=\e_i:i _t\ and Y=ui:i∈tY=\u_i:i _t\, where ei,ui∈Ωi,te_i,u_i∈ _i,t. Let A−i=A∖eiA^-i=A \e_i\. By monotonicity, Ft(Y,st)−Ft(A,st)≤Ft(A∪Y,st)−Ft(A,st)F_t(Y;s_t)-F_t(A;s_t)≤ F_t(A∪ Y;s_t)-F_t(A;s_t). Fix an arbitrary ordering i1,…,im\i_1,…,i_m\ of tN_t, where m=|t|m=|N_t|. By telescoping, Ft(A∪Y,st)−Ft(A,st)=∑ℓ=1mFt(uiℓ∣A∪ui1,…,uiℓ−1;st)F_t(A∪ Y;s_t)-F_t(A;s_t)= _ =1^mF_t (u_i_ A∪\u_i_1,…,u_i_ -1\;s_t ). Since A−iℓ⊆A∪ui1,…,uiℓ−1A^-i_ A∪\u_i_1,…,u_i_ -1\, submodularity implies Ft(uiℓ∣A∪ui1,…,uiℓ−1;st)≤Ft(uiℓ∣A−iℓ;st)F_t (u_i_ A∪\u_i_1,…,u_i_ -1\;s_t )≤ F_t(u_i_ A^-i_ ;s_t). Therefore, Ft(Y,st)−Ft(A,st)≤∑i∈tFt(ui∣A−i;st).F_t(Y;s_t)-F_t(A;s_t)≤ _i _tF_t(u_i A^-i;s_t). (41) Next, by normalization and telescoping along the same ordering, Ft(A,st)=∑ℓ=1mFt(eiℓ∣ei1,…,eiℓ−1;st)F_t(A;s_t)= _ =1^mF_t (e_i_ \e_i_1,…,e_i_ -1\;s_t ). Since ei1,…,eiℓ−1⊆A−iℓ\e_i_1,…,e_i_ -1\ A^-i_ , submodularity gives Ft(eiℓ∣ei1,…,eiℓ−1;st)≥Ft(eiℓ∣A−iℓ;st)F_t (e_i_ \e_i_1,…,e_i_ -1\;s_t )≥ F_t(e_i_ A^-i_ ;s_t). Hence, ∑i∈tFt(ei∣A−i;st)≤Ft(A,st). _i _tF_t(e_i A^-i;s_t)≤ F_t(A;s_t). (42) Combining (41) and (42) yields Ft(Y,st)−2Ft(A,st) F_t(Y;s_t)-2F_t(A;s_t) (43) ≤∑i∈t[Ft(ui∣A−i;st)−Ft(ei∣A−i;st)]. ≤ _i _t [F_t(u_i A^-i;s_t)-F_t(e_i A^-i;s_t) ]. Taking expectations in (43) over the independent samples A∼t(⋅∣x)A _t(· x) and Y∼t(⋅∣y)Y _t(· y) gives f~t(y,st)−2f~t(x,st) f_t(y;s_t)-2 f_t(x;s_t) ≤∑i∈t∑a∈iy(i,a)A−i∼t−i(⋅∣x)[Ft((i,a)∣A−i;st)] ≤ _i _t _a _iy_(i,a)E_A^-i _t^-i(· x) [F_t((i,a) A^-i;s_t) ] −∑i∈t∑a∈ix(i,a)A−i∼t−i(⋅∣x)[Ft((i,a)∣A−i;st)]. - _i _t _a _ix_(i,a)E_A^-i _t^-i(· x) [F_t((i,a) A^-i;s_t) ]. Here, under t(⋅∣x)D_t(· x), the selected action of agent i is independent of A−iA^-i and has marginal distribution (x(i,a))a∈i(x_(i,a))_a _i; similarly, under t(⋅∣y)D_t(· y), the selected action of agent i has marginal distribution (y(i,a))a∈i(y_(i,a))_a _i and is independent of A. By Lemma 2, the expected marginal gain is the corresponding PME coordinate derivative. Therefore, f~t(y,st)−2f~t(x,st)≤⟨∇f~t(x,st),y−x⟩. f_t(y;s_t)-2 f_t(x;s_t)≤ ∇ f_t(x;s_t),y-x . Dividing by 22 proves (38). (2) The optimality condition of (39) gives the three-point inequality η⟨g,u−x+⟩≤DKL(u∥x)−DKL(u∥x+)−DKL(x+∥x).η g,u-x^+ ≤ D_ KL(u\|x)-D_ KL(u\|x^+)-D_ KL(x^+\|x). (44) For each active agent i∈ti _t, Hölder’s inequality gives [3, 17] η η ∑a∈igi,a(x(i,a)+−x(i,a)) _a _ig_i,a (x^+_(i,a)-x_(i,a) ) (45) ≤η(maxa∈i|gi,a|)∑a∈i|x(i,a)+−x(i,a)|. ≤η ( _a _i|g_i,a| ) _a _i |x^+_(i,a)-x_(i,a) |. By Young’s inequality, η(maxa∈i|gi,a|)∑a∈i|x(i,a)+−x(i,a)| η ( _a _i|g_i,a| ) _a _i |x^+_(i,a)-x_(i,a) | ≤η22(maxa∈i|gi,a|)2+12(∑a∈i|x(i,a)+−x(i,a)|)2. ≤ η^22 ( _a _i|g_i,a| )^2+ 12 ( _a _i |x^+_(i,a)-x_(i,a) | )^2. Pinsker’s inequality, applied to the two categorical distributions over iA_i, gives 12(∑a∈i|x(i,a)+−x(i,a)|)2≤∑a∈ix(i,a)+logx(i,a)+x(i,a). 12 ( _a _i |x^+_(i,a)-x_(i,a) | )^2≤ _a _ix^+_(i,a) x^+_(i,a)x_(i,a). Thus, η∑a∈igi,a(x(i,a)+−x(i,a)) η _a _ig_i,a (x^+_(i,a)-x_(i,a) ) ≤η22(maxa∈i|gi,a|)2+∑a∈ix(i,a)+logx(i,a)+x(i,a). ≤ η^22 ( _a _i|g_i,a| )^2+ _a _ix^+_(i,a) x^+_(i,a)x_(i,a). Summing over i∈ti _t yields η⟨g,x+−x⟩≤DKL(x+∥x)+η22∥g∥∞,22.η g,x^+-x ≤ D_ KL(x^+\|x)+ η^22 g _∞,2^2. (46) Combining (44) and (46), we obtain η⟨g,u−x⟩ η g,u-x =η⟨g,u−x+⟩+η⟨g,x+−x⟩ =η g,u-x^+ +η g,x^+-x ≤DKL(u∥x)−DKL(u∥x+)+η22∥g∥∞,22. ≤ D_ KL(u\|x)-D_ KL(u\|x^+)+ η^22 g _∞,2^2. Dividing by η proves (40). ∎ V-B Suboptimality Gap in the General Case Dynamic approximation regret compares the cumulative utility attained by an algorithm with that of a sequence of stagewise optimal allocations [42, 41]. Existing formulations for multi-agent online submodular coordination consider a fixed agent-action domain. However, the consecutive comparator policies in OMAS may belong to different policy domains as agents arrive and depart. We introduce an open-system variant that measures comparator variation after mapping the previous comparator to the new domain through policy migration. Given the current state sts_t and open-system domain, define the stagewise discrete optimum Ft⋆(st)=maxA∈ℐtFt(A,st)F_t (s_t)= _A _tF_t(A;s_t). Let xt⋆∈argmaxx∈ℱtf~t(x,st)x_t ∈ _x _t f_t(x;s_t). By Lemma 3, f~t(xt⋆,st)=Ft⋆(st) f_t(x_t ;s_t)=F_t (s_t). The sequence xt⋆t=1T\x_t \_t=1^T may vary with the state and the active-agent domain. Define the tabular policy πt⋆ _t associated with xt⋆x_t by (πt⋆)i(a∣o)=x(i,a),t⋆,o=oi,t,πi(a∣o),o≠oi,t,i∈t,o∈i,a∈i.( _t )^i(a o)= casesx_(i,a),t ,&o=o_i,t,\\ π^i(a o),&o≠ o_i,t, cases\ i _t,\ o _i,\ a _i. (47) By (24), DKL,t(πt⋆∥πt)=DKL(xt⋆∥xt)D_ KL,t( _t \| _t)=D_ KL(x_t \|x_t). The transition from time step t to t+1t+1 consists of remaining agents ℛt+1R_t+1, arriving agents t+1inN_t+1 in, and departing agents t+1outN_t+1 out. SubMAPL first obtains the post-update tabular policy πt+ _t^+ through the KL-mirror update in (25)-(26). It then applies the open policy migration in Definition 3: πt+1=ℳt(πt+) _t+1=M_t( _t^+). Let π^=πtt=1T π=\ _t\_t=1^T denote the online policy sequence generated by SubMAPL, and let pπ^p π denote the trajectory distribution induced by π π and the transition kernels Ptt=1T\P_t\_t=1^T. Following KL-potential tracking analyses on a fixed domain [15, 28], we define the open-system KL tracking variation as Topen=τ∼pπ^[∑t=1T−1( _T open=E_τ p π [ _t=1^T-1 ( DKL,t+1(πt+1⋆∥πt+1) D_ KL,t+1( _t+1 \| _t+1) (48) −DKL,t(πt⋆∥πt+))+]. -D_ KL,t( _t \| _t^+) )_+ ]. This variation records the increase in the KL tracking potential between consecutive time steps while allowing both the stagewise benchmark and the open-system policy domain to change. In particular, it incorporates agent arrivals and departures through ℛt+1R_t+1, t+1inN_t+1 in, and t+1outN_t+1 out. When the active-agent set is fixed, ℳtM_t is the identity map, and TopenV_T open reduces to the corresponding KL tracking variation on a fixed tabular-policy domain. Definition 4 (Open-System Dynamic Approximation-Regret). The open-system dynamic 1/21/2-approximation regret is defined as RegT1/2=∑t=1Tτ∼pπ^[12Ft⋆(st)−f~t(xt,st)].Reg_T^1/2= _t=1^TE_τ p π [ 12F_t (s_t)- f_t(x_t;s_t) ]. (49) By Lemma 1, f~t(xt,st) f_t(x_t;s_t) is the conditional expected stage utility of the factorized categorical policy πt _t. Thus, RegT1/2Reg_T^1/2 measures its cumulative approximation gap relative to the time-varying stagewise optimal values. Lemma 5 (Open-System KL-Mirror Approximation-Regret Bound). Let πtt=1T\ _t\_t=1^T be the policy sequence generated by Algorithm 1. Under 1 and 2, for any constant step size η>0η>0, RegT1/2≤s1∼μ1[DKL,1(π1⋆∥π1)]+Topen2η+ηTNmaxB24.Reg_T^1/2≤ E_s_1 _1 [D_ KL,1 ( _1 \| _1 ) ]+V_T open2η+ η TN_ B^24. (50) Proof. For each time step t, the categorical-face first-order bound in Lemma 4 gives 12Ft⋆(st)−f~t(xt,st)≤12⟨∇f~t(xt,st),xt⋆−xt⟩. 12F_t (s_t)- f_t(x_t;s_t)≤ 12 ∇ f_t(x_t;s_t),x_t -x_t . (51) Since xtx_t and xt⋆x_t are measurable with respect to the pre-sampling history ℋtH_t, taking expectations and using (34) yields τ∼pπ^[12Ft⋆(st)−f~t(xt,st)] _τ p π [ 12F_t (s_t)- f_t(x_t;s_t) ] (52) ≤12τ∼pπ^[⟨g^t,xt⋆−xt⟩]. ≤ 12E_τ p π [ g_t,x_t -x_t ]. Since ℱt=∏i∈tℱiF_t= _i _tF_i, the local KL-mirror updates in (22) jointly realize the product-space update in Lemma 4. Apply the KL mirror-ascent inequality with x=xtx=x_t, u=xt⋆u=x_t , and g=g^tg= g_t, where the post-update vector xt+x_t^+ has coordinates x(i,a),t+=πi,+(a∣oi,t),(i,a)∈Ωt.x_(i,a),t^+=π^i,+(a o_i,t),\ (i,a)∈ _t. By (24) and (47), together with the fact that πt+ _t^+ and πt _t coincide at all noncurrent observations, DKL(xt⋆∥xt) D_ KL(x_t \|x_t) =DKL,t(πt⋆∥πt), =D_ KL,t ( _t \| _t ), (53) DKL(xt⋆∥xt+) D_ KL(x_t \|x_t^+) =DKL,t(πt⋆∥πt+). =D_ KL,t ( _t \| _t^+ ). Therefore, ⟨g^t,xt⋆−xt⟩≤DKL,t(πt⋆∥πt)−DKL,t(πt⋆∥πt+)η+η2∥g^t∥∞,22. g_t,x_t -x_t ≤ D_ KL,t ( _t \| _t )-D_ KL,t ( _t \| _t^+ )η+ η2 g_t _∞,2^2. (54) By the uniform gradient bound in (37), ∥g^t∥∞,22≤NmaxB2. g_t _∞,2^2≤ N_ B^2. (55) Combining (52), (54), and (55) gives τ∼pπ^[12Ft⋆(st)−f~t(xt,st)] _τ p π [ 12F_t (s_t)- f_t(x_t;s_t) ] ≤τ∼pπ^[DKL,t(πt⋆∥πt)−DKL,t(πt⋆∥πt+)]2η+ηNmaxB24. ≤ E_τ p π [D_ KL,t ( _t \| _t )-D_ KL,t ( _t \| _t^+ ) ]2η+ η N_ B^24. (56) For compactness, define Φt=DKL,t(πt⋆∥πt) _t=D_ KL,t ( _t \| _t ), and Γt=DKL,t(πt⋆∥πt+) _t=D_ KL,t ( _t \| _t^+ ). For t=1,…,T−1t=1,…,T-1, we have Φt−Γt _t- _t =Φt−Φt+1+Φt+1−Γt = _t- _t+1+ _t+1- _t (57) ≤Φt−Φt+1+[Φt+1−Γt]+. ≤ _t- _t+1+ [ _t+1- _t ]_+. By the definition of the two potentials, [Φt+1−Γt]+=[DKL,t+1(πt+1⋆∥πt+1)−DKL,t(πt⋆∥πt+)]+. [ _t+1- _t ]_+= [D_ KL,t+1 ( _t+1 \| _t+1 )-D_ KL,t ( _t \| _t^+ ) ]_+. (58) Summing (57) over t=1,…,T−1t=1,…,T-1 gives ∑t=1T−1(Φt−Γt)≤Φ1−ΦT+∑t=1T−1[Φt+1−Γt]+. _t=1^T-1( _t- _t)≤ _1- _T+ _t=1^T-1 [ _t+1- _t ]_+. (59) Adding the terminal term ΦT−ΓT _T- _T to both sides and using ΓT≥0 _T≥ 0 yields ∑t=1T(Φt−Γt)≤Φ1+∑t=1T−1[Φt+1−Γt]+. _t=1^T( _t- _t)≤ _1+ _t=1^T-1 [ _t+1- _t ]_+. (60) Taking expectations with respect to τ∼pπ^τ p π and using the definition of TopenV_T open in (48), we obtain ∑t=1Tτ∼pπ^[Φt−Γt]≤τ∼pπ^[Φ1]+Topen. _t=1^TE_τ p π [ _t- _t ] _τ p π [ _1 ]+V_T open. (61) Summing (56) over t=1,…,Tt=1,…,T and applying (61) gives ∑t=1Tτ∼pπ^[12Ft⋆(st)−f~t(xt,st)] _t=1^TE_τ p π [ 12F_t (s_t)- f_t(x_t;s_t) ] ≤s1∼μ1[DKL,1(π1⋆∥π1)]+Topen2η+ηTNmaxB24. ≤ E_s_1 _1 [D_ KL,1 ( _1 \| _1 ) ]+V_T open2η+ η TN_ B^24. (62) The left-hand side equals RegT1/2Reg_T^1/2 by Definition 4, which proves (50). ∎ Lemma 5 controls the cumulative approximation gap relative to the time-varying stagewise optimal values. However, 1 evaluates the cumulative policy value induced over the full trajectory. We next connect the stagewise approximation-regret guarantee in Lemma 5 to the finite-horizon objective of 1. By Corollary 1, J(π^)=τ∼pπ^[∑t=1Tf~t(xt,st)].J( π)=E_τ p π [ _t=1^T f_t(x_t;s_t) ]. (63) Let J⋆=maxπJ(π)J = _πJ(π) be the optimal finite-horizon value over the considered class of decentralized factorized policy sequences. For readability, denote the bound in (50) by T=s1∼μ1[DKL,1(π1⋆∥π1)]+Topen2η+ηTNmaxB24.C_T= E_s_1 _1 [D_ KL,1 ( _1 \| _1 ) ]+V_T open2η+ η TN_ B^24. (64) Moreover, define the finite-horizon benchmark mismatch ΔT=[J⋆−τ∼pπ^[∑t=1TFt⋆(st)]]+. _T= [J -E_τ p π [ _t=1^TF_t (s_t) ] ]_+. (65) Theorem 1 (Finite-Horizon Performance Bound). Let π^=πtt=1T π=\ _t\_t=1^T be the policy sequence generated by Algorithm 1. Under 1 and 2, we have 12J⋆−J(π^)≤T+12ΔT, 12J -J( π) _T+ 12 _T, (66) where TC_T and ΔT _T are defined in (64) and (65), respectively. Proof. By Definition 4 and Lemma 5, J(π^)≥12τ∼pπ^[∑t=1TFt⋆(st)]−T.J( π)≥ 12E_τ p π [ _t=1^TF_t (s_t) ]-C_T. (67) By the definition of ΔT _T in (65), τ∼pπ^[∑t=1TFt⋆(st)]≥J⋆−ΔT.E_τ p π [ _t=1^TF_t (s_t) ]≥ J - _T. (68) Substituting (68) into (67) and rearranging yields (66). ∎ The mismatch term ΔT _T captures the discrepancy between the optimal finite-horizon value and the cumulative stagewise optimal values along the trajectory induced by SubMAPL. Since the stagewise KL-mirror analysis does not control this term without additional temporal structure, Theorem 1 provides a finite-horizon decomposition rather than a uniform approximation guarantee. V-C Suboptimality Gap With Submodular Finite-Horizon Utility We next identify a structural setting in which the stagewise approximation-regret bound yields a finite-horizon approximation guarantee. In coverage and information-collection problems, the stage utility can often be represented as the marginal gain of a trajectory-level submodular function with respect to the accumulated history [26]. Under such a time-expanded representation, if the ground set and the feasible families are independent of the executed policy, submodularity connects the cumulative stagewise oracle values along the SubMAPL trajectory with the finite-horizon optimum J⋆J . Assumption 3 (Time-Expanded Submodular Utility [26]). There exist a policy-independent time-expanded ground set Ω¯1:T _1:T, policy-independent feasible families ℐ¯tt=1T\ I_t\_t=1^T, and a normalized, monotone, submodular function F¯:2Ω¯1:T→ℝ≥0 F:2 _1:T _≥ 0. For every feasible execution, each At∈ℐtA_t _t corresponds to a time-expanded action set A¯t∈ℐ¯t A_t∈ I_t, and the state sts_t contains the accumulated history A¯1:t−1=⋃τ=1t−1A¯τ A_1:t-1= _τ=1^t-1 A_τ. The stage utility satisfies Ft(At;st)=F¯(A¯t∣A¯1:t−1)=F¯(A¯1:t−1∪A¯t)−F¯(A¯1:t−1)F_t(A_t;s_t)= F( A_t A_1:t-1)= F( A_1:t-1∪ A_t)- F( A_1:t-1). Moreover, every A¯t′∈ℐ¯t A_t ∈ I_t corresponds to some feasible At′∈ℐtA_t _t. 3 is used to convert the stagewise approximation-regret bound into a finite-horizon guarantee. It holds for trajectory-level coverage and information-collection objectives whose cumulative utility is represented by a monotone submodular function of the selected time-expanded items [19, 14, 26]. Example 1 (Static Sensing Coverage Utility [30]). Consider a multi-agent coverage problem over a finite target set Q. At time step t, each agent-action pair (i,a)∈Ωt(i,a)∈ _t covers a sensing region Ct(i,a)⊆C_t(i,a) , that does not depend on the current state. Assume that Ωt _t and the sensing regions Ct(i,a)(i,a)∈Ωt\C_t(i,a)\_(i,a)∈ _t are determined independently of the executed policy. Define the time-expanded ground set Ω¯1:T=(i,a,t):t∈[T],(i,a)∈Ωt _1:T=\(i,a,t):t∈[T],\ (i,a)∈ _t\. For each feasible At∈ℐtA_t _t, let A¯t=(i,a,t):(i,a)∈At A_t=\(i,a,t):(i,a)∈ A_t\, and let ℐ¯t=A¯t:At∈ℐt I_t=\ A_t:A_t _t\. Define A¯1:t=⋃τ=1tA¯τ A_1:t= _τ=1^t A_τ and A¯1:0=∅ A_1:0= . Given target weights wq≥0w_q≥ 0, define F¯(S)=∑q∈wqq∈⋃(i,a,t)∈SCt(i,a),S⊆Ω¯1:T. F(S)= _q w_q1 \q∈ _(i,a,t)∈ SC_t(i,a) \,\ S _1:T. Then F¯ F is normalized, monotone, and submodular. If sts_t records the targets covered before time t, the stage utility satisfies Ft(At;st)=F¯(A¯t∣A¯1:t−1)F_t(A_t;s_t)= F( A_t A_1:t-1), and therefore ∑t=1TFt(At;st)=F¯(A¯1:T). _t=1^TF_t(A_t;s_t)= F( A_1:T). Thus, 3 holds. Theorem 2 (Finite-Horizon Approximation under Time-Expanded Submodularity). Let π π be the policy sequence generated by Algorithm 1. Suppose 1, 2, and 3 hold. Then J(π^)≥13J⋆−23T.J( π)≥ 13J - 23C_T. (69) Proof. Consider an arbitrary trajectory generated by π π. Let A¯tt=1T\ A_t\_t=1^T denote the corresponding time-expanded action sets, and let stt=1T\s_t\_t=1^T denote the state sequence. Let A¯t′t=1T\ A_t \_t=1^T be any fixed feasible reference sequence with A¯t′∈ℐ¯t A_t ∈ I_t for each t, and define A¯1:t′=⋃τ=1tA¯τ′ A_1:t = _τ=1^t A_τ with A¯1:0′=∅ A_1:0 = . By 3, for each A¯t′∈ℐ¯t A_t ∈ I_t, there exists At′∈ℐtA_t _t whose corresponding time-expanded action set is A¯t′ A_t . By monotonicity of F¯ F, F¯(A¯1:T′)≤F¯(A¯1:T)+F¯(A¯1:T′∣A¯1:T). F( A_1:T )≤ F( A_1:T)+ F( A_1:T A_1:T). (70) Using the chain rule for marginal gains, we have F¯(A¯1:T′∣A¯1:T) F( A_1:T A_1:T) =∑t=1TF¯(A¯t′∣A¯1:T∪A¯1:t−1′) = _t=1^T F ( A_t A_1:T∪ A_1:t-1 ) ≤∑t=1TF¯(A¯t′∣A¯1:t−1), ≤ _t=1^T F ( A_t A_1:t-1 ), (71) where the inequality follows from A¯1:t−1⊆A¯1:T∪A¯1:t−1′ A_1:t-1 A_1:T∪ A_1:t-1 and the diminishing-returns property of the submodular function F¯ F. By 3, the marginal gain of the reference time-expanded action set A¯t′ A_t along the SubMAPL history is exactly the corresponding stage utility: F¯(A¯t′∣A¯1:t−1)=Ft(At′;st)≤Ft⋆(st). F( A_t A_1:t-1)=F_t(A_t ;s_t)≤ F_t (s_t). (72) Combining (70)–(72) gives, for the trajectory under consideration, F¯(A¯1:T′)≤F¯(A¯1:T)+∑t=1TFt⋆(st). F( A_1:T )≤ F( A_1:T)+ _t=1^TF_t (s_t). (73) We next take expectation with respect to the trajectory distribution induced by SubMAPL. By 3, the cumulative utility along the SubMAPL trajectory telescopes: ∑t=1TFt(At,st) _t=1^TF_t(A_t;s_t) =∑t=1TF¯(A¯t∣A¯1:t−1) = _t=1^T F( A_t A_1:t-1) =∑t=1T[F¯(A¯1:t)−F¯(A¯1:t−1)] = _t=1^T [ F( A_1:t)- F( A_1:t-1) ] =F¯(A¯1:T), = F( A_1:T), where F¯(∅)=0 F( )=0 because F¯ F is normalized. Therefore, J(π^)=τ∼pπ^[F¯(A¯1:T)].J( π)=E_τ p π [ F( A_1:T) ]. Taking expectation in (73) over τ∼pπ^τ p π gives F¯(A¯1:T′)≤J(π^)+τ∼pπ^[∑t=1TFt⋆(st)]. F( A_1:T )≤ J( π)+E_τ p π [ _t=1^TF_t (s_t) ]. (74) Since (74) holds for every feasible reference sequence A¯t′t=1T\ A_t \_t=1^T with A¯t′∈ℐ¯t A_t ∈ I_t, it also holds after maximizing the left-hand side over all such reference sequences: maxA¯t′∈ℐ¯t,t∈[T]F¯(A¯1:T′)≤J(π^)+τ∼pπ^[∑t=1TFt⋆(st)]. _ A_t ∈ I_t,\ t∈[T] F( A_1:T )≤ J( π)+E_τ p π [ _t=1^TF_t (s_t) ]. (75) Since the time-expanded feasible families are policy-independent, every realization generated by an admissible policy π satisfies A¯t∈ℐ¯t A_t∈ I_t for all t∈[T]t∈[T]. Therefore, for any admissible policy π, J(π)=τ∼pπ[F¯(A¯1:T)]≤maxA¯t′∈ℐ¯t,t∈[T]F¯(A¯1:T′).J(π)=E_τ p^π [ F( A_1:T) ]≤ _ A_t ∈ I_t,\ t∈[T] F( A_1:T ). Taking the maximum over π gives J⋆≤maxA¯t′∈ℐ¯t,t∈[T]F¯(A¯1:T′).J ≤ _ A_t ∈ I_t,\ t∈[T] F( A_1:T ). Combining this inequality with (75) yields J⋆≤J(π^)+τ∼pπ^[∑t=1TFt⋆(st)].J ≤ J( π)+E_τ p π [ _t=1^TF_t (s_t) ]. (76) It remains to use the stagewise approximation-regret bound. From (67), we have τ∼pπ^[∑t=1TFt⋆(st)]≤2J(π^)+2T.E_τ p π [ _t=1^TF_t (s_t) ]≤ 2J( π)+2C_T. (77) Substituting (77) into (76) gives J⋆≤3J(π^)+2T.J ≤ 3J( π)+2C_T. Rearranging proves (69). ∎ Lemma 5 establishes an open-system dynamic 1/21/2-approximation-regret bound for SubMAPL relative to the time-varying stagewise PME maximizers. These results characterize the stagewise tracking performance of SubMAPL along its induced state trajectory. However, the objective in 1 is the optimal finite-horizon policy value, which need not coincide with the cumulative stagewise optimal values. Thus, we quantify this discrepancy through the mismatch term ΔT _T in (66). Under 3, the policy-independent time-expanded submodular representation connects the stagewise benchmark to the finite-horizon optimum, yielding the approximation guarantee in Theorem 2. VI Numerical Experiments Figure 2: Coverage ratio under the controlled 5→2→55→ 2→ 5 active-agent profile. From left to right: uniform, mixture of two Gaussians, and Gaussian process fields. Curves show the means, and shaded regions denote 95%95\% confidence intervals over shared evaluation scenarios. We evaluate SubMAPL on a multi-agent coverage task [26]. SubMAPL is trained with a fixed (time-invariant) agent set and evaluated on open systems with a time-varying agent set. VI-A Experimental Setup The workspace V is a 30×3030× 30 grid with Nmax=5N_ =5 agents. To model spatially heterogeneous information, we weigh grid cells according to a probability distribution. We consider a uniform field, a mixture of two isotropic Gaussian components, and a positive log-Gaussian process field generated using a separable radial basis function (RBF) kernel. Cell weights remain constant throughout each experiment. All methods are evaluated with the same cell weights and initial agent positions. The global state sts_t contains the active-agent set tN_t, the current agent positions, and the accumulated coverage set t−1hist=⋃k=1t−1k(Ak,sk)C_t-1 hist= _k=1^t-1C_k(A_k;s_k), which records all cells sensed before the action at time t. The complete coverage history is maintained by the environment for state transitions and utility evaluation but is not directly available to individual agents during decentralized execution. Each agent observes only a local encoding of the coverage status described below. Each agent receives a discrete local observation oi,to_i,t. It contains: 1) the index of the agent’s current 6×66× 6 region in a partition of the workspace into 2525 regions; 2) the relative positions of at most two nearest active neighbors within the communication radius rcom=2r_ com=2; 3) the states of the agent’s current cell and its four axially adjacent cells, where each cell is classified as already covered or outside the workspace, uncovered with low information density, or uncovered with high information density; and 4) the agent’s previous action. Thus, an agent observes only nearby coverage and neighbor information, rather than the complete coverage history or the positions of all agents. At each step t, active agent i∈ti _t selects a motion action ai,t∈i=idle,left,right,up,downa_i,t _i=\ idle, left, right, up, down\, which determines its next position. Let Di(ai,t,st)D_i(a_i,t;s_t) denote the sensing region of agent i after applying action ai,ta_i,t at state sts_t, which includes all cells within Chebyshev distance rcov=1r_ cov=1 from the agent’s new position. Hence, Di(ai,t,st)D_i(a_i,t;s_t) forms a 3×33× 3 neighborhood and determines the information collected by agent i. The cells sensed as a result of executing AtA_t at state sts_t are t(At,st)=⋃i∈tDi(ai,t,st).C_t(A_t;s_t)= _i _tD_i(a_i,t;s_t). (78) Let t−1hist=⋃k=1t−1k(Ak,sk)C_t-1 hist= _k=1^t-1C_k(A_k;s_k) denote all cells covered before the action at time t. We define the stage utility as the weighted information collected from uncovered cells: Ft(At,st)=∑v∈t(At,st)∖t−1histρ(v),F_t(A_t;s_t)= _v _t(A_t;s_t) _t-1 histρ(v), (79) where ρ(v)≥0ρ(v)≥ 0 is the weight of cell v∈v . Utility Ft(⋅,st)F_t(·;s_t) is a normalized, monotone, and submodular set function over the active agent-action ground set Ωt _t, satisfying 1 [18, 30]. We measure performance as the weighted coverage ratio CovRatiot=∑v∈thistρ(v)∑v∈ρ(v).CovRatio_t= _v _t histρ(v) _v ρ(v). (80) We compare our proposed algorithm SubMAPL (Algorithm 1) with four benchmarks. MA-SPL [41]: a policy-based continuous-extension method that employs a submodular surrogate gradient, a minimum-marginal-gain correction, neighbor consensus, and Euclidean projection. MA-OSEA [42]: a multilinear-extension method based on curvature-aware surrogate gradients, neighbor consensus, uniform mixing, and a projection-free KL update. REINFORCE [34]: a tabular return-based policy-gradient method trained using the global newly covered information as the stage reward. OSG [36]: a centralized online greedy method that sequentially selects one action for each agent according to their current marginal coverage gains following a fixed order. SubMAPL and REINFORCE are trained in a closed-system setting for 30003000 episodes with horizon T=100T=100 steps. Each evaluation trajectory has length T=2000T=2000. MA-SPL and MA-OSEA are initialized with uniform policies and perform their native online updates throughout the evaluation horizon. At each time step, OSG processes the active agents in a fixed order, and each active agent greedily maximizes FtF_t over the active agent set at each step t. A complete communication graph is used for MA-SPL and MA-OSEA. SubMAPL does not perform inter-agent communication or consensus during decentralized execution. Each agent instead locally observes the relative positions of at most the two nearest active agents within communication radius of rcom=2r_ com=2. For the methods trained in the closed-system setting, each agent retains its finite-logit policy table while inactive and restores it upon reactivation. We use five training seeds and five evaluation scenarios. For SubMAPL and REINFORCE, results are first averaged over training seeds within each evaluation scenario. The curves report averages across the five evaluation scenarios, and the shaded regions delimit 95%95\% confidence intervals. VI-B Results Table I: Normalized areas under the coverage curves in the open-system evaluation. Higher values indicate faster overall information acquisition. Method Uniform Mixture of two Gaussians Gaussian process Average SubMAPL 0.966 0.960 0.963 0.963 MA-SPL 0.939 0.914 0.918 0.924 MA-OSEA 0.843 0.775 0.831 0.816 REINFORCE 0.377 0.499 0.487 0.454 OSG 0.917 0.873 0.850 0.880 We first evaluate performance under mild changes in the active agent set tN_t, and then conduct a stress test with strongly time-varying agent participation. VI-B1 Main Comparison Figure 3: Performance under random agent participation on the Gaussian-process field. Top: coverage ratios of the five methods. Bottom: the active-agent profile shared by all methods, reported as the mean with 95%95\% confidence intervals over five shared evaluation scenarios. In the main comparison, all five agents are active for t=0,…,699t=0,…,699, three agents are temporarily unavailable for t=700,…,1299t=700,…,1299, and all five are active again from t=1300t=1300. Fig. 2 compares the five methods under the same open-system profile. SubMAPL achieves the fastest overall information acquisition in all three landscapes. Table I reports the normalized areas under the coverage curves for all five methods. SubMAPL achieves the largest area in every information-density landscape, with an average normalized area of 0.9630.963, compared with 0.9240.924 for the strongest competing method, MA-SPL. This advantage indicates that SubMAPL acquires information more rapidly throughout the evaluation horizon. The online optimization baselines exhibit different transient behavior. OSG initially acquires information rapidly by selecting actions from current marginal gains, but its sequential myopic decisions eventually plateau below complete coverage. MA-OSEA improves after the active population is restored at t=1300t=1300, especially in the nonuniform fields, but remains slower than MA-SPL and SubMAPL. REINFORCE is substantially slower and shows the clearest loss of progress during the interval with only two active agents. The results support the benefit of combining this categorical relaxation with full local-action marginal feedback and KL-mirror policy updates in the tested open-system coverage task. VI-B2 Open-system Robustness Table I: Performance under the random agent participation on the Gaussian-process information field. Method Normalized area Final coverage 95%95\% coverage successes Mean T0.95T_0.95 SubMAPL 0.887 0.999 5/5 580 MA-SPL 0.844 0.989 5/5 904 MA-OSEA 0.683 0.894 0/5 – REINFORCE 0.338 0.444 0/5 – OSG 0.665 0.714 0/5 – The normalized area is the area under the coverage-ratio curve normalized by the evaluation horizon. T0.95T_0.95 denotes the first time step at which the coverage ratio reaches 0.950.95 and is averaged only over successful scenarios. The mean normalized-area advantage of SubMAPL over MA-SPL is 0.0430.043, with a 95%95\% confidence interval of [0.009,0.078][0.009,0.078]. We next evaluate the transferability of the closed-system trained policies under stronger stochastic variation in agent participation. The experiment uses the Gaussian process field. One agent remains active throughout the evaluation horizon, whereas each of the other four agents is active over a randomly generated contiguous time interval. All methods are evaluated under the same active-agent schedule within each evaluation scenario. Fig. 3 shows that SubMAPL achieves the fastest cumulative information acquisition despite substantial changes in both the size and composition of the active-agent set. Table I shows that SubMAPL achieves the largest normalized area and the highest final coverage. Both SubMAPL and MA-SPL reach 0.950.95 coverage in all five scenarios, but SubMAPL reaches this level considerably earlier, with a mean hitting time of 580580 steps compared with 904904 steps for MA-SPL. SubMAPL reuses observation-conditioned local policy tables learned before deployment and restores the corresponding policy whenever an agent becomes active. Therefore, it avoids restarting the decision process after each change in participation. MA-SPL continues to adapt online, but its slower transient response reduces the information accumulated early in the finite horizon. These results indicate that the learned SubMAPL policies remain effective under substantial random changes in the size and composition of the active-agent set, without deployment-time policy updates. VII Conclusion This paper studied decentralized policy learning for open multi-agent task allocation with monotone submodular team utilities. We introduced the partition multilinear extension (PME) as a policy-based continuous representation of the expected stage utility induced by factorized categorical policies and developed SubMAPL, a KL-mirror policy-learning method using the stochastic local gradient as feedback over each agent’s feasible action set. We showed that this feedback provides unbiased PME coordinate-gradient information and that the KL-mirror update is exactly equivalent to an additive logit update under tabular softmax parameterization. We established open-system approximation-regret guarantees and finite-horizon performance bounds. Numerical experiments on information coverage showed that SubMAPL policies remain effective under random changes in agent participation and outperform online submodular-coordination and policy-gradient baselines. Future work will consider richer communication constraints, neural policy approximation, and long-horizon value-aware objectives. References [1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan (2021) On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research 22 (98), p. 1–76. Cited by: §IV-A. [2] G. Anil, P. Doshi, D. A. Redder, A. Eck, and L. Soh (2025) MOHITO: multi-agent reinforcement learning using hypergraphs for task-open systems. In The 41st Conference on Uncertainty in Artificial Intelligence, Cited by: item (3). [3] A. Beck and M. Teboulle (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters 31 (3), p. 167–175. Cited by: §IV-B, §IV-B, §IV, item 2, §V-A. [4] A. A. Bian, B. Mirzasoleiman, J. Buhmann, and A. Krause (2017) Guaranteed non-convex optimization: submodular maximization over continuous domains. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Vol. 54, p. 111–120. Cited by: §I-A, item 1. [5] G. Calinescu, C. Chekuri, M. Pal, and J. Vondrák (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40 (6), p. 1740–1766. Cited by: §I, §I, §I-A, §I-C, §I-A, §I. [6] J. Castellini, S. Devlin, F. A. Oliehoek, and R. Savani (2025) Difference rewards policy gradients. Neural Computing and Applications 37 (19), p. 13163–13186. Cited by: item (1). [7] C. Chekuri, J. Vondrák, and R. Zenklusen (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing 43 (6), p. 1831–1879. Cited by: §I. [8] W. Chen, C. Qian, S. Xing, Y. Zhou, and V. Crawford (2026) Multi-agent reinforcement learning with submodular reward. arXiv preprint arXiv:2603.06810. Cited by: §I, §I, §I-A. [9] R. De Santi, M. Prajapat, and A. Krause (2024) Global reinforcement learning: beyond linear and convex rewards via submodular semi-gradient methods. In Proceedings of the 41st International Conference on Machine Learning, Vol. 235, p. 10235–10266. Cited by: §I, §I. [10] D. Deplano, N. Bastianello, M. Franceschelli, and K. H. Johansson (2026) Optimization and learning in open multi-agent systems. IEEE Transactions on Automatic Control 71 (6), p. 3864–3879. Cited by: item (3), §I, §I-A, §I-A, §I. [11] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey (2009) An analysis of approximations for maximizing submodular set functions—I. In Polyhedral Combinatorics: Dedicated to the memory of DR Fulkerson, p. 73–87. Cited by: §I, §I. [12] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson (2018) Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 32, p. 2974–2982. Cited by: item (1), §IV. [13] S. Fujishige (2005) Submodular functions and optimization. Vol. 58, Elsevier. Cited by: §I. [14] D. Golovin and A. Krause (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research 42, p. 427–486. Cited by: §V-C. [15] E. Hall and R. Willett (2013) Dynamical models and tracking regret in online convex programming. In International Conference on Machine Learning, p. 579–587. Cited by: §V-B. [16] H. Hassani, M. Soltanolkotabi, and A. Karbasi (2017) Gradient methods for submodular maximization. Advances in Neural Information Processing Systems 30. Cited by: §I-A. [17] E. Hazan (2016) Introduction to online convex optimization. Foundations and Trends in Optimization 2 (3-4), p. 157–325. Cited by: §IV-B, §IV, §V-A. [18] A. Krause and D. Golovin (2014) Submodular function maximization. In Tractability: Practical Approaches to Hard Problems, Cited by: §VI-A, Definition 1. [19] A. Krause, A. Singh, and C. Guestrin (2008) Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. In Journal of Machine Learning Research, Vol. 9, p. 235–284. Cited by: §V-C. [20] J. Liu, F. Li, X. Jin, and Y. Tang (2026) Distributed task allocation for multi-agent systems: a submodular optimization approach. IEEE Transactions on Automatic Control. Cited by: §I. [21] J. Liu, Y. Yang, L. Ballotta, F. Li, Y. Tang, and R. Carli (2026) Submodular multi-agent policy learning for online distributed task allocation in open multi-agent systems. arXiv preprint arXiv:2605.13269. Cited by: item (1), item (2), item (3), §I, §I, §IV, Definition 2, Lemma 1, Lemma 2, Proposition 1. [22] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch (2017) Multi-agent actor-critic for mixed cooperative-competitive environments. Advances in Neural Information Processing Systems 30. Cited by: §I, §I, §IV. [23] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher (1978) An analysis of approximations for maximizing submodular set functions—I. Mathematical programming 14, p. 265–294. Cited by: §I, §I, §I-C. [24] F. A. Oliehoek C. Amato et al. (2016) A concise introduction to decentralized pomdps. Springer. Cited by: §I-B. [25] J. Peters and S. Schaal (2008) Natural actor-critic. Neurocomputing 71 (7-9), p. 1180–1190. Cited by: §IV-A. [26] M. Prajapat, M. Mutnỳ, M. N. Zeilinger, and A. Krause (2024) Submodular reinforcement learning. In International Conference on Learning Representations, Cited by: §I, §I, §I-C, §I, §V-C, §V-C, §VI, Assumption 3. [27] M. L. Puterman (2014) Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Cited by: §I-A. [28] S. Shahrampour and A. Jadbabaie (2017) Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions on Automatic Control 63 (3), p. 714–725. Cited by: §IV, §V-B. [29] L. Su, X. Li, Y. Hua, X. Dong, and J. Lü (2026) Optimal tracking of time-varying formation in open nonlinear multiagent systems. IEEE Transactions on Automatic Control. Cited by: §I. [30] X. Sun, C. G. Cassandras, and X. Meng (2019) Exploiting submodularity to quantify near-optimality in multi-agent coverage problems. Automatica 100, p. 349–359. Cited by: §VI-A, Example 1. [31] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour (1999) Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems 12. Cited by: §IV-A. [32] J. Vondrák (2008) Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing, p. 67–74. Cited by: §I. [33] S. Welikala, C. G. Cassandras, H. Lin, and P. J. Antsaklis (2022) A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems. Automatica 144, p. 110493. Cited by: §I. [34] R. J. Williams (1992) Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning 8 (3), p. 229–256. Cited by: item REINFORCE []:, item REINFORCE []:. [35] Z. Xu, S. S. Garimella, and V. Tzoumas (2025) Communication-and computation-efficient distributed submodular optimization in robot mesh networks. IEEE Transactions on Robotics 41, p. 3480–3499. Cited by: §I. [36] Z. Xu, H. Zhou, and V. Tzoumas (2023) Online submodular coordination with bounded tracking regret: theory, algorithm, and applications to multi-robot coordination. IEEE Robotics and Automation Letters 8 (4), p. 2261–2268. Cited by: §I, §I, §I, §I-C, item OSG []:, item OSG []:. [37] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu (2022) The surprising effectiveness of PPO in cooperative multi-agent games. Advances in Neural Information Processing Systems 35, p. 24611–24624. Cited by: §I, §I. [38] K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Basar (2018) Fully decentralized multi-agent reinforcement learning with networked agents. In Proceedings of the 35th International Conference on Machine Learning, Vol. 80, p. 5872–5881. Cited by: §I, §I, §I, §I-B. [39] M. Zhang, L. Chen, H. Hassani, and A. Karbasi (2019) Online continuous submodular maximization: from full-information to bandit feedback. Advances in Neural Information Processing Systems 32. Cited by: Assumption 2. [40] Q. Zhang, W. Huang, C. Jin, P. Zhao, Y. Shu, L. Shen, and D. Tao (2025) Multinoulli extension: a lossless yet effective probabilistic framework for subset selection over partition constraints. In Proceedings of the 42nd International Conference on Machine Learning, p. 75030–75066. Cited by: Remark 1. [41] Q. Zhang, Y. Sun, C. Jin, X. Zhang, Y. Shu, P. Zhao, L. Shen, and D. Tao (2025) Effective policy learning for multi-agent online coordination beyond submodular objectives. Advances in Neural Information Processing Systems 38, p. 164278–164339. Cited by: §I, §V-B, item MA-SPL []:, item MA-SPL []:, Remark 1. [42] Q. Zhang, Z. Wan, Y. Yang, L. Shen, and D. Tao (2025) Near-optimal online learning for multi-agent submodular coordination: tight approximation and communication efficiency. In International Conference on Learning Representations, Cited by: §I, §I, §I, §IV, §V-B, item MA-OSEA []:, item MA-OSEA []:.