Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
Yuepeng Yang, Yuxin Chen, Yuejie Chi
cs.LG, math.OC, stat.ML
Submitted: 2026-08-06
Updated: 2026-08-10
License: http://creativecommons.org/licenses/by/4.0/
The gist: Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.
Terminology
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 epsilon-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 sigma. Let H 0 and H sigma denote the nominal and robust optimal bias spans, respectively. We identify sigma 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 SA over epsilon squared H 0,H sigma, & epsilon sigma H 0, H 0,H sigma+ sigma H sigma squared, & epsilon sigma H 0. 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.
Sources
- Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
- Discounted Reinforcement Learning Is Not an Optimization Problem
- Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis
- Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP
- Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values
- Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks