A Unified Framework for Bayesian Optimization under Contextual Uncertainty

Thank you for the time and effort spent writing this review, and for your interesting questions.

1. On the necessity of both $\alpha$ and $\beta$: Both parameters are necessary, as robust satisficing and worst-case sensitivity have $\alpha=0$ and do not involve the $v(\mathbf x)$ term at all. If only $\beta$ were present, we would not be able to set the weight on the $v(\mathbf x)$ term to $0$ to recover these objectives.

2. On what happens if $d(\mathbf p_t, \mathbf p^*)$ does not approach $0$: In practice, even if $\mathbf p_t$ does not approach $\mathbf p^*$, we are still able to get good performance. In our experiments, for simplicity, we keep $\mathbf p_t$, $\mathbf p^*$, and $\epsilon_t > 0$ constants throughout, and we see that TS-BOCU still performs well and displays the sublinear property. The necessary condition for good performance is nuanced: informally speaking, we can perform well as long as the learner is able to reduce the uncertainty at all 'relevant' decision-context points, where 'relevance' is determined by the supports of the distributions within the uncertainty set $\mathcal U_t$. Notice that $\mathbf p^*$ only governs the distribution of contexts observed, and is not a part of the uncertainty objective: only the learner-chosen parameters $\mathbf p_t$ and $\epsilon_t$ are. This means that, if the true underlying function $f$ were completely known to the learner, it does not matter what $\mathbf p^*$ is, the learner would be able to solve the problem exactly. $\epsilon_t \rightarrow 0$ (with the constraint $d(\mathbf p_t, \mathbf p^*) \leq \epsilon_t$) is a sufficient but not necessary condition for good performance. $\mathbf p^*$ gets more difficult to learn as $|\mathcal C|$ increases.

3. On the performance of TS-BOCU on the DRO uncertainty objective in Infection: While the performance seems not great, we still observe the sublinear property towards the final iterations as the growth of the curve slows down. If we were to run the experiments for more iterations, this sublinear property would be more clear. Also, it may simply be the case that the baselines are very strong in this setting. UCB-BOCU is explicitly designed for the DRO uncertainty objective, whereas a possible reason that UCB-RO performs well is that the RO optimal decision coincides with the DRO optimal decision with this objective function. In any case, the sublinear property still assures us that our algorithm is able to handle the DRO objective as expected, although the relative performance between baselines will certainly vary depending on specific objective function.

4. On the finite decision and context spaces: We have formalized the extension to continuous, infinite decision sets in the new uploaded revision. The regret bound maintains the same order with respect to $T$, and the conditions necessary for sublinear regret remain the same as explained in the body of the paper. Please see our global response titled "Revision for infinite decision sets and intractability of infinite context sets" (https://openreview.net/forum?id=oMNkj4ER7V&noteId=EjvMtBW1sK) for more details. In that post, we have also defended the assumption of a finite context set. To summarize the salient points, DRO with infinite context sets is intractable with general convex distribution distances $d$, and this difficulty leads to the assumption of a finite context set being standard in the DRBO literature. Our experiment results are still from an implementation with a finite decision set, but we imagine that the results would not be too different if the optimization were performed over an infinite decision set instead.

5. On guidance for setting $\alpha$, $\beta$, and $\epsilon$ in practice: We agree with you that such a discussion would be interesting and useful. However, we also fear that such a discussion would become more subjective and philosophical than technical, and may depend too much on the individual use case. For example, what arguments could be made for a risk-averse learner to optimize the value-at-risk versus the conditional value-at-risk versus the mean-variance tradeoff? We decided in the end that an extended discussion on this topic would be out of the scope of this paper. We leave the choice of uncertainty objective to the practitioner; our goal was to show that the practitioner can choose between a large diversity of uncertainty objectives with a single mental framework and a single algorithm.

We hope this response has improved your opinion of our paper.

Thank you for the time and effort taken to review our paper.

1. On the significance of the unification and the analysis: We believe that the significance of the unification goes beyond adding two parameters, as the right-derivative of the DRO objective at any $\epsilon$ was not known in the BOCU literature to be an uncertainty objective of interest. Tay et. al. (2022) introduced the idea of worst-case sensitivity to DRBO, but the worst-case sensitivity is only the right-derivative at $\epsilon = 0$. Our work is the first to establish the general usefulness of the right-derivative by proving in Proposition 3.1 that the right-derivative at $\epsilon > 0$ is of theoretical interest as well through the robust satisficing objective. We believe that this is a non-trivial and elegant extension of DRBO. As you have pointed out, it is good to have a unified form for previously unrelated objectives, but the unification was anything but straightforward.

   Recognizing and formally proving the relevance of the right-derivative was only the first part: the novel analysis of the regret bound for Thompson sampling when the right-derivative is part of the objective was not a straightforward undertaking. As we mention in the paper, the derivative term presents significant challenges: the limit term causes difficulties without a closed form, and the inner term is a difference of worst-case expected values which, informally speaking, `erases' the dependency on the uncertainty set and precludes bounding it in terms of the margin $\epsilon$ as was done for the DRO objective. We encourage you to explore the supplementary material, in particular Lemma A.3 and its auxiliary lemmas Lemma A.4, A.5, A.11, A.12, and A.13, to see the work involved in bounding the DRO first-derivative regret. For rigor, we also prove with Proposition 4.2 that the upper bound sequence $U_t$ used in the proof of the regret bound is well-defined.

2. On the first-derivative objective: Sections 2 and 3 on the general framework are general enough to be applicable outside of BO as well; note that the sequential learning setting and GPs are only introduced in Section 4. Proposition 3.1 is an original proposition that, to the best of our knowledge, has not been published anywhere else. It is entirely plausible that a similar result exists in the operations research literature that we are unaware of, and that we have simply re-discovered it. However, given that robust satisficing was only introduced this year (Long et. al., 2023), it seems unlikely.

3. On the finite decision and context spaces: We have extended our results to continuous, infinite decision sets in the new uploaded revision. The regret bound maintains the same order with respect to $T$, and the conditions necessary for sublinear regret remain the same as explained in the body of the paper. Please see our global response titled "Revision for infinite decision sets and intractability of infinite context sets" (https://openreview.net/forum?id=oMNkj4ER7V&noteId=EjvMtBW1sK) for more details. In that post, we have also defended the assumption of a finite context set. To summarize the salient points, DRO with infinite context sets is intractable with general convex distribution distances $d$, and this difficulty leads to the assumption of a finite context set being standard in the DRBO literature.

We hope this response has improved your opinion of our paper. Please let us know if you have any more concerns, we are happy to engage further.

Hello, a gentle reminder that the author-reviewer discussion period ends in about 2 days. If you have any remaining questions or concerns about our work after reading our response, please let us know so we may address them. Thanks!

Thank you for your review.

1. On the finite decision and context spaces: We have extended our results to continuous, infinite decision sets in the new uploaded revision. The regret bound maintains the same order with respect to $T$, and the conditions necessary for sublinear regret remain the same as explained in the body of the paper. Please see our global response titled "Revision for infinite decision sets and intractability of infinite context sets" (https://openreview.net/forum?id=oMNkj4ER7V&noteId=EjvMtBW1sK) for more details. In that post, we have also defended the assumption of a finite context set. To summarize the salient points, DRO with infinite context sets is intractable with general convex distribution distances $d$, and this difficulty leads to the assumption of a finite context set being standard in the DRBO literature. This should address your concerns about the strengths of these assumptions and the corresponding usefulness of our theoretical results.

2. On the reference distribution $\mathbf p$: We wish to emphasize that the reference distribution $\mathbf p$ is a problem parameter chosen by the learner and captures the learner's prior belief of the context distribution, and is not the true distribution $\mathbf p^*$. It is very possible in real life to obtain a reasonable prior distribution for random contexts, such as from expert knowledge or estimation from historical data. For instance, in the introduction's example of sunlight in farming, the amount of solar radiation is a quantity that has been tracked by meteorological organizations for decades (e.g., https://nsrdb.nrel.gov/). A reasonable reference distribution of solar radiation can be estimated from this data. If the learner has no expert knowledge or historical data, they can simply set the reference distribution at iteration 1 $\mathbf p_1$ to be the uniform distribution with a large margin $\epsilon_1$ to capture the uncertainty, then update their reference distributions $\mathbf p_t$ for $t>1$ based on the observed contexts over the learning procedure. This is the 'data-driven' setting in Kirschner et. al. (2020) described under 'Conditions for sublinear regret' in Sec. 4.

   From a more technical perspective, it is not possible to even define the DRO problem without a reference distribution. Every problem definition under the BOCU framework needs some reference distribution to say anything useful, including BO for expected values (Toscano-Palmarin & Frazier, 2022), risk-averse BO (Cakmak et al., 2020; Nguyen et al., 2021a;b), and prior work in distributionally robust BO (Kirschner et al., 2020; Nguyen et al., 2020; Tay et al., 2022).

3. On the "reasoning and justification behind experimental results". We have to kindly ask you to elaborate on your concerns. What exactly about the design of the experiments do you not understand or agree with? Is it the choice of 1) objective functions, 2) uncertainty objectives, 3) distribution distances, 4) problem parameters, or 5) baselines? We believe we have made a reasonable effort to compare our proposed algorithm to suitable baselines across a diversity of objective functions, uncertainty objectives, and distribution distances. If there is anything that does not make sense to you, please specify them so that we can discuss them and improve our paper.

4. Your style suggestions have been noted. In the latest revision, we have moved the caption of Table 1 to the top. Due to ICLR's citation style that requires the name and date, including the references in Table 1 would cause it to be too cluttered. We have instead included equation numbers beside each uncertainty objective; the relevant references are always right before each equation.

We hope these revisions and clarifications have improved your opinion of our paper. We look forward to hearing more from you.

Hello, a gentle reminder that the author-reviewer discussion period ends in about 2 days. If you have any remaining questions or concerns about our work after reading our response, please let us know so we may address them. Thanks!

Thank you for your review and your insightful comments.

1. On the assumptions in Theorem 4.1.: Note that we have uploaded a new revision of the paper to extend our results to infinite decision sets, and in so doing require an additional assumption.

   a. Assumption 1, that the GP kernel is either the squared exponential kernel or the Matérn kernel with $\nu > 2$: This assumption is required for the extension to infinite decision sets, see our global post for more details. It is a standard assumption for the discretization argument (Kandasamy et al., 2018; Srinivas et al., 2010). This assumption is a modeling choice and thus can certainly be true in practice, in fact, these are the most popular kernels used in practice.

   b. Assumption 2, that the distribution distance $d$ is the TV distance: This assumption is not a common assumption in the relevant literature, and was made in order to aid regret analysis due to the challenging derivative term in our novel objective function. As mentioned in the paper, the assumption that $d$ is the TV distance aids analysis considerably as TV admits a closed form for the optimal solution of the convex optimization problem Equation 2 (see Lemma A.11 in Appendix A.11). This assumption is also a modeling choice and thus can also be true in practice if the practitioner wishes it to be.

   c. Assumption 3a, that for all $t\leq T$, $d(\mathbf p_t, \mathbf p_t^*) \leq \epsilon_t$ : This is a standard assumption in DRBO (Kirschner et. al., 2020; Tay et. al., 2022). This assumption is used to ensure that the true distribution $\mathbf p_t^*$ is within the uncertainty set $\mathcal U_t$, so that we can bound the distance between $\mathbf p_t^*$ and the worst-case distribution $\mathbf q_t$ via a triangle inequality with the reference distribution $\mathbf p_t$. Informally speaking, we need $\mathbf p_t^*$ to be within some known distance from $\mathbf q_t$, otherwise the regret (computed with $\mathbf q_t$) cannot be related to the observed contexts (drawn from $\mathbf p_t^*$). In practice, while $\mathbf p_t$ and the margin $\epsilon_t$ are chosen by the learner, $\mathbf p_t^*$ is unknown and thus it is not possible to guarantee that it holds, other than with a trivially large $\epsilon_t$. This issue can be alleviated by choosing $\mathbf p_t$ that is likely to be close to $\mathbf p_t^*$ via expert knowledge or estimation from historical data, or by taking the 'data-driven' approach from Kirschner et. al. (2020) and adapting $\mathbf p_t$ to the observed contexts during the learning procedure.

   d. Assumption 3b, that for all $t\leq T$ and all $c \in [|\mathcal C|]$, $p^*_{t, c} \geq p_{\text{min}} > 0$. This assumption was also made in Theorem 4.2 in Inatsu et. al. (2022). We require this assumption again in order to aid regret analysis due to the challenging derivative term in our novel objective function. Intuitively, if a context has $0$ probability of being observed, the uncertainty at decision-context pairs with that context is very difficult to reduce. In practice, since $\mathbf p_t^*$ is not controllable, this may not hold. However, this problem may be alleviated by a careful choice of context domain such that it is unlikely that any of the contexts have $0$ probability of occuring.

2. On the maximum information gain $\gamma_T$: $\gamma_T$ is not bounded in $T$, but as long as $\gamma_T < \mathcal O(T)$, the overall regret bound is sublinear in $T$ and the algorithm converges to the optimal solution. Examples of kernels that fulfill this condition are the linear, squared exponential, and Matérn ($\nu > 1$) kernels. From Theorem 5 in Srinivas et. al. (2010), for the linear kernel, $\gamma_T = \mathcal O(d \log T)$; for the squared exponential kernel, $\gamma_T = \mathcal O((\log T)^{d+1})$; for the Matérn kernel with $\nu > 1$, $\gamma_T = \mathcal O(T^{d(d+1)/(2v+d(d+1))}(\log T))$, where in this context $d = m + \ell$ is the dimensionality of the joint decision-context space.

3. On the performance of TS-BOCU on the DRO uncertainty objective in Infection: While the performance seems not great, we still observe the sublinear property towards the final iterations as the growth of the curve slows down. If we were to run the experiments for more iterations, this sublinear property would be more clear. Also, it may simply be the case that the baselines are very strong in this setting. UCB-BOCU is explicitly designed for the DRO uncertainty objective, whereas a possible reason that UCB-RO performs well is that the RO optimal decision coincides with the DRO optimal decision with this objective function. In any case, the sublinear property still assures us that our algorithm is able to handle the DRO objective as expected, although the relative performance between baselines will certainly vary depending on specific objective function.

We hope our response has improved your opinion of our paper.

Hello, a gentle reminder that the author-reviewer discussion period ends in about 2 days. If you have any remaining questions or concerns about our work after reading our response, please let us know so we may discuss them. Thanks!