Below is the off-policy every visit MC prediction algorithm for estimating $V\approx v_{\pi}$, which I took from coursera. enter image description here

It seems to me that this algorithm is not correct. Let me explain why. Assume that $t=T-1$ and let $\pi(A_{T-1}|S_{T-1})=0$, which means there is no possibility for target policy $\pi$ to go from $S_{T-1}$ to terminal state via action $A_{T-1}$. Hence, based on this observation we should have $V(S_{T-1}) \approx v_{\pi}(S_{T-1})=0$. However, the algorithm in the pseudoce returns $V(S_{T-1}) \approx v_{\pi}(S_{T-1})=R_{T}$. What do you think?


1 Answer 1


The weighting calculation ignores how the current action $A_t$ was chosen.

The action being evaluated does not need its probability adjusted by importance sampling, only future actions. This is because you have "already decided" to evaluate/update a particular $Q(s,a)$ and any probabilities of being in that part of the trajectory do not come into play (they do affect approximators such as neural nets, but that is a secondary effect that is often ignored). More formally, updating $Q(s,a)$ is conditional on you having a record $S_t = s, A_t = a$, so you do not take into account the probabilities of that happening. Whilst the return from that point on is a sample from a distribution including all the probabilities for observing $A_{t+1}$ to $A_{T-1}$ which you do need to adjust for if you are observing results from a different policy to the one you want to update.

An off-by-one relationship where you only weight for future actions is maintained simply by having the $W$ update at the end of the loop, after the Q update for the same timestep. In fact $W$ is being updated ready for calculating the weightings to apply to the previous timestep (previous because the loop is decrementing $t$). At $t = T-1$ there are no future actions, and you have not been around the loop even once yet.

When you get to the subject of off-policy TD control later on, you can also ignore how the last action in the partial trajectory was chosen, because you will use the target policy's action instead. Which means single-step Q learning doesn't use importance sampling at all.


You must log in to answer this question.

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