Hessian-Aware Bayesian Optimization for Decision Making Systems

Dear reviewer, here are the answers to your questions.

• On the ablation study.

• • As is typical in reinforcement learning or deep learning style papers, we ablated the higher-order model extensively (Algorithm 1,2,3). We did not ablate Algorithm 4 (Bayesian optimization) as we're not familiar of this as a technique in Bayesian optimization papers.
• • This paper evolved from an earlier work where we explored other techniques for empirically optimizing the acquisition function in BO which is the significant bottleneck since the work of Kandasamy et. al. We have several unreleased results regarding research into optimizing or improving the DIRECT algorithm.
• • We did not pursue and abandoned the above research work as it was deemed no longer interesting or valuable to the AI community.
• • We are not sure how evolutionary algorithms would fare at this problem. We wanted to have an algorithm backed by theoretical regret guarantees which is what Algorithm 4 provides.
• • To determine whether the Hessian helps in BayesOpt. We compared against TreeBO which is the exact same additive structure as our work, however, our approach uses the surrogate Hessian to learn the dependency structure. This validation is presented in Fig. 4 and Fig. 9 in Appendix C.5.

• How good is this surrogate? What are the situations where this surrogate doesn't offer reliable information?

• • In our validation, we found the surrogate to be always helpful. We believe this has to do with the "constructed nature" of the benchmarks, which allows for significant learnability.

We want to give a very small addendum to our response. We finally understood the reviewer's comments about ablation of Algorithm 4. We want to point out that there are only 2 hyperparameters in Algorithm 4 (Bayesian optimization), which were completely unchanged throughout the validation and found through simple grid search.

The hyperparameters for Algorithm 4 are as follows:

• HA-GP-UCB
• • Size of the largest maximal clique: Note that in the theoretical analysis, the regret scales with the size of the largest clique. We observed that having larger maximal cliques would demonstrate slow improvement in the objective function due to an overly complex additive model. Having smaller maximal cliques would cause the objective function to asymptotically converge to a subpar value due to the limited expressiveness of the additive model.
• • Total number of additive kernels: Due to computational reasons, we limited the total number of additive kernels generated. We encountered out-of-memory and computational issues on commodity GPUs if this value was set too high.

The hyperparameters for Algorithm 1, 2, 3 are as follows:

• Higher-order model
• • Neural network sizes: Internally, our higher-order model is constructed using neural networks forming the computational components. Each neural network component consisted of 2 hidden layers, with 4 neurons per layer. We found that having overly large networks would be too large for HA-GP-UCB to optimize, and likely would be too large for memory-constrained devices.

Dear reviewer,

We are looking into making changes to the draft to aid in readability. Here are immediate answers to your questions.

• Basic problem setting

• • The basic problem setting is that of multiple agents interacting cooperatively to accomplish a common goal. This is also in a memory constrained setting (such as on IoT devices or drone delivery tasks). Within this problem setting, we propose a variant of high dimensional Bayesian optimization and show how it can optimize a compact policy space (memory constrained setting). Specifically we show in the case of malformed reward scenarios or complex multi-agent interactions, globally optimizing a small policy using our approach outperforms related work.

• Definitions of key words

• • Abstraction: We solve several problems in our work by using abstraction. Abstraction, is separating a complex system into many components which interact in a well defined manner. In our work we use abstraction to separate decision making into role assignment, and role interaction,
• • Immutable: Immutable here means something that does not change. As we are optimizing over a parameter space, the immutable part of the policy (the instructions Alg. 1,2,3) are immutable as they are not searched over or optimized.
• • Compile: Here compilation means the immutable and mutable (parameters) part of the policy are joined together to create the actual policy.

• What is the definition of the role affinity function \Lambda^\theta_r,i ? What does it indicate?

• • The role affinity function is trying to quantify the affinity for an agent to take on a specific role. It indicates the affinity for that agent to take on that specific role.

• What is h without subscript in line 4 of Algorithm 4?

• • h is a tensor (a stack of matrices) formed by collecting many Hessian matrices from line 3 in Algorithm 4.

• What is a surrogate of Hessian? How is it constructed ?

• • The surrogate Hessian is a surrogate quantity used in the paper as access to the true Hessian is either not available or too expensive to approximate. We discuss this further in Appendix H. The construction of the surrogate is as follows (found in Appendix A)
• • To estimate the Hessian, we used the Hessian-Vector product approximation. We relaxed the discrete portions of our metamodel policy into differentiable continuous approximation for this phase using the Sinkhorn-Knopp algorithm for the Role Assignment phase. For role interaction network connectivity, we used a sigmoid to create differentiable “soft” edges between each role.

• The authors claim the cumulative regret of the proposed method scale with O(log D). What assumption makes it possible? The implication behind assumption 1 is difficult to find for me. Does it assume some low dimensional essential dependency in the underlying true function?

• • The approximate high level sketch of Assumption 1 is that the dependency graph drawn from the Erdős-Rényi model is of low degree/connectivity. The base of the logarithm is related to the quantity p_g we discuss in Assumption 1. This is elaborated on in the proof of Theorem 1.

Dear reviewer,

We are looking into making changes to the draft to aid in readability. Here are immediate answers to your questions.

• Why MARL and BO?

• • In order to make Bayesian Optimization valuable and competetive theoretically and empirically with a clear use case, we focused on decision making systems for memory constrained devices.

• Why conference and not journal?

• • We believe that many excellent works in Computer Science come from conference publications. Which is why we hoped to have this work be accepted at a conference.

• H_pi can always be used as a reliable surrogate for H_v?

• • This is a good question. In all of our validation scenarios, H_pi always served well in learning the dependency structure. We believe that this is due to the "constructed nature" of the reinforcement learning benchmarks. The tasks themselves are constructed in such a way that learning is possible. We're thinking about whether it is possible to make an argument along this direction in the Appendix.

• Need for JIT-compilation?

• • The JIT-compilation was a design decision in order to have a compact policy space. We are looking for citations and references which show that this approach is a reasonable way to simplify a parameter space.

• Algorithm 4 initialization procedure

• • We use Sobol sequences in order to quasi-randomly sample the parameter space.

We apologize for the last minute and quick response. Due to this issue which we noticed ourselves, we have changed the "metamodel" to a HOM (higher order model), and we have also changed "JIT-compilation" to GEN (generation) or GEN process.

This is more in line with the literature that we are able to find on the topic (as shown in footnote 4).

Dear reviewer,

We are looking into making changes to the draft to aid in readability. Here are immediate answers to your questions.

• The presentation of the paper is poor.

• • We are looking into improving the readability with another draft.

• More background knowledge should be introduced to further clarify the motivations, like the necessity of the JIT compilation.

• • This is an interesting point, our approach with JIT compilation was to save on resources as we were considering the specific use case of memory constrained devices. We will see if we can find other related work which does the same to justify this design choice.

• The notation is extensively abused and many algorithms and notations have no formal definitions (See questions for some of them).

• • We attempted our best to not abuse notation. Unfortunately, to make contributions that would be interesting and valuable to the decision making systems community, as well as have theoretical results, some of our notation was slightly abused.

• The motivation of one of the main contributions, using Hessian in Bayesian optimization is not very clear. As Bayesian optimization is a black-box function, directly querying Hessian might be very hard.

• • We discuss this in detail in Appendix H.

• There are no proofs or lemmas for the theorems.

• • We are not sure about what the reviewer means? Our proofs and lemmas were included in the supplementary materials. Could it be the case that this was not uploaded in OpenReview? If this is the case then we will reach out to the PCs in order to make sure that this will be fixed.

• RW on Learning the dependency graph;

• • We are not aware of other works that learn the dependency graph other than Gibbs sampling or evolutionary algorithms, which we have included.

• RW on Modeling dependency graph as a MPNN;

• • We are not aware of any additional work which models the dependency graph in Bayesian optimization as a MPNN. If the reviewer knows of such a work, we are happy to add it. The closest such related work is that of Rolland et. al.

• RW on Bayesian optimization to learn the graph structure;

• • We do not use Bayesian optimization to learn the graph structure. We use a random sampling strategy over the domain. This is described in Algorithm 4.

• How to observe the surrogate Hessian of the black-box function?

