提出高效求解大规模马尔可夫决策过程的新方法
Efficient Solving of Large Single Input Superstate Decomposable Markovian Decision Process
- 基于单输入超状态分解结构，重构状态转移图
- 实现平均奖励与折扣奖励问题的精确高效求解
- 适合处理具有特定结构的大规模决策问题
求解马尔可夫决策过程（MDP）仍是序列决策中的核心挑战，尤其在状态空间庞大、需长期优化时。贝尔曼动态规划算法中的策略评估步骤在无限时域设定（如平均奖励或折扣奖励）下计算成本高昂。在马尔可夫链中，聚合与分解技术长期用于利用结构分解降低复杂度。本文将此思想拓展至一类结构性MDP：单输入超状态可分解马尔可夫决策过程（SISDMDP），该结构结合了Chiu的单输入分解与Robertazzi的单循环递归性质。当某策略诱导出此结构时，其转移图可分解为具有中心化递归的交互组件。我们据此提出一种精确且高效的策略评估方法，可推广至平均奖励与折扣奖励两类问题，实现可扩展求解。
原文摘要 · Abstract (English)
Solving Markov Decision Processes (MDPs) remains a central challenge in sequential decision-making, especially when dealing with large state spaces and long-term optimization criteria. A key step in Bellman dynamic programming algorithms is the policy evaluation, which becomes computationally demanding in infinite-horizon settings such as average-reward or discounted-reward formulations. In the context of Markov chains, aggregation and disaggregation techniques have for a long time been used to reduce complexity by exploiting structural decompositions. In this work, we extend these principles to a structured class of MDPs. We define the Single-Input Superstate Decomposable Markov Decision Process (SISDMDP), which combines Chiu's single-input decomposition with Robertazzi's single-cycle recurrence property. When a policy induces this structure, the resulting transition graph can be decomposed into interacting components with centralized recurrence. We develop an exact and efficient policy evaluation method based on this structure. This yields a scalable solution applicable to both average and discounted reward MDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。