Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides an algorithm for the problem of episodic Contextual Bayesian optimization (CBO) under “switching costs” associated with the decision at each round. This problem formulation is motivated by the application of altitude optimization for Airborne Wind Energy (AWE) systems, in which a wind turbine’s operating altitude can be changed between episodes in order to maximize energy production, but where the changing of altitude itself uses energy. Noting that this problem setup is similar to that in metrical task systems (MTSes) except that the objective function is unknown, the authors propose a Gaussian Process-based variation of the mirror descent schemes used to address MTS problems. They provide a bound on the cumulative regret of their algorithm, and show in both synthetic experiments and experiments in the AWE setting that their algorithm outperforms algorithms that neglect switching costs. 
strengths_and_weaknesses: Strengths: 
* The paper is very well presented. Even as someone who is outside this area, I was easily able to understand the broad strokes of the motivation and approach (even if not the details).
* The problem formulation seems well-motivated by a problem of societal importance, and per the authors’ claim is not previously addressed in the literature (though I am not familiar enough with the literature to validate this claim).
* The proposed method is a nice synthesis of ideas proposed separately in the CBO and MTS setting.
* The experiments are thorough and convincing, demonstrating and validating the settings in which the proposed algorithm and baselines do/don’t do well.

Weaknesses: 
* In Section 4.1 (AWE experiments), it is not clear to me how MinC-Known and MD-Known were run as baselines if $f$ is in reality not known. Alternatively, if $f$ is in reality known in the AWE setting, then it is not clear to me why the proposed method is needed. More clarity on this would be helpful in understanding whether the current approach is indeed needed and/or how the experiments were run. 
* The authors do not meaningfully discuss any limitations of their approach. However, at minimum, limitations associated with the assumptions made in the paper as well as (e.g.) computational complexity considerations associated with using GPs should be discussed.

Minor points:
* Would it be possible to add error bars to Figure 1?
questions: * In the AWE experiments, in the real-world setting, is $f$ known or unknown? If it is known, what is the justification for the current problem setup? If unknown, how are the MinC-Known and MD-Known baselines run for this experiment?
* What is the implication of assumptions such as the regularity assumptions on $f$, which are utilized to construct the proposed method? How does that affect in what settings (related to wind energy production or more broadly) the method may not be expected to work?
* How computationally intensive is the method, and how does that affect what settings it can be used in and/or how well it might scale?
limitations: * No limitations are discussed. However, at minimum, limitations associated with the assumptions made in the paper as well as (e.g.) computational complexity considerations associated with using GPs should be discussed.
* In the checklist, the authors choose “N/A” when asked to describe any potential negative societal impacts of their work. However, as the proposed GP-MD algorithm is relatively general, it is of course possible that it can have bad applications in addition to the good ones (AWE) focused on in the paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a contextual Bayesian optimization algorithm with penalisation for movement cost, which is motivated by the problem of tuning the altitude of wind turbines to maximize energy output while minimizing the altitude adjustment. That is, a movement cost is incurred which is larger if the difference between the actions selected in the current and the previous steps is larger. The proposed algorithm is based on the problem of metrical task systems, and combines lower confidence bound from Bayesian optimization with online mirror descent. The regret of the proposed algorithm is analysed, and the algorithm achieves competitive empirical performances in a real-world wind energy systems experiment.
strengths_and_weaknesses: Strengths:
- The proposed problem of contextual BO with movement cost is well motivated, through the AWE systems. The experiment on AWE using real-world wind data is also a nice demonstration of the practicality of the proposed method.
- The idea of using the confidence bounds often adopted in BO as a bridge to connect BO with online learning algorithms is a very interesting and promising idea.
- The experiments are well designed, and the experimental results indeed show the advantage of the proposed method.
- The paper is well written.

Weaknesses:
- Two recent works on BO with movement cost are missing:   
[1] SnAKe: Bayesian Optimization with Pathwise Exploration, 2022.    
[2] Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times, 2022.   
The methods in both of these papers are also motivated by the issue of movement cost (i.e., a larger cost is incurred if the selected inputs in two consecutive iterations have larger differences). Both papers were available in Jan 2022, and hence I believe they should have been discussed and compared with.
- I have a major concern regarding the dependence of the regret bound (Theorem 1) on the episode horizon H. Normally, in BO and other bandit algorithms, we consider the regret in every step. That is, if there are in total $T$ iterations/steps, the final theoretical result is usually presented as an upper bound on the total cumulative regret **across all $T$ steps**. In the context of this paper, it will translate to the total cumulative regrets across all $H\times N_{ep}$ steps. However, the regret bound in Theorem 1 has an undesirable dependence on H: for the squared-exponential kernel, both terms in the regret upper bound depend on $H$ linearly, which implies that the total regret in all $H\times N_{ep}$ steps is linear in the number of steps ; for the Matern kernel, the dependence of the first term on H will be super-linear, implying super-linear total cumulative regret.
- Related to the last point, lines 237-238 says that "a similar dependence on H is also present in the batch Bayesian optimization results and analysis that we also build upon (see [19, Theorem 2])". I understand what is meant here, but I think this statement is misleading. In [19], their regret bound has a dependence on $\exp(\gamma_H)$ ($H$ will correspond to the batch size in [19]) rather than $H \times \exp(\gamma_H)$. Moreover, the regret bound depending on $\exp(\gamma_H)$ is only their intermediate results, and in their subsequent analysis, they had shown that by following a special initialization procedure, the dependence on $\exp(\gamma_H)$ can be replaced by a constant which is independent of $H$. Therefore, I think [19] should not be used to justify the dependence of the regret bound on $H$ in this paper. Please correct me if I had any misunderstanding here.
- Also related to the point above regarding the dependence on $H$: lines 263-264 say that "We run the algorithms over a single episode" and that "We also discover that updating the confidence bounds after every timestep in GP-MD leads to better performance in practice". Therefore, it seems that in your practical implementation, you have entirely ignored the episodic setting and reverted back to the standard contextual BO setting. If I understand correctly, (if you ignore the heuristic of updating the confidence bounds after every timestep) in this setting, $H$ will be equal to $T$, and hence your regret bound will not be sub-linear anymore as I discussed above in the point on the dependence on $H$.
- Given what I have discussed in the three points above, I think an explanation as to "why the theoretical analysis follows the episodic setting" is needed. Because for now, it seems to me that the episodic setting is only adopted so that the final regret upper bound can be sub-linear in the total number of episodes, while in practice, the episodic setting is not needed.
- (minor) The paper is in general well written, including the method section of Section 3. The only place I think needs more explanations/intuitions is equation (12) and the paragraph following it.
questions: - Some of the questions have been listed under Weaknesses in "Strengths And Weaknesses" above.
- Equation (3), and lines 128-129: I'm curious about the connection between the regret definition here and the usually adopted regret definition in contextual BO/contextual bandit (e.g., reference [30] in the paper). Does the "offline optimal action sequence" also have the knowledge of the groundtruth functions of f and d? If we let $\alpha=1$ and $\beta=0$, will equation (3) reduce to the same regret definition as that in contextual BO/contextual bandit?
limitations: I didn't find discussions of limitation. I can imagine that potential limitations could be the dependence on $H$ (which I discussed at length under Strengths and Weaknesses), and that the action space is required to be discrete. The paper has no negative societal impact that I can think of.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes and resolves the episodic contextual Bayesian optimization (BO) with movement costs by combining BO and an existing online learning solution to the metrical task system. The proposed algorithm, GP-MD, is proved to have a sublinear regret guarantee. Furthermore, GP-MD is empirically shown to outperform existing contextual BO in problems with movement costs, especially the real-world optimization problem for wind energy systems.
strengths_and_weaknesses: The proposed problem of contextual BO with movement costs is new and significant in practice (e.g., with the applications to wind energy systems). Even though I have not thoroughly gone through the appendix, the proposed algorithm is sound and convincing. The empirical performance of GP-MD is shown in both synthetic and real-world optimization problems.

On the other hand, if I am not mistaken, the setting in the experiments is not episodic: in the algorithm and analysis, the GP posterior is updated after each episode, while in the experiments, the GP posterior is updated after every timestep and the experiments are performed in only 1 episode. To be consistent, the experiments should be performed in multiple episodes, or the algorithm and analysis should be done with GP posterior updated after every timestep. I am also curious about the real-world example where the episodic setting applies.

How is the proposed algorithm scalable to larger action and context space? When the dimension of the action and the context space is larger (e.g., 4 or 5), discretizing the space will result in a large number of points. Therefore, a discussion or the time complexity analysis of the proposed algorithm with respect to the size of the action and context spaces can be helpful.

In the real world experiment, the GP hyperparameters are assumed to be known (fixed), which is not very practical.

There is a minor typo: Ne -> Nep in line 132.

questions: Please clarify on the episodic setting in the experiments and scalability of the proposed approach mentioned above.
limitations: The authors could improve the discussion on the scability of the work with respect to the size of the action and context spaces.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of contextual Bayesian optimization that considers the cost of switching decisions at each round. The main idea is incorporating the online learning for metrical task systems and introducing a randomized mirror descent algorithm. The paper provides regret guarantees and evaluate on altitude optimization for Airborne Wind Energy Systems. Empirically, the proposed approach consistently outperforms baseline CBO approaches.
strengths_and_weaknesses: Strengths:

- Study an important and novel problem in contextual Bayesian optimization that considers moving cost between configurations.
- Good real-word case study.
- Writing is easy to follow.

Weaknesses:

- Possible missing comparison to other baseline.
- No code released.

Originality:

The originality of the paper is two folds. First, it proposes a new problem that has not been studied explicitly in the prior work. Second, it introduces a new method to solve this problem, although the majority of the proposed algorithm is derived from existing work by Coester and Lee.

Quality:

The problem is well defined and the proposed method is complete. The algorithm is not complicated which makes the approach accessible to potentially wide audience.

Clarity:

The writing is clear and easy to follow.

Significance:

The paper studies a very important problem in contextual Bayesian optimization that considers moving cost between configurations.

questions: - Why does the paper only considers CBO with moving cost, not the vanilla BO with moving cost? If vanilla BO with moving cost, would the problem be reduced to  multi-objective BO?
- Why does the experiment not compare to the method in paper "Bayesian optimization for modular black-box systems with switching costs"?

I would like to hear more justifications on these questions from the authors.
limitations: - No mention on open-sourcing the code.
review_title: null

Meta-review: metareview: This paper proposes a contextual Bayesian optimization algorithm with penalization for movement cost, which is motivated by the problem of tuning the altitude of wind turbines to maximize energy output while minimizing the altitude adjustment. That is, a movement cost is incurred which is larger if the difference between the actions selected in the current and the previous steps is larger. The proposed algorithm is based on the problem of metrical task systems, and combines lower confidence bound from Bayesian optimization with online mirror descent. The regret of the proposed algorithm is analyzed, and the algorithm achieves competitive empirical performances in a real-world wind energy systems experiment.

All reviewers agree that this is an important and novel problem for Contextual Bayesian Optimization.  The experiment were a nice demonstration of the practicality of the approach.  All four reviewers were on the positive side for acceptance.

confidence: Certain
Decision: Accept