RACT: TOWARDS AMORTIZED RANKING-CRITICAL TRAINING FOR COLLABORATIVE FILTERING
Year: 2020

Abstract:
We investigate new methods for training collaborative filtering models based on actor-critic reinforcement learning, to more directly maximize ranking-based objective functions. Specifically, we train a critic network to approximate ranking-based metrics, and then update the actor network to directly optimize against the learned metrics. In contrast to traditional learning-to-rank methods that require re-running the optimization procedure for new lists, our critic-based method amortizes the scoring process with a neural network, and can directly provide the (approximate) ranking scores for new lists. We demonstrate the actor-critic’s ability to significantly improve the performance of a variety of prediction models, and achieve better or comparable performance to a variety of strong baselines on three large-scale datasets.

heading: 1 INTRODUCTION
text: Recommender systems are an important means of improving a user’s web experience. Collaborative filtering is a widely-applied technique in recommender systems (Ricci et al., 2015), in which patterns across similar users and items are leveraged to predict user preferences (Su & Khoshgoftaar, 2009). This naturally fits within the learning paradigm of latent variable models (LVMs) (Bishop, 2006), where latent representations capture the shared patterns. Due to their simplicity and effectiveness, LVMs are still a dominant approach. Traditional LVMs employ linear mappings of limited modeling capacity (Paterek, 2007; Mnih & Salakhutdinov, 2008), and a growing body of literature involves applying deep neural networks (DNNs) to collaborative filtering to create more expressive models (He et al., 2017; Wu et al., 2016; Liang et al., 2018). Among them, variational autoencoders (VAEs) (Kingma & Welling, 2013; Rezende et al., 2014) have been proposed as non-linear extensions of LVMs (Liang et al., 2018). Empirically, VAEs significantly outperform many competing LVMbased methods. One essential contribution to the improved performance is the use of the multinomial likelihood, which is argued by Liang et al. (2018) to be a close proxy to ranking loss.
This property is desirable, because in recommender systems we generally care more about the ranking of predictions than an individual item’s score. Hence, prediction results are often evaluated using top-N ranking-based metrics, such as Normalized Discounted Cumulative Gain (NDCG) (Järvelin & Kekäläinen, 2002). The VAE is trained to maximize the likelihood of observations; as shown below, this does not necessarily result in higher ranking-based scores. A natural question concerns whether one may directly optimize against ranking-based metrics, which are by nature non-differentiable and piecewise-constant. Previous work on learning-to-rank has been explored this question in the information-retrieval community, where relaxations/approximations of ranking loss are considered (Weimer et al., 2008; Liu et al., 2009; Li, 2014; Weston et al., 2013).
In this paper, we borrow the actor-critic idea from reinforcement learning (RL) (Sutton et al., 1998) to propose an efficient and scalable learning-to-rank algorithm. The critic is trained to approximate the ranking metric, while the actor is trained to optimize against this learned metric. Specifically, with the goal of making the actor-critic approach practical for recommender systems, we introduce a novel feature-based critic architecture. Instead of treating raw predictions as the critic input, and hoping the neural network will discover the metric’s structure from massive data, we consider
∗Corresponding author †Equal Contribution
engineering sufficient statistics for efficient critic learning. Experimental results on three large-scale datasets demonstrate the actor-critic’s ability to significantly improve the performance of a variety of latent-variable models, and achieve better or comparable performance to strong baseline methods.

heading: 2 BACKGROUND: VAES FOR COLLABORATIVE FILTERING
text: Vectors are denoted as bold lower-case letters x, matrices as bold uppercase letters X, and scalars as lower-case non-bold letters x. We use ◦ for function composition, for the element-wise multiplication, and | · | for cardinality of a set. δ(·) is the indicator function. We use n ∈ {1, . . . , N} to index users, and m ∈ {1, . . . ,M} to index items. The user-item interaction matrix X ∈ {0, 1}N×M collected from the users’ implicit feedback is defined as:
xnm { 1, if interaction of user n with item m is observed; 0, otherwise. (1)
Note that xnm = 0 does not necessarily mean user n dislikes item m; they may simply be unaware of the item. Further, xnm = 1 is not equivalent to saying user n likes item m, but that there is at least interest.
VAE model VAEs have been investigated for collaborative filtering (Liang et al., 2018), where this principled Bayesian approach is shown to achieve strong performance on large-scale datasets. Given the user’s interaction history x = [x1, ..., xM ]> ∈ {0, 1}M , our goal is to predict the full interaction behavior with all remaining items. To simulate this process during training, a random binary mask b ∈ {0, 1}M is introduced, with the entry 1 as un-masked, and 0 as masked. Thus, xh = x b is the user’s partial interaction history. The goal becomes recovering the masked interactions: xp = x (1− xh), which is equivalent to recovering the full x as xh is known. In LVMs, each user’s binary interaction behavior is assumed to be controlled by a k-dimensional user-dependent latent representation z ∈ RK . When applying VAEs to collaborative filtering (Liang et al., 2018), the user’s latent feature z is represented as a distribution q(z|x), obtained from some partial history xh of x. With the assumption that q(z|x) follows a Gaussian form, the inference of z for the corresponding x is performed as:
qφ(z|x) = N (µ, diag(σ2)), with µ,σ2 = fφ(xh), xh = x b, b ∼ Ber(α), (2) where α is the hyper-parameter of a Bernoulli distribution, fφ is a φ-parameterized neural network, which outputs the mean µ and variance σ2 of the Gaussian distribution.
After obtaining a user’s latent representation z, we use the generative process to make predictions. In Liang et al. (2018) a multinomial distribution is used to model the likelihood of items. Specifically, to construct pθ(x|z), z is transformed to produce a probability distribution π over M items, from which the interaction vector x is assumed to have been drawn:
x ∼ Mult(π), with π = Softmax(gθ(z)) (3) where gθ is a θ-parameterized neural network. The output π is normalized via a softmax function to produce a probability vector π ∈ ∆M−1 (an (M − 1)-simplex) over the entire item set.
Training Objective Learning VAE parameters {φ,θ} yields the following generalized objective: Lβ(x;θ,φ)=LE+βLR, with LE=−Eqφ(z|x) [ log pθ(x|z) ] and LR=KL(qφ(z|x)||p(z)) (4)
where LE is the negative log likelihood (NLL) term, LR is the KL regularization term with standard normal prior p(z), and β is a weighting hyper-parameter. When β = 1, we can lower-bound the log marginal likelihood of the data using equation 4 as −Lβ=1(x;θ,φ) ≤ log p(x). This is commonly known as the evidence lower bound (ELBO) in variational inference (Blei et al., 2017). Thus equation 4 is the negative β-regularized ELBO. To improve the optimization efficiency, the reparametrization trick (Kingma & Welling, 2013; Rezende et al., 2014) is used to draw samples z ∼ qφ(z|x) to obtain an unbiased estimate of the ELBO, which is further optimized via stochastic optimization. We call this procedure maximum likelihood estimate (MLE)-based training, as it effectively maximizes the (regularized) ELBO. The testing stage of VAEs for collaborative filtering is detailed in Section A of the Supplement.
Advantages of VAEs The VAE framework successfully scales to relatively large datasets by making use of amortized inference (Gershman & Goodman, 2014): the prediction for all users share the same procedure, which effectively requires evaluating two functions – the encoder fφ(·) and the decoder gθ(·). Crucially, as all users share the same encoder/decoder, the number of parameters required for an autoencoder is independent of the number of users. This is in contrast to some traditional latent factor collaborative filtering models (Paterek, 2007; Hu et al., 2008; Mnih & Salakhutdinov, 2008), where a unique latent vector is learned for each user. The reuse of encoder/decoder for all users is well-aligned with collaborative filtering, where user preferences are analyzed by exploiting the similar patterns inferred from past experiences (Liang et al., 2018). VAEs has the two advantages simultaneously: expressive representation power as a non-linear model, and the number of parameters being independent of the number of users. The same NLL, but different DCG
Pitfalls of VAEs Among various likelihood forms, it was argued in Liang et al. (2018) that multinomial likelihoods are a closer proxy to the ranking loss than the traditional Gaussian or logistic likelihoods. Though simple and effective, the MLE procedure may still diverge with the ultimate goal in recommendation of correctly suggesting the top-ranked items. To illustrate the divergence between MLE-based training and ranking-based evaluation, consider the example in Figure 1. For the target x = {1, 1, 0, 0}, two different predictions A
and B are provided. In MLE, the training loss is the multinomial NLL: −x logπ, where π is the predicted probability. From the NLL point of view, B is a better prediction than A, because B shows a lower loss than A. However, B ranks an incorrect item highest, and therefore would return a worse recommendation than A. Fortunately, NDCG is calculated directly from the ranking, and so captures this dependence. This inspired us to directly use ranking-based evaluation metrics to guide training. For details on calculating NDCG, refer to Section E.2 of the Supplement.

heading: 3 RANKING-CRITICAL TRAINING
text: We introduce a novel algorithm for recommender system training, which we call Ranking-Critical Training (RaCT). RaCT learns a differentiable approximation to the ranking metric, which the prediction network then leverages as a target for optimization through gradient ascent. This is in contrast to existing methods in collaborative filtering, which define an objective relaxation ahead of time. This methodology of learning approximations to functions which cannot be optimized directly stems from the actor-critic paradigm of RL, which we adapt for collaborative filtering.
Any ranking-based evaluation metric can be considered as a “black box” function ω : {π;x, b} 7→ y ∈ [0, 1], which takes in the prediction π to compare with the ground-truth x (conditioned on the mask b), and outputs a scalar y to rate the prediction quality. As in equation 2, b partitions a user’s interactions into those that are “observed” and “unobserved” during inference. As we are only interested in recovering the unobserved items in recommendation, we compute the ranking score of predicted items πp = π (1− xh) based on the ground-truth items xp. One salient component of a ranking-based Oracle metric ω∗ is to sort πp. The sorting operation is nondifferentiable, rendering it impossible to directly use ω∗ as the critic. While REINFORCE (Williams, 1992) may appear to be suited to tackle the non-differentiable problem, it suffers from large estimate variance (Silver et al., 2014), especially in the collaborative filtering problem, which has a very large prediction space. This motivates consideration of a differentiable neural network to approximate the mapping executed by the Oracle. In the actor-critic framework, the prediction network is called the actor, and the network which approximates the oracle is called the critic. The actor begins by making a prediction (action) given the user’s interaction history as the state. The critic learns to estimate the value of each action, which we define as the task-specific reward, i.e., the Oracle’s output. The value predicted by the critic is then used to train the actor. Under the assumption that the critic produces the exact values, the actor is trained based on an unbiased estimate of the gradient of the prediction value in terms of relevant ranking quality metrics. In Figure 2, we illustrate the actor-critic paradigm in (b), and the traditional auto-encoder shown in (a) can be used as the actor in our paradigm.
Naive critic Conventionally one may concatenate vectors [πp,xp] as input to a neural network, and train a network to output the measured ranking scores y. However, this naive critic is impractical, and failed in our experiments. Our hypothesis is that since this network architecture has a huge number of parameters to train (as the input data layer is of length 2M , where M > 10k), it would require rich data for training. Unfortunately, this is impractical: {π,x} ∈ RM are very high-dimensional, and the implicit feedback used in collaborative filtering is naturally sparse.
Feature-based critic The naive critic hopes a deep network can discover structure from massive data by itself, leaving much valuable domain knowledge unused. We propose a more efficient critic, that takes into account the structure underlined by the assumed likelihood in MLE (Miyato & Koyama, 2018). We describe our intuition and method below, and provide the justification from the perspective of adversarial learning in Section D of the Supplement.
Consider the computation procedure of the evaluation metric as a function decomposition ω = ω0◦ωψ , including two steps:
• ω0 : π 7→ h, feature engineering of prediction π into the sufficient statistics h ; • ωψ : h 7→ ŷ, neural approximation of the mapping from the statistics h to the estimated
ranking score ŷ, using a ψ-parameterized neural network.
The success of this two-step critic largely depends on the effectiveness of the feature h. We hope feature h is (i) compact so that fewer parameters in the critic ωψ can simplify training; (ii) easy-tocompute so that training and testing is efficient; and (iii) informative so that the necessary information is preserved. We suggest to use a 3-dimensional vector as the feature, and leave more complicated feature engineering as future work. In summary, our feature is
h = [LE , |H0|, |H1|], (5)
where (i) LE is the negative log-likelihood in equation 4, defined in the MLE training loss. (ii) |H0| is the number of unobserved items that a user will interact, withH0 = {m|xm = 1 and bm = 0}. (iii) |H1| is the number of observed items that a user has interacted, withH1 = {m|xm = 1 and bm = 1}. The NLL characterizes the prediction quality of the actor’s output π against the ground-truth x in an item-to-item comparison manner, e.g., the inner product between two vectors −x logπ as in the multinomial NLL (Liang et al., 2018). Ranking is made easier when there are many acceptable items to rank highly (e.g. when |H0| is large), and made difficult when predicting from very few interactions (e.g. when |H1| is small), motivating these two features. Including these three features allows the critic to guide training by weighting the NLL’s relation to ranking given this context about the user. Interestingly, this idea to consider the importance of user behavior statistics coincides with the scaling trick in SVD (Nikolakopoulos et al., 2019b).
Note that |H0| and |H1| are user-specific, indicating the user’s frequency to interact with the system, which can be viewed as side-information about the user. They are only used as features in training the critic to better approximate the ranking scores, and not in training the actor. Hence, we do not use additional information in the testing stage.
Actor Pre-training In order to be a helpful feature for the critic, the NLL must hold some relationship to the ranking-based objective function. But for the high-dimensional datasets common to collaborative filtering, the ranking score is near-uniformly zero for a randomly-initialized actor. In
this situation, a trained critic will not propagate derivatives to the actor, and therefore the actor will not improve. We mitigate this problem by using a pre-trained actor, such as VAEs that have been trained via MLE.
Critic Pre-training Training a generic critic to approximate the ranking scores for all possible predictions is difficult and cumbersome. Furthermore, it is unnecessary. In practice, a critic only needs to estimate the ranking scores on the restricted domain of the current actor’s outputs. Therefore, we train the critic offline on top of the pre-trained MLE-based actor. To train the critic, we minimize the Mean Square Error (MSE) between the critic output and true ranking score y from the Oracle:
LC(h, y;ψ) = ‖ωψ(h)− y‖2, (6)
where the target y is generated using its non-differential definition, which plays the role of ground truth simulator in training.
Actor-critic Training Once the critic is well trained, we fix its parameters ψ and update the actor parameters {φ,θ} to maximize the estimated ranking score
LA(h;φ,θ) = ωψ(h), (7)
where h is defined in equation 5, including NLL feature extracted from the prediction made in equation 4, together with count features. During back-propagation, the gradient of LA wrt the prediction π is ∂LA∂π = ∂LA ∂h ∂h ∂π . It further updates the actor parameters, with the encoder gradient ∂LA ∂φ = ∂LA ∂π ∂π ∂φ and the decoder gradient ∂LA∂θ = ∂LA ∂π ∂π ∂θ . Updating the actor changes its predictions, so we must update the critic to produce the correct ranking scores for its new input domain.
The full RaCT training procedure is summarized in Algorithm 1 in the Supplement. Stochastic optimization is used, where a batch of users U = {xi|i ∈ B} is drawn at each iteration, with B as a random subset of user index in {1, · · · , N}. The pre-training of the actor in Stage 1 and the critic in Stage 2 are important; they provide good initialization to the actor-critic training in Stage 3 for fast convergence. Further, we provide an alternative interpretation to view our actor-critic approach in equation 6 and equation 7 from the perspective of adversarial learning (Goodfellow et al., 2014) in the Supplement. This can partially justify our choice of feature engineering.

heading: 4 RELATED WORK
text: Deep Learning for Collaborative Filtering There are many recent efforts focused on developing deep learning models for collaborative filtering (Sedhain et al., 2015; Xue et al., 2017; He et al., 2018a;b; Zhang et al., 2017; Chen et al., 2017). Early work on DNNs focused on explicit feedback settings (Georgiev & Nakov, 2013; Salakhutdinov et al., 2007; Zheng et al., 2016), such as rating predictions. Recent research gradually recognized the importance of implicit feedback (Wu et al., 2016; He et al., 2017; Liang et al., 2018), where the user’s preference is not explicitly presented (Hu et al., 2008). This setting is more practical but challenging, and is the focus of our work. The proposed actor-critic method belongs to the general two-level architectures for recommendation systems, where a coarse to fine prediction procedure is used. For a systematic method comparison for top-N recommendation tasks, we suggest referring to Dacrema et al. (2019). Our method is closely related to three papers, on VAEs (Liang et al., 2018), collaborative denoising autoencoder (CDAE) (Wu et al., 2016) and neural collaborative filtering (NCF) (He et al., 2017). CDAE and NCF may suffer from scalability issues: the model size grows linearly with both the number of users as well as items. The VAE (Liang et al., 2018) alleviates this problem via amortized inference. Our work builds on top of the VAE, and improves it by optimizing to the ranking-based metric.
Learned Metrics in Vision & Languages Recent research in computer vision and natural language processing has generated excellent results, using learned instead of hand-crafted metrics. Among the rich literature of generating realistic images via generative adversarial networks (GANs) (Goodfellow et al., 2014; Radford et al., 2015; Karras et al., 2018), our work is most similar to Larsen et al. (2016), where the VAE objective (Kingma & Welling, 2013) is augmented with the learned representations in the GAN discriminator (Goodfellow et al., 2014) to better measure image similarities. For language generation, the discrepancy between word-level MLE training and sequence-level semantic evaluation has been alleviated with GANs or RL techniques (Bahdanau et al., 2016; Ren et al., 2017; Lin et al.,
2017). The RL approach directly optimizes the metric used at test time, and has shown improvement on various applications, including dialogue (Li et al., 2016), image captioning (Rennie et al., 2017) and translations (Ranzato et al., 2015). Despite the significant successes in other domains, there has been little if any research reported for directly learning the metrics with deep neural networks for collaborative filtering. Our work fills the gap, and we hope it inspires more research in this direction.
Learning to Rank (L2R) The idea of L2R has existed for two decades in the information-retrieval community. The goal is to maximize a given ranking-based evaluation metric (Liu et al., 2009; Li, 2014), generally through optimizing objective relaxations (Weimer et al., 2008). Many L2R methods used in recommendation, such as the popular pairwise L2R methods BPR (Rendle et al., 2009) and WARP (Weston et al., 2011), are trained by optimizing a pairwise classification function that penalizes mis-ranked pairs of items. Through negative sampling (Hu et al., 2008), these methods can scale to extremely high-dimensional output spaces. However, it is computationally expensive to compute low-variance updates to a model when the number of items is large.
An alternative to the pairwise approach is listwise loss functions, which minimize a loss calculated from a user’s entire interaction history. By considering the entire interaction history these methods can more closely model ranking, and generally perform better than their pairwise counterparts (Xia et al., 2008). Furthermore, compared to methods which calculate relative ranking for each pair (Weston et al., 2011), the per-user amortization of rank-calculation can be computed more efficiently. NLL is an example of a listwise loss function, as it is calculated over a user’s entire interaction history. Interestingly, NLL is also used as the loss function for ListNet (Cao et al., 2007), a classic listwise L2R method designed to probabilistically maximize Top-1 Recall. The VAE framework under NLL can be seen as a principled extension of this method to Top-N collaborative filtering. Our ranking-critical training further extends this methodology by explicitly calculating the relationship between a differentiable listwise loss function and the desired ranking-based evaluation function.

heading: 5 EXPERIMENTS
text: Experimental Settings We implemented our algorithm in TensorFlow. The source code to reproduce the experimental results and plots is included as Supplementary Material. We conduct experiments on three publicly available large-scale datasets, which represent different item recommendation scenarios, including user-movie ratings and user-song play counts. This is the same set of user-item consumption datasets used in Liang et al. (2018), and we keep the same pre-processing steps for fair comparison. The statistics of the datasets, evaluation protocols and hyper-parameters are summarized in the Supplement. VAE (Liang et al., 2018) is used as the baseline, which plays the role of our actor pre-training. The NCDG@100 ranking metric is used as the critic’s target in training.
Baseline Methods We use ranking-critical training to improve the three MLE-based methods described in Section 2.1: VAE, DAE, and MF. We also adapt traditional L2R methods as the actors in our framework, where the L2R loss is used to replace LE in equation 5 to construct the feature. We consider WARP and LambdaRank, two pairwise loss functions designed for optimizing NDCG, for these experiments. We also compare our approaches with four representative baseline methods in collaborative filtering. CDAE (Wu et al., 2016) is a strongly-performing neural-network based method, weighted MF (Hu et al., 2008) is a linear latent-factor model, and SLIM (Ning & Karypis, 2011) and EASE (Steck, 2019) are item-to-item similarity models. We additionally compare with Bayesian Pairwise Ranking (Rendle et al., 2009), but as this method did not yield competitive performance on these datasets, we omit the results.

heading: 5.1 OVERALL PERFORMANCE OF RACT
text: Improvement over VAE In Figure 3, we show the learning curves of RaCT and VAE on the validation set. The VAE converges to a plateau by the time that the RaCT finishes its actor pretraining stage, e.g., 150 epochs on ML-20 dataset, after which the VAE’s performance is not improving. By contrast, when the RaCT is plugged in, the performance shows a significant immediate boost. For the amount of improvement gain, RaCT takes only half the number of epochs that VAE takes in the end of actor pre-training. For example, RaCT takes 50 epochs (from 150 to 200) to achieve an improvement of 0.44-0.43 = 0.01, while VAE takes 100 epochs (from 50 to 150) to achieve an improvement of 0.43-0.424 = 0.006.
Training/Evaluation Correlation We visualize scatter plots between learning objectives and evaluation metric for all users on ML-20M dataset in Figure 4. More details and an enlarged visualization is shown in Figure 6 of the Supplement. The Pearson’s correlation r is computed. NLL exhibits low correlation with the target NDCG (r is close to zero), while the learned metric in RaCT shows much higher positive correlation. It strongly indicates RaCT optimizes a more direct objective than an MLE approach. Further, NLL should in theory have a negative correlation with the target NDCG, as we
wish that minimizing NLL can maximize NDCG. However, in practice it yields positive correlation. We hypothesize that this is because the number of interactions for each user may dominate the NLL values. That partially motivates us to consider the number of user interactions as features.
Comparison with traditional L2R methods As examples of traditional L2R methods, we compare to our method using WARP (Weston et al., 2011) and LambdaRank (Burges et al., 2007) as the rankingcritical objectives. We use implementations of both methods designed specifically to maximize NDCG. We observe that WARP and LambdaRank are roughly 2 and 10 times more computationally expensive than RaCT per epoch, respectively. Table 1 shows the results of RaCT, WARP and LambdaRank, using the same amount of wall-clock training time. We observe the trends that WARP degrades performance, and LambdaRank provides performance roughly equal to VAE. WARP’s poor performance is perhaps due to poor approximation of the ranking when the number of items is large.
Comparison with existing methods In Table 1, we report our RaCT performance, and compare with competing methods in terms of three evaluation metrics: NDCG@100, Recall@20, and Recall@50. We use the published code1 of Liang et al. (2018), and reproduce the VAE as our actor pre-training. We further use their reported values for the classic collaborative filtering methods CDAE, WMF, and SLIM. Our reproduced VAE results are very close to Liang et al. (2018) on the ML-20M and
1https://github.com/dawenl/vae_cf
Actor Before After Gain
VAE 0.4258 0.4339 8.09 VAE (Gaussian) 0.4202 0.4224 2.21 VAE (β = 0) 0.4203 0.4255 5.17 VAE (Linear) 0.4156 0.4162 0.53 DAE (Liang et al., 2018) 0.4205 0.4214 0.87 MF (Liang et al., 2018) 0.4159 0.4172 1.37 WARP 0.3123 0.3439 31.63
Table 2: Performance gain (×10−3) for various actors.
Netflix datasets, but slightly lower on the MSD dataset. The RaCT is built on top of our VAE runs, and consistently improves its baseline actor for all the evaluation metrics and datasets, as seen by comparing the rows RaCT and VAE‡. The proposed RaCT also significantly outperforms competing LVMs, including VAE, CDAE, and WMF.
When comparing to EASE (Steck, 2019), our method performs substantially better for ML-20M, comparably for Netflix, and is substantially outperformed for MSD. We observe a similar trend when comparing SLIM (an item-to-item similarity method) and CDAE (a latent variable method). As SLIM and EASE rely on recreating the Gram-matrix G = XTX, their performance should improve with the the number of users (Steck, 2019). However this performance may come at a computational cost, as inference requires multiplication with an unfactored M ×M matrix. EASE requires computing a dense item-to-item similarity matrix, making its inference on MSD roughly 30 times more expensive than for VAE or RaCT. A practitioner’s choice between these two methods should be informed by the specifics of the dataset as well as demands of the system.
In the Supplement, we study the generalization of RaCT trained with different ranking-metrics in Section F.1, and break down the performance improvement with different cut-off values of NDCG in Section F.3, and with different number of interactions of X in Section F.4.

heading: 5.2 WHAT ACTOR CAN BE IMPROVED BY RACT?
text: In RL, the choice of policy plays a crucial role in the agent’s performance. Similarly, we would like to study how different actor designs impact RaCT performance. Table 2 shows the performance of various policies before and after applying RaCT. The results on NDCG@100 are reported. The VAE, DAE and MF models follow the setup in Liang et al. (2018).
We modify one component of the VAE at a time, and check the change of performance improvement that RaCT can provide. (1) VAE (Gaussian): we change likelihood form from multinomial to Gaussian, and observe a smaller performance improvement. This shows the importance of having a closer proxy of ranking-based loss. (2) VAE (β = 0): we remove the KL regularization by setting β = 0, and replace the posterior sampling with a delta distribution. We see a marginally smaller performance improvement. This compares a stochastic and deterministic policy. The stochastic policy (i.e., posterior sampling) provides higher exploration ability for the actor, allowing more diverse samples generated for the critic’s training. This is essential for better critic learning. (3) VAE (Linear): we limit the expressive ability of the actor by using a linear encoder and decoder. This significantly degrades performance, and the RaCT cannot help much in this case. RaCT shows improvements for all MLE-based methods, including DAE and MF from Liang et al. (2018). It also shows significant improvement over WARP. Please see detailed discussion in Section F.5 of the Supplement.

heading: 5.3 ABLATION STUDY ON FEATURE-BASED CRITIC
text: In Figure 5, we investigate the importance of the features we designed in equation 5, using results from the ML-20M dataset. The full feature vector consists of three elements: h = [LE , |H0|, |H1|]. LE is mandatory, because it links the actor to the critic; removing it would break the back-propagation to train the actor. We carefully remove |H0| or |H1| from h at each time, and observe that it leads to performance degradation. In particular, removing |H0| results in a severe over-fitting issue. When both counts are removed, we observe an immediate performance drop, as depicted by the orange curve. Overall, the results indicate that all three features are necessary to our performance improvement.

heading: 6 CONCLUSION & DISCUSSION
text: We have proposed an actor-critic framework for collaborative filtering on implicit data. The critic learns to approximate the ranking scores, which in turn improves the traditional MLE-based nonlinear LVMs with the learned ranking-critical objectives. To make it practical and efficient, we introduce a few techniques: a feature-based critic to reduce the number of learnable parameters, posterior sampling as exploration for better critic estimates, and pre-training of actor and critic for fast convergence. The experimental results on three large-scale datasets demonstrate the actor-critic’s ability to significantly improve the results of a variety of latent-variable models, and achieve better or comparable performance to strong baseline methods.
Though RaCT improves VAEs, it does not start from the best performing actor model. The very recent work by Dacrema et al. (2019) conducts a systematic analysis of algorithmic proposals for top-N recommendation tasks. There are other simple and efficient methods that perform better than VAEs, such as pure SVD-based models (Cremonesi et al., 2010; Nikolakopoulos et al., 2019b), RecWalk (Nikolakopoulos & Karypis, 2019) and Personalized Diffusions (Nikolakopoulos et al., 2019a). One interesting future research direction is to explore learning-to-rank techniques for them.

heading: A TESTING STAGE OF VAES FOR COLLABORATIVE FILTERING
text: We focus on studying the performance of various models under strong generalization (Liang et al., 2015) as in (Liang et al., 2018). All users are split into training/validation/test sets. The models are learned using the entire interaction history of the users in the training set. To evaluate, we use a part of the interaction history from held-out (validation and test) users to infer the user-level representations from the model, and compute quality metrics by quantifying how well the model ranks the rest of the unseen interaction history from the held-out users. Specifically, for a held-out user with the full history x, we take xh = x b offline using the randomly generated mask b. xh is then frozen as the testing input, and is fed into various trained models during the evaluation stage to get the prediction π̂. The recovered interaction x̄ = π̂ (1−xh) for the masked seen part is then evaluated by ranking-based metrics.

heading: B BACKGROUND ON TRADITIONAL LEARNING-TO-RANK METHODS
text: Formally, the Bayesian Personalized Ranking (BPR) (Rendle et al., 2009) loss for the n-th user is LBPR = ∑ i∈K+ ∑ j∈K− σ(πnj − πni), (8)
where σ(·) is the sigmoid function, K+ denotes the set of items that the user has interacted with before, and K− denotes the complement item set. The Weighted Approximate-Rank Pairwise (WARP) model (Weston et al., 2011) has been shown to perform better than BPR for implicit feedback (Kula, 2015):
LWARP = ∑ ni∈K+ ∑ j∈K− w(ri)max(0, 1 + πnj − πni)), (9)
where w(·) is a weighting function for different ranks, and ri is the rank for the i-th item for n-th user. A common choice of weighting function w(·) for optimizing NDCG is w(r) = ∑r i=1 αi, with αi = 1/i. WARP improves BPR by the weights w(·) and the margin between positive and negative items.

