Bayesian Analysis of Combinatorial Gaussian Process Bandits

Authors: Jack Sandberg, Niklas Åkerblom, Morteza Haghir Chehreghani
Primary area: reinforcement learning
Keywords: Multi-armed bandits, Combinatorial bandits, Contextual bandits, Gaussian processes, Energy-efficient navigation

Abstract:
We consider the combinatorial volatile Gaussian process (GP) semi-bandit problem. Each round, an agent is provided a set of available base arms and must select a subset of them to maximize the long-term cumulative reward. We study the Bayesian setting and provide novel Bayesian cumulative regret bounds for three GP-based algorithms: GP-UCB, GP-BayesUCB and GP-TS. Our bounds extend previous results for GP-UCB and GP-TS to the \emph{infinite}, \emph{volatile} and \emph{combinatorial} setting, and to the best of our knowledge, we provide the first regret bound for GP-BayesUCB. Volatile arms encompass other widely considered bandit problems such as contextual bandits.
Furthermore, we employ our framework to address the challenging real-world problem of online energy-efficient navigation, where we demonstrate its effectiveness compared to the alternatives.

Decision: accept (poster)
Reviewer scores: 5, 8, 5, 5

Reviews and discussion:
<thread>
creation date:
1730211542546

thread_type:
official_review

<thread_object>
creator: reviewer_8zlg

<content>
summary:
The paper studies Gaussian process bandits in the contextual volatile semi-bandit setting. The contribution of the paper is mainly theoretical as it provides novel Bayesian regret bounds for previously designed algorithms. In addition, there is an interesting application of their framework in online energy efficient navigation. This experimental application builds on top of the previously designed experiment of the same application in bandit papers.

strengths:
The paper is building on top of other previously published frameworks, however, it is not a straightforward extension of the previous works. 

The experiments (application of their framework) in online energy-efficient navigation problem seem to have added some novelties and value to the paper. 

The paper is written in an excellent way. The explanations for the most important parts of the algorithms are clear. Also the similarities and differences (novelties) of their framework in comparison to the state-of-the-art is clarified properly.

weaknesses:
No synthetic data experiment. Not even in the supplementary material. In my opinion, synthetic data experiments can significantly add to the development of intuitions about the framework. Also since you have much more control over the creation of the data, it can reveal interesting properties of the framework [in comparison with state-of-the-art]. 

Also, I could not find an experiment with the horizon more than 500 rounds. I am curious about the performance of the frameworks as the horizon goes well beyond T=500. I believe that proper comparison of bandit frameworks [most of the times] comes with running the experiments for long horizons. 

I did not notice any discussion in the paper about possible extensions and future directions and further impacts of their research.

questions:
Does the type of directed graph affect the applicability of the framework? For instance, how does the graph [being cyclic or acyclic] affect the performance of the framework? 

I did not notice any discussion in the paper about possible extensions and future directions and further impacts of their research, not even in the supplamentary section. Why? Can you please clarify?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730720346498

thread_type:
official_review

<thread_object>
creator: reviewer_wna6

<content>
summary:
The paper claims to present a novel Bayesian regret bounds for GP-UCB and GP-TS in combinatorial, volatile and infinite arms setting. Further they present the experimental results for a real world application of online energy efficient navigation.

strengths:
The paper provides the bounds for the Bayesian regret for GP-BUCB, GP-UCB and GP-TS.

weaknesses:
1. Though the work claims to present the bounds for volatile case but the proof for the bounds do not seem to consider it. As an example what would happen when the best arm is not present among the observed arms?
2. Not significant contribution, the paper mainly builds on the works of Russo & Roy 2014, Srinivas et al 2012 and Takeno et al 2023, where in to compute the Bayesian regret one only needs to compute the expectation over the high probability regret bounds given by the above works.
3. Lemma 3.1 the results are considered for different regimes of horizons for different cases of the ratio, why not choose the limits as 1 to T for the 3rd case, wouldn't that be a tighter bound?

questions:
See the weakness section
</content>
</thread_object>

</thread>
<thread>
creation date:
1730738642104

thread_type:
official_review

<thread_object>
creator: reviewer_2dsa

<content>
summary:
This paper investigates the combinatorial volatile Gaussian process (GP) semi-bandit problem and provides the first Bayesian regret bounds for the GP-BayesUCB algorithm. In addition to this novel contribution, the authors extend their theoretical analysis to include Bayesian cumulative regret bounds for the GP-UCB and GP-TS algorithms, effectively addressing a notable research gap as highlighted in Table 1. To demonstrate the practical relevance of their framework, the authors apply their methods to a real-world problem: online energy-efficient navigation.

strengths:
1.	Clear and Structured Presentation:
The paper is well-written, with clear explanations and illustrations of the research gaps. The novelty of this work is effectively communicated, making it accessible even to readers who may not be deeply familiar with the field.
2.	Solid Theoretical Contributions:
The authors provide rigorous theoretical analysis and establish new Bayesian regret bounds for multiple algorithms, including GP-BayesUCB, GP-UCB, and GP-TS. The paper addresses a significant gap in the literature by formalizing regret bounds for these settings. Full proofs are provided in the appendices, showcasing the depth of their analysis (though the correctness of these proofs was not verified).
3.	Practical Application:
The real-world application of their framework to online energy-efficient navigation is both relevant and interesting. It demonstrates the practical utility of their theoretical advancements and highlights the potential for real-world impact.

weaknesses:
1.	Lack of Discussion on Theoretical Challenges:
While the paper provides new theoretical results, it does not clearly articulate the specific challenges encountered in deriving these results for GP-BayesUCB, GP-UCB, and GP-TS. A discussion on the theoretical hurdles and how they were addressed would provide valuable insight into the novelty and difficulty of these contributions.
2.	Reproducibility Concerns:
No code is provided for the experiments. This absence raises concerns about the reproducibility of the empirical results.

questions:
1.	Connection Between Theory and Empirical Results:
The online energy-efficient navigation application is a compelling demonstration of the framework’s practical utility. However, it would be helpful to clarify how the empirical results relate to the theoretical findings. Specifically, can the empirical results be used to verify or illustrate key observations from the theoretical analysis? If this connection is not direct, could you design controlled simulated experiments that more explicitly validate the theoretical regret bounds or insights?
2.	Extended Comparison in Table 1:
Including the regret rates alongside the regret bounds in Table 1 would greatly enhance its utility. This addition would allow readers to quickly compare the performance of different algorithms in terms of their theoretical guarantees. An extended table with this information would provide a clearer overview of the contributions and situate the work more firmly within the existing literature.
3.	Discussion of Theoretical Challenges:
As mentioned in the weaknesses, a dedicated section or paragraph discussing the theoretical challenges faced in deriving the regret bounds for GP-BayesUCB, GP-UCB, and GP-TS would add significant value. This discussion could cover aspects such as handling the volatility in combinatorial settings, managing the complexities introduced by semi-bandit feedback, or other technical hurdles specific to these algorithms.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730877242565

thread_type:
official_review

<thread_object>
creator: reviewer_mcbv

<content>
summary:
The authors derive Bayesian regret bounds for various algorithms applied to combinatorial volatile GP semi-bandit problems. Specifically, the authors derive regret bounds for 3 algorithms: GP-UCB, GP-BayesUCB, and GP-Thompson Sampling. In comparison to previous works, this is the first regret bound for GP-Bayes UCB, and in addition, extend the existing regret bounds for GP-UCB and GP-TS to infinite, volatile and combinatorial setting (which is also includes the popular contextual bandit setting).

The authors apply these algorithms to the problem of online energy-efficient navigation to demonstrate the performance of the various algorithms.

strengths:
The main strengths of the paper is the theory. I do believe the GP semi-bandit problems considered in this paper are important, and having regret bounds for the algorithms discussed in this paper is also useful. 

Specifically, it is nice to see sub-linear regret bound for all three algorithms.

Furthermore, I also believe that the general techniques developed here may be useful to derive regret bounds for other bandit settings.

weaknesses:
1. I think the paper lacks some clarity, and the exposition can improve significantly. For example, it requires recalling previous literature to properly understand the set-up in Section 2.1: Is A a finite set? 2^A is the set of a all subsets of A? What happens when A is infinite as in Section 3.2? 
2. Though the dependency on T is sub-linear, I am not sure how to view the dependency on K. Especially in the infinite case. Are there any lower bounds for these settings? It is hard to view how good or bad the bounds are with lack of comparisons.
3. Building on top of 2 above, I am curious to know if this is the best dependency on T you can get. I am used to seeing \sqrt{T} regret bounds for bandit algorithms -- is this not achievable in such settings?
4. I thought that the experimental section was too artificial. If the motivation is to solve the problem in best possible way, there are probably better ways of solving the problem (for example using RL), than naively applying the semi-bandit learning algorithms. If the point is to show the performance of various algorithms, a simple example would suffice. In my opinion, the addition of these experiments does not add any additional value to the paper, and does not change the fact that the papers main (only) contributions are the theoretical bounds.

questions:
Please respond to my above concerns.

In addition, I would request the authors to add theorems / propositions after Theorems 3.2 and 3.6, without any \gamma_t and \beta_t terms. Or more generally, with as few variables as possible.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731920574976

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of changes made based on reviewer feedback

comment:
- Text marked with ${\color{blue}\text{blue}}$ has been added and text marked with ${\color{red}\text{red}}$ will be removed.
- Added comparison of regret to Table 1, as suggested by reviewer 2DSA.
- Added clarifications to section 2.1 regarding the base arms $\mathcal{A}$ and the available base arms $\mathcal{A}_t$ based on feedback from reviewer mCBV.
- Added discussion of lower bound in terms of $K$ and $T$ to section 3.1 based on feedback from reviewer mCBV.
- To make space for the above changes, Figure 4 was removed from the main paper and are instead presented in Figure 5 in the appendix. Note that the results in the now removed Figure 4 was a subset of Figure 5 (previously Figure 6).
</content>
</thread_object>

</thread>


Metareview:
metareview:
This is a borderline paper with one reviewer being very positive and three reviewers somewhat critical. After having had a read through the reviews and discussions I believe that the criticisms are mostly about minor issues like the presentation of results. The paper presents useful results around Gaussian process semi-bandit problems and applies these techniques to a real-world problem. I believe that these contributions are valuable and worth being published.