Robust and Diverse Multi-Agent Learning via Rational Policy Gradient

Thank you for your review. We are grateful that you highlighted our “novel algorithm” and that the paper "empirically demonstrates the method outperforms existing baselines". We address each point individually:

“(1) The experiments are too toy. Four primary environment such as matrix games, Overcooked, STORM, Hanabi are performed. These experiments are too easy and only few agents play. More complex experiments should be performed,such as Markov Games with more agents, or "StarCraft II"

Our experiments use the same environments as many recent related research. Overcooked and Hanabi are regularly used to test various SOTA algorithms for cooperative environments. Indeed, Hanabi was identified as a challenge domain (Bard, Nolan, et al. "The hanabi challenge: A new frontier for AI research.") that remains unsolved and in which existing algorithms (i.e., the algorithms used to solve Go) fail. Furthermore, the game is far from small considering how many possible combinations and sequences of cards each player can have and the fact that players need to communicate hidden information.

“Is it suitable for large number agents, or large scale Markov Game … ?”

In principle, all of our algorithms should scale to a large number of agents and larger Markov games. We observed a constant linear overhead (between 1.5-3 times) over existing algorithms across our experiments (a detail that we will include in the final version of the paper). We believe that further implementation and scaling compute resources will allow the algorithms to scale to these larger settings with the same benefits observed in our experiments.

“There are some format error such as lacking ‘conclusion’ …”

We will add a proper conclusion with the extra page allowed for the camera-ready version. Here is a draft:

We introduce the problem of rationality-preserving policy optimization and give a solution in the form of a gradient-based algorithm called rational policy gradient (RPG). We demonstrate the diverse uses of RPG by constructing algorithms that robustify agents, expose rational adversarial examples, and learn genuinely diverse behaviors across general-sum settings. Our results highlight that the success of adversarial optimization in zero-sum training methods can be extended to the general-sum setting and we aim to inspire further research in this direction. Furthermore, we hope that the generality of RPG will enable the development of entirely new classes of adversarial optimization algorithms in general-sum settings.

“Details of neural networks should be given...”

Thank you for catching this. Most hyperparameters for the experiments are given in appendix E.3 but we missed details about the neural network architecture: we used a network with two hidden layers of size 64 in Overcooked, STORM, and the matrix games, and two hidden layers with size 512 in Hanabi. The architecture is taken from a popular open-source implementation for self-play policies in these environments (Rutherford, Alexander, et al. "Jaxmarl: Multi-agent rl environments and algorithms in jax."). These details will be added in the final version.

“‘Only pseudocode is available. How to obtain the open‑source code?’”

We will include a link to a full open-source implementation of the code in the final version of the paper along with scripts for reproducing the paper’s experiments.

Thank you for your review. We appreciate your noting that our “paper has a significant impact on the community” and that the experiments are “rigorously conducted.” We address each point individually:

“(-) I believe the three joint policies (pi_adversary, pi_victim), (pi_i, pi_-i) , (pi_1,…, pi_m) are sometimes used interchangeably, making Section 3.2, among others, hard to follow. While I believe it clarifies section 3.1, using all three of them is overwhelming.”

“While RPO and RPG are defined for n-player stochastic games, experiments are two-player ones. Linked to the clarity issues of the three different joint-policies mathematical expression, wouldn’t it be clearer only to use i and -i.And maybe to define everything in a two-player game and state that it generalizes to n-player ones. Especially because pi_-i, the co-player policy, can represent a single or a joint policy without problem in the definition.”

Thank you for this feedback – we agree that the amount of notation through section 3 is overwhelming and we will improve this in the final version. We agree that it would be most clear to simply use i and -i in as many places as possible (potentially simply eliminating pi_adversary and pi_victim). However, the reason we also use the (pi_1,…, pi_m) is because even while the underlying game might only involve two players, the optimization problem on top of that game could involve more than two policies. For example, the adversarial diversity algorithm aims to find a set of N pairs of policies that are as diverse (i.e. incompatible) as possible. The choice of N can be larger than 2. We will do a better job of clarifying this distinction in Section 3 and simplify the notation where possible.

“What is the overhead of duplicating all agents and training several policies at the same time? I’d be happy to have an incentive for the computational cost of the approach and its scalability with more than two agents.”

We agree that this is an important detail to add to the paper and will add it to the final version for each of our experiments. On average, the original adversarial diversity algorithm with a population size of 2 is 2 times slower in wall-clock time (per step) than self-play while the AD-RPG (ours) is an additional 3 times slower than AD (due to the extra cost of manipulator policies and computing higher-order gradients). The computational overhead of the higher-order gradients is constant in the number of agents so the method should scale well beyond two agents. However, we will leave this investigation for future work. Moreover, recent works have demonstrated paths for further scaling higher-order gradients (Logan, et al. "Optimizing ml training with metagradient descent").

“At the beginning of the paper, zero-sum games are not considered because self-sabotage has no meaning in that setting. However, this method could also improve the learning of policies in a competitive setting, especially when considering the first three claims empirically demonstrated. Did you try the algorithm in a competitive setting?”

The main reason we did not test our algorithm in a zero-sum setting is because RPO is a strict-generalization of the associated algorithms from the zero-sum setting (explained on lines 121-124 of the submission) since adversarial incentives (minimizing your opponent’s reward) and individual incentives (maximize your own score) coincide. For example, AT-RPO simply reduces to the same problem as AT in the zero-sum setting. Because of this, we believed that using RPG in the zero-sum setting would just add unnecessary complexity to the algorithm. However, inspired by your question, we decided to empirically test our implementation of RPG in a zero-sum setting. We picked the matrix game of rock-paper-scissors:

and tested both AT and AT-RPG. Both methods have very similar behavior in which the adversary and victim oscillate between picking rock, paper, or scissors during training (similar to the oscillating behavior in Figure 13). We found that increasing the lookahead (e.g. greater than 8) in AT-RPG led to this behavior stabilizing and converging on playing the strategy that randomizes across the three actions (in the same way lookahead stabilizes the oscillations in Figure 13). Thank you for asking this question – we will include these results in the final-version and believe it will strengthen the paper.

“The paper lacks a proper conclusion …”

We will add a proper conclusion with the extra page allowed for the camera-ready version. Here is a draft:

We introduce the problem of rationality-preserving policy optimization and give a solution in the form of a gradient-based algorithm called rational policy gradient (RPG). We demonstrate the diverse uses of RPG by constructing algorithms that robustify agents, expose rational adversarial examples, and learn genuinely diverse behaviors across general-sum settings. Our results highlight that the success of adversarial optimization in zero-sum training methods can be extended to the general-sum setting and we aim to inspire further research in this direction. Furthermore, we hope that the generality of RPG will enable the development of entirely new classes of adversarial optimization algorithms in general-sum settings.

“Implicitly, the Hanabi games tested are two‑player, but it should be stated explicitly.”

We will state this in section 5.4 and the caption of Fig 7.

“Typo line 160 peusocode” and “Line 35”

Thank you for the clarification suggestion – the typo will be fixed, and the line‑35 clarification added.

Thank you for your review. We are glad you found the work “well‑motivated” with “extensive experiments” and a “principled optimisation formalism.” We address each point individually:

“Experiments remain in small/2-agent domains, although the formulation is pretty generalized.”

Our experiments use the same environments as many recent related research. Overcooked and Hanabi are regularly used to test various SOTA algorithms for cooperative environments. Indeed, Hanabi was identified as a challenge domain (Bard, Nolan, et al. "The hanabi challenge: A new frontier for AI research.") that still remains unsolved.

“L123, BR is a policy right? BR = \arg\max U(\pi_{i}, \pi_{-i}) for rigorousness?”

Thank you for catching this – this is a typo and will be fixed in the final version.

“No clear explanation on O_i and L_dice in this paper …”

O_i is the optimization objective for agent i. For example, in the case of adversarial training, for agent adversary, O_adversary = min_{π_adversary} U_victim (π_victim , π_adversary). It is first introduced in section 3.2 but we will add an explanation of the notation to the preliminary section for clarity.

L_dice is formally defined in the appendix in section E.1 in equation (10), but we agree that this is an important detail to include in the main section and will include it in Section 4 with the extra page allowed in the final version.

“Theoretically unclear why the method can prevent self‑sabotage, and the paper does not define self‑sabotage formally.” What is “self-sabotage”, can you give a formal definition / theorem? It was first documented in Cui et al 2023 but I think it was just described instead of officially formalized.”

Similar to existing work, we characterize self-sabotage as a general phenomenon when agents act against their own interests in order to minimize another player’s reward as part of an optimization problem. We do formally define Rationality-preserving Policy Optimization (Definition 3.1 on line 105) which we believe encapsulates the underlying issue behind self-sabotage by preventing agents from acting against their own interests.

“Moreover, the self-sabotage issue described in this paper and Cui et al 2023 can be easily patched by masking out invalid actions with large negative values?

Unfortunately, the self-sabotage issue cannot simply be solved by masking out invalid actions. The sabotaging behavior is characterized as an entire state-action policy, involving a long sequence of actions and interactions that result in self-sabotage. It’s not clear how to precompute all of the policies that result in self-sabotaging behavior and it’s also not clear how to mask out this precomputed set of self-sabotaging policies during the optimization.

“The method looks pretty like a fixed-size population version of CoMeDi combined with DiCE update. So I am not sure how the authors compare a fixed-size population method with an iterative-expanding population method to make sure it is a fair comparison.”

Our algorithm aims to solve the self-sabotage problem in a fundamentally different way than CoMeDi. While CoMeDi aims to limit the ability of agents to identify whether they are in self-play or cross-play during training, RPG entirely removes the incentive to self-sabotage. Appendix C includes a lengthy discussion of how RPG compares to existing approaches (including CoMeDi) and how our method overcomes the limitations of methods such as CoMeDi. Our paper demonstrates that CoMeDi fails to prevent self-sabotage in any of the environments and we don’t see how anything would improve for CoMeDi if it were changed to simultaneously learn the fixed-size population (as done with AT-RPG). Moreover, RPG is applicable to a wide range of adversarial optimization problems, whereas CoMeDi only applies to adversarial diversity.

“Sample variance grows with look‑ahead steps.”

We are not sure this is necessarily true and would appreciate any more intuition behind this claim. In the limit of look-ahead steps the base agent converges to some minima which could end up being very similar behavior (i.e., low variance). Some long-term meta-gradient approaches take advantage of this property using the implicit function theorem (which we leave to future work). Existing meta-gradient approaches (that use lookahead) have scaled to large settings with long lookahead (50+ step lookahead in Engstrom, Logan, et al. "Optimizing ml training with metagradient descent."), so we believe there is a lot of potential for RPG to further scale.

“Related‑work omissions (Charakorn 2023, Rahman 2024).”

Thank you for bringing these to our attention. We will include a discussion of these related works in the final version.

Thanks authors for providing this draft definition. I think the definition makes sense. Another suggestion is that your algorithm part might be missing an iteration loop through all players when updating $\theta'$, a mixture usgae of $k$ and $m$, and many narrations or paper organization could be clearer. Looking forward to the next revision of it.

Thank you for your review. We appreciate that “the paper gives an insightful theoretical framing” and the “insights drawn from [the examples] are compelling”. We address each point individually:

“Regarding Claim 3: Finding rational adversarial examples… it is unclear how this conclusion is drawn.”

Figure 7 is quite nuanced and we will clarify each of the columns in the final version. If we understand your questions correctly, then your suggested (a) is in fact the AP-RPG and PAIRED-A-RPG columns: these are two different methods for constructing “worst-case but rational” adversaries against the different victims represented by the rows. The conclusion “PAIRED-A-RPG is more effective than AP-RPG” is drawn because between those two columns, PAIRED-A-RPG more consistently finds the worst-case (by achieving the lower score) than AP-RPG. Your suggestion for “(b) a no-attack baseline” is represented by the column “Training”: this shows the performance that the policy gets at the end of training (when paired with itself). Finally, the column “AP” simply demonstrates that the AP algorithm acts irrationally and always achieves zero reward. Thank you for raising these points since we believe this clarification will help the reader better understand the evidence supporting claim 3.

