Meta-Black-Box-Optimization through Offline Q-function Learning

We appreciate the reviewer for your valuable comments. We provide reponses as below to address your concerns.

[Advantages of Q-Mamba] We would like to first clarify that the core motivation of Q-Mamba is providing an offline learning paradigm for MetaBBO domain, with at least comparable performance with online MetaBBO approaches and significantly reduced training cost. From Table 1 (in-distribution test) and Figure 2 (OOD test), we have validated such aspects. We would like to also argue that by using Mamba architecture to facilitate efficient parallel scan during the training, Q-Mamba actually improve the efficiency of Q-transformer by approximate 20% (13h vs 16h).

[Train-test split] We would like to first explain that the train-test split in experiments follows up-to-date MetaBBO methods, where the motivation of such split is to make the meta-level policy learn comprehensively across as many complex problem landscape as possible, hence ensuring a good generalization performance. Meanwhile, we agree with the reviewer that a more uniform train-test split can further demonstrate the learning effectiveness of Q-Mamba. Following this suggestion, we have tried a uniform train-test split (move f16, f17 and f21 from train set to test set, move f6, f8 and f9 from test set to train set) to compare Q-Mamba and other baselines. Due to the space limitation, we provide the results in https://anonymous.4open.science/r/QMamba_review-C0CF/train_test_split.md (due to the narrow rebuttal window, we only provide results on $Alg0$). The results there consistently validate the superior perforamence of Q-Mamba.

[Ablation on BBO algorithm without Q-Mamba pre-train] We agree with the reviewer that the learning effectiveness could be further validated by such ablation. Following the suggestion, we have used the same 19 random seeds and $Alg0 \sim Alg2$ to optimize the 8 tested problems. We provide the comparison results in https://anonymous.4open.science/r/QMamba_review-C0CF/Without_pre-train_ablation.md. The results above clearly demonstrate the learning effectiveness of Q-Mamba, which could boost the optimization performance of the backend BBO optimizer.

[Essential References] For reference [1][2] the reviewer suggests, we would like to explain that the reason why we only list them as related works rather than compare them as basleines is that Q-Mamba aims at DAC tasks in BBO, while [1][2] explore representing BBO optimizer by NN. We hence chose RLPSO, GLEET and LDE, which are tailored for DAC tasks as baselines to construct the offline data and compare.

[Self-adaption of Q-Mamba] We would like to clarify that Q-Mamba inherits the adaption ability of MetaBBO methods. Specifically, as we illustrated in page 5, Figure 1, in each decision step of Q-Mamba, we let the model knows the current optimization status $s^t$, which informs it the optimziation problem and landascape information so that Q-Mamba could adaptovely adjust the hyper-parameters. We hope this could address your concern.

[Results on f16, f21 and f22] Since the f16, f21 and f22 are now located at the training dataset in the paper, we have not tested them in in-distribution test in Section 5.2, Table 1. However, we could provide the testing results of the trained Q-Mamba on these training functions, which you can access at https://anonymous.4open.science/r/QMamba_review-C0CF/Performance_f16_f21_f22.md. The results there show that Q-Mamba could significantly boost $Alg0 \sim Alg2$ on these three problem isntances with complex properties.

[The low-level BBO algorithm optimizes for only one generation on the problem per DAC process…] This is a very interesting question and we admit that, currently, once Q-Mamba decides a configuration for the low-level optimizer, this configuration is only used for that generation. Q-Mamba need to decide again for the next generation. However, we would like to clarify that this “one config one step” paradigm align with traditional adaptive EAs where in each generation the hyper-parameters are adjusted. We denote this issue as an interesting future work.

We appreciate the reviewer for such comprehensive review and insightful comments. We provide following point-to-point responses to address the concerns in “Experimental Designs Or Analyses”, “Other Strengths And Weaknesses”, “Other Comments Or Suggestions” and “Questions For Authors”.

[Train-test split] We agree with the reviewer that a more uniform train-test split can further demonstrate the learning effectiveness of Q-Mamba. Following this suggestion, we have tried a uniform train-test split to compare Q-Mamba and other baselines. Due to the space limitation, we provide the results in https://anonymous.4open.science/r/QMamba_review-C0CF/train_test_split.md. The results there consistently validate the superior perforamence of Q-Mamba.

[Comparing Q-Mamba with the pre-trained MetaBBO method] We would like to remind the reviewer that the online baselines we compared in Table 1 are exactly the ones we used to construct our E&E dataset.

[Problem dimension in OOD testing] We used two-layer MLP structure (#state_dim, #hidden_dim=64, #action_dim) as the optimizees in these neuroevolution tasks. Since the #state_dim and #action_dim vary across the four Gym enviroments we used, the problem dimension for “InvertedDoublePendulum-v4” is 833, for “HalfCheetah-v4” is 1542, for “Pusher-v4” is 1991 and for “Ant-v4” is 2312. We would add these details into the paper if it was accepted.

[Impact of E&E dataset size] Following the suggestion, we have randomly extracted 1K, 3K, 5K trajectories from our previously constructed E&E dataset (10K) to train and test Q-Mamba on $Alg0 \sim Alg2$ respectively. We report the same performance metric as Table 1 of these Q-Mamba variants in https://anonymous.4open.science/r/QMamba_review-C0CF/Dataset_size_impact.md. We observe that, generally, if the dataset includes very narrow experiences data, the performance of Q-Mamba might suffers. A large scale pre-training could ensure the overall learning effectiveness.

[Training difficulty/cost introduced by the Q-decomposition] We would like to explain for the reviewer that the training difficulty is significantly reduced by the Q-decomposition. As we elaborated in Section 4.4, line 237-253, applying policy learning on the massive associated configuration space of EAs is challenging, while decomposing this space makes simple q-learning possible, which is usually effective than policy gradient method. The training cost of Q-Mamba is further reduced by our proposed offline learning paradigm.

[Reason of faster inference] We note that as we have decribed in Section 4.4, right col, line 248-265, we only used a single default mamba block, with input_dim as 14 (#state_dim=9 + #action_token_dim=5) and output_dim as 16 (the chosen discretization granularity in our paper). With this setting, the total learnable parameters are 5124. For online baselines, the MLP in RLPSO holds 6496 learnable parameters and the LSTM in LDE holds 6560 learnable parameters. This indicates Q-Mamba remains the same complexity. The faster inference comes from the hardware-aware design in Mamba, where it arranges the expanded states and its parameters in GPU SRAM rather than GPU HBM, such “on the fly” computation ensure an acceptable inference efficiency although the sequence is much longer.

[Numerical scale of state feature] In Q-Mamba, when we compute state feature, we first min-max normalize the population positions by the searching range of the given problem, then min-max normalize the obejctive values within that population. This facilitate the generalization across various problems.

[Ablation of online setting Mamba architecture] Following the suggestion, we have conducted two additional ablation studies:

• First, we remove the thrid case in the training objective (Eq. (5), the CQL regularization in offline setting) and train Q-Mamba in online paradigm. we provide the results in https://anonymous.4open.science/r/QMamba_review-C0CF/Online_Mamba_ablation.md, which indicate that major difference between the online and offline learning of Q-Mamba is the training efficiency. This is due to that in offline setting, we can load the entire trajectory into GPU to facilitate efficient parallel scan of Mamba, hence significantly reducing the training cost.
• Then we remove the mamba_block in Q-Mamba, leaving only the MLP q-value head, train a Q-Mamba variants with the same training setting. We provide the comparison results in https://anonymous.4open.science/r/QMamba_review-C0CF/Mamba_ablation.md. The results show that Mamba architecture contributes to the performance of Q-Mamba significantly. We would like to remind the reviewer that, in Table 1, the comparison of our Q-Mamba and Q-transformer also provide evidence that Mamba architecture is more suitable for long sequence tasks such as MetaBBO.

We appreciate the reviewer for the thorough and insightful review. We provide following point-to-point responses to address the concerns in your valuable comments.

[Performance metric] We would like to first note that such nomalized metric has been widely used in recent works, e.g., SYMBOL (https://openreview.net/forum?id=vLJcd43U7a , ICLR 24), GLHF (https://openreview.net/forum?id=fWQhXdeuSG , NeurIPS 24) and ConfigX (https://arxiv.org/abs/2412.07507 , AAAI 25). In the rollout process, for each of the 8 tested problem instances, we apply each baseline including our Q-Mamba for controlling $Alg0 \sim Alg2$ to optimize the given problem instances, across 19 independent runs. We would like to clarify that testing a baseline by different initial population is a common practice in BBO testing to measure the performance robustness. As we fix these 19 random seeds for different baselines, these baselines are tested under the same 19 initial conditions hence the fairness of our performance metric is ensured. Besides the normalization in the single step reward provides convenience for presenting average performance across different problem instances for our readers, since various problems show various objective scales. We hope the above explanation could address your concern.

[Numerical results] Following your suggestion, we have provided the numerical results of in-distribution testing in https://anonymous.4open.science/r/QMamba_review-C0CF/Numerical_results.md. We provide 3 tables ($Alg0 \sim Alg2$) for each of the 8 tested problems respectively, this is because if we do not normalize them as we did in the paper, these results can not be averaged into one table. We respectifully request the reviewr to check these results, which show that the actual performance superiorty of Q-Mamba is even more larger.

[Evidence of distribution shift] We thank the reviewer for this valuable suggestion! Indeed, we should provide more direct evidence to validate there is indeed distribution shift in offline MetaBBO. To this end, we have additionally trained Q-Mamba models under no-CQL setting. In specific, we modify the training objective in Eq. (5) of our paper by removing the q-value regularization term on OOD actions (the thrid case). We provide the performance results in https://anonymous.4open.science/r/QMamba_review-C0CF/no-CQL_ablation.md. The results provide a clear evidence that, if we remove the q-value regularization, the distribution shift could significantly downgrade the performance of Q-Mamba.

[SOTA offline RLs in OOD] Following the suggestion, we zero-shot two offline RL baselines (QDT ICML 23, QT ICML 24) to the four neuroevolution tasks we have tested and provide comprehensive comparison results in https://anonymous.4open.science/r/QMamba_review-C0CF/neuroevolution_zero_shot.md. The results there consistently reveal that offline RLs generally underperform online MetaBBO methods, which further underscores the significance of our Q-Mamba. We hope this could address your concern.

[Novelty] We would like to argue that the only similarity of our work with Q-transformer is the q-function decomposition scheme. Q-Mamba differentiate with Q-transformer in the following aspects:

1. Target tasks: we have to note that Q-Mamba represents pioneering efforts to explore the possibility of offline RL in MetaBBO tasks, which outperforms online baselines with significantly less training cost . In contrast, Q-transformer, as well as many other offline RLs are developed and examined for classic control tasks.
2. Special designs: We have explored many customized design choices in this paper to make offline-RL adaptable for MetaBBO:
   • Neural network design: we have combined strength of newly propsoed Mamba architecture into the q- decomposition scheme to boost MetaBBO long sequence tasks (the comparison of Q-transofrmer and Q-Mamba in Table 1 provides a validation).
   • Offline dataset construction: we have proposed a novel dataset construction scheme (Section 4.2) which could collect rigorous exploration and exploitation experiences from diverse baselines. Further ablation study on the data ratio $\mu$ (Section 5.2, Table 3) provide valuable insight of how to make good datasets for offline MetaBBO task.
   • Training objective redesign: compared to the training objective in original CQL and Q-transformer, we additionally add a weight $\beta$ (second case in Eq. (5)) to enhance the q-value learning in the last decomposed action dimensions since the q-value update of the other action dimentions before depends on the accuracy of the last one. The ablation study in Section 5.2 Table 2 demonstrate the effectiveness of such design.

We sincerely request the reviewer to review the above elaboration on the novelty of our work. We appreciate your efforts in reviewing our paper. Please feel free to discuss with us if any concern remains in the author-reviewer discussion period.

We appreciate reviewer #yyGg for the thorough review and valuable comments. For the concerns raised above, we provide following point-to-point responses to address them.

[Performance improvement significance] We would like to first clarify that the seemingly small relative performance improvement of Q-Mamba against the online baselines (RLPSO, LDE and GLEET) it learns from is mainly due to the normalized metrics we used for better presentation (as explained in the end of page 6, Section 5.1). Based on the above elaboration, the seemingly small relative performance improvement in Table actually represents significant absolute performance improvement. To demonstrate this, we additionally provide the absolute optimization performance comparison results in https://anonymous.4open.science/r/QMamba_review-C0CF/Numerical_results.md, where we provide 3 tables ($Alg0 \sim Alg2$), each for the tested 8 problem instances in CoCo-BBOB testsuites, showing the average best found objective value and error bar across the same 19 independent runs. We hope this could clear the reviewer’s concern. We would add these results into the appendix if the paper was accepted and remind the readers in main text to check them.

[Decomposition necessity] We provide comparison results on two additional BBO algorithm sampled from the same ConfigX (https://arxiv.org/abs/2412.07507) modular algorithm space, which hold 22 and 37 hyper-parameters respectively. The offline dataset preparation and the settings follow those in our experiments. Due to the 5000 characters limitation in rebuttal, we provide the results in https://anonymous.4open.science/r/QMamba_review-C0CF/Decomposition_necessity.md where the effectiveness of the decomposition scheme is further validated by the consistent performance superiority of Q-Mamba to both the non-decomposed online methods (RLPSO, LDE and GLEET) and offline methods. We would add these results into the paper if it was accepted and respectifully request the reviewer to check them.

[Order of action dimension] We would like to clarify Q-Mamba does not have to address the order bias since we use the pre-order traversal on a legal algorithm structure (represent the algorithm structure as a workflow tree and traversal it in a depth-first way), which can naturally reduce the permutations of the operators in a BBO algorithm to a definitive ordered permutation. On the one hand, doing so could apparently reduce the training difficulty. On the other hand, the auto-regressive learning in Q-Mamba could implicitly learns the semantic context of the algorithm structure, hence improving the potential generalization performance across various algorithm structures. We thanks the reviewers for this insightful comments and would add this elaboration in our paper to improve the clarity of the methodology.

[Relation with CQL] Let us make a quick explanation of the relation between the training objective in Eq. (5) and CQL. First, we adopt the original definition of CQL in Eq. (1) of its paper (https://arxiv.org/pdf/2006.04779). We also align our training objective with the implemented version in Eq. (2) of the q-Transformer paper (https://arxiv.org/abs/2309.10150). In our decomposition setting, the former two cases in Eq. (5) apply OOD sampling for the policy evaluation. Specifically, we sample maximum q values of the next action step $\max \limits_{j} Q_{i+1,j}^t$ for the action dimension within the same time step yet before the last one, and $\max \limits_{j} Q_{1,j}^{t+1}$ for the last one dimension. Due to the potential distribution shift, such maximum sampling possibly varies with the demonstration we have collected, hence we use the third case in Eq. (5) to regularize the OOD actions, reducing their q-values to the minimal accumulated reward that could be achieved in the optimization process, which is 0 in this case. We respectifully request the reviewer to check the above explanation and hope this could address your concern.

[Random seeds] We use three random seeds (1, 333, 9485) for the training of Q-Mamba and other baselines. We use 19 random seeds (100, 200,…,1900) for testing baselines on the CoCo-BBOB problem isntances. We use 10 random seeds (100,200,…,1000) for testing baselines on Neuroevolution problems.