acceptodds
Under review as a conference paper at ICLR 2027

Optimizing Mechanism Parameters for Markov Games under Policy-Space Equilibrium Constraints

Abstract

Mechanism parameter optimization seeks to align the strategic behavior of players with global system objectives. While this problem is tractable in games with closed-form equilibrium solutions, extending it to Markov games remains challenging. The presence of stochastic transitions and high-dimensional state spaces precludes closed-form equilibrium characterization, necessitating computationally intensive multi-agent reinforcement learning (MARL) methods for equilibrium computation. Embedding such methods within an outer black-box optimization loop over mechanism parameters incurs substantial computational cost. We propose a gradient-based framework for optimizing mechanism parameters in two-player Markov games under quantal response equilibrium constraints. Our approach addresses the lack of differentiability in MARL-based equilibrium computation through two key components. First, we iteratively construct and evolve a manageable set of representative policies as mechanism parameters vary, mitigating the intractability of the full policy space. Second, we apply implicit differentiation to the equilibrium conditions over these representative policies, yielding gradient signals that enable efficient parameter optimization. We theoretically show that the surrogate gradient computed from the representative policy set approximates the full-space gradient, and analyze the convergence of gradient descent driven by this surrogate gradient. We evaluate our framework on two mechanism optimization settings: transition dynamics modification and reward function revision. Specifically, we consider minimizing unfairness in Kuhn Poker and balancing productivity and equality in the AI Economist environment. Experiments show that our framework outperforms the baselines in solution quality and search efficiency.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Mechanism parameter optimization, equilibrium-constrained optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ph31OpenReview ↗
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 S\mathcal{S} 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

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

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

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

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 S\mathcal S just kind of separate?

Thank you for pointing out this ambiguity in Fig. 1. The three circles representing S\mathcal S, U(θ)\mathbb U(\theta), and σS∗(θ)\boldsymbol{\sigma}_{\mathcal S}^*(\theta) belong to the same group, as they are all outputs of PSRO for a given mechanism parameter θ\theta. 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.

Reviewer_B4CfOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the problem of mechanism parameter optimization in Markov games. Since equilibrium computation could be computationally expensive, the paper employs the PSRO algorithm to compute the quantal-response equilibrium (QRE). The authors then apply implicit differentiation to the QRE and develop a gradient descent-based algorithm for optimizing mechanism parameters. The paper further establishes theoretical guarantees on the gradient approximation error and convergence of the proposed algorithm. Finally, empirical results are provided to validate the theoretical findings.

Critical strengths
  • Mechanism parameter optimization in Markov games is a well-motivated problem. Given the computational challenges of finding Nash equilibria in Markov games, considering mechanism optimization with QRE is a natural and reasonable approach.
  • The mathematical arguments and proofs are sound.
  • Extensive numerical results are provided to validate the theoretical findings.
Critical weaknesses
  • The technical novelty of this paper appears somewhat limited. In particular, implicit differentiation through equilibrium conditions in Markov games has already been studied in [1]. The authors should clearly distinguish their approach from existing methods and highlight the technical contributions of this paper.

  • The theoretical guarantees rely on several strong assumptions whose practical applicability remains unclear. For example, Assumption 1 requires every omitted policy to have a positive policy gap. However, the stopping condition of PSRO does not necessarily guarantee this condition. Together with Assumption 4, which imposes an additional constraint involving the number of omitted policies and the policy gap, these requirements raise concerns about the applicability of the proposed algorithm. The authors are encouraged to provide concrete examples or sufficient conditions under which these assumptions are satisfied.


[1] Wang, Jing, et al. "Differentiable arbitrating in zero-sum markov games." arXiv (2023).

Questions for authors

See weaknesses.

7 comments

Thank you for your feedback and constructive suggestions! We have carefully revised our manuscript to address the concerns you raised. In the following, we present our responses to each comment and describe the corresponding changes made to the manuscript.


Critical Weakness 1: Technical Novelty

  • The technical novelty of this paper appears somewhat limited. In particular, implicit differentiation through equilibrium conditions in Markov games has already been studied in [1]. The authors should clearly distinguish their approach from existing methods and highlight the technical contributions of this paper.

