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?