Robust Bayesian Satisficing

Summary

The paper proposes robust Bayesian satisficing, a new setting of BO that is similar to distributionally robust BO. Robust Bayesian satisficing aims to achieve a 'good enough' expected value given by some threshold $\tau$ and relaxed by the distribution distance between a reference and a true distribution. The paper proposes 2 new notions of regret, design an algorithm with regret bounds, and empirically compare this algorithm to DRBO and other suitable baselines.

Strengths

1. Robust satisficing as a new optimization objective for BO is interesting and presents an alternative 'good enough' objective along with a relaxation based on distribution distance that is sensible. It enables distributionally robust BO in another way that does not involve uncertainty sets. 2. The new regret definitions make sense, and the proposed algorithm is supported by theoretical guarantees on its performance via regret bounds. 3. The empirical evaluations present support the claim that the proposed algorithm performs well with the proposed regret definitions. 4. Overall I believe that this work has relevance to the community, subject to the issues raised in the Weaknesses section being addressed properly.

Weaknesses

Technical concerns: 1. How is the threshold $\tau$ to be selected in a real world problem? The paper states that it 'can be expressed as a percentage of the SO solution', but when $f$ is unknown, the expected value of the SO solution is unknown as well. From Algorithm 1, $\tau$ is an input prior to any BO rounds. This is an important question to answer, since one of the claimed advantages over DRBO is that there is no need to pick uncertainty sets which may be unknown a priori. But now you have to pick $\tau$ which is also unknown a priori, so it seems that you have replaced one hyperparameter for another. In order to satisfy Assumption 1, it is claimed that $\tau$ can be dynamically selected, but that makes the regret and thus the regret bounds not well-defined, since the regret is a function of a constant $\tau$. If $\tau$ is to be dynamically selected and learned, then the algorithm and regret bounds should be explicitly written to take this into consideration, instead of claiming in a footnote that it 'can be straightforwardly adapted to work with dynamic thresholds'. 2. The experiments in the main paper are simple synthetic benchmarks which by themselves are not comprehensive enough an empirical evaluation. I see that you have an interesting real world benchmark on insulin dose allocation in the appendix, why is it hidden there without a reference from the main paper? Why aren't WRBO and SO tested on that benchmark? Clarity issues: 1. The equation below line 102 defining $\kappa_{\tau, t}$ and the preceding sentence does not quite make sense. It seems to me that you do not need that sentence and equation, simply define fragility as in Eq. (1), and then the following sentence makes clear what $x_t^*$ and $\kappa_{\tau, t}$ are. 2. In all the figures, heatmaps are uninterpretable without a colorbar indicating the values that each color corresponds to. 3. Lemma 1 uses the maximum information gain $\gamma$ before it is defined, and includes a definition for determinant when determinant is not used there.

Questions

No additional questions other than those raised in Weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes.

Summary

This paper studies a contextual Bayesian optimization problem when the true and reference distributions of the context can be different due to distribution shifts. The authors propose an algorithm called robust Bayesian satisficing algorithm (RoBOS) based on the idea of robust saisificing (RS). Through theoretical analysis and empirical results, the authors demonstrate their results on two notions of regret: lenient regret and robust satisficing regret. For the theoretical part, the authors have a thorough analysis and show that RoBOS achieves with high probability $\tilde{\mathcal{O}}(\gamma_T \sqrt{T})$ robust satisficing regret and $\tilde{\mathcal{O}}(\gamma_T \sqrt{T} + \sum_{t=1}^T \epsilon_t)$ lenient regret, where $\gamma_T$ is the maximum information gain and $\epsilon_t$ is the amount of distribution shift in round $t$. For the empirical part, the authors propose two synthetic benchmarks and one real-world benchmark, and for all cases, they demonstrate RoBOS outperforms distributionally robust BO (DRBO).

Strengths

Distribution shift is an important challenge in Bayesian Optimization, and it is great authors propose a new algorithm that attempts to address these issues, it also brings in some new interesting future research questions. The proposed question and results are new, to my best knowledge. I also like the algorithm, which naturally combines the empirical fragility and common algorithms in the contextual Bayesian optimization setting. The paper is well-written in most parts except for a few minor parts.

Weaknesses