[1] Wang, Jing, et al. "Differentiable arbitrating in zero-sum markov games." arXiv (2023).

We appreciate the opportunity to further clarify the distinctions between our work and Wang et al. (2023). We had briefly discussed this related work in the related work section of our original manuscript. Following the reviewer's helpful suggestion, we have expanded this discussion to highlight three key differences and contributions of our approach.

(1) Differentiation space and computational efficiency. Wang et al. and our framework perform implicit differentiation in fundamentally different spaces. Specifically, Wang et al. perform equilibrium differentiation directly in the parameter space of the underlying policies. This involves second-order derivatives with respect to policy parameters. When policies are represented by neural networks, these parameters can number in the millions, making such differentiation computationally expensive. In contrast, our framework abstracts the underlying Markov game into a restricted policy-space meta-game and performs implicit differentiation on its QRE conditions. The resulting system has a dimension determined only by the number of representative policies, typically on the order of tens. This substantially reduces the dimensionality and computational cost of equilibrium differentiation.

(2) Equilibrium representation and non-transitive games. Wang et al. represent each player's equilibrium behavior using a single parameterized policy, whereas our framework explicitly maintains a set of representative policies and computes a QRE over their payoff matrix. This distinction is particularly valuable for non-transitive games, where strategic interactions exhibit cyclic relationships. Prior studies have highlighted the importance of maintaining diverse policy populations for capturing such interactions and approximating equilibria in non-transitive games (Lanctot et al., 2017; Yao et al., 2023). By explicitly representing the payoff relationships among different policies, our framework naturally captures strategic diversity and cyclic interactions, rather than relying on a single parameterized policy to represent equilibrium behavior. This policy-space formulation provides a natural way to handle both transitive and non-transitive games, including games such as Kuhn Poker.

Lanctot et al. "A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning." Advances in Neural Information Processing Systems (NeurIPS), 2017. Yao et al. "Policy Space Diversity for Non-Transitive Games." Advances in Neural Information Processing Systems (NeurIPS), 2023.

(3) Broader applicability to mechanism optimization. Wang et al. focus on reward function modification, where the mechanism parameters θ\theta affect the reward functions Ri,θ(s,a)R_{i,\theta}(s,a) while the transition dynamics P(s′∣s,a)P(s'|s,a) remain fixed. In contrast, our framework allows θ\theta to affect both the transition dynamics Pθ(s′∣s,a)P_\theta(s'|s,a) and the reward functions Ri,θ(s,a)R_{i,\theta}(s,a). This broader formulation enables optimization of different types of mechanisms, including those that modify the rules of the game rather than merely adjusting players' rewards. We demonstrate this flexibility through two distinct applications: optimizing card-dealing probabilities in Kuhn Poker (transition dynamics modification) and optimizing tax rates in the AI Economist (reward function modification).

In summary, while prior studies such as Wang et al. (2023) have employed implicit differentiation through equilibrium conditions, our framework makes three distinct contributions: (1) substantially reducing the dimensionality and computational cost of equilibrium differentiation through a restricted policy-space formulation; (2) explicitly capturing strategic diversity and non-transitive interactions by maintaining a representative set of policies; and (3) extending mechanism optimization to encompass both transition dynamics and reward functions.

We have expanded the related work (p. 2) section to make these distinctions clearer and better highlight the contributions of our approach.

Critical Weakness 2: Theoretical Assumptions

  • The theoretical guarantees rely on several strong assumptions whose practical applicability remains unclear. For example, Assumption 1 requires every omitted policy to have a positive policy gap. However, the stopping condition of PSRO does not necessarily guarantee this condition. Together with Assumption 4, which imposes an additional constraint involving the number of omitted policies and the policy gap, these requirements raise concerns about the applicability of the proposed algorithm. The authors are encouraged to provide concrete examples or sufficient conditions under which these assumptions are satisfied.

We appreciate your helpful suggestion! Below, we provide additional empirical assessments and theoretical discussions to clarify the applicability and limitations of our assumptions. We have incorporated these analyses into our revised manuscript.

Assumption 1

Assumption 1 states that, within a neighborhood of the restricted QRE, every omitted policy yields a lower payoff than the best policy in the retained set. To empirically validate this assumption, we conduct additional experiments on Kuhn Poker. Specifically, we use PSRO to construct a restricted policy set Si\mathcal{S}_i containing 20 representative policies for each player. We then randomly sample 980 additional policies per player from the policy space to approximate the omitted policy set Ri\mathcal{R}_i.

To assess Assumption 1, we consider the following criterion: Δ(r)=min⁡i∈1,2min⁡a∈Rimin⁡q:∥q−σˉ−i∗∥1≤r[max⁡c∈SiJi(c,q)−Ji(a,q)].\Delta(r)=\min_{i\in\\{1,2\\}}\min_{a\in\mathcal{R}_i}\min_{q:\lVert q-\bar{\sigma}_{-i}^{*}\rVert_1\le r}\left[\max_{c\in\mathcal{S}_i}J_i(c,q)-J_i(a,q)\right]. Here, Δ(r)\Delta(r) measures the worst-case payoff gap between the best retained policy and any sampled omitted policy, considering all feasible opponent strategy mixtures qq within an L1L_1-neighborhood of radius rr around the restricted QRE. A positive value of Δ(r)\Delta(r) indicates that Assumption 1 holds over the sampled policy sets for the specified neighborhood.

The table below reports the mean and standard deviation of Δ(r)\Delta(r) across five randomly sampled dealing-probability configurations.

Perturbation radius rrMean Δ(r)\Delta(r)Standard deviation
0.0000.0330.011
0.0010.0330.011
0.0050.0320.011
0.0100.0310.011
0.0200.0290.012
0.0500.0240.013
0.1000.0150.013

We can see that the worst-case gap remains positive given small perturbation radius rr. The worst-case gap increases as the neighborhood radius rr decreases. These results provide empirical support for the feasibility of Assumption 1 on the sampled policy sets in Kuhn Poker.

We have added the above assessment of Assumption 1 to Section 5 (p. 8), with the detailed formulation, experimental setup, and complete results provided in Appendix F.3 (pp. 31–32, Table 3).

Assumption 3

Assumption 3 imposes differentiability and smoothness-related regularity conditions on the objective functions. To provide empirical evidence regarding the local regularity of the objective function, we conduct additional experiments in the AI Economist environment.

We randomly sample three seven-dimensional tax-rate vectors and keep the policy pool fixed. Around each vector, we apply positive and negative perturbations along five directions at two scales, with ℓ1\ell_1 norms of 0.010.01 and 0.0050.005. For each perturbed parameter vector, we recompute the restricted QRE and evaluate the corresponding designer objective FS(σS∗(θ),θ)F_{\mathcal S}(\sigma_{\mathcal S}^*(\theta),\theta). The table reports the maximum absolute percentage deviation from the center across the ten signed perturbations at each scale.

Maximum relative FSF_{\mathcal S} deviation, ∥Δθ∥1=0.01\|\Delta\theta\|_1=0.01Maximum relative FSF_{\mathcal S} deviation, ∥Δθ∥1=0.005\|\Delta\theta\|_1=0.005
0.1084% ± 0.0835%0.0620% ± 0.0387%

The results show that the restricted designer objective exhibits low sensitivity to small perturbations in the mechanism parameters, with smaller deviations at the finer perturbation scale. These observations are consistent with locally regular behavior of the objective function in the tested parameter neighborhoods. Although they do not directly establish the differentiability or Lipschitz smoothness required by Assumption 3, they provide empirical evidence of local stability in a complex Markov game setting.

We have added the above assessment of Assumption 3 to Section 6 (p. 10), with the experimental protocol, complete statistics, and interpretation provided in Appendix I.5 (p. 41).

Assumption 2

Assumption 2 requires both the full and restricted logit-response mappings to have Jacobian norms bounded by a common constant L<1L<1. Next, we first introduce a new proposition to characterize the Jacobian bound. Consider a logit-response mapping p(q)=softmax⁡(Vq)p(q)=\operatorname{softmax}(Vq), where V=λUV=\lambda U includes the rationality parameter. Let q0q_0 be the opponent's zero-padded restricted-QRE strategy and p0=p(q0)p_0=p(q_0). We introduce the following proposition (the proof is added to our revised manuscript).

Proposition 6. Define RB=max⁡j(max⁡kVkj−min⁡kVkj)R_B=\max_j(\max_kV_{kj}-\min_kV_{kj}) and DB=max⁡j∑kp0k(Vkj−μ0j)2D_B=\max_j\sqrt{\sum_kp_{0k}(V_{kj}-\mu_{0j})^2}, where μ0j=∑kp0kVkj\mu_{0j}=\sum_kp_{0k}V_{kj}. Then,

\lVert q-q_0\rVert_1\le r}} \lVert\operatorname{Jac}_q p(q)\rVert_1 \le D_B e^{R_B r/2}.$$ Proposition 6 presents a single bound for a general logit-response mapping, and it applies to both the full and restricted logit-response mappings by substituting their respective payoff matrices $V$. Therefore, we can evaluate the two bounds separately and check whether both are smaller than $1$. We use Kuhn Poker to empirically assess whether this condition can be satisfied. Similar to our evaluation of Assumption 1, we employ PSRO to generate 20 representative policies per player, forming the restricted policy set $\mathcal S_i$. We then randomly sample 980 additional policies per player, obtaining 1,000 policies per player to approximate the full policy space $\Pi_i$. For five randomly sampled dealing-probability configurations, we evaluate the Jacobian bounds for the full-reference and restricted mappings using Proposition 6. The table below reports the corresponding means and standard deviations. | Perturbation radius $r$ | Full-reference bound: mean±SD | Restricted bound: mean±SD | | :---------------------: | :---------------------------: | :-----------------------: | | 0.000 | 0.454 ± 0.068 | 0.417 ± 0.074 | | 0.001 | 0.454 ± 0.068 | 0.417 ± 0.075 | | 0.005 | 0.456 ± 0.068 | 0.418 ± 0.075 | | 0.010 | 0.459 ± 0.069 | 0.420 ± 0.076 | | 0.020 | 0.464 ± 0.070 | 0.424 ± 0.077 | | 0.050 | 0.480 ± 0.074 | 0.435 ± 0.082 | | 0.100 | 0.507 ± 0.080 | 0.454 ± 0.090 | The results show that both Jacobian bounds can remain below $1$ within the tested neighborhoods, demonstrating that the contraction condition in Assumption 2 is achievable in practice, e.g., in the Kuhn Poker setting. **We have added the above assessment of Assumption 2 to Section 5 (p. 8) and included the complete proof of Proposition 6 to Appendix F.5 (pp. 33–34, Table 4).**
Reviewer_9pKfOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

In this paper, the author studies the mechanism parameter optimization problem where the underlying game is a two-player Markov games in which agents play quantal response equilibrium. In specific, the authors propose a gradient -based computational framework for optimizing the mechanism parameter that combines restricted policy idea from PSRO and implicit differentiation of equilibrium conditions. Finally, the authors demonstrate the framework's efficacy through (1) optimizing card-dealing probability to minimize unfairness between players in Kuhn Poker and (2) optimizing tax policy to balance productivity and equality in the AI Economist environment.

Critical strengths
  • In general, the problem is well motivated, and the authors propose a appealing way to optimize the mechanism parameter which induces a underlying Markov game with quantal response as solution concept. I think using PSRO-style restricted policy set to enable scaling to larger games is also an inspiring practice choice. I think the experiment results are also encouraging: especially the AI Economist and the ablation study does demonstrate that the equilibrium-response gradients contain useful information beyond the direct mechanism gradient (however, I have several concerns about that experiment, see Questions).
Critical weaknesses
  • My main concern is that the theoretical results rely on the strong assumptions that are not justified, and the theoretical analysis ignores some important factors. First, Theorem 1 assumes that every omitted policy is uniformly worse than the best retained policy (Assumption 1) and that logit best-response mappings are contractions (Assumption 2), which are in fact pretty strong and not sufficiently justified in the paper. The authors describe the PSRO procedure used to estimate QRE, but the stopping criterion of PSRO procedure is "stopping when new policies receive negligible probability under QRE", and it can't guarantee these first conditions. Moreover, it also does not prove that gradient approximation necessarily improves as the policy pool expands. And for the second condition, if I understand correctly, the norm of JacσΦJac_\sigma\Phi depends on the payoffs and the rationality parameter λ\lambda. There is no general guarantee that it is smaller than one, particularly for large λ\lambda or strongly interacting players.

And there are several technical issues that the author overlook: (1) The authors didn't discuss how to break tie when there are multiple QRE since the QRE is not unique in general-sum games, (2) Theorem 2 does not analyze constrained gradient descent but both experiments have constrained mechanism parameter space, (3) Theoretical analysis ignores important implementation errors: the theory considers the difference between the exact full-game QRE gradient and an exact restricted-game QRE gradient, but using estimated payoffs, approximate best responses, and numerical equilibrium solutions will induce errors, and those errors should be accounted in the final analysis, (4) Kuhn Poker uses objective function (Eπ∼σU1(π,θ))2(\mathbb E_{\pi\sim\sigma}U_1(\pi,\theta))^2 which is inconsistent with the general model's $F(\sigma,\theta) =\mathbb E_{\pi\sim\sigma}[f(\pi,\theta)]$.

  • My another major concern is regarding the AI Economist experiment. Please see the Question section.
Questions for authors
  • For the AI Economist experiment, Appendix I.1 states that the per-step reward is the incremental change in utility, and Table 3 specifies a discount factor of (\gamma=0.99). However, Appendix I.3 appears to differentiate only the terminal utility, which is generally not equivalent to differentiating the discounted cumulative reward. Could the author clarify what reward, discount, and cumulative discounted utility they use for estimating the QRE in the experiment?
  • Moreover, Appendix I.2 argues that because the tax-rate vector is excluded from agents' observations, their action histories and pre-tax incomes are independent of θ\theta when policies are fixed. However, this does not generally follow: tax rates may change agents' wealth, which can affect subsequent observations, action availability, or transitions even under fixed policies. Could the author better justify their argument?
8 comments

We sincerely appreciate your thoughtful comments! We have updated our manuscript in response to your valuable suggestions. Below, we provide point-by-point responses to your comments, along with the corresponding revisions made to the manuscript.


Critical Weakness: Theoretical Assumptions

My main concern is that the theoretical results rely on the strong assumptions that are not justified, and the theoretical analysis ignores some important factors. First, Theorem 1 assumes that every omitted policy is uniformly worse than the best retained policy (Assumption 1) and that logit best-response mappings are contractions (Assumption 2), which are in fact pretty strong and not sufficiently justified in the paper. The authors describe the PSRO procedure used to estimate QRE, but the stopping criterion of PSRO procedure is "stopping when new policies receive negligible probability under QRE", and it can't guarantee these first conditions.

We provide empirical evidence supporting Assumption 1 and have incorporated the corresponding experimental results into our revised manuscript.

We appreciate the reviewer raising this concern! Assumption 1 requires that every omitted policy yields a lower payoff than the best retained policy throughout a neighborhood of the restricted QRE. To empirically assess this assumption, we conduct additional experiments in the Kuhn Poker setting. Specifically, we employ PSRO to generate 20 representative policies for each player, forming the restricted policy set Si{\mathcal S}_i. We further randomly sample 980 additional policies per player from the policy space to approximate the omitted policy set Ri{\mathcal R}_i.

To evaluate Assumption 1, we consider the following criterion: Δ(r)=min⁡i∈1,2min⁡a∈Rimin⁡q:∥q−σˉ−i∗∥1≤r[max⁡c∈SiJi(c,q)−Ji(a,q)].\Delta(r)=\min_{i\in\\{1,2\\}}\min_{a\in\mathcal{R}_i}\min_{q:\lVert q-\bar{\sigma}_{-i}^{*}\rVert_1\le r}\left[\max_{c\in\mathcal{S}_i}J_i(c,q)-J_i(a,q)\right]. Here, Δ(r)\Delta(r) measures the worst-case payoff gap between the best retained policy and any sampled omitted policy, considering all feasible opponent strategy mixtures qq within an L1L_1-neighborhood of radius rr around the restricted QRE. A positive value of Δ(r)\Delta(r) indicates that Assumption 1 holds over the sampled policy sets for the specified neighborhood. Moreover, since a smaller rr corresponds to a smaller feasible neighborhood, Δ(r)\Delta(r) is monotonically non-increasing with respect to rr. Thus, Assumption 1 becomes easier to satisfy as the neighborhood radius decreases. The table below reports the mean and standard deviation of Δ(r)\Delta(r) across five randomly sampled dealing-probability configurations.

