Pointwise Query Complexity in Noisy Zero-Sum Games: A Bellman Characterization and Nonlinear Confidence Profiles
We study the expected number of noisy entry queries required to find an approximate Nash equilibrium of an arbitrary real zero-sum matrix game. Algorithms must be correct on every payoff matrix and every permitted sub-Gaussian observation law; their expected cost is evaluated separately at each target matrix. We characterize this robust pointwise optimum, within a factor of two and at the original accuracy and confidence, by finite lists of statistical alternatives, intersections of acceptable-answer sets, and a posterior Bellman recursion. The characterization holds both for independent entry observations and for conditionally sub-Gaussian observations with predictable kernels. We construct square games with a nonlinear confidence profile of order dL + min{d², d^(3/2)L}, where L = log(1/δ), and prove that no universal additive representation H1 log(1/δ) + H2 exists with confidence-independent nonnegative terms. The same obstruction holds for stopping-time quantiles. Finally, a family with pointwise expected complexity O(d) forces every single globally correct policy to use Ω(d²) queries on some member.
Authors
- Zheng Zhijie (ORCID: https://orcid.org/0009-0006-7610-0691)
Institutions
- Peking University (CN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24346640
- Primary Topic
- Game Theory and Applications
- Type
- preprint