acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 , reset access, and certified oracles, outer iterations suffice for an -Nash pair with high probability, where is the feature dimension and the joint-action count. Counting primitive transitions adds a factor . 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.

Primary area:
reinforcement learning
Keywords:
low-rank Markov games, representation learning, equilibrium learning, multi-agent reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_c136OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies Nash certification in discounted zero-sum Markov games with unknown low-rank transitions. It learns one model and solves two confidence games, with payoffs r+b and r-b.

The conservative crossing pairs the lower game's maximizing policy with the upper game's minimizing policy. With exact planning, this pair minimizes a unilateral-deviation certificate. The certificate comes from a fixed two-sided envelope that holds uniformly over policies. The reverse crossing provides an exploration policy.

Critical strengths
  1. The two-sided confidence interface covers all stationary joint policies, including data-selected best responses. The resulting certificate concerns deviations in the true environment.
  2. Both auxiliary games retain a zero-sum structure and permit discounted Shapley planning. The analysis explicitly tracks estimation and planning errors.
  3. The interaction count includes roll-in transitions. It separates outer iterations, training samples, and planning calls. The natural alternative also receives a same-order guarantee.
  4. The experiments separate certificate tightness, true policy quality, and exploration cost. They report cases where alternatives perform better.
Critical weaknesses
  1. The comparison with related work [Strategically Efficient Exploration in Competitive Multi-agent Reinforcement Learning]. Please add a citation and compare certificate properties, width arguments, and statistical guarantees.
  2. The new connections in the statistical argument could be explained more intuitively. The paper and Appendix A acknowledge the tools from [REP-UCB, Representation Learning for Online and Offline RL in Low-rank MDPs] and [Representation Learning for General-sum Low-rank Markov Games]. A short account could identify reused tools, adaptations, and their connection to the crossed-policy certificate. This would help readers assess the statistical contribution.
Questions for authors

none

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

This paper studies two-player zero-sum discounted Markov games under the additional assumption of unknown low-rank transitions, i.e., the environment's transition kernel can be represented by two low-dimensional factors. The paper assumes both factors are unknown and must be learned from data.

The problem the paper addresses is interesting. A Nash equilibrium computed in a learned model may no longer be close to a Nash equilibrium in the true environment. The goal is to find a pair of policies and, based on the available data, provide a certificate, i.e., an upper bound on the true Nash gap.

The authors propose DRep-ZS, which solves two confidence games on the same learned model: an upper game with reward (r+b)(r+b) and a lower game with reward (r−b)(r-b), where bb is a bonus reflecting model uncertainty. The algorithm pairs the maximizing policy from the lower game with the minimizing policy from the upper game, called the conservative crossing, to form the candidate policies. It pairs the maximizing policy from the upper game with the minimizing policy from the lower game, called the reverse crossing, for subsequent exploration and the corresponding data collection.

To analyze these pairings, the paper defines a strategic-confidence envelope: for every stationary joint policy, its value in the true environment is bounded on both sides by the values obtained in the learned model using r−br-b and r+br+b (up to an additional slack of ζ\zeta). With the learned model and the uncertainty bonus fixed, the paper computes an upper bound on the true Nash gap for every pair of policies, and the conservative crossing minimizes this upper bound. The paper further proves that the reverse crossing provides the exploration needed to shrink the certificate further. Finally, it gives a sample complexity guarantee under assumptions such as finite-class realizability.

Critical strengths

The research problem is valuable. Finding a Nash equilibrium in a learned model does not mean the policies are good enough in the true environment. The paper offers not only an algorithmic design but also a sample complexity guarantee under fairly standard theoretical assumptions such as finite-class realizability.

Critical weaknesses

Many of the experiments mainly use small-scale, synthetic games. For example, the experiments in Appendix H.5 have only 64 or 256 states, with a low-rank dimension of 4. Larger-scale experiments would better demonstrate the method's effectiveness.

Questions for authors

The paper mainly shows that its method makes the envelope certificate smaller. Can you show, through experiments in larger and more complex settings, that the policies actually obtained are better?

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

This paper studies certification of approximate Nash equilibria in discounted zero-sum Markov games with unknown low-rank transitions. It learns a transition model and constructs two confidence games using rewards r+br+b and r−br-b. The lower-game maximizing policy paired with the upper-game minimizing policy is used to certify a candidate; the reverse crossing is used to guide exploration. Under a policy-uniform two-sided value envelope and exact planning, the paper proves that the conservative crossing minimizes a particular unilateral-deviation certificate induced by that fixed envelope. It also gives an interaction upper bound under finite-class realizability, known normalized rewards, reset access, and certified estimation and planning oracles, with controlled estimation and planning errors. Experiments compare certificates on shared data and exploration policies under common stopping rules. The supplementary package includes experiment code, seeds, saved data and checkpoints, analysis scripts, and validation checks.

Critical strengths
  1. A clear connection between certification and exploration. The paper uses two confidence games on one learned model for two distinct purposes: one crossing minimizes a specified deviation certificate, while the reverse crossing supplies an exploration rule. The analysis also accounts for controlled estimation and planning errors.

  2. Detailed and auditable experimental materials. The supplementary package includes configurations, seeds, code, saved results, analysis scripts, and checks against selected paper values. I ran the provided result-verification script; it passed its checks of task counts, frozen constants, coverage audits, and representative reported values. The package also retains reported confidence failures rather than omitting them. This makes the experimental claims easier to inspect and reproduce.

Critical weaknesses
  1. The main guarantee depends on a restrictive access and computation model. The sample-complexity result assumes a finite transition-model class containing the truth, known normalized rewards, reset access, and certified approximate-MLE and Shapley-planning oracles. The confidence analysis also uses paired uniform-action probes. These assumptions are central to the guarantee. The paper notes that fitting and planning may still scale with the state space, that the action and discount dependencies are not known to be minimax optimal, and that the finite-class experiments do not test large implicit model classes (Sections 2, 5, and 7; Appendix B). The artifact makes the finite synthetic experiments auditable, but does not address how to obtain the required estimation and planning guarantees in large-scale settings. Thus the theorem is a useful conditional interaction bound, while its applicability to common function-approximation settings remains unclear.

  2. The practical value of optimizing the fixed-envelope certificate is not established by the experiments. The theorem concerns a specific certificate induced by a fixed two-sided envelope; it does not imply that the selected policy has a smaller true Nash gap or that exploration is more efficient. In the shared-data experiment (Table 1), calibrated crossing certificates improve over nominal-envelope certificates by 2.4%–6.9%, but their medians remain 0.408–0.653, well above the 0.05 threshold. The nominal policies have final true gaps below 10−710^{-7}, and the likelihood-set certificates are zero in all 30 final runs. Under the proof-profile constants, all reported envelope bounds exceed one. In the delayed-conflict experiment (Table 2), bonus-MDP and uniform exploration reach the 0.05 threshold faster than reverse crossing in all six settings; for L=2,a=0.25L=2,a=0.25, the respective mean transition counts are 629, 834, and 3,112. These exploration results use calibrated likelihood-set stopping rather than the theorem’s proof-profile stopping, so they do not contradict the theorem. However, they leave open whether the proposed certificate and exploration rule provide a practical advantage over simpler alternatives. The supplementary package allows these results to be checked, but does not change this empirical conclusion.

Questions for authors
  1. Can the authors provide an example using the proof-covered confidence parameters in which the certificate reaches a practically meaningful threshold, ideally for a larger or implicit model class? If not, could they clarify whether the current guarantee should be viewed primarily as an interaction-complexity result rather than a practical stopping rule?

  2. Are there additional assumptions on the representation or data distribution under which the fixed-envelope certificate can be related to the true Nash gap or to the likelihood-set certificate? This would help establish when minimizing this particular certificate is useful beyond the stated fixed-envelope comparison.

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

The paper considers learning approximate Nash equilibria in discounted two-player zero-sum Markov games where the transition kernel is low-rank, P⋆(s′∣s,a,b)=⟨ϕ⋆(s,a,b),μ⋆(s′)⟩P^\star(s'\mid s,a,b)=\langle\phi^\star(s,a,b),\mu^\star(s')\rangle, and both factors are unknown. The learner is given a finite realizable model class M\mathcal M, reset access to d0d_0, known rewards, an approximate MLE oracle and a Shapley planning oracle. The goal is to output a policy pair together with an observable upper bound on its true Nash gap.

In Section 3, the authors present the main idea. At round nn, given a fitted model P^n\widehat P_n and an elliptical bonus bnb_n in the learned features, they solve two zero-sum games on the same model: an upper game with payoff r+bnr+b_n (saddle pair (πn+,νn+)(\pi^+_n,\nu^+_n), value vˉn\bar v_n) and a lower game with payoff r−bnr-b_n (saddle pair (πn−,νn−)(\pi^-_n,\nu^-_n), value v‾n\underline v_n). The two solutions are then crossed:

  • the conservative crossing (πn−,νn+)(\pi^-_n,\nu^+_n) is the output candidate. If the model and the bonus form a two-sided envelope that holds for every stationary joint policy, then Gap(πn−,νn+)≤vˉn−v‾n+2ζn+2ηn\mathrm{Gap}(\pi^-_n,\nu^+_n)\le \bar v_n-\underline v_n+2\zeta_n+2\eta_n (Lemma 5). Prop. 6 shows that this pair minimizes the deviation certificate induced by the envelope.
  • the reverse crossing (πn+,νn−)(\pi^+_n,\nu^-_n) is the exploration policy. Its bonus occupancy upper bounds the width vˉn−v‾n\bar v_n-\underline v_n (Lemma 7).

In Sections 4 and 5, the authors present the algorithm (DREP-ZS) and its analysis. Every round, a geometric roll-in under the previous exploration pair samples a state and two uniform-action probe tuples are collected. The analysis follows REP-UCB [1]: a confidence event that holds for all stationary joint policies (Theorem 8), one-step-back inequalities and an elliptical potential in the fixed true features ϕ⋆\phi^\star. The main result (Corollary 10) is that N=O~(d2J(J+d2)log⁡(∣M∣/δ)(1−γ)4ϵ2)N=\widetilde O\left(\frac{d^2J(J+d^2)\log(|\mathcal M|/\delta)}{(1-\gamma)^4\epsilon^2}\right) outer iterations suffice for an ϵ\epsilon-Nash pair, where J=ABJ=AB, with one more (1−γ)−1(1-\gamma)^{-1} factor for primitive transitions. The authors also analyze a comparator, i.e., nominal (CE) equilibrium output with joint-action bonus-MDP exploration, and show that it attains the same order (Theorem 11).

In Section 6, the authors run experiments on enumerated model classes (∣M∣≤32|\mathcal M|\le 32). They compare the certificates on shared data, and the exploration rules under a common output and stopping rule. In the appendix, the reduction is extended to stationary CCE in general-sum games assuming a (PPAD-hard) oracle.

Critical strengths
  • Solving two zero-sum games instead of one general-sum game is a nice observation. Making every player optimistic for itself, as in [2], gives payoffs (r+b,−r+b)(r+b,-r+b), which is a general-sum game where computing a stationary Nash equilibrium is PPAD-hard in the discounted setting. Splitting it into two Shapley problems avoids this, and both the certificate and the exploration rule come from the same two solutions.
  • I went through Lemma 5, Prop. 6 and Lemma 7, and the role of the shifted second tuple in the one-step-back argument, and I believe they are correct. Estimation and planning errors are tracked explicitly and the interaction count includes the roll-ins.
  • The confidence event holds simultaneously for every stationary joint policy. This is what one needs for a Nash certificate, since the best responses depend on the learned model.
  • The authors are very candid about their empirical results. Negative results and false certifications are kept, and the authors state themselves that the proof constants are vacuous. This is rarer than it should be.
Critical weaknesses
  • The conceptual novelty is limited. The conservative crossing is the standard pessimistic output in offline zero-sum Markov games, i.e., the max player optimizes the lower bound and the min player optimizes the upper bound (e.g., PMVI [3], see also [4,5]). The reverse crossing is optimistic self-play where each player is optimistic for itself [6,7], and bounding the width by the bonus along the optimistic pair is the usual step. The statistical part is REP-UCB [1] with a second probe tuple. So, the contribution is putting these pieces together in the discounted stationary setting with an unknown low-rank kernel. The related work does not connect the conservative crossing to offline pessimism and [3] is not cited. I think this should be made explicit and the novelty claims should be tuned.

  • Prop. 6 adds little in my opinion. Cn(π,ν)C_n(\pi,\nu) separates into a term that depends only on ν\nu and a term that depends only on π\pi, so its minimizer is the pair of saddle policies directly from the definition. Moreover, the minimality is relative to one particular certificate. Minimizing it can increase the true gap (in the one-state example of Section 3.1, CE has gap 0 and the crossing has gap 0.00975), the likelihood-set certificate of Appendix F.2 is much tighter in every experiment, and the strict-separation construction of Appendix E.3 needs a redundant representation and rare histories. Since Theorem 11 gives CE + bonus MDP the same order of interactions, there is no separation in sample complexity either. It is not clear to me what minimizing this certificate buys.

  • The rate does not say much about the game structure. With J=ABJ=AB, the factor d2J(J+d2)d^2J(J+d^2) means an A2B2A^2B^2 dependence instead of A+BA+B. The horizon dependence is (1−γ)−4(1-\gamma)^{-4} outer iterations and (1−γ)−5(1-\gamma)^{-5} transitions with rewards in [0,1−γ][0,1-\gamma], which becomes (1−γ)−6(1-\gamma)^{-6} and (1−γ)−7(1-\gamma)^{-7} for rewards in [0,1][0,1]. The only lower bound transfers MDP results (Prop. 15). The rate is roughly what one gets by substituting JJ in a REP-UCB-style analysis, and it does not show that the two-game structure matters statistically.

  • The experiments do not support the practical use of the method, and the paper says so itself:

  • The experiments do not test representation learning. The model classes have 8-32 enumerated kernels and the MLE is exact by enumeration, so this is model selection among a few candidates. The "unknown low-rank" part of the title is never tested at scale and there is no instantiation with function approximation. Further, the shared-data comparison uses only trajectories collected by DREP-ZS (Appendix H.5), so the comparator is never evaluated on the data it would collect itself.

  • The assumptions are restrictive: a finite realizable class, resets to d0d_0, known rewards, uniform paired probes and an MLE oracle that is intractable in general. These are standard in this line of work, but Prop. 21 that relaxes finiteness has no concrete instantiation.


[1] Uehara, M., Zhang, X. and Sun, W., 2022. Representation learning for online and offline RL in low-rank MDPs. ICLR 2022.

[2] Ni, C., Song, Y., Zhang, X., Ding, Z., Jin, C. and Wang, M., 2023. Representation learning for general-sum low-rank Markov games. ICLR 2023.

[3] Zhong, H., Xiong, W., Tan, J., Wang, L., Zhang, T., Wang, Z. and Yang, Z., 2022. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. ICML 2022.

[4] Cui, Q. and Du, S.S., 2022. When are offline two-player zero-sum Markov games solvable? NeurIPS 2022.

[5] Yan, Y., Li, G., Chen, Y. and Fan, J., 2024. Model-based reinforcement learning for offline zero-sum Markov games. Operations Research.

[6] Bai, Y. and Jin, C., 2020. Provable self-play algorithms for competitive reinforcement learning. ICML 2020.

[7] Liu, Q., Yu, T., Bai, Y. and Jin, C., 2021. A sharp analysis of model-based reinforcement learning with self-play. ICML 2021.

Questions for authors
  • How does the conservative crossing differ from the pessimistic output of PMVI [3], and the reverse crossing from optimistic self-play? What is new beyond combining them in this setting?

  • Is there a class of games where crossing-based exploration needs strictly fewer interactions than CE + bonus MDP, or than uniform exploration? If not, what is the case for DREP-ZS over CE + bonus MDP with likelihood-set certification and a split failure budget as in Corollary 28?

  • Where does each factor of JJ come from? Do you think that per-player probes that only cover unilateral deviations could give an A+BA+B dependence?

  • The exploration comparisons use CE output with likelihood-set stopping. What happens with the native envelope certificate as the stopping rule, which is the setting your theory covers? Does reverse crossing beat bonus MDP there?

  • Can you repeat the shared-data comparison on trajectories collected by CE + bonus MDP?

  • Which parameter profile does the 300-seed policy-uniform audit use? If it is the calibrated one, how should the failing seed be read for a method whose main selling point is certification?

  • Given the PPAD-hard oracle and that the experiments only consider a team-potential family, what does the CCE extension (Appendix G) add to the paper?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Dear Reviewers and Area Chair,

Thank you again for your careful reviews and constructive feedback.

As the discussion period is approaching its end, we would like to kindly follow up on our rebuttal. We have provided detailed responses to the reviewers' concerns and hope that our clarifications have addressed the main questions.

We would greatly appreciate any further feedback, particularly if there are remaining concerns that we could clarify before the discussion closes.

Thank you for your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.