Understanding the W term in off policy monte carlo learning

Question

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.

Answer 1

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