Abstract
Robust Markov Decision Processes (RMDPs) provide a framework for learning policies that remain effective under environment perturbations. However, traditional RMDP solvers are often model-based, requiring $O(|S|^2|A|)$ memory, and rely on "strong oracles" to solve inner distributionally robust optimization (DRO) problems. This paper presents a model-free approach that eliminates these requirements. By reformulating the RMDP into a penalized version, we enable the use of stochastic gradient methods, reducing memory complexity to $O(|S||A|)$. We provide sample complexity guarantees for both generative and Markovian data regimes and validate our approach through numerical experiments.
Introduction
Reinforcement Learning (RL) has seen significant success in controlled environments, yet deploying these models in the real world remains challenging due to "distribution shift." A policy trained in a simulator may fail if the real-world transition dynamics differ even slightly. Robust MDPs (RMDPs) address this by optimizing for the worst-case scenario within a defined uncertainty set of transition probabilities.
Despite their theoretical appeal, RMDPs suffer from two primary practical limitations:
- Memory Complexity: Model-based RMDPs must store transition matrices, leading to $O(|S|^2|A|)$ storage requirements, which is infeasible for large state spaces.
- The Oracle Assumption: Most algorithms assume a "strong oracle" exists to solve the inner optimization problem (finding the worst-case transition). In practice, this is computationally expensive and often unrealistic.
A Penalized, Model-Free Approach
To overcome these hurdles, we propose a shift from the standard constrained RMDP formulation to a penalized RMDP. Instead of restricting the transition function to a hard uncertainty set, we introduce a penalty term based on the divergence from a reference distribution.
Lagrangian Duality and SGA
By applying Lagrangian duality to the Distributionally Robust Optimization (DRO) problem, we transform the search for the worst-case distribution into a risk minimization problem. This reformulation is crucial because it allows the use of Stochastic Gradient Ascent (SGA) to solve the inner problem incrementally, removing the need for a perfect oracle.
Memory Efficiency
Our algorithm follows a Q-learning-style update. Because it operates in a model-free regime, it only needs to store the Q-values and auxiliary variables for the gradient steps, maintaining a memory footprint of $O(|S||A|)$. This matches the memory efficiency of standard, non-robust Q-learning and represents a significant improvement over model-based methods.
Theoretical Insights
A key contribution of this work is proving the statistical equivalence between the penalized RMDP and the traditional constrained RMDP. This ensures that the computational benefits of the penalized form do not come at the cost of robustness.
Furthermore, we address the stability of the optimization. Constrained DRO problems often suffer from unbounded gradients, which can lead to algorithmic instability. We demonstrate that our penalized formulation provides bounded gradients, ensuring the convergence of stochastic gradient methods. For Markovian data (where samples are collected along a trajectory rather than queried arbitrarily), we utilize the Poisson equation method to handle dependent noise, proving that the algorithm still converges to the optimal robust policy.
Sample Complexity
We analyze the algorithm's performance across two data regimes:
- Generative Model: In this setting, where any state-action pair can be sampled at will, we establish a convergence rate of $O(T^{-1/2})$.
- Markovian Data: In the more realistic trajectory-based setting, we achieve a rate of $O(T^{-1/3})$. While the Markovian rate is slightly slower, it represents a significant theoretical milestone for a model-free robust algorithm.
Experimental Validation
We validated our findings using a 10-state, 2-action chain MDP. The environment was designed to test the agent's ability to handle perturbations in transition probabilities, with rewards concentrated at one end of the chain. Our experiments confirmed that:
- The robust value function correctly approaches the non-robust value function as the robustness parameter $\lambda$ increases.
- The algorithm efficiently finds the optimal robust policy without the $O(|S|^2|A|)$ memory overhead.
- The stochastic gradient approach successfully replaces the need for an optimization oracle, maintaining convergence even with sampled data.
Conclusion
This work bridges the gap between the theoretical robustness of RMDPs and the practical requirements of large-scale RL. By removing the need for model estimation and optimization oracles, we provide a path toward more scalable and reliable reinforcement learning in uncertain environments. Future work will focus on improving the Markovian convergence rate to $O(T^{-1/2})$ and exploring instance-dependent analysis to further refine sample efficiency.
Summary updated