acceptodds
Under review as a conference paper at ICLR 2027

From Verification to Discovery: The Query Complexity of Equilibrium Certification

Abstract

Self-play can learn approximate Nash equilibria from noisy interactions, but does finding an equilibrium require more information than checking a supplied candidate? We study this gap between discovery and verification and how it depends on payoff structure. For bounded zero-sum games with unit-variance Gaussian payoff queries, verification under a constant-factor accuracy margin uses queries at fixed small accuracy and confidence, while discovery can require . The lower bound applies to arbitrary approximate equilibria because every valid mixed output reveals hidden action labels. By contrast, every fixed-rank class has minimax discovery complexity in the same regime. Our fixed-rank upper bounds use response compression to learn strategic responses directly from noisy payoffs without supplied factors or anchors. For nontrivial rank-one games, we obtain the exact minimax law . Rank two retains linear dependence on and the optimal accuracy exponent up to logarithmic factors. Finally, combining structured search, generic self-play, and independent verification retains these gains without knowing the rank while preserving correctness on every bounded game.

Primary area:
learning theory
Keywords:
zero-sum games, equilibrium certification, query complexity, low-rank matrices, minimax theory, pure exploration

Reviews

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

The authors study the following model. There is a matrix A∈[−1,1]k×kA \in [-1, 1]^{k \times k} defining a zero-sum normal-form game. A learner may make noisy queries to the entries of AA: on each round tt, the learner selects an entry (i,j)∈[k]2(i, j) \in [k]^2 and observes Aij+ztA_{ij} + z_t where ztz_ts are iid unit Gaussians. Under this model, the authors consider the query complexity of (1) finding an equilibrium, and (2) verifying a given equilibrium (to precision ϵ\epsilon w.p. 1−δ1 - \delta). The main results are the following. Let ϵ,δ\epsilon, \delta be constants.

  • There is a separation between equilibrium finding and equilibrium verification: the former takes Ω(klog⁡log⁡k)\Omega(k \log \log k) queries, but the latter takes O(k)O(k) queries.
  • If AA has constant rank, then equilibrium finding also takes O(k)O(k) queries.
Critical strengths

The query complexity of equilibrium computation is an interesting problem, as the authors point out. In my opinion, the most interesting result in this paper is the Ω(klog⁡log⁡k)\Omega(k \log \log k) query complexity lower bound on equilibrium finding.

Critical weaknesses

The writing quality is very poor, reminiscent of the deficiencies of AI-generated math: needlessly confusing/arbitrary/nonstandard terminology/notation, over-emphasis on detail, etc. I vote to reject on these grounds alone.

Questions for authors

None.

1 comment
AuthorsOpenReview ↗

Thank You for Your Feedback

We sincerely thank you for your careful review and for recognizing our equilibrium-finding lower bound as “the most interesting result in this paper.” We apologize for the delay in responding, as we undertook a substantial rewrite of the manuscript. We have highlighted all changes in blue. Our point-by-point responses follow.

Q1: The writing quality is very poor, reminiscent of the deficiencies of AI-generated math: needlessly confusing/arbitrary/nonstandard terminology/notation, over-emphasis on detail.

A: Thank you for identifying these problems with the writing. We agree that calling the search task “certification” invited confusion with verification. We have clarified the task terminology in the main text as shown below. The table identifies the original items where they have been moved.

LocationWhat we changed
Terminology (Sections 1–7)The search task is now called “equilibrium finding,” and checking a supplied pair is called “candidate verification.” We have replaced “full-box” with bounded-game terminology and “physical precision” with “payoff-scale precision.”
Notation (Section 2)Since the main text uses only Gaussian observations, we have dropped the superscript GG from Mn,mG\mathcal M^G_{n,m}. The equilibrium condition is stated through the two regret inequalities, without repeatedly referring to Cεind(A)\mathcal C_\varepsilon^{\mathrm{ind}}(A). We keep the extra notation in the appendices where different models or equilibrium criteria need to be distinguished.
Lower-bound results (Section 3)The original Theorem 3.1(ii), its effective widths, and Corollary 3.3 are now recorded in Corollaries I.2 and I.3 in Appendix I. Section 3 now concentrates on the fixed-accuracy separation and its proof. The general upper bound remains alongside the lower bound.
Proof overview and Figure 2 (Section 3)We have rewritten both to explain why every approximate equilibrium reveals the hidden set and where the log⁡log⁡k\log\log k factor comes from. The overview no longer introduces the construction's score functions. Their definitions and the witness calculations are left to Appendix J.
Low-rank argument (Section 4)The discussion now follows the algorithm: solve the game defined by the current response representation, then check its candidate in the original game. A reliable rejection reveals a missing response direction. We explain why rank limits these additions before giving the matrix identities, and show how bounded interpolation transfers error control to the other actions. The inversion and precision calculations remain in Appendices M and P.4.
Extensions (Theorem 4.3 and Section 5)We have moved the rank-one perturbation guarantee and the neighborhoods of shifted skew-symmetric games to Appendices L.5, P.5 to P.7, and Q. The main bounds and their assumptions remain in the text, including the accuracy margin required for verification.
Repeated material (Figure 1 and Table 1)Table 1 retains both panels: fixed accuracy and confidence in (a), and accuracy and confidence dependence in (b). We have shortened repeated discussion in the introduction and conclusion.

The rewritten lower-bound overview begins:

The hard games are indexed by a hidden set UU of action labels. Their paired rows force every approximate equilibrium to separate the labels inside UU from those outside it. A public decoder therefore recovers UU from any valid output, regardless of its support.

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

Suppose a k by k zero-sum game has stochastic payoffs, in the sense that any pure profile is associated with a unit-variance Gaussian distribution that decrees how much the row player pays the column player. It's of interest to figure out how many payoff queries are needed in order to construct an equilibrium. A payoff query returns a sample from the distribution associated with the pure profile being queried. There's a trade-off between learning the expected value fairly well by querying it repeatedly, and checking on other pure profiles. There's also a related problem of given a proposed solution, verify that it's an approximate NE. The paper studies the query complexity of these tasks.

