Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency

Authors: Qixin Zhang, Zongqi Wan, Yu Yang, Li Shen, Dacheng Tao
Primary area: reinforcement learning
Keywords: online learning, submodular maximization, surrogate gradient, multi-agent

Abstract:
Coordinating multiple agents to collaboratively maximize submodular functions in unpredictable environments is a critical task with numerous applications in machine learning, robot planning and control. The existing approaches, such as the OSG algorithm,  are often hindered by their poor approximation guarantees and the rigid requirement for a fully connected communication graph. To address these challenges, we firstly present a $\textbf{MA-OSMA}$ algorithm, which employs the multi-linear extension to transfer the discrete submodular maximization problem into a continuous optimization, thereby allowing us to reduce the strict dependence on a complete graph through consensus techniques. Moreover, $\textbf{MA-OSMA}$ leverages a novel surrogate gradient to avoid sub-optimal stationary points. To eliminate the computationally intensive projection operations in $\textbf{MA-OSMA}$, we also introduce a projection-free $\textbf{MA-OSEA}$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Theoretically, we confirm that both algorithms achieve a regret bound of $\widetilde{O}(\sqrt{\frac{C_{T}T}{1-\beta}})$ against a  $(\frac{1-e^{-c}}{c})$-approximation to the best comparator in hindsight, where $C_{T}$ is the deviation of maximizer sequence, $\beta$ is the spectral gap of the network and $c$ is the joint curvature of submodular objectives. This result significantly improves the $(\frac{1}{1+c})$-approximation provided by the state-of-the-art OSG algorithm. Finally, we demonstrate the effectiveness of our proposed algorithms through simulation-based multi-target tracking.

Decision: accept (spotlight)
Reviewer scores: 6, 8, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1729695519507

thread_type:
official_review

<thread_object>
creator: reviewer_e6bz

<content>
summary:
This paper presents two algorithms for solving the multi-agent online submodular maximization problem, accompanied with a convergence analysis for each. Both algorithms achieve near-optimal approximation ratio while requiring less restrictive assumptions about the graph structure (connected instead of complete). Notably, the second algorithm further gets rid of the projection step by using a specific Bergman divergence (KL divergence) within the mirror descent framework. The effectiveness of the proposed algorithms is also validated through a simulated multi-target tracking task.

strengths:
1. The paper's contributions and the structure are clearly delivered, with additional remarks are provided to enhance understanding. The appendix is well-organized and easy to read.
2. The contributions are interesting and compelling. They advance prior work to a near-optimal approximation ration and substantially relaxing the assumptions regarding graph connectivity.

weaknesses:
1. Overall, the writing could be improved. This paper is heavy on notations & definitions, and the authors should be more careful when introducing definitions/abbreviations/notations. Specific examples are listed below:

- Line 16: What do OSG, MA-OSMA, MA-OSEA stand for? The contribution "...skilfully (typo) harnessing the KL divergence..." is too technical and detailed for an abstract. A more high-level intuition is expected at this stage.

- Line 49: The abbreviation MA-OSM is introduced twice.

- Line 138: Typo "lowercase."

- "Notations" paragraph: On Line 142, avoid starting a sentence with math notations. The lowercase "s" is used without an explicit definition.

- Line 154: "MA-OSM" is introduced again.

- Line 225: Consider using a different notation than "F" for clarity.

- Theorem 2: Is the phrase "for any x,y" missing?

- Algorithm 1: Using $\eta_t$ suggests an adaptive step size, but it is set to a constant in Remark 8.

- Assumption 5: Is $\mathbb{E}[\tilde{\nabla}F_t^s(x)\mid x]=\nabla F_t^s(x)$ derived from the estimation procedure, or is it an assumption? Constant $G$ is not defined.

- Theorem 5: notation $\gamma$ should be redefined, as its first definition occurs early in the paper and the other one in Algorithm 2 appears only afterwards, which is shown later in the paper. Consider using a different set of parameters than $C_1,C_2,C_3$, which are already used in Theorem 3.

