Finite-Sample Regret Analysis of Nash Q-Learning with Random-Feature Approximation

We study finite-sample equilibrium learning in episodic two-player zero-sum {Markov} games, where {Nash} equilibria coincide with minimax saddle points and {Nash}-Q style value iteration provides a natural algorithmic template. Existing analyses of {Nash}-Q style learning provide regret guarantees in tabular settings and under fixed linear realizability, but do not explicitly account for representation error arising from scalable nonlinear approximation. We propose an optimistic {Nash} Q-learning framework that replaces tabular/linear value representations with a hyperdimensional random-feature embedding—instantiated via random {Fourier} features to approximate a shift-invariant kernel—while retaining tractable ridge-style updates and per-state minimax stage-game computation. Our main results establish high-probability regret guarantees that decompose into a statistical uncertainty term governed by an effective-dimension complexity measure and an explicit additive approximation term induced by random-feature kernel approximation. The approximation term decreases with the embedding dimension, yielding a principled approximation–estimation tradeoff and recovering linear-style finite-sample behavior in the realizable regime. Empirically, we evaluate on a suite of episodic zero-sum benchmarks spanning tabular and continuous-state settings and observe stable learning behavior and performance trends consistent with the predicted dependence on representation dimension.