# Why does REINFORCE work at all?

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?

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.

• Hmm, I still don't get it. The action that you speak of, is part of an initially incorrect policy. Why should I believe that it will get me closer to the real policy? Aug 15 '20 at 17:09
• This is the same way that Monte Carlo methods work, it is just a form of the generalised policy iteration. Loosely speaking, you run an episode according to your policy to 'evaluate' it and then you perform the gradient ascent updates to improve the policy. Aug 15 '20 at 17:48
• What do you mean why should you "believe" that it gets you closer to optimal policy? Do you know what's gradient ascent or how it works? You have a policy and you evaluate objective function. If the objective function is not close to the extremal value then you change your parameters in the direction of the steepest ascent and you change your policy. Next time when you take a trajectory objective function will have a higher value because you changed your parameters accordingly and your policy is improved. Eventually, by doing updates you should converge to optimal policy. Aug 15 '20 at 20:00
• Haha yes, makes sense now! Thank you :) Aug 16 '20 at 1:12
• you know what the optimal value of actions is, thats what you are ascending towards with your optimization, sounds like you were wondering how optimizing towards the initial actions taken would work, which makes sense because it wouldnt Aug 16 '20 at 4:36