mlsanityData to 14 Oct 2026

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

arXiv 2506.07040 ↗First posted 8 Jun 2025cs.LG cs.AI stat.MLcited by 4

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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 tildeO(ε-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 tildeO(ε-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.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 22 of its 37 references that are in the map. First posted on arXiv 8 Jun 2025.

Builds on

22 of 37 references.

Closest ancestors · 6

Same direction, newest first

  1. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach26 May
  2. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm21 May
  3. 2025Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning15 May
  4. 2025From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes25 Apr
  5. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning24 Feb
  6. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach26 Jul

Other references · 16

  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 185
  3. 2018The Limits and Potentials of Deep Learning for Roboticscited by 104
  4. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  5. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  6. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  7. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 36
  8. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
  9. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 31
  10. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  11. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
  12. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
4 more
  1. 2023Robust Average-Reward Markov Decision Processescited by 22
  2. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  3. 2021Learning Robust Policy against Disturbance in Transition Dynamics via State-Conservative Policy Optimizationcited by 18
  4. 2023First-order Policy Optimization for Robust Policy Evaluationcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2026Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductionscited by 2
  2. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  3. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  4. 2026Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDP
  2. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximation
  3. 2026Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
  4. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
  5. 2026Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values
  6. 2021Robust Entropy-regularized Markov Decision Processes
  7. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
  8. 2024Optimistic Q-learning for average reward and episodic reinforcement learning