Doesn't the n-step Tree Backup algorithm negatively affect the DQN-Agent by creating inconsistent look-ahead targets?

Question

In the text book of Sutton and Barto on page 152 they introduce the n-step Tree Backup algorithm, where the tree-backup n-step return is defined via $$ G_{t:t+n} = R_{t+1} + \gamma \sum_{a \neq A_{t+1}} \pi(a | S_{t+1})Q_{t+n-1}(S_{t+1}, a) + \gamma \pi(A_{t+1}| S_{t+1})G_{t+1, t+n}. $$

Assume we have a sample of the replay buffer and its consecutive transitions $$ (S_{t}, A_{t}, R_{t+1}, S_{t+1}), (S_{t+1}, A_{t+1}, R_{t+2}, S_{t+2}), ..., (S_{t+n-1}, A_{t+n-1}, R_{t+n}, S_{t+n}). $$ Since in Deep Q-Learning, the target policy $\pi$ is usually the greedy-policy, we have $$ \pi(a|S_{t+1}) = \begin{cases} 1, & \text{if } a= argmax_{a}Q(a, S_{t+1}) \\ 0, & \text{otherwise}. \end{cases} $$ Hence, I think we would in general look only up to n-steps ahead rather than always n-steps, since the n consecutive samples from the replay buffer don't guarantee that the transitions happended according to the current policy $\pi$. Doesn't this negatively affect the agent's behavior since sometimes the target is made up of only one timestep and sometimes of several?

Thanks in advance for any help!

Answer 1

Hence, I think we would in general look only up to n-steps ahead rather than always n-steps, since the n consecutive samples from the replay buffer don't guarantee that the transitions happended according to the current policy $\pi$.

This is correct in general in n-step off-policy learners: Whenever exploration chooses an action that the target policy has $0$ probability of selecting, then there is nothing to learn about the target policy from that specific choice. The best you can do is take some other estimate - in TD learning that will be a bootstrap estimate taken earlier than n steps for some state-action estimates. You don't have to do this, but a bootstrap estimate is often better than throwing away the sampled experience (in off-policy Monte Carlo control, you would indeed throw away that earlier experience, and the method can still work in practice though).

It is possible to learn from time steps later than exploration, you just re-start from the new $s, a$ pair (and new count up to n). If this changes the estimate of $Q(s,a)$ so that this exploratory action is better in state $s$, then the target policy will change and what was once exploratory will become part of the target policy.

There is no way around this in off-policy value estimators.

Doesn't this negatively affect the agent's behavior since sometimes the target is made up of only one timestep and sometimes of several?

"Negatively affect" with respect to what?

The main reason for using n-step learning is to find a sweet spot between the bias inherent in bootstrap estimates - worse in TD(0) - and the variance inherent to fully sampled returns from long trajectories - worse in Monte Carlo or TD(1). This reason still applies when the steps that are full samples of experience can vary between $1$ and $n$. There will usually be a value of max $n$ (combined with specific exploration probabilities) between 1 and the full episode length that works better than either of those extremes.

It is worth noting that in the DQN "rainbow" paper, the authors add n-step returns, ignoring the theory regarding truncating with an early bootstrap. They simply store the discounted sum of rewards $r_{t+1}$ to $r_{t+n}$, plus $s_{t+n}$ for e.g. n=4 steps ahead in the experience replay table, regardless of whether the agent took an exploratory action (in addtion, any of the actions might become exploratory with respect to the target policy later because the experience replay table is effectively an offline dataset). In practice this still works better than single-step updates despite the break from theory, at least for relatively low $n$ and $\epsilon$, and the kinds of environments that DQN was developed against (Atari games).