On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes

arXiv:2403.06806v1 Announce Type: new
Abstract: 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\left({\frac{1}{T}}\right),$ which translates to $O\left({\log(T)}\right)$ regret, where $T$ represents the number of iterations. Prior work on performance bounds for discounted …

abstract analysis arxiv context convergence cs.lg cs.sy decision eess.sy focus global gradient horizon markov policy processes shows spaces state tabular type