- 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
- The construction of abstractions for stochastic games is important for machine learning systems.
- The three tests are useful ingredients for achieving the intended goal.
- The experiments are also useful.
Critical weaknesses
-
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.
-
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.
-
The experiments should compare the proposed abstraction method against the existing method in [1].
-
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
(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 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 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 = 2, 4, 8 and , = 2 to 16): on the side-bet family as Proposition 7 requires of its reward condition, and on 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 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.
(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.