acceptodds
Under review as a conference paper at ICLR 2027

Nash-Preserving Symmetry Reductions for Markov Games

Abstract

The standard solution concept for a Markov game is the Nash equilibrium, a joint policy at which no agent gains by deviating alone. Symmetry can make such a game much smaller, but the smaller game is useful only if an equilibrium found there is still an equilibrium of the original. This is not automatic: a symmetric policy that no agent can improve on within the symmetric class may still be beaten by an asymmetric deviation, so a reduction is trustworthy only if the Nash gap it reports matches the true one. We give two reductions that meet this test exactly. Symmetry among states collapses the game to one on groups of equivalent states; symmetry among interchangeable agents replaces their separate policies with a single shared one. Each preserves the Nash gap against all deviations, not merely symmetric ones, and the two combine when compatible. Because the reduced gap is the true one, we use it in three ways: to tighten existing convergence bounds, to derive a new one for shared policies that exposes the cost of tying agents together, and to cut the samples a generative model needs by pooling symmetric queries. Experiments on cooperative and zero-sum tabular games confirm that the reductions preserve equilibria and accelerate policy optimization.

Primary area:
reinforcement learning
Keywords:
Symmetry reduction, Nash equilibrium, Markov games

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_6qgDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies symmetry reductions in finite discounted Markov games. State symmetries produce a quotient game. Agent permutations produce one shared table over pointed-state orbits. Each entry records the player's own local state and the multiset of the other players' states. The two reductions can be combined when their group actions commute. The paper transfers existing convergence bounds to state quotients. It also gives a finite-time bound for shared log-barrier softmax policy gradient. With a generative model, it pools symmetric transition rows. Experiments test the benefits in cooperative and zero-sum tabular games.

Critical strengths
  1. The pointed-state and stabilizer construction keeps the deviator's identity explicit. It explains why agent sharing differs from a state quotient of the original game.
  2. Corollary 1 studies finite-time convergence with tied parameters. It exposes both orbit counts and sharing multiplicity, with an explicit condition for improving the bound.
  3. The experiments measure the true unrestricted Nash gap. The discussion also separates row savings, per-row estimation costs, and planning costs.
Critical weaknesses

The account of prior theory needs more care. The paper acknowledges that the reductions are classical. However, Section 1.1 places some earlier work under priors and empirical validation. This can understate its theory. van der Pol et al. (2022) already handle global symmetries and agent permutations together. Theorem 4.4 of Chen and Zhang (2024) gives symmetric-value and optimal-policy guarantees for cooperative Markov games. Theorem 4.0.2 of Emmons et al. (2022) connects symmetric local optima to Nash equilibria in common-payoff normal-form games. Their Section 4.1 also discusses shared-policy MARL. Please focus the distinction on policy classes, deviation classes, exact per-policy gap identities, and finite-time bounds. These precedents do not establish redundancy. They do show why the gap cannot be described broadly as a lack of prior theory or equilibrium guarantees. The best-response argument should also be linked more directly to classical results such as Zinkevich and Balch (2001).

Questions for authors

none

2 comments

A more careful account of prior theory

We thank the reviewer for identifying where our discussion understated prior theory. Our revision has incorporated the suggestions with highlighted text, no longer presenting the following prior works as mainly empirical uses of symmetry:

  • We’ve acknowledged van der Pol et al. (2022) in unifying global symmetries and agent permutations. Our counterpart (Section 3.3) should be viewed as a similar effort to unify our Theorems 1 and 2.
  • On Chen and Zhang (2024), we’ve acknowledged their symmetric optimality guarantees for cooperative Markov games.
  • Please refer to our response to QxF2 on Emmons et al. (2022).
  • On Zinkevich and Balch (2001), we’ve made it clear how our theory utilizes and contrasts theirs. Specifically, we utilize their single-agent results in a best-response step in our proofs of Theorems 1 and 2, while the stabilizer technique in proof of our Theorem 2 removes the assumption in their Theorem 3 that requires the agents to occupy distinct local states. We’ve also made it clear that our novelty is not the existence of an invariant policy, but its effect on the Nash-gap identities (our Eqs. (4) and (7)).

Thank you for the clarification and revisions. The more careful treatment of prior theory and the clearer distinction of your contributions address my concerns. I maintain my weak acceptance recommendation.

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