My biggest concern is the two regrets defined in the paper: the lenient regret and the robust satisficing regret, which depends explicitly on the threshold $\tau$. In particular, previous papers in robust satisficing [1] also did the analysis using common performance measures such as average performance. The authors also lack justification for their proposed new notion: robust satisficing regret, beyond matching the definition of robust satisficing which might favor RoBOS. In addition, think the theoretical analysis employed is standard in the literature. I think the following issues need to be addressed: 1. Could you also demonstrate (theoretically or empirically) the performance of RoBOS if the goal is to maximize the reward? 2. How sensitive is the choice of $\epsilon$ in DRBO/ WRBO versus the choice of $\tau$ in RoBOS? In the literature, e.g., Figure 1 of [1], they measured the performance of the robust satisficing model over a sequence of $\tau$ and solve the distributional robust optimization model over a sequence of radius of $r$, then they compared the efficient frontier on both average performance and CVaR. This might be a way to further justify the effectiveness of RoBOS. Reference: [1] Daniel Zhuoyu Long, Melvyn Sim, and Minglong Zhou. Robust satisficing. Operations Research, 71(1):61–82, 2023.

Questions

There are a few places where terms are not defined in the statement, or they are confusing: 1. In lines 102 and 103, can you be more specific on the difference between $\kappa_{\tau,t}$ and $\kappa_{\tau,t}(x)$? In particular, in both optimization problems, what are the decision variables, and what is fixed? 2. In Lemma 1 (line 155), the term $\gamma_{t-1}$ is not defined, the term appears in line 185, which should be moved earlier. 3. The definition of $B’$ should be moved from line 227 to the statement of Theorem 4. 4. In Figure 3, the first line, should be benchmark “2”. Questions for the empirical results: 1. In Figure 1, why $\tau = Z_0/2$? 2. In line 256, the true distribution is picked randomly from the set $\mathcal{U}_t$, can you be more specific on this? 3. In Figure 3, the latter 2 plots seem incomplete. For lenient regret, why does the plot only plot for $t \le 100$? For robust satisficing regret, only RoBOS is complete. 4. In both synthetic benchmarks, could you justify the choice of $\tau$? In particular, are the experimental results consistent for a wide range of $\tau$? Questions for the theoretical results: 1. Page 10 of the appendix, line 288: is the reward function $r(t)=-|o(t-K)_+|$? 2. How is Eq (29) in line 323 derived? Why can we set $B=1$ in Lemma 5? It might be good to be more specific here.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors stated their proposed method RoBOS may be worse than DRBO if the goal is to maximize the reward, which is the main limitation of their work. The other potential limitation I think is the robust satisficing model might be sensitive to the choice of $\tau$. I suggest the author also analyze their results in other performance measures and see how sensitive their results are with respect to the choice of $\tau$. There is no potential negative societal impact.

Summary

This paper studies robust satisficing in contextual Bayesian optimization under distribution shift in the distributions of the context. They show that under some assumptions their algorithm achieves sublinear lenient regret and under some relaxed assumptions they achieve sublinear robust satisficing regret. They compare their method agains distributionally robust optimization approach [10] for contextual Bayesian optimization.

Strengths

I have my reservations against points that I mentioned below, but I believe this research direction is valuable and interesting.

Weaknesses

The writing of the paper can be improved. The clarity and coherence of the writing could be enhanced. There are instances where the ideas are not effectively communicated, leading to confusion for the reader. Furthermore, the structure of the paper could benefit from more logical organization and smoother transitions between sections. Additionally, some grammatical and punctuation errors need to be addressed, as they can detract from the overall quality of the paper. A revision focusing on refining the writing style and ensuring a more polished presentation would greatly strengthen the paper.

Questions

1) Why did you choose to use MMD distance to measure the discrepancy between distributions. 2) In Table 1, there must be a space between $\min$ and $k$ for RS objective. 3) I do not fully understand why one would prefer RS over DRO. Can you please clarify this point? When it would make sense to use RO, RS and DRO? 4) Line 141: Please provide references that GP assumption is common. 5) Lemma 1: Where does the det operator appear appear in Lemma 1? Why is it introduced there? What is $\gamma_{t-1}$? What is $e$? 6) If LCB is never used, why it is introduced? 7) How restrictive the regularity assumption on $f$? 8) Optimism in the face of uncertainty is a well-known concept but I am not sure how it is motivated in Section 3 and how your model is optimistic. Can you please elaborate on this? 9) For the fair comparison of methods: To make a fair comparison between DRBO and your method you should consider robust regret introduced in [10]. 10) Is $\tau$ fixed throughout the algorithm? Referring to footnote at Page 7, I understand that you claim $\tau$ can be selected adaptively but I think it must be selected adaptively otherwise $\hat \kappa_{\tau, t}(x)$ can be infinity, right? 11) Can you please intuitively explain what does the model in (1) satisfy and what is it robust against? Why $\tau$ can be explained as $Z_t? 12) I find it unnatural that the regret bound in Theorem 3, is not dependent on $\tau$. I understand it is because $\tau$ appears also in the RS regret definition. I think a more natural approach would be separating these two $\tau$'s and seeing that the regret only depends on the difference of these two $\tau$'s. (similar argument goes for the lenient regret) Can you also show the regret guarantee on the robust regret as defined in [10]?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Yes.

Summary

I think the main contributions of this paper are as follows: - Proposes a new decision-making framework called robust Bayesian satisficing (RBS) which combines robust satisficing with Bayesian optimization. RBS aims to achieve a satisfactory solution under distributional shifts by observing a predefined satisfactory threshold. This is different from distributionally robust optimization which requires an ambiguity set and stochastic optimization which optimizes for a given reference distribution. - Defines two regret measures to evaluate the performance of RBS algorithms: lenient regret and robust satisficing regret. Lenient regret measures the cumulative loss of an algorithm's chosen actions with respect to an aspiration level. Robust satisficing regret measures the loss with respect to the robust satisficing benchmark which is the aspiration level minus the fragility (a measure of suboptimality per unit distribution shift). The paper shows the connection between these two regret measures. - Proposes an RBS algorithm called Robust Bayesian Optimistic Satisficing (RoBOS) which uses Gaussian processes to model the objective function. RoBOS only requires an aspiration level as input and does not need an ambiguity set. RoBOS chooses actions to minimize the estimated fragility which is an optimistic estimate of the true fragility. - Proves that RoBOS achieves sublinear robust satisficing regret and lenient regret under certain assumptions. The regret bounds depend on the maximum information gain and the sum of distribution shifts. - Demonstrates the effectiveness of RoBOS on synthetic problems and compares it with other robust Bayesian optimization algorithms.

Strengths

Robust Bayesian satisficing is a novel framework that combines robustness to distributional shifts with satisficing behavior. This provides an alternative to existing paradigms like distributionally robust optimization and stochastic optimization. RBS does not require precise knowledge of the ambiguity set and can handle unknown distribution shifts. Also, the paper provides theoretical guarantees on the regret of RoBOS under some assumptions. The robust satisficing regret and lenient regret of RoBOS grow sublinearly with time. The regret bounds show the dependence on maximum information gain and the sum of distribution shifts, providing insight into how RoBOS handles distributional shifts. In addition, the experimental results verify the theoretical findings on the sublinearity of the regret bounds. Finally, the paper is well-written, clear, and easy to follow.

Weaknesses

- Some assumptions seem to be strong for this problem. For example, the bounds require the sum of distribution shifts to be sublinear in time which may not always hold in practice. It would be good to discuss how the algorithm behaves when these assumptions are violated. - The experiments are limited to synthetic problems. It would be good to evaluate RoBOS on some real-world benchmark problems to demonstrate its effectiveness in practical settings. Comparisons with more algorithms on these problems would also strengthen the experimental evaluation. There are many datasets for distributional shifts that the author can leverage to verify their algorithm. - Although as defined in the conclusion as a future direction, it would be beneficial to discuss the effects of continuous context in this problem, since the focus is on deterministic contexts in this paper. Analyzing RoBOS when contexts are stochastically generated would provide greater insight into how it handles uncertainty.

Questions

In addition to the previous section: I am curious how this approach can be utilized for test-time distribution shifts and adaptations.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

They covered this part very well in my view.

Response to the author rebuttal

I thank the authors for their detailed response. I have some further comments that I realize when I was going over the paper. * In Figure 1, is there a typo in the definition of $Z_0 = \mathbb E_{c \sim P_t}$? * I am still having hard time understanding why $\tau$ can be explained as a percentage of $Z_t$ when $f$ is known. * I do not see that the assumption $\tau\leq \mathbb E_{c \sim \mathbb P_t}[f_{\hat x_t}]$ in the statement of Theorem 3. In Line 190, it is stated that Theorem 3 holds for any threshold $\tau$. Can you please clarify these points? Thank you!