Thank you for your careful review, and for recognizing our contribution to mixed-space Bayesian optimization.

what exactly motivated the authors to consider that using trees would be good for BO

We agree with the reviewer that we should better motivate BARK to ensure practitioners use BARK appropriately. Our revised paper will include the requested figures and the following discussion.

Our greatest motivation for using trees is for modeling - and specifically optimizing over - mixed feature spaces. Purely continuous spaces are well-modeled by standard Euclidean GP kernels. Purely categorical spaces can be addressed with multi-armed bandit approaches. However, many real-world problems have mixed domains. Trees have strong modeling performance in mixed spaces. Moreover, we can define a MIP to optimize the AF exactly and we can formulate this MIP so that it is effectively solved with off-the-shelf software. The resulting BO procedure does not require approximations during the optimization step.

Modeling with trees offers several additional benefits. First, we are able to model non-stationary functions, where the lengthscale changes throughout the domain. We demonstrate this behavior in Rebuttal Figure 1. This is especially desirable in high dimensions, where a locally short lengthscale will not harm BARK's global uncertainty quantification.

Second, we assume prior correlation between values in categorical features due to the nature of splitting rules in trees. The indicator kernel typically used for categorical features with GPs (Ru et al., 2020) assumes that each value is independent. BARK is able to capture correlations between values, as demonstrated in Rebuttal Figure 3. Trees therefore have a more expressive prior on functions over categorical values.

Some black-box functions are indeed better modeled by trees, as demonstrated in the MAX benchmark where a grid-based AF optimization is used for all methods. However, other benchmarks are better modeled with the assumptions of smoothness provided by Euclidean GP kernels.

Table 1... doesn't compare against other standard regression baselines

Section 7.1 aims to show that BART and BARK have similar modeling abilities, and that our kernel perspective on BART still leads to strong regression performance. Since our only point is that BART and BARK are similar with respect to regression, we did not compare to a wide array of regression models. However, we agree that including RBF-GP would provide more context and the revised paper will include an extended version of the table: Rebuttal Table 2. Additionally, as noted in our reply to Reviewer zyg8, we will signpost the purpose of Table 1 more clearly.

I suspect that the tree-based kernel does indeed perform well on mixed search spaces, but the authors need to make this motivation more explicit. This can be boosted better with... benchmarking on continuous-only functions

Thanks for helping us make our motivation more explicit. Indeed, we do not expect BARK to outperform an RBF kernel in continuous-only BO. As explained by the reviewer, these continuous-only BO problems may be smooth, and therefore have a higher prior probability under an RBF kernel. The reviewer is correct that our original submission focuses on mixed spaces where we expect BARK to be more suitable. We also agree that adding continuous-only benchmarks offers a more complete view. We will provide two continuous-only benchmarks in the revised paper: Hartmann (6D) and Styblinski-Tang (10D), which we show in Rebuttal Figure 4. Despite BARK's non-smooth assumption, we still observe reasonable performance from BARK in this setting.

how this new BARK-GP regresses on a 1D categorical / discrete function

To motivate using trees, our revised paper will include an example of regression on both a 1D discrete function and a 1D categorical function: Rebuttal Figure 2 and Rebuttal Figure 3. We will explain in the revised paper that BARK may not necessarily provide better regression for discrete, ordinal features (which are simply continuous features sampled on a grid) compared to Euclidean GPs, but that BARK provides a method of optimizing over such features without approximations.

We kindly thank the reviewer for their thoughtful review, and for recognizing the potential of our method.

lack of discussion of wall-time for BO

As mentioned in Appendix G.1, we limit each MIP optimization to 100 seconds. However, we agree that a more complete comparison is highly relevant. Please see requested results in Rebuttal Figure 5 for a selection of 3 benchmarks. We will also include this figure and the following discussion in the main paper:

BARK is slower than competing methods, taking ~50s to fit the model, and 100s to optimize. This is due to the combination of the expensive MCMC procedure, and the large optimization formulation. This is comparable to the fitting time for BART, and the time taken to evaluate BART on a grid of 2^14 points. BARK is best applied in BO settings where the objective is expensive to evaluate (e.g. taking at least several minutes, or having a large associated financial cost). Note that the PestControl and MAX (material design) benchmarks reflect examples of such black-box functions. For settings where experiments are cheap and/or function evaluations are quick, we recommend alternate methods.

Fig. 5 shows error bars but doesn't say what they are.

Thanks for noting our omission: the revised paper will state explicitly in the figure caption that the bars are the 25th and 75th percentile of regret achieved across the 20 runs.

this software will depend on Gurobi, which is very expensive for many people

Gurobi does provide a free academic license, but we recognize that requiring a licensed software will limit the reach of this work. Gurobi is a very strong optimizer for MIP problems, and open source solvers would take longer to maximize the AF. However, we would still be interested in providing such an interface, especially if there is community interest.

We thank the reviewer for their thorough review, and for identifying the strengths of our work.

The choice of UCI datasets

Section 7.1 demonstrates that the BARK model performs similarly in regression to the BART model. BART is typically used in regression settings with tabular datasets, so the purpose using these UCI benchmarks is to be fair to BART. This section demonstrates that the improved performance of BARK in BO is due to the acquisition function optimization, and not any superior modeling capability.

Agreed with the reviewer that we should state the purpose of Section 7.1 more clearly: the revised paper will clearly signpost our objective of comparing regression tasks where BART is already known to be strong.

the convexity of the expected acquisition function

Thebelt et al. (NeurIPS, 2022) show the convexity of the nonlinear part of the acquisition function: see their development in their Section 4. The acquisition function (AF) itself is not convex in the input space, but only with respect to the mean and variance, which leads to improved performance with mixed-integer solvers.

for the comparison to BART I am wondering though whether the comparison does not have to be refined... the key claim of an improved efficiency seems to require some quantification

Many BART samples are required to compute the predictive variance, e.g. experiments in Chipman et al. (2010) use at least 1000 function samples. We agree with the reviewer that, in regression, this lower sample efficiency may not be a disadvantage. However, the high number of samples means that it is infeasible to formulate an optimization problem over the BART AF, as the number of variables and constraints required to encode these tens of thousands of trees would be too great. The large number of samples therefore necessitates a grid-based approach to optimizing the AF. Our revised paper will clarify the relevance of the 'sample efficiency' claim in Section 5.2.

Furthermore, the required density of the grid on which BART is evaluated increases exponentially with the problem dimension, and so it is not feasible to allow for a sufficiently dense grid in high dimensional problems. The grid sized used in our experiments was chosen to match the wall clock time of the BARK optimization (see Rebuttal Figure 5, where evaluating BART at 2^14 gridpoints takes the same wall-clock time as the BARK optimization).

Could it be useful to have a hierarchical presentation of a general form of the model used in this and prior works

Thank you for the suggestion - we will add to the paper a summary of the existing literature (see Rebuttal Table 3), that highlights key similarities and differences between the various BO methods covered in the literature review.

no room to discuss [the MIP approach] in the main paper

Thebelt et al. (NeurIPS, 2022) develop a detailed discussion of the MIP. We have extended the optimization model, and will clarify these improvements in Appendix G. The contributions we will clarify in the revised version include: extending the MIP to include multiple tree-structure samples and linking the kernel samples in the (approximate) integrated AF.

see more compactly the various parameters

Thanks for the nice idea, which helps us improve clarity. We will add this summary of the BARK parameters (see Rebuttal Table 1) to the paper.