acceptodds
Under review as a conference paper at ICLR 2027

Calibrating Policy Covers for Nash Equilibrium Learning

Abstract

A policy cover can reach every important state while its uniform mixture provides poor data for equilibrium learning. We study how to calibrate a finite cover in zero-sum Block games without identifying the latent-state decoder. Under common emissions and a finite evaluable decoder class containing the true decoder, constraints on all candidate-decoder events are equivalent at the population level to latent coverage constraints. Incorrect candidates therefore do not require a more conservative population mixture. Every library admits a coverage factor R\leq\min \ {M,S\}, where is its size and the latent state count. We estimate the event constraints from shared rollouts and implement them by linear programming. Under finite-class fitting conditions, the resulting Nash guarantee replaces by in the sufficient fitting budget, while charging cover construction and calibration. A hidden-coordinate class gives a polynomial-time implementation. In a three-stage family with an unknown entrance, episodes match an adaptive lower bound up to logarithms, whereas uniform sampling of the same library requires . Fixed-budget experiments distinguish distribution quality from the costs and best-response errors that determine downstream performance.

Primary area:
reinforcement learning
Keywords:
zero-sum Markov games, low-rank Markov games, unilateral policy coverage, representation learning, Nash equilibrium computation

Reviews

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

This paper studies how to turn a policy cover into a sampling distribution for learning Nash equilibria in episodic zero sum Block Markov games. The main observation is that, under common emissions and inclusion of the true decoder, constraints defined through observable decoder events are equivalent to constraints on latent state coverage. This allows the learner to calibrate mixture weights without first identifying the decoder.

The resulting coverage factor satisfies R≤min⁡{M,S}R\leq\min\{M,S\}, where MM is the library size and SS is the number of latent states. The authors provide a finite sample calibration procedure and connect its coverage guarantee to the Nash gap through Bellman errors along dynamic best responses. They also give a computable hidden coordinate example and an entrance construction illustrating the benefit of adaptive sampling. The experiments compare coverage and Nash performance while accounting for collection, calibration, and fitting costs.

Critical strengths
  1. The connection between observable events and latent coverage is clean and useful. Lemma 1 explains why adding incorrect candidate decoders does not worsen the population coverage requirement when the true decoder is included. This addresses a concrete obstacle to choosing useful mixture weights under an unknown representation. The calibration analysis then turns this observation into a statistical guarantee while accounting for the cost of estimating the constraints.

  2. The paper carefully distinguishes improved coverage from improved equilibrium performance. Theorem 3 follows Bellman errors along the actual dynamic best responses, which are directly relevant to exploitability. The sample accounting also retains the cost of constructing the original cover. The experimental comparisons are appropriately controlled and openly report cases where better coverage fails to improve the final Nash gap. These distinctions make the claims more credible and their limitations easier to understand.

Critical weaknesses
  1. The improvement is conditional on obtaining a suitable policy cover. The dependence on library size improves in the downstream fitting term, but the full construction cost remains and can dominate the total budget. The results therefore provide a useful modular improvement without establishing a better leading rate for general equilibrium learning under comparable access assumptions. The entrance example gives a sharp separation from uniform sampling, although a simple search based on observed returns achieves the same sample order. This limits the breadth of the algorithmic advance.

  2. The empirical advantage over reasonable alternatives is limited. In the main learned cover experiment, at the larger budget and 64 calibration episodes per member, the LP achieves a mean Nash gap of 0.01013 compared with 0.01123 for equal PCE. The paired confidence interval includes zero, while uniform action collection achieves 0.00866 under the complete budget. Greedy reweighting and the observable L1L_1 comparator also remain competitive. Although the paper discusses these results fairly, they leave limited evidence that the proposed pipeline offers a consistent practical benefit beyond the entrance examples.

Questions for authors
  1. What finite sample guarantee can be obtained for the observable L1L_1 objective in Proposition 19 using the same decoder access and calibration observations? A comparison of the resulting calibration and fitting budgets would help clarify the statistical contribution of the domination constraints beyond the choice of optimizer.

  2. Can you quantify a regime in which calibration produces a substantial reduction in the complete episode budget when the cover is constructed by the stated provider? Equation (8) identifies when the fitting saving exceeds calibration overhead, but the size of that saving relative to the full cover construction cost is less clear.

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

This paper proposes a method for calibrating policy covers to improve Nash equilibrium learning in two-player zero-sum Block Markov games without identifying the latent-state decoder. Using observable-event constraints and linear programming, the authors establish a coverage factor R≤min⁡{M,S}R \leq \min\{M,S\} and improve the downstream fitting sample complexity by replacing the dependence on cover size MM with RR. They also provide an adaptive sampling separation, a polynomial-time implementation for a structured model class, and synthetic experiments evaluating Nash gaps and sample efficiency.

Critical strengths

The paper provides an interesting approach to improving exploration distributions without identifying the latent-state decoder. The equivalence between observable-event and latent-state coverage constraints is a useful theoretical insight.

Critical weaknesses
  1. The paper establishes an improvement in the sufficient post-cover fitting complexity by replacing the library-size dependence M with the simultaneous coverage factor R. However, the overall exploration complexity retains the full policy-cover construction cost, which can dominate the total sample complexity.

  2. Although the learned mixture improves worst-case latent-state coverage, this does not consistently translate into better equilibrium learning. In the coupled PCE experiments, the proposed LP does not demonstrate a statistically significant improvement over uniform PCE mixing, and simpler alternatives sometimes achieve lower Nash gaps at the same total episode budget.

Questions for authors

Can the authors identify a class of instances in which LP calibration provably improves sample complexity over other adaptive sampling procedures, rather than only over independent uniform mixing?

Reviewer_9QJzOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies how to allocate samples across an existing policy cover when learning a Nash equilibrium in zero-sum Block Markov games. This paper shows that, under common emissions and a suitable finite decoder class, observable coverage constraints are equivalent to constraints on latent-state coverage. This allows the sampling mixture to be calibrated without identifying the true decoder. The resulting guarantee replaces dependence on library size with a potentially smaller coverage factor in the downstream fitting budget, while accounting for cover construction and calibration costs. Synthetic experiments also supports the benefits and costs of this sampling adaptation.

Critical strengths
  1. The equivalence between observable and latent coverage is a useful and helpful structural result. It explains why including incorrect candidate decoders need not force a worse sampling mixture, and makes calibration possible without first recovering the true decoder.

  2. The paper connects improved sample allocation to a concrete Nash-learning guarantee. It shows how a smaller coverage factor can reduce downstream fitting costs, and it keeps the costs of obtaining the cover and calibrating the mixture in the accounting, which is interesting.

Critical weaknesses

The experiments show useful sampling adaptation, but provide less convincing evidence that the proposed calibration pipeline improves performance at a matched total budget. It would be better to conduct more experiments to support theoretical results.

Questions for authors
  1. It would be better to provide a comparison table with related works (a detailed Table 1, in the main content instead of Appendix).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Dear Reviewers and Area Chair,

Thank you for your thoughtful reviews and constructive feedback.

As the discussion period is approaching its end, we would like to kindly follow up on our rebuttal. We hope our responses have addressed the main concerns raised in the reviews.

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

Thank you again 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.