Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization
Not on the map. Why?
Abstract (arXiv)
We study robust Markov decision processes (RMDPs) with general policy parameterization under s-rectangular and non-rectangular uncertainty sets. Prior work is largely limited to tabular policies, and hence either lacks sample complexity guarantees or incurs high computational cost. Our method reduces the average reward RMDPs to entropy-regularized discounted robust MDPs, restoring strong duality and enabling tractable equilibrium computation. We prove novel Lipschitz and Lipschitz-smoothness properties for general policy parameterizations that extends to infinite state spaces. To address infinite-horizon gradient estimation, we introduce a multilevel Monte Carlo gradient estimator with tildeO(ε-2) sample complexity, a factor of O(ε-2) improvement over prior work. Building on this, we design a projected gradient descent algorithm for s-rectangular uncertainty (O(ε-5)) and a Frank--Wolfe algorithm for non-rectangular uncertainty (O(ε-4) discounted, O(ε-10.5) average reward), significantly improving prior results in both the discounted setting and average reward setting. Our work is the first one to provide sample complexity guarantees for RMDPs with general policy parameterization beyond (s, a)-rectangularity. It also provides the first such guarantees in the average reward setting and improves existing bounds for discounted robust MDPs.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 37 of its 54 references that are in the map. First posted on arXiv 11 Feb 2026.
Builds on
37 of 54 references.
References · 37
- 2017Sim-to-Real Transfer of Robotic Control with Dynamics Randomizationcited by 616
- 2018Stochastic Variance-Reduced Policy Gradientcited by 103
- 2022Discovered Policy Optimisationcited by 103
- 2018Lipschitz Continuity in Model-based Reinforcement Learningcited by 90
- 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
- 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
- 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 59
- 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
- 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
- 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
- 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
- 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 29
25 more
- 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
- 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
- 2023Robust Average-Reward Markov Decision Processescited by 22
- 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
- 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
- 2022Efficient Policy Iteration for Robust Markov Decision Processes via Regularizationcited by 19
- 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
- 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
- 2023Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Setscited by 15
- 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
- 2023Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimalitycited by 12
- 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
- 2024Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximationcited by 11
- 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
- 2025Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learningcited by 7
- 2023First-order Policy Optimization for Robust Policy Evaluationcited by 6
- 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oraclescited by 6
- 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
- 2021Robust Entropy-regularized Markov Decision Processescited by 4
- 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
- 2024An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networkscited by 3
- 2025Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gaincited by 3
- 2025Why DPO is a Misspecified Estimator and How to Fix Itcited by 3
- 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 2
- 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.