Answers.Body: <p>The expression you are looking at in the link, <span class="math-container">$G_t \nabla_{\theta} \text{ln}(\pi(A_t|S_t,\theta_t))$</span>, is not the cost function, but the estimated gradient of the cost function. You cannot simply remove the <span class="math-container">$\nabla_{\theta}$</span> to see the cost function, because the state distribution that weights components of the cost function (i.e. how often you will observe each trajectory) depends critically on <span class="math-container">$\theta$</span>.</p>
  <p>The real cost function would be the negative of expected return from the start (or stable for non-episodic) state distribution, i.e. <span class="math-container">$-J(\theta)$</span>. This does not have a simple expansion, because it must be summed up over the distribution of states and the policy, both of which depend on <span class="math-container">$\theta$</span>.</p>
  <p>Usually in reinforcement learning, the optimisation is not stated as a cost function to minimise, but as an expression to maximise. We want to maximise <span class="math-container">$J(\theta)$</span> which summarises our expected return. Hence a factor of the gradient is added to <span class="math-container">$\theta$</span> during update steps.</p>
  <p>From comments:</p>
  <blockquote>
  <p>if the policy stumbles upon a set of parameters which makes <span class="math-container">$G_t=0$</span>, doesn't that make the estimated gradient zero hence causing the policy to stop improving</p>
  </blockquote>
  <p>Partially correct.</p>
  <p>A return of zero from any single trajectory will make the updates from all actions also be zero, regardless of whether or not a return of zero is a good result. This motivates REINFORCE with baseline or Actor-Critic approaches that don't use final return <span class="math-container">$G_t$</span>, but advantage, or a similar baselined value instead. These methods are less sensitive to absolute value of returns.</p>
  <p>For the agent to get stuck with all zero gradients though, <em>all</em> possible trajectories would have to give a return of zero. This would be a problem for any experience-based system, and there is no reinforcement learning system that can find better actions if the feedback is all the same.</p>
  <p>In fact this is also a problem regardless of what the fixed value is - if all experience returns the same end return, then nothing can be learned to differentiate actions. Simple REINFORCE would actually generate gradients (because <span class="math-container">$G_t$</span> multiplier will be non-zero), and it might <em>look like</em> it is learning something because <span class="math-container">$\theta$</span> will change with gradient-based steps. But actually it will end up choosing a policy pseudo-randomly, because as far as the agent can tell all policies are the same.</p>
  <p>One thing to bear in mind is that the gradient estimates generated in REINFORCE (and policy gradients in general) are <em>biased</em>. You don't know the true gradient, and there is no simple way to remove the bias for a single sample - you have to rely on the gradient steps across very many samples to even out this bias. In fact you can add almost any offset to the multiplier <span class="math-container">$G_t$</span>, provided it doesn't depend <em>immediately</em> on the policy, and you still have a valid gradient estimate for update steps. This is why advantage-based systems work, they choose an offset based on state value which conveniently reduces variance on each sample.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-05T13:17:20.333Z
Answers.Text: Sorry, I meant loss, not cost function. I didn't remove ∇θ, it was stated in the link that the function we want to minimise is −Gt ln π(At|St,θt). Example from other sources such as https://github.com/Finspire13/pytorch-policy-gradient-example/blob/master/pg.py also seems to indicate this is indeed the function we want to minimize (correct me if I am wrong). Anyway, my question still remains - if the policy stumbles upon a set of parameters which makes Gt=0, doesn't that make the estimated gradient zero hence causing the policy to stop improving?
Answers.UserDisplayName: Jason L
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-05T13:35:43.900Z
Answers.Text: @JasonL That doesn't make much difference - a cost function is conventially the sum of some loss functions. $J(\theta)$ is the cost function, and components of it weighted by state distribution are the loss functions. The quote from the link is incorrect. I will answer your comment in the body of the question
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-06T13:08:39.027Z
Answers.Text: Thanks for your input @Neil. I don't think the quote from the link is incorrect. I've looked at a number of example implementations for vanilla policy gradient and −Gt log π(At|St,θt) is indeed the loss function being minimized. I think my question mainly originates from observing the loss value as training progresses - that I noticed sometimes the agent plays very badly achieving a low score, the loss decreases. Then I realised it could be term Gt in the loss that contributes to this. So it would appear that the agent is being 'rewarded' for bad play.
Answers.UserDisplayName: Jason L
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-05T10:45:33.733Z
Answers.LastActivityDate: 2023-06-05T14:02:18.320Z
Answers.LastEditDate: 2023-06-05T14:02:18.320Z
Answers.UserDisplayName: Neil Slater
Body: <p>Specifically, according to this post:</p>
  <p><a href="https://ai.stackexchange.com/questions/11929/how-is-the-policy-gradient-calculated-in-reinforce">How is the policy gradient calculated in REINFORCE</a></p>
  <p>the function I need to minimise is:</p>
  <p><span class="math-container">$−Gt \log \pi(At|St,θt)$</span></p>
  <p>where <span class="math-container">$Gt$</span> is the discounted reward, and <span class="math-container">$\pi$</span> is the policy which outputs a probability distribution of actions given the state and network parameters.</p>
  <p>Since the negative log of probability is always positive or zero, this expression also achieves a minimum of zero if <span class="math-container">$Gt$</span> is zero i.e. no reward, assuming the reward of the game is always non-negative.</p>
  <p>This seems to be the opposite of what we want to do which is to find a policy network parameters that maximises the discounted reward <span class="math-container">$Gt$</span>. What am I misunderstanding here?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-06T10:05:48.903Z
Comments.Text: Can you please put your **specific question** in the title? Clearly, "what am I misunderstanding here?" is a bit vague and it would be great if you could formulate a clearer question in the title.
Comments.UserDisplayName: nbro
Tags: <policy-gradients>
Title: Zero reward in policy gradient
UserDisplayName: Jason L
ThreadText: # Zero reward in policy gradient
  
  (Asked by: username_0 on 2023-06-05)
  
  Specifically, according to this post:
  
  [How is the policy gradient calculated in REINFORCE](https://ai.stackexchange.com/questions/11929/how-is-the-policy-gradient-calculated-in-reinforce)
  
  the function I need to minimise is:
  
  $−Gt \log \pi(At|St,θt)$
  
  where $Gt$ is the discounted reward, and $\pi$ is the policy which outputs a probability distribution of actions given the state and network parameters.
  
  Since the negative log of probability is always positive or zero, this expression also achieves a minimum of zero if $Gt$ is zero i.e. no reward, assuming the reward of the game is always non-negative.
  
  This seems to be the opposite of what we want to do which is to find a policy network parameters that maximises the discounted reward $Gt$. What am I misunderstanding here?
  
  **Tags:** policy-gradients
  > **Comments:**
  > **username_1**: Can you please put your **specific question** in the title? Clearly, "what am I misunderstanding here?" is a bit vague and it would be great if you could formulate a clearer question in the title.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2023-06-05. Score: 3
  
  The expression you are looking at in the link, $G\_t \nabla\_{\theta} \text{ln}(\pi(A\_t|S\_t,\theta\_t))$, is not the cost function, but the estimated gradient of the cost function. You cannot simply remove the $\nabla\_{\theta}$ to see the cost function, because the state distribution that weights components of the cost function (i.e. how often you will observe each trajectory) depends critically on $\theta$.
  
  The real cost function would be the negative of expected return from the start (or stable for non-episodic) state distribution, i.e. $-J(\theta)$. This does not have a simple expansion, because it must be summed up over the distribution of states and the policy, both of which depend on $\theta$.
  
  Usually in reinforcement learning, the optimisation is not stated as a cost function to minimise, but as an expression to maximise. We want to maximise $J(\theta)$ which summarises our expected return. Hence a factor of the gradient is added to $\theta$ during update steps.
  
  From comments:
  
  > if the policy stumbles upon a set of parameters which makes $G\_t=0$, doesn't that make the estimated gradient zero hence causing the policy to stop improving
  
  Partially correct.
  
  A return of zero from any single trajectory will make the updates from all actions also be zero, regardless of whether or not a return of zero is a good result. This motivates REINFORCE with baseline or Actor-Critic approaches that don't use final return $G\_t$, but advantage, or a similar baselined value instead. These methods are less sensitive to absolute value of returns.
  
  For the agent to get stuck with all zero gradients though, *all* possible trajectories would have to give a return of zero. This would be a problem for any experience-based system, and there is no reinforcement learning system that can find better actions if the feedback is all the same.
  
  In fact this is also a problem regardless of what the fixed value is - if all experience returns the same end return, then nothing can be learned to differentiate actions. Simple REINFORCE would actually generate gradients (because $G\_t$ multiplier will be non-zero), and it might *look like* it is learning something because $\theta$ will change with gradient-based steps. But actually it will end up choosing a policy pseudo-randomly, because as far as the agent can tell all policies are the same.
  
  One thing to bear in mind is that the gradient estimates generated in REINFORCE (and policy gradients in general) are *biased*. You don't know the true gradient, and there is no simple way to remove the bias for a single sample - you have to rely on the gradient steps across very many samples to even out this bias. In fact you can add almost any offset to the multiplier $G\_t$, provided it doesn't depend *immediately* on the policy, and you still have a valid gradient estimate for update steps. This is why advantage-based systems work, they choose an offset based on state value which conveniently reduces variance on each sample.
  
  > **Comments:**
  > **username_0**: Sorry, I meant loss, not cost function. I didn't remove ∇θ, it was stated in the link that the function we want to minimise is −Gt ln π(At|St,θt). Example from other sources such as https://github.com/Finspire13/pytorch-policy-gradient-example/blob/master/pg.py also seems to indicate this is indeed the function we want to minimize (correct me if I am wrong). Anyway, my question still remains - if the policy stumbles upon a set of parameters which makes Gt=0, doesn't that make the estimated gradient zero hence causing the policy to stop improving?  
  > **username_2**: @JasonL That doesn't make much difference - a cost function is conventially the sum of some loss functions. $J(\theta)$ is the cost function, and components of it weighted by state distribution are the loss functions. The quote from the link is incorrect. I will answer your comment in the body of the question  
  > **username_0**: Thanks for your input @Neil. I don't think the quote from the link is incorrect. I've looked at a number of example implementations for vanilla policy gradient and −Gt log π(At|St,θt) is indeed the loss function being minimized. I think my question mainly originates from observing the loss value as training progresses - that I noticed sometimes the agent plays very badly achieving a low score, the loss decreases. Then I realised it could be term Gt in the loss that contributes to this. So it would appear that the agent is being 'rewarded' for bad play.  
  
  ---
  
  