One Model, Two Games: Certifying Nash Equilibria in Discounted Zero-Sum Low-Rank Markov Games

An equilibrium of a learned game can admit profitable deviations in the true environment. We study how to certify approximate Nash equilibria in discounted zero-sum Markov games with unknown low-rank transitions. Our method solves two confidence games on one learned model. Under a policy-uniform two-sided value envelope and exact planning, pairing the lower game's maximizing policy with the upper game's minimizing policy minimizes the induced unilateral-deviation certificate. The reverse pairing controls its width and supplies sufficient exploration using the same solutions. A natural alternative combines a nominal equilibrium with a joint-action MDP maximizing bonus occupancy. We prove interaction upper bounds of the same order for both methods, while their fixed-envelope certificates can be strictly separated. Under finite-class realizability, known rewards in $[0,1-\gamma ]$, reset access, and certified oracles, $\tilde{O}(d^{2}J(J+d^2)/((1-\gamma {)}^4{ϵ}^2))$ outer iterations suffice for an $ϵ$-Nash pair with high probability, where $d$ is the feature dimension and $J$ the joint-action count. Counting primitive transitions adds a factor $(1-\gamma {)}^{-1}$. The guarantee allows controlled estimation and planning errors despite changing learned features. Experiments distinguish certificate tightness from policy quality and exploration cost: crossing gives tighter envelope certificates on shared data, whereas bonus and uniform exploration are faster on delayed-conflict games. The sufficient confidence parameters remain conservative at these budgets.