Answers.Body: <p>The first part of this answer is a little background that might bolster your intuition for what's going on. The second part is the more practical and direct answer to your question.</p>
  
  <hr>
  
  <p>The gradient is just the generalization of the derivative to multivariable functions. The gradient of a function at a certain point is a vector that points in the direction of the steepest increase of that function.</p>
  
  <p>Usually, we take a derivative/gradient of some loss function <span class="math-container">$\mathcal{L}$</span> because we want to minimize that loss. So we update our parameters in the direction <em>opposite</em> the direction of the gradient. </p>
  
  <p><span class="math-container">$$\theta_{t+1} = \theta_{t} - \alpha\nabla_{\theta_t} \mathcal{L} \tag{1}$$</span></p>
  
  <p>In policy gradient methods, we're not trying to minimize a loss function. Actually, we're trying to <em>maximize</em> some measure <span class="math-container">$J$</span> of the performance of our agent. So now we want to update parameters in the same direction as the gradient.</p>
  
  <p><span class="math-container">$$\theta_{t+1} = \theta_{t} + \alpha\nabla_{\theta_t} J \tag{2}$$</span></p>
  
  <p>In the episodic case, <span class="math-container">$J$</span> is the value of the starting state. In the continuing case, <span class="math-container">$J$</span> is the average reward. It just so happens that a nice theorem called the Policy Gradient Theorem applies to both cases. This theorem states that</p>
  
  <p><span class="math-container">$$\begin{align}
  \nabla_{\theta_t}J(\theta_t) &amp;\propto \sum_s \mu(s)\sum_a q_\pi (s,a) \nabla_{\theta_t} \pi (a|s,\theta_t)\\
  &amp;=\mathbb{E}_\mu \left[ \sum_a q_\pi (s,a) \nabla_{\theta_t} \pi (a|s,\theta_t)\right].
  \end{align}\tag{3}
  $$</span></p>
  
  <p>The rest of the derivation is in your question, so let's skip to the end.</p>
  
  <p><span class="math-container">$$\begin{align}
  \theta_{t+1} &amp;= \theta_{t} + \alpha G_t \frac{\nabla_{\theta_t}\pi(A_t|S_t,\theta_t)}{\pi(A_t|S_t,\theta_t)}\\
  &amp;= \theta_{t} + \alpha G_t \nabla_{\theta_t} \ln \pi(A_t|S_t,\theta_t)
  \end{align}\tag{4}$$</span></p>
  
  <p>Remember, <span class="math-container">$(4)$</span> says exactly the same thing as <span class="math-container">$(2)$</span>, so REINFORCE just updates parameters in the direction that will most increase <span class="math-container">$J$</span>. (Because we sample from an expectation in the derivation, the parameter step in REINFORCE is actually an unbiased estimate of the maximizing step.) </p>
  
  <hr>
  
  <p>Alright, but how do we actually get this gradient? Well, you use the chain rule of derivatives (backpropagation). Practically, though, both Tensorflow and PyTorch can take all the derivatives for you. </p>
  
  <p>Tensorflow, for example, has a minimize() method in its Optimizer class that takes a loss function as an input. Given a function of the parameters of the network, it will do the calculus for you to determine which way to update the parameters in order to minimize that function. But we don't want to minimize. We want to maximize! So just include a negative sign. </p>
  
  <p>In our case, the function we want to minimize is 
  <span class="math-container">$$-G_t\ln \pi(A_t|S_t,\theta_t).$$</span> </p>
  
  <p>This corresponds to stochastic gradient descent (<span class="math-container">$G_t$</span> is not a function of <span class="math-container">$\theta_t$</span>). </p>
  
  <p>You might want to do minibatch gradient descent on each episode of experience in order to get a better (lower variance) estimate of <span class="math-container">$\nabla_{\theta_t} J$</span>. If so, you would instead minimize 
  <span class="math-container">$$-\sum_t G_t\ln \pi(A_t|S_t,\theta_t),$$</span>
  where <span class="math-container">$\theta_t$</span> would be constant for different values of <span class="math-container">$t$</span> within the same episode. Technically, minibatch gradient descent updates parameters in the average estimated maximizing direction, but the scaling factor <span class="math-container">$1/N$</span> can be absorbed into the learning rate.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-22T03:30:27.210Z
