<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>

CC BY-SA 4.0
2020-04-24T07:33:40.537Z
2020-04-24T07:33:40.537Z
2020-06-17T09:57:20.710Z
Neil Slater
<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>

<reinforcement-learning><monte-carlo-methods><off-policy-methods>
Understanding the W term in off policy monte carlo learning
Stephane Hatgis-Kessell
# 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?


---

