Minimax-Optimal Learning for Robust Average-Reward MDPs.

Decision-making systems often operate under uncertainty about the exact dynamics of their environment. Distributionally robust Markov Decision Processes (MDPs) provide a framework to handle this by considering a set of possible transition kernels rather than a single nominal one. This research focuses on the average-reward criterion, a common objective in continuous decision-making, and investigates how many samples are truly needed to learn a policy that is robustly optimal. The study establishes precise upper and lower bounds for the minimax total sample complexity required to achieve an epsilon-optimal robust policy. A key finding is the identification of a "perturbation scale" that distinguishes between high- and low-tolerance regimes, where the sample complexity behaves differently. The total sample complexity is shown to comprise a term similar to nominal MDP results and an additional robustness-specific term that emerges in the low-tolerance regime. These optimal rates are achieved through novel reduction-based plug-in procedures. These procedures intelligently select between nominal and robust reductions, along with their discount factors, either by using known span parameters or by calibrating these choices directly from data. This work provides fundamental theoretical insights into the sample efficiency of learning robust policies in uncertain environments.