Towards Provable Log Density Policy Gradient
Pulkit Katdare Anant Joshi Katherine Driggs-Campbell
Policy gradient methods are a vital ingredient behind the success of modern
reinforcement learning. Modern policy gradient methods, although successful,
introduce a residual error in gradient estimation. In this work, we argue that
this residual term is significant and correcting for it could potentially
improve sample-complexity of reinforcement learning methods. To that end, we
propose log density gradient to estimate the policy gradient, which corrects
for this residual error term. Log density gradient method computes policy
gradient by utilising the state-action discounted distributional formulation.
We first present the equations needed to exactly find the log density gradient
for a tabular Markov Decision Processes (MDPs). For more complex environments,
we propose a temporal difference (TD) method that approximates log density
gradient by utilizing backward on-policy samples. Since backward sampling from
a Markov chain is highly restrictive we also propose a min-max optimization
that can approximate log density gradient using just on-policy samples. We also
prove uniqueness, and convergence under linear function approximation, for this
min-max optimization. Finally, we show that the sample complexity of our
min-max optimization to be of the order of $m^{-1/2}$, where $m$ is the number
of on-policy samples. We also demonstrate a proof-of-concept for our log
density gradient method on gridworld environment, and observe that our method
is able to improve upon the classical policy gradient method by a clear margin,
thus indicating a promising novel direction to develop reinforcement learning
algorithms that require fewer samples.