# Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 3 Aug 2026.

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

- [Robust and Adaptive Planning under Model Uncertainty](https://mlsanity.com/paper/1901.02577/) (2019)
- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [K-Adaptability in Two-Stage Mixed-Integer Robust Optimization](https://mlsanity.com/paper/1706.07097/) (2017)
- [Policies Grow on Trees: Model Checking Families of MDPs](https://mlsanity.com/paper/2407.12552/) (2024)
- [Multi-Environment MDPs with Prior and Universal Semantics](https://mlsanity.com/paper/2602.10938/) (2026)
- [Learning Contextual Runtime Monitors for Safe AI-Based Autonomy](https://mlsanity.com/paper/2601.20666/) (2026)

## Abstract (arXiv)

Sequential decision-making in real-world applications often involves uncertainty about the environment's model. Uncertain Markov decision processes (UMDPs) represent the possible environments as a set of MDPs with shared states and actions but potentially different transition probabilities and rewards. Optimizing a single policy across all possible MDPs may sacrifice performance, while preparing an individually optimized policy for every MDP may violate operational, regulatory, or interpretability constraints on the number of policies that can be prepared and deployed. We consider settings in which model uncertainty is resolved shortly before execution, allowing the most suitable policy to be selected from a limited set prepared in advance. We introduce k-adaptable policy synthesis, which optimizes such a set of k policies under a minimax-regret objective. We prove that the problem is NP-hard and develop KAPS, an exact nested branch-and-bound algorithm with problem-specific bounds and heuristics. KAPS jointly optimizes which MDPs share a policy and the policies themselves. Experiments across various UMDP benchmarks show that the largest reduction in regret consistently occurs when increasing from one to two policies. In the single-policy setting, KAPS is competitive with existing methods in solution quality and proves optimality substantially more often.