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

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, $H$, and $1/ϵ$ 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.