arXiv：cs.LG（机器学习，全量分类）· Han Zhong, Yinyu Ye·· 14 小时前AI 评分37
鲁棒马尔可夫决策过程的线性规划表示与强多项式算法
Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
AI 导读
研究针对奖励与转移均为有理多面体状态-动作矩形不确定性的鲁棒马尔可夫决策过程（RMDP），通过编码有限步鲁棒策略迭代构造单一线性规划，其最优解可恢复鲁棒最优值及全部最优平稳随机策略。
正文
Abstract:We study linear programming (LP) representations and strongly polynomial algorithms for robust Markov decision processes (RMDPs) with rational polyhedral state-action rectangular uncertainty in rewards and transitions. By encoding a finite sequence of robust policy-iteration steps, we construct a single LP whose optimal solutions recover the robust optimal value and all optimal stationary randomized policies. At fixed discount, the LP has polynomial dimension and encoding length and can be constructed in strongly polynomial time. We also develop a general complexity analysis of robust policy iteration that combines the cost of minimizing over uncertainty sets with the number of iterations needed to evaluate a policy. For a fixed discount factor, we use this analysis to improve the known complexity bounds for $\ell_1$ and $\ell_\infty$ RMDPs and establish new strongly polynomial bounds for general interval, weighted $\ell_1$, and Wasserstein RMDPs, as well as turn-based stochastic games with these uncertainty sets.
| Subjects: | Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC) |
| Cite as: | arXiv:2610.02131 [cs.LG] |
| (or arXiv:2610.02131v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.02131 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Han Zhong [view email]
[v1]
Thu, 1 Oct 2026 17:41:29 UTC (60 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org