# Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 51 references that are in the map.
- First posted on arXiv 3 Sep 2023.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Maximum Entropy RL (Provably) Solves Some Robust RL Problems](https://mlsanity.com/paper/2103.06257/) (2021)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12909/) (2020)
- [Reinforcement Learning with Perturbed Rewards](https://mlsanity.com/paper/1810.01032/) (2018)
- [Reinforcement Learning with a Corrupted Reward Channel](https://mlsanity.com/paper/1705.08417/) (2017)
- [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)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [Regularized Policies are Reward Robust](https://mlsanity.com/paper/2101.07012/) (2021)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Your Policy Regularizer is Secretly an Adversary](https://mlsanity.com/paper/2203.12592/) (2022)
- [Efficient Policy Iteration for Robust Markov Decision Processes via Regularization](https://mlsanity.com/paper/2205.14327/) (2022)
- [Regularization Matters in Policy Optimization](https://mlsanity.com/paper/1910.09191/) (2019)
- [Manipulating Reinforcement Learning: Poisoning Attacks on Cost Signals](https://mlsanity.com/paper/2002.03827/) (2020)
- [Reinforcement Learning for Linear Quadratic Control is Vulnerable Under Cost Manipulation](https://mlsanity.com/paper/2203.05774/) (2022)

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

- [Correlated Proxies: A New Definition and Improved Mitigation for Reward Hacking](https://mlsanity.com/paper/2403.03185/) (2024)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [State Entropy Regularization for Robust Reinforcement Learning](https://mlsanity.com/paper/2506.07085/) (2025)
- [Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes](https://mlsanity.com/paper/2502.09432/) (2025)
- [Discrete Compositional Generation via General Soft Operators and Robust Reinforcement Learning](https://mlsanity.com/paper/2506.17007/) (2025)
- [Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values](https://mlsanity.com/paper/2603.00945/) (2026)
- [Best-Effort Policies for Robust Markov Decision Processes](https://mlsanity.com/paper/2508.07790/) (2025)
- [Robust General Utility for Reinforcement Learning](https://mlsanity.com/paper/2608.03562/) (2026)

## Abstract (arXiv)

In robust Markov decision processes (RMDPs), it is assumed that the reward and the transition dynamics lie in a given uncertainty set. By targeting maximal return under the most adversarial model from that set, RMDPs address performance sensitivity to misspecified environments. Yet, to preserve computational tractability, the uncertainty set is traditionally independently structured for each state. This so-called rectangularity condition is solely motivated by computational concerns. As a result, it lacks a practical incentive and may lead to overly conservative behavior. In this work, we study coupled reward RMDPs where the transition kernel is fixed, but the reward function lies within an α-radius from a nominal one. We draw a direct connection between this type of non-rectangular reward-RMDPs and applying policy visitation frequency regularization. We introduce a policy-gradient method and prove its convergence. Numerical experiments illustrate the learned policy's robustness and its less conservative behavior when compared to rectangular uncertainty.