Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives
Authors: Qixin Zhang
Yan Sun
Can Jin
Xikun ZHANG
Yao Shu
Puning Zhao
Li Shen
Dacheng Tao
Venue: NeurIPS 2025 poster ()
Keywords: Multi-Agent Coordination
Policy Learning
Continuous Relaxation
Online Non-Submodular Maximization
Surrogate Functions
Primary area: reinforcement_learning

Abstract: In this paper, we present two effective  policy learning algorithms for multi-agent online coordination(MA-OC) problem. The first one, **MA-SPL**,  not only can achieve the optimal $(1-\frac{c}{e})$-approximation guarantee for the MA-OC problem with submodular objectives but also can handle the unexplored  $\alpha$-weakly DR-submodular and $(\gamma,\beta)$-weakly submodular scenarios, where $c$ is the curvature of the investigated submodular functions, $\alpha$ denotes the diminishing-return(DR) ratio and the tuple$(\gamma,\beta)$ represents the submodularity ratios.  Subsequently, in order to reduce the reliance on the unknown parameters $\alpha,\gamma,\beta$ inherent in the **MA-SPL** algorithm, we then introduce the second online algorithm named **MA-MPL**. This **MA-MPL** algorithm is entirely *parameter-free* and simultaneously can maintain the same approximation ratio as the first  **MA-SPL** algorithm. The core of our **MA-SPL** and **MA-MPL** algorithms is a novel continuous-relaxation technique term as policy-based continuous extension. Compared with the well-established multi-linear extension, a notable advantage of this new policy-based continuous extension is its ability to provide a lossless rounding scheme for any set function, thereby enabling us to tackle the challenging  weakly submodular objective functions. Finally, extensive simulations are conducted to demonstrate the effectiveness of our proposed algorithms.

Effective Policy Learning for Multi-Agent Online
Coordination Beyond Submodular Objectives
Qixin Zhang
Yan Sun
Can Jin
Xikun Zhang' Dacheng Tao
Yao Shu Puning Zhao
Li Shen
College Computing and Data Science, Nanyang Technological University, Singapore
The University of Sydney 'Hong Kong University of Science and TecnnologyGGuangzhuuu)
"Rutgers University "Snn Yat-sen University
{qixin.zhang xikun zhang, dacheng.tao/) tao]aatuu edu.ag; ag, sun9899 @ snn..ydney.edu.au
boahhuhhkutt-z.eduu ead.edd..c {zhaopn, shenli6) schnolp ahenli6]@mail. @mail.
sysu. edu. cn
Abstract
In this paper, we present two effective policy learning algorithms for multi-agent online coordimation(MA-OC) problem. The first one. MA-SPL, not only can achieve the optimal (1 2) a-aproximatiion guarantee for the MA-OC problem with sub- modular objectives but also can handle the unexplored a- a-weakly DR DR-submodular and (y, -we-kllll submodular scenarios, where c is the curvature of the investi- gated submodular functions, a denotes the tuple (9 represents the submodularity ratios. Subsequently, in order to reduce the reliance on the unknown parameters a;, 7; 3 inherent in the MA-SPL algorithm, we further introduce the second online algorithm named MA-MPL. This MA-MPL algorithm is entirely purameler-free and simultaneously can maintain the same approximation ratio the first MA-SPE algorithm. The core of our MA-SPL and MA-MPL algorithmss is a novel continuous-relxxttin based continuous extension. Compared with the well-established multi-linear extension, a notable advantage of this new policy-based continuous extension is its ability to provide lossless rounding scheme for any set function, thereby enabling us to tackle the challenging weakly submodular objectives. Finally, extensive simulations conducted to validate the effectiveness of proposed algorithms.
ratio and the
technique termed as policy-
Introduction
Coordinating multiple autonomous agents cooperatively complete complex tasks in time-varying environments is a significant challenge with extensive applications in machine learning, robotics and control, including target tracking [27, 129, 130, 132], area monitoring [55, 73, 97], multi-path planning [100, 101, 102], mobile sensor placement [65, 67, 95], environmental mapping [6. 75] and task assignment [92, 5J. Critically, with the rapid advancement of self-supervised learning and the development of large Transformers with billions of parameters, large language models (LLMs)
now capable of generating factual and coherent responses to human queries [11, 25, 107, 51]. However, the mixed quality of training data can lead to the generation of undesired responses, presenting sigmificant challenge. Therefore, how select limited number of high-quality input- output examples from multi-source and massive datasets for fine-tuning LLMs remains critical challenge a problem that can be formulated as multi-agent collaborative data selection [69, 70, 80, 93]. Moreover, the emergence of foundation models further highlights the necessity of effective
'These authors contributed equally this work. Corresponning author: Dacheng Tao.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

cooperation architectures to enable multi-agent Al systems to mutually learn and adapt in dynamic environments [4, 23. 28, 60]. Motivated by these diverse scenarios, thus this paper delves into the Multi-Agent Online (oordination(MAA-0 problem, establishing theoretical paradigm for real-world embodied systems, L.MMs fine-tuning, and intelligent agent collaboration.
Prior to this, numerous studies have demonstrated that the utility functions associated with wide range of multi-agent coordination scenarios often exhibit a diminishing (eatsshiinggeettr(R)RR property. Specifi- cally, as the number of agents increases, the marginal gain in benefit will tend to decrease. For instance, in area monitoring using a fleet of unmanned aerial Ahiicle(UAAV)) due to the overlaps of sensing ranges, the increment of the total monitored area from adding an additional UAV typically becomes less and less as the team of UAVs expands. Note that the diminishing seniiiiiiinn-etuurr property is also known as submodularity in mathematics [7, 42]. Consequently, vast majority of research regarding multi-agent coordination focus on submodular objectives (45, 50, 64, 66, 78, 92, 94, 95, 1 14, 115, 126, 129, 131].
However, recent works [55, 56, 59, 62, 117] observed that there also exist many multi-agent coordi- nation scenarios inducing utility functions that are tossetto-uumodullrr but not strictly submodular. A notable example is the employment of a swarm of UAVs to track multiple moving objects. In this scenario, each UAV needs to periodically determine its moving direction and speed. Particularly, un- der the Kalman filter framework, [55, 56, 62] pointed out that the aforementioned trajectory selection problem of UAVs can be formulated as a multi-agent variant of the general online weakly submodular maximization problems. It is worth noting that the currently well-known algorithms for weakly sub- modular maximization are highly dependent on the discrete local search [20, 43, 53, 76, 106]. So far, however, how to extend this local search into online settings still remains an uncharted territory. Thus, almost all existing studies regarding multi-agent coordination with weakly submodular objectives choose to neglect the changing environment and focus on simple offline scenarios [55, 56, 62, 1 117]. In view of all this, a natural question arises:
Q1: Is it possible to design an effective online algorithm for MA-OC problem with weakly submodular objectives?
In addition, we also find that when the objective function exactly submodular, the state-of-the-an al- gorithms [94, 126] for the MA-OC problem only can guarantee a sub-optimal -approxxmaa, which mismatches the best possible (1 {) >apppoximmtioon established in the works [105, 54] for single-agent submodular maximization. Here, denotes the curvature of the investigated submodular functions. Given this drawback, another question comes to our mind, that is,
Q2: Is it possible to achieve the optimal (1 -1-3 -aprroximmatttooo ratio for MA-OC problem with submodular objectives?
In the subsequent sections of this paper, we will provide an affirmative answer to these two questions by presenting an effective online algorithm named MA MALSPL, which not only can achieve the optimal (1 - appproximmttnnnnn for the MA-OC problem with submodular objectives but also can address the previously unexplored weakly submodular scenarios. The core of our proposed MA-SPL algorithm a novel continuous-relaxatioo framework named policy-based continuous extension, which can efficiently transform the discrete set function maximization problem into a solvable continuous optimization task. Furthermore, compared to the well-established multi-linear extension [15], a notable advantage of our proposed policy-baseds continuous extension is that it can provide a lossless rounding scheme for any set objective function. In contrast, all known lossless rounding schemes for the multi-linear extension require the set objective function to be submodular [15, 18, 19]. Moreover, to eliminate the dependence of both DR ratio and submodularity ratio inherent in our proposed aePoLalooitie algorithm, we further present a parameter-free online algorithm termed as MA MA-MPL for the MA-OC problem with general weakly submodular objectives.
MA-SPL
In summary, we make the following contributions:
This paper introduces an innovative continuous- relaxxatoon technique named policy- based continuous extension for the general multi-agent coordination problem. Furthermore, we conduct an in-depth exploration of the differentiability. monotonicity and submodularity of our proposed policy- continuous extension. More importantly, when the investigated set objective function submodular or weakly submodular, we design three different surrogate functions for our policy-based continuous extension. The stationary points of these three surrogate functions can yield a better approximation guarantee than those of the original policy- based continuous extension itself.

---

Table I: Comparison of the different algorithms for T-round MA-OC problem. Note that 'Approx.' denotes the obtained approximation ratio, '#Com.' represents the number communication, '#Queries' denotes the number of queries to the set objective functions, 'D-Regret' denotes the dynamic regret bound, 'Proj-free' indicates whether the method does not require projection, Paara-free" indicates whether the method does not require prior knowledge of curvature and parameters a, 7, 3. Pr is the deviation of maximizer sequenee, is the spectral gap of the weight matrix, d(C)) is the diameter of the graph C, 6(7, B(1 - 7) + +7 and K 2 E Ki.
Method
Unility
Para-fice
Proj-free
Graph
Approx.
#Com.
#Queries
D-Regiet
OSG (115,
Submodular
Complete
O(T)
O(e2)
(l7PTT)
MA-OSMA [126]
Submodular
x
Connected
OIT)
((w7)
MA-OSEA [126)
Suhmodular
x
Connected
O(T)
((17)
MA-SPI. (Algorithm I)
Submodular
Counected
(1-3)
O(T)
O(e2)
0
1-7
o--weaklyy DR-Subb
x
Connected
(1-e-))
O(T)
O(e7)
(s. ())-weklly Sub
x
Connected
(17)
0(47)
MA-MPL
e-weakly DR-SSub (1, we-welyly Sub
Connected
0(19)))
O(r7%))
(PGT)
(Algorithm 2)
Connected
a(T9)))
(
(d(C)
Building on these surrogate functions, we then propose novel online algorithm named MA-SPP for the concerned MA-OC problem. Moreover, we also verify that, when the set objective function is
monotone submodular with curvature c, a-weakly DR DR-submodular (7,33) --wakly submodular, our
proposed MA MA-SPL can achieve an approximation ratio of (1 - .) (1 (1-e -a) or (1 -000--000--00000-- ->)+7"))
A(1-7)+7
with a dynamic regret bound of O
PrT
to the best comparator in hindsight, respectively. Here,
I-T
Pr is the deviation of maximizer sequence, the spectral gap of the network, denotes the DR ratio, 33 represents the upper submodularity ratio and is the lower submodularity ratio.
To eliminate the dependence of both DR ratio and submodularity ratio of our MA-SPL algorithm. we next present a parameier-free online algorithm named MA-MPL for the MA-OC problem. The cornerstone of this MA-MPL algorithm is novel inequality between our proposed policy-based con- tinuous extension and the original set objective function. Moreover, when the objective function is monotone a-weakly ou-souoodulaar or (7, -weakly submodular, our proposed MA-MPL algorithm also can enjoy the same approximation ratio with a regret bound of O (PIT) to the best comparator in hindsight, where d(G) is the diameter of the corresponding communication graph G.
We conduct numerical experiments to verify the effectiveness of our proposed algorithms.
Related Work. Due to space limitations, the comprehensive literature review is placed in Appendix A. In particular, we present a detailed comparison of our proposed MA-SP! algorithm and MA-MP) algorithm with existing studies on multi-agent online coordination in Table 1.
2 Problem Setup
This section will provide a detailed introduction to multi-agent online coordination((MA-OO) problem.
In MA-OC problem, we generally consider collection of n distinct agents, indexed by the set N & [1. and interconnected through an undirected network G(N, E). Here, & S A x V represents the possible communication links among agents. Additionally, each agent endowed with a unique set of actions V, & {Vi,1..... Ui... meaning that these action sets are mutually disjoint, i.e., V.nV; = @ for any i,j E N.. In the process of multi-agent online coordination, at every time spot action set V;, After committing to these choices, the environment will reveal utility set function ft defined over the aggregated action space V A UiEvY; Then, the agents receive the utility faluie (t))) As a result, the goal of agents is to maximize their cumulative reward as much as possible. Specifically, at each time step / [T], we need to address the following set function maximization problem multi-agent collaborative manner:
/ is
[T), each agent i E A' will separately select one action a;(() from its own
max fe(S), s. S C V and |S n V. LLViE.
(I)
Furthermore, in numerous practical applications regarding MA-OC problem, each agent usually has limited perceptual range, allowing it to sense only the environmental changes in its immediate
3

---

surroundings. For example, in target tracking scenarios involving a swarm of unmanned aerial vehi)les(UAVs), each UAV only can perceive the targets within its sensing radius. leaving those outside this range undetected. To model this limitation, several studies on the MA-OC problem [126, 115, 114, 95, 94] adopt a local feedback model. More specifically, after ft is revealed, each agent i e W only permitted to query a local marginal oracle Qi V; x 2 + R, defined as 2i S) & [aaa)) _ (a)) - [+()) for any a E Vi and S _ V. This implies that, at each time E [T], agents only can receive the marginal evaluations about the actions within their individual action set, rather than the full information of ft. We also impose this local-feedback constraint in this paper.
Before going into the details, it is crucial to emphasize that, in many real-world scenarios, there exists such an (approximate) local marginal feedback oracle O for each agent E N after fr is revealed. Typically, in addition to the decision-makee shelf learning algorithms to estimate the marginal contributions of their available actions based on the observed and collected information (See [27]). Moreover, the local information available to one agent often insufficient for precisely assessing the actions of other agents who are not close vicinity. Given this fact, confining each agent to the marginal estimations of the actions within its own action set also can further reduce the accumulation of learning crrors.
process, agents often utilize various off-the-
Dynamic p- g-Regret: Generally speaking, the set function maximization problem (1) is NP-hard [83, 35], indicating that no polynomial-times algorithms can solve optimally, Thus, this paper employs the dynamic p-regret [21, 61, 103, 115, 126, 134] to measure the performance of our proposed algorithms for MA-OC problem. In dynamic p-regret, the algorithm is compared against a sequence of local maximizers with scale parameter p E [0, i... (T) & o - f((A)) Σi= fc fuLeev (t)). where Aï is the optimal solution of problem (I) and a, (t) is the action chosen by agent i at time t.
3 Preliminaries
In this section, we introduce some basic concepts and the frequently used notations.
Notations. For any positive integer n, the symbol [n] denotes the set fl.....n), .n. Op and 1, denote the p-dimensional vector whose all components are O and 1, respectively. Moreover, || 1la and || 2l2 stand for the L1 norm and L2 norm for vectors, respectively. We also use Am to represent the standard m-dimennsonal simplex, that is, A., - ((81)..., Em x; S 1, x; 2 0, Vi E [m]}-
Submodularity and Curvature. Let V be finite ground and ʃ 2 + R,, be set function mapping any subset of V to a non-negative real number. Then, for any two subsets S,T C V, we denote by S()) the marginal contribution of adding the elements of T to S, i.e., S(T(S) & U f(S). In particular, when T is a singleton set {w), we also use [(V(S) to represent f((v)()) Therefore, we say a set function f is submodular if and only if it satisfies the diminishing- return property [85, 42, 41], that is, f(]SS Z f()(T)) for any S C T C V and v E V T. To precisely characterize the diminishing-return property, [26, 36, 105, 109] introduced the concept of curvature for submodular functions, which is defined as A 1 minsgv, /(Su(e))-/(S)
f((1))-f(0)
Monotonicity. A set function f : 2 + R. is monotone if and only if f(S) S f(T) for any S S C V. Moreover, in this paper, we suppose the set function f is normalized, that is, (0) 0.
Weak Submodularity. set function f 2 + RR+ is said to be y-weakly submodular from below for some y E (0, 1] if and only if Everys (u|S) 2 (f(T) f(S) for any two subsets S C T C V. where y is called as the lower submodularity ratio [29, 30, 20]. Similarly, we also can define the weak submodularity from above, that is, a set function f 2" + RR, is B-weakly submodular from above for some 3 2 1 if and only if Ever,s [( (u)) < (J( - (S C C V. where 3 is the upper submodularity ratio. When set function f is both 7-weakly submodular from below and 8-weakly submodular from above, we say it is (v, wweakly submodular [106].
Weak DR DR-submodularity. A set function f : 2 + R2 is a-weakly Du-submodular for some a E 1) if and only [(((S) 2 (:((v]T) for any two subsets 5 CCC. T C V and v E V T. In particular, is often called as the diminishing-returnnD noting that, from the previous definition of weak submodularity, we can infer that an a- a-weakly subsubnod function automatically satisfies the conditions for being (a, 1 --weklly submodular.
ratio [9, 68, 43, 48, 76]. It is worth

---

4 Policy-based Continuous-Relxationn Framework
Before presenting our proposed algorithms for the MA-OC problem, we firstly explore the offline set function maximization problem (I). In recent years, compared to discrete optimization, the field of continuous optimization has made significant advancements, yielding broad spectrum of effective algorithmic frameworks and theoretical tools. Consequently, one promising strategy to addressing the set function maximization problem (1) is to convert it into solvable continuous optimization problem throughout continuous-relxxatiin techniques.
A well-known contitious-relaaation framework is the multi-linear extension [15]. which was in- troduced for maximizing submodular set functions. Regrettably, this relaxation framework cannot be directly applied to the general set function maximization problem (1), as most existing lossless rounding schemes for multi-linear extension- -uchh as pipage rounding [1], swap rounding [18], and contention resolution [19]-rely heavily the submodular assumption. Note that lossless rounding schemes refer to methods that convert the obtained continuous solution into a feasible discrete solution without any loss in terms of the objective function value. To date, how to losslessly round the multi-linear extension of non-submodular set functions, e.g. (7, 3-weaklyy submodular and a-weakly DR-submodular functions, still remains an open question [106]. To overcome this hurdle, we will introduce an innovative continuous-relaxati technique in the subsequent part of this section.
4.1 Policy- -baed Continuous Extension
From the previous description about the MA-OC problem provided in Section 2, we can view the set function maximization problem (I) as a variant of multi-agent cooperative game [2, 98, 1 112 120]. Inspired by this viewpoint, we naturally consider whether each agent i E "N can learn policy TV - (Tr.1...., ).,..) over its individual action space V, A {u..1...., Ui,, } and then utilizes this policy n, to make decision, where each Te. represents the probability of agent taking the action m,m,, v' E [Kg]. Based on this idea, if letting a; E V. U {Ø} denote the random action chosen by each policy n,, Vi E N, then we can obtain the following policy-based continuous extension, namely, Definition 1. If T4 & (MT.1....., Ti, E AR, for any i E N. then the policy-based continuous extension F;: : 1=11 An. - for the set function maximization problem (1) can be defined as:
E (fe(UE {ai)) II [I((a/zz)): 2=1
(1 n.,)
(2)
(LEV.U(O).ViEN
where p((mT)) is a probability distribution over the set V; U {0). that is, p(ui, Timm, Vi [m), Vm E [ss] and p(0(7z) =1 - Tim.. Vi N.
Remark 1. It is noteworthy that, in (2), with the probubility Em Ti,m the policy n, will not pick any action from V., which means there is a possibility that no action will be chosen, i.e., 0. Remark 2. The definition in (2) highlights a notable advantage of our proposed policy-based continuous extension: it does not assign probabilities to any subset that violates the constraint of problem (1), As result, for any set function fe and any (Ti...... Th)) E III= Ar.. throughout the Definition 1, we can easily generate a subset, i.e., Ua that adheres to the constraints of problem (1) while ensuring E (fe (U) (a:)))
FI( Rn). In contrast, all known lossless rounding schemes of the multi- linear extension require the function ft to be submodular [15, 18, 19].
Remark 3. Notably, we observe that the works 196, 128] have introduced two relaxation techniques for lattice submodular and k-submodular functions, both of which are analogous to our policy-based continuous extension F,. However, it is crucial to emphasize that there exist notable differences between our work and [96, 128]: a) The lattice formulation rypically requires an 'order' relationship among different actions of the same agent. However, in our multi-agent coordination problem, we do not impose any specific order on the decisions. Consequently, the results and algorithms from [96, 128] are not directly applicable to our scenario. b) In addition to submodularity, our paper also considers weak submodularity and allows for varying sizes of action sets among agents.
With the policy-based continuous extension F, defined in Eq.(2), the set function maximization problem (1) can be naturally relaxed into a continuous maximization task, i.e.,
N,,,, max (. : s.t. || S 1, π4 E [0, 1] Vi W.
In order to effectively tackle the policy optimization problem (3), we next investigate the properties of our proposed policy-basce continuous extension F,.
5

---

4.2 Properties of Policy-based Continuous Extension
This subsection will focus on characterizing the differentiabilityy monotonicity and submodularity of our proposed policy-based continuous extension. Specifically, we have the following theorem:
Theorem (Proof in Appendix D). The policy-bused continuous extension Fe II- Ax, + R+
defined in (2) satisfies the following properties:
1): For any point (B1,... (BI....,,n)) E IT= ARY, the first-order derivative of Ft at variable Ti,m. Vi
N, vm E [Ke], can be expressed as follows:
OF
@TCmm (T TT.....,TTy. R.,) A Thn (fi(vrm) [ UjFiJEN (a;t))
where új TT indicates that action 0j is randomly selected from Vj U (0) based on the policy Tj;
2): If the set function ft is monotone, then aF: (TI..... Tnn) 2 0 for any point (TI,..., An) 85....
Ih Ang. E and m E [Ki], which means the monotonicity of ft can be inherited by Fg
3): If ft is a-weakly DR-submodular, then F; is a-weakly continuous DR-submodular [58, 88) over IT Ary that is, for any two point .T....., Thn) -IT_ An, and (r.....,, T.h) E III A if
Ti S nς Vi E N,, we have that V ..)) 2 V .T.. ..)))
4): For any subset S within the constraint of problem (1) and any point ( J..) E E Axp. when is monotone a-weakly DR- DR-submodular, the following inequality holds:
OF.
a (ff((5) FF In) )
Σ
(T...... Rn),
(L.m)) ES
where {(i, m)) vi, E S} denotes the set of all indices (i, m)) such that Uim E S. Similarly, when fo is monotone (7, --wekklly submodular, we can show that
(7² (()) (8(1 7) -2)) R.))
OF
(
TT.)
(5)
(f.m)::))... ES
Remark Part 3) indicates that when fe is submodular, namely a our policy-based continuous
extension F2 belongs to the well-studied continuous DR-submodular functions. However, it is important to highlight that these existing results for continuous FR-submodular maximization [57, 58, 89, 90, 111, 122] cannot be directly extended to our policy-based continuous extension Ft. This because all of them heavily rely on the inequality (y --x, VG(x)) 2 V - G(x) where G monotone continuous DR-submodular function and / denotes coordinate-wsee maximum operation. Note that the previous inequality requires that the domain of must be closed under the maximum operation V. However, the domain I An, of our proposed F; does not meet this requirement.
5 Multi-Agent Policy Learning
This section explores how to utilize the policy- continuous extension introduced in Section to address our concerned MA-OC problem. Broadly speaking, a notable advantage of continuous- relaxation techniques is that they enable the use of graddeent-baat based methods, such as gradient ascent [8, 72, 86] and Frank-Wolfe method [10, 71], to tackle discrete optimization problems. Moreover, as is well established the literature [3. 31, 44, 71], under mild conditions, wide range of gradient- algorithms can converge to the stationary points of their target objectives. Motivated by these findings, we next investigate the stationary points of our proposed policy- based continuous extension Fz.
5.1 Stationary Points and Surrogate Functions
At first, we recall the definition of stationary points for maximization problem, that is, Definition Given a differentiable function functioo G - R and domain C S K. point x E C is called stationary point for the function G over the domain C if and only if m'mmxaee (y - VG(x)) 0.
Next, we examine the performance of the stationary points of our proposed posicy-based continuous extension F; relative to the maximum value of problem (1). Specifically, have that

---

