Gaussian Process Bandits for Top-k Recommendations

Authors: mohit  yadav
daniel  sheldon
cameron  musco
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:05:45

Abstract: Algorithms that utilize bandit feedback to optimize top-k recommendations are vital for online marketplaces, search engines, and content platforms.  However, the combinatorial nature of this problem poses a significant challenge,  as the possible number of ordered top-k recommendations from $n$ items grows exponentially with $k$. As a result, previous work often relies on restrictive assumptions about the reward or bandit feedback models, such as assuming that the feedback discloses rewards for each recommended item rather than a single scalar feedback for the entire set of top-k recommendations. We introduce a novel contextual bandit algorithm for top-k recommendations, leveraging a Gaussian process with a Kendall kernel to model the reward function.
Our algorithm requires only scalar feedback from 
the top-k recommendations and does not impose restrictive assumptions on the reward structure. 
Theoretical analysis confirms that the proposed algorithm achieves sub-linear regret in relation to the number of rounds and arms. Additionally, empirical results using a bandit simulator demonstrate that the proposed algorithm outperforms other baselines across various scenarios.

Main paper: 
 introduction: 
 The top-k recommendation problem involves providing a ranked list of k items, such as news articles or products, from a pool of n items [34, 13] . Online algorithms must adapt to dynamic user preferences, making bandit algorithms suitable due to their use of limited feedback [1] . Developing bandit algorithms is challenging due to limited feedback and the need for computational efficiency in real-time recommendation environments. Recent research on user interfaces for recommendations highlights that the overall layout of the recommendation page is crucial for user appeal, as modern UI designs have evolved from simple dropdown lists to complex, visually engaging layouts [17, 13, 18] . Consequently, bandit algorithms must jointly select and display all top-k items, rather than simply choosing the most relevant k items and ordering them by decreasing user relevance [31] .The joint consideration of top-k items makes the number of arms (possible actions for the bandit algorithm) combinatorially large, i.e., Θ(n k ). Previous research on bandit algorithms often imposes strict assumptions on feedback models [30, 21] . For instance, semi-bandit feedback provides a scalar reward for each of the top k items, thus decomposing the combinatorial feedback into item-level feedback. However, this type of feedback is frequently unavailable [32] . Another common feedback model is cascade browsing [16] , which assumes that users examine items in a predetermined order and cease browsing once a desirable item is found, offering item-specific scalar feedback but failing to capture potential non-linear interactions among items [26] . Figure 1 illustrates the limitations of the cascade model in capturing user interactions within modern top-k recommendation interfaces.These limitations motivate us to adopt a more general full-bandit feedback setting, where only a single scalar value is provided for the entire top-k set of recommendations [24] .Figure 1 : A snapshot from Etsy showcases Father's Day shopping recommendations. The lack of an obvious linear search order challenges the assumptions of the cascade model. Additionally, the proximity and arrangement of items are likely to influence clicks, indicating complex interaction patterns and supporting the need for full-bandit feedback without assumptions about user interactions with recommended items.Table 1 : Compute and memory analysis for the proposed GP-TopK bandit algorithm. Rows represent different costs: total compute and memory of the GP-TopK algorithm for T rounds, time for matrix-vector multiplication (mvm) with the kernel matrix KX t for t th round, and time to update KX t . Columns represent different approaches: the kernel approach, which uses full kernel matrices, and our novel feature approach, which performs the same operations through feature expansions and scales more efficiently with respect to T. The symbols c, k, and T denote the embedding size for contexts, the number of items, and the number of rounds, respectively.kernel approach feature approach compute O(T 3 )O(c • k 2 • T 2 ) memory O(T 2 ) O(c • k 2 • T) mvm(K Xt ) O(t 2 ) O(c • k 2 • t) compute K Xt O((c + k 2 ) • t) O(c • k 2 )Beyond feedback assumptions, the reward structure in bandit algorithms must be decomposable into scalar values for individual items to prevent a combinatorial explosion of arms-something that is not always feasible. For example, modern e-commerce platforms value and track metrics such as diversity and fairness [1] , which cannot be captured by focusing solely on individual items [15] . This necessitates algorithms for full-bandit feedback settings that operate without specific assumptions about the objectives or reward structures [24] .This work introduces a bandit algorithm that uses Gaussian processes (GPs) to model rewards under full-bandit feedback (i.e., a single scalar value). GPs are selected for their flexibility in accommodating feedback across discrete, continuous, and mixed domains, such as continuous contexts and discrete rankings [33] . Additionally, unlike parametric models that require optimization incorporating accumulated feedback from previous rounds, GP updates are computationally efficient, involving only data updates [24] . Although GP inference may face computational limits, we will develop efficient inference methods tailored to our proposed algorithm. A further challenge in designing GP-based bandit algorithms for top-k recommendations is constructing expressive positivedefinite kernels that capture similarities between top-k recommendations [9] . This work mitigates these computational and modeling challenges, as illustrated in the following sections.Broadly speaking, GPs have been previously explored for bandit algorithms [27, 19] . Krause et al. [14] employed GPs for contextual bandits in continuous domains; we focus on the discrete domain of top-k recommendations. Vanchinathan et al. [28] used GPs with a position-based feedback model, and Wang et al. [31] used GPs with semi-bandit feedback for recommending top-k items. In contrast, our work does not rely on a specific reward model or feedback assumption, and develops an an efficient GP-based bandit algorithm for top-k recommendations.Our primary contribution is the GP-TopK algorithm, a contextual bandit algorithm for recommending top-k items. This algorithm operates in a full-bandit feedback setting without relying on assumptions on reward, making it broadly applicable compared to prior works. We leverage GPs with variants of the Kendall kernel [12] to model the reward function and optimize the upper confidence bound (UCB) [27] acquisition function for selecting the next arm. Additionally, we introduce a novel weighted convolutional Kendall kernel for top-k recommendations that address pathologies in existing variants of the Kendall kernel when applied to top-k recommendations.Our second key contribution is enhancing the scalability of the GP-TopK algorithm for longer time horizons. Initially, the computational cost for top-k recommendations using the GP-TopK algorithm is O(T 4 ) for T rounds. We first reduce this to O(T 3 ) by leveraging iterative algorithms from numerical linear algebra [25] . Next, we derive sparse feature representations for the novel weighted convolutional Kendall kernel, further reducing the compute requirements from O(T 4 ) to O(T 2 ) and memory requirements from O(T 2 ) to O(T ). Table 1 summarizes these improvements in time and memory requirement, including their dependence on other parameters.We provide a theoretical analysis showing that GP-TopK's regret is sub-linear in T , benefiting from the feature representations of the Kendall kernels introduced in this work. Specifically, we establish an upper bound on regret that is nearly quadratic in n, significantly improving over the naive Θ(n k ) bound for top-k recommendations without using feature representations [27] . Finally, we empirically validate GP-TopK's regret on real-world datasets, demonstrating improvement over baseline methods.The remainder of this paper is organized as follows: Section 2 introduces Kendall kernels for full and top-k rankings, including the novel weighted convolutional Kendall kernel. Section 3 presents faster matrix-vector multiplication algorithms for Kendall kernels, enhancing the efficiency of the proposed bandit algorithm, which is further detailed along with the regret analysis in Section 4. Finally, Sections 5 and 6 present empirical results and concluding discussion, respectively. 
kendall kernels for full and top-k rankings: 
 This section introduces Kendall kernels and their extensions for top-k recommendations, forming the foundation of our approach. We first establish key notations and them present Sections 2.1 and 2.2, which introduce Kendall kernels for full rankings and top-k rankings, respectively. To capture ranking positions, the vector p σ ∈ R n corresponds to a full ranking σ with entry p σ i gives the rank of item i. For top-k rankings, p π ∈ R n is similarly constructed by arbitrarily assigning distinct ranks to items not in the top k. For relative ranks, indicator functions p σ i<j and p σ i>j denote whether item i is ranked before or after item j, respectively in σ. Also, p π i<j and p π i>j are similar indicator functions defined for top-k rankings.Notations: Let [n] = 1,Jiao et al. [9] showed that the Kendall tau rank correlation coefficient [12] is a positive definite (p.d.) kernel for full rankings, which we refer to as the standard Kendall (SK) kernel. The weighted Kendall (WK) kernel generalizes the SK kernel by differentially weighting item pairs [10] . Specifically, the SK and WK kernels for full rankings σ 1 , σ 2 are defined as:EQUATIONEQUATIONwhere η i,j is 1 if the pair (i, j) is concordant (ordered the same in both rankings) and -1 otherwise; concretely,η i,j (σ 1 , σ 2 ) := p σ1 i<j • p σ2 i<j + p σ1 i>j • p σ2 i>j -p σ1 i<j • p σ2 i>j -p σ1 i>j • p σ2 i<j ; and w((p σ1 i , p σ1 j ), (p σ2 i , p σ2 j )) is the value of a positive definite weighting kernel w(•, •) : [n] 2 ×[n]2 → R that operates on pairs of ranks. The w i,j adds flexibility and can assign varying importance to ranks, similar to the discounted cumulative gain (DCG) metric [7] . Note that both SK and WK kernels are p.d. and right-invariant with respect to Π n [10] . In other words, they compute similarity based only on the relative ranks of pairs, not on the labels of items, as clearly evident from Equations 1 and 2.Weighted Kendall and Convolutional Kendall (CK) kernels. To adapt the WK kernel from full rankings to top-k rankings, Jiao et al. [10] set the weighting function w(i, j, σ 1 , σ 2 ) to zero if either item is not in the top-k of either ranking. While this approach yields a p.d. kernel, it disregards items outside the intersection of top-k rankings. In contrast, the convolutional operation provides an alternative for adapting the standard Kendall kernel to top-k rankings.Let B π denote the set of full rankings consistent with the top-k ranking π (i.e., for every item i in π, ∀σ ∈ B π , p π i = p σ i ). The convolutional Kendall kernel can be defined as follows:EQUATIONwhere k sk is the standard Kendall kernel. Since the CK kernel is a convolution of another p.d. kernel, it is also a p.d. kernel [5] . Unlike the WK kernel for top-k rankings, the CK kernel accounts for items not in both top-k rankings. However, computing the CK kernel is expensive, requiring exponentially many evaluations of the kernel k sk in the double summation. Therefore, Jiao et al. [9] developed an efficient algorithm to bypass this double summation, reducing compute to O(k log k) time.Proposed Weighted Convolutional Kendall (WCK) Kernel. To combine the strengths of the WK and CK kernels for top-k rankings, we propose the weighted convolutional Kendall kernel for top-k rankings π 1 and π 2 ∈ Π k :EQUATIONwhere k wk represents the weighted Kendall kernel for full rankings σ 1 , σ 2 ∈ Π n .The proposed WCK kernel combines the flexibility of differentially weighting ranks among the top-k items (as in the WK kernel) with the ability to account for items outside the intersection of both top-k rankings (as in the CK kernel). Additionally, as a convolution of a p.d. kernel, it is also a p.d. kernel. However, computing the WCK kernel remains challenging, as it requires exponentially many evaluation of the k wk kernel, as given in the RHS of Equation 4. To address this, we focus on a specific form of rank weights of the k wk kernel, called as product-symmetric rank weights:EQUATIONwhere, w s (i, j) : [n] × [n] → R is a symmetric function, i.e., w s (i, j) = w s (j, i). Notably, the WCK kernel can be computed efficiently for the case of these weights (see Claim 1 below). (i, j) = 1 log(i+1) • 1 log(j+1), inspired by the DCG metric commonly applied in recommendation systems [7] . Notably, the WK kernel ranks two rankings with no overlap (π 0 and π 1 ) as more similar than two rankings with the same items in reversed order (π 0 and π 2 ), indicating a clear pathology. Further, the CK kernel fails to distinguish between reversed pairs at different ranks (k ck (π 0 , π 3 ) = k ck (π 0 , π 4 )), presenting another limitation if known variants of Kendall kernels for top-k rankings. By using product-symmetric ranking weights, the WCK kernel addresses these shortcomings, providing a more nuanced similarity comparison for top-k rankings.Claim 1. The weighted convolutional Kendall kernel (Equation 4) with product-symmetric rank weights (Equation 5) can be computed in O(k 2 ) time.Appendix A provides the proof that leverages the structure of product-symmetric rank weights w ps to establish the existence of a feature representation for the WCK kernel, as formally stated below in Claim 3 below. We then demonstrate that the inner product of these features, and hence the WCK kernel, can be computed in O(k 2 ) time (Algorithm 2 in the appendix). Similar to the result of Jiao et al. [9] for the CK kernel, this approach avoid exponentially many evaluations of k wk on the RHS of Equation ( 4) by enabling a direct computation of the WCK kernel. 
