Adaptive $Q$-Network: On-the-fly Target Selection for Deep Reinforcement Learning

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

Weakness 1: [...] it lacks a theoretical analysis on why the selection scheme from Eq (2) leads to convergence rather than local minima. A formal theoretical analysis would strengthen the paper by explaining the convergence properties of the proposed method.

We thank the Reviewer for their suggestion. In Appendix A.1 of the updated submission, we now prove that AdaQN is guaranteed to converge to the optimal action-value function in the tabular setting with probability $1$.

Sketch of the proof: we demonstrate AdaQN's convergence by adapting the proof of convergence of the Generalized Q-learning framework presented in [1]. For that, we first explain which modifications to the Generalized Q-learning framework are needed to englobe AdaQN. Then, we prove that the assumptions required for convergence still hold with the presented modification.

[1] Q. Lan, et al. Maxmin q-learning: Controlling the estimation bias of q-learning. ICLR, 2020.

Question 1: Given the motivation to "speed up hyperparameters selection," how can the selected hyperparameters by AdaQN be used effectively?

We stress that the purpose of AdaQN is not to pre-select some hyperparameters that could be used to train a well-performing agent from scratch. In this work, we argue and demonstrate that training a method with fixed hyperparameters is suboptimal compared to selecting (and changing) them dynamically, thus better coping with the high non-stationarity of the RL training process.

If more environment interactions are available, we recommend continuing the training with AdaQN. Especially when the search space is infinite (Section $5.4$), AdaQN will continue to explore the space of hyperparameters while focusing on the hyperparameters that fit the target well. Thanks to the offline selection mechanism, no environment iteration will be wasted on exploration. Additionally, the population size can be reduced if the computation power is a limiting factor.

Question 2: Can the selected hyperparameters by AdaQN be used to train a better DQN? It seems the improvements by AdaQN are due to the use of different Q-functions, similar to ensemble methods, with the difference being the use of various hyperparameters instead of just different initializations. Could the paper be motivated by performance improvement using different hyperparameters rather than speeding up hyperparameter selection?

As mentioned in the answer to Question $1$, we point out that the main goal of this work is not to speed up hyperparameter selection. The main objective is to improve performances and remove the need for expert knowledge on hyperparameters. Our approach selects the hyperparameters dynamically during training to cope with the non-stationarity of the RL process, as we demonstrate that keeping fixed hyperparameters is suboptimal. As pointed out by the Reviewer and mentioned in the last paragraph before Section 4.1, "By cleverly selecting the next target network from a set of diverse online networks, AdaQN has a higher chance of overcoming the typical challenges of optimization".

The results of Figure $6$ is an example where AdaQN is used to train a better DQN. Indeed, AdaDQN consistently outperforms the orange curve which corresponds to the hyperparameters of vanilla DQN. In those $3$ configurations, adding diversity allows AdaDQN to outperform vanilla DQN.

We thank the Reviewer for the thorough comments and questions.

Weakness 1/Question 1: Evaluation protocol

It would be good to know what the performance would be when running from scratch with the best performing hyperparameters. I would suggest explaining this with equation notation to make it precise. Moreover, perhaps it would be useful to explain the hyperparameter tuning task setting, what the objective and metrics are in the background.  

Thank you for pointing this out. We incorporated the following in Appendix $B.1$ in the updated submission. We now detail the evaluation protocol for the considered methods. The reported performance of the individual runs of DQN and SAC as well as AdaDQN, AdaDQN with $\epsilon_b = 0$, RandDQN, AdaDQN-max, AdaSAC, RandSAC, and Meta-Gradient DQN are the raw performance obtained during training aggregated over seeds and environments. The reported performances of the other methods require some post-processing steps to account for the way they operate:

• Random search: we report the empirical average over all the possible individual runs of the hyperparameter search space in Figure $4$. This is possible because the search space is finite. In Figure $7$ (left), we had to adapt this protocol as the search space is infinite. This is why we computed the best performance observed before a given timestep as the current performance before computing the IQM over the seeds.
• DEHB: the same protocol as a random search was used. The average return over the last epoch is given to the hyperparameter optimizer as a metric to be maximized.
• Grid search: we first compute the IQM performance of each individual run aggregated over seeds and tasks. Then, we compute the IQM of the best individual run and scale the resulting IQM horizontally to the right by the number of individual runs to account for the environment steps taken by all individual runs. If we note $p_k(t)$ the IQM obtained by a hyperparameter $k$ after $t$ environment steps. The IQM of grid search is reported as $p_{\text{grid search}}(t \times N) = \max_{k \in \{1, .., K\}} p_k(t)$ where $K$ is the number of individual runs used in the grid search.
• SEARL: we recall that SEARL has the specificity of periodically evaluating every $Q$-network of its population. Each time every $Q$-network is evaluated, we use the best return to compute the IQM of SEARL-max and the worst return to compute the IQM of SEARL-min.

