Fast Slate Policy Optimization: Going Beyond Plackett-Luce
Authors: Otmane Sakhi
David Rohde
Nicolas Chopin
Venue: Accepted by TMLR ()

Abstract: An increasingly important building block of large scale machine learning systems is based on returning slates; an ordered lists of items given a query. Applications of this technology include: search, information retrieval and recommender systems.  When the action space is large, decision systems are restricted to a particular structure to complete online queries quickly. This paper addresses the optimization of these large scale decision systems given an arbitrary reward function. We cast this learning problem in a policy optimization framework and propose a new class of policies, born from a novel relaxation of decision functions. This results in a simple, yet efficient learning algorithm that scales to massive action spaces. We compare our method to the commonly adopted Plackett-Luce policy class and demonstrate the effectiveness of our approach on problems with action space sizes in the order of millions.

Published in Transactions on Machine Learning Research (12/2023)
Fast Slate Policy Optimization: Going Beyond Plackett-Luce
Otmanc Sakhi CREST-ENSAE, Criteo Al Lab
o. o.sahh@@riita..com
David Rohde Criteo Al Lab
d.rohde@criteo.com
Nicolas Chopin CREST-ENSAE
nicolas. chopin Gensae.f
Reviewed on OpenReview: https: // openreview. net/ forun? id= f7a8XCRtUu
Abstract
An increasingly important building block of large scale machine learning systems is based on returning slates; an ordered lists of items given a query. Applications of this technology include: search, information retrieval and recommender systems. When the action space large, decision systems are restricted to a particular structure to complete online queries quickly. This paper addresses the optimization of these large scale decision systems given arbitrary reward function. We cast this learning problem in policy optimization framework and propose new class of policies, born from novel relaxation of decision functions. This results in a simple, yet efficient learning algorithm that scales to massive action spaces. We compare our method to the commonly adopted Plackett-Luce policy class and demonstrate the effectiveness of our approach on problems with action space sizes the order of millions.
1 INTRODUCTION
Large scale online decision systems, ranging from search engines to recommender systems, constantly queried lo deliver ordered lists of content given contextual information. As example, user who has just seen the film 'Batman', might be recommended: Superman, Batman Returns, Bird Man, or a user that is reading a page about 'technology' might be interested in other stories about biotechnology, solar power, and large language models. A large scale production system must therefore be able to rapidly respond to query like 'Batman' or 'technology' with an ordered list of relevant items.
A proven solution to this problem is to generate the ordered list using approximate maximum inner product search (MIPS) algorithm (Shrivastava & Li, 2014), which, at the expense of constraint in the decision rule, provides extremely rapid querying even for massive catalogues. While MIPS based systems are a proven technology at deployment time, the offline optimization of them is not, and the standard algorithm based on policy learning using the Plackett- distribution is infeasibly slow, as the algorithm both iterates slowly and requires very large numbers of iterations to converge. Fortunately, other approaches are possible which both iterate faster and require fewer itcrations. In this paper, we propose a simple algorithm that enjoys better convergence properties than competitors.
We denote by E X context; it can be the history of the user, search query even whole web page. The decision system is tasked to deliver, given the context an ordered list of actions Ax = [ai...., axl of arbitrary size K E N*, often referred to as slates. This slate can be an ad banner, a list of recommended content or search results. Our decision system, given contextual information x, constructs a slate by selecting subset of actions {aj,..., }x} C from a potentially large discrete set and ordering them. Let P [A] be the size of the action set. Fixing the slate size K, we model our system by decision function d: X - SK (A) that maps contexts to the space Sx (A) of ordered lists of size K. Each pair of context. x and slate A is

---

Published in Transactions on Machine Learning Research (12/2023)
associated with reward function' r(Ax, .)) that encodes the relevance of the slate Ag for We suppose that the contexts are stochastic, and coming from an unknown distribution v(X). Our objective is to find decision systems that maximize the expected reward, given by:
Ex)((X) [r(Ax d()),x))
Assuming that we have access the reward function, the solution of this optimization problem is given by:
e E E d(z) argmax r(Ak,z). (x
(1)
This solution, while optimal, is intractable as it requires, for a given context x, the search in the enormous space (AA) of size O(PR) to find the best slate. Instead of maximizing the expected reward over the whole space, we want to restrict ourselves to decision functions of practical use. In this direction, we begin by defining the parametric relevance function fo A X R:
V(a,)) E Ax =)(a,z)=1ae = h=(x)² Bo:
with the learnable parameter 0 = BI, parametric transform h= X R- that creates context embedding of size L, and 3n the embedding of action in R', the embedding dimension L is usually taken to be much smaller than P, the size of the action space. We then define our decision function:
E do(x) = argsort K (he(x)"Ba) aEA
(2)
with argsort the argsort function truncated at the K-th item. Restricting the space of decision functions to this parametric form reduces the complexity of returning a slate for the context from O(PK) to O(log K). This complexity can be further decreased. Equation (2) transforms the querying problem to the MIPS: Max- imuum Inner Product Search problem (Shrivastava & Li, 2014), for which different algorithms were proposed (Gionis et al., 1999; Malkov & Yashunin, 2020; Guo et al., 2020) to find solution in logarithmic time complexity. These algorithms build fixed indexes over the action embeddings B, with particular structures to allow the identification (sometimes approximate) of the K actions with the largest inner product with the query h=(x). This allow us to reduce even further the complexity of the argsort operator from O(P log K) to a logarithmic time complexity (log P), making fast decisions possible in problems with massive action spaces A. This leaves with the problem of finding the optimal decision function within the constraints of this parametric form. This is achieved by solving the following:
0 arg max Exou(x) [r(Ak = do(x)) 8=|,,0]
As do not have access to v(X', replace the previous objective with its empirical counterpart:
0" arg max 0=(,66]
1
Σ
+ (Ak = do(
(3)
N
with {ai (eeN observed contexts and an offline reward estimator; it includes the Direct Method, Inverse Propensity Scoring (Horvitz & Thompson, 1952), Doubly Robust Estimator (Dudik al., 2014) and many other variants, as presented in (Sakhi et al., 2023b). The optimization problem of Equation (3) is complicated by the fact that the reward can be non-smooth and that our decision function is not differentiable. A way to handle this is by relaxing the optimization objective. Differentiable sorting algorithms (Grover et al., 2019; Prillo & Eisenschlos, 2020) address similar problem but make strong assumptions about the structure of the reward function, and cannot scale to large action space problems. To be as general as possible, we take another direction and relax the problem into an oflline policy learning formulation (Bottou et al., 2013; Swaminathan & Joachims, 2015). We extend our space of parametrized decision functions to a well chosen space of stochastic policies Ta X ((Sx(A)), that given context z, define probability distribution
mmtivvted by business metrics and/or users engagement.
2

---

Published in Transactions on Machine Learning Research (12/2023)
Arbitrary Reward
Low Gradient Variance
Time Complexity
Space Complexity
PL-PG
X
O(SP)
O(SP)
PL-Rank
OSSP)
(SSP)
LGP
(SSP)
(
LGP-MIPS
O ( log P)
(
Table High level comparison between the different optimization algorithms for slate decision functions, with P the size of the action space, L the size of the embedding space and S the number of samples used to approximate the gradient. PL-PG is Plackett-Luce trained with the Score Function Gradient (Williams, 1992). PL-Rank is the algorithm proposed in Oosterhuis (2022). LGP is our proposed method and LGP-MIPS is its accelerated variant. Our method works with arbitrary rewards, scales logarithmically with P and have low memory foolprint (L < P).
over the space of slates of size K. Given a policy ne, we relax Equation (3), taking an additional expectation under my to obtain:
#r E arg max R(TO) 1
N Σ E (x (f(Ak. x;)]
(4)
The most common policy class for this type of problem is Plackett-Luce (Plackett, 1975), that generalises the softmax parametrization to slates of size K 1. Under this policy class, computing exact gradients is intractable but we obtain approximate gradients w.r.t to 0 of Equation (4). Common approximations (Williams, 1992) are based sampling from the policy, variance that grows with the slate size K. In the special case of decomposable rewards over items the slate (Swaminathan et al., 2017), exploiting this linearity structure (Oosterhuis, 2022) provides gradient estimates with better variance. However, training speed still scales lincarly with making policy learning infeasible in large action spaces.
computed in O log K) and suffer from a
In this work, we propose LGP: Latent Gaussian Perturbation, a new policy class based on smoothing the latent space, that is perfectly suitable to optimize decision functions of the form described in (2). As shown in Table 1, our method provides fast sampling, low memory usage, gradient estimates with better computational and statistical properties while being agnostic to the reward structure. When the embeddings are prefixed, this class naturally benefits from approximate MIPS technology, making sampling logarithmic in the action space size and opening the possibility for policy optimization over billion-scale space sizes.
This paper will be structured as follows. In Section 2, we will review the Plackett-Tace policy class and present its limitations. Section will introduce our newly proposed relaxation, motivate its use and propose learning algorithm. We focus in Section 4 on experiments to validate findings empirically. Section 5 will cover the related work and conclude with Section 6.
2 Plackett-Luce Policies
2.1 A Simple Definition
We relax our objective function and model online decision systems stochastic policies over the space of slates; ordered lists of actions. There some natural parametric forms to define policy on discrete action spaces. If we are dealing with the simple case of K = (slate of one action), we can adopt the softmax policy (Swaminathan & Joachims, 2015; Sakhi et al., 2023b) that, conditionod on the context x E X' and for a particular action a E A, is of the form
Te(a|z) = exp(fola,x)) exp(fo(a,x)) Zz(x)
E, exp(
This softmax parametrization found great success (Swaminathan & Joachims, 2015; Chen al., 2019; Sakhi et al., 2023b), and ubiquitous in applications where the goal learn policies or distributions over discrete actions. Once deal with K > 1, one can generalize the previous form giving us the Plackett-Tauce
3

---

Published in Transactions on Machine Learning Research (12/2023)
policy (Plackett, 1975). For given and particular slate Ax [a1,..., agl, we write its probability:
K
exp (0,,
II
To(as A1:-1);
(5)
Zo (x)
==1
with Zz(x) Zx(x) and Zz(x) Zz cxplfo
Computing these probabilities can be done in ((P) which is comparable to the simple case where K = 1. The probabilities given by the Plackett-Luce policy are intuitive. Equation (5) can be seen as the probability to generate the slate Ax- = [o1,... ax] by sampling without replacement from a categorical distribution over the discrete space with action probabilities proportional to exp(Jo(a, x)). This sampling procedure can be done in O(KP), but its sequential nature is a bottleneck for parallelization. Another way sample from this distribution is to exploit the following expression:
[1
Ax = argsort (Sola', x) + x
To( x x)) = (o.0)"((.1))
a'EA
with ~ (0, a vector of P independent Gumbel random variables. This is known in the literature as the Gumbel trick (Huijben et al., 2021). This means that sampling from a Plackett-Luce boils down to sampling P independent Gumbel random variables, which costs O(P), and then computing an argsort of the noised x)) over the discrete action space. We cannot. exploit approximate MIPS for this computation as the noise is added after computing the inner product f(a,2), making this step cost O log K), which makes the total complexity of sampling O(Plog K), slightly better than the first procedure while compatible with parallel acceleration.
2.2 Optimizing The Objective
We want to learn slate policies that can maximize the objective in Equation (4). As our objective is decom- posable over contexts, stochastic optimization procedures can be adopted Ruder (2016) making optimization over large datasets possible. For this reason, we can focus on the gradient of the objective for a single context æ. We derive the score function gradient (Williams, 1992):
Veli(T)lz) Bxs(((K) [F(AK, V) Ve (A [x]]
(6)
K
Emo(-l)) [P(Ak: x) V log (a/s2 A4-1)]-
(7)
This gradient defined as an expectation under (=(x)) over all possible slates. Computing it exactly requires summing O(PK) lerms which is infeasible. This allows approximate the gradient by sampling, which reduces the computation complexity but will see that this gradient suffers from further problems.
Computational Burden. The computational complexity of the gradient is crucial for allowing fast learn- ing of slate as impacts the running time of every gradient step. Even if we avoid computing the gradient exactly, its approximation can still be bottleneck when dealing with large action spaces for the following reasons: (1) Sampling: Approximating the expectation by sampling slates from =0(-12) can be done in O(P log K). However, if the action space is large (P in the order of millions), even linear complexity P can be problematic, massively slowing down optimization procedure. (2) The Normalizing Constant:
Approximating the gradient needs the computation of Vo log No (x) for the sampled slates This can slow down the optimization procedure as computing the normalizing constant Zg(x) requires summing over all actions, making the complexity the operation linear in P.
We can solve this computational burden by tackling the two previous problems separately. We can get rid of the normalizing constant in the gradient by generalizing the results of Sakhi et al. (2023b). For a single context x, we derive a covariance gradient that does not require Zo
Vol((T)(=) Cov Are Amol)
F(AK x), Σ Volo(a,,z)
(8)
4

---

Published in Transactions on Machine Learning Research (12/2023)
with B = ([)(A--(())(BB-- E covariance between A a scalar function, and B vector. The proof of this new gradient expression is developed in Appendix A.1. One can see that for K = 1, we recover the results of Sakhi et al. (2023b). This form of gradient does not involve the computation of a normalizing constant, which solves the second problem, but still requires sampling from the policy x0{-|2>) to get a good covariance estimation. To lower the time complexity of this step, we can use Monte Carlo techniques such as Importance Sampling/Rejccte
Sampling (Owen, 2013) with carcfully chosen proposals to achieve fast sampling without sacrificing the accuracy of the gradient approximation. We develop a discussion around accelerating Plackett- training in Appendix A.1. While we may have ways to deal with the computation complexity, the Plackett-Lace Policy gradient estimate still suffers from the following problems:
Variance Problems. Let us focus on the gradient derived in Equation (6). Its exact computation is intractable, and we need to estimate it by sampling from no(-)æ). Let us imagine we sample a slate Ax [a,,... ax] to estimate the gradient:
Ga(z) = P(AK.(AKA) x) Ve log NO To (Aklz)
=(AAK x)
gx(x,
with (x) set to V Vologme Te(a),,, to simplify the notation. Gø(z) is an unbiased estimator of the gradient Voll(Ta(=)) and can be used in a stochastic optimization procedure in principled manner (Ruder, 2016). However, the efficiency of any stochastic gradient descent algorithm depends on the variance of the gradient estimate (Ajalloeian & Stich, 2021), which is defined for vectors X as:
V[X] = E [||X - [[X]]| ER
Gradients with small variances allow practitioners to use bigger step sizes, which reduces the number of iterations as it makes the whole optimization procedure converge faster. Naturally, we would want the variance of our estimator to be small. Unfortunately, the variance of Go(z) grows with the slate size K. Writing down the variance w.r.t n0(-1z) of Go(z):
W[Go(=)] = Voggo Σ 2(g( +2
+2 Cwwlf(AA ((4,
The first term of this variance is sum over the slate of individual variances, which clearly grows as K grows. For the covariance terms, we argue that, especially when initializing the parameter randomly, the gradients of (z) and de (z) will have in expectation different signs making the covariance terms cancel out, leaving the sum of the individual variance terms dominate. This gives variance that grows in O(K).
Previous work already showed empirically that the score function gradient for the Plackett-Luce distribution has a large variance (Gadetsky et al., 2020; Buchholz et al., 2022), large enough that learning is not possible in difficult scenarios without considering variance reduction methods (Gadetsky et al., 2020). possible solution Randomized Quasi-Monte Carlo (Buchholz et al., 2022; I. I''Ecuyer, 2016), which produces more accurate estimates by covering the sampling space better. Its value only significant when we sample few slates h to approximate the gradient (Buchholz et al., 2022; L'Ecuyer, 2016). Another direction explores control variates (Gadetsky et al., 2020) variance reduction technique. This method requires additional computational costs and a perfect modelling of a differentiable reward proxy to expect variance reduction (Grathwohl et al., 2018).
We want to find a way to both reduce the variance our method and the computational burden. One of the simplest method reduce the variance and gain in computation speed is to reduce the number of parameters we want to train (Koch et al., 2021). In our problem of online decision systems, some parameters can be learned independently making policy learning easier (Sakhi et. al., 2023b).
5

---

Published in Transactions on Machine Learning Research (12/2023)
2.3 Fixing The Action Embeddings
As we are dealing with large action spaces, are constrained to the following structure the relevance function fo for fast querying:
Va A z) Ba.
with both (x) and Ba living in embedding space RR& with I. < P. The dimension of the matrix / is [L PI, which can be very large when P is large, and dominates E in terms of number of parameters (Koch et al., 2021; Sakhi et al., 2023b). If we can fix the matrix B, it would benefit our approach both in terms of computational efficiency and variance reduction. Indeed, reducing the number of parameters accelerates lcarning, makes the problem more identifiable, and reduces drastically the gradient variance as:
F[] W[Go(=)] = +
= V[G=(()) + W[)) > V[G=
with Go())) Vo)(m)) the centred gradient estimate. In many applications (think about infor- mation retrieval, recommender systems ad placement), the action embeddings can be learned from the massive data we have on the actions. In these scenarios, actions boil down to web pages, products we want to recommend or place in an ad. We usually have collaborative filtering signal (Sakhi et al., 2020; Liang et al., 2018) and product descriptions (Vasile et al., 2016) to learn embeddings from. These signals help us obtain good action embeddings 3 and allow us to fix the action matrix before proceeding to the downstream task we are solving. This approach of fixing B is not new, Koch et al. (2021) fix 3 to learn a large scale recommender system deployed in production, and Sakhi et al. (2023b) show empirically that lcarning 3 actually hurts the performance of softmax policies in large scale scenarios.
We can still learn more about the actions. Even with 3 fixed, there are sufficient degrees of freedom to solve our downstream task. If we write down:
h=(x) bi (x)
with E = = 2}, Z being a learnable matrix of size [L', L). the relevance function can be writlen as: (ZBa);
so x)) (zB))
Va A.
This means that, even though the matrix 3 is fixed, we can learn a linear transform of 3 with the help of Z, injecting information from the downstream task and learning a transformed representation of the actions in the embedding space. In the rest. of the paper, we will fix the action embeddings / making the parametrization of the relevance function fo reduce O E, giving for any x:
fola,z) = ho(z) Ba, Va A.
3 Latent Gaussian Perturbation
Fixing the embeddings helps to decrease the variance and the number of parameters to optimize substantially, which makes our policy learning routine converge faster. This approach, however, does not deal with the fundamental limit of the Plackett-Luce variance, which grows with the slate size K. This policy class also needs particular care accelerate its learning; we should adopt the new gradient formula stated in (8) combined with advanced Monte Carlo techniques to approximate the gradient efficiently, making the implementation of such methods difficult to achieve.
These issues come intrinsically with the adoption of the Plackett-Luce policy, and suggest that we should think differently about. how we define policies over slates. Let us investigale this family of policies. For a particular context x and a slate Ak, we write down its Gumbel trick (Huijben et al., 2021) expression:
[
[1{Ax=
Ax argsort K (ha(#)) Bar + xx] d'EA
Te (A x)) = (o,1)"(0,))

---

Published in Transactions on Machine Learning Research (12/2023)
The Plackett-Luce policy is smoothed, differentiable relaxation of the following deterministic policy:
bo(Ax(=)= = Ax = argsort* {ho(2))
a'EA
= 1 [Ax = da())).
by is a deterministic policy putting all its mass on the actions chosen by our decision function dg. Note that, taking an expectation under by in Equation (4) recovers Equation (3). It means that introducing noise relaxed Equation (3) to differentiable objective. This relaxation is achieved by randomly perturbing the scores of the different actions with Gumbel noise (Huijben et al., 2021). As this perturbation is done in the action space level, it induces properties that are not desirable: (1) The gradient of this policy is expectation under potentially large action space, accentuating variance problems. (2) The perturbation scales with the size of the action space, as we need P random draws of Gumbel noises. (3) Sampling from this policy cannot naturally benefit from approximate MTPS algorithms, as discussed previously.
We observe that the majority of these problems emergee from doing this perturbation in the action space level. With this in mind, we introduce the LGP: Latent Gaussian Perturbation policy, that is defined for context and slate Ax by:
[ Ax = argsort K {(ha(z) + +c)" B |]] d'EA
T6 (Ax = EENNV(0,0P1a)
with a > 0, shared standard deviation across dimensions in the latent space R The LGP policy defines a smoothed, differentiable relaxation of the deterministic policy bg by adding Gaussian noise the latent space IR.. This approach can be generalized by perturbing the latent space with any other continuous distribution Q. The resulting method, called LRP: Latent Random Perturbation presented in Appendix A.2. Focusing on LGP, this class of policies present desirable properties:
Fast Sampling. For given æ, sampling from LGP policy boils down to sampling a Gaussian noise and computing an argsort as:
Ak ~ TT((1z) + Aς = argsort {(ho(z) + Bur) (L) d'EA
As the action embeddings 3 are fixed, and we are performing a perturbation in the latent space, sampling can be done by calling approximate MIPS on the perturbed query hī(x) ha(x) + achieving a complexity of Oloog P) and improving on the sampling complexity O log K) of the Plackett-Luce family.
Well behaved gradient. Similar to the gradient under the Plackett-Luce policy (6), we can derive a score function gradient for LGP policies. Let Ag [h} = argsort a'EAA (hTBww) 3w3 the MIPS result for query h. Let us write the expected reward under vg for particular context z:
Í( (r) = EAx (:1a) [((A,
-E..N10,221) [f(AK (2)(2) x),
(En- Ax a)),
The last equality allows us to derive the following gradient:
vo = VoEnn--W(hhcr,,,,, (h},
Enn-- (h), log (o h)],
with log h)) the log density of ((ho(z)) evaluated in h. We obtain unbiased gradient
estimate by sampling Eg _N(0,, It), setting h ho(x) + dep and computing:
(% = f(Ax(h) (og
(Ax (1)
(9)
This gradient expression solves all issues that the Plackett-Tauce gradient estimate suffered from:

---

Published in Transactions on Machine Learning Research (12/2023)
Fast Gradient Estimate. This gradient can be approximated in sublinear complexity Olog P). Building an estimator of the gradient follows these three steps: (1) We sample 60 ~ (O, Iz), which is done in a complexity (L)) < O(P). (2) We evaluate the gradient of 6 hx in O(L) with no dependance on P. (3) We generate the slate Ak (h}. This boils down to computing an argsort that can be accelerated using approximate MIPS technology, giving a complexity of Ollog P).
Better Variance. LGP's gradient estimate have better statistical properties for two main reasons: (1) The gradient is defined as expeclation under continuous distribution R², instead of an expectation under a large discrete action space A of size P > L. This can have an impact on the variance of the gradient cstimator as the sampling space is smaller. (2) The approximate gradient defined in Equation (9) does not depend on the slate size K. This results in a variance that does not grow with K, which will translate to substantial performance gains on problems with larger slates. However, the expression of this gradient suggests that our attention should be directed towards the standard deviation instead, as the variance of the gradient estimate defined in Equation (9) will scale in O(1/o²).
the latent space
Even if can be treated as an additional parameter, we fix it to = 1/L in all our experiments for a fair comparison. The resulting approach will be hyper-parameter free, and will show both statistical and computational benefits. We give a sketch of the resulting optimization procedure in Algorithm 1. This procedure easy implement any automatic differentiation package (Paszke et al., 2019) and is compatible with stochastic first order optimization algorithms (Ruder, 2016). In the next section, we will measure the benefits of the proposed algorithm in different scenarios.
Algorithm 1: Learming with Latent Gaussian Perturbation
Inputs: D {ax 1 reward estimator f, the action embeddings
Parameters: T 2 Monte Carlo samples number $ 2 1
Initialise: 0 0n. MIPS index of B, 1/L
for t= 0 to - do
sample context
D
sample S standard Gaussian noises e1...., Eg NNO, 1t)
compute for E [S] ht ho(x) + compute slates Ax (h, for E [S] with MIPS
Estimate the gradicnt: grads + So
Σ 8=1
Update the policy parameter 0: +- - agrada
end return A
4 Experiments
4.1
Experimental Setting
For our experiments, we focus on learning slate decision functions for the particular case of recommendation as collaborative filtering datasets are easily accessible, facilitating the reproducibility of our results. We choose three collaborative filtering datasets with varying action space size, MovieLens25M (Harper & Konstan, 2015), Twitch (Rappaz et al., 2021) and GoodRoads (Wan & McAuley, 2018; Wan et al., 2019). We process these datasets transform them into user-item interactions of shape [U. with U and the number of users and actions. The statisties of these datasets are described in Table 2.
8

---

Published in Transactions on Machine Learning Research (12/2023)
We follow the same procedure Sakhi et al. (2023b) to build our experimental setup. Given dataset, we split randomly the user-item interaction session [X,Y] into two parts; the observed interactions X and the hidden interactions Y. the observed part X represents all the information we know about the user, and will be used by our policy Ty to deliver slates of interest. The hidden part Y is used to define a reward function that will drive the policy to solve a form of session completion task. For a given slate Ax = [M1.... "x], we define the reward as:
K 1 EY] A(AK.))
2
Although we can adopt arbitrary form for the reward fonction, we want rewards that depend on the whole slate (Aouali et al., 2023b) and that take into account the ordering of the items. We choose a linear reward to be able to compare our method to PL-Rank (Oosterhuis, 2022), which exploits the reward structure to improve the training of Plackett-Luce policies. The objective we want to optimize the following:
i((TO) 1 Σ EA EA X.)]
The next step is to parametrize the policy Te. For large scale problems, and for a given X, we are restricted to use the following paramctrization of the relevance function fo:
fo (a, X) = ho(X))
Va E A.
Given the observed interactions X, we compute the action embeddings 3 using SVD matrix decompasition (Klema & Laub, 1980). This allows to project the different action into a latent space of lower dimension I. & P, making 3 of dimension [L, PI. In all experiments, 3 will be fixed unless we want to study the impact of training the embeddings. When B is fixed, we create an approximate MIPS index using the HNSW algorithm (Malkov & Yashunin, 2020) with the help of the FAISS library (Johnson et al., 2019). This index will accelerate decision-making online as described the training of LGP policies. With 3 defined, we still need to parametrize the user embedding function hg- Given X, we first define the mean embedding function M X + R4:
Equation (2) and can also be exploited to speed up
M(X)
B.. aEX
Σ
X
The function M computes the average of the item embeddings the user interacted with in X (Koch et al., 2021). hg follows as:
ho(X) (XX))
(10)
with 0 a parameter of dimension [r, L.), much smaller than [L, P], the dimension of B. All policies in these experiments will use this parametrization. Experiments with deep policies can be found in Appendix A.3.4. The training conducted on a CPU machine, using the Adam optimizer (Kingma & Ba, 2014), with batch size of 32. We tune the learning rate validation set for all algorithms. We adopt Algorithm 1 to train LGP and its accelerated variant LGP-MIPS. We denote by PL-PG, the algorithm that trains the Plackott-Luce policy trained with the score function gradient; sample S 2 slates [Ak..., from To to derive the gradient estimate for a given X:
S G Σ
(11)
We also compare our results to PL-Rank (Oosterhuis, 2022) that exploits the linearity of the reward to have a better gradient estimate. As we are mostly interested in the performance of the decision system de, all the rewards reported in the experiments are computed using:
1 Σ E=1
Rk(d)) U
A(do XX),,
9

---

Published in Transactions on Machine Learning Research (12/2023)
# *Actions
# #Users
Interactions Density
MovieLens 25M
55K
162K
0.24%
Twitch
750K
580K
0.008%
GoodReads
2.23M
400K
0.01 %
Table 2: The statistics the datasets after preprocessing
In the next section, we study empirically the performance of these approaches by training them with the same time budget on the different datasets. Additional experiments can be found in Appendix A.3 to confirm the robustness of our results and better understand the behaviour of both the Plackett- policy and the newly introduced LGP policy.
4.2 Performance under the same time budget
To measure the performance of our algorithms, use all three datasets with their statistics described in Table 2. We fix the latent space dimension L = 100 and use slate size of K = 5 for these experiments. We split each dataset by users and keep 10% to create a validation set, on which the reward of the decision function is reported. As these algorithms present different iteration speeds, we fix the same time budget for all training methods for a fair comparison. Training with a time budget also simulates a real production environment, where practitioners are bounded by time constraints and schoduled deployments. For all datasets and training routines, we allow runtime of 60 minutes, and evaluate our policies on the validation set for 10 equally spaced intervals. The results of these experiments are presented in Figure 1 where we plot the evolution of the validation reward on all datasets, for different values of S E {1, 100]; the number of samples used to approximate the gradient.
Our first observation from the graph is that PL-PG cannot compete with other algorithms, even in the simplest scenario of the MovieLens dataset. Its poor performance mainly due to the high variance of its gradient estimate. This is confirmed by the performance of PL-Rank. Indeed, the PL-Rank algorithm works with the same policy class, has the same iteration cost (scales linearly in P) and only differs on the quality of the gradient estimate; exploiting the structure of the reward allow These results confirm our first intuition. PL-PG suffer from large variance problems (even in modest sized problems) and is not suitable to solve large scale slate decision problems.
obtain estimate with lower variance.
Let us now focus on our newly proposed algorithms: LGP and its accelerated variant LGP-MIPS. We observe that in all scenarios considered, the acceleration brought by the approximale MIPS index benefits our algo- rithm in terms of performance. For the same time budget, LGP-MIPS obtains better reward than LGP, with the biggest differences observed on datasets with large action spaces; Twitch and GoodReads. LGP-MIPS always gives the best performing decision function, for all datasets and number of Monte Carlo samples S considered. These results are promising our algorithm which is agnostic to the form of the reward outper- forms PL-Rank that is solely designed to tackle the particular case of linear rewards. This performance is due to LGP-MIPS's superior sampling complexity combined with an unbiased, low variance gradient estimate. It is also worthy to note that we were unable to run algorithms optimizing Plackett-Tauce policies (PL-PG and PL-Rank) on the GoodReads dataset with S = 100 due to its massive memory footprint. As sampling done methods need for each iteration samples of size O(SP) compared method for which the sampling is done in the latent space requiring O(SL) memory usage. Being able to increase the number of Monte Carlo Samples S is desirable, as it helps reduce the variance of the gradient estimates and accelerates further the training.
the action space, Tlackett-Luce-ll to
These results demonstrate the utility our newly proposed method over Plackett-Luce for learning slate decision systems. The LGP policy class combined with accelcrated MIPS indices produces unbiasod, low variance gradient estimates that are fast to compute, can scale to massive action spaces and exhibit low memory usage, making our algorithm the best candidate for optimizing large scale slate decision systems.
10

---

Published in Transactions on Machine Learning Research (12/2023)
0.9
0/5
0.6
0.8
0.7-
0.5
0.6
0.4
0.-
6.4
10
10
0.9
0.0
6.7
0.3
0.4
0.3
0.
0.2
0.7
0.9-
0.0
0.5
0.7-
0.6-
on
0.5
6.3
62-
LGP-MIPS
LGP
0.3
0.0
PL-PG
Number
Number CONtani
Number
Figure 1: The performance of slate decision functions obtained after optimizing them by different training algorithms for the time budget of 60 minutes. Each evaluation the validation data is done after 6 minutes of training.
4.3 Performance under the same number of iterations
We proposed a new family of policies that enables fast optimization, and naturally benefits from unbiased gradient estimates with a variance that does not depend on the slate size K. The results reported in Figure show that the newly proposed methods are suitable for optimizing large scale decision systems, under strict time constraints. We provide further experiments and compare the performance of the obtained policies after training them, with different approaches, under the behaviour of the variance of the gradient approximations while neglecting the iteration cost. For the same learning rate, gradient approximations with low variance need less optimization iterations to converge. As PL methods tend to iterate slowly, especially in large action space scenarios (Twitch and Goodreads), we fix the number of itcrations in all experiments to the iterations made by PL-PG after 60 minutes of optimization. We report the evolution the training reward of all methods, for different settings, in Figure 2. We identify two evolution patterns from the plots. first, fast convergence pattern that PL-Rank alongside the LGP family enjoy, and second, much slower convergence pattern of PL-PG. This difference in training reward evolution conveys the following message; the LGP family benefit from gradient estimate with variance similar to PL-Rank, and much lower than the variance of the PL-PG gradient estimate. In addition, not only can the LGP family iterates faster, but it enjoys low variance gradient estimates and does not rely on a lincarity assumption on the reward. This further confirms the improvements brought by the LGP family, motivating it as an excellent allernative Plackeu-LLuce for optimize large scale decision systems.
number of iterations. This gives insight into the
5 Related work
Recent advances in learning large scale decision systems adopt the offline Learning framework (Chen al., 2022; Wang et al., 2022; Ma al., 2020; Chen al., 2019) proving itself powerful paradigm align business metrics with the offline optimization problem. Research in this direction either explore the of known policy learning algorithms (Chen et al.,
Learning from interactions. Contextual
11

---

Published in Transactions on Machine Learning Research (12/2023)
Goodren
0.20
0.20
0.25
0.2-
0.5-
6.15
0.22-
0.20
0.4-
0.3
0.36
20003
43000
40000
80003
1000000
1203c0
1000
2000
2002
6002
5000
7000
520
3002
1500
2000
2500
2000
0.81
0.16
0.20
6.14
0.22
0.21
5-10
0.5
0.00
0.4-
0.00
0.38
2020
4030
s000
5000
10300
12002
200
400
990
802
1030
1200
1.0
200
200
400
Nowars on Traainn Dar
0.02
0.29
0.095
0.53
3.022
0.20
0.43
0.22
LGP-MIPS
3.850
0.20
0.35
LGP
PL-Rank
0.10
PL-PG
Kumber Beralions
Numberr (teratiion
Number lerwiions
Figure 2: Comparing the performance of slate decision functions obtained by running our different training algo-
rithms for the same iterations. The newly proposed relaxation LGP have a gradient estimate of quality comparable to PL-Rank as they result in policies with a similar training behaviour. LGP methods enjoy low variance gradient estimate without making an assumption on the structure of the reward, contrary to PL-Rank.
2022) for learning online decision systems or define better rewards to guide this learning (Wang et al., 2022; Christakopoulou et al., 2022). Chen et al. (2019) showed that large scale recommender systems can benefit from the contextual bandit formulation and introduced correction to the REINFORCE gradient to encourage softmax policies to recommend multiple items. Their method can be seen as heuristic applicable when the slate level reward is decomposable into a sum of single item rewards. This assumption is violated in scttings where strong interactions cxist between the items in the slate. Our method is versatile, does not assume any structure on the reward, and is able to optimize slate decision systems by introducing a new relaxation, smoothing them into a policy that has a better learning behavior than classical Plackett-L.uce.
Scalability. The question of scaling offline policy learning to large scale decision systems has received limited attention. It has been shown that offiine softmax policy learning can be scaled to production systems (Chen et al., 2019). Recently, Sakhi et al. (2023b) focused on studying the scalability of optimizing policies tailored to one item recommendation using the covariance gradient estimator combined with importance sampling (Owen, 2013) to exploit approximate MIPS technology in the training phase. Their gradient approximation is provably biased, sacrificing the convergence guarantees provided by stochastic gradient descent. (Ruder, 2016). Our method extends the scope of this paper, as it can be applied to slate recommendation. It provides simpler relaxation than Plackeu-LLuce, producing a learning algorithm that benefits from approximate MIPS technology, naturally obtaining unbiased gradient estimates with better statistical properties.
Learning to Rank. The learning to rank literature separates algorithms by the output space they operate on, making a clear distinction between pointwise, pairwise and listwise approaches (Liu, 2009). Our method falls in the latter (Xia et al., 2008), as we operate with policies on the slate level. The majority of work in LTR trains docision systems through the optimization of ranking losses (Wang et al., 2018; Oosterhuis, 2022), defined as differentiable surrogates of ranking metrics or by an adapted marimum likelihood estimation (Rendle et al., 2009; Ma et al., 2021). In the same direction, differentiable sorting algorithms (Grover et al.,
12

---

Published in Transactions on Machine Learning Research (12/2023)
2019; Prillo & Eisenschlos, 2020) aim at producing differentiable relaxation to sorting functions that handle reward on the item level These methods also require linear rewards in addition to training an item-item interaction matrix, quadratic on the action space size, making them unsuitable to massive action spaces. We are interested training reward-driven, large scale slate decision systems, to learn rankings that are more aligned with arbitrary, complex rewards functions.
Smoothing non-differentiable objectives. Our procedure can be interpreted as a stochastic relaxation of non-differentiable decision functions. This relaxation is achieved by introducing well chosen noise in the latent space. PAC-Bayesian policy learning (London & Sandler, 2019; Sakhi et al., 2023a; Aouali et al., 2023a) and Black-Box optimization algorithms (Bajaj et al., 2021; Rechenberg, 1978; Staines & Barber, 2012) adopt a similar paradigm to optimize non-smooth loss functions. They proceed by injecting noise in the parameter space and derive a gradient with respect to the noise distribution. This parameter level perturbation can suffer from computational issues when the number of parameters increases. Our method is agnostic to the number of parameters. By perturbing the latent space directly, we bypass this problem and simplify the sampling procedure resulting in faster and more efficient. training.
6 Conclusion and future work
Countless large scale online decision systems are tasked with delivering slates based on contextual informa- tion. We formulate the learning of these systems in the offline contextual bandit setting. This framework relaxes decision systems to stochastic policies, and proceeds at learning them through REINFORCE-like algorithms, Plackett-Luce provides an interpretable distribution over ordered lists of items but its use in a large scale policy learning context is far from being optimal. In this paper, we motivate the Latent Gaus- sian Perturbation, a new policy class over ordered lists defined as a stochastic, differentiable relaxation of the argsort decision function, induced by perturbing the latent space. The LGP policy provides gradient estimates with better computational and statistical properties. We built an intuition on why this new policy class is better behaved and demonstrated through extensive experiments that not only LGP is faster to train, considerably reducing the computational cost, but it also produces policies with better performance making the use of Plackett-Luce policios in this context obsolete. This work gives practitioners new way to address large scale slate policy learning and aim at contributing into the adoption of REINFORCE decision systems. The results obtained in this paper suggest that the relaxations used to define policies have a big role optimization and that we might need to take a step backward and reconsider the massively adopted Softmax/ PPlackett-Luce paramotrization. As we only focused on simple noisc distributions, nice avenue of research will be to study the impact of the choice of these distributions on the learning algorithm produced.
13

---

Published in Transactions on Machine Learning Research (12/2023)
References
Ahmad Ajallocian and Scbastian U. Stich. On the convergence of sgd with biased gradients, 2021.
Imad Aouali, Vietor-Emmanuel Brunel, David Rohde, and Anna Korba. Exponential smoothing for off-policy learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 984 1017. PMLR, 23 29 Jul 2023a. URL html.
attps://proceeding mlr. press//v022aauulll.
Tmad Aouali, Achraf Ait Sidi Hammou, Sergey Ivanov, Otmane Sakhi, David Rohde, and Flavian Vasile. Probabilistic Rank and Reward: Scalable Model for Slate Recommendation, working paper or preprint, January 2023b. URL https: //all.haaaa.... poclence/hal-0395990
Ishan Bajaj, Akhil Arora, and M. M. Faruque Hasan. Black-Boo Optimization: Methods and Applications, pp. 35 65. Springer International Publishing, Cham, 2021. ISBN 978-3-030-66515-9, doi: 10.1007/ 178-3-030-66515-1 2. URL https: http::////oo..o/1..1/1... 300000/9788-000-6661---
Léon Bottou, Jonas Peters, Joaquin Caahonero-Candlla. Denis X. Charles, D. Max Chickering, Elon Portu- galy, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising, Journal of Machine Learning Research, 14(65):3207 3260, 2013.
URL htttp://jmll hwtg/aapers/v14440 http:ppperr/////oooott........
Alexander Buchholz, Jan Malte Lichtenberg, Giuseppe Di Benedetto, Yannik Stein, Vito Bellini, and Matteo Ruffini. Loriaariance estimation in the plackett-luce model via quasi-monte monte carlo sampling, 2022. URL
arg/abs/2205 06024.
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H. Chi. Top-k off- policy correction for reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM '19, pp. 456-464, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450359405, doi: 10. 10.1145/2289000.39999... URL https: //doi. 100/10. 1145/3289600 9220999900000099999 3290999.
Minmin Chen, Can Xu, Vince Gatto, Devanshu Jain, Aviral Kumar, and Ed Chi. Off-policy actor-critic for recommender systems. In Proceedings of the 16th ACM Conference on Recommender Systems, RecSys '22 pp. 338-349, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392785, doi: 10. 01144/3553227735467755 URL https::/ddl http:///oo.or///..../ wwt.oo.../////....... 1145//5222222 3546758.
Konstantina Christakopoulou, Can Xu, Sai Zhang, Sriraj Badam, Trevor Potter, Daniel Li, Hao Wan, Xinyang Yi, Ya Le, Chris Berg, Eric Bencomo Dixon, Ed H. Chi, and Minmin Chen. Reward shaping for user satisfaction in reinforce recommender, 2022. URL https: /tt///aivv.og/aaabb. 1516611199...........1
Miroslav Dudik, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485-511, 2014.
Artyom Gadetsky, Kirill Struminsky, Christopher Robinson, Novi Quadrianto, and Dmitry Vetrov. Low- variance black-box gradient estimates for the plackett-luce distribution. Proceedings of the AAAI Con- ference on Artificial Intelligence, 34(00):10122-10000 Apr. 2020. doi: 10.1609 http//aai.vv3333 v344066.6777 URL https://ojs.... aaai. aeeai.orgginii org/index... wwtpiiiw.ppp..a///a//pa pttp:/AAA//trtice//eeeeeee///e/e
Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing, In Proceedings of the 25th International Conference on Very Large Data Bases, VLDB '99, pp. 518 518-529 529,, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606157.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. In International Conference on Learning Representations, 2018. URL https: https: http:/:://pppreiee..oem htt.://wwnett//ommttdd//ssaaaaa
14

---

Published in Transactions on Machine Learning Research (12/2023)
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Represenlations, 2019. URL https: wwwpeeewwwweeeeetoooriiiiiieeeee
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Acceler- ating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, 2020. URL https: /ttpppp///axvi.../////eee www.aawwwww...../.a.reeee.eeeeee wtwgg/abs/990.../ 10396.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), dec 2015. ISSN 2160-6455. doi: 10.1145/2827872. URL https://doi. org/ 10. N0.1145/282787..
Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Associalion, 47(260):663 (01666666666-66 1952.
Tris AM Huijben, Wouter Kool, Max B Paulus, and Ruud JG van Sloun. A review of the gumbel-max trick and its extensions for discrete stochasticity in machine learning. arXiv preprint arXiv:2110.0100 2021.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transac- tions on Big Data, 7(3):535-547, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ar preprint arXiv:1412 12. 12.6000,,0 2014.
V. Klema and A. Laub. The singular value decomposition: Its computation and some applications. IEEE Transactions on Automatic Control, 25(2):164-176, 1980. doi: 1A11099/TA.19...... 1102314.
Olivier Koch, Amine Benhalloum, Guillaume Genthial, Denis Kuzin, and Dmitry Parfenchik. Scalable representation learning and retrieval for display advertising. arXiv preprint ar wxXv:2101.00877 2021.
Pierre L L'Ecuyer. Randomized Quasi-Monte Carlo: An Introduction for Practitioners. In 12th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC 2016), Stanford, United States, August 2016. URL https: https////aaa..naa..aaaa...a faariia.frhal-01155051
Dawen Liang, Rahul G. Krishnan, Matthew D. Hoffman, and Tony Jebara. Variational autoencoders for collaborative filtering. In Proceedings of the 2018 World Wide Web Conference, WWW '18, pp. 689 698, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Com- mittee. ISBN 978145035665 doi: 10. 10.1145/3178886.3336 3186150.
URL https: //doi org/ 10 1145/3178876.
Tie Yan Liu. Learning to rank for information retrieval. Found. Trends Inf. Retr., 3(3):225 331, mar 2009. ISSN 1554-0669. doi: 1001501/150000006. URL https://doi. http::///oooor//1.... 10. 1561/550000006..
Ben London and Ted Sandler. Bayesian counterfactual risk minimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4125-4133. PMLR, 09-15 Jun 2019. URL https:
/ //proceedings. mlr. www.mmlrr...///..mmmmmm press/v97 htte///ooonn...../ html.
Jiaqi Ma, Zhe Zhao, Xinyang Yi, Ji Yang, Minmnin Chen, Jiaxi Tang, Lichan Hong, and Ed H. Chi. Off-policy learning in two-stage recommender systems. In Proceedings of The Web Conference 2020, WWW '20, pp. 463 143, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450370233. doi:
04.1455/3366423333300000 URL https://doi: org/10....11..// 1145/3366423 33801130.
Jiagi Ma, Xinyang Yi, Weijing Tang, Zhe Zhao, Lichan Hong, Ed Chi, and Qiaozhu Mei. Learning-to-res -torinnggt--rakk with partitioned preference: Fast estimation for the plackett-luce model. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Stafistics, volume 130 of Proceedings of Machine Learning Research, pp. 928 936. PMLR, 13 15 Apr 2021. URL https:// hatp:://ppoceedingee mlr. mlr.presse www.pereavv///mmmm hwtp/ma20....mmmmmmmma.a html.
15

---

Published in Transactions on Machine Learning Research (12/2023)
Yu A. Malkov and D. A. Yashumin. Efficient and robust approximate nearest neighbor search using hicrarchi- cal navigable small world graphs. TEFE Trans. Pallern Anal. Mach. Intell, 42(4):824 836, apr 2020. ISSN 0162-8828. doi: 10.1109/TPAMM.201 2889473. URL http:://doi.ogg//// 10011110//PAAA 2018. 2889473.
Harrie Oosterhuis. Learning-to-rank at the speed of sampling: Plackett-luce gradient estimation with min- imal computational complexity. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '22, pp. 2266 2271, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450387323. doi: https://doi. org/18 10. 1145/3477495 .5477499.3331142.
3531842.. URL
Art B. Owen. Monte Carlo theory, methods and examples. https://artowen. su. http://rttoee...adddmaaaia////// 2013.
Adamn Pasıke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019. URL nttp://papers.nnt www.nnuurrip... cctppee.eperrppppccppppperr cc/paper/ 9015 pytpppyyoo-an---eeeeea -n--ammeraiie--ttt--eeeeeee oatpra/eessyyytiiiiirrrrrrrreere wwwprrmmannndeeeeeaeiiiaeae
pdf.
R. L. Plackett, The analysis of permutations. Journal of the Royal Statistical Society. Series C (Ap- plied Stalistics), 24(2):193 202, 1975. ISSN 00359254, 14679876. URL http://wwwt http::/wwww.jsorrrrm jstor ott.ssable///ttbe////eee 2346567.
Sebastian Prillo and Julian Martin Eisenschlos. Softsort: A contimuous relaxation for the argsort operator. Tn Proceedings of the 37th International Conference on Machine Learning, ICML'20. JML..org, 2020.
Jérémic Rappaz, Julian McAuley, and Karl Aberer. Recommendation on Live-Streaming Platforms: Dynamic Availability and Repeot Consumption, pp. 390-30 399. Association for Computing Machinery, New York, NY, USA, 2021. ISBN 97834508845 URL httt::::/dooooorg/100
I. Rechenberg. Evolutionsstrategien. In Berthold Schneider and Ulrich Ranft (eds.), Simalationsmethoden in der Medizin und Biologie, pp. 83 114, Berlin, Heeidelberg, 1978. Springer Berlin Heidelberg. ISBN 778-3-642-81282-11
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. Bpr: Bayesian per- sonalized ranking from implicit. feedback. In Proceedings of the Twenly-Fifth Conference on Uncerlainly in Artificial Intelligence, UAI '09, pp. 452 261, Arlington, Virginia, USA, 2009. AUAI Press. ISBN 9780974903958.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXim:1609.0474 2016.
Otmane Sakhi, Stephen Bonner, David Rohde, and Flavian Vasile. BLOB: A Probabilistic Model for Rec- ommendation That Combines Organic and Bandit Signals. In Proceedings of the 26th ACM SIGKDD In- lernalional Conference on Knowledge Discovery &; Dala Mining, KDD '20, pp. 783 793, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450379984. doi: 10.1145 10.1145/3394465 /3333399.9.3333121.. URL httpp:://ol http://d...r//////////// 1145/3394446 000044448644311..1. 3403121.
Otmane Sakhi, Pierre Alquier, and Nicolas Chopin. PAC-Bayesian Offline Contextual Bandits With Guar- antees. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, vol- une 202 Proceedings of Machine Learning Research, pp. 17777299799. PMI.R, 29 Jul 2023a. URL html. https://proceeding mlr. press//202/sakh1222 html.
Otmane Sakhi, David Rohde, and Alexandre Gilotte. Recommendation. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8) Jun. 2023b. doi: 10.1609/amai. v3718 26158.. URL https://ojs. aaai. org/index. www.s/.pppppp.. htpp/AAA//articce/vvee/// 26158.
Fast Offline Policy Optimization for Large Scale
16

---

Published in Transactions on Machine Learning Research (12/2023)
Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Aduances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL https:// proceedings. serridiinnnnuurppp.p. cctppp//b44411aaaettttoa0oo0oe00 Paper.....
Joe Staines and David Barber. Variational optimization, 2012. URL
4507.
Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In Francis Bach and David Blei (cds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 814 814-823, Lille, France, 07-09 Jul 2015. PMLR. URL https://proceeddiee
mlr. www.spresssviie htt7////aaaaaaaal555a html.
Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miroslav Dudik, John Langford, Damien Jose, and Imed Zitouni. Off-policy evaluation for slate recommendation. In Proceedings of the 31st International Conference on Newral Information Processing Systems, NIPS'17, pp. 3635 3645, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Flavian Vasile, Elena Smirnova, and Alexis Conneau. Meta-prod2vec: Product embeddings using side- information for recommendation, In Proceedings of the 10th ACM Conference on Recommender Sys- tems, RecSys '16 pp. 225 232, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450340359, doi:
(t/////9910.29991110 URL https://doi. org/10. 1145/2959100 0t1.//99991100.29910.0. 2959160.
Mengting Wan and Julian J. McAuley. Item recommendation on monotonic behavior chains. In Sole Pera, Michael D. Ekstrand, Xavier Amatriain, and John O'Donovan (eds.), Proceedings of the 12th ACM Conference on Recommender Systems, RecSys 2018, Voncowver BC, Canada, October 2-7, 2018, pp. 86-94. ACM, 2018. doi: 10. 4244///3240323334003999 URL https://doi.. htt:///ii.oggg////// org/10. 1tt//00..1115555 1145/1240323.333 3240369.
Mengting Wan, Rishabh Misra, Ndapa Nakashole, and Julian J. McAulcy. Fine-grained spoiler detection from large-scale review corpora. In Anna Korhonen, David R. Traum, and Lluís Märquez (eds.), Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers, pp. 2605-2610. Association for Computational Linguistics, 2019. doi:
h1///33/11p19122//// URL https: org/0 1ttp:/1111111111//111111111
Xuanhui Wang, Cheng Li, Nadav Golbandi, Mike Bendersky, and Marc Najork. The lambdaloss framework for ranking metric optimization. In Proceedings of The 27th ACM International Conference on Information and Knowledge Management (CTKM '18), pp. 1313- 2018.
Yuyan Wang, Mohit Sharma, Can Xu, Sriraj Badam, Qian Sun, Tee Richardson, Tisa Chung, Ed H. Chi, and Minmin Chen. Surrogate for long-term user experience in recommender systems. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, pp. 4100-4109, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450393850. doi: 10.1145/ 3534678.3539073. URL https://doi. wttp///............1 114eo0551//3338111111 3539077
Ronald J. Williams. Simple statistical tradieen-fflloowing algorithms for connectionist reinforcement learning. Machine Learning, 8(3):229-255 1992. doi: 10. BBF0992696.
Fen Xia, Tie Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: The- ory and algorithm. In Proceedings of the 25th International Conference on Machine Learning, ICML '08, pp. 1192-1199 1199, New York, NY, USA, 2008. Association for Computing Machinery, ISBN 9781605582054. doi: 10. 11951136666... 1390306. URL https://ddo http://ttoo///////////// org/10 10. 1141 /144/1391156.... 1390306.
17

---

end Published in Transactions on Machine Learning Research (12/2023)
A Appendix
A.1 Accelerating Plackett-Luce training
Algorithm 2:
Categorical Distribution: Rejection sampling using MIPS
Input: li, B, 2, and indexes on B and parameter K, catalogue size P
Output: a which is a sample from P(A= a) = Σ.' (x)
exp(ha(w)) 0x)
01 ...... aK (rg)ort(b=xx)" B)1.
Z' P Pexp(hs(<>) Bax)
Z" Σn exp(h=(x)** B₂) exp(h=(x) (x))Bax) Bax)
PK (c))(h=(x)) 8a, /2" ...., exp(pxx (x)) Bax 2
while True do
~ cat([tail, head], 1442 3'42"
2"
if d-head then
~~ cal(ar)..... ak: Pk)
return end
if d=tail then
Sample q uniformly from the set f1...., P}
Sample u from a uniform distribution
exp(ha(a) 9.)
if
u then
exp(hg(e))
return !
end
end
As it was discussed in the main paper, we can derive a covariance gradient that does not require the computation of the normalizing constant Zz(x):
K
Vol((T)lz) Cov Annma(l)s) F(AK, x),
Σ Volo(a,,z))
1=1
with Cov[A, B| - [[A))(B [[B]) covariance between A scalar function, and B vector. The proof follows:
VoR(TT) (m)( Vo log (o(
E ((A log A:-1) A:-1)]
K
I (x(()) (f(AR (Vefolar,)) Vo log Z 1-1 (x))
Using the log trick, we derive the following equality:
log (x) = (enfal
This equality is then injected in the gradient formula derived above to obtain:
K
P(AK, x), VoR(TT) = Cov Ag)mo(()))
Vofo(ar,))
18

---

Published in Transactions on Machine Learning Research (12/2023)
This concludes the proof. One can see that for K 1, recover the results of Sakhi et al. (2023b). This form of gradient still requires sampling from the policy (-(r)ar) to get good covariance estimation. To lower the time complexity of this step, we can use Monte Carlo techniques such as Importance Sampling/ Rejection Campling/Reeection
Sampling (Owen, 2013) with carefully chosen proposals to achieve fast sampling without sacrificing the accuracy of the gradient approximation.
In Sakhi et al. (2023b), a softmax policy learning algorithm was accelerated by approximating the gradients using self normalized importance sampling algorithm with proposal distribution that can both exploit the MIPS structure and is a good approximation of the target softmax distribution. This idea also be used to motivate a rejection sampling algorithm, as similar proposal can be shown to form an envelope of the target density. can also be extended from softmax to Plackett-Luce. When the idea of rejection sampling is combined with the MIPS proposal, it results in the rejection sampling algorithm shown in Algorithm 2. While Algorithm can be extended the slate policy case, enabling the fast evaluation of the covariance gradient estimator, it will still suffer from high variance gradient estimates.
A.2 LRP: Latent Random Perturbation
The method presented in the main paper can be generalized. Instead of focusing on Gaussian distributions, the latent perturbation can be done by any continuous distribution resulting in the more general LRP: Latent Random Perturbation policy. For a context x and a slate Ak, its expression is given by:
T (Ax(=) Fune [1 [Ax = argsort {(ho(z) + +) Bal |]] d'EA
with Q a continuous distribution on the latent space R', the LRP policy defines a smoothed, differentiable relaxation of the deterministic policy by by adding noise in the latent space R This class of policies present desirable propertics:
Fast Sampling. an argsorl as:
For a given æ, sampling from a LRP policy boils down to sampling from Q and computing
Ak ~ of (-Iz) Ak = argsort
K + { e ~~ Q
a'EA
Let us suppose the sampling from Q is easy. As the action embeddings 3 are fixed, and we are performing a perturbation in the latent space, we can set (z) he(x) +e which makes sampling compatible with approx- imate MIPS technology making the sampling achievable in Ollog P), better than the sampling complexity O(P log K) of the Placett-Luce family.
Well behaved gradient. Similar to the gradient under the Plackett-Luce policy (6), we can derive a score function gradient for LRP policies. For a given x, let us write its expected reward under =g.
(((T)1z) [z) E AN (11) [[A
h 20(x) - h h= +e, e~ Q
Ax = argsort {h" Bar
Enr (f (Ak (x) + +c],a)]
a'Ed
Ox(x) is the induced distribution on the user embeddings. (x(x) has tractable density if we choose classical noise distribution Q (e.g. Gaussian). Working with the induced distribution 2x(x) transforms the learning parameters 0 to parameters of the distribution, allowing us to derive the following gradient:
V To xx) = VpEn-os(a) (AA
(F (h), lo (z, h)],
19

---

Published in Transactions on Machine Learning Research (12/2023)
with log (2, h) the log density of Qo(z) evaluated in h. We can obtain unbiased gradient estimate by sampling h ~ Qa (x)):
((A))=(AA(() log h).
(12)
This gradient expression solves all issues that the Plackett-Luce gradient estimate suffered from:
Fast Gradient Estimate. This gradient can be approximated in a sublinear complexity O(log P). Building an estimator of the gradient follows these three steps: (1) We sample h ~ Qo which boils down to adding the noise ~ Q to ha(x). This can be done in a complexity O(L) < O(P) if Q is chosen properly. (2) We evaluate the gradient of the log density Ve log (0 h) on h. With a well-chosen 2, this can be done in (L) as we do not need to normalize over a large discrcte action space. (3) We generate the slate [h). This boils down to computing an argsort which can be accelerated using approximate MIPS technology, giving complexity of Olog P)-
Better Variance. LRP's gradient estimate have better stalistical properties for two main reasons: (1) The gradient is defined as an expectation under a continuous distribution on the latent space R², instead of an expectation under a large discrete action space A of size P > L. This can have an impact on the variance of the gradient estimator as the sampling space is smaller. (2) The approximate gradient defined in Equation (12) does not depend on the slate size K. This results in a variance that does not grow with K. This means that we will notice substantial gains when Training policies with larger slates.
A.3 Additional Experiments
A.3.1 Robustness of the results
We conduct a further simulation study to be sure that the results obtained in the main paper are robust both to initialisation and to the slate size K. To this end, we repeat the same experimental setup in the performance subsection; the optimization of our algorithms for 10 minutes and evaluate the obtained policy on the validation split. For each dataset, we define two settings; a setting with a moderate slate size of K = 5 and one with a bigger slate size of K = 100. The training procedure is repeated for 6 different seeds, and we present the average performance and the standard error for different values of {1, 10, 100}; the number of samples used to approximate the gradient. We present results of two different natures:
use all three datasets, and we fix the latent space dimension L = 100. We run
The performance on the validation set, of the obtained policies after training them with different algorithms, under the same time constraint of 10 minutes, reported in Table 3.
The performance on the training set, of the obtained policies, after training them for the same number of iterations. As training with PL algorithms can be very slow, we fix the number of iterations to the iterations done by PL-PG in 10 minutes. The results of these experiments are reported in Table 4.
Let us first focus on the performance obtained after training policies under the same time budget. Looking at Table 3, we can clearly observe that LGP, especially its MIPS accelerated version, always yields the best performing policies no matter the setting adopted. The obtained results are significant, as the standard error is small compared to the difference of performance between the methods. These obscrvations confirm that the LGP family is perfectly suited for industrial applications, as it iterates faster and is robust to different settings. It is noteworthy that the PL family cannot run with big Monte Carlo samples S, especially in applications with large action spaces, as it suffers from large memory footprint.
For the sake of completeness, we also report in Table 4, the performance of our decision systems after training them with different approaches under a fixed number of iterations. One can observe that PL-Rank results in the best decision systems, followed by the LGP family. These results suggest that by exploiting the linearity of the reward, the gradient estimates derived by PL-Rank enjoy better variance than the gradient estimates
20

---

Published in Transactions on Machine Learning Research (12/2023)
of the LGP family. The application of PL-Rank: however is only restricted to linear rewards, contrary to newly proposed approach that does not make any assumptions on the structure of the reward. This means that when the reward is complex, LGP methods should be adopted, as they offer a better alternative to the naive, gradient estimate of PL-PG.
Algorithm
S
MovieLens
Twitch
GoodReads
K 5
K 100
K 5
K 100
K 5
K = 100
S=1
0.834 + 0.003
0.599 0.002
0.438 + 0.009
=
0447 0.002
0.396 = 0.007
LGP-MIPS
S 10
0.866 0.003
0.881 0.003
0.567 1 0.007
0.563 0.004
0.539 0.004
0.554 1 0.004
S = 100
0.865 + 0.002
0.867 1 0.002
0.607 + 0.005
0.609 0.005
0.580 + 0.001
0.592 + 0.002
5 = 1
0.753 1 0.005
0.776 1 0.004
0.171 1 0.004
0.195 0.004
0,259 1 0.013
0.278 1 0.013
LGP
== 10
0.716 + 0.004
0.744 + 0.005
0.133 + 0.002
0.152 + 0.003
0.227 + 0.012
0.244 = 0.012
= 100
0.700 + 0.003
0.721 0.003
0.097 + 0.002
0.111 0.003
+
0.204 + 0.010
5
0.750 0.004
0.769 0.005
0.103 + 0.003
0.113 0.003
0.188 + 0.009
0,200 0.010
PL-Rank
8 = 10
0.584 + 0.013
0.597 + 0.010
0.087 + 0.002
0.096 + 0.003
0.179 + 0.009
0.191 + 0.010
S = 100
0,342 + 0.015
0.353 + 0.016
0.084 + 0.002
0,093 + 0.003
N/A
N/A
S S 10
0.347 0.019
U.356 + 0.020
0,084 + 0.002
0.093 0.002
0.181 + 0.009
0.194 = 0.009
PL-PG
0.345 0.021
0.354 = 0.021
0.0844 + 0.002
0.093 0.003
0.180 + 0.009
0.192 + 0.010
5 = 100
0.323 1: 0.018
0.332 + 0.018
0.084 + 0.002
0.093 + 0.003
N/A
N/A
Table 3: Performance by time budget (10 minutes). Results obtained by the different algorithms while changing the slate size K and the number of Monte Carlo samples S. All runs were completed in 10 minutes. We report in this table the average performance and its standard error over different seeds. All statistics reported on the validation set. The proposed algorithms give robust results in different settings.
Algorichm
S
MovieLens
Twitch
GoodReads
K=
K= 100
K 5
100
5
K 100
S=1
0.645 - 0.011
0.307 0.004
0.098 + 0.004
0.107 = 0.005
0.192 + 0.010
0,205 0.011
LCP-MIPS
S = 10
0.528 = 0.012
0.537 : 0.011
0.086 = 0.003
0.096 = 0.004
0.179 + 0.007
0.194 = 0.007
8 = 100
0.361 + 0.016
0.374 4: 0.017
0.079 1 0.005
0.088 : 0.006
0.185 + 0.007
0.198 0.006
S 1
0.623 0.009
0.646 4.06000.00 0.004
0.094 = 0.004
0.108 = 0.003
0.192 + 0.010
0.207 = 0.011
LGP
S = 10
0.513 0.012
0.324 0.010
0.086 = 0.003
0.096 = 0.004
0.179 + 0.007
0.193 = 0.007
$ = 100
0.360 = 0.015
0.372 + 0.016
0.081 = 0.005
0.088 = 0.005
0.184 + 0.007
0.197 0.006
5=1
0.750 0.006
0.779 0.003
0.102 = 0.004
0.113 = 0.005
0.188 + 0.010
0.203 0.010
PL-Rank
S = 10
0.587 = 0.011
0.600 + 0.009
0.082 + 0.003
0.092 = 0.003
0.176 + 0.007
0.190 0.007
$ = 100
0.332 + 0.016
0.334 + 0.016
0.081 + 0.005
0.088 = 0.005
N/A
N/A
S
0.342 1 0.017
0.356 1 0.019
0.084 1 0.004
0.096 = 0.004
0.181 1 0.010
0.196 1 0.004
PL-PG
10
0.348 1 0.018
0.355 1 0.020
0.079 1 0.002
0.090 = 0.003
0.176 1 0.007
0.190 1: 0.007
= 100
0.305 + 0.018
0.313 + 0.018
0.081 + 0.005
0.088 - 0.005
N/A
N/A
Table 4: Performance by iteration. Results obtained with the different algorithms while changing the slate size K and the number of Monte Carlo samples S. The number of iterations is decided by the slowest iterating algorithm (PL-PG) after rumning for 10 minutes. We report in this table the average performance and its standard error over 6 different seeds. PL-Rank gives the best results, followed by the LGP family.
A.3.2 Effect of fixing 3
In this section, we want to validate the intuition built throughout the paper about the behaviours of both the Plackett-Luce and LGP policy classes. We focus MovieLens (Harper & Konstan, 2015), medium scale dataset that allows to test all our methods, regardless of their potential to scale to harder problems. For all experiments in this section, we fix L = 100 < P and we study the impact of fixing the action embeddings B. As discussed in Section 3, having the embeddings fixed is a natural solution to improve the learning of these large scale decision systems as it can reduce both the variance of the gradient estimates and the running time of the optimization procedure. To validate this, we focus on the Plackett-Luce policy and define two slightly different parametrizations:
Learn 0: this the parametrization introduced in Equation (10), with fixed and we only learn the parameter 0.
21

---

Published in Transactions on Machine Learning Research (12/2023)
-143
333
Loo Nartnncc of Crwtenn www.eiiirrrrioo
0.22
923
-155
Training PL-PG: Training
2500
viee 7506 10830 22585 39993 37903 2030
2500
5.000 15:00
15303 32300 31500 23030
35000
Figure 3: Experiments on the MovieLens dataset: We look at the effect of fixing the action embeddings 3 on the training of Plackett-Laic policies. Training results in slow optimization procedure and gradient estimates with bigger variance.
Learn 8: We treat 3 a parameter after initializing it with the SVD values. Because our user embedding function he is linear in 0, we get rid of this parameter as it becomes redundant once B can be optimized. This gives the following parametrization:
(x,,a)XXxx A, fs(a,x) M())a
We train Plackett-Luce policy with both parametrizations for epoch, while fixing the slate size K = 2 and the Monte Carlo samples to S = 1. In this experiment, our objective is not to produce the best policies but to understand how fixing the embeddings can impact the optimization procedure. We report in Figure 3 the evolution of both the gradient estimate variance and the reward on the training data for both parametrizations. We can observe that treating 3 as a parameter to optimize, even when initialized properly leads slow learning. The variance of the gradient estimate when learning is bigger than the variance when learning 0 with fixed, and this will get bigger for problems with larger action spaces P > L. We suspect that this is one of the reasons that explain the pace of learning when optimizing B. The same phenomena was observed in Sakhi et al. (2023b). The same experiments demonstrated that training 0 alone was twice as fast as training 3 in this experiment. This suggests that fixing 3 to good value is beneficial for training large scale decision systems both in terms of ileration efficiency. We advocale for fixing the action embeddings B when learning large scale MIPS systems.
A.3.3 Impact of the slate size K.
One of the caveats of the Plackett-Luce slate policy is that its gradient estimate has variance that grows with the slate size K, reducing its scope of applications to modest slate sizes. the gradient estimate of LGP however docs not suffer from this issuc, and we want to showcase that with a simple experiment. Wo derived gradient estimates for LGP- methods that have a variance that scales O(1/0²). Although the standard deviation can be treated as hyperparameter depending on the task, allow fair comparison of the gradient variance of these methods, we set to particular value coming from the following observation. For particular action a:
~ ((h((o)), hTB. Be ~ Ba, o² Ba11))
h2 B, ho(x)) 3a ca
T
with 6a N'O0, (a (211)) This can be interpreted as adding scaled guassian noise the score of action a. As we add standardized Gumbel noise 7a G(0, 1) to the action scores to define the Plackett-Luce policy, we want, for a fair comparison, to have:
Va E A, al|Ball
22

---

Published in Transactions on Machine Learning Research (12/2023)
Log Variance of Gradient Estimles
Number of training Reeations
RLPG
PL-G,, K=
R.FG,
LGP,K- 5
LSP.
Figure 4: Impact of the slate size K on the log variance of the gradient estimate of both PL-PG and LGP on MovieLens. Contrary to LGP, PL-PG has a gradient estimate with a variance that grows with K.
One heuristic approximately achieve that is to compute the empirical mean of the 3 norms B SGEel199a1 and set 1/B. This value will be used for this experiment.
We use the MovieLen dataset, and train the LGP policy without exploiting the MIPS inder on B, and Plackett-Luce with the parametrization of Equation (10) for 10 epochs with S = 1, while varying the slate size E (2, 5, 10). Note that all policies are initialized with the same random seed for a fair comparison. We report the evolution of the variance of the gradient istte alongside the reward on the training data. The results of these experiments are presented in Figure
Focusing on the evolution of the variance, grows with K contrary to LGP that has a variance of its gradient estimate staying al the same scale no matter the value of K. We argue that this has a direct impact on the optimization procedure as for the same value of K, we observe in Figure that LGP-based methods outperform Plackett-Luce learning schemes consistently, making a good candidate for learning slate policies.
that Plackett-Luce does indeed have variance that
A.3.4 Experiments with Neural Networks.
For these experiments, we want to explore deep policies and see if we can still empirically validate our findings in this case as well. For this, we adopt the following function to compute the user embedding ha,
h (X) sigmoid (M()) 02.
(13)
which boils down to sigmoid, two layer feed forward neural network with both O and 0g of size [I., L.. We run PL-PG, PL-Rank and LGP-MIPS on the three datasets, for the same running time (60 minutes) and cross-validate the learning rate choosing the best value for each algorithm. We aggregate the results on Figure 5. The plot suggests that even for deep policies, LGP-MIPS outperforms Plackett-Luco- methods on all datascts and for different values of the number of Monte Carlo samples We also obscrve that. training in this case more unstable, especially for Plackett-Luuce-basee methods having parameters accentuate the variance problems of their gradient estimates. It is noteworthy that, the reward obtained with deep policies in our experiment is less than the one achieved by linear policios. This suggests that deep policies require additional care when training, and we might want to stick to simple policies if we are interested in fast and reliable optimization.
23

---

Published in Transactions on Machine Learning Research (12/2023)
Movielens
Twitch
Goodreads
0.65
Revard Valcattn
0.6-
0.3
0.40
030
0.4
0.30
020
0.15
Revere bal0000e 035
0.5
0.5
0.7
0.8
0.45
0.5
0.10
0.4
3.3
0.35
0.2
0.2
1.0
Bewerd on Valleaton D3ta
0.5
0.5
5.4
5- 100
0.5
3.3
0.3
0.4
LGP-MIPS
0.3
PL-Rank
3
6
3
30
Number of avaluationss
Number of wodlustion
Number wvalustions
Figure 5: The performance of slate decision functions, with Neural Network Backbones, obtained by our different training algorithms after running the optimization for 60 minutes.
24


Reviews:
[{"review_id": "1Bs77h2W0n", "reviewer": "Reviewer_6C5d", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\n1. The problem is well-motivated and practical. \n\n2. The idea of latent space perturbation is intuitive. The derivation of the gradient estimates discussion of its advantage is sound and insightful.\n\n3. The improvement in experiments under same training time is significant.\n\n4. The writing is clear and easy to follow.\n\n\nWeaknesses\n\nNo major weaknesses were identified. I have some minor concerns:\n\n1. I would suggest the authors make formal statements regarding statistical improvement of LGP. 1) Is the gradient estimates unbiased? I noticed related discussion under \"Well behaved gradient\". The authors may consider using a theorem to formally make the claim.  2) Similar question regarding \"Better variance\". Could the authors provide a formal statement (and proofs) to compare the variance of gradient estimates between LGP and baseline?\n\n2. In the experiments, the authors evaluate LGP and baselines under the same training time (60minutes) and showed the effectiveness in accelerating computation. I would suggest the authors also report results under the same training iterations to validate the impact of smaller  variance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studied slate recommendation in offline contextual bandit setting. Previous works commonly optimize the ranking policy under Plackett-Luce distribution. The authors aim to solve the issues with Plackett-Luce policy class such as slow in computation and suffering large variance. The authors proposed Latent Gaussian Perturbation (LGP) with the key idea of relaxing the objective to be differentiable by perturbing in the latent space instead of in the action space. LGP reduces computation complexity and enjoys smaller variance in gradient estiamtes. Empirical results on real-world datasets validated the effectiveness of proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kx5hOwiPLA", "reviewer": "Reviewer_Tht2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The topic is interesting, and the method is sound. My opinion is that the paper is not well structured, and this makes its reading hard. For instance, the problem formulation is entwined with the introduction.\n\nMoreover, I think the authors should put more effort into stating explicitly when they are presenting something from the literature and when it is a novel contribution. For instance, section 2 is all about the PL policies, which are part of the literature; therefore, I think using 1.5 pages is not focusing the paper on the most interesting part.\n\nFinally, I think the paper lacks some formalism in stating the properties of the developed method. For instance, I would have expected some formal theorem/lemmas showing the properties of what the authors proposed. At the same time, they only provide informal statements and defer the discussion to the appendix. I think you should put some effort into reformulating such statements in a formal way.\n\nMinor:\n- \"In this paper we demonstrate such an algorithm\". Not clear\n- The introduction proposes both a description of the problem and the problem formulation. I suggest you to reorganize such a section to highlight the two elements. \n- you need to define \\nu(\\mathcal{X}) in equation before Eq. (3)\n- add punctuation to formulas\n- \"it induces properties that are hard to deal with:\" Please explain\n- add a textual description of the pseudocode", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a novel algorithm for slates learning. The advantages of the proposed techniques, namely LGP, are that they show a better time complexity in terms of the size of the action space P. The authors provide empirical evidence that the propose method is also providing better reward than other state-of-the-art available options.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses for details-. The main changes are related to the structure and writing of the paper to have a clear picture of the contribution and to provide formal statements for the claims requiring formal proof.", "broader_impact_concerns": "I do not foresee any ethical concerns about the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VKbjVOOwnl", "reviewer": "Reviewer_PZmb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n*) The proposed Latent Gaussian perturbation policy is conceptually simple and can be argued to have several advantages over the common Plackett-Luce policy. In the experiments, the proposed algorithms clearly outperform existing ones.\n\nWeaknesses:\n*) The empirical evaluation is rather limited (see my requested changes below); in particular, the experiments do not seem to report average results and do not provide any standard deviations\n*) The paper is cumbersome to read, partly because it tries to introduce the most general concept but then only considers a special case (e.g., general decision functions -> parametric relevance functions -> parametric relevance functions with fixed action embeddings, or latent random perturbation -> latent Gaussian perturbation). I would recommend to shorten the presentation and refrain from providing the general description where only the concrete description is needed in order to make the paper more comprehensible and use the space for additional experiments.\n\nThere are a number of typos / minor issues:\n*) Please refer to appendix sections rather than just saying “can be found in the Appendix”\n*) Section 3, first sentence of second paragraph: some word is missing \n*) Page 8: making the evaluation of ITS THE log density gradient easy \n*) Page 9, first line: start sentence with “The” rather than “the”\n*) Section 5, paragraph on Learning to Rank: remove white space before the period; later a period is missing\n*) Page 8, last line: the notation UI for the user-item interaction session is unclear and one might confuse it for a product of U and I. \n*) Page 18, last sentence: on the task, TO allow", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of slate recommendation via policy learning and proposes Latent Gaussian perturbation policies as replacement for the commonly used Plackett-Luce policies, thus addressing some of the shortcomings of the Plackett-Luce policies (high computational cost and high variance of gradient estimator).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the paper needs to clearly show the proposed method’s benefits in an extensive empirical evaluation (the various runtime discussions are nice, but in the end the authors provide only asymptotic *upper* bounds). To that end, at a minimum, I would like to see\n*) plots with average results + confidence intervals / standard deviations (and an explanation how these are obtained)\n*) a better explanation why PL-PG does not work in the considered setting (what happens if one further increases S or the batch size or decreases the learning rate?)\n*) performance as a function of the number of epochs rather than runtime – please also provide some details how runtime is measured\n*) experiments with different values of K\n*) a more thorough investigation of the variance of the different gradient estimators, discussed in the main part of the paper\n*) plots that show the expected reward under the policy (the optimization objective)", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers appreciated the considered problem and also the proposed approach. However, initially, there were concerns regarding experimental evaluation and also presentation of the paper. The concerns regarding experiments have been partly addressed by adding new experimental results but these results should also be carefully discussed in the main paper and not only in the appendix - in this regard the paper needs to be improved. Regarding presentation, two reviewers raised concerns in their initial reviews but were also not fully satisfied with the changes made by the authors. The authors implemented several changes addressing parts of the concerns but avoided making bigger adjustments to, for instance, make the paper more "comprehensible" (PZmb) by focussing the presentation more on the actually addressed aspects. I also saw the authors' response in that regard and would suggest to only introduce the directly relevant parts first and later have a more general discussion as needed. Considering all this, I am recommending a minor revision addressing the open concerns of the reviewers.
Side note: The reviewers also suggested providing theoretical statements/insights but I agree with the authors that these are not necessary for accepting the paper and might not be easy to derive.
Decision: Accept (poster)