证明了鲁棒MDP策略迭代可在强多项式时间内求解
Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs
- 提出针对L∞不确定性鲁棒MDP的策略迭代算法
- 在固定折扣因子下，算法时间复杂度为强多项式
- 解决该类问题长期存在的算法复杂性难题
马尔可夫决策过程（MDPs）是序贯决策的基础模型。鲁棒MDPs（RMDPs）通过允许转移概率的不确定性，并针对最坏情况下的不确定性实现优化而加以扩展。特别是具有L∞不确定性集的(s,a)-矩形RMDPs构成一个基础且表达力强的模型：它包含经典MDPs和回合制随机博弈。本文研究该模型在折扣收益下的优化问题。对于这些优化模型，多项式时间与强多项式时间算法的存在性是一个基本问题。对于标准MDPs，线性规划对任意折扣因子均提供多项式时间算法，而Ye的经典工作建立了固定折扣因子下的强多项式时间结果。将此类结果推广到RMDPs一直是一个重要开放问题。本文证明：对于固定折扣因子的(s,a)-矩形L∞ RMDPs，鲁棒策略迭代算法可在强多项式时间内运行，从而解决了这一关键算法问题。
原文摘要 · Abstract (English)
Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilities and optimizing against the worst-case realization of that uncertainty. In particular, $(s, a)$-rectangular RMDPs with $L_\infty$ uncertainty sets form a fundamental and expressive model: they subsume classical MDPs and turn-based stochastic games. We consider this model with discounted payoffs. The existence of polynomial and strongly-polynomial time algorithms is a fundamental problem for these optimization models. For MDPs, linear programming yields polynomial-time algorithms for any arbitrary discount factor, and the seminal work of Ye established strongly--polynomial time for a fixed discount factor. The generalization of such results to RMDPs has remained an important open problem. In this work, we show that a robust policy iteration algorithm runs in strongly-polynomial time for $(s, a)$-rectangular $L_\infty$ RMDPs with a constant (fixed) discount factor, resolving an important algorithmic question.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。