acceptodds
Under review as a conference paper at ICLR 2027

Strategy Completeness as a State-Abstraction Objective for Multi-Agent Markov Games

Abstract

This paper studies state abstraction in multi-agent Markov games through the lens of strategy completeness—the requirement that a compressed policy class preserve the capacity to best-respond against strategic opponents. We show that standard abstraction criteria, including predictive fidelity and value equivalence, are insufficient in competitive environments: an abstract representation can achieve zero transition prediction error and exact value calibration while incurring linear best-response loss against dynamic opponents. To explain this gap, we establish an exponential separation between decision preservation and value reconstruction, proving that preserving optimal responses against an opponent family can require exponentially fewer abstract states than reconstructing the underlying values of the same tasks under arbitrary action-dependent transitions. Motivated by this separation, we formulate the joint optimization of state partitions and policy profiles as a factorized Bellman program. We develop a provably efficient algorithm that exploits bounded treewidth in the primal graph induced by the joint Bellman factorization, computing an -optimal abstraction with certified lower and upper bounds in time polynomial in the explicit input size, , and for fixed treewidth. Finally, experiments on Markov Soccer and Connect Four validate the theory, showing that best-response-oriented state abstraction reduces best-response loss and root Nash gap compared to predictive and value-based baselines under matched representation budgets.

Primary area:
learning theory
Keywords:
multi-agent reinforcement learning, state abstraction, strategy completeness, Markov games, Bellman factorization, treewidth, policy-space response oracles, equilibrium transfer

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_EZtpOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies which state distinctions a compressed representation must retain to support best responses against a specified opponent family. It jointly considers equilibrium preservation and response quality under a shared state partition. Its main results are an exponential separation between preserving optimal decisions and reconstructing task values, and a Bellman formulation with certified optimization under bounded treewidth. Additional results address statistical error, local certification, and opponent populations. Experiments compare abstraction criteria in Markov Soccer and demonstrate response-policy compression in 4-by-4 Connect Four, alongside smaller checks of the optimization procedure.

Critical strengths
  1. The paper identifies a useful distinction between preserving predictions and preserving strategic choices. A representation that describes play accurately under one policy need not retain the information needed to respond to another opponent. The examples in Section 1 and Appendix D make this issue concrete. More substantially, Theorem 4.1 shows that preserving optimal responses can require exponentially fewer abstract states than reconstructing the values of the same tasks, even with action-dependent transitions. This gives a clear reason to optimize the representation for strategic decisions directly.
  2. The proposed objective has a substantial mathematical foundation. The joint Bellman formulation connects the representation to both deployment quality and opponent-specific responses, and Theorem 5.1 provides an optimization certificate under an explicit structural condition. The appendices carefully distinguish approximation, statistical, and opponent-coverage errors. They also acknowledge restrictions such as the difference between a small physical interaction graph and a low-treewidth optimization problem. These qualifications make the theoretical contribution more convincing than a compression heuristic supported only by benchmark returns.
Critical weaknesses
  1. The strongest algorithmic guarantee and the largest experiment concern different procedures. Theorem 5.1 depends exponentially on the optimization graph's treewidth; Appendix E.8 shows that even the partition selectors can force this width to grow with the partition budget. The reported exact-optimization checks use only three to five states. Connect Four instead demonstrates compression of an already computed response-policy set, which is valuable but does not establish that the certified joint optimization scales. The Soccer experiment is described as optimizing the joint Bellman formulation, but Appendix J.2 does not report the solver procedure, runtime, or optimality certificate. Consequently, the empirical evidence supports response preservation more clearly than efficient discovery of the representation. This limits the practical claim rather than invalidating the theoretical results; identifying what was actually solved and at what cost would materially strengthen the paper.
Questions for authors
  1. Which solver produced the Soccer results in Table 6? From the existing runs, can you report whether these are globally certified solutions or feasible heuristic solutions, together with runtime and any available lower–upper bound?
  2. For Connect Four, which computations require full-state response solutions before compression, and what are the construction time and peak memory, compared with the reported deployment-storage saving? This would clarify whether the practical benefit is primarily policy storage or also reduced solution cost.
1 comment

Thank you very much for pushing us to clearly separate the upfront cost of finding a partition from the downstream cost of storing and deploying it. You are completely right about the scope of Theorem 5.1: its runtime scales exponentially with the supplied elimination width—which the partition selectors themselves can inflate—and our earlier small-game checks did not establish its scalability on either benchmark.

