Why does REINFORCE work at all?

Question

Here's a screenshot of the popular policy-gradient algorithm from Sutton and Barto's book -

I understand the mathematical derivation of the update rule - but I'm not able to build intuition as to why this algorithm should work in the first place. What really bothers me is that we start off with an incorrect policy (i.e. we don't know the parameters $\theta$ yet), and we use this policy to generate episodes and do consequent updates.

Why should REINFORCE work at all? After all, the episode it uses for the gradient update is generated using the policy that is parametrized by parameters $\theta$ which are yet to be updated (the episode isn't generated using the optimal policy - there's no way we can do that).

I hope that my concern is clear and I request y'all to provide some intuition as to why this works! I suspect that, somehow, even though we are sampling an episode from the wrong policy, we get closer to the right one after each update (monotonic improvement). Alternatively, we could be going closer to the optimal policy (optimal set of parameters $\theta$) on average.

So, what's really going on here?

Answer 1

The key to REINFORCE working is the way the parameters are shifted towards $G \nabla \log \pi(a|s, \theta)$.

Note that $ \nabla \log \pi(a|s, \theta) = \frac{ \nabla \pi(a|s, \theta)}{\pi(a|s, \theta)}$. This makes the update quite intuitive - the numerator shifts the parameters in the direction that gives the highest increase in probability that the action will be repeated, given the state, proportional to the returns - this is easy to see because it is essentially a gradient ascent step. The denominator controls for actions that would have an advantage over other actions because they would be chosen more frequently, by inversely scaling with respect to the probability of the action being taken; imagine if there had been high rewards but the action at time $t$ has low probability of being selected (e.g. 0.1) then this will multiply the returns by 10 leading to a larger update step in the direction that would increase the probability of this action being selected the most (which is what the numerator controls for, as mentioned).

That is for the intuition -- to see why it does work, then think about what we've done. We defined an objective function, $v_\pi(s)$, that we are interested in maximising with respected to our parameters $\theta$. We find the derivative of this objective with respect to our parameters, and then we perform gradient ascent on our parameters to maximise our objective, i.e. to maximise $v_\pi(s)$, thus if we keep performing gradient ascent then our policy parameters will converge (eventually) to values that maximise $v$ and thus our policy would be optimal.