- Line 992: typo "y"->"x"

- Line 1058: "argmin"?

- Line 1100: is $=[y_{t,i}]_{\mathcal{V}\textbackslash \mathcal{V}_i}$ a typo?

- Line 1126: Typo - $x$ should be $y_{t,i}$ in the first term on RHS.

- Line 1029+1030: Typo $F^A$ should be $F^s$.

- Line 1183: Can you provide more specific references to the results in Nedic&Ozdaglar, 2009 and Horn&Johnson, 2012?

- Line 1291: Typo - $F^A$ should be $F^s$.

- Line 1374: Typo - "the first equation of Lemma 12."

- Line 1420: Typo - $f$ missing.

2. Algorithm 2: It would be beneficial to provide more insights into the difference between Algorithm 1&2.

3. The related work section is not informative enough to provide a high-level overview of earlier work, provide more detailed explanation and comparison of the works listed in Table 1 more in detail would be helpful.

4. Line 83: Please provide citations for these "well-established consensus techniques."

5. For the simulations, error bars are missing from the plot and 5 iterations seems insufficient for drawing robust conclusions.

questions:
1. The comparison of prior work can be better clarified. For now, the contribution part in the introduction doesn't provide a clear picture of how the improvements are made and why they are novel.
2. The paper would benefit from more detailed insights into improvements and associated trade-offs? E.g. regarding the connectivity of the graph, while the prior work assume a complete graph, but they only require a directed acyclic graph (as indicated in Figure 1). In contrast, the completeness is no longer needed but the edges need to be undirected. Why is this trade-off beneficial? Another similar question comes from the regret bound: it is degrading from $\tilde{\mathcal{O}}(\sqrt{C_T*T})$ to $\mathcal{O}(\sqrt{C_T * T/(1-\beta)})$. Although the simulations suggest improved performance, a theoretical explanation of why this compromise in the regret bound is reasonable would be valuable. Could you provide more insights?
3. Could you elaborate on how to sample from different actions under the constraint "$\sum_{a\in\mathcal{V}_i}x_a\leq 1$" without requiring normalization?
4. Can you clarify the novelty of Theorem 2 compared to Corollary 7 in Zhang et al. 2024 in Remark 3? The results look very similar, apart from the difference in curvature.
5. Can you explain more on the difference between Distributed-CG and this paper? The two seem closely related but Distributed-CG is only mentioned in the appendix.
6. Line 1402: Can you provide a more detailed explanation of why the first inequality follows from the monotonicity of $f_t$? It is applied several time but the connection between the monotonicity of $F$ and monotonicity of $f$ is not clear 
7. Does this paper offer any novel insights into optimization, beyond those already established in the literature?
</content>
</thread_object>

</thread>
<thread>
creation date:
1729838985983

thread_type:
official_review

<thread_object>
creator: reviewer_qepy

<content>
summary:
This paper proposes an algorithm for online multi-agent submodular optimization problem, which is then extended to a projection-free variant. The main contribution is that the proposed algorithm relaxes the complete graph assumption and achieves tighter approximation ratio, as compared to the SOTA algorithm.

strengths:
The paper is overall well-written. The proposed algorithm removes the limitation of complete graph assumption as compared to the SOTA algorithm. It also achieves a tighter approximation ratio as compared to the SOTA algorithm.

weaknesses:
1. The execution of the algorithm relies on the curvature parameter $c$. However, this parameter may be unknown beforehand. 
2. In line 11 of the Alg. 1 and line 12 of the Alg. 2, the objective function needs to be evaluated for 2$\sum_i|\mathcal{V}_i|$ times. This can be very inefficient when the function $f_t$ is expensive to evaluate or the number of actions is large.  
3. The experimental evaluation part is relatively weaker than the theoretical contribution. In the experiments, the paper did not verify the theoretical result, that is, some figure showing the ratio between empirical objective value and the optimal value.

