- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors optimise mechanism parameters in two-player Markov games under quantal best response, extending prior work beyond closed-form two-player MARL settings. Since stochastic transitions and large state spaces preclude closed-form equilibria and make black-box MARL-in-the-loop optimisation intractable, they propose a gradient-based framework with two components: (1) a set of representative policies to avoid the intractable full policy space, and (2) implicit differentiation of equilibrium conditions over these policies. They prove the surrogate gradient approximates the full-space gradient and analyse convergence properties. Evaluated on transition dynamics modification among other metrics, the method outperforms some baselines.
Critical strengths
The paper addresses a rea problem in MARL and proposes valid tractable solutions.
The solution concept and relevant, and somewhat convincing that it poses an advancement to state-of-the-art MARL.
Proofs are sound and correct in general, no major discrepancies that I could notice.
Critical weaknesses
Relatively incremental, the authors propose method that enhances established MARL algorithms by introducing representative policies and implicit differentiation, both of which are already explored in literature [1,2]. The authors combine both approaches to tackle intracractability, and show better performance - however, we would expect that to be the case, and possibly some negative results in edge cases (which are not explored).
The assumptions are relatively strong, approximate best response, Lipschitz continuity, and twice differentiable smoothness provide conditions that make the convergence proof naturally easy to obtain - the technical challenge is not too high.
[1] Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., & Graepel, T. (2017). A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning. Advances in Neural Information Processing Systems, 30.
[2] Ling, C. K., Fang, F., & Kolter, J. Z. (2018). What Game Are We Playing? End-to-end Learning in Normal and Extensive Form Games. Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp. 396–402.
Questions for authors
What efforts need to be done to extend this to more than a two player setting?
What happens when representative policies are selected poorly? Are there consequences in which the implicit differentiation can assist? Are there safeguards against?
In Fig. 1 why is just kind of separate?
Elaborating on the weakness, I would assume in a game like AI Economist, the state-action-reward geometry could be non smooth ... yet the convergence proofs assume a lot of Lipschitz smoothness... would the theory align with empirical evidence here?
In Fig 3 b) what does this simplex indicate here? The arrows seem to point erratically.
5 comments
Critical Weakness 2: Assumptions and Theoretical Analysis
The assumptions are relatively strong, approximate best response, Lipschitz continuity, and twice differentiable smoothness provide conditions that make the convergence proof naturally easy to obtain - the technical challenge is not too high.
Thank you for your comments! In the revised manuscript, we have added empirical evidence and further discussions to provide additional support for our assumptions. Below, we briefly summarize them, explain the role of the assumptions in our theoretical analysis, and discuss the technical challenges involved in our theoretical analysis.
(1) Additional evidence and discussion regarding the assumptions. We have provided the following assessments of the four assumptions in our revised manuscript (please refer to the revised manuscript for details).
- Assumption 1. We conduct additional experiments on Kuhn Poker by constructing representative policy sets and sampling additional policies to approximate the omitted policy space. The results show positive payoff gaps on average within the tested neighborhoods of the restricted QRE, providing empirical support for this assumption. The empirical assessment of Assumption 1 has been added to Section 5 (p. 8), with the detailed experimental setup and payoff-gap results provided in Appendix F.3 (pp. 31–32, Table 3).
- Assumption 2. We introduce a new proposition that establishes an analytical upper bound on the Jacobian norm of the logit-response mapping. Using this bound, we empirically demonstrate that both the full-reference and restricted response mappings can satisfy the required contraction condition in Kuhn Poker. The analytical bound supporting Assumption 2, its complete proof, and the empirical contraction assessment have been added to Appendix F.5 (pp. 33–34, Proposition 6 and Table 4), with a summary in Section 5 (p. 8).
- Assumption 3. We conduct additional experiments in the AI Economist environment by perturbing the mechanism parameters and examining the resulting changes in the designer's objective. The results show low sensitivity to small perturbations, providing empirical evidence of local stability. The local-sensitivity experiment relevant to Assumption 3 has been added to Section 6 (p. 10), with the complete protocol and results provided in Appendix I.5 (p. 41, Table 7).
- Assumption 4. We analyze how policy-set expansion can reduce the left-hand side of this condition by decreasing the number of omitted policies and potentially improving their payoff separation. The discussion of how policy-set expansion affects Assumption 4 has been added in Appendix D.3 (p. 27).
(2) Motivation of the theoretical analysis. We would like to emphasize that these assumptions are introduced as sufficient conditions for obtaining theoretical insights into our framework, rather than as necessary conditions for its effectiveness. Given the complexity of equilibrium-constrained optimization in Markov games, our primary goal is to understand how the approximation of the policy space affects the reliability of mechanism optimization. In particular, our theoretical results characterize how the quality of the representative policy set affects the gradient approximation error and the convergence guarantee. This provides insights into the relationship between policy-space approximation and mechanism optimization performance under the stated conditions.
(3) Technical challenges in the theoretical analysis. We agree that deriving a gradient-descent convergence bound under standard smoothness conditions is relatively straightforward. However, the main technical challenge in our analysis lies in establishing that the gradient computed from a restricted policy set can reliably approximate the gradient of the original full-space objective.
Specifically, even if the restricted QRE is close to the full-space QRE, this does not directly imply that their gradients with respect to mechanism parameters are close. To establish this connection, our proof first bounds the effect of omitted policies on the equilibrium distributions, and then further bounds the difference between the derivatives of the two equilibria, which are obtained from different coupled implicit systems. Only after controlling both differences can we establish the gradient approximation error bound in Theorem 1 and subsequently derive the convergence guarantee in Theorem 2. Without this analysis, standard smoothness arguments alone would not establish a convergence guarantee for the original full-space objective when using restricted-policy gradients.
We present our assumptions and gradient-approximation guarantees in Section 4.4 (pp. 6–7) and provide the detailed equilibrium and derivative comparisons underlying these guarantees in Appendices D.1–D.2 (pp. 19–26).
Questions
What efforts need to be done to extend this to more than a two player setting?
We appreciate the suggestion to extend our work. Although our current framework focuses on two-player Markov games, its core methodology can be extended to settings with more than two players. The extension will mainly involve the following aspects.
(1) Equilibrium computation: we would extend PSRO to maintain representative policy sets for all players and construct payoff tensors over their joint policy combinations. Each player's logit response would be computed against the mixed strategies of all other players, resulting in a coupled QRE system involving all players.
(2) Implicit differentiation: the coupled QRE system can be differentiated using the same implicit differentiation principle as in our current framework. However, the number of joint policy combinations grows exponentially with the number of players, making exhaustive payoff estimation increasingly expensive. We can consider sampling joint policy combinations to alleviate this computational cost.
(3) Theoretical analysis: the main theoretical challenge lies in extending the contraction conditions and gradient approximation bounds to account for interactions among multiple players. We acknowledge that establishing these guarantees would require more involved analysis.
Overall, extending the core framework to multiple players is conceptually feasible, while improving computational scalability and establishing the corresponding theoretical guarantees would require further investigation. We have added the above discussion to the conclusion section (p. 10) of our paper.
What happens when representative policies are selected poorly? Are there consequences in which the implicit differentiation can assist? Are there safeguards against?
Thank you for this question! We would like to clarify how our framework handles potentially poor representative policies.
First, poor policies may exist in the initial policy sets, as these policies are randomly selected. However, they are less likely to be introduced during subsequent PSRO iterations, since PSRO progressively expands the policy sets by training and incorporating new best-response policies (i.e., policies that maximize expected payoffs against the opponents' current mixed strategies).
Second, even if some poor policies are included in the representative policy sets, their influence on the resulting equilibrium is generally limited. Under QRE, policies with lower expected payoffs are assigned smaller probabilities through the logit response function. Therefore, weaker policies tend to receive less probability mass and have a smaller influence on the equilibrium and the resulting surrogate gradient.
Third, the iterative policy expansion in PSRO serves as the safeguard against poor policy selection. Even if the initial policy sets contain weak policies, PSRO continuously introduces stronger best-response policies. As these stronger policies are incorporated, the relative probability mass assigned to the weaker policies tends to decrease, allowing the newly introduced policies to play a more important role in determining the equilibrium. In this way, iterative policy expansion helps mitigate the influence of poor initial policy selection.
We would also like to clarify that implicit differentiation does not directly address the issue of poor policy selection. As discussed above, our framework relies on the iterative policy expansion in PSRO to mitigate this issue.
We have added the above discussion to Section 4.1 (p. 4).
In Fig. 1 why is just kind of separate?
Thank you for pointing out this ambiguity in Fig. 1. The three circles representing , , and belong to the same group, as they are all outputs of PSRO for a given mechanism parameter . These outputs also serve as inputs to the subsequent modules of our framework.
In the revised Figure 1 (p. 6), we have enclosed them in a single rectangular box to make this relationship clear.
We sincerely thank you for your careful review and valuable comments! We have revised our manuscript accordingly. Below, we provide point-by-point responses to your comments.
Critical Weakness 1: Technical Contributions
[1] Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., & Graepel, T. (2017). A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning. Advances in Neural Information Processing Systems, 30.
[2] Ling, C. K., Fang, F., & Kolter, J. Z. (2018). What Game Are We Playing? End-to-end Learning in Normal and Extensive Form Games. Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp. 396–402.
We acknowledge that our contribution is not to introduce either technique independently, but to integrate them into a gradient-based framework that makes equilibrium-constrained mechanism parameter optimization computationally tractable in complex Markov games. Next, we clarify the distinctions from the two cited works, the benefits of this integration, and the key technical challenges involved.
(1) Relationship to the cited works. Our framework builds on the Policy Space Response Oracles (PSRO) method introduced by Lanctot et al. (2017). However, PSRO itself does not provide gradients of equilibrium behavior with respect to mechanism parameters, which are essential for our optimization problem.
Regarding Ling et al. (2018), their implicit differentiation approach is developed specifically for two-player zero-sum games, where QRE can be characterized through an entropy-regularized convex-concave min-max formulation. In contrast, our framework supports general-sum Markov games, where the two players have separate payoff matrices and the QRE generally cannot be characterized by the same zero-sum min-max formulation. We instead differentiate the coupled QRE fixed-point conditions, allowing us to compute equilibrium sensitivities in general-sum settings.
(2) Novelty and computational benefits of integrating the two techniques. We would like to emphasize that our central methodological contribution is the integration of these two techniques for mechanism parameter optimization in Markov games. This integration addresses a fundamental computational challenge that neither technique resolves independently. On the one hand, PSRO reduces the enormous policy space of a Markov game to a manageable set of representative policies, but does not provide gradients for optimizing mechanism parameters. On the other hand, implicit differentiation can provide equilibrium gradients, but directly applying it to the full policy space of a complex Markov game is computationally intractable.
By combining these techniques, we enable implicit differentiation on a compact policy-space meta-game rather than the full Markov game. This makes it possible to obtain informative equilibrium gradients at a manageable computational cost, enabling efficient gradient-based optimization of mechanism parameters without relying on expensive black-box searches involving repeated equilibrium computations.
(3) Technical challenges beyond a straightforward combination. We would like to emphasize that integrating these techniques is not entirely straightforward. PSRO relies on RL-based best-response training to construct and update representative policy sets, which is not directly differentiable. A key challenge is therefore to obtain meaningful gradients with respect to mechanism parameters without differentiating through the entire RL training process.
To address this, we separate policy generation from gradient computation. For the current representative policy set, we compute how the empirical payoff matrices change with the mechanism parameters, implicitly differentiate the QRE conditions with respect to these payoffs, and combine the resulting sensitivities through the chain rule. This enables us to compute surrogate gradients for mechanism optimization without backpropagating through the RL-based policy generation process, while allowing the representative policy sets to evolve as the mechanism parameters change.
We have expanded the discussion of these distinctions in Section 2 (pp. 2–3) and contributions in Sections 4.1–4.3 (pp. 4–5).