fast matrix-vector multiplication with kendall kernel matrices: 
 In Gaussian processes, inference can be accelerated by using iterative algorithms that take advantage of fast matrix-vector-multiplications (MVMs) with the kernel matrix [3] . This section introduces fast algorithms for kernel MVMs by exploiting the implicit structure of Kendall kernel matrices.Let mvm(K Xt ) denote the runtime required to multiply the t × t kernel matrix K Xt = (k(x i , x j )) xi,xj ∈Xt by any admissible vector. In the naive approach, this runtime is mvm(KX t ) = O(t 2 ). However, if k(x i , x j ) = ϕ a (x i ) T ϕ b (x j ) for any arbitrary x i and x j , where the vectors ϕ a (x i ) and ϕ b (x j ) are sparse and contain only z non-zero entries, then mvm(K Xt ) reduces to O(z • t), which is a significant improvement over O(t 2 ) when z ≪ t. When ϕ a = ϕ b , we refer to ϕ a as the linear feature vector for the kernel k. Before focusing on top-k ranking kernels, we provide a linear feature vector for the WK kernel on full rankings (given earlier in Equation 2).Claim 2. Let ϕ wk (σ) : Π n → R ( n2 ) be a vector indexed by unique item pairs (i, j), defined as:ϕ wk i,j (σ) := 1 n 2 • w s (p σ i , p σ j ) • p σ i<j -p σ i>j ,where w s is the symmetric weighting function in product-symmetric weights. Then, ϕ wk is a linear feature vector for the weighted Kendall kernel with product-symmetric weights w ps .Using Claim 2, the linear feature vector for the WK kernel can be extended to the WK top-k ranking kernel by utilizing the structure of product-symmetric weights, which allows weights to be set to zero for items outside of the top-k rankings, as described in Section 2.2. Precisely, such a feature vector for the top-k ranking kernel is sparse; specifically, the feature vector ϕ wk (π) contains only O(k 2 ) non-zero entries due to the WK kernel's focus on item pairs within the top-k. Consequently, the runtime for mvm(K Xt ) in the WK kernel matrix is reduced to O(k 2 • t).Claim 3. Let ϕ wck (π) : Π k → R ( n 2 ) be a vector indexed by unique item pairs (i, j) given as:ϕ wck i,j (π) := 1 ( n 2 )• w wck i,j (π) • p π i<j -p π i>j , where w wck i,j (π) is determined as follows:w wck i,j (π) =        w s (p π i , p π j ) if p π i ∈ [k] & p π j ∈ [k] w s (p π i , •) else if p π i ∈ [k] & p π j / ∈ [k] , w s (p π j , •) else if p π i / ∈ [k] & p π j ∈ [k] , 0 otherwise,where w s denotes symmetric weights and w s (ℓ, •) = 1 n-k n j=k+1 w s (ℓ, j). Then, the vector ϕ wck is a linear feature vector for the WCK kernel k wck . By uniformly setting w s (•, •) ≡ 1 in the definitions above, ϕ wck i,j (π) specializes to a linear feature vector for the CK kernel.Moving forward, we focus on deriving a sparse feature vector for the WCK kernel, enabling fast MVMs with the WCK kernel, which includes the CK kernel as a special case. Notably, any convolutional kernel inherits linear features from its constituent kernel. Specifically, σ∈Bπ ϕ wk i,j (σ) forms a feature vector for the WCK kernel, which follows from Equation 4 and However, computing this feature vector explicitly is computationally challenging, as it requires summing over all σ ∈ B π , which includes an exponential number of terms, i.e., Θ(n k ).In response to this challenge, Claim 3 shows that the summation can be computed analytically and provides explicit linear feature vectors for the WCK and CK kernels. It also shows that ϕ wck has only O(k 2 + 2nk) nonzero entries among its O(n 2 ) total entries. Consequently, mvm(K Xt ) for the WCK kernel requires O((k 2 + 2nk) • t) operations, which improves from O(t 2 ) to linear in t. However, this introduces a dependence on n, the number of items, which poses a serious limitation and is beneficial only when n ≤ t. In the following theorem, we leverage redundancy in ϕ wck to eliminate this dependence on n, leading to the following main theorem about the mvm(K Xt ).Theorem 1. For the WCK kernel with product-symmetric weights w ps , the computational complexity of multiplying the kernel matrix K Xt with any admissible vector is O(k 2 t), i.e., mvm(K Xt ) = O(k 2 t), where X t is any arbitrary set of t top-k rankings.Appendix A provides the proof in two steps. First, we utilize the values of ϕ wck from Claim 3 and categorize ϕ wck (π 1 ) T ϕ wck (π 2 ) based on item pairs, as summarized in Table 4 . Next, we show that only five combinations yield non-zero values, i.e., ϕ wck (π 1 ) T ϕ wck (π 2 ) = 5 i=1 s i (π 1 , π 2 ). Each term s i (π 1 , π 2 ) is a dot product of vectors ϕ ai (π 1 ) T ϕ bi (π 2 ), which contains at most O(k 2 ) non-zero entries. Thus, for the WCK and CK kernels, mvm(K Xt ) = O(k 2 t), since these vectors across all five terms include only O(k 2 ) non-zero entries. Consequently, Theorem 1 demonstrates that employing these vector representations for top-k rankings leads to faster MVMs, i.e., mvm(K Xt ) = O(k 2 t) ≪ O(t 2 ). 
proposed gp-topk bandit algorithm: 
 In this section, we begin by formally defining the top-k recommendation problem within a bandit framework and introduce a generic contextual bandit algorithm, detailed in Algorithm 1. We then explain how the components of the algorithm are instantiated using the proposed GP approach, followed by an analysis of its computational complexity and cumulative regret.Let T denote the number of rounds. Contexts C are represented in a finite c-dimensional space, i.e., C ⊆ R c . In the t th round, we receive a context c t ∈ C and select a top-k ranking π t ∈ Π k . Subsequently, a noisy reward y t = f (c t , π t ) + ϵ t is observed, where f is the true reward function and ϵ t is round-independent noise. The regret is defined asr t := max π ′ ∈ Π k f (c t , π ′ ) -f (c t , π t ), withcumulative regret R T := T t=1 r t . The accumulated data at the t th round is D t = (c i , π i , y i ) t i=1 . Below, the Algorithm 1 provides provides a generic schematic of the bandit algorithm.Input: Total rounds T , initial reward model M 0 , and acquisition function AF.1:for t = 1, • • • , T do 2:Observe a context c t from the context space C.Select a top-k ranking π t that maximizes AF(M t-1 (c t , π)) for the context c t .Obtain the scalar reward y t .Update the reward model M t using the accumulated feedback D t . 6: end for We aim to design the components of above Algorithm 1 with the objectives of minimizing cumulative regret and ensuring computational efficiency. It requires two key components: (a) a reward model M t that estimates the reward for any context and top-k ranking utilizing the accumulated data D t and (b) an acquisition function AF for selecting π t given the reward model M t and observed context c t .Reward model M and acquisition function AF. The proposed GP-TopK bandit algorithm leverages GP regression to model the reward function over the domain of contexts and top-k rankings. Section B.1 briefs GP regression for the completeness. Essentially, the reward model M maintains a distribution over functions f , i.e., f ∼ N (0, k(•, •)), where k is a product kernel function over both contexts and top-k rankings (C Π k ). Specifically, the kernel function k is defined as follows:EQUATIONwhere k c (c 1 , c 2 ) = c T 1 c 2 is the dot-product kernel and k r is a kernel for top-k rankings. We use variants of the Kendall kernel for k r from Section 2. Updating the reward model M t at the t th round involves adding new data points to our GP regression, which is computationally inexpensive compared to the fine-tuning steps required by parametric models to incorporate the latest feedback.We use the UCB function as the acquisition function, balancing exploration and exploitation by selecting actions that maximize the upper confidence bound of the estimated reward [27] . The UCB acquisition function isAF(M t (c t , π)) := µ f |D ((c t , π))+β 1 2 •σ f |D ((c t , π)), where σ f |D ((c t , π)) = k f |D ((c t , π), (c t , π)) and β controls the trade-off between exploration and exploitation. Here, µ f |D and k f |D are the GP posterior mean and covariance functions, as detailed in Section B.1. At the t th round, the algorithm selects the top-k ranking π ∈ Π k that maximizes AF(M t (c t , π)), which is performed using local search [19] , as detailed further in Appendix B.Computational complexity. The GP-TopK bandit algorithm does not require compute for model updates. In other words, updating M t , i.e., in the Line 5 of the Algorithm 1 requires only updating the list of accumulated feedback data D t . The GP-TopK relies on local search to optimize AF, so the computational demands stem solely from AF evaluations within the local search. As shown in Section B.1, computing the GP variance term for evaluating AF, i.e, σ f |D ((c t , π)) involves solvingK Xt + σ 2 I -1 v for a vector v, where X t = [(c 1 , π 1 ), • • • , (c t , π t )].Naively, this operation requires O(t 3 ) time per round, amounting to total O(T 4 ) over T rounds. Iterative algorithms, however, can expedite the process by leveraging fast MVMs with kernel matrices, as discussed in Section 3. Below, Theorem 2 formalizes the computational demands of the GP-TopK algorithm.Theorem 2. Assuming a fixed number of iterations required by the iterative algorithms, the total computational time for running the GP-TopK bandit algorithm for T rounds of top-k recommendations, using the contextual product kernel (Equation 6), is O(k 2 cℓT 2 ). This applies to WK, CK, and WCK top-k ranking kernels, where ℓ is the number of local search evaluations.The proof of Theorem 2, provided in Appendix B, demonstrates efficiency gains from combining feature representations with iterative algorithms, reducing computational time from O(T 4 ) to O(T 2 ). This is a substantial improvement, as even a single MVM with the matrix K Xt using the full kernel matrix at each round would require O(T 3 ) compute time. Additionally, the theorem shows that the running time of the GP-TopK algorithm does not explicitly depend on the number of items n.R T = T t=1 max π ′ ∈Π k f (c t , π ′ )-f (c t , π t ), where π t is the ranking chosen at round t. Optimizing cumulative regret for top-k recommendations is challenging, as it requires learning the context-arm relationship and matching the best possible mapping. To bound cumulative regret, regularity assumptions are essential, as noted in prior works [27, 14] . We consider the following two assumptions, either of which suffices. Also, X := C Π k for below assumptions.Assumption 1. X is finite, meaning that only finite contexts are considered (|C| < ∞), and the reward function f is sampled from the GP prior with a noise variance of ξ 2 .Assumption 2. X is arbitrary and the reward function f has a bounded RKHS norm for the kernel k, i.e., ∥f ∥ k ≤ B. The reward noises ϵ t form an arbitrary martingale difference sequence (i.e., reward noise does not systematically depend on its past values) and are uniformly bounded by ξ.The following theorem proves the regret bound for the GP-TopK algorithm under Assumption 1 or 2.Theorem 3. If either Assumptions 1 or 2 hold, settingβ t as 2 log |C|•|Π k |•t 2 •π 2 6δand 300γ t ln 3 t δ respectively, the cumulative regret R T of the GP-TopK bandit algorithm for top-k recommendations can, with at least 1 -δ probability, be bounded by Õ(n C 1 T c(log|C| + k + log(T 2 π 2 /6δ))) under Assumption 1, andÕ(n C 1 (2B 2 c + 300n 2 c 2 ln 3 (T /δ))T ) under Assumption 2. Here, C 1 = 8 log(1+ξ -2 ), and Õ excludes logarithmic factors related to n, k, and T .Appendix B.4 provides the proof, leveraging the insight that log det|I + ξ -2 • K X T | for any set X T can be effectively bounded using the finite-dimensional feature vectors introduced in this work.Specifically, Proposition 2 utilizes the feature vectors from Section 2. Building on Proposition 2, Theorem 3 establishes that the cumulative regret of the GP-TopK bandit algorithm grows sublinearly in T with high probability for both assumptions. Furthermore, this result also underscore the importance of using top-k ranking kernels, which improve the asymptotic order in terms of n by factors of n k/2-1 and n k-1 under Assumptions 1 and 2, respectively, compared to Srinivas et al. [27] . This improvement is substantial even for small values of k, such as k = 6, as shown in Table 3 . C1T c log|C| + k + log T 2 π 2 6δ Õ n C1T c log|C| + k + log T 2 π 2 6δAssumption 2This workÕ n k 2 C1T c 2B 2 + 300n k c ln 3 T δ Õ n C1T c 2B 2 + 300n 2 c ln 3 T δ 5 ExperimentsThis section empirically evaluates the proposed GP-TopK bandit algorithms for the top-k recommendations using a simulation based on the MovieLens dataset [4] . The reliance on simulation for evaluating bandit algorithms is prevalent in the literature. It stems from the difficulty of conducting online evaluations in real-world bandit scenarios, mainly when there are combinatorial arms [28] .Next, we provide details of the simulation setup and considered reward settings. Following that, we present results for the empirical regret for small and large numbers of arms below, respectively.Simulation setup and reward settings. The bandit simulation setup follows the framework outlined by Jeunen et al. [8] , utilizing real-world datasets on user-item interactions. Specifically, we train user and item embeddings using a collaborative filtering approach [6] . The user embeddings are accessed by the bandit algorithms as context embeddings, while the item embeddings remain hidden. In the non-contextual setup, the first user from the dataset is chosen as a fixed context throughout the bandit algorithm run, allowing us to use the same reward functions as the contextual bandit algorithm.For setting up the reward functions, we utilize a similarity function s(c, θ) := ς(a • (c T θ) -b) to measure similarity between any user and item embeddings, where a and b are similarity score and shift scalars, respectively. The sigmoid function ς maps similarity scores to a range between 0 and 1, enhancing the interpretability of the reward signal [31] . We set a and b to 6 and 0.3, respectively, to fully utilize the range of the similarity function, as assessed by evaluating its value for many arms.We set up two preliminary reward functions based on the similarity function s. The first is the DCG metric, fdcg (c, π) =k i=1 1 log 2 (i+1) s(c, θ πi ), where c and θ πi represent the context and item embeddings, respectively. The second is the diversity measure, fdiv (π) = 1 k 2 k i=1 k j=1 θ T πj θ πi . These metrics quantify the relevance and diversity of top-k recommendations, respectively.We use these functions in two contextual reward settings. The first setting focuses on normalized- [7] . The second setting combines fndcg and fdiv as fndcgdiv (c, π) = λ • fndcg (c, π) + (1 -λ) • fdiv (π), evaluating the aggregate effect of relevance and diversity. We set λ = 0.75 to emphasize relevance over diversity.DCG (n-DCG), fndcg (c, π) = fdcg(c,π) max π ′ fdcg(c,π ′ )Evaluation for small arm space. This section presents empirical results for the cumulative regret of bandit algorithms with a limited number of arms. Specifically, with n = 20 and k = 3, there are 6, 840 top-k rankings, allowing for an exhaustive search to optimize the acquisition function. All bandit algorithms run in batch mode, updating every five rounds. We consider both reward settings for contextual and non-contextual scenarios, using a subset of five users for the contextual setting.Several baselines are set to assess the benefits of ranking (Kendall) kernels. Section C details the remaining hyper-parameter configurations and details of other baseline bandit algorithms. The Random algorithm randomly recommends any k items. The ϵ-greedy algorithm alternates between recommending a random top-k ranking with a probability of ϵ and choosing the top-k ranking with the highest observed mean reward. In contextual settings, ϵ-greedy differentiates arms for each unique context. Similarly, MAB-UCB conceptualizes each ranking as an independent arm, an equivalent of using a direct delta kernel approach for GPs along with UCB AF. In contextual scenarios, MAB-UCB also treats arms distinctly per context. Each variant of the top-k ranking kernel yields one variation of the proposed GP-TopK algorithm, namely, WK, CK, and WCK. Figure 2 presents empirical values of the cumulative regrets for the above baseline and the proposed GP-TopK algorithms. In all cases, across both reward settings and in both contextual and non-contextual setups, the variants of the proposed GP-TopK algorithm outperform baselines that do not use Kendall kernels, highlighting the significance of top-k ranking kernels for full bandit feedback. Specifically, the CK and WCK kernels significantly outperform the WK kernel regarding the converged values of the regret, with the WCK kernel further improving on the CK kernel variant. In both settings, the WCK approach outperforms other baselines. For more details, see the textual description.Evaluation for large arm space.We evaluate bandit algorithms in a large arm space scenario with n = 50 and k = 3 and k = 5, resulting in 1.1 × 10 5 and 1.1 × 10 10 possible top-k rankings, respectively. Using local search, we focus on the nDCG reward. The remaining configuration is consistent with the small arm space setup. We use 10 restarts and 5 steps in each search direction for the local search, starting with 1000 initial candidates.Figure 3 shows that the regret for the GP-TopK variants remains consistently lower even with a large arm space, despite the use of local search. The WCK approach significantly outperforms the CK, especially for k = 5, as illustrated in the right plot of Figure 3 . Additional empirical results on the effectiveness of local search in a large arm space and other rewards are given in Appendix C. 