Answers.Text: Thanks you answered one of my questions about an implementation summing over the products of the (negative) log probabilities and their associated returns (I hadn’t considered it as mini batch implementation). I really appreciate the detailed answer. I guess I was trying to figure out how to represent it in a framework but I got bogged down in the details and forgot that Sutton / Barto mentioned that $J$ is a representation of the value of the start state. With the two answers provided I’m starting to find my way.
Answers.UserDisplayName: Hanzy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-22T03:23:46.850Z
Answers.LastActivityDate: 2019-04-22T05:17:31.570Z
Answers.LastEditDate: 2019-04-22T05:17:31.570Z
Answers.UserDisplayName: Philip Raeisghasem
Body: <p>Reading Sutton and Barto, I see the following in describing policy gradients:</p>
  
  <p><a href="https://i.sstatic.net/LnCdQ.jpg" rel="noreferrer"><img src="https://i.sstatic.net/LnCdQ.jpg" alt="policy grad "></a></p>
  
  <p>How is the gradient calculated with respect to an action (taken at time t)? I've read implementations of the algorithm, but conceptually I'm not sure I understand how the gradient is computed, since we need some loss function to compute the gradient. </p>
  
  <p>I've seen a good PyTorch article, but I still don't understand the meaning of this gradient conceptually, and I don't know what I'm looking to implement. Any intuition that you could provide would be helpful. </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-21T20:23:09.020Z
Comments.Text: Are you asking if the gradient is with respect to an action? If yes, then, no, the gradient is not with respect to an action, but with respect to the parameters (of e.g. the neural network representing your policy), $\theta_t$. Conceptually, you don't need any "loss" to compute the gradient. You just need a multivariable differentiable function. In this case, the multivariable function is your parametrised policy $\pi(A_t \mid S_t, \theta_t)$.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-21T20:31:12.423Z
Comments.Text: @nbro Conceptually I understand that, but the action is the output of the policy. So what I don’t understand is how conceptually we are determining the gradient of the policy with respect to the action it output? Further if the action is making a choice, that wouldn’t be differentiable. I looked at the implementation that used an action probability instead. But I’m still unsure what is the gradient of the policy with respect to the output of the policy. It doesn’t make sense to me yet.
Comments.UserDisplayName: Hanzy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-21T20:37:54.810Z
Comments.Text: @nbro I guess I see that it’s technically the gradient of the probability of selecting an action At. But still not sure how to implement that. We want to know how the probability would change with respect to changing the parameters. Maybe I’m starting to get a little insight.
Comments.UserDisplayName: Hanzy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-21T20:48:32.870Z
Comments.Text: I think this is just a notation or terminology issue. To train your neural network representing $\pi$, you will need a loss function (that assesses the quality of the output action), yes, but this is not explicit in Barto and Sutton's book (at least in those equations), which just states that the gradient is with respect to the parameters (variables) of the function. Barto and Sutton just present the general idea. Have a look at this reference implementation: https://github.com/pytorch/examples/blob/master/reinforcement_learning/reinforce.py.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-22T01:29:45.473Z
Comments.Text: @nbro thanks for the link; I actually think I’m almost there. In this implementation we take the (negative) log probability and multiply it by the return. We moved the return inside the gradient since it’s not dependent on $theta$.  Then we sum over the list of returns and use the summing function as the function over which we compute the gradient. So the gradient is the SUM of all future rewards wrt to theta (which, in turn, effects the choice of action). Is this correct? (I’m going back to read it again now).
Comments.UserDisplayName: Hanzy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-22T01:43:02.403Z
Comments.Text: @nbro sorry I meant to say the sum of all future rewards times the (negative) log probability of selecting the action taken that led to that reward. (I couldn’t edit my previous comment for clarity).
Comments.UserDisplayName: Hanzy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-22T02:39:59.677Z
Comments.Text: @nbro I’m assuming torch tracks the gradients by tracking  entries in policy.saved_log_probs since they were drawn from torch.Categorical() distribution. Otherwise these log probabilities would simply be entries in a list w/o any way to track how they were computed or their gradients.
Comments.UserDisplayName: Hanzy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-22T02:53:10.420Z
Comments.Text: @nbro I’m now just trying to figure out why we want to sum over all the products of (negative) log probabilities of each action and their associated return instead of doing an update on each time step. The Sutton / Barto algorithm has a different update for every time step. I suppose if we are already tracking gradients of every log probability then instead of doing one update at a time we can do an aggregate update to a linear combination of them? This makes sense to me but I haven’t written it out to prove it.
Comments.UserDisplayName: Hanzy
Tags: <reinforcement-learning><policy-gradients><sutton-barto><notation><reinforce>
Title: How is the policy gradient calculated in REINFORCE?
UserDisplayName: Hanzy
ThreadText: # How is the policy gradient calculated in REINFORCE?
  
  (Asked by: username_0 on 2019-04-21)
  
  Reading Sutton and Barto, I see the following in describing policy gradients:
  
  [![policy grad ](https://i.sstatic.net/LnCdQ.jpg)](https://i.sstatic.net/LnCdQ.jpg)
  
  How is the gradient calculated with respect to an action (taken at time t)? I've read implementations of the algorithm, but conceptually I'm not sure I understand how the gradient is computed, since we need some loss function to compute the gradient.
  
  I've seen a good PyTorch article, but I still don't understand the meaning of this gradient conceptually, and I don't know what I'm looking to implement. Any intuition that you could provide would be helpful.
  
  **Tags:** reinforcement-learning, policy-gradients, sutton-barto, notation, reinforce
  
  > **Comments:**
  > **username_1**: Are you asking if the gradient is with respect to an action? If yes, then, no, the gradient is not with respect to an action, but with respect to the parameters (of e.g. the neural network representing your policy), $\theta_t$. Conceptually, you don't need any "loss" to compute the gradient. You just need a multivariable differentiable function. In this case, the multivariable function is your parametrised policy $\pi(A_t \mid S_t, \theta_t)$.  
  > **username_0**: @username_1 Conceptually I understand that, but the action is the output of the policy. So what I don’t understand is how conceptually we are determining the gradient of the policy with respect to the action it output? Further if the action is making a choice, that wouldn’t be differentiable. I looked at the implementation that used an action probability instead. But I’m still unsure what is the gradient of the policy with respect to the output of the policy. It doesn’t make sense to me yet.  
  > **username_0**: @username_1 I guess I see that it’s technically the gradient of the probability of selecting an action At. But still not sure how to implement that. We want to know how the probability would change with respect to changing the parameters. Maybe I’m starting to get a little insight.  
  > **username_1**: I think this is just a notation or terminology issue. To train your neural network representing $\pi$, you will need a loss function (that assesses the quality of the output action), yes, but this is not explicit in Barto and Sutton's book (at least in those equations), which just states that the gradient is with respect to the parameters (variables) of the function. Barto and Sutton just present the general idea. Have a look at this reference implementation: https://github.com/pytorch/examples/blob/master/reinforcement_learning/reinforce.py.  
  > **username_0**: @username_1 thanks for the link; I actually think I’m almost there. In this implementation we take the (negative) log probability and multiply it by the return. We moved the return inside the gradient since it’s not dependent on $theta$.  Then we sum over the list of returns and use the summing function as the function over which we compute the gradient. So the gradient is the SUM of all future rewards wrt to theta (which, in turn, effects the choice of action). Is this correct? (I’m going back to read it again now).  
  > **username_0**: @username_1 sorry I meant to say the sum of all future rewards times the (negative) log probability of selecting the action taken that led to that reward. (I couldn’t edit my previous comment for clarity).  
  > **username_0**: @username_1 I’m assuming torch tracks the gradients by tracking  entries in policy.saved_log_probs since they were drawn from torch.Categorical() distribution. Otherwise these log probabilities would simply be entries in a list w/o any way to track how they were computed or their gradients.  
  > **username_0**: @username_1 I’m now just trying to figure out why we want to sum over all the products of (negative) log probabilities of each action and their associated return instead of doing an update on each time step. The Sutton / Barto algorithm has a different update for every time step. I suppose if we are already tracking gradients of every log probability then instead of doing one update at a time we can do an aggregate update to a linear combination of them? This makes sense to me but I haven’t written it out to prove it.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-04-22. Score: 7 | Accepted answer
  
  The first part of this answer is a little background that might bolster your intuition for what's going on. The second part is the more practical and direct answer to your question.
  
  ---
  
  The gradient is just the generalization of the derivative to multivariable functions. The gradient of a function at a certain point is a vector that points in the direction of the steepest increase of that function.
  
  Usually, we take a derivative/gradient of some loss function $\mathcal{L}$ because we want to minimize that loss. So we update our parameters in the direction *opposite* the direction of the gradient.
  
  $$\theta\_{t+1} = \theta\_{t} - \alpha\nabla\_{\theta\_t} \mathcal{L} \tag{1}$$
  
  In policy gradient methods, we're not trying to minimize a loss function. Actually, we're trying to *maximize* some measure $J$ of the performance of our agent. So now we want to update parameters in the same direction as the gradient.
  
  $$\theta\_{t+1} = \theta\_{t} + \alpha\nabla\_{\theta\_t} J \tag{2}$$
  
  In the episodic case, $J$ is the value of the starting state. In the continuing case, $J$ is the average reward. It just so happens that a nice theorem called the Policy Gradient Theorem applies to both cases. This theorem states that
  
  $$\begin{align}
  \nabla\_{\theta\_t}J(\theta\_t) &\propto \sum\_s \mu(s)\sum\_a q\_\pi (s,a) \nabla\_{\theta\_t} \pi (a|s,\theta\_t)\\
  &=\mathbb{E}\_\mu \left[ \sum\_a q\_\pi (s,a) \nabla\_{\theta\_t} \pi (a|s,\theta\_t)\right].
  \end{align}\tag{3}
  $$
  
  The rest of the derivation is in your question, so let's skip to the end.
  
  $$\begin{align}
  \theta\_{t+1} &= \theta\_{t} + \alpha G\_t \frac{\nabla\_{\theta\_t}\pi(A\_t|S\_t,\theta\_t)}{\pi(A\_t|S\_t,\theta\_t)}\\
  &= \theta\_{t} + \alpha G\_t \nabla\_{\theta\_t} \ln \pi(A\_t|S\_t,\theta\_t)
  \end{align}\tag{4}$$
  
  Remember, $(4)$ says exactly the same thing as $(2)$, so REINFORCE just updates parameters in the direction that will most increase $J$. (Because we sample from an expectation in the derivation, the parameter step in REINFORCE is actually an unbiased estimate of the maximizing step.)
  
  ---
  
  Alright, but how do we actually get this gradient? Well, you use the chain rule of derivatives (backpropagation). Practically, though, both Tensorflow and PyTorch can take all the derivatives for you.
  
  Tensorflow, for example, has a minimize() method in its Optimizer class that takes a loss function as an input. Given a function of the parameters of the network, it will do the calculus for you to determine which way to update the parameters in order to minimize that function. But we don't want to minimize. We want to maximize! So just include a negative sign.
  
  In our case, the function we want to minimize is
  $$-G\_t\ln \pi(A\_t|S\_t,\theta\_t).$$
  
  This corresponds to stochastic gradient descent ($G\_t$ is not a function of $\theta\_t$).
  
  You might want to do minibatch gradient descent on each episode of experience in order to get a better (lower variance) estimate of $\nabla\_{\theta\_t} J$. If so, you would instead minimize
  $$-\sum\_t G\_t\ln \pi(A\_t|S\_t,\theta\_t),$$
  where $\theta\_t$ would be constant for different values of $t$ within the same episode. Technically, minibatch gradient descent updates parameters in the average estimated maximizing direction, but the scaling factor $1/N$ can be absorbed into the learning rate.
  
  > **Comments:**
  > **username_0**: Thanks you answered one of my questions about an implementation summing over the products of the (negative) log probabilities and their associated returns (I hadn’t considered it as mini batch implementation). I really appreciate the detailed answer. I guess I was trying to figure out how to represent it in a framework but I got bogged down in the details and forgot that Sutton / Barto mentioned that $J$ is a representation of the value of the start state. With the two answers provided I’m starting to find my way.  
  
  ---
  
  