On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
CoRR(2024)
摘要
We present the first finite time global convergence analysis of policy
gradient in the context of infinite horizon average reward Markov decision
processes (MDPs). Specifically, we focus on ergodic tabular MDPs with finite
state and action spaces. Our analysis shows that the policy gradient iterates
converge to the optimal policy at a sublinear rate of
O(1/T), which translates to O(log(T))
regret, where T represents the number of iterations. Prior work on
performance bounds for discounted reward MDPs cannot be extended to average
reward MDPs because the bounds grow proportional to the fifth power of the
effective horizon. Thus, our primary contribution is in proving that the policy
gradient algorithm converges for average-reward MDPs and in obtaining
finite-time performance guarantees. In contrast to the existing discounted
reward performance bounds, our performance bounds have an explicit dependence
on constants that capture the complexity of the underlying MDP. Motivated by
this observation, we reexamine and improve the existing performance bounds for
discounted reward MDPs. We also present simulations to empirically evaluate the
performance of average reward policy gradient algorithm.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要