aiqbench analysis
This research introduces an optimization framework for Interval Markov Decision Processes that synthesizes multi-strategies to maximize action choices while guaranteeing robustness against uncertain transition probabilities. By formulating the problem as a mixed-integer linear program, the method scales efficiently to systems with hundreds of thousands of states without sacrificing permissiveness compared to standard single-policy approaches.
Optimization-Based Robust Permissive Synthesis for Interval MDPs
arXiv:2510.03481v3 Announce Type: replace Abstract: We present an optimization-based framework for robust permissive synthesis for Interval Markov Decision Processes (IMDPs). While robust IMDP controller synthesis typically yields a single policy and most permissive-synthesis methods assume exact transition models, we synthesize multi-strategies that retain multiple actions while guaranteeing satisfaction of probabilistic reachability or expected-reward specifications under all admissible transition probabilities. We formulate the problem as a mixed-integer linear program (MILP) that maximizes the number of enabled state--action pairs subject to robust Bellman constraints. We develop two encodings: a direct vertex-enumeration formulation and a dualization-based formulation that avoids explicit enumeration of uncertainty-polytope vertices and has size linear in the number of successor transitions. Experiments on four benchmark domains show that both encodings achieve the same optimal permissiveness and scale to IMDPs with hundreds of thousands of states. Compared with standard robust single-policy synthesis, the resulting multi-strategies retain substantially more action choices.
Abstract:We present an optimization-based framework for robust permissive synthesis for Interval Markov Decision Processes (IMDPs). While robust IMDP controller synthesis typically yields a single policy and most permissive-synthesis methods assume exact transition models, we synthesize multi-strategies that retain multiple actions while guaranteeing satisfaction of probabilistic reachability or expected-reward specifications under all admissible transition probabilities. We formulate the problem as a mixed-integer linear program (MILP) that maximizes the number of enabled state--action pairs subject to robust Bellman constraints. We develop two encodings: a direct vertex-enumeration formulation and a dualization-based formulation that avoids explicit enumeration of uncertainty-polytope vertices and has size linear in the number of successor transitions. Experiments on four benchmark domains show that both encodings achieve the same optimal permissiveness and scale to IMDPs with hundreds of thousands of states. Compared with standard robust single-policy synthesis, the resulting multi-strategies retain substantially more action choices.
Robotics (cs.RO); Systems and Control (eess.SY)
arXiv:2510.03481 [cs.RO]
(or arXiv:2510.03481v3 [cs.RO] for this version)
From: Khang V. Huynh [view email] [v1] Fri, 3 Oct 2025 19:57:43 UTC (381 KB) [v2] Mon, 16 Mar 2026 16:33:00 UTC (380 KB) [v3] Thu, 10 Sep 2026 23:14:24 UTC (376 KB)
Full text under the publisher's open licence · 191 words
Related coverage
[AINews] not much happened today
Latent Space · Sep 18, 2026
Informe de riesgos de la IA de frontera (febrero–marzo de 2026)
METR · May 19, 2026
Frontier AI Risk Report (February–March 2026)
METR · May 19, 2026
Frontier Risk Report (February to March 2026)
METR · May 19, 2026