3
$\begingroup$

I'm reviewing the Rainbow paper and I'm not sure I understand how they can use DQN with multi-step learning, without doing any correction to account for off-policiness.

So. I understand how you can use 1-step update off-policy: the reward for a single transition doesn’t depend on the current policy, so you can reuse this experience in the future.

I also understand the point of n-step updates: it’s a trade-off between having high biais with 1-step update (as you get only limited information from a single transition) and having high variance with n-step update (as in that case both the policy and the environment can be stochastic, so you end up adding n random variables together).

What I do not get is how you can use n-step return off-policy, which is what the Rainbow DQN seems to do. With n-step returns you are considering trajectories, and you can’t assume that these trajectories would have been taken if the agent was using the current policy.

If I understood correctly, in the case of policy gradient this is dealt with using importance sampling, which will reduce the impact of policies which are further away from the current one.

But I don’t see the equivalent of this for multi-step DQN?

$\endgroup$
2
$\begingroup$

In the Rainbow approach, theoretical correctness of the off-policy return values is completely ignored, and it just uses:

$$G_{t:t+n} = \gamma^n\text{max}_{a'}[Q(S_{t+n},a')] + \sum_{k=0}^{n-1} \gamma^{k}R_{t+k+1}$$

It still works and improves results over using single-step returns.

They rely on a few things for this to work:

  • $n$ is not large, compared to amount of variability in the environment that occurs over those steps. So the return is usually correct even if there was an exploratory action taken. Many game events (and also real-world physics) have some fuzziness - e.g. as long as in Pong you hit the ball with a part of the paddle, it will be a reasonable result, and only some (literal) edge cases will cause a major difference in rewards.

  • Exploration is low ($\epsilon$ set to $0.01$ or $0.001$)

  • Rewards are sparse, so the n-step return very often only depends on state progression. As long at $S_{t+n}$ is as likely to be reached starting from $S_t$ under both the exploratory and target policies, then the simple returns are approximately correct.

  • The policy changes slowly, maybe taking a million frames to converge to optimal, which is far larger than the replay memory.

From a theoretical basis in Q learning, it would be better to use "up to n-step" returns that truncate at the time step when the action taken diverges from the current learned policy. However, that is more complex, as you have to assess the learned policy at each of the n steps in order to decide when to truncate - I suspect given the researchers know how $Q(\lambda)$ works, that they may have tried this and just found the extra correctness was not worth the extra complexity and CPU cost. In other environments it may be worth the effort to implement this.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks, makes sense! could you expend on how Retrace(lambda) and Eligibility Traces relate to this? $\endgroup$ – MasterScrat Feb 26 '19 at 12:50
  • $\begingroup$ @MasterScrat: I mention $Q(\lambda)$ as that works by truncating the return when it hits an off-policy action choice. Without the trace, extending n-step to $\lambda$ just adds in more sums i.e. $(1-\lambda)^m G_{t:t+1} + \lambda(1-\lambda)^{m-1} G_{t:t+2} + \lambda^2(1-\lambda)^{m-1} G_{t:t+3} . . . . + \lambda^m G_{t:t+m}$ etc where $m \le n$ is the last time step taken on-policy (actually I'd need to double check that equation - don't assume it is correct - but the sense of it should be correct). Using a trace makes it even more complex, as you run updates within the n steps. $\endgroup$ – Neil Slater Feb 26 '19 at 13:02

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.