acceptodds
Under review as a conference paper at ICLR 2027

No Target-Free Equilibrium Learning: Adaptive Phase Transitions in Zero-Sum Games

Abstract

Learning a game has no target-independent statistical complexity. Under the same noisy payoff observations, values and low-exploitability decisions may be accurately learned while point equilibrium recovery remains statistically unresolved. We first prove a dimension-uniform accuracy–sensitivity obstruction for every globally Lipschitz single-valued strategy rule, together with an exact two-by-two separation of value, decision, branch, and point risks. We then introduce TARGET, an implementable procedure that discovers an unknown simple equilibrium interface, estimates its information normal and side targets, and adaptively allocates samples. Uniformly over a fixed quantitative class and compact phase ranges, TARGET recovers the active chart, converges to the oracle Gaussian score, and attains the known-geometry minimax interface-side risk and the least-favorable-pair point and confidence benchmarks. Matching lower bounds show that geometric oracle information has zero first-order value, while an explicit competing-interface family identifies the sharp adaptation boundary. Finally, we derive the exact price of sampling before the downstream equilibrium target is known: one experiment is simultaneously oracle optimal for several targets if and only if their normalized information profiles coincide. A certified generator and a fixed-seed study of 320 heterogeneous games verify implementation and exhibit dimension-free collapse onto the predicted information-normal curves.

Primary area:
learning theory
Keywords:
zero-sum games, equilibrium learning, equilibrium selection, equilibrium interfaces, adaptive experimental design, minimax inference, noisy payoff queries, statistical learning theory

Reviews

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

The content of the paper is built around three claims on learnability of various properties related to Nash equilibrium in zero-sum matrix games.

The first claim says that game value and exploitability is stable w.r.t. small changes of the matrix entries whereas this is not true for the equilibrium strategies. Consequently, one cannot have a Lipschitz continuous function from the space of m×km\times k-matrices to the strategy space.

The second claim deals with matrix games where the matrix entries are noisy and one can only sample them. The paper assumes that they are i.i.d. and follow normal distribution. Given a matrix game, it might be close in the matrix space to the boundary where the equilibrium strategies suddenly change. So the question is whether a learning algorithm can recognize on which size of the boundary the true matrix is. The paper provides such an algorithm (called TARGET) that works for an extremely complicated class of games so that its definition is only sketched in the main text.

The last claim deals with the situation where we must sample first without knowing in advance which equilibrium-related property is the requested output. The paper quantifies the ratio how much the expected error change in comparison with the situation where we know the property in advance.

Critical strengths

I find the topic quite interesting and worth of pursuing. The paper brings a finer classification of what is meant by equilibrium learnability. It usually assumes outputting low-exploitable pair of strategies whereas this paper investigates finer questions we might have regarding the equilibrium of a noisy game.

Critical weaknesses

I have several concerns regarding the presentation. It is exceptionally long (125 pages) for a conference paper. So it is hard to compress the main message into the main 9-pages text. Still, I think that could be done in a human readable fashion. However, the paper fails completely to communicate its results. If the text is meant for a human researcher, it must provide a certain level of guidance supporting the understanding of presented results. This is not the case for the paper under review. It is structured as a machine-like sequence of facts without any insights. Most of the crucial definitions are postponed to the appendix, still the theorems in the main text use them without any explanation. This makes comprehension of the main text impossible as one has to always inspect the appendix. What is the point to state formally a theorem if it uses undefined symbols without any intuitive explanation? The presentation issue is well demonstrated by the last concluding section. It does not provide a reasonable scientific conclusion. It looks more like a summary log. For instance, the paragraph "Proof and implementation map" starts with the sentence "The logical chain is auditable." I guess that a human researcher would never write something like that.

My second concern is applicability of Theorem 3.1 supporting the second paper's claim. As I wrote above the class of games where Theorem 3.1 applies is quite complicated. The theorem assumes known numerical margins for an unknown interface, a complete finite atlas, independent Gaussian measurements of chosen payoff entries, and a game lying close to the boundary. It naturally rises the question of its applicability. How could we obtain or certify the class margins and atlas for an unknown game, and what is the computational cost of doing so w.r.t. the matrix size?

Questions for authors

I have no question.

