1
$\begingroup$

The off-policy TD learning control using state value function from page 34 of David Silver's RL lecture is: $$ V(S_t) \leftarrow V(S_t) + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} (R_{t+1} + \gamma V(S_{t+1})) - V(S_t) \right). $$

I'd like to change this update rule to action value function Q, something like:

$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} (R_{t+1} + \gamma Q(S_{t+1},A_{t+1})) - Q(S_t,A_t) \right). $$

Then what is the corresponding importance sampling ratio?

Since $A_t$ is already determined (because we are calculating $Q(S_t,A_t)$), I think $\pi(A_t|S_t)$ is definitely 1. But what about $\mu (A_t|S_t)$? Is it 1 or not?

$\endgroup$
2
$\begingroup$

Since $A_t$ is already determined (because we are calculating $Q(S_t,A_t)$), I think $\pi(A_t|S_t)$ is definitely 1. But what about $\mu (A_t|S_t)$? Is it 1 or not?

You could assign values of 1 to each to get the right answer, but the situation is different. You can see that more clearly in the definition of action value, $q(s,a)$:

$$q_{\pi}(s,a) = \mathbb{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1}|S_t=s, A_t=a]$$

The condition on the expectation $|S_t=s, A_t=a$ means that the value of $A_t$ is already assumed. There is no need to know or use the associated probability, and no need to adjust between probabilities of different policies when estimating returns for the first action choice.

In addition, the last action choice used to bootstrap in Q learning is always the maximising action over current Q values. That is an on-policy choice with respect to the target policy $\pi$, so does not need to be adjusted for.

For single-step Q learning, there is no need to use importance sampling to adjust for policy differences between behaviour and target policies. The correct update equation rule is:

$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left( R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t) \right). $$

This does change for n-step updates, where you do need to take account of differences in action choice between target and behaviour policies for $A_{t+1}, A_{t+2}$ up to $A_{t+n-1}$. However, you should bear in mind that $\pi(a|s)$ is zero for any non-maximising action - if you use weighted importance sampling then any trajectory with an exploring action before calculating the TD update contributes zero update.

So, if you are calculating over longer trajectories, in e.g. Q($\lambda$), it is common to see this simplified to a logical test and some kind of shortcut update. You rarely see explicit use of importance sampling - with probability calculations and ratios - in Q learning.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.