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

Yang Xu; Swetha Ganesh; Vaneet Aggarwal

cs.LGJun 8, 2025

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

Authors: Yang Xu, Swetha Ganesh, Vaneet Aggarwal

Organizations: Purdue University, West Lafayette, Indiana, USA 47907

Abstract

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.

Explore similar work

Oct 2, 2025cs.LG

Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximation

Distributionally robust reinforcement learning seeks policies that remain effective when the deployment environment differs from the one that generated the training data. We study model-free robust Q-learning with

χ^2

uncertainty sets and linear function approximation, using data from a single trajectory of an unknown nominal MDP. Evaluating the

χ^2

robust Bellman target introduces the square root of a conditional second moment, which cannot be estimated unbiasedly from one transition, while the projected robust Bellman operator need not be contractive. We address these obstacles through a variational reformulation of the robust Bellman target and a blockwise frozen-target scheme, and establish a finite-time error bound relative to the optimal robust Q-function for every

γ\in(0,1)

. A neural-network experiment illustrates how the variational target can be used in a continuous-state nonlinear-control task.

Saptarshi Mandal, Yashaswini Murthy, R. Srikant

Q-Learning Model-Free Reinforcement Learning Bellman Equation Finite Time Analysis Convergence

Ask PDF

Aug 6, 2026cs.LG

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

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.

Yuepeng Yang, Yuxin Chen, Yuejie Chi

Markov Decision Processes Optimal Policies Sample Complexity Decisions

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