Perturbation radius rrMean Δ(r)\Delta(r)Standard deviation
0.0000.0330.011
0.0010.0330.011
0.0050.0320.011
0.0100.0310.011
0.0200.0290.012
0.0500.0240.013
0.1000.0150.013

We can see that the worst-case gap remains positive given small perturbation radius rr. Furthermore, the worst-case gap increases as the neighborhood radius rr decreases, which is consistent with the theoretical monotonicity property discussed above. These results provide empirical support for the feasibility of Assumption 1 on the sampled policy sets in Kuhn Poker.

The empirical assessment of Assumption 1 has been added to the “Assessment of Assumptions” paragraph in Section 5 (p. 8), with the experimental setup, payoff-gap formulation, and complete results provided in Appendix F.3 (pp. 31–32, Table 3).

Moreover, it also does not prove that gradient approximation necessarily improves as the policy pool expands.

Thank you for raising this concern! Building on Theorem 1, we establish an upper bound on the gradient approximation error that admits a monotonically decreasing envelope as the representative policy set expands. We have incorporated this analysis into our revised manuscript.

Theorem 1 establishes the following upper bound on the gradient approximation error: ∥∇θFΠ(σΠ∗(θ),θ)−∇θFS(σˉS∗(θ),θ)∥1≤Cloce−λΔ.\left\lVert\nabla_\theta F_\Pi({\boldsymbol\sigma}_{\boldsymbol\Pi}^{\ast}(\theta),\theta)-\nabla_\theta F_{\mathcal{S}}(\bar{\boldsymbol\sigma}_{\mathcal{S}}^{\ast}(\theta),\theta)\right\rVert_1\le C_{\mathrm{loc}}e^{-\lambda\Delta}. By further analyzing the constant ClocC_{\mathrm{loc}} derived in Appendix D, we obtain a refined error bound, as stated in the following corollary (with its complete proof provided in our revised manuscript).

Corollary 1. Suppose Assumptions 1–4 hold throughout policy-set expansion, with a common contraction constant and uniform bounds on the payoffs, objective function, and their derivatives. There exists a constant K>0K>0, independent of the representative policy set, such that ∥∇θFΠ(σΠ∗(θ),θ)−∇θFS(σˉS∗(θ),θ)∥1≤K(∣R1∣+∣R2∣)e−λΔ.\left\lVert\nabla_\theta F_\Pi({\boldsymbol\sigma}_{\boldsymbol\Pi}^{\ast}(\theta),\theta)-\nabla_\theta F_{\mathcal{S}}(\bar{\boldsymbol\sigma}_{\mathcal{S}}^{\ast}(\theta),\theta)\right\rVert_1\le K\left(\lvert\mathcal{R}_1\rvert+\lvert\mathcal{R}_2\rvert\right)e^{-\lambda\Delta}. The above corollary shows that the gradient approximation error is bounded by K(∣R1∣+∣R2∣)e−λΔK(|\mathcal R_1|+|\mathcal R_2|)e^{-\lambda\Delta}, which depends on both the number of omitted policies and the payoff gap Δ\Delta. As the representative policy set expands, ∣R1∣+∣R2∣|\mathcal R_1|+|\mathcal R_2| monotonically decreases. Although Δ\Delta may vary with policy-set expansion, if it admits a uniform lower bound Δ‾\underline{\Delta}, we have K(∣R1∣+∣R2∣)e−λΔ≤K(∣R1∣+∣R2∣)e−λΔ‾.K\left(\lvert\mathcal{R}_1\rvert+\lvert\mathcal{R}_2\rvert\right)e^{-\lambda\Delta}\le K\left(\lvert\mathcal{R}_1\rvert+\lvert\mathcal{R}_2\rvert\right)e^{-\lambda\underline{\Delta}}. where the right-hand side decreases monotonically as the representative policy set expands. Note that Δ\Delta is positive based on Assumption 1. Therefore, in the worst case, we can simply choose Δ‾=0\underline{\Delta}=0, and the resulting upper bound becomes K(∣R1∣+∣R2∣)K(|\mathcal R_1|+|\mathcal R_2|), which still decreases with policy-set expansion.