Soccer solver, runtime, and certificate. The original Table 6 referenced the joint Bellman objective; revised Section 7.2 and Appendices I.2–I.3 replace that experiment with a fully documented run. Rather than relying on Theorem 5.1, we precompute minimax values via Shapley iteration with HiGHS linear programs (4.054 s) and task values via discounted value iteration (1.024 s). Sequential cell assignment with small linear programs then produces a feasible 115-label partition in 7.003 s at the selected threshold (excluding exploratory threshold selection).

To rigorously assess how close this partition is to optimal on the specified rational instance, we certify 0.0003375141≤J128≤0.00632166760.0003375141 \leq J_{128} \leq 0.0063216676, where the budget counts playable labels and the absorbing label is kept separate. Integer residual checks certify the feasible tuple (upper bound), while 129 playable witness states covering all 8,256 pairs establish the lower bound. Taken together, this interval rules out zero loss while cleanly bracketing the global optimum. Note that the exactly-128-label held-out comparison in Table 5 uses the floating-point instance and is evaluated separately.

Connect Four preprocessing, memory, and deployment. Here, the practical benefit of our method is not avoiding full-state solves, but compressing their output into a substantially smaller, certified deployment representation (Section 7.1, Table 4, Appendix I.1). We first perform full-state minimax and best-response computations via integer backward induction, retaining all optimal actions at each state (including ties). Theorem 6.2 then finds the minimum partition compatible with those optimal-action sets under the legal-action and turn constraints.

For seed 1729, the upfront full-state work dominates the runtime—opponent construction (10.677 s), minimax computation (0.239 s), all 24 response tables (6.331 s), and independent original-game evaluation (6.014 s)—whereas partitioning and decoding itself takes just 0.101 s. Overall, a fresh end-to-end process completes in 29.302 s and peaks at 570.75 MiB of memory (excluding a separately timed 2.733 s for game enumeration). The payoff comes at deployment: the 3,975 labels require 695,791 bytes (including the state-to-label lookup table), or 39.86% of the uncompressed active-policy tables, with both totals excluding the common state index and precomputation workspace. An independent subset dynamic program further confirms that this partition size is minimal across all five pools.

Reviewer_t8aVOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper presents a method for state abstraction in competitive multiagent Markov games. Unlike previous absraction schemes such as traditional ones used in standard RL and equilibrium transfer, the state abstraction in this paper corresponds to "strategy completeness" which prioritizes state granularity that preserves the ability to find best response strategies to the opponents.

Critical strengths

The general idea of abstractions based on strategy completeness is a natural fit for competitive games. The results seem interesting and relevant.

Critical weaknesses

The paper suffers significantly from poor technical clarity. I could not understand even the most basic of definitions due to missing definitions and inconsistencies. As such, most of the paper was not accessible to me, despite having done work in this area. As such, I have very little confidence in the correctness of any result in the paper.

I've highlighted several specific points in "Questions for Authors"

Questions for authors

Intro example: what is \gamma and why is the return H/2, where h = 1/(1+\gamma)? Is gamma a discount factor? You haven’t even mentioned that it’s a discounted MDP nor defined anything yet, this is too unclear to be useful. Is this a continuing MDP? Are there transitions from s0 -> s1 and s1 -> s0? I’m already lost. .. on page 2, third paragraph of the paper. For this paragraph to make sense, I have to assume self-transition from the single abstract state to itself, a continuing MDP, and discounted returns.. none of which are mentioned (and I’m still not even sure if they are correct). The reader should not have to make assumptions to follow what should be a simple example on page 2.. this alienates the reader right away.

