{"id":"8098648b-b0c4-4b78-8670-dcaf2c27dd35","arxiv_id":"2412.15877","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A proof that if states are merged when their optimal Q-values are close, the Nash equilibrium of the abstracted zero-sum Markov game has a duality gap bounded by O(ε/(1−γ)^3).","lead":"This paper derives error bounds for state abstraction in two-player zero-sum Markov games, showing how much the equilibrium of an abstracted game can differ from the true game's equilibrium. The bounds are simple, but the main abstraction criterion requires knowing the game's optimal values in advance, which limits the practical benefit.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3 relies on inequality (12), which is false for the lifted abstract equilibrium; the proof of Theorem 1 as written is invalid and needs repair.","rationale":"The reader's weakest_assumption concerns the practical circularity of needing Q* to construct ϕQ*. That is a real framing limitation, but it does not attack the conditional theorem: Assumption 1 explicitly assumes ϕQ*, and Section 4.1 acknowledges that abstraction discovery is open. The central mathematical proof, however, contains a false step. Inequality (12) claims Q* cannot lie below the Q-function of the best response to the lifted abstract equilibrium, but π*_GA is not the ground equilibrium, so the minimax property of Q* does not apply there. The two-state example in the attack is a concrete witness: Q* values differ by exactly δ between the aggregated states, yet Q^{π†}−Q* is positive. The final bound may still be correct — the example's duality gap is O(δ) and well inside 12δ/(1−γ)^3 — but the provided proof does not establish Lemma 3 as written. This is a correctness risk in the central proof rather than a framing issue, so I keep the verdict conditional with the additional requirement that Lemma 3's lower-bound argument be corrected or the theorem re-proved.","tokens_in":18369,"tokens_out":25953,"duration_ms":222013,"concrete_test":"Run value iteration on the two-state game above with γ=0.5 and δ=0.01; compute Q* and Q^{π†,π*_GA,2} where π*_GA is the 1/2–1/2 lift of the abstract equilibrium. Verify that Q*(s1,(T,L))−Q^{π†}(s1,(T,L)) = −0.00125 < 0, contradicting (12). If reproduced, replace the invalid inequality in Lemma 3 with a symmetric recursion on min(Q^{π†}−Q*) and re-derive whether the constant 2ε/(1−γ)^2 survives; this determines whether Theorem 1 stands with corrected proof or needs a revised bound.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 4.2, proof of Lemma 3, uses inequality (12): Q*(s,a) - Q^{π†_1,π*_GA,2}(s,a) ≤ 0, citing the minimax property (1). This does not follow: (1) applies to the ground equilibrium π*, while π*_GA is an equilibrium of the abstract game, so π*_GA,2 need not be the ground equilibrium strategy. A best response to a suboptimal π*_GA,2 can achieve strictly more than V*, making Q^{π†} exceed Q*. Concrete failure: take γ=0.5, states s1,s2, actions T/B and L/R, rewards [[0,1],[1,0]] at s1 and [[0,1+δ],[1+δ,0]] at s2 (scale by 1/(1+δ) if the [0,1] reward bound is enforced), and transitions T:s1→s1, B:s1→s2, T:s2→s1, B:s2→s2. For small δ, the ground values are V1=1+δ/4, V2=1+3δ/4, so max_a |Q*(s1,a)-Q*(s2,a)|=δ, satisfying Assumption 1 with ε=δ. The abstract game is one self-looping state with reward matrix [[0,1+δ/2],[1+δ/2,0]], whose equilibrium lifts to 1/2–1/2 mixing. Against this lifted policy, player 1's best-response values are x=1+δ/2 at s1 and y=1+δ at s2, so Q^{π†}(s1,(T,L))=0.5+δ/4 while Q*(s1,(T,L))=0.5+δ/8; thus Q*−Q^{π†}=−δ/8<0, contradicting (12). The stated Lemma 3 bound may still be true, but the proof as written does not establish it; a symmetric recursion on min(Q^{π†}−Q*) is needed to repair Theorem 1.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends approximate state abstraction from single-agent MDPs to two-player zero-sum Markov games (TZMGs). It defines an abstract game through a state aggregation map and a weighting function, then studies the duality gap of the abstract game's Nash equilibrium when lifted to the ground game. The central theoretical result (Theorem 1) claims that, if states are aggregated by a map satisfying Assumption 1, i.e., states in one block have Q*-values within epsilon for every action profile, then the lifted equilibrium has duality gap at most 12 epsilon / (1 - gamma)^3. Section 6 gives analogous bounds for model similarity, Boltzmann-distribution similarity, and multinomial-distribution similarity, and Section 5 reports Markov Soccer experiments showing the number of abstract states and the duality gap as a function of epsilon.","tokens_in":18868,"tokens_out":15409,"duration_ms":126581,"significance":"If the main bound is established, the paper provides a useful first quantitative extension of Abel et al.'s MDP abstraction bounds to zero-sum Markov games. The explicit polynomial dependence on 1/(1 - gamma), the clean decomposition of the duality gap into two one-sided best-response bounds, and the reduction of three further abstraction criteria to the Q*-based criterion are attractive features. The manuscript is also honest about several limitations, including the need to know Q* to construct the abstraction. However, the proof of the central Lemma 3 currently relies on an invalid inequality, and the proof of Theorem 2 uses a model-similarity condition stronger than the one actually assumed. These gaps are load-bearing and must be repaired before the results can be accepted. The experiments illustrate the trade-off but report only approximate duality gaps and do not provide code or data.","major_comments":[{"comment":"The step 'Q*(s,a) - Q^{pi-dagger_1, pi*_GA,2}(s,a) <= 0' is not a consequence of the minimax property (1). Equation (1) characterizes the ground equilibrium pi*, whereas pi*_GA,2 is the lifted equilibrium of the abstract game and is not in general equal to pi*_2. If pi*_GA,2 is suboptimal, player 1's best response can achieve strictly more than V*, making Q^{pi-dagger} exceed Q*. A concrete two-state example (gamma = 0.5, rewards [[0,1],[1,0]] at s1 and [[0,1+delta],[1+delta,0]] at s2, with transitions T:s1->s1, B:s1->s2, T:s2->s1, B:s2->s2) satisfies Assumption 1 with epsilon = delta, yet Q*(s1,(T,L)) - Q^{pi-dagger}(s1,(T,L)) = -delta/8 < 0. Thus the proof of Lemma 3, and therefore of Theorem 1, is invalid as written. The lower-bound half of Lemma 3 appears obtainable by a symmetric min-recursion, so the result may be repairable, but the repair must be supplied.","section":"§4.2, Lemma 3 and Eq. (12)"},{"comment":"Assumption 2 only bounds differences of transition probabilities at the level of abstract blocks, i.e., |sum_{s' in G_A(s'_A)} (P(s'|s1,a) - P(s'|s2,a))| <= epsilon. The proof of Lemma 5 then uses the bound sum_{s'} |P(s'|s1,a) - P(s'|s2,a)| |V(s')| <= gamma epsilon |S| / (1 - gamma). This requires a per-state L1 bound, which Assumption 2 does not provide. A block-sum bound of epsilon does not imply such an L1 bound: two transition distributions can differ by total variation 2 within a single abstract block while all block sums are zero. Therefore the displayed derivation of inequality (13) is not justified, and Theorem 2 as stated is not proved. The assumption should be strengthened to include sum_{s'} |P(s'|s1,a) - P(s'|s2,a)| <= epsilon, or a genuinely different argument is needed.","section":"§6, proof of Lemma 5 / Assumption 2"},{"comment":"The abstraction is defined in terms of Q*, the very quantity a solver would be trying to compute. The paper acknowledges this in §4.1 ('minimax Q-learning is used to calculate Q-values for the ground game'), but the practical circularity remains a significant limitation: Theorem 1 is a conditional guarantee for abstractions that are already Q*-consistent, and the experimental protocol in §5.2 first solves the ground game and then aggregates. The manuscript should state explicitly that no computational saving for the original ground game is claimed unless Q*, or a sufficiently accurate approximation of it, is available at no greater cost. This does not invalidate the conditional bound, but it materially affects how the contribution should be read.","section":"§4.1 and §5.2"}],"minor_comments":[{"comment":"The heading 'Extentions' should be 'Extensions'.","section":"§6 heading"},{"comment":"The word 'apggregation' appears in the statement of Assumption 1 and in the sentence before Theorem 1; it should be 'aggregation'.","section":"Assumption 1 and Theorem 1 statement"},{"comment":"The equality 'epsilon + gamma epsilon |S| / (1 - gamma) = epsilon + gamma(|S|-1) epsilon / (1 - gamma)' is arithmetically incorrect; the correct right-hand side is epsilon (1 + gamma(|S|-1)) / (1 - gamma). The final stated bound of Lemma 5 is consistent with the corrected expression, so this appears to be a typo, but it should be fixed.","section":"§B.2, Eq. (13)"},{"comment":"The duality gaps reported in Figure 3 are approximations obtained from Q-learning, not exact values, and no code or data are provided. The authors should state approximation errors or use exact dynamic programming on the 760-state game, and should report the number of random seeds used.","section":"§5.2"}],"recommendation":"major_revision","confidential_remarks":"The central gap in Lemma 3 is, in my assessment, repairable: the counterexample attacks only the auxiliary inequality (12), not the final bound, and a symmetric min-recursion should recover the missing lower bound. The Theorem 2 issue is more serious because the stated block-sum assumption appears too weak for the proof technique used; this may require either changing the assumption or removing the theorem. I would not reject the paper on the basis of the Theorem 1 proof gap, but the authors must supply a corrected proof before the claims can be considered established. I also recommend asking for code/data availability, since the experimental section currently does not permit reproducibility checks."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a legitimate, incremental extension of Abel et al.'s approximate state abstraction from MDPs to two-player zero-sum Markov games. The main theorem's proof holds up; the stress-test note about inequality (12) is mistaken.\n\nWhat's new: the paper defines Q*-similarity abstraction for TZMGs and proves a duality gap bound of 12ε/(1−γ)^3 for the induced equilibrium. It also gives bounds for model, Boltzmann, and multinomial similarity via reductions to the Q* criterion. That's a real extension of an established program, not a new framework.\n\nThe proof of Theorem 1 is mostly clean. Lemma 2 and Lemma 3 follow standard contraction arguments. I checked the specific stress-test concern: inequality (12) claims Q* − Q^{π†} ≤ 0, and it is actually valid. For any fixed opponent policy π2, player 1's best-response value is at least the minimax value V*, so V^{π†} ≥ V* pointwise, and hence Q^{π†} ≥ Q*. The counterexample in the stress-test note actually satisfies (12): it gives Q* − Q^{π†} = −δ/8, which is ≤ 0. So that concern evaporates. There are minor typos—'apggregation' in Assumption 1, 'Extentions' in Section 6, and an arithmetic slip in the proof of Lemma 5 where the bound is looser than needed but still valid.\n\nThe real limits are elsewhere. Assumption 1 is defined around Q*, which you don't know until you solve the game. The paper acknowledges this in Section 4.1, but it means the abstraction is an a posteriori guarantee, not a practical cost-saver. The experiments build the abstraction after solving the ground game, and they report approximate duality gaps from Q-learning without error bars or code. The model-similarity bound scales with |S|, and the Boltzmann bound has an e^{1/(1−γ)} factor, so those extensions are mostly formal.\n\nWho should read it: people working on state abstraction for MARL or exploitability in games. It's a solid contribution to that subfield, though not a breakthrough. It deserves a serious referee; the proofs should be checked carefully, but I believe the central result is correct.\n\nRecommendation: send it to review. A referee can fix the typos and ask for cleaner experiments, but the core theory is sound.","headline":"A solid, incremental extension of approximate state abstraction to zero-sum Markov games; the main proof holds up, and the stress-test concern about Lemma 3 is mistaken.","tokens_in":19297,"tokens_out":11723,"would_cite":true,"duration_ms":80329,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A15","91A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"State aggregation in zero-sum Markov games preserves near-optimal play, up to an error linear in how much Q-values are allowed to differ within a merged block.","keywords":["state abstraction","Markov games","zero-sum games","duality gap","Nash equilibrium","minimax Q-learning","state aggregation","approximate abstraction"],"falsifier":"Search exhaustively over small two-player zero-sum Markov games: for each game compute Q* exactly, build the coarsest partition satisfying Assumption 1 for a fixed ε, solve the abstract game exactly, and check whether the lifted equilibrium's duality gap exceeds 12ε/(1−γ)^3; one exceeding example would refute Theorem 1, and none would support it.","tokens_in":18193,"feed_emoji":"🎮","tokens_out":8188,"duration_ms":67161,"temperature":0.7,"pith_summary":"This paper asks whether shrinking the state space of a two-player zero-sum Markov game still leaves the players near an equilibrium of the original game. It answers yes: if states are merged only when their optimal state-action values differ by at most ε, the equilibrium computed in the compressed game, when lifted back to the original game, has duality gap at most 12ε/(1−γ)^3. The duality gap here is the largest amount either player could gain by deviating, so the bound quantifies how much abstraction costs in solution quality. The paper derives the same kind of guarantee for three additional aggregation criteria and shows in a Markov Soccer experiment that the abstraction reduces 760 states to under 300 for moderate ε while keeping the gap close to the ground game.","feed_headline":"State compression keeps zero-sum game equilibria near-optimal","feed_subtitle":"Proved: abstracted games give equilibria within 12ε/(1−γ)^3 of the original game.","key_machinery":"The load-bearing object is the Q*-similarity abstraction φ_{Q*} together with the weighted abstract game it induces. States in a block are averaged with weight function w to define abstract rewards and transitions, and the abstract game is solved for its Nash equilibrium, which is then lifted back by π*_GA(s)=π*_A(φ_{Q*}(s)). The proof machinery is the duality-gap decomposition into one-sided deviation gains, followed by three perturbation lemmas: Lemma 2 bounds the abstract-versus-ground Q-value gap, Lemma 3 bounds the ground-equilibrium-versus-lifted-policy gap, and Lemma 1 converts a uniform Q-value closeness of δ into a 2δ/(1−γ) value-difference bound. Minimax Q-learning is the algorithm used in the experiments both to estimate Q* for building the abstraction and to solve the abstract game.","core_discovery":"The central claim is Theorem 1. For a two-player zero-sum Markov game with discount factor γ, let φ_{Q*} be an aggregation function that maps ground states with close optimal minimax state-action values into one abstract state; explicitly, if φ_{Q*}(s1)=φ_{Q*}(s2), then |Q*(s1,a)−Q*(s2,a)| ≤ ε for every action profile a. Let π*_GA be the policy profile obtained by playing a Nash equilibrium of the abstract game in the ground game. Then GAP(π*_GA) ≤ 12ε/(1−γ)^3. The proof splits the duality gap into the two one-sided best-response advantages, bounds the difference between abstract and ground Q-values by ε/(1−γ), bounds the performance gap between the ground equilibrium and the lifted abstract equilibrium by 2ε/(1−γ)^2, and then bootstraps through the discount factor. The same template yields bounds for model similarity, Boltzmann distribution similarity, and multinomial distribution similarity in Theorems 2–4.","pith_inferences":["The abstraction starts from Q* of the ground game, so in a truly large game one must first learn those values; a natural extension the paper only mentions in passing is an iterative loop that estimates Q*, abstracts, solves, re-estimates, and refines the partition.","The theorem's bound is uniform over states, so it also certifies each state's deviation loss; the paper reports only aggregate duality gaps, and checking per-state gaps would test how tight the uniform bound is.","The same proof template should extend to other solution concepts or to games with more than two players, but the minimax structure of the duality gap would need a different measure of equilibrium distance.","The experimental duality gaps are approximated with Q-learning rather than computed exactly, so the reported curves support the theory qualitatively but are not a precise test of the constant 12 in the bound."],"forward_implications":["Exact abstraction (ε=0) recovers the ground equilibrium: the lifted equilibrium has duality gap 0, so it is a true Nash equilibrium of the original game.","For a fixed abstraction error ε, the guarantee degrades as 1/(1−γ)^3, so near-deterministic long-horizon games need much finer state partitions to keep the same solution quality.","The model-similarity bound carries an extra factor of |S|, so Q*-based abstraction is the more scalable criterion when Q* values are available.","The Boltzmann and multinomial similarity criteria inherit the Q* bound with inflated ε, so exploration-oriented abstractions also come with explicit performance guarantees.","The Markov Soccer experiment indicates that coarse abstractions with ε around 0.6 keep the duality gap close to the ground game, while coarser partitions produce deadlocks and noticeably larger gaps."],"supporting_citations":[{"why":"Supplies the approximate state abstraction framework with four similarity criteria that this paper extends from single-agent MDPs to two-player zero-sum Markov games.","marker":"Abel, Hershkowitz, and Littman 2016"},{"why":"Defines two-player zero-sum Markov games and minimax Q-learning, which provide the ground model, the equilibrium concept, and the algorithm used in the experiments.","marker":"Littman 1994"},{"why":"Establishes that stochastic games have a unique minimax value, which justifies writing Q* and V* and using the minimax condition on which the proof relies.","marker":"Shapley 1953"},{"why":"Provides the unified abstraction criteria and the iterative abstraction-refinement idea that motivate Assumption 1 and the construction of the abstract game.","marker":"Li, Walsh, and Littman 2006"},{"why":"Shows that minimax Q-learning converges to a Nash equilibrium, supporting the experimental use of Q-learning to compute equilibria of both ground and abstract games.","marker":"Szepesvári and Littman 1999"}],"fun_headline_variants":["State abstraction for Markov games with tight equilibrium bounds","Abstraction error bounded for zero-sum game equilibria","Provable guarantee: abstracted Markov games nearly optimal","Aggregate states, keep equilibria: new bound for Markov games","Zero-sum Markov games: state abstraction preserves equilibria"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bound holds only when states are grouped according to Q*, the optimal state-action values of the original game, because Assumption 1 quantifies the partition in terms of those values; if Q* is not known accurately, the constructed abstraction may violate Assumption 1 and the theorem no longer applies.","fun_headline_variants_meta":{"raw":{"variants":["State abstraction for Markov games with tight equilibrium bounds","Abstraction error bounded for zero-sum game equilibria","Provable guarantee: abstracted Markov games nearly optimal","Aggregate states, keep equilibria: new bound for Markov games","Zero-sum Markov games: state abstraction preserves equilibria"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000789,"raw_usage":{"total_tokens":3479,"prompt_tokens":947,"completion_tokens":2532,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":563,"completion_tokens_details":{"reasoning_tokens":2453}},"tokens_in":563,"tokens_out":2532,"duration_ms":16778,"temperature":1.0,"reasoning_tokens":2453,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:00:33.035428+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search exhaustively over small two-player zero-sum Markov games: for each game compute Q* exactly, build the coarsest partition satisfying Assumption 1 for a fixed ε, solve the abstract game exactly, and check whether the lifted equilibrium's duality gap exceeds 12ε/(1−γ)^3; one exceeding example would refute Theorem 1, and none would support it.","supporting_citations":[{"cited_title":"E.; and Littman, M","cited_arxiv_id":null,"evidence_quote":"Supplies the approximate state abstraction framework with four similarity criteria that this paper extends from single-agent MDPs to two-player zero-sum Markov games."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines two-player zero-sum Markov games and minimax Q-learning, which provide the ground model, the equilibrium concept, and the algorithm used in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that stochastic games have a unique minimax value, which justifies writing Q* and V* and using the minimax condition on which the proof relies."}],"review_version":1}