In off-policy MC control algorithm by Sutton & Barto, why do we perform a last update when sample action is inconsistent with target policy?

Question

I have a question about the $W$ term in the off-policy MC control algorithm on Page 111 of Sutton & Barto. I have also included it in the figure below.

My question: shouldn't the check $A_{t} = \pi(S_{t})$ be made before updating $C(S_{t}, A_{t})$ and $Q(S_{t}, A_{t})$? And, at this point if $A_{t} \neq \pi(S_{t}) $ then the inner loop should exit before updating $Q(\cdot)$. If $A_{t} = \pi(S_{t})$ then shouldn't $W$ be updated to $W = W \frac{1}{b(A_{t}|S_{t})} $ before updating the $Q(s, a)$ and $C(s, a) functions?

The algorithm as stated seems problematic to me. For example, if say the target policy $\pi$ is deterministic and behavior policy $b$ is stochastic. If in period $T-1$ the behavior policy takes an action that is not consistent with $\pi$ then the importance sampling ratio $\rho_{T-1:T-1} = 0$. However, the algorithm as shown would update $Q(S_{T-1}, A_{T-1})$ since the checks I referred to above don't occur until the end of the inner loop. What am I missing here?

Answer 1

I think that this is an intentional subtle detail of the algorithm that ensures the convergence property. The claim in the book is that for any $b$ that provides us with "an infinite number of returns for each pair of state and action" the target policy $\pi$ will converge to optimal.

Imagine now that we have such a bad policy $b$ that it never aligns with the target policy action at the last step $t=T-1$ of each generated episode: $A_{T-1} = \pi(S_{T-1})$. In that case the weight value will stay $W=1$ and the the algorithm will be reduced to (ignoring $t$ indices for the last $S,A,R$ triplet): $$\begin{array}{l} C(S,A) \leftarrow C(S,A) + 1 \\ Q(S,A) \leftarrow Q(S,A) + \frac{1}{C(S,A)}\left[R - Q(S,A)\right] \end{array}$$
Which is just the tabular incremental averaging for the Q values (see for example eq. (2.3)).

If we bail from the for loop before these updates, then no updates would happen at all. And authors won't be able to claim convergence to optimal policy for all those "good" sampling policies $b$.