Formal proof of vanilla policy gradient convergence

Question

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, 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 the mentioned 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 this, 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.

Answer 1

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. – Piotr Rarus

Adding more to Piotr Rarus comment:

It appears that the convergence of the REINFORCE Monte Carlo algorithm for vanilla policy gradient procedures has not been formally proven. The literature, including Sutton and Barto's book on reinforcement learning, only provides claims of convergence under certain stochastic approximation step size requirements.

The paper by Bottou on online stochastic gradient descent algorithms provides a general proof of convergence, but it is not clear if it is applicable to the REINFORCE algorithm due to the changing distribution of the on-policy state.

Bertsekas and Tsitsiklis provide convergence proof for updating the rules of the form

$x_{t+1} = x_t +\gamma_t (s_t + w_t)$

where,

• $w_t$ is some error with $\mathbb{E}[w_t | \mathcal{F}_t] = 0$ for ascending $\sigma$-fields $\mathcal{F}_t$.

This may be applicable to the REINFORCE algorithm, but further analysis would be needed to verify this.

Overall, it seems that a formal proof of convergence for the REINFORCE Monte Carlo algorithm for vanilla policy gradient procedures is currently lacking.

Answer 2

I have written one, also following what Sutton's book does, but make each transform step more clearly(hopefully...)

\begin{align} \nabla J(\theta) &= \nabla v_\pi(s_0) \\ &= \nabla [\sum_a \pi(a|s_0)q_\pi(s_0, a)] \\ &= \sum_a[\nabla \pi(a|s_0) q_\pi(s_0, a) + \pi(a|s_0) \nabla q_\pi(s_0, a)] \ \ // by \ product \ derivative \ formula \\ &= \sum_a[\nabla \pi(a|s_0) q_\pi(s_0, a) +\pi(a|s_0) \nabla \sum_{s_1, r} p_\pi(s_1, r|s_0, a)(r +v_\pi(s_1)) ] \ \ // constant \ r \ has \ derivative \ 0 \\ &= \sum_a[\nabla \pi(a|s_0) q_\pi(s_0, a) +\pi(a|s_0) \sum_{s_1} p_\pi(s_1|s_0, a)\nabla v_\pi(s_1) ] \\ &\ \ \ (expanding \ v_\pi(s1) \ recusively ...)\\ &= \sum_a[\nabla \pi(a|s_0) q_\pi(s_0, a)] + \\ &\ \ \ \ \sum_a [\pi(a|s_0) \sum_{s_1} p_\pi(s_1|s_0, a)]* \sum_{a'}[\nabla \pi(a'|s_1) q_\pi(s_1, a') ]+ \\ &\ \ \ \ \sum_a[\pi(a|s_0) \sum_{s_1} p_\pi(s_1|s_0, a)]* \sum_{a'}[\pi(a'|s_1) \sum_{s_2} p_\pi(s_2|s_1, a')\nabla v_\pi(s_2) ] \\ & \ \ \ （keep \ recursion..., you \ could \ see \ there \ exists \ a \ form \ of \ \sum_a [\nabla \pi(a|s_x) q_\pi(s_x, a)]，\\ & \ \ \ multiplied \ by \ prob \ of \ s_0 \ to \ s_x \ following \ all \ possible \ routes. \ To \ simplify， \\ &\ \ \ let \ P_\pi(s_0, s_x,k) \ represent \ prob \ of \ s_0 \ to \ s_x \ after \ k \ steps.）\\ &= \sum_{s_x \in S} \sum_{k=1}^{\infty}P_\pi(s_0 \to s_x, k) \sum_a \nabla\pi(a|s_x)q_\pi(s_x, a) \\ &= \sum_{s_x \in S} [\sum_{k=1}^{\infty}P_\pi(s_0 \to s_x, k)] \sum_a \nabla \pi(a|s_x)q_\pi(s_x, a) \\ &\ \ \ ([...] represents \ prob \ of \ an \ episode \ ended \ in \ state \ s_x. Denote \ it \ \eta_\pi(s_x)) \\ &= \sum_{s_x \in S} \eta_\pi(s_x) \sum_a \nabla \pi(a|s_x)q_\pi(s_x, a) \\ &= [\sum_{s}\eta_\pi(s) ] * \sum_{s_x} \frac{\eta_\pi(s_x)}{\sum_{s}\eta_\pi(s)} * \sum_a \nabla \pi(a|s_x)q_\pi(s_x, a) \\ &= [\sum_{s}\eta_\pi(s) ] * \mu_\pi(s_x) * \sum_a \nabla \pi(a|s_x)q_\pi(s_x, a) \\ &\varpropto \mu_\pi(s_x) * \sum_a \nabla \pi(a|s_x)q_\pi(s_x, a) \\ Q.E.D. \\ \end{align}