• • We discuss this in Appendix A: To estimate the Hessian, we used the Hessian-Vector product approximation. We relaxed the discrete portions of our metamodel policy into differentiable continuous approximation for this phase using the Sinkhorn-Knopp algorithm for the Role Assignment phase. For role interaction network connectivity, we used a sigmoid to create differentiable “soft” edges between each role.

• What is the motivations of using Hessian in BO? If you already observed Hessian, why not using the gradient descent?

• • The motivation for using the Hessian in BO is to generalize the theoretical arguments of Srinivas et. al., Duvenaud et. al., Kandasamy et. al. and Rolland et. al. We believed that by using the Hessian a tighter regret bound in the high-dimensional Bayesian optimization could be obtained. We're not sure what the second part of the question means. Could the reviewer clarify?

• what do you mean by JIT compilations? The meaning is not clear in the context of multi-agent policy structure.

• • JIT compilation is taking the immutable (unchanging) part of the metamodel policy (Alg. 1,2,3) and combining it with the mutable (changing) part of the metamodel policy (the parameters) and constructing the actual model which takes decisions.

• Why do you use MPNN rather than graph convolution, graph attention or other transformer vi rants? These models should be more expressive.

• • As we were interested in making contributions to the decision making systems field, we were not interested in using these techniques from the deep learning literature. It could certainly be the case that using these architectures could be more expressive. We are not able to comment on this as we are not in the deep learning field.

• Regarding $\theta_{r,i}$ and other portions of the metamodel parameter space.

• • We defined these terms implicitly when we used them. Unfortunately due to the space constraints of the conference format, this was the only way we could submit this paper to a conference.
• • These terms are defined, implicitly, in Section 4.1, 4.2, as well as in the graphical illustration of Fig. 2.
• • We also invite the reviewer to read the code included in the supplementary materials, which we have tried to make very understandable and readable.

We continue with further answers in the next comment.

• Superscript $(i)$ in Section 4.4

• • Superscript $(i)$ represents the maximal clique within the additive decomposition. Here a complex high dimensional function space being search over is simplified by assuming it is constructed through addition of functional subspaces. This allows us to use the nice properties of linearity of addition. We touch upon this further in the proof of Proposition 1 in Appendix E.

• What is the mathematical expression of regret $r(t)$ of querying Hessian?

• • The regret mathematical expression is related to the model of computation we are analyzing in. For example, often time or space complexity is analyzed in order to understand and evaluate the quality of algorithms. Communication complexity is another complexity term that is used in distributed computing environments. In decision making algorithms, typically the key complexity is the regret, which compares the decision made to the best possible decision that could have been made with perfect information.

• What is $\mathcal{U}$ in Algorithm 4?

• • $\mathcal{U}$ represents the uniform random distribution that we sample from in order to learn the dependency structure.

• What is the Max-Cliques operation in Algorithm 4?

• • The Max-Cliques operation in Algorithm 4 computes the maximal cliques that was discussed earlier in our response. This is related to finding the Max-Cliques that allow us to simplify the functional space which we discuss further in the proof of Proposition 1. We note that typically, this specific operation is NP-hard in time complexity, however, this is typically thought not to be a problem within the model of computation we are analyzing in (decision making).
• • This specific operation was approximated quickly using the NetworKit library.

We want to highlight our defined term, "JIT-compilation."

In the introduction we describe, "To achieve this, we use a metamodel which generates a policy model. The metamodel is divided into immutable instructions (i.e., algorithms) corresponding to the abstractions of the role and role interaction and mutable parameters that are just-in-time (JIT) compiled into a policy model during evaluation."

In section 4.3, we describe, "To overcome these challenges, we propose a metamodel which JIT-compiles into a graphical model. The JIT-compilation is conditional on the agents’ state thus capturing dynamic role interactions; in addition the compilation allows for a more compact policy space with far fewer parameters. The resultant compiled graphical model captures the state-dependent interaction between roles and yields the resultant actions for each role. After compilation, the interaction between roles are captured by the resultant conditional random field."

Also in section 4.3, we describe, "The graphical model compilation procedure is presented in Algorithm 2. Finally, Algorithm 3 drives the JIT-compilation."

