acceptodds
Under review as a conference paper at ICLR 2027

Distributed Policy Learning for Online Submodular Maximization over Time-Varying Directed Graphs

Abstract

This paper investigates the online submodular maximization problem for multi-agent systems over time-varying directed communication networks. At each round, multiple agents collaboratively maximize a time-varying monotone submodular utility function using only local information, and without prior knowledge of future objectives. This setting has wide applications including multi-robot target tracking, client selection in federated learning, and distributed information fusion in the dynamic environment. Existing approaches, such as OSG and MA-OSMA, typically rely on fixed and connected graphs, which limits their applicability to networks with asymmetric communication and intermittent connectivity arising from packet losses and communication link failures. To address these limitations, we propose a Push-Sum Online Surrogate Mirror Ascent (POSMA) algorithm which utilizes a multilinear extension to transform the original discrete problem into a continuous optimization problem. A push-sum mechanism is further incorporated to compensate for the aggregation bias. Under the B-strongly connected communication, we theoretically confirm that the algorithm achieves an approximation ratio of with an average dynamic regret, where bounds the curvature of all objective functions. Moreover, we quantitatively characterize how network connectivity degradation slows the agreement rate and therefore increases online submodular regret by establishing the regret bound , where represents the cumulative variation of the optimal action sets, and characterizes the rate of agreement related to the jointly connected bound . Finally, we conduct simulations of multi-target tracking to demonstrate the effectiveness of the proposed algorithm and show the benefits compared with the baseline algorithm under fixed and time-varying communication graphs.

Primary area:
optimization
Keywords:
Online submodular maximization, Multi-agent, Time-varying digraphs, Policy learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_5yp4OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies multi-agent online monotone submodular maximization over time-varying directed communication graphs. The authors propose POSMA, which replaces doubly stochastic consensus with push-sum aggregation over column-stochastic matrices and rescales the Bregman term of the local mirror-ascent update by the push-sum weight, in order to correct the aggregation bias caused by directed communication. Under B-strong connectivity, POSMA retains the curvature-dependent approximation ratio of MA-OSMA and attains a dynamic regret bound that depends on network connectivity and on the variation of the optimal action sets, and is sublinear whenever this variation grows sublinearly; a consensus error bound is also provided. Experiments on simulated multi-target tracking compare POSMA with MA-OSMA, MA-OSEA, and OSG, and examine the effects of the connectivity parameter B and the curvature bound.

Critical strengths
  1. The paper extends online multi-agent submodular coordination from static undirected graphs with doubly stochastic weights to B-strongly connected time-varying directed graphs, in which individual rounds may be disconnected. The communication weights can be constructed using only the out-degree of each agent, without requiring balanced or undirected communication, which makes the method easy to deploy.

  2. The paper provides an explicit dynamic regret bound (Theorem 1) and a consensus error bound (Theorem 2), with detailed proofs of the supporting Lemmas and Theorems in the appendix.

Critical weaknesses
  1. The main components of POSMA come from MA-OSMA and the push-sum analysis of Nedić and Olshevsky [1]. Extending consensus-based methods to time-varying directed graphs via push-sum is an established route, and Zhang et al. [2] also list it as a future direction in their conclusion. Remark 3 outlines the ingredients introduced for this purpose (agreement over successive rounds, push-sum normalization, and a weighted Bregman potential), but does not explain which of these steps cannot be handled by existing push-sum analyses. In addition, the rate stated in the abstract omits the lower-order term retained in Eq. (76). As the authors note after Eq. (76), the hidden constants depend on the minimum push-sum weight, for which Lemma 9 only guarantees a lower bound that is exponentially small in the number of agents and in B. The claim that the bound quantitatively characterizes the effect of connectivity degradation should therefore be stated more carefully.

  2. The regret curves in Fig. 4 (Appendix E.1) require the optimal utility at every round, but the paper does not explain how this value is obtained, although the per-round problem is NP-hard (Section 2.2) and the joint action space is far too large for enumeration. Moreover, Appendix A assumes that the objective sequence is fixed independently of the algorithmic randomness, whereas in the tracking experiments the utility depends on agent positions determined by past actions, and adversarial targets react to approaching agents (Zhang et al., [2]; Appendix E.4). The experiments also lack an ablation of the two algorithmic modifications.

[1] Angeli aNedić and Alex Olshevsky. Distributedoptimizationover time-varyingdirectedgraphs. IEEE Transactionson Automatic Control, 60(3): 601–615,2015

[2] Qixin Zhang, Zongqi Wan, YuYang, LiShen, and DachengTao. Near-optimalonlinelearning for multi-agent submodular coordination: Tight approximation and communication efficiency. In The Thirteenth International Conference on Learning Representations, 2025.

Questions for authors
  1. Novelty. Is there a step in the analysis where the standard push-sum analysis of Nedić and Olshevsky (2015) [1] cannot be applied directly, for example, due to the coupling between the push-sum weights and the Bregman term? If so, please point to the corresponding lemma. Is the rescaled Bregman coefficient (Remark 2) necessary, and how does POSMA perform without it?

  2. Optimal value in Fig. 4. How was the per-round optimal utility computed? If an approximation was used, how should the reported regret be interpreted?

  3. Theory versus experiments. Does the current analysis cover objectives that depend on past actions? If not, should the experiments be understood as an empirical evaluation beyond the theoretical setting?

  4. The authors may consider adding experiments on a non-tracking task, or with a larger number of agents, to examine the generality of the method.

[1] Angeli aNedić and Alex Olshevsky. Distributedoptimizationover time-varyingdirectedgraphs. IEEE Transactionson Automatic Control, 60(3): 601–615,2015

7 comments