questions:
1. Can the authors comment on how to select $c$ in practice?
2. The algorithm introduces a set of hyperparameters such as step size $\eta_t$, mixing parameter, and the weight matrix. Can the authors comment on how to select these hyperparameters?
3. In figure 3, I can understand the utility column. But can the authors elaborate on the other two columns and why are they also interesting?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730671935561

thread_type:
official_review

<thread_object>
creator: reviewer_nhda

<content>
summary:
This paper studies a multi-agent online submodular maximization problem (MA-OSM). In each step, each agent independently selects a decision from a unique decision set, queries local marginal gains of an underlying submodular function, and exchanges information with neighboring agents. By leveraging a novel surrogate function approach for the multi-linear extension of submodular functions, the paper proposes an online algorithm that achieves a tight approximation ratio relative to the offline solution under a connected communication graph, with a regret bound of $O\left(\sqrt{\frac{C_T T}{1 - \beta}}\right)$, where $C_T$ is the deviation of the maximizer sequence and $\beta$ is the spectral gap of the network. The paper further develops a projection-free variant of the first algorithm, and attains the same approximation ratio with a slight loss in the regret guarantee. Numerical results effectively illustrate the performance of the proposed algorithms compared to prior work, which has sub-optimal approximation ratios.

strengths:
-  The proposed algorithms improve the approximation ratio of prior work from $\frac{1}{1+c}$ to the tight ratio $\frac{1-e^{-c}}{c}$. Additionally, this improvement is achieved with limited feedback requirements, rather than needing a complete communication graph.

- The use of surrogate functions to overcome limitations related to stationary points in the original multi-linear extension is both effective and inspiring. 

- The paper is well presented, with a coherent flow, clear contributions, and strong results.

weaknesses:
- There is some ambiguity regarding the communication complexity of the proposed algorithms. Although they attain a tight approximation ratio, it is unclear if the communication complexity is also tight. Based on the title, the paper seems to claim tight communication efficiency; however, this aspect is not clearly addressed. Additionally, the paper appears to assume a static communication graph, which may not apply to applications like multi-target tracking as discussed in the numerical section.

- In the proposed algorithm, each agent is required to query the local marginal gain oracle multiple times. While this is common in prior work, it is not evident if/how such an oracle would exist in practical applications.

questions:
- Could you provide formal comments on the tightness of the communication complexity for both proposed algorithms?
- Since the proposed algorithms can be viewed as an online implementation of offline approximation algorithms, it would be beneficial to provide a formal comparison with the work of [Razazadeh and Kia 2023] in the main paper. 
- The regret guarantee depends on $C_T$, the deviation of the maximizer sequence. Please specify how $C_T$ varies and impacts the regret guarantee. 
- what does the subscript $d$ denote in the regret definition?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730673837068

thread_type:
official_review

<thread_object>
creator: reviewer_wfew

<content>
summary:
This work proposes two algorithms MA-OSMA and MA-OSEA that collaboratively solve an online, multi-agent submodular optimization problem. Both algorithms produce $\left(\frac{1-e^{-c}}{c} \right)$ sub-optimal solutions in contrast to $\frac{1}{1+c}$ approximate solutions produced by state of the art methods. They also achieve a regret bound of $\tilde O\left( \sqrt\frac{C_TT}{1-\beta} \right)$. The MA-OSMA algorithm requires a costly projection step, this is then removed by using a KL divergence and "mixing uniform distribution" argument in MA-OESA. The method is then illustrated via numerical simulations.

strengths:
The paper addresses an interesting and relevant problem - motivated by multi-agent robotic problems. The main contributions of the paper are:
- Improving on the state of the art performance bounds of the OSG algorithm by approving the approximation quality to $\frac{1-e^{-c}}{c}$ where $c$ encodes the curvature of the problem.
- The second algorithm, MA-OESA, removes the need for a projection step which allegedly is computationally expensive.

weaknesses:
I believe there are several areas where this paper can be improved - mostly in the area of presentation and clarity of exposition.

