Title: SEQ2SLATE: RE-RANKING AND SLATE OPTIMIZATION WITH RNNS

Abstract: Ranking is a central task in machine learning and information retrieval. In this task, it is especially important to present the user with a slate of items that is appealing as a whole. This in turn requires taking into account interactions between items, since intuitively, placing an item on the slate affects the decision of which other items should be placed alongside it. In this work, we propose a sequence-to-sequence model for ranking called seq2slate. At each step, the model predicts the next item to place on the slate given the items already selected. The recurrent nature of the model allows complex dependencies between items to be captured directly in a flexible and scalable way. We show how to learn the model end-to-end from weak supervision in the form of easily obtained click-through data. We further demonstrate the usefulness of our approach in experiments on standard ranking benchmarks as well as in a real-world recommendation system.

1. INTRODUCTION:

Ranking a set of candidate items is a central task in machine learning and information retrieval. Many existing ranking systems are based on pointwise estimators, where the model assigns a score to each item in a candidate set and the resulting slate is obtained by sorting the list according to item scores (Liu et al., 2009) . Such models are usually trained from click-through data to optimize an appropriate loss function (Joachims, 2002) . This simple approach is computationally attractive as it only requires a sort operation over the candidate set at test (or serving) time, and can therefore scale to large problems. On the other hand, in terms of modeling, pointwise rankers cannot easily express dependencies between ranked items. In particular, the score of an item (e.g., its probability of being clicked) often depends on the other items in the slate and their joint placement. Such interactions between items can be especially dominant in the common case where display area is limited or when strong position bias is present, so that only a few highly ranked items get the user's attention. In this case it may be preferable, for example, to present a diverse set of items at the top positions of the slate in order to cover a wider range of user interests. A significant amount of work on learning-to-rank does consider interactions between ranked items when training the model. In pairwise approaches a classifier is trained to determine which item should be ranked first within a pair of items (e.g., Herbrich et al., 1999; Joachims, 2002; Burges et al., 2005) . Similarly, in listwise approaches the loss depends on the full permutation of items (e.g., Cao et al., 2007; Yue et al., 2007) . Although these losses consider inter-item dependencies, the ranking function itself is pointwise, so at inference time the model still assigns a score to each item which does not depend on scores of other items. There has been some work on trying to capture interactions between items in the ranking scores themselves (e.g., Qin et al., 2008; 2009; Zhu et al., 2014; Rosenfeld et al., 2014; Dokania et al., 2014) . Such approaches can, for example, encourage a pair of items to appear next to (or far from) each other in the resulting ranking. Approaches of this type often assume that the relationship between items takes a simple form (e.g., submodular) in order to obtain tractable inference and learning algorithms. Unfortunately, this comes at the expense of the model's expressive power. In this paper, we present a general, scalable approach to ranking, which naturally accounts for high-order interactions. In particular, we apply a sequence-to-sequence (seq2seq) model (Sutskever et al., 2014) to the ranking task, where the input is the list of candidate items and the output is the resulting ordering. Since the output sequence corresponds to ranked items on the slate, we call this model sequence-to-slate (seq2slate). The order in which the input is processed can significantly affect the performance of such models (Vinyals et al., 2016) . For this reason, we often assume the availability of a base (or "production") ranker with which the input sequence is ordered (e.g., a simple pointwise method that ignores the interactions we seek to model), and view the output of our model as a re-ranking of the items.

To address the seq2seq problem, we build on the recent success of recurrent neural networks (RNNs) in a wide range of applications (e.g., Sutskever et al., 2014) . This allows us to use a deep model to capture rich dependencies between ranked items, while keeping the computational cost of inference manageable. More specifically, we use pointer networks, which are seq2seq models with an attention mechanism for pointing at positions in the input (Vinyals et al., 2015b) . We show how to train the network end-to-end to directly optimize several commonly used ranking measures. To this end, we adapt RNN training to use weak supervision in the form of click-through data obtained from logs, instead of relying on ground-truth rankings, which are much more expensive to obtain. Finally, we demonstrate the usefulness of the proposed approach in a number of learning-to-rank benchmarks and in a large-scale, real-world recommendeation system.

2. RANKING AND SLATE OPTIMIZATION AS SEQUENCE PREDICTION:

The ranking problem is that of computing a ranking of a set of items (or ordered list or slate) given some query or context. We formalize the problem as follows. Assume a set of n items, each represented by a feature vector x i ∈ R m (which may depend on a query or context). Let π ∈ Π denote a permutation of the items, where each π j ∈ {1, . . . , n} denotes the index of the item in position j. Our goal is to predict the output ranking π given the input items x. For instance, given a specific user query, we might want to return an ordered set of music recommendations from a set of candidates that maximizes some measure of user engagement (e.g., number of tracks played).

In the seq2seq framework, the probability of an output permutation, or slate, given the inputs is expressed as a product of conditional probabilities according to the chain rule:

EQUATION

This expression is completely general and does not make any conditional independence assumptions.

In our case, the conditional p(π j |π <j , x) ∈ ∆ n (a point in the n-dimensional simplex) models the probability of any item being placed at the j'th position in the ranking given the items already placed at previous positions. Therefore, this conditional exactly captures all high-order dependencies between items in the ranked list, including those due to diversity, similarity or other interactions. Our setting is somewhat different than a standard seq2seq setting in that the output vocabulary is not fixed. In particular, the same index (position) is populated by different items in different instances (queries). Indeed, the vocabulary size n itself may vary per instance in the common case where the number of items to rank can change. This is precisely the problem addressed by pointer networks, which we review next.

POINTER-NETWORK ARCHITECTURE FOR RANKING:

We employ the pointer-network architecture of Vinyals et al. (2015b) to model the conditional p(π j |π <j , x). A pointer network uses non-parametric softmax modules, akin to the attention mechanism of Bahdanau et al. (2015) , and learns to point to items in its input sequence rather than predicting an index from a fixed-sized vocabulary. Our seq2slate model, illustrated in Fig. 1 , consists of two recurrent neural networks (RNNs): an encoder and a decoder, both of which use Long Short-term Memory (LSTM) cells (Hochreiter and Schmidhuber, 1997) . At each encoding step i ≤ n, the encoder RNN reads the input vector x i and outputs a d-dimensional vector e i , thus transforming the input sequence {x i } n i=1 into a sequence of latent memory states {e i } n i=1 . At each decoding step j, the decoder RNN outputs a d-dimensional vector d j which is used as a query in our attention function. The attention function takes as input the query d j ∈ R d and the set of latent memory states computed by the encoder {e i } n i=1 and produces a probability distribution over the next item to include in the output sequence as follows:

s j i = v tanh (Wenc • ei + W dec • dj) (2) p θ (πj = i|π<j, x) ≡ p j i = e s j i / k / ∈π <j e s j k if i / ∈ π<j 0 if i ∈ π<j ,

where W enc , W dec ∈ R d×d and v ∈ R d are learned parameters in our network, denoted collectively by parameter vector θ. The probability p j i = p θ (π j = i|π <j , x), is obtained via a softmax over the remaining items and represents the degree to which the model points to input i at decoding step j. To output a permutation, the p j i are set to 0 for items i that already appear in the slate. Once the next item π j is selected, typically greedily or by sampling (see below), its embedding x πj is fed as input to the next decoder step. The input of the first decoder step is a learned d-dimensional vector, denoted as go in Fig. 1 . Importantly, p θ (π|x) is differentiable for ant fixed permutation π which allows gradient-based learning (see Section 3). We note the following. (i) The model makes no explicit assumptions about the type of interactions between items. If the learned conditional in Eq. ( 2) is close to the true conditional in Eq. ( 1), then the model can capture rich interactions-including diversity, similarity or others. We demonstrate this flexibility in our experiments (Section 4). (ii) x can represent either raw inputs or embeddings thereof, which can be learned together with the sequence model. (iii) The computational cost of inference, dominated by the sequential decoding procedure, is O(n 2 ), which is standard in seq2seq models with attention. We also consider a computationally cheaper single-step decoder with linear cost O(n), which outputs a single vector p 1 , from which we obtain π by sorting the values (similarly to pointwise ranking).

3. TRAINING WITH CLICK-THROUGH DATA:

We now turn to the task of training the seq2slate model from data. A typical approach to learning in ranking systems is to run an existing ranker "in the wild" and log click-through data, which are then used to train an improved ranking model. This type of training data is relatively inexpensive to obtain, in contrast to human-curated labels such as relevance scores, ratings, or rankings (Joachims, 2002) . Formally, each training example consists of a sequence of items {x 1 , . . . , x n } and binary labels (y 1 , . . . , y n ), with y i ∈ {0, 1}, representing user feedback (e.g., click/no-click). Our approach easily extends to more informative feedback, such as the level of user engagement with the chosen item (e.g., time spent), but to simplify the presentation we focus on the binary case. Our goal is to learn the parameters θ of p θ (π j |π <j , x) (Eq. ( 2)) such that permutations π corresponding to "good" rankings are assigned high probabilities. Various performance measures R(π, y) can be used to evaluate the quality of a permutation π given the labels y, for example, mean average precision (MAP), precision at k, or normalized discounted cumulative gain at k (NDCG@k). Generally speaking, permutations where the positive labels rank higher are considered better. In the standard seq2seq setting, models are trained to maximize the likelihood of a target sequence of tokens given the input, which can be done by maximizing the likelihood of each target token given the previous target tokens using Eq. ( 1). During training, the model is typically fed the ground-truth tokens as inputs to the next prediction step, an approach known as teacher forcing (Williams and Zipser, 1989) . Unfortunately, this approach cannot be applied in our setting since we only have access to weak supervision in the form of labels y (e.g clicks), rather than ground-truth permutations. Instead, we show how the seq2slate model can be trained directly from the labels y.

3.1. TRAINING USING REINFORCE:

One potential approach, which has been applied successfully in related tasks (Bello et al., 2017; Zhong et al., 2017) , is to use reinforcement learning (RL) to directly optimize for the ranking measure R(π, y). In this setup, the objective is to maximize the expected ranking metric obtained by sequences sampled from our model: E π∼p θ (.|x) [R(π, y)]. One can use policy gradients and stochastic gradient ascent to optimize θ. The gradient is formulated using the popular REINFORCE update (Williams, 1992) and can be approximated via Monte-Carlo sampling as follows:

EQUATION

where k indexes ranking instances in a batch of size B, π k are permutations drawn from the model p θ and b(x) denotes a baseline function that estimates the expected rewards to reduce the variance of the gradients.

3.2. SUPERVISED TRAINING:

RL, however, is known to be a challenging optimization problem and can suffer from sample inefficiency and difficult credit assignment. As an alternative, we propose supervised learning using the labels y. In particular, rather than waiting until the end of the output sequence (as in RL), we wish to give feedback to the model at each decoder step. Consider the first step, and recall that the model assigns a score s i to each item in the input. We define a per-step loss (s, y) which essentially acts as a multi-label classification loss with labels y as ground truth. Two natural, simple choices for are cross-entropy loss and hinge loss:

EQUATION

hinge (s, y) = max{0, 1min i:yi=1

s i + max j:yj =0 s j } ,

where ŷi = y i / j y j , and p i is a softmax of s, similar to Eq. ( 2). Intuitively, with cross-entropy loss we try to assign high probabilities to positive labels (see also Kurata et al., 2016) , while hinge loss is minimized when scores of items with positive labels are higher than scores of those with negative labels. Notice that both losses are convex functions of the scores s. To improve convergence, we consider a smooth version of the hinge-loss where the maximum and minimum are replaced by their smooth counterparts: smooth-max(s; γ) = 1 γ log i e γsi (and smooth minimum is defined similarly, using min i (s i ) =max i (-s i )).

If we simply apply a per-step loss from Eq. ( 4) to all steps of the output sequence while reusing the labels y at each step, then the loss is invariant to the actual output permutations (e.g., predicting a positive item at the beginning of the sequence has the same cost as predicting it at the end). Instead, we let the loss at each decoding step j depend on the items already chosen, so no further loss is incurred after a label is predicted correctly. In particular, for a fixed permutation π, define the sequence loss:

EQUATION

where S = {s j } n j=1 , and π<j (s j , y) depends only on the indices in s j and y which are not in the prefix permutation π <j = (π 1 , . . . , π j-1 ) (see Eq. ( 4)). Including a per-step weight w j can encourage better performance earlier in the sequence (e.g., w j = 1/ log(j + 1)). Furthermore, if optimizing for a particular slate size k is desired, one can restrict this loss to just the first k output steps.

DECODING POLICIES DURING TRAINING:

Since teacher-forcing is not an option, we resort to feeding the model its own previous predictions, as in Bengio et al. (2015) ; Ranzato et al. (2016) . In this case, the permutation π is not fixed, but rather depends on the scores S. Specifically, we consider two policies for producing a permutation during training, sampling and greedy decoding, and introduce their corresponding losses.

Greedy policy:

The greedy policy consists of selecting the item that maximizes p θ (•|π <j , x) at every time step j. The resulting permutation π * then satisfies π * j = argmax i p θ (π j = i|π * <j ) and our loss becomes L π * . The greedy policy loss is not continuous everywhere since a small change in the scores s may result in a jump between permutations, and therefore L π . Specifically, the loss is non-differentiable when any s j has multiple maximizing arguments. Outside this measure-zero subspace, the loss is continuous (almost everywhere), and the gradient is well-defined. Sampling policy The sampling policy consists of drawing each π j from p θ (•|π <j , x). The corresponding loss E[L] = π p θ (π)L π (θ) is differentiable everywhere since both p θ (π) and L π (θ) are differentiable for any permutation π (See appendix for a direct derivation of E[L] as a function of S). In this case, the gradient is formulated as:

EQUATION

which can be approximated by:

EQUATION

where b(x k ) is a baseline that approximates L π k (θ). Applying stochastic gradient descent intuitively decreases both the loss of any sample (right term) but also the probability of drawing samples with high losses (left term). Notice that our gradient calculation differs from scheduled sampling (Bengio et al., 2015) which instead computes the loss of the sampled sequences (right term) but ignores the probability of sampling high loss sequences (left term). We found it helpful to include both terms, which may apply more generally to training of sequence-to-sequence models (Bengio et al., 2015; Goyal et al., 2016) .

For both training policies, we minimize the loss via stochastic gradient descent over mini-batches in an end-to-end fashion.

4. EXPERIMENTAL RESULTS:

We evaluate the performance of our seq2slate model on a collection of ranking tasks. In Section 4.1 we use learning-to-rank benchmark data to study the behavior of the model. We then apply our approach to a large-scale commercial recommendation system and report the results in Section 4.2. Implementation Details We set hyperparameters of our model to values inspired by the literature. All experiments use mini-batches of 128 training examples and LSTM cells with 128 hidden units. We train our models with the Adam optimizer (Kingma and Ba, 2014) and an initial learning rate of 0.0003 decayed every 1000 steps by a factor of 0.96. Network parameters are initialized uniformly at random in [-0.1, 0.1]. To improve generalization, we regularize the model by using dropout with probability of dropping p dropout = 0.1 and L2 regularization with a penalty coefficient λ = 0.0003. Unless specified otherwise, all results use supervised training with cross-entropy loss xent and the sampling policy. At inference time, we report metrics for the greedy policy. We use an exponential moving average with a decay rate of 0.99 as the baseline b(x) in Eq. (3) and Eq. ( 6). When training the seq2slate model with REINFORCE, we use R = NDGC@10 as the reward function and do not regularize the model. We also considered a bidirectional encoder RNN (Schuster and Paliwal, 1997) but found that it did not lead to significant improvements in our experiments.

4.1. LEARNING-TO-RANK BENCHMARKS:

To understand the behavior of the proposed model, we conduct experiments using two learning-torank datasets. We use two of the largest publicly available benchmarks: the Yahoo Learning to Rank Challenge data (set 1),1 and the Web30k dataset. We adapt the procedure proposed by Joachims et al. (2017) to generate click data. The original procedure is as follows: first, a base ranker is trained from the raw data. We select this base ranker by training all models in the RankLib package,3 and selecting the one with the best performance on each data set (MART for Yahoo and LambdaMART for Web30k). We generate an item ranking using the base model, which is then used to generate training data by simulating a user "cascade" model: a user observes each item with decaying probability 1/i η , where i is the base rank of the item and η is a parameter of the generative model. This simulates a noisy sequential scan. An observed item is clicked if its ground-truth relevance score is above a threshold (relevant: {2, 3, 4}, irrelevant: {0, 1}), otherwise no click is generated.

To introduce high-order interactions, we augment the above procedure as follows, creating a generative process dubbed diverse-clicks. When observing a relevant item, the user will only click if it is not too similar to previously clicked items (i.e, diverse enough), thus reducing the total number of clicks.

Similarity is defined as being in the smallest q percentile (i.e., q = 0.5 is the median) of Euclidean distances between pairs of feature vectors within the same ranking instance:

d ij = x i -x j .

We use η = 0 (no decay, since clicks are sparse anyway due to the diversity term) and q = 0.5. This modification to the generative model is essential for our purpose as the original data does not contain explicit inter-item dependencies. We also discuss variations of this model below.

Using the generated training data, we train both our seq2slate model and baseline rankers from the RankLib package: AdaRank (Xu and Li, 2007) , Coordinate Ascent (Metzler and Croft, 2007) , LambdaMART (Wu et al., 2010) , ListNet (Cao et al., 2007) , MART (Friedman, 2001) , Random Forests (Breiman, 2001) , RankBoost (Freund et al., 2003) , RankNet (Burges et al., 2005) . Some of these baselines use deep neural networks (e.g., RankNet, ListNet), so they are strong state-ofthe-art models with comparable complexity to seq2slate. The results in Table 1 show that seq2slate significantly outperforms all the baselines, suggesting that it can better capture and exploit the dependencies between items in the data.

To better understand the behavior of the model, we visualize the probabilities of the attention from Eq. ( 2) for one of the test instances in Fig. 2 . Interestingly, the model produces slates that are close to the input ranking, but with some items demoted to lower positions, presumably due to the interactions with previous items. We next consider several variations of the generative model and of the seq2slate model itself. Results are reported in Table 2 . The rank-gain metric per example is computed by summing the positions change of all positive labels in the re-ranking, and this is averaged over all examples (queries).

Comparison of training variants:

In Table 2 , we compare the different training variants outlined in Section 3, namely cross entropy with the greedy or sampling policy, a smooth hinge loss with γ = 1.0, and REINFORCE. We find that supervised learning with cross entropy generally performs best, with the smooth hinge loss doing slightly worse. Our weakly supervised training methods have positive rank gain on all datasets, meaning they improve over the base ranker. Results from Table 3 : Performance compared to a competitive base production ranker on real data.

One-step decoding We compare seq2slate to the model which uses a single decoding step, referred to as one-step decoder (see Section 2). In Table 2 we see that this model has comparable performance to the sequential decoder. This suggests that when inference time is crucial, as in many real-world systems, one might prefer the faster single-shot option. One possible explanation for the comparable performance of the one-step decoder is that the interactions in our generated data are rather simple and can be effectively learned by the encoder. By contrast, in Section 4.2 we show that on more complex real-world data, sequential decoding can perform significantly better.

Sensitivity to input order Previous work suggests that the performance of seq2seq models are often sensitive to the order in which the input is processed (Vinyals et al., 2016; Nam et al., 2017) . To test this we consider the use of seq2slate without relying on the base ranker to order the input, but instead items are fed to the model in random order. The results in Table 2 (see shuffled data) show that the performance is indeed significantly worse in this case, which is consistent with previous studies. It suggests that reranking is an easier task than ranking from scratch.

Adaptivity to the type of interaction To demonstrate the flexibility of seq2slate, we generate data using a variant of the diverse-clicks model above. In the similar-clicks model, the user also clicks on observed irrelevant items if they are similar to previously clicked items (increasing the number of total clicks). As above, we use the pairwise distances in feature space d ij to determine similarity. For this model we use q = 0.5, and η = 0.3 for Web30k, η = 0.1 for Yahoo, to keep the proportion of positive labels similar. The results in the appendix (see Table 4 ) show that seq2slate has comparable performance to the baseline rankers, with slightly better performance on the harder Web30k data. This demonstrates that our model can adapt to various types of interactions in the data.

4.2. REAL-WORLD DATA:

We also apply seq2slate to a ranking problem from a large-scale commercial recommendation system. We train the model using massive click-through logs (comprising roughly O(10 7 ) instances) with cross-entropy loss, the greedy policy, L2-regularization and dropout. The data has item sets of varying size, with an average n of 10.24 items per example. We learn embeddings of the raw inputs as part of training. Table 3 shows the performance of seq2slate and the one-step decoder compared to the production base ranker on test data (of roughly the same size as the training data). Significant gains are observed in all performance metrics, with sequential decoding outperforming the one-step decoder. This suggests that sequential decoding may more faithfully capture complex dependencies between the items. Finally, we let the learned seq2slate model run in a live experiment (A/B testing). We compute the click-through rate (CTR) in each position (#clicks/#examples) for seq2slate. The production base ranker serves traffic outside the experiment, and we compute CTR per position for this traffic as well. Fig. 3 shows the difference in CTR per position, indicating that seq2slate has significantly higher CTR in the top positions. This suggests that seq2slate indeed places items that are likely to be chosen higher in the ranking. 

5. RELATED WORK:

In this section we discuss additional related work. Our work builds on the recent impressive success of seq2seq models in complex prediction tasks, including machine translation (Sutskever et al., 2014; Bahdanau et al., 2015) , parsing (Vinyals et al., 2015a) , combinatorial optimization (Vinyals et al., 2015b; Bello et al., 2017) , multi-label classification (Wang et al., 2016; Nam et al., 2017) , and others.

Our work differs in that we explicitly target the ranking task, which requires a novel approach to training seq2seq models from weak feedback (click-through data).

Most of the work on ranking mentioned above uses shallow representations. However, in recent years deep models have been used for information retrieval, focusing on embedding queries, documents and query-document pairs (Huang et al., 2013; Guo et al., 2016; Palangi et al., 2016; Wang and Klabjan, 2017; Pang et al., 2017) (see also recent survey by Mitra and Craswell (2017) ). Rather than embedding individual items, in seq2slate a representation of the entire slate of items is learned and encoded in the RNN state. Moreover, learning the embeddings (x) can be easily incorporated into the training of the sequence model to optimize both simultaneously end-to-end. Closest to ours is the recent work of Ai et al. (2018) , where an RNN is used to encode a set of items for re-ranking. Their approach uses a single decoding step with attention, similar to our one-step decoder. In contrast, we use sequential decoding, which we find crucial in certain applications (see Section 4.2). Another important difference is that their training formulation assumes availability of full rankings or relevance scores, while we focus on learning from cheap click-through data. Finally, Santa Cruz et al. (2017) recently proposed an elegant framework for learning permutations based on the so called Sinkhorn operator. Their approach uses a continuous relaxation of permutation matrices (i.e., the set of doubly-stochastic matrices). Later, Mena et al. (2018) combined this with a Gumbel softmax distribution to enable efficient learning. However, this approach is focused on reconstruction of scrambled objects, and it is not obvious how to extend it to our ranking setting, where no ground-truth permutation is available.

6. CONCLUSION:

We presented a novel seq2slate approach to ranking sets of items. We found the formalism of pointer-networks particularly suitable for this setting. We addressed the challenge of training the model from weak user feedback to improve the ranking quality. Our experiments show that the proposed approach is highly scalable and can deliver significant improvements in ranking results. Our work can be extended in several directions. In terms of architecture, we aim to explore the Transformer network (Vaswani et al., 2017) in place of the RNN. Several variants can potentially improve the performance of our model, including beam-search inference (Wiseman and Rush, 2016) , and training with Actor-Critic (Bahdanau et al., 2017) or SeaRNN (Leblond et al., 2018 ) and it will be interesting to study their performance in the ranking setting. Finally, an interesting future work direction will be to study off-policy correction (Joachims et al., 2018) Since the terms are continuous (and smooth) in S for all j and π <j , so is the entire function.

B ADDITIONAL EXPERIMENTAL RESULTS:

Ranker Yahoo Web30k MAP NDCG@5 NDCG@10 MAP NDCG@5 NDCG@10 seq2slate 0. 

:

https://webscope.sandbox.yahoo.com/catalog.php?datatype=c

https://www.microsoft.com/en-us/research/project/mslr/

https://sourceforge.net/p/lemur/wiki/RankLib/

Figures and Tables:

Figure 1: The seq2slate pointer network architecture for ranking.

Figure 2: Visualization of attention probabilities on benchmark data. Intensities correspond to p j i

Performance of seq2slate and other baselines on data generated with diverse-clicks.

Table content: <table><tr><td>Ranker</td><td colspan="6">Yahoo MAP NDCG@5 NDCG10 MAP NDCG@5 NDCG@10 Web30k</td></tr><tr><td>seq2slate</td><td>0.67</td><td>0.69</td><td>0.75</td><td>0.51</td><td>0.53</td><td>0.59</td></tr><tr><td>AdaRank</td><td>0.58</td><td>0.61</td><td>0.69</td><td>0.37</td><td>0.38</td><td>0.46</td></tr><tr><td>Coordinate Ascent</td><td>0.49</td><td>0.51</td><td>0.59</td><td>0.31</td><td>0.33</td><td>0.39</td></tr><tr><td>LambdaMART</td><td>0.58</td><td>0.61</td><td>0.69</td><td>0.42</td><td>0.46</td><td>0.52</td></tr><tr><td>ListNet</td><td>0.49</td><td>0.51</td><td>0.59</td><td>0.43</td><td>0.47</td><td>0.53</td></tr><tr><td>MART</td><td>0.58</td><td>0.60</td><td>0.68</td><td>0.39</td><td>0.42</td><td>0.48</td></tr><tr><td>Random Forests</td><td>0.54</td><td>0.57</td><td>0.65</td><td>0.36</td><td>0.39</td><td>0.45</td></tr><tr><td>RankBoost</td><td>0.50</td><td>0.52</td><td>0.60</td><td>0.24</td><td>0.25</td><td>0.30</td></tr><tr><td>RankNet</td><td>0.54</td><td>0.57</td><td>0.64</td><td>0.43</td><td>0.47</td><td>0.53</td></tr></table>

see also Table5in the appendix) suggest that training with REINFORCE yields comparable results on Yahoo but significantly worse results on the more challenging Web30k dataset. We find no significant difference in performance between relying on the greedy and sampling policies during training.