Theorem 2 (Proof in Appendix E). Given set function ft: -2 + Rt, (Ti Th is a stationary
point of its policy-based continuous extension F, over the domain II= D., and S denotes the optimal solution of the corresponding maximization problem (1), then the following inequalities hold:
1): When ft is monotone submodular with curvature c E [0, 1]. ,, 2 (1t0) fe(5"):
2): When Jt is monotone a-weakly DR-submodular, P. " TT,)) 2
a²
fe(S*);
Ita?
3): When ft is monotone (7y, ---eaklyy submodular, (,
8+B(1 fe(S)).
Remark 5. is worth noting that, in a certain sense, the approximation guarantees established in Theorem 2 is tight. In Appendix E.3, we will present simple instance of a submodular function S0 i.e., c= a = -y = B = 1, whose policy-baser continuous extension Fy can attain a -approximation guarantee stationary point that is also a local maximum.
Theorem 2 indicates that when the original set function f. is monotone submodular with curvature c, a-weakly DRssubmodular or (y, 3)-waklly submodular, the direct application of gradient- based methods our proposed policy-based continuous extension F2 can ensure approximation ratio of
( (1+e): ( a²
(+oa)) or (+ to the problem (1), respectively. However, as shown in [105, 36],
the optimal approximation ratio for maximizing a monotone submodular function with curvature e (1 )) which significantly exceeds the previous + Japproximmatoon provided by stationary points of Fr. Similarly, [53] pointed out that the optimal approximation for a-weakly DR-submodular
maximization is (1 - e e) which is also greater than the (144z) -approximation established in Theorem 2. Motivated by these findings, we naturally wonder whether is possible to enhance the approximation guaraniees of the stationary points of our proposed policy-based continuous extension.
Previously, the multi-linear extension of submodular functions also encountered similar issue, namely, the stationary points of the multi-linear extension only can guarantee a sub-optimal 1 approximation [38, 58]. To overcome this drawback, prior studies [39, 40, 122, 126] constructed a novel surrogate function for the multi-linear extension and proved that the stationary points of this surrogate function can achieve the optimal (1 2) >approxxmmation Inspired by this idea, we also hope to develop a surrogate function for our proposed policy-based -baed continuous extension F; such that it can improve the approximation ratios of the stationary points of F,. Specifically, we have that
Theorem 3 (Proof in Appendix F). Similar to [122, 125, 126], for any given policy-based continuous extension Ft introduced in Definition 1, consider surrogate function Ft I[==1 Ak. - R+ whose gradient at each point E IT= Ar, is weighted average of the gradient V V x). i.e. (x) = So w(=)V * æ)dz where w(zz) is a positive weight function over [0, 1]. After elaborately designing the weight function w((2), we can show that:
1): When fe is a-weakly DR-submodular and wi()) co(s-1), for any stationary point (πf,-.., -....... nTS)) of the surrogate objective Fÿ over IT ARG, then have (TT nT, (1 f
2): When fe is (r, (T.B)-weend B--eeakl submodular and w(2) (x-11))=-11) where d(T, B) = 3(1 - -7) + 72 for any stationary point (zi,.... TT,,) ). of the surrogate objective Fę over the domain II ART, then
we can show that Fe(mt TT,) (002((211)) (22(1---06r0)) ({())):
6(7,8)
3): When fo is submodular with curvature and w(2) c=11, for any stationary point (Ti,... TT,)) of the objective (FE+ + Go) over IT= ARp then we have F (TÇ TT,) > (1- ((S",, where S* the optimal subset of problem (1) and (T T.,)) 2 Et 1i Em
VV Ti.am-
Remark 6. Note that part 3) of Theorem considers the objective (ET + G) instead of the surrogate Fi alone. Here, G, is special linear linear function related to the minimum margin gains of the corresponding submodular objective fú that is. fe (a|V- {a}), Va E V. Furthermore, it is important to emphasize that the proof of Theurem 3 is not a parallel copy of the articles [122, 126] regarding the multi-linear extension. This is because the works [122, 126] also utilized the same inequality in Remark 4, which requires our domain to be closed under the operation V. However, the domain of our F; does not satisfy this condition. As a result, new techniques are required to verify Theorem 3.
7

---

Algorithm 1: Aulti-Agent Surrogate Policy Learning(MA
Input: Time horizon T, weight function w(2), action set V; [#1,1,... Vi,e, J. weight matrix
W e [wsylaxe parameters (a, 7, 8) and step size ne Vt [T]
// Policy Initialization (Lines 1-2)
Initialize policy vector (...: (1)) for each agent i EW;
2 the policy (1) - 1n, and (1) _ On, when i + for any E
3 for 1 = 1.....,,, do
for each agent E . do
// Actions Sampling and Information Exchange (Lines 5-8) Compute the normalized policy P.(() - (e,((e)
[
Utilize the normalized policy (t( to sample an action (1) from Vi:
Agent exccutes the sampled action (t);
Exchange policy vector (t), (Tft),,..,,,,..ll with the neighboring agent j E N;;
// Surrogate Gradient Estimation (Lines 9-16)
Generate a random number (t) from n.v. Z where Pr(Z I 2) Li w(a)da
E [0,1]]
To w(a)da
10
for j jo 1, 1,...," ni do
Utilize the weighted policy 21) T. sample action (,(1) V2 (0):
12
Compute the random subset of actions S;(4) == ( (()};
13
Estimate the derivatives of the surrogate function based on Theorem and 3, i..,
OFT (T.,, (()) A (l)
SL w(z)dz) (vim (s)))), Vm E [k]]
14
if ft submodular then Update (1,m(() (dl, + 6 Sc (Vi,m))) })), Vm [ka]:
Aggregate the surrogate gradient estimations (dr, .... di,x, (t)) as vector d((t); // Policy Update (Lines 17-19)
16
Update (t +1 EmEN,UHO) ( for any j + and j E No
I7
Compute (t. 1) é EjENURR (t) (t);
18
Update (t, A argmin ||b ys,(t 1)112:
5.2 Multi-Agent Policy Learning via Surrogate Functions
Theorem 3 suggests that, when the original set function is monotone submodular with curvature a-weakly DR-submodular or (7, -ea-llllly submodular, the direct application of gradient-based methods targeting stationary points to the surrogate function Fe or its variant (F² + Go can
5) (21)) to the function achieve tight approximation ratio of (1 (1-5). (1 (1 or (2 $(1-2)+7²
maximization problem (I), respectively. Furthermore, recent study [126] developed an effective online algorithm for the multi-agent submodular coordination problem based on the well-studied consensus technique [84, 99, 118, 119] and the surrogate functions of multi-linear extension [122, 126]. Thus, in order to address the unexplored weakly submodular scenarios and simultaneously achieve the optimal (1 -approximmtaoon for submodular settings, we naturally consider replacing the surrogate functions of multi multi-linear extension in the algorithms of [126] with those of our proposed policy-based continuous extension F,, Motivated by this idea, we then present a general online algorithm named MA-SPL for MA-OC problem, with details presented in Algorithm
In Algorithm 1, at every time step E [T]. each agent N will maintain a local policy vec- (T., (t)..... n.. (t)). Here, (t) represents the policy being executed by agent while # (t).)
reflects agent i's current estimate of the policy Ti,s()) being taken by other agent j. Af- ter that, each agent selects an action a; (t) from V; based on the normalized policy p:(() s,,(t)) and shares its local policy vector with the neighboring agent j Nr. where Mf denotes the neighbors
TR,

---

of agent i. Then, according to the results of Theorem and Theorem 3, each agent estimates the first-order partial derivatives of our proposed surrogate function Fü at every coordinate ai Specifically, agent i initially samples a random number (t) from the random variable 2 with distri- bution Pr(Z S =) - Li w(a)da
Vz E [0, 1] and then approximates each
aF;
To w(a)daa
by di (t) _ ( fz (va. (t)) where (t) is a random set generated from the weighted policy vector (t) (t).... Tt. (t)). Furthermore, when the set objective function fi is submod- ular, Algorithm will further adjust each surrogate gradient estimation di,m (t) with the minimum marginal contribution (v [ }), Vm E [M,]] (See Lines 14-15). Finally, each agent updates its policy T.. (t) throughout a projected ascent along the direction dt & (di, ..................... di, (t)).
In sharp contrast with the previous MA-OSMA and MA-OSEA algorithms in [126], the key inno- vation of Algorithm 1 lies in the use of proposed policy- bhaee- continuous extension and its surrogate functions to update the policy vector in Lines 9-19, rather than relying on the well-studied multi-linear extension [15]. Morcover, our proposed policy-based continuous extension naturally aligns with the actions sampling process in Lines 5-7, ensuring that, for any set function ft. the function value at the executed actions UieN (t)
at least as large as the expected function value Fg (11,1 :.:: T..,)), namely, E (Ji(Vie (())) 2 F. (T ,,.n). This is a significant advantage over the multi-linear extension, as the latter generally requires the submodular assumption to guarantee the losslessness of the action sampling of Lines 5-7 (See Lemma 13 in [126])-
Next, provide the theoretical analysis for the proposed Algorithm 1. Before that, introduce some standard assumptions about the communication graph G(N,E) E) and the weight matrix W, i...
Assumption 1. The graph G(N E) is connected. Furthermore, the weight matrix W [wig]nxn E R is symmetric and doubly stochastic, namely, WT W and W1, 1,. That is to say, T < 1 where T = max[[>2[[ (.) (n (W)I) is the second largest magnitude of the eigenvalues of W and X₂ (W) denotes the i-th largest eigenvalue of matrix W.
With this Assumption 1, we then can get the following convergence results for our Algorithm 1, i.e. Theorem 4 (Proof in Appendix G). Under Assumption 1, when each set objective function fo is monotone submodular with curvature c, a-weakly DR Ru-budoodlaar or (ri - submodular. if we set the weight function w(z) according to Theorem and choose d) (V( (1 (-D)P()) where
Pr & ET= AA, is the deviation of maximizer sequence and the symbol A> denotes the symmetric difference, namely, SAT = (8) (T) (5), then our proposed Algorithm I can achieve dynamic p-regret bound of (V
P.T
that is, E (RG(T)) S <0(V P.T
where p= ()
= (1- el-- or ( (PPL-N)- ). respectively.
B(1-9))+7)
Remark 7. To the best of our knowledge, this is the first result that achieves the tight (1 -)- approximation for the MA-OC problem with submodular objectives and simultaneoussy can tackle the previously unexplored (7, -wwekllly submodular and a-weakly oR-buboodular scenarios.
Remark 8. Note that when considering the weakly submodular objectives, Line 9 of Algorithm I requires prior knowledge of the ratios o,, 7, 3 to set the weight function w(z). However, in general, accurately computing these parameters will incur exponential computations. To overcome this drawback, further present parameter-free online algorithm named MA-MPP in Appendix B.
6 Numerical Experiments
In this section, we validate the effectiveness of our proposed MA-SPL and MA-MPL algorithms via two different multi-target tracking scenarios. Especially in Figure I(a), (()) we consider submodular facility-location objective function [115, 126] with different proportions of 'Random', 'Adversarial" and 'Polyline' targets. According to the results in Figure ((a)-((c), we can find that the average utility of our MA -PL can significantly exceed the ofate-of-thh--ar MA-OSMA and MA-OSEA algorithms in [126], which is consistent with our Theorem Note that the suffixes in Figure I(a)-1(d) represent two different choices for communication graphs, where 'c' stands for complete graph and 'r' denotes an Erdos-Renyi random graph with average degree 4. contrast, Figure I (d)- adopt bayesian A-optimal criterion for the target tracking task, which will lead to a-weakly

---

-Rssubmodular utility function [53, 55, 106]. Given the unknown DR ratio a, in Figure 1(c)-1(f), we perform a brute-force 0.1-network search find the optimal parameter settings for MA-SPL algorithm. Subsequently, we report the best a = 0.1 case and the worse from Figure (d), we also find that our proposed MA-MPL and MA-SPL can substantially outperform the 'RANDOM' baseline, which is in accord with our theoretical findings. Particularly in 'RANDOM' baseline, we let each agent i randomly execute an action from its own action set V. Due to space limitations, more discussions about experiment setups and results are presented in Appendix C.
scenario in Figure I(d). Similarly,
(a) FE (b)
(c) PPA:
(d) O-Oytiml Design
(c) Complete Grugh
(f) Ende- Endos-Reny Gruph
Figure 1: A comparison of the running average utility across two distinct target tracking simulations.
7 Conclusion
In this paper, we primarily introduce an effective online policy learning algorithm named MA-SPL for the concerned MA-OC problem. Compared with the state-of-art MA-OSMA and MA-OSEA algorithms [126], our proposed MA-SPL not only can guarantee a tight (1 = -aapproximation for MA-OC problem with submodular objectives but also can address the unexplored (7, (...B)--weee -weakly submodular and a-weakly DR DRssubmodular scenarios. Subsequently, to eliminate the dependence on the unknown DR ratio and submodularity ratio in our MA-SPL algorithm, we further present parameter-free online algorithm named MA-MPL for the MA-OC problem. The key cornerstone of our MA-SPL and MA-MPL algorithms a novel continuous relaxation termed as policy-based continuous extension. In sharp contrast with the well-studied multi-lineal extension [15], notable advantage of this new policy-based continuous extension is its ability to provide lossless rounding scheme for any set function, thereby enabling us to tackle the challenging weakly submodular objective functions.
Acknowledgment
This project is supported by the National Research Foundation, Singapore, under its NRF Professor- ship Award No. NRF-P2024-001.
References
[1] Alexander A Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8:307-328, 2004.
[2] Stefano V Albrecht, Filippos Christianos, and Lukas Schäfer. Multi-Agent Reinforcement Learning: Foundations and Modern Approaches. MIT Press, 2024.
[3] Zeyuan Allen-Zhu. How make the gradients small stochastically: Even faster convex and nonconvex sgd. Advances in Neural Information Processing Systems, 31, 2018
[4] Anonymous. Scaling munge-language-mddl--moe ACL Rolling Review June 2024, 2024. under review.
multi-agent collaboration. In Submitted to
[5] Gürdal Arslan, Jason R Marden, and Jeff S Shamma. Autonomous vehicle-target assignment: A game-theoretical formulation. Journal of Dynamic Systems, Measurement and Control, Transactions of the ASME, 129(5))584-596 2007.
[6] Nikolay Atanasov, Jerome Le Ny, Kostas Daniilidis, and George J Pappas. Decentralized active information acquisition: Theory and application to multi-robot slam. 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 4775-4782. IEEE, 2015.
10

---

[7] Francis Bach et al. Learning with submodular functions: A convex optimization perspective. Foundations and Trends@ machine learning. 6(2-3):145-373, 2013.
[8] Dimitri Bertsekas. Convex optimization algorithms. Athena Scientific, 2015.
[9] Ilija Bogunovic, Junyao Zhao, and Volkan Cevher. Robust maximization of non-submodular objectives. In International Conference on Artificial Intelligence and Statistics, pages 890-899, PMLR, 2018.
[10] Gábor Braun, Alejandro Carderera, Cyrille w Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods. arXiv preprint arXiv:2211.14103, 2022.
[11] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877- 1901, 2020.
[12] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a nonsym- metric technique. Mathematics of Operations Research, 44(3):988-1005, 2019.
[13] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via new bounds for dr-submodular functions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1820-1831, 2024.
[14] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithmss, pages 1433-1452. SIAM, 2014.
[15] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing monotone submodular function subject to matroid constraint. SIAM Journal on Computing, 40(6):1740- 1766, 2011.
[16] Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: A review. Statistical science, pages 273-304, 1995.
[17] Luiz Chamon and Alejandro Ribeiro. Approximate supermodularity bounds for experimental design. Advances in Neural Information Processing Systems, 30, 2017.
[18] Chandra Chekuri, Jan Vondrak, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 575-584, 2010.
[19] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43(6):1831-110 2014.
[20] Lin Chen, Moran Feldman, and Amin Karbasi. Weakly submodular maximization beyond cardinality constraints: Does randomization help greedy? In International Conference on Machine Learning, pages 804-813, PMLR, 2018
[21] Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. In International Conference on Artificial Intelligence and Statistics, pages 1896-1905. PMLR, 2018.
[22] Shengminjie Chen, Donglei Du, Wenguo Yang, Dachuan Xu, and Suixiang Gao. Continuous non mon-moootone dr-submodular maximization with down-closed convex constraint, 2024.
[23] Weize Chen, Jiarui Yuan, Chen Qian, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Optima: Optimizing effectiveness and efficiency for L.bdd multi-agent system. In Wanxiang Che, Joyce Nabende, Flkaterina Shutova, and Mohammad Taher Pilehvar, editors, Findings of the Association for Computational linguistics: ACI. 2025, pages 11534-1 1557, Vienna, Austria, July 2025. Association for Computational Linguisties.
11

---

[24] Yixin Chen, Ankur Nath, Chunli Peng, and Alan Kuhnle. Discretely beyond 1/e: Guided combinatorial algortihms for submodular maximization. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 108929-108973. Curran Associates, Inc., 2024.
[25] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-
113, 2023.
[26] Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete applied mathematics, 7(3):251-274, 1984.
[27] Micah Corah and Nathan Michael. Scalable distributed planning for multi-robot, multi-target tracking. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 437-444, IEEE, 2021.
[28] Yufan Dang, Chen Qian, Xueheng Luo, Jingru Fan, Zihao Xie, Ruijie Shi, Weize Chen, Cheng Yang, Xiaoyin Che, Ye Tian, et al. Multi-agent collaboration via evolving orchestration. Advances in Neural Information Processing Systems, 2025.
[29] Abhimanyu Das and David Kempe. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In International Conference Muchine Learning, pages 1057-1064, 2011.
[30] Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19(3):1334, 2018.
[31] Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Learning, pages 2658-2661 PMLR, 2020.
[32] Bin Du, Kun Qian, Christian Claudel, and Dengfeng Sun. Jacobi-style iteration for distributed submodular maximization. IEEE transactions on automatic control, 6779)-468--4702, 2022.
[33] Marwa El Halabi, Suraj Srinivas, and Simon Lacoste-Julien. Data-efficient structured pruning via submodular optimization. Advances Neural Information Processing Systems, 35:36613- 36626, 2022.
[34] Ethan Elenberg, Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. The Annals of Statistics, 46(66))3339-3368, 2018.
[35] Uriel Feige. A threshold of In n for approximating set cover. Journal of the ACM, 45(4))634- 652, 1998.
[36] Moran Feldman. Guess free maximization of submodular and linear sums. Algorithmica, 83(3):853-878, 2021.
[37] Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. 20/1 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 570-579. IEEE, 2011.
[38] Yuval Filmus and Justin Ward. The power of local search: Maximum coverage over a matroid. In 29th Symposium on Theoretical Aspects of Computer Science, volume 14, pages 601-612. L.PIcss 2012.
[39] Yuval Filmus and Justin Ward. A tight combinatorial algorithm for submodular maximization subject matroid constraint. In 2012 IEFE 53rd Annual Symposium on Foundations of Computer Science, pages 659-668. IEEE, 2012.
12

---

[40] Yuval Filmus and Justin Ward. Monotone submodular maximization over a matroid via non-oblivious local search. SIAM Journal on Computing, 43(2):514-542, 2014.
[41] Marshall Fisher, George L Nemhauser, and Laurence A Wolsey. An analysis of approxi- mations for maximizing submodular set functions-ii In Polyhedral Combinatorics, pages 73-87. Springer, 1978.
[42] Satoru Fujishige. Submodular functions and optimization. Elsevier, 2005.
[43] Khashayar Gatmiry and Manuel Nomez-Rodriguuee Non-submodular function maximization subject a matroid constraint, with applications. arXiv preprint arXiv:1811.078b0 2018.
[44] Saeed Ghadimi and Guanghui Lan, Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on oplimization, 23(4):2341 2013.
[45] Bahman Gharesifard and Stephen L Smith. Distributed submodular maximization with limited information. IEEE transactions on control of network systems, 5(4):1635- 2017.
[46] Boqing Gong, Wei-Lun Chao, Kristen Grauman, and Fei Sha. Diverse sequential subset selection for supervised video summarization. Advances in neural information processing systems, 27, 2014.
[47] Suning Gong, Qingqin Nong, Wenjing Liu, and Qizhi Fang. Parametric monotone function maximization with matroid constraints. Journal of Global Optimization, 75(3):833-849) November 2019.
[48] Suning Gong, Qingqin Nong, Tao Sun, Qizhi Fang, Dingzhu Du, and Xiaoyu Shao. Maximize a monotone function with a generic submodularity ratio. Theoretical Computer Science, 853:16-24, 2021.
[49] Michael Grant and Stephen Boyd. Cvx: Matlab software for disciplined convex programming. version 2.1, 2014.
[50] David Grimsman, Mohd Shabbir Ali, Joao P Hespanha, and Jason R Marden. The impact of information in distributed submodular maximization. IEEE Transactions on Control of Network Systems, 6(4):1334-1333 2018.
[51] Daya Guo, Dejian Yang. Haowei Zhang, Junxiao Song. Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprint arXiv:2501. 1200: 2025.
[52] Kai Han, Shuang Cui, Benwei Wu, et al. Deterministic approximation for submodular maximization over a matroid in nearly linear time. Advances in Neural Information Processing Systems, 33:430-441, 2020.
[53] Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. Submodular maximiza- tion beyond non negatiiiti: Guarantees, fast algorithms, and applications. In International Conference on Machine Learning, pages
PMLR, 2019.
[54] Nicholas Harvey, Christopher Liaw, and Tasuku Soma. Improved algorithms for online submodular maximization via first-order regret bounds. Advances in Neural Information Processing Systems, 33:123-133, 2020.
[55] Abolfazl Hashemi, Mahsa Ghasemi, Haris Vikalo, and Ufuk Topcu. Submodular observation selection and information gathering for quadratic models. In International Conference Machine Learning, pages 2653-2662. PMLR, 2019.
[56] Abolfazl Hashemi, Mahsa Ghasemi, Haris Vikalo. and Ufuk Topcu. Randomized greedy sensor selection: Leveraging weak submodularity. IEEE Transactions on Automatic Control, 66(1):199-212, 2020.
[57] Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic conditional (nadient++::non) convex minimization and continuous submodular maximization. SIAM Journal on Optimization, 304)33355333 2020.
13

---

[58] Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, pages 5841-5851, 2017.
[59] Syed Talha Jawaid and Stephen L Smith. Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems. Automatica, 61:282-288, 2015.
[60] Can Jin, Hongwu Peng, Qixin Zhang, Yujin Tang, Dimitris N Metaxas, and Tong Che. Two heads better than one: Test-time scaling of multi-agent collaborative reasoning. arXiv 2025.
preprint arXiv:2504.0977
[61] Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pages 1466-55, 2007.
[62] Ege Can Kaya, Michael Hibbard, Takashi Tanaka, Ufuk Topcu, and Abolfazl Hashemi. Ran- domized greedy methods for weak submodular sensor selection with robustness considerations. Automatica, 171:11198: 2025.
[63] G. Khashayar and G. R. Manuel. Non-submodular function maximization subject matroid constraint, with applications, 2019.
[64] Solmaz S Kia. Submodular maximization subject to uniform and partition matroids: From theory practical applications and distributed solutions. arXiv preprint a0110. 2025.
[65] Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne VanBriesen, and Christos Faloutsos. Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Rexources Planning and Management, 1 134(6):516) 11-5526,,, 2008.
[66] Andreas Krause, H Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Robust submod- ular observation selection. Journal of Machine Learning Research, 9(12), 2008
[67] Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008.
[68] Alan Kuhnle, J David Smith, Victoria Crawford, and My Thai. Fast maximization of non- submodular, monotonic functions on the integer lattice. In International Conference on Machine Learning, pages 2786-2795 PMLR, 2018
[69] Lilly Kumari, Shengjie Wang, Amav Das, Tianyi Zhou, and Jeff Bilmes. An end-to-end submodular framework for data-efficient in-context learning. In Findings of the Association for Computational Linguistics: Lingittsse NAACL 2024, pages 3293 1993-3008, 2024.
[70] Lilly Kumari, Shengjie Wang, Tianyi Zhou, Nikhil Sarda, Anthony Rowe, and Jeff Bilmes. Bumblebee: Dynamic KV-cache streaming submodular summarization for infinite-context transformers. In First Conference on Language Modeling, 2024.
[71] Simon Lacoste-Julien. Convergence rate of frank-wolfe for non-convex objectives. arXiv preprini arXiv: /607 11070600000353. 2016.
[72] Guanghui Lan. First-order and stochastic optimization methods for machine learning, vol- ume 1. Springer, 2020.
[73] Ruolin Li, Negar Mehr, and Roberto Horowitz. Submodularity of optimal sensor placement for traffic networks. Transportation research part B: methodological, 171:29 43, 2023.
[74] Yucheng Liao, Yuanyu Wan, Chang Yao, and Mingli Song. Improved projection online continuous submodular maximization. arXiv preprint arXiv:2305.1 14444 2023.
[75] Jun Liu, Lifeng Zhou, Pratap Tokekar, and Ryan K Williams. Distributed resilient submodular action selection in adversarial environments. IEEE Robotics and Automation Letters, 6(3):5832- 5839, 1021.
14

---

[76] Cheng Lu, Wenguo Yang, Ruiqi Yang, and Suixiang Gao. Maximizing a non non con-decreasing non- submodular function subject to various types of constraints. Journal of Global Optimization. 83(4):727-751, August 2022.
[77] Piyushi Manupriya, Pratik Jawanpuria, Karthik S. Gurumoorthy, SakethaNath Jagarlapudi, and Bamdev Mishra. Submodular framework for structured -eparre optimal transport. Forty-first International Conference on Machine Learning, 2024.
[78] Jason R Marden. The role of information in distributed resource allocation. IEEE Transactions on Control of Network Systems, 4(3):64-664, 2016.
[79] Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[80] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submod- ular maximization. The Journal of Machine Learning Research, 17(1):33308373,, 2016.
[81] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Decentralized submodular maximization: Bridging discrete and continuous settings. In International conference machine learning. pages 5616-3625. PMLR, 2018.
[82] Loay Mualem and Moran Feldman. Resolving the approximability offline and online non- monotone dr-submodular maximization over general convex sets. In International Conference on Artificial Intelligence and Statistics, pages 2542-2564. PMLR, 2023.
[83] Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal on computing, 24(2))227-234) 1995.
[84] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-61, 2009.
[85] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approxima- tions for maximizing submodular set functions-i, Mathematical Programming, 14(1):265-
294, 1978.
[86] Y Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2013.
[87] Rad Niazadeh, Tim Roughgarden, and Joshua R Wang. Optimal algorithms for continuous non-monotone submodular and dr-submodular maximization. Journal of Machine Learning Research, 21(125):1-31, 2020.
[88] Mohammad Pedramfar and Vaneet Aggarwal. From linear to linearizable optimization: A novel framework with applications to stationary and non-stationary DR-submodular optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[89] Mohammad Pedramfar, Yididiya Y. Nadew, Christopher John Quinn, and Vaneet Aggarwal, Unified projection-fres algorithms for adversarial OR-subnodular optimization. In The Twelfth International Conference on Learning Representations, 2024.
[90] Mohammad Pedramfar, Christopher John Quinn, and Vaneet Aggarwal. A unified approach for maximizing continuous DR-submodular functions. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[91] Manish Prajapat, Mojmir Mutny, Melanie Zeilinger, and Andreas Krause. Submodular reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024.
[92] Guannan Qu, Dave Brown, and Na Li. Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions. Automatica, 105:206-215. 2150 2019,
[93] Akbar Rafiey. Decomposable submodular maximization in federated setting. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 2 21-27, 2024.
15

---

[94] Navid Rezazadeh and Solmaz S Kia. Distributed strategy selection: A submodular set function maximization approach. Automatica, 153:1 10000 2023.
[95] Alexander Robey, Arman Adibi, Brent Schlotfeldt, Hamed Hassani, and George J Pappas. Optimal algorithms for submodular maximization with distributed constraints. In Learning for Dynamics and Control, pages 150-162. PMLR, 2021.
[96] Aytune Sahin, Yatao Bian, Joachim Buhmann, and Andreas Krause. From sets to multisets: provable variational inference for probabilistic integer submodular models. In International Conference on Machine Learning, pages 8388-8399 PMIR, 2020.
[97] Brent Schlotfeldt, Vasileios Tzoumas, and George J Pappas. Resilient active information acquisition with teams of robots. IEEE Transactions on Robotics, 38(1):244-261, 2021.
[98] Elham Kazana-n and Khashayar Khorasani. Multi-agent team cooperation: A game theory approach. Automatica, (5(10):2205-22133 2009.
[99] Shahin Shahrampour and Ali Jadbabaic. Distributed online optimization in dynamic envi- ronments using mirror descent. IEEE Transactions on Automatic Control, 63(3)7714-725, 2017.
[100] Guangyao Shi, Lifeng Zhou, and Pratap Tokekar. Robust multiple-path orientcering problem: Securing against adversarial attacks. IEEE Transactions on Robotics, 39(3):2000-2077 2023.
[101] Amarject Singh, Andreas Krause, Carlos Guestrin, William Kaiser, and Maxim Batalin. Efficient plamning of informative paths for multiple robots. In Proceedings of the 20th international joint conference on Artifical intelligence, pages 2204-2211 2007.
[102] Amarjeet Singh, Andreas Krause, and William J Kaiser. Nonmyopic adaptive informative path planning for multiple robots. In Proceedings of the 2 International Joins Conference on Artificial Intelligence, pages 1843-1850, 2009.
[103] Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Advances in Neural Information Processing Systems, pages 1577-1584, 2008.
[104] Yan Sun, Qixin Zhang, Zhiyuan Yu, Xikun Zhang, Li Shen, and Dacheng Tao. Maskpro: Linear-space probabilistic learning for strict (n: M)-sparsity on large language models. arXiv preprint arXiv:2506. 12876, 2025.
[105] Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Research, +2(4):1197-121) 2017
[106] Theophile Thiery and Justin Ward. Two-sided weak submodularity for matroid constrained optimization and regression. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178, pages 3605-3634. PMLR, 02-05 Jul 2022.
[107] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Tim- othée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
[108] Harry L Van Trees. Detection, estimation, and modulation theory, part I: detection, estimation, and linear modulation theory. John Wiley & Sons, 2004.
[109] Jan Vondrák. Submodularity and curvature: The optimal algorithm (combinatorial optimizztion and discrete algorithms). RIMS Kokyuroku Bessatsu B, 23:253-2666 23:253-266. 2010.
[110] Yuanyu Wan, Lijun Zhang, and Mingli Song. Improved dynamic regret for online frank wolfe. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 3304- 3327. PMLR, 12-15 Jul 2023.
16

---

[111] Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, and Zhijie Zhang. Bandit multi- linear dr-submodular maximization and its applications on adversarial submodular bandits. In International Conference on Machine Learning, pages 35491-35555 PMLR, 2023.
[112] Jianhong Wang, Yuan Zhang, Yunjie Gu, and fae-Kyun Kim. Shaq: Incorporating shapley value theory into multi-agent q-learning. Advances in Neural Information Processing Systems, 35:5941 5954, 2022.
[113] Jun Wang. Zaifu Zhan, Qixin Zhang, Mingquan Lin, Meijia Song, and Rui Zhang. Data- efficient biomedical in-context learning: diversity-enhanced submodular perspective. arXiv preprint 2.5:.v2500...... /40 2025.
[114] Zirui Xu, Xiaofeng Lin, and Vasileios Tzoumas. Bandit submodular maximization for multi- robot coordination in unpredictable and partially observable environments. In Robotics: Science and Systems, 2023.
[115] Zirui Xu, Hongyu Zhou, and Vasileios Tzoumas. Online submodular coordination with bounded tracking regret: Theory, algorithm, and applications to multi-robot coordination. IEEE Robotics and Automation Letters, 8(4):2261 -2668 2023.
[116] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference on Machine Learning, pages 449-457, PMLR, 2016.
[117] Lintao Ye, Zei Liu, Ming Chi, and Vijay Gupta. Maximization of nonsubmodular functions under multiple constraints with applications. Automatica, 155:111126, 2023.
[118] Deming Yuan, Alexandre Proutiere, Guodong Shi, et al. Multi-agent online optimization. Foundations and Trends Optimization, 7(2-3):81 -133,, 2024.
[119] Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):
2016.
[120] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321-384, 2021.
[121] Mingrui Zhang. Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization: From full-information to bandit feedback. In Advances in Neural Information Processing Systems, pages 9206-92062 02669997,211 2019.
[122] Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submodular maximization: Boosting via non-oblivious function. In International Conference on Machine Learning, pages 261 16 26134, PMLR, 2022.
[123] Qixin Zhang, Zengde Deng, Zaiyi Chen, Kuangqi Zhou, Haoyuan Hu, and Yu Yang. Online learning for non-monotons dr- dr-suboodular maximization: From full information to bandit feedback. In International Conference on Artificial Intelligence and Statisties, pages 3515- 3537. PMLR, 2023.
[124] Qixin Zhang, Zengde Deng, Xiangru Jian, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Communication--ffiieeee decentralized online continuous dr-submodular maximization. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 1330--333 2023.
[125] Qixin Zhang, Zongqi Wan, Zengde Deng, Zaiyi Chen, Xiaoming Sun, Jialin Zhang, and Yu Yang. Boosting gradient ascent for continuous dr-submodular maximization. arXiv preprint arXiv:2401.088 008330,,0000..... 2024.
[126] Qixin Zhang, Zongqi Wan, Yu Yang, Li Shen, and Dacheng Tao. Near-optimal online learning for multi-agent submodular coordination: Tight approximation and communication efficiency. In The Thirteenth International Conference on Learning Representations, 2025.
17

---

[127] Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. Learning for Dynamics and Control, pages 48-59. PMLR, 2021.
[128] Huanjian Zhou, Lingxiao Huang, and Baoxiang Wang. Improved approximation algorithms for SkS-submodular maximization via multilinear extension. In The Thirleenth International Conference on Learning Representations, 2025.
[129] Lifeng Zhou and Vijay Kumar. Robust multi-robot active target tracking against sensing and communication attacks. IEEE Transactions Robotics, 39(3):1768 1780, 2023.
[130] Lifeng Zhou and Pratap Tokekar. Sensor assignment algorithms improve observability while tracking targets. IEEE Transactions on Robotics, 1206-1110,,,,,, 2019.
[131] Lifeng Zhou and Pratap Tokekar. Risk-aware submodular optimization for multirobot coordi- nation. IEEE Transactions on Robotics, 38(5):3064 -3844, 2022.
[132] Lifeng Zhou, Vasileios Tzoumas, George Pappas, and Pratap Tokekar. Resilient active target tracking with multiple robots. IEEE Robotics and Automation Letters, 4(1):129-13) 136, 2018.
[133] Junlong Zhu, Qingtao Wu, Mingchuan Zhang. Ruijuan Zheng, and Keqin Li. Projection- free decentralized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research, 22(51))11-22, 2021.
[134] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning, pages 928-936, 2003,
18

---

The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] is generally preferable "[No] ", it is perfectly acceptable answer "[No] provided proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendíx. If you answer [Yes] a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly state the paper's contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Some limitations of our proposed MA-MPL algorithm have been discussed in the Appendix I.
Guidelines:
19

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We have clearly stated the required assumptions and an accompanying com- plete proof in the appendix for each theory result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We present the detailed experiment setups and results in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
20

---

If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We reveal the codes about our experiments in supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
hublic/guidess httgg/gdd//ccSsiiiee (woo///oeeiisiiooooooooo onnolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https: // wwtpcc/cppppccee............cttt httpppppwpppppppppppppppppppaael httpe/ggiiddee/eeeebiiiiiiiiieie
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
21

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We present the detailed experiment setups and results in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We repeat each experiments five times and report the average utility in Ap- pendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma eтror bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We present the detailed experiment setups and results in Appendix C.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
22

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: pettps://neurppp: wttpeeewis.....uuppeeeee wttppctcpccccccccttttttcccccccct Cerollic/Ethissuiiee Cthicchuieelinee
Answer: [Yes]
Justification: Our research conforms, in every respect, the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our work is primarily of theoretical nature and has no immediate societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No high risk data model have been used.
Guidelines:
The answer NA means that the paper poses such risks.
23

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No existing asset has been used in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thooee com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new asset is introduced in the paper
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No experiments with human subjects were conducted.

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We conducted no experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core methodology of work does not involve the use of LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the core method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https pettpss//nntt //tpur/ess...//ee/ for what should or should be described.
/LLM)
25

---

Appendices for "Effective Multi-Agent Online Coordination Beyond Submodular Objectives"
Table of Contents
A Literature Review
27
A.1 Submodular Maximization
27
A.2 Non-Submodular Maximization
27
Multi-Agent Submodular Maximization
Seaaia..........................
28
A.4 Multilincar Extension
................................
29
B Parameter-free Multi-Agent Policy Learning
30
C Additional Experimental Details and Results
32
C.I Target Tracking with Facility-Loccation Objective Functions
32
C.2 Target Tracking under Extended Kalman-Fille Framework
34
More Details Experimental Setups
36
D Proof of Theorem 1
36
E Proof of Theorem 2
39
E.1 Proof of Part 2) and Part 3) in Theorem 2
39
E.2 Proof of Part 1) in Theorem 2
40
E.3 A Policy-based Continuous Extension with 1/2-Approximanee Stationary Point
42
F Proof Theorem 3
43
F.1 Proof of Part 1) and Part 2) in Theorem
43
F22 Proof of Part 3) in Theorem 3
45
G Convergence Analysis of MA-SPL Algorithm
47
Convergence Analysis MA-MPL Algorithm
56
Limitation and Broader Impact
62
26

---

A Literature Review
In this section, we aim to provide a comprehensive review of the related literature.
A.1 Submodular Maximization
A set function f 2² + R is called submodular if and only if it satisfies the diminishing- return property, namely, for any two subsets A C B C V and V B, (() -(A)) - It is widely recognized that the maximization of submodular functions is NP-hard, implying that no polynomial totomial-timeeaaee algorithms can solve optimally. To overcome this challenge. [85] introduced a greedy algorithm for solving the monotone submodular maximization problem under a cardinality constraint and demonstrated that this greedy algorithm can achieve an approximation ratio of (1 ) Subsequently, [35] showed that this (1 - "-pp)-pppoximaation guarantee is tight for monotone submodular maximization under reasonable complexity- -hhooretic assumptions. After that, [41] extended the greedy algorithm to the general matroid constraint. However, [41] also pointed out that under such a matroid constraint, the approximation ratio achievable by the greedy algorithm diminishes from (1 e - to 1/2. To achieve the tight (1 e - "-approximation under matroid constraint, then [15] proposed continuous greedy algorithm for submodular functions. A key innovation of this continuous greedy algorithm is novel continuous relaxxttior technique termed as the multi-linear extension. Furthermore, there has been extensive research dedicated to the non-monotone submodular maximization [12, 13, 19, 22, 24, 37, 52, 82, 87, 123]
A.2 Non-Submodular Maximization
Recently, numerous studies have found that there exist various real-world applications inducing utility functions that are close to submodular, but not strictly submodular. Examples include variable selection [30, 34], data summarization [46, 79, 113], neural network pruning [33, 104], target tracking [55, 56] and sparse optimal transport [77].
Weakly Submodular Maxinization. A important class of -usbmouuaa functions is known as 7-weakly submodular functions. Specifically, for a set function f 2" + R4, it is called y-weakly submodular if and only if, for any two subsets A S B S V, the following inequality holds: Σ.EBAA [(( A) 2 (J(B)= f(4)). The y-weakly submodular functions were originally introduced by the work [29]. Furthermore, when considering the simple cardinality constraint, [29] also show that the standard greedy algorithm can achieve an approximation ratio of (1 -e -->) for the maximization of a 7-weakly submodular function. Subsequently, [53] proved that, for any e > O, no polynomial-time algorithm can achieve (1 é ->pappooxiittiinn for the problem of maximizing a 7-weakly submodular function subject to a cardinality constraint. As for more complicated matroid constraints, [20] showed that the residual random greedy method of [14] can achieve an approximation ratio of [++7)² for the problem of maximizing a monotone y-weakly submodular functions. After that, [63] examined the approximation performance of the standard greedy algorithm on the 7-weakly submodular maximization problem over a matroid constraint, which indicated that the standard greedy algorithm only can offer an approximation ratio of U.4,² VFY+I
where r is the rank of the matroid. It important to note that this approximation ratio 0.4y /P+1 is not a constant guarantee and highly depends on the matroid rank In order to improve the approximation performance of these greedy-based algorithms over matroid constraints, [106] introduced the notion of upper submodularity ratio B and developed a more powerful distorted local-search algorithm for (7, we-kllyy submodular maximization problem. More importantly, this distorted local search
can guarantee a (B
8(1-7)+72 -aprroximation for the problem of maximizing monotone (7, B) --eellllly submodular functions subject to a matroid constraint. Note that, when the (7, B)- weakly submodular function is closer to being submodular, i.c., 7,3 + 1, the approximation ratio (1-- (P(1 (90-0+12) will approach the tight (1- 1/e). Conversely, when 7, 3 - 1, the approximation
ratio (I+7JT of the residual random greedy method [20] will trend to the sub-optimal 1/4.
Weakly DR-Submodular Maximization. The other important class of non-submo functions known a-weakly DR-submodular functions, where a is variously referred to the diminishing-
27

---

(DR) ratio [68], the generalized curvature [9] or the generic submodularity ratio [48]. The work of [63] is the first to explore the problem of maximizing a a-weakly Du-smbuod maximization subject to general matroid constraints and proved that the standard greedy algorithm achieves approximation ratios of a for the matroid-constrained a-weakly DR-submodular maximization. I+a Recently. [47] also showed that the continuous greedy combined with the contention resolution scheme [19] can obtain a sub-optimal approaximation ratio of
e e=)) for the problem of maximizing a monotone a-weakly DR-submodular functions subject to a matroid constraint. To achieve the tight (1 e apppoxxmmttionn guarantee, [76] presented a novel distorted lecal- method for the problem of maximizing a a-weakly DR-submodular maximization subject to al matroid constraint, which is motivated via the non-oblivious search [40, (4,,39,33) 38).
A.3 Multi-Agent Submodular Maximization
Multi-Agent Offline Submodular Maximization. Coordinating multiple agents to collaboratively maximize a submodular function is a critical task with numerous applications in machine learning, robot planning and control. A common solution for multi-agent submodular maximization problem heavily depends on the distributed implementation of the classic sequential greedy method [41], which can ensure (Tte) aapproximatioo [26] when the submodular function possesses a curvature of e E [0. 1]. However, this distributed greedy algorithm requires each agent to have full access to the decisions of all previous agents, thereby forming a complete directed communication graph. Subsequently, several studies [50, 45, 78] have investigated how the topology of the communication network affects the performance of the distributed greedy method. Particularly, [50] pointed out that the worst-case performance of the distributed greedy algorithm will deteriorate in proportion to the size of the largest independent group of agents in the communication graph. In order to overcome these challenges, various studies [94, 95, 32] utilized the multi-lined extension [15] to design algorithms for solving mutli-agent submodular maximization problem. Specifically, [32] proposed multi-agent variant of gradient ascent for mutli-agent submodular maximization problem and showed that this multi-agent variant of gradient ascent can attain 2 OPT over any connected communication graph where OPT is the optimal value. After that, to achieve the tight (1 - 1/e) -aaaappoxiimatoon [95] developed multi-agent variant of continuous greedy method [15,, 19]. However, this multi-agent continuous greedy [95] requires the exact knowledge of the multi-linear extension, which will lead to the exponential number of function evaluations. To tackle this drawback, [94] also proposed
stochastic variant of continuous greedy method [15, 19], which can enjoy ( (1-e ")PPT - c. Here, c is the curvature of the investigated submodular objectives.
According to the hardness result in centralized submodular maximization [105], the optimal achiev- able approximation guarantee for maximizing submodular function with curvature is (1 9).
However, as previously discussed, the state-of-the-art approximation guarantee for multi-agent offline submodular maximization problems is ( "), which highly mismatches the best possible guarantee f
of (1 - :) established in [105]. Thus, if Algorithm I we treat any incoming objective function ft. vt E [T] as fixed submodular set objective f. our Algorithm I can be naturally transformed into an approximation algorithm with the tight (1 - 9) guarantee for multi-agent offline submodular maximization problems. Similar to [126], we compare this offline version of our Algorithm I with existing algorithms for multi-agent offline submodular maximization problems in Table 2.
Multi-Agent Online Submodular Maximization. [115] is the first one to explore the multi-agent submodular maximization problems in time-varying environments. Moreover, [115] also proposed an online sequence greedy(OSG) algorithm for multi-agent online submodular maximization problems and proved this OSG algorithm can achieve a sub-optimal (T+c) Japprooiiiini over a complete communication graph, where is the joint curvature of the investigated submodular objectives. Concurrently, [114] extended this OSG algorithm into bandit settings. In order to improve this sub-optimal - >aapproximation guarantee and reduce the rigid requirement of fully connected communication network of OSG algorithm, [126] utilized the non-oblivious auxiliary functions presented in [122] to design two multi-agen variants of online gradient ascent algorithm, namely, MA-OSMA algorithm and MA-OSEA algorithm, for the multi-agen online submodular maximization problem. Furthermore, [126] also showed that these two MA-OSMA and MA-OSEA algorithms
can attain a regret bound of Ö( PrT against a (1 (I-e-") approximation to the best comparator in
28

---

Table 2: Comparison the different algorithms for multi-agent offfine submodular maximization problems. Note that 'Approx.' denotes the obtained approximation result, '#Com.' represents the number of communication, *#Querie'' denotes the number of queries to the set objective functions, 'Proj-fres Froj-ffree' indicates whether the method does not require projection, Para-free' indicates whether the method does not require the knowledge of curvature e, OPT denotes the optimal function value, d(G) is the diameter the graph G, T the spectral gap of the
weight matrix, K E and (G) 2 1 is the number of nodes in the largest independent set in graph G.
Method
Type
Para-free
Proj-free
Approx. JOPT
Graph(C) complete
#Com. (in)
#Queries
Reference
Greedy Method
det.
[26]
PGA
sto.
4OPT
connected
[32]
Greedy Method
det.
TTalcy 10PT
connected
((n)
O(Ka)
[50, 45]
CDCG
det.
(1 1)OPT -c
connected
(1-rle) [
[95]
Distributed-CG
sto.
(1 -0PTT-
connected
[94]
MA-OSMA
sto.
x
x
(re -OPPT--- connected
O [--mje
[126]
MA-OSEA sto.
x
(Le -PPT- connected
Kloog
[126]
Algorithm
sto.
x
(1 3OPT
connected
Theorem 4
hindsight, where Pr is the deviation of maximizer sequence, T is the spectral gap of the network and is the joint curvature of submodular objectives.
A.4 Multilinear Extension
As almost all state-of-the-ar algorithms for multi-agent submodular coordination [94, 95, 126] rely on the malti-linear extension of [15], thus, in this subsection, we review the concept of multi-lnnerr extension and compare it with our proposed policy-based continuous extension in Section 4.
At first, we define x _ that K = [V] such that we can re-define V _ [x] A (l....,k} ,K.. Then, we can show that Definition 3. For a set function f: f:2'
Ei= K4. Furthermore, from the definition of V in Section 2, we can know
+ .R,, we define its multi-linear extension as
G(x)= = Σ (F(A) II Ia II ((1-za)) ASV
EER* =ER>x (F(R)).
(6)
aEA
agAA
where (II,..., Ix) 10, 11th and R C V is random set that contains each element a E V independently with probability va and excludes it with probability 1 We write R ~ x to denote that R C a random set sampled according x.
With this multi-linear extension, we then can transfer the previous discrete subset selection problem (1) into a continuous maximization which aims at learning the optimal independent probability for each element a E V, that is,
max G(x), X E [0, 11th and Σ x. < SI.ViEN.
is important to note that, if we round any point x included into the constraint of problem (7) by the definition of multi-linear extension, namely, (6. there is certain probability that the resulting subset will violate the partition constraint of the subset selection problem (1). Therefore, for multi- lineer extension, we need to design specific rounding methods based the properties of the investigated set objective functions. However, current known lossless rounding schemes for multi- linear extension, such pipage rounding [1], swap rounding [18] and contention resolution [19], are heavily dependent on the submodular assumption. Currently, how to losslessly round the multi- linear extension of non-submodular set functions, e.g. (y, 3) --eelll submodular and o-weakly DRssubmodulaar functions, still remains an open question [106]. Conversely, our proposed policy- based continuous extension in Section 4 does not assign probabilities any subsets that are out of the partition constraint of problem (1), which means that, for any set function f 2 + R., and any given policy vector (T,, ... ,.,) E II.-, Ax,, we can, through the Definition 1, easily produce a subset that conforms to the constraint of problem (1) without any loss in terms of the expected function value F (T T.))
29

---

B Parameter-free Multi-Agent Policy Learning
It is important to note that, when considering the weakly submodular scenarios, the Line 9 of Algo- rithm 1 requires the prior knowledge of the unknown submodularity ratio (7, the diminishing- return(DR) ratio a to set the weight function w(z). However, in general, accurately computing these parameters will incur exponential computations. To overcome this drawback, in this section, explore how to design a parameter-free online a algorithm for the MA-OC problem with (7: -eeakly submodular or o-weakly DR-submodular objectives.
Note that, in part 4) of Theorem I, we establish a novel relationship between our proposed policy- based continuous extension F, and its original set function fi- More specifically, when the fc is monotone a-weakly DRssubmodular or (7, -W-eklly submodular, the weighted discrepancy between any (S) and its policy- policy-based bbsedd continuous extension (T It,) can be bounded by some sum of first-order derivatives, i.e., E(.m)).... ES B (T1,... ......... TT.). It is worth noting that the BF, (TI...... T.n) does not rely the knowledge of a, 7/ B. computation of this sum Σ (4.m))... 0T., Therefore, we naturally consider whether it possible to devise a parameter-free online algorithm for the MA-OC problem by controlling this aforementioned sum E(im)) 3..m 1 Taa) to narrow the gap between (T n.,)) and f()
OF
Ofs
Before that, [21, 88, 121, 133] utilized the idea of meta-actions [103] to devise Meta-Frank- Wolfe algorithm for online submodular maximization problems. The core of this Meta-Frank- Wolfe algorithm lies in iteratively optimizing
upper bound of the gap of the corresponding multi-linear extension G., i... (y. (x)) 2 Gy(y) - (x),, which is very similar to our previously discussed idea. Motivated by this finding, we then leverage the idea of meta-actions [103] and the insight from part 4) of Theorem 1 to design a parameter-free MA-MPL algorithm for the MA-OC problem with (7, By-eellly submodular a-weakly -R-submodular objectives, as shown in Algorithm 2.
Like the Algorithm 1, the core of our Algorithm 2 is primarily composed of three interleaved components, namely, Policy Update and Information Exchange (Lines 5-10), Actions Sampling(Lines 11-13), Surrogate Gradient Estimation(Lines 9-16) and Batch Gradient Estimation and Linear Oracles Update (Lines 14-21). Firstly, at every time step [T]. each agent E N employs K online linear oracles {Q( .....Q'' ......(()) (Kk to mimic the process of decentralized Meta-Frank-Wolle [81, 94] for maximizing our proposed policy-based continuous extension F,. Specifically, during every inner iteration i E [K], each agent pushes the i-th local policy vector Th,
(k- 1) along the direction (k-1) (M)) E AR, provided by the oracle Q²²², while maintaining other policies T..j .j # unchanged. Then, agent i exchanges the updated policy vector (1), yE (!) with the neighboring agent; j .V; and simultancously utilizes these received information to initialize the next policy (R)
(k) & max,eN,,44 (y (y (0), Ym E N, where y! (t) x (k=")) + R v (1) and
1 (2)
Tim i.e., π. ii.
im (((=")()) Vm # i. After completing all K iterations, each agent i normalizes the final (K) policy vector ni,; (1) to select an action at()) from V( Lines 1 11-13). Next, in Lines 14-20, each agent i uses a I.-batch stochastic estimation ahx) (1) to approximate the first-order partial derivatives (k)
y (1) A
of our proposed policy-based continuous extension F, at every policy vector (x..1 (t). ..... (k) (t)) and every coordinate Ti,m: Vm E [ks]. Finally, each agent feeds the obtained L-batch gradient estimation d (L) back to its corresponding linear oracle (,a²)
Note that in the process of Algorithm 2, each agent E N only needs evaluate the margin contributions of the actions within its own action set V/ Line 18).
It is important to highlight that, compared with the previous studies [21, 103, 126, 133], the innova- tions of our proposed MA MA-MPL algorithm are threefold: First, we utilize a policy- based continuous extension instead of the well-studied multi-linear extension to adjust the linear oracles in Lines 14-21. Second, rather than using a weight matrix to aggregate the received information, we employ the coordinate- wise maximization operation to update the policy vector(See Line 10). Third, to reduce communication complexity, we implement the batch gradient estimation in Lines 16-20.
Next, provide the theoretical analysis for the proposed Algorithm 2. Before that, we introduce some standard assumptions about the linear maximization oracles (**) Vi E N, [K], namely,
30

---

Algorithm 2: Ageti-Agent Meta-Policy Lcarning(MA-MPL)
Input: Time horizon T, action set V; (u:,1..... vi,,, }, Communication Graph G(N,E), number of online linear maximization oracles, namely, K and batch size // Policy Vector and Online Linear Oracles Initialization (Lines 1-2) Initialize policy vector (T (t).... Ti, (in(()) & O, VI E [7') for each agent i E NN;
2 Initialize K online linear oracles over AN., i.e., {Q (1) for i I...., do for each agent E N // Policy Update and Information Exchange (Lines 5-10) for k = .,
,!... (K)
for each agent i E E
K do
Set the shared vector y L.eh (1) A (1) for any + i and m eN;
(k) Ti,m
Obtain the update direction v (1) Ax; from oracle Q
Compute yi. 1.5 (t)
Ti,
(h- (t) K
(k)
(t);
Exchange the vector (y (k) (
(k) (t)
with the neighboring agent j Ni;
Set T. 2 maxjeNGuft (y (t)), Vm E:;
(k)
10
// Actions Sampling (Lines 11-13)
Compute the normalized policy pt(t) 2 n/. (t)/l (K) (f)l::
11
12
Utilize the normalized policy (t( to sample an action (1) from V;; Agent executes the sampled action at(;);
13
// Batch Gradient Estimation and Linear Oracles Update (Lines 14-21)
14
for k = 1,.... .....,,K do
Set the gradient estimation d (1) Ox,i
15
16
for I,... I,..., do
Utilize the policy T. (1) (t) to sample an action (,(t) E V; U (0) for any N:
17
Estimate the derivatives of Fú based on Theorem 1, i.e.,
OF. (1) (I.
(k) (1).... T.n (t)
Ii.m (t) A (1i.m Ujfi (a,(1)) Vm [sl]
(k)
ii.
19
Aggregate the gradient estimations
(0111 (t), Ii.n. (t)) as vector g; (k) (t); (t);
Update d (t) a (1) ig: (k)
20
Feed back the batch gradient estimation d (1) to the linear oracle (h))
21
Assumption 2. Each linear muximization oracle Q!aa) can achieve dynamic regret of O(v where Vr the variation of any feasible path (u....., ur) <IT ARp that to say, Vi 2
Et u, u.-1ll2for any path (ui...., wr) II
Remark 9. It is worth noting that there exist several effective and efficient algorithms that can achieve a regret bound of O(vVTT) for online linear maximization problem, for instance, online Frank Wolfe [110] and online gradient ascent [116, 127, 134].
Theorem (Proof provided in Appendix H). Under Assumption when the communication graph G(N,8) E) is connected and each set function ft is monotone a-weakly DR-submodular or B)- weakly submodular, if we set L = (TT) and K = O(VT), proposed MA MA-MPL algorithm can achieve a dynamic p-regret bound of O (d) (PrT), that is, E (R)(T)) < (d VPrT), respectively.
(21 (1201-e- -L0---001--0
-(80-))+~))
where p = or
8(-7))1"
Remark 10. Note that, in Theorem 5, d(G) represents the diameter of graph G(N,8) fiee, the length of the shortest path between the most distanced nodes. Moreover, Pr 2 Σx |A7A MAAA is the deviation of maximizer sequence and A denotes the symmetric difference.
31

---

C Additional Experimental Details and Results
In this section, we test the effectiveness of our proposed Algorithm 1 and Algorithm in two different multi-target tracking scenarios.
C.1 Target Tracking with Facility-Location Objective Functions
In line with the prior studies [115, 126), consider 2-dimensional plane where 20 agents deployed to track 30 moving targets over duration of 25 seconds, subdivided into T - 1250 discrete iterations, At every iteration, agents must determine their movement direction from "up". "down", "left", "right", or "diagonally". Simultaneously, agents also need to adjust their speeds from a predefined set of 5, 10, or 15 units/s. As for targets, we categorize them into three different types: the unpredictable 'Random' and the structured 'Polyline' as well the challenging 'Adversarial'. More specifically, at every iteration, 'Random' target will change its movement angle @ randomly from [0, 2n] and steers at a random speed between units/s and 10 units/s. In contrast, the 'Poly- line" target will maintain its trajectory and only behaves like the 'Random' target at the specific {0. 1. 2 T'] ..., (h 1)L [ 1]thh iteration where is the predefined total iterations and A: is a random number from (1, 2, 4). Regarding the 'Adversarial' target, it mimics the 'Random' targets when all agents are beyond a 20 units. Nevertheless, upon detecting an agent within the 20-unit range, the 'Adversarial' target will evade at speed of 15 units/s for one second, pointing to the direction that maximizes the average distance of all agents.
Generally speaking, every motion of any agent can be characterized by three key parameters, namely, its movement angle 0, speed s and the unique identifier i. With all these three parameters, then the action set V; available to each agent i E [20] can be mathematically represented as:
3
Vi = [(0, ((0,,,)): E (5, 10, 15)units/s, 0 E { 4 T 2n }. Vi [20),
where each tuple (6, s.i) encodes a specific action of agent i, that is, it will move at a speed of s in the direction of 0. Furthermore, each time step / E [T], we denote the location of each target j E [30] as (t). Similarly, we also utilize the symbol ((... (4) to represent the new position of agent after moving from its previous location at time (t - 1) with a movement angle and speed s.
To enhance the tracking quality, common strategy is to minimize the distances between agents and targets. Inspired by this idea, many studies [27, 114, 115, 126] naturally consider the following facility-location objective function for agents at every iteration E [7), that is,
30
f((S)
max
(0...))SS (lo(0,..)) (1) 0,(())2
where [|((_,..s (t) (1)ll2 represents the Euclidean distance between the location oz of target j and the new position (00,..s) (t) after agent executing the action (0, s) and is a subset of the ground action set V A V. It is important to note that the larger the value of 1000,..::000 becomes, the closer the action (8, s, :) drives agent to the target j.
Considering this facility-location utility set function fe and the truth that each agent only can execute one decision from V; every time 1. E (T), then we can easily transform the aforementioned multi-target tracking problem as multi-agent online coordination(MAAOOC) problem introduced in
Section 2. Particularly, at each time t E [T]. we need to tackle the following facility-location utility set function maximization problem in multi-agent manner, namely,
max f((), s.t. S V and [S = 1, Vi A.
(8)
Furthermore, numerous studies 191, 115, 126] have verified that this facility-location objective function fo is monotone submodular. As result, the problem (8) can be equivalently reformulated as the problem (1) in Section 2, i.e..
max f((S), s.t. S C and |Sn Vo S 1.ViE.
32

---

100
CRS Mocent
80
Average Distinnc
Average Number
Averuye Unitty
0.8
60-
0.6
8
40
MAROMA
20
0.2
MARK
MAMM
200
400
600
1200
200
400
1000
1200
400
600
800
1000 1200
Time
Time
Time Step
(a) Average Utility
(b) Average Distance
(c) Average Number
Figure 2: Comparison of the running average utility and the runing average number of targets within unit well as the running average distance of Top-5 nearest targets of OSG, MA-OSMA, MA-OSEA, MA-OSEA with our proposed MA-SPL and MA-MPL algorithms on the multi-target tracking scenario with 'Random's :' 'Adversarial': "Polyline=
100
0.8
C9)
14
Averape Usitty
60
Average Distunce
Average Numberr
60-
0.5
0.4
40-
20
0.2
0.1
200
Time 1000 1200
200
400
1000
1200
600 800
Time
Time
(a) Average Utility
(b) Average Distance
(c) Average Number
Figure 3: Comparison of the running average utility and the runing average number of targets within unit well as the running average distance of Top-5 nearest targets of OSG, MA-OSMA, MA-OSEA, MA-OSEA with our proposed MA-SPL and MA-MPL algorithms on the multi-target tracking scenario with 'Random's 'Adversarial': 6:::1.. =:::1.
12
Distange
1.2
10
Average Liility
80
1.0
0.8
Average
Mc-00M
0
600 800 1000
400
600
800 Step
1000
1000 1200
Time Step
Time Step
(a) Average Utility
(b) Average Distance
(c) Average Number
Figure 4: Comparison of the running average utility and the runing average number of targets within unit well as the running average distance of Top-5 nearest targets of OSG, MA-OSMA, MA-OSEA, MA-OSEA with our proposed MA-SPL and MA-MPL algorithms on the multi-target tracking scenario with 'Random's 'Avversarial' 4::551.
=4:5:1.
In simulations, we initialize the starting positions of all agents and targets randomly within 20- unit radius circle centered at the origin. Furthermore, we consider different proportions of 'Ran- dom', 'Polyline', and 'Adversarial" targets. Specifically, we the proportions of targets as 'Random's : : =8:1:1 in Figure 2 and 6:3:1 in Figure 3 as well as 4:5:1 in Figure 4. Like [126], we also use the suffixes to represent two different choices for communication graphs, where 'c" stands for a complete graph and 'r' denotes an Erdos-Remy random graph with average degree 4. According to the results in Figure 2(a), Figure 3(a) and Figure 4(a), we can find that the average utility of our proposed MA-SPL algorithm can significantly exceed the otate-of-thheart MA-OSMA and MA-OSEA algorithms in [126], which consistent with our Theorem 4, that is to say, our proposed MA-SPI algorithm achieve tight (1 appproximatio guarantec
33

---

for submodular objectives, while the MA-OSMA and MA-OSEA in [126] only can guarantee a sub-optimal ( )-approximation. Like [126], in Figure 2(b), Figure 3(b) and Figure 4(b), also compare the average distance from agents to their closest five targets of our proposed MA-SPP and MA-MPL algorithms against OSG [115], MA-OSMA and MA-OSEA algorithms. Similarly, we observe that our proposed MA MA-SPL can effectively reduce the average distance between agents and targets. Furthermore, from Figure 2(c). Figure 3(c), and Figure 4(c), we also can infer that, compared with OSG, MA-OSMA, and MA-OSEA algorithms, our proposed MA-SPL can make more targets gather within 1 unit of agents. It is worth noting that as the proportion of 'Adversarial' targets increases, both the maximum runing average utility and the maximum running average number of targets within unit exhibit downward trend.
C.2 Target Tracking under Extended Kalman-Filter Framework
In previous Appendix C.I, we considered a simplified multi-target tracking model, that is, we assume that the monitoring quality of each moving target j only depends on its nearest agent. However, in many real-world scenarios, due to agents' different sensing capabilities and varying observation angles, relying solely on the information collected by the nearest agent for accurately tracking the state of each target is unrealistic. Instead, we generally need to aggregate the data from multiple agents to comprehensively reconstruct the targets' behaviors.
Recently, in order to obtain an accurate estimation of every target's 's location, [55, 56] employed -ilkte(EKK)) framework to process the observations of multiple distinct agents. Specifically, let us consider a target tracking task using a swarm of agents(UAVs)) equipped with GPS and radar systems. In this scenario, at each time / [7], each agent can measure the range to each target j throughout its radar system and also can obtain its own position information from GPS. Furthermore, like the work [55], we also assume that the range measurements of the radar systems follow a quadratic model, namely,
an extend
((0,a.))~> (t) = (0....)) ot,() ((0)),)),;(t,,
(9)
where the symbol r(0.a.i) -ij (t) denotes the range measurement of agent i to target after agent i executes the action (0, 8, i), (1) is the location of target j. ((e,s.))+5(()) (4) is the additive independent noise and the symbol 000.s.i) (t) represents the new position of agent after moving from its previous location at time t 1 with a movement angle and speed s.
Note that when the new position at (t) and the range measurement ((0,s.))+, are known, we can view Equation (9) random quadratic experiment of the unknown location (1). In other words, different action (0, s, i) can lead to distinct random quadratic observation of the unknown parameter (t). Inspired by this perspective, we can formulated the action selection problem in multi-target tracking task as an experimental design problem, which aims at selecting a feasible subset from the
whole collection of experiments (T(0,-.))>> (t) = 2 [llo (t)- -o (t)
+(00,..0) (0, s, e V}
such that the measurements of these selected sub-experiments can accurately estimate the location of every target. Particularly, under the classical Van Trees' inequality [108), the work [55] established lower bound for the covariance matrix associated with the EKF estimator of the location oj (l).
Specifically, at time step / E [T]. if we consider the sub-experiment S C V, then the lower-bound matrix B3 (t) in the Van Trees' inequality for the EKF estimate of the unknown location 0, (t) can be expressed as (Please refer to Theorem 2 in [55]):
(t(+) = (I Σ
1
P + Z10,a,)) -o0e)));5(00000)) + +1((() ,
(10)
(0,,,)) (0. (t)
where -() - (00,..) (t-) o, - ( (t) & Var (E(0...)))((t))
Cov (0,(1) 01 1)) and (1) is the Fisher information matrix associated with the normal- ized random gap (o)(t) (t (t-1 1) TE (o)(t) - (t- 1))) Note that in Equation (10), the tuple (0, s, i) represents not only selected action but also an observation experiment.
With this lower-bound covariance matrix (1), we then can utilize various so-called alphabetical criteria [16, 17] to design utility function for selecting a superior action set such that the resulting
34

---

0.464
0.462
0.464
0.463
0.462
Average Unility
6.482
Arerage Utility
8,42
0,451
Average
6.463
00.450
8.46
0468
14 00111
0.458
0.458
300
200
400
500
1.00
200
300
460
500
100
750
300
400
500
T Time Step
Time Step
Time Step
(a) Average Utility
(h) Complete Graph
(c) Sirdos-Renys Graph
Figure 5: In Figure 5(a), we compare the running average utility of our proposed MA-SPL and MA-MPL algorithms with that of the 'RANDOM" baseline in a multi-target tracking simulation with A-optimal objective functions. In 'RANDOM' baseline, each agent randomly selects an action from its own action set V; at every iteration. As for Figure 5(b) and Figure 5(c), we illustrate the impact of different DR ratios a E {0.1, 0.2, ... 1} on MA-SPL algorithm. Particularly in Figure 5(b), we considers complete communication graph among agents, whereas we employs an Erdos-Renyi graph with an average degree of Figure 5(c). Note that Figure 5(a) only shows the results for the best scenario (a = 0.1) and the worst-case scenario (a for our proposed MA-SPL algorithm.
EKF estimation can accurately approximate the location of each target. One commonly used strategy is to employ the A-optimality, i.e., consider minimizing the trace of the lower-bound covariance matrix (t) equivalently maximize:
30
J+(S) = > (T Tr B (0)
(11)
where "Tr" is the trace of matrix and also consider 30 moving targets in simulation.
Thus, under the A-optimality criterion, we can model the agents' action selection task as a special instance of the multi-agent online coordination problem with the set objective function fr defined in Equation (11). Furthermore, according to recent studies [53, 55, 106), we can show that the utility function fo in Equation (11) is monotone a-weakly DR-submodular and (r, -3--walllyy submodular (See Thcorem 6 in [55] and Theorem C.2 in [106]).
In our simulations, to simplify the computation of the lower-bound matrix (t), we model the movement of each target as two-dimensional Brownian motion. Specifically, we set 0,(1) & (t - 1) + 0.02 (02, I2) where I2 is the 2-dimensional identity matrix. Moreover, we assume that the noise f) follows an independent normal distribution, i.c., E(0,s.,)~>j ~ (0, 0.01). As for agents, every iteration t [T), we adjust their speeds from a set of 7, or 12 units/s and simultaneously change their movement directions from "up". "down", "left", "right", " or "diagonally". As result, the action set V; available to each agent i [20] can be mathematically formulated as:
3x T., , 2m Vi [20].
Vi- {(0, s, i): E (2, unittss 0 E
4 4'2
where 9 denotes the movement angle, is the speed and represents the unique identifier.
Given the unknown diminishing--rturr(DDD
ratio a of our investigated set function ft, we test 10 for our proposed MA-SPL and then present the results
different configurations from a = 0.1 in Figure 5(b) and Figure 5(c). Particularly in Figure 5(b), we considers a complete communication graph among agents, whereas we employs an Erdos-Renyi graph with an average degree of 4 in Figure 5(c). Subsequently, we compare the results of the best-case scenario (a 0.1) and the worst-case scenario (a = 1) of our proposed MA-SPL algorithm with the parameter-free MA-MPL algorithm and 'RANDOM' baseline in Figure 5(a). According to the curves in Figure 5(a), we can find that the running average utility of our proposed MA-MPL and MA-SPL algorithms can significantly exceed the baseline 'RANDOM' algorithm, which is in accord with our Theorem 4 and Theorem 5. Moreover, we also find that the purameter-free MA-MPL algorithm can effectively outperform the MA-SPL algorithm associated with 0. O.1-network search. is worth noting that no previous works explore the MA-OC problem with weakly submodular objectives. Thus, we adopt the 'RANDOM' algorithm as baseline in Figure 5(a). In 'RANDOM', each agent i randomly selects action from
35

---

its own action set V. Like the previous Appendix C.I, we also use the suffixes to represent two different choices for communication graphs Figure 5(a), where 'c' stands for a complete graph and "r' denotes an Erdos-Renyi random graph with average degree 4.
C.3 More Details on Experimental Setups
This subsection discusses some additional details about our experiments.
At first, we describe the parameter configurations about our proposed 'MA-SPL', 'MA-MPL', 'MA- OSMA' and 'MA-OSEA'. Specifically, we make the following setups:
In MM-SPL', namely, the Algorithm 1, we set the step size 1/: = VT and employ a 10 batch of stochastic estimation to approximate the surrogate gradient of our proposed policy-based continuous extension in Section 5.1. As for the projection in Line 19 of Algorithm utilize the CVX optimization solver [49].
In 'MA-MPL', namely, the Algorithm of Appendix B, we set the batch size I, 10 and the number of oracles K 15. As for the online linear maximization oracle, we utilize the online gradient ascent algorithm [116, 134] with step size = O (TT
In 'MA-OSMA', namely Algorithm 1 of [126], we consider the Euclidean distance with |x||
1 and implement a 10 batch stochastic estimation o(x) = 2 set the step size ÿ) = /T
to approximate the surrogate gradient of multi-linear extension. Similarly, we also use the CVX solver for projection operations.
In 'MA-OSEA', namely Algorithm 2 of [126), we also set the step size T) J and consider the mixing parameter y = 1/71-5,
As for the communication graph G, we consider two different setups:
Complete graph' where we set the weight wij = A. Vi,j E [n] where n = [W| is the number of agents.
'Erdos-Reyyi random graph with average degree 4 where if the edge (i,j) is an edge of the graph, we set Way A 1/(1 + max(d,, d,)) where d, is the degree of agent i E N and when (i,j) is not an edge of the graph and * j. we consider Way = 0. Finally, we set Wii 1 EjEN; Wij where Ns is the neighboring nodes of agent i.
Furthermore, for curves related to MA-SPL, MA-MPL, MA-OSMA, MA-OSEA and OSG, we repeat these algorithms five runs and then report the average result. Note that, in Figure 2(a), Figure 3(a), Figure 4(a) and Figure 5(a), the running average utility at any time t is defined as [Enelq (((()e)))(a((()))) where (;(tz) is the action chosen by agent E [n] at time f1.
D Proof of Theorem 1
In this section, we prove the Theorem 1.
1): From Definition 1, we have that
OF,
(TI,.... , ,T))
2 (IT= p(ay(t)))))
Σ
( (a,))
(12)
a,EV)U(O)
(F((U))) {ayt) Op(as(ms)
Σ
II
p(ay(Tz)).
a,EV,U(O)NNEEN
j7ijEN
Note that p(u m (T)) Tim, Vi E [n], Vm
[Ry] and ((0(TT))) 1- Em= Tim. Vi N. Therefore,
I-
we have Opla. = 1 when Gj = Vi mm.
-1 when a, = and @p(a.(m.) = 0 when 0m..
8x mm
36

---

a, & {us, 0}. Then, according to (q.( we can get the following equality:
OFt
nn))
im.m
Op(a, (T)
E
U5 {ast)
II p(a)1T,))
@timm
jFJJNN
Σ
Σ (fe(Uzz {aj})
pp(ail
Il p(a, play)
(0)))
OLeV,
J#LJEN
Σ
- (A (a,)))
II jRijEN
p(as/T)) (T,)
0 (.E
E
fe UJAIJEN {a₂t)
II p(azla,)
(yEV
jdijEN
UffiseN Bujaa,NjEN UpfAeen (a;1)),
(13)
where aj ~ n, indicates that action ay is randomly selected from V; U (0} based on the policy πzz- O such that 0. In other words, for any (TI...., nnn) II Ax., we have IV
2): When Se is monotone, we can know that fe(vi,m| UsAiJEN {a²})
DE (TI,..... Rn)
Bm..
VF,
nnn o, namely, for any two point (Ti...., TH) E I Drs and (πf (.f...., .., x²,) S F((TT) .....,..... Th) ). So monotone. 3): For any fixed policy vector (zf, (zi,...,,,, x.)) II==1 Ax, and (zf, n IT Ac, where T I n Vi E N,, we consider unified sampling strategy generate actions. Before that, set each n. (Λ .......... Th..) and xτ. (T), (......... .............. TL.;;)
IT AR,, n. S π. for any E A, we have
Vi W. At first, transfer the sampling process according to policy πe to uniform random variable X; [0, 1), namely,
01,1 If X; (0,
m2-1
m for any integer m [2, kg]
If X2
a( a(Xi,
(14)
Ki
( If X,
When X, is an uniform random variable over range [0, 1]. easy check that the a(X,, nT) follows the same law as the policy n. that is, Pr(a(X;, n = v..)) m. and Pr(a(X,, n.)
0) =1 1- -1-E Em= Ti where the symbol 'Pr' denotes the probability.
Similarly, also transfer the sampling process according to policy πι to two independent uniform random variables X,, Y E 10, namely,
Ri
a(X,, x()
If If
b
T2
U1.1 If X
1ikk and Y [0,
> k= Tr
a(X,, Y, R x
Ki
mm
k= (T)) K T(.
Em (3T) -T(
Ui.m
If X; >
Ki and
Y
), J,ym E (2, ma]
k= T
k= T
K4
Ki
9
If X
The and V
Σ
(#l T((k))
(15)
37

---

From part 1) and fixed a sequence of independent uniform variables X,, Y, VA E N, we can have that ( .......... Ex, (fe( UjFiJeN (a(X,,,,)))
aF,
itim
and
0F, (T Tht) (x) (fi ((((u,m)
USALJN fa(X, Y,, x. NY x())))
From Eq.(14) and (15) we can know that {a(X(, & fa(X Y, u; π;)} such that () } C UUHiseN(a(X; Y,, nf, T.). Then, from the definition of a-DR submod- ularity, we have that fa (v.mm UjtiJeN (a(X,, xT)}) 2 afr (vi,m UjAieNN {a(X;, TH x))). so (T ) 2 (TT )
4): For any subset S within the constraint of problem (1) and any point (mı,..., Tt,)) E II A... when ft is monotone (r, ---ekllyy monotone submodular, we firstly can show that for any two actions d1, d2 E V and the subset B S V, we have that
(fe(ar]B B (a2)) fe(02) B)) (F+(BBBB)))))) (a1, (a1, (2)) - S(B)) St(as B) fe(a2 B),
such that
fr(a B) 2 7fr(a) B faat) - -1- (o2
(16)
Therefore, we can show that
OF,
Σ
[1 (I.....,TT nnp))
(m.m).vm ES
Σ
EayNR,NYsEN (fe (va.ml Usfi.jeN (az1))
(17)
Σ
EajaR (T UjeN {az}) - (11-7). (1- UjfiJeN (a,))):
(6,m)..... ES
where the first equality follows from part 1) of Theorem and the second inequality comes from the (16). Then, from the w-weakly submodularity,
Σ (8
Bajway NJJAN (fe (Us.ml USEN (azl))
2 TBayyz ( USE {az}))
USEN
(18)
2 2 (f(()) 21(1((5)
where the final inequality follows from the monotonicity.
Furthermore, from the 9-weakly upper submodularity.we also have,
Σ
ViEN (Fe (as UsFiseN (aj)))
(i ES
Σ MajnR [f((a)) UjAiJeN {a,}))
(19)
iEN
< Mayyaa NjeN Je UjEN (az3) f((0))
(T. nn):
where the second inequality follows from the definition of 8-upper submodularity. Merging (1.( and (18) into Eq.(17), we have that
OF.
Σ
Faim (TI..... n.,)
(6.m):t..me ES
Σ Eu (7fi (1s.ml USEN (az)) (1 (1-7)ff U fo,t))
m
2 (n2 (72 (f((S) Fo( .nm) - -(1-2))F((M
= =>2{((S)- - ((1 -7,8 +22) F.,
38

---

As for ft is monotone a-weakly DR-submodular, we also can show that
OF.
Σ
(T....., Tt.) Ea Bayaa,
Σ
fc fr(vi.m UJALSEN faz))
(f.m): ES
(L,m)).i, ES
2 My ( (S) USW (sEN)
a (f((S) (T nT));
where the first inequality follows from the a-DR submodularity and the final inequality comes from the monotonicity of ft-
E Proof of Theorem 2
In this section, we verify the Theorem
Before that, we firstly suppose that the symbol 1, represents the indicator function over the subset S V, namely, for any action ti.m E S, the vector 1s sets the corresponding probability for this action 2m 1. Note that, when S satisfies the constraints of problem (1), namely, |S n Vil s 1, we can infer that 1s E II Ax..
E.1 Proof of Part 2) and Part in Theorem 2
With the previously defined symbol 1s, we can rewrite the 4) of Theorem 1 as: i): when Sa is monotone a-weakly DR-submodular, the following inequality holds:
a (f((S)- Fi(TI,... ...).. S (1s, (T T,)));
ii): when ft is monotone (7, (o.f8))-ekkk) submodular, we can show that
(7* f( - " S (1s, VE, Rn)))
In order prove Theorem 2, next show the relationship between ((TI,-.. nn), (T. ..., n.,)) and Ft (TI,,...., T..). From (13), if (Ti, (Ti, , Tin,)) Vi E N, we can show
(TI,,.... nm), ( ,.,))
OF, msm Drcm
(T....., nen)
Tim Eay KJEN (fe(rium UjAiSeN (aj3))
II p(as)Ts) ) jtiJEN
Σ
M((rim| UJALSEN {aj})
Tim
p(uimm)
Σ
[ UjFiseN (azt)
II p(azl1z))
(20)
Σ
felcmm USLWEN (a.))p((u.mlm))
II
(Ta))
m=l
jfijeN
(f((a)) UpFISEN {azt) II
Σ
p(a5)1z))
i= REVZ((()
(1)
JEN
Eag~s,
(Fe(as) (anJee((a;)))
39

---

where the second equality follows from the 1) of Theorem 1, the third equality comes from the final equality of the Eq.(13), the fourth equality follows from p(u Tt)) F2,m and the final equality from the fact that the random element 0; is drawn from the policy T₁.-
Therefore, if the original set function fe is 3-weakly submodular from above, show that
(TT1.... n. (TI
Bay Baya,, NJEN Se(asl UjFiSEN (a=1))
Σ
Je(as) UjtiJeN {az})
(21)
1=1
S BBa MEEN ( fr(0))
= (T). T.,)
Therefore, by merging (21( and the 4) of Theorem 1, when the set function f. is monotone and (2, -)wekllly submodular, for any subset S within the constraint problem (1) and (TI....; ,T)) E
1==1 map we have that
(1g [m1,- J, VF n.,)) 2 f2 - (3 + 3(1 - + (T) n.)
Similarly, from the definition of a-weakly DR-submodular function, we know that a-weakly DR- submodular function automatically satisfies the conditions for being -wweakly submodular from above, we also have that, when Je is monotone a-weakly DR-submodular,
1 F nny.
(1s (TI...... n.). VF . n.,)) 2 af((S) (a
a
Therefore, when (Ti..... ( nt,) is stationary point of F; over the domain I[ Ax.. we have i): fe is monotone (7, 3--wellly submodular, for any S within the constraint of problem (1), fe() (3 + {( 7) 2) FTi TF, & (1s - (xi n, F -,,)) - In other words,
x2
Ft ,T,,, 3 3(1 - 7) + f((5)))
where S* is the optimal subset of problem (1).
We get the 3) in Theorem 2.
Similarly, ii): when fü is monotone a-weakly DR-submodular, for any S within the constraint of problem (1),
af((S) - (a 1 P x S (1s - (ni,..., "i.,..,,,,,,.. ( ..,,,) s 0.
In other words,
F(
+ a f((S).
where S* optimal subset of problem (1). We get the 2) in Theorem 2.
E.2 Proof of Part 1) in Theorem 2
In this subsection, prove the part 1) in Theorem 2. From (17), we have
(1s, (F, T.m)) =
Σ
WieN (Ie(ve. UstiseN (az1)).
ms
40

---

From (20), we have
n
((T) (I......, T.)), (T,(TI,..... Ttn))
Boy ny ViEN (f((a)) UjfiJeN (ai))).
Therefore, we have that
{1s (II, , Tn), V (TI, .., ,.,))
Σ BagnRyNNJEN (fe( (1am UJLLJEN (ast)) - Σ (aayaa,ivsss (f((a)) USHWEN (a;1))
2m
n
=Baj-Ey,VjeN
Σ
f1 UjAiJeN fa,t) Σ (a Upassen(a;]]
(L.m)as,, ES
fe UJFIJEN {a₂))
E
ft(a UjfiSeN faz)))
Ri, E(S)U)ENTa))
(22)
When fa is monotone submodular, have
Σ fe UUAiseN {aj}) 2 UUJEN (a))) fi(UseNlos)). (23)
Furthermore, from the definition of curvature we also have
fe (UJEN U)) where this inequality follows from (UJeN {a,)) \s= (User (azl)) (VIeN Similarly, from the submodularity, we have
(24)
Σ f((a,) USALJEN {a₂)) < (((ee))))))) (25)
((((UEEN)
where the inequality comes from that (UJeN {az} nS) c (UzzsseN (az)) if EuenN(a;)) (S. Merging (24) and (25) into (22), can show that
(1s (T), nn) VI,TTI,.... Tn.))
Bag YjEN
Σ
UjtiJe {az})-
E
fe(a: UjfiseN (as)))
aEUseNtass]s
f((S) fa fa(UjeN - -(f(ieelo)) ((Uxx((t)))))
2 VieN
VieN (I((S) - (1 c){((jee((a)))
= f((S) - (1 FT
Thus, if (II nT is stationary point of F; over the domain IT=h = Ax., when f is monotone submodular with curvature c, we have, for any S in the constraint of problem (1), we have
fa(S) - (1 + (T .......,,,, x;) & (1s (ri ......,,))))
$ 0.
So.
F. ... ,,,,))
+ (((S),
where S" is the optimal subset of problem (1).
41

---

E.3 A Policy-based Continuous Extension with 1/2-Approximation Stationary Point
In this subsection we consider a special set function.
At first, let the universe set U consist of n elements -n and n A elements :ii...---n-x]] all weight 1, and n elements (c1...., .n-1) of arbitrarily small weight > Then, we define two different types of sets namely, A, and Aitn for any i E [n]. that is to say,
A - (G) for S sisn
A, - {1 ....... Fn 11
Ants - {aa) for 1 sissn n- 1,
Azn {g) ........ kn-k).
After that, we define coverage set function f 2 7 R+ over these 2n distinct set {A Anti........ A where V [2n]. Specifically.for any subset S V.
f(S) Σ w(v),
(26)
vEUtcs A.
where w()) is the weight of clement c.
Moreover, we consider a partition constraint that contains at most one of {A; Anti) for any i E [n]. If we set V; fi, + n} and V & Useim] Vi - [2n], we naturally obtain the following coverage maximization problem:
max f(S) s.t. S V. < vi [n]. SCV V
(27)
Note that this problem (27) special case of the concern problem (1). From the result of [38]. we know that the coverage function ʃ in Equation (26) is submodular set function, namely,
= =-=-1
A key feature of the coverage maximization problem (27) is that [38] found that the standard greedy [85] will be stuck at a local maximum subset {AI...., An where [n] and f(S)
(I+e)n. In contrast, when e is very small, the optimal subset for the problem (27) is (An+1..... A2n (1+c)n
where S (n ..... ,n1 and ((S) 2n k Note that lima- lim k-0 2
Motivated by this finding of [38], we also can show that the point [n] A (1,..., 0. 0) is
local stationary point of the policy-based continuous extension of the set function Equation (26). More specifically, we have the following theorem:
Theorem 6. The point [m] is stationary point of the policy-based continuous extension F of the set function f in Equation (26). Moreover,
show M(a+1....223]
F(1pa)
2n-k-T
(1++)m
2.2
Remark 11. This theorem indicates that when the objective set function is submodular, namely, c=a = = 1, the approximation guarantees established in Theorem 2 tight.
Proof. first, for any i [n], we assume π, = (TT,, TT22). Then, according to Definition we have that the pasicy-based continuous extension F of the set function f in Equation (26) can be formulated as:
Σ (f(U (a+)) II(a(T)))
F( nn.
(28)
(.)
where p(i(T,)) = T4.. p(n + i|Tt,) = T2. and p(0/Tt,) = Te.1 T1.2
From part 1) of Theorem also show that,
aF (1 (1])) = for sisn 1
0F
(1(m)) = nt 1,
0m:
0Tn,11
aF
OF
0n (1 [x) = for <is n
0n (1(m)) = nt
42

---

As result, for any (TI..... nT)) E IT== A2, we have
(TT) nn) [m]. (F (m)))
OF (1 + πं. Tm,
OF
OF
112 0
(1(m))
Σ
0Tg,1 (1mz)
OF
OF
11,1 0T.,,1
(1 + 12.2 0m,
(1(mi) - (1 + t) 1)
11,1 + (n 1) (n kn (1 + c) 1)
T1,1 + (n (),, + Tn,2) ((n (n 1)) (1+ +) 1)
[1,1 1) + ((n- - - (nn-nn111)))) 1)) T
(n 1)(1 Fn,1 -
T1,1 - 1) + k)Ta,2 - (n 1)(1 - Nn.1 TT,2) S O,
where the final inequality follows from - 1: < 0 and 1 - nn.1 nn.2 2 0. As a result, from Definition 2, we can know that the point 1|x] is stationary point of the policy- based continuous extension F. Note that F(1())) = f((n)) (1 c) 1) such that F(]mm))
(1+c)n
[(fn+1....nn) 2n-k-1
(1teln Particularly when k - 0, - 0 and n + co, J(++1......))) 2n- + 2.
f(1m)
F Proof of Theorem? 3
In this section, we cut the proof of Theorem 3 in two distinct subsections. Specifically, Appendix F.1
provides the proof for parts 1) and 2), while Appendix F.2 addresses the part 3).
F11 Proof of Part 1) and Part 2) Theorem 3
Before verifying the parts 1) and 2), firstly prove the following theorem:
Theorem 7. Given monotone set function ft. its policy-based continuous extension F, introduced in Definition 1, if we consider a surrogate function Fi : -II=1 As; + IR,, whose gradient at each point x E I[ An. is weighted average of the gradient V * x). namely, FF((x) 2 So V(2)VF((z d) where w(z) a positive function over [0, 1), we have that:
i): When a-weakly DR-submodular and w(2) c=(=-1), for any policy vector (TI...., nn,) I Ar, and any subset S within the constraint of problem (1), then the following inequality holds:
1s (TI .......TA. T.n), (T. .nm)
1s - (TI....., Tnn, ( cala-1i (z (TI....,,TT)) dz
(29)
2 - -- f((S)
ii: When ft is (7, -W-wllyyy submodular and w(2) = 1x1-1) where 6(7, 3(1-)) for any policy vector (II,...., TT,) I An, and any subset S within the constraint problem (1).
-3) +2
43

---

then the following inequality holds:
1s (Tg, ... nn), .T,,..., n.n))
1s (TI, Tnn) ( (2 ( dz
(30)
(2 - e [e(S)- FI(TI..... Ta)
( (3)
Proof. For i): At first, we verify the following relationship:
(T), (TI...., Nnl, (
(2 (T1. (TI,.... nn)) de
ca(2-1) 11 (TI..... n,), Vi (= * (TI,.... stm)) dz
[' a(2-11 dl's (z (TI,.... [mn d=
dz
ca d (z [T.....,
(z=11) Fr (z * (Z)..... nn)) 12=00 - ( Pe (= (Ti,..., an)) (e)(--1)
= F. ..... nnn ( ca(z-1) Fr (z (II....,,T)) dz,
where the final equality follows from F,(0) 0. Then, we have the following inequality:
1s,
ca(s-1) (0(s-1)FF (2* (T1. n.)))
ca(z-1)
1s, VF (= * (T..... n.)) dz
(a(=-1) (J((S) - P.(3 (II....., F.)) dz
2 a
j0
co(z-1)d) fi(s) S ca(x-1) Fr (2 (TI...., nmn)) dz
@ 00
(1- fi(5) f cal=-1) (z (T...... Th dz,
where the first inequality follows from the part of Theorem 1. As result, we have
1s (TI.... An): I' cal=-1) (z (TI,.... .T.)). 2 (1 (1-- ((()) T.,))
As for ii): Similarly, when fe is monotone (7, we-kklly submodular and w(()) = c((x,))(=-1) where o(7,8) 8(1 7) + 2 we have
44

---

11 (I....., [.)) (0(%,0)=-11 (T
(T....., (T,))...,TT)))))) dz
L (062,991-111d (= (TI....,
=001)19)3-11 (z (T) (Z),.... Tn)) 1=t ((7, (' e (z (TI....,, ktn)) dz
(m) -1) /-" (062,9)(=11) Fr (= (TI,..., ;,)) dz.
Then, also have
1s1 (07.80(=-1)) (z (TI....,,Ti)) (7))
(0(T,0(=-11) 1s, VP (2 ( ,.....,,,))))) dz
/ (11,10(=-11) (72f((8) - 1(., F) (2 (TI......TT.) dz
(7² I'" ((T10066-1)z) (((5) - o(7, /'' (((m10(011)) F. (2 (T1, (T,,..., nn.)) de
2 (7 (((---0((n))) f((S) 3(r / Co(T.1M(=-1) (2 (12==111100)0000
(TI..... . an)) dz,
0(7, B)
where the first inequality follows from the part 4) of Theorem 1. As result, we have
1s (T.,.... an); [ (0x,3)(-11)) (= (TI, (TI,.... nnn)
am))dz) dz) 2 - - (F T...
Φ(7,13)
From Definition 2, we can show that, when the policy vector (zj...., nr, ) is the stationary point of the surrogate objective F. over domain II=- Ax, and S satisfies the constraint of problem (I), due to 1s 11 AR.. the following inequality holds:
1s - (Tf. TT,, / w())VFi (2 (Ti....., R) dz S 0,
where w()) is the corresponding weight function.
Then, following Theorem 7, show that whenfi is monotone a-weakly DR-submodular and u=(2) (=()-1), for any policy vector (II...., Ttn) E I Ax, and any subset S within the constraint of problem (1),
Frff...... T (1-e- c1-c
So we get the result of part 1) of Theorem 3. Similarly, from ii) of Theorem 7, we also can achieve the part 2) of Theorem
F.2 Proof Part 3) in Theorem
In this subsection, we prove 3) in Theorem 3.
At first, we define a modular function 9t over V, namely, for any subset S S V. (e( & Enes fi (a|V), \ {a}). Then, when ft is monotone submodular, we can show that the set function (ft 9t) is also monotone submodular function. That is,
45

---

Theorem 8. For monotone submodular function ft V - Rt. we define modular function (c(S) Eaes fa (a|V), {a)) VS _ V, then we also can show that the set function (fe 9t)) is monotone submodular and non-negative.
Proof. Because the set function (Jr St) is the sum of submodular function Sa and modular function -tt, (St 9t) must submodular [105]. Then, we show the monotonicity of the set
function (Se ). At first, for any subset S _ V and any action a E V S, we have that
(ft - 9.) (a] = ft (a]S) 9r (a|S) = Je (a - fa (a|V {at) 2 0,
(31)
where the final inequality follows from the submodularity of fa.
From Eq)(31), we can know that (ʃe 9t) monotone. Moreover, due to (((0) = g:( = 0.
(Jz - ge) is non-negative.
Next, we show the policy-based continuous extension of our aforementioned modular function gt- Theorem 9. Given a monotone submodular function ft V + I.,, we define its related modular function as (S(S) & Loes fi (a|V) \ {a}), VS S V. Then we can show that the policy-base continuous extension of gr is as follows: Ge(TI.....TTT E > Em-1 (fe(ve,x - 3) Timm
if TΙ = (Tr.)..... (s,,)) E AR,, E N.
Proof. By the definition of gr and Definition 1, we can show that
Ge(ZI,...,TTT..
E
(oO(U) (a:)) II p(a.)
II p(a.(m.)) E Σ f (ai))((aaa)) E (E)
Σ
(CE ((a./\\aa)))
n
aEWU
(flcvulV-(oae Tr.m.
Tim..
where the final equality follows from V; = fU.. M.
From Theorem 8, we know that, when ft is monotone submodular, so is (Jz gt). Then, if we apply Theorem the monotone submodular function (Se 9t). we can have the following relationship:
Lemma 1. Given monotone submodular set function fr. we define modular function ge (S) & Loes ft (alV) \ (a)), VS C V. then, for any policy vector (Rı,..., nn) E =llm Ax, and any subset S within the constraint of problem (1), the following inequality holds:
1s (TT, (T.,..., Tn), 6 e- (Fi - G.) (2 (TI,..., nTm)) dz
(32)
(1-1 (fe 9t) (S) (F+ (F,-G,) G.) (ZI,...,,TT,, Th))
where F, and G2 is the corresponding volicy-based continuous extension of ft and 9t. respectively. Remark 12. Note that the submodular objective function is also 1-weakly DR- SRR-uomodulla fucntion. Thus, the results of Lemma come from Theorem and Theorem 8.
Moreover, from the definition of G, in Theorem 9, we know that G. is a linear function over I De; such that
1s (T T.,) (TI........ ,,)) (1s) ,T)) g:
Tn).
(33)
Merging (32) and (33), get the following theorem:
46

---

Theorem 10. Given monotone submodular set function ft with curvature for its policy- based continuous extension F, introduced in Definition 1, we consider surrogate function Fi -ll=1 Ar; 1 whose gradient at each point x E II Ae; is a weighted average of the grudient VF,(= * x)), numely, (x) - So el= x æ)dz, we have that, for any policy vector (T1...... ,.p) IIIi= Ax, and any subset S within the constraint of problem (1), the following inequality holds:
Ge
1s (TI Nn).V V
Pt
(T (TTI....,,TT,, nnn)
(TI... Thn) + f ca(e-1)FF ( (T......, R.)) dz
(34)
19 (TI..... nn))
) f((S) Fi (T (T,,,.., Tun).
Proof. According (32) and (33), we have that
1s (TI..... n. (G Tnd + ('' -- cF - Gi) (2 * (AI...., nT)) dz
2 (1 1/e)f((s) + (c(S) Fc((TT,......
(35)
2 (1 1/e)f((s)) + (1-c)f((5) Fc((TTI......
= (1 c/e)f((() Fe((TT,..... n.),
where the final inequality follows from the definition of curvature (See Lemma 2.1. in [105]).
Moreover, due to that G, is a linear function, we have
_ v (Fi - Gi) (2 (TL. Jnn) dz
Vi (z (T T.)) dz {' d D- n.))
(36)
c-lV ( T.).. (1- -111))-) (T, R.,);
where the first equality follows from VG, (II....,, Rn)) VG, [T , Rn).
Merging (35) and (36)3 we get the (34).
From the result of Theorem 10, for any stationary point , over I[ Ax, and any subset S within the constraint problem (1), then we have the following inequality:
,I,)) of the objective (F, + Ct)
02 1s (n.,...., ) V
Gt F? +
(z......, ,,.,,,,,)))) 2 - 2) f((S) Ff ..... x
In other words, Fe 2 - 9) f((*)) where S* is the optimal subset problem (1).
G Convergence Analysis of MA-SPL Algorithm
In this section, we verify Theorem 4.
Before that, we firstly show that the surrogate gradient estimations in Line 16 of Algorithm 1, namely, di(t) is bounded and proposed policy-based continuous extension F; is smooth.
Lemma 2. If we set M as the maximum marginal contribution of each monotone set function ft. namely, M A max (T) (fi(e)S)),the then have (t)(2) S v w(2)dz + )) where (t) is the surrogate gradient estimations in Line 16 of Algorithm 1.
47

---

Proof. From Lines 13-15, we know that di,m(t) (S2= w(2)dz) (vi.. (S((t) or mt)m(t - (Ui2o (( ( S.((t) e (u (.) Thus, have dd,m(t) 2 So w(=)dz + M for any i E N and m E [rs]] such that ||d:(()]2 = V Id (1)2 S Vea(So w(z)dz + M.
Before investigating the smoothness of our proposed policy-based continuous extension Pr, we firstly show its second-order partial derivative, i.e.,
Lemma 3. For any vector (TI,.... Rn) ) E I Arp the second-order derivative of Fg variables may mag Vig E N, Vm1 E [m,,], Viz E EN, Vmz [Kiz], can be defined as:
i): When i1 = 12, Tme, my Om mm
(TI..... Jt.) = 0;
ūi): When i1 + i2.
8 F. (T.n(t),...... ((,)))....,,..(()))) i ii ma
= -EasaLYiEN fo (1 (Uig) fa:t) U (uiz.ma)) fe (Uin.mll Vig(tiis)) (ait)
Remark 13. From the Lemmna if we set M as the maximum marginal contribution of each monotone function fü namely, M maxsgy,eev)sseem (fr(e]S)), then can show that Ri,n (t)(tt)) & M.
F.
05 m1 0K22.m2
Lemma If we set M as the maximum marginal contribution of each monotone set function St. namely, M - VVV) (fe(e)S),, then we can show that the Hessian matrix of the policy-based continuous extension F; of the previous monotone set function ft satisfies that,
2 Fr FT T.)..... S 2
Kis
(37)
1=1
where (TI...., R.)
I Ax.-
Remark 14. For any matrix A E Bxx, the (2, 60) )oom of A is defined as ||A = sup[llAx||so
R |x||2 1} where l|2 denotes the L2 norm.
Proof. From the definition of the norm
||- 112,o0, show that
V22 [1 2.) = max
V (T...... 1b. S 2 Σ Ris
JEN
where F n. [j. is the j-th line of the Hessian matrix (T n.) and the final incquality follows from Remark 13.
From Lemma 4, we can show that our proposed policy-based continuous extension F₁ is (M Σ smooth, namely,
Lemma 5. If we set M as the maximum marginal contribution of each monotone set function fo namely, M maxscv.eevsseen (fr(e]S)), then can show that our proposed policy-based continuous extension F; is (M Dis kx)-smootth
48

---

Proof. For any two point x;) E IT== Ax. and (xf.....,.t)))) m E II Axo if S πạ. for
any E NC the following inequality holds:
(T ................................ m. (F .....,,,))l
V F. ATt. ,
T AT, x². ; x. 12,
1/2
Fi ...,,...,; x + Ar))) zt...., n, )d2llo
S M
where the first inequality comes from | I vn inequality follows from the E3.(7 Thus, Fi is (M Di=1 smmoshh
[n/lx//a |2 for any n-dimensional vector x and the final
With Lemma 2 and Lemma 5, next prove Theorem 4. At first, show that each policy vector (Te,1 (t),.()..... (t)...., a at)), Vi E NN, Vt E [T] of Algorithm included the constraint [[ Ax, That is, we have the following lemma:
Lemma 6. In Algorithum Under Assumption (T,,1 ... (t)
IT An.
Proof. We prove this theorem by induction. At first, from the Line in Algorithm 1, know that x E Ax, for any i,j E NN, so (1). nn [()) E I[ Ar,, Vi E W. Then, if for some & E [2], (t),
Ni,n (t)) E IT== Ax. From Line 17, we know that Rt,m(t + 1) == Σjenugg (j (t) for any m F i. Then, due to Assumption 1, have Ejex(u Wy 1 and Wy 2 0 such that n, (t + 1) E ARm: Vm * Moreover, from Line 19, we also know that (t 1) E Ax,- Thus, (T,,1 (E + 1), (t + 1)) E I[ Ax.-
Before going into the proof of Theorem 4, we define some commonly used symbols, namely,
Li=1 (t,
x & (t): (t), (t, (n) Ranns, Vj e N
n
Zi, (1)
Σ
( (1), Vi e:;
jENau())
Σn= (()
(.
2eate(t) (2,;; :nn Raaxs fA VJEN
(t) A (0), (t) A Tt, + 1) - (t), (t)
R Vj W.
With these symbols, we can verify that
Lemma 7. E(IIr,,(t)]la = E(I 1) - z, (t)ll) = V w(2)dz + M where M is the maximum marginal contribution of each monotone set function fr.
Proof. When + j. from Line 17, we know that at, + 1) (t) such that ri. 0,,, and ((Irr,((1)l2) = 0 < V w/ w())d== + ! M. As for i j. from Line 18 and Line 19, we have st + 1) = arg min |b - (z,,(t) + (t), bEA.,
Note that (t) E Aay. Thus, we have
< [2,x(1)- + +nd.(()) ||2 - lld)((11l2 S wmall w
(38)
where the final inequality follows from Lemma 2.
49

---

Lemma 8. Under Assumption for any E [T] and i E N. we have that
1 m M, Vngt-m(f L/¹ 2o(2)d +
Σ iEN
B(
, 1)1l)
Vas'-m// So w(2)dzz 2 M,
Σ VEN
B( Zi. + - 5 + 1)II &
Σ
Vn
m=
where max Ax2 matrix W.
is the second largest magnitude of the eigenvalues of the weight
Proof. From the definition of (t)( we can show that
xt, 1) (t) z, [t)(t)+
Σ
Wii-k.j-
(39)
REN:U())
As result, from the (39), we also have that
zoste (t + 1) cate (t) + (W & Lx, )regfe( (t)
2 II, ) 1 L (m)
(40)
m=1
( @ Ix )ragt((m).
where the symbol & denotes the Kronecker product. If we also define (t)) that
[t]] (t):
R and from the Eq.(40), we also have
1n
xeale(() (t) =
60 In; (e)le(1) (1)
(41)
1
s I, (m))
m=1
Then, from the (40) and (41(,,), we have that, for any i E.
neylee (t at
+ xeate (t) = Σ Σ
(wi--]ss N reale (m).
(42)
m= JENiU(S)
(42) indicates that
(W-- 1) rogee (m/)
E 1 mrate( (t 1) =xgge(())))
(t)ll) =
Σ
Σ
m= jENiufit
(ww--1Js +) ||r (ma)ll
Σ Σ
S E
m=1 JEN.U()
[W-- - ()) I WATll /'' w(2)dz - m
m= iEN:U()
Vnrt S. w(2)dz + 'mm... M,
m=1
where the second inequality comes from Lemma 7 and the final inequality follows from Ejenung [ n I Vir'-m((ee Proposition I in [84]). Due to Zt
1) ExENCURO (t + 1) we also can have [[[I==, + 1) tt + 1)ll2) S
EjeNueo (t + at (t()2) S E Vnrt-m( (I' w(z)dz 1. 0
50

---

Lemma 9. When each objective function ft is monotone submodular with curva- ture c. a-weakly DR-submodular or (n, (, --waklly submodular. we set the ratio p
respectively. Moreover, we the symbol M to (1-3)(1-6-)) ( (010---000-0000 (01)))
((11)))) -(1-9)+72
denote the maximum marginal contribution of each monotone set function ft. namely, M & maxxsCY,eEvsS.eE (fr(e[S)). Then, under Assumption 1, if each set function fo is bounded Vt E [T), the following inequality holds for Algorithm 1:
Σ ((A))) Σ (1), ......,,.................... (1)) S 5M
mill w(z)dz + _ Σ Σ
pl-m 1/m
I w(2)d= 2
T
T
+ +nvmal
Σ
U 2
(IZZa(1) - (amm2)) || + (1))))))))
2n
where A is the optimal solution of problem (1) and 2 max(()2(W)))) (P))))))))))))))) is the second largest magnitude of the eigenvalues of the weight matrix W.
Proof. In order to unify the proofs in different setting, i.e., submodular objective with cur- vature c, a-weakly DR-submodular objective and (7.3)-weakly submodular objective, we de- fine some auxiliary symbols. At first, when each objective function fe monotone submod- ular with curvature a-weakly DR-submodular or (v, -)wakly submodular, we set
(1--),(1-=-)) (²0-=-(00-0t"") respectively. Moreover, compared to weakly sub- p(1-))+7²
modular scenarios, Theorem 3 designs different auxiliary function for submodular scenar- ios. Therefore, when each ft is monotone submodular with curvature cor weakly submodular, we define F. = Fi or F = (Fr + G.) respectively. Note that the F. is the surrogate function considered in Theorem 3 for different settings and G, is linear function defined as Ge(Z,,..., nn) ) A E Em= (fr( {vi,,))) Ti,m-
From Theorem and Theorem 10, we have that
pf((A)) FT ..... (t))
V V. (1), (()), 1A; (T), ...., ..,)),..........
VIT (1), (t)...., x() Σ
VET (T,, ........................ mo,(())] 1A; (T., .... F. (t))
iEN
(T. T.. (t)) 11, (T), ...0)........................... ml.(t))) ..))),.........))
EN
(f) m1) (t).......... (t)) - (t)..........
EN
(43)
where the symbol (V (P (T). (t)) is the projection over the policy n. i.c.. (F (t)) m represents a (E k.) diimensiio vector that only keeps the first- order derivative variable Te,,, Vm [Rg] and set other coordinates to that is say,
OF V (T (0)) A ((......... O...,,.... 0Tg
OF. .......,...... (x): Daa
where x A (T). (t))
51

---

For D we have
VF (T. (t) (t)) Σ
(T. ................................ mLn(t)] 2.
11;
..... R. -(8..(t)....,..1111))
IEN
VF [ (t) ................................ ,.))
Σ
(t))
||:; - ( ................................ a, (t))l
iEN
V F. ( T.,((t))
- VF (m)..........((( min((t)]
(1 + n (t))
ENN
2n Σ
[IV
Rn (8)) (T., (t),................... ,T. (..(())
EEN
w()) 2 nz - f w(z) (1). 2* T4, (1))zz) (,)
2m
Σ
IEN
$ 2Mm 2
/ m(=)zd=)] Σ (TT. () (t).,.,).... (+)]l2)
- [t,((t) - -x.)(1)1l2)
iEN
22Mn Σ
ni) w(2)zd2) Σ
JEN
IEN
/ L (()))d2)( /' w(z)da - Σ 7'-
< n
Σ
Tmm
m=1
(44)
where the fourth inequality follows Lemma 5 and the final inequality from Lemma 8.
For 3 under Lemma 2 and Lemma 8, we have,
V (T. .....
T...., (..)()))
- (t). (t))
EN
I Vrall/ //' w(2)dx+ + Σ Σ
[t],(()
(t]ll
(45)
iEN JEN
S /VEMBR9111 3/2 m((2)dz + 1 )
l-m
mmm
As for ②,, we have,
(T., ..,,,,,,,,. (1)) ((), 1A3 - (T).. (....))))(()))
HEW
V PT (().....(((()))) (0,) 11: 15:--1a (1). mLn())) (as(0).)EE))
E
E
HEN
(T.. (T4,1 (t), ... .()) (E.(()) 11; - (eu(())...,,ann1
E
E
VEN
E
(dd, ..... dn((t), 14; - (t), ..... (.)))....T..((tt)
E
(di d, (t)), 14; - (1), .....
+ E (dd (t), ... d. (t) (z., (f), (t) (I,, (t), ni, m.,((t)))
(46)
52

---

For 3 we have that,
2 < E (I)d d.. (2))l22 (t), ................................ (t)))(t)))))) - (Tt, (t), ... Tu (t)]()))
vin,M S w(z)dz IE [1((,,((): .................. 2,, - (J4,, (t), ..... The -,, (1))l)
S Vnn, M
w())d= + IB [1(2),(0) (1) - -2,, (.),,.................... ,,,( (m))l))
+ V L. w(2)dz + 1 LB (1( a2.1 (t)...,, T.. - Tt.. (t))ll2)
(47)
S VTR 1 w(=)dz + Σ
Σ
E
(1 - (.)(2) + [2,,(1) - {0)(()
NEN JEN
S 2nn <2n2VE,M f w(2)d= + 1
7
m
1m
m=1
For a At first, from the Line 19 of Algorithm 1, we know that, for any x E Ar.. we have || + 1) - x1|2 I (t),,(t) + d,d,() x||2- If we slightly abuse the notation 1 (Arm))) to denote ky-dimensional indicator vector over (A7 n V3). Note that 14; a ( dimmmeenii indicator vector over A; Then, we have [t, + 1) - 1 (4::v:))
(t),,(()) nt);(t) 1(47m))) 112
(t),,(tt) 1(A;:2))l 112 + 2n. (d) (Apmma) + (
Therefore,
(d,(1), ((42n))) (t))
(1) + 1 (12,,(() 1(47)1))133 1 + 1)
(ca7ni)) 113)
2
21p-
< The 2
(Fl / w<())z= 1 _ 21tt
1 (121:(0)) 1 || 1) 10 1c4nm))11).
where the final inequality follows from Lemma 2.
Note that
(((dd (t), dz 11; - (t), .2. (0))))
E ((di(t), ((47))))) z1,(())))
11t 2h M/r/ /'' w())dz + 1 M +
1 Σ
(122)(1)) ((A22)))2 [|x,a(1++] + (at2)))1
2T
(48)
Merging (48) (47), (46). (45), Eq.(44) into Eq.), finally have (t))
Pf((AT) -.., 2 ks)( L' w(2)d2 + 1 8 mm
+ Th . mmnnss// + + - + 2m
(l2,,(() - -13 1) - (ammm))11)
Therefore, we get Lemma 9.
Next, we prove an upper bound of Σt= 2n Σ (12,,(0) 1camma - || + 1)
I(A;m2))1 11)) that to say,
53