Critical strengths

It's quite a nice algorithmic game theory problem, which adds to a line of work on query complexity and could lead to more interesting follow-up work.

The authors shows a clear separation between finding and checking an approximate Nash equilibrium. The technical result is interesting and clear in showing where the extra query cost comes from.

For rank one games, the authors give a tight query complexity bound, and linear dependence on n+mn+m for every fixed rank at fixed accuracy. These results seem meaningful and would be of interest to the community.

Critical weaknesses

The writing is very dense at times and notation heavy, without sufficient intuition. This may hinder understanding. This is particularly so for the content in the appendix, I found it very difficult to parse.

On the technical side, since the paper’s main question is the query complexity for general k×kk \times k games, having a gap (between the LB & UB) would be a key weakness (although I appreciate that this gap is not too large).

The general fixed-rank UB would really only have bite when rank and accuracy are both fixed constants, and this weakens the technical contribution.

Questions for authors

Questions For Authors: Could the authors detail the challenge for robustness for arbitrary rectangular matrices with rank two?

Some problems with the writing: Sect 2.1. lines 121-125: Here's where things get hard to follow. If I understand right, I_t and J_t are mixed strategies for the row/col players respectively (?) Then the observation X_t is obtained by sampling pure strategies (i,j) from I_t and J_t, and then sampling a value from the (univariate Gaussian) distribution of values coming from entry (i,j). In general, i and j need not be known(?), although the query could use pure strategies. An alternative query model could allow mixed strategies to be queried, then their expected payoff, with unit Gaussian noise added, is returned. That's more powerful since you get (in a single query) the averaging over the mixed strategies. The vertical bar hints that the observation X_t may depend on the history {\cal F}_{t-1}, not sure how that works. I would think that the choice of query may sensible depend on the history of observations, but I can't guess a model within which the observation (which I assume means the response to the query) depends on the history.

3 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/3)

We sincerely thank you for your support and encouraging assessment of our work. We particularly appreciate your recognition that this is “quite a nice algorithmic game theory problem” and that “the technical result is interesting and clear in showing where the extra query cost comes from.” Your thoughtful questions and suggestions have also helped us strengthen the paper and clarify important aspects of our results. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses follow.


Q1: Could the authors detail the challenge for robustness for arbitrary rectangular matrices with rank two?

A: Thank you for asking us to explain the robustness obstacle. The main obstacle is preserving row stability during the subsequent column selection. In Appendix P.4.2, exact rank two makes the row interpolation coefficients independent of the chosen nonsingular column pair. Thus selecting columns preserves the row bound obtained in the first step. This invariance is the specific property that the perturbation argument must replace.

What perturbations require. Consider A=B+EA=B+E with rank⁡(B)≤2\operatorname{rank}(B)\leq2 and ∥E∥∞≤ρ\\\|E\\\|_\infty\leq\rho, using the entrywise norm. The proof must extend interpolation control on the selected submatrix to uniform residual bounds over all entries. It must also retain bounded representations on both sides and the bounded feasible coordinates used in Lemma P.16. These guarantees must hold even near rank-one instances while preserving the query bound of Theorem 4.5(i).

Why skew symmetry helps. A shared anchor pair and a determinant identity provide joint control of both sides. Lemma P.20 uses this structure to construct an exact rank-two surrogate within O(ρ)O(\rho) of the latent matrix. The rectangular argument needs a corresponding stability guarantee for separately selected row and column anchors. We have explained this exact-rank dependency and the required stability guarantees in Remark 4.7 and Appendix P.4.2.


Q2: If I understand right, ItI_t and JtJ_t are mixed strategies for the row/col players respectively ?

A: Thank you for highlighting this ambiguity in our notation. No. ItI_t and JtJ_t are the row and column indices of the pure-action pair queried at round tt, whereas x∈Δnx\in\Delta_n and y∈Δmy\in\Delta_m denote mixed strategies. The query policy may select ItI_t and JtJ_t randomly and adaptively based on the history. We have revised Section 2.1 to clarify this distinction. The revised text reads:

At round tt, the learner selects a pair of pure-action indices (It,Jt)∈[n]×[m](I_t,J_t)\in[n]\times[m] using the history Ft−1\mathcal F_{t-1} and its own randomization. Both indices are observed by the learner. It then receives Xt=AItJt+ξtX_t=A_{I_tJ_t}+\xi_t, where ξt∼N(0,1)\xi_t\sim\mathcal N(0,1) is fresh noise independent of the preceding history and the selected pair.


Q3: Then the observation XtX_t is obtained by sampling pure strategies (i,j)(i,j) from ItI_t and JtJ_t, and then sampling a value from the (univariate Gaussian) distribution of values coming from entry (i,j)(i,j). In general, ii and jj need not be known(?), although the query could use pure strategies.

A: Thank you for asking us to clarify what the learner observes. No. The learner directly selects (It,Jt)(I_t,J_t) as the query pair. These are the realized row and column indices of the queried entry, not distributions from which additional actions are sampled. The query policy may randomize its choice based on the history Ft−1\mathcal{F}_{t-1}, but both selected indices are known to the learner. Conditional on the selected cell, the oracle returns one fresh Gaussian payoff observation. We have revised Section 2.1 to clarify the query mechanism. The revised text reads:

Both indices are observed by the learner.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/3)

Q4: An alternative query model could allow mixed strategies to be queried, then their expected payoff, with unit Gaussian noise added, is returned. That's more powerful since you get (in a single query) the averaging over the mixed strategies.

A: Thank you for suggesting this alternative query model. Yes. The proposed oracle permits direct mixed-strategy queries. It returns x⊤Ay+Zx^\top Ay+Z in one query and includes pure-cell queries as the special case x=eix=e_i, y=ejy=e_j. We deliberately study the pure-cell model because our setting is motivated by noisy simulated matchups in which each observation reveals a single payoff-matrix entry. Both discovery and verification use this same query model.

We have added an explicit discussion of this distinction in Section 2.1. In particular, sampling I∼xI\sim x and J∼yJ\sim y and observing AIJ+ZA_{IJ}+Z does not implement the proposed oracle. The former is generally a Gaussian mixture with variance 1+Var⁡(AIJ)1+\operatorname{Var}(A_{IJ}), whereas the latter returns a Gaussian observation with mean x⊤Ayx^\top Ay and unit variance. The revised text reads:

A different oracle could accept (x,y)(x,y) directly and return x⊤Ay+Zx^\top Ay+Z, with Z∼N(0,1)Z\sim\mathcal N(0,1). It includes pure-cell queries. Sampling I∼x,J∼yI\sim x,J\sim y and querying (I,J)(I,J) instead generally gives a Gaussian mixture with variance 1+Var⁡(AIJ)1+\operatorname{Var}(A_{IJ}).


Q5: The vertical bar hints that the observation XtX_t may depend on the history Ft−1\mathcal{F}_{t-1}, not sure how that works. I would think that the choice of query may sensible depend on the history of observations, but I can't guess a model within which the observation (which I assume means the response to the query) depends on the history.

A: Thank you for pointing out the unclear conditioning notation. For a fixed queried cell, the response distribution does not depend on the history. Conditioning on Ft−1\mathcal{F}_{t-1} states that this same law holds under adaptive querying. Observations across rounds can still be dependent because later queries use earlier responses. Section 2.1 now states this explicitly:

It then receives Xt=AItJt+ξtX_t=A_{I_tJ_t}+\xi_t, where ξt∼N(0,1)\xi_t\sim\mathcal N(0,1) is fresh noise independent of the preceding history and the selected pair.


Q6: The writing is very dense at times and notation heavy, without sufficient intuition. This may hinder understanding. This is particularly so for the content in the appendix, I found it very difficult to parse.

A: Thank you for identifying where the exposition needs more guidance. We agree that the paper needs a clearer explanation of the ideas behind its technical arguments. The main issue is not the length of the proofs, but the lack of guidance on why the constructions are introduced and how the different arguments fit together. We have made the following revisions.

LocationRevision
Section 4The fixed-rank discussion now presents the algorithmic idea before the query bound. A cross defines the CUR surrogate, whose equilibrium is then tested in the original game. The important step is what happens after rejection: a deviation witness produces a new Schur pivot and increases the skeleton dimension. This explains both the rank progress and the bound of at most rr expansions.
Appendices H–JA common roadmap now distinguishes the three lower-bound constructions. H uses a rank-two star to establish the confidence cost. I develops the dense-good-layer construction for rectangular games. J introduces the intersection witness, which allows s=Θ(log⁡k)s=\Theta(\log k) even at fixed accuracy and yields the superlinear discovery lower bound.
Appendix MA new dependency diagram shows how the CUR residual identities lead to dominant-row purification, candidate construction, fresh verification, and Schur pivot extraction. The final modules then establish the structural invariants and control the failure probability and termination.
Appendix PThe opening discussion and module table now distinguish three arguments: skew-symmetric rank two (P.1–P.3), arbitrary rectangular rank two (P.4), and near-skew robustness (P.5–P.7). The table also states the role of the binary-feedback extension in P.8.
Appendix AThe notation reference now includes proof-specific auxiliary symbols and links to their definitions. The longer proofs introduce these quantities where they are used.
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/3)

For instance, Section 4 now explains the algorithm before its query bound:

The general construction expands its response representation after each reliable rejection. An invertible s×ss\times s cross defines a low-rank surrogate, and rejection of a surrogate equilibrium in the original game exposes a nonzero Schur residual and hence a missing response direction. Each such rejection increases the represented dimension, so at most rr expansions occur.

These expository changes preserve the underlying arguments and explain their roles before presenting the technical details.


Q7: On the technical side, since the paper's main question is the query complexity for general k×kk\times k games, having a gap (between the LB & UB) would be a key weakness (although I appreciate that this gap is not too large).

A: Thank you for raising the remaining minimax gap. We agree that the exact minimax rate for unrestricted balanced games remains open in the fixed-accuracy, fixed-confidence regime. Specifically, Theorem 3.1 and our self-play upper bound give

ckε−2(log⁡log⁡(ek)+log⁡1δ)≤Mk,k(ε,δ)≤Ckε−2(log⁡(ek)+log⁡1δ).ck\varepsilon^{-2}\left(\log\log(ek)+\log\frac{1}{\delta}\right) \leq \mathcal{M}_{k,k}(\varepsilon,\delta) \leq Ck\varepsilon^{-2}\left(\log(ek)+\log\frac{1}{\delta}\right).

For fixed ε\varepsilon and δ\delta, a factor of order log⁡k/log⁡log⁡k\log k/\log\log k remains. Our bounds nevertheless match in several important regimes. For arbitrary rectangular dimensions, when log⁡(1/δ)≥log⁡(e(n+m))\log(1/\delta)\geq\log(e(n+m)), we establish Mn,m(ε,δ)=Θ((n+m)ε−2log⁡(1/δ))\mathcal{M}_{n,m}(\varepsilon,\delta)=\Theta((n+m)\varepsilon^{-2}\log(1/\delta)). For balanced games, we also obtain Mk,k(ε,δ)=Θδ(kε−2log⁡(ek))\mathcal{M}_{k,k}(\varepsilon,\delta)=\Theta_{\delta}(k\varepsilon^{-2}\log(ek)) when δ\delta is fixed and ε≤log⁡(ek)/k\varepsilon\leq\log(ek)/k.

The fixed-accuracy lower bound applies to every valid approximate equilibrium, regardless of its support or which equilibrium the learner selects. Together with the O(k)O(k) verification guarantee in Lemma 2.1 under its stated accuracy margin, it establishes a strict separation between discovery and verification. Section 3 now separates these claims, and Corollary I.3 in Appendix I records the matching regimes.


Q8: The general fixed-rank UB would really only have bite when rank and accuracy are both fixed constants, and this weakens the technical contribution.

A: Thank you for emphasizing the role of the fixed-parameter regime. We agree that Theorem 4.1 does not provide an optimal joint dependence on rank and accuracy. Its deterministic query cap scales as Cr(n+m)ε−(4r+6)log⁡(cr/δ)C_r(n+m)\varepsilon^{-(4r+6)}\log(c_r/\delta). However, it establishes the minimax-optimal dependence on action dimension and confidence for every fixed rr and ε\varepsilon. More precisely, combining its upper bound with the rank-one lower bound gives, for D=n+mD=n+m, r≥1r\geq 1, (n,m)≠(1,1)(n,m)\neq(1,1), 0<ε≤1/80<\varepsilon\leq 1/8, and 0<δ≤1/40<\delta\leq 1/4,

cDε−2log⁡1δ≤M≤r(n,m,ε,δ)≤CrDε−(4r+6)log⁡crδ.cD\varepsilon^{-2}\log\frac{1}{\delta} \leq \mathcal{M}_{\leq r}(n,m,\varepsilon,\delta) \leq C_rD\varepsilon^{-(4r+6)} \log\frac{c_r}{\delta}.

The accuracy dependence is substantially sharper at ranks one and two. Theorem 4.3 establishes the exact minimax rate M≤1=Θ(Dε−2log⁡(1/δ))\mathcal{M}_{\leq 1}=\Theta(D\varepsilon^{-2}\log(1/\delta)) throughout the stated parameter range. For arbitrary rectangular rank-two games, Theorem 4.5 gives a deterministic upper bound of CDε−2Lε3log⁡(cLε/δ)CD\varepsilon^{-2}L_\varepsilon^3\log(cL_\varepsilon/\delta), where Lε=log⁡(2/ε)L_\varepsilon=\log(2/\varepsilon). Since the rank-one class is contained in the rank-two class, the lower bound follows from Theorem 4.3. This comparison is now explicit in Corollary 4.6:

cDε−2log⁡1δ≤M≤2(n,m,ε,δ)≤CDε−2Lε3log⁡cLεδ.cD\varepsilon^{-2}\log\frac{1}{\delta} \leq \mathcal{M}_{\leq 2}(n,m,\varepsilon,\delta) \leq CD\varepsilon^{-2}L_\varepsilon^3 \log\frac{cL_\varepsilon}{\delta}.

Thus, rank two achieves the optimal ε−2\varepsilon^{-2} accuracy exponent up to logarithmic factors while retaining linear dependence on the number of actions.

We have revised the opening of Section 4 to distinguish the general fixed-rank guarantee from these sharper rank-specific results. We have also expanded the discussion of Corollary 5.1 to clarify that a single rank-agnostic policy automatically attains the improved guarantees for rank-one and rank-two games while remaining valid over the entire payoff box.

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

Setting. The paper studies two-player zero-sum matrix games with an unknown payoff matrix A∈[−1,1]n×mA\in[-1,1]^{n\times m}. Each query to cell (i,j)(i,j) returns a fresh N(Aij,1)\mathcal N(A_{ij},1) sample. For every matrix in this class, the strategy must return (x^,y^)(\hat x,\hat y) whose row and column regrets are both at most ε with probability at least 1−δ1-\delta. Cost is measured as the worst-case expected number of queries.

Verification. The verifier checks a fixed candidate in three steps:

  • Run median elimination on the row-response arms ei⊤Aye_i^\top Ay and the column-response arms x⊤Aejx^\top Ae_j.
  • Estimate the two selected responses and the candidate payoff from fresh samples.
  • Accept if GapA≤ε/4\mathrm{Gap}_A\le\varepsilon/4, and reject if either regret exceeds ε.

The procedure uses O((n+m)ε−2log⁡(1/α))O((n+m)\varepsilon^{-2}\log(1/\alpha)) queries.

Unrestricted discovery. The upper bound is O(ε−2[nlog⁡n+mlog⁡m+(n+m)log⁡(1/δ)])O(\varepsilon^{-2}[n\log n+m\log m+(n+m)\log(1/\delta)]), achieved by combining three components: bandit self-play (Bai et al., 2022, specialized to a single stage), a Bernoulli factory that converts Gaussian samples into bounded unbiased samples, and a propose–verify–restart wrapper.

The lower bound comes from two constructions:

  • A rank-two star construction yields the confidence term (n+m−2)ε−2log⁡(1/δ)(n+m-2)\varepsilon^{-2}\log(1/\delta).
  • A dense construction uses rows (i,±)(i,\pm) with payoffs ±(ai(j)−8ε1{i∈U})\pm(a_i(j)-8\varepsilon\mathbf 1\{i\in U\}) together with a public sign dictionary.

In the dense construction, any output whose regrets are both at most ε satisfies FU(y)≤3εF_U(y)\le 3\varepsilon, so the threshold ui(y)>4εu_i(y)>4\varepsilon recovers the hidden set UU from every valid output. A change-of-measure argument between deletion neighbors T=S∖{i}T=S\setminus\{i\} that share a single error budget then yields Ω(Nε−2log⁡(s/δ))\Omega(N\varepsilon^{-2}\log(s/\delta)). Two witnesses determine the resulting rates:

  • The additive witness requires s≤1/(16ε)s\le 1/(16\varepsilon). When ε≲log⁡k/k\varepsilon\lesssim\log k/k, it yields Θ(kε−2log⁡k)\Theta(k\varepsilon^{-2}\log k).
  • The intersection witness uses 2s2^s columns, which allows s=Θ(log⁡k)s=\Theta(\log k) at fixed ε, and yields Ω(kε−2[log⁡log⁡k+log⁡(1/δ)])\Omega(k\varepsilon^{-2}[\log\log k+\log(1/\delta)]).

Bounded rank. The algorithm maintains an invertible cross C=AI,JC=A_{I,J} and a surrogate matrix B=A:,JC−1AI,:B=A_{:,J}C^{-1}A_{I,:}. It solves the surrogate game to gap ε/16 and verifies the solution in the true game. On rejection, it converts the deviation witness into a residual pivot with ∣Eij∣≥ε/16|E_{ij}|\ge\varepsilon/16, which raises the skeleton rank by one. Two techniques ensure stability:

  • Noisy maximum-volume row swaps bound the interpolation coefficients by 2.
  • The determinant margin ∣det⁡C∣≥(ε/16)s|\det C|\ge(\varepsilon/16)^s stabilizes the empirical inverse.

