Answers.Body: <p>The pseudocode you have copied looks incorrect to me, and I think it is from the first edition.</p>
  <p>The main issue is at the end of the loop. Where the book has</p>
  <blockquote>
  <p><span class="math-container">$\qquad W \leftarrow W \frac{1}{\mu(A_t|S_t)}$</span></p>
  <p><span class="math-container">$\qquad \text{If } W = 0 \text{ then ExitForLoop}$</span></p>
  </blockquote>
  <p>It should have either</p>
  <blockquote>
  <p><span class="math-container">$\qquad W \leftarrow W \frac{1}{\mu(A_t|S_t)}$</span></p>
  <p><span class="math-container">$\qquad \text{If } \pi(S_t) \neq A_t \text{ then ExitForLoop}$</span></p>
  </blockquote>
  <p>or</p>
  <blockquote>
  <p><span class="math-container">$\qquad W \leftarrow W \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}$</span></p>
  <p><span class="math-container">$\qquad \text{If } W = 0 \text{ then ExitForLoop}$</span></p>
  </blockquote>
  <p>This latter one is more general - it covers situations where the target policy can be stochastic - but doesn't fit with the notation used elsewhere for a deterministic policy. For some reason the first edition book had a mistake using hybrid algorithm which adjusted to a deterministic target policy except for the exit loop statement. This is fixed in <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">the second edition</a> (page 111).</p>
  <blockquote>
  <p>after 10,000 iterations</p>
  </blockquote>
  <p>Are your episodes really 10,000 time steps long? If so, the chances of off-policy MC control learning anything for early time steps seems remote unless <span class="math-container">$\epsilon$</span> is really low (and in which case <span class="math-container">$W$</span> will not get too high). If not, have you missed that <span class="math-container">$W \leftarrow 1$</span> occurs at the start of each episode?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-24T07:33:40.537Z
Answers.LastActivityDate: 2020-04-24T07:33:40.537Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Neil Slater
Body: <p>In Sutton and Barto's RL textbook they included the following pseudocode for off policy Monte Carlo learning. I am a little confused, however, because to me it looks like the W term will become infinitely large after a couple thousand iterations (and this is exactly what happens when I implement the algorithm).</p>
  
  <p>For example, say that the MC algorithm always follows the behavioral policy for each episode (ignoring epsilon soft/greedy for examples sake). If the probability of the action specified by the policy is 0.9, then after 10,000 iterations W would have a value of 1.11^10,000. I understand that the ratio of W to C(a,s) is what matters, however this ratio cannot be computer once W becomes infinite. Clearly I am misunderstanding something.</p>
  
  <p><a href="https://i.sstatic.net/RubOG.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/RubOG.png" alt="enter image description here"></a></p>
  
Tags: <reinforcement-learning><monte-carlo-methods><off-policy-methods>
Title: Understanding the W term in off policy monte carlo learning
UserDisplayName: Stephane Hatgis-Kessell
ThreadText: # Understanding the W term in off policy monte carlo learning
  
  (Asked by: username_0 on 2020-04-24)
  
  In Sutton and Barto's RL textbook they included the following pseudocode for off policy Monte Carlo learning. I am a little confused, however, because to me it looks like the W term will become infinitely large after a couple thousand iterations (and this is exactly what happens when I implement the algorithm).
  
  For example, say that the MC algorithm always follows the behavioral policy for each episode (ignoring epsilon soft/greedy for examples sake). If the probability of the action specified by the policy is 0.9, then after 10,000 iterations W would have a value of 1.11^10,000. I understand that the ratio of W to C(a,s) is what matters, however this ratio cannot be computer once W becomes infinite. Clearly I am misunderstanding something.
  
  [![enter image description here](https://i.sstatic.net/RubOG.png)](https://i.sstatic.net/RubOG.png)
  
  **Tags:** reinforcement-learning, monte-carlo-methods, off-policy-methods
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-24. Score: 2 | Accepted answer
  
  The pseudocode you have copied looks incorrect to me, and I think it is from the first edition.
  
  The main issue is at the end of the loop. Where the book has
  
  > $\qquad W \leftarrow W \frac{1}{\mu(A\_t|S\_t)}$
  >
  > $\qquad \text{If } W = 0 \text{ then ExitForLoop}$
  
  It should have either
  
  > $\qquad W \leftarrow W \frac{1}{\mu(A\_t|S\_t)}$
  >
  > $\qquad \text{If } \pi(S\_t) \neq A\_t \text{ then ExitForLoop}$
  
  or
  
  > $\qquad W \leftarrow W \frac{\pi(A\_t|S\_t)}{\mu(A\_t|S\_t)}$
  >
  > $\qquad \text{If } W = 0 \text{ then ExitForLoop}$
  
  This latter one is more general - it covers situations where the target policy can be stochastic - but doesn't fit with the notation used elsewhere for a deterministic policy. For some reason the first edition book had a mistake using hybrid algorithm which adjusted to a deterministic target policy except for the exit loop statement. This is fixed in [the second edition](http://incompleteideas.net/book/RLbook2020.pdf) (page 111).
  
  > after 10,000 iterations
  
  Are your episodes really 10,000 time steps long? If so, the chances of off-policy MC control learning anything for early time steps seems remote unless $\epsilon$ is really low (and in which case $W$ will not get too high). If not, have you missed that $W \leftarrow 1$ occurs at the start of each episode?
  
  
  ---
  
  