Variance-Reduced Policy Gradient Approaches for Infinite Horizon Average
  Reward Markov Decision Processes
Swetha Ganesh Washim Uddin Mondal Vaneet Aggarwal
We present two Policy Gradient-based methods with general parameterization in
the context of infinite horizon average reward Markov Decision Processes. The
first approach employs Implicit Gradient Transport for variance reduction,
ensuring an expected regret of the order $\tilde{\mathcal{O}}(T^{3/5})$. The
second approach, rooted in Hessian-based techniques, ensures an expected regret
of the order $\tilde{\mathcal{O}}(\sqrt{T})$. These results significantly
improve the state of the art of the problem, which achieves a regret of
$\tilde{\mathcal{O}}(T^{3/4})$.