---

Lemma 10. Under Assumption 1, we have that
T
Σ 2T
4n
E
(A m2)lle)
71++1
7e+1
where A is the optimal solution of problem (1) and we slightly abuse the notation (AAOV)) to denote R4 fe-dimensional indicator vector over (A7 nV:)) Note that 1 is (Ei=1 dimeesiooa indicator vector over AT.
Proof.
T
(lz,,(t) - ((47m1)l22 (t + - ((47m2))1
217t
(((lz,,(t)) - ((A7m1))1B)
(( (24))
7c+1
E [12,, 1) 1c4 m2n |2,,(1 + - 144rn
7/++1
:=1
i=1
1
E
[lz,,(t+ 1) 1 (1) 2 [t, 1) 164222)113
T|++1
T
[T (t + 1) 1 (ammma)B
1]t+1
4
Firstly, we have I Σ.
[4)
$
Moreover, we have 4 4n
MT+1
m
As for ②,, we have
1
B(1
E
(1
1u: ||zi, + Icanusl13)
1/+11
T
E (((1 - 144;_ +2 (z + +1) 1c4ppe) (AAm)) - (c4t))m))))
1111
E [|1(4;))))) 144 mz))ll))
Mh+1
where the final inequality from (2,, + 1(4:n))) ((4))))) m(4 $ |lzz, 1)
1 1A2 [[1(A)M))) 1(47,) < 22|1(()) 1,z;
54

---

Then, we have
T
(tz + +1) - 14anm))ll-11aa + 1) - 1cagmw)l1))
11+11
T
E
WiyHt, + - 1 - lc4tmv)ll))
1/++1
Imi
kml
jENCU((
T
Σ
Wasll + - 1(45n))
Σ
[T, + 1) - (aagv))13
M]++1
BEN JENiU(H
IEN
T
Σ
w.)llz,((+11 1) ((47m)))
Σ
|| + ( ILaznve)13)
11++1
iEN
JEN(
iEN
where the first inequality follows from the convexity of [2 the third equality is from may = wis and the final equality follows from Assumption
We finally get
T
T
4n
(11 1114)mm)-1(AA. (At,,
2T
1T+1
7++1
t=1 i=1
As result, we can show that
Lemma 11. Under Assumption 1, when each set objective function fr is monotone submodular with curvature c, a-weakly DR- oR-buboodular or (n, -weaklly submodular, if we set the weight function w(2) according to Theorem 3, we have that
T
T
ki) J w(2)dz + - Σ
1
T
((AAt)
Σ
E(Je (UEn)a((())) S R
Σ
8 m
1/m
i=1
1= mm
+ mnVaal
//' w(z)dz + M
T
4n
T
E [11(0771)) -ca5,
WT++
M++1
Proof. Merging Lemma 10 into Lemma 9, we can get that
T
mi Lo w(z)dz + ) T mm
Σ (((A)) - Σ ()).. (t)) & 5M
m=1
+ +n/mil L' w(s)d=+ ! 2MM
4n
6 B [ [1
1 mass,,))))ll)
2
MT+1
11++1
t=1
i=1
From Theorem 1, we also can show that Fx(x) F((y) & nM xx - yll2 for any E [T] such that
we have
(T. n. FI 12.2 (t))
< nM][(TT, (t)...,,, (TT, (t)......... Tu. (t))
nM Σ (1) (1)(2 S nM ΣΣ (T,(()) R S 12/2M/2 /f w(=)dz+ 1 c
Σ , - Am:
where the final inequality follows from Lemma 8.
Moreover, from the monotonicity of F,(See 2) in Theorem 1) and Lines 5-8, we also can infer that
E (fe (a.(t)) (t) (t)) Fi (t), (2,, (t), Fn,
55

---

where the final inequality comes from p.(()=
2 TT)(())
Therefore, we have that
(f)l1
T
T
Ki)( L w(2)dz + ,
T
2 E=1
f((At) - Σ B(f (U (UF=)a(((tt)))
& n
n
Σ
7m
i=1
1=1 m==
1 + tnvhilf Sf w(z)dz + )
Σ
T
4n
T
[11(4:1))) 1 mAiz))
2
mr++1
m
1=1
1=1
From Lemma 11, if we set the step size 7 = 0 0( where Py - EE', (Ai+1 AAA and A denotes the symmetric difference, we can show that
Fe(1A;)
Σ Bli (a:(())
T
T 1mm) + 2 m) + O
T ΣΣ>
0
+
B(Il - Lcs,,,
7/++1
M)++1
1m mml
Am
-o
PrT
where the final equality follows from Pr E
Ei= [[(4)))) (Ar -
Ei [((a))))) mxnnl A Σ A A441AAj
H Convergence Analysis of MA-MPL Algorithm
In this section, we prove Theorem 5.
At first, we verify that each policy vector (T. (k) following lemma:
(f).... n (t)) E II. Ax.. namely, we have the
Lemma 12. When the communication graph G(V,E) is connected, we can show that
(M) (t)...., T (1(1))) E IIi== for any E N and S K as well E [T].
Proof. From the Line of Algorithm 2, we can know that (1) (2 0, V, E [T] such that (T (.),.................. (t) I Ar. Moreover, from Lines 8, for a fixed E [T], we know
that only agent E N can change the policy n(/)) (t). Furthermore, from Line 10, we also can infer that, for other agent j + i, its policy ([bb)
5,6 (t) is copy of some past iteration of (k) (t), namely, (k))
there exists a K1 I k such that T 2//1(()) (t) = T, (t). According to the Line and Line 10, we have T (t) n. (k-1) 1) (t) + v
(1), so we have n.. (t) = 1 Dt. V (m) (t) E Ax; for any [K]
E [T] and N. Therefore, we have (T.) (, (1) II Ax, for any E N and
e [K] as well as E [T].
(K) Note that, from Lines 11-13, each agent N only uses the policy n (t) to make decision. so the real policy vector taken by all agents is (K) (t), Tuin (t)). Motivated by this find- ing, next investigate some relationships between the policy vector (z (k) (t)....,,T.)) (t)) and (T..1 (k) (I)....,T.))) (1)). That is,
(k) ...., To,
Lemma 13. When the communication graph E(Y,E) is connected, we set R. 2 Er K₁ and utilize can show that
the symbol 1, denote the k-dimensional vector whose all elements
d(G)
0 0 n
(k) (t) /1x. (t).. (t)) (T.
T (t)( < K
56

---

where d(G) is the diameter of a graph, that is to say, the length of the shortest path between the most distanced nodes.
Proof. From Lines 6-10, we can show that, for fixed h E [K] and t E [T). each (t) (t) =
T (k)) (t) where hy E [ d(G)), kj. Moreover, according to the Line 8 and Line 10, we have
J. (t) Tij (t) R (t), so we have Th (t) * E V2 (t) for any k E [K]
(8)
(t)
(2) E [T] and i E N. Therefore, we have that 2j (1) T. (t) , En vj v)()(()) such that
(t) So we have the result of Lemma 13. K
(k)
0 S 1xys T (t) ( k-k diG)
K
(k) Next, we investigate the relationships between (Ii (t), Thn (t) and (τi,) (t).
(
In.n
(k-
(t)).
Lemma 14. When the communication graph G(V. E) is connected, we can show that
(0, (t) (x (-1.1 (k--1) (1), ...., h (1))
ने (v 1 (1) ... (v (1):
1
( 0 Inm (2) (t)..... (. (t))
(T/11 (f),... ..... T n.. -1))
1
K
11 where 2 > Ki and d(G) is the diameter of graph, i.e the length of the shortest path between
the most distanced nodes.
(R-1) (1) + K ) (t) Proof. According to the Line 8 and Line 10, we have (1) -,j we get result of Lemma 14.
(1). Therefore,
With Lemma 13 and Lemma 14, we next give an upper bound about the error between the gradient (T (K) (t),....,,,,,,, (1. (t)) and Lemma 15. When the communication graph G(V,)) is connected, if we set M as the maximum marginal contribution of each monotone set function fo. namely, M P maxscv.eev(s.eet (fr(e[S)), we can show that
(1) (t)).
2200 S /VanMa(G)
(ZT( (1), .......................
K
where K = Ei= Ki and d(G) is the diameter of graph, i.e., the length of the shortest path between the most distanced nodes.
OF. Proof. At first, we investigate the error between the first-order derivative Sr..m (N (t), T (t)
and the first-order derivative aF ami.m
(k) (x (t), ...., , (t)) for some E N and m E [m:].
(b)
(k) OF, (Tt (1), 1 (t))
(())(())
aF,
(3) (T. (t),.... n 1 (2)
(K)
Tg.m
-1 OT.,m
OFF.
F²Fi
(x), [ 2.
. (1)
) (t)
Oi, O OTim.
$ M (Ie (z(1)(()) - ... (t), (2) (1) (t) G.
K
where the first equality comes from = (x) + (1 (1nx))((110 (t) ... X (1-A)T (t)
for some À [0, 1], the first inequality follows from Remark 13 and the final inequality comes from Lemma 13. Then, we have that
V (T. (t),
(k) (t) - (T.( (1),
(4) (0))
< / K max 74.m
OF
(Tt
(b)
(k) n.n
(t))
OF. Ft.m
(T (k) (t),
(2) (1))
<
VKnMd(G)
K
where k = Ei K2 and (G) is the diameter of graph, i.e., the length of the shortest path between the most distanced nodes.
57

---

Now, we prove Theorem 5.
Lemma 16. When the communication graph G(V.)) is connected, if we set M as the maximum marginal contribution of each monotone set finction fo. namely, M - sas (fr(e(S)), we can show that,
i):) if ft is a monotone w-weakly submodular function:
T Σ
T M(AA)) - Σ
(10 (1, (0)... (2))
- E
nM (2: Ke)
2VKn
T
2nM VK T
20:
K
vL
d
(1)
v(((())
ii::) if fo monotone (y, (1,33)-vn weekly submodular:
72 - (11-0-
T
T
Σ M(AA)) - - (F((T( (())))()) (f).-..,,x,,))) x2221(1))
B)
nM K.))
2 2
T +
2nMva T
+
())
6(7,38
K
$17,8) VL
K n
K ΣΣΣ (t),
(1amaa -v, (1).
where where slightly abuse the notation (A702) denote ku-dimensional indicator vector over (A4 0 (.).) Note that A; is (Ei (.))ddimessooal indicator vector over A₁ and o( (3) 3(1 -1 + Note the En (a. (a ((A))V)) - v.'(t) (v. is the dynamic regret of linear maximization oracle gbha) over the competitive sequence (IAATT:::... Ma4n2)). Therefore, we also rewrite the previous two results
i):) if fe a monotone o--weakly submodular function:
T E f((A7) Σ E (0....,,.........))))
T
Σ
2VEn2Md(G)
T K
2nM T
+
20
VL
K K
RO!
k=
ii::) if fs monotone (r, --ekkly submodular:
2² -2(1---(11 ((7.9))
T
Σ M(A))) Σ
(1 (1) (2) (1)
((T,3)
n.M( ii (&))
+ 2
T
2nd Vn T ()7,8) VL
K +
20(1,3)
2(7,8)
K
1
R4!4) (I(4719)...... (1 1(4apva).
K
k=
where R (1A4T))).... (ApnV)) (AAnn)))..,,AA)))))) is the dynamic regret of linear maximization oracle Q.!²
over the competitive sequence (1 (lAARne)).... 144522))
58

---

Proof.
FI (K) (t).,,
x (t) - F( (k- (4) (t))
VT (k-1) (1), -... _,, (1))
(k-1) (t), -.)................... (T) (1) (t))
M M(Σ ki)) (1)))()))
(k
(1) - (1) (1)) (1)
111
nM (M Ks)
2 K
(T
(1-1)
mn (1)), (vi (K) (1)
( (()()))
2K
1 (k-
R.(E ki))
(F.
(0)).1A)
K
2K
(T (k-1)
(v) (O) (1)) 1A)
+ K
(t)...... (t)), ) n.M Ki)
(F (k-
K
2K²
1
[Fi(TT,1 (t), (t)
(k-1)
1 nm (t))
Σ
( (K- (t).
(k-1) { (v] (t) (t)....., vf) 1A3
K
EN
1
V (T, (1)
(1) ,,) "0)0 n
(1 (1), (1) (v) ()) 1Az
K
/ + K
1 ((af" (t),"() (t)) (1))
(t))
where the first inequality follows the Lemma namely, our proposed policy-based continuous extension F3 is (M E mm)-smooth andthe symbol (t), I.. n;
is the projection
over the policy n. namely, VFT (F...())......... (t)) represents (Ei K, ) dimeensooal vector that only keeps the first-order derivative variable Ti.m: Vm E [Ms]] and set other coordinates to that is to say,
V (T. T.,( A ....,......
OF. θT..1 (x),
OF, OTi.
(x) 0,
R1
where x A (1).
For D. according to 4) of Theorem 1, when fe is monotone a-weakly DR-submodular,
(1 ((.......((k))))))) (1)), LA:) 2 a (I.(AF) Fr( (K
(1))
n.
As for the setting that fa is monotone (7, --,akl- submodular, we also have
(P - ((), (3 (M1.11 (O, (0),,.,,(("" (1))
59

---

For ④ according to Lemma 15, we have
(1) (1), offt"11)) ((v()) (D)...,,v!'(())) - -14;) )
( ( (1) T/m (()) Σ
V [
REN
F
T/ (1))
-E
( (o (1))
.v1 (1)
- 14;
iEN
m
Σ IEN
1)
(0)) K5
V (t),...,... m (t))
(h) ()...))))...)'''')))))) 14:
[1,1
iEN
s 2n Σ
(1- (11) - V
(1-1) (1) 1
(0))
12
iEN
2/Km²² Md(G)
2n Σ
/F ....,.................... (t)...., (t)) (F (0),,,,""
5
2
K
iEN
As for 3
E
VF, FF, (K- (t), (t)] -
(v]
(t) v() - 1ar)
BEN
V (T (1 (t)...., Am (0)) x
- -(af" (t), (t),...... 1000.....!100 (1)
[[v]² (t)...... ((,,+()))....+((((()) 14111
E
2
< 2nlE
Σ iEN
( (t)....., R (00) - d
$ 2n
1
81 (t), .t......B
(k)
g 02
(+)))
L
R2
< 2
L
where the third inequality follows Lines 15-20, namely, (af) (6), a (l)
is L-batch stochastic , ((-"(()) and the final inequality follows from Re-
gradient for EIEN (F (k-1) () (0,...,,
mark 13 and Ei= Kig.
Therefore, when ft is monotone a-weakly Subbbuuoa we have that
(7( (O),..,
(()))..,,,.))))) (1) (((T((-1)))))) (t)....
(1))(())
An
a K
E (fe(At) (T (k-1) (t),... Jnn (())) nM KG))
2/ 2/En2Md(GT)
Md(G)
2nM
K
2
2K
K2
K
L
1
((a()) (t). ..., (1)) (v1 (k) (t), v v(),...,((((() -LA;)
K
Then, we can have that
(f((A)) - (().,,))))..........)) (t))
< (1 x) E (f:(4))) -
(k- 1) (1)).. (1).....T...) (...,()))=)))))
nM <2
11 Ki)
2/Rn² Md(
2n
K
2K²
K2
K
1
((al)) (t). (()()) (v (t). (t)...... (() LAi)
K
60

---

As result,
E (
- F((TT)11 (1),..., T(2 (1))
< (1 x)
E (I.(4)) ( -....,0)))...............
..... 160 (11))
K
K
(a (t),... (t)).......((())) (v) 10) (t), vn (t)) - 1A;)
K k=
+ Σ
K
(1
a
K-m
n.M 12 Ki)
RV Md(G)
2nM
K
2K²
K2
K
V L.)
m=1
$ (1 x) (F((AA))
E K.)
R
2
2ac
ak
C
(O).... (.),.....c. ..)( (v (1) (f)...... ((),...,,,(() -AA;)
K
SE E (Je(AT) +
11=1 ks) 2 Rn Md)
ak + a
2n.
16
2a
L.
K
(t).... (t)).........()() (t)
(b) (t), (t).....
v.. (t)) - LA;)
K 1m
where the second inequality follows from Dm=1 (1 inequality from from (1 - R S <eaa when K 2 3.
K S a.
K-m
K
FO = 0 and the final
))K
So we can get the following result,
(1-e Σ M(A)) Σ (F
(1) x(2(())
nM
(E Ke)
2VFn(Md((G) T 2nMVF T
20
a
a
VL
K
T
ΣΣΣ (1) (o) ()
k=
where we slightly abuse the notation 1 (Army.) to denote diydiimesiional indicator vector over (A4) 0 V.). Note that 14; is a (E=1 k2) -i)ddimnnio indicator vector over A
Similarly, when fa is monotone (7. 3)-kellly submodular, we also have (F((T()))
(8) (t), ((h( ( (t)
m. (())
2 (T(((())))))))))))))){{)))))(( o(T, 3) (T (4)
T (
n. (2. k:)
2/Kn² Md(G)
2nM
K
K
2K2
K2
K
T.
1
(1( (k) (t), (t)..... ................... d (+) (vi (k) (t) (t),...., (4) LAT) -1A)
+ K
where (07, 3) = 3(1 7) +72
Then, we have
E
(((A)) - 6(7, (K)
1
2(1,3) E (725((47) p6% (1
(K-
(f)...,,(( (t)))))))
K
(nM(EL (4) 2
2nM K +
+ ()7,88
2K2
K2
K
01. B)
((1 (t)..., (v (v()) (t). (......!!((())))))))) (t)) LAz
K
61

---

As result, we can get the following result,
2-11 - e )
T
T
((()))
Σ
E
(K) (1), ((. (1
(7,,8)
1=1
1=1
n. n.M
ii=1
2/kn² (1,,))
Md(G)
T
2KM T
1
(t) (t) 1(agnia)).
20(7,, 3)
K o(,,8) VI. K
As result, when K T and L. = T, if Assumption 2 holds, that is, each linear maximization oracle e,ah) can achieve the a regret bound of (VVVTT) where Vr is the variation of any feasible
path (ui,..., UT) where u, A... Vi [T]. that is, VT A Ei l|u u-11l2 for any path (uI,..., ...., ur) E I AR, then we can have the following results:
i): when fe is a monotone a-weakly submodular function, Algorithm 2 achieves:
T
T Σ
(1 - e Σ f(AA))
E
(L (1).
(t)
(t))
Ra)
2/Km² 2V(n) Md(G)
T
2n T
K K
RQ!4
(1caк)z):... ... (.4pp))))))))
20
K
VL
k=
1=1
1
T
1a4 1casnval
+0 (d(G))T)
T-1
T
Σ
L47 - 10i1|
+
i=1
LAi -1:ll o (d(G)VPPr)
0
d(G))
T
where the third inequality follows from the concavity of V function and the final equality comes from Pr A ΣT |4i AA; A ΣTH || LA; lll _ -T= |A LAi lla.
ii): Similarly, when fo is a monotone (r, -weakly submodular:
21 - e (1,
T
T
f((A))
E
(K) (t)...,, xtth (F((T)
6(,,8)
1=1
00 d(G)
T Σ
L
- 1az 1Ar1|
(o(((i)/IP))
I Limitation and Broader Impact
In this work, in order to eliminate the dependence on the unknown DR ratio and submodularity ratio in our proposed MA-SPL algorithm, we introduce a parameter-free online algorithm named MA-MPL for the MA-OC problem. However, this new MA-MPL algorithm typically incurs greater communication complexity, as shown in Table 1. Notably, recent studies [74, 124] employed a blocking procedure from [121] to reduce the number of communication in the decentralized online Frank- Frank-Wolfe algorithm [133]. Since our MA-SPL algorithm also can be viewed variant of decentralized online Frank-Woll
algorithm [133], we believe that this blocking strategy is a promising technique to help reduce the communication complexity of our proposed MA-MPL algorithm. We plan to explore this in future work. Furthermore, this work focuses on theoretically exploring MA-OC problem with (7, weekkly submodular and a-weakly DR subboduuu objectives. So we do not foresee any form of negative social impact induced by our work.
62


Reviews:
[{"review_id": "XBr3hBe6kl", "reviewer": "Reviewer_4FMc", "summary": "This paper studies the multi-agent online coordination problem, where multiple agent choose their actions in a finite action set to maximize a set function. This is an optimization problem with discrete support. The authors propose to learn stochastic polices for the agents so that the problem is converted to a continuous optimization problem, and this framework is named policy-based continuous-relaxation. Under this framework, the authors characterizes the suboptimality of stationary points of the relaxed continuous function (Theorem 2). Moreover, a surrogate objective function is proposed to improve the suboptimality gap (Theorem 3). Effectiveness of the algorithm is verified by simulations.", "questions": "Questions are included in ``Strengths and Weaknesses''.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**This is a nice submission with the following strengths:**\n- A new continuous relaxation is proposed for set function optimization, which enables provably efficient optimization for weakly submodular functions. As a comparison, previous relaxation approaches relies heavily on the ``strong'' submodular assumption.\n- The authors theoretically characterize suboptimality of stationary points and proposes a method to improve suboptimality. \n- An end-to-end optimization algorithm is proposed and analyzed.\n- Empirical evaluation verify the effectiveness of the algorithm.\n\n**That said, the reviewer do have the following concerns/question:**\n- After policy-based relaxation, the problem is essentially reduced to a multi-agent identical interest game (a subset of potential games (PG)). There exists a huge amount of literature that designs provably efficient algorithms that learn nash equilibrium (a subset of stationary points) and provide price of anarchy lower bounds (or suboptimality in the context of this paper) for PGs. Are results for PGs also applicable to this setting? If so, how are the results in this paper compare to results for potential games? \n- Consider the surrogate function In theorem 3. Are stationary points (denoted by $x^s$) of the surrogate function also stationary points of the policy-based relaxed objective $F$? If not, what will happen if we start from $x^s$ and do gradient descent using gradients of function $F$? Will this strategy increase or decrease the sub-optimality gap? In case this is hard to characterize theoretically, I would like to see at least come empirical evaluations and discussions.\n- In line 5 of Algorithm 1, the authors normalize the policy and sample actions. Is it necessary for the empirical performance or theoretical analysis? As far as I am concerned, function $F^s$ seems to be supported on the entire probability simplex and gradient descent seems to work without this projection step. If this step is indeed necessary either theoretically or empirically, ablation simulation studies and discussions would be helpful. \n\n**Minor comments**:\n- The current abstract has involved too many specific terms (e.g. submodularity ratio, weakly submodularity ratio) for the general audience to understand. It would be helpful to talk about them more high-levelly.\n- It would be helpful to give a high-level introduction about how previous extension, e.g. multi-linear extension, works.", "was_revised": true, "final_justification": "The authors addressed most of my concerns in the rebuttal. I will maintain my original rating towards accept.", "rebuttal": "Thank you very much for your careful reading and constructive feedback. We are grateful for the time and effort you have dedicated to reviewing our manuscript. In what follows, we will address some of your concerns in `Weaknesses`.\n\n---\n`Weakness1`: After policy-based relaxation, the problem is essentially reduced to a multi-agent identical interest game (a subset of potential games (PG)). There exists a huge amount of literature that designs provably efficient algorithms that learn nash equilibrium (a subset of stationary points) and provide price of anarchy lower bounds (or suboptimality in the context of this paper) for PGs. Are results for PGs also applicable to this setting? If so, how are the results in this paper compare to results for potential games?\n\n---\n\nThank you for your insightful comments. \n\nAt first, we are so sorry that neither of us is a specialist in computational game theory or Nash equilibrium. However, based on our limited knowledge of potential games, we think that if we ignore the changing environment and return to the offline setting, previous algorithms for learning or approximating Nash equilibrium could be applicable to our proposed policy-based continuous extension $F_{t}$. Nonetheless, according to our Theorem 2 and the approximation result for the equilibrium solutions of submodular utility functions (See Proposition 1 in [Du et al., 2022]), we can infer that these existing algorithms for approximating Nash equilibrium of $F_{t}$, in theory, also can guarantee a **sub-optimal approximation ratio** of $(\\frac{1}{1+c})$, $(\\frac{\\alpha^{2}}{1+\\alpha^{2}})$ or $(\\frac{\\gamma^{2}}{\\beta+\\beta(1-\\gamma)+\\gamma^{2}})$ to the offline multi-agent coordination problem (1), when the original set function $f_{t}$ is monotone  submodular with curvature $c$, $\\alpha$-weakly DR-submodular or $(\\gamma,\\beta)$-weakly submodular. \n\nSecondly, in order to obtain tight approximation guarantees, we indeed could apply algorithms for approximating Nash equilibrium to the surrogate function $F^s_t$ proposed in our Theorem 3. However, similar to our proposed **MA-SPL** algorithm, these aforementioned equilibrium algorithms on $F^{s}_{t}$ also require prior knowledge of the difficult-to-obtain diminishing-return(DR) ratio $\\alpha$ and submodularity ratios $\\beta,\\gamma$ to set weight function $w(z)$. In comparison, our **MA-MPL** algorithm not only achieves **tight** approximation ratios but also is **parameter-free**.\n\n---\n>`Weakness2`: Consider the surrogate function In theorem 3. Are stationary points (denoted by $x^{s}$) of the surrogate function also stationary points of the policy-based relaxed objective $F$? If not, what will happen if we start from $x^{s}$ and do gradient descent using gradients of function $F$? Will this strategy increase or decrease the sub-optimality gap? In case this is hard to characterize theoretically, I would like to see at least come empirical evaluations and discussions.\n\n---\nThank you for your constructive feedback.\n\nAt first, we are so sorry that we cannot confirm whether the stationary point $x^{s}$ of surrogate function $F^s_t$ is also a stationary point of the original policy-based continuous relaxation $F_{t}$. It is worth noting that, if $x^{s}$ is a stationary point of $F^s_t$, for any  $y\\in\\prod_{i=1}^{n}\\Delta_{k_{i}}$, it satisfies $\\langle y-x^s,\\int_0^1 w(z)\\nabla F_{t}(z*x^s)dz\\rangle\\le 0 $.\n\nHowever, when $y\\in\\prod_{i=1}^{n}\\Delta_{k_{i}}$,  we seemingly cannot derive $\\langle y-x^{s},\\nabla F_{t}(x^{s})\\rangle\\le0$ from the above condition $\\langle y-x^{s},\\int_{0}^{1} w(z)\\nabla F_{t}(z*x^{s})\\mathrm{d}z\\rangle\\le0$. \n\nSecondly, previous studies [Sviridenko et al., 2017, Harshaw et al., 2019]  have indicated that for any $\\epsilon>0$, it cannot be approximated in polynomial time within a ratio of $(1-\\frac{c}{e}+\\epsilon)$ or $(1-e^{-\\alpha}+\\epsilon)$  for maximizing a monotone submodular function with curvature $c$ or $\\alpha$-weakly DR-submodular function, unless **RP**=**NP**. Furthermore, from Theorem 3, we can know that $x^{s}$ can attain an approximation ratio of $(1-\\frac{c}{e})$ or $(1-e^{-\\alpha})$ to the submodular or $\\alpha$-weakly DR-submodular maximization problem (1), respectively. Therefore, based on these established inapproximability results  [Sviridenko et al., 2017, Harshaw et al., 2019] , we can ensure that it is theoretically impossible to improve the approximation ratios for the entire family of submodular or weakly submodular functions by starting from a stationary point $x^{s}$ of $F^{s}_{t}$ and then performing gradient ascent using the gradients of the original $F_t$,  as $x^{s}$ has already achieved the **tight** approximation ratio of $(1-\\frac{c}{e})$ or $(1-e^{-\\alpha})$.\n\n---\n`Weakness3`: In line 5 of Algorithm 1, the authors normalize the policy and sample actions. Is it necessary for the empirical performance or theoretical analysis? As far as I am concerned, function $F^{s}$ seems to be supported on the entire probability simplex and gradient descent seems to work without this projection step. If this step is indeed necessary either theoretically or empirically, ablation simulation studies and discussions would be helpful.\n\n---\nThank you very much for your insightful question. It certainly highlights an aspect of our paper that deserves further clarification.\n\nAt first, it is worth noting that, in this paper, we mainly explore the **monotone** objective set function $f_{t}$. Then, according to part **2)** of Theorem 1, we also can know that when the original objective set function $f_{t}$ is monotone, its policy-based continuous extension $F_{t}$ is also monotone. More specifically, for any two  policy vectors $(\\pi_1,\\dots,\\pi_n)$ and $(\\hat{\\pi}_1,\\dots,\\hat{\\pi}_n)$,  if  $\\hat{\\pi}_i\\ge\\pi_i$  and $f_t$  is **monotone**,\nwe have $F_t (\\hat{\\pi}_1,\\dots,\\hat{\\pi}_n)\\ge F_t (\\pi_1,\\dots,\\pi_n)$.\n\n\n Motivated by this result, we also can show that, for any policy vector $(\\pi_{1},\\dots,\\pi_{n})\\in\\prod_{i=1}^{n}\\Delta_{k_{i}}$, when $f_{t}$ is **monotone**,\n\nwe have $F_t (\\frac{\\pi_1}{|| \\pi_1 ||_1},..., \\frac{\\pi_n}{|| \\pi_n ||_1})\\ge F_t (\\pi_1,\\dots,\\pi_n)$  due to  $\\frac{\\pi_i}{|| \\pi_i ||_1}\\ge \\pi_i $.\n\nAs a result, in line 5 of Algorithm 1, we utilize the normalized policy to select actions. We truly appreciate you pointing out the deficiency in the description of our Algorithm 1. We will add an extra remark to the line 5 of Algorithm 1 in the final version.\n\n---\n>`Minor Weakness1`: The current abstract has involved too many specific terms (e.g. submodularity ratio, weakly submodularity ratio) for the general audience to understand. It would be helpful to talk about them more high-level.\n\n---\nThanks for your suggestion. \nIndeed, the abstract currently contains too many specific terms like diminishing-return(DR) ratio $\\alpha$\nand submodularity ratios $\\beta,\\gamma$, which are not friendly to general audiences. To make the abstract more high-level, we will unify **$\\alpha$-weakly DR-submodular and $(\\gamma,\\beta)$-weakly submodular scenarios** as **weakly submodular scenarios** in our final version.\n\n---\n>`Minor Weakness2`:  It would be helpful to give a high-level introduction about how previous extension, e.g. multi-linear extension, works.\n\n---\nThanks for your helpful suggestion. \n\nBefore that, we have considered adding some basic content about multi-linear extension and its comparison with our proposed policy-based continuous extension in **Related Work** section or the end of **Section 4.2**. However, due to space limitations, we moved it to Appendix C.4. In order to help readers interested in multi-linear extension quickly locate Appendix C.4, we will add some relevant details and a reference to it after Remark 5 in our final version.\n\n---\n**References**\n- B. Du, K. Qian, C. Claudel, and D. Sun. Jacobi-style iteration for distributed submodular maximization. IEEE transactions on automatic control(TAC), 2022\n\n- C. Harshaw, M. Feldman, J. Ward, and A. Karbasi. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. ICML, 2019.\n\n-  M. Sviridenko, J. Vondr ´ak, and J. Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Research(MOR), 2017"}, {"review_id": "TiW09viQdQ", "reviewer": "Reviewer_fLMy", "summary": "The authors propose a novel continuous-relaxation technique to achieve multi-agent cooperation under submodular and weakly submodular objectives, and they theoretically prove the optimality of the algorithm while analyzing performance metrics such as communication cost and regret. The paper is well-structured and clearly written. However, further discussion is needed regarding problem modeling, assumptions, and the practical feasibility and deployability of the proposed method.", "questions": "1. How do you justify the requirement that each agent's action set must be disjoint, especially in scenarios where agents (such as identical UAVs or UGVs) would naturally share similar or identical action sets?\n2. Could you discuss the practical feasibility of your approach in terms of communication requirements, asynchronous operation, and onboard computational constraints to better demonstrate the deployability of your algorithm?", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\nThe authors have provided thorough modeling, algorithm design, and theoretical analysis for multi-agent cooperation problems with submodular and weakly submodular objective functions. The paper is well-written, the algorithms are comprehensive, and the proofs are convincing.\n\n**Weaknesses**\n\n1. I have some concerns regarding the modeling of the problem. The author requires the action sets of each agent to be disjoint, which is rather puzzling, since identical UAVs or UGVs would typically have the same action set. Furthermore, the stated problem (1) appears to be independent of the system state, whereas, in my view, the UAVs’ tracking tasks are highly dependent on target locations and related state information. In addition, if there are two equivalent decisions at time t (for instance, agent a moving right or agent b moving left), it is unclear which will be selected. Has the heterogeneity in the decision outcomes of different agents been fully considered?\n2. Although the paper focuses primarily on the theoretical aspects, it would be beneficial to include some discussion on practical considerations, such as the feasibility of communication, the possibility of asynchronous operations, and computational feasibility under constrained onboard resources, in order to strengthen the persuasiveness of the algorithm’s deploy ability.", "was_revised": true, "final_justification": "I remain positive on the paper, including the writing, the method and the theoretical results. The submission is not in my area, so I have lowest confidence about my score.", "rebuttal": "Thank you very much for your careful reading and constructive feedback. We are grateful for the time and effort you have dedicated to reviewing our manuscript. In what follows, we will address some of your concerns in `Weaknesses` and `Questions`.\n\n---\n>`Question1`: How do you justify the requirement that each agent's action set must be disjoint, especially in scenarios where agents (such as identical UAVs or UGVs) would naturally share similar or identical action sets?\n---\nThanks for your feedback.  \n\nThis question certainly highlights an aspect of our paper that deserves further clarification. In the context of UAVs’ tracking task, each UVA indeed shares the same movement space. However, it is crucial to emphasize that the **movement space** is distinct from the **action set** we consider in our paper. Broadly speaking, the objective function of the UAVs’ tracking task is not solely dependent on the identical **movement space**.  The key factor in shaping the objective function is **which UAV/agent carries out which particular movement decision**. To reflect the different role of each agent within the tracking system, we  commonly assign unique identity tags to each movement.\n\nSpecifically, in our experiments, we consider the movement decision space $M=((\\theta,s):s\\in\\{5,10,15\\}\\text{units/s},\\theta\\in(\\frac{\\pi}{4},\\frac{\\pi}{2},\\frac{3\\pi}{4},\\pi,\\dots,2\\pi))$ where $\\theta$ and $s$ represent the movement angle and the speed, respectively. To identify the executor of the movement, we will label the movement space $M$ with identity tags. Consequently, for each agent $i\\in\\{1,2,\\dots,20\\}$, its action space $V_{i}$ is constructed as follows:\n\\begin{equation*}\n   V_{i}=M\\times i=((\\theta,s,i):s\\in\\{5,10,15\\}\\text{units/s},\\theta\\in(\\frac{\\pi}{4},\\frac{\\pi}{2},\\frac{3\\pi}{4},\\pi,\\dots,2\\pi)),\n\\end{equation*}\nwhere the action $(\\theta,s,i)$ indicates that agent $i$ moves towards the direction of $\\theta$ at a speed of $s$. \n\nWith identification information included, these action sets are mutually disjoint, namely, $V_{i}\\cap V_{j}=\\emptyset$ for any $i\\neq j\\in(1,2,\\dots,20)$. Please note that this approach with identity tagging is widely adopted in multi-agent systems, for example, multi-round product marketing [Sun et al., 2018, Huang et al.,2024] and online multi-advertisement slot allocation [Streeter et al., 2009].\n\n---\n> `Weakness1`: I have some concerns regarding the modeling of the problem. The author requires the action sets of each agent to be disjoint, which is rather puzzling, since identical UAVs or UGVs would typically have the same action set. Furthermore, the stated problem (1) appears to be independent of the system state, whereas, in my view, the UAVs’ tracking tasks are highly dependent on target locations and related state information. In addition, if there are two equivalent decisions at time $t$ (for instance, agent a moving right or agent b moving left), it is unclear which will be selected. Has the heterogeneity in the decision outcomes of different agents been fully considered?\n---\nThank you very much for your feedback. Firstly, regarding the assumption that the action sets of each agent are mutually disjoint, please refer to our response to `Question1`.\n\nSecondly, in our models, every specific sequence of system states $(s_{1},s_{2},\\dots,s_{T})$ in fact corresponds to a unique sequence of objective set functions $(f_{1},\\dots,f_{T})$, where each set function $f_{t}$ is determined by the system states $(s_{1},\\dots,s_{t-1})$ for any $1<t\\le T$. Especially in the context of UAVs tracking tasks, these system states  primarily depend on the real-time locations of targets and agents. Unlike most control-related papers that assume the system environment follows a specific equation, our modeling considers any sequence of state sequences $(s_{1},s_{2},\\dots,s_{T})$ that can ensure the (weak) submodularity of every $f_{t}$ for any $t\\in[T]$. It is worth noting that when the system states $(s_{1},\\dots,s_{t-1})$ are fixed, the submodularity or weak submodularity of each objective set function $f_{t}$ has been extensively verified in the literature[49, 50, 53, 55, 104, 115]. Thus, the goal of our paper aims to design an effective online algorithm that can achieve a tight approximation guarantee with a $\\mathcal{O}(\\sqrt{T})$-regret bound under the worst-case states sequence $(s_{1},s_{2},\\dots,s_{T})$ that can ensure (weak) submodularity. Overall, our model focus on the worst-case states sequence(adversarial environment) rather than a specific one, which might lead you to mistakenly think our paper is unrelated to system states.\n\nFinally, we apologize that our current model and algorithms seemingly cannot distinguish two different decisions that have the same effect on the objective set function $f_{t}$. Incorporating the heterogeneity regarding the decision outcomes of different agents into our model is indeed an interesting topic for future research. Before that, in order to ensure the diversity and fairness of decisions, many studies, such as [Chen et al., 2020, Mitra et al., 2021, Zuo et al., 2023], have introduced an additional penalty term into the original objective function. Specifically, instead of optimizing  $f_{t}$, they consider a new objective function $f_{t}+\\lambda\\cdot h_{t}$, where $h_{t}$ measures the fairness or diversity of different agents and $\\lambda$ is a positive constant. We believe this approach is also applicable for addressing heterogeneity.\n\n---\n>`Weakness2`:Although the paper focuses primarily on the theoretical aspects, it would be beneficial to include some discussion on practical considerations, such as the feasibility of communication, the possibility of asynchronous operations, and computational feasibility under constrained onboard resources, in order to strengthen the persuasiveness of the algorithm’s deploy ability.\n\n>`Question2`: Could you discuss the practical feasibility of your approach in terms of communication requirements, asynchronous operation, and onboard computational constraints to better demonstrate the deployability of your algorithm?\n---\nThanks for your constructive suggestions.\n\nFrom a high-level viewpoint, we think the main bottlenecks affecting the deployability of our proposed algorithms stem from **a)** the time-varying communication graph caused by agents' position changes and **b)**  the non-negligible energy constraints of agents.\n\n**a)** : Generally speaking, due to limited perceptual range, each agent/UAV only can exchange information with others within its sensing radius.  Furthermore, in the online decision-making process, the positions of agents/UAVs will evolve over time, which in turn causes the communication graph topology to continually change. However, in our MA-SPL and MA-MPL algorithms, we assume a fixed communication graph, which may not align well with the real-word time-varying communication topology. Fortunately, time-varying network topologies have been extensively studied in distributed optimization [Nedic et al., 2017, Zhu et al., 2021]. We believe these previous insights from distributed optimization can be effectively integrated into our algorithms to enhance their real-world applicability.\n\n\n**b)** : Broadly speaking, each movement decision of UAVs will consume a certain amount of power resources. However, our current model only focuses on the utility of decisions without accounting for these associated energy costs. This may lead our algorithms to ignore decisions with high ROI(return-on-investment) but lower utility. In reality, such decisions might extend the UAVs' operational duration and boost cumulative utility by allowing more decision rounds. Fortunately, we find that the energy constraints of UAVs are well-matched with the trending long-term constrained online learning framework [Sadeghi and Fazel, 2020, Nie et al., 2024]. Specifically, at each time step $t\\in[T]$,  a power consumption function $c_{t}^{i}$ is assigned to each agent $i$. We aim to ensure that the total power consumption of every agent $i$ does not exceed its predefined budget $B_{T}^{i}$, that is, $\\sum_{t=1}^{T}c_{t}^{i}(a_{i}(t))\\le B_{T}^{i}$, where $a_{i}(t)$ is the action taken by agent $i$ at time $t$. We believe that incorporating this concept of long-term constraints into our model can extend our algorithms to accommodate energy cost constraints, thereby improving their real-world deployability.\n\n---\n**References**\n\n- W. Chen, W. Zhang, and H. Zhao. Gradient method for continuous influence maximization with budget-saving considerations. AAAI 2020\n\n- Y. Huang, S. Zhang, L. V. S. Lakshmanan, W. Lin, X. Xiao, and B. Tang. Efficient and effective algorithms for a family of influence maximization problems with a matroid constraint. Very Large Data Bases(VLDB) 2024\n\n- S. Mitra, M. Feldman, and A. Karbasi. Submodular+ concave. NeurIPS, 2021\n\n- A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 2017\n\n- G. Nie, V. Aggarwal, and C. Quinn. Gradient methods for online dr-submodular maximization with stochastic long-term constraints. NeurIPS, 2024\n\n- O. Sadeghi and M. Fazel. Online continuous dr-submodular maximization with long-term budget constraints. AISTATS, 2020\n\n- M. Streeter, D. Golovin, and A. Krause. Online learning of assignments.NeurIPS, 2009.\n\n- L. Sun, W. Huang, P. S. Yu, and W. Chen. Multi-round influence maximization. KDD, 2018\n\n- J. Zhu, Q. Wu, M. Zhang, R. Zheng, and K. Li. Projection-free decentralized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research, 2021\n\n- P. Zuo, Y. Wang, and S. Tang. Regularized online dr-submodular optimization. UAI, 2023"}, {"review_id": "BOkzIVk4xf", "reviewer": "Reviewer_EsTn", "summary": "This paper addresses the multi-agent online coordination (MA-OC) problem where multiple agents jointly select actions to maximize a time-varying, submodular or weakly submodular reward function under combinatorial constraints. The authors introduce a new relaxation called the policy-based continuous extension and develop two algorithms:\n\n- MA-SPL: An online learning algorithm with tight approximation ratios for monotone submodular, weakly submodular, and weakly DR-submodular objectives. \n\n- MA-MPL: A parameter-free variant that does not require knowledge of problem-specific constants (like curvature or weak submodularity parameters), yet still achieves similar performance.\n\nThe algorithms come with theoretical dynamic $\\rho$-regret bounds and approximation guarantees. Empirical evaluations on multi-target tracking scenarios demonstrate that both methods outperform existing baselines.", "questions": "- Regarding the first point in weakness about the assumption on local feedback oracles, could the authors explain and discuss how the oracle can exactly and effectively model the limitation of UAV's perception range (Lines 106--110) and how such oracles might be realized and learned in practice?\n\n- Could the authors elaborate on the practical implications of the increased communication complexity of MA-MPL compared to MA-SPL? Are there specific real-world scenarios where this trade-off would make MA-MPL less desirable despite its parameter-free nature?\n        \n- The authors claim that the approximation ratio achieved by the algorithms MA-SPL and MA-MPL is tight. \n    Can the authors comment on the tightness of the regret bound achieved by MA-SPL and MA-MPL as well? \n\n- The authors claim that ``new techniques are required to verify Theorem 3'' (Line 284). \n    Can the authors briefly summarize the new techniques required in the proof for Theorem 3? \n\n- In Figures 1(d)--1(f), the x-axis \"Time Step\" goes up to $500$, and the average utility does not seem to converge, nor the curves tend to become flat. \n    By contrast, in Figure 1(a)-1(c), the time step goes up to 1200, and the average utility converges to a steady value. \n    Is there a specific reason why the authors did not use a larger time scale and let the average utility converge for Figures 1(d)--1(f)?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The introduction of the novel ``policy-based continuous extension'' is a significant contribution. Its ability to provide a lossless rounding scheme for weakly submodular functions (not just submodular ones) is a clear advantage over traditional existing multi-linear extensions and addresses a critical limitation in the field. \n- Theoretical guarantees are strong and tight. The paper provides rigorous theoretical analysis for both MA-SPL and MA-MPL algorithms, demonstrating near-optimal approximation ratios and dynamic regret bounds. \n- The parameter-free MA-MPL algorithm is novel. The development of the MA-MPL algorithm to eliminate the dependence on possibly unknown parameters (such as $\\alpha$, $\\beta$, $\\gamma$) is also practical.  In real-world scenarios, these parameters are often difficult to estimate, making the parameter-free approach a valuable direction to study.\n- Overall, the manuscript is overall nicely written and easy to follow. Moreover, the theoretical analysis is rigorous, and the proofs look correct and sound, built upon existing results and tools on submodular optimization and online optimization. \n\nWeaknesses\n\n- The most significant weakness and largest concern with this paper lies in the assumption on access to a local feedback oracle. The paper assumes access to local marginal feedback oracles $ \\mathcal{Q}_{i}^{t} $ for marginal gains which are further to be used for calculating surrogate gradients (Lines 111--115). While the authors claim that such a local marginal feedback oracle is ``common'' (Lines 116--118), and it is used as a core assumption in [111] cited by the authors, which is the work of this manuscript built upon, more discussions on how the oracles are connected to real-world scenarios and used to model them (for example, how the limitation of UAV's perception range can be captured by and modeled as local marginal feedback oracles, and possibly with one more concrete example beyond UAVs) and how such oracles might be realized and learned in practice (instead of merely citing [23]) would be helpful and could enhance clarity for a broader audience.\n- Although the novelty of the manuscript is acknowledged, it seems to me that the novelty of the parameter-dependent algorithm MA-SPL is rather limited. The algorithm mostly follows the structure of the algorithm MA-OSEA in [111] and inherits the results from it, such as action sampling, information exchange, information aggregation, surrogate gradient estimation and policy update. The only difference is the use of policy-based continuous extension instead of multi-linear extensions. Hence, the framework of the algorithm MA-SPL overall isn't entirely novel, a fact that should be clearly acknowledged in the manuscript. \n- While the algorithm MA-MPL is parameter-free, the paper acknowledges that it ``typically incurs greater communication complexity'' (Line 1505 and Table I) in the order of $\\mathcal{O}(T^{5/2})$. Although it states future work will explore reducing this, a more in-depth discussion or initial analysis of this complexity compared to MA-SPL or other methods would strengthen the paper. It is also worthwhile to highlight the trade-off between a parameter-free algorithm and a greater running time in the manuscript. \n- The experimental validation is limited to simulated environments for UAV target tracking. \n    Evaluation on real-world systems or physical hardware (e.g., robotic coordination) would strengthen the empirical claims and showcase practical viability. Moreover, for weakly submodular objectives (Figure 1d-1f, Appendix A.2), the comparison is primarily against a random baseline, which seems to be a weak and low benchmark. While the authors state that no previous work explores MA-OC with weakly submodular objectives (Line 836), it would be beneficial to discuss if there are any offline weakly submodular maximization algorithms that could conceptually be adapted or contrasted (even if not directly online) to provide more context for the performance of the proposed algorithm.", "was_revised": true, "final_justification": "1. This paper introduces new algorithms for multiagent online coordination, with nice theoretical results. \n2. The techniques used meaningfully extend prior works on submodular optimization, and while I had some minor concerns about the practicality of their algorithms, the rebuttals have convinced me that the contributions are significant. \n3. Most of the other reviewers also shared similar sentiments, and I think the only major 'unresolved' issue is that of the performance measure (dynamic regret) analyzed in this paper. However, I think finding a more suitable performance measure for the online coordination problem probably warrants another paper on its own, and I am thus happy to maintain my score for the current paper.", "rebuttal": "Thank you very much for your careful reading and insightful suggestions. We are grateful for the time and effort you have dedicated to reviewing our manuscript. In what follows, we will address some of your concerns in  `Questions`.\n\n---\n>`Question1`: Regarding the first point in weakness about the assumption on local feedback oracles, could the authors explain and discuss how the oracle can exactly and effectively model the limitation of UAV's perception range (Lines 106--110) and how such oracles might be realized and learned in practice?\n---\nThank you very much for your question. \n\nIn practical scenarios, beyond the online decision-making process discussed in this paper, each agent $i\\in\\mathcal{N}$ generally utilizes its own observations and those of neighboring agents, denoted as $\\Theta_{t}(i)$, to estimate the set objective function $f_{t}(S)$. However, due to the limitations of local information $\\Theta_{t}(i)$, the obtained set function estimation $f_{t}(\\cdot|\\Theta_{t}(i))$ often fails to accurately predict the marginal contributions of agents  $j\\in\\mathcal{N}$ that are far from agent $i$. To address this issue and simultaneously reduce the accumulation of learning errors, each agent $i$ is often permitted to use $f_{t}(\\cdot|\\Theta_{t}(i))$ for approximating its own actions' marginal contributions. This is why we adopt a local feedback assumption for each agent  $i$. \n\nIt is worth noting that, in the local feedback model, we overlook the approximation errors of $f_{t}(\\cdot|\\Theta_{t}(i))$ and suppose that each $f_{t}(\\cdot|\\Theta_{t}(i))$ can unbiasedly or accurately estimate the marginal contributions of agent $i$. Similar to [23], we also incorporate prediction errors into our regret bound analysis. We leave this for future research.\n\n Below, we provide a practical example of how to achieve these local feedback oracles. Consider the scenario in [83] where multiple satellites monitor a set of locations on Earth. Suppose there are $M$ locations labeled as $[M]$ and $n$ satellites denoted as $[n]$. At each time step $t\\in[T]$, each satellite $i$ selects $k$ locations from its feasible locations $L_{i}\\subseteq[M]$ to monitor, where the monitoring quality of each location $j$ is determined by the current video resolution $o^t_j(i)$ \nprovided by satellite $i$. Additionally, we assume that the monitoring effectiveness of each location depends only on the highest resolution of satellites monitoring This leads to the following submodular set objective function: $f_t(S)=\\sum_{j=1}^{M}\\max_{i\\in U_j(S)}o^t_j(i)$ where $S\\subseteq[n]\\times[M]$ represents the pairing of satellites and locations and $U_{j}(S)$ denotes the set of satellites monitoring location $j$ under $S$. It is important to note that each decision made by satellite $i$ only affects location $j\\in L_{i}$. In other words, if the communication graph allows satellites with overlapping monitoring ranges to exchange their decisions and resolution values $o^{t}_{j}(i)$ (see Fig. 1 in [83]), then each satellite $i$ can precisely calculate the marginal contribution of its own actions throughout simple arithmetic and maximization operations.  It is worth noting that, in this case, satellite $i$ cannot estimate the contributions of satellites without overlapping monitoring ranges.\n\n---\n> `Question2`: Could the authors elaborate on the practical implications of the increased communication complexity of MA-MPL compared to MA-SPL? Are there specific real-world scenarios where this trade-off would make MA-MPL less desirable despite its parameter-free nature?\n\n---\nThanks for your question. \n\nIt is worth noting that, in  Line 9 of **MA-SPL** algorithm, we require prior knowledge of the ratios $\\alpha,\\beta,\\gamma$ to set the weight function $w(z)$. However, according to the definitions of weak submodularity and weak DR-submodularity, we know that accurately computing these parameters generally  involves exponential computations.\n\nThus, the core of our proposed **MA-MPL** algorithm aims to overcome scenarios where obtaining the structural parameters $\\alpha,\\beta,\\gamma$ is very difficult. Specifically, **MA-MPL** algorithm uses an additional $O(\\sqrt{T})=O(\\frac{T^{3/2}}{T})$ times communication complexity and $O(T^{3/2})=O(\\frac{kT^{5/2}}{kT})$ times  query complexity to avoid the exponential computations required for the ratios $\\alpha,\\beta,\\gamma$ inherent in **MA-SPL** algorithm. \n\nFrom our previous description, we know that when the computational cost of the ratios $\\alpha,\\beta,\\gamma$ is significantly lower than the additional $O(\\sqrt{T})$ times communication overhead and $O(T^{3/2})$ times function evaluations, **MA-MPL** becomes less desirable than **MA-SPL**. For instance, in Figure 1(a)-1(c) where we know $\\alpha=\\beta=\\gamma=1$, parameter-dependent **MA-SPL** algorithm can achieve a better average reward with only $1/15$ of the function evaluations of parameter-free MA-MPL algorithm. (Note that this ratio $1/15$ is derived from the setups in Appendix A.3, where **MA-SPL** uses $10$ batches of stochastic estimation, while **MA-MPL** employs 10 batches of stochastic estimation for each of $15$ online linear maximization oracles.)\n\n---\n>`Question3`: The authors claim that the approximation ratio achieved by the algorithms **MA-SPL** and **MA-MPL** is tight. Can the authors comment on the tightness of the regret bound achieved by **MA-SPL** and **MA-MPL** as well?\n---\nThank you for your question. \n\nIt is important to note that when our objective function  $f_{t}$ is submodular and its curvature $c\\rightarrow0$, the $f_{t}$ will degenerate into a modular function, that is, $f_{t}(\\cup_{i=1}^{n}a_{i})=\\sum_{i=1}^{n}f_{t}(a_{i})$. According to Definition 1, in this case, our proposed policy-based continuous extension $F_{t}$ will become a continuous **linear** function. From the classic theory of online linear optimization(OLO),  it is well-known that the $\\mathcal{O}(\\sqrt{T})$-regret bound  is optimal for general OLO problems, which also implies the optimality of the regret bounds of our proposed **MA-SPL** and **MA-MPL** algorithms with respect to the dependence on the time horizon $T$.\n\nIn addition, we observe that the regret bounds of the **MA-SPL** and **MA-MPL** algorithms are also highly dependent on the topology of the communication graph $G$, such as the spectral gap $\\tau$ and the diameter $d(G)$. Since this paper predetermines a communication network $G$, the design of a more efficient graph $G$ is beyond our current scope. At the same time, we are aware that many studies have investigated how to identify a more efficient communication architecture for multi-agent coordination problems. For further exploration, please refer to [45,40].\n\n---\n> `Question4`: The authors claim that **new techniques are required to verify Theorem 3** (Line 284). Can the authors briefly summarize the new techniques required in the proof for Theorem 3?\n---\nThank you for your question. In the original work [109,111], the authors required the following inequality to prove their key conclusions(See Eq. (7) in [109] or Eq. (11) in [111]), that is to say,\n\\begin{equation*}\n    \\langle\\textbf{y},\\nabla G(\\textbf{x})\\rangle\\ge\\langle\\textbf{y}\\vee\\textbf{x}-\\textbf{x},\\nabla G(\\textbf{x})\\rangle\\ge G(\\textbf{y}\\vee\\textbf{x})-G(\\textbf{x}),\n\\end{equation*} where $G$ is multi-linear extension of some submodular function $f$ and $\\vee$  denotes coordinate-wise maximum operation. It is worth noting that this inequality necessitates that $\\textbf{y}\\vee\\textbf{x}$ remains within the domain of $G$ for any two feasible $\\textbf{y}$ and $\\textbf{x}$. However, the domain $\\prod_{i=1}^{n}\\Delta_{k_{i}}$ of our proposed policy-based continuous extension $F_t$ does not meet this requirement.\n\nTo overcome this limitation, we have developed two new inequalities for our proposed policy-based continuous extension  $F_t$  in our paper, that is,\n\n**a)**: when $f_{t}$ is monotone $\\alpha$-weakly DR-submodular, the following inequality holds:\n\\begin{equation*}\n\t\\alpha\\Big(f_{t}(S)-F_{t}(\\uppi_{1},\\dots,\\uppi_{n})\\Big)\\le\\langle1_{S},\\nabla F_{t}(\\uppi_{1},\\dots,\\uppi_{n})\\rangle,\n\\end{equation*} where  $S$ satisfies the constraints of problem (1) and the symbol $1_{S}$ represents the indicator function over the subset $S\\subseteq V$, namely, for any action $v_{i,m}\\in S$, the vector $1_{S}$ sets the corresponding probability for this action $v_{i,m}$ as $1$;\n\n**b)**: when $f_{t}$ is monotone $(\\gamma,\\beta)$-weakly submodular, we can show that\n\\begin{equation*}\n\t\\Big(\\gamma^{2}f_{t}(S)-(\\beta(1-\\gamma)+\\gamma^{2})F_{t}(\\uppi_{1},\\dots,\\uppi_{n})\\Big)\\le\\langle 1_{S},\\nabla F_{t}(\\uppi_{1},\\dots,\\uppi_{n})\\rangle.\n\\end{equation*}\n\n---\n>`Question5`: In Figures 1(d)-1(f), the x-axis ``Time Step\" goes up to 500, and the average utility does not seem to converge, nor the curves tend to become flat. By contrast, in Figure 1(a)-1(c), the time step goes up to 1200, and the average utility converges to a steady value. Is there a specific reason why the authors did not use a larger time scale and let the average utility converge for Figures 1(d)-1(f)?\n---\nThanks for your question.\n\n We sincerely apologize for any confusion caused by the different time step scales used in Figures 1(a)-1(c) and Figures 1(d)-1(f). In Figures 1(d)-1(f), due to the unknown diminishing-return(DR) ratio $\\alpha$, we employed a brute-force $0.1$-network search to identify the optimal parameter setups. Consequently, in sharp contrast to Figures 1(a)-1(c), we needed to conduct additional $50$ experiments (each repeated five times). To save total computational time, we therefore adopted a smaller time step of 500 in Figures 1(d)-1(f).\n\nWe deeply appreciate you pointing out this limitation in our experimental design. To ensure that the curves in Figures 1(d)-1(f) become flat or converge, we will extend the time steps of these experiments in our final manuscript version."}, {"review_id": "oMsjWCqouV", "reviewer": "Reviewer_fXn2", "summary": "This paper deals with a multi-player cooperative online learning problem with monotone submodular or non-submodular objectives. The ground set is partitioned into $n$ groups, and each player $i \\in [n]$ chooses one element from the $i$th group in each round. The goal is to upper-bound on approximate dynamic regret with approximation ratio $\\rho$. The paper's contributions are three-fold. The first one is to introduce a generalization of the multilinear extension, which they call policy-based continuous extension. The second one is to apply the boosting technique to improve the approximation ratio (for example, to $1-c/e$ for monotone submodular functions with curvature $c$). The third one is to combine this offline technique with existing dynamic regret minimization algorithms to obtain dynamic regret upper bounds. The proposed algorithm are also empirically validated.", "questions": "Please see the weaknesses discussed above. If my understanding contains serious mistakes, I would be happy to reconsider my score. For example, the proposed multilinear extension is essentially different from existing ones, I would appreciate your clarifications.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Among this paper's contributions, the boosting technique is most interesting to me. This was originally proposed by Zhang, Deng, Chen, Hu, and Yang in ICML 2022 for continuous submodular maximization. This method designs an optimal weight and maximizes a surrogate function that is the weighted average of the objective function. This paper applies the boosting technique to curvature-bounded submodular functions, $\\gamma$-weakly DR-submodular functions, and $(\\gamma, \\beta)$-weakly submodular functions to obtain good approximation ratio guarantees.\n- The problem setting of multi-agent online coordination is interesting and opens the door to new applications of submodular maximization, although it was already proposed in Zhang, Wan, Yang, Shen, and Tao in ICLR 2025. If the authors provided more practical applications in which parameters $c$, $\\gamma$, and $\\beta$ can be bounded, the significance of this paper is clearer.\n\n---\nWeaknesses:\n- I am not a big fan of the concept of approximate regret. Since the solution in each round can exceed the approximation ratio $\\rho$, theoretical guarantees on approximate regret do not really represent the \"regret\" for not playing the optimal action in hindsight. It just guarantees convergence of the approximation ratio of the total reward in hindsight. This paper considers dynamic regret, and its interpretation is more complicated.\n- The authors claim that the policy-based continuous extension is their contribution. This is a generalization of the multilinear extension to partition matroid constraints (or $k$-submodular functions in context). However, the same idea already appeared in existing papers. For example, Sahin, Bian, Buhmann, and Krause called it \"generalized multilinear extension\" and used it for submodular maximization on the integer lattice. Wang and Zhou used in ArXiv 2021 paper for $k$-submodular maximization.\n- I understand that all the factors of this paper (multi-agent coordination, dynamics regret minimization, and the boosting technique) are independently interesting to some extent, but these combinations make the paper complicated and blur the paper's focus in my opinion.", "was_revised": true, "final_justification": "I do not change the score from the initial review. I hope the points I raised were addressed in the revised version.", "rebuttal": "Thank you very much for your careful reading and constructive feedback. We are grateful for the time and effort you have dedicated to reviewing our manuscript. In what follows, we will address some of your concerns in `Weaknesses`.\n\n---\n> `Weakness1`: I am not a big fan of the concept of approximate regret. Since the solution in each round can exceed the approximation ratio $\\rho$, theoretical guarantees on approximate regret do not really represent the ``regret\" for not playing the optimal action in hindsight. It just guarantees convergence of the approximation ratio of the total reward in hindsight. This paper considers dynamic regret, and its interpretation is more complicated.\n---\nThank you for your insightful comments. We fully agree with your viewpoint. \n\nRecently, after reading the work[Tajdini et al., 2024], we also realize that the $\\rho$-Regret is not be a perfect metric for online (weakly) submodular maximization problem, as the rewards or solutions obtained in each round can indeed surpass the predefined approximation ratio $\\rho$. The primary reason why we adopt the dynamic $\\rho$-Regret in this paper is to maintain consistency with the previous studies [Xu et al., 2023b,a, Zhang et al., 2025].\n\n---\n> `Weakness2`: The authors claim that the policy-based continuous extension is their contribution. This is a generalization of the multilinear extension to partition matroid constraints (or $k$-submodular functions in context). However, the same idea already appeared in existing papers. For example, Sahin, Bian, Buhmann, and Krause called it \"generalized multilinear extension\" and used it for submodular maximization on the integer lattice. Wang and Zhou used in ArXiv 2021 paper for $k$-submodular maximization.\n---\nThank you for your detailed feedback.\n\nWe agree with your perspective. If each agent has an action set of the **same** size, that is, $V_{i}=(v_{i,1},\\dots,v_{i,k})$ and we represent the decision of all $n$ agents as a lattice vector $\\mathbf{s}=(s_{1},\\dots,s_{n})$ where $s_{i}\\in(0,1,\\dots,k)$ stands for the $i$-th agent choosing action $v_{i,s_{i}}$ (with $s_{i}=0$ denoting the null action $\\emptyset$), then the multi-agent coordination problem (1) in our paper can be transformed as a lattice function maximization problem: $\\max_{\\mathbf{s}\\in(0,\\dots,k)^n}c_{t}(\\mathbf{s})$ where $c_{t}(\\mathbf{s})=f_{t}(\\cup_{i=1}^{n}\\{v_{i,s_{i}}\\})$ and each $v_{i,0}$ represents $\\emptyset$. Under this reformulation, the continuous extension introduced in [Sahin et al., 2020, Zhou et al., 2025] is indeed equivalent to the policy-based continuous extension in this paper. \n\nSince our proposed policy-based continuous extension was primarily inspired by concepts from multi-agent cooperative game [Albrecht et al., 2024, Zhang et al., 2021], we are grateful for your highlighting of these relevant works in another field regarding lattice submodular or k-submodular maximization that we had previously overlooked. We will incorporate them into the final version of our manuscript. Furthermore, we also want to emphasize that there exist notable **differences** between our work and the prior studies[Sahin et al., 2020, Zhou et al., 2025] about lattice function or $k$-submodular maximization.\n\n**a)** The lattice formulation typically requires an **order relationship** among different actions of the same agent.  For instance, in the facility location problem, each action  $v_{i,j}$ usually represents a sensor with a coverage radius of $j$ placed at location  $i$ and thus we know $v_{i,k}\\ge v_{i,k-1}\\dots\\ge v_{i,1}$. In other words, the sensor with a coverage radius of $j$ is better than that with radius of $k$ when $k<j$. However, in our multi-agent coordination problem, we do not impose any specific **order relationship** on the decisions space. Without this predefined order, we even cannot ensure that the aforementioned $c_{t}(\\mathbf{s})$ is a lattice submodular or $k$-submodular function over the domain $(0,\\dots,k)^n$ when $f_{t}$ is submodular.  It is worth noting that the definition of lattice submodular or $k$-submodular function typically requires an order relationship for coordinate-wise maximum and minimum operations.  As a result, we think the results and algorithms of [Sahin et al., 2020, Zhou et al., 2025]  are not directly applicable to our scenario, despite the equivalence in the underlying continuous extension.\n\n**b)** In addition to submodularity, our paper also considers the unexplored weak submodularity and allows for varying sizes of action sets among agents.\n\n**(We apologize for not having located the Wang and Zhou paper from 2021 on ArXiv regarding $k$-submodular maximization. However, we have found a similar work [Zhou et al., 2025]. But we are unsure if this is the paper Reviewer fXn2 mentioned.)**\n\n---\n> `Weakness3`: I understand that all the factors of this paper (multi-agent coordination, dynamics regret minimization, and the boosting technique) are independently interesting to some extent, but these combinations make the paper complicated and blur the paper's focus in my opinion.\n\n---\nThanks for your constructive suggestions.  We agree that the combination of multiple factors complicates our paper. To better highlight the core of multi-agent coordination, we plan to provide more specific details about multi-target tracking in the numerical experiments in the final version. Meanwhile, we will offer more in-depth explanations and motivations regarding our proposed  **MA-SPL** and **MA-MPL** algorithms in Section 5.2.\n\n---\n**References**\n\n- S. V. Albrecht, F. Christianos, and L. Schafer. Multi-Agent Reinforcement Learning: Foundations and Modern Approaches. MIT Press, 2024.\n\n- A. Sahin, Y. Bian, J. Buhmann, and A. Krause. From sets to multisets: provable variational inference for probabilistic integer submodular models. ICML 2020\n\n- A. Tajdini, L. Jain, and K. G. Jamieson. Nearly minimax optimal submodular maximization with bandit feedback. NeurIPS, 2024\n\n- Z. Xu, X. Lin, and V. Tzoumas. Bandit submodular maximization for multi-robot coordination in unpredictable and partially observable environments. Robotics: Science and Systems(RSS), 2023a.\n\n- Z. Xu, H. Zhou, and V. Tzoumas. Online submodular coordination with bounded tracking regret: Theory, algorithm, and applications to multi-robot coordination. IEEE Robotics and Automation Letters(RAL),  2023b\n\n- K. Zhang, Z. Yang, and T. Basar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321–384, 2021.\n\n- Q. Zhang, Z. Wan, Y. Yang, L. Shen, and D. Tao. Near-optimal online learning for multi-agent submodular coordination: Tight approximation and communication efficiency. ICLR 2025\n\n- **H. Zhou, L. Huang, and B. Wang. Improved approximation algorithms for $k$-submodular maximization via multilinear extension.  ICLR 2025**"}]

Author rebuttal:

Meta-review: This paper introduces two algorithms for multi-agent online coordination based on a new policy-based continuous extension. The work is supported by strong theoretical results, rigorous proofs, and the practical value of a parameter-free algorithm (MA-MPL). Reviewers highlighted these strengths while also pointing to some concerns about assumptions (disjoint action sets, oracle access), limited novelty for MA-SPL, higher communication cost of MA-MPL, and the lack of real-world experiments. During rebuttal, the authors clarified these points, and reviewers acknowledged the responses and provided final justifications for the reviews. Overall, the review process was thorough, and there is consensus that the contributions are solid and impactful. 

The only remaining issue after the panel discussion is the use of dynamic \(\rho\)-regret as a suitable performance measure in this section. To address this, the panel would like to request from the authors to add a short discussion in the camera-ready version of their paper highlighting the points that were raised during the rebuttal discussion and, in particular, with Reviewer fXn2; namely that \(\rho\)-Regret may not be a perfect metric for online (weakly) submodular maximization problem, as the rewards or solutions obtained in each round can indeed surpass the predefined approximation ratio, explaining also the reasons why this is used in the current paper.
Decision: Accept (poster)