The paper investigates whether restricting a Markov game to symmetric policies, which is convenient when symmetric states exist or provide interchangeable agents the same shared policy, preservers the Nash equilibria of original game. A key observation is that optimal deviations of deviating agent is also symmetric. Consequently, Nash gap in reduced game matches that of orifinal game against all deviations, including the asymmetric ones.

Critical strengths

The problem of certifying symmetric policies in Markov games addresses whether the policies found by parameter sharing or symmetric policy networks are Nash equilibria of the original game is an important problem in MARL, and is therefore relevant to ICLR. The main idea of the paper is simple and clean: if the other agents play symmetrically, one agent cannot gain more by deviating asymmetrically than by deviating symmetrically.

The theoretical development appears to be sound and complete.

Critical weaknesses

Minor concern.

(Novelty) As far as I know, Nash gap identities are novel. However, the paper's claim that "none has asked" this question is questionable. The mechanism behind identities is composition of two known facts derived from (M. Zinkevich and T. Balch, ICML, 2001) and the fact that best response to symmetric opponents is symmetric, which is the standard step in existence proofs for symmetric equilibria. Regarding Thm. 2, Emmons et al. (2022) prove its cooperative counterpart and cover Markov games, and (Vadori et al, NeurIPS 2020) define shared equilibria for parameter-shared agents, which is the restricted notion the paper argues against.

Questions for authors
  1. What distinguishes Thm. 2 from other works on the symmetric Markov perfect equilibrium computations?
  2. What initial distribution μ\mu is used in the experiments of Sect. 5, and does the speed-up in Fig. 1 persist when each parameterization is run at its own tuned step size?
1 comment

We thank the reviewer for the careful review and constructive feedback. Below, we address the questions and concerns.

Novelty of Thm. 2

It is correct that our Thm. 2 is closest to Emmons et al. (2022, Theorem 4.0.2), which states that, in common-payoff normal-form games, any locally optimal symmetric strategy is a (global) Nash equilibrium. Our work is different in the following aspects:

  • Setting. Emmons et al. prove their equilibrium statement (Theorem 4.0.2) in the setting of common-payoff normal-form games, while we deal with the more general setting of general-sum Markov games. To apply to our setting, Emmons et al. need to pay the exponential cost of expressing a Markov game in its normal-form equivalent. In contrast, our Thm. 2 exploits the state structure to reduce the deviator’s state space with the notion of pointed-orbits (zi(s)z^i(s)), making it more efficient.
  • Statement. Their Theorem 4.0.2 applies only to exact (local) optima, while our Thm. 2 applies to every symmetric policy (optimal or not), characterizing its Nash-gap by checking a smaller set of deviations. As a result, Thm. 2 enables the improved guarantees in our Section 4.

Our revision has incorporated the clarifications above with highlighted text.

Experiments: initial distribution

All experiments in Section 5 use the uniform initial distribution. We will state this explicitly.

Experiments: tuned step size in Fig. 1

Figure 1 runs every parameterization at a common step size η0\eta_0 (η0=5\eta_0=5 for softmax PG on the Ring, η0=0.3\eta_0=0.3 for softmax OGDA on cyclic pursuit). In the new Appendix Q, we tune the full table's step size over {14,12,1,2,4}⋅η0\{\tfrac14,\tfrac12,1,2,4\}\cdot\eta_0 and keep every other setting fixed.

GameParameterizationStep sizeIterations until gap stays ≤10−2\le10^{-2}Final gap
RingFull tabletuned1,0602.4×10−32.4\times10^{-3}
RingState quotientη0\eta_05401.1×10−31.1\times10^{-3}
RingAgent permutationη0\eta_08401.8×10−31.8\times10^{-3}
RingCommutingη0\eta_01202.1×10−42.1\times10^{-4}
Cyclic pursuitFull tabletunednot reached in 6,0001.3×10−21.3\times10^{-2}
Cyclic pursuitState quotientη0\eta_05,6004.9×10−34.9\times10^{-3}

As shown in Figure 2 in the appendix, even at its best step size the full table remains slower than every reduction run at the common, untuned step size, in both games. Tuning narrows the gap but does not close it.

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