discussion: 
 This work develops a contextual bandit algorithm for top-k recommendations using Gaussian processes with Kendall kernels in a full-bandit feedback setting, without restrictive assumptions about feedback or reward models. Gaussian processes provide computationally efficient model updates for accumulated feedback data, although inference can be challenging. We address this by deriving features for Kendall kernels tailored to top-k rankings, resulting in a faster inference algorithm that reduces complexity from O(T 4 ) to O(T 2 ). While demonstrated here for the product kernel between contexts and top-k rankings, these computational improvements extend naturally to other kernel types, such as additive kernels. Additionally, we address limitations of known variants and propose a more expressive Kendall kernel for top-k recommendations. Finally, we provide both theoretical and empirical results demonstrating the improved performance of the proposed GP-TopK algorithm.Future Directions and Limitations. This work opens several research avenues. Efficient matrixvector multiplication with Kendall kernel matrices can enable faster bandit algorithms with various acquisition functions, such as Thompson sampling and expected improvement. Exploring other kernels, like Mallow kernels, for top-k rankings and developing efficient algorithms for them is an intriguing direction, especially since the effectiveness of our algorithm depends on the function space induced by the RKHS of the underlying kernel. Assessing how well these kernels approximate various reward functions for top-k recommendations would provide valuable insights.Exploring other bandit problem settings, such as stochastic item availability or delayed feedback, would enhance the applicability of this work to more complex scenarios. Extending the finitedimensional GP framework to other acquisition functions using local search is another promising direction. One limitation of our regret analysis is that it does not account for approximations in the arm selection step due to local search [20] . This limitation is common in continuous domains, where optimizing acquisition functions often involves non-convex optimization [27] .Impact. This research advances bandit algorithms for top-k item recommendations. By improving recommendation efficiency and accuracy, our algorithms can enhance user experiences across platforms, promoting content relevancy and engagement. However, they may reinforce implicit biases in training data, limiting content diversity and entrenching prejudices. Therefore, monitoring over time is essential when deploying these algorithms in real-world environments.This section includes the proofs that were omitted from Section 2, presented in the following order:• In Section A.1, we present proofs for Claims 2 and 3, which concern the feature representations of Kendall kernels.• In Section A.2, we provide Algorithms 2 and a proof of its correctness for computing the WCK kernel in O(k 2 ) time, thereby proving Claim 1. Additionally, we extend this proof to cover the proof of correctness for Algorithm 3, which can compute the CK kernel in O(k log k), initially introduced by Jiao et al. [9] . The original paper presented the algorithm without a formal proof of correctness, a gap we address and fill in this section.• Section A.3 details the proof for Theorem 1, discussing the matrix-vector multiplications with the Kendall kernel matrix for top-k rankings. This proof builds on the Algorithm 2 given for computing the WCK kernel for top-k rankings.A.1 Feature Representation for Kendall Kernels for Top-k RankingsThis section revisits the claims regarding the feature representations of the weighted Kendall kernel and the weighted convolutional Kendall kernel, subsequently providing the proofs for these claims mentioned earlier.Claim 2. Let ϕ wk (σ) : Π n → R ( n 2 ) be a vector indexed by unique item pairs (i, j), defined as:ϕ wk i,j (σ) := 1 n 2 • w s (p σ i , p σ j ) • p σ i<j -p σ i>j ,where w s is the symmetric weighting function in product-symmetric weights. Then, ϕ wk is a linear feature vector for the weighted Kendall kernel with product-symmetric weights w ps .Proof. Following the definition of linear feature representation, we need to prove that k wk (σ 1 , σ 2 ) = ϕ(σ 1 ) T ϕ(σ 2 ) for the product-symmetric weight kernel as given in Equation 5. Recalling from Equation 2, we have k wk (σ 1 , σ 2 ) as follows:EQUATIONwhere the second line incorporates the use of the product-symmetric weight kernel. Next, our focus shifts to the simplification of η i,j (σ 1 , σ 2 ), which is elaborated as follows:η i,j (σ 1 , σ 2 ) = p σ1 i<j • p σ2 i<j + p σ1 i>j • p σ2 i>j -p σ1 i<j • p σ2 i>j -p σ1 i>j • p σ2 i<j , = p σ1 i<j • (p σ2 i<j -p σ2 i>j ) + p σ1 i>j • (p σ2 i>j -p σ2 i<j ), = (p σ1 i<j -p σ1 i>j ) • (p σ2 i<j -p σ2 i>j ).Combining the above factorization of η i,j with Equation 7, we get:EQUATION) be a vector indexed by unique item pairs (i, j) given as:ϕ wck i,j (π) := 1 ( n 2 )• w wck i,j (π) • p π i<j -p π i>j , where w wck i,j (π) is determined as follows:w wck i,j (π) =        w s (p π i , p π j ) if p π i ∈ [k] & p π j ∈ [k] w s (p π i , •) else if p π i ∈ [k] & p π j / ∈ [k] , w s (p π j , •) else if p π i / ∈ [k] & p π j ∈ [k] , 0 otherwise,where w s denotes symmetric weights and w s (ℓ,•) = 1 n-k n j=k+1w s (ℓ, j). Then, the vector ϕ wck is a linear feature vector for the WCK kernel k wck . By uniformly setting w s (•, •) ≡ 1 in the definitions above, ϕ wck i,j (π) specializes to a linear feature vector for the CK kernel.Proof. The main idea revolves around leveraging the feature representation of the Weighted Kendall kernel for a full ranking and the linearity of the convolution operation. It is already established that k wk (σ 1 , σ 2 ) = ϕ wk (σ 1 ) T ϕ wk (σ 2 ), as demonstrated in Claim 2. Recall that the WCK kernel requires a double summation over pairs of rankings from B π1 and B π2 , which represent the sets of full rankings consistent with their respective top-k rankings, as described in Equation 4. We simplify the WCK kernel as follows:k wck (π 1 , π 2 ) = 1 |B π1 | • 1 |B π2 | • σ1∈Bπ 1 σ2∈Bπ 2 ϕ wk (σ 1 ) T ϕ wk (σ 2 ) =   1 |B π1 | • σ1∈Bπ 1 ϕ wk (σ 1 ) T   •   1 |B π2 | • σ2∈Bπ 2 ϕ wk (σ 2 )   :=ϕ wck (π2) = ϕ wck (π 1 ) T ϕ wck (π 2 ).The simplification above reveals that the feature representation, ϕ wck , for the WCK kernel, is a n 2 dimensional vector and can be indexed by unique pairs of items (i, j), much like the ϕ wk . However, the double summation is over an exponentially large number of pairs of rankings. Moving forward, we shift our focus to the individual entries of this representation involving this summation, elucidating the analytical values within the summation by exploring four unique cases, each dependent on whether these specific items fall within the top-k rankings.In Case 1, we examine the scenario where items i and j are within the top-k ranking π. Here, the focus is on the feature representation of the pair, specifically when both elements are ranked among the top-k positions.Case 1:EQUATIONThe simplification in lines 3rd and 4th follows from the fact that any full ranking σ ∈ B π , consistent with the top-k ranking π, the relative ranks and weights of items i and j remains unchanged, givenp π i ∈ [k] and p π j ∈ [k].Concretely, this implies p σ i<j = p π i<j for all σ ∈ B π and similar with the other term.In Case 2, we analyze when item i is in the top-k ranking while item j is not.Case 2: p π i ∈ [k] and p π j / ∈ [k]. ϕ wck i,j (π) = 1 |B π | • σ∈Bπ 1 n 2 • w s (p σ i , p σ j ) • p σ i<j -p σ i>j = 1 |B π | • 1 n 2 • σ∈Bπ w s (p σ i , p σ j ) • (1 -0) (since p π i ∈ [k] and p π j / ∈ [k]) = 1 |B π | • 1 n 2 • σ∈Bπ w s (p π i , p σ j ).Next, every possible consistent ranking is considered jointly while fixating on a specific rank outside top-k elements, leading to (n -k -1)! different rankings. Given that |B π | = (n -k)!, we can refine the above expression as follows:EQUATIONIn Case 3, we analyze when item i is not in the top-k ranking while item j is. Case 3:p π i / ∈ [k] and p π j ∈ [k]. Similar to case 2, the simplification follows analogously, with the only change being 1 p σ i<j -1 p σ i>j = -1 instead of 1. Thus, by symmetry between i and j, we have the following:ϕ wck i,j (π) = -1 n 2 • w s (•, p π j ) = -1 n 2• w s (p π j , •) (using symmetry of w s ). (10) Lastly, in Case 4, we analyze when items i and j are not in the top-k ranking.Case 4:EQUATION)The result of zero arises from symmetry. Since p σ i and p σ j are not in the top-k ranking, they are treated symmetrically in the summation overall rankings in B π . For any ranking σ, suppose p σ i = l and p σ j = m, there exists a corresponding ranking σ ′ such that only the items i and j are swapped. Therefore, jointly, these two rankings yield w s (l, m) and -w s (l, m). Since w s is symmetric, the overall contribution from each pair of such rankings is zero. Hence, the entire summation nets to zero.Thus, with the explanation provided for each case and combining results from Equations 8, 9, 10 and 11, it's trivial to validate the Claim 3, i.e., ϕ wck i,j (π) = 1 ( n 2 )• w wck i,j (π) • p π i<j -p π i>j for all unique pair of items. From Case 4, we have O((n -k) 2 ) entries leaving at max only O(k 2 + 2nk) non-zero entries.In this section, we provide and delve into the proofs of Algorithms 2 and 3 for the weighted convolutional Kendall kernel and the convolutional Kendall kernel, as previously discussed in Section 2. Section A.2.1 for valid both the correctness and computational complexity of Algorithm 2 as given earlier in Claim 1. Following this, Section A.2.2 revisits Algorithm 3, initially introduced by Jiao et al. [10] . The original publication presented the algorithm without formal proof of its correctness, which we rectify and offer in Section A.2.2.This section provides a proof to Claim 1 to establish the efficiency and accuracy of Algorithm 2 in computing the weighted convolutional Kendall kernel, as specified in Equation 4, with a focus on its computational complexity.Claim 1. The weighted convolutional Kendall kernel (Equation 4) with product-symmetric rank weights (Equation 5) can be computed in O(k 2 ) time.Proof. The claim is proven through Algorithm 2, where we establish its correctness and demonstrate its computation requirement is O(k 2 ). The essence of our proof centers on analyzing the feature representation of the WCK kernel, ϕ wck , as outlined in Claim 3. The feature vectors of ϕ wck reside in a n 2 dimensional space, indexed by pairs of items. Our approach is to demonstrate that Algorithm 2 accurately computes the right-hand side (RHS) of the equation k wck (π 1 , π 2 ) = ϕ wck (π 1 ) T ϕ wck (π 2 ). This involves a summation over item pairs, expressed as k wck (π 1 , π 2 ) = l<m ϕ wck l,m (π 1 ) T ϕ wck l,m (π 2 ). Our proof analyzes various scenarios: cases where pairs of items, namely l and m, fall within the top-k, scenarios with one item within the top-k and the other outside, and situations where neither item is within the top-k. Each of these cases contributes distinctively to the computation of the overall kernel, resulting in different terms in the algorithmic computation. This is encapsulated in Algorithm 2, where k wck (π 1 , π 2 ) = 5 i=1 s i (π 1 , π 2 ), and each s i corresponds to the terms given earlier in Algorithm 2 from Section 2.Before proceeding with the cases of this summation as given in Table 4 , we recall the notations utilized by Algorithm 3 in Definition 1. Also, remember that we will be proving for product-symmetric weights as given in Equation 5, where, w s : [n] × [n] → R n and its one-dimensional marginals are w s (ℓ, •) = 1 n-k n j=k+1 w s (ℓ, j) Table 4 shows how these cases are organized and relate to different s i terms required for computing the WCK kernel. The key strategy involves breaking down the kernel's computation into cases based on the positioning of item pairs within the top-k rankings. In case 1, we consider all the scenarios when both indices are within the set of items in both top-k rankings, i.e., all items in the set I 1 ∪ I 2 . Definition 1. Algorithm 2 and 3 and utilize following notations.• I 1 and I 2 are the sets of items in rankings π 1 and π 2 , respectively.• σ 1 ∈ Π |I1| and τ 1 ∈ Π |I1∩I2| are the full rankings of I 1 and I 1 ∩ I 2 , both consistent with the input top-k ranking π 1 . I.e., relative ranks of items is same yielding ∀l, m ∈ -Let I 1 and I 2 be the sets of items in rankings π 1 and π 2 , respectively.I 1 ∩ I 2 , p π1 i>j = p τ1 i>j . • Analogously,1: if |I 1 ∩ I 2 | ≥ 2 then 2: s 1 (π 1 , π 2 ) = 1 ( n 2 ) 1≤l<m≤n|l,m∈I1∩I2 w s (p π1 l , p π1 m ) • w s (p π2 l , p π2 m ) • η l,m (π 1 , π 2 ) 3: end if 4: if |I 1 ∩ I 2 | ≥ 1 and |I 1 \ I 2 | ≥ 1 then 5: s 2 (π 1 , π 2 ) = 1 ( n 2 ) • l∈I1∩I2|m∈I1\I2 w s (p π1 l , p π1 m ) • w s (p π2 l , •) p π1 l<m -p π1 l>m 6: end if 7: if |I 1 ∩ I 2 | ≥ 1 and |I 2 \ I 1 | ≥ 1 then 8: s 3 (π 1 , π 2 ) = 1 ( n 2 ) • l∈I1∩I2|m∈I2\I1 w s (p π1 l , •) • w s (p π2 l , p π2 m ) • p π2 l<m -p π2 l>m 9: end if 10: if |I 1 \ I 2 | ≥ 1 and |I 2 \ I 1 | ≥ 1 then 11: s 4 (π 1 , π 2 ) = -1 ( n 2 ) • l∈I1\I2|m∈I2\I1 w s (p π1 l , •) • w s (p π2 m , •) 12: end if 13: if |I 1 ∩ I 2 | ≥ 1 and |[n] \ (I 1 ∪ I 2 )| ≥ 1 then 14: s 5 (π 1 , π 2 ) = 1 ( n 2 ) • (n -|I 1 ∪ I 2 |) • l∈I1∩I2 w s (p π1 l , •) • w s (p π2 l , •) 15: end if 16: k wck (π 1 , π 2 ) = s 1 (π 1 , π 2 ) + s 2 (π 1 , π 2 ) + s 3 (π 1 , π 2 ) + s 4 (π 1 , π 2 ) + s 5 (π 1 , π 2 )Case 1: The pair (l, m) ∈ I 1 ∪ I 2 falls within the top-k, leading to three distinct cases. Below, we provide s i terms for each case as given in Table 4 .Case 1-a: Two items in I 1 ∩ I 2 , meaning both l and m belong to I 1 I 2 . Using Claim 3 regarding the feature vector ϕ wck , we simplify s 1 as follows:EQUATION)Case 1-b: When one item is in I 1 ∩ I 2 , the other must reside either in I 1 \ I 2 or I 2 \ I 1 , thus leading to two distinct sub-cases. This is specified in Table 4 . Concretely, if the other item is in I 1 \ I 2 , it contributes to the s 2 terms, whereas if it's in I 2 \ I 1 , it contributes to the s 3 terms.Corresponding to Case 1-b-i, when the other item is in I 1 ∩ I 2 , i.e., s 2 is the term corresponding to indices where l is in I 1 ∩ I 2 and m in I 1 \ I 2 , or the reverse, represented by partial sums u and v. For the partial sum u, with l in I 1 ∩ I 2 and m in I 1 \ I 2 , we find that p π2 l is in [k], while p π2 m is not. The simplification of u proceeds using Claim 3 as follows:u = 1≤l<m≤n|l∈I1∩I2|m∈I1\I2 1 n 2 • w s (p π1 l , p π1 m ) • p π1 l<m -p π1 l>m • 1 n 2 • w s (p π2 l , •) p π2 l<m -p π2 l>m = 1 n 2 1≤l<m≤n|l∈I1∩I2|m∈I1\I2 w s (p π1 l , p π1 m ) • w s (p π2 l , •) p π1 l<m -p π1 l>m .Similarly, the partial sum v can be simplified as follows:v = 1≤l<m≤n|m∈I1∩I2|l∈I1\I2 1 n 2 • w s (p π1 l , p π1 m ) • p π1 l<m -p π1 l>m • -1 n 2 • w s (p π2 l , •) • p π2 l<m -p π2 l>m = -1 n 2 1≤l<m≤n|m∈I1∩I2|l∈I1\I2 w s (p π1 l , p π1 m ) • w s (p π2 l , •) • p π1 l<m -p π1 l>m = -1 n 2 1≤m<l≤n|l∈I1∩I2|m∈I1\I2 w s (p π1 m , p π1 l ) • w s (p π2 m , •) • p π1 m<l -p π1 m>l = 1 n 2 1≤m<l≤n|l∈I1∩I2|m∈I1\I2 w s (p π1 l , p π1 m ) • w s (p π2 l , •) p π1 l<m -p π1 l>m .In the above, the first two lines use results from Claim 3 and use similarity of w s . In the following line, l and m are exchanged. Lastly, the negative sign is pushed into the indicator functions to make the summand function of this partial sum v similar to the partial sum u, and the similarity of the w s is utilized. The above partial sums simplify s 2 as follows:EQUATIONAnalogously, in Case 1-b-ii, we deduce the corresponding term s 3 for the pair of indices as described Table 4 through symmetry. Specifically, the term s 3 can be outlined as follows:EQUATION)Case 1-c: Both items are outside I 1 ∩ I 2 , specifically, l ∈ I 1 \ I 2 and m ∈ I 2 \ I 1 or the reverse.Like Case 1-b-i, we divide s 4 into partial summations u and v. Now, we calculate u under the condition that l ∈ I 1 \ I 2 and m ∈ I 2 \ I 1 .u = 1≤l<m≤n|l∈I1\I2|m∈I2\I1 1 n 2 • w s (p π1 l , •) • p π1 l<m -p π1 l>m • 1 n 2 • w s (p π2 m , •) • p π2 l<m -p π2 l>m , = 1 n 2 • 1≤l<m≤n|l∈I1\I2|m∈I2\I1 w s (p π1 l , •) • (1 -0) • w s (p π2 m , •) • (0 -1) , = -1 n 2 • 1≤l<m≤n|l∈I1\I2|m∈I2\I1 w s (p π1 l , •) • w s (p π2 m , •).Similarly, we can estimate partial sum v for the set l ∈I 2 \ I 1 & m ∈ I 1 \ I 2 .Using calculations similar to Case-1-b-i for summing u and v, we have:EQUATION)Case 2: One item exists in I 1 ∩ I 2 , the other in [n] \ (I 1 ∩ I 2 ). It branches into two sub-cases: Case 2-a with one item in I 1 ∪ I 2 , and Case 2-b, where one item outside I 1 ∩ I 2 but is in I 1 ∪ I 2 . Focusing on Case 2-a, represented by s 5 , we simplify as follows. This involves two index scenarios, either l ∈ I 1 ∩ I 2 and m / ∈ I 1 ∪ I 2 or vice versa, represented by partial sums u and v. We now simplify u below:u = 1 n 2 1≤l<m≤n|l∈I1∩I2|m / ∈I1∪I2 1 n 2 • w s (p π1 l , •) • p π1 l<m -p π1 l>m • 1 n 2 • w s (p π2 l , •) • p π2 l<m -p π2 l>m , = 1 n 2 1≤l<m≤n|l∈I1∩I2|m / ∈I1∪I2 w s (p π1 l , •) • w s (p π2 l , •), = 1 n 2 1≤l<m≤n|l∈I1∩I2 w s (p π1 l , •) • w s (p π2 l , •) • (n -|I 1 ∪ I 2 |).Using steps similar to the previous case, we get the following value for s 5 :EQUATIONFor Case 2-b, l or m are absent from I 1 or I 2 , leading to two sub-scenarios. Consequently, either ϕ wck l,m (π 1 ) is zero or ϕ wck l,m (π 2 ) is zero. Therefore, these terms don't contribute to the overall WCK kernel value.Case 3: No item is in the top-k, i.e., both l, m / ∈ I 1 ∪ I 2 . As both items are absent from the top-k in either ranking, the value trivially reduces to zero.After covering all configurations of l and m, we incorporate results from Equations 12, 13, 14, 15, and 16. This integration yields the expression k wck (π 1 , π 2 ) = 5 i=1 s i (π 1 , π 2 ), where, each term s i matches precisely with its corresponding expression in Algorithm 2. The proof for the correctness of Algorithm 2 is complete, as each term s i corresponds to its respective expression in the algorithm. Regarding the time complexity of Algorithm 2, each term s i sums at most k 2 quantities, and each quantity summed can be computed in O(1) time. Therefore, the computation time required for Algorithm 2 is O(k 2 ).This section provides Algorithm 3 for computing the convolutional Kendall kernel, as specified in Equation 3. Later, its efficiency and accuracy are proved in Claim 4.Input: Two top-k rankings π 1 , π 2 ∈ Π k . Output: Convolutional Kendall kernel k ck (π 1 , π 2 ).-Let I 1 and I 2 be the sets of items in rankings π 1 and π 2 , respectively.-Let σ 1 ∈ Π |I1| and τ 1 ∈ Π |I1∩I2| be the full rankings of I 1 and I 1 ∩ I 2 , both consistent with the input top-k ranking π 1 .-Analogously, construct σ 2 and τ 2 utilizing the set I 2 and ranking π 2 .1: if |I 1 ∩ I 2 | ≥ 2 then 2: s 1 (π 1 , π 2 ) = 1 ( n 2 ) • |I1∩I2| 2 • k sk (τ 1 , τ 2 ) 3: end if 4: if |I 1 ∩ I 2 | ≥ 1 and |I 1 \ I 2 | ≥ 1 then 5: s 2 (π 1 , π 2 ) = 1 ( n 2 ) • l∈I1∩I2 2 • (σ 1 (l) -τ 1 (l)) -k + |I 1 ∩ I 2 | 6: end if 7: if |I 1 ∩ I 2 | ≥ 1 and |I 2 \ I 1 | ≥ 1 then 8: s 3 (π 1 , π 2 ) = 1 ( n 2 ) • l∈I1∩I2 2 • (σ 2 (l) -τ 2 (l)) -k + |I 1 ∩ I 2 | 9: end if 10: s 4 (π 1 , π 2 ) = -1 ( n 2 ) • |I 1 \ I 2 | • |I 1 \ I 2 | 11: s 5 (π 1 , π 2 ) = 1 ( n 2 ) • |I 1 ∩ I 2 | • |[n] \ (I 1 ∪ I 2 )| 12: k ck (π 1 , π 2 ) = s 1 (π 1 , π 2 ) + s 2 (π 1 , π 2 ) + s 3 (π 1 , π 2 ) + s 4 (π 1 , π 2 ) + s 5 (π 1 , π 2 )Claim 4. Algorithm 3 computes the convolutional Kendall kernel (as given in the Equation 3) with a computational complexity of O(k 2 ).Proof. To establish the correctness of Algorithm 3, we will adopt the same proof approach as the one used for Claim 1 concerning Algorithm 2. Specifically, we will adhere to the earlier categorization in Table 4 and notations given in Definition 1. Since the CK kernel can be derived by uniformly setting the weight function w s (i, j) = 1, we will insert them in s i terms as given in Algorithm 2. These cases will be revisited and simplified by applying the condition w s (i, j) = 1. Note that this also implies its one-direction marginal weights to be 1, i.e., w s (i, •) = 1Simplifying the s 1 Term: For the WCK kernel, Case 1-a leads to the expression of s 1 as stated in Equation 12. In this case, when two items, specifically l and m, are both in the intersection I 1 ∩ I 2 , it implies that p π1 l , p π1 m , p π2 l , and p π2 m all rank within the top-k, denoted as [k]. We simplify the s 1 term for CK kernel as follows:EQUATIONThe simplification process begins by assigning unit rank weights in the first line, i.e., w i = 1. Following this, by relabeling the items in I 1 ∩ I 2 and using τ 1 and τ 2 , which are the rankings of π 1 and π 2 limited to the setI 1 ∩ I 2 as defined in Definition 1, it is established that η l ′ ,m ′ (τ 1 , τ 2 ) = η l,m (π 1 , π 2 ). This is because the relative order of any pair of items is maintained in τ 1 and τ 2 .Consequently, this leads to the final simplification to a scaled value of the standard Kendall kernel k sk , as given in Equation 1.Simplifying the s 2 and s 3 Terms: The s 2 and s 3 terms are obtained for Case 1-b, which is for case when one item is in I 1 ∩ I 2 and the other item is either in I 1 \ I 2 or I 2 \ I 1 . We divide this into two sub-cases. Case 1-b-i: The other item is in I 1 \ I 2 , with s 2 representing the summation terms derived from the CK's inner product. Case 1-b-ii: The other item is I 2 \ I 1 , where s 3 denotes the summation terms. We simplify the s 2 term for the CK kernel as follows:s 2 (π 1 , π 2 ) = 1 n 2 l∈I1∩I2|m∈I1\I2 w s (p π1 l , p π1 m ) • w s (p π2 m , •) p π1 l<m -p π1 l>m = 1 n 2 l∈I1∩I2|m∈I1\I2 p π1 l<m -p π1 l>m = 1 n 2 l∈I1∩I2|m∈I1\I2 p π1 l<m :=u - 1 n 2 l∈I1∩I2|m∈I1\I2 p π1 l>m :=v.Next, we examine the terms u and v in detail, starting with u. The term u, which corresponds to p π1 l<m , signifies instances where item l is ranked before item m in the top-k ranking π 1 . This can be derived from the observation that σ 1 (l) -1 items are positioned before item l in the set I 1 . Out of these items, τ 1 (l) -1 also belong to the intersection I 1 ∩ I 2 . This follows from the definition of the full rankings σ 1 and τ 1 on the set I 1 and the intersection I 1 ∩ I 2 , respectively. Consequently, it can be concluded that σ 1 (l) -τ 1 (l) items from the set difference I 1 \ I 2 are ranked before item l. The second term, v, corresponds to p π1 l>m and involves a calculation that takes into account the items ranked after the l-th item in the set I. Specifically, there are k -σ 1 (l) items following the l-th item. Within the intersection I 1 ∩ I 2 , the number of items before l is given by|I 1 ∩ I 2 | -τ 1 (l). Therefore, the expression (k -σ 1 (l)) -(|I 1 ∩ I 2 | -τ 1 (l))represents the count of elements that are positioned after l in the set differenceI 1 \ I 2 .Combining the above calculations for both terms u and v, the s 2 term for the CK kernel can be simplified as follows:EQUATIONUsing the symmetry between Case 1-b-i and Case 1-b-ii, we can simplify s 3 for the CK kernel as follows:EQUATIONSimplifying the s 4 and s 5 Terms: We simplify the s 4 and s 5 terms for the CK kernel starting from Equation 15 and Equation 16, respectively, as follows:EQUATIONEQUATION)We have obtained the values of all the simplified s i terms for the CK kernel in Equations 17, 18, 19, 20, and 21 . By combining these terms, we getk ck (π 1 , π 2 ) = 5 i=1 s i (π 1 , π 2 ), where each term s i precisely matches its corresponding expression in Algorithm 3. This completes the proof of the correctness of Algorithm 3. Regarding its time complexity, each term s i sums at most k 2 quantities, and each quantity can be computed in O(1) time. Therefore, the time required for Algorithm 3 to compute the CK kernel is O(k 2 ).This section revisits Theorem 1 about the fact matrix-vector multiplication time for the Kendall kernel matrix for top-k rankings. Specifically, we aim to eliminate the mvm(K X )'s dependence on the number of items, i.e., n on and linear dependence in the number of rounds, i.e., T , as claimed in Theorem 1.Theorem 1. For the WCK kernel with product-symmetric weights w ps , the computational complexity of multiplying the kernel matrix K Xt with any admissible vector is O(k 2 t), i.e., mvm(K Xt ) = O(k 2 t), where X t is any arbitrary set of t top-k rankings.Proof. The cornerstone of this proof lies in the computation of the WCK kernel, as delineated in Algorithm 2. This algorithm requires only O(k 2 ) computation. For brevity, we write X to represent X T , and the proof follows for any X t , i.e., any value of t, not just T .As also suggested previously, we will demonstrate through the equation K X = (Φ a X ) T Φ b X , where both matrices Φ a X and Φ b X have columns with only O(k 2 ) non-zero entries. Consequently, this leads to the computational complexity of matrix-vector multiplication, denoted as mvm(K X ), being O(k 2 • T ).From Algorithm 2, we know that each entry of the kernel matrix k(π 1 , π 2 ), can be expressed as a sum 5 i=1 s i (π 1 , π 2 ). Assuming each s i (π 1 , π 2 ) equals ϕ ai (π 1 ) T ϕ bi (π 2 ), and considering that all vectors ϕ ai and ϕ bi exhibit this property, we can express K X as (Φ a X ) T Φ b X . Here, the i th row of (Φ a X ) T and the j th column of Φ b X are represented by[ϕ a1 (π i ) T , • • • , ϕ a5 (π i ) T ] and [ϕ b1 (π j ), • • • , ϕ b5 (π j )],respectively. Therefore, the overall mvm complexity can be characterized by the sparsity of the vectors ϕ ai and ϕ bi , as is formalized in the claim presented below.Claim 5. Consider a kernel matrix K X corresponding to any set X of cardinality T . Each entry of K X , denoted as k(x 1 , x 2 ), is defined by the sum 5 i=1 s i (x 1 , x 2 ), where each s i (x 1 , x 2 ) is the result of the dot product ϕ ai (x 1 ) T ϕ bi (x 2 ), where, ϕ ai and ϕ bi are vectors characterized by having O(z) non-zero entries. Given this structure, the matrix-vector multiplication complexity for K X is O(nnz • T ), i.e., mvm(K X ) = O(z • T ).Proof. We will demonstrate this in the following discussion by concentrating on the k th entry of the output vector, specifically K X v, for any arbitrary vector v:(K X v) k = j K X (k, j)v j = j i=1 s i (π k , π j ) v j = j 5 i=1 ϕ ai (π k ) T ϕ bi (π j ) v j , = 5 i=1   j ϕ ai (π k ) T ϕ bi (π j )v j   = 5 i=1 ϕ ai (π k ) T   j ϕ bi (π j )v j   .Given that for all i, ϕ bi possesses only O(z) non-zero entries for any π j , the computation of j ϕ bi (π j )v j requires O(z) operations. This implies that the expression j ϕ bi (π j )v j also necessitates O(z) computation. Applying a similar rationale to ϕ ai , it follows that computing (K X v) k demands only O(z) operations. Extending this argument to all entries of the output vector, it is evident that computing K X v requires only O(z • T ) computation Utilizing Claim 5, it suffices to complete the proof by showcasing that these exist vectors ϕ ai and ϕ bi , each with only O(k 2 ) non-zero elements, corresponding to each s i as specified in Algorithm 2. Additionally, these vectors ensure that s i (π 1 , π 2 ) = ϕ ai (π 1 ) T ϕ bi (π 2 ). We will next establish such vectors for all s i terms. Starting with the s 1 term below.Showcasing s 1 (π 1 , π 2 ) = ϕ a1 (π 1 ) T ϕ b1 (π 2 ) for sparse ϕ a1 (π 1 ) and ϕ b1 (π 2 ) vectors. We begin by manipulating s 1 , as defined in Equation 12. For the sake of brevity, their scalar factors will be omitted in the following explanation.EQUATION, = (ϕ a1 (π 1 ) T ϕ b1 (π 2 ).Both ϕ a1 and ϕ b1 are sparse by design, taking non-zero values only when l and m appear in the top-k rankings. This demonstrates the existence of sparse vectors for the s 1 term. Next, we will establish the same for the s 2 and s 3 terms.Showcasing sparse vectors for s 2 and s 3 . We begin by manipulating s 2 , as defined in Equation 13, while ignoring its scalar factor. We will exploit symmetry between s 2 and s 3 terms. s 2 (π 1 , π 2 ) = l∈I1∩I2|m∈I1\I2 w s (p π1 l , p π1 m ) • w s (p π2 l , •) p π1 l<m -EQUATIONEQUATIONEquation 25 demonstrates the existence of vectors ϕ a2 and ϕ b2 for the s 2 term. The vectors ϕ a21 and ϕ a22 , possessing O(k) and O(k 2 ) non-zero entries respectively, are defined in Equations 23 and 24.Consequently, the ϕ a2 vector has O(k 2 ) non-zero entries. Similarly, it can be shown that ϕ b2 contains O(k 2 ) non-zero entries, thus fulfilling the proof requirements for proving the s 2 term. For the s 3 term, we observe a symmetry between s 2 and s 3 , namely s 3 (π 1 , π 2 ) = s 2 (π 2 , π 1 ). This symmetry makes it trivial to satisfy the requirements, as further highlighted by the following equation:EQUATIONShowcasing sparse vectors s 4 (π 1 , π 2 ) = ϕ 4a (π 1 ) T ϕ 4b (π 2 ). We begin by manipulating the s 4 term without scalar, as defined in Equation 15.EQUATIONThe equation shows that s 5 (π 1 , π 2 ) = ϕ 5a (π 1 ) T ϕ 5b (π 2 ), where both ϕ 5a and ϕ 5b possess components with a maximum number of non-zero entries, as indicated in Equations 31 and 32. This completes the proof requirements for the s 5 term.By combining the results from Equations 22, 25, 26, 30, and 33, we have demonstrated the existence of vectors ϕ ai and ϕ bi , each containing only O(k 2 ) non-zero elements, and have established thats i (π 1 , π 2 ) = ϕ ai (π 1 ) T ϕ bi (π 2 ) for each i ∈ 1, 2, 3, 4, 5.In conjunction with Claim 5, this completes the proof.This section includes the proofs that were omitted from Section 4, presented in the following order:• Section B.1 outlines a brief of Gaussian process regression for any domain.• Section B.2 summarizes the committed details about the local search utilized for optimizing the UCB function.• Section B.3 provides the removed proof for the Theorem 2 concerning the overall time for the bandit algorithm.• Section B.4 provides the proof for Theorem 3 concerning regret analysis of the proposed bandit algorithm.In GP regression [22] , the training data are modeled as noisy measurements of a random function f drawn from a GP prior, denoted f ∼ N (0, k(•, •)), where k : X × X → R is a kernel function over any domain X . The observed training pairs (x i , y i ) are collected as X = [x 1 , . . . , x T ] and y = [y 1 , . . . , y T ] ∈ R T , where, for an input x i , the observed value is modeled as y i = f (x i ) + ϵ, with ϵ i ∼ N (0, σ 2 ). The kernel matrix on data is K X = [k(x i , x j )] T i,j=1 ∈ R T ×T . The posterior mean µ f |D and variance σ f |D functions for GPs are:EQUATIONEQUATIONwhere k x ∈ R T has as its i th entry k(x, x i ), z = (K X + σ 2 I) -1 y, and I is an identity matrix. For GP regression on an arbitrary domain X , the kernel function must be a p.d. kernel [23] .Naive approaches rely on the Cholesky decomposition of the matrix K X + σ 2 I, which takes Θ(T 3 ) time [23] . To circumvent the Θ(T 3 ) runtime, recent works use iterative algorithms such as the conjugate gradient algorithm, which facilitate GP inference by exploiting fast kernel matrix-vector multiplication (MVM) algorithms, i.e., v → K X v [3] . In practice, these methods yield highly accurate approximations for GP posterior functions with a complexity of Θ(p • T 2 ) for p iterations of the conjugate gradient algorithm, as mvm(K X ) = T 2 , and mvm(M ) is the operation count for multiplying matrix M by a vector. p ≪ T proves to be efficient in practical application [3] .Optimizing the AF, i.e., UCB function, poses a significant challenge due to its enormous size of Π k . Drawing inspiration from prior research on Bayesian optimization within combinatorial spaces, we employ a breadth-first local search (BFLS) to optimize the UCB acquisition function [2, 19] . The BFLS begins with the selection of several random top-k rankings. Subsequently, each specific top-k ranking is compared with the UCB values of its neighboring rankings, proceeding to the one with the highest UCB value.The neighbors of a top-k ranking include all its permutations and the permutations of modified top-k rankings obtained by swapping one item with any of the remaining items. For any top-k ranking, there are (n -k) • k! + k! neighbors, which is often not huge as k is often ≤ 6. This search continues until no neighboring top-k ranking with a higher value is discovered. Although BFLS is a local search, the initial random selection and multiple restart points help it evade local minima, a strategy that previous studies have corroborated [19] .Theorem 2. Assuming a fixed number of iterations required by the iterative algorithms, the total computational time for running the GP-TopK bandit algorithm for T rounds of top-k recommendations, using the contextual product kernel (Equation 6), is O(k 2 cℓT 2 ). This applies to WK, CK, and WCK top-k ranking kernels, where ℓ is the number of local search evaluations for selecting the next arm in every round.Proof. The proof can be straightforwardly derived by combining the results presented in Table 1 , which succinctly summarizes the time complexities for each step of computing the UCB using both feature and kernel approaches. It is important to emphasize that iterative algorithms enhance results from O(T 4 ) to O(T 3 ) in computational complexity. Furthermore, these algorithms can further reduce complexity to O(T 2 ) when used with the feature approach.The results presented in Table 1 can be validated through straightforward observations and by leveraging findings from previous Sections 2. Specifically, Section 2 offers proof for the mvm(K X ) row explicitly. For the compute K Xt row, the complexity of kernel approaches is deduced from Algorithms 2 and 3. For feature approaches, the compute K Xt row is inferred from the sparsity of the feature representations as stated in Claim 3. Lastly, the memory row is straightforwardly deduced for the kernel approach by counting its entries. For the feature approach, it is derived from the sparsity of the feature representations.In this section, we revisit Theorem 3 and provide its proof. The proofs build on the work by Krause et al. [14] , delivering results for bounding the contextual regret in the context of the top-k ranking problem. To set the stage for our regret analysis, let's first define the critical term maximum mutual information, denoted by γ t , is given below:γ t := max X⊆X :|X|=t I(y X ; f ), I(y X ; f ) = H(y X ) -H(y X |f ),where I(y X ; f ) quantifies the reduction in uncertainty (measured in terms of differential Shannon entropy) about f achieved by revealing y A [27] . In Gaussian observation case, the entropy can be computed in closed form:H(N (µ, Σ)) = 1 2 log |2πeΣ|, so that I(y X ; f ) = 1 2 log |I + ξ -2 K X |, where K X = [k(x, x ′ )] x,x ′ ∈Xis the Gram matrix of k evaluated on set X ⊆ X . For the contextual bandit algorithm, X represents contexts and arms considered until round t.Before proving Theorem 3, we align the Krause et al. [14] results with our notation for consistency. Furthermore, we modify β t to accommodate embeddings encompassing negative values, aligning with the fact that contextual embeddings may exhibit negative dimensions.Proposition 1 (Theorem 1, [14] ). Let δ ∈ (0, 1), and the unknown reward function f be sampled from the known GP prior with known noise variance σ 2 . Suppose one of the following holds:1. Assumption 1 holds and set β t = 2 log(|X |t 2 π 2 /6δ).2. Assumption 2 holds and set β t = 2B 2 + 300γ t ln 3 (t/δ).Then the cumulative regret R T of the contextual GP bandit algorithm with the UCB acquisition function is bounded by Õ( √ C 1 T γ T β T ) w.h.p. Precisely, Pr R T ≤ √ C 1 T γ T β t ) + 2 ∀T ≥ 1 ≥ 1 -δ, where, C 1 = 8/ log(1 + σ -2 ) and the notation Õ hides logarithmic factors in n, 1 δ and T .Proposition 1 shows that the regret R T for the contextual GP bandit algorithm, utilizing the UCB acquisition function is bounded with high probability within Õ( √ C 1 T γ T β T ), where the notation Õ hides logarithmic factors in n, 1 δ and T . To ascertain the Õ order for R T , it is imperative to first bound the Õ order of γ T β t . We begin by examining the γ T term in the subsequent proposition. Proposition 2. Under the assumptions of Theorem 3, γ T can be succinctly characterized as γ T = O(n 2 c log(n 2 T ) + c log T ), which also simplifies to Õ(n 2 c), where the Õ notation omits logarithmic factors in n and T .Proof. For the GP bandit algorithm with the UCB acquisition function, γ T = C • log |I + σ -2 K X T | , where C equals (1/2) • (1 -1/e) -1 and K X T represents the kernel matrix computed over contexts and arms across T rounds [27, 14] . Precisely, K X T is calculated using the contextual kernel defined in Equation 6. It is applied to contexts and top-k ratings from the feedback data D t , corresponding to Line 6 of the generic contextual bandit Algorithm 1.Next, we leverage the characteristic of the contextual kernel being a product kernel. Consequently, the maximum mutual information term for the joint kernel, γ T , can be upper bounded by c • (γ π T + log T ), where c denotes the dimensionality of contexts and γ π T represents the maximum information gain in a non-contextual setting [14] . Specifically, γ π T is computed similarly but is confined to top-k rankings. That is, γ π T = C • log |I + σ -2 K X π | , with K X π T being calculated exclusively using the top-k kernels on the top-k rankings as selected by the bandit algorithm. X π T represents the top-k rankings selected by the bandit algorithm, i.e., excluding the contexts from the collected feedback.Recalling the formulation for top-k rankings kernels, we have . Given the Gershgorin circle theorem, which bounds all eigenvalues of a matrix by the maximum absolute sum of its rows, therefore we can conclude that γ π T = O(n 2 log(n 2 T )), as for all the columns of the Φ X π have bounded normed as given in Claims 2 and 3, i.e., ||ϕ(π)|| 2 2 ≤ 1 [29] . By combining γ π T = O(n 2 log(n 2 T )) with the contextual product kernel, we obtain γ T = O(n 2 c log(n 2 T ) + c log T ), thereby providing the claimed bound in the proposition.K X T = Φ T X π T Φ X π T ,Next, we build on Propositions 1 and 2 to prove the main theorem regarding the regret of the proposed GP-TopK bandit algorithm for top-k recommendations. Proof. We will prove the above theorem for both cases separately.For Assumption-1. Given |C| is finite and β T = 2 log(|D|T 2 π 2 /6δ). First, we focus on bounding β T as follows: Thus, we showcase the asserted bound for the regret R T as Õ √ C 1 T γ T β T = Õ n C 1 T c(log|C| + k + log(T 2 π 2 /6δ)) .β T =For Assumption-2. Given ∥f ∥ k ≤ B and β t = 2B 2 + 300γ t ln 3 (t/δ). First, we bound the β T term using Proposition 2 as follows: Similarly, we can analogously perform the analysis for Assumption 1 and combine it with Proposition 1 to obtain the regret bounds mentioned in the Table 3 .β T = 2BThis section presents omitted details from the main body of the text.We utilized multiple NVIDIA Tesla M40 GPUs with 40 GB RAM on our in-house cluster for our experiments. The experiments in Section 5 required approximately 5 GPU-hours for small arm space and 24 GPU-hours per iteration for large arm space. We conducted about 50 to 100 iterations throughout the project. The results reported in Section C.3 required the same computational resources as the large arm space experiments.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
 
 Appendix:  


Decision: This paper considers the slate recommendation problem where $k$ items are simultaneously recommended to a user at the same time. To solve this problem the authors adapt existing Gaussian process methods to the top-$k$ setting by modifying Kendall kernels to the top-$k$ setting. They also provide a regret analysis and empirical studies to justify their proposed algorithm.

Based on the reviews and ratings, this paper is borderline, but more on the accept side. All reviewers recommend to accept this paper, and they all agree that the paper is well written and easy to read. However, while this paper clearly has many strengths, it also has some weaknesses, as pointed out by the reviewers. In particular, I agree with Reviewer 9Xg2 that the novelties of the proposed algorithm seem to be limited.

Reviews: review: paper_summary: paper_summary: This paper considers the slate recommendation problem where k items are simultaneously recommended to a user at the same time (in a banner or "slate").  In order to solve this problem the authors adapt existing Gaussian process methods to the top-k setting by modifying Kendall kernels to the top-k setting.  They also introduce some computational tricks that allow for the algorithm to be quadratic in the embedding size.  They also provide a regret analysis and empirical studies to defend their algorithm.
strength_weakness: strength_weakness: I would like to provide some commentary on this paper and how it might relate to production recommender systems without in any way wanting to diminish the excellent work done in this paper.  NeurIPS is a primarily academic research venue and this paper is very well executed and it is very pleasing to see a recommender systems paper of such quality.

I would however be very surprised if this method or a method derived from it was applied in a real system for a number of reasons.

First, I like the authors use of Figure 1 in order to highlight limitations of the cascade model (the even simpler position based model has similar problems), there have however been models proposed for this case including the Probabilistic Rank and Reward model - https://arxiv.org/pdf/2208.06263 .  The "full bandit framework" while useful does discard the useful preference information about what was clicked (as well as saying the banner was clicked somewhere), this information is usually quite valuable.

The covariance functions of the model (equation 6) is very well explained and the idea is interesting.  A further useful note is that using this multiplied form the reward is correlated if both the context is similar _and_ the actions (top-k) are similar, due to multiplication if either is approximately zero the covariance is zero.  The covariance in the action space is rather limited however as it has no notion for some actions being similar.  For example if you are going to recommend action movies then you might fill the top-k with totally different action movies yet still have a correlated reward.  The model in this paper has some similarities, including the factorized covariance matrix https://arxiv.org/abs/2008.12504

Finally, this paper learns a unique reward for every top-k ordering.  This results in a combinatorial explosion both in learning and in delivering recommendations.  While the assumption is interesting it does not allow for finding the best recommendations performing an argsort often approximated using a fast maximum inner product search (e.g. LSH or HNSW), it seems difficult to relax these assumptions in real world systems.
questions: questions: Do you agree with the limitations discussed above?
limitations: limitations: yes
paper_summary: paper_summary: The authors propose a new bandit algorithm for top-k recommendations that utilizes a Gaussian Process to model the reward of the exponentially large set of arms, and provide regret bounds which improve upon the naive approach of modeling each arm independently. The authors also present a new kernel and show that the associated kernel matrix displays a particular structure that can be exploited to efficiently compute GP predictions. Finally, experimental validation show the improved regret with respect to baseline algorithms and other similar kernels.
strength_weakness: strength_weakness: - The authors claim the new algorithm to be their primary contribution, though it is a simple adaptation of a contextual GP-UCB to top-k recommendations, and a lot of attention is dedicated instead to the new kernel and its computational costs.
- Despite the strengths of the new kernel, it is not particularly novel as it is a straightforward combination of existing kernels.
- Figures in the Experiments section should be more clear about the confidence ranges (the confidence level in Figure 2 is not mentioned, and the ranges appear to be missing entirely in Figures 3 and 5).

I found a few typos and confusing passages, but overall, they didn't affect the reading experience. I will report them here as a feedback:
line 99: typo ww(...) -> w(...)
lines 254-256: this sentence sounds like the new terms involving n in the bounds are n^{k/2-1} and n^{k-1}, maybe the intended meaning was to highlight the improvement with respect to the cited results?
lines 281-283: \lambda = 0.25 emphasizes diversity over relevance
line 751: typo shoes -> shows
line 821: typo very -> every (also possibly missing a subject after "observed"?)
questions: questions: 1) The number of local searches is a substantial factor in the overall time complexity of the proposed algorithm, and the number of local searches seems to be particularly high for the large arm space scenarios. Since optimizing the computational costs of the algorithm is a big part of this work, I would like to ask the authors whether they have considered and whether it is possible and/or practically useful to further exploit the structure of the kernel to avoid recomputing the predictor entirely when moving between neighbors.
limitations: limitations: N/A
paper_summary: paper_summary: The paper introduces a contextual bandit algorithm for top-k recommendations, leveraging Gaussian processes with a Kendall kernel to model the reward function. The proposed method utilizes full-bandit feedback without assumptions such as semi-bandit feedback or cascade browsing. Theoretical analysis demonstrates a sublinear regret with the number of rounds and arms, and empirical results from simulations show superior performance compared to other baselines. The authors also improve the computational efficiency and memory requirements of the algorithm.
strength_weakness: strength_weakness: 1. The paper claims that existing bandit algorithms impose strict assumptions about feedback models, e.g., semi-bandit feedback or cascade browsing. I agree with this statement. However, the paper addresses this problem by directly using Gaussian processes to model the reward function. Isn't this also a restrictive assumption? The authors should clarify this point.
2. The paper lacks a detailed discussion on the choice of the Kendall kernel. The authors should provide more insights into why this kernel was chosen and its advantages over other kernels.
3. There are existing works about top-k combinatorial bandits with full-bandit feedback, such as Rejwan and Mansour (2020) [1]. However, the paper does not compare its method with these existing works. The authors should compare their method with these existing works to demonstrate the difference and novelty of their approach.

[1] Rejwan, Idan, and Yishay Mansour. "Top-$ k $ combinatorial bandits with full-bandit feedback." Algorithmic Learning Theory. PMLR, 2020.
questions: questions: Questions:
1. Why did you choose the Kendall kernel for the Gaussian process? What are the advantages of this kernel over other kernels?
2. How does your algorithm's performance compare to existing works that use full-bandit feedback, such as Rejwan and Mansour (2020)?
limitations: limitations: Limitations are adequately discussed in the paper.
paper_summary: paper_summary: This paper addresses the problem of top-k recommendation with bandit feedback, where the goal is to recommend a list of k items and receive feedback only on the overall quality of the list, not individual items. This captures the notion that user satisfaction depends on the overall quality of the recommendations, not just the single most relevant item. To tackle this, the authors propose a novel algorithm combining Gaussian Process Upper Confidence Bound (GP-UCB) with a specifically designed weighted Kendall kernel. The paper proposes faster inference exploiting features of the Kendall kernel, improving computational complexity from $O(T^4)$ to $O(T^2)$. An upper bound on cumulative regret is derived, showing sublinear regret. Finally, synthetic experiments show that the proposed algorithm can outperform a few baselines.

Disclosure: I have reviewed a previous version of this paper.
strength_weakness: strength_weakness: Weaknesses:
* The approach does not seem scalable to real-world problems
* The theoretical contribution could be further clarified
questions: questions: * The theoretical analysis builds on the analysis of Krause & Ong (2011), adapted to the Kendall kernel. Can the authors please clarify the technical contribution (novelty) compared to Krause & Ong (2011).
* The approach does not seem practical. The empirical evaluation is done with a small number of items (n<=50) and short horizon (T<500). In real-world applications the number of items is often much larger and the number of rounds can also be large.
* The acquisition function is not applied to all possible top-k rankings, rather a local search approach is used. The regret analysis does not account for the approximation due to the local search. The implementation also uses an approximate posterior rather than an exact posterior. This creates a discrepancy between the implementation of the algorithm and the theoretical analysis. The authors are somewhat upfront about this.
* L304 (Evaluation for large arm space):
First, I wouldn’t say that n=50 is large. In real-world applications n is in the millions (e.g., music, books) or billions (e.g., videos).
Second, when showing the regret in Figrue 3 you should actually show all iterations (1-500), not just the ones that include a model update (every 5 steps).

* A few comments from the previous review that are still not fixed:
  * You still have an overloaded notation $\sigma$ for both a ranking (L88) and the sigmoid function (L273). In the previous version you had a three-way overload of $\sigma$ and now it’s only two, but this is easy to fix.
  * Another example from the rebuttal: “CG is the conjugate gradient algorithm. We will clarify this in the future.”
In the current version this part is moved to the appendix (L707), but still appears as “CG”, without clarification.
  * L283: “We set $\lambda = 0.25$ to emphasize relevance over diversity.” This value actually gives a 0.25 weight to ndcg and a 0.75 weight to diversity so the weight for diversity is higher. I also mentioned this in my review to the previous version, did I not understand this correctly and this is why you ignored the comment?
limitations: limitations: No societal issues.

Comments: title: Thanks for acknowledging the comment.
comment: Thanks for the clarifications. Thanks for your responses and I will keep my rating.
Thank you and my concerns have been addressed. Regarding my first question, I realize now that my initial confusion stemmed from the statement: "This necessitates algorithms for full-bandit feedback settings **without assumptions about the objective or reward**." in Lines 40-41. This sentence appears contradictory because using Gaussian processes to model the reward function is still an assumption for me. I suggest that the authors consider rephrasing this sentence for clarity.

I will maintain my current rating, considering a balanced comparison with other papers in my review batch.
Thanks for the clarifications.
Thank you, Reviewer DrUM, for your prompt response. We genuinely appreciate it. We’ll consider adding a related work section in the appendix due to space constraints if it’s not feasible in the main section.

At your convenience, we would greatly appreciate it if you could clarify whether your concerns have been addressed or not. While your clarification is very important to us and is a crucial step in the review process, we understand if you’re unable to reply. 

Thanks again!
Thanks for your responses and I will keep my rating. I also recommend adding a 'Related Work' section to help readers better understand the distinctions between your work and other related research.