The query bound is Cr(n+m)ε−(4r+6)log⁡(cr/δ)C_r(n+m)\varepsilon^{-(4r+6)}\log(c_r/\delta). Combined with the rank-one lower bound, this gives Θr,ε((n+m)log⁡(1/δ))\Theta_{r,\varepsilon}((n+m)\log(1/\delta)).

Rank one and rank two.

  • Rank one: two absolute-value scans find a pivot with bounded ratios, and the identity Aij=AibAaj/AabA_{ij}=A_{ib}A_{aj}/A_{ab} then reduces the game to a 2×22\times2 game on the extreme rows and columns. This yields Θ((n+m)ε−2log⁡(1/δ))\Theta((n+m)\varepsilon^{-2}\log(1/\delta)) and tolerates entrywise perturbations of up to ε/16.
  • Rank two, rectangular: O((n+m)ε−2L3log⁡(L/δ))O((n+m)\varepsilon^{-2}L^3\log(L/\delta)), where L=log⁡(2/ε)L=\log(2/\varepsilon).
  • Rank two, skew-symmetric: O(nε−2[log⁡(2+min⁡{n,ε−1})+log⁡(1/δ)])O(n\varepsilon^{-2}[\log(2+\min\{n,\varepsilon^{-1}\})+\log(1/\delta)]).
  • Every rank-two output has support size at most three.

Adaptivity. Structured proposals and generic self-play run on a dyadic schedule, and each candidate is checked by a fresh verifier under a summable error budget. The resulting strategy is correct on every bounded matrix, and its expected cost is the minimum of the applicable bounds.

The paper is purely theoretical and contains no experiments.

Critical strengths

1. A decoding reduction makes the lower bound independent of which equilibrium the learner returns. Every valid output satisfies FU(y)≤V⋆+R+C≤3εF_U(y)\le V^\star+R+C\le 3\varepsilon. Whatever equilibrium or support the learner chooses, the column strategy alone therefore reveals UU through a fixed threshold. Combined with the error budget shared across deletion neighbors, this gives what is, to my knowledge (moderate confidence), the first proof that the log⁡k\log k factor in bandit self-play is necessary in the worst case. Specifically:

  • When ε≲log⁡(ek)/k\varepsilon\lesssim\log(ek)/k, the rate is Θ(kε−2[log⁡k+log⁡(1/δ)])\Theta(k\varepsilon^{-2}[\log k+\log(1/\delta)]).
  • By Corollary N.5, no bandit self-play routine can uniformly guarantee an expected duality gap of O(k/T)O(\sqrt{k/T}).

2. A bounded-rank algorithm that requires no anchors, factors, incoherence, or condition-number bounds. Each verifier rejection produces a Schur residual pivot of magnitude at least ε/16, so the rank bounds the number of expansions, and the determinant margin takes the place of a condition-number assumption. For every fixed (r,ε)(r,\varepsilon), the dependence on n+mn+m is linear, which establishes a strict separation between complexity classes. The mechanism is simple and potentially reusable.

Critical weaknesses

1. The central separation is quantitatively negligible, disappears at high confidence, and inherits its mechanism from bandit subset selection.

At fixed ε, the lower bound is ckε−2[log⁡log⁡(ek)+log⁡(1/δ)]ck\varepsilon^{-2}[\log\log(ek)+\log(1/\delta)], while the verifier costs Ckε−2log⁡(c/δ)Ck\varepsilon^{-2}\log(c/\delta). Their ratio grows only when log⁡log⁡k\log\log k dominates log⁡(1/δ)\log(1/\delta), and Corollary 3.3(a) shows that the two are of the same order once log⁡(1/δ)≥log⁡(e(n+m))\log(1/\delta)\ge\log(e(n+m)).

The construction is also purely asymptotic: it produces the log⁡log⁡k\log\log k term only when k≥240k\ge 2^{40}, and below this threshold the bound reduces to the star bound, which lacks that term. Moreover, the mechanism is inherited. Step 2 relies on subsets from adjacent layers, deletion neighbors, a single shared error budget, and the convexity of kl\mathrm{kl}—exactly the Explore-m argument of Kalyanakrishnan et al. (2012). Their Theorem 8 shows that any PAC algorithm selecting mm near-optimal arms needs on the order of (n/ε2)ln⁡(m/δ)(n/\varepsilon^2)\ln(m/\delta) samples on some instance, and the authors identify the aggregation of error terms across instances as the key step behind the log⁡m\log m dependence. In that problem, verifying a proposed subset with a margin takes only O(nε−2log⁡(1/δ))O(n\varepsilon^{-2}\log(1/\delta)) samples: run PAC minimum selection on the subset and PAC maximum selection on its complement. “Discovery costs more than verification” is therefore a known pure-exploration phenomenon.

The paper's new contribution is the game embedding. At fixed accuracy, the embedding accommodates only s=Θ(log⁡k)s=\Theta(\log k) labels, which explains the log⁡log⁡k\log\log k factor. Yet the main text presents the shared budget as the paper's own mechanism and mentions subset selection only in the related work.

2. The bounded-rank result is a classification with no practical value for r≥2r\ge 2, and the low-rank analysis is disconnected from the structure that motivates it.

The paper hides the dependence on ε\varepsilon. The general upper bound is Cr(n+m)ε−(4r+6)log⁡(cr/δ)C_r(n+m)\varepsilon^{-(4r+6)}\log(c_r/\delta), and the analysis involves Ls=ss−1(16/ε)sL_s=s^{s-1}(16/\varepsilon)^s and a net of size (1+4096s/ε)s(1+4096s/\varepsilon)^s. The upper and lower bounds differ by a factor of ε−(4r+4)\varepsilon^{-(4r+4)}, which the Θr,ε\Theta_{r,\varepsilon} notation absorbs, yet Figure 1 and Table 1 label this class “minimax” and “minimax optimal.”

