Setting. The paper studies two-player zero-sum matrix games with an unknown payoff matrix A∈[−1,1]n×m. Each query to cell (i,j) returns a fresh N(Aij,1) sample. For every matrix in this class, the strategy must return (x^,y^) whose row and column regrets are both at most ε with probability at least 1−δ. 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⊤Ay and the column-response arms x⊤Aej.
- Estimate the two selected responses and the candidate payoff from fresh samples.
- Accept if GapA≤ε/4, and reject if either regret exceeds ε.
The procedure uses O((n+m)ε−2log(1/α)) queries.
Unrestricted discovery. The upper bound is O(ε−2[nlogn+mlogm+(n+m)log(1/δ)]), 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/δ).
- A dense construction uses rows (i,±) with payoffs ±(ai(j)−8ε1{i∈U}) together with a public sign dictionary.
In the dense construction, any output whose regrets are both at most ε satisfies FU(y)≤3ε, so the threshold ui(y)>4ε recovers the hidden set U from every valid output. A change-of-measure argument between deletion neighbors T=S∖{i} that share a single error budget then yields Ω(Nε−2log(s/δ)). Two witnesses determine the resulting rates:
- The additive witness requires s≤1/(16ε). When ε≲logk/k, it yields Θ(kε−2logk).
- The intersection witness uses 2s columns, which allows s=Θ(logk) at fixed ε, and yields Ω(kε−2[loglogk+log(1/δ)]).
Bounded rank. The algorithm maintains an invertible cross C=AI,J and a surrogate matrix B=A:,JC−1AI,:. 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, 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 ∣detC∣≥(ε/16)s stabilizes the empirical inverse.
The query bound is Cr(n+m)ε−(4r+6)log(cr/δ). Combined with the rank-one lower bound, this gives Θr,ε((n+m)log(1/δ)).
Rank one and rank two.
- Rank one: two absolute-value scans find a pivot with bounded ratios, and the identity Aij=AibAaj/Aab then reduces the game to a 2×2 game on the extreme rows and columns. This yields Θ((n+m)ε−2log(1/δ)) and tolerates entrywise perturbations of up to ε/16.
- Rank two, rectangular: O((n+m)ε−2L3log(L/δ)), where L=log(2/ε).
- Rank two, skew-symmetric: O(nε−2[log(2+min{n,ε−1})+log(1/δ)]).
- 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.
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.
The rewritten lower-bound overview begins: