Distributed Epigraph Form Multi-Agent Safe Reinforcement Learning

Q5 (1/2): How to determine the sampling interval of $z$?

A5 (1/2): Thanks for the question! We sample $z$ uniformly from $[z_\mathrm{min}, z_\mathrm{max}]$. While we have briefly introduced the choice of the sampling interval of $z$ in Appendix D.3 and Table 4 in the original submission, here we provide a more detailed explanation of the choice of $z_\mathrm{min}$ and $z_\mathrm{max}$.

Since $z_\mathrm{min}$ represents an estimate of the minimum cost incurred by the MAS, we set it to a small negative number $-0.5$. We set $z_\mathrm{max}$ differently depending on the complexity of the environment.

MPE

For $z_\mathrm{max}$, with maximum simulation timestep $T$, we estimate it in the MPE environments using the following equation:

$$z_\mathrm{max} = \tilde{l}_\mathrm{max} * T,$$ $$\tilde{l}\_\mathrm{max} = \mathrm{initdist}\_{\max} \\, w_\mathrm{distance} + w_\mathrm{reach} + u_\mathrm{max} w_\mathrm{control}$$

where $\tilde{l}_\mathrm{max}$ is a conservative estimate of the maximum cost $l$. This is conservative in the sense that this reflects the case where

• the agents and goals are initialized with the maximum possible distance ($\mathrm{initdist}_{\max}$)
• the agents do not reach their goal throughout their trajectory
• the agents incur the maximum control cost for all timesteps

$w_\mathrm{distance}$, $w_\mathrm{reach}$, and $w_\mathrm{control}$ denote the corresponding weights of the different cost terms in the cost function $l$ in (62) and (63) of the original submission.

Multi-agent MuJoCo

For the multi-agent MuJoCo environments, we first train the agents with (unconstrained) MAPPO with different random seeds, record the largest cost incurred, double it, and then use that as $z_\mathrm{max}$.

We have added the above discussion in Appendix E.3 in the revised paper.

---

Q5 (2/2): What will happen if we choose the interval too large or too small?

A5 (2/2): Good question. We perform an additional experiment in the Spread environment where we scale the value of $z_\mathrm{max}$ used for sampling $z$, and denote by $z_\mathrm{max, orig}$ the original value used in the paper, i.e., $z_\mathrm{max} / z_\mathrm{max, orig} = 1.0$ uses the same value as in the paper.

We see both safety and costs do not change much even when our estimate of the maximum cost $z_\mathrm{max}$ changes by up to $50\\%$. However, if $z_\mathrm{max}$ is too large (e.g., $2 z_\mathrm{max, orig}$), the policy becomes too conservative because not enough samples of $z$ that are near $z^*$ are observed, reducing the sample efficiency. On the other hand, when $z_\mathrm{max}$ is too small (e.g., $0.25 z_\mathrm{max, orig}$), there may be states where the optimal $z^*$ does not fall within the sampled range. This causes the rootfinding step to be inaccurate, as $V^h$ will be queried at values of $z$ that were not seen during training, resulting in safety violations.

We have added the new experimental results and the discussion on the choice of sampling interval for $z$ in Appendix E.7.

We really appreciate the valuable questions raised, especially the questions that point out two important confusions (Q2 and Q3). We address all questions below.

In brief, we:

1. Clarify the confusion in our propositions
2. Revise the proof of Theorem 1 to be more concise
3. Provide additional experimental results to demonstrate the influence of the sampling interval of $z$

We sincerely hope that our reply addresses the reviewer's concerns.

Detailed replies

Q1, Q4: Is the multi-agent system considered homogeneous or heterogeneous? Is MAPPO or HAPPO used? The authors are suggested to incorporate the update formulas of NNs in the appendix.

A1, A4: We consider homogeneous multi-agent systems and hence use MAPPO. We have clarified that the MAS is homogeneous in the revised version (Section 3.1). Following your suggestion, we have also included detailed update formulas for the NNs in Appendix E.3 in the revised paper.

---

Q2 (1/2): (6) is not the correct Lagrangian for (3). Please provide the correct form of the Lagrangian for (3), and ensure the comparison between your method and the Lagrangian method is accurate.

A2 (1/2): We apologize for the confusion. (6) is not the Lagrangian of (3). The CMDP setting has the constraint

$$\sum_{k=0}^\infty c(x^k) \leq d$$

The zero constraint violation CMDP setting uses $c \geq 0$ and $d=0$. Since our constraint $h$ in (3) takes negative values, we can translate it to the zero constraint violation setting by taking

$$c(x) := \max\\{ 0, h(x) \\},$$

which results in the constraint optimization problem

\min_\pi J(\pi) \quad \mathrm{s.t.} \quad \sum_{k=0}^\infty \max\big\\{0, h(x^k) \big\\} \leq 0

The Lagrangian of the above is then

$$\max_{\lambda \geq 0} \min_\pi J(\pi) + \lambda \sum_{k=0}^\infty \max\\{0, h(x^k)\\}$$

which is what we intended to mean with (6).

We have corrected this and included the above explanation in the revised version in the "Comparison with the Lagrangian method" paragraph in Section 3.2.

Q2 (2/2): Can your method reduce computational complexity for example?

A2 (2/2): We do not reduce computational complexity. The training time of our method is similar to that of Lagrangian methods. While we have provided the training time of our method in Appendix D.1 in the original submission (Appendix E.1 in the revised paper), now we also add the training time of baselines in Appendix E.1 in the revised paper for comparison.

---

Q3: Proposition 1 is wrong. Neither $h(x^k)$ nor $V(x^{k+1},z^{k+1};\pi)$ is a function of $u^k$. It also seems that the proposed algorithm is irrelated to Proposition 1.

A3: The $\min_{u^k}$ in Proposition 1 is a typo. Thanks for spotting it! We have deleted the erroneous $\min_{u^k}$ from Proposition 1 in our revised paper.

To answer the second part, we want to emphasize that Proposition 1 is actually key to our paper:

1. Satisfying dynamic programming implies that the value function is Markovian. In other words, for a given $z^0$, the value at the $k$-th timestep is only a function of $z^k$ and $x^k$ instead of the $z^0$ and the entire trajectory up to the $k$-th timestep.
2. Consequently, this implies that the optimal policy is also Markovian and is only a function of $z^k$ and $x^k$.
3. Rephrased differently, since the value function is Markovian, this implies that, for a given $z^0$ and $x^0$, the value at the $k$-th timestep is equal to the value (at the initial timestep) of a new problem where we start with $\tilde{z}^0 = z^k$ and $\tilde{x}^0 = x^k$.
4. Since we relate the value function of consecutive timesteps, given a value function estimator, we can now control the bias-variance tradeoff of the value function estimate by using $k$-step estimates instead of the Monte Carlo estimates.
5. Instead of only using the $k$-step estimates for a single choice of $k$, we can compute a weighted average of the $k$-step estimates as in GAE to further control the bias-variance tradeoff.

In the revision, we expand on our existing discussion in Appendix C to avoid future confusion. Thanks for bringing this topic!

Thanks for the additional comments.

Q1 (1/2): Based on the responses to Q2 and Q5, we find that the proposed epigraph form-based method can be unpractical in real-world scenarios due to the challenge of determining the sampling interval of the auxiliary variable $z$ (sometimes we even need to train the agents with some unsafe MARL algorithms to determine this interval).

R1 (1/2): The sampling interval of $z$ is a hyperparameter. However, since $z$ is the desired cost upper bound, the heuristics we propose provide very good estimates of this hyperparameter which require at most one run of a MARL algorithm.

In contrast, other safe MARL algorithms require much more than one run to find good performing hyperparameters (e.g., static Lagrange multiplier, Lagrange multiplier learning rate).

From this perspective, we argue that our proposed method is more practical than existing safe MARL methods.

---

Q1 (2/2): The manuscript does not clarify whether $z$ has any physical meaning.

R1 (2/2): We have mentioned multiple times in the paper that $z$ is a desired cost upper bound (e.g., Line 191, 220, 221). Hence, $z$ has the same units as the cost. For example, if the objective is to minimize the sum of the distance to the goal (meters), then $z$ has units of meters.

Line 183 and Line 190 provide an explanation of why $z$ can be interpreted as a cost upper bound.

In contrast, the Lagrange multiplier has units of (objective units) / (constraint units). We believe it is easier to interpret units of the objective than it is to interpret the ratio of objective units to constraint units.

---

Q2 (1/2): In Remark 1 and the proof of Theorem 1, the authors repeatedly attempt to justify that the maximum function (see the constraint in (13b)) can be replaced by a single function. We believe this replacement is not theoretically rigorous.

R2 (1/2): Thanks for the feedback! We agree our statements in Remark 1 could be more rigorous and have fixed this in the revised version.

Specifically, instead of using notations that could be misinterpreted as equality of functions (e.g., $V = V^l$ or $V = V^h$), we clarify that we mean that the function evaluations at certain arguments are equal, e.g., for a specific $x$, $z$, and $\pi$ that

$$V(x, z; \pi) = V^l(x; \pi) \qquad \text{ or } \qquad V(x, z; \pi) = V^h(x; \pi).$$

However, we disagree that the proof of Theorem 1 is not theoretically rigorous. If the reviewer is confident that the proof of Theorem 1 is not rigorous, please point us to a specific line in the proof that we may have overlooked.

---

Q2 (2/2): In the proof of Theorem 1, a lot of new optimization problems which are different from the original problem are proposed and discussed. As a result, the contribution of this work is still questionable.

R2 (2/2): In the proof of Theorem 1, we first prove Lemma 1, which is the single-agent version of Theorem 1. We then show that Lemma 1 (single-agent version) implies Theorem 1 (multi-agent version). Only one optimization problem (17) is introduced, in Lemma 1. We do not believe that introducing a new optimization problem in our proof makes the contribution of the paper questionable.

---

Q3: Another serious problem is that the authors replace the initial state distribution in the constraint of the original problem (see 5(b)) with an arbitrary state distribution in (15b). Based on the arbitrary state distribution, the authors state that they need to solve the outer problem in a distributed manner, which becomes one key contribution of this work. However, if the agents are initialized based on the initial distribution, there is no need to solve the outer problem in the distributed manner.

R3: We kindly remind the reviewer that we consider deterministic dynamics (1). Moreover, the problem we wish to solve (2) is conditioned on $x^0$, and we wish to solve (2) over all $x^0$. Consequently, all the optimization problems that we solve are also conditioned on $x^0$.

In particular, (5) is conditioned on $x^0$. This means the solution $z^\*$ to (5) will be different for different $x^0$. Since the $x^0$ used during test time is not known in advance, we can not solve (5) in advance.

Finally, there is no initial state distribution in our problem, and we have not mentioned the word "distribution" at all in the entire paper.

We would like to thank the reviewer for finding our approach novel and for acknowledging our comparison to existing theoretical approaches.

1. What are the global guarantees on the safety aspect when using the proposed epigraph formulation?

A1: As introduced in Section 4.1 of the original submission, the proposed epigraph formulation is equivalent to the original multi-agent constraint optimal control problem. Therefore, solving the epigraph formulation has the same global guarantees on the safety aspect as the original problem. For more information on the equivalence, we have added the proof in Appendix G in the revised version.

---

2. Do the methods proposed in the empirical evaluation solve the tasks? If so, why the author does not report the mean global success rate/ mean global return?

A2: We already report the mean global return. The cost $l$ in our paper is equivalent to the negation of the global return, and is NOT the cost in the CMDP setting. The cost in our paper, defined in Line 148 of the original paper, refers to the objective function rather than the constraints and is a measurement of task completion instead of safety. This is the convention used in optimal control (see [α, β, γ]), and can be translated to the reward maximization setting by taking the cost $l$ as the negative of the reward function.

We define the cost function $l$ we use in our experiments using the distance to the goal and the control penalty (Appendix D.2 in the original submission), which correspond to task completion. Hence, lower costs mean that the agents better complete the given task.

The global return = global cumulative cost is already reported in Figure 3 and Figure 6. Algorithms that incur less cost (x-axis) solve the task better.

Since our approach is motivated by optimal control techniques and uses an optimal control problem formulation, we maintain our use of the word "cost" to refer to the objective to match the convention of the optimal control community.

However, to prevent confusion, we have added the following sentence in the revised paper when defining the cost $l$:

Given a global cost function $l: \mathcal X\times\mathcal U\to\mathbb R$ describing the task for the agents to accomplish

We have also added a footnote in the revised paper to explain the relationship with the CMDP setting:

The cost function $l$ is not the cost in CMDP. Rather, it corresponds to the negation of the reward in CMDP.

---

3. This decentralized approach primarily guarantees "constraint satisfaction" rather than task completion, meaning that while the agents may stay safe, they might not achieve the global objective if staying in place satisfies the constraints without addressing the task goals.

A3: As clarified in the above answer, the cost minimization is concerned with task completion and is separate from satisfying the safety constraints. Theorem 1 states that we can solve for the outer problem — finding the $z$ that optimizes for task performance subject to safety constraints — in a distributed way that yields the same optimal solution as the original centralized approach and thus achieves the optimal task completion that can be achieved while maintaining safety.

A policy $\pi$ that "stays in place" would be safe and hence have a low constraint value function $V^h$. However, since the task is not being achieved, the cost value function $V^l$ for task completion would be high. Such a $\pi$ could be optimal if $z$ is large enough, where the total value function

$$V(x, z; \pi) = \max\{ V^h(x, \pi), V^l(x, \pi) - z \} = V^h(x, \pi)$$

would be equal to $V^h$, and hence $\pi$ which optimizes for safety is optimal.

However, for a smaller $z$ such that $V(x, z; \pi) = V^l(x, \pi) - z$, this $\pi$ would not be optimal. Instead, the optimal policy for this smaller $z$ would need to minimize $V^l$ by completing the task. Different values of $z$ then balance between the two objectives.

The optimal $z$, found by solving (10a) in the original version and (13a) in the revised version, or equivalently solved decentralized using Theorem 1, will find the $z$ that results in the lowest cost, i.e., most task completion, while still maintaining safety.

References

[α] Todorov, Emanuel. "Compositionality of optimal control laws." NeurIPS 2009.

[β] Chow, Yinlam, et al. "A lyapunov-based approach to safe reinforcement learning." NeurIPS 2018.

[γ] Li, Yingying, Xin Chen, and Na Li. "Online optimal control with linear dynamics and predictions: Algorithms and regret analysis." NeurIPS 2019.

Dear Reviewer tD17,

Thank you again for the constructive questions. We have addressed them in our previous replies accordingly. For a brief summary, we have:

1. Explained that we did report the performance of solving the task, which might have been a very important misunderstanding of the reviewer.
2. Explained the scalability and the use of GNN.
3. Discussed about more related works.
4. Clarified some notations.

As the discussion period deadline approaches, we sincerely want to know if our reply has addressed your concerns. If so, would you please kindly raise your score? We are also happy to answer any further questions you have.

We thank the reviewer for their constructive remarks on our paper and for raising important questions.

1. The Lagrangian multiplier, $\lambda$, may also decrease depending on various Lagrangian version configurations.

A1: This is true only if the constraint can take negative values. More specifically, if the CMDP constraint is

$$\sum_{k=0}^\infty c(x^k) \leq d,$$

then the Lagrange multiplier update is $\sum_{k=0}^\infty c(x^k) - d$, which could be negative depending on the choice of $c$ and $d$.

However, in the zero constraint violation setting that we are targeting, $c(x^k) \geq 0$ and $d = 0$. In this setting, $\lambda$ does not decrease because $\sum_{k=0}^\infty c(x^k) - d \geq 0$

In the revised paper, we have expanded on this explanation (see Paragraph "Comparison with the Lagrangian method" in Section 3.2).

---

2. The performance of the Lagrangian method depends on the parameter settings for different tasks. In my understanding, if we fine-tune the Lagrangian parameters, the Lagrangian method can also perform better.

A2: We agree with the reviewer on this observation. This also matches what we have observed in our experiments — for the Lagrangian method, the performance using the same hyperparameters varies greatly on different tasks. This is an advantage of our algorithm since we only need to use one set of hyperparameters to consistently outperform the baselines in all environments.

In our experiments, we have explored the following settings:

1. The Lagrange multiplier is held static during training. In this case, larger values of Lagrange multipliers result in conservative policies that have a high cost (InforMARL-L(5)), while small values of Lagrange multipliers result in aggressive policies that violate safety constraints (InforMARL-L(1)). Our method, however, consistently outperforms both of them without hyperparameter tuning. In addition, using a non-optimal Lagrange multiplier can cause the optimal solution to change (Section 5.2, paragraph 2). Therefore, even if the optimal policy is found, this is not the optimal policy of the original problem. The optimal policy of the original problem is recovered only if the Lagrange multiplier used is optimal. However, searching for the optimal Lagrange multiplier can require many runs, which we would like to avoid, especially in tasks where each run takes 6 hours to run.

2. The Lagrange multiplier is learned during training. We have shown in Figure 5 that this causes unstable training. This empirical result is also supported by our theoretical analysis in the paragraph "Comparison with the Lagrangian method" in Section 3.2.

Our proposed method outperforms both settings. Therefore, as claimed in the contributions, our algorithm achieves stable training and does not require hyperparameter tuning.

---

3. Can the study provide a convergence analysis?

A3: Thanks for the suggestion! We have added a convergence analysis in Appendix F to our revised version that shows that the policy of the inner RL problem (13b in the revised version) converges almost surely to a locally optimal policy.

In short, since the training of our algorithm is centralized, we can reduce the inner problem to a single-agent avoid RL problem by defining a suitable augmented state and a set of augmented dynamics. We then obtain the result by following the convergence analysis of single-agent avoid RL from existing works.