Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies
Choosing a small set of backup plans when the world's rules are unclear
When a robot or AI system doesn't know exactly how its environment works, it must either commit to one strategy that works everywhere or prepare a separate plan for every possibility—both costly choices. This work shows how to prepare just a handful of versatile strategies in advance, then pick the best one once uncertainty clears up. The researchers found that jumping from one strategy to two cuts regret roughly in half, with diminishing returns afterward.
Real autonomous systems—from medical devices to industrial controllers—often face regulatory or computational limits on how many different behaviors they can deploy. This approach lets operators hedge against uncertainty cheaply by preparing only 2–5 strategies instead of one inflexible plan or hundreds of custom ones. In settings where the true environment reveals itself seconds before execution begins, it's a practical middle ground between adaptation and constraint.