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

7. Does this paper offer any novel insights into optimization, beyond those already established in the literature?

Thank you very much for your question.

From our perspective, we think this paper may provide the following novel insights into the optimization community:

a) The gradient of objective functions may not always serve as a good direction for many non-convex optimizations. This point is evident from our Theorem 2, where we design an auxiliary function for the multi-linear extension of submodular functions. Specifically, we have theoretically demonstrated that by ascending along a new surrogate gradient, we may reach better stationary points.

b) Consensus techniques in decentralized optimization can effectively integrate information and achieve the coordination among multi-agent scenarios. For instance, in this paper, although each agent can only access the marginal evaluations of actions within their own action set, our theoretical proofs for Algorithms 1 and 2 show that with the help of consensus techniques, we can achieve superior performance. It is important to clarify the distinction between the decentralized problem and the multi-agent scenario emphasized in this paper. Typically, in decentralized optimization, each local node is assumed to maintain its own local utility function, with the collective goal being to optimize the sum of these local functions. In contrast, within the scope of this paper, we assume that all agents share a common submodular function, but each agent is restricted to accessing a unique set of actions.

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......

Thank you very much for your valuable feedback. We will carefully review and correct the issues related to notations, definitions, and abbreviations as you have pointed out.

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

Thank you for your suggestion.

As mentioned in the text, the key difference between Algorithm 1 and Algorithm 2 lies in the incorporation of a ``mixing a uniform distribution" technique in Algorithm 2. Due to space limitations, we were unable to elaborate on this, but we are happy to provide further insights as follows.

The main challenge with KL-divergence is that its gradient tends towards infinity at the boundary, which contradicts the Lipschitz condition stated in Assumption 4. To address this issue, we introduce a small perturbation in our decision vector to prevent it from reaching the boundary. Specifically, in Algorithm 2, at line 7, we incorporate a uniform distribution by adding $\frac{1}{n}\mathbf{1}$ to our decision vector. This ensures that our final decision keeps away from the boundary. Notably, $\frac{1}{n}\mathbf{1}$ can be interpreted as a uniform distribution across all $n$ actions.

We hope this explanation clarifies the unique aspects of Algorithm 2 and its difference from Algorithm 1.

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.

Thank you for your suggestion. We appreciate your feedback on the related work section.

For a detailed explanation and comparison of the previous works, please refer to our previous responses to the Question 1 and Question 5, where we have provided a thorough analysis and comparison of the works listed in Table 1 and Table 2.

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

We apologize for not providing citations for the "well-established consensus techniques" at their first mention on Line 83. Although these relevant citations were included later in the text, we fully understand the importance of immediate attribution. We will add the appropriate citations at Line 83 in the revised version.

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

Thank you for your valuable feedback on our simulation results. The primary theoretical contribution of our paper is that Algorithms 1 and 2, in expectation, can provide a better approximation guarantee than OSG. Therefore, our experiments only demonstrate the empirical performance in terms of the average case. The robustness of our multi-agent algorithms is indeed a topic worth exploring, such as regret bounds and approximation ratios under high probability. We will consider this as a future direction.

Thank you for your detailed and insightful comments. We are truly grateful for the time and effort you have dedicated to reviewing our manuscript. Your feedback is invaluable to us. Below, we will address the concerns you have raised in the sections of Questions and Weaknesses.

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.

Thank you very much for your insightful comments.

Firstly, due to the limited space, we have chosen to place the main comparison of prior work in Appendix A.1. However, in Table 1, we have provided a detailed comparison with the most relevant OSG algorithms.

Secondly, before summarizing our three contributions in our paper, we have detailed the main techniques and novelties employed in our algorithms, which constitute the cornerstone of our improvements. Specifically:

a) "We utilize the multi-linear extension to transform the discrete submodular maximization problem into a continuous optimization problem. This approach allows us to alleviate the stringent requirement for a complete communication graph by leveraging well-established consensus techniques in decentralized optimization."

