acceptodds
Under review as a conference paper at ICLR 2027

STRATA: Equilibrium-Relative State Abstractions for Markov Games

Abstract

Which state abstractions of a Markov game preserve its equilibria? We answer with a hierarchy of three strategic-distortion criteria for -player games: global model similarity (D0), model similarity under unilateral deviations from the played profile (D1), and best-response-value similarity (D2), and prove that at every level an approximate equilibrium of the abstract game lifts to an approximate Nash equilibrium of the ground game (at the model levels also coarse-correlated equilibria, with distortions under the device's conditional laws). The levels nest, and existing multi-agent abstraction criteria are profile-independent: the restriction D1 and D2 relax. We show where that restriction costs: in a constructed family where the played mixture cancels a variable's effect on the payoffs of played actions, every criterion that compares rewards or minimax values joint action by joint action (on all joint actions, the undominated ones or the minimax supports) keeps all of the variable's values, while D1 and D2 keep none; criteria that compare states through minimax strategies are not covered. Where discarding dominated actions suffices, it compresses more: on our two Markov Soccer games the prior value criterion restricted to undominated actions, a baseline we add, is lossless with fewer states than D2 (328 and 772). Because D1 and D2 are defined relative to the equilibrium being played, learning them is a fixed-point problem; we give a refinement loop that splits only the states that deviations from the current equilibrium tell apart, terminates by construction, and returns a joint (abstraction, equilibrium) fixed point at which the tolerance holds for the equilibrium actually played. Solving exactlyagainst ground truth: on Markov Soccer, D0cannot compress, D1 rediscovers the hand-designed abstraction, and D2 matches it with 15% fewer states, while the prior model criterion cannot compress eithern needs more states (805 vs. 649) at a larger duality gap; on the prior criterion's own benchmark, D2 is lossless (zero duality gap at every state) with fewer states (582 vs. 612), an of nine pitch sizes and reverses on four. One abstraction refined on three games, with the states of the hand design, matches or improves on it on every held-out game.

Primary area:
learning theory
Keywords:
multi-agent reinforcement learning, state abstraction, Markov games, equilibrium computation, bisimulation, exploitability, game theory, Nash equilibrium

Reviews

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

The paper investigates what information in a stochastic game can be forgotten without the resulting strategies in the abstract stochastic game exceeding a certain exploitability threshold in the original game. The paper provides three tests to determine whether an abstraction preserves these guarantees. Finally, the paper proposes a method to construct the abstraction, along with experiments demonstrating the sensitivity of the tests with respect to exploitability. The major limitation of the paper is the organisation of the ideas around the reduction of the original stochastic game while controlling exploitability.

Critical strengths
  1. The construction of abstractions for stochastic games is important for machine learning systems.
  2. The three tests are useful ingredients for achieving the intended goal.
  3. The experiments are also useful.
Critical weaknesses
  1. The related work is incomplete. The comparison to the existing work is unclear, including:

    [1] Sandholm and Singh, “Lossy Stochastic Game Abstraction with Bounds.” Proceedings of the ACM Conference on Economics and Computation (EC), 2012.

    It would be important to position and compare the paper with respect to [1] and more recent approaches.

  2. The paper should be structured around one central idea: constructing a lossy reduction of stochastic games. The three tests should then be introduced as supporting tools to establish the conditions under which an abstraction constitutes a lossy reduction.

  3. The experiments should compare the proposed abstraction method against the existing method in [1].

  4. The paper lacks clarity because it focuses on individual ingredients rather than the central goal of constructing a lossy reduction.

Questions for authors
  • How does your proposal compare with [1] and other recent methods?
  • How does your abstraction method compare with existing methods both theoretically and empirically?
5 comments

(1/2) Thank you for the review. We take your comments in order.

Sandholm & Singh (2012), [1]. We agree that the submission's treatment of [1] is not a comparison: one sentence in §6 (p. 8, l. 427-431) places its error measures, with those of Ishibashi et al. (2025), in the profile-independent row of Table 1. The revision replaces it with the following.

  • Setting. [1] treats finite-horizon, undiscounted stochastic games whose states form a layered DAG, with any number of players and general sums, and abstracts both states and actions. The discounted, infinite-horizon case is sketched and left to future work (their §5.1). We treat discounted, infinite-horizon Markov games such as Markov Soccer, and abstract states only.
  • Guarantee and error measure. [1] bounds the regret, in the original game, of a lifted subgame-perfect equilibrium of the abstract game, by reward and transition errors taken as maxima over states and all joint actions, independently of any strategy. Our D0 measures the same kind of error for state abstraction in the discounted setting: reward and pushed-forward transition differences over all joint actions, independent of play, compared pairwise within a class, where [1] compares each state with its class's abstract model, which its algorithms take from a prototype state. D1 and D2 replace "every joint action" with "every unilateral deviation from the profile being played" (Definition 1).
  • What the difference buys. Proposition 7 (pp. 4-5, l. 208-221) constructs a family HNH_N in which any partition whose reward differences, compared joint action by joint action, stay below Δβ/2\Delta\beta/2 must keep every value of a variable dd whose effect on played actions the equilibrium mixture cancels. [1]'s reward condition is of this kind: comparing each state with a prototype strictly within Δβ/4\Delta\beta/4 implies pairwise differences below Δβ/2\Delta\beta/2; the revision states this in §6. D1 and D2 keep none of the values of dd, which we check exactly on 83 games (§5.2, l. 353-359; App. H).
  • Algorithms. [1] constructs abstractions with a greedy pass and an integer program that satisfy its bounds by construction, and proves the within-level decision problem NP-complete. Our loop refines against the equilibrium it finds, and has to, because our tolerance is defined relative to that equilibrium: a partition built against a fixed reference profile, whether re-solved once or rebuilt three times, violates its tolerance by 4.8 to 30 times (Table 4, p. 19).

(2/2) Experiments against [1]. [1]'s algorithms and bounds are stated for finite-horizon layered games, and the discounted case is only sketched (their §5.1), so they cannot be run as published on discounted, infinite-horizon games such as ours. What does apply is its error measure, and we have now run it, with its protocol and predictions registered before the runs (D109 in the updated supplementary material): [1]'s reward error (its eqs. 3-8) and, for transitions, the L1L_1 distance of the pushed-forward transitions under every joint action, a test no stricter than [1]'s, each state compared with its class prototype as in [1]'s Algorithm 2, state abstraction only, refined inside the procedure we use for D0 and scored as every row of Table 3 (exact duality gap of the lifted equilibrium). It returns the identity partition on both games of Table 3 at every one of 23 tolerances from 10−910^{-9} to 0.4 (760 and 1,520 states), so [1]'s stricter transition test would too, as the model criterion of Ishibashi et al. (2025) and our own D0 do on both games (Table 3; the D0 row on the plain game was run for the revision). So none of the three model-level criteria that compare states over all joint actions ([1]'s, Ishibashi et al.'s and our D0) compresses Markov Soccer. On the distractor game, comparing states only under deviations from the profile played is what compresses: D1 rediscovers the hand-designed abstraction (760 states) and D2 matches its exploitability with 15% fewer states (Table 2). On the two separation families [1]'s measure keeps every value of the irrelevant variable (no class mixes two values; side-bet family NN = 2, 4, 8 and GNG_N, NN = 2 to 16): on the side-bet family as Proposition 7 requires of its reward condition, and on GNG_N as Proposition 6(iii) shows for tolerance zero. The revision adds [1] as a row of Table 3. This tests [1]'s error measure, not its algorithms or its action abstraction, which are defined for finite-horizon games.

Other recent methods, in theory and in experiments. The most recent state-abstraction method for Markov games we know of is Ishibashi et al. (2025). We compare against both its model criterion and its Q⋆Q^\star criterion on its own 760-state benchmark, with exact gaps where that paper estimates them by minimax Q-learning (Table 3, Fig. 2, App. E); add a dominance-aware variant, which compresses Markov Soccer more than our criteria (§5.2) but whose partitions, unlike the loop's, do not transfer to the changed game of §5.3; and repeat the comparison on nine pitch sizes (App. I) and on Oshi-Zumo, a game we did not design (App. J). The theoretical comparison is Table 1, the nesting results (Propositions 3 and 5) and the two separations (Propositions 6 and 7).

Soundness. The weaknesses the review lists concern related work, organization and the comparison with [1], which we address above. If there is also a concern about correctness, for example a step in a proof or a flaw in an experiment, we would be grateful to hear it so that we can answer it during the discussion.

Organization and clarity. We accept this, and the revision reorganizes the abstract and §1 around the question you name: how to reduce a stochastic game while controlling the exploitability, in the original game, of the strategies the reduction yields. An abstraction is presented as a lossy reduction whose loss is that exploitability. §1 states four research questions (which tests license such a reduction and what each bounds; what each test may forget; how to construct a reduction whose test depends on its own equilibrium, and at what cost; what a reduction buys, measured exactly), says which section answers each, and gives one contribution per question; §3-§5 open with the question they answer. §4 also says how the construction is used and what it costs. The reorganization changes no result or theorem, and the title is unchanged.

I thank the authors for their rebuttal and the revisions.

The revised paper is clearer. The positioning relative to Sandholm and Singh (2012) is improved.

My main remaining concern is algorithmic. The distinction between finite-horizon and discounted infinite-horizon games does not preclude comparison with Sandholm and Singh’s algorithms. The latter setting can be approximated through finite-horizon truncation. Evaluating their error criterion within the authors' refinement procedure is informative, but does not replace an algorithmic comparison.

Moreover, the additional experiments clarify that the proposed criteria do not consistently yield smaller abstractions or better computational efficiency than existing alternatives. The refinement procedure guarantees admissibility at termination, but not minimality or computational advantage.

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

The paper analyzes abstraction in Markov games. It studies three levels of similarity: global model similarity (D0), model similarity under unilateral deviations from the played profile (D1), and best-response-value similarity (D2) --- thereby opening up some new ground. As has been pointed out before, the problem of finding and abstraction and equilibrium is a fixed-point problem because abstraction and equilibrium finding constitute a chicken-and-egg problem. The paper presents an algorithm for Markov games that finds such a fixed point. The paper also has experiments on small Markov games.

Critical strengths

The paper studies three levels of similarity: global model similarity (D0), model similarity under unilateral deviations from the played profile (D1), and best-response-value similarity (D2) --- thereby opening up some new ground.

As has been pointed out before, the problem of finding and abstraction and equilibrium is a fixed-point problem because abstraction and equilibrium finding constitute a chicken-and-egg problem. The paper presents an algorithm for Markov games that finds such a fixed point.

The paper also has experiments on Markov games (albeit small ones).

Critical weaknesses

While Markov games have been studied a lot, they don't really occur much in practice, if at all. More impactful would be if these results could be generalized to the context of extensive-form games.

The experiments are on very small games. It is not clear that the approaches would scale.

It is not clear how one would use these results. The usual way abstraction is used in games is that one makes an abstraction that is smaller than the real game so that one can use an equilibrium-finding algorithm on the abstracted game. It is not clear (at least not to me) how the results in the present paper would be helpful toward that. Perhaps the authors can explain how they would be helpful in that, or helpful in some other practical way.

See also my other question below.

Minor point: should probably also cite the JACM paper 'Lossless abstraction of imperfect information games'.

Questions for authors
  1. It is not clear how one would use these results. The usual way abstraction is used in games is that one makes an abstraction that is smaller than the real game so that one can use an equilibrium-finding algorithm on the abstracted game. It is not clear (at least not to me) how the results in the present paper would be helpful toward that. Perhaps the authors can explain how they would be helpful in that, or helpful in some other practical way.

  2. As the paper states, the potentially new aspects D1 and D2 quantify over a single player's deviations against the profile being played. What is the profile being played in games that have multiple equilibria?

4 comments

(1/3) Thank you. We answer Q1 first, then Q2, the remark on fixed points, scale, and extensive form.

How one would use these results (Q1). For games whose model can be stored. The loop needs the ground game's model and, for D2, exact single-agent best responses in it at every iteration, so it is not a route to games too large to write down; App. K reports that learned best responses did not replace them. What it takes off the ground game is the equilibrium computation, one LP per state per sweep, which it runs on abstract games only. Four uses are measured in the paper:

  • Constructing the abstraction without knowing what to discard. Starting from a single abstract state, D1 rediscovers the hand-designed abstraction of the distractor game exactly (760 of 1,520 states, the same exploitability), and D2 finds one with 15% fewer states at the same exploitability, or 4.9 times lower exploitability at 1.6 times the states; the tolerance moves along that curve (Table 2).
  • Checking an abstraction one already has. For a hand design or any other partition, D0-D2 say which level licenses it, with Theorems 1-2 as admissibility conditions (their bounds are loose, 26 to 10510^5 times the exact values); with exact best responses the lower side of the bracket is its exact exploitability (Remark 2, Corollary 4).
  • Solving less. As a distractor variable grows from 2 to 64 values (1,520 to 48,640 states), the D1 loop solves 95 to 116 thousand matrix games throughout, while the ground solve grows linearly to 3.26 million: at 64 values D1 solves 34.4 times fewer and D2 14.0 times fewer, up from 3.98 at 32 values because D2 needed 7 iterations instead of 11 (both solve more at 2 values, D2 also at 4; Table 5). Timed end to end (new; single runs on an otherwise idle machine), the LPs take 7 s (D1) and 31 s (D2) against 187.5 s of LPs in the ground solve at 32 values. With our reference implementation's per-iterate diagnostics switched off (bounds, distortions, exact exploitability; the split rule does not use them), the D2 loop is faster than the ground solve from 8 values on: 1.34, 1.43, 1.61 and 1.49 times at 8, 16, 32 and 64 values (316 s against 472 s at 64). The margin did not grow from 32 to 64 values: over that step the loop's time per iteration grew 4.2 times, the game's transitions 4 times and the ground solve's time 2.5 times. With the diagnostics, and for D1 at every size, our implementation is slower: D1's split rule, a fixed-point refinement on what a deviator faces, costs more as implemented than the LPs it saves, and we did not tune the loop for cost. The loop's equilibrium is approximate (exact exploitability 0.004 to 0.058, falling as the variable grows) where the ground solve is exact. The revision adds both timings to Table 5 and corrects the sentence after it (l. 1024-1025), which called the loop cheaper where it only solves fewer matrix games.
  • Reusing one abstraction across games. One D2 partition refined on three games is less exploitable than the hand design on every held-out game with δ>0\delta>0, including one outside the training range (0.039 against 0.159), at 1.65 times its states (§5.4). When a new game is known only through a generative model, a partition learned on a related game with a known model cuts the samples needed 13 times on GNG_N at N=16N=16 (1.6 at N=2N=2; §5.3); on the second family we test, HNH_N, the unabstracted learner needs fewer.

(2/3) Which profile, in games with several equilibria (Q2). The profile is the one the loop itself plays: the lift of the equilibrium that the solver selects on the final abstract game. The loop returns a joint (abstraction, equilibrium) fixed point, and the tolerance, and with it the bounds of Theorems 1-2, holds for that equilibrium rather than for every equilibrium (§4, l. 255-269; App. A.7). This is deliberate. Covering every equilibrium is what profile-independent criteria do (D0, or exact bisimulation; in two-player zero-sum games, the Q⋆Q^\star criterion, which implies D2 whenever the lifted profile is exact at every state, Proposition 5), and Propositions 6-7 show what that costs in states. Selection does move the partition, and we measured how far: rerunning the loops on four games with each player's actions listed in reverse order, so that only the LP solver's choice among equilibria can change, changes the partition at every tolerance and its size at 15-21 of 21, while D2's smallest lossless partition moves by at most 2% (582 to 573 states on the benchmark) and that of its near-best-deviation variant by up to 11% (App. I; the revision corrects l. 1529-1533 of the submission, which said "the same games"). Since submission we have made the choice explicit, with the rules and predictions registered before the runs (D107 in the updated supplementary material). A second-stage LP over each abstract stage game's optimal face chooses among its equilibria; our games are two-player zero-sum, where any such choice is an exact equilibrium of the abstract game, so Theorems 1-2 apply unchanged. The choice is also a lever: taking, at every re-solve, the optimal strategy closest to the previous iterate's shrinks D2's smallest lossless partition (scored as in App. I, by re-solving the abstract game with our default solver) on all ten games, by 3-18% (582 to 498 states on the benchmark, 1,243 to 1,053 on the distractor game), and halves the median number of iterations (8 to 4); every returned partition passed the exact admissibility check at the profile played, and the rule beats an abstraction-blind choice (the optimal strategy with the smallest largest component) on nine of ten games. The rule we had registered as the lever, choosing the equilibrium that minimizes within-class reward spread, did nothing, and four of the six registered predictions failed. The revision reports this in Appendix O.

The fixed point has been noted before. Agreed. Brown & Sandholm (2015) interleave action abstraction and equilibrium finding in extensive-form games; we discussed them in App. B (l. 1050-1055), and the revision moves this into §6. What changes here is that the tolerance itself is defined relative to the equilibrium, so the fixed point is what makes the bound apply: a partition built against a fixed reference profile, whether re-solved once or rebuilt three times, violates its tolerance by 4.8 to 30 times (Table 4, p. 19). The revision also cites Gilpin & Sandholm (JACM 2007); thank you. In games with ordered signals, every Nash equilibrium of the abstracted game that GameShrink produces converts to an equilibrium of the original game, a guarantee that does not depend on the profile. D1 and D2 at zero tolerance ask only that the abstraction be lossless for the equilibrium played; that is what lets them drop a variable whose effect only the played mixture cancels, which every criterion comparing rewards or minimax values joint action by joint action must keep (Proposition 7).

(3/3) Scale. You are right that the games are small. The largest we solve exactly has 48,640 states, 64 times the prior benchmark: the distractor game with its distractor variable at 64 values, where the loops return 760 (D1) and 700 (D2) classes at exact exploitability 0.004 while solving 34.4 and 14.0 times fewer matrix games than the ground solve (Table 5, rows added in the revision). Its added states are copies along a variable that barely matters (a cost δ=0.05\delta = 0.05), so it shows that the loop discards such a variable at scale, not that it handles a large game with rich structure; and the loop needs the ground game's model and, for D2, exact best responses, so it is not a route to games too large to write down. Every quantity is computed exactly, which is what lets us check each bound and separation against ground truth (§1, "Why exact"). With learned best responses, the profile-relative loop did not carry over to function approximation (App. K, on which no claim of the paper rests). What did carry over is the D0 level used as a test for which observation variables to delete, chosen without deviators: on MPE predator-prey with distractor channels and held-out layouts, MAPPO with those variables deleted beats raw MAPPO head-to-head in both roles (three fresh seeds at 2×1072\times10^7 steps), though at that budget its measured exploitability lower bound is the higher of the two (App. K).

Markov games in practice, and extensive form. We do not claim Markov games are more common than extensive-form games, but they are the working model, with fully observed states, in several literatures. In empirical industrial organization, discounted stochastic games are estimated on industry data under Markov perfect equilibrium, as formalized by Maskin & Tirole (2001), whose payoff-relevant state App. B discusses: the Ericson & Pakes (1995) model, the two-step estimator of Bajari, Benkard & Levin (Econometrica, 2007), and Ryan (Econometrica, 2012) on the US cement industry. In security, Lye & Wing (2005) model attacker and administrator as a two-player stochastic game and compute its Nash equilibria. Among game-playing systems, no-press Diplomacy is a seven-player simultaneous-move game on a fully observed board (Anthony et al., 2020). In multi-agent RL, Markov games have been the formal model since Littman (1994), though benchmark suites such as that of Lowe et al. (2017) are partially observable. On extensive form: a finite perfect-information extensive-form game is a turn-based Markov game on its tree (the player not moving has one action, and each leaf's payoff is rescaled by γ−depth\gamma^{-\text{depth}} to undo discounting), so that class is covered. Imperfect information, where abstraction matters most in practice, needs partially observable stochastic games, which part of the game-solving literature has adopted as a common model (Kovařík et al., 2022: unrolling a factored-observation stochastic game gives an EFG, and every perfect-recall timeable EFG corresponds to one; Student of Games, Schmid et al., 2023, is presented in that formalism). Our criteria and theorems are stated for fully observed Markov games, and we do not claim they carry over to that case. The revision adds a sentence to §2 to this effect.

Thank you again for your review. One result posted since our reply bears on your question of how the results help the usual pipeline (build a smaller abstract game, solve it, carry its equilibrium back). At reviewer a9yT's request we ran Sandholm & Singh's state-abstraction algorithms (their greedy pass and an integer program) in exactly that pipeline, on finite-horizon truncations of both games of Table 3; every row is in our reply to a9yT. They are lossless only at tolerance 10−910^{-9}, where they keep every state at level 0; at every positive tolerance the lifted strategies are exploitable (GAP 0.013 to 0.72). On the plain game with the pitch's symmetry factored out (380 states), the D2 loop is lossless with 296 states and the D2u loop with 196 (the dominance-aware baseline we add: 194). The games are small, as you note, and we make no claim about scale beyond §7 and Table 5. We are glad to answer anything else before the discussion closes.

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

This paper studies state abstraction in Markov games with the goal of preserving approximate equilibria. The authors introduce three strategic-distortion criteria: D0, which measures global model similarity; D1, which measures model similarity under unilateral deviations from a given strategy profile; and D2, which measures the similarity of best-response action values. Unlike previous criteria, D1 and D2 explicitly take into account the equilibrium strategies being played.

The paper establishes theoretical guarantees on how approximate equilibria of abstract games transfer to the original games and clarifies the relationships among the proposed criteria and existing approaches. In particular, Proposition 7 constructs a family of games in which D1 and D2 achieve substantially greater state compression than previous entrywise model- and value-based criteria, even when the latter are restricted to undominated actions or equilibrium supports.

The authors also propose an iterative refinement algorithm that alternates between equilibrium computation and state abstraction refinement. Experiments on constructed games and Markov Soccer evaluate the resulting compression, exploitability, and sample efficiency, with additional experiments on three-player general-sum games.

Critical strengths
  1. An interesting and well-motivated approach to state abstraction. The idea of defining state similarity relative to the equilibrium strategies being played is appealing. Since the ultimate goal is to preserve equilibria rather than the entire game model, focusing on unilateral deviations is a natural and potentially useful relaxation of previous abstraction criteria.

  2. Theoretical guarantees and a meaningful separation result. The paper establishes guarantees for transferring approximate equilibria from abstract games to the original games. More importantly, Proposition 7 demonstrates that the proposed criteria can achieve substantially greater state compression than existing entrywise criteria, even after restricting those criteria to undominated actions or equilibrium supports. This provides a clear theoretical justification for considering equilibrium-relative abstraction rather than simply refining existing model- or value-based approaches.

Critical weaknesses
  1. Limited theoretical guarantees of practical superiority over existing methods. Although the proposed criteria are theoretically less restrictive, the paper does not establish that the resulting abstraction algorithms consistently outperform existing approaches in terms of computational efficiency or the number of abstract states obtained. This is understandable, since finding an efficient abstraction is itself a difficult problem. Nevertheless, the theoretical advantages of the criteria do not necessarily translate into algorithmic advantages. In addition, while the equilibrium-transfer guarantees are useful, I am not entirely convinced that they represent a substantial technical advance over the results of Ishibashi et al. (2025) and earlier work on approximate state abstraction.

  2. Mixed empirical advantages and limited validation beyond zero-sum games. The experiments do not consistently demonstrate the superiority of the proposed approach. In particular, the dominance-aware baseline achieves stronger compression than D2 in some Markov Soccer settings. This may reflect the inherent difficulty of finding good abstractions rather than a fundamental limitation of the proposed criteria, but it makes the practical advantage less conclusive. Furthermore, although the theoretical framework covers general-sum games with multiple players, the empirical evaluation focuses primarily on two-player zero-sum games. The general-sum experiments are relatively limited, leaving the broader applicability of the approach insufficiently established.

Questions for authors
  1. Technical novelty relative to prior work: Could the authors clarify which aspects of the proofs of Theorems 1 and 2 require fundamentally new arguments beyond the techniques used by Abel et al. (2016) and Ishibashi et al. (2025)? I find the equilibrium-relative criteria interesting, but would like to better understand the technical novelty of the equilibrium-transfer guarantees.

  2. Gap between theoretical and empirical advantages: Proposition 7 provides a convincing separation from existing entrywise abstraction criteria, whereas the experimental results show that dominance-aware baselines can sometimes achieve better compression. What do the authors consider the main obstacle to realizing the theoretical advantages of D1 and D2 more consistently in practice? Is this primarily a limitation of the refinement algorithm, or do the proposed criteria themselves have practical limitations that are not captured by the separation results?

  3. Scope of the general-sum extension: Given that the main theoretical and empirical comparisons with prior work focus on two-player zero-sum games, what is the strongest evidence that the proposed approach provides similar practical benefits in general-sum games? Would restricting the main contribution to zero-sum Markov games allow for stronger theoretical or algorithmic results?

3 comments

(1/2) Thank you for a careful review. We take the two weaknesses together, then your three questions.

Practical comparison (W1, W2). We agree with W1: the paper neither claims nor shows that the resulting algorithms consistently need fewer states or less computation than existing ones (§7, l. 454-462); the timings added since submission are in our general response. On W2, which criterion needs fewer states depends on the game's structure. On the Markov Soccer games the dominance-aware baseline is lossless with fewer states than D2, on all ten of App. I, the two of §5.2 among them (328 vs. 582 and 772 vs. 1,243; §5.2, l. 330-339; App. I, l. 1535-1539). Where the structure of Proposition 7 is present the order reverses: on the side-bet family built on a 3 × 4 soccer core, D2 is lossless with 248-250 states while the baseline needs 290, 580 and 1,160 at NN = 2, 4 and 8 (Table 14, p. 27). Compression of the game the partition was computed on is also not the whole story: in §5.3, where the core game changes between training and test, the dominance-aware partitions do not transfer (even with the exact test model they leave an exploitability of 0.79-1.41), while the loop's do, and D1's cut the samples needed 13 times at NN = 16. This is why we describe the results as a map rather than a ranking (l. 073).

Q1: what is new in the proofs of Theorems 1-2. Two steps are specific to games; the contraction around them is standard, as the paper says. With N=1N = 1 and ε^=0\hat\varepsilon = 0, Theorem 2 is Lemma 1 of Abel et al. (2016), and its proof follows their Claims 1-3 (p. 5, l. 242-244; p. 14, l. 722-723); Lemmas 3-4 are aggregation analogues of the simulation lemma (p. 13, l. 673-675). Two steps are specific to games. (i) Lemma 2 (p. 12, l. 616-629): the MDP a player faces in the abstract game against an abstract profile is exactly the ww-aggregation of the MDP it faces in the ground game against the lift. This is what lets a single-agent argument run against the profile being played, and why the other players' profile must be ϕ\phi-measurable. (ii) Correlated equilibria: for a coarse-correlated equilibrium the distortions must be taken under both the marginal a deviator faces and the conditionals a follower faces; with the marginal alone the statement is false (Remark 1, p. 14, l. 702-710, a two-state counterexample kept as a regression test in the code). Relative to Ishibashi et al. (2025), the contribution lies elsewhere: the profile-relative criteria, the nesting results that relate their two criteria to the hierarchy (Propositions 3 and 5), and the separations (Propositions 6-7), which are lower bounds over every criterion of a class, proved by explicit constructions rather than by contraction. The revision states the two game-specific steps at the end of §3.

(2/2) Q2: is the obstacle the algorithm or the criteria? On Markov Soccer mainly the criterion, with the search second, and the experiments separate the two.

  • Criterion. At the exact ground equilibrium and the tolerance at which one pass of D2 is lossless, the minimum clique cover of the ε\varepsilon-compatibility graph, which lower-bounds every admissible partition at that profile, is 566 and 1,143 states against the baseline's 328 and 772 (§7, l. 462-468; App. N), so no search at that profile and tolerance closes the gap. For the loop itself, whose distance moves with the partition, the coarsest admissible partition is open (App. N, l. 2137-2140). The gap sits on the values of dominated own actions, which D2 compares and the baseline does not (l. 335-338); comparing only near-best deviations (Proposition 10) keeps Theorem 2's bound and shrinks D2's lossless partitions on seven of ten games, though not to the baseline's size. This is a property of the criteria that the separations do not capture, and it can be made exact: in a mirror of Proposition 7, where a variable enters only through the reward of one strictly dominated action, D1, D2 and D2u keep all MM of its values (D2: 488, 971, 1,980 and 3,972 classes for MM = 2, 4, 8, 16) while the dominance-aware criterion keeps none (145 classes at every MM), checked exactly. With Proposition 7, this shows that neither kind of criterion dominates the other; the revision adds the family with its proof (Proposition 11, App. O): the dominance-aware criterion merges all MM values at tolerance 0, while D1 below a tolerance of ω\omega and D2 below ω/2\omega/2 need at least MM classes; and Corollary 12 shows that, at an exact Markov perfect equilibrium, D2's distortion can exceed the dominance-aware criterion's tolerance only through the values of own actions that iterated dominance removes.
  • Search. Proposition 5's inequality holds on all 342 partitions built for Table 16 (App. I, l. 1499-1500), so every lossless Q⋆Q^\star partition among them is D2-admissible at the same tolerance (§5.2, l. 365-366): the criterion admits them, and the shortfall there is in the search, whose refinement never undoes a split (l. 366-367). The loop also over-refines: on 134 of the 135 (game, tolerance) runs of App. I that end lossless, an earlier iterate is already lossless and smaller (the classes added after that point are on average 9.7% of the returned partition). The revision reports this study, registered after a disclosed four-game pilot (D101 in the supplementary material).
  • Equilibrium selection, an algorithmic lever: choosing, at every re-solve, the optimal strategy closest to the previous iterate's shrinks D2's lossless partitions by 3-18% on all ten games (582 to 498 states on the benchmark; details in our reply to DV8c), narrowing the gap to the baseline without closing it.
  • A limitation the separations do not capture. On the side-bet family, the D1 and D2 partitions are exact on the test game up to 10−510^{-5}, yet they learn from samples more slowly than the unabstracted model (§5.3, l. 394-398). The explanation we registered, the estimator's within-class weighting, was tested and ruled out; the cause is open (App. G, l. 1315-1334).

Q3: general-sum games. The strongest evidence is exactness and automatic discovery, not a compression advantage. On random three-player general-sum games (8 games, 4 distractor costs), Theorems 1 and 2 and Proposition 3 hold on all 768 (abstraction, profile) pairs, 640 of them non-equilibrium profiles, and D1, starting from a single abstract state, recovers the 20-state hand design in 21 of 24 games with δ>0\delta > 0, where D0 refinement returns the identity. D2 does not reproduce its two-player advantage (App. L, p. 38). These games use potential-structured rewards so that equilibria can be found, and the CCE statement is not tested empirically (§7, l. 457-460). Restricting the main contribution to zero-sum games would not change Theorems 1-2, which do not use zero-sum structure. What zero-sum structure buys, the paper already uses where it needs it: the abstract games are solved by linear programs; any choice among their equilibria is an exact equilibrium, which is what makes the selection rule of our reply to DV8c safe; and Propositions 5-8 (the Q⋆Q^\star nesting, both separations and the sample bound) are stated for two-player zero-sum games, as is every comparison with prior work. If you think the paper reads better that way, we will scope the contribution statement to two-player zero-sum games and present §5.5 as verification of the general-sum theorems.

Thank you again for your review. One result posted since our reply bears on W1, whether the criteria yield fewer abstract states than existing approaches. At reviewer a9yT's request we ran Sandholm & Singh's (2012) state-abstraction algorithms on finite-horizon truncations of both games of Table 3; every row is in our reply to a9yT. They are lossless only at tolerance 10−910^{-9}, with every state kept at level 0, and lossy at every positive tolerance. On the plain game with the pitch's symmetry factored out (380 states), the smallest lossless partitions are: the dominance-aware baseline 194 states, the D2u loop 196, the D2 loop 296, the model criterion of Ishibashi et al. (2025) 380, and Sandholm & Singh's algorithms 380 at level 0. Against both existing approaches the D2 and D2u loops compress more; the dominance-aware baseline, which we add, remains the smallest, as in our reply. We are glad to answer anything else before the discussion closes.

Comments on the paper

10 comments
Area_Chair_coLYOpenReview ↗

Reviewers: (by Nov. 18 AoE) please comment on author's feedback, and consider re-rating.

Dear Reviewers,

The authors have replied to your reviews. Does the author solve your concerns?

Please respond to the author and consider editing your rating.

The author-reviewer discussion phase will end on November 18 at 11:59pm AoE.

Thanks.

AC

AuthorsOpenReview ↗

Revised PDF Uploaded: List of Changes

(1/3) Revised PDF uploaded: list of changes

We have uploaded a revised PDF. New and changed text is in blue, except the new references and Appendix O, which is new throughout. The abstract, §1 and §5 are reorganized around the question a9yT names (items 1 to 4 and 10); the reorganization changes no result, number or theorem, and the title is unchanged. The numbering of sections, tables, figures, theorems and appendices is unchanged, so the references in the reviews and in our replies still hold; Table 1 gains a row, and the three new tables (22 to 24) are in Appendix O. Locations are page and line numbers of the revised PDF.

  1. Abstract (p. 1, l. 11-30), rewritten along the lines of item 2: an abstraction as a lossy reduction whose loss is the exploitability of the equilibrium carried back; the three tests, by how they compare states; the two separations and the dominance-aware baseline; the benchmark's numbers (582 states for the D2 loop, 612 for the prior value criterion, 328 for the baseline). "Existing multi-agent abstraction criteria" now reads "existing model criteria for Markov games" (revision 8). The OpenReview abstract field carries the new abstract.
  2. §1 (p. 1, l. 34 to p. 2, l. 105), reorganized around four research questions (a9yT): an abstraction as a lossy reduction, with two running examples, a variable that matters only when both players play an action no equilibrium plays (the family GNG_N) and a variable that sets the stakes of a side bet whose effect the played mixture cancels (the family HNH_N) (p. 1, l. 34-44); four research questions and the sections that answer them (l. 45-48); the three ways of comparing states of Table 1, what each may forget, and where the dominance-aware baseline compresses more (p. 1, l. 49 to p. 2, l. 82); and one contribution per question (p. 2, l. 84-105), which now also states where the loop is faster in wall-clock and that the baseline does better than D1 and D2 on the distractor game. The sentence on existing criteria is scoped to state-abstraction criteria for Markov games, and "in their words" is removed from the sentence on Ishibashi et al. (2025): the phrase was ours, not theirs.
  3. Sections 3 to 5 (p. 3, l. 134-136; p. 5, l. 266-268; p. 6, l. 302-304 and 311; p. 7, l. 331; p. 8, l. 409): new titles ("Three tests for a lossy reduction", "Constructing the reduction is a fixed-point problem", "Exact verification"; §5.1 to §5.3 "What each test compresses", "The three ways of comparing states, head to head", "Sample efficiency on a held-out game"), and each section opens by naming the research questions it answers.
  4. Table 1 (p. 4, l. 163-169): a middle row for the dominance-aware baseline, which compares states only on joint actions that survive iterated elimination of strictly dominated actions or on minimax supports; the caption names the three ways of comparing states. With that row, §3 (p. 4, l. 195) and contribution (2) say that three arrows of the table are relaxations, where the submitted text said every arrow.
  5. §2 (p. 3, l. 129-132): one sentence on extensive-form games: perfect-information games are turn-based Markov games, with leaf payoffs rescaled for discounting; imperfect information is not covered (DV8c).
  6. §3, after Proposition 8 (p. 5, l. 252-258): which proof steps are standard and which are specific to games (pVnR, Q1).

(2/3) List of changes, continued

  1. Statements narrowed or corrected to what the proofs and tables give (p. 2, l. 107 to p. 3, l. 108; p. 4, l. 173, 192 and 207-209; p. 5, l. 219-222, 228-229, 244, 247 and 263; p. 7, l. 324-329 and 361-365; p. 17, l. 882, 889-891 and 914-916; p. 19, l. 996-1003 and 1020; p. 20, l. 1048-1050 and 1060-1061; p. 23, l. 1211-1212; p. 24, l. 1292; p. 33, l. 1749-1750 and 1781; p. 37, l. 1970; p. 38, l. 2028): §1 says that every experiment of §5 computes exploitability exactly and that its two-player games are solved exactly (the three-player games of §5.5 are evaluated exactly, their abstract games solved exactly in 100 of 128); §3 gives Theorem 2's ratio to the exact value (250-12,000x) where it said "looser still"; the distractor variable of §4, Table 5 and Figure 2 is no longer called payoff-irrelevant, as it carries the cost δ; Appendix A calls the deviator lower bound the operative measure, not a stopping criterion; in Appendix K every exploitability is a lower bound from trained deviators, the learned profile is not called an equilibrium, and a noise channel predicts itself only up to its resampling; Theorem 2 is stated for an approximate Nash equilibrium as in Theorem 1; the "in particular" of Proposition 5 requires the lifted equilibrium to be exact at every state (GAP = 0); Proposition 6 holds for every such N, its proof now gives the step behind its factor N, and its closing sentence covers the model criteria at tolerance 0 only, as the abstract (l. 17) and §1 (l. 53) now say; in Proposition 7 and its proof, β's norm is the largest absolute entry and equilibria play the side actions with uniform marginal, and its conclusion is that the listed criteria never merge two values of d (the submitted factor N does not hold for model criteria at positive tolerance); Proposition 8 says that no Markov perfect equilibrium plays τ, and its remark gives the R^2 cost of rescaling rewards; Appendix A's comparison with the prior value criterion's bound cites Proposition 5, and its remark on correlated equilibria says that its condition is per recommendation; in §5.1, Theorem 1's ratio to the exact value is stated for δ > 0, and as 26x on a held-out game, and the ceiling on exploitability in these two-player zero-sum games is V_max ≈ 20, not N V_max ≈ 40 as submitted (also in Appendices A and C), so Theorem 2's bound passes it from δ = 0.05 on; a remark after Proposition 10 says the D2u loop meets its condition by construction, and step (3) of its proof covers every action in the support; on GNG_N (§5.2), D2 was run on the seven soccer games, and the restricted criteria need no more states than the loops (fewer on soccer).

  2. §4 (p. 6, l. 279-281 and 285-299): the iteration counts now cover the ten games of Appendix I (D2 up to 19 iterations; the submission said 11). New paragraph "Use, cost and selection": how the loop fits the abstract, solve, lift pipeline; its cost in matrix games and in wall-clock time; checking a given abstraction with exact best responses; which equilibrium the bounds refer to, and how much the solver's choice among equilibria moves the partition (DV8c, Q1 and Q2).

  3. §5.2 and §5.3 (p. 7, l. 337-343 and 374-377; p. 8, l. 397-403 and 411): a row in Table 3 for Sandholm & Singh's error measure, which returns the identity partition on both games at all 23 tolerances up to 0.4 (a9yT); D0 added to the plain game's top row (l. 342): run in the revision at the same 23 tolerances, it also returns the identity at each (Appendix O, p. 43, l. 2274-2276); the sentence reading the table updated, with two corrections: at gap 0.1 or below on the distractor game, 595 vs. 1,297 states on the common grid (submitted: 649 vs. 1,324 at gap 0.11, from Table 3's coarser grid; App. I, p. 30, l. 1613-1615), the pitches compared are the benchmark and eight more, and "342 of 342" counts the partitions on which Proposition 5's inequality was checked; the opening of §5.3 now agrees with Table 5 on what computing a partition costs.

  4. §5.1 and §5.2, organized around what each comparison establishes (p. 6, l. 323; p. 7, l. 358-370; p. 8, l. 378 and 393-395): §5.1 states the result of Table 2 in the text; §5.2 opens with the two separations, checked exactly on all 170 games, before the benchmark comparison; the paragraph on the dominance-aware baseline is headed "Where discarding dominated actions does better" (its result is unchanged); and §5.2 closes with what happens when the core game changes (§5.3).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.