While these results do not guarantee that the actual gradient approximation error decreases at every expansion step, they provide insight into how policy-set expansion can help reduce the gradient approximation error.

Corollary 1 has been added to Section 4.4 (p. 7), with its complete proof and the discussion of the monotonically decreasing error-bound envelope provided in Appendix D.3 (pp. 26–27).

And for the second condition, if I understand correctly, the norm of JacσΦ{\text Jac}_{\boldsymbol\sigma}{\Phi} depends on the payoffs and the rationality parameter λ\lambda. There is no general guarantee that it is smaller than one, particularly for large λ\lambda or strongly interacting players.

Thanks for the comment! We provide empirical evidence illustrating that Assumption 2 can hold in practice and have incorporated the corresponding results into our revised manuscript.

First, we derive a new proposition to characterize the Jacobian bound. Consider a logit-response mapping p(q)=softmax⁡(Vq)p(q)=\operatorname{softmax}(Vq), where V=λUV=\lambda U includes the rationality parameter. Let q0q_0 be the opponent's zero-padded restricted-QRE strategy and p0=p(q0)p_0=p(q_0). We introduce the following proposition (the proof is added to our revised manuscript).

Proposition 6. Define RB=max⁡j(max⁡kVkj−min⁡kVkj)R_B=\max_j(\max_kV_{kj}-\min_kV_{kj}) and DB=max⁡j∑kp0k(Vkj−μ0j)2D_B=\max_j\sqrt{\sum_kp_{0k}(V_{kj}-\mu_{0j})^2}, where μ0j=∑kp0kVkj\mu_{0j}=\sum_kp_{0k}V_{kj}. Then,

\lVert q-q_0\rVert_1\le r}} \lVert\operatorname{Jac}_q p(q)\rVert_1 \le D_B e^{R_B r/2}.$$ Assumption 2 requires both the full and restricted logit-response mappings to have Jacobian norms bounded by a common constant $L<1$. Proposition 6 presents a single bound for a general logit-response mapping, and it applies to both mappings by substituting their respective payoff matrices $V$. Therefore, we can evaluate the two bounds separately and check whether both are smaller than $1$. Next, we use Kuhn Poker as an example to empirically assess whether this condition can be satisfied. Similar to our evaluation of Assumption 1, we employ PSRO to generate 20 representative policies per player, forming the restricted policy set $\mathcal S_i$. We then randomly sample 980 additional policies per player, obtaining 1,000 policies per player to approximate the full policy space $\Pi_i$. For five randomly sampled dealing-probability configurations, we evaluate the Jacobian bounds for the full-reference and restricted mappings using Proposition 6. The table below reports the corresponding means and standard deviations. | Perturbation radius $r$ | Full-reference bound: mean±SD | Restricted bound: mean±SD | | :---------------------: | :---------------------------: | :-----------------------: | | 0.000 | 0.454 ± 0.068 | 0.417 ± 0.074 | | 0.001 | 0.454 ± 0.068 | 0.417 ± 0.075 | | 0.005 | 0.456 ± 0.068 | 0.418 ± 0.075 | | 0.010 | 0.459 ± 0.069 | 0.420 ± 0.076 | | 0.020 | 0.464 ± 0.070 | 0.424 ± 0.077 | | 0.050 | 0.480 ± 0.074 | 0.435 ± 0.082 | | 0.100 | 0.507 ± 0.080 | 0.454 ± 0.090 | The results show that both Jacobian bounds can remain below $1$ within the tested neighborhoods, illustrating that the contraction condition in Assumption 2 is achievable in practice. While this does not establish that Assumption 2 holds in all games, it provides empirical evidence of its feasibility in the Kuhn Poker setting. **The empirical assessment of Assumption 2 has been added to Section 5 (p. 8), while Proposition 6, its complete proof, and the full experimental results are provided in Appendix F.5 (pp. 33–34, Table 4).** We also acknowledge that the original manuscript did not provide justification for these assumptions. Our primary motivation for introducing them is to make the theoretical analysis tractable and provide insights into the behavior of our framework under well-defined conditions, such as how the quality of the representative policy set affects the convergence guarantees.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.