Details on the hyperparameter spaces and the other hyperparameters are available in Tables 1, 2, 3, and 4 of Appendix $B.1$.

Moreover, the axis labels such as "Env steps" can be confusing, because the same notation is used in standard RL where one just runs the best performing hyperparameters without considering cost of searching the hyperparameters.

We agree that some works do not share the number of environment steps used for tuning the method's hyperparameters. We argue that this is a bad practice as it does not reflect the dependency of the proposed algorithm w.r.t its hyperparameters. It can also lead to wrong conclusions when less effort has been spent on tuning the baseline's hyperparameters. Therefore, we include all the environment steps used for achieving the reported performances, as advocated by [1].

[1] J. K.H. Franke, G. Koehler, A. Biedenkapp, and F. Hutter. Sample-efficient automated deep reinforcement learning. ICLR, 2021. 

Weakness 2/Question3: Selecting from different discount factor

Around the end of the paper, there was a part about also selecting the discount parameter, but this seemed unsound to me. The discount parameter affects the Q-function, so different Q-functions would necessarily require different targets, and I don’t think they could be shared. For example setting $\gamma = 0$ would probably give good small prediction errors, but would not actually perform well.

Thank you for raising this point. While each $Q$-function is learned w.r.t. a different discount factor, they are all compared against the same discount factor $\gamma = 0.99$. This prevents situations where a smaller discount factor would be favored as suggested by the Reviewer. This mechanism is close to the way Meta-Gradient DQN works. Indeed, Meta-Gradient DQN uses a cross-validated discount factor for computing the meta-objective. As indicated in the last paragraph of Section $5.4$, we choose the same value for the cross-validated discount factor and the shared discount factor so that the algorithms can be compared fairly.

We thank the Reviewer for the time spent on our rebuttal. We are glad to see that our rebuttal addressed their questions.

Regarding the evaluation protocols, I think it could still be explained more clearly with equation notation, writing out precisely what was done.

We thank the Reviewer for their suggestion. We now further refined Appendix $A.1$ in the updated submission, where the equation used for computing the reported IQMs of each method is written down.

I also still think that the "Env steps" notation can be confusing, so I would suggest thinking about whether it could be revised somehow.

We understand the Reviewer's concern. However, we would like to keep "Env steps" as a label because we believe it is an accurate description of the quantity it represents. Nonetheless, we now emphasized that "the environment steps used for tuning the hyperparameters are also accounted for when reporting the results" in Line $267$ of Section $5$ in the updated submission.

Explaining the autoRL framework with mathematical notation in the preliminaries or background would also be useful to set the stage and clarify precisely what is being aimed to do in the paper.

Thank you. We now added a sentence in the first paragraph of the introduction that clearly states the scope of the paper. We believe that this is enough to properly understand the AutoRL framework under which our approach is developed.

Thank you for your detailed comments.

a. I would have expected the protocol to compute the expected maximum of the random search after $t$ steps.

We stress that this protocol is only applied in Figure $4$ in which the search space is composed of $16$ hyperparameters. We first computed all possible individual runs (Figure $4$ (right)) and, in Figure $4$ (left), we derive:

• Grid search as the IQM of the best individual run horizontally scaled to the right by the number of individual runs to account for the environment steps taken by all individual runs. The IQM of grid search is reported as $p_{\text{grid search}}(t \times K) = \max_{k \in \{1, .., K\}} p_k(t)$.

• Random search as the empirical average over all individual runs. The IQM of random search is reported as $p_{\text{random search}}(t) = \frac{1}{K} \sum_{k \in \{1, .., K\}} p_k(t)$. This corresponds to the expected performance of what a random search would look like if only one individual trial were used. We chose to add this metric to show that AdaSAC is a better algorithm than simply picking a random hyperparameter.

This clarification is now part of Appendix $B.2$ in the updated submission.

b. This seems to however compute the average irrespective of the number of steps

We clarify that the number of steps is taken as input such that $p_{\text{random search}}(t) = \frac{1}{K} \sum_k p_k(t)$. Note that we forgot the argument $t$ for $p_{\text{random search}}$ in the previous revision; we have now added it.

c. it would never converge to the performance of the maximum hyperparameter.

As mentioned in the answer to Point a., the curve of random search is only shown for the duration of one individual run because the purpose is simply to show that AdaSAC is a better algorithm than simply picking a random hyperparameter.