At realistic scales, the method also never outperforms generic self-play. Generic self-play costs O(kε−2log⁡k)O(k\varepsilon^{-2}\log k), so the general bounded-rank method improves on it only when log⁡k≳Crε−(4r+4)\log k\gtrsim C_r\varepsilon^{-(4r+4)}; for r=3r=3 and ε=0.1\varepsilon=0.1, this requires log⁡k≳1016\log k\gtrsim 10^{16} times an unspecified ratio of constants. Net enumeration is exponential in rr, and the paper acknowledges that the procedure is computationally inefficient. Practical gains arise in only two narrow cases:

  • Rank one, which reduces to a 2×22\times2 game on the extreme rows and columns and whose lower bound is the classical PAC best-arm bound.
  • Skew-symmetric rank two.

The paper also omits its connection to the motivating literature. Skew-symmetric rank two is directly relevant to self-play evaluation: using the Schur decomposition, Balduzzi et al. (2019) show that a population's empirical gamescape can be represented in a space whose dimension equals the rank of the skew-symmetric evaluation matrix. The planar support geometry in Appendix P is exactly the rank-two gamescape, yet the paper does not cite this line of work.

Questions for authors
  1. Please state the constant CC in Lemma 2.1. Using your explicit constants, what is the smallest kk for which the lower bound in Theorem 3.1(i) exceeds the verifier's upper bound at concrete values such as ε=δ=0.05\varepsilon=\delta=0.05? If no realistic kk exists, the abstract and Figure 1 should state that the separation is asymptotic.

  2. Do you agree that, as Corollary 3.3(a) shows, the separation disappears once log⁡(1/δ)≳log⁡log⁡k\log(1/\delta)\gtrsim\log\log k? If so, please state this in the abstract.

  3. Apart from the decoding reduction, which step in the proofs of Theorems I.1 and J.1 differs from the argument for Theorem 8 in Kalyanakrishnan et al. (2012)?

  4. How does CrC_r grow with rr? For r=2,3r=2,3 and ε=0.1\varepsilon=0.1, how large must kk be for the rank-rr upper bound to fall below the generic upper bound?

  5. Does the fixed-accuracy lower bound hold for skew-symmetric games, the relevant class for symmetric self-play? The embedding (0A−A⊤0)\begin{pmatrix}0&A\\\\-A^\top&0\end{pmatrix} suggests that it does, but symmetrization changes the definition of regret. Please confirm.

6 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/4)

We sincerely thank you for the careful and thoughtful review, as well as for your constructive comments and suggestions. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses follow.


Q1: The paper's new contribution is the game embedding. At fixed accuracy, the embedding accommodates only s=Θ(log⁡k)s=\Theta(\log k) labels, which explains the log⁡log⁡k\log\log k factor. Yet the main text presents the shared budget as the paper's own mechanism and mentions subset selection only in the related work.

A: Thank you for emphasizing the need for clear attribution. The shared-budget argument follows the subset-selection proof of Kalyanakrishnan et al. (2012, Theorem 8). Our contribution to this lower bound is the game embedding that forces every valid approximate equilibrium to reveal the hidden subset. We have made this distinction explicit in the main text.

The intersection witness in Theorem J.1 allows the subset size to grow at fixed accuracy. With Θ(k)\Theta(k) candidate labels, its dictionary uses d=Θ(2slog⁡k)d=\Theta(2^s\log k) columns. The requirement d+1≤kd+1\le k allows s=Θ(log⁡k)s=\Theta(\log k). The inherited log⁡(s/δ)\log(s/\delta) factor then gives Ω(kε−2log⁡log⁡k)\Omega(k\varepsilon^{-2}\log\log k) for fixed 0<ε≤1/160<\varepsilon\le1/16 and 0<δ≤1/40<\delta\le1/4. The attribution now appears in the introduction, Section 3 Step 2, and Figure 2(b). Remark 3.4 explains how the column requirement produces the log⁡log⁡k\log\log k factor.


Q2: The upper and lower bounds differ by a factor of ε−(4r+4)\varepsilon^{-(4r+4)}, which the Θr,ε\Theta_{r,\varepsilon} notation absorbs, yet Figure 1 and Table 1 label this class “minimax” and “minimax optimal.” The paper hides the dependence on ε\varepsilon.

A: Thank you for pointing out this ambiguity in the optimality claim. The general fixed-rank bounds do leave the stated polynomial gap in ε\varepsilon. They match in action count and confidence for fixed r,εr,\varepsilon. Figure 1 now says “Optimal in kk at fixed r,ε,δr,\varepsilon,\delta.” Table 1(a) fixes r,ε,δr,\varepsilon,\delta, as stated in its note.

For integer r≥1r\ge1 and n,m≥1n,m\ge1 with (n,m)≠(1,1)(n,m)\ne(1,1), the bounds hold throughout 0<ε≤1/80<\varepsilon\le1/8 and 0<δ≤1/40<\delta\le1/4:

c(n+m)ε−2log⁡(1/δ)≤M≤rG(n,m,ε,δ)≤Cr(n+m)ε−(4r+6)log⁡(cr/δ).c(n+m)\varepsilon^{-2}\log(1/\delta) \le \mathcal M_{\le r}^{\mathrm G}(n,m,\varepsilon,\delta) \le C_r(n+m)\varepsilon^{-(4r+6)}\log(c_r/\delta).

Here c>0c>0 is universal and Cr,cr≥1C_r,c_r\ge1 depend only on rr. The lower bound follows from the rank-one subclass (Theorem 4.3), and the upper bound is Theorem M.1. Theorem 4.1 now displays both bounds, so the accuracy dependence is visible without expanding Θr,ε\Theta_{r,\varepsilon}.

The optimal accuracy dependence for general r≥3r\ge3 remains open. The specialized results are sharper: rank one has matching bounds in all parameters (Theorem 4.3), while rank two attains the ε−2\varepsilon^{-2} exponent up to logarithmic factors (Theorem 4.5). The table distinguishes these guarantees. The abstract and contribution summary state the fixed-parameter regime, and Theorem 4.1 identifies the optimal action-count and confidence dependence at fixed rank and accuracy.


Q3: Net enumeration is exponential in rr, and the paper acknowledges that the procedure is computationally inefficient.

A: Thank you for raising the computational issue. Net enumeration makes the general-rank procedure computationally inefficient as rr grows. Theorem 4.1 establishes an information-theoretic query bound: at fixed r,εr,\varepsilon, discovery has linear dependence on n+mn+m. The net size also enters the query upper bound because each direction requires a separate response search. This limitation is now stated directly after Theorem 4.1.

The algorithms for ranks one and two have polynomial real-arithmetic cost and retain linear query dependence on n+mn+m. Rank one uses scalar endpoint searches (Theorem 4.3), while rank two uses planar support and feasibility searches (Theorem 4.5). These procedures avoid the general-rank enumeration. Whether linear query dependence on the number of actions can be retained with computation polynomial in rank remains unresolved in our work.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/4)

Q4: The rank-one result reduces to a 2×22\times2 game on the extreme rows and columns, and its lower bound is the classical PAC best-arm bound.

A: Thank you for placing the rank-one result in context. The endpoint geometry and the PAC lower-bound argument are standard. Rank one serves as a sharp benchmark for the higher-rank results. Theorem 4.3 establishes the minimax rate Θ((n+m)ε−2log⁡(1/δ))\Theta((n+m)\varepsilon^{-2}\log(1/\delta)) in the noisy cell-query model without known factors or a supplied nonzero pivot.

The algorithm either certifies a pure pair or finds a pivot with bounded row and column ratios. This lets the endpoint searches and estimates of the four selected payoffs use precision proportional to ε\varepsilon. A constant number of standard PAC searches (Even-Dar et al., 2006) therefore gives a deterministic cap of the stated order.

The discussion after Theorem 4.3 now makes this benchmark role explicit and points to the pivot analysis in Appendix L.3. Appendix L.4 attributes the lower-bound method to Mannor and Tsitsiklis (2004).


Q5: The paper also omits its connection to the motivating literature. Skew-symmetric rank two is directly relevant to self-play evaluation: using the Schur decomposition, Balduzzi et al. (2019) show that a population's empirical gamescape can be represented in a space whose dimension equals the rank of the skew-symmetric evaluation matrix. The planar support geometry in Appendix P is exactly the rank-two gamescape, yet the paper does not cite this line of work.

A: Thank you for pointing us to the empirical gamescape literature. The reviewer is correct: the skew-symmetric rank-two geometry in Appendix P.2 is a planar representation of the empirical gamescape of Balduzzi et al. (2019, Proposition 3). Their Proposition 4 also provides its equilibrium interpretation. Theorem P.11 adds a finite-confidence query guarantee under Gaussian payoff noise when the evaluation matrix and its coordinates are unknown.

Let AijA_{ij} denote det⁡(zi,zj)\det(z_i,z_j) with zi∈R2z_i\in\mathbb R^2. The convex hull K=conv⁡z1,…,znK=\operatorname{conv}\\{z_1,\ldots,z_n\\} is linearly isomorphic to their empirical gamescape at rank two. For q∈Δnq\in\Delta_n and zˉq=∑jqjzj\bar z_q=\sum_jq_jz_j,

max⁡i(Aq)i=max⁡z∈Kdet⁡(z,zˉq).\max_i(Aq)_i=\max_{z\in K}\det(z,\bar z_q).

Bounding this support value by ε\varepsilon certifies (q,q)(q,q) as an ε\varepsilon-Nash equilibrium within the given population. These results are now cited before Theorem 4.5, and Appendix P.2 gives the coordinate correspondence. Section 6 explains how our bound quantifies the noisy evaluations needed to find a certified mixture within a fixed policy population.


Q6: Please state the constant CC in Lemma 2.1. Using your explicit constants, what is the smallest kk for which the lower bound in Theorem 3.1(i) exceeds the verifier's upper bound at concrete values such as ε=δ=0.05\varepsilon=\delta=0.05? If no realistic kk exists, the abstract and Figure 1 should state that the separation is asymptotic.

A: Thank you for requesting an explicit quantitative comparison. We can take C=35,000C=35{,}000 and c=10,240c=10{,}240 in Lemma 2.1. At ε=δ=0.05\varepsilon=\delta=0.05, the explicit lower bound in Theorem J.1 has crossover scale log⁡log⁡k≈1.23×108\log\log k\approx1.23\times10^8 against the verifier cap. Thus, no realistic dimension exhibits a numerical separation under these bounds. The abstract and Figure 1 now state explicitly that the separation is asymptotic. For the explicit verification bound, each response-arm observation has centered sub-Gaussian proxy at most 22. An explicit median-elimination schedule gives

NME(d,q,β)≤4609dq−2log⁡2560β.N_{\mathrm{ME}}(d,q,\beta) \leq 4609d q^{-2}\log\frac{2560}{\beta}.

We use PAC accuracy q=3ε/7q=3\varepsilon/7 and scalar estimation accuracy a=ε/32a=\varepsilon/32. Allocating failure probabilities α/4\alpha/4 to each PAC search and α/6\alpha/6 to each scalar estimate, and accepting when both estimated regrets are at most ε/2\varepsilon/2, yields

Nver≤[4609(73)2+6(32)2](n+m)ε−2log⁡10240α≤35,000(n+m)ε−2log⁡10240α.\begin{aligned} N_{\mathrm{ver}} &\leq \left[4609\left(\frac73\right)^2+6(32)^2\right] (n+m)\varepsilon^{-2}\log\frac{10240}{\alpha}\\\\ &\leq 35{,}000(n+m)\varepsilon^{-2} \log\frac{10240}{\alpha}. \end{aligned}

Here the three scalar estimates and their ceilings are absorbed using n+m≥2n+m\ge2. With q+2a=55ε/112q+2a=55\varepsilon/112, acceptance reports regret bounds below ε\varepsilon. The choice a=ε/32a=\varepsilon/32 also preserves the 7ε/167\varepsilon/16 completeness margin used in Appendix Q. For the crossover calculation, let Nk=⌊k/2⌋N_k=\lfloor k/2\rfloor, sk=⌊(log⁡2k)/2⌋s_k=\lfloor(\log_2 k)/2\rfloor, and rk=⌊sk/2⌋r_k=\lfloor s_k/2\rfloor. For k≥240k\geq 2^{40}, Theorem J.1 gives an explicit lower bound that exceeds the verifier cap when

