Avoiding Model Estimation in Robust Markov Decision Processes with a Generative Model

Wenhao Yang, Han Wang, Tadashi Kozuno, Emma Jordan, Zhihua Zhang

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:

  1. Memory Complexity: Model-based RMDPs must store transition matrices, leading to $O(|S|^2|A|)$ storage requirements, which is infeasible for large state spaces.
  2. 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:

  1. The robust value function correctly approaches the non-robust value function as the robustness parameter $\lambda$ increases.
  2. The algorithm efficiently finds the optimal robust policy without the $O(|S|^2|A|)$ memory overhead.
  3. 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

Abstract

Robust Markov Decision Processes (MDPs) are getting more attention for learning a robust policy which is less sensitive to environment changes. There are an increasing number of works analyzing sample-efficiency of robust MDPs. However, most works study robust MDPs in a model-based regime, where the transition probability needs to be estimated and requires $\mathcal{O}(|\mathcal{S}|^2|\mathcal{A}|)$ storage in memory. A common way to solve robust MDPs is to formulate them as a distributionally robust optimization (DRO) problem. However, solving a DRO problem is non-trivial, so prior works typically assume a strong oracle to obtain the optimal solution of the DRO problem easily. To remove the need for an oracle, we first transform the original robust MDPs into an alternative form, as the alternative form allows us to use stochastic gradient methods to solve the robust MDPs. Moreover, we prove the alternative form still preserves the role of robustness. With this new formulation, we devise a sample-efficient algorithm to solve the robust MDPs in a model-free regime, from which we benefit lower memory space $\mathcal{O}(|\mathcal{S}||\mathcal{A}|)$ without using the oracle. Finally, we validate our theoretical findings via numerical experiments and show the efficiency to solve the alternative form of robust MDPs.
BibTeX
@misc{yang2023avoiding,
  author = {Wenhao Yang and Han Wang and Tadashi Kozuno and Emma Jordan and Zhihua Zhang},
  title = {{Avoiding Model Estimation in Robust Markov Decision Processes with a Generative Model}},
  year = {2023},
  eprint = {2302.01248},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.01248},
}
Figure