# An Efficient Solution to s-Rectangular Robust Markov Decision Processes

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 31 Jan 2023.

## Builds on (most cited first, 13 of 13)

- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Maximum Entropy RL (Provably) Solves Some Robust RL Problems](https://mlsanity.com/paper/2103.06257/) (2021)
- [Equivalence Between Policy Gradients and Soft Q-Learning](https://mlsanity.com/paper/1704.06440/) (2017)
- [Assessing Generalization in Deep Reinforcement Learning](https://mlsanity.com/paper/1810.12282/) (2018)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [Robust Markov Decision Process: Beyond Rectangularity](https://mlsanity.com/paper/1811.00215/) (2018)
- [Model-Based Reinforcement Learning Exploiting State-Action Equivalence](https://mlsanity.com/paper/1910.04077/) (2019)
- [Robust Entropy-regularized Markov Decision Processes](https://mlsanity.com/paper/2112.15364/) (2021)

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

- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learning](https://mlsanity.com/paper/2505.18447/) (2025)
- [Distributionally Robust Deep Q-Learning](https://mlsanity.com/paper/2505.19058/) (2025)
- [ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty](https://mlsanity.com/paper/2510.11899/) (2025)
- [Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Sets](https://mlsanity.com/paper/2510.19950/) (2025)
- [Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2609.28792/) (2026)

## Abstract (arXiv)

We present an efficient robust value iteration for texttts-rectangular robust Markov Decision Processes (MDPs) with a time complexity comparable to standard (non-robust) MDPs which is significantly faster than any existing method. We do so by deriving the optimal robust Bellman operator in concrete forms using our Lp water filling lemma. We unveil the exact form of the optimal policies, which turn out to be novel threshold policies with the probability of playing an action proportional to its advantage.