Recently, I have read the “Reinforcement Learning: An Introduction” 2nd Edition, and I found that the pseudo-code relevant to the incremental implementation of off-policy learning is weird, the weight updating statement seems like defined in an error position. Why does this piece of code assigning the weight value after the value estimation? The final result is slightly different from the different positions of that statement. Therefore, is that pseudo-code wrong?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The pseudocode is correct.
Importance sampling weights do not apply to the action of the action value $Q(S_t,A_t)$ that is being updated, because that action is not being sampled to discover the return*, it is instead the action that you are assessing the return for. That is, you don't care about the relative probabilities of taking an action, and comparing an observed policy with a target policy, when the value you are trying to calculate is based on the assumption that the agent has just taken that action.
More formally, $Q(s,a) = \mathbb{E}[G_t|S_t=s, A_t=a]$ i.e. it is already conditional on the value of $S_t$ and $A_t$, so you don't adjust for their probabilties of occurring. Note this is different to $V(s) = \mathbb{E}[G_t|S_t=s]$ in TD learning based on state values, where you do need to adjust for relative probabilities of $A_t$ under the different policies.
It is important to note too that the code works backwards from the end of the episode. So the return from $S_{T-2}, A_{T-2}$ will include the importance sampling ratio due to decision made at $T-1$, which may occur at different frequencies between $\pi$ and $b$ - that is what the ratio is designed to do, correct for those future differences which affect expected return. Whilst the decision at $T-2$ is already done by point that you want to update $Q(S_{T-2}, A_{T-2})$, it is in the past as far as the action value is concerned.
As you are working backwards and will next update for $T-3$, the point when you would insert any ratio due to choice at $T-2$ is after you have updated $Q(S_{T-2}, A_{T-2})$ but before you start updates for $T-3$. The end of the loop is simplest way to show that in pseudocode.
Another option would be to calculate the ratio at the start of the loop due to looking one step ahead (for $t+1$ time step), and deal with requests for non-existent action $A_T$ by forcing that ratio to be 1. That would be slightly uglier pseudocode, but achieve the same thing, and it is technically correct, because $\pi(\cdot|s_T) = b(\cdot|s_T)$ by definition both policies take no action in the terminal state with probability $1$.
* Technically the state/action pair is still being seen overall depending in part the expected frequency of the state distribution due to behaviour policy (as opposed to target policy), and that can be an issue when using any form of generalisation, such when using an approximation function for Q. However, importance sampling does not address this - it is only adjusting for immediate policy decisions.
