Gaussian Process Bandits for Top-k Recommendations
Authors: Mohit Yadav
Cameron N Musco
Daniel Sheldon
Venue: NeurIPS 2024 poster (2024)
Keywords: Gaussian processes
Bandit algorithms
Top-k recommendations
Linear Algebra
Iterative Algorithms
Primary area: probabilistic_methods
TL;DR: This paper explores Gaussian process bandit algorithms using Kendall kernels for top-k ranking, introducing a new variant of the Kendall kernel, enabling fast inference, and including a regret analysis.

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.

Gaussian Process Bandits for Top-k Recommendations
Mohit Yadav
Daniel Sheldon
University of Massachusetts Amherst ymohit@cs umass.edu
University of Massachusetts Amherst sheldon&er umass. edu
Cameron Musco
University of Massachusetts Amherst cnuscoêcs. umass edu
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 significant challenge, as the possible number of ordered top-k recommendations from n items grows exponentially with As a result, previous work often relies on restrictive assumptions about the reward or bandit feedback models, such 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 novel contextual bandit algo- rithm for top-k recommendations. leveraging a Gaussian process with a Kendall kernel 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. Addi- tionally, empirical results using bandit simulator demonstrate that the proposed algorithm outperforms other baselines across various scenarios.
Introduction
The top-k recommendation problem involves providing ranked list of k items, such news articles or products, from pool of n items [34, 13). Online algorithms must adapt to dynamic user preferences, making bandit algorithms suitable due their use of limited feedback [1]. Developing bandit algorithms challenging due to limited feedback and the need for computational efficiency in real-time recommendation environments. Recent research highlights that the overall layout of the recommendation page is crucial for user appeal, 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 items and ordering them by decreasing user relevance [31].
interfaces for recommendations
The joint consideration of top-k items makes the number of arms (possible actions for the bandit algorithm) combinatorially large, i.e., (n)*) Previous research bandit algorithms often imposes strict assumptions on feedback models [30, 21J. For instance, semi-bandit feedback provides scalar reward for each of the top à items, thus decomposing the combinatorial feedback into item-level feedback. However, this type of feedback is frequently unavailable [32]. Another common feedback model cascade browsing [16]. which assumes that users examine items predetermined order and cease browsing once a desirable item is found, offering item-specific scalar feedback but failing capture potential non-linear interactions among items [26]. Figure illustrates the limitations of the cascade model in capturing user interactions within modern top-k recommendation interfaces.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

These limitations motivate us to adopt a more general full full-bandir feedback setting, where only single scalar value is provided for the entire top-k set of recommendations [24].
Compute and memory analysis for the proposed GP- Topk bandit algorithm. Rows represent different costs: total com- pute and memory of the GP- Topk algorithm for T rounds, time for matrix-vector multiplication (mvm) with the kernel matrix Kx, for tth round, and time update Kx,- Columns represent different approaches: the kernel approach, which uses full ker- nel 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.
Table 1:
Bulley
A snapshot from Eisy show- cases Father's Day shopping recommenda- tions. The lack of an obvious linear search order challenges the assumptions of the cas- cade model. Additionally, the proximity and arrangement of items are likely to influence clicks, indicating complex interaction pat- terns and supporting the need for full-bandit feedback without assumptions about user in- teractions with recommended items.
Figure 1:
Tasks compute
kernel approach
feature approach
( (
O k2 T2) O k2. T)
memory
mvm(Kx) (x.))
(t2)) O((c + 19) -t)
Occkk.. O(c.k²)
compute Kx,
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 someeting 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 bandit algorithm that uses Gaussian processes (GPs) to model rewards under full-bandis feedback (i.e., a single scalar value). GPs are selected for their flexibility in accommodating feedback across discrete, continuous, and mixed domains, such continuous contexts and discrete rankings [33]. Additionally, unlike parametric models that require optimization incorporating accumulated feedback from previous rounds, GP updates computationally efficient, involving only data updates [24]. Although GP inference may face computational limits, we will develop efficient inference methods tailored to proposed algorithm. A further challenge in designing GP-based bandit algorithms for top-k recommendations is constructing expressive positive- definite 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-base and Wang et al. [31] used GPs with semi-bandit feedback for recommending top-k items. In contrast, work does not rely specific reward model feedback assumption, and develops an efficient GP-based bandit algorithm for top-k recommendations.
feedback model,
1.1 Contributions
Our primary contribution is the GP-TopK algorithm, a contextual bandit algorithm for recommending top-k items. This algorithm operates in 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 novel weighted convolutional Kendall kernel for top-k recommendations that address pathologies existing variants of the Kendall kernel when applied to top-k recommendations.
Our second key contribution is enhancing the scalability horizons. Initially, the computational cost for top-k recommendations using the GP-TopK algorithm (TT)) for T rounds. We first reduce this to (T3) by leveraging iterative algorithms from numerical linear algebra [25]. Next, we derive sparse feature representations for the novel weighted
GP-TopK algorithm for longer time

---

convolutional Kendall kernel, further reducing the compute requirements from O(T*) ) to ( and memory requirements from ( to OTT). Table summarizes these improvements in time and memory requirement, including their dependence on other parameters.
We provide 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 (nn)) bound for top-k recommendation. without using feature representations [27]. Finally, we empirically validate GP-TopK's regret on real-world datasets, demonstrating improvement over baseline methods.
1.2 Organization
The remainder of this paper is organized as follows: Section introduces Kendall kernels for full and top-k rankings, including the novel weighted convolutional Kendall kernel. Section 3 presents faster netrixxvvecor multiplication algorithms for Kendall kemnlls, enhancing the efficiency of the proposed bandit algorithm, which is further detailed along with the regret analysis in Section 4. Finally, Sections and 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.
Notations: Let [n] 1.2...., with representing top-k ranking-an ordered tuple of k distinct elements from [n)] For a full ranking (k- = n),, we use a and denote the set of all possible top-k rankings by IT,, with cardinality [T = (n*)). To capture ranking positions, the vector pd R corresponds to full ranking with entry P gives the rank of item i. For top-k rankings, p E R" is similarly constructed by arbitrarily assigning distinct ranks to items not in the top k. For relative ranks, indicator functions pk=y and Pizs denote whether item i is ranked before or after item j. respectively in a. Also, pikj and Piyy are similar indicator functions defined for top-k rankings.
2.1 Kendall Kernels for Full Rankings
Jiao al. [9] showed that the Kendall tau rank correlation coefficient [12] a positive definite (p.d.) kemel 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 02,02 defined as:
kock (01.02) 02) =
M,5011002)
(1)
uk (01, (0),
w((p .D (p,3, .,7)) ())())02))
(2)
where Th.j is if the pair (i,5) is concordant (ordered the same in both rankings) and -1 oth- erwise; concretely, w(p," ), (p?", . p3")
02) piy Pi2; + pi pī3 - p.ts P pis plgj and is the value of positive definite weighting kernel w(..) |n] [n|² x [n] + I that operates on pairs of ranks. The Way adds flexibility and can assign varying importance to ranks, similar to the discounted cumulative gain (DCG) metric [7]. Note that both SK and WK kemels
p.d. and right-invariant with respect to II [10]. In other words, they compute similarity based only on the relative ranks of pairs, not the labels of items, as clearly evident from Equations and 2.
2.2 Kendall Kernels for Top-k Rankings
Weighted Kendall and Convolutional Kendall (CK) kernels. To adapt the WK kernel from full rankings to top-k rankings, Jiao al. [10] set the weighting function wri,, 0 02) to zero either item is not in the top-k of either ranking. While this approach yields a p.d. kernel, it disregards
3

---

items outside the intersection of top-k rankings. In contrast, the convolutional operation provides an alternative for adapting the standard Kendall kernel top-k rankings.
Let Br denote the set of full rankings consistent with the top-k ranking æ (i.e., for every item in x doa E Bx P ). The convolutional Kendall kernel can be defined as follows:
Bock (TI, T2) =
Σ
aa (01, 02),
B BB.l. Bma 01EBa1 02E
where k* is the standard Kendall kernl. Since the CK kernel is convolution of another p.d. kernel, it is also p.d. kernel [5]. Unlike the WK kernel for top-k rankings, the CK kernel accounts for items not both top-k rankings. However, computing the CK kernel is expensive, requiring exponentially many evaluations of the kernel k** 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 म and m2 E II::
tock T1 T2)
1
Σ
1 (011 02),
(4)
[x
af B
where tank represents the weighted Kendall kernel for full rankings 01, E II"
The proposed WCK kernel combines the flexibility of differentially weighting ranks among the top-k items 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 convolution of a p.d. kernel, it is also p.d. kernel. However, computing the WCK kernel remains challenging, as requires exponentially many evaluation of the back kernel, as given in the RHS of Equation 4. To address this, we focus on specific form of rank weights the lank kernel, called as product-symmetric rank weights:
Wpe ((1151)) (22.5))
(ii. (2()
(5)
where, w. (i. [m] x [n] H IR is symmetric function, i.e., w.( (i.j)) = ws(j. (j. f). Notably, the WCK kernel can be computed efficiently for the case of these weights (see Claim below).
The WCK kernel, even with the relatively simple wps weights, exhibits notable proper- ties, as shown Table 2. In this table, we use (i.j) Tog(E+1) Tog(F+Tj inspired by the DCG metric commonly applied in recommendation systems [7]. Notably, the WK kernel ranks rankings with no over- lap (mo and Ti) as more similar than two rankings with the same items in reversed or- der (To and т2), indicating a clear pathol- ogy. Further, the CK kernel fails to dis- tinguish between reversed pairs at different ranks (kek (No: π3)= = ce (ma, T4)), present- ing another limitation if known variants of Kendall kernels for top-k rankings. By us- ing product-symmetric ranking weights, the WCK kernel addresses these shortcomings, providing more nuanced similarity compar- ison for top-k rankings.
Table 2: Comparison of Kendall kernel similarities for top- k rankings. The table shows kernel values ((TTa for the top-k ranking Wo [1, 2, with other rankings (MT, Ta. and
Rankings are arranged left right by increasing similarity to To- The similarity values provided by the proposed kernel increase from left to right as expected, demonstrating the desirable behavior of the WCK kernel with DCG rank weights, unlike other variants. kernels are unit-normalized. See text further details.
Ta, RT)
Top-k Kernels
π [4,5,
[3, 2, 1]
[2, 1,3)
[1,3, (.22
WK
0.00
-1.00
0.33
0.33
CK
-0.60
0.60
0.87
0.87
WCK
-0.88
0.09
0.46
0.87
Claim 1. The weighted convolutional Kendall kernel (Equation 4) with product-symmetric rank weights (Equation can be computed O(k2) time.
Appendix provides the proof that leverages the structure of product-symmetric rank weights Wis to establish the existence of feature representation for the WCK kernel, 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 (k2) time (Algorithm 2 in the appendix). Similar to the result of Jiao al. [9] for the CK kernel, this approach avoid exponentially many evaluations of b 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-men vectio-mullipliications (MVMs) with the kernel matrix [3]. This section introduces fast algorithms for kernel MVMs by exploiting the implicit structure of Kendall kernel matrices.
Let nnvm(xx,) denote the runtime required multiply the t kernel matrix Kx, (1e my)mmaaaxxx by any admissible vector. In the naive approach, this runtime is mvm (XX;) = (tt)). However, if k(,;,, and 6² (xy) are sparse and contain only z non-zero entries, then mvm (Kx,) reduces to O(z t), which is a significant improvement over O(t²) when 2 < t. When dt Φ", we refer to 6 as the linear feature vector for the kernel k. Before focusing on top-k ranking kernels, we provide linear feature vector for the WK kernel on full rankings (given earlier in Equation 2).
(x;)) (T"((z)) for any arbitrary z; and v., where the vectors of (x;)
Claim 2. Let (5 (a) II + (R( be vector indexed by unique item pairs (i. defined as: 2 (o)
1
w..pp. (ples p(>;))
where is the symmetric weighting function in linear feature vector for the weighted Kendall kernel with product-symmetric weights Wps.
weights. Then, dh is
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 feature vector for the top-k ranking kernel is sparse; specifically, the feature vector 6=* (π) contains only O(k2) non-zero entries due to the WK kemel''s focus on item pairs within the top-k. Consequently, the runtime for mvm x.) in the WK kernel matrix is reduced O t).
Moving forward, we focus on deriving 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 lin- car features from its constituent kernel. Specifically. EgeB, wook (ar forms feature vector for the WCK kerel,, which follows from Equation and However, computing this feature vec- tor explicitly is computationally chal- lenging, as it requires summing over all o E By, which includes an expo- nential number of terms, i.c., OnnF).
Claim 3. Let gwok II R(2) be vector in- dexed by unique item pairs (i,5) given as: swek (π) ==
VG) w (TT) (pT<j pizs), where w (T) is determined as follows:
W. w.(P (p. PJ) P E [k]
& p E [k]
w. (P. else if P. E kk] & pj $ [k]
w.eck (T)
w. (P else if p. & [k] & P [k]]
otherwise,
where W. denotes symmetric weights and we(k, n-k Ej= w.(L.j)- Then, the vector qwekk a lin- ear feature vector for the WCK kernel kock, By uni- formly setting w.(:.)) = the definitions above, soock (π) specializes linear feature vector for the CK kernel.
In response to this challenge, Claim shows that the summation can be com- puted analytically and provides ex- plicit linear feature vectors for the WCK and CK kernels. also shows that week has only O(k2 + 2nk) non- zero entries among its O(n?) total en- tries. Consequently, mvm(Kg for
5

---

the WCK kernel requires O((k² + 2nk) f) operations, which improves from O to linear in t. However. this introduces a dependence on n, the number of items, which poses serious limitation and is beneficial only when Σ f. In the following theorem, we leverage redundancy in gack to eliminate this dependence on n, leading to the following main theorem about the mvm(Kx,)
Theorem 1. For the WCK kernel with product-symmetrt weights Wps. the computational complexity of multiplying the kernel matrix Kx, with any admissible vector is Okk2t), i.e., mvm Kx, Okk2t) where Xt is any arbitrary set of top-k rankings.
Appendix A provides the proof in two steps. First, we utilize the values of swek from Claim 3 and categorize ojtck (T1)² (uock based on item pairs, as summarized in Table 4. Next, we show that only five combinations yield non-zero values, i.c., & (T1)² quck (m²) Σ -i=1= (1(11, T2). Each term (T( T22 is dot product of vectors 6c &a (mT )" ("'d p (122). which contains at most O(k2) non-zero entries. Thus, for the WCK and CK kernels, (xm((x,) = O(k²t), since these vectors across all five terms include only O(k2) non-zero entries. Consequently, Theorem 1 demonstrates that employing these vector representations for top-k rankings leads to faster MVMs, i.e., mvvm(xx)) (l22)) (112).
4 Proposed GP-TopK Bandit Algorithm
In this section, we begin by formally defining the top-k recommendation problem within bandit framework and introduce generic contextual bandit algorithm, detailed in Algorithm 1. We then explain how the components of the algorithm are instantiated using 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 finite c-dimensional space, i.c., C _ RR In the g round, we receive a context C₁ E C and select a top-k ranking म E 11 Subsequently, noisy reward // f(c,, xx) + e is observed, where f is the true reward function and is round-independern noise. The regret is defined Ft max TT f(e, π f(c,, me), with cumulative regret Ry Σt rr. The accumulated data the th round is D. (c,, ny y:) Below, the Algorithm 1 provides provides a generic schematic of the bandit algorithm.
Algorithm Contextual Bandit Algorithm for - Recommendations
Input: Total rounds T. initial reward model Mo. and acquisition function AF. / 1,... _Tdo do
1: for
2: Observe context C₁ from the context space C.
3: Select a top-k ranking ne that maximizes AF(M,11(Ce T)) for the context Ct.
4: Obtain the scalar reward y/.
5: Update the reward model M, using the accumulated feedback De.
end for
We aim to design the components of above Algorithm I with the objectives of minimizing cumulative regret and ensuring computational efficiency. It requires two key components: (a) a reward model M, that estimates the reward for any context and top-k ranking utilizing the accumulated data D, and (b) an acquisition function AF for selecting ni given the reward model M, and observed context c,
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 distribution over functions f. i.e., f ~ (0, +)), where k is product kernel function over both contexts and top-k rankings (C X 11*). Specifically, the kernel function & is defined as follows:
(6) where (c) (2) = of 02 is the dot-product kernel and ke" is a kernel for top-k rankings. We use variants of the Kendall kernel for k" from Section 2. Updating the reward model M, at the tth
k((C1, nI), (c2, m²)) = (c1, C2) k (T1, T2).

---

round involves adding new data points to our GP regression, which is computationally inexpensive compared to the fine-tuning steps required by parametric models 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 is AF(M,((c, m)) = fr +))+ -a s) r)), where a f)
Vky ((C,, F), (c,, r]] and 3 controls the trade-off between exploration and exploitation. Here, "DiD and y are the GP posterior mean and covariance functions, as detailed in Section B.1. At the thh round, the algorithm selects the top-k ranking II that maximizes AF(M((C x)), 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. other words, updating Mr. i.e., in the Line of the Algorithm requires only updating the list of accumulated feedback data D, 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 1.1, computing the GP variance term for evaluating AF, i.e, a f (((,, x)) involves solving
[Kx, + =² for a vector V, where X, = [(c,, mI), ... (Ca, TT)]- Naively, this operation requires (tt²) time per round, amounting to total O over I'' 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 of This applies to WK, CK, and WCK top-k ranking kernels, where E 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)) to O This is substantial improvement, as even a single MVM with the matrix Kx, using the full kernel matrix at each round would require (TT)) 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.
Regret analysis. The cumulative regret is R Et= max en fle,, TT) --f((c. me), where nt the ranking chosen at round f. 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, == C X I for below assumptions.
Assumption X is finite, meaning that only finite contexts are considered ((C) < xi), and the reward function f is sampled from the GP prior with a noise variance of
Assumption 2. X is arbitrary and the reward function i has bounded RKIIS norm for the kernel ki i.e. |1/l|, < B. The reward noises e 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 hold, setting Be as 2 [C].| +
66
and 300 In (t) respectively. the cumulative regret Rr of the GP-TopK ban- dit algorithm for top-k recommendations can, with at least - probabiliiy, be bounded by O(n/C,TTc(lgCC)-- log(TT272/6)) under Assumption 1, and
300n²c² (T/8)T) under Assumption 2. Here, C1 ToR(1+e Tj. and O excludes logarithmic factors related to n, k, and T.
Appendix B.4 provides the proof, leveraging the insight that log + Kx,, for any set Xr can be effectively bounded using the finite-dimensional feature vectors introduced in this work.
7

---

Specifically, Proposition 2 utilizes the feature vectors from Section 2. Building on Proposition 2. Theorem 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 by factors of 1/2-1 and = under Assumptions and 2, respectively, compared to Srinivas et [27]. This improvement is substantial even for small values of k, such as k = 6, as shown in Table 3.
Table 3: Comparison with Srinivas ct al. (2010) on regret bounds for the bandit algorithm under both assumptions. Definitions of notations provided in the main text.
Assumption
Srinivas et al. (2010)
Proposed GP-TopK Algorithm
(
δ n CITT [log[]| + log
r2n²
[log[C] log
T2p2
63
Assumption 2
Srinivas et al. (2010)
This work
ò VoTe (2B² 300n/cln 300n (4)
Ô (n/CaTe(222 30 (z))
5
Experiments
This section empirically evaluates the proposed GP-TopK bandit algorithms for the top-k recom- mendations using simulation based the MovieLens dataset [4]. The reliance 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 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 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 context embeddings, while the item embeddings remain hidden. In the non-contextual setup, the first user from the dataset is chosen as fixed context throughout the bandit algorithm run, allowing us use the same reward functions the contextual bandit algorithm.
For setting up the reward functions, we utilize a similarity function s(c. 0) = <(a (c" b) to measure similarity between any user and item embeddings, where and b are similarity score and shift scalars, respectively. The sigmoid function ş maps similarity scores to a range between and 1, enhancing the interpretability of the reward signal [31]. We set 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, (c 7) Ei= long(=-T) (c, 0x where and 0z, represent the context and item embeddings, respectively. The second is the diversity measure, fa) Σ. Σ}= 0" On,. 0r,
These metrics quantify the relevance and diversity of top-k recommendations, respectively.
We use these functions two contextual reward settings. The first setting focuses on normalized- [7]. The second setting combines fudcy and fav as Indogdii (c, π) = - (c, T) + A) fan (T), evaluating the aggregate effect of relevance and diversity. We set = 0.75 to emphasize relevance over diversity.
DCG (n-DCG), fndcy(,, TT) max,/ fag(c,a))
(a,(0,5)
Evaluation for small arm space. This section presents empirical results for the cumulative regret of bandit algorithms with a limited number arms. Specifically, with n = 20 and A = 3, there are 6, 840 top-k rankings, allowing for exhaustive search to optimize the acquisition function. All bandit algorithms run batch mode, updating every five rounds. We consider both reward settings for contextual and non-contextual scenarios, using subset of five users for the contextual setting.
8

---

Several baselines are set to assess the benefits of ranking (Kendall) kernlls. Section C details the remaining configurations and details of other baseline bandit algorithms.
400
Bandom
Eggreedy
d 220
350
OK
WCK
100
700
10
10
100 T
200
T
(a)
(c)
Figure 2: Comparative evaluation of bandit algorithms: The cumulative regret Hr over T rounds is shown. Lower values indicate better performance. Plots (a) and (b) represent non con-contextual settings for nDCG (fudz) nDCG diversity (ukplte rewards, respectively. Plots (c) and (d) show results for contextual settings for five users using the same rewards. The y-axis for (a) and (b) is on the left, and for (c) and (d) on the right. The GP-TopK algorithm with Kendall kernels, especially the weighted convolutional Kendall (WCK) kernel, outperforms others. Details other algorithms are in the text. Results averaged over six trials.
The Random algorithm randomly recommends any k items. The c-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, c-greedy differentiates arms for each unique context. Similarly, MAB-UCB conceptualizes each ranking as an independent arm, an equivalent of using direct delta kernel approach for GPs along with UCB AF. In contextual scenarios, MAB-UCA 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 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.
Evaluation for large arm space. We evaluate bandit algorithms in a large arm space scenario with 50 and & = 3 and A = 5, resulting 10 and top-k rankings, respectively. Using local search, we focus on the nDCG reward. The remaining configura- tion is consistent with the small arm space setup. We use 10 restarts and steps in each search direction for the local search, starting with 1000 initial candidates.
1600
Random
e-gredyy
10 possible
WK
800
WCK
%
100
Figure 3: Comparative evaluation bandit algorithms for large arm spaces, with > 1.1 x 10" arms for the left plot and > 1.1 x 10a0 arms for the right plot. Cumulative regret with respect to the rounds of the bandit algorithm depicted. Results averaged over six trials. both settings, the WCK approach outperforms other baselines. more details, see the textual description.
Figure 3 shows that the regret for the GP-TopK variants remains con- sistently lower even with a large arm space, despite the use local search. The WCK approach significantly outperforms the CK, es- pecially for A 5, illustrated in the right plot of Figure 3. Additional empirical results on the effectiveness of local search large arm space and other rewards are given Appendix C.
6 Discussion
This work develops contextual bandit algorithm for top-k recommendations using Gaussian pro- cesses with Kendall kernels in a full-bandit feedback setting, without restrictive assumptions about feedback 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 kemnels tailored to top-k rankings, resulting in a faster inference algorithm that reduces complexity from ((74) to O(T2). 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 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 matrix- vector multiplication with Kendall kernel matrices 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 delayed feedback, would enhance the applicability of this work to more complex scenarios. Extending the finite- dimensional 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 plat- forms, promoting content relevancy and engagement. However, they may reinforce implicit biases in training data, limiting content diversity and entrenching prejudices. Therefore, monitoring over time essential when deploying these algorithms in real-world environments.
References
[1] Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. Multi-objective bandits: Optimizing the generalized gini index. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 625-634, PMLR, 2017.
[2] Aryan Deshwal, Syrine Belakaria, Janardhan Rao Doppa, and Dae Hyun Kim. Bayesian optimization over permutation spaces. In Proceedings of the 25th Conference on Artificial Intelligence (AAAI), pages 2515-6522 2022.
[3] Jacob R. Gardner, Geoff Pleiss, David Bindel, Kilian Q. Weinberger, and Andrew Gordon Wilson, GPyTorch: Blackbox matrix-matrin Gaussian process inference with GPU accelcration. Advances in the 31st Neural Information Processing Systems (NeurIPS), pages 7576-7586, 2018.
[4] Maxwell Harper and Joseph Konstan. The Movielens datasets: History and context. In Transactions on Interactive Intelligent Systems, volume 5, pages 1-19. ACM, 2015.
[5] David Haussler. Convolution kernels on discrete structures. Technical report, Technical report, Department of Computer Science, University of California Santa Cruz, 1999.
[6] Yifan Hu, Yehuda Koren, and Chris Volinsky. Collaborative filtering for implicit feedback datasets. In 8th IEEE International Conference on Data Mining (ICDM), pages 263-272. IEEE, 2008.
[7] Kalervo Jarvelin and Jaana Kekalainen. Cumulated gain-based evaluation of ir techniques. In
ACM Transactions of Information Systems, volume 20, pages 422-446, 2002.
[8] Olivier Jeunen and Bart Goethals. Top-k contextual bandits with equity of exposure. In Proceedings of the 15th ACM Conference on Recommender Systems (RecSys), pages 310-320, 2021.
[9] Yunlong Jiao and Jean-Philippe Vert. The Kendall and Mallows kernels for permutations. In Proceedings of the 32nd International Conference on Machine Learning (ICMI., pages 1935-1944 PMLR, 2015.
10

---

[10] Yunlong Jiao and Sean-Philippe Vert. The weighted Kendall and high-order order kernels for permu- tations. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 2314-2322. PMLR, 2018
[1]] Michael N. Katehakis and Arthur F. Veinott. The multi-armed bandit problem: Decomposition and computation. In Mathematics of Operations Research, volume 12, pages 262-268, 1987.
[12] Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81 1938.
[13] Bart P. Knijnenburg, Martijn C. Willemsen, Zeno Gantner, Hakan Soncu, and Chris Newell, Explaining the user experience of recommender systems. In User Modeling and User-Adapted Interaction, volume 22, pages 441-504, 2011.
[14] Andreas Krause and Cheng Ong. Contextual gaussian process bandit optimization. Advances in the 24th Neural Information Processing Systems (NeurIPS), page 2447-2455, 2011.
[15] Matevvz Kunaver and Tomavz Povzrl. Diversity in recommender systems survey. In Knowledge Bused Systems, volume 123, pages 154-162, 2017.
[16] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 767-776. PMLR, 2015.
[17] E. Lex, Dominik Kowald, Paul Seitlinger, Thi Ngoc Trang Tran, Alexander Felfernig, and Markus Schedl. Psychology-infone Information Retrieval, volume 15, pages 134-242, 2021.
recommender systems. In Foundations and Trends in
[18] Zeyang Liu, Yiqun Liu, Ke Zhou, Min Zhang. and Shaoping Ma. Influence of vertical result in web search examination. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 193-202, 2015.
[19] Changyong Oh, Jakub Tomezak, Efstratios Gavves, and Max Welling. Combinatorial bayesian optimization using the graph Cartesian product. Advances in the 32nd Neural Information
Processing Systems (NeurIPS), 2019.
[20] My Phan, Yasin Abbasi Yadkori, and Justin Domke. Thompson sampling and approximate inference. Advances in the 32nd Neural Information Processing Systems (NeurIPS), 32, 2019.
[21] Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its applica- tion on diversified online recommendation. In In Proceedings of the 2014 SIAM International Conference Data Mining, pages 461 1699, 2014.
[22] Carl Edward Rasmussen. Evaluation of Gaussian processes and other methods for non-linear regression. PhD thesis, University of Toronto Toronto, Canada, 1997.
[23] Carl Edward Rasmussen. Gaussian Processes in Machine Learning. In Advanced Lectures on Machine Learning, pages 63-71. Springer, 2004.
[24] Idan Rejwan and Yishay Mansour. Top-k combinatorial bandits with full-bandit feedback. In Algorithmic Learning Theory, pages 752-776. PMLR, 2020.
[25] Yunus Saatçi. Scalable inference for structured Gaussian process models. PhD thesis, University of Cambridge, 2012.
[26] Dong-Her Shih, Kuan-Chu Lu, and Po- Yuan Shih. Exploring shopper's browsing behavior and attention level with an eeg biosensor cap. In Brain Sciences, volume page 301, 2019.
[27] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning (ICML), pages 1015-1022, 2010.
[28] Hastagiri P Vanchinathan, Isidor Nikolic, Fabio De Bona, and Andreas Krause. Explore- exploit in top-n recommender systems via Gaussian processes. In Proceedings of the 8th ACM Conference Recommender Systems (RecSys), pages 222,,23,40 2014.
[29] Richard S. Varga. Geršgorin and his circles. 2004.
[30] Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits, In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 51 14-41122, 2018.
[31] Yingfei Wang, Hua Ouyang, Chu Wang, Jianhui Chen, Tsvetan Asamov, and Yi Chang. Efficient ordered combinatorial semi-bandits for whole-page recommendation. Proceedings of the 20th Conference on Artificial Intelligence (AAAI), volume 31, page 2746-2753 2017.
11

---

[32] Yue Wang, Dawei Yin. Luo Jie, Pengyuan Wang, Makoto Yamada, Yi Chang, and Qiaozhu Mei. Beyond ranking: Optimizing whole-page presentation. Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, pages 103-112, 2016.
[33] Christopher K. Williams and Carl Edward Rasmussen. Gaussian Processes for Regression. Advances in the 9th Neural Information Processing Systems (NeurIPS), pages 514-520, 1996.
[34] Dong Xin, Jiawei Han, and Kevin Chen-Chuan Chang. Progressive and selective merge: computing top-k with ad-hoc ranking functions. ACM SIGMOD Conference, pages 103-114, 2007.
12

---

A Kendall Kernels for Full and Top-k Rankings Omitted Details
This section includes the proofs that were omitted from Section 2, presented the following order:
In Section A. we present proofs for Claims and 3, which concern the feature representa- tions of Kendall kernels.
In Section A.2, we provide Algorithms and proof of its correctness for computing the WCK kernel in (A-²)) time, thereby proving Claim 1. Additionally, extend this proof to cover the proof of correctness for Algorithm 3, which can compute the CK kernel in Ok log k). initially introduced by Jiao al. [9]. The original paper presented the algorithm without formal proof of correctness, 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 given for computing the WCK kernel for top-k rankings.
A.1 Feature Representation for Kendall Kernels for Top-k Rankings
This 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 ou (o) II + (R())
be vector indexed by unique item pairs (i,5), defined
(a) = w.(pp.pp) (pics pizs), Pig
rok
where We is the symmetric weighting function in product-symmetree weights. Then, de is a weights Wps.
linear feature vector for the weighted Kendall kernel with
Proof. Following the definition linear feature representation, we need to prove that bank (01 02) = ((a1)* ((02) for the product-symmetric weight kernel as given in Equation 5. Recalling from Equation 2, we have wk (01, .2) as follows:
b (01,
w((p.' (p, (p?".,)))) m2)(01,02)
W. (P. p5t) wp (p²)) ()(0))00))
where the second line incorporates the use of the product-symmetric weight kernel. Next, our focus shifts to the simplification of nh (T, o2), which is elaborated as follows:
[N.(01,02) -Picj P.2, + P3) P33 p.2j P33 p.3 p?2
=P22 (P12) p(3) + p. (p:3) p12,),
(p - p(s)) (p12) p(3)).
Combining the above factorization of myy with Equation 7, we get:
kook kw (01,02)
W. (p. ,P') ",,"),,)),,,"........ (p. (p22, p(3,) (pf2, p,3,)
13

---

oi (0)) (02)
(2)
= o o(02).
Claim Let duock (Ir) II R(()) be a vector indexed by unique item pairs (i. given as: doec (T)
wek (T) (p%= piy,), where weck (T) is determined as follows:
(. p3 P E [K] & Pj E
wp(P else if p E [K] & p $ [+]
w wokk (TT)
w. (P else if p. $ [K] & Pj E [k],
otherwise,
where We denotes symmetric weights and w. wo(e,-) n- n Lijk+t Wg(L,j). Then, the vector ruok is a linear feature vector for the WCK kernel kwok, By uniformly setting wa(::-) = 1 in the definitions above, &rek (x) specializes to 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 demonstrated in Claim 2. Recall that the WCK kernel
that k. (01, 02) onh (a1)² & requires double summation over pairs of rankings from Bx, and B 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:
Buck (Tick
(TT, TT) =
1
Σ
Σ
Suck (o1) (uk
Bzy
Brzz
B
dukk (o1)²
Σ
(o2)
BBR
[Baal
oiE
az Baz
[dwcc((TT))
rock (T)) wuek (T2)
The simplification above reveals that the feature representation, guck, for the WCK kernel, is a (*) dimensional vector and can be indexed by unique pairs of items (i, much like the oank 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 we examine the scenario where items 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: po [k] and p [k].
(
wokk (TT)
(p, p,)) (p - -Pi-))
B
oE B
1
1
w. (p. .P))
Σ plaj Σ pizs
B
Br
14

---

w. (p. ..). (Brrl .i<s - -Bxl .P3.))
[x
(2)
1
ws(p? .P) (pics p(3))
(8)
The simplification in lines 3rd and 4th follows from the fact that any full ranking a E Bg, consistent with the top-k ranking ı, the relative ranks and weights of items and j remains unchanged, given P E [k] and p E [Re]. Concretely, this implies Picj Pikj for all E B, and similar with the other term.
In Case 2, we analyze when item is in the top-k ranking while item j is not.
Case 2: p. E [k]] and p
& [
wock Pin
(T)
w. (p/. ()) (pl=) - pi>j)
B
B
Σ oEBr
W/ (Pf DJ) (1 - 00 (since p E [k]] and p. & [R])
[x
Σ oEB,
w. (P PD)).
[
Next, every possible consistent ranking is considered jointly while fixating on specific rank outside top-k elements, leading to (n - k 1)! different rankings. Given that |Bx = (n k)!, we can refine the above expression follows:
wuck P.j
(T)
W. (P. (n k 1)!
B
1=
(n
1)!
W. (p,,1)
Bx
1=
(=k+1
W. (p..
In Case 3, we analyze when item is not in the top-k ranking while item j is.
Case 3: P. & [k] and p E [k]. Similar to case 2, the simplification follows analogously, with the only change being Ip?c, 1r,,, -1 instead of 1. Thus, by symmetry between and j, have the following:
-1
wuck (T)
wo( P3)
(p),
(using symmetry of w.).
(10)
Lastly, in Case 4, we analyze when items i and j are not in the top-k ranking.
Case 4: Pp & [k] and P & [k].
wook (Tr) |B O
Σ
suck (o)
oe
15

---

wi (P (p. (D))) (pic) -P(s))
B
0 (by symmetry).
(11)
The result of zero arises from symmetry. Since P and P are not in the top-k ranking, they are treated symmetrically the summation overall rankings in B, For any ranking o, suppose p I and P = m, there exists a corresponding ranking o' such that only the items and are swapped. Therefore, jointly, these two rankings yield w,,(, m) and (w,(1, m.) Since wA 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., & (T) VG)
w wek (TT) (pi<y p}>y)) for all unique
pair of items. From Case 4, we have O(n - =) entries leaving max only O + 2nk) non-zero entries.
A.2 Algorithms for Computing Kendall Kernels for top-k Rankings
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 Section 1 for valid both the correctness and computational complexity of Algorithm as given earlier in Claim 1. Following this, Section A.2.2 revisits Algorithm 3, initially introduced by Jiao al. [10]. The original publication presented the algorithm without formal proof of its correctness, which we rectify and offer in Section A.2.2.
A.2.1 Efficiently Computing the Weighted Convolutional Kendall Kernel
This section provides a proof to Claim 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(k2) time.
Proof. The claim is proven through Algorithm 2, where we establish its correctness and demonstrate its computation requirement is O(k2). The essence of our proof centers on analyzing the feature representation of the WCK kernel, dueck, as outlined in Claim 3. The feature vectors of dock
reside in a (() 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 kackk (T1 m2) wacck (II) )T druck (T2). This involves summation over item pairs, expressed as kwck (TrI, (TI, 722
Etem Pi,m ( dxpck (Tz2).
Our proof analyzes various scenarios: cases where pairs of items, namely 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 wack [TT, 72) Din s: (T1, N2), and each s; 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 given in Equation 5, where, w, : [n] [n] + R" and its one-dimensional marginals are w., nー n Ej=k+1 (.({.j Table 4 shows how these cases are organized and relate to different 8t 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 I Ig.
16

---

Case
Description
Both items (1, m) in 11 U 12. Branches into the following three sub sub-cases based on the presence items I1 I2:
1-a: Both items in /1 n 12. The concerned term is 81.
1-b: One item I I2. Subdivided into 1-b-i (other in I2) and 1-b-ii
(other in 1 11): concerned terms are 82 and 83-
I-c: No item 4 n 12. Addresses cases where / and m are in different sets
(41 12 12 and 12 \ 41); concerned term is 54.
2
One item in 1 UZz. Lee., either 7 is 1 UT2 or is in 1, U12 leading to sub-cases
2-a and 2-b; concerned term 85-
3
No item in 1 U 1z. Addresses the scenario where neither / nor m is in 11 U U1;
value trivially zero.
Table 4: Case categorization for proof of Algorithms and based item pair ranks, where and I2 are the sets of items for top-k rankings тH and æ2, respectively.
Definition Algorithm 2 and 3 and utilize following notations.
I and l2 are the sets of items in rankings Tı and T2. respectively.
σ E IIl4al and Tı IIlinnaal are the full rankings of 1n and 1 n 12, both consistent with the input top-k ranking Le., relative ranks of items is same yielding Vl, E Ii 12, p = pi>.
Analogously, d2 and T2 are constructed utilizing the set 12 and ranking
Algorithm Computing Weighted Convolutional Kendall Kernel
Input: Two permutations T1, T2 E II Ranking weighting function ws [m] x [n] + IR" and
its one dimensional marginals are (,, -ーニ ビ5= W. (f,
Output: Convolutional Weighted Kendall kernel w (T,
Let I1 and I2 be the sets of items in rankings and respectively.
1: if n Igl 2 2 then Eigkemgaltmeeinn (. T1 p..) w.(p," T2 . m. (T1, T2)
(1 T2)
(2)
3: end if
ir [ 1 and 41 121 1 then
52( T2)
w. "p P w.(p." (pfem pm)m) mehn
Σ
end if
if I n 2 and L2 2 1 then
8: sa(TI, T2)
Σ
w. (P,",, ..) w.(pp', ,p:) (pTem p(
end if
10: if I 12 > and
12 h1 then
11: 84(T1, T2)
Σ
w.(p,' .:) ..(p....)
(G)
1ET, V2 mEAM
12: end if
13: T
and
[M] \ (4 U 12)
2 then
14: m2)
(n [h U 22) Σ w.(p"", .)) (p."..)))
lehnn
15: end if
16: pack (11, T2) = $1 (T,, T2) + S2 (1, m2) + ST(TT, T2) + s1(m1, 12) + ss (T T2)
Case The pair m) E T2 falls within the top-k, leading to three distinct cases. Below, we provide s; terms for each case given in Table 4.
17

---

Case 1-a: Two items in 11 n Iz. meaning both I and m belong to I1 n Iz. Using Claim 3 regarding the feature vector of quck we simplify 51 as follows:
81 (T1, T2)
E
pi (T1) siack (T22)
(T1)
Σ
We(p"" " . (picm - pism)
v (3)
IglcmSnll.mElin
W. (P ppm) (picm p?
1
W. (p pm (p, T2 Pm)) (T T2).
(12)
IslcmSallmm/ink
When one item is in 4 12 the other must reside either in 41 \ 12 42 41, thus leading to two distinct sub-cases. This is specified in Table 4. Concretely, if the other item is in I1 Iz, contributes to the 82 terms, whereas if it's in I2 I1 contributes the $y terms.
Case 1-b:
Corresponding to Case 1-b-i, when the other item in Ii 72, i.e., 82 is the term corresponding to indices where / is in I 0 12 and m in Ji \ J2 or the reverse, represented by partial sums and v. For the partial sum u, with in n 1 and m I \ T2, we find that p Th in [k), while p not. The simplification of proceeds using Claim 3 as follows:
Σ
w. (p pm.) (p7cm p7))m)
Iglmmnlleennaalmee V2
W's (p,², (P pisml
Σ
W. (P(P P..)) w. (.(pp,)))) (pi
p()m)
Similarly, the partial sum be simplified follows:
Σ
w. (p pm)) (p p75
IslcmEn WE
w. (pT (pTe pP3m)
Σ
(P(p"' pm u. (pT",) (p7c.. - -P7m))
Σ
(p 1) us (p (p pm>1)
IgmelsnllAinne m
Σ
w. (p Ti P..) w. (p)",)) (p
p.3m).
I meh
In the above, the first two lines use results from Claim and use similarity of w.. In the following line, and m are exchanged. Lastly, the negative sign is pushed into the indicator functions to make the summand function this partial sum v similar the partial sum u, and the similarity of the w, is utilized. The above partial sums simplify as follows:
82 (T)
Σ
(.(p"' T1 P.:) w. w, (pT p)3
(13)
lehnglmm//i
18

---

Analogously, in Case 1-b-ii, we deduce the corresponding term for the pair of indices as described Table through symmetry. Specifically, the Sg can be outlined as follows:
(T T22
E
ws(p w/ (p) Pm)) (pk2m
(14)
IEhn
Both items are outside I 12, specifically, E In \ 12 and m E 12 \ I or the reverse. Like Case 1-b-i, we divide 84 into partial summations u and v. Now, we calculate u under the condition that E 11 12 and m E l2 \a).A.
Case 1-c:
E
1 (P') (pT),)) (p7 -ismm)
41
IgIemEn/EE MalmElA
w. (pm T2 :) (plcm pism)
Σ
w.(P T1 : (1 .)) 0) w. -0 11);
Islemmnjiel Valme
Σ
(P(P (P
Iglemgnliedi Vaaaennieeeiiiaaaaaa.. Ja
Similarly, estimate partial sum for the set I E 12 h & m T1 Iz. Using calculations
similar to Case- 1-b-i for summing u and U, we have:
sa(T1: T2)
Σ MELAAM
WP(P .)) w. (P
(15)
Case 2: One item exists in In T2, the other in [n] \ (2))) I2). branches into sub-cases: Case 2-a with one item I, U I2, and Case 2-b, where one item outside I n 12 but is in J U Focusing on Case 2-a, represented by 85, simplify follows. This involves index scenarios, either
I E I n 12 and m & Ii U 12 or vice versa, represented by partial sums u and v. We now simplify below:
Σ
1
w. (p,",,)) (pp) pm3m)
IslemEn
(p "2 (pizm -P/
Σ
wa(p"' (p(pp",.),
I teinnaalaan
Σ
w.(p w.(pp,)) - (nn (n- [1 U I2)).
Using steps similar to the previous case, we get the following value for 85!
85 (T T2) = (n ILUb)
Σ w.(pp")) .)) w. (p,,))
(16)
lETina
For Case 2-b, or m are absent from I or Iz, leading to two sub-scenarios. Consequently, either 6lock (Ii) ) is zero oyock (T2) is zero. Therefore, these terms don't contribute to the overall WCK kernel value.
19

---

Case 3: No item is in the top-k, i.., both I, m & I1 U Iz. As both items are absent from the top-k in either ranking, the value trivially reduces zero.
After covering all configurations of and m, incorporate results from Equations 12, 13, 14, 15, and 16. This integration yields the expression b-ack (m1, T2) Σ 8y (T T2), where, each term 8; matches precisely with its corresponding expression in Algorithm 2. The proof for the correctness of Algorithm is complete, as each term s; corresponds its respective expression in the algorithm. Regarding the time complexity of Algorithm 2, each term 8; sums at most k2 quantities, and each quantity summed can be computed ((1) time. Therefore, the computation time required for Algorithm 2 is (
A.2.2 Efficiently Computing the Convolutional Kendall Kernel
This section provides Algorithm for computing the convolutional Kendall kernel, as specified in Equation 3. Later, its efficiency and accuracy are proved in Claim
Algorithm Computing Convolutional Kendall Kernel [10]
Input: Two top-k rankings T1, 72 E II
Output:
Convolutional Kendall kernel kc (T1,
Let T and T2 be the sets of items in rankings m and TT, respectively.
Let σ E 11 and E 1144a be the full rankings of I and 4, n 12. both consistent
with the input top-k ranking TT
Analogously, construct ø2 and 72 utilizing the set l2 and ranking m2.
if [1 T2| 2 2 then
(I( T2) = (3)
(Iinaa)) k (TI, T2)
3: end if
if
[ 2 and I I2 2 1 then Etenni, 2 (1) - k+ 0
5: 82(T1, T2)
6: end if
ir [1. 2 1 and 4g 41 2 1 then
8: s3(T1, T2) (3)
Σ Lignnz 2. (a2(1) r2))) - k + 1h 0
end if
10: (T T2) =
144 12 14 12]
(2)
11: 85(T), T2) -G] |
[|]] (Ti U1)
12: Acck (T1, (21, = (T) + (2 T2) + (3( π2) + SI(TI, (2) + $5(T1,
Claim 4. Algorithu 3 computes the convolutional Kendall kernel (as given in the Equation 3) with a computational complexity of O(k2).
Proof. To establish the correctness of Algorithm 3, we will adopt the same proof approach as the one used for Claim concerning Algorithm 2. Specifically, we will adhere to the earlier categorization in Since the CK kernel can be derived by uniformly setting
Table 4 and notations given Definition the weight function w.( (i, 1, we will insert them in terms as given in Algorithm 2. These cases will be revisited and simplified by applying the condition (i.j.) implies its one-direction marginal weights to be 1, i.e., (,.
Note that this also
Simplifying the 81 Term: For the WCK kernel, Case leads to the expression 81 as stated in Equation 12. In this case, when two items, specifically 1 and m, are both in the intersection I n 72, implies that p. p p 72 and 2 all rank within the top-k, denoted as [k]. We simplify the 8 term for CK kernel as follows:
20

---

$1 (1 T2)
Σ
Ws(P," Th pmm)
W. (p)) .pm) 1m. (T T2)
Σ
nmm (T,, T2)
IslemSn|l.menn
(11n2))) k (n,,
Σ
(m,
(17)
K<l <m'' S<''m's Shhnkl
The simplification process begins by assigning unit rank weights in the first line, i.c., W; 1. Following this, by relabeling the items in n Iz and using πI and 72. which are the rankings of Ti and T2 limited to the set I n 12 as defined in Definition 1, it is established that m WVmmm(T) (T1, T2)
Mi (Ti, T2). This is because the relative order of any pair of items is maintained in Ti and 72- Consequently, this leads to the final simplification to scaled value of the standard Kendall kernel k. as given in Equation 1.
Simplifying the $2 and 83 Terms: The $2 and 83 terms are obtained for Case 1-b, which for case when one item is in I1 n 12 and the other item either in Zı l2 I2 \ IT. We divide this into two sub-cases, Case 1-b-i: The other item is in I1 \ 12, with representing the summation terms derived from the CK's inner product. Case 1-b-ii: The other item is /2 IT, where 83 denotes the summation terms. We simplify the $2 term for the CK kernel as follows:
(2(,
Σ
Cp(PP' T1 ...) Wa(P (p7cm. pP)m)
LET Tehinlamme V2
Σ
(picm
pm3m)
2 LEL nelml Va
Σ
Σ
=
Piam
Pim
2000
Next, examine the terms and in detail, starting with The term u, which corresponds to 21 signifies instances where item / is ranked before item m in the top-k ranking Tı. This can be items are positioned before item in the set 71. Out of these items, (1) also belong to the intersection 11 Iz. This follows from the definition of the full rankings σ and Tı on the set 4 and the intersection 11 n 12, respectively. Consequently, can be concluded that (() Ti (4) items from the set difference 71 \ I2 ranked before item (. The second term, v, corresponds to p.sm and involves a calculation that takes into account the items ranked after the 1-th item the set I. Specifically, there are k o (I) items following the 1-th item. Within the intersection /1 0 I2, the number of items before is given by //, n 12 (4). Therefore, expression (k σ1 (1)) (17, n 72 - (!)) represents the count of elements that are positioned after in the set difference 12
derived from the observation that σ (1)
Combining the above calculations for both terms u and v, the 82 term for the CK kernel can be simplified as follows:
(2 T2) =
Σ
2- (a)())) (1) - k ( 12).
(18)
LEhn
Using the symmetry between Case 1-b-i and Case 1-b-ii, we can simplify sy for the CK kernel as follows:
Sa(TI,, T2) {m)
Σ
2 (az(1) T2())) - + [T 0 Tz)-
(19)
21

---

Simplifying the 81 and Ss Terms: We simplify the sı and $5 terms for the CK kernel starting from Equation and Equation 16, respectively, as follows:
-14 2 122 14> 1
84(T1,
w. wo(p'',) w. (Pm.
(20)
IE V
(T)
1
(n (4
Σ lefinza
ws(p (p(p
11 n 12)
[1
(4 22)
(21)
We have obtained the values of all the simplified 8; terms for the CK kernel in Equations 17, 18, 19, 20, and 21. By combining these terms, we get kock (TI. T2) = Σ 1= (i(T1, π2), where each term & precisely matches corresponding expression Algorithm 3. This completes the proof of the correctness of Algorithm 3. Regarding its time complexity. each term 8; sums at most k quantities, and each quantity can be computed in ((1) time. Therefore, the time required for Algorithm 3 to compute the CK kernel is O(22).
A.3 Fast Matrix- Multiplication with Kendall Kernel Matrix on Top-k Rankings
This section revisits Theorem 1 about the fact matrix- multiplication time for the Kendall kernel matrix for top-k rankings. Specifically, we aim to eliminate the mvm (ym(Kx) (x)'s dependence on the number of items, i.e., 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 Wps. the computational complexity of multiplying the kernel matrix Kx, with any admissible vector is OKk2t), i.e., mvm( (x,) x,,)= = OkkPt), f), where X₁ is any arbitrary set of 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 Okk2) computation. For brevity, write X to represent Xr, and the proof follows for any X₁, ie., any value f, not just T.
As also suggested previously, we will demonstrate through the equation Kx = (0x) TTa where both matrices 4% and 4% have columns with only Okk²) non-zero entries. Consequently, this leads to the computational complexity of matrix-vector multiplication, denoted as mvm(Kx). being O(k2- T).
From Algorithm 2. we know that each entry of the kernel matrix ((T11 can be expressed as sum 1 m2). Assuming each s; (T1, T2) equals da (m1)² ) dh (T2). and considering that all vectors 64 and d² exhibit this property, we can express Kx as (#g) TT Here, the ith row of ($x) )r and the jth column of Φ are represented by [d0) (TT)²* ..... " (T,) )" and [ (my), th (T )]. respectively. Therefore, the overall mvm complexity can be characterized by the sparsity of the vectors 6t and σht, as formalized in the claim presented below.
Claim 5. Consider kernel matrix Kx corresponding any set X of cardinality T. Each entry of K x, denoted 6(x1,22), is defined by the sum Σ 81(11, where each sc(x1, x22 is the result of the dot product d5ts (x1)²² TT (x2), where, ại and Φ² are vectors characterized by having (z) non-zero entries. Given this structure, the matrix-vector multiplication complexity for Kx O(wna T", i.e., mvm(Kx) O(z-T).
Proof. We will demonstrate this in the following discussion by concentrating on the 1tth entry of the output vector, specifically Kxv, v, for any arbitrary vector v:
(Kxv)& Σ (xx(k))) = Σ Σ
(TRR TT)
29 2== Σ
aa (TT,) To (b())) Ug
1=1
22

---

th (Tx) (Tx) (T)))))))
sa tan (Tx))
Σ the Eddl(TT)) (T))()))))))
Given that for all i, 6² possesses only (()) non-zero entries for any Jj. the computation of Ej 6h (TT))y requires (z) operations. This implies that the expression Σ; Sh (TT)) also neces- sitates (2) computation. Applying a similar rationale to Ø", it follows that computing (Kxv)k demands only ((=) operations. Extending this argument to all entries of the output vector, it is evident that computing Xxv requires only (= T) computation
Utilizing Claim 5, it suffices to complete the proof by showcasing that these exist vectors df: and 6h, each with only O(k²) non-zero elements, corresponding to each s; specified in Algorithm Additionally, these vectors ensure that sT(11, (2) d= (x ) (T2). We will next establish such vectors for all terms. Starting with the 81 term below.
Showcasing 81 (m1, m2) = 60 (m) ) (T (m²) for sparse d01 (m) and dd (x2) vectors. We begin by manipulating $1, as defined in Equation 12. For the sake of brevity, their scalar factors will be omitted in the following explanation.
8i (T1, n2)
Σ IscmmnnilmEnml
wP(Pi Pm)) w. (P7" p (T1,,
Σ IslemSnilmEinnk
(P p w. wp(Pp p.) (picm
pimm) (p -P
Σ
(P(PP 21 pm)) (p p(sm) w. (p, Pm) (p7cm -Pim):
Σ
wp(Pp" P (p/))
p 1pp1 1p E(A]
Islemnn
=0 (TTs)
(P To (p/2m
pizmi 1p p ElR
(
(d (x) )² 1 (Tz).
(22)
Both 6th and のه are sparse by design, taking non-zero values only when and m appear in the top-k rankings. This demonstrates the existence of sparse vectors for the 81 term. Next, will establish the same for the $2 and terms.
Showcasing sparse vectors for 82 and 83. We begin by manipulating $2, as defined in Equation 13, while ignoring its scalar factor. We will exploit symmetry between and 83 terms.
2T T2)
Σ
Wa (p (p)) w.(pp"
(pT2m p()m)
Σ
w. (pT
w. (. T1 pm (pTc. - -P7mm)
lElinaa
meliva
Σ (P ,.)
Σ meh
w. (P ( (pizm pimm)
Σ
w.(p.' pit (p p(smm)
Iehina
mehnfa
Σ
PP (P
p. PE(
p.
E(H
Σ
WP T1 P (p p(
1E(m)
meh
= 121 (172
(x1)
23

---

E "s(p (pW p
(p72m
p()m)
(23)
20 ( (T
20 (T2)
Σ
w. .)us
.mm (plam ppim))
ImElint
-a (TT)) )ah 2 (T2) +
Σ
W (P(P 72 1 pm
Lm
Pa2
We (p) 11 Pm) (pism - pl plym)
1 D. pm E(
(24)
fm
(0 (T + p0 (TT)² 1 (T2): (T2):
10 (TT); ( (T2) I 10 (TT))): o ((T2)) = (TI) (T2)
(25)
(x1)
(
Equation 25 demonstrates the existence of vectors d²2 and 2º for the 82 term. The vectors 6oat and 6022, possessing (kk and (k?2) non-zero entries respectively, are defined in Equations 23 and 24. Consequently, the 6d vector has (Ik2) non-zere entries. Similarly, it can be shown that のh contains O(k²) non-zero entries, thus fulfilling the proof requirements for proving the 82 term. For the 53 term, we observe symmetry between 82 and 8y. namely Sy(T) T2) 82 T1). This symmetry makes it trivial to satisfy the requirements, further highlighted by the following equation:
$3( = $2( m1) = -00² (T2) (mT) = - (T2) = (m((m)) (T) (26)
=X)(((T)) =
Showcasing sparse vectors (4( (TI)² (0 We begin by manipulating the 54 term without scalar, as defined in Equation 15.
(1 T2) = Σ
LETIVa
Σ lehi
w. (P(p
Σ (.
Σ wo wp(p
me
mElin
Observing that w = Σ w. (p represents a constant value that does not depend on 1z, we can
meh
further simplify the above expression for $1 as follows:
(1(
Σ ws(P .))
W
Σ
wo(P
1EAV2
mEA
W
w. ws(pp ..)
T0
Σ
(p
tehing
mehins
Σ
wa(p ,))
Σ
+
(p
VEriNa
mEhnta
Σ wc
(P
Σ W.
(p
(27)
lelinaa
Next, to simplify the above equation, we first focus on the second term and have the following:
Σ w.(p...)
Σ
(p
mElinla

---

Σ |E/n]
p. p "
+
Σ
W W. (pm +),
mehitz
(x1)
= (
(T²)
les ( pa (T72) +
Dm E(K) e (P
mE|M
:m cm (mT) = (ma)
( )" اا (m2) + Ø 440z
(T ) aa (T2)
(28)
Next, we simplify the third and last term in the Equation 27 as follows:
Σ w. (p
we(P
wo(p) ) p. pm E(M) W. (p )) pp pm E(R)
lefil
mEAin2
te(n),melv]
(m)
0
thg (122
0 ( (TT)² d (12))
(29)
Next, combining the results from Equations 27, 28, and 29, we obtain the following:
$1( T2) = W. 0 4m (TI): 401 ( ( 402 (-)
x tb (T2): ( -0 4hs (T2) ( (T2))==000
=0t (T1)²
= (m1) 4 ( (T2).
(30)
Equation 30 showcases both te and の) has three components with having only O non-zero entries, thus fulfilling the requirements for the 84 term. Next, we focus on the 85 term.
Showcasing sparse vectors (5 nT) 50 [1]] x (2)) excluding its scalar component, as outlined in Equation 16.
We begin by examining the $5 term,
(5 T2) (n 100-1114 (11))
Σ w. (p."...)) wp(pp"
lehifa
= (n (2k- - 1/1 n I2))
Σ (.(P
(p(pp" (p
lehnfz
(n- 2k)
Σ
(. T1 ) w. (p [T 122
Σ
w. w.(PP ) w. (pT)
tehinz
Σ
Vn - 2k (p ; Vn - 2k (p,),
lElina
Σ W. (p,) (T .) (P T2 .) //1 11
(31)
lEtina
Σ
Vn 2k W. (pT T Vn 2k W. (p(pp")) 177(()
[6(m]
1 (11))
1= 2 wp . ).) (
Σ
W.
(.(Pp' (p
5a
(T1)
(T2)
Σ
w.(pp"
wp,
Σ 1.
mehnt
(0501
(TT)² 1 (TT2 +
Σ
ws(pi' ws (p,,,
= (T (TT2 +
Σ
(.( p pm E|K
(. T2
mE(n)meEn)
(F1)
(T))
(32)
25

---

saai (x1)² / (T2) + ( ( (T2),
[0 (TI 2 (TI) 2 jd (m2) + uz (T2) ( d (T²))
(33)
(m2)
The equation shows that (T(; ma) d5a (m)) )² 25 (m²), where both d and Φ possess com- ponents with a maximum number of non-zero entries, as indicated in Equations 31 and 32. This completes the proof requirements for the 35 term.
By combining the results from Equations 22, 25, 26, 30, and 33, have demonstrated the existence of vectors 60 and d² each containing only ((a2) non-zero elements, and have established that (i(TI, T22 - "0 ) S (T2) for each E 1, 2,3, 4, In conjunction with Claim 5, this completes the proof.
B Proposed GP-TopK Bandit Algorithm- Omitted Details
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 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.
B.1 Gaussian Process Regression
In GP regression [22], the training data are modeled as noisy measurements of a random function drawn from a GP prior, denoted f (O, k(.,))) :). where k X' X - R is a kernel function over any domain X. The observed training pairs (x,, yi) are collected as X [x.. . Xy and
y = [91..... yrl E R", where, for an input x,, the observed value is modeled as y, = f(x,) + with 6, NO0 a²). The kernel matrix data is Kx = xxxx,,,))17
R Tx The posterior
mean /4 (D and variance di functions for GPs are:
())((x) =K=z
(34)
x)) = k(x,x) x) k2 (Kx + -021)-
(35)
where kx RT has its th entry k(x,x,), GP regression on an arbitrary domain X. the kernel function must be p.d. kernel [23].
(Kx + 021)~ and is identity matrix. For
Naive approaches rely on the Cholesky decomposition of the matrix Kx + I²I, which takes @(T*) time [23]. To circumvent the ((T3) runtime, recent works use iterative algorithms such as the conjugate gradient algorithm, which facilitate GP inference by exploiting fast kernel matrix-vects multiplication (MVM) algorithms, i.e., + Kxv [3]. practice, these methods yield highly accurate approximations for GP posterior functions with complexity of O(p T2) for iterations of the conjugate gradient algorithm, as mvm K x) T2, and mvm (M) the operation count for multiplying matrix M by vector. < T proves to be efficient in practical application [3].
B.2 Contextual GP Reward Model
Optimizing the AF, i.e., UCB function, poses a significant challenge due to its enormous size of I 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, 19J. 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.
26

---

The neighbors of 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! neighhors, which is often not huge as l: is often < 6. This search continues until no neighboring top-k ranking with a higher value discovered. Although BFLS local search, the initial random selection and multiple restart points help it evade local minima, a strategy that previous studies have corroborated [19].
B.3 Assessing GP-TopK Compute Requirements
Theorem 2. Assuming 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 Okk2)fl This applies to WK, CK, and WCK top-k ranking kernels, where & 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 (T**) to (T in computational complexity. Furthermore, these algorithms can further reduce complexity to (TT2) when used with the feature approach.
The results presented in Table
be validated through straightforward observations and by leveraging findings from previous Sections 2. Specifically, Section offers proof for the mvm(K) row explicitly. For the compute Kx, row, the complexity of kernel approaches is deduced from Algorithms 2 and 3. For feature approaches, the compute Kx, row is inferred from the sparsity of the feature representations as stated in Claim 3. Lastly, the memory row straightforwardly deduced for the kernel approach by counting its entries. For the feature approach, it is derived from the sparsity of the feature representations.
B.4 Regret Analysis
In this section, we revisit Theorem and provide its proof. The proofs build on the work by Krause 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 Yt, is given below:
it X
(yx:f))
[(yx;f) = H 1 (yxlf),
where (yyx; /' quantifies the reduction in uncertainty (measured in terms of differential Shannon entropy) about f achieved by revealing уa (27]. In Gaussian observation case, the entropy can be computed in closed form: HNN Σ)) 1/ log [2meE], that 7 Tuxx; f) X C X. For the contextual bandit algorithm, X represents contexts and arms considered until round t.
log T g-2
where Kx [k<x, x')=,,'))=,='x" is the Gram matrix of k evaluated
Before proving Theorem 3, we align the Krause et al. [14] results with our notation for consistency. Furthermore, we modify 3, accommodate embeddings encompassing negative values, aligning with the fact that contextual embeddings may exhibit negative dimensions.
Proposition 1 (Theorem 1, [14]). Let 8 e (0, 1), and the unknown reward function I be sampled from the known GP prior with known noise variance o², Suppose one of the following holds:
Assumption I holds and set Br ()
2. Assumption 2 holds and set Bt = 2B 300 In (t/6).
Then the cumulative regret Rr of the contextual GP bandit algorithm with the UCB acquisition function is bounded by Ö(vCTTmETT) w.h.p. Precisely,
27

---

Pr Pr S VI.TrD +2 2 2 1 8, the notation Ô hides logarithmic factors in n, and T.
where, C1 = 8/log( + o o² and
Proposition shows that the regret Ri for the contextual GP bandit algorithm, utilizing the UCB acquisition function bounded with high probability within (()CTT"rTT)) where the notation O hides logarithmic factors in n, 1 8 and T. To ascertain the O order for Rr, it is imperative to first bound the O order of yr. We begin by examining the yr term in the subsequent proposition.
Proposition 2. Under the assumptions of Theorrmm 3, Yr can be succinetly characterized Pr clo(cll + clog T), which also simplifies to (n²cc), where the O notation omits logarithmic factors in n and
C log (1I + 2xx ) where C equals (1/2) (1 1/e) and Kx, represents the kernel ma- trix computed over contexts and arms across 7 rounds [27, 14). Precisely, Xx, calculated using the contextual kernel defined in Equation 6. It is applied to contexts and top-k ratings from the feedback data D., corresponding Line of the generic contextual bandit Algorithm 1.
Proof. For the GP bandit algorithm with the UCB acquisition function, YT
Next, we leverage the characteristic of the contextual kernel being product kernel. Consequently, the maximum mutual information term for the joint kemell, "r, can be upper bounded by (y + log T), where e denotes the dimensionality of contexts and 7/ represents the maximum information gain in non-contextual setting [14]. Specifically, 77 is computed similarly but confined top-k rankings. That is, 7 C log (I4 2 *Kx=)) l). with Kx; being calculated exclusively using the top-k kernels on the top-k rankings as selected by the bandit algorithm. X7. 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 Kx, = Txr 4xp, where 4x E
((a) T comprises feature columns pertinent to the top-k ranking kemnels, as elucidated in Section A. Utilizing the Weinstein Chinstein-Aronzzjnpn Aronszajn identity, 78 is expressed as C-log (1 + o
2xx; 1 t
Further,
we deduce that 17 < C c.E log (|1+ o -x,x),, where X is an eigenvalue of xx; xx.. Given the Gershgorin circle theorem, which bounds all cigenvalues of a matrix by the maximum absolute sum of its rows, therefore we can conclude that 7 On (ng(n²T)),, as for all the columns of the xx= have bounded normed as given in Claims 2 and 3, i.e., [ < [29].
By combining 7 On log(n?T)) with the contextual product kernel, we obtain Yr ((n'clog(n")) + c clog T), thereby providing the claimed bound in the proposition.
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
[C] |C]- 1-2 ?
Theorem 3. If either Assumptions 1 or hold, setting Be as 2 and 300y, In3 (1) respectively, the cumulative regret Rr of the GP-TopK ban- dit algorithm for top-k recommendations can, with least 1 1 probability, be bounded by O(n/CTTa((oo(C)- log((T+22666))) under Assumption 1, and
66
O(n//r 3 In (T/8)TT under Assumption 2. Here, C1 = To and θ excludes logarithmic factors related to k, and T.
Proof. We will prove the above theorem for both cases separately.
For Assumption-1. Given |C] is finite and 3r llgg( x /65). First, we focus on bounding Br as follows:
Sr = 2 22
28

---

= o + + log (62
As (2) S n& and k! v k*, also have log log (2)kk k!) I log (n**** O log(nk)),
which implies that By O klog(nk) + log(T /6 Combining this with Proposition
2, we have following:
(vr O ((n log TT) + (log] (lgg(nk) log(T" /66))
= logelog(n 2 (log(cl log(nk) + log xog(T2x²/6))) (Ignoring c llgg term)
= (n'e (logiC) + k + log(T /6))) /)
Thus,
we showcase the asserted bound for the regret Ry as Ô OVCiTTyrrr)
Ô (n + ++ [og(
For Assumption-2. Given || I B and Br = 2B² + 300% 300% (t/66) First, we bound the Br term using Proposition as follows:
BT 2B² + 300 .T In (T/0),
2B² + 300 (nnccog(n21)) + clogT) In (T/0).
Using the above result, have the following:
(V VGTT (..TT..(2BB-40 + +00 .r In (T/5))
O (CTTrrrr)) 0
=0 (VCGTnello(n'TT) (2B² + 300 n²clog(n?T) In (T))(T)8))
= (
Comparison with Srinivas et al. (2010). Using the identity kernel for top-k rankings, we can develop a finite-dimensional feature for the contextual kernel and apply Theorem 5 by Srinivas et al. (2010). Given that "r O(n log T),, the regret bounds are as follows under both assumptions. For instance, the calculations for the O( (CTTTT88 under the Assumption 2 follows:
O(VCTTu)))) =
(VGTT (2B² + 300 7r (TT(
=0 (ntiI(Neelogg (2B² 300 clgg) In (T(61)
Ö n (0TTG22B=+000+enn22
Similarly, we can analogously perform the analysis for Assumption and combine it with Proposi- tion to obtain the regret bounds mentioned the Table
C Experiments Omitted Details
This section presents omitted details from the main body of the text.
C.1 Compute resources
We utilized multiple NVIDIA Tesla M40 GPUs with 40 GB RAM on our in-house cluster for our experiments. The experiments Section required approximately 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 the large arm space experiments.
29

---

100
0.0
WK
CK
WCK
WK
CK
WCK
(a)
(b)
Figure Local search results optimizing combinatorial objectives II for n 50 = 6. For details, see the textual description. Left (a) shows how many times out of 100 trials the local search recovers the exact maximizer, i.c., and right plot (h) shows average value the ohjective for returned maximizer. These results indicate that the local search utilized in this work is effective.
C.2 Bandit Simulation and Hyper-parameter Configurations -mitree Details
To set up the simulation, we utilized embeddings trained on the Moviel.ens dataset using a collabora- tive filtering approach [6]. We consider 1M variant of the MovieLens dataset, which contains 1 million ratings from 6040 users for 3677 items, Specifically, we train user embeddings Cu and item embeddings 0g such that the user's attraction the items are captured by the inner product of the user embedding with the item embeddings, respectively. Both context and item embeddings, i.e., C. and 8, are 5-dimensional, optimized by considering the 5-fold performance on this dataset. The reward provided in our experiments is contaminated with zero mean and standard deviation equals 0.05.
For the e-greedy baselines, considered various values of considered, specifically (0.01, 0.05, 0.1). The outcomes are presented for the configuration that demonstrates optimal performance. For MAB-UCB baseline, the algorithm has upper confidence score ucb(i)
14 Smab V 2l((++1) [11]. Here, 14 represents the average reward, denotes the total number of 1h4
rounds, and signifies the frequency of arm i being played. fmab is hyper- parameter. We evaluate Smab values within the set {0.1. 0.25, 0.5) and disclose results for the best-performing configuration. For the parameters of proposed GP-TopK bandit algorithms, we set Br = .gg log(I - x²) with Pop E {0.05, 0.1, 0.5), reporting results the value that yields the best performance. The choice of 3 is informed by prior work in GP bandits [27]. The selection of for all variants is determined by optimizing the log-liieldood of the observed after every 10 rounds by considering values in the set (0.01, 0.05, 0.1}.
C.3 Additional results
Local search results for optimizing combinatorial objectives in 1 for 50 and k 6. Specif- ically, n² max, & (T)) where o" represents the feature vector for Kendall kernels on top-k rankings. Notably, for this optimization problem, it is known that the optimal value is 1 obtained by only x. Figure shows results for this optimization problem when applied to WK, CK, and WCK kernels.
Reward results for large arm space for the nDCG + diversity reward. Similar to Figure 3, a large setup with n 50 for = 3 and A 6, considered. For k 6, the possible arms are over 1.1 x 10 possible top-k rankings. Given the vastness of this arm space, computing the optimal arm for the diversity reward is not straightforward. Therefore, we focus on reporting the cumulative reward in Figure 5. We implement this setup using a Local search in batch mode, updating every 5 round and considering substantial horizon T 100 rounds. Specifically, we use 5 restarts, steps in every search direction, and start with 1000 initial candidates. Figure 5 shows that the WCK approach demonstrates superior performance, continuing to learn effectively even after extensive rounds.
30

---

1600
1600
Rardom
e-rredy
MAB
800
WBC
800
%
100
Figure 5: Comparative evaluation of bandit algorithms for large spaces for the nDCG diversity reward, with 10 for the left plot and > 1.1 x 10th for the right plot, respectively. Cumulative reward with respect to the rounds of the bandit algorithm is depicted. Results are averaged over 6 trials. In both settings, the WCK approach outperforms other baselines. For more details, see the textual description.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Section briefs both contributions and scope of this work.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 6 reflects on the limitations of this work.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Proofs of all Claims and Theorems are provided in the Appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 5 provides necessary details of bandit simulator and experimental setups considered in this work.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our code be accessed using this hyper-link.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Section provides experimental details and few remaining details are given in the Appendix C.
31

---

7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All figures reported in this work have errorbars with them.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section C provides relevant information about compute resources.
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics https: http://neeuiipppeee httpppp...cpbbccc//ccccieieeeeee
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
Section reflects on the impact of this work.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: this work does not release any such resource or asset.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: this work release only code with instructions for its usage.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
32


Reviews:
[{"review_id": "SA5L4vbks6", "reviewer": "Reviewer_tLdn", "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.", "questions": "Do you agree with the limitations discussed above?", "limitations": "yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is extremely readable and well presented, I particularly like the boxes highlighting key claims and the examples e.g. Table 2 and Figure 1.  The mathematical notation is clean and consistently used, and the authors are clearly in command of the literature they are building on.  This is particularly evident when the authors are able to draw a clean distinction between existing work and their contributions.\n\nThe experiments are well designed, cleanly implemented, well executed and presented immaculately.", "weaknesses": "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.\n\nI 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.\n\nFirst, 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.\n\nThe 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\n\nFinally, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Dear Reviewer tLdn,** \n\nWe appreciate your positive feedback on the readability and design of our experiments. We address your comments in the order they were presented.  \n\n> On the cascade model, utilize click information. \n\nWe 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.\n\n\n> On covariance functions and its shortcomings. \n\nThank 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.\n\n> Finding recommendations with inner product search \n\nWe 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.\n\n**Thank you for the insightful review!**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ULNUCMU0e1", "reviewer": "Reviewer_9Xg2", "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.", "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": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The paper is very well presented and easy to read, and the proofs are also very clear.\nThe authors provide meaningful insight into the strengths of their new kernel through small examples and the results of the experiments.\n- The computational costs of a Gaussian Process using the new kernel are extensively addressed, and their approach is significantly more efficient than a standard procedure.", "weaknesses": "- 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.\n- Despite the strengths of the new kernel, it is not particularly novel as it is a straightforward combination of existing kernels.\n- 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).\n\nI found a few typos and confusing passages, but overall, they didn't affect the reading experience. I will report them here as a feedback:\nline 99: typo ww(...) -> w(...)\nlines 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?\nlines 281-283: \\lambda = 0.25 emphasizes diversity over relevance\nline 751: typo shoes -> shows\nline 821: typo very -> every (also possibly missing a subject after \"observed\"?)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Dear Reviewer 9Xg2,**\n\nWe 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. \n\n>  new algorithm to be their primary contribution \n\nWe 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. \n\n>  more clear about the confidence ranges \n\nThank 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. \n\n>  on the possibility of efficient local search exploiting the kernel structure \n\nThank 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. \n\n**We are grateful for the valuable feedback on our work. We welcome further engagement and look forward to learning from your perspective.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ApR58TFBst", "reviewer": "Reviewer_DrUM", "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.", "questions": "Questions:\n1. Why did you choose the Kendall kernel for the Gaussian process? What are the advantages of this kernel over other kernels?\n2. How does your algorithm's performance compare to existing works that use full-bandit feedback, such as Rejwan and Mansour (2020)?", "limitations": "Limitations are adequately discussed in the paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-organized and well-written, with clear explanations and detailed experimental results.\n2. The proposed algorithm achieves state-of-the-art performance in top-k recommendation tasks compared with various baselines. The theoretical analysis provides a solid foundation for the algorithm's performance guarantees.\n3. The improvements in computational efficiency and memory requirements are novel, and technical, making the algorithm more practical for real-world applications.", "weaknesses": "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.\n2. 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.\n3. 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.\n\n[1] Rejwan, Idan, and Yishay Mansour. \"Top-$ k $ combinatorial bandits with full-bandit feedback.\" Algorithmic Learning Theory. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Dear Reviewer DrUM,** \n\n\nWe 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. \n\n> Are Gaussian processes restrictive for modeling rewards?\n\nThe 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.\n\n> 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?  \n\nSection 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.\n\n> Compared to existing works that use full-bandit feedback, such as Rejwan and Mansour (2020)?\nRejwan 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. \n\n**We appreciate your valuable feedback and look forward to learning from it to enhance this work.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AhKRQiu2dp", "reviewer": "Reviewer_N1XB", "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.\n\nDisclosure: I have reviewed a previous version of this paper.", "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).\n* 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.\n* 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.\n* L304 (Evaluation for large arm space):\nFirst, 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).\nSecond, 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).\n\n* A few comments from the previous review that are still not fixed:\n  * 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.\n  * Another example from the rebuttal: “CG is the conjugate gradient algorithm. We will clarify this in the future.”\nIn the current version this part is moved to the appendix (L707), but still appears as “CG”, without clarification.\n  * 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": "No societal issues.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n* Extends the literature on top-k recommendations with a GP-UCB algorithm\n* Well presented", "weaknesses": "Weaknesses:\n* The approach does not seem scalable to real-world problems\n* The theoretical contribution could be further clarified", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Dear Reviewer N1XB,** \n\n\nWe 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.\n\n> clarify the technical contribution (novelty) compared to Krause & Ong (2011).\n\nWe 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. \n\n> 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). \n\nThe 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.\n\nRegarding 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.\n\nOur 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. \nIt'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.\n\n* [1]. LinkedIn blog on building large-scale system \nhttps://www.linkedin.com/blog/engineering/recommendations/building-a-large-scale-recommendation-system-people-you-may-know\n* [2]. IJCAI tutorial on Bayesian Optimization for Balancing Metrics in Recommender Systems https://ijcai20.org/t03/   \n\n> The acquisition function is not applied to all possible top-k rankings, and the regret analysis does not account for the approximation \n\nIn 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.\n\n> Figure 3 should show all iterations (i.e., in the batch mode)\n\nThanks 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. \n\n\n**We value your detailed feedback and welcome further engagement to strengthen this work.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Dear Program Chairs, Area Chairs, and Reviewers,**

We appreciate the constructive feedback on our work. It is encouraging that all reviewers affirm this work's soundness, presentation, and contributions. Below, we address the questions and concerns raised by each reviewer. We provide additional figures as reviewers  9Xg2 and DrUM requested in the attached single-page pdf. 

**Thanks again!**

Meta-review: 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.
Decision: Accept (poster)