Bayesian Analysis of Combinatorial Gaussian Process Bandits

We thank **reviewer 8zLg** for their review and feedback. We are pleased to hear that the reviewer finds value in our experimental setup and greatly appreciates our writing. Below, we address the points raised by the reviewer. **W1: 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].** All our experiments are performed in a controlled setting by sampling the expected reward from a Gaussian process and the noise from i.i.d. zero-mean Gaussians. The mean, kernel and noise parameters are based on realistic values given by the deterministic energy model in Eq. (8). The graph and its corresponding edge features are also based on the real-world road networks of Luxembourg and Monaco. Note that we could have set the parameters and the graph arbitrarily. By using realistic values, the obtained regrets can be interpreted in terms of the energy saved and we do not lose much, if any, control over the data creation. Additionally, this still corresponds to a synthetic data generation process. In the experiments, we study interesting properties of the algorithms, such as the impact of the BayesUCB and UCB parameter values. We find that GP-BayesUCB has parameters that can be tuned to lower the regret whilst maintaining theoretical guarantees, unlike GP-UCB. Additionally, we vary the lengthscale parameter in the GP prior and demonstrate the difference between our method and previous work is most pronounced with longer lengthscales since it simplifies the problem. See our answer to reviewer 2DSA for further discussions on the connection between theory and empirical results. **W2: 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.** For any bandit experiments on a limited budget, there is a tradeoff between the number of experiments, samples and horizon length. Note that even with $T=500$, the best-performing method (GP-TS) usually reaches saturation. The main purpose of introducing GP-methods to the energy-efficient navigation problem was to improve the sample efficiency compared to Åkerblom et al. (2023) by taking advantage of correlations. Therefore, we chose to provide more experiments rather than longer experiments to demonstrate that the superior sample efficiency holds across different routes, networks, UCB parameter values and lengthscales. **W3: I did not notice any discussion in the paper about possible extensions and future directions and further impacts of their research.** See **Q2**. **Q1: 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?** In general, the type of directed graph should not affect the applicability of the overall framework and its theoretical analysis. However, given some domain knowledge on the type of graph one may tailor the steps in Algorithm 1 to improve the performance. For example, given an acyclic graph one does not need to guarantee that the weights are positive and one could therefore replace Dijkstra's algorithm with the Bellman-Ford algorithm for small enough graphs. **Q2: 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?** An important future direction of this research is to study the multi-agent setting where the vehicle can learn from observations given by a fleet of vehicles. The methods we introduce should be able to learn from fewer vehicles since by taking correlations into account, we do not need to explore the entire network. Our motivation for considering the online energy-efficient navigation problem is to extend the effective range of electric vehicles by identifying efficient routes quickly. We hope that our work can lead to reduced range anxiety among consumers and speed up the transition to a sustainable transportation system. We will try to add an additional section to the supplementary material before the discussion phase ends.

We thank **reviewer WnA6** for their review and examination of our work. The reviewer is not convinced that we properly consider the volatile case however we assert that **we do consider the volatile case** and we hope the reviewer will engage in further discussions so that any confusion can be clarified. **W1: 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?** The volatile case is considered for all the proofs in the paper. Note that the best arm, $\mathbf{a}_t^*$, is defined as the best arm among the available arms (see line 140) and we use the subscript $t$ to indicate that it varies over time. For clarification, could you point to a specific equation, lemma or theorem where the volatile case is not considered? **W2: 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.** The Bayesian regret cannot simply be computed by taking the expectation over the high-probability bounds given by Srinivas et al. (2012), Russo \& Roy (2014), and Takeno et al. (2023). In fact, neither Russo \& Roy nor Takeno et al. provide high probability bounds, they both provide Bayesian regret bounds. As we state in the introduction, our contribution is to extend existing Bayesian regret bounds for GP-bandits to new and practically important settings: the infinite, volatile, and combinatorial settings. Additionally, we introduce the first regret bound for GP-BayesUCB (which was introduced by Nuara et al., 2018). Note that previous results only held for finite volatile (Russo \& Roy, 2014) or infinite non-volatile settings (Srinivas et al., 2012, Takeno et al., 2023, 2024, Kandasamy et al., 2018). The closest similar work to ours (Nika et al., 2022) provide frequentist bounds for GP-UCB in the same setting but we establish Bayesian regret bounds in a unified manner for GP-UCB, GP-TS and GP-BUCB. For the finite case, we adapt the results of Chang et al. (2011) to bound the inverse error function $\text{erf}^{-1}(u)$ (Lemma 3.1) and obtain regret bounds for GP-BUCB with more flexible parameters compared to GP-UCB. We provide a demonstration in our experiments of how the choice of parameters can lower the regret but maintain theoretical guarantees. Our technical contribution for the infinite setting is to provide an analysis of the discretization error $U_t([\mathbf{a}]_{\mathcal{D}_t}) - U_t(\mathbf{a})$ (Lemma 3.5) which is the key step to allow volatile arms. **W3: 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?** Taking the limits $[1,T]$ instead of $[1,\infty]$ does not yield a meaningfully tighter bound. On page 16, line 846, we would obtain an additional term ($\propto t^{1-\xi/\omega}$) that would go to zero as $T \rightarrow{} \infty$ . Note also that in the equivalent lemma for GP-UCB and GP-TS (Lemma A.2) we also take the limit $T \rightarrow{} \infty$ to obtain a constant bound, see lines 783-786. By doing the same in Lemma 3.1, we are consistent with the other algorithms and previous work.

We thank **reviewer 2DSA** for their review and feedback. We are happy to hear that the reviewer appreciates our theoretical contributions and its practical application. Below, we address the points raised by the reviewer. **W1 Lack of Discussion on Theoretical Challenges** See **Q3**. **W2 Reproducibility Concerns: No code is provided for the experiments. This absence raises concerns about the reproducibility of the empirical results.** The code will be made publicly available for the camera-ready version. Our experiments relies only upon openly accessible data and we have provided references on how to access it. In addition, the data processing and algorithms used are detailed in the main text and supplementary material. **Q1 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?** Yes, the empirical results can be used to verify or illustrate key observations from the theoretical analysis. First, as the theory suggests and the results in Figure 1 validate, the algorithms obtain sublinear regret w.r.t $T$. Second, our theoretical analysis shows that the GP-BayesUCB provides more flexible parameters than GP-UCB. It is generally accepted that GP-UCB algorithms tends to overexplore due to too large theoretical confidence intervals. In the right column of Figure 3, we show that the confidence parameter $\beta_t$ of GP-BayesUCB is lower than that of GP-UCB, and additionally we can tune it to be even lower. In practice, (left and middle column of Figure 3), we also show experimentally that GP-BayesUCB obtains lower regret than GP-UCB. Third, as discussed by Russo \& Roy (2014), the performance of UCB algorithms depend on designing tight confidence bounds whereas the regret of Thompson sampling algorithms (using Russo \& Roy's framework) can be bounded by any set of confidence bounds. For complex bandit settings, designing tight confidence bounds can be significantly harder. Whilst our theoretical results suggest that GP-TS should perform similar to GP-UCB and GP-BayesUCB, our experiments demonstrate that GP-TS obtains significantly lower regret which can likely be attributed to the point raised by Russo \& Roy. This finding is also consistent with other works for GP and non-GP bandits. **Q2 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.** Thank you for the suggestion, we have updated Table 1 to include the regret bounds of previous work. **Q3 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.** In section 3.1 and 3.2, note that we do discuss the theoretical challenges encountered although we frame it in terms of our technical contributions. Prior to introducing Lemma 3.2 respectively 3.5, we discuss the limits of the analysis from previous work and what we do to overcome it. For example in section 3.1, we describe how $\mathbb{E}[U_t(\mathbf{a}\_{t})-f(\mathbf{a}\_{t})]$ must be bound differently compared to the standard case of GP-UCB in Russo \& Roy (2014) due to the inverse error function $\text{erf}^{-1}(u)$ used by GP-BayesUCB or, in section 3.2, we point out that the volatile setting invalidates a key step in the proof of Takeno et al. (2023) and that we overcome that by analyzing the discretization error of $U_t([\mathbf{a}]_{\mathcal{D}_t}) - U_t(\mathbf{a})$.

We thank **reviewer mCBV** for their review and feedback. We are pleased to hear that the reviewer finds our theoretical regret bounds useful. Below, we address the points raised by the reviewer. **W1: 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?** $\mathcal{A}$ can be either a finite or infinite set, in section 3.1 we consider $|\mathcal{A}| < \infty$ and in section 3.2 we consider $|\mathcal{A}| = \infty$. (We can update the text for sec. 3.2 to state $|\mathcal{A}| = \infty$. Currently we only say it in words.) Yes, we use $2^{\mathcal{A}}$ to denote the power set. This is fairly standard notation but a clarifying sentence will be added. The combinatorial structure in our problem complicates the situation when $\mathcal{A}$ is infinite and it is worth clarifying further. The agent must select a combination of base arms but may not pick the same arm twice. To prevent issues with limit points, we therefore restrict the available base arms at round $t$ , $\mathcal{A}_t$ , to be finite. Even though $\mathcal{A}_t$ is finite, whether $\mathcal{A}$ is finite or infinite has large implications for contextual bandits. In the navigation problem, time-varying features (such as congestion, time of day or outside temperature) can only be modelled as continuous features if $\mathcal{A} = \infty$ but would be limited to discretized features if $\mathcal{A} < \infty$. **W2: 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.**: We have added additional comparisons regarding the dependency on $K$ to section 3.1. Regarding comparisons w.r.t. $K$, we do compare against the closest work by Nika et al. (2022) and obtain the same dependency. For a linear kernel, one could also compare against Wen et al. (2015) where a linear dependency on $K$ is obtained for CombLinTS and CombLinUCB although their setting may differ slightly from ours. Similar to us, their regret bound depends only on $K$ and not on the number of base arms. Therefore, we do not believe the infinite case should change anything about the dependency on $K$. For combinatorial semi-bandits with linear reward functions (but independent amrs), Merlis \& Mannor (2020) obtain a $\Omega(\sqrt{K} \log K)$ lower bound which would suggest a gap of $\sqrt{K} \log K$ for the linear kernel. Zheng Wen, Branislav Kveton, Azin Ashkan. Efficient Learning in Large-Scale Combinatorial Semi-Bandits. Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1113-1122, 2015. Nadav Merlis and Shie Mannor. Tight Lower Bounds for Combinatorial Multi-Armed Bandits. In Proceedings of Thirty Third Conference on Learning Theory, pp. 2830–2857. PMLR, 2020 **W3: 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?** We have added additional discussion about lower bounds w.r.t. $T$ to section 3.1. To our knowledge, there are no known lower bounds for Bayesian regret of GP-bandit algorithms in general. However, Scarlett et al. (2017) and Cai et al. (2021) discuss lower bounds for non-Bayesian regret. For the SE-kernel, they obtain $R(T) = \Omega(\sqrt{T (\log T)^{d/2}})$ which would indicate that our bounds are tight up to logarithmic factors of $T$. Note that we do compare our dependency on $T$ against the non-combinatorial and non-volatile results obtained by Takeno et al. (2023; 2024) in section 3.1 and 3.2. For the finite case, Takeno et al. obtains a $\mathcal{O}(\sqrt{T \gamma_T})$ bound which is $\mathcal{O}{\sqrt{\log T}}$ tighter than our bound. But for the infinite case our bounds match Takeno et al. For the infinite case, constructing a finite discretization is a standard technique used to prove the regret bounds in the literature but is believed to be the cause of the extra $\mathcal{O}(\sqrt{\log T})$ factor, see discussion in Takeno et al. (2023). We have also updated Table 1 to contain the regret bounds of previous work. Xu Cai, Jonathan Scarlett. On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization. Proceedings of the 38th International Conference on Machine Learning, PMLR 139:1216-1226, 2021. Jonathan Scarlett. Tight Regret Bounds for Bayesian Optimization in One Dimension. Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4500-4508, 2018.

**W4: 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.** Whilst the combinatorial semi-bandit problem can be seen as simply a special case of a reinforcement learning (RL) problem, RL formulations introduce unnecessary complexities (e.g. learning state transitions, transition-dependent rewards) that worsen the sample efficiency significantly. As an example, the actions selected by the agent will affect the traffic environment but those changes are unlikely to affect the agent itself since any edge is traversed at most once during an episode. For the problem of route and charging station selection, semi-bandit algorithms (Åkerblom et al., 2023a) have been demonstrated to scale up to graphs with orders of magnitude more nodes and edges compared to deep RL algorithms (Lee et al., 2020; Qian et al., 2019). Åkerblom et al. (2023b) introduce a semi-bandit framework that combines informed priors with efficient exploration at a low computational cost. Compared to Åkerblom et al. (2023), our formulation further improves the exploration and sample efficiency by utilizing the correlations (given by the GP) between edge weights. Doing the same for a RL problem would not be as straightforward and would lack the proven strong performance guarantees given by bandit methods. Lee et al. "Deep reinforcement learning based optimal route and charging station selection." Energies 13.23 (2020): 6255. Qian et al. "Deep reinforcement learning for EV charging navigation by coordinating smart grid and intelligent transportation system." IEEE transactions on smart grid 11.2 (2019): 1714-1723. Åkerblom et al. "A Combinatorial Semi-Bandit Approach to Charging Station Selection for Electric Vehicles." Transactions on Machine Learning Research (2023a). Åkerblom et al. "Online learning of energy consumption for navigation of electric vehicles". Artificial Intelligence, 317:103879, (2023b) **Q1: 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.** For the squared-exponential kernel and ignoring logarithmic terms we get $\text{BR}(T) = \mathcal{O}(K \sqrt{T})$. Note that $\gamma_T$ and $\beta_T$ are standard terms that appear in most regret bounds in the GP-bandit literature, see Srinivas et al. (2012). Additionally, in the paragraphs below Thm 3.2 and 3.6, we highlight the order of complexity that we obtain and compare the expression we get against previous works. By suggestion from reviewer 2DSA, we have updated Table 1 to include our regret bounds and those from previous works. The included regret bounds are simplified compared to those in Thms 3.2 and 3.6.