Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Yuepeng Yang; Yuxin Chen; Yuejie Chi

cs.LGAug 6, 2026

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Authors: Yuepeng Yang, Yuxin Chen, Yuejie Chi

Organizations: *Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.

Abstract

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an $\varepsilon$ -optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over $(s,a)$ -rectangular total-variation uncertainty sets of radius at most $σ$ . Let $H_0$ and $H_σ$ denote the nominal and robust optimal bias spans, respectively. We identify $σH_0$ as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is $NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases}$ Here $S$ and $A$ are the numbers of states and actions, and $N$ is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.

Explore similar work

Jun 8, 2025cs.LG

Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning

We study model-free methods for distributionally robust infinite-horizon average-reward Markov decision processes (MDPs). We present non-asymptotic convergence analyses of Q-learning and actor-critic algorithms for robust average-reward MDPs under contamination, total-variation distance, and Wasserstein uncertainty sets. A key ingredient of our analysis is showing that the optimal robust Bellman operator is a strict contraction with respect to a carefully designed semi-norm. This property enables a stochastic approximation update that learns the optimal robust

Q

-function with

\tilde{\mathcal{O}}(ε^{-2})

dependence on the target accuracy. We also establish robust TD convergence bounds whose constants are uniform over all stationary policies, yielding an efficient data-driven routine for robust critic estimation. Building on this, we introduce an actor-critic algorithm that learns an

ε

-optimal robust policy with

\tilde{\mathcal{O}}(ε^{-2})

dependence on the target accuracy. We provide numerical simulations to illustrate the qualitative behavior of the proposed algorithms. Our results contribute to the theoretical foundations of robust planning under model misspecification and to model-free approaches for building robust long-run policies directly from simulation data.

Yang Xu, Swetha Ganesh, Vaneet Aggarwal

Q-Learning Soft Actor-Critic Bellman Equation Critic-Free Reinforcement Learning Classical Planning

Ask PDF

May 18, 2025cs.LG

Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

Robust reinforcement learning (RL) under the average-reward criterion is essential for long-term decision-making, particularly when the environment may differ from its training dynamics. However, most existing studies focus on model-based settings and provide only asymptotic guarantees, hindering their principled understanding and practical deployment, especially in data-limited scenarios. We aim to close this gap by proposing a model-free algorithm, \textbf{Robust Halpern Iteration (RHI)}. We first design our algorithm based on a black-box sampling oracle, which can estimate the worst-case performance accurately. We then derive the finite sample complexity of RHI under the generative model setting, assuming the sampling oracle. To concretely design such an oracle, we propose a

K

-order multi-level Monte-Carlo estimator, which is shown to have a lower bias compared to prior methods. We further instantiate our design for multiple uncertainty models, including KL and

χ^2

divergence sets, and show that our RHI algorithm achieves an

\varepsilon

-optimal robust policy with a sample complexity of

\tilde{\mathcal{O}}\left( \frac{SA\mathcal{H}^2}{\varepsilon^{(2+o(1))}}\right)

, where

S,A

are the number of states and actions, and

\mathcal{H}

is the robust optimal span. Our result asymptotically matches the best complexity in robust average reward RL.

Zachary Roch, George Atia, Yue Wang

Model-Free Reinforcement Learning Optimal Policies Sample Complexity Alternating Direction Method Of Multiplier

Ask PDF

Jun 12, 2026cs.LG

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms

N

. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in

N

. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an

O(1/\sqrt{N})

optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution of our work is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.

Tianhao Wu, Matthew Zurek, Weina Wang +1

Markov Decision Processes Sample Complexity Lyapunov Function

Ask PDF