A Continual Learning Perspective to Entropy Regularized Deep Reinforcement Learning

Q4. Ablation on more tasks

A4. We are currently running the ablation regarding the choice of $M$ on all Mujoco tasks. We thank you for your suggestion and will complement our answer as soon as we have more results.

Dear Reviewer b4CY,

Thank you for your valuable feedback. We provide a preliminary answer to your comments below, and will complement our answer as soon as we have the additional ablation experiments you requested.

Q1. Relevance of the tasks

A1. In your review, you claim that

The classic control environments are, in my opinion, not informative when comparing RL algorithms. The same holds for the Minatar environments.

In our paper, we cite the prior work Ceron et al. 2021 whose claims appear to be in contradiction to your statement above. They show that the Classic Control + MinAtar environments are sufficiently rich to reach comparable conclusions when comparing RL algorithms as with a more complex testbed. We would appreciate if you could clarify whether you disagree with the claims of Ceron et al. 2021 and your reasoning for this.

Q2. Lacking comparison with SAC

A2. Reiterating our answer to reviewer U8vT, we would like first of all to remind the reviewer that StaQ is only compatible with discrete action spaces and hence we only use discrete-action deep RL baselines. In the paper, we consider four baselines: TRPO, PPO, DQN and Munchausen DQN (M-DQN).

Soft Actor Critic (SAC) is not compatible with discrete action spaces, but M-DQN can be seen as an adaptation of SAC to discrete action spaces with an additional KL-divergence regularizer. Please see the discussion in the M-DQN paper (Vieillard et al. 2020) on page 3, between Eq. (1) and (2). The M-DQN paper also discusses Soft-DQN in Eq. (1), which they call the "most straightforward discrete-actions version of Soft Actor-Critic (SAC)", and which can be obtained from M-DQN by simply setting the KL-divergence regularization weight to zero. However, we did not consider Soft-DQN as a baseline because the M-DQN paper shows that M-DQN generally outperforms Soft-DQN.

We also note that by setting $M=1$ in StaQ, we remove the KL-divergence regularization and only keep the entropy bonus. This baseline can also be seen as an adaptation of SAC to discrete action spaces: indeed, if we set $M=1$ in Eq. (14) we recover the policy logits $\xi_{k+1} = \frac{\alpha}{1-\beta^M}\sum_{i=0}^{M-1}\beta^i Q_{\tau}^{k-i} = \frac{\alpha}{1-\beta}Q_{\tau}^{k} = \frac{Q_{\tau}^{k}}{\tau}$ (because $\alpha \tau = 1-\beta$), such that $\pi_{k+1} \propto \exp\left(\frac{Q_{\tau}^k}{\tau}\right)$. While for SAC, the actor network is obtained by minimizing this problem (Eq. 14 in Haarnoja et al. 2019) $\pi_{k+1} = \arg\min \text{KL}\left(\pi \Big| \frac{\exp\left(\frac{Q_{\tau}^k}{\tau}\right)}{Z_{\text{norm.}}}\right)$, but in the discrete action setting, we can sample directly from $\exp\left(\frac{Q_{\tau}^k}{\tau}\right)$---which is the minimizer of the above KL-divergence term---and we do not need an explicit actor network. As such StaQ with $M=1$ could be seen as an adaptation of SAC to discrete action spaces. Please note that we have already included $M=1$ in the ablation study for some environments.

In summary, because M-DQN outperforms Soft-DQN and because StaQ with $M=1$ resembles SAC (as it uses only soft Q-functions and no KL-divergence regularization), we do not believe that Soft-DQN would be useful as an additional baseline, however we would be open to feedback on this.

Q3. Intention behind Fig. 3a

A3. The main claim of this paper is that we are able to implement a Policy Mirror Descent like algorithm with strong theoretical guarantees. The theory guarantees monotonic improvements and therefore we wanted to see if in practice we have more stable monotonically increasing performance compared to baselines. For many tasks, this can be observed at a glance, as StaQ runs demonstrate the lower variance in the returns. However, in tasks such as SpaceInvaders in Fig.2, we can see a comparable variance between StaQ and M-DQN. Fig. 3a zooms into the performance of StaQ and M-DQN on SpaceInvaders by plotting the centered returns of the individual runs. It shows that the variance in StaQ is not caused by large performance oscillation within runs, and in fact we still see the same smooth return curves as observed on other environments in Fig. 7; but simply the variance is due to one seed of StaQ that was more succesful than the others, likely due to better exploration, which is a component beyond the scope of this paper. We also note that the other two seeds did not fail in this plot, and in fact the average performance of StaQ on SpaceInvaders is slightly higher than that of M-DQN. It just so happens that one seed performed better than all other seeds, including the runs of M-DQN.