Sec 3: v is not defined … is it a vector of state values? r_i^{\pi, q} not defined (reward is a function of state and action, what does it mean to be superscripted by policies.. maybe an expected value? Why am I having to guess? P defined as a function from S \times A -> \Delta(S) but then used as a transition matrix later? (I assume so, since P^{\pi, q} also not defined) W_i^q not defined.. Is it a single value? Why is it capitalized if it’s not a matrix? Is [K] = {1, 2, …, K }? If so, it should be defined.

Definition 3.2 is especially cryptic. First, V_i^{\sigma, q} is not defined. Second, based on equation (2), the infinity norm implies that these must be vector quantities.. but the wording on page 3 “The unrestricted best-response value is the unique fixed point W_i^q” implies its a single value. Maybe it’s values at each state…? Then, it states “For any opponent q \in \cal{Q}”, so here q refers to an opponent but not one paragraph ago q was a a profile q \in \Sigma_{-i}”. Wait, the superscripts are also q here, which mean q must be the same q.. so why the inconsistency between \Sigma_{-i} and \cal{Q}?

I very vaguely understand equation (2) to be computing the distance between the best response values achieved in the abstract space compared to the unrestricted space.

Equation (3) is included but not used here, presumably later. It seems to be relating the compression potential as a function of K.

And we’re back to q \in \Sigma_{-i} in the paragraph after Def 3.2?!

1 comment

Thank you for reading our submission so carefully and for pinpointing exactly where our exposition fell short. We sincerely apologize for making you piece together basic definitions before you could evaluate our results. Your questions directly guided our revisions to the opening example and Section 3, which we clarify below.

The two-state example. The intended model is a discounted, infinite-horizon MDP with discount factor 0≤γ<10 \leq \gamma < 1 and effective horizon H=(1−γ)−1H = (1-\gamma)^{-1}. From either original state, every action transitions to s0s_0 or s1s_1 with equal probability (1/21/2 each), allowing transitions in both directions. Taking the safe action yields a reward of 1/21/2 at every step, giving a value of ∑t≥0γt/2=H/2\sum_{t \geq 0} \gamma^t / 2 = H/2 from either state. In contrast, choosing left at s0s_0 and right at s1s_1 yields a reward of 11 at every step, achieving an optimal value of HH. Any policy restricted to a single label earns an expected value of H/2H/2 under a uniform initial state distribution; consequently, the smaller of its two state values is at most H/2H/2. Since the safe policy achieves this bound at both states, the minimum worst-state loss is exactly H−H/2=H/2H - H/2 = H/2.

Values, policies, and transitions. Section 3 now explicitly constructs the response MDP prior to Definition 3.2, and Table 2 summarizes all notation for easy reference. For a fixed player ii, q∈Π−iq \in \Pi_{-i} denotes a stationary joint policy profile of the other players. Taking the expectation of the reward function and transition kernel over the opponents' actions yields the induced reward riq(s,ai)r_i^q(s,a_i) and transition kernel Piq(⋅∣s,ai)P_i^q(\cdot \mid s,a_i). Further taking the expectation over player ii's policy σ\sigma produces the reward vector riσ,qr_i^{\sigma,q} and the state-transition matrix Piσ,qP_i^{\sigma,q} (with one row per original state). Here, v∈RSv \in \mathbb{R}^{\mathcal{S}} represents a candidate state-value vector. Similarly, Viσ,qV_i^{\sigma,q} and WiqW_i^q are state-value vectors indexed by the original states: Viσ,qV_i^{\sigma,q} evaluates policy σ\sigma against qq, whereas WiqW_i^q gives the unrestricted best-response value against qq.

What Definition 3.2 measures. Your interpretation matches our intended comparison exactly. Both policies are evaluated in the original game, with the constraint that σ\sigma must play the same action distribution at all states sharing the same label in {1,…,K}\{1,\ldots,K\}. For a given task h=(i,q)h=(i,q), Eq. (1) selects a task-specific, label-constrained policy σ\sigma that minimizes the worst-case (maximum) loss across all initial states. For a fixed player ii, Q⊆Π−i\mathcal{Q} \subseteq \Pi_{-i} denotes the set of benchmark opponent profiles, and H\mathcal{H} collects these player-opponent tasks (i,q)(i,q) across all players. Finally, DKD_K represents the minimum worst-task response loss achievable using at most KK state labels, while JKJ_K in Eq. (2) extends this objective by also incorporating the deployment Nash gap under the same state partition.

Beyond these specific points, we also recognized other areas where the writing could be clearer. Guided by your overall feedback, we have thoroughly revised and polished the entire manuscript. If your schedule permits, we would greatly appreciate it if you could take a look at the revised version.

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

The paper proposes strategy completeness as the preservation target for state abstraction in Markov games, in place of predictive fidelity, value equivalence, or equilibrium transfer alone.

Critical strengths

The conceptual move seems useful and carefully executed. Prior offline-MARL work treats strategy completeness as an assumption on a pre-given policy class, and this paper turns it into a constructive abstraction objective with a quantitative defect.

Critical weaknesses
  1. The evaluation metric is the method’s own objective. Best-response loss is what the proposed method optimizes directly, while the baselines in Table 3 optimize other criteria. Winning at a matched budget is close to structural. The only result that tests opponents outside the optimized set is the held-out league evaluation in Section 7, and that one is small.

  2. The theory and the large experiments may not be about the same algorithm. Theorem 5.1 needs small treewidth, and Section 8 admits exact optimization breaks down when treewidth is large. Section 7 reports Algorithm 1 verified only on the 76 small games, with no certificate given for Soccer or Connect Four. If those headline numbers do not come from the certified algorithm, the two main contributions are not validating the same thing.

Questions for authors
  1. Which procedure actually produced the K=128 Soccer and K=22,057 Connect Four partitions?

  2. For Soccer, what is the best-response loss of the K=128 best-response partition against opponents drawn from outside the 32-profile benchmark, compared with the value-probe partition? This would distinguish "captures strategically relevant structure" from "overfits the declared pool."

1 comment

Thank you very much for suggesting the exact experiment needed to make the Soccer comparison truly informative. We fully agree that achieving low loss on the 32 opponents used to construct the partition leaves generalization to unseen opponents an open question. Accordingly, we have conducted the fixed-budget, held-out comparison you requested.

Which procedure produced the partitions? Our initial submission described the K=128K=128 Soccer result via its Bellman objective and the K=22,057K=22{,}057 Connect Four result as a refinement of full-state responses. Table 3 details the exact procedure for each:

  • Soccer: Sequential cell assignment using small linear programs produced 115 playable labels; for the held-out comparison, a deterministic splitting rule expanded this to exactly 128 labels.
  • Connect Four: Exact backward induction, followed by the matching and subset algorithm from Theorem 6.2, found the minimum zero-loss partition under the stated turn and legal-action constraints. For seed 1729, this yielded 3,975 labels for an equilibrium and 24 responses.

Note that the bounded-treewidth algorithm in Theorem 5.1 addresses a separate setting.

How does the partition perform outside the construction pool? We froze each partition before evaluating it on 48 unseen tasks drawn from three independently generated pools. All methods were given the same budget—128 playable labels plus one separate absorbing label—and used identical cellwise linear programs to fit a response to each new opponent. The finite value-probe baseline used eight fixed training-policy pairs. As shown in Table 5, our refined feasible partition achieved a mean held-out loss of 0.00394 (max 0.01303), compared with 0.19692 (mean max 0.32240) for value probes. All baseline figures are averaged over five clustering initializations, with the maximum taken across the 48 tasks within each run. The strongest baseline, action-signature clustering, achieved a mean loss of 0.01202 and a mean maximum loss of 0.04416, achieving lower loss in 84 of the 240 paired task-by-initialization comparisons (Appendix I.5).

Taken together, these results confirm that a frozen partition can effectively adapt to unseen opponents from this generator when paired with a newly fitted response. Finally, note that the measured losses reflect the performance of the fitted policies and thus serve as upper bounds on the best losses representable by their respective partitions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Comment to the Area Chair

We are deeply grateful to the Area Chair and all three reviewers for their thoughtful, constructive feedback on submission 57361. Together, the reviews highlighted three core technical questions—what loss our abstraction actually measures, which large-scale results are formally certified, and whether a partition generalizes to unseen opponents—along with important concerns about overall clarity. Our revision addresses each of these points directly:

  • Definitions (Reviewer t8aV). Section 3 now defines the induced response MDP and both original-state value vectors before introducing best-response loss. Eq. (1) makes clear that each opponent's response policy must apply across all initial states. To aid readability, Table 2 summarizes all notation in one place, and Figure 1 illustrates how response loss and the deployment Nash gap combine in the shared-partition objective.
  • Algorithms and evidence (Reviewers EZtp & 7Xqk). Table 3 now lists the exact solver and verification method used for every benchmark, while Theorem 5.1 keeps its bounded-treewidth scope. On 161,029-state Connect Four, a separate constant-sum algorithm certifies the exact minimum partition size across all five opponent pools under the stated constraints; we also now report full-state preprocessing, peak memory, and deployment storage separately. On the rational Soccer instance, independent checks certify both lower and upper bounds on J128J_{128} (with a finite optimality gap remaining). These fully documented runs replace the earlier historical results whose policies and solver logs were unavailable.
  • Held-out opponents (Reviewer 7Xqk). Our new held-out evaluation compares all methods under the same label budget and response-fitting procedure, freezing each partition before testing on 48 unseen tasks. Our partition achieved a mean held-out loss of 0.00394, compared to 0.19692 for finite value probes. The strongest baseline reached 0.01202 and outperformed our partition on a subset of individual tasks. Section 7.2 and Appendix I.5 provide the full task-level breakdown and explicitly scope our conclusions to opponents from the tested generator.
  • Writing and exposition (with special thanks to Reviewer t8aV). Beyond these targeted fixes, we are especially grateful to Reviewer t8aV for pinpointing where our writing fell short. Guided by their feedback, we rewrote and polished the entire manuscript to improve clarity, flow, and notational consistency.

In addition to these updates, we have substantially strengthened the paper's theoretical results—please see Theoretical Changes in the Revision (For the Area Chair and Reviewers) for a full summary. We sincerely appreciate the opportunity to revise our work and hope these improvements allow our theoretical claims, formal certificates, and empirical results to be evaluated clearly on their respective merits.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.