Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization
This work addresses the problem of sample efficiency and computational tractability in robust MDPs for researchers and practitioners in reinforcement learning, representing a significant advance beyond prior incremental improvements.
The paper tackles robust Markov decision processes with general policy parameterization under s-reectangular and non-rectangular uncertainty sets, achieving improved sample complexity guarantees, such as a multilevel Monte Carlo gradient estimator with Õ(ε⁻²) sample complexity and algorithms with O(ε⁻⁵) for s-rectangular and O(ε⁻⁴) for non-rectangular discounted settings.
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 $\tilde{\mathcal{O}}(ε^{-2})$ sample complexity, a factor of $\mathcal{O}(ε^{-2})$ improvement over prior work. Building on this, we design a projected gradient descent algorithm for s-rectangular uncertainty ($\mathcal{O}(ε^{-5})$) and a Frank--Wolfe algorithm for non-rectangular uncertainty ($\mathcal{O}(ε^{-4})$ discounted, $\mathcal{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.