15(Nk−sk+1)rk512skkkl⁡(0.95,0.05rk)>70,000log⁡(204,800).\frac{15(N_k-s_k+1)r_k}{512s_k k} \operatorname{kl}\left(0.95,\frac{0.05}{r_k}\right) > 70{,}000\log(204{,}800).

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/4)

Appendix J.1 brackets the smallest integer satisfying this explicit comparison by 123035968<log⁡log⁡kmin⁡<123035969123035968<\log\log k_{\min}<123035969. This threshold concerns the stated bounds and dictionary choice, not an optimized verifier. Lemma 2.1 now gives the explicit constants, and Appendices C and D prove the sampling budget and compatible margins. Section 3 includes the crossover discussion. The abstract states: “This is an asymptotic separation in the action dimension.”


Q7: Do you agree that, as Corollary 3.3(a) shows, the separation disappears once log⁡(1/δ)≳log⁡log⁡k\log(1/\delta)\gtrsim\log\log k? If so, please state this in the abstract.

A: Thank you for raising this question about the confidence regime. Corollary I.3(a) proves that discovery matches the verification scale for k×kk\times k games when log⁡(1/δ)≥log⁡(2ek)\log(1/\delta)\ge\log(2ek). At log⁡(1/δ)≳log⁡log⁡k\log(1/\delta)\gtrsim\log\log k, Theorem 3.1 no longer certifies a separation, but this does not establish matching rates. The abstract now states the high-confidence condition explicitly. For k≥2k\ge2, 0<ε≤1/160<\varepsilon\le1/16 and 0<δ≤1/40<\delta\le1/4, set L=log⁡(1/δ)L=\log(1/\delta). Theorem 3.1 and Equation (4) give

ckε−2[log⁡log⁡(ek)+L]≤Mk,k(ε,δ)≤Ckε−2[log⁡(ek)+L].c k\varepsilon^{-2}\bigl[\log\log(ek)+L\bigr] \le \mathcal M_{k,k}(\varepsilon,\delta) \le C k\varepsilon^{-2}\bigl[\log(ek)+L\bigr].

Lemma 2.1 gives an O(kε−2L)O(k\varepsilon^{-2}L) verification bound under its stated accuracy margin. Section 3 now distinguishes these ranges and points to the full matching-regime statement in Appendix I. The abstract states: “When log⁡(1/δ)≥log⁡(2ek)\log(1/\delta)\ge\log(2ek), unrestricted finding matches the verification scale.”


Q8: Apart from the decoding reduction, which step in the proofs of Theorems I.1 and J.1 differs from the argument for Theorem 8 in Kalyanakrishnan et al. (2012)?

A: Thank you for asking us to clarify the proof's contribution. The shared-error-budget aggregation is inherited from Kalyanakrishnan et al. (2012, Theorem 8). We do not claim it as new. The main additional contribution is the construction of hard matrix games that makes this argument yield a fixed-accuracy lower bound. The technical differences are summarized below.

AspectKalyanakrishnan et al. (2012)Our results
ProblemBernoulli Explore-mm. The learner identifies an mm-subset of near-optimal arms.Gaussian cell-query matrix games. The learner identifies an approximate Nash equilibrium.
Hard instancesInstances indexed by I∈Im−1∪ImI\in\mathcal I_{m-1}\cup\mathcal I_m. Arm means are determined by subset membership.Theorem I.1 uses a dense Rademacher code and paired rows. Theorem J.1 introduces an intersection dictionary.
Neighboring instancesII and I∪jI\cup\\{j\\} differ only in arm jj, whose mean changes from 1/2−2ε1/2-2\varepsilon to 1/2+2ε1/2+2\varepsilon.T=S∖iT=S\setminus\\{i\\} differs from SS only on the corresponding row pair, with entrywise shift h=8εh=8\varepsilon.
Change of measurePathwise Bernoulli likelihood-ratio comparison, with Markov and Kolmogorov bounds.Stopped-transcript Gaussian KL identity applied to adaptive queries on the changed row pair.
Error aggregationA shared error budget across adjacent layers yields the log⁡(m/δ)\log(m/\delta) factor.The same aggregation principle is used. We do not claim this step as new.
Fixed-accuracy witnessNo mixed-strategy probability-mass constraint arises in the bandit construction.The additive witness in Theorem I.1 requires s≤1/(16ε)s\leq 1/(16\varepsilon). The intersection witness in Theorem J.1 removes this restriction.

The key additional ingredient is the intersection witness in Theorem J.1. It assigns total mass 16ε16\varepsilon to columns that are simultaneously positive on all labels in the hidden subset. This mass is independent of ss. In particular, for N≥2s≥4N\geq 2s\geq4, d=⌈256⋅2slog⁡(256N)⌉d=\lceil256\cdot2^s\log(256N)\rceil, n≥2Nn\geq2N, m≥d+1m\geq d+1, 0<ε≤1/160<\varepsilon\leq1/16, and 0<δ<1/20<\delta<1/2, Theorem J.1 gives, with r=⌊s/2⌋r=\lfloor s/2\rfloor,

Mn,mG(ε,δ)≥15(N−s+1)r512ε2skl⁡(1−δ,δr).\mathcal M_{n,m}^{\mathrm G}(\varepsilon,\delta) \geq \frac{15(N-s+1)r}{512\varepsilon^2s} \operatorname{kl}\left(1-\delta,\frac{\delta}{r}\right).

This permits s=Θ(log⁡N)s=\Theta(\log N) at fixed accuracy and yields the Ω(kε−2log⁡log⁡k)\Omega(k\varepsilon^{-2}\log\log k) lower bound for balanced games.

We have revised the proof overview in Section 3 to distinguish the inherited aggregation argument from our game-specific construction. We have also clarified the comparison in Related Work and added Remark J.2 explaining why the intersection witness removes the accuracy-dependent restriction.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.