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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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$$

Improve this answer
$\endgroup$
9
  • $\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, 2021 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$
    – Neil Slater
    Nov 9, 2021 at 9:19
  • $\begingroup$ I don't agree on your explanation on the overestimation, because in the tabular case, there is no such thing as overestimation, it's not like Q learning $\endgroup$
    – Alberto
    Jul 12 at 19:32
  • $\begingroup$ Say I throw a coin, and play head with P=1, then the value will be $E[Q(x)] = p(H)Q(H) + p(T)Q(T)$, and if I leave a friend that plays heads and tails with P=0.5 I get $ = E[p(x)/b(x)Q(x)] = p(H)Q(H) + p(T)Q(T)$ $\endgroup$
    – Alberto
    Jul 12 at 19:43
  • $\begingroup$ thus given that he sometimes plays tail, I should not consider any of its rewards coming from them, thus, makes no sense that we should "reduce the overestimation"... instead, in my opinion, the importance sampling ratio should stay in front of the whole update, having $V = V + \pi/b[TD]$ $\endgroup$
    – Alberto
    Jul 12 at 19:45

You must log in to answer this question.

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