2
$\begingroup$

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.

Algorithm from Sutton Barto

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you. I wish they at least had a brief comment stating this. To leave this completely without comment seems strange (it was driving me crazy). Thank you again. Regarding, "we have such a bad policy 𝑏 that it never aligns with the target policy action at the last step 𝑡=𝑇−1 of each generated episode". I suppose that is not possible given coverage, right? It might be super slow but has to align from time to time. $\endgroup$
    – Curious2learn
    May 15, 2021 at 23:47
  • $\begingroup$ @Curious2learn I agree that this point should've been stressed, as far as I understand the algorithm is not too practical and authors wanted to move on to the next chapters that discuss all the (authors' original) improvements to this approach. $\endgroup$
    – Kostya
    May 15, 2021 at 23:54
  • $\begingroup$ @Curious2learn As for the possibility of such a "bad" $b$. I guess that depends on concrete MDP - there are definitely MDPs where it is inconsistent with coverage, but I think one can come up with an MDP where it is possible. $\endgroup$
    – Kostya
    May 15, 2021 at 23:57
  • $\begingroup$ Thank you. Another reason why such an update might make sense is the following. Say the initial target policy specifies an action $a$ in state $s$ in $T-1$. Suppose the updated value of $Q(s, a) $ is greater than 0, and all other initial $Q(s, a') <= 0$. Then if $Q(s, a2) > Q(s, a)$, and even if the behavior policy takes actions a2 from time to time, any experience from that would never be used to improve the target policy. But updating even when the sample action is inconsistent with the target policy can help improve the action under the target policy. $\endgroup$
    – Curious2learn
    May 16, 2021 at 0:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .