2
$\begingroup$

The update formula for the TD(0) off-policy learning algorithm is (taken from these slides by D. Silver for lecture 5 of his course)

$$ \underbrace{V(S_t)}_{\text{New value}} \leftarrow \underbrace{V(S_t)}_{\text{Old value}} + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} (\underbrace{R_{t+1} + \gamma V(S_{t+1}))}_{\text{TD target}} - \underbrace{V(S_t)}_{\text{Old value}} \right) $$

where $\frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)}$ is the ratio of the likelihoods that policy $\pi$ will take this action at this state divided by the likelihood that behavior policy $\mu$ takes this action at this state.

What I do not understand is:

Assume the behavior policy $\mu$ took an action that is very unlikely to happen under policy $\pi$. I would assume this term goes towards $0$.

$$ \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} = 0 $$

But, if this term goes to $0$, the whole equation would become the following

$$ V(S_t) \leftarrow V(S_t) - \alpha V(S_t) $$

This would mean we decrease the value of this state.

But this doesn't make any sense to me, if the 2 policies are very different, we gain little to no information. Therefore, I would assume the value would be unchanged instead of decreased.

What is my misconception here?

$\endgroup$
0
2
$\begingroup$

This would mean we decrease the value of this state.

Yes. This update that reduces the estimate is correct because it adjusts for the inevitable over-estimate of value when the exploration policy selects an action that is more likely in the target policy than in the behaviour policy. This over-estimate must happen, if your agent experiences some actions with a likelihood ratio close to $0$, it must also experience some actions with a likelihood ratio greater than $1$. This follows because $\mathbb{E}_{\mu}[\frac{\pi(a|s)}{\mu(a|s)}] = 1$*, provided the behaviour policy covers the target policy (behaviour policy has non-zero probability for all actions where the target policy has non-zero probability).

Those actions with a likelihood ratio greater than $1$ are not actually better than before due to being taken off-policy, so their value used in the update will be an over-estimate.

It is only in the limit of large numbers of samples that the adjusted value function will converge on a good estimate of the value function for the target policy.

Basic importance sampling can have problems with increased variance due to this effect. In fact the variance can be shown to be unbound/infinite in some cases. I am not sure if it is the case in TD learning, but definitely the case in Monte Carlo with importance sampling. TD(0) does benefit from reduced variance from bootstrapping, so it probably doesn't have unbound variance. Still, it has higher variance than on-policy TD(0).


*

For any fixed state, $s$,

$$\mathbb{E}_{\mu}[\frac{\pi(a|s)}{\mu(a|s)}] = \sum_a \mu(a|s) \frac{\pi(a|s)}{\mu(a|s)} = \sum_a \pi(a|s) = 1$$

$\endgroup$
2
  • $\begingroup$ Great explanation, thank you very much. So it's only when we consider multiple updates it's starting to be a correct update. If we'd have only 1 or 2 it wouldn't be that good. $\endgroup$
    – KoKlA
    Nov 9 '21 at 9:18
  • 1
    $\begingroup$ @KoKlA Yes, although "just one or two" would also be bad in most on-policy TD(0) as well due to initial bootstrap bias. The difference with importance sampling is that you need even more samples. But the benefit is being able to separate the need for exploring from the need to learn a specific target. $\endgroup$ Nov 9 '21 at 9:19

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.