Yang, Chen, Chi pin exact sample complexity for robust average-reward MDPs

Distributionally robust Markov decision processes (MDPs) are the standard framework for sequential decision-making when the true transition model is uncertain. A team led by Yuepeng Yang, Yuxin Chen, and Yuejie Chi has now closed a major gap in the theory: exactly how many samples are needed to learn an epsilon-optimal robust policy under the average-reward criterion. Assuming a generative model that samples from the nominal kernel, with performance evaluated over (s,a)-rectangular total-variation uncertainty sets of radius sigma, the authors prove matching upper and lower bounds on minimax sample complexity, up to logarithmic factors.

The result splits into two regimes separated by the scale sigma*H0, where H0 and Hsigma are the nominal and robust optimal bias spans. In the high-tolerance regime (epsilon >= sigma*H0), sample complexity scales as SA/epsilon^2 * min{H0, Hsigma}, matching the classical non-robust average-reward MDP rate. In the low-tolerance regime, an additional sigma*Hsigma^2 term appears, reflecting the intrinsic cost of being robust when the policy must be highly accurate. The authors achieve these rates with two plug-in reduction procedures: a span-informed version that uses known span parameters to select the reduction type and discount factor, and a span-agnostic version that calibrates both choices entirely from data. This gives both a theoretical benchmark and a practical algorithm for robust reinforcement learning.