- 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
-
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.
-
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
-
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.
-
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
-
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?
-
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?
-
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?
-
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
3. Technical difficulties in dynamic regret analysis. With the fixed symmetric doubly stochastic matrix in MA-OSMA [1], for ,
\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 , which decays faster as increases and does not change the leading rate. The hidden constants retain , and Lemma 9 guarantees only , which can be exponentially small in and . 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 rounds replaces by in and in ; (ii) a given graph sequence yields from and its finite-horizon minimum weight . The details in Appendices A.4 and A.5 are summarized below:
(a) Improving the bound by considering only rounds. The refined average regret bound in Eq. (80) is . To improve the bounds on and , we consider only the actual 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. ---
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
weaknessesand yourquestionsare listed as follows. We greatly appreciate your time and constructive advises to enhance the quality of the manuscript.Weaknesses: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 B-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, where rt+1,i=xt+1,i−yt+1,i measures the difference between the updated policy estimate xt+1,i and aggregated policy estimate yt+1,i. The weighted residual wt+1,irt+1,i therefore represents the perturbation introduced by ongoing local learning. Without wt+1,irt+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 instead of ηt in MA-OSMA [1]. When wt+1,i>1, the smaller step prevents the larger message weight from giving the local gradient excessive influence. When wt+1,i<1, the larger step compensates for the smaller weight, which would otherwise weaken the local gradient influence. For ψ(x)=21∣x∣22, 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.