b) "We develop a surrogate function for the multilinear extension of submodular functions with curvature $c$. This innovation empowers us to surpass the sub-optimal $(\frac{1}{1+c})$-approximation stationary points."

c) "We implement a distinct strategy for updating the selected probabilities associated with each agent's actions and those of others. This strategy requires agents to only assess the marginal gains of actions within their own action sets, thereby reducing the practical requirement on the observational scope of each agent."

We hope these points will help you understand both the novel aspects and the improvements in our work.

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 $\widetilde{O}(\sqrt{C_{T}T})$ to $O(\frac{\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?

Firstly, due to space limitations, our paper assumes a static undirected communication network among agents to simplify the description of the communication graph. However, the capabilities of the algorithmic framework we employ are far from it. We can efficiently extend our algorithms to time-varying and directed network topologies using consensus techniques from (Nedic & Olshevsky, 2014; Nedic et al., 2017), as indicated in our "Conclusions and Future Work" section. Therefore, this is not a trade-off but an enhancement. From the perspective of communication topology, our Algorithms 1 and 2 exhibit greater flexibility and efficiency compared to OSG.

Secondly, to a certain extent, we can view our proposed Algorithms 1 and 2, as well as OSG, as the different trade-off paths between approximation ratio and regret. Specifically,

a) Our Algorithms 1 and 2 slightly sacrifice the regret bound to ensure a tight approximation ratio and reduce the communication burden;

b) On the contrary, OSG ensures a consistent $\widetilde{O}(\sqrt{C_{T}T})$ regret bound, but it will incur a significant communication overhead and a sub-optimal approximation guarantee.

Finally, we wish to emphasize that our chosen path significantly outperforms OSG. It is important to note that the theoretical results of OSG algorithm indicate that its regret bound will exhibit a deviation of $O(\log(T))$ compared to $O(\sqrt{C_{T}T}))$. Although the spectral information indeed affects the regret bound of our MA-OSMA, ensuring $\frac{1}{1-\beta}<C\log(T)$ for some constant $C$ is sufficient to guarantee that our MA-OSMA achieves superior performance in both regret bound and approximation ratio compared to the OSG algorithm. When the time-horizon $T$ is very large, a relatively sparse graph even can secure $\frac{1}{1-\beta}<<C\log(T)$ for some constant $C$.

Thank you for your detailed and insightful comments. We are truly grateful for the time and effort you have dedicated to reviewing our manuscript. Your feedback is invaluable to us. Below, we will address the concerns you have raised in the sections of Questions and Weaknesses.

Questions:

1.Can the authors comment on how to select $c$ in practice?

This is a good question. we have also highlighted this point as one of the directions for future direction in our "Conclusions and Future Work" section.

In practice, it is impossible to know the exact value of the curvature $c$. However, we know that $c$ lies within the interval $[0,1]$. An important property is that if a function has curvature $c$, it also has curvature $c'$ for any $c' \geq c$. Therefore, in our experiments, we set $c=1$ to ensure that our algorithm can achieve at least a $(1 - e^{-1})$-approximation guarantee.

Beyond this, we have a rough idea regarding how to select the curvature $c$. Since we know that curvature $c$ is within the interval $[0,1]$, we can divide this interval using a set of values ${\epsilon, 2\epsilon, \dots, 1}$, given an $\epsilon$ where we assume $\frac{1}{\epsilon}$ is an integer. We then maintain $\frac{1}{\epsilon}$ different versions of the MA-OSMA algorithm, each using one of these values as their curvature $c$. For example, we could denote them as MA-OSMA($\epsilon$), MA-OSMA($2\epsilon$), \dots, MA-OSMA($1$). We can treat these $\frac{1}{\epsilon}$ different versions of the MA-OSMA algorithm as a bandit problem with $\frac{1}{\epsilon}$ arms, where our goal is to find the optimal arm. Generally speaking, when $\epsilon$ is sufficiently small, we can guarantee a $\left(\frac{(1 - e^{-c})}{c} - \epsilon\right)$-approximation ratio. However, this approach requires running $\frac{1}{\epsilon}$ different versions of the MA-OSMA algorithm, which may impose a significant computational burden.

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?

