We thank the Reviewer for the insightful comments and the time spent reviewing the paper.

1. The technical analysis lacks strong theoretical justifications [...].

We argue that the theoretical analysis is valid and supports our claim that iDQN has a theoretical benefit over DQN. In the revised submission, we further clarify Section $5$ in order to ease the understanding. We stress the point that using an already-published theorem does not make the theoretical analysis weaker. In Section $5$, we now propose two different points of view. In the first one, we consider iDQN without target networks and demonstrate that each approximation error is minimized with $K$ times more gradient steps than with DQN. In the second point of view, we justify why the following approximation errors are controllable when using iDQN as opposed to DQN, which uses a naive approach.

2. Concerning the computation requirement, [...].

We face the problem that an algorithm takes a different amount of time to run depending on:

• the type of GPU used to run the algorithm. Our cluster has different types of GPUs, which makes the comparison hard to make (see table underneath).
• the number of seeds that are run in parallel.
• the Atari game. Some games take longer to run simply because the emulator takes longer to generate the next step.
• the performance. Better algorithms are more likely to generate longer trajectories. This also has an impact on the running time.

Here are some examples to illustrate our point:

A: RTX 4090 B: RTX 2080Ti, RTX 3080Ti, RTX 3090, or A5000 GPU

For those reasons, we changed the sentence in the paper to say that the running time of iDQN is comparable to the one of IQN on the same hardware for the same Atari game.

3. The ablation study and discussion section provide an interesting discussion on the hyperparameters [...].

We agree with the Reviewer. We further clarified those claims with $2$ new ablation studies on the $2$ hyperparameters in Figure $9$ middle and right of the revised submission.

4. Is an open-source implementation of the code [...].

We invite the Reviewer to have a look at our code in the appendix. We will turn the GitHub public upon acceptance.

Thank you for the replies that clarify most of my questions. I thus currently maintain a positive assessment of the paper.

Concerning the code, I still do not see it. I suppose that I am missing the obvious... In which part of the appendix is it? Or do you mean the pseudo-code in Algorithm 1, which is different than open source code?

We thank the Reviewer for the extensive feedback.

1. Although intuitively sound, the main idea lacks sufficient theoretical support. [...].

We respectfully disagree about this. We believe that there is a misunderstanding and hope that Section $5$ of the new submission clarifies it. We think that the example brought by the Reviewer is misleading for the general understanding of the theoretical benefit of iDQN. We insist on the fact that it is crucial to compare the behavior of iDQN with the behavior of DQN in the example given by the Reviewer. In the revised submission, we now tackle this specific case in Figure $6$ and the text explaining this figure. The approximation errors corresponding to the downstream networks can indeed vary along the training, especially when the target networks of iDQN get updated. Nonetheless, we show that those approximation errors are bounded by a controllable term as opposed to DQN, which only takes the last online network as a starting point to learn the approximation error of the subsequent step. In simpler words, while DQN has a naive approach to minimize the approximation errors corresponding to the subsequent steps, iDQN proposes a way to pre-train the next online $Q$-function.

2. There is weak empirical evidence that learning many Bellman iterations in parallel is feasible [...].

We believe that this comment is linked with the first point and hope that the answer helps clarify the concern. We now have updated the submission and provided significant additional evidence that learning many Bellman iterations brings a boost in performance. Indeed, Figure $7b$ of the revised submission shows that iDQN + $3$-step return is performing on the level of advanced distributional methods while not learning the distribution of the return. Figure $8$ illustrates that the combination of iDQN with IQN is outperforming iDQN and IQN.

Concerning the experiment on Car-On-Hill, we provide the following table showing the distance of the current estimate $V^{\pi_k}$ to the optimal $Q$-function $|| V^* - V^{\pi_k} ||$:

When $K$ increases, we observe a clear decrease of the considered distance.

3. The separate network heads for iDQN are split immediately after the convolutional layers, [...].

The cost of splitting the heads after the last convolutional layer can be quantified by the spatial complexity and the temporal complexity. Regarding the spatial complexity, we provide a thorough analysis in Section $C$ of the appendix. This analysis shows that the increase in spatial complexity is negligible compared to the memory required for storing the replay buffer. For the temporal complexity, in theory, it is possible to fully parallelize the additional computations required by iDQN such that it is reduced to the temporal complexity of DQN. In practice, we observe an overhead comparable to IQN. We believe that the approach proposed by iDQN is still worth it, considering the theoretical and experimental advantages that it brings.

We want to point out a misconception brought by the review. The boost in performance given by iDQN over DQN is not a direct consequence of the fact that iDQN is using more parameters. Indeed, in iDQN, the actions are sampled from a single network having the same amount of parameters than a DQN agent. It is the way the networks are trained that brings a boost in performance.

4. The target-network update frequency is faster for iDQN than the baseline DQN [...].

We provide a new ablation study in Figure $8$ right of the revised submission in which we set the rolling step frequency of iDQN to be equal to the target update frequency of DQN ($8000$). In this experiment, we observe that iDQN greatly outperforms DQN. This is due to the fact that iDQN performs $4$ times more gradient steps per approximation error than DQN while having the same overall number of gradient steps.

5. The paper would benefit from a stronger discussion of $n$-step returns, [...].

We kindly ask the Reviewer to have a look at the new submission in which new experiments with $n$-step return have been added. We agree with the Reviewer that an $n$-step return can be seen as a stochastic approximation to $n$ iterations of the (on-policy) Bellman operator; however, these $n$ iterations are directly included in the reward instead of being learned in a chained manner like iDQN proposes.

Thank you for noticing this mistake. We now cite the suggested work for $n$-step return.

We thank the Reviewer for the insightful comments and feedback. We appreciate the fact that the appendix was meticulously studied.

1. I had trouble understanding the intuition the author's [...].

We believe that understanding what we call "learning the Bellman iteration" is a major point for the general comprehension of our work. Therefore, we hope that the following clarification will be useful to clear all doubts. The optimal $Q$-function is the fixed point of the Bellman operator. DQN uses the fact that the Bellman operator is a contracting operator. Thus, iterating multiple times over this Bellman operator can lead any random $Q$-function to the desired fixed point. Theoretically speaking, DQN applies the Bellman operator when computing the target, as explained in Section $3$. Due to the use of function approximation, DQN needs to first learn the target before applying the Bellman operator a second time. This step of learning the target is what we call learning the Bellman iteration.

Nevertheless, we take the Reviewer's opinion into account and, in the revision, we now use the term: “minimizing the approximation errors” in Section $5$.

2. The theoretical analysis seems very informal [...].

We believe that there is a misunderstanding here since the $Q$-functions used in iDQN are the same as the ones used in the theorem. We stress that DQN and iDQN are performing approximate value iteration. As written in Section $5$, the loss of DQN $(r + \gamma \max_{a'} Q_{k-1}(s', a') - Q_k(s, a))$ is an unbiased estimator of the approximation error $||\Gamma Q_{k-1} - Q_k||_{2, \nu}^2$ and the same goes for iDQN. We further clarify that part in Section $5$. We would appreciate some feedback from the Reviewer to know if this has improved the understandability of the section. We hope that this explanation togethet with the clarification brought in the answer of point $1.$ help resolve this misunderstanding.

3. It's not clear whether the comparison to DQN is fair [...].

We point out that the comparison to DQN is not only made for the same amount of gradient steps but also for the same amount of samples. The latter is the usual way of comparing algorithms for the Atari benchmark. In order the respond to the last part of the comment, we added an experiment in Figure $8$ left of the revised submission. In this experiment, we set the rolling step frequency to be equal to the target update frequency of DQN ($8000$). In that case, both algorithms have access to the same amount of Bellman iterations. In the same figure, we added an experiment in which DQN performs $4$ times more gradient steps than DQN (Adam), as asked by the Reviewer. We see that the performances drop while iDQN greatly outperforms both versions of DQN.

4. The ablation study is quite limited.

We understand the request. We invite the Reviewer to check the revised submission in which we added several ablation studies corresponding to each point raised by the review. A description of the new ablation studies is provided in the general response.

5. Why does iDQN have 4 set convolutional layer parameters [...].

Looking at Figure $11$, there are $2$ set of convolutional layers for online networks and $2$ set of convolutional layers for target networks. Only the online networks are shown in the Figure $11$. As raised in point $11.$, we have modified the figure to avoid any possible confusion.

6. Does having several online/target network provide any benefits [...].

Yes, it does. As we now show in Figure $17$ of the revised submission, the networks are more flexible when they are independent hence allowing them to further explore the space of $Q$-function.

7. Does this idea of having many online/target networks help [...].

Please find a new ablation study to answer this question in Figure $9$ middle. When $T=1$, iDQN might suffer from the stochasticity of the location of the online $Q$-functions as shown with the experiment on Asterix.

8. What is the effect of rolling online/target networks? [...]

The rolling step allows iDQN to regress the following Bellman iteration. After the first rolling step, iDQN learns from iteration $2$ to $K+1$ instead of from iteration $1$ to $K$. Without rolling steps, iDQN would be stuck at $K$ Bellman iteration, and the fixed point could not be reached. With a fixed amount of gradient steps, more Bellman iterations are not always better since each Bellman iteration needs to be learned properly. We added an experiment in the revised submission to support that point. In Figure $9$ right, we decreased the rolling step frequency from $R=6000$ to $R=100$. In Breakout, iDQN with $R=100$ has access to $60$ times more Bellman iterations than iDQN with $R=6000$ while performing worse.

We thank the Reviewer for the useful suggestions and comments.

1. I'm a bit of two minds about this work in that the approach is interesting, [...].

We now provide more experiments in the new submission to show the benefit of iDQN. We want to highlight the new experiments on iDQN + 3-step return, presented in Figure $7b$. iDQN + 3-step return achieves similar results to strong distributional approaches (Rainbow, IQN + 3-step return, and Munchausen DQN + IQN + 3-step return).

2. Similarly while iDQN can be combined with IQN (as a stand in for newer, more complicated algorithms) [...].

We believe that this point is related to the answer of point $1.$. Furthermore, we added a more comprehensive study on the combination of IQN and iDQN in Figure $8$ (left). iIQN is now the combination of iDQN and IQN with $64$ quantiles and $64$ target quantiles (like the original version of IQN) instead of $32$ quantiles and $32$ target quantiles used in the first submission. We stress the fact that REM is using an ensemble of $Q$-function to sample actions, while in iDQN, the actions are sampled from a single $Q$-function. Nevertheless, we added a specific figure for the comparison (see Figure $20$).

3. Finally, if we look at the extended 54 Atari experiments [...].

Similarly to point $2.$, we believe that this point is related to the answer to point $1.$. Moreover, in this work, we decided to focus on the interquartile mean since it has been shown to be more appropriate to differentiate algorithms [1]. Looking at the number of games a method is outperforming another method does not take into account the gap between the scores in each game. Overall, iDQN overtakes DQN on $30$ Atari games while losing on $23$ games and being on par on $1$ game.

4. In particular it would be helpful for the authors to address [...].

We believe that this comment no longer applies to the revised submission. We hope that the additional experiments satisfy the Reviewer.

[1] Rishabh Agarwal et. al. Deep reinforcement learning at the edge of the statistical precipice. Neurips, 2021.