When Less Is More: Polylogarithmic Nash-Value Regret in Bandit Matrix Games

In an unknown zero-sum matrix game, an adaptive opponent can choose which payoff column the learner observes. Under informed-bandit feedback, the opponent sees the learner's mixed row strategy before choosing a column; the learner then observes that column and one sampled payoff. Existing polylogarithmic Nash-value regret guarantees for this feedback model cover $2\times 2$ games. We obtain such a guarantee for square games of any dimension with a unique, fully mixed equilibrium. Our algorithm, Instance-Certified Restricted-Face Learning (IC-RF), plays against the columns it has learned well enough. If the opponent withholds other columns, this restricted game yields a value surplus; if those columns appear, the learner gains samples. A multiscale ledger uses the surplus to finance learning across accuracy levels without knowing the game's separation parameters. An observable saddle certificate then starts local refinement. At any fixed confidence level, the resulting high-probability Nash-value regret is $O(\log T\log \log T)$, with a constant polynomial in the instance difficulty parameters. Experiments under best-response opponents show lower finite-horizon regret than established bandit baselines in most tested settings, while revealing slow certification in some higher-dimensional noisy games.