- 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
- 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.
- 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
- 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
- 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?
- 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.
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.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.