Table content: <table><tr><td/><td/><td/><td>Yahoo</td><td/><td/><td/><td>Web30k</td><td/></tr><tr><td>Ranker</td><td colspan="8">MAP NDCG@5 NDCG@10 rank-gain MAP NDCG@5 NDCG@10 rank-gain</td></tr><tr><td>seq2slate</td><td>0.67</td><td>0.69</td><td>0.75</td><td>7.4</td><td>0.51</td><td>0.53</td><td>0.59</td><td>18.3</td></tr><tr><td>Greedy policy</td><td>0.66</td><td>0.69</td><td>0.75</td><td>7.2</td><td>0.50</td><td>0.52</td><td>0.59</td><td>18.3</td></tr><tr><td>smooth-hinge</td><td>0.66</td><td>0.69</td><td>0.75</td><td>7.1</td><td>0.49</td><td>0.51</td><td>0.58</td><td>17.9</td></tr><tr><td>RL</td><td>0.66</td><td>0.68</td><td>0.75</td><td>5.7</td><td>0.44</td><td>0.47</td><td>0.53</td><td>-0.5</td></tr><tr><td>one-step decoder</td><td>0.66</td><td>0.69</td><td>0.75</td><td>6.4</td><td>0.49</td><td>0.51</td><td>0.58</td><td>16.5</td></tr><tr><td>shuffled data</td><td>0.61</td><td>0.64</td><td>0.71</td><td>-</td><td>0.36</td><td>0.36</td><td>0.44</td><td>-</td></tr><tr><td>base ranker (no-op)</td><td>0.58</td><td>0.61</td><td>0.69</td><td>0</td><td>0.45</td><td>0.48</td><td>0.54</td><td>0</td></tr></table>

Comparison of model and data variants for seq2slate on data generated with diverse-clicks.

Table content: <table><tr><td>Ranker</td><td>MAP</td><td colspan="3">NDCG@5 NDCG@10 rank-gain</td></tr><tr><td colspan="2">one-step decoder +26.79%</td><td>+10.69%</td><td>+40.67%</td><td>0.83</td></tr><tr><td>seq2slate</td><td>+31.32%</td><td>+14.47%</td><td>+45.77%</td><td>1.087</td></tr></table>

Performance of seq2slate and other baselines on data generated with similar-clicks.

Table content: <table><tr><td/><td/><td>82</td><td>0.82</td><td>0.84</td><td>0.44</td><td>0.54</td><td>0.50</td><td/></tr><tr><td>AdaRank</td><td/><td>0.83</td><td>0.81</td><td>0.84</td><td>0.41</td><td>0.52</td><td>0.48</td><td/></tr><tr><td colspan="2">Coordinate Ascent</td><td>0.83</td><td>0.82</td><td>0.85</td><td>0.39</td><td>0.47</td><td>0.44</td><td/></tr><tr><td colspan="2">LambdaMART</td><td>0.84</td><td>0.83</td><td>0.85</td><td>0.41</td><td>0.52</td><td>0.48</td><td/></tr><tr><td>ListNet</td><td/><td>0.83</td><td>0.83</td><td>0.85</td><td>0.41</td><td>0.53</td><td>0.49</td><td/></tr><tr><td>MART</td><td/><td>0.83</td><td>0.82</td><td>0.85</td><td>0.41</td><td>0.52</td><td>0.48</td><td/></tr><tr><td colspan="2">Random Forests</td><td>0.83</td><td>0.82</td><td>0.84</td><td>0.40</td><td>0.48</td><td>0.45</td><td/></tr><tr><td colspan="2">RankBoost</td><td>0.83</td><td>0.83</td><td>0.85</td><td>0.38</td><td>0.43</td><td>0.41</td><td/></tr><tr><td>RankNet</td><td/><td>0.83</td><td>0.82</td><td>0.84</td><td>0.35</td><td>0.36</td><td>0.35</td><td/></tr><tr><td/><td/><td/><td>Yahoo</td><td/><td/><td/><td>Web30k</td><td/></tr><tr><td>Ranker</td><td colspan="8">MAP NDCG@5 NDCG@10 rank-gain MAP NDCG@5 NDCG10 rank-gain</td></tr><tr><td>seq2slate</td><td>0.82</td><td>0.82</td><td>0.84</td><td>8.5</td><td>0.44</td><td>0.54</td><td>0.50</td><td>16.0</td></tr><tr><td>Greedy policy</td><td>0.82</td><td>0.82</td><td>0.84</td><td>8.5</td><td>0.44</td><td>0.54</td><td>0.50</td><td>15.9</td></tr><tr><td>smooth-hinge</td><td>0.80</td><td>0.80</td><td>0.82</td><td>7.7</td><td>0.44</td><td>0.54</td><td>0.50</td><td>15.9</td></tr><tr><td>RL</td><td>0.82</td><td>0.82</td><td>0.84</td><td>8.5</td><td>0.42</td><td>0.53</td><td>0.49</td><td>-14.8</td></tr><tr><td>one-step decoder</td><td>0.81</td><td>0.81</td><td>0.82</td><td>7.7</td><td>0.44</td><td>0.53</td><td>0.49</td><td>15.5</td></tr><tr><td>shuffled data</td><td>0.80</td><td>0.80</td><td>0.81</td><td>-</td><td>0.40</td><td>0.44</td><td>0.42</td><td>-</td></tr><tr><td>base ranker (no-op)</td><td>0.78</td><td>0.76</td><td>0.79</td><td>0</td><td>0.43</td><td>0.53</td><td>0.49</td><td>0</td></tr></table>

