14
$\begingroup$

So I stumbled upon this question, where the author asks for a proof of vanilla policy gradient procedures. The answer provided points to some literature, but the formal proof is nowhere to be included. Looking at Sutton,Barto- Reinforcement Learning, they claim that convergence of the REINFORCE Monte Carlo algorithm is guaranteed under stochastic approximation step size requirements, but they do not seem to reference any sources that go into more detail.

I am curious whether or not anybody actually has a formal proof ready for me to read. I found a paper, which goes into detail for proving convergence of a general online stochastic gradient descent algorithm, see https://leon.bottou.org/publications/pdf/online-1998.pdf , section 2.3.

However, I am not sure if the proof provided in the paper is applicable to the algorithm described in Sutton's book. In said algorithm, one obtains samples which, assuming that the policy did not change, is in expectation at least proportional to the gradient. However, the analytic expression of the gradient

$$\nabla J(\theta) \propto \sum_s \mu(s)\sum_a q_{\pi}(s,a)\nabla \pi(a|s,\theta)$$

depends on the on policy state distribution $\mu(s)$ which changes when we update $\theta$. Therefore, when updating during the algorithm, the distribution changes.

Any help would be greatly appreciated. Bottou's paper, which I linked above states that the event is drawn from a fixed probability distribution, which is not the case here.

EDIT:

So after reading some more papers, I found https://dspace.mit.edu/bitstream/handle/1721.1/3462/P-2404-38121470.pdf which is a paper of Bertsekas and Tsitsiklis. They argue that under certain assumptions convergence to a stationary point is guaranteed, where one has an update rule of the form

$$x_{t+1} = x_t +\gamma_t (s_t + w_t)$$ and $w_t$ is some error with $$\mathbb{E}[w_t | \mathcal{F}_t] = 0$$ for ascending $\sigma$-fields $\mathcal{F}_t$, which can be thought of conditioning on the trajectory $x_0,s_0\dots,x_{t-1},s_{t-1},w_{t-1},x_t,s_t$. I believe that this might be a solution, since we need an expected gradient update given the past parameter $x_t$, which determines the sampling distribution which is exactly what the policy gradient theorem guarantees. I'd be happy if someone could verify this.

$\endgroup$
  • 1
    $\begingroup$ Proof will only work for convex spaces. Though not even once have I stumbled upon one in professional work. Drift analysis might be more helpful for non-convex spaces. $\endgroup$ – Piotr Rarus - Reinstate Monica Nov 26 '19 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.