Continuing the curve for random search would lead to the performance of the maximum hyperparameter. However, computing the expected performance of random search beyond the first individual run is computationally demanding as $16! \approx 2.0 \times 10^{13}$ combinations have to be taken into account. Moreover, we argue that the most relevant part of this curve is the first individual run as AdaSAC only uses this amount of environment interactions. Therefore, we decided not to compute the curve for random search after the first individual run.

Regarding the explanation of the setting, what I had in mind was to write out in equations that you are running a set of trials, where each trial has some number of steps $T$. Each trial can have either different hyperparameters or the hyperparameters may also be tuned adaptively. You are trying to find the best performing policy compared to the total number of environment steps considered, etc... This kind of explanation would clarify what the exact setting is.

We thank the Reviewer for the suggestion. In the updated submission, we clarified the AutoRL setting in which our work stands by formulating the following optimization problem that our approach aims to solve:

$\max_{k} J(\theta_t^k) s.t. \forall k \in \{1, .., K\}, \theta_t^k \in \text{arg} \min_{\theta} f(\theta; \zeta_t^k),$

where $t$ is the current timestep, $K$ is the population size, $\theta_t^k$ is the $k^{\text{th}}$ element of the population, $J$ is the cumulative discounted return, and $f$ represents the objective function of the learning process.

Indeed, as explained in the last paragraph of Section $4$, at each timestep $t$, AdaQN aims at using the best agent of the population. Since the identity of the best agent is not known without evaluating each agent explicitly (as done for instance by SEARL), AdaQN relies on the online network corresponding to the selected target network for sampling actions as a proxy for picking the best agent.

We hope that this clarifies our setting as requested by the Reviewer.

Regarding:

We believe that by using the subscript $t$ in Equation 2, we consider the timestep meaning that the hyperparameters can evolve during the training, thus including the adaptive scenario.

I see your point, but I think it could be made clearer by including the sequence of hyperparameters into the objective. Currently, you write it in terms of optimizing at each step, but actually the objective is the best performance after the sequence of multiple hyperparameters.

Regarding your new comments about the protocol:

because the main goal of this experiment is to show how AdaSAC performs against fixed hyperparameters.

This statement doesn't seem consistent with the experiment to me. If the aim is to show performance against fixed hyperparameters, there is no need to take into account the hyperparameter search time, and you could just show the max performing hyperparameter without rescaling. The fact that you do include such rescaling indicates to me that this experiment is about the hyperparameter optimization performance. Anyhow, I appreciate that you have added the change. One remaining comment I have about this is that the performance of random search would depend on the length of the learning. It is expected that your proposed autoRL method would require more time to reach peak performance compared to just running the best hyperparameter picked by an oracle. From this, we might expect that the optimal random search trial length is shorter than the required trial length for your autoRL method. Therefore, to make the result more convincing, I think it's best if you also do a search over the trial length, and pick the trial length that maximizes the performance for random search. This would make for the most convincing results.

Regarding the results in Figure 7, I was also not convinced by your arguments. It seemed to me that you played around with the settings a bit, and picked something that seemed reasonable. But, I think it would be necessary to do a principled search for the hyperoptimizer parameters and provide evidence that they are performing well. It seems that instead of replicating existing baselines (where we could check against prior performance), you tuned everything yourself, so it is unclear to me whether your baseline algorithms are well-performing. In terms of performance of the hyperoptimizers, due to your setting where you consider the performance of the current best trained policy, it is necessary to both select the best hyperparameters, and to train these hyperparameters until completion. You mentioned that short trials for random search do not work well, but this may be because the trial length is too short to reach peak performance of the policy. If you instead use short trials to search for the hyperparameter followed by training with this hyperparameter until completion, the results may be different. For the adaptive methods like DEHB, as you're only showing the learning performance, it is not clear whether the algorithm is functioning correctly. It could be just stuck evaluating various hyperparameters for 20M frames without checking the performance on any hyperparameter for 40M frame thus limiting the achieved performance. I requested also adding the performance of the best hyperparameter when training directly with this hyperparameter from scratch, yet this is not included (your method is not expected to outperform this, and it's not a problem if it does not, but it would be good to know how it compares for reference, because this result would provide an upperbound on the performance of non-adaptive hyperparameter optimization).

Moreover, there are other metrics by which to check hyperoptimization performance, e.g., instead of looking at the performance of the current best policy, one could look at the performance of the policy after training to completion with the currently selected best hyperparameters. I understand that your setting is not the same, but the comparison algorithms are not necessarily designed for your setting, so I think it may be better to take into account the possibility of stopping hyperoptimization half-way through and training until the end with the chosen hyperparameter.

While I am not completely convinced by the experimental work, I have decided to keep my score, and I encourage the authors to further revise the analysis.

7. I requested also adding the performance of the best hyperparameter when training directly with this hyperparameter from scratch [...].

We believe that the concept of "best hyperparameter" is ill-defined in our work, because the best hyperparameters are different for each seed and each training step, due to the non-stationarity of the RL optimization procedure. Because of this, our experiments are designed to compare AutoRL methods, not fixed hyperparameters. Even when fixed hyperparameters are considered for random search and DEHB, the chosen hyperparameters vary from one seed to another. Nonetheless, the best performance obtained across the trials is observable as the final performance of random search and DEHB. This comes from the fact that we apply the maximum operator across each trial as explained in Appendix $B.2$.

8. I understand that your setting is not the same, but the comparison algorithms are not necessarily designed for your setting, so I think it may be better to take into account the possibility of stopping hyperoptimization half-way through and training until the end with the chosen hyperparameter.

We believe that SEARL suits the setting of our work well as it aims at maximizing the return by selecting well-performing hyperparameters. Moreover, we point out that performing early stopping is not straightforward as it requires many subjective choices (the number of trials before stopping, the trial length, and the selected hyperparameter for the long training) which would require large amount of computational resources to tune empirically, which goes against the aim of this work of finding effective hyperparameters while optimizing the usage of samples. This is why, we chose standard AutoRL baselines that require less tuning while offering competitive performances [1].

[1] Theresa E. et. al. Hyperparameters in reinforcement learning and how to tune them. ICML, 2023.

We thank the Reviewer for the insightful feedback and questions.

Weakness 1: From my understanding, AdaQN's performance is still dependent on the initial range of hyper-parameters considered in the multiple Q setup. If this range is not representative of the optimal settings, AdaQN may not achieve the best possible performance.

We agree that the range of available hyperparameters influences the performances. In the case that little domain knowledge on the hyperparameters is available, it is a safe choice to consider a wide range of hyperparameters. Importantly, AdaQN performs well in this case. To verify this, we evaluate AdaSAC with a wide search space in Section $5.4$. Indeed, AdaSAC could select from $18$ action functions, $24$ optimizers, $4$ losses, a wide range of learning rates, and fully parameterizable architectures (a detailed description of the search space is available in Table $4$, in Appendix $B.1$). This way, we ensure that poorly performing hyperparameters are also included in the search space. In Figure $7$ left, we conclude that AdaDQN is able to learn effectively even in wide search space, reaching higher performances than the baselines.

Weakness 2: Also, it seems error or bias in the calculation of approximation error will affect the selection of the shared target.

We point out that we do not aim at estimating the approximation error directly. Instead, we use the minimum of the considered cumulated losses as an estimation of the hyperparameter minimizing the considered approximation errors. Importantly, we show in Theorem $4.1$ that this selection mechanism is accurate under the condition that the dataset is rich enough to represent the Bellman operator in expectation. To verify that this selection mechanism is effective in practice, we evaluate other variants of the proposed approach. AdaDQN-max is a variant of AdaDQN where the maximum of the cumulated loss is chosen instead of the minimum. RandDQN and RandSAC are variants of AdaDQN and RandSAC where the next target is chosen randomly from the set of online networks. The results presented in Figure $2$ (right) and Figure $4$ (right) support the idea that the proposed selection mechanism is effective, as AdaDQN and AdaSAC consistently outperform the proposed variants.

Question 1: Can AdaQN effectively be applied on continuous action spaces (actor-critic frameworks) especially in complex high-dim environments?

Yes, we present an adaptive version of SAC (AdaSAC) in Algorithm $2$, in Appendix $B$. AdaSAC outperforms random search and grid search on $6$ MuJoCo environments. The individual performances of AdaSAC and the baselines are presented in Figure $5$. We argue that those environments can be considered complex and high-dimensional, especially Humanoid and HumanoidStandup, where the state space is composed of $348$ dimensions and the action space is composed of $17$ dimensions.

Question 2: Which Q should be use to derive a policy network (maybe similar as we choose the one for target calculation)?

Ideally, one should choose the most accurate $Q$-network. Unfortunately, this information is not available but more importantly, learning the policy from the same $Q$-network could lead the other $Q$-networks to learn passively. This would make the accuracy of the other $Q$-networks drop as identified in [1] making them useless for the rest of the training. As suggested by the Reviewer, we take the $Q$-network corresponding to the selected target network (as a proxy for the best-performing network). To avoid passive learning, we randomly select another $Q$-network with low probability as commonly done with $\epsilon$-greedy policies. This information is explained in more detail in the last paragraph of Section $4.1$.

[1] G. Ostrovski, et al. The difficulty of passive learning in deep reinforcement learning. NeurIPS, 2021.