Gaussian Process Bandits for Top-k Recommendations

Dear Reviewer N1XB,

We are thankful for your continued positive outlook on this work and encouraged to find recognition of our contributions. Thanks for identifying the typos; we will fix them. Next, we respond to your questions and weaknesses below.

clarify the technical contribution (novelty) compared to Krause & Ong (2011).

We utilize Theorem 1 from Krause & Ong (2011) (presented as Proposition 1), which relates the regret bound to the maximum mutual information, generalizing the contextual GP-UCB bandits from Srinivas et al. (2010). Building on Proposition 1, we focus on bounding the maximum mutual information by leveraging Weinstein–Aronszajn identity and the feature representation of top-k rankings kernels introduced in Section 3 (as given in Proposition 2). This result in Proposition 2 is not and yields significantly tighter regret bounds, as shown in Table 3, following your previous review suggestion. For further details, please see Section B.4.

The approach does not seem practical, and the empirical evaluation is done with a small number of items (n<=50) and a short horizon (T<500).

The empirical assessment was designed to demonstrate the effectiveness of our approach in terms of regret minimization, focusing on a large arm space setting (e.g., 10+ billion arms for n=50 and k=3). The chosen parameters of n and T were intended to provide a conclusive comparison of the regret minimization effectiveness against other baseline algorithms rather than to showcase scalability to "practical" real-world scales.

Regarding the application in practical scenarios, we recognize that real-world systems often deal with billions of items, far exceeding the 50 items considered in our study. However, practical recommendation systems typically employ a multi-staged architecture involving rankers and re-rankers that progressively filter and narrow down the item pool from billions to often fewer than 50 items (see [1] and [2]). Bandit algorithms, or Bayesian optimization techniques, are usually applied at the final stage of these systems, suggesting that our approach could be more applicable to practical settings than it might seem.

Our theoretical analysis indicates that the proposed algorithm is expected to yield further improvements for larger horizons, i.e., for $T>500$, the approach shall scale much better. It's important to note that the primary aim of this work is not to deliver a ready-to-deploy industrial-scale recommendation bandit algorithm but rather to advance research in this area under a more generalized setting with fewer assumptions. Nevertheless, we are open to refining our approach based on your feedback to better align with practical demands and real-world applicability.

• [1]. LinkedIn blog on building large-scale system https://www.linkedin.com/blog/engineering/recommendations/building-a-large-scale-recommendation-system-people-you-may-know
• [2]. IJCAI tutorial on Bayesian Optimization for Balancing Metrics in Recommender Systems https://ijcai20.org/t03/

The acquisition function is not applied to all possible top-k rankings, and the regret analysis does not account for the approximation

In principle, the local search can explore all possible top-k rankings. Still, we acknowledge that it may not always yield a global optimizer. Addressing this approximation challenge is notably complex. Most literature, including the foundational GP-UCB paper by Srinivas et al. (2010), which received the ICML-2020 Test of Time Award, assumes exact optimization of the acquisition function and proves regret bounds under this assumption. The gap between theory and practical optimization remains underexplored. The only related study we are aware of is by Jungtaek Kim and collaborators in their paper "On Local Optimizers of Acquisition Functions in Bayesian Optimization," which investigates this issue in continuous input spaces and presents challenging results under several assumptions about the behavior of the reward function, http://mlg.postech.ac.kr/~jtkim/papers/ecmlpkdd_2020.pdf.

Figure 3 should show all iterations (i.e., in the batch mode)

Thanks for raising this point. The added PDF provides the regret computation for all iterations. It yields higher variance and slightly more regret while keeping the conclusions and observations consistent, as we anticipated and overserved in our experiments earlier.

We value your detailed feedback and welcome further engagement to strengthen this work.

Dear Reviewer DrUM,

We appreciate your positive feedback on multiple aspects, including writing, results, theoretical analysis, and novel improvements in computational efficiency and memory requirements. We respond to your questions below.

Are Gaussian processes restrictive for modeling rewards?

The ability of GPs to accurately model a specific reward function depends on the expressivity of the RKHS associated with the utilized kernel. Informally, as long as there exists a vector 𝑤, s.t, the norm $||𝑤^T𝜙(𝜋)−𝑓||$ is small, where 𝑓 is the true reward function and \phi(\pi) is the feature space, the proposed algorithm should be effective. This statement can be extended to contextual setup as well. It’s worth noting that Assumption 2 outlines the same principle, similar to prior works such as Krause & Ong (2011). Following your suggestion, we assessed the accuracy of the RKHS of the proposed kernel in approximating reward signals through linear regression in the feature space. We trained on 10,000 arm configurations and tested on another 10,000, repeating this six times to measure MSE performance for the nDCG reward as detailed in the paper. The MSE for the NDCG was 0.816 +/- 0.017 for WK, 0.157 +/- 0.009 for CK, and 0.069 +/- 0.010 for WCK.

Could you provide a Detailed discussion on the choice of the Kendall kernel? Why did you choose it for the Gaussian process? What are its advantages over other kernels?

Section 2.1 discusses the choice of the Kendall kernel, emphasizing its suitability for Gaussian processes due to being positive definite, right-invariant, and appropriate for rankings. It stands out as one of the few kernels that meet these requirements, alongside the Mellow kernel, built on top of the Kendall kernel. We opted for the Kendall kernel for its simplicity and potential ease of adaptation to top-k rankings. Considering Mellow Kernels would be an exciting avenue for future work. Section 2.2 elaborates on the appropriateness of the Kendal kernel, with examples provided in Table 2.

Compared to existing works that use full-bandit feedback, such as Rejwan and Mansour (2020)? Rejwan and Mansour (2020) present a study on full-bandit feedback for combinatorial bandits. They focus on selecting a subset of top-k items without concern for their arrangement, which is a different problem setting than what this work considers.

We appreciate your valuable feedback and look forward to learning from it to enhance this work.

Dear Reviewer 9Xg2,

We appreciate your positive feedback on the readability and clarity of the proofs. We respond to your comments below. Thanks for pointing out typos and flipped values of \lambda parameter, i.e., when we wrote \lambda = 0.25, we meant to write \lambda = 0.75.

new algorithm to be their primary contribution

We agree that our primary contribution can be viewed as an efficient implementation of the GP-UCB for the ranking kernels studied—this is a significant and essential part of our work. At the same time, although we do not alter the schematic of the GP-UCB, our contributions extend beyond the efficient implementation of the kernels, novel kernel for top-k rankings, exploring the full-bandit feedback settings, empirically showing optimal arm selection for the contextual acquisition function over the top-k domain, and providing its regret analysis.

more clear about the confidence ranges

Thank you for your critical observation. The confidence level for Figure 2 is 95%. In Figure 5, confidence intervals were omitted due to poor visibility, while Figure 3 exhibits confidence behavior similar to that of Figure 2. We have included these figures in the attached pdf for your reference.

on the possibility of efficient local search exploiting the kernel structure

Thank you for your insightful question. The number of local searches significantly influences our algorithm, which grows linearly with the number of items in our implementation due to the neighbors considered by the local search. There might be a strategy to improve this further to reduce the number of neighbors. However, it does not seem trivial to create smaller and more relevant neighborhoods for the local search by leveraging the relationship between the UCB acquisition function and the feature representation of the arm, i.e., $\phi(\pi)^T{w}_t + \beta \sqrt{\phi(\pi)^T M_t \phi(\pi)}$, where ${w}_t$ and $M_t$ are fixed matrices at the t-th step.

We are grateful for the valuable feedback on our work. We welcome further engagement and look forward to learning from your perspective.

Dear Reviewer tLdn,

We appreciate your positive feedback on the readability and design of our experiments. We address your comments in the order they were presented.

On the cascade model, utilize click information.

We acknowledge that exploiting click information can be valuable. Still, it can also be misleading when the cascade model or item presentation order is ambiguous, e.g., in the scenarios given in the paper. Our approach addresses scenarios where the cascade model may not be appropriate. We certainly agree that click information is valuable, and it’s worth exploring a middle ground between full-bandit feedback and more restricted models like the cascade model.

On covariance functions and its shortcomings.

Thank you for highlighting the limitations of the proposed product kernel, which requires both context and top-k rankings to be similar to utilize data from previous rounds. This limitation can be mitigated using other kernels, such as the additive kernel (similar to Krause et al. [14]). The contributions to accelerate the bandit algorithm remain applicable even with the additive kernel. We will clarify this further in the final draft. Exploring even broader classes of kernels for ranking/context spaces that admit efficient algorithms could be an exciting direction for future work.

Finding recommendations with inner product search

We agree that the proposed approach does not allow for straightforward inner product search and requires an optimization algorithm due to the more generic setting, i.e., non-composability of rewards over items. This is also true for the GP bandit algorithm given by Wang et al. [32], despite having a much more relaxed scenario of the semi-bandit feedback.

Thank you for the insightful review!