Dear Reviewer,

Thank you for your detailed response and for articulating so clearly your point of view. Even if we may not agree on all points, it at least leads to an interesting discussion. Please see below for our comments.

Q1: Relevance of the tasks and challenges of exploration

A1. We would like to point out that the authors of Ceron et al. 2021 do in fact use the MinAtar environments in several subsequent publications, see for example Willi et al. 2024, Araújo et al. 2021 and Ostrovski et al. 2021. More generally, the Atari environments are a widely-used standard benchmark for discrete-action RL, and MinAtar is designed to replicate those environments except with a more compact feature representation and faster runtime.

If we were to exclude the MuJoCo environments, we would still be able to see the same overall picture: that StaQ is capable of achieving performance comparable to or above the baselines, and with better stability, but it struggles with hard exploration problems. Indeed, out of the 9 Classic Control+Minatar environments, 4 of them are classified as hard exploration problems by Ceron et al. 2021 (see page 8), and 3 out of the 4 problems where StaQ doesn't outperform baselines are on these hard exploration tasks. It seems that on these hard exploration problems, $\epsilon$-greedy exploration used by DQN and M-DQN is a better exploration heuristic than sampling from the stochastic policy. This is not true only for StaQ but also for PPO/TRPO that similarly use a stochastic policy and struggle on these tasks. We do not know exactly why is this the case, but perhaps using deterministic policies is more likely to achieve ''deep exploration'' as discussed in Osband et al. 2016. Fortunato et al. 2018 also show that exploration with deterministic policies generally works better than stochastic ones on several benchmarks.

Nonetheless, StaQ can be combined with any behavior policy for exploration, but exploration is a challenge of its own that is beyond the scope of this paper. Since our focus is rather on the stability of deep RL, we added the 5 MuJoCo tasks as an additional testbed since they have dense rewards, simplifying exploration, and leaving the proper use of function approximators as the only challenge. We agree with you that the results on MuJoCo strengthen the claim of the paper, but in no way do they negate the results on other environments. They rather complement them since if we remove the 4 hard exploration problems from Ceron et al. 2021, we are only left with 5 environments, which is perhaps too few.

Q2: Adding discussion on SAC baseline

A2. We agree on this and we have updated the manuscript to make the connection between M-DQN/Soft-DQN and StaQ more explicit. Please see the mention (red text) in the Baselines paragraph of Sec. 6 and the full discussion in Appendix D. Thank you for this feedback.

Q3: Intention behind Fig. 3a

A3. Regarding why M-DQN has better exploration, we refer to A1 above. Nevertheless, we agree that Fig. 3a may be confusing to the reader. We plan to update that figure to clarify this point. We will update you when the manuscript has been updated to incorporate your feedback.

Q4. Ablation on more tasks

A4. Following up from our previous response, we have now updated the manuscript to include ablation studies for a range $M$, and have also ablated the choice of $\epsilon=0.05$ on more MuJoCo tasks. Please see Fig. 9 in App. B.3.

Dear Reviewer,

Following up on Q3, we have now updated the manuscript to incorporate your feedback regarding the clarity of Fig. 3a. The related changes to the text is in green. We now plot the Hopper environment rather than SpaceInvaders, as we believe this more clearly demonstrates the improved stability of StaQ, and is a more representative example. Note that, as before, we perform the same stability comparisons for a range of Classic Control + MuJoCo environments in App. B.2.

We hope that this addresses your concerns, and we welcome any further feedback on this.

Dear Reviewer,

We thank you again for following up on the discussion, and we are happy to see that all your questions except the choice of environments have found a positive resolution. Let us point out that the experimental part is only one aspect of our paper, and that our contributions comprise a theoretical aspect, that extends the analysis of approximate PMD to a more practical finite-memory setting. In the context of a theoretically grounded setting, we believe that evaluating our algorithm on Classic Control tasks is relevant. Please see the discussion below.

Validity of Classic Control benchmarks. We believe it is insightful to confirm our theoretical results on tasks where exploration and policy evaluation are easier, in order to leave policy update as the only differentiating factor between StaQ and baselines. The Classic Control tasks fulfill this need and we see greatly improved performance and stability over baselines. Of course, if our empirical evaluation was limited to these smaller dimensional problems, one would naturally wonder how StaQ would scale to larger environments. Luckily, this is not the case in this paper and we also evaluate StaQ on larger testbeds, namely MuJoCo and MinAtar, comparing favourably with the baselines.

Feedback on the theoretical contributions. Our exchange has only focused on the empirical merits of our contributions. While we are grateful for your feedback on this aspect, as it helped us improve the paper, we still hope that you have assessed the merits of our paper with all of our contributions in mind. In the present state however, your review does not mention in any capacity our theoretical results, neither in good or bad, and we would really appreciate your feedback on this aspect. If some aspects of our contributions, or their relation to existing literature are unclear, we would be happy to use the extended discussion period to clarify them.

As a reminder, we have analyzed two entropy regularized Policy Mirror Descent (PMD) like algorithms that only keep in memory the last $M$ Q-functions. The exact entropy regularized PMD form of a policy at iteration $k$ is given by

$\pi_k\propto \exp\left(\alpha \sum_{i=0}^k \beta^i Q^{k-i}\right)$ with $\beta < 1$ a discount factor. The intuition is that since $\beta^i$ vanishes for large $i$, deleting a very old Q-function will have little impact on the policy. However, in our theoretical analysis we show that naively deleting the last Q-function (Vanilla Finite-Memory EPMD, Sec. 4.1) results in an irreducible error that prevents convergence. A significant theoretical contribution of our paper is proving that there exists a modified policy update rule (Weight-corrected Finite-Memory EPMD, Sec 4.2) for which exact convergence is guaranteed, provided the memory size $M$ is sufficiently large. We also derive an expression of a minimal $M$ as of function of $\beta$ and the MDP's discount factor $\gamma$. We believe this is a strong contribution to the community, as it leads to practical algorithms with clear empirical benefits and a solid theoretical framework to build on, and we would be happy to hear your thoughts on this aspect of our work.

Thank you for your reply.

"As stated in the paper (Line 366), the Stacked NN architecture that allows us to evaluate StaQ in the high regimes with reasonable scaling is only compatible with MLPs but not with CNNs for now."

I did not note this line when reading through the paper. I believe it is very important to mention this in abstract as well as the experiments section. In the experiments section, link it to the reason for not conducting experiments on complex testbeds, instead of only referring to Obando-Ceron et al. 2021. Since you have found a mistake in my message, I believe it is only fair that I undo my action on yesterday.

Besides this, I still keep my initial concerns.

"Of the 4 tasks where StaQ underperforms, 3 are classified as hard exploration by Ceron et al. 2021" "StaQ performance on Classic Control/MinAtar hard exploration tasks"

They actually state: " It is worth highlighting that both Seaquest and Freeway appear to lend themselves well for research on exploration methods, due to their partial observability and reward sparsity." There is no statement of a hard exploration task. It is not common practice to name a task that vanilla DQN can solve a "hard" exploration task. Hard exploration tasks are Minigrid or Montezuma's revenge or Vizdoom. This has been the problem from the beginning in this discussion, where you overstate both the significance of the evaluation environments and of StaQ's performance. I see that this is further done in Section 6.4:

"StaQ is generally competitive with the state-of-the-art, but it might fail on some environments such as MountainCar or a few MinAtar environments. "

Could the authors please explain which algorithms are state-of-the-art? For Mujoco, TRPO is from 2015, and PPO is from 2017. How did the authors reach the conclusion that StaQ is competitive with the state-of-the-art? Also the phrase "but it might fail on some environments such as MountainCar or a few MinAtar envronments" is quite confusing. You test on 5 MinAtar environments, where StaQ significantly underperforms on 3/5 environments. In other words, it fails in the MinAtar domain. As I said before, the performance and evaluation claims do not make sense to me.

Dear Reviewer, thank you for your response. We really appreciated the continued discussion on this.

Hardness of exploration. Our use of the terminology "Hard Exploration" is relative to the full set of tasks that we consider, to contrast MountainCar/Freeway/Seaquest with e.g. the MuJoCo tasks, and to understand why StaQ (and PPO/TRPO) struggle on those environments. We could have simply called them "harder exploration" tasks rather than "hard exploration", if you will. Of course, there are tasks that are much harder in terms of exploration than MountainCar or these MinAtar tasks, and you named a few of them.

Exploration challenges specific to StaQ and Max Ent algorithms. As you noted, M-DQN/DQN do not struggle on the MountainCar/MinAtar tasks, but they are still problematic for StaQ. Although these problems are not the hardest, they still have a sparse reward structure, which makes it challenging in terms of exploration for StaQ and any algorithm following the maximum entropy principle: if a reward cannot be observed from the initial uniform policy, then this initial uniform policy acts as an attractor because the agent observes no reward and the initial uniform policy is the one maximizing entropy.

This is precisely what happens in MountainCar. One can easily check on this problem that if you sample actions uniformly at random you can do millions of steps and you might never observe a reward. As such, due to the maximum entropy principle, StaQ prematurely converges to the uniform policy and never leaves this local optimum. In contrast, algorithms that explore with deterministic policies seem to still eventually achieve some rewards that enable learning (completely by chance, as none of the baselines implement a theoretically sound exploration method).

Why we include harder exploration tasks while it is not the focus of the paper. As we already said, any behavior policy can be combined to StaQ to properly solve the exploration problem, but since exploration in deep RL is still pretty much an open question we thought it better to focus only on our main contribution which is the policy update. We believe this is valid as there are still many tasks that have dense rewards (e.g. MuJoCo tasks), and thus easier exploration, but in which existing deep RL algorithm can still show unstable learning dynamics which is the main point we want to address in this paper. Nonetheless, we thought it good to still have a section (Sec 6.4 + App B.5) dedicated to exploration to emphasize, perhaps contrary to popular belief, that the maximum entropy principle is not a proper answer to the exploration/exploitation trade-off in RL, and that our paper only sees entropy regularization as a way to stabilize learning, not improve exploration.

Failure on a few MinAtar tasks. If you see Fig. 12 in App. B.5, where we have tried several entropy bonus weights, you can see that with a lower entropy weight we can reach a return of about 50 on Freeway, not too far off from strongest baselines. So talking about failure of StaQ in this case is perhaps a bit strong as it seems to be more of a hyper-parameter tuning problem. But we agree with the general sentiment that StaQ underperforms in this set of tasks, and we do not see the same high mean low variance return plots as in the other testbeds.

Dear Reviewer oaMK,

Thank you for your valuable feedback. We address each comment in detail to the best of our ability but would like some clarification on Q1 to make sure we are providing an adequate answer.

Q1/Q3. Plasticity vs stability and suitability of the RL tasks

A1. StaQ is composed of an explicit Q-function approximated by a neural network, and an optimization-free actor repesented by an average of past Q-functions. First of all, we note that there is no loss in plasticity compared to the state-of-the-art for the Q-function in StaQ. Each $Q_{\tau}^k$ is trained independently, thus we introduce no restriction or change to the learning procedure and use a standard MLP architecture for the Q-function. Stability is introduced in the actor, through the averaging over past Q-functions, which is a standard entropy-regularized Policy Mirror Descent (PMD) operation that is well understood and justified theoretically. While it will slow down the rate of change of the policy depending on the weight of the KL-regularizer that acts as the learning rate, in no way does it compromise plasticity or performance and wouldn't prevent convergence to an optimal policy.

We do not understand exactly what you mean when stating that the tasks are

relatively static and do not require the development of new skills

To us, this sounds like an exploration problem that is conducted by the behavior policy that ensures that all state-action pairs have been sufficiently sampled. It is an orthogonal challenge to the stability of the policy update tackled in this paper (see also the discussion in A3 for Reviewer U8vT). Provided that exploration is handled well, and since we impose no restriction to the learning of the Q-function, we do not believe there is any conceptual hurdle preventing StaQ from ''developing new skills''.

However, we might be misunderstanding your question, especially since you cite Meta-World. Perhaps you mean the development of new skills in the continual RL sense, as in a reward function that changes with time? That would still not alter the convergence of PMD, although it may slow it down if the new reward function is too different from previous one. Nonetheless, our paper only covers single-task RL with a fixed reward function. We chose the tasks in our paper based on suggestions and common usage in prior work, as discussed in Line 414. Namely, we have used all 9 tasks suggested by Ceron et al. 2021 for comparing discrete action deep RL algorithms, and have included the MuJoCo environments as additional standard RL tasks. What new insights do you believe the Meta-World tasks specifically would add to our experimental evaluation?

Q2. Inference and training speed.

A2. We will update the paper and add a table detailing the inference and training speeds. Thank you for the suggestion.

Q4. Ensemble Bootstrapping for Q-Learning.

A3. The referenced paper (Peer et al. 2021) describes EBQL, an extension of Double Q-Learning (Hasselt et al. 2015) to an ensemble of arbitrary size. We would like to emphasize that EBQL is an ensemble over the current Q-functions, to reduce bias in policy evaluation, whereas the policy update step of StaQ is averaging over past Q-functions, to stabilize policy update. These components are independent, and as mentioned in A1, any policy evaluation algorithm can be used in conjunction with StaQ, including EBQL.

In our policy evalution we do use an ensemble of two (current) Q-functions in StaQ, but it is not sufficient to stabilize learning. This instability can be seen e.g. in the ablation of Fig. 3b with $M=1$, which removes our contribution to the policy update and only leaves the effect of the ensembling over Q-functions. Currently, we have only presented the $M=1$ ablation for Acrobot, however we plan to add these plots for all MuJoCo tasks in the Appendix.

It would be interesting to explore the impact of different policy evaluation mechanisms, including EBQL, CrossQ, EMIT and many more on the policy update of StaQ. The stability of the policy update in StaQ makes it a good testbed, as it should reduce learning noise and leave only differences in policy evaluation algorithms. However, we leave this to future work as we believe that these improvements are independent of the policy update proposed here.

Thank you for your detailed explanation.

I agree that the StaQ method has successfully improved performance per each single task. However, since the tasks used in the study are not frequently utilized in Continual RL, as far as I know, I believe it is necessary to justify why these specific tasks were chosen to address the dilemma that commonly arise in Continual RL. Although the paper by Ceron et al. (2021) mentions that these tasks provide valuable scientific insights, it does not mean that these tasks are suitable for validating each algorithm in terms of the dilemma.

I am curious to hear the authors' opinions on my thoughts above.

Dear reviewer,

Thank you for your quick reply.

Is stability of StaQ at the expense of performance? Plasticity in the Continual Learning (CL) literature is measured by performance on the task (De Lange et al., 2021). We completely agree with you that stability could have been at the expense of performance, but clearly this is not the case for StaQ as we have more stable learning and good performance compared to baselines. This good trade-off is not surprising for parameter isolation methods in the CL literature (please see Sec. 6 in De Lange et al., 2021 for comparison of CL approaches), and the cost of parameter isolation methods is rather computational.

Now, if the question is whether the RL tasks are challenging enough to be used as RL baselines, we point out again the work of Ceron et al. 2021 that proposes a set of 9 tasks to compare discrete action deep RL algorithms, which we have all used. To that we have added 5 Mujoco tasks (Hopper, HalfCheetah, Walker, Ant and Humanoid) which are common in the deep RL literature. We believe that results on these 14 tasks support our claim with a certain level of confidence that the stability of StaQ is not at the expense of its performance, and complement our theoretical contributions that showed that the Policy Mirror Descent-like algorithm that we proposed does not limit performance as it converges to the optimal policy.

Thank you for your comments.

The reason I highlighted Meta-World tasks was that the plasticity-stability dilemma is frequently studied in the tasks (e.g., https://arxiv.org/pdf/2209.13900). Developing a method to tackle Meta-World tasks inherently requires addressing both plasticity and stability. Similarly, since your manuscript explicitly mentions the plasticity-stability dilemma, I expected that both aspects—plasticity and stability—would be carefully addressed throughout the work. However, from my perspective, the paper primarily focuses on stability in a single task, as the term "plasticity" is mentioned only in the Introduction, and it is unclear how plasticity is addressed in the context of a single task. Although the authors used the tasks proposed by Ceron et al. 2021, it is necessary to explain whether these tasks are truly suitable for studying the dilemma. I am not insisting that experiments should be conducted specifically in the Meta-World environment but I think it is important to clarify this point.

Please let me know if there is any part I may have missed.

Dear Reviewer,

Thank you so much for following up on the discussion, as we believe we have now identified the source of misunderstanding. In short, this paper is not about Continual RL but about looking at the policy update step in single-task deep RL as a Continual Learning (CL) problem, which opens up a range of novel approaches in the deep RL context. We hope the detailed answer below alleviates any confusion regarding this point. We have also updated the paper (see blue text) to clarify this distinction for the readers.

Are tasks suitable for Continual RL? This paper is not about Continual RL. For instance, in the paper you cited above (Wołczyk et al., 22), a learner is presented a sequence of Markov Decision Processes (MDPs) and the authors investigate if training on one MDP could lead to knowledge transfer to the next MDP. In our setting, a learner sees only one MDP and its performance is only measured on this one MDP. Studying whether knowledge transfers among tasks and if knowledge is retained on older tasks is beyond the scope of this paper.

Despite being limited to a single MDP, single-task RL has still strong ties with CL because of the sequential nature in which data arrives. As mentioned in our paper, we are not the first to draw this parallel, the CL survey of Lesort et al. 2020 discusses this similarity (please see specifically Sec. 2.4.3). Drawing this connection is interesting because it opens up a plethora of CL methods that are not well researched in the deep RL context, but are applicable even in a single task setting. Specifically, in this paper we focus on the entropy regularized policy update problem described below (Eq. 6 of the paper)

The objective of the update can be seen as CL, as we receive a new ''task'' which is to find $p$, a maximum entropy distribution over actions that puts its largest mass on actions with high Q-values, yet, through the KL-divergence term above, we do not want $p$ to differ too much from $\pi_k$, and forget the solution of the previous ''task''. Because of this similarity with CL, existing methods to solve this problem can be categorized with the CL literature lens, for example: Lazic et al. 2021 used a rehearsal method (replay buffer/experience replay in deep RL terminology) to tackle the above policy update, while Schulman et al., 15 uses a parameter regularization approach. While these cover two of the three main classes of CL methods (De Lange et al., 2021), the novelty of this paper is in investigating a method pertaining to the third class (parameter isolation) to tackle this problem, as this class of methods has strong performance in CL benchmarks (See Sec. 6 of De Lange et al., 2021), yet remains largely understudied in deep RL. We have updated the manuscript to clarify this, towards the end of Sec. 3 (blue text).

Finally, as we are only looking at single task RL problems, any good benchmark for single task deep RL is a good benchmark for our work. In CL terminology, measuring plasticity amounts to measuring performance on the task, which in deep RL is usually done by periodically evaluating the policy return as we do in our experimental evaluation. In addition, we also measure stability by looking at the intra-seed performance variation with time. We have clarified this at the beginning of the Experiments section (blue text).

We hope these explanations and changes in the text resolve the confusion on the nature of our work and we thank you for your feedback.

A2. Training and inference speed. Following up from one of our previous responses, we have now updated the manuscript to include the training time and inference speed of StaQ, as a function of memory size $M$ and state space dimension, also comparing it to the baselines. This is mentioned in Table 1 (page 8) in the main text and detailed in full in App. C (page 32), in red text. As expected, the training and inference times of StaQ do not have a significant dependence on $M$ or state space dimension, as the SNN computes all of the past Q-functions in parallel.

Thank you for your response.

I now fully understand the misunderstanding I had earlier. In continual reinforcement learning, some approaches address catastrophic forgetting by employing multiple networks. Initially, I was unclear why the authors, despite referencing the main challenge of continual learning (CL) as their motivation, did not focus on addressing task transitions. After the explanation, now I convince that the authors have skillfully leveraged the concept of CL to develop a well-grounded theoretical framework under a clear motivation for single-task settings. They have formulated their approach in a manner that demonstrates significant improvements in experimental performance. Thus, I increase my evaluation score.

I would kindly suggest considering a slight revision of the manuscript to address potential misunderstandings, similar to the one I initially had, to ensure clarity for future readers.

Dear Reviewer,

Thank you for your positive response. Following your suggestion we have incorporated, in the final revision of the paper, our last discussion into Appendix E. We have also more clearly stated that we are addressing the single-task case, see line 215 in blue of the main paper. In addition, we have added how we understand stability-plasticity dilemma in the single-task case, see lines 404-406 in blue of the latest version.

Dear Reviewer 8HXA,

We thank you for your comprehensive review and interesting questions. We answer them in detail below.

Q1. Practical effects of approximation error in Q-function.

A1. In previous theoretical studies of approximate PMD, it was shown that in the presence of approximation error in the Q-function, linear convergence of PMD is maintained up to reaching an error floor that depends on the Q approximation error. While these results do not take into consideration the deletion of past Q-functions introduced in StaQ, it is important to note that up to the first deletion, StaQ is an exact PMD algorithm as far as policy update goes. In our experiments, this means that for $M=300$, and with 5000 steps per iteration, for the first 1.5 million steps, there is no deletion and StaQ is using an exact PMD policy update. In Fig. 6, we can see that peak performance is reached at 1.5 million steps for some tasks but not others; however, as it can be seen in our experiments, deleting Q-functions has no noticeable effect on learning in all considered cases, and does not introduce any perceptible changes in the learning dynamics compared to the first 1.5 million ''exact steps''. Thus, we believe it is fair to say that StaQ behaves almost exactly like a true PMD policy update, and inherits its robustness to noise in the Q-function..

Q2. Motivation and impact of mean vs min averaging of Q targets.

A2. In the literature both approaches exist: in a discrete-action setting, use of the minimum of the target Q-functions was introduced in Maxmin Q-Learning (Lan et al. 2020), and is also common in actor-critic algorithms such as TD3 (Fujimoto et al.) and SAC (Haarnoja et al.). On the other hand, taking the mean of the target Q-functions is the more traditional interpretation of an ensemble, and was used for example in the paper Peer et al. 2021 suggested by Reviewer oaMK. In our paper we treat this choice as a hyperparameter and chose the overall best for each class of environment (Classic Control, MuJoCo, MinAtar). As discussed in App. B4 (under the heading "Policy evaluation and exploration"), we find that the minumum generally results in more stable training, but struggles with weak reward signals due to its tendency to underestimate. Our observations here are in line with the literature on the impact of over/underestimation bias of the Q-function, see e.g. Sec. 3 of (Lan et al. 2020).

Q3. Scaling of StaQ with M and state-action space.

A3. We will shortly add a table showing the runtime of StaQ for different choices of M and different settings of the state-action space. We will complete our answer then.

Q4. Can Continual Learning (CL) techniques be used in the Q-function of StaQ.

A4. Yes, we impose no restriction on policy evaluation, and virtually any approach that would improve the accuracy or stability of the Q-function can be used in StaQ, including a better management of the replay buffer, as discussed in the future work section. Regularization techniques have also been tried in the past, for instance in the OpenAI implementation of TRPO/PPO, it was proposed to use a trust region on the value function (See Eq. (29) of Schulman et al. 16), and this could also be used in our setting. True to the motivation of our paper, we think however that parameter isolation methods remain poorly studied in RL, and are a potent alternative as they improve stability without compromising plasticity, and the current compute power can largely support their cost. Along these lines, a potentially interesting CL idea (that of splitting the learning between a fast and slow component) is discussed in the future work section.

Q5. SNNs for CNN and LSTM layers.

A5. Recurrent networks such as LSTMs or GRUs are based on matrix multiplication operations that are similar to MLPs. It should be rather trivial, at least conceptually, to support these operations in a stacked neural architecture by stacking the matrices of several recurrent networks and performing these matrix operations in batch, as with the provided code. However, implementations of recurrent architectures for processing a sequence of inputs are usually coded in a lower level language (in C for instance). Contrary to MLPs, we would need to alter automatic differentiation libraries at a lower level to properly support stacking of recurrent models. But this is an engineering problem, not a conceptual one. For CNNs, we believe the groups option in the Conv2d class of PyTorch can be used to implement stacked networks, although we have not tested it yet.

Dear Reviewer, following up on Q3., we have now updated the manuscript to include the training time and inference speed of StaQ, as a function of memory size $M$ and state space dimension, also comparing it to the baselines. Please see this mentioned in Table 1 (page 8) in the main text and detailed in App. C (page 32), in red text. As expected, the training and inference times of StaQ do not have a significant dependence on $M$ or state space dimension, as the SNN computes all of the past Q-functions in parallel.

Dear Reviewer, thank you again for your feedback. We are glad to hear that you believe this would make a good paper for the community.

Following our discussion about Q1, on the impact of a Q-function approximation error on convergence, we have updated our manuscript. We have generalised the theoretical analysis to include the case where the policy update is performed using an approximation $\tilde{Q}\_\tau^k$ of the Q-function $Q\_\tau^k$, which is bounded by $||\tilde{Q}\_\tau^k - Q\_\tau||\_\infty \le \epsilon\_{eval}$. This new theoretical analysis complements our first answer to Q1, that similarly to previous theoretical studies of approximate PMD, the linear convergence of StaQ is maintained until it reaches an error floor that depends on the Q approximation error $\epsilon_{eval}$.

In practice, and to complement our previous answer to Q1, we can see on the Classic Control tasks and Hopper, where perhaps $\epsilon_{eval}$ is very low, that the final variance in policy return between runs is extremely small and all seeds seem to converge to similarly performing policies. However, as the task dimensionality grows, the error floor due to $\epsilon_{eval}$ increases and the policies do not concentrate as much on similarly performing policies.

Regarding the new proofs, since our contributions are focused on the policy update, we have left the statements in the main paper unchanged, analyzing only the error introduced by the deletion mechanism in the policy. But the proofs in App. A now treat the more general case of a presence of both an error in policy update and policy evaluation, as formalized by the new text in brown color at the start of the first theorem's proof. The two error types do not interact, and the policy evaluation error only adds an independent error floor as previously analyzed in the approximate PMD setting (Zhan et al. 21). The results are thus not surprising but for the sake of completeness, we think they can still be interesting. Note that the old proofs can be recovered by setting the policy evaluation error $\epsilon_{eval} = 0$ and by replacing the approximate Q-function $\tilde{Q}\_{\tau}$ by the true Q-function $Q\_{\tau}$.

Dear Reviewer U8vT,

Thank you for your valuable feedback. We address each comment in detail, one by one below.

Q1. No SAC or EWC baselines

A1. We would like first of all to remind the reviewer that StaQ is only compatible with discrete action spaces and hence we only use discrete-action deep RL baselines. We consider in the paper four baselines: TRPO, PPO, DQN and Munchausen DQN (M-DQN).

SAC. Soft Actor Critic (SAC) is not compatible with discrete action spaces, but M-DQN can be seen as an adaptation of SAC to discrete action spaces with an additional KL-divergence regularizer. Please see the discussion in the M-DQN paper (https://proceedings.neurips.cc/paper/2020/file/2c6a0bae0f071cbbf0bb3d5b11d90a82-Paper.pdf) on page 3, between Eq. (1) and (2). The M-DQN paper also discusses Soft-DQN in Eq. (1), which they call the "most straightforward discrete-actions version of Soft Actor-Critic (SAC)", and which can be obtained from M-DQN by simply setting the KL-divergence regularization weight to zero. However, we did not consider Soft-DQN as a baseline because the M-DQN paper shows that M-DQN generally outperforms Soft-DQN.

We also note that by setting $M=1$ in StaQ, we remove the KL-divergence regularization and only keep the entropy bonus. This baseline can also be seen as an adaptation of SAC to discrete action spaces: indeed, if we set $M=1$ in Eq. (14) we recover the policy logits $\xi_{k+1} = \frac{\alpha}{1-\beta^M}\sum_{i=0}^{M-1}\beta^i Q_{\tau}^{k-i} = \frac{\alpha}{1-\beta}Q_{\tau}^{k} = \frac{Q_{\tau}^{k}}{\tau}$ (because $\alpha \tau = 1-\beta$), such that $\pi_{k+1} \propto \exp\left(Q_{\tau}^k / \tau\right)$. While for SAC, the actor network is obtained by minimizing this problem (Eq. 4 in https://arxiv.org/pdf/1812.05905) $\pi_{k+1} = \arg\min \text{KL}\left(\pi \Big| \frac{\exp\left(Q_{\tau}^k/\tau\right)}{Z_{\text{norm.}}}\right)$, but in the discrete action setting, we can sample directly from $\exp\left(Q_{\tau}^k/\tau\right)$ --- which is the minimizer of the above KL-divergence term --- and we do not need an explicit actor network. As such StaQ with $M=1$ could be seen as an adaptation of SAC to discrete action spaces. Please note that we have already included $M=1$ in the ablation study for some environments.

In summary, because M-DQN outperforms Soft-DQN and because StaQ with $M=1$ resembles SAC (as it uses only soft Q-functions and no KL-divergence regularization), we do not believe that Soft-DQN would be useful as an additional baseline, however we would be open to feedback on this.

EWC. Elastic Weight Consolidation (EWC) is a continual learning approach for supervised learning problems, and is not designed to tackle instabilities specific to deep RL. However, as discussed in the paper (line 73), TRPO uses a similar natural gradient approach to online EWC (https://arxiv.org/pdf/1801.10112) and can be seen as online EWC applied to RL. TRPO (and thus a form of EWC) is used as a baseline and behaves rather well in terms of stability: on the stability plots in the Appendix (Fig. 7 and 8), TRPO is usually the second most stable algorithm after StaQ.

Q2. Clarity of Section 3

A2. We would appreciate if you could point out to specific equations in Sec. 3 that you found hard to read. We would be happy to improve the writing.

Q3. Synergy between additional exploration strategies and StaQ

A3. Addressing the exploration/exploitation dilemma is the key challenge of tabular RL. In the deep RL setting, there is the additional challenge of instabilities during training caused by the use of neural networks. Our paper focuses only on the latter challenge. However, we believe that the benefits of novel exploration strategies for deep RL would be more apparent if the lack of exploration is the only cause of under-performance, otherwise good exploration might be lost in the "noise" of performance oscillation and collapse, if instabilities remain in deep RL. We believe that exploration in the deep setting will be easier to approach if the research community could get rid of the instabilities of deep RL -- and we believe that this paper brings novel insights towards this goal.

Reviewer b4CY also expressed some concerns regarding the choice of the environments for our experiments. The main arguments of the reviewer were that environments except MuJoCo ones are either low-dimensional, like the Classic Control environments, or are not a common choice of benchmarks for Deep RL such as Minatar, especially considering that Atari is a more popular choice. Another reason mentioned by the reviewer is that, on some of those environments, StaQ has lower performance and is outperformed by DQN or M-DQN (unlike on MuJoCo tasks). In their last message, Reviewer b4CY also cast some doubt on the choice of our baselines and on them being state-of-the-art.

We disagree with Reviewer b4CY and our arguments to support our decision in the choice of baselines or benchmarks are provided in our last set of replies to Reviewer b4CY.