This paper studies Nash equilibria in Markov games. In a Markov game, multiple agents interact with an environment. They take actions and receive rewards, the current state and actions affect the distribution of subsequent states, and each agent optimizes its own value function. A Nash equilibrium is a combination of policies, one per agent, under which no agent can improve its own value function by changing its own policy. If each agent can choose any policy, the joint policy space becomes very large. In practice, however, many Markov games have Nash equilibria in which each agent's policy has a certain symmetric structure. This paper focuses on exploiting such symmetry to reduce the size of the problem while preserving Nash equilibria. To prove that Nash equilibria are preserved, the paper goes further and considers the unrestricted Nash gap, i.e., how much each agent can improve its own value function by changing its policy. Here, "unrestricted" means that each agent may change its policy arbitrarily when the Nash gap is computed.

Specifically, the paper considers two main types of symmetry. The first is state symmetry, which transforms states without changing agent labels or action labels. The corresponding state quotient merges states that can be mapped to one another by these transformations. The second is agent-permutation symmetry, which permutes agents together with their corresponding state/action coordinates. The paper also studies the case where the two reductions are combined.

The main theoretical results are as follows. In finite discounted Markov games, Theorem 1 proves that the unrestricted Nash gap is exactly preserved for the G-state-symmetric games defined in Definition 1, and Theorem 2 proves that the unrestricted Nash gap is exactly preserved for agent-permutation-symmetric games. "Exactly preserved" means the Nash gap equals the one obtained when each agent may choose any policy. Preserving the Nash gap therefore implies that a Nash equilibrium of the reduced game corresponds to a Nash equilibrium of the original game, so Nash equilibria can be computed in a smaller space.

Critical strengths

The research question has significant theoretical and practical importance. The paper specifies the conditions under which Nash equilibria possess symmetry. In games that satisfy these conditions, the size of the policy space can be reduced, simplifying the problem.

Critical weaknesses

The current experiments consist of only two small-scale settings. The Ring experiment has only 3 agents, and the two-player zero-sum game on C10C_{10} has only 10 positions. The numerical experiments would be more convincing if the paper showed larger-scale experiments and results in more complex settings.

Questions for authors

In larger-scale experiments, is the efficiency gain of symmetry-exploiting OGDA over full-table OGDA larger or smaller? Can you provide experimental evidence?

2 comments

We thank the reviewer for the careful review and constructive feedback. Below, we address the questions and concerns.

Larger-scale experiments

The gain grows with scale. We enlarged both games of Figure 1.

Cyclic pursuit. We increased the cycle from C10C_{10} to C50C_{50} (∣S∣=2,500\lvert\mathcal S\rvert=2{,}500 states, against ∣S‾∣=50\lvert\overline{\mathcal S}\rvert=50 in the quotient), with the same OGDA step size and initialization:

GameIterations to gap 0.050.05 (quotient / full table)Final gap (quotient / full table)Ratio of final gaps (full table / quotient)
C10C_{10}250 / 2,2504.9×10−34.9\times10^{-3} / 2.1×10−22.1\times10^{-2}2.1×10−2/4.9×10−3≈42.1\times10^{-2}/4.9\times10^{-3}\approx4
C50C_{50}700 / not reached in 10,0002.4×10−32.4\times10^{-3} / 0.280.280.28/2.4×10−3≈1160.28/2.4\times10^{-3}\approx116

The ratio of final gaps rises from about 4 to about 116 as the cycle grows, and the full table no longer reaches gap 0.050.05 within the budget.

Ring with 6 agents. We increased the Ring from N=3N=3 to N=6N=6 agents on m=8m=8 sites, giving ∣S∣=262,144\lvert\mathcal S\rvert=262{,}144 states and 729729 joint actions. After 4,000 iterations of softmax PG:

ParameterizationNumber of groupsFinal Nash gap
Commuting∣W∣=792\lvert\mathcal W\rvert=7924.9×10−34.9\times10^{-3}
Agent permutation∣Z∣=6,336\lvert\mathcal Z\rvert=6{,}3362.7×10−22.7\times10^{-2}
State quotient∣S‾∣⋅N=196,608\lvert\overline{\mathcal S}\rvert\cdot N=196{,}6080.280.28
Full table∣S∣⋅N=1,572,864\lvert\mathcal S\rvert\cdot N=1{,}572{,}8640.350.35

The commuting reduction reaches gap 0.050.05 after 240 iterations, which the full table never reaches within the budget. With six agents the agent symmetry (∣Sym6∣=720\lvert\mathrm{Sym}_6\rvert=720) is much larger than the rotation group (8 elements), so the reductions that share across agents now lead, as the orbit counts of Section 3.3 predict.

Both results are shown in Figure 3 in the appendix.

Thank you for your response and additional experiments. My concerns have been addressed. I will keep the rating

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.