稳健马尔可夫决策过程的线性规划表示与强多项式算法
Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
精选理由
为鲁棒决策提供统一线性规划表示与强多项式算法，提升求解效率。
AI 摘要
arXiv:2610.02131v1 公告类型：新 摘要：我们研究具有奖励和转移的有理多面体状态-动作矩形不确定性的稳健马尔可夫决策过程（RMDPs）的线性规划（LP）表示与强多项式算法。通过编码一系列有限的稳健策略迭代步骤，我们构造了一个单一的LP，其最优解可以恢复稳健最优值以及所有最优平稳随机策略。在折扣因子固定时，该LP具有多项式规模的维数和编码长度，并且可以在强多项式时间内构造。我们还对稳健策略迭代进行了通用复杂度分析，将不确定性集合上的最小化成本与评估一个策略所需的迭代次数结合起来。对于固定的折扣因子，我们利用这一分析改进了已知的 $\ell_1$ 和 $\ell_\infty$ RMDPs 的复杂度界，并为一般区间型、加权 $\ell_1$ 型和 Wasserstein 型RMDPs，以及具有这些不确定性集合的轮流行动随机博弈，建立了新的强多项式复杂度界。