aiqbench analysis
This research addresses model uncertainty in Markov decision processes by introducing a method to synthesize small sets of policies that minimize worst-case regret before execution. The proposed KAPS algorithm provides an exact solution for selecting optimal policy subsets, demonstrating significant performance gains when expanding from one to two adaptable strategies rather than larger ensembles. This work advances the theoretical foundations and practical deployment limits of robust sequential decision-making systems in uncertain environments.
Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies
arXiv:2608.02509v1 Announce Type: new 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.
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.
Artificial Intelligence (cs.AI); Machine Learning (cs.LG)
arXiv:2608.02509 [cs.AI]
(or arXiv:2608.02509v1 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2608.02509 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 289 words
Related coverage
Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
arXiv · Jul 24, 2026
Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime
arXiv · Oct 6, 2026
Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation
arXiv · Oct 6, 2026
An Efficient Minimax-Optimal Algorithm for Adversarial $m$-Set Bandits
arXiv · Aug 26, 2026