提出高效可靠的鲁棒马尔可夫决策模型求解方法，支持多种不确定性设定。
Solving Robust Markov Decision Processes: Generic, Reliable, Efficient
- 基于随机博弈理论，无需显式构造博弈模型，通用性强。
- 可处理百万状态的鲁棒MDP问题，求解速度比现有工具快数个数量级。
- 提供计算过程中的精度保证，适合需要高可靠性的决策系统。
马尔可夫决策过程（MDP）是建模概率环境下序列决策的经典框架。在鲁棒MDP（RMDP）中，每种动作关联一个概率分布的不确定性集，用于刻画转移概率不精确的情况。本文基于与随机博弈的已知理论联系，提出一种通用、可靠且高效的RMDP求解框架。该方法对模型和目标均具广泛适应性：支持区间、L¹或L²球、多面体等多种不确定性集，适用于长期平均奖励、无折扣总奖励及随机最短路径等目标。其可靠性体现在不仅在极限下收敛，且在计算过程中可提供精度保证；高效性源于避免显式构建底层随机博弈，使原型实现相比现有工具提速数个数量级，可在一分钟内求解含百万状态的RMDP问题。
原文摘要 · Abstract (English)
Markov decision processes (MDP) are a well-established model for sequential decision-making in the presence of probabilities. In robust MDP (RMDP), every action is associated with an uncertainty set of probability distributions, modelling that transition probabilities are not known precisely. Based on the known theoretical connection to stochastic games, we provide a framework for solving RMDPs that is generic, reliable, and efficient. It is *generic* both with respect to the model, allowing for a wide range of uncertainty sets, including but not limited to intervals, $L^1$- or $L^2$-balls, and polytopes; and with respect to the objective, including long-run average reward, undiscounted total reward, and stochastic shortest path. It is *reliable*, as our approach not only converges in the limit, but provides precision guarantees at any time during the computation. It is *efficient* because -- in contrast to state-of-the-art approaches -- it avoids explicitly constructing the underlying stochastic game. Consequently, our prototype implementation outperforms existing tools by several orders of magnitude and can solve RMDPs with a million states in under a minute.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。