STRATA: Equilibrium-Relative State Abstractions for Markov Games

Which state abstractions of a Markov game preserve its equilibria? We answer with a hierarchy of three strategic-distortion criteria for $N$-player games: global model similarity (D0), model similarity under unilateral deviations from the played profile (D1), and best-response-value similarity (D2), and prove that at every level an approximate equilibrium of the abstract game lifts to an approximate Nash equilibrium of the ground game (at the model levels also coarse-correlated equilibria, with distortions under the device's conditional laws). The levels nest, and existing multi-agent abstraction criteria are profile-independent: the restriction D1 and D2 relax. We show where that restriction costs: in a constructed family where the played mixture cancels a variable's effect on the payoffs of played actions, every criterion that compares rewards or minimax values joint action by joint action (on all joint actions, the undominated ones or the minimax supports) keeps all of the variable's values, while D1 and D2 keep none; criteria that compare states through minimax strategies are not covered. Where discarding dominated actions suffices, it compresses more: on our two Markov Soccer games the prior value criterion restricted to undominated actions, a baseline we add, is lossless with fewer states than D2 (328 and 772). Because D1 and D2 are defined relative to the equilibrium being played, learning them is a fixed-point problem; we give a refinement loop that splits only the states that deviations from the current equilibrium tell apart, terminates by construction, and returns a joint (abstraction, equilibrium) fixed point at which the tolerance holds for the equilibrium actually played. Solving exactlyagainst ground truth: on Markov Soccer, D0cannot compress, D1 rediscovers the hand-designed abstraction, and D2 matches it with 15% fewer states, while the prior model criterion cannot compress eithern needs more states (805 vs. 649) at a$7.7\times$ larger duality gap; on the prior criterion's own benchmark, D2 is lossless (zero duality gap at every state) with fewer states (582 vs. 612), an of nine pitch sizes and reverses on four. One abstraction refined on three games, with $1.65\times$ the states of the hand design, matches or improves on it on every held-out game.