Thank you for spending so much time to review our work and give so many constructive suggestions. We have carefully read the comments and revised the manuscript. Our responses to weaknesses and your questions are listed as follows. We greatly appreciate your time and constructive advises to enhance the quality of the manuscript.


Weaknesses:


W1.1. The main components of POSMA (DOSMA-PS in the revised manuscript) come from MA-OSMA and the push-sum analysis of Nedić and Olshevsky [1]. Extending consensus-based methods to time-varying directed graphs via push-sum is an established route, and Zhang et al. [2] also list it as a future direction in their conclusion. Remark 3 outlines the ingredients introduced for this purpose (agreement over successive rounds, push-sum normalization, and a weighted Bregman potential), but does not explain which of these steps cannot be handled by existing push-sum analyses.

Thank you for your comments. We agree that Push--Sum is an established communication mechanism under unbalanced or directed topologies and Lemmas 1--5 and 8 are from MA-OSMA [1]. However, extending this framework to ongoing policy learning under time-varying BB-strongly connected digraphs requires addressing three main challenges. (a) Bounding policy disagreement during online learning. Local policy updates continue even when communication is intermittent. The challenge is to bound how the disagreement effects accumulate as they propagate under time-varying directed graphs. (b) Addressing local update perturbations in the weighted policy iteration. Each local update enters the iteration multiplied by a time-varying Push--Sum weight. The step size must account for this weight to obtain a uniform bound on each agent's weighted perturbation. (c) Preserving the approximation factor in the dynamic regret analysis. Time-varying directed aggregation yields weighted Bregman bounds, while the surrogate gradient inequality requires an unweighted sum of gradient inner products. Specifically, the following points explain how we address each challenge.

1. Including update residuals in policy exchange in the agreement analysis. In our setting, each agent performs a local mirror ascent step on a surrogate objective, then aggregates the resulting policies (probability distributions). However, under intermittent connectivity, agents generally maintain different estimates of the global policy, including probability distributions of the actions for other agents. Moreover, these estimates also change after each local optimization step, so a consensus-only iteration does not fully describe their evolution. To solve this problem, in contrast to the basic Push--Sum mechanism, we include the update residual in the next weighted policy estimate, qt+1,i=wt+1,ixt+1,i=∑j[A(t)]ijqt,j+wt+1,irt+1,i,\mathbf q_{t+1,i}=w_{t+1,i}\mathbf x_{t+1,i}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+w_{t+1,i}\mathbf r_{t+1,i}, where rt+1,i=xt+1,i−yt+1,i\mathbf r_{t+1,i}=\mathbf x_{t+1,i}-\mathbf y_{t+1,i} measures the difference between the updated policy estimate xt+1,i\mathbf x_{t+1,i} and aggregated policy estimate yt+1,i\mathbf y_{t+1,i}. The weighted residual wt+1,irt+1,iw_{t+1,i}\mathbf r_{t+1,i} therefore represents the perturbation introduced by ongoing local learning. Without wt+1,irt+1,iw_{t+1,i}\mathbf r_{t+1,i}, the agreement error would omit continued local learning. We instead track both the propagation of the initial policy estimates and the accumulated effects of these perturbations.

2. Scaling local steps to time-varying directed graphs. The changing weights can amplify or suppress the influence of local surrogate gradient estimates. We use ηt/wt+1,i\eta_t/w_{t+1,i} instead of ηt\eta_t in MA-OSMA [1]. When wt+1,i>1w_{t+1,i} > 1, the smaller step prevents the larger message weight from giving the local gradient excessive influence. When wt+1,i<1w_{t+1,i} < 1, the larger step compensates for the smaller weight, which would otherwise weaken the local gradient influence. For ψ(x)=12∣x∣22\psi(\mathbf x)=\frac12\\|\mathbf x\\|_2^2, the same reference and gradient, and inactive probability constraints under both steps,

& \mathbf q_{t+1,i}^{\mathrm{scaled}}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+\eta_t\mathbf g_{t,i},\\\\ & \mathbf q_{t+1,i}^{\mathrm{unscaled}}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+\eta_tw_{t+1,i}\mathbf g_{t,i}. \end{aligned}$$ The adjusted step prevents the additional multiplication of $\mathbf g_{t,i}$ by $w_{t+1,i}$. For general probability-constrained updates, Lemma 7 gives $w_{t+1,i}\mathbb E\\|\mathbf r_{t+1,i}\\|\le G\eta_t$, controlling local updates in the agreement analysis.

3. Technical difficulties in dynamic regret analysis. With the fixed symmetric doubly stochastic matrix in MA-OSMA [1], for u∈C\mathbf u\in\mathcal C,

\le\frac1{\eta_t}[\sum_iD_\psi(\mathbf u,\mathbf x_{t,i})-\sum_iD_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ The unweighted inner products bound dynamic $\alpha$-regret through the surrogate gradient inequality. For time-varying directed graphs, the bound instead involves weights from consecutive rounds, $$\sum_i\langle\mathbf g_{t,i},\mathbf u-\mathbf x_{t+1,i}\rangle \le\frac1{\eta_t}[\sum_iw_{t,i}D_\psi(\mathbf u,\mathbf x_{t,i})-\sum_iw_{t+1,i}D_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ Weighting the original local inequalities would also reweight the left-hand side. To address this difficulty, Lemma 12 uses the mirror ascent inequality with coefficient $w_{t+1,i}/\eta_t$, $$\langle\mathbf g_{t,i},\mathbf u-\mathbf x_{t+1,i}\rangle \le\frac{w_{t+1,i}}{\eta_t}[D_\psi(\mathbf u,\mathbf y_{t+1,i})-D_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ Substituting $\sum_iw_{t+1,i}D_\psi(\mathbf u,\mathbf y_{t+1,i})\le\sum_iw_{t,i}D_\psi(\mathbf u,\mathbf x_{t,i})$ into the summed local bounds gives the second inequality. The differences now involve consecutive rounds, allowing telescoping and accounting for changing optimal action sets in Lemma 13 without reweighting the gradient inner products. In summary, the technical contribution is to control weighted policy updates and connect weighted Bregman differences across rounds without reweighting the surrogate gradient inner products. The resulting guarantees retain the approximation ratio and the dependence on $T$ and $C_T$ for executed joint action sets under more general graph conditions. [1] 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*, 2025b. ---

W1.2. In addition, the rate stated in the abstract omits the lower-order term retained in Eq. (76). As the authors note after Eq. (76), the hidden constants depend on the minimum push-sum weight, for which Lemma 9 only guarantees a lower bound that is exponentially small in the number of agents and in B. The claim that the bound quantitatively characterizes the effect of connectivity degradation should therefore be stated more carefully.

Thank you for your comments. The abstract reports the leading rate for fixed parameters, while the complete finite-horizon bound in Eq. (80) retains M0,T/TM_{0,T}/T, which decays faster as TT increases and does not change the leading rate. The hidden constants retain 1/γ1/\gamma, and Lemma 9 guarantees only γ≥N−NB\gamma\ge N^{-NB}, which can be exponentially small in NN and BB. We have made both qualifications explicit and described the result as a worst-case upper bound with explicit communication dependence. To reduce additional overestimation, we improve the estimates in two cases: (i) bounding the sums over TT rounds replaces 1/[λ(1−λ)]1/[\lambda(1-\lambda)] by λ−1min⁡T,(1−λ)−1\lambda^{-1}\min\\{T,(1-\lambda)^{-1}\\} in M0,TM_{0,T} and λ−1min⁡(T−1)/2,(1−λ)−1\lambda^{-1}\min\\{(T-1)/2,(1-\lambda)^{-1}\\} in M2,TM_{2,T}; (ii) a given graph sequence yields λgraph\lambda_{\mathrm{graph}} from A(t)A(t) and its finite-horizon minimum weight γT\gamma_T. The details in Appendices A.4 and A.5 are summarized below:

(a) Improving the bound by considering only TT rounds. The refined average regret bound in Eq. (80) is E[Regα(T)]/T≤2M1M2,T/T+M0,T/T\mathbb E[\mathrm{Reg}_\alpha(T)]/T\le2\sqrt{M_1M_{2,T}/T}+M_{0,T}/T. To improve the bounds on M0,TM_{0,T} and M2,TM_{2,T}, we consider only the actual TT rounds,

\le\frac1\lambda\min\left\\{T,\frac1{1-\lambda}\right\\},$$ and $$\frac1T\sum_{t=1}^{T}\sum_{s=1}^{t-1}\lambda^{t-s-2} \le\frac1\lambda \min\left\\{\frac{T-1}{2},\frac1{1-\lambda}\right\\}.$$ Both estimates are no larger than the previous bound $1/[\lambda(1-\lambda)]$. The first inequality can reduce $M_{0,T}/T$, while the second can reduce $2\sqrt{M_1M_{2,T}/T}$ by improving the estimate of $M_{2,T}$. **(b) Refining the worst-case estimate of $\lambda$ using $A(t)$.** To obtain an estimate that better reflects the time-varying directed graphs, we examine the column-stochastic matrices $A(t)$ to determine how information propagates over successive rounds. For column-stochastic matrices, let $$P_s=A(s+L-1)\cdots A(s),\qquad \tau(P_s)=\frac12\max_{i,j}\sum_{k=1}^{N} |[P_s]_{ki}-[P_s]_{kj}|,$$ where $P_s$ represents communication over $L$ rounds, and a smaller $\tau(P_s)$ indicates better mixing of information from different agents [1]. Under the assumptions of Lemma 9 in the previous version of this paper, choose a window length $L$ with $\kappa < 1$ and define $$\kappa=\sup_s\tau(P_s),\qquad \bar\kappa=\max\left\\{\kappa,\frac1\beta\right\\}, \qquad \lambda_{\mathrm{graph}}=\bar\kappa^{1/L}.$$ Using $\phi_i(t)=w_{t+1,i}/N$, we obtain $$\left|[A(t:s)]_{ij}-\phi_i(t)\right| \le\tau(A(t:s)) \le\bar\kappa^{\lfloor(t-s+1)/L\rfloor} \le\beta\lambda_{\mathrm{graph}}^{t-s}.$$ The resulting bound has the same form as Lemma 9 and retains the original $\beta$, allowing $\lambda_{\mathrm{graph}}$ to replace the universal $\lambda$ in subsequent bounds. For a given sequence over $T$ rounds, we also calculate the weights $w_{t,i}$ and their minimum $$\gamma_T=\min_{\substack{1\le t\le T+1\\\i\in\mathcal N}}w_{t,i}\ge\gamma.$$ Here, $\gamma=\inf_{t,i}w_{t,i}$ is the original uniform lower bound. The corresponding finite-horizon bounds can use $\lambda_{\mathrm{graph}}$ and $\gamma_T$ in place of $\lambda$ and $\gamma$. The substituted coefficients $M_{0,T}^{\mathrm{graph}}$ and $M_{2,T}^{\mathrm{graph}}$ are given in Eq. (83), and the resulting regret bound and step size are given in Eqs. (86) and (85). The bound still depends on the inverse minimum weight. The guaranteed lower bound $N^{-NB}$ can be exponentially small in $N$ and $B$, and the original uniform lower bound remains available for guarantees over all rounds. For fixed parameters, $M_{0,T}/T$ decays faster than the leading contribution. We have stated the fixed-parameter qualification in the abstract and retained the complete bound in Appendix A.4. The discussions of Figures 2 and 5 distinguish utility comparisons from tests of regret scaling. We have also added experiments with $60$ and $100$ agents in Appendix B.5 (Figure 8). The revised abstract and Remark 5 clarify that the result is a worst-case regret upper bound with explicit communication dependence, not a tight prediction of actual regret. [1] Ilse C. F. Ipsen and Teresa M. Selee. Ergodicity coefficients defined by vector norms. *SIAM Journal on Matrix Analysis and Applications*, 32(1):153--200, 2011. ---
Reviewer_75raOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses a reasonable and useful extension: distributed online submodular maximization over time-varying directed graphs. However, the algorithmic contribution is largely a Push-Sum adaptation of MA-OSMA, and the theoretical novelty is concentrated in the weighted Bregman/consensus analysis rather than in the optimization method itself.

Critical strengths

S1. The problem setting is relevant. Directed, time-varying, intermittently connected communication is realistic for multi-agent systems.

S2. The paper retains the curvature-dependent approximation factor and gives an explicit communication rate λ\lambda and a consensus-error bound.

S3. The experiments cover both static undirected and time-varying directed graphs, and POSMA performs well under the latter.

Critical weaknesses

W1. The multilinear relaxation, curvature-dependent surrogate, stochastic gradient estimator, blockwise mirror updates, rounding argument, and approximation factor are inherited from the ICLR 2025 MA-OSMA work. The new contribution is primarily their integration with push-sum communication through a weight-adjusted update and corresponding weighted dynamic-regret analysis. The authors fail to sufficiently explain which technical obstacle requires a substantially new idea rather than an adaptation of existing surrogate-gradient and push-sum analyses. In particular, the approximation factor is preserved rather than improved, and the fundamental horizon/comparator-variation dependence remains similar.

W2. The λ\lambda-based bound seems too conservative. With λ=(1−N−NB)1/B\lambda = (1-N^{-NB})^{1/B}, the factor 1/λ(1−λ)1/\sqrt{\lambda(1-\lambda)} is approximately BNNB/2\sqrt{B}N^{NB/2}, or 1.86×10391.86\times 10^{39} for the experimental setting N=20N=20, B=3B=3. The authors should distinguish this worst-case connectivity guarantee from a tight characterization of network dependence, discuss the additional dependence on the minimum push-sum weight, and ideally provide sharper graph-specific estimates.

W3. Push-Sum and the B-strong-connectivity consensus analysis are also standard tools (e.g., Nedic & Olshevsky, 2015; Lee et al., 2017). There are some nontrivial new things in this paper, such as the weight-adjusted local mirror ascent step size. However, in the current manuscript, the main results read like a careful composition of two known lines of work rather than a new conceptual contribution.

W4. The theory–simulation link is not fully justified. The analysis assumes objective and communication sequences are fixed independently of algorithmic randomness. However, in the tracking simulations, future agent/target positions depend on the sampled actions and may be history-dependent or adversarial. Thus, the theorem does not directly cover the closed-loop simulation without additional justification. Also, 1/d is unbounded as d approaches 0. The experiments should specify a minimum-distance/clipping rule consistent with the bounded-gradient assumptions.

W5. Given the limited technical novelty, the experiments should have been more comprehensive. There are no error bars/significance tests in the main figures, no runtime or communication-cost comparison, and no additional directed time-varying baseline such as a direct Push-Sum + online greedy/submodular method. The static-undirected result also shows that POSMA is initially worse than MA-OSEA. The later improvement needs statistical support.

Questions for authors

See W1-W5.

9 comments

Thank you for spending so much time to review our work and give so many constructive suggestions. We have carefully read the comments and revised the manuscript. Our responses to weaknesses and your questions are listed as follows. We greatly appreciate your time and constructive advises to enhance the quality of the manuscript.


Weaknesses:


W1.1. The multilinear relaxation, curvature-dependent surrogate, stochastic gradient estimator, blockwise mirror updates, rounding argument, and approximation factor are inherited from the ICLR 2025 MA-OSMA work. The new contribution is primarily their integration with push-sum communication through a weight-adjusted update and corresponding weighted dynamic-regret analysis. The authors fail to sufficiently explain which technical obstacle requires a substantially new idea rather than an adaptation of existing surrogate-gradient and push-sum analyses.

Thank you for your comments. We agree that Push--Sum is an established communication mechanism under unbalanced or directed topologies and Lemmas 1--5 and 8 are from MA-OSMA [1]. However, extending this framework to ongoing policy learning under time-varying BB-strongly connected digraphs requires addressing three main challenges. (a) Bounding policy disagreement during online learning. Local policy updates continue even when communication is intermittent. The challenge is to bound how the disagreement effects accumulate as they propagate under time-varying directed graphs. (b) Addressing local update perturbations in the weighted policy iteration. Each local update enters the iteration multiplied by a time-varying Push--Sum weight. The step size must account for this weight to obtain a uniform bound on each agent's weighted perturbation. (c) Preserving the approximation factor in the dynamic regret analysis. Time-varying directed aggregation yields weighted Bregman bounds, while the surrogate gradient inequality requires an unweighted sum of gradient inner products. Specifically, the following points explain how we address each challenge.

1. Including update residuals in the agreement analysis. Under intermittent connectivity, agents maintain different estimates of other agents' action probabilities. Local learning continually changes the estimates, so a consensus-only iteration cannot describe the full process. We include the update residual in the next weighted policy estimate, qt+1,i=wt+1,ixt+1,i=∑j[A(t)]ijqt,j+wt+1,irt+1,i,\mathbf q_{t+1,i}=w_{t+1,i}\mathbf x_{t+1,i}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+w_{t+1,i}\mathbf r_{t+1,i}, where rt+1,i=xt+1,i−yt+1,i\mathbf r_{t+1,i}=\mathbf x_{t+1,i}-\mathbf y_{t+1,i} is the difference between the updated and aggregated policy estimates. The weighted residual accounts for continued learning. We bound both the propagation of initial policy estimates and the accumulated effects of local updates.

2. Scaling local steps to time-varying directed graphs. The changing weights can amplify or suppress the influence of local surrogate gradient estimates. We use ηt/wt+1,i\eta_t/w_{t+1,i} instead of ηt\eta_t in MA-OSMA [1]. When wt+1,i>1w_{t+1,i} > 1, the smaller step prevents the larger message weight from giving the local gradient excessive influence. When wt+1,i<1w_{t+1,i} < 1, the larger step compensates for the smaller weight, which would otherwise weaken the local gradient influence. For ψ(x)=12∣x∣22\psi(\mathbf x)=\frac12\\|\mathbf x\\|_2^2, the same reference and gradient, and inactive probability constraints under both steps,

&\mathbf q_{t+1,i}^{\mathrm{scaled}}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+\eta_t\mathbf g_{t,i},\\\\ &\mathbf q_{t+1,i}^{\mathrm{unscaled}}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+\eta_tw_{t+1,i}\mathbf g_{t,i}. \end{aligned}$$ The adjusted step prevents the additional multiplication of $\mathbf g_{t,i}$ by $w_{t+1,i}$. For general probability-constrained updates, Lemma 7 gives $w_{t+1,i}\mathbb E\\|\mathbf r_{t+1,i}\\|\le G\eta_t$, controlling local updates in the agreement analysis.

3. Technical difficulties in dynamic regret analysis. With the fixed symmetric doubly stochastic matrix in MA-OSMA [1], for u∈C\mathbf u\in\mathcal C,

\le\frac1{\eta_t}[\sum_iD_\psi(\mathbf u,\mathbf x_{t,i})-\sum_iD_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ The unweighted inner products bound dynamic $\alpha$-regret through the surrogate gradient inequality. For time-varying directed graphs, the bound instead involves weights from consecutive rounds, $$\sum_i\langle\mathbf g_{t,i},\mathbf u-\mathbf x_{t+1,i}\rangle \le\frac1{\eta_t}[\sum_iw_{t,i}D_\psi(\mathbf u,\mathbf x_{t,i})-\sum_iw_{t+1,i}D_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ Weighting the original local inequalities would also reweight the left-hand side. To address this difficulty, Lemma 12 uses the mirror ascent inequality with coefficient $w_{t+1,i}/\eta_t$, $$\langle\mathbf g_{t,i},\mathbf u-\mathbf x_{t+1,i}\rangle \le\frac{w_{t+1,i}}{\eta_t}[D_\psi(\mathbf u,\mathbf y_{t+1,i})-D_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ Substituting $\sum_iw_{t+1,i}D_\psi(\mathbf u,\mathbf y_{t+1,i})\le\sum_iw_{t,i}D_\psi(\mathbf u,\mathbf x_{t,i})$ into the summed local bounds gives the second inequality. The differences now involve consecutive rounds, allowing telescoping and accounting for changing optimal action sets in Lemma 13 without reweighting the gradient inner products. In summary, the technical contribution is to control weighted policy updates and connect weighted Bregman differences across rounds without reweighting the surrogate gradient inner products. The resulting guarantees retain the approximation ratio and the dependence on $T$ and $C_T$ for executed joint action sets under more general graph conditions. [1] 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*, 2025b. --- > **W1.2. In particular, the approximation factor is preserved rather than improved, and the fundamental horizon/comparator-variation dependence remains similar.** Thank you for your comments. Although the approximation factor and the leading dependence on $T$ and $C_T$ remain unchanged, we establish both guarantees for continued policy learning over time-varying $B$-strongly connected digraphs with possibly disconnected individual graphs. Establishing these guarantees requires controlling policy disagreement caused by continued learning, bounding local update perturbations under changing weights, and preserving the surrogate gradient inequality in the dynamic regret analysis. The adjusted local step controls the weighted perturbations, the weighted residual bounds account for their accumulated effects on disagreement, and the weighted Bregman analysis permits telescoping without reweighting the gradient inner products. These algorithmic and theoretical contributions establish agreement and dynamic $\alpha$-regret guarantees under intermittent directed communication while retaining the curvature-dependent approximation ratio and the leading dependence on $T$ and $C_T$. ---

W2. The λ\lambda-based bound seems too conservative. With λ=(1−N−NB)1/B\lambda=(1-N^{-NB})^{1/B}, the factor 1/λ(1−λ)1/\sqrt{\lambda(1-\lambda)} is approximately BNNB/2\sqrt{B}N^{NB/2}, or 1.86×10391.86\times10^{39} for the experimental setting N=20N=20, B=3B=3. The authors should distinguish this worst-case connectivity guarantee from a tight characterization of network dependence, discuss the additional dependence on the minimum push-sum weight, and ideally provide sharper graph-specific estimates.

Thank you for your comments. We acknowledge that the mixing factor λ\lambda in Lemma 9 is a worst-case bound over all admissible BB-strongly connected graph sequences. To reduce conservatism, we improve the estimates in two cases: (i) for any admissible sequence with N=20N=20, B=3B=3 and T=2500T=2500, considering only TT rounds reduces the geometric-sum factors in M0,TM_{0,T} and M2,TM_{2,T} from 3.46×10783.46\times10^{78} to approximately 25002500 and 1249.51249.5, respectively; the square-root factor decreases from 1.86×10391.86\times10^{39} to 35.3535.35; (ii) for a given graph sequence, we calculate λgraph\lambda_{\mathrm{graph}} from A(t)A(t) and the minimum weight γT\gamma_T over the same horizon. The details in Appendices A.4 and A.5 are summarized below:

1. Improving the bound by considering only TT rounds. The refined average regret bound in Eq. (80) is E[Regα(T)]/T≤2M1M2,T/T+M0,T/T\mathbb E[\mathrm{Reg}_\alpha(T)]/T\le2\sqrt{M_1M_{2,T}/T}+M_{0,T}/T. To improve the bounds on M0,TM_{0,T} and M2,TM_{2,T}, we consider only the actual TT rounds,

\le\frac1\lambda\min\left\\{T,\frac1{1-\lambda}\right\\},$$ and $$\frac1T\sum_{t=1}^{T}\sum_{s=1}^{t-1}\lambda^{t-s-2} \le\frac1\lambda \min\left\\{\frac{T-1}{2},\frac1{1-\lambda}\right\\}.$$ Both estimates are no larger than the previous bound $1/[\lambda(1-\lambda)]$. The first inequality can reduce $M_{0,T}/T$, while the second can reduce $2\sqrt{M_1M_{2,T}/T}$ by improving the estimate of $M_{2,T}$. For $N=20$ and $B=3$, we have $$\frac1{\lambda(1-\lambda)}\approx3.46\times10^{78}, \qquad \frac1{\sqrt{\lambda(1-\lambda)}}\approx1.86\times10^{39}.$$ For $T=2500$, the new factors are approximately $2500$ in $M_{0,T}$ and $1249.5$ in the communication-dependent part of $M_{2,T}$. The corresponding square-root factor decreases from $1.86\times10^{39}$ to approximately $35.35$. The remaining coefficients are unchanged. The refinement retains the worst-case $\lambda$ and does not establish tight network dependence.
Reviewer_8ySFOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies online monotone submodular maximization under a partition constraint, where each agent picks one action per round, over time-varying directed communication graphs. POSMA works as follows: (i) It relaxes each round’s problem with the multilinear extension; (ii) Each agent updates only its own coordinates by mirror ascent on the surrogate gradient of Zhang et al. (2025); (iii) Agents aggregate policies by push-sum with column-stochastic, out-degree-based weights. The mirror step is rescaled by the push-sum weight. Under B-strong connectivity, the main results are a characterization of the expected dynamic regret on average, and a pairwise disagreement bound between agents. The experiments are multi-target tracking simulations. POSMA is compared with MA-OSMA, MA-OSEA and OSG on static and time-varying graphs.

Critical strengths

Explicit dynamic-regret characterization under directed, intermittent communication. The analysis keeps the tight curvature-dependent ratio of MA-OSMA while relaxing the communication model to column-stochastic, time-varying digraphs. The connectivity parameters appear explicitly in the bound. Technically sound integration of push-sum with weighted mirror ascent.

Critical weaknesses

Limited novelty. Push-sum for unbalanced or directed topologies is standard in distributed optimization. Time-varying networks have also been treated for decentralized online submodular maximization. Much of the analysis reuses MA-OSMA lemmas (Lemmas 1–5 and 8), so the contribution is mainly the combination.

The connectivity dependence is conservative. The paper presents this as a quantitative characterization of how connectivity degradation affects regret, but the experiments do not test the predicted scaling.

Assumption 2 is very restrictive and inconsistent with the mirror-ascent framing. A Bregman divergence is symmetric essentially only when ψ\psi is quadratic. Convexity in the second argument also fails for common potentials such as negative entropy. Assumption 2 therefore appears to reduce the method to Euclidean projected gradient ascent, and the paper should say so.

Experimental reporting. POSMA also outperforms MA-OSMA on static undirected graphs, the setting MA-OSMA was designed for, and this needs explaining: is it a step-size or tuning difference?

Questions for authors

In (1), why ≤1\le 1 in the constraint, instead of =1=1? Is this to ensure a convex formulation later in (4)? Is the optimal solution with ≤1\le 1 always attained at the boundary -- the paper does not say.

Convexity of g. Where the coordinate-separable potential ψ(x) = Σ g(x_a) is introduced (Definition 3, eq. (8)), g is only assumed continuously differentiable. Shouldn’t g be at least strictly convex for D_{g,n_i} to be a valid divergence? Strong convexity follows later from Assumption 1, but it should be stated where g is defined.

Admissible potentials. Which potentials satisfy Assumption 2 besides the squared Euclidean norm? If none, would you restate the method and results in Euclidean form?

Static-graph comparison. On static undirected graphs, what explains POSMA beating MA-OSMA? Were step sizes tuned separately for each method, and how many runs are behind Figure 1?

14 comments

Thank you for spending so much time to review our work and give so many constructive suggestions. We have carefully read the comments and revised the manuscript. Our responses to weaknesses and your questions are listed as follows. We greatly appreciate your time and constructive advises to enhance the quality of the manuscript.


Weaknesses:


W1. Limited novelty. Push-sum for unbalanced or directed topologies is standard in distributed optimization. Time-varying networks have also been treated for decentralized online submodular maximization. Much of the analysis reuses MA-OSMA lemmas (Lemmas 1--5 and 8), so the contribution is mainly the combination.

Thank you for your comments. We agree that Push--Sum is an established communication mechanism under unbalanced or directed topologies and Lemmas 1--5 and 8 are from MA-OSMA [1]. However, extending this framework to ongoing policy learning under time-varying BB-strongly connected digraphs requires addressing three main challenges. (a) Bounding policy disagreement during online learning. Local policy updates continue even when communication is intermittent. The challenge is to bound how the disagreement effects accumulate as they propagate under time-varying directed graphs. (b) Addressing local update perturbations in the weighted policy iteration. Each local update enters the iteration multiplied by a time-varying Push--Sum weight. The step size must account for this weight to obtain a uniform bound on each agent's weighted perturbation. (c) Preserving the approximation factor in the dynamic regret analysis. Time-varying directed aggregation yields weighted Bregman bounds, while the surrogate gradient inequality requires an unweighted sum of gradient inner products. Specifically, the following points explain how we address each challenge.

1. Including update residuals in policy exchange in the agreement analysis. In our setting, each agent performs a local mirror ascent step on a surrogate objective, then aggregates the resulting policies (probability distributions). However, under intermittent connectivity, agents generally maintain different estimates of the global policy, including probability distributions of the actions for other agents. Moreover, these estimates also change after each local optimization step, so a consensus-only iteration does not fully describe their evolution. To solve this problem, in contrast to the basic Push--Sum mechanism, we include the update residual in the next weighted policy estimate, qt+1,i=wt+1,ixt+1,i=∑j[A(t)]ijqt,j+wt+1,irt+1,i,\mathbf q_{t+1,i}=w_{t+1,i}\mathbf x_{t+1,i}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+w_{t+1,i}\mathbf r_{t+1,i}, where rt+1,i=xt+1,i−yt+1,i\mathbf r_{t+1,i}=\mathbf x_{t+1,i}-\mathbf y_{t+1,i} measures the difference between the updated policy estimate xt+1,i\mathbf x_{t+1,i} and aggregated policy estimate yt+1,i\mathbf y_{t+1,i}. The weighted residual wt+1,irt+1,iw_{t+1,i}\mathbf r_{t+1,i} therefore represents the perturbation introduced by ongoing local learning. Without wt+1,irt+1,iw_{t+1,i}\mathbf r_{t+1,i}, the agreement error would omit continued local learning. We instead track both the propagation of the initial policy estimates and the accumulated effects of these perturbations.

2. Scaling local steps to time-varying directed graphs. The weights induced by the time-varying directed graphs can amplify or suppress the influence of local surrogate gradient estimates. Thus, we use the step size ηt/wt+1,i\eta_t/w_{t+1,i} instead of ηt\eta_t in MA-OSMA [1] to accommodate the time-varying directed graphs.

Relative to the step size ηt\eta_t in MA-OSMA [1], this step is smaller when wt+1,i>1w_{t+1,i} > 1 and larger when wt+1,i<1w_{t+1,i} < 1. To illustrate this scaling, consider the Euclidean potential ψ(x)=12∣x∣22\psi(\mathbf x)=\frac12\\|\mathbf x\\|_2^2, the same reference yt+1,i\mathbf y_{t+1,i}, and the surrogate gradient estimate gt,i\mathbf g_{t,i}, with inactive probability constraints under both steps. The two steps yield

&\mathbf q_{t+1,i}^{\mathrm{scaled}}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+\eta_t\mathbf g_{t,i},\\\\ &\mathbf q_{t+1,i}^{\mathrm{unscaled}}=\sum_j[A(t)]_{ij}\mathbf q_{t,j}+\eta_tw_{t+1,i}\mathbf g_{t,i}. \end{aligned}$$ The adjusted step prevents the additional multiplication of $\mathbf g_{t,i}$ by $w_{t+1,i}$. Furthermore, the scaled step allows us to retain the curvature-dependent approximation factor of MA-OSMA [1] in the dynamic regret bound over time-varying directed graphs, as shown next.

3. Technical difficulties in dynamic regret analysis. Due to the time-varying directed graphs, Bregman bounds involve weights wt,iw_{t,i} and wt+1,iw_{t+1,i} from different rounds. We derive weighted Bregman bounds and use a weighted potential across rounds. With the fixed symmetric doubly stochastic matrix in MA-OSMA [1], for u∈C\mathbf u\in\mathcal C, we have

\le\frac1{\eta_t}[\sum_iD_\psi(\mathbf u,\mathbf x_{t,i})-\sum_iD_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ Note that the unweighted sum of inner products on the left is the local optimization term used in the surrogate-gradient analysis of dynamic $\alpha$-regret. However, for time-varying directed graphs, the bound uses weights from both rounds, $$\sum_i\langle\mathbf g_{t,i},\mathbf u-\mathbf x_{t+1,i}\rangle \le\frac1{\eta_t}[\sum_iw_{t,i}D_\psi(\mathbf u,\mathbf x_{t,i})-\sum_iw_{t+1,i}D_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ Generally, weighting the first inequality changes the left-hand side instead of yielding the second. To address this difficulty, we use the mirror ascent inequality with the coefficient $w_{t+1,i}/\eta_t$ in Lemma 12, $$\langle\mathbf g_{t,i},\mathbf u-\mathbf x_{t+1,i}\rangle \le\frac{w_{t+1,i}}{\eta_t}[D_\psi(\mathbf u,\mathbf y_{t+1,i})-D_\psi(\mathbf u,\mathbf x_{t+1,i})].$$ Substituting $\sum_iw_{t+1,i}D_\psi(\mathbf u,\mathbf y_{t+1,i})\le\sum_iw_{t,i}D_\psi(\mathbf u,\mathbf x_{t,i})$ into the summed local bounds gives the second inequality. Only consecutive $\mathbf x_{t,i}$ and $\mathbf x_{t+1,i}$ remain, which allows telescoping over $t$, as detailed in Lemma 13. Thus, the regret proof accommodates time-varying directed graphs while retaining the unweighted gradient inner products. In summary, adjusted steps, weighted residual bounds, and regret analysis under time-varying $B$-strongly connected digraphs go beyond combining MA-OSMA [1] and Push--Sum. The dynamic $\alpha$-regret guarantee covers executed joint action sets over time-varying directed graphs and retains the curvature-dependent approximation ratio. [1] 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*, 2025b.

W2. The connectivity dependence is conservative. The paper presents this as a quantitative characterization of how connectivity degradation affects regret, but the experiments do not test the predicted scaling.

Thank you for your comments. We acknowledge that the mixing factor λ\lambda in Lemma 9 is a worst-case bound over all admissible BB-strongly connected digraphs. To reduce the conservatism of the regret bound, we improve the estimates in two cases: (i) for any admissible sequence, bounding the sums over TT rounds replaces 1/[λ(1−λ)]1/[\lambda(1-\lambda)] by λ−1min⁡T,(1−λ)−1\lambda^{-1}\min\\{T,(1-\lambda)^{-1}\\} in M0,TM_{0,T} and λ−1min⁡(T−1)/2,(1−λ)−1\lambda^{-1}\min\\{(T-1)/2,(1-\lambda)^{-1}\\} in the communication-dependent part of M2,TM_{2,T} in Eq. (77); (ii) for a given graph sequence, we calculate λgraph\lambda_{\mathrm{graph}} from the column-stochastic matrices A(t)A(t) while retaining the original β\beta. The details in Appendices A.4 and A.5 are summarized below:

1. Improving the bound by considering only TT rounds. The refined average regret bound in Eq. (80) is E[Regα(T)]/T≤2M1M2,T/T+M0,T/T\mathbb E[\mathrm{Reg}_\alpha(T)]/T\le2\sqrt{M_1M_{2,T}/T}+M_{0,T}/T. To improve the bounds on M0,TM_{0,T} and M2,TM_{2,T}, we consider only the actual TT rounds,

\le\frac1\lambda\min\left\\{T,\frac1{1-\lambda}\right\\},$$ and $$\frac1T\sum_{t=1}^{T}\sum_{s=1}^{t-1}\lambda^{t-s-2} \le\frac1\lambda \min\left\\{\frac{T-1}{2},\frac1{1-\lambda}\right\\}.$$ Both estimates are no larger than the previous bound $1/[\lambda(1-\lambda)]$. The first inequality can reduce $M_{0,T}/T$, while the second can reduce $2\sqrt{M_1M_{2,T}/T}$ by improving the estimate of $M_{2,T}$. The refinement retains the worst-case $\lambda$ and does not establish tight network dependence. **2. Using the column-stochastic matrices $A(t)$.** To obtain an estimate that better reflects the time-varying directed graphs, we examine the column-stochastic matrices $A(t)$ to determine how information propagates over successive rounds. For column-stochastic matrices, let $$P_s=A(s+L-1)\cdots A(s),\qquad \tau(P_s)=\frac12\max_{i,j}\sum_{k=1}^{N} |[P_s]_{ki}-[P_s]_{kj}|,$$ where $P_s$ represents communication over $L$ rounds, and a smaller $\tau(P_s)$ indicates better mixing of information from different agents [1]. Under the assumptions of Lemma 9 in the previous version of this paper, choose a window length $L$ with $\kappa < 1$ and define $$\kappa=\sup_s\tau(P_s),\qquad \bar\kappa=\max\left\\{\kappa,\frac1\beta\right\\}, \qquad \lambda_{\mathrm{graph}}=\bar\kappa^{1/L}.$$ Using $\phi_i(t)=w_{t+1,i}/N$, we obtain $$\left|[A(t:s)]_{ij}-\phi_i(t)\right| \le\tau(A(t:s)) \le\bar\kappa^{\lfloor(t-s+1)/L\rfloor} \le\beta\lambda_{\mathrm{graph}}^{t-s}.$$ The resulting bound has the same form as Lemma 9 and retains the original $\beta$, allowing $\lambda_{\mathrm{graph}}$ to replace the universal $\lambda$ in subsequent bounds. For a finite communication sequence, the guarantee applies to the corresponding finite horizon. The substituted bounds and step size are stated in Appendix A.5, Eqs. (83)--(88). The discussions of Figures 2 and 5 in our manuscript have described utility changes with $B$. Utility reflects the reward component of dynamic $\alpha$-regret, since $\mathbb E[\mathrm{Reg}_\alpha(T)]/T=\alpha\mathbb E[\sum_{t=1}^{T}f_t(\mathcal A_t^*)]/T-\mathbb E[\sum_{t=1}^{T}f_t(\mathcal A_t)]/T$. For the same objective sequence and optimal-utility benchmark, lower average utility corresponds to higher average regret. Our regret bound describes the worst case over all admissible $B$-strongly connected graph sequences. A larger $B$ allows longer intervals before information can propagate among all agents. Accordingly, the universal estimate $\lambda=(1-N^{-NB})^{1/B}$ approaches one as $B$ increases, enlarging the factor $1/\sqrt{\lambda(1-\lambda)}$. Meanwhile, the guaranteed minimum-weight lower bound $\gamma\ge N^{-NB}$ decreases, potentially enlarging the coefficients containing $1/\gamma$. Thus, the bound explicitly shows how a larger connectivity window can worsen the worst-case guarantee, while the utility curves illustrate the practical effect of changing $B$ in the tested settings. We have clarified the distinction in the abstract and Remark 5. To keep the claims consistent with the analysis, we have revised the abstract and Remark 5 to state a worst-case dynamic $\alpha$-regret upper bound with explicit dependence on communication parameters. The additional experiments complement this guarantee without treating the bound as a tight prediction of actual regret. [1] Ilse C. F. Ipsen and Teresa M. Selee. Ergodicity coefficients defined by vector norms. *SIAM Journal on Matrix Analysis and Applications*, 32(1):153--200, 2011. ---

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.