- In section 2.1 the authors state that "each agent $i$ within $\mathcal N$ is equipped with a unique and discrete set of actions". But in the numerical section this seems to be contradicted as the simulation considers the case where each agent has exactly the same choices: up, down, left, right, diagonal etc. Are they unique or identical?!

- In the formulation (1), what is the set $\mathcal A$? Is it just a subset of $\mathcal V$?

- In terms of motivation, it is not clear why the algorithm from Vondrak or Bian et al, cannot be used to achieve the $\frac{1-e^{-c}}{c}$ bound. 

- It's a bit weird to claim that your own algorithm "skillfully harnesses" something. I suggest removing this from the abstract and body.

- The explanation of how to circumvent the fact that KL-divergence is not Lipschitz is not clear at all. The text is full of jargon. What does "mixing a uniform distribution" mean? Neither Theorem 5 nor remark 9 seem to have any parameters from uniform distribution. Please provide some intuition about what is going on here.


- The OSG method should be described and compared to MA-OSMA and MA-OESA in a more direct way. What is the main difference between the algorithms, how do the necessary assumptions differ etc. Why is it that it only achieves $\frac{1}{1+c}$-accurate solutions? This will strengthen the numerical section where it is shown in simulations that the proposed methods out-perform it.

questions:
- The paper lacks any discussion of how the performance of the two algorithms differ beyond what is in Table 1. How costly is the projection step? How do the two methods differ beyond a factor of $\log T$ regret?
- Does the spectral information show up anywhere in the regret bound of the OSG algorithm? Likewise, do any of the connection graph properties appear in the derivation of the approximation ratio in MA-OSMA or MA-OSEA. It seems like they need to appear somewhere and here they appear in the regret bound - was this an active choice? It seems like there is trade-off between approximation ratio and Regret.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730680151897

thread_type:
official_review

<thread_object>
creator: reviewer_h5ct

<content>
summary:
The author(s) propose a continuous surrogate approximation of multi-agent submodular maximization problems and solve via mirror ascent approach to (i) achieve tight approximation, and (ii) reduce communication density among agents. The proposed approach is evaluated in multi-robot target tracking examples.

strengths:
1. The contribution is novel and sound, and the theoretical results are strong.  
2. The paper is well presented in general. The authors clearly motivated challenges existing in the literature and this work’s objectives.
3. The efficacy of the proposed approach is validated using sufficient amount of empirical evidence.

weaknesses:
1. Problem formulation
- I think the author(s) should list the assumptions made in this section explicitly, such as those in lines 177 and 159.
- I think this section is a bit unconnected with the motivating example. I would appreciate a bit more introduction about why and how problems like multi-agent tracking can be formulated as online submodular maximization problems. For example, I am a bit confused here why the objective function is revealed after agents make decisions and why the objective function is guaranteed to be submodular?
2. Experiments:
- Is all the targets being strictly homogeneous in type a requirement from the algorithm? What if different targets are of different types?
3. Contribution: this work builds upon a few existing methods in the literature. The novelty of the approaches can be better specified; cf. Question 3.
4. While submodular optimization has a variety of applications, the problem studied in this work seems to be more specific to robotics applications. I think is relatively less relevant to this venue. 
5. Other minor points:
- Line 70: “Furthermore” – hyperlink is redundant
- Figure 3: It can be shown in the caption or in the figure that 3 rows represent different target types. Right now, it’s a bit hidden in the text.

