Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies
2026-08-03 • Artificial Intelligence
Artificial IntelligenceMachine Learning
AI summaryⓘ
The authors study how to make good decisions when you're unsure about how the environment works, represented by multiple possible models called UMDPs. Instead of making one policy for all models or one for each model, they focus on preparing a limited number (k) of policies in advance and picking the best one after learning which model applies. They introduce a method called k-adaptable policy synthesis and show it’s a hard problem, then provide an algorithm named KAPS to solve it efficiently. Their tests show big improvements by moving from one to two policies, and their method works well compared to others when only one policy is used.
Uncertain Markov decision processesPolicy synthesisSequential decision-makingMinimax regretNP-hardBranch-and-bound algorithmModel uncertaintyAdaptive policiesOptimization
Authors
Sterre Lutz, Daniël Vos, Matthijs T. J. Spaan, Anna Lukina
Abstract
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.