Answers.Body: <p>The essence of your observation is that Sutton's version of REINFORCE is taking into consideration all of the trajectory to compute the returns, while in the pytorch version only the future is taken into consideration, hence going in reverse to sum the future rewards and ignore the previous rewards. The consequence is that future actions are not punished for early mistakes. The guys at OpenAI refer to this as reward-to-go, but, personally, I find that it resembles Monte Carlo On Policy Control without Exploring Starts or First Visit from Sutton's book.</p>
  <p>You can find more on REINFORCE and Policy Gradient in <a href="https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html#don-t-let-the-past-distract-you" rel="nofollow noreferrer">Spinning Up RL: Part3: Intro to policy gradient -  Don't let the past distract you</a>.</p>
  <p>Also, something to note is that even in Sutton's version, the whole trajectory is unrolled, i.e. the episode completes, and then the weights get updated. Otherwise it stops being  a Monte Carlo Method and it becomes a TD method. In addition, you can't make a change on a single point because sampling is a non differentiable operation, instead, the gradient is estimated by collecting a lot of trajectories.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-19T09:27:27.427Z
Answers.Text: Isn't in the Pseudo-Code of Sutton also only the future taken into account? Since it says: return from step t.
Answers.UserDisplayName: PeterD
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-29T11:01:40.100Z
Answers.LastActivityDate: 2022-05-30T08:46:06.017Z
Answers.LastEditDate: 2022-05-30T08:46:06.017Z
Answers.UserDisplayName: Dimitris Monroe
Body: <p>REINFORCE is a Monte Carlo policy gradient algorithm, which updates weights (parameters) of policy network by generating episodes. Here's a pseudo-code from Sutton's book (which is same as the equation in Silver's RL note):</p>
  
  <p><a href="https://i.sstatic.net/QJFB2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/QJFB2.png" alt="reinforce"></a></p>
  
  <p>When I try to implement this with my own problem, I found something strange. Here's implementation from <a href="https://github.com/pytorch/examples/blob/master/reinforcement_learning/reinforce.py" rel="nofollow noreferrer">Pytorch's official GitHub</a>:</p>
  
  <pre><code>def finish_episode():
      R = 0
      policy_loss = []
      returns = []
      for r in policy.rewards[::-1]:
          R = r + args.gamma * R
          returns.insert(0, R)
      returns = torch.tensor(returns)
      returns = (returns - returns.mean()) / (returns.std() + eps)
      for log_prob, R in zip(policy.saved_log_probs, returns):
          policy_loss.append(-log_prob * R)
      optimizer.zero_grad()
      policy_loss = torch.cat(policy_loss).sum()
      policy_loss.backward()
      optimizer.step()
      del policy.rewards[:]
      del policy.saved_log_probs[:]
  </code></pre>
  
  <p>I feel like there's a difference between the above two. In Sutton's pseudo-code, the algorithm updates <span class="math-container">$\theta$</span> for <strong>each step</strong> <span class="math-container">$t$</span>, while the second code (PyTorch's one) accumulate loss and update <span class="math-container">$\theta$</span> with the summation, i.e. <strong>after each episode</strong>. 
  I tried to search other implementation of REINFORCE, and I found that most of the implementations follow the second form, update after each generated episodes. </p>
  
  <p>To check whether both give the same result, I changed the second code as </p>
  
  <pre><code>def finish_episode():
      R = 0
      policy_loss = []
      returns = []
      for r in policy.rewards[::-1]:
          R = r + args.gamma * R
          returns.insert(0, R)
      returns = torch.tensor(returns)
      returns = (returns - returns.mean()) / (returns.std() + eps)
      for log_prob, R in zip(policy.saved_log_probs, returns):
          optimizer.zero_grad()
          loss = -log_prob * R
          loss.backward()
          optimizer.step()
  
  ...
  </code></pre>
  
  <p>and run it, which gives different result (if my code has no problem). 
  So they are not the same, and I think the last one is more close to the original pseudo-code of REINFORCE. What am I missing now? Is it okay because the results are approximately same? (I'm not sure about this claim)</p>
  
  <p>However, in some sense, I think Pytorch's implementation is the <em>right</em> version of REINFORCE. In Sutton's pseudo-code, episode is generated first, so I think <span class="math-container">$\theta$</span> shouldn't be updated at each step and should be updated after the total loss is computed. If <span class="math-container">$\theta$</span> is updated at each step, then such <span class="math-container">$\theta$</span> might be different with the original <span class="math-container">$\theta$</span> that used to generate the episode.  </p>
  
Tags: <reinforcement-learning><pytorch><implementation><sutton-barto><reinforce>
Title: Should the policy parameters be updated at each time step or at the end of the episode in REINFORCE?
UserDisplayName: Seewoo Lee
ThreadText: # Should the policy parameters be updated at each time step or at the end of the episode in REINFORCE?
  
  (Asked by: username_0 on 2019-10-29)
  
  REINFORCE is a Monte Carlo policy gradient algorithm, which updates weights (parameters) of policy network by generating episodes. Here's a pseudo-code from Sutton's book (which is same as the equation in Silver's RL note):
  
  When I try to implement this with my own problem, I found something strange. Here's implementation from Pytorch's official GitHub:
  def finish_episode():
      R = 0
      policy_loss = []
      returns = []
      for r in policy.rewards[::-1]:
          R = r + args.gamma * R
          returns.insert(0, R)
      returns = torch.tensor(returns)
      returns = (returns - returns.mean()) / (returns.std() + eps)
      for log_prob, R in zip(policy.saved_log_probs, returns):
          policy_loss.append(-log_prob * R)
      optimizer.zero_grad()
      policy_loss = torch.cat(policy_loss).sum()
      policy_loss.backward()
      optimizer.step()
      del policy.rewards[:]
      del policy.saved_log_probs[:]
  
  I feel like there's a difference between the above two. In Sutton's pseudo-code, the algorithm updates $\theta$ for each step $t$, while the second code (PyTorch's one) accumulate loss and update $\theta$ with the summation, i.e. after each episode. 
  I tried to search other implementation of REINFORCE, and I found that most of the implementations follow the second form, update after each generated episodes. 
  To check whether both give the same result, I changed the second code as 
  def finish_episode():
      R = 0
      policy_loss = []
      returns = []
      for r in policy.rewards[::-1]:
          R = r + args.gamma * R
          returns.insert(0, R)
      returns = torch.tensor(returns)
      returns = (returns - returns.mean()) / (returns.std() + eps)
      for log_prob, R in zip(policy.saved_log_probs, returns):
          optimizer.zero_grad()
          loss = -log_prob * R
          loss.backward()
          optimizer.step()
  
  ...
  
  and run it, which gives different result (if my code has no problem). 
  So they are not the same, and I think the last one is more close to the original pseudo-code of REINFORCE. What am I missing now? Is it okay because the results are approximately same? (I'm not sure about this claim)
  However, in some sense, I think Pytorch's implementation is the right version of REINFORCE. In Sutton's pseudo-code, episode is generated first, so I think $\theta$ shouldn't be updated at each step and should be updated after the total loss is computed. If $\theta$ is updated at each step, then such $\theta$ might be different with the original $\theta$ that used to generate the episode.
  
  **Tags:** reinforcement-learning, pytorch, implementation, sutton-barto, reinforce
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-10-29. Score: 3 | Accepted answer
  
  The essence of your observation is that Sutton's version of REINFORCE is taking into consideration all of the trajectory to compute the returns, while in the pytorch version only the future is taken into consideration, hence going in reverse to sum the future rewards and ignore the previous rewards. The consequence is that future actions are not punished for early mistakes. The guys at OpenAI refer to this as reward-to-go, but, personally, I find that it resembles Monte Carlo On Policy Control without Exploring Starts or First Visit from Sutton's book.
  
  You can find more on REINFORCE and Policy Gradient in [Spinning Up RL: Part3: Intro to policy gradient - Don't let the past distract you](https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html#don-t-let-the-past-distract-you).
  
  Also, something to note is that even in Sutton's version, the whole trajectory is unrolled, i.e. the episode completes, and then the weights get updated. Otherwise it stops being a Monte Carlo Method and it becomes a TD method. In addition, you can't make a change on a single point because sampling is a non differentiable operation, instead, the gradient is estimated by collecting a lot of trajectories.
  
  > **Comments:**
  > **username_2**: Isn't in the Pseudo-Code of Sutton also only the future taken into account? Since it says: return from step t.  
  
  ---
  
  