Comparison of model and data variants for seq2slate on data generated with similar-clicks.

Table content: <table/>

Peer review (iclr2019):
 If the stated revisions are incorporated into the paper, it will be a substantially stronger version. I*m leaning towards accepting the revised version -- all my concerns are addressed by the authors* comments. --- The paper uses a Seq2Seq network to re-rank candidate items in an information retrieval task so as to account for inter-item dependencies in a weakly supervised manner. The gain from using such a re-ranker is demonstrated using synthetic experiments as well as a real-world experiment on live traffic to a recommender system. Paragraph below eqn2: for *any* fixed permutation. Figure1 and notation indicates that, at each step of decoding, the selected input x_j is fed to the decoder. The text suggests the embedding of the input e_j is fed to the decoder (which is consistent with "go" being a d-dimensional vector, rather than the dimensionality of x). Single step decoder with linear cost: Is there a missing footnote? If not, why call it p^1? Simpler notation to just call it p. Eqn7: Role of baseline. In REINFORCE, b(x) is typically action-independent (e.g. approximating the state value function induced by the current policy). L_pi(theta) is action dependent (depends on the permutation sampled from P_theta). So, I*m unclear about the correctness of Eqn7 (does it yield an unbiased policy gradient?) Eqn5: Expected some discussion about the mismatch between training loss (per-step cross entropy) vs. testing loss (e.g. NDCG@k). Does a suitable choice of w_j allow us to recover standard listwise metrics (that capture interactions, e.g. ERR)? Expt implementation: Why was REINFORCE optimizing NDCG@10 not regularized? Expt cascade click model: Expected an even simpler experiment to begin with; [Is the Seq2Slate model expressive enough to capture listwise metrics?] Since the relevances are available, we can check if Seq2Slate trained to the relevance labels yields NDCG performance comparable to LambdaMART, and whether it can optimize metrics like ERR. Table1: On the test set, is NDCG&MAP being computed w.r.t the ground truth relevances? So, is the claim that Seq2Slate is more robust when clicks are noisy in a one-sided way (i.e. relevant items may not receive clicks)? Not clear how much of this benefit comes from a more expressive model to predict relevances (see suggested expt above) vs. Seq2Slate from clicks. NDCG & MAP definitely don*t account for inter-item dependencies, so unclear what is being tested in this experiment. For diverse-clicks, eta=0 while for similar-clicks, eta>0 (in a dataset dependent way). Why? Can expt numbers for the 3 choices of eta be added to the appendix? [Seems like cherry-picking otherwise] Can Ai et al, 2018 be benchmarked on the current expt setup? Is it identical to the single-step decoder proposed in the paper? Comment: Would be more accurate to call seq2slate a re-ranker throughout the text (in the abstract and intro, the claim is seq2slate is a ranker). Expected to see training time and inference time numbers. Since Seq2Slate does extra computation on top of, e.g. LambdaMART, it is useful to know how scalable it can be during training, and when the extra perf is worth the O(n^2) or O(n) [for single-step decoding] during inference. General comments: Clarity: The paper is well written and easy to follow. There are a few notation choices that can be improved/clarified. Originality: This work seems closely related to Ai et al, SIGIR 2018. Going from a single-shot decoding to sequential decoding is an incremental step; the real-world experiment seemed the most novel and compelling contribution (however, it is unclear how one can reproduce it). Significance: The paper addresses a significant real-world problem. Many high-impact applications of ranking rely on being able to model inter-dependencies well. Quality: The paper has interesting contributions, but can be substantially stronger (see some of the specific comments above). For instance, A careful study of the computational vs. performance trade-off, fine-grained comparison of different decoding architectures, better understanding of which architectural choices allow us to model any arbitrary ranking metric more effectively vs. which ones are more robust to click noise vs. which ones capture inter-item dependencies.