We're working on adding a table of notations in order to aid readability which we can include in the Appendix. We will be uploading this shortly.

I apologize that I didn't see the proofs in the appendix in the initial review.

However, I don't find the authors' response satisfactory. It remains unclear of the motivation of doing Hessian aware algorithm for black-box optimization and how costly it will be. Hessian type of methods are like double-sword but the author didn't make it clear what's the disadvantages and limitations. The authors said that they would do their best to improve the paper and would update the paper. However, till now, there has been no revision uploaded (I checked the revision history and found it empty). Because the paper was poorly written, the paper remains poorly written since there is no update. Thus, it is still difficult for me to understand and assess the contribution of the paper.

Therefore, I would keep my score.

• We will immediately reach out to the PC as this should not be the case. We have uploaded many revisions for the paper.
• We elaborate on the costs and benefits of the Hessian several times within the paper, and show that due to the expensive nature of the Hessian, we focus our specific use case to only decision making systems where a useful and valuable surrogate Hessian can be extracted from observing the policy generation process.
• • Introduction: In our work, we overcome this shortcoming by observing the GEN process of the HOM. In particular, we can measure a surrogate Hessian during the GEN process which significantly simplifies the task of learning the additive structure. We term this approach Hessian-Aware GP-UCB (HA-GP-UCB) and visualize our approach in Fig. 1.
• • Section 4.4: In practice, observing the hessian $H_v$ is not possible due to v being a black box function. However, during the GEN process we can observe a surrogate Hessian, $H_\pi$. This surrogate Hessian is closely related to the $H_v$ as $v(\theta)$ is determined through interaction of the policy with an unknown environment. Because the value of a policy is a function of the policy; it follows by the chain rule $H_\pi$ is an important sub-component of $H_v$. We utilize the surrogate Hessian in our work and demonstrate its strong empirical performance in validation.
• • Appendix H: In Section 4.5 we remarked that although we cannot observe $H_v$, we can observe a surrogate hessian, $H_\pi$ which is related to $H_v$ by the chain rule. We justify our choice here with showing how $H_\pi$ is an important sub-component of $H_v$ (Skorski, 2019).
• • Appendix H: A possible avenue of overcoming this limitation is considering Hessian estimation through zero’th order queries. Several works along this direction have recently appeared using Finite Differences (Cheng et al., 2021), as well as Gaussian Processes (Müller et al., 2021). We consider removing this dependency on the surrogate Hessian for future work.

We want to especially highlight, our approach is not a general purpose approach to Bayesian Optimization. Our approach is an approach to solving difficult problems in decision making systems using Bayesian Optimization. General purpose HA-GP-UCB is outside the scope of this work.

We thank the reviewer for continuing to engage with us. I empathize with the reviewer, and I can confidently state that this work attempts to have the most content within the conference format. This comparison is with the other works I am reviewing right now across major conferences associated with machine learning.

We want to highlight the key points that went into the research and construction of this paper which make it a valuable contribution:

• Our work needed to be theoretically grounded requiring a regret bound.
• Our work was in the subfield of high-dimensional Bayesian optimization requiring us to fix the incorrect proof by Kandasamy et. al. and give a non-trivial and complete regret bound when compared to the work of Rolland et. al.
• Our work needed to have strong empirical results in at least one subfield of machine learning to justify our approach.
• Our work needed to have strong empirical results in a currently valuable field of machine learning to have a chance of acceptance to the conference format.

Given the above constraints, our paper attempted to satisfy all these requirements which made it hard to follow. We thank the reviewer for their work in reviewing this paper.

Dear reviewer,

We are looking into making changes to the draft to aid in readability. Here are immediate answers for your questions:

• This paper is hard to follow. There are too many components but they are not described appropriately.

• • We are looking into how best to edit the main paper text and the appendix in order to improve the readability of the paper.

• Writing and presentation should be improved. For example, the Introduction section is started by the following sentences: "Decision Making Systems choose sequences of actions to accomplish a goal. Multi-Agent Decision Making Systems choose actions for multiple actors working together towards a shared goal. Multi-Agent Reinforcement Learning (MARL) has emerged as a competitive approach for optimizing Decision Making Systems in the multi-agent settings" These are three independent sentences. This part should be re-written. In addition, a period is missing. Also, this sentence "We propose the usage of Bayesian Optimization (BO)" is somewhat unnatural. Please revise it. There are other cases, but I would not enumerate all of them. Please revise an article carefully.

• • We are looking into how best to edit this part of the paper. We do want to highlight that the purpose of these three sentences is to highlight and show that, our specific contribution is to the field of multi-agent decision making systems, not reinforcement learning, or Bayesian optimization. As this is the case, we needed to frame and introduce all of these areas and how they're related within the introduction and how our work fits in the context of these areas.

• Figures are too small and legends are overlapped with graphs; please see Figures 4 and 5.

• • We can include larger figures which are the exact same as Figure 4 and 5 in the Appendix. As our contribution requires significant validation, we had to make the figures a bit smaller to present all of the important validation in the main text.

• Theoretical results heavily rely on the previous work, in particular (Srinivas et al., 2010).

• • We respectfully disagree. We believe that our work builds on top of Srinivas et. al., as well as Duvenaud et. al., Kandasamy et. al. and Rolland et. al. We do want to highlight that our theoretical results are novel as they provide a regret bound that scales with O(log D) with the dimension, which is significantly better than other bounds in high dimensional Bayesian optimization.

• I would like to ask about the results in Figure 5. First off, why do BO results only show current maxima until a particular iteration, i.e., monotonically increasing? Why are the other results fluctuated? Also, why do the results at initial iterations differ across algorithms? It seems unfair to the baseline methods. Moreover, some baseline methods are better than the proposed methods. These results seem reasonable. Why do the authors use Bayesian optimization instead of reinforcement learning in these problems?

• • This is intimately related to how (in the area of decision making systems) different approaches are evaluated. In reinforcement learning based decision making systems, the policy that is evaluated is the singular policy that is being trained using reinforcement. In Bayesian optimization, the policy that is evaluated is the best found policy so far. Hence the difference between policy search (Bayesian optimization) and policy reinforcement (reinforcement learning). Our validation and our results show in resource constrained environments, with malformed or sparse reward, our approach of policy search using Bayesian optimization outperforms policy reinforcement methods such as various reinforcement learning methods we validated against.

• Results in Table 1

• • In Table 1 we show the conditions under which HA-GP-UCB outperforms related work. This is related to the motivation and problem statement of the paper where we are interested in sparse or malformed rewards in cooperative multi-agent decision making scenarios.

We thank the reviewer for engaging in discussion with us.

Although it is highly unusual, and we have not seen results in reinforcement learning papers displayed in such a manner. We have created a new Appendix, Appendix K, where we replot the results from reinforcement learning approaches using the "best policy found so far" approach similar to BO. We want to point out that in practice, this is not how reinforcement learning works. However, in the spirit of giving reinforcement learning the best benefit of the doubt, we have created Appendix K with these results.

In this Appendix, we see that all our conclusions from the paper still remain and stand.

In addition, we repeat the same procedure for Table 5, and Table 6 which investigate RL and MARL under sparse or malformed reward. This is presented in Appendix L. In Appendix L, we see that all our conclusions from the paper still remain and stand as shown by Table 7 and Table 8.

We have also expanded footnote 10 to refer to Appendix J, Appendix K, and Appendix L showing these alternate presentations of data.

We hope that this helps the reviewer compare the two approaches of policy search and policy reinforcement. We also note that in all these cases, the data presented is overly favorable to RL and MARL, yet still our conclusions and observations hold.

We are also happy to help clarify any other concerns and engage with the reviewer further for this paper.

We once more thank the reviewers for reviewing this paper. We have an additional revision for the reviewers. In this revision, we add a table of notations for the reviewers. This table can be found in Appendix B. We have also added a footnote at the beginning of the Design section (footnote 2) pointing to Appendix B.

We are happy to answer any questions and provide any more details and interact with reviewers to help them reach a decision on this paper.

We also thank the meta-reviewer for the upcoming task of making a decision on this paper given the diverse set of scores and reviews this paper has received.

Sincerely,

The authors of Hessian-Aware Bayesian Optimization for Decision Making Systems.