Thanks for your question regarding the selection of hyperparameters in our algorithm. We have detailed these settings in Appendix A.3 of our manuscript.

Specifically, for the weight matrix $\mathbf{W}$ in the context of a random graph, we assign values as follows: if the edge $(i,j)$ exists in the graph, we set $w_{ij} = \frac{1}{1 + \max(d_i, d_j)}$, where $d_i$ and $d_j$ represent the degrees of agents $i$ and $j$, respectively. If $(i,j)$ is not an edge and $i \neq j$, then $w_{i,j} = 0$. Lastly, we define $w_{i,i} = 1 - \sum_{j \in \mathcal{N}i} w_{i,j}$. For a complete graph, we set $w_{ij} = \frac{1}{N}$, where $N$ is the total number of agents. Besides, we have chosen $c = 1$, $\eta_t = \frac{1}{\sqrt{T}}$ and the mixing parameter $\gamma=\frac{1}{T^{2}}$ in the MA-OSMA and MA-OSEA algorithms.

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?

Thank you for your insightful question.

In our experiments, we have adopted the commonly used "inverse of distance" as our primary metric for utility. In addition to this, we also consider the number of targets in proximity to agents and the average distance between agents and targets as valuable indicators for evaluating the effectiveness of tracking algorithms.

To this end, we offer a comparison of our Algorithm 1, Algorithm 2, and the OSG algorithm based on these two indicators in the final two columns in Figure 3. The data clearly demonstrate that both of our algorithms outperform the OSG algorithm in terms of all these metrics. This comparison highlights the effectiveness of our approach in not only maximizing utility but also in optimizing the spatial distribution and proximity to targets.

Weaknesses:

1. The execution of the algorithm relies on the curvature parameter $c$. However, this parameter may be unknown beforehand.

Please refer to our response to the first question earlier.

I would like to thank the authors for the detailed responses. They address most of my concerns. And I would like to maintain my rating.

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?

First, let's revisit the definition of a submodular function. A set function $f:2^{V}\rightarrow\mathcal{R}_{+}$ is submodular if and only if for any $S\subseteq T\subseteq V$ and $e\in V\setminus T$, the following inequality holds:

$f(S\cup\{e\})-f(S)\ge f(T\cup\{e\})-f(T)$.

This definition means that the incremental benefit derived from adding an element to a set will diminish as the size of set grows larger, which is a mathematical expression of the well-known "diminishing-returns" principle in economics. As a result, it is evident that submodular objectives are extensively pervasive in contemporary economic activities. In addition, maximization of submodular functions has found numerous applications in machine learning, including data summarization (Lin & Bilmes, 2010; 2011; Wei et al., 2013; 2015), product recommendation (Kempe et al., 2003; El-Arini et al., 2009; Mirzasoleiman et al., 2016a) and in-context learning (Kumari et al., 2024). Broadly speaking, we assume here that the objective function is monotone submodular, which offers extensive applicability and encompasses a broad range of applications in machine learning.

Second, across a variety of scenarios of multi-robot coordination, the assumption of a monotone submodular objective function is not only standard but also has been rigorously validated by a multitude of theoretical frameworks (Zhou et al., 2018; Qu et al., 2019; Corah & Michael, 2021; Schlotfeldt et al., 2021; Krause et al., 2008). Generally speaking, the goal of multi-agent coordination is to better monitor and track other objects. From an information-theoretic perspective, it's all about gathering as much information as we can about other entities. In the context of information theory, entropy is a scientific concept that measures the expected amount of information needed to describe the state of the variable. Therefore, many tasks of multi-robot coordination (Corah & Michael, 2021;Zhou et al., 2018) embrace entropy as a metric to assess the information acquired and subsequently aim to (approximately) maximize it. It is important to note that the entropy function being monotone submodular has been highly validated via an extensive body of work, such as (Krause et al. (2008) ).

