1
$\begingroup$

Suppose in your replay buffer you store only $(s_t, a_t, r_{t+1}, s_{t+1})$.

Instead of finding the optimal Q function with this Bellman backup

$Q(s_t, a_t) \leftarrow Q(s, a) + \alpha [R_{t+1} + max_{\hat{a}} \gamma Q(s_{t+1}, \hat{a}) - Q(s_t, a_t)]$

It seems to me like for any stored experience, you can generate an action $a'$ according to your current policy $\pi$ for $s_{t+1}$, and then use this Bellman backup

$Q(s_t, a_t) \leftarrow Q(s, a) + \alpha [R_{t+1} + \gamma Q(s_{t+1}, a') - Q(s_t, a_t)]$

There are already answers to this previously asked question, but those assume that you store the action $a_{t+1}$ you actually took in $s_{t+1}$ and use that in your TD error estimate like so.

$Q(s_t, a_t) \leftarrow Q(s, a) + \alpha [R_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)]$

That's obviously wrong since you're sampling actions from an irrelevant policy distribution in that case and it doesn't make sense to reuse experiences. But if you generated new actions again for every sample experience, isn't that a correct update for your current policy? Of course, in practice this would be pretty inefficient since you would have to do a forward pass for every sample experience in your batch.

$\endgroup$
1
$\begingroup$

Of course, in practice this would be pretty inefficient since you would have to do a forward pass for every sample experience in your batch.

In fact if you were using $\epsilon$-greedy, you would need to find $a' = \text{argmax}_{\hat{a}} Q(s_{t+1}, \hat{a})$ in any case most of the time in order to find the greedy action, so this has more or less the same cost as Q-learning.

Is your idea, to use experience replay and re-generate $a'$ used in

$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha [R_{t+1} + \gamma Q(s_{t+1}, a') - Q(s_t, a_t)]$

partially off-line (due to experience replay delay), but still on-policy?

I think the answer is a cautious "maybe yes, but it loses some advantages of on-policy".

The value of $a_t$ is from the old policy, so you may be updating a record that you no longer care much about. However, that doesn't stop it being on-policy, and is more generally a problem with experience replay. In some cases it is a benefit, because re-visiting older experience might discover that actually the value of an older specific state/action pair is still relevant once you get closer to convergence.

More worryingly, you have no guarantee that you have or will ever visit $(s_{t+1},a')$ in practice. As such it might be an on-policy action selection, but it shares bootstrapping problems with off-policy, which will result in higher variance and problems converging when used with function approximation.

This combination of the two points could make the action choice $a'$, one that was never actually taken under any policy, and one that you would not naturally be considering under the current policy - for instance $s_{t+1}$ could be unreachable under the current policy (although for $\epsilon$-greedy that would never be the case). I think that at least some researchers would call that an off-policy update.

$\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.