# Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processes

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2020.

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

- [RAMBO-RL: Robust Adversarial Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.12581/) (2022)
- [Risk-Averse Bayes-Adaptive Reinforcement Learning](https://mlsanity.com/paper/2102.05762/) (2021)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Robust Anytime Learning of Markov Decision Processes](https://mlsanity.com/paper/2205.15827/) (2022)
- [Reward-Free Curricula for Training Robust World Models](https://mlsanity.com/paper/2306.09205/) (2023)
- [Robust Reinforcement Learning Under Minimax Regret for Green Security](https://mlsanity.com/paper/2106.08413/) (2021)
- [Model-based Offline RL via Robust Value-Aware Model Learning with Implicitly Differentiable Adaptive Weighting](https://mlsanity.com/paper/2603.08118/) (2026)
- [Coevolutionary Algorithm for Building Robust Decision Trees under Minimax Regret](https://mlsanity.com/paper/2312.09078/) (2023)
- [Robust Deep Reinforcement Learning against Adversarial Behavior Manipulation](https://mlsanity.com/paper/2406.03862/) (2024)
- [On Minimizing Adversarial Counterfactual Error in Adversarial RL](https://mlsanity.com/paper/2406.04724/) (2024)

## Abstract (arXiv)

The parameters for a Markov Decision Process (MDP) often cannot be specified exactly. Uncertain MDPs (UMDPs) capture this model ambiguity by defining sets which the parameters belong to. Minimax regret has been proposed as an objective for planning in UMDPs to find robust policies which are not overly conservative. In this work, we focus on planning for Stochastic Shortest Path (SSP) UMDPs with uncertain cost and transition functions. We introduce a Bellman equation to compute the regret for a policy. We propose a dynamic programming algorithm that utilises the regret Bellman equation, and show that it optimises minimax regret exactly for UMDPs with independent uncertainties. For coupled uncertainties, we extend our approach to use options to enable a trade off between computation and solution quality. We evaluate our approach on both synthetic and real-world domains, showing that it significantly outperforms existing baselines.