heading: C PSEUDO-CODE FOR RACT
text: We summarize the full training procedure of RaCT in Algorithm 1.
D INTERPRETATION WITH GANS
We can view our actor-critic approach in equation 6 and equation 7 from the perspective of Generative Adversarial Networks (GANs). GANs constitute a framework to construct a generator G that can mimic a target distribution, and have achieved significant success in generating realistic images (Goodfellow et al., 2014; Radford et al., 2015; Karras et al., 2018; Brock et al., 2018). The most distinctive feature of GANs is the discriminator D that evaluates the divergence between the current generator distribution and the target distribution (Goodfellow et al., 2014; Li et al., 2017). The GAN learning procedure performs iterative training between the discriminator and generator, with the discriminator acting as an increasingly meticulous critic to refine the generator. In our work, the actor can be interpreted as the generator, while the critic can be viewed as the discriminator.
Note that GANs and actor-critic models learn the metric functions (Finn et al., 2016), and it has been shown in Pfau & Vinyals (2016) that GANs can be viewed as actor-critic in an environment where the actor cannot affect the reward. This is exactly our setup. One key difference is that we know the Oracle metric, and the critic is trained to mimic the Oracle’s behaviour.
Algorithm 1: Our full ranking-critical training with stochastic optimization. Input : Interaction matrix X; Actor parameters (encoder φ and decoder θ), Critic parameters ψ.
1 Initialize: Randomly initialize weights φ, θ and ψ 2 /* Stage 1: Pretrain the actor via MLE */ 3 while not converged do do 4 Sample a batch of users U ; 5 Update {θ,φ} with gradient ∂Lβ∂θ and ∂Lβ ∂φ in equation 4; 6 end
7 /* Stage 2: Pretrain the critic via MSE */ 8 while not converged do do 9 Sample a batch of users U ;
10 Construct features h in equation 5 and target y from the Oracle; 11 Update ψ with gradient ∂LC∂ψ in equation 6; 12 end
13 /* Stage 3: Alternative training of actor and critic */ 14 for t = 1, 2, . . . , T do 15 Sample a batch of users U ; 16 /* Actor step */ 17 Update {θ,φ} with gradient ∂LA∂θ and ∂LA ∂φ in equation 7; 18 /* Critic step */ 19 Construct features h in equation 5 and target y from the Oracle; 20 Update ψ with gradient ∂LC∂ψ in equation 6; 21 end
Conditioned on interaction history xh corrupted from x, the actor predicts the distribution parameter π over items, which further constructs the likelihood p(x|π). We use q to designate the data empirical distribution, the target conditional is q(x|π). It can be formulated as the standard adversarial loss for the conditional GAN (Mirza & Osindero, 2014). It has been shown that the optimal critic (Goodfellow et al., 2014; Li et al., 2017) for a conditional GAN can be represented as the log likelihood ratio
R∗(π,x) = log q(x|π) p(x|π)
(10)
In the collaborative filtering setup, we often make the assumptions that p(x|π) are simple distributions, such as multinomial in VAEs (Liang et al., 2018) and Gaussian in MF. This simplification allows the parameterization of critic following the following form (Miyato & Koyama, 2018):
R∗(π,x) = x>Vν(π) + C (11)
wherex is the target, ν(π) is a layer of the critic with inputπ, and V and C are the parameters to learn. Most notably, this formulation introduces the prediction information via an inner product, as opposed to concatenation. The form equation 11 is indeed the form we proposed for NLL feature x logπ, with V = I and ν(·) = log(·). C includes the normalizer for the prediction probability (Miyato & Koyama, 2018), which is related to the count features in equation 5.

heading: E EXPERIMENTAL SETUP

heading: E.1 DATASETS
text: We conduct experiments on three publicly available datasets. Table 3 summarizes the statistics of the data. These three ten-million-size datasets represent different item recommendation scenarios, including user-movie ratings and user-song play counts. This is the same set of medium- to large-scale user-item consumption datasets used in Liang et al. (2018), and we keep the same pre-processing steps for fair comparison.

heading: E.2 EVALUATION PROTOCOL
text: In the testing stage, we get the predicted ranking by sorting the multinomial probability πp. For each user, we compare the predicted ranking of the held-out items with their true ranking. Two ranking-based metrics are considered, Recall@R and the truncated NDCG (NDCG@R), where R is the cut-off hyper-parameter. While Recall@R considers all items ranked within the first R to be equally important, NDCG@R uses a monotonically increasing discount to emphasize the importance of higher ranks versus lower ones.
Formally, we define m(r) as the item at rank r, andH0 as the held-out unobserved items that a user will interact.
DCG@R = R∑ r=1 2δ[m(r)∈H0] − 1 log(r + 1) . (12)
By dividing DCG@R by its best possible value, we obtain NDCG@R in [0, 1].
Recall@R = R∑ r=1 δ[m(r) ∈ H0] min(R, |H0|) . (13)
The denominator normalizes Recall@R in [0, 1], with maximum value 1 corresponding to the case that all relevant items are ranked in the top R positions.

heading: E.3 EXPERIMENT HYPER-PARAMETERS
text: We set hyper-parameters by following Liang et al. (2018) for comparisons. For VAE, the dimension of the latent representation is 200. When KL regularization is removed (β = 0), i.e., for DAE and MF, we instead apply `2 regularization (0.01) on weights to prevent overfitting. Adam optimizer (Kingma & Ba, 2014) is used, with batch size of |B| = 500 users. For ML-20M, the actor is pre-trained for 150 epochs, and alternative training for 50 epochs. On the other two datasets, the actor is pre-trained for 75 epochs, and alternative training for 25 epochs. The critic is pre-trained for 50 epochs for all three datasets. The alternative training has equal update frequency for actor and critic. This schedule ensures that we the have the same total number of actor training epochs as Liang et al. (2018): 200 epochs for ML-20M, 100 epochs for the other two datasets.
2https://grouplens.org/datasets/movielens/20m/ 3https://www.netflixprize.com/
A fully-connected (FC) architecture is used for all networks, as detailed in Table 4. Please refer to Goodfellow et al. (2016) for the activation functions. Batch Normalization (Ioffe & Szegedy, 2015) is used to normalize the input features, because the magnitude of the inputs (NLL) change as training progresses. The encoder outputs the mean and variance of the varational distribution; the variance is implemented via an exponential function.

heading: F ADDITIONAL EXPERIMENTAL RESULTS

heading: F.1 GENERALIZATION ACROSS RANKING METRICS
text: To study the generalization ability of RaCT, we consider training the critic against Recall@100, in addition to NDCG@100. The only difference is that Recall treats each item as equally important, while NDCG treats the higher ranking items as more important. The results are shown in Table 6. Indeed, the RaCT gets slightly better testing Recall values when trained against the Recall metric, and the reverse holds for NDCG. More importantly, RaCT allows generalization across different ranking metrics: all testing metric values are significantly improved when trained against either Recall or NDCG.
Following Liang et al. (2018), we compare with NCF on two small datasets, ML-1M (6,040 users, 3,704 items) and Pinterest (55,187 users, 9,916 items). This is because the prediction stage of NCF is slow, due to a lack of amortized inference as in VAE. We use their publicly available datasets and metrics for fair comparison. The results are evaluated with a small cut-off value R, to only study the highly ranked items: NDCG@10 and Recall@10. The performance are compared in Table 7. Our observation that DAE performs better than VAE on these two datasets is consistent with Liang
et al. (2018). In general, RaCT shows higher improvement when a larger dataset (Pinterest), or a stochastic actor (VAE) is considered. This is because the sizes of the two datasets are relatively small, the critic can be better trained when more samples are observed. On the larger Pinterest dataset, the auto-encoder variants perform better than NCF by a big margin, and our RaCT further boosts the performance.

heading: F.2 CORRELATION BETWEEN TRAINING METRICS
text: Figure 6 explores the relationship between NLL, the learned RaCT metric, and NDCG. We ensure that the best model for each method is used: the model after actor pre-training (Stage 1) is used for NLL plots, and the model after the actor-critic alternative training (Stage 3) is used for RaCT plots. The bottom row of plots displays the output of these models on the testing data. This demonstrates that RaCT’s connection to the ranking metric generalizes to unseen data.

heading: F.3 BREAKDOWN ANALYSIS FOR DIFFERENT CUT-OFF VALUES
text: NDCG@100 only reflects the ranking quality at the cut-off value R = 100. i.e., the top-100 ranking items. To study the ranking quality at different range of the predicted list, we consider a large range of R, and report the corresponding NDCG values. We consider R = 5, 20, 50, 100, 200, and report the results in Figure 7. The NDCG@R values are improved for various R, though the critic is trained against NDCG@100. This is because the NDCG metrics of different R are highly correlated, the RaCT can generalize across them.

heading: F.4 BREAKDOWN ANALYSIS FOR DIFFERENT NUMBER OF INTERACTIONS
text: In Figure 8, we show performance improvement across increasing user interactions. We use ML-20M dataset for this case study. The # interactions is the number of items each user interacts with (groundtruth), indicating the user’s activity level. Figure 8(a) shows the scatter plots between NDCG@100 values and various number of interactions on the testing dataset, for both VAE and our RaCT methods. RaCT generally improves VAE for a large range of user interactions. We further categorize the users in four groups according to their number of interactions: <250, 250−500, 501−750, >750, and plot the mean of NDCG@100 values for two methods in Figure 8(b). RaCT improves VAE except for users with high activity level (>750). This is probably because the number of the most active users is small, as observed in Figure 8(a). It yields a lack of training data for critic learning, which potentially hurts the performance.

heading: F.5 ON THE PERFORMANCE IMPROVEMENT OF ACTORS VIA RACT.
text: We also consider the two other auto-encoder variants used in Liang et al. (2018) as the actor. (1) The DAE in Liang et al. (2018) chooses a smaller architecture M → 600 → M , which achieves better performance than the larger architecture as in our VAE (β = 0) by prevent over-fitting. While we observe the same result, it is interesting to note that the VAE (β = 0) shows a much larger improvement gain than DAE (Liang et al., 2018) when trained with our RaCT technique, and eventually significantly outperforms the latter. This shows that the additional modeling capacity is
necessary to capture the more complex relationship in prediction, when the goal is ranking rather than MLE. (2) The MF in Liang et al. (2018) employs a Gaussian likelihood, which also gets slight improvement with the RaCT. Overall, we can conclude that the RaCT method improves all the MLE-based variants.
We also use ranking-loss-based WARP as the actor. For the large datasets considered in this paper, calculating the full WARP-loss for each user is impractically slow. We derive a simple approximation to WARP which runs in quasilinear time to the number of items. Even so, it takes around 30 minutes per epoch on ML-20M dataset, roughly 30 times slower than the VAE. WARP yields the score 0.312, which is lower than other baseline methods. This is consistent with the studies in Liang et al. (2018); Sedhain et al. (2016). However, when RaCT is applied, WARP gets a significant improvement; in fact, the largest improvement gain of all the actors. This indicates the RaCT is a more direct and effective approach for learning to rank on large datasets.

Review summaries:
The authors propose a novel reinforcement learning (RL) based recommendation algorithm (i.e., Ranking-Critical Training, RaCT) for modeling users' implicit feedback, which is illustrated in Figure 2(b). Specifically, the authors apply the actor-critic RL paradigm to approximately optimize the ranking-oriented loss/objective function in collaborative filtering with implicit feedback, which is a difficult and important problem. In particular, the critic network is used to approximate the ranking-oriented metric, and the actor network is used for optimizing this metric. Moreover, for efficiency, the authors also propose a feature-based critic to replace the original one.

The work presents a two-level architecture for building an efficient ranking solution for standard collaborative filtering task in recommender systems. The core of this solution is the actor-critic approach, where the critic (motivated by ideas from RL) tries to directly approximate a ranking-based metric using as an input prediction from the actor (VAE framework) and the ground truth knowledge from an Oracle. Both actor and critic require a pre-training step, after which the critic is set to propagate adjustments to actor parameters. Experiments demonstrate the advantage of such approach over competing methods.

This paper builds on the line of work of developing latent variable models (LVMs) for collaborative filtering with implicit feedback (e.g. which items a user has previously clicked on).  While variational autoencoders allow convenient construction of nonlinear LVMs, they are trained by maximizing the multinomial likelihood for the items selected.  Thus the training objective is not perfectly matched to the evaluation objective, which is typically something like NDCG @N or RECALL @N, neither of which is differentiable.  This paper proposes an actor-critic RL approach to train the nonlinear LVM directly for the NDCG loss.  The idea is to create a critic model that learns to approximate NDCG, and to train the actor to optimize this approximate objective.  However, they find that they are unable to build an effective critic when taking the predictions and ground truth directly.  However, they find that with a simple set of 3-features, they can build an effective critic that gives improved or competitive performance on several metrics on 3 large-scale datasets.  When their method (RaCT) is not the best, it is beaten by EASE, which is computationally much more expensive.