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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Pointwise Query Complexity in Noisy Zero-Sum Games: A Bellman Characterization and Nonlinear Confidence Profiles

Zheng Zhijie
2 links
Zenodo (CERN European Organization for Nuclear Research)
Game Theory and Applications
preprint

Pointwise Query Complexity in Noisy Zero-Sum Games: A Bellman Characterization and Nonlinear Confidence Profiles

Zheng Zhijie
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Peking University (CN)
Game Theory and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon