# Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization

arXiv: https://arxiv.org/abs/2602.11387 · HTML: https://mlsanity.com/paper/2602.11387/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 54 references that are in the map.
- First posted on arXiv 11 Feb 2026.

## Builds on (most cited first, 30 of 37)

- [Sim-to-Real Transfer of Robotic Control with Dynamics Randomization](https://mlsanity.com/paper/1710.06537/) (2017)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Discovered Policy Optimisation](https://mlsanity.com/paper/2210.05639/) (2022)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Lipschitz Continuity in Model-based Reinforcement Learning](https://mlsanity.com/paper/1804.07193/) (2018)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Policy Gradient for Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13589/) (2023)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes](https://mlsanity.com/paper/2309.01922/) (2023)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)
- [Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2301.00858/) (2023)
- [Efficient Policy Iteration for Robust Markov Decision Processes via Regularization](https://mlsanity.com/paper/2205.14327/) (2022)
- [Model-Free Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2305.10504/) (2023)
- [Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic](https://mlsanity.com/paper/2301.12083/) (2023)
- [High-probability sample complexities for policy evaluation with linear function approximation](https://mlsanity.com/paper/2305.19001/) (2023)
- [Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets](https://mlsanity.com/paper/2305.19004/) (2023)
- [A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach](https://mlsanity.com/paper/2407.18878/) (2024)
- [Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs](https://mlsanity.com/paper/2404.02108/) (2024)
- [Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality](https://mlsanity.com/paper/2312.03618/) (2023)
- [Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation](https://mlsanity.com/paper/2406.01762/) (2024)
- [Optimistic Q-learning for average reward and episodic reinforcement learning](https://mlsanity.com/paper/2407.13743/) (2024)
- [First-order Policy Optimization for Robust Policy Evaluation](https://mlsanity.com/paper/2307.15890/) (2023)
- [Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2505.10007/) (2025)
- [Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles](https://mlsanity.com/paper/2403.11925/) (2024)
- [Linear Mixture Distributionally Robust Markov Decision Processes](https://mlsanity.com/paper/2505.18044/) (2025)

## Built on by (most cited first, 1 of 1)

- [Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values](https://mlsanity.com/paper/2603.00945/) (2026)

## 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.