Off-policy n-step learning with DQN

Question

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?

Answer 1

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.