Finally, it is crucial to emphasize that, in our experiments, we adopted the same approximation for entropy as detailed in (Xu et al., 2023), assuming that the information acquired about each moving target is inversely proportional to the distance between the agent and the target. Despite this simplification, the objective remains a monotone submodular function.

Weaknesses:

1. Problem formulation

• 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?

Thank you for your comments.

To address your concerns, let's first revisit the multi-agent tracking scenarios. Specifically, at each time step $t\in[T]$, agents firstly select their directions of movement and speeds. Subsequently, the effectiveness of the agents' movement at time $t$ is evaluated based on the positions of targets at time $t+1$. Since the location information of the targets at time $t+1$ is not known in advance, we normally assume that the objective function is revealed after the agents have made their decisions.

Regarding your question on why the objective function is guaranteed to be submodular, we refer you to our previous response to the fourth question.

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.

Thank you for your suggestion. Initially, we had considered explicitly listing the constraints on the feedback of agents (Lines 177-178) as a distinct assumption. However, due to space limitations, we ultimately had to incorporate them within the Problem Formulation section. In response to your feedback, we are considering the addition of a new "Assumption" immediately following Line 181.

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 Questions and Weaknesses.

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?

Thanks for your question. It certainly highlights an aspect of our paper that deserves further clarification.

In the context of multi-target tracking tasks, each agent indeed shares the same movement space. However, it is crucial to emphasize that the "movement space" is conceptually distinct from the "action space" we consider. Generally speaking, the objective function of the multi-target tracking task is not solely dependent on the consistent "movement space". The key factor in shaping the objective function is which agent carries out which particular movement. To reflect the different role of each agent within the tracking system, we commonly assign unique identity tags to each movement.

To illustrate, in our experiments, we consider the movement decision space M={($\theta,s$): $s\in${5,10,15}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: $V_{i}=M\times${$i$}$=${$(\theta,s,i)$: $s\in${5,10,15}units/s, $\theta\in${$\frac{\pi}{4},\frac{\pi}{2},\frac{3\pi}{4},\pi,\dots,2\pi$} }, where the action $(\theta,s,i)$ indicates that agent $i$ moves towards the direction of $\theta$ at a speed of $s$.

With identification information included, these action sets are mutually disjoint, namely, $V_{i}\cap V_{j}$ for any $i\neq j\in${$1,2,\dots,20$}. Please note that this approach of distinguishing identities through tagging each decision is a widely adopted practice in multi-agent system, as exemplified in revenue maximization over multiple campaigns (Du et al., 2017; Aslay et al., 2017; Han et al., 2021), multi-round product marketing (Sun et al., 2018) and online multi-Ad slot allocation (Streeter et al.,2009).

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.

Thank you for your question. Next, we will briefly discuss the advantages of the multi-linear extension over the original submodular maximization problem from two aspects. Before we proceed, it is essential to emphasize that the superiority of multi-linear extension is widely recognized within the submodular optimization community.

a) Beyond Cardinality Constraint: When considering the simple cardinality constraint, t, (Nemhauser et al., 1978) demonstrated that the greedy algorithm can provide a tight $(1-1/e)$-approximation to the submodular maximization problem. However, when confronted with more complex matroid constraints, as shown in (Fisher et al., 1978), the greedy method only can guarantee a sub-optimal $1/2$-approximation to the submodular maximization problem. For a long period, how to achieve the tight $(1-1/e)$-approximation for the submodular maximization problem over matroid constraints remains an open question. It was not until the seminal works of (Calinescu et al., 2011; Chekuri et al., 2014) introduced the multi-linear extension and a series of rounding methods to improve the greedy method. Therefore, a notable benefit of the multi-linear extension is its capacity to enhance the approximation ratio of the greedy method over complex combinatorial constraints, which is the primary motivation behind our adoption of the multi-linear extension in this paper.

b) Adapting to complicated optimization scenarios: In recent years, the field of continuous optimization has seen the emergence of various efficient algorithmic frameworks. Consequently, another advantage of the multi-linear extension is its ability to leverage gradient information, potentially making it compatible with numerous scenarios of continuous optimization , , such as distributed settings (Mokhtari et al., 2018; Zhu et al., 2021; Zhang et al., 2023), online learning (Chen et al., 2018b;a; Zhang et al., 2022) and minimax optimization (Adibi et al., 2022; Zhang et al., 2024). In contrast, the tools available for discrete optimization are not only more limited but also often cumbersome.

Thank you for your detailed and insightful reviews. We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript. Your feedback is invaluable to us. In the following, we will address the concerns you have raised in the sections of Questions and Weaknesses.

Questions:

• Could you provide formal comments on the tightness of the communication complexity for both proposed algorithms?

We sincerely apologize for the confusion caused by our subtitle. We would like to clarify that, in this paper, we only claim that our $\frac{(1-e^{-c})}{c}$-approximation ratio is tight in a certain sense, as evidenced by Theorem 4.1. in (Vondrak, 2010). With respect to the communication graph, our main contribution is to relax the rigid requirement of a complete graph in the previous OSG algorithm, without asserting that our communication complexity is optimal.

Designing an optimal communication graph for Multi-Agent Online Submodular Maximization(MA-OSM) Problem is indeed a very interesting problem. There have been numerous studies exploring "how to design the graph topology while maintain an optimal convergence rate", as seen in (Chow et al., 2016; Song et al., 2022; Vogels et al., 2023). Applying these techniques to our Algorithms 1 and 2 is certainly a promising direction.

• 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.

Thank you very much for your suggestion. We had initially considered providing a thorough comparison of our Algorithms 1 and 2 against the work of [Razazadeh and Kia 2023] in the offline scenario within the main body of the paper. However, due to space limitations, we had to include this comparison in Appendix A.1 and Table 2.

In general, in the offline setting, compared to [Razazadeh and Kia 2023], our Algorithms 1 and 2 can achieve a $\frac{1-e^{-c}}{c}$-approximation with fewer queries to the submodular function. Specifically, [Razazadeh and Kia 2023] can achieve $(\frac{1-e^{-c}}{c})OPT-\epsilon$ at the cost of $O(\frac{n\log(\frac{1}{\epsilon})}{\epsilon^{3}})$ value queries to the submodular function. In contrast, our Algorithm 1 and Algorithm 2 only require inquiring the submodular objective $O(\frac{n}{\epsilon^{2}})$ and $O(\frac{n\log(\frac{1}{\epsilon})}{\epsilon^{2}})$ times to attain $(\frac{1-e^{-c}}{c})OPT-\epsilon$, if we view any incoming objective function $f_{t}$ as some fixed submodular set function $f$ and then return the set $\{\cup_{i\in\mathcal{N}}{a_{t,i}}\},\forall t\in[T]$ with probability $\frac{1}{T}$.

• The regret guarantee depends on $C_{T}$, the deviation of the maximizer sequence. Please specify how $C_{T}$ varies and impacts the regret guarantee.

Thank you very much for your question. In this paper, we have not made any assumptions regarding the deviation of the maximizer sequence $C_{T}$, which means $C_{T}$ may evolve in an unpredictable direction. For instance, if $C_{T}=O(T)$, neither our Algorithms 1 and 2 nor the OSG can achieve superior regret performance. This to some extent reflects the well-known ``no free lunch" theorem. Theoretically, as highlighted in (Besbes et al., 2015), if $C_{T}$ is linear in $T$, then no admissible policy can attain sub-linear regret.

• what does the subscript $d$ denote in the regret definition?

Thanks for your question. The subscript $d$ in the regret definition represents the dynamic regret. This $d$ is mainly used to distinguish from another common measure used to assess the performance of online algorithms, namely, static regret. We show the definition of static regret as follows:

$**Reg**^{s}_{\alpha}(T)=\alpha\max_{\mathcal{A}}\Big(\sum_{t=1}^{T}f_{t}(\mathcal{A})\Big)-\sum_{t=1}^{T}f_{t}(\cup_{i\in\N}\{a_{t,i}\})$.

Note that in static regret, we use the best static strategy as our benchmark. In contrast, in dynamic regret, we adopt a dynamically optimal strategy, that is,

$**Reg**^{d}_{\alpha}(T)=\alpha\sum_{t=1}^{T}f_{t}(\mathcal{A}_{t}^{*})-\sum_{t=1}^{T}f_{t}(\cup_{i\in\N}\{a_{t,i}\})$.

• 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.

Thank you very much for your feedback. We would like to clarify the meaning of `mixing a uniform distribution’.

The primary issue with KL-divergence is that as it approaches zero, its gradient tends towards infinity, which violates the Lipschitz condition. To circumvent this, we introduce a small perturbation in our decision vector to keep it away from the boundary. Specifically, in Algorithm 2, line 7, we mix a uniform distribution, namely, adding $\frac{1}{n}**1**$ to our decision vector. This ensures that our final decision stays away from the boundary. Note that $\frac{1}{n}**1**$ can be interpreted as a uniform distribution over all $n$ actions. The term ·mixing a uniform distribution' is commonly used in some bandit papers, which is why we adopted this phrasing. We apologize for any confusion this term may have caused.

• 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.

Thank you very much for your suggestion.

Due to space limitations in the main paper, we were unable to provide a more detailed description of the OSG algorithm. However, we can offer a brief overview of its core idea here. The OSG algorithm is fundamentally based on the standard greedy method. It operates by allowing one agent to select the best action from its action set and then communicates this choice to the other agents. Subsequently, the second agent selects the best action from its own action set based on the current knowledge and shares its choice with the remaining agents. This greedy iteration continues in a sequential manner.

Since the greedy method only can achieve a sub-optimal $\frac{1}{1+c}$-approximation for general submodular maximization problems (Fisher et al., 1978), the OSG algorithm also suffers from this limitation. This is the primary reason why OSG only achieves $\frac{1}{1+c}$-approximation solutions.

Thank you for your detailed and insightful reviews. We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript. Your feedback is invaluable to us. Below, we will respond to the concerns you have raised in Questions and Weaknesses.

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?

Firstly, in order to provide a clearer understanding of the computational cost associated with the general mirror projection in Algorithm 1, we will begin by introducing the standard methodological framework used to address a single constrained optimization problem.

1. We will consider the Lagrangian multiplier method, namely,

$L(\mathbf{b},\lambda)=(-\langle \Big[\tilde{\nabla}F_{t}^{s}(\mathbf{x}_{(t,i)})\Big]_V,\mathbf{b}\rangle+(1/\eta_t)\mathcal{D}_g (\mathbf{b}, \mathbf{y}_t)+\lambda(\sum b_k-1)$;

（Please note that due to LaTeX symbol issues in OpenReview, some subscripts may not be displayed.）

2. Then, fixing $\lambda\ge0$, we aim to find the optimal $\mathbf{b}^*(\lambda)=\arg\min L(\mathbf{b},\lambda)$;

3. Next, by substituting the optimal $\mathbf{b}^*(\lambda)$, we derive a one-dimensional function with respect to $\lambda$, i.e., $g(\lambda)=L(\mathbf{b}^*(\lambda),\lambda)$;

4. Finally, we find $\lambda^*=\arg\max g(\lambda)$ and obtain the optimal projection vector $\mathbf{b}^*=\mathbf{b}^*(\lambda^*)$.

From the algorithmic framework we have described, it is clear that the primary computational expense in the general mirror projection lies in the search for the optimal dual variable $\lambda^*=\arg\max g(\lambda)$. Even in the case of the Euclidean distance, the process of finding the optimal dual variable requires multiple iterations of binary search, as demonstrated in Appendix B in (Zhou et al., 2022). In contrast, when considering KL divergence, we can explicitly determine the optimal dual variable, as detailed in our Appendix E.

Secondly, to mitigate the issue that the gradient of the KL divergence tends to infinity when approaching the boundaries, we have incorporated a shift of $\frac{\gamma}{n}\mathbf{1}_{n}$ in Step 7 of Algorithm 2. This modification results in a regret deviation of $\log(T)$ for Algorithm 2.

• 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.

Thank you very much for your question.

Firstly, as indicated in (Grimsman et al., 2018), the approximation ratio of OSG will deteriorate in proportion to the size of the largest independent group of agents within the communication graph, as detailed in our Table 1. Generally speaking, the number of nodes in the largest independent set is highly correlated with the spectral information. Thus, based on the current known results, we can only conclude that spectral information influences the approximation ratio of OSG. Similarly, our analysis of algorithms MA-OSMA and MA-OSEA only reveals that spectral information impacts their regret bounds.

Secondly, to a certain extent, we can view our proposed Algorithms 1 and 2, as well as OSG, as the different trade-off paths between approximation ratio and regret. Specifically,

a) Our Algorithms 1 and 2 slightly sacrifice the regret bound to ensure a tight approximation ratio and reduce the communication burden;

b) On the contrary, OSG ensures a consistent $\widetilde{O}(\sqrt{C_{T}T})$ regret bound, but it will incur a significant communication overhead and a sub-optimal approximation guarantee.

Finally, we wish to emphasize that our chosen path significantly outperforms OSG. It is important to note that the theoretical results of OSG algorithm indicate that its regret bound will exhibit a deviation of $O(\log(T))$ compared to $O(\sqrt{C_{T}T}))$. Although the spectral information indeed affects the regret bound of our MA-OSMA, ensuring $\frac{1}{1-\beta}<C\log(T)$ for some constant $C$ is sufficient to guarantee that our MA-OSMA achieves superior performance in both regret bound and approximation ratio compared to the OSG algorithm. When the time-horizon $T$ is very large, a relatively sparse graph even can secure $\frac{1}{1-\beta}<<C\log(T)$ for some constant $C$.

Rezazadeh and Kia (2023). Distributed strategy selection: A submodular set function maximization approach. Automatica, 153:111000.

Schlotfeldt et al. (2021). Resilient active information acquisition with teams of robots. IEEE Transactions on Robotics, 38(1):244–261.

Song et al. (2022). Communication-efficient topologies for decentralized learning with o(1) consensus rate. Advances in Neural Information Processing Systems, 35:1073–1085.

Streeter et al. (2009). Online learning of assignments. Advances in neural information processing systems, 22.

Vogels et al. (2023). Beyond spectral gap: the role of the topology in decentralized learning. Journal of Machine Learning Research, 24(355):1–31.

Vondrák (2010). Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algorithms). RIMS Kokyuroku Bessatsu B, 23:253–266.

Wei et al. (2013). Using document summarization techniques for speech data subset selection. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 721–726.

Wei et al. (2015). Submodularity in data subset selection and active learning. In International conference on machine learning, pp. 1954–1963. PMLR.

Xu et al. (2023). Online submodular coordination with bounded tracking regret: Theory, algorithm, and applications to multi-robot coordination. IEEE Robotics and Automation Letters, 8(4):2261–2268.

Zhang et al. (2022). Stochastic continuous submodular maximization: Boosting via non-oblivious function. In International Conference on Machine Learning, pp. 26116–26134. PMLR.

Zhang et al. (2023). Communication-efficient decentralized online continuous dr-submodular maximization. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 3330–3339.

Zhang et al. (2024). Boosting gradient ascent for continuous dr-submodular maximization. arXiv preprint arXiv:2401.08330.

Zhou et al. (2018). Resilient active target tracking with multiple robots. IEEE Robotics and Automation Letters, 4(1):129–136.

Zhou et al. (2022). Probabilistic bilevel coreset selection. In International Conference on Machine Learning, pp. 27287–27302.

Zhu et al. (2021). Projection-free decentralized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research, 22(51):1