questions:
1. Line 157: The assumption that different agents must have mutually disjoint action sets looks odd to me. Taking multi-target tracking task as an example, wouldn’t different agents totally have access to execute the same action?
2. Multi-linear extension: I would appreciate that if the author(s) could speak more about how good the continuous relaxation is compared to the original submodular maximization problem and under which conditions. Right now, the presentation just takes this relaxation for granted.
3. In Algorithm 1, what enables the relaxed requirement of a sparse communication graph stated in the contribution statement? Is this part of the author(s) contribution or something enabled by the fact of using existing online mirror ascent methods? A related point is that the author(s) claim that the novelty of their proposed non-oblivious surrogate function for the multi-linear extension objective is the curvature information. Is accounting for the curvature information in non-oblivious surrogate approximation of multi-linear extension a well-recognized challenge in the literature? 
4. The requirement that the objective function needs to be monotone submodular seems to be strong. Can the author(s) elaborate on how restrictive this is?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732205626325

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
References

comment:
Adibi et al. (2022). Minimax optimization: The case of convex-submodular. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3556–3580. PMLR.

Aslay et al. (2017). Revenue maximization in incentivized social advertising. Proc. VLDB Endow., 10(11):1238–1249, August 2017.

Besbes et al. (2015). Non-stationary stochastic optimization. Operations research, 63(5):1227–1244, 2015.

Bian et al. (2017). Guarantees for greedy maximization of non-submodular functions with applications. In International conference on machine learning (ICML), pp. 498–507. PMLR.

Bian et al. (2020). Continuous Submodular Function Maximization. arXiv preprint arXiv:2006.13474.

Calinescu et al. (2011). Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740–1766, 2011.

Chekuri et al. (2014). Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43(6): 1831–1879, 2014.

Chen et al. (2018a). Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity. In International Conference on Machine Learning (ICML), pp. 814–823. PMLR.

Chen et al. (2018b). Online Continuous Submodular Maximization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1896–1905. PMLR.

Chow et al. (2016). Expander graph and communication-efficient decentralized optimization. In 2016 50th Asilomar Conference on Signals, Systems and Computers, pp. 1715–1720. IEEE.

Corah and Michael (2021). Scalable Distributed Planning for Multi-Robot, Multi-Target Tracking. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 437–444. IEEE.

El-Arini et al. (2009). Turning down the noise in the blogosphere. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 289–298.

Fisher et al. (1978). An analysis of approximations for maximizing submodular set functions—II. In Polyhedral Combinatorics, pp. 73–87. Springer.

Grimsman et al. (2018). The impact of information in distributed submodular maximization. IEEE Transactions on Control of Network Systems, 6(4):1334–1343.

Han et al. (2021). Efficient and Effective Algorithms for Revenue Maximization in Social Advertising. In Proceedings of the 2021 international conference on management of data, pp. 671–684.

Hassani et al. (2017). Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, pp. 5841–5851.

Hazan et al. (2016). Introduction to online convex optimization. Foundations and Trends® in Optimization, 2(3-4):157–325.

Kempe et al. (2003). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146.

Krause et al. (2008). Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2).

Kumari et al. (2024). An end-to-end submodular framework for data-efficient in-context learning. In Findings of the Association for Computational Linguistics: NAACL 2024, pp. 3293–3308.

Lin and Bilmes (2010). Multi-document summarization via budgeted maximization of submodular functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 912–920.

Lin and Bilmes (2011). A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 510–520.

Mirzasoleiman et al. (2016a). Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning, pp. 1358–1367. PMLR.

Mirzasoleiman et al. (2016b). Distributed submodular maximization. The Journal of Machine Learning Research, 17(1):8330–8373.

Mokhtari et al. (2018). Decentralized submodular maximization: Bridging discrete and continuous settings. In International conference on machine learning, pp. 3616–3625. PMLR.

Nedi´c and Olshevsky (2014). Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601–615.

Nedic and Ozdaglar (2009). Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61.

Nedi´c et al. (2017). Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597–2633.

Nemhauser et al. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1):265–294.

Qu et al. (2019). Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions. Automatica, 105:206–215.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The reviewers are unanimously positive about the intellectual contributions of this work. I have reviewed the manuscript and it provides a strong contribution to the theory of discrete optimization in the multi-agent setting, resolving some fundamental complexity barriers of prior art related to evaluation of projections. Its practical utility is also apparent in some applications. For these reasons, I recommend this paper be accepted.