Geometric Policy Iteration for Markov Decision Processes
Geometric Policy Iteration for Markov Decision Processes
复制标题
马尔可夫决策过程的几何策略迭代
DOI：
10.1145/3534678.3539478
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
J. D. Loera
中科院分区：
文献类型：
--
作者：
Yue Wu;J. D. Loera
最近发现的有限折扣马尔可夫决策过程（MDP）值函数的多面体结构有助于理解强化学习的成功。我们调查的价值函数多面体更详细，并使用超平面安排的多面体边界的特征。我们进一步表明，价值空间是一个联盟的许多细胞相同的超平面安排，并将其与多面体的经典线性规划制定的MDPs。受这些几何性质的启发，我们提出了一种新的算法，几何策略迭代（GPI），以解决折扣MDPs。GPI通过切换到映射到值函数多面体边界的动作来更新单个状态的策略，然后立即更新值函数。这种新的更新规则旨在更快地提高值，而不影响计算效率。此外，我们的算法允许异步更新的状态值，这是更灵活和有利的传统的策略迭代相比，当状态集是大的。我们证明了GPI的复杂性达到了最佳已知的界限O|?|超过1 - γ log 1超过1-γ的策略迭代，并以经验证明GPI对各种大小的MDP的强度。
Recently discovered polyhedral structures of the value function for finite discounted Markov decision processes (MDP) shed light on understanding the success of reinforcement learning. We investigate the value function polytope in greater detail and characterize the polytope boundary using a hyperplane arrangement. We further show that the value space is a union of finitely many cells of the same hyperplane arrangement, and relate it to the polytope of the classical linear programming formulation for MDPs. Inspired by these geometric properties, we propose a new algorithm, Geometric Policy Iteration (GPI), to solve discounted MDPs. GPI updates the policy of a single state by switching to an action that is mapped to the boundary of the value function polytope, followed by an immediate update of the value function. This new update rule aims at a faster value improvement without compromising computational efficiency. Moreover, our algorithm allows asynchronous updates of state values which is more flexible and advantageous compared to traditional policy iteration when the state set is large. We prove that the complexity of GPI achieves the best known bound O|?|over 1 - γ log 1 over 1-γ of policy iteration and empirically demonstrate the strength of GPI on MDPs of various sizes.