Answers.Body: <p>The key to REINFORCE working is the way the parameters are shifted towards <span class="math-container">$G \nabla \log \pi(a|s, \theta)$</span>.</p>
  <p>Note that <span class="math-container">$ \nabla \log \pi(a|s, \theta) = \frac{ \nabla \pi(a|s, \theta)}{\pi(a|s, \theta)}$</span>. 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 <span class="math-container">$t$</span> 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).</p>
  <p>That is for the intuition -- to see why it <em>does</em> work, then think about what we've done. We defined an objective function, <span class="math-container">$v_\pi(s)$</span>, that we are interested in maximising with respected to our parameters <span class="math-container">$\theta$</span>. 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 <span class="math-container">$v_\pi(s)$</span>, thus if we keep performing gradient ascent then our policy parameters will converge (eventually) to values that maximise <span class="math-container">$v$</span> and thus our policy would be optimal.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-15T17:09:49.300Z
Answers.Text: 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?
Answers.UserDisplayName: stoic-santiago
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-15T17:48:56.700Z
Answers.Text: 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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-15T20:00:52.400Z
Answers.Text: 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.
Answers.UserDisplayName: Brale
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-16T04:36:38.707Z
Answers.Text: 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
Answers.UserDisplayName: nickw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-15T14:16:04.453Z
Answers.LastActivityDate: 2020-08-15T21:52:54.493Z
Answers.LastEditDate: 2020-08-15T21:52:54.493Z
Answers.UserDisplayName: David
Body: <p>Here's a screenshot of the popular policy-gradient algorithm from Sutton and Barto's book -
  <a href="https://i.sstatic.net/YsOS1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/YsOS1.png" alt="enter image description here" /></a></p>
  <p>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 <strong>incorrect policy</strong> (i.e. we don't know the parameters <span class="math-container">$\theta$</span> yet), and we use this policy to generate episodes and do consequent updates.</p>
  <p>Why should <strong>REINFORCE work at all?</strong> After all, the episode it uses for the gradient update is generated using the policy that is parametrized by parameters <span class="math-container">$\theta$</span> <em>which are yet to be updated</em> (the episode isn't generated using the <strong>optimal policy</strong> - there's no way we can do that).</p>
  <p>I hope that my concern is clear and I request y'all to provide some intuition as to why this works! I suspect that, <strong>somehow</strong>, 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 <span class="math-container">$\theta$</span>) on average.</p>
  <p>So, what's really going on here?</p>
  
Tags: <reinforcement-learning><policy-gradients><reinforce>
Title: Why does REINFORCE work at all?
UserDisplayName: stoic-santiago
ThreadText: # Why does REINFORCE work at all?
  
  (Asked by: username_0 on 2020-08-15)
  
  Here's a screenshot of the popular policy-gradient algorithm from Sutton and Barto's book -
  [![enter image description here](https://i.sstatic.net/YsOS1.png)](https://i.sstatic.net/YsOS1.png)
  
  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?
  
  **Tags:** reinforcement-learning, policy-gradients, reinforce
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-08-15. Score: 4 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_1**: 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.  
  > **username_2**: 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.  
  > **username_3**: 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  
  
  ---
  
  