Robust $\phi$-Divergence MDPs

Chin Pang Ho, Marek Petrik, Wolfram WiesemannNeurIPS 2022 · OpenReview

TL;DR

Robust Markov Decision Processes (RMDPs) protect against estimation errors in transition probabilities but are notoriously slow to compute. This paper introduces a lightning-fast algorithmic framework for solving RMDPs constrained by non-linear $\phi$-divergence ambiguity sets (like KL divergence and $\chi^2$-distance). By reducing the core optimization step to highly structured, low-dimensional simplex projections, their method achieves speeds orders of magnitude faster than commercial solvers and state-of-the-art first-order methods.

What Problem Does This Paper Address?

Standard Markov Decision Processes (MDPs) assume you know the environment's transition probabilities perfectly. In reality—especially in reinforcement learning—you have to estimate these parameters from sampled data. Policies optimized on these flawed estimates are brittle and can fail catastrophically when deployed in the real world.

Robust MDPs (RMDPs) fix this by optimizing for the worst-case scenario within a set of plausible transition probabilities, known as an "ambiguity set." Statistically, the best ambiguity sets are defined by non-linear $\phi$-divergences (like Kullback-Leibler divergence or $\chi^2$-distance).

Visualizations of different ambiguity sets on a probability simplex.

However, solving RMDPs with these sets is computationally brutal. It requires solving a complex convex optimization problem at every single step of value iteration. Existing approaches rely on heavy-duty commercial solvers (like MOSEK) or slow first-order methods, making robust planning prohibitively slow even for moderately sized problems.

Methods

The authors dramatically speed up the robust Bellman update by exploiting the mathematical structure of $\phi$-divergences.

Normally, the robust Bellman update is a complex max-min problem. The authors use the minimax theorem to flip this problem and solve it via bisection. The magic happens in the inner loop: the problem is reduced to a "generalized projection onto a probability simplex."

Instead of throwing a generic convex solver at this $S$-dimensional projection problem (where $S$ is the number of states), the authors mathematically prove that for specific $\phi$-divergences, the problem can be collapsed into a 1D or 2D convex optimization problem.

Summary of supported $\phi$-divergences and their improved computational complexities compared to prior art.

These reduced problems can then be solved almost instantly using simple, tailored techniques like bisection, binary search, or sorting.

Datasets

The authors evaluate their algorithms using synthetically generated random RMDP instances. They randomly generate nominal transition probabilities, rewards, and uncertainty budgets to test the computational speed of the projection problems and the full robust Bellman updates. No standard real-world benchmarks were used, as the paper's focus is purely on algorithmic runtime and theoretical complexity.

Key Insights and Ideas

  • Dimensionality reduction is a cheat code: You don't need a heavy-duty solver for $\phi$-divergence RMDPs. The inherent structure of these statistical distances allows an $S$-dimensional optimization problem to be safely collapsed into 1 or 2 dimensions.
  • Robustness for the price of a logarithm: A standard, non-robust Bellman update takes $\mathcal{O}(S^2 \log A)$ time. The authors' robust version takes $\mathcal{O}(S^2 \cdot A \log A)$ or $\mathcal{O}(S^2 \log S \cdot A)$. This means adding rigorous statistical robustness only incurs a logarithmic computational overhead regarding the state/action space.
  • Exact solutions exist for some metrics: For Variation Distance and $\chi^2$-distance, the projection problem doesn't even need iterative approximation. It can be solved exactly in $\mathcal{O}(S \log S)$ time using sorting and binary search.

Key Results

  • Crushing Commercial Solvers: The proposed algorithms are roughly two orders of magnitude (100x) faster than the commercial state-of-the-art solver MOSEK 9.3 when solving the core projection problem.
  • Beating State-of-the-Art First-Order Methods: Compared to a recent first-order method designed specifically for RMDPs, the new algorithm is significantly faster. By the 5th Bellman iteration on a KL-divergence set, the proposed method is roughly 20x faster.
  • Scalability: As the state and action spaces grow (tested up to $S=3000$ and $S=A=300$), the speedup ratio compared to baseline solvers actually increases, proving that the theoretical time complexity advantages hold up in practice.

Limitations and Future Work

The primary limitation of this work is that it strictly focuses on the model-based setting with tabular representations (finite, discrete states and actions). It does not directly address continuous state spaces or function approximation (like neural networks).

The authors explicitly note this and suggest that future work should focus on extending these fast projection techniques to scalable model-free algorithms. Because fast Bellman operators are a building block for Q-learning and policy gradients, these findings could eventually pave the way for highly efficient, robust Deep Reinforcement Learning.

Summary updated

Abstract

In recent years, robust Markov decision processes (MDPs) have emerged as a prominent modeling framework for dynamic decision problems affected by uncertainty. In contrast to classical MDPs, which only account for stochasticity by modeling the dynamics through a stochastic process with a known transition kernel, robust MDPs additionally account for ambiguity by optimizing in view of the most adverse transition kernel from a prescribed ambiguity set. In this paper, we develop a novel solution framework for robust MDPs with $s$-rectangular ambiguity sets that decomposes the problem into a sequence of robust Bellman updates and simplex projections. Exploiting the rich structure present in the simplex projections corresponding to $\phi$-divergence ambiguity sets, we show that the associated $s$-rectangular robust MDPs can be solved substantially faster than with state-of-the-art commercial solvers as well as a recent first-order solution scheme, thus rendering them attractive alternatives to classical MDPs in practical applications.
BibTeX
@inproceedings{ho2022robust,
  author = {Chin Pang Ho and Marek Petrik and Wolfram Wiesemann},
  title = {{Robust $\textbackslash\{\}phi$-Divergence MDPs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=ugtCiOaxPc},
}
Figure