“Include a conclusion section …”

We will add a proper conclusion with the extra page allowed for the camera-ready version. Here is a draft:

We introduce the problem of rationality-preserving policy optimization and give a solution in the form of a gradient-based algorithm called rational policy gradient (RPG). We demonstrate the diverse uses of RPG by constructing algorithms that robustify agents, expose rational adversarial examples, and learn genuinely diverse behaviors across general-sum settings. Our results highlight that the success of adversarial optimization in zero-sum training methods can be extended to the general-sum setting and we aim to inspire further research in this direction. Furthermore, we hope that the generality of RPG will enable the development of entirely new classes of adversarial optimization algorithms in general-sum settings.

“Could the authors clarify what the variable n represents … ?”

The n in equation (4) should be an m, the number of policies in the optimization problem. The capital N variable in Algorithm 1 is the number of lookahead steps. We will add this clarification the caption of Figure 3. Thank you for improving the clarity of the paper with these comments.

“Are there any guidelines or intuitions for selecting the hyperparameters in Algorithm 1?”

This is a great question, a discussion of these hyperparameters can be found in appendix E.2 under section “Variable learning rates”, but will consider elevating it to the main text to make this point more visible. We often found it important to use a larger manipulator learning rate (alpha_2) than base agent learning rate (alpha_3) to magnify the manipulator’s ability to influence the base agent’s learning. A larger inner base agent learning rate (alpha_1) allows the manipulator to project the base agent’s update further into the future, similar to using additional lookahead steps.

“There seems to be an inconsistency between the text and figure caption: Line 260 states that five policies are trained with different random seeds, while the caption of Figure 5 mentions two seeds. Please clarify the exact number of seeds used when evaluating robustness claims.”

We agree that the wording is confusing and will be fixed in the final version. There are indeed 5 seeds per algorithm. The cross-play grids in Figure 5 depict the average score that a specific pair (i.e., “two seeds”) of policies get when paired as teammates in the two-player game.

“In Figure 7, could you confirm whether the values under the adversarial attack columns refer to: (a) performance during adversarial training, or (b) performance after training without adversaries and testing with adversarial attacks?

It is (b), the performance when testing with an adversarial attack (although some of the rows were also trained with adversarial methods). We agree that the explanation of this figure needs to be improved and will clarify this point along with your previous comments related to this figure.

Additionally, as the content is tabular, it may be clearer to present it as a table rather than a figure.”

Thank you for the suggestion, we will edit this in the final version.

Thank you for your review. We appreciate your recognition that we “address an important and understudied failure mode” with “comprehensive experiments.” We address each point individually:

“the mathematical formulation of the core problem is vague. For instance, the exact nature of the adversarial optimization problem being generalized is not clearly defined (e.g., is it a Markov game? Is the environment shared or decentralized?). The rationality constraint (Definition 3.1) is stated informally as “πi ∈ BR(π−i′)”, but the space of allowable π−i′ is not precisely defined. Are these stationary policies, stochastic, or deterministic?”

Section 2 contains some of these details: the problem is a general-sum partially-observable stochastic game (also known as a Markov game); the observations can be shared, decentralized, or partially shared according to the observation function O : S × A × Ω → [0, 1]; and the policies are stochastic. We agree that these points are important and will be made more clear in the final version. The space of allowable π−i′ is the entire space Π−i and we will add this to the final version. Thank you for identifying these points as this will make the paper easier to understand.

“Are manipulators optimized simultaneously with base agents, or is there an alternating schedule? Is there any stability concern when both influence each other via nested gradients?”

The manipulators are indeed optimized simultaneously with the base agents. The updates in equations (3) and (4) happen together on each time step. Alternating or nested optimization schedules is a very interesting direction for future research. Stability concerns are often an issue in multi-agent learning settings and we did observe oscillating behaviors in certain matrix games that are known to have unstable equilibrium (Figure 13). However, increasing the number of lookahead steps in RPG actually leads to stabilizing this oscillating behavior (also in Figure 13). Further exploring the ability for manipulators to stabilize multi-agent learning dynamics would be another exciting direction for future research.