Reviewer_GLXoOpenReview ↗
Rating
1(−1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies statistical equilibrium learning in finite two-player zero-sum matrix games from noisy payoff samples. It advances three claims. First, stable decisions do not imply stable strategies: for every globally Lipschitz single-valued strategy rule, a dimension-uniform accuracy–sensitivity obstruction holds, with an exact 2×2 separation of value, decision, branch, and point risks. Second, unknown simple interfaces are adaptively learnable at oracle risk: the TARGET procedure selects a chart from a finite regular-kernel atlas, estimates game-derived side targets and the information normal, allocates samples, and attains declared known-geometry minimax benchmarks, with matching lower bounds and a sharp competing-interface boundary. Third, there is no target-free experiment: if the downstream target is revealed after sampling, the exact price Γ of target ignorance is a convex minimax quantity, and one design is simultaneously oracle optimal for all targets if and only if normalized information profiles coincide. A certified support-splitting generator and a 320-game fixed-seed study accompany the theory.

Critical strengths
  1. The dimension-uniform accuracy–sensitivity obstruction is a clean quantitative result, and the exact 2×2 separation of value, decision, branch, and point risks is a useful conceptual contribution.

  2. The finite regular-kernel atlas and five-stage TARGET procedure are specified precisely, with uniform guarantees over a declared class, matching lower bounds, and an explicit competing-interface boundary. The target-ignorance duality is also exact and interpretable: Γ, the compatibility condition Γ=1, and the disjoint-support value Γ=R give a sharp finite-dimensional theory, and the post-hoc protocol is a genuinely useful framing.

Critical weaknesses
  1. The writing of the paper is extremely poor. It fails to provide any research background or motivation, nor does it discuss any relevant prior work. Furthermore, the paper fails to provide clear definitions of the research problem, the setting, and the necessary notation before introducing the theoretical results. Due to the poor writing, the entire text is difficult to read; therefore, my subsequent review may be flawed.

  2. The title and Claim 3 are contradicted by the paper's own Theorem 5.1. Equation (5.6) states Γ=1 if and only if the normalized information profiles coincide. As written the title is false on a nonempty, explicitly characterized set of instances, and it should be restated around the price Γ: a target-free experiment exists precisely when the profiles coincide, and its exact price is Γ.

  3. The paper does not separate its new content from the classical results that contain its two main technical claims. For Claim 1, "no continuous exact selector" is the classical failure of lower hemicontinuity of the Nash correspondence, with the 2×2 indifference path as the textbook witness [1, 2], and the nonregular point target is precisely the setting of the impossibility theorem for nondifferentiable functionals [3], and "zero first-order value" is the standard language of adaptive estimation [4]. For Claim 3, Theorem 5.1's Γ is, after the standard normalization, the reciprocal of the classical guaranteed-efficiency criterion ([5] §11; [6] for R=2; [7] for the maximin/Bayes duality), the O(N^{-1}) rounding in eq. (5.7) is a special case of [5] and [8], and Appendix S.6's "closed-form instance" of maxi–min design contradicts Appendix L.7's listing of the dual as a retained claim. Appendix H's "simultaneously honest" coverage and projected region closely track the partial-identification set-inference literature [9–11] without citing it, multiple-equilibrium econometrics [12] is absent, and the one genuinely new object is the game-derived profiles and the post-hoc target protocol.

  4. "Adaptive Phase Transitions" is never defined.

  5. The empirical study contains no external learning-algorithm baseline, and its only non-oracle comparison is confounded. The paper calls TARGET an "implementable procedure" and Claim 2 claims design, side, point, and confidence benchmarks, but the non-oracle study reports only chart recovery, a design-variance ratio of 1.0154, and a side-risk RMSE of 0.0354; the point-risk and confidence panels are oracle Monte Carlo. Same-model, budget-matched baselines are already cited in the paper and are not run: the LP-based two-stage method of Remark B.8, the instance-dependent n×2 method cited there, and sampled optimistic MWU/OMD or a sampled CFR variant.

  6. The 320-game study is a verification of the paper's own generator, not an independent test. All 320 games come from one support-splitting construction, and Theorem 4.1 already proves the universal collapse for this family. The word "heterogeneous" therefore overstates the structural diversity, and the study cannot test external validity beyond the proved domain. The paper should either add an independent generator or relabel the study as a verification of the proved law.

[1] E. van Damme. Stability and Perfection of Nash Equilibria.

[2] E. Kohlberg and J.-F. Mertens. On the Strategic Stability of Equilibria.

[3] K. Hirano and J. R. Porter. Impossibility Results for Nondifferentiable Functionals.

[4] P. J. Bickel. On Adaptive Estimation.

[5] F. Pukelsheim. Optimal Design of Experiments.

[6] L. Imhof and W.-K. Wong. A Graphical Method for Finding Maximin Efficiency Designs.

[7] C. Tommasi, J. M. Rodríguez-Díaz, and J. López-Fidalgo. An equivalence theorem for design optimality with respect to a multi-objective criterion.

[8] F. Pukelsheim and S. Rieder. Efficient rounding of approximate designs.

[9] G. W. Imbens and C. F. Manski. Confidence Intervals for Partially Identified Parameters.

[10] V. Chernozhukov, H. Hong, and E. Tamer. Estimation and Confidence Regions for Parameter Sets in Econometric Models.

[11] J. P. Romano and A. M. Shaikh. Inference for the Identified Set in Partially Identified Econometric Models.

[12] E. Tamer. Incomplete Simultaneous Discrete Response Model with Multiple Equilibria.

Questions for authors
  1. Do you claim that no target-free experiment exists at all, or that its exact price is Γ, with Γ=1 whenever the normalized information profiles coincide? If the latter, will you retitle the paper and restate Claim 3 to state the price rather than an impossibility, given that Appendix S.6 already characterizes both cases?

  2. Which part of "no continuous exact selector" do you claim as new: the qualitative impossibility, which is the textbook lower-hemicontinuity failure [1, 2] and the setting of [3], or the dimension-uniform quantitative bound ψ(L)? And how does Definition H.1's "simultaneously honest" coverage differ from the set-inference constructions [9–11], given that Appendix L.4's conclusion that "equilibrium inference itself is not new" omits [12]?

  3. Theorem 5.1's Γ is the reciprocal of guaranteed efficiency [5], [6] solves the R=2 case, and [7] proves the maximin/Bayes duality; eq. (5.7) is a special case of [5] and [8]. What exactly is new beyond the game-derived profiles and the post-hoc target protocol, and why does Appendix L.7 list the dual as a retained claim when Appendix S.6 presents it as a closed-form instance of maxi–min design?

  4. Why is there no budget-matched, same-model baseline in the empirical study, and where are the non-oracle versions of the point-risk and confidence results of Theorem 3.1 (items 4–5)? If the side target is undefined for value/regret methods, can you show their value or exploitability curves on the same 12 games per dimension (d ∈ {3, 5, 10, 20}) × 4 phase values?

  5. Define "phase" and "transition": which theorem establishes a critical point or discontinuity in κ? If the intended phenomenon is the smooth κ=λ/s_G crossover plus the Nδ_N²→∞ testing boundary, what justifies "phase transitions" in the title?

Reviewer_W6YpOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies stochastic two player zero sum matrix games where at step tt the player choses it∈[n]i_t \in [n] and jt∈[m]j_t \in [m] and observes Ait,jt+ηtA_{i_t, j_t} + \eta_t where ηt\eta_t is a sub-gaussian noise. They focus on pure exploration setting where the goal is to find a paired mixed strategy (x,y)(x, y) closest to a Nash equilibrium after TT rounds. They characterize Lipschitz constant characterization of any algorithm achieving error ϵ\epsilon w.r.t matrix AA, showing $ \frac{1}{4\epsilon} \le L$ is necessary and there exists an algorithm with L≤O(log⁡(n∨m)ϵ)L \le O(\frac{\log (n \vee m)}{\epsilon}). Moreover, they design a two stage sampling algorithm, that in a restricted class of matrices where there are two unknown equilibrium supports, it achieves asymptoticly optimal error. Lastly they show no algorithm can achieve small estimation error in multiple estimation objectives in this setting unless they coincide.

Critical strengths
  • The algorithm in section 3 in the specific class of matrix games achieves optimality equilibrium estimation error and uses reduction to a hypothesis test problem.
Critical weaknesses
  • Most of the main claims have limited novelty and are direct corollaries of prior work. Theorem 4.4 in [1] yields Lipschitz lower bound in Theorem 2.2 in a more general setting. For section 3, existing algorithms such as [2] achieve the same sample complexity O(Δ−2)O(\Delta^{-2}), where Δ\Delta is the minimum payoff gap, in the subclass studied in the paper while being near optimal for all stochastic zero sum matrix games. The paper should specify what TARGET improves beyond such algorithms and what sample complexity it can achieve for general zero sum games. Similarly, Theorem 5.1 is a corollary of known optimal design results [3].
  • The related work is not well written, it fails to include most relevant work and compare the authors claims with prior work. The writing in general needs substantial change making the new contributions clear and making the assumptions for all claims more clear.

[1] Epasto, Alessandro, Mohammad Mahdian, Vahab Mirrokni, and Emmanouil Zampetakis. "Optimal approximation-smoothness tradeoffs for soft-max functions." Advances in Neural Information Processing Systems 33 (2020): 2651-2660.

[2] Maiti, Arnab, Kevin Jamieson, and Lillian Ratliff. "Instance-dependent sample complexity bounds for zero-sum matrix games." In International Conference on Artificial Intelligence and Statistics, pp. 9429-9469. PMLR, 2023.

[3] Tommasi, Chiara, Juan M. Rodríguez-Díaz, and Jesús F. López-Fidalgo. "An equivalence theorem for design optimality with respect to a multi-objective criterion: C. Tommasi et al." Statistical Papers 64, no. 4 (2023): 1041-1056.

Questions for authors
  • Why was the special matrix game class studied in section 3 beyond allowing the reduction of the problem to a hypothesis test?
  • Does the algorithm TARGET achieve better error than prior work general purpose algorithms?
  • Can the analysis be extended to any two matrices A,A′A, A' without specific assumptions on their equilibrium support?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.