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.

summaries: 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.

summaries: 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.

abstractText: 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.

authors:
Dzmitry Bahdanau
Philemon Brakel
Kelvin Xu
Anirudh Goyal
Ryan Lowe
Joelle Pineau
Aaron Courville
Yoshua Bengio

title: An actor-critic algorithm for sequence prediction

venue: arXiv preprint arXiv:1607.07086,

authors:
Thierry Bertin-Mahieux
Daniel PW Ellis
Brian Whitman
Paul Lamere

title: The million song dataset

venue: In ISMIR,

title: Pattern recognition and machine learning

venue: Pattern Recognition and Machine Learning,

authors:
David M Blei
Alp Kucukelbir
Jon D McAuliffe

title: Variational inference: A review for statisticians

venue: Journal of the American Statistical Association,

authors:
Andrew Brock
Jeff Donahue
Karen Simonyan

title: Large scale gan training for high fidelity natural image synthesis

venue: arXiv preprint arXiv:1809.11096,

authors:
Christopher J Burges
Robert Ragno
Quoc V Le

title: Learning to rank with nonsmooth cost functions

venue: In NIPS,

authors:
Zhe Cao
Tao Qin
Tie-Yan Liu
Ming-Feng Tsai
Hang Li

title: Learning to rank: From pairwise approach to listwise approach

venue: In International conference on machine learning,

authors:
Jingyuan Chen
Hanwang Zhang
Xiangnan He
Liqiang Nie
Wei Liu
Tat-Seng Chua

title: Attentive collaborative filtering: Multimedia recommendation with item-and component-level attention

venue: In Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval,

authors:
Paolo Cremonesi
Yehuda Koren
Roberto Turrin

title: Performance of recommender algorithms on top-N recommendation tasks

venue: In ACM Conference on Recommender systems,

authors:
Maurizio Ferrari Dacrema
Paolo Cremonesi
Dietmar Jannach

title: Are we really making much progress? a worrying analysis of recent neural recommendation approaches

venue: In ACM Conference on Recommender Systems,

authors:
Chelsea Finn
Paul Christiano
Pieter Abbeel
Sergey Levine

title: A connection between generative adversarial networks, inverse reinforcement learning, and energy-based models

venue: arXiv preprint arXiv:1611.03852,

authors:
Kostadin Georgiev
Preslav Nakov

title: A non-iid framework for collaborative filtering with restricted boltzmann machines

authors:
Samuel Gershman
Noah Goodman

title: Amortized inference in probabilistic reasoning

venue: In Proceedings of the Annual Meeting of the Cognitive Science Society,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Xiangnan He
Lizi Liao
Hanwang Zhang
Liqiang Nie
Xia Hu
Tat-Seng Chua

title: Neural collaborative filtering

venue: In Proceedings of the 26th International Conference on World Wide Web, pp. 173–182. International World Wide Web Conferences Steering Committee,

authors:
Xiangnan He
Xiaoyu Du
Xiang Wang
Feng Tian
Jinhui Tang
Tat-Seng Chua

title: Outer product-based neural collaborative filtering

authors:
Xiangnan He
Zhankui He
Xiaoyu Du
Tat-Seng Chua

title: Adversarial personalized ranking for recommendation

venue: In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval,

authors:
Yifan Hu
Yehuda Koren
Chris Volinsky

title: Collaborative filtering for implicit feedback datasets

venue: In Data Mining,

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

authors:
Kalervo Järvelin
Jaana Kekäläinen

title: Cumulated gain-based evaluation of ir techniques

venue: ACM Transactions on Information Systems (TOIS),

authors:
Tero Karras
Timo Aila
Samuli Laine
Jaakko Lehtinen

title: Progressive growing of gans for improved quality, stability, and variation

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: ICLR,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

title: Metadata embeddings for user and item cold-start recommendations

venue: arXiv preprint arXiv:1507.08439,

authors:
Anders Boesen Lindbo Larsen
Søren Kaae Sønderby
Hugo Larochelle
Ole Winther

title: Autoencoding beyond pixels using a learned similarity metric

venue: In International Conference on Machine Learning,

authors:
Chunyuan Li
Hao Liu
Changyou Chen
Yuchen Pu
Liqun Chen
Ricardo Henao
Lawrence Carin

title: Alice: Towards understanding adversarial learning for joint distribution matching

title: Learning to rank for information retrieval and natural language processing

venue: Synthesis Lectures on Human Language Technologies,

authors:
Jiwei Li
Will Monroe
Alan Ritter
Michel Galley
Jianfeng Gao
Dan Jurafsky

title: Deep reinforcement learning for dialogue generation

venue: arXiv preprint arXiv:1606.01541,

authors:
Dawen Liang
Minshu Zhan
Daniel PW Ellis

title: Content-aware collaborative music recommendation using pre-trained neural networks

authors:
Dawen Liang
Rahul G Krishnan
Matthew D Hoffman
Tony Jebara

title: Variational autoencoders for collaborative filtering

authors:
Kevin Lin
Dianqi Li
Xiaodong He
Zhengyou Zhang
Ming-Ting Sun

title: Adversarial ranking for language generation

authors:
Mehdi Mirza
Simon Osindero

title: Conditional generative adversarial nets

venue: arXiv preprint arXiv:1411.1784,

authors:
Takeru Miyato
Masanori Koyama

title: cgans with projection discriminator

authors:
Andriy Mnih
Ruslan R Salakhutdinov

title: Probabilistic matrix factorization

authors:
Athanasios N Nikolakopoulos
George Karypis

title: RecWalk: Nearly uncoupled random walks for top-N recommendation

venue: In ACM International Conference on Web Search and Data Mining,

authors:
Athanasios N Nikolakopoulos
Dimitris Berberidis
George Karypis
Georgios B Giannakis

title: Personalized diffusions for top-N recommendation

authors:
Athanasios N Nikolakopoulos
Vassilis Kalantzis
Efstratios Gallopoulos
John D Garofalakis

title: EigenRec: generalizing pureSVD for effective and efficient top-N recommendations

venue: Knowledge and Information Systems,

authors:
Xia Ning
George Karypis. Slim

title: Sparse linear methods for top-n recommender systems

venue: In 2011 11th IEEE International Conference on Data Mining,

title: Improving regularized singular value decomposition for collaborative filtering

venue: In Proceedings of KDD cup and workshop,

authors:
David Pfau
Oriol Vinyals

title: Connecting generative adversarial networks and actor-critic methods

venue: arXiv preprint arXiv:1610.01945,

authors:
Alec Radford
Luke Metz
Soumith Chintala

title: Unsupervised representation learning with deep convolutional generative adversarial networks

venue: arXiv preprint arXiv:1511.06434,

authors:
Marc’Aurelio Ranzato
Sumit Chopra
Michael Auli
Wojciech Zaremba

title: Sequence level training with recurrent neural networks

authors:
Zhou Ren
Xiaoyu Wang
Ning Zhang
Xutao Lv
Li-Jia Li

title: Deep reinforcement learning-based image captioning with embedding reward

authors:
Steffen Rendle
Christoph Freudenthaler
Zeno Gantner
Lars Schmidt-Thieme

title: Bpr: Bayesian personalized ranking from implicit feedback

venue: In Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence,

authors:
Steven J Rennie
Etienne Marcheret
Youssef Mroueh
Jarret Ross
Vaibhava Goel

title: Self-critical sequence training for image captioning

venue: In CVPR,

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

title: Stochastic backpropagation and approximate inference in deep generative models

authors:
Francesco Ricci
Lior Rokach
Bracha Shapira

title: Recommender systems: introduction and challenges

venue: In Recommender systems handbook,

authors:
Ruslan Salakhutdinov
Andriy Mnih
Geoffrey Hinton

title: Restricted boltzmann machines for collaborative filtering

venue: In Proceedings of the 24th international conference on Machine learning,

authors:
Suvash Sedhain
Aditya Krishna Menon
Scott Sanner
Lexing Xie

title: Autorec: Autoencoders meet collaborative filtering

venue: In Proceedings of the 24th International Conference on World Wide Web,

authors:
Suvash Sedhain
Aditya Krishna Menon
Scott Sanner
Darius Braziunas

title: On the effectiveness of linear models for one-class collaborative filtering

venue: In AAAI,

authors:
David Silver
Guy Lever
Nicolas Heess
Thomas Degris
Daan Wierstra
Martin Riedmiller

title: Deterministic policy gradient algorithms

title: Embarrassingly shallow autoencoders for sparse data

authors:
Xiaoyuan Su
Taghi M Khoshgoftaar

title: A survey of collaborative filtering techniques

venue: Advances in artificial intelligence,

authors:
Richard S Sutton
Andrew G Barto
Francis Bach

title: Reinforcement learning: An introduction

venue: MIT press,

authors:
Markus Weimer
Alexandros Karatzoglou
Quoc V Le
Alex J Smola

title: Cofi rank-maximum margin matrix factorization for collaborative ranking

authors:
Jason Weston
Samy Bengio
Nicolas Usunier

title: Wsabie: Scaling up to large vocabulary image annotation

venue: In IJCAI,

authors:
Jason Weston
Hector Yee
Ron J Weiss

title: Learning to rank recommendations with the k-order statistic loss

venue: In Proceedings of the 7th ACM conference on Recommender systems,

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Machine learning,

authors:
Yao Wu
Christopher DuBois
Alice X Zheng
Martin Ester

title: Collaborative denoising auto-encoders for top-n recommender systems

venue: In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining,

authors:
Fen Xia
Tie-Yan Liu
Jue Wang
Wensheng Zhang
Hang Li

title: Listwise approach to learning to rank - theory and algorithm

authors:
Hong-Jian Xue
Xinyu Dai
Jianbing Zhang
Shujian Huang
Jiajun Chen

title: Deep matrix factorization models for recommender systems

authors:
Shuai Zhang
Lina Yao
Aixin Sun

title: Deep learning based recommender system: A survey and new perspectives

venue: arXiv preprint arXiv:1707.07435,

authors:
Yin Zheng
Bangsheng Tang
Wenkui Ding
Hanning Zhou

title: A neural autoregressive approach to collaborative filtering

venue: arXiv preprint arXiv:1605.09477,

authors: Pfau Vinyals

title: which is related to the count features in equation 5. E EXPERIMENTAL SETUP E.1 DATASETS We conduct experiments on three publicly available datasets. Table 3 summarizes the statistics of the data

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.

title: RACT: TOWARDS AMORTIZED RANKING-CRITICAL TRAINING FOR COLLABORATIVE FILTERING


summaries: This paper proposes the Composite Q-learning algorithm, which combines the algorithmic ideas of using compositional TD methods to truncate the horizon of the return, as well as shift a return in time. They claim that this approach will improve the method's data efficiency relative to standard Q-learning. They demonstrate its performance relative to Q-learning in a tabular domain, as well as in deep RL domains which use the compositional idea as an off-policy critic.

summaries: This paper introduces a new Q-learning formalism that helps reduce the bias of single step bootstrapping in Q-learning by learning multiple single step bootstrapping Q functions in parallel. This is accomplished by composing multiple n-step returns, showing that a recursive definition of n-step returns allows each return to be learned using only a single step of bootstrapping instead of at most n steps of bootstrapping. The paper solves the problem of the n-step fixed horizon by additionally composing a gamma discounted Q function that is shifted by n. In the end, the Q function used for behavior still predicts the same values as vanilla Q-learning, but with significantly less bias without a large increase in variance.

summaries: This paper proposes to split the value function into two separately learned components (a short-term truncated value function, and a long-term shifted value function) suggesting the short term truncated returns should learn faster as compared to the tail of the returns. They provide temporal difference formulations for a truncated value function and shifted value function, enabling efficient learning of the two components. They also provide derivations of other similar approaches to the off-policy case. Finally, they compare their algorithm to several approaches on a subset of the MuJoCo tasks, and a novel tabular domain.

abstractText: In the past few years, off-policy reinforcement learning methods have shown promising results in their application for robot control. Deep Q-learning, however, still suffers from poor data-efficiency which is limiting with regard to realworld applications. We follow the idea of multi-step TD-learning to enhance data-efficiency while remaining off-policy by proposing two novel TemporalDifference formulations: (1) Truncated Q-functions which represent the return for the first n steps of a target-policy rollout w.r.t. the full action-value and (2) Shifted Q-functions, acting as the farsighted return after this truncated rollout. We prove that the combination of these shortand long-term predictions is a representation of the full return, leading to the Composite Q-learning algorithm. We show the efficacy of Composite Q-learning in the tabular case and compare our approach in the function-approximation setting with TD3, Model-based Value Expansion and TD3(∆), which we introduce as an off-policy variant of TD(∆). We show on three simulated robot tasks that Composite TD3 outperforms TD3 as well as state-of-the-art off-policy multi-step approaches in terms of data-efficiency.

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A. Rusu
Joel Veness
Marc G. Bellemare
Alex Graves
Martin A. Riedmiller
Andreas Fidjeland
Georg Ostrovski
Stig Petersen
Charles Beattie
Amir Sadik
Ioannis Antonoglou
Helen King
Dharshan Kumaran
Daan Wierstra
Shane Legg
Demis Hassabis

title: Human-level control through deep reinforcement learning

authors:
David Silver
Thomas Hubert
Julian Schrittwieser
Ioannis Antonoglou
Matthew Lai
Arthur Guez
Marc Lanctot
Laurent Sifre
Dharshan Kumaran
Thore Graepel

title: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play

authors:
Timothy P. Lillicrap
Jonathan J. Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations,

authors:
Martin Riedmiller
Roland Hafner
Thomas Lampe
Michael Neunert
Jonas Degrave
Tom van de Wiele
Vlad Mnih
Nicolas Heess
Jost Tobias Springenberg

title: Learning by playing solving sparse reward tasks from scratch

authors:
Tuomas Haarnoja
Sehoon Ha
Aurick Zhou
Jie Tan
George Tucker
Sergey Levine

title: Learning to walk via deep reinforcement learning

venue: In Proceedings of Robotics: Science and Systems,

authors:
Gabriel Barth-Maron
Matthew W. Hoffman
David Budden
Will Dabney
Dan Horgan
Dhruva TB
Alistair Muldal
Nicolas Heess
Timothy P. Lillicrap

title: Distributed distributional deterministic policy gradients

venue: In 6th International Conference on Learning Representations,

authors:
Vladimir Feinberg
Alvin Wan
Ion Stoica
Michael I. Jordan
Joseph E. Gonzalez
Sergey Levine

title: Model-based value expansion for efficient model-free reinforcement learning

authors:
Joshua Romoff
Peter Henderson
Ahmed Touati
Yann Ollivier
Emma Brunskill
Joelle Pineau

title: Separating value functions across time-scales

authors:
Doina Precup
Richard S. Sutton
Satinder P. Singh

title: Eligibility traces for off-policy policy evaluation

venue: Proceedings of the 17th International Conference on Machine Learning ICML,

authors:
Doina Precup
Richard S. Sutton
Sanjoy Dasgupta

title: Off-policy temporal difference learning with function approximation

venue: Proceedings of the 18th International Conference on Machine Learning ICML,

authors:
Rémi Munos
Tom Stepleton
Anna Harutyunyan
Marc G. Bellemare

title: Safe and efficient offpolicy reinforcement learning

venue: Advances in Neural Information Processing Systems

authors:
Jacob Buckman
Danijar Hafner
George Tucker
Eugene Brevdo
Honglak Lee

title: Sampleefficient reinforcement learning with stochastic ensemble value expansion

venue: Advances in Neural Information Processing Systems 31, NeurIPS,

authors:
Kristopher De Asis
J. Fernando Hernandez-Garcia
G. Zacharias Holland
Richard S. Sutton

title: Multi-step reinforcement learning: A unifying algorithm

venue: Proceedings of the 32nd AAAI Conference on Artificial Intelligence,

authors:
J. Fernando Hernandez-Garcia
Richard S. Sutton

title: Understanding multi-step deep reinforcement learning: A systematic study of the DQN target

venue: Deep Reinforcement Learning Workshop (NeurIPS 2018),

authors:
Harm van Seijen
Mehdi Fatemi
Romain Laroche
Joshua Romoff
Tavian Barnes
Jeffrey Tsang

title: Hybrid reward architecture for reinforcement learning

venue: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems,

authors:
Kristopher De Asis
Alan Chan
Silviu Pitis
Richard S. Sutton
Daniel Graves

title: Fixed-horizon temporal difference methods for stable reinforcement learning

title: Learning to predict by the methods of temporal differences

authors:
David Silver
Guy Lever
Nicolas Heess
Thomas Degris
Daan Wierstra
Martin A. Riedmiller

venue: In Proceedings of the 31th International Conference on Machine Learning, ICML,

authors:
Scott Fujimoto
Herke van Hoof
David Meger

title: Addressing function approximation error in actor-critic methods

venue: Proceedings of the 35th International Conference on Machine Learning, ICML,

authors:
Hado van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double qlearning

venue: Proceedings of the 30th AAAI Conference on Artificial Intelligence,

title: A generalization error for q-learning

venue: J. Mach. Learn. Res.,

authors:
Chi Jin
Zeyuan Allen-Zhu
Sébastien Bubeck
Michael I. Jordan

title: Is q-learning provably efficient

venue: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems,

authors:
Michael J. Kearns
Satinder P. Singh

title: Near-optimal reinforcement learning in polynomial time

venue: Machine Learning,

authors:
Greg Brockman
Vicki Cheung
Ludwig Pettersson
Jonas Schneider
John Schulman
Jie Tang
Wojciech Zaremba

title: URL http://arxiv.org/ abs/1606.01540

venue: Openai gym. CoRR,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In IEEE/RSJ International Conference on Intelligent Robots and Systems,

heading: 1 INTRODUCTION

text:
In recent years, Q-learning (Watkins and Dayan, 1992) has achieved major successes in a broad range of areas by employing deep neural networks (Mnih et al., 2015; Silver et al., 2018; Lillicrap et al., 2016), including environments of higher complexity (Riedmiller et al., 2018) and even in first real world applications (Haarnoja et al., 2019). Due to its off-policy update, Q-learning can leverage transitions collected by any policy which makes it more data-efficient compared to onpolicy methods. Deep Q-learning, however, still has a very high demand for data samples which is limiting with regard to robot applications.
One reason for the low data-efficiency is the long temporal horizon the reward signal has to propagate through. Data-efficiency of on-policy Temporal-Difference methods can be enhanced by the use of n-step returns, where a Monte Carlo rollout of length n is combined with a bootstrap of the value function. To employ n-step returns in an off-policy setting, subtrajectories of the exploratory policy have to be stored. These stored multi-step returns, however, will differ from the true value of the target-policy. In order to benefit from n-step data, the replay buffer has to be restricted in size or n has to be set to a small value to keep the samples close to the target-policy (Barth-Maron et al., 2018; Hessel et al., 2018). To avoid these problems, a dynamics model can be used for imaginary rollouts, the so-called Model-based Value Expansion (MVE) (Feinberg et al., 2018). Alternatively, the full return can be composed of value functions with increasing discount, an approach called TD(∆) (Romoff et al., 2019). In this work, we define a model-free Temporal-Difference formulation which follows the idea of multi-step learning while remaining off-policy.
Our contributions are threefold. First, we introduce the Composite Q-learning algorithm. For its formulation, we define Truncated Q-functions, representing the return for the first n steps of a target-policy rollout w.r.t. the full action-value. In addition, we introduce Shifted Q-functions which represent the farsighted return after this truncated rollout. Both are then combined in a mutual recursive definition of the Q-function for the final algorithm. Second, we evaluate MVE within TD3, leading to MVE-TD3. And third, we introduce TD3(∆), an extension of TD(∆) to deep Q-learning. We discuss related work in Section 2, describe the theoretical background in Section 3 and define Composite Q-learning, MVE-TD3 and TD3(∆) in Section 4. By breaking down the long-term return into a composition of several short-term predictions, our method increases data-efficency which
we show in the tabular case and for three simulated robot tasks in Section 5. We then conclude in Section 6.

heading: 2 RELATED WORK

text:
In order to correct for the deviation from the current target-policy, several methods suggest the use of Importance Sampling (Precup et al., 2000; 2001; Munos et al., 2016). Approaches based on Importance Sampling, however, can come with a vast increase in variance or can be of high cost and are not easily applicable to deterministic policies.
One way to remain off-policy in multi-step Q-learning is to get the Monte Carlo rollout on the basis of the current target-policy applied to a learned dynamics model (Feinberg et al., 2018; Buckman et al., 2018). Due to accumulating errors of single-step models, this can lead to severe stability issues in the Q-update, which is also the conclusion of Feinberg et al. (2018). The authors suggest to average all intermediate i-step returns to smoothen out the model error, the so-called TD-k trick. In contrast to our work, Feinberg et al. assume to have access to the true reward function. In order to balance the length of the model-assisted rollout, Buckman et al. (2018) couple it with an uncertainty estimate from value function and model ensembles. We alleviate the problem of accumulating error by estimating a multi-step dynamics model implicitly via consecutive bootstrapping.
Most related to our approach is TD(∆) (Romoff et al., 2019). Romoff et al. formalize a Bellmanoperator over the differences between value functions of increasing discount values. Their approach is on-policy and can therefore benefit directly from n-step returns. We extend TD(∆) to the offpolicy case below. Q-learning can also be extended to a SARSA-like tree-backup called Q(σ) (Asis et al., 2018; Hernandez-Garcia and Sutton, 2018). However, it is an open question how to adjust this idea to continuous action-spaces and deterministic policies. In the Hybrid Reward Architecture (HRA), van Seijen et al. (2017) suggest a decomposition of the reward and the estimation of value functions for each part of this decomposition which are then combined as an approximation of the full return. HRA addresses the problem of complex rewards and is thus complementary to our work focusing on long time scales. Concurrently to our work, Asis et al. (2019) introduced Fixed Horizon TD-learning, formalizing action-value functions for different horizons in time. In contrast to our work, however, Asis et al. define a consecutive bootstrapping formulation w.r.t. the target policies of the different truncated horizons and not the full return. A first general description of using intermediate predictions in Temporal Differences to restrict predictions to a fixed temporal horizon has been introduced in (Sutton, 1988).

heading: 3 BACKGROUND

text:
We consider tasks modelled as Markov decision processes (MDP), where an agent executes action at ∈ A in some state st ∈ S following its stochastic policy π. According to the dynamics model M of the environment, the agent transitions into some state st+1 ∈ S and receives scalar reward rt. The agent aims at maximizing the expected long-term return:
Rπ(st) = Eaj≥t∼π,sj>t∼M T−1∑ j=t γj−trj ∣∣∣∣∣∣st  , (1)
where T is the (possibly infinite) temporal horizon of the MDP and γ ∈ [0, 1] the discount factor. It therefore tries to find π∗, s.t. Rπ∗ ≥ Rπ for all π. If the model of the environment is unknown, model-free methods based on the Bellman Optimality Equation over the so-called action-value can be used:
Qπ(st, at) = Eaj>t∼π,sj>t∼M T−1∑ j=t γj−trj ∣∣∣∣∣∣st, at  . (2)
In the following, we abbreviate Eaj>t∼π,sj>t∼M[·|st, at] by Et,π,M[·]. One popular representative of continuous model-free reinforcement learning is the Deep Deterministic Policy Gradient algorithm (DDPG) (Lillicrap et al., 2016). In DDPG, actor µ is a deterministic mapping from states to actions, µ : S 7→ A, representing the actions that maximize the critic Qµ, i.e.
µ(st) = arg maxaQ µ(st, a). Q and µ are estimated by function approximators Q(·, ·|θQ) and µ(·|θµ), parameterized by θQ and θµ. The critic is optimized on the mean squared error between predictions Q(sj , aj |θQ) and targets yj = rj + γQ′(sj+1, µ′(sj+1|θµ ′ )|θQ′), where Q′ and µ′ are target networks, parameterized by θQ ′ and θµ ′ . The parameters of µ are optimized following the deterministic policy gradient theorem (Silver et al., 2014):
∇θµ ← [ 1
m ∑ j ∇aQ(s, a|θQ)|s=sj ,a=µ(sj |θµ)∇θµµ(s|θµ), (3)
and the parameters of the target networks are updated according to:
θQ ′ ← [ (1− τ)θQ′ + τθQ and θµ′ ← [ (1− τ)θµ′ + τθµ, (4)
with τ ∈ [0, 1]. TD3 (Fujimoto et al., 2018) adds three adjustments to vanilla DDPG. First, the minimum prediction of two distinct critics is taken for target calculation to alleviate overestimation bias, an approach belonging to the family of Double Q-learning algorithms (van Hasselt et al., 2016). Second, Gaussian smoothing is applied to the target-policy, addressing the variance in updates. Third, actor and target networks are updated every d-th gradient step of the critic, to account for the problem of moving targets.

heading: 4 OFF-POLICY MULTI-STEP Q-LEARNING

text: In this section, we introduce the Composite Q-learning algorithm, an off-policy multi-step reinforcement learning method to enhance data-efficiency, along with MVE-TD3 and TD3(∆) as baselines.

heading: 4.1 COMPOSITE Q-LEARNING

text:
The main motivation behind this work is the assumption that learning values on short time scales can be achieved faster than for the full temporal horizon of a task, which can be prohibitively long. As Murphy (2005) shows for the fixed-batch fitted Q-iteration case, the number of samples needed to achieve a certain generalization error is exponential in the horizon of the MDP. As discussed in Jin et al. (2018), Q-learning with UCB-exploration has total regret polynomial in the horizon of the MDP and exponential with -greedy exploration (Kearns and Singh, 2002). We thus argue that truncated horizons for a fixed MDP translate to lower sample complexity of value-estimation. Building upon this idea, we estimate the return of n-step rollouts of the target-policy via Truncated Q-functions which we then combine to the full return with model-free Shifted Q-functions, an approach we call Composite Q-learning, while remaining purely off-policy. Since these quantities cannot be estimated directly from single-step transitions, we introduce a consecutive bootstrapping
scheme based on intermediate predictions. For an overview, see Figure 1a. The full algorithm is in the appendix. Code based on the implementation of TD31 can be found in the supplementary.

heading: 4.1.1 TRUNCATED Q-FUNCTIONS

text:
In order to formalize the off-policy estimation of n-step returns, assume that n (T − 1) and that (T − 1− t) mod n = 0 for task horizon T . We make use of the following observation:
Qπ(st, at) = Et,π,M [ rt + γrt+1 + γ 2rt+2 + γ 3rt+3 + · · ·+ γT−1rT−1 ] = Et,π,M
[t+n−1∑ j=t γj−trj + γn t+2n−1∑ j=t+n γj−(t+n)rj  + · · ·+ γT−n
 T−1∑ j=T−n γj−(T−n)rj ]. (5)
That is, we can define the action-value as the combination of partial sums of length n. We can then define the Truncated Q-function as Qπn(st, at) = Et,π,M[ ∑t+n−1 j=t γ
j−trj ], which we plug into Equation (5):
Qπ(st, at) = Et,π,M[Q π n(st, at) + γ nQπn(st+n, at+n) + · · ·+ γT−nQπn(sT−n, aT−n)]. (6) Theorem 1. Let Qπ1 (st, at) = rt be the one-step Truncated Q-function and Qπi>1(st, at) = rt + γEt,π,M[Q π i−1(st+1, at+1)] the i-step Truncated Q-function. Then Q π i (st, at) represents the
truncated return Qπi (st, at) = Et,π,M[ ∑t+i−1 j=t γ j−trj ].
Following Theorem 1 (the proof can be found in the supplementary), we approximate Qπn(st, at) off-policy via consecutive bootstrapping. Let QTr(·, ·|θQTr) denote a function approximator with parameters θQ
Tr and n outputs, subsequently called heads, estimating Qπi . Each output Q Tr i boot-
straps from the prediction of the preceding head, with the first approximating the immediate reward function. The targets are therefore given by:
yTrj,1 = rj and y Tr j,i>1 = rj + γQ Tr′ i−1(sj+1, µ ′(sj+1|θµ ′ )|θQTr′i−1), (7)
where µ′ corresponds to the actor maximizing the full Q-value as defined in Section 3. That is, QTr represents evaluations of µ at different stages of truncation and yTrj,i<n serve as intermediate predictions to get yTrj,n. We then only use Q Tr n , which implements the full n-step return, as the first part of the composition of the Q-target. Please note that in order to estimate Equation (6), the dynamics model would be needed to get st+c·n of a rollout starting in st. In the following, we describe an approach to achieve an estimation of Equation (6) model-free.

heading: 4.1.2 SHIFTED Q-FUNCTIONS

text:
To get an estimation for the remainder of the rollout Qπn:∞ = Et,π,M[γ nQ(st+n, at+n)] after n steps, we use a consecutive bootstrapping formulation of the Q-prediction. Theorem 2. Let Qπ1:∞(st, at) = Et,π,M[γQπ(st+1, at+1)] be the one-step Shifted Q-function and Qπi>1:∞(st, at) = Et,π,M[γQ π i−1:∞(st+1, at+1)] the i-step Shifted Q-function. Then Q π i:∞(st, at) represents the shifted return Qπi:∞(st, at) = Et,π,M[γ iQπ(st+i, at+i)].
Again, the proof of Theorem 2 can be found in the supplementary. Let QSh(·, ·|θQSh) denote the function approximator estimating the Shifted Q-function Qπn:∞, parameterized by θ
QSh . We can shift the Q-prediction by bootstrapping without taking the immediate reward into account, so as to skip the first n rewards of a target-policy rollout. The Shifted Q-targets for heads QShi therefore become:
yShj,1 = γQ ′(sj+1, µ ′(sj+1|θµ ′ )|θQ′) and yShj,i>1 = γQSh′i−1(sj+1, µ′(sj+1|θµ ′ )|θQSh′i−1). (8)
1https://github.com/sfujim/TD3

heading: 4.1.3 COMPOSITION

text:
Following the definitions of Truncated and Shifted Q-functions, we can compose the full return. Theorem 3. Let Qπn(st, at) = Et,π,M[ ∑t+n−1 j=t γ
j−trj ] be the truncated return and Qπn:∞(st, at) = Et,π,M[γ
nQ(st+n, at+n)] the shifted return. Then Qπ(st, at) = Qπn(st, at) + Qπn:∞(st, at) represents the full return, i.e. Q π(st, at) = Et,π,M[ ∑∞ j=t γ j−trj ].
The incorporation of truncated returns breaks down the time scale of the long-term prediction by the Shifted Q-function. For details, see the proof of Theorem 3 in the supplementary. We can thus define the Composite Q-target as:
yQj = rj + γ(Q Tr′ n (sj+1, µ ′(sj+1|θµ ′ )|θQTr′n ) +QSh′n (sj+1, µ′(sj+1|θµ ′ )|θQSh′n )), (9)
approximated by Q(·, ·|θQ) with parameters θQ. Since we have true reward rj , we include it in the target. Please note, that shifting the action-value in time imposes a bottleneck, since it relies on the estimation of the full action-value. We therefore jointly estimate QTr, QSh and Q with function approximator QC(·, ·|θQC ). Let SEC denote the squared error between targets yCj and predictions QC(sj , aj |θQ C ). See Figure 1b for the detailed architecture of the Composite Q-network.
Each pairQTri +Q Sh i |1≤i≤n is a complete approximation of the true Q-value. The circular dependency can lead to stability issues, due to the amplification of propagated errors. We add a regularization term to the loss penalizing the deviation between the prediction of Q and the n different Q-pairs to keep estimates in a narrow range. It is implemented as the weighted mean squared error, i.e. the loss function becomes:
L = 1 m m∑ j=1
( SEC + β 1
n n∑ i=1 ( Q(sj , aj |θQ)− ( QTri (sj , aj |θQ Tr i ) +QShi (sj , aj |θQ Sh i ) ))2) , (10)
for batch of size m and with β being the regularization weight. Actor µ is then updated on Q.

heading: 4.2 TD3(∆) AND MVE-TD3

text:
Most related to Composite Q-learning are TD(∆) (Romoff et al., 2019) and MVE-DDPG (Feinberg et al., 2018). In this section, we describe how to extend TD(∆) to an off-policy setting and how to combine MVE and TD3.
TD3(∆) Another way to divide the value function into multiple time scales is TD(∆) (Romoff et al., 2019). To this point, it has only been applied in an on-policy setting. In favor of comparability, we extend TD(∆) to Q-learning, yielding TD3(∆). The main idea of TD(∆) is the combination of different value functions corresponding to increasing discount values. Let γ∆ denote a fixed ordered sequence of increasing discount values, i.e. γ∆ = (γ1, γ2, . . . , γk)>|γi>1>γi−1 . We can then define delta functions Wi as: W1 = Qγ1 and Wi>1 = Qγi −Qγi−1 . (11) Let Q∆(·, ·|θQ∆) denote the function approximator estimating Qγ1≤i≤k . Based on the derivations in (Romoff et al., 2019), the targets for Q-learning can be formalized as:
yγj,1 = rj + γ1Q ′ γ1(sj+1, µ ′(sj+1|θµ ′ )|θQ′γ1 ) and
yγj,i>1 = (γi − γi−1)Q′γi−1(sj+1, µ′(sj+1|θµ ′ )|θQ ′ γi−1 ) + γiW ′ i (sj+1, µ ′(sj+1|θµ ′ )|θW ′i ),
(12)
which can then be used in any Q-learning algorithm. The authors suggest the use of n-step targets within TD(∆) which is not easily applicable in an off-policy setting. In our experiments, we therefore compare our approach to single-step TD3(∆). The algorithm can be found in the appendix.
MVE-TD3 We also apply Model-based Value Expansion within TD3, subsequently called MVETD3. We add Gaussian policy smoothing to the rollout of the model. In contrast to Feinberg et al. (2018), however, we do not assume to have knowledge about the reward function. Our model therefore approximates both, dynamics and reward.

heading: 5 EXPERIMENTAL RESULTS

text: We evaluate Composite Q-learning in both, the tabular setting and the actor-critic method TD3.

heading: 5.1 TABULAR COMPOSITE Q-LEARNING

text:
To analyze the effect of incorporating short-term prediction QTrn in the Q-update, we apply Composite Q-learning in the tabular case to the MDP of horizon K given in Figure 2a. We compare it to vanilla Q-learning, as well as multi-step Q-learning based on subtrajectories of the exploratory policy and imaginary rollouts of the target-policy with the true model of the MDP.
Results for K = 20 are depicted in Figure 2b. All approaches update the Q-function with a learning rate of 10−3 on the same fixed batch of 103 episodes with a percentage of 10% non-optimal transitions. For the multi-step approaches, we set rollout length n = 4. Since there is no generalization among states in the tabular setting, we update the Shifted Q-function with a learning rate of 10−2 and the Truncated Q-functions with a learning rate of 10−3. An evaluation of different learning rates for the Shifted Q-functions is depicted in Figure 3. We compare Composite Q-learning and vanilla Q-learning to Shifted Q-learning, which corresponds to Q-learning with a one-step shifted target (without approximate n-step returns from a Truncated Q-function). The results show that shifting the value in time alone is slowing down convergence. Precisely, Shifted Q-learning with a learning rate of 1.0 is equivalent to vanilla Q-learning, the same holds for Composite Q-learning with a learning rate of 10−3 for the Shifted Q-function. The counterpart with different learning rates for the Truncated Q-functions, while keeping the learning rates for the full Q-estimate and Shifted Q-functions fixed, can be seen in Figure 4. While there is improvement in convergence using a larger learning rate for the Truncated Q-functions, the results show higher variance and less benefit than the Shifted Q-functions in Figure 3. The results suggest that the interplay between short- and long-term predictions yields the most benefit if the learning rate for the Shifted Q-functions can be set to a higher value. We believe this to be due to two possible reasons. The higher learning rates for the Truncated Q-functions might lead to overfitting to the shorter horizons (given that it represents an easier learning problem compared to the full return), whereas the Shifted Q-functions allow for
higher learning rates, since they only have to consider the variability of the distribution over next states leading to decreased variance in their targets. In the experiments in Section 5.2, we show that this can also be achieved by generalization as in the given architecture in Figure 1b. The erroneous updates of on-policy multi-step Q-learning lead to convergence to a wrong action-value which is underlining the importance of truly off-policy learning. However, if the true model can be used for the rollout, this can be really effective. The difference in convergence speed between Q-learning and Composite Q-learning is highly significant (p-value of 4 · 10−8 according to a t-test) and grows with increasing horizon, as shown in Table 1. This is in line with the findings of Jin et al. (2018) who establish a connection between the horizon of an MDP and the sample complexity of value estimation.

heading: 5.2 COMPOSITE Q-LEARNING WITH FUNCTION APPROXIMATION

text:
We evaluate TD3, Composite TD3, MVE-TD3 and TD3(∆) on three robot simulation tasks of OpenAI Gym (Brockman et al., 2016) based on MuJoCo (Todorov et al., 2012): Walker2d-v2, Ant-v2 and Hopper-v2. A visualization of the environments is depicted in Figure 5.
Parameter Setting Our main focus is on the analysis of the structure of Q-functions and not to achieve maximum possible performance. We therefore keep the main parameters the same across all approaches (the underlying algorithm was TD3 in all cases), since this would lead to another source of potential differences otherwise. Learning rate (10−3), target update (5 · 10−3) and actor setting (two hidden layers with 400 and 300 neurons and ReLU activation) are the same as in the default setting of TD3. We use Gaussian exploration noise with σ = 0.15. The critic in Composite Q-learning consists of four layers with 500 neurons and leaky ReLU activation, the critic in all other
approaches and the model in MVE-TD3, with a learning rate of 10−3, has two layers. However, we also evaluate TD3 and TD3(∆) with the same critic setting as Composite TD3, see Figure 8 in the supplementary. This corresponds to the most stable setting we could find for TD3 with the given subset of MuJoCo tasks. For Composite TD3, we set n = 50 and β = 10−4 for Walker2d-v2 and Hopper-v2 and β = 5 · 10−5 for Ant-v2. For TD3(∆), we use the γ-schedule as suggested by the authors, i.e. γ1 = 0 and γi>1 = γi−1+1 2 , with an upper limit of 0.99 (Romoff et al., 2019). For MVE-TD3, we use a rollout length of 3, as described in Feinberg et al. (2018).
Data Efficiency We choose the area under the learning curve as performance measure, which is a common way to evaluate data-efficiency and learning stability (see e.g. Hessel et al. (2018)). Since vanilla TD3 can have severe stability issues for a small number of runs, we compare median and interquartile ranges (IQR). As listed in Table 2, Composite TD3 outperforms TD3, as well as state-of-the-art multi-step approaches, in terms of learning speed throughout training. After the considered time frame of 4 · 105 transitions, Composite TD3 has a 19%, 11% and 19% larger area under the median learning curve, in comparison to vanilla TD3. As depicted in Figure 6, MVE-TD3 is highly sensitive w.r.t. accumulating errors in reward and state prediction, even when applying the TD-k trick. However, if dynamics and reward are estimated with high accuracy, model-based rollouts can be very effective, as the results show for Ant-v2. Based on our experiments, TD3(∆) seems to be less sensitive than MVE-TD3, albeit also less efficient than Composite TD3. The maximum return found by all approaches within 4 · 105 transitions can be seen in Table 3.
TD-error Analysis To test our intuition stated in the motivation, we refer to the lower row of Figure 6 which shows the TD-errors for the different stages of truncation, as well as the TD-errors for the complete Q-estimate. All Truncated Q-estimates have lower TD-error throughout learning and it can be seen that the TD-error is consistently higher for longer horizons. This reaffirms our
hypothesis that learning is easier on shorter horizons. The Composite Q-target therefore reflects the true action-value faster which is beneficial for Q-learning.
Sensitivity to Hyperparameters Lastly, we evaluate the influence of n and β, exemplary for the Walker2d-v2 environment. The results can be seen in Figure 7. Shorter truncation horizons can lead to faster convergence, but the variance increases. If n is rather large, however, it can slow learning down. The same holds if the regularization weight β is set to a high value. On the other hand, regularization is needed to keep the predictions in a narrow range, since it can lead to stability issues, otherwise.

heading: 6 CONCLUSION

text:
We introduced Composite Q-learning, an off-policy learning method that divides the long-term value into smaller time scales. It combines Truncated Q-functions acting on a short horizon with Shifted Q-functions for the remainder of the rollout. We analyzed the efficacy of Composite Q-learning in the tabular case and showed that the benefit of short-term predictions increases with growing task horizon. We further evaluated MVE-TD3 and introduced TD3(∆), an off-policy variant of TD(∆). We showed on three simulated robot tasks that Composite TD3 outperforms vanilla TD3 by 19%, 11% and 19% in terms of area under the median learning curve. The given results provide evidence that Composite TD3 enhances data-efficiency compared to other approaches in off-policy multi-step learning.
Going forward, the uncertainty estimate based on the variance of the Composite Q-network could be of benefit in both, update calculation and exploration. We further leave the application of the truncated formulation of other quantities such as state change or auxiliary costs as future work.

heading: A ALGORITHM FOR COMPOSITE TD3

text:
A detailed description of Composite DDPG is given in Algorithm 1, where the adjustments of TD3 are omitted for simplicity. In order to transform Algorithm 1 to its TD3-equivalent, Gaussian policy smoothing has to be added to all targets in Line 8, as well as taking the minimum prediction of two distinct critics for each target. Furthermore, actor and target networks have to be updated with delay.
Algorithm 1: Composite DDPG 1 initialize critic QC , actor µ and targets QC ′, µ′ 2 initialize replay bufferR 3 for episode = 1..E do 4 get initial state s1 5 for t = 1..T do 6 apply action at = µ(st|θµ) + ξ, where ξ ∼ N (0, σ) 7 observe st+1 and rt and save transition (st, at, st+1, rt) inR 8 calculate targets:
yTrj,1 = rj yTrj,i>1 = rj + γQ Tr′ i−1(sj+1, µ ′(sj+1|θµ ′ )|θQ Tr′ i−1) yShj,1 = γQ ′(sj+1, µ ′(sj+1|θµ ′ )|θQ ′ ) yShj,i>1 = γQ Sh′ i−1(sj+1, µ ′(sj+1|θµ ′ )|θQ Sh′ i−1) yQj = rj + γ(Q Tr′ n (sj+1, µ ′(sj+1|θµ ′ )|θQ Tr′ n ) +QSh′n (sj+1, µ ′(sj+1|θµ ′ )|θQ Sh′ n ))
yCj = [ yQj , y Tr j,1, y Tr j,i>1, y Sh j,1, y Sh j,i>1 ] 9 update QC on minibatch b of size m fromR according to Equation (10)
10 update µ on Q 11 adjust parameters of QC ′ and µ′

heading: B ALGORITHM FOR TD3(∆)

text:
A detailed description of DDPG(∆) is given in Algorithm 2. The authors suggest the use of n-step samples which is not easily applicable in an off-policy setting. In our experiments, we therefore compare our approach to single-step TD3(∆). To transform DDPG(∆) to TD3(∆), the adjustments as described in Appendix A have to be applied analogously.
Algorithm 2: DDPG(∆) 1 initialize critic Q∆, actor µ and targets Q∆′, µ′ 2 initialize replay bufferR 3 set discount values γ∆ = (γ0, γ1, . . . , γk)ᵀ 4 for episode = 1..E do 5 get initial state s1 6 for t = 1..T do 7 apply action at = µ(st|θµ) + ξ, where ξ ∼ N (0, σ) 8 observe st+1 and rt and save transition (st, at, st+1, rt) inR 9 calculate targets:
yγj,1 = rj + γ1Q ′ γ1(sj+1, µ ′(sj+1|θµ ′ )|θQ ′ γ1 ) yγj,i>1 = (γi − γi−1)Q ′ γi−1(sj+1, µ ′(sj+1|θµ ′ )|θQ ′ γi−1 )
+γiW ′ i (sj+1, µ ′(sj+1|θµ ′ )|θW ′ i )
10 update Q∆ on minibatch b of size m fromR 11 update µ on Qγk 12 adjust parameters of Q∆′ and µ′

heading: C TRUNCATED Q-FUNCTIONS

text:
Theorem 1. Let Qπ1 (st, at) = rt be the one-step Truncated Q-function and Qπi>1(st, at) = rt + γEt,π,M[Q π i−1(st+1, at+1)] the i-step Truncated Q-function. Then Q π i (st, at) represents the
truncated return Qπi (st, at) = Et,π,M[ ∑t+i−1 j=t γ j−trj ].
Proof. Proof by induction. Qπ1 (st, at) = rt by definition. The theorem follows from induction step:
Qπi (st, at) = rt + γEt,π,M [ Qπi−1(st+1, at+1) ] = rt + γEt,π,M
(t+1)+(i−1)−1∑ j=(t+1) γj−(t+1)rj  = rt + γEt,π,M
 t+i−1∑ j=(t+1) γj−(t+1)rj  = rt + Et,π,M
 t+i−1∑ j=(t+1) γj−trj  = Et,π,M
t+i−1∑ j=t γj−trj  .

heading: D SHIFTED Q-FUNCTIONS

text:
Theorem 2. Let Qπ1:∞(st, at) = Et,π,M[γQπ(st+1, at+1)] be the one-step Shifted Q-function and Qπi>1:∞(st, at) = Et,π,M[γQ π i−1:∞(st+1, at+1)] the i-step Shifted Q-function. Then Q π i:∞(st, at) represents the shifted return Qπi:∞(st, at) = Et,π,M[γ iQπ(st+i, at+i)].
Proof. Proof by induction. Qπ1:∞(st, at) = Et,π,M[γQ π(st+1, at+1)] by definition. The theorem follows from induction step:
Qπi:∞(st, at) = Et,π,M [ γQπi−1:∞(st+1, at+1) ] = Et,π,M [ γ(γi−1Qπ(st+1+i−1, at+1+i−1))
] = Et,π,M [ γ(γi−1Qπ(st+i, at+i))
] = Et,π,M [ γiQπ(st+i, at+i) ] .

heading: E RESOLVING THE MUTUAL RECURSION

text:
Theorem 3. Let Qπn(st, at) = Et,π,M[ ∑t+n−1 j=t γ
j−trj ] be the truncated return and Qπn:∞(st, at) = Et,π,M[γ
nQ(st+n, at+n)] the shifted return. Then Qπ(st, at) = Qπn(st, at) + Qπn:∞(st, at) represents the full return, i.e. Q π(st, at) = Et,π,M[ ∑∞ j=t γ j−trj ].
Proof.
Qπ(st, at) = Q π n(st, at) +Q π n:∞(st, at)
= Et,π,M t+n−1∑ j=t γj−trj + γ nQπ(st+n, at+n)  = Et,π,M
t+n−1∑ j=t γj−trj + γ n ( Qπn(st+n, at+n) +Q π n:∞(st+n, at+n) ) = Et,π,M
t+n−1∑ j=t γj−trj + γ n ( t+2n−1∑ j=t+n γj−t−nrj + γ nQπ(st+2n, at+2n) ) = Et,π,M
t+n−1∑ j=t γj−trj + t+2n−1∑ j=t+n γj−trj + γ 2nQπ(st+2n, at+2n)  = Et,π,M
t+2n−1∑ j=t γj−trj + γ 2nQπ(st+2n, at+2n)  . Repeating this process then gives Qπ(st, at) = Et,π,M[ ∑∞ j=t γ j−trj ].
Due to the composite structure, the Shifted Q-function represents the long-term sum of partial returns provided by the Truncated Q-function, as opposed to single reward values.

heading: F TD3 AND TD3(∆) WITH LARGER NETWORKS

text: To further analyze the impact of the Composite Q-learning structure, we evaluate TD3 and TD3(∆) with the same number of parameters for the critic, as depicted in Figure 8. The approaches do not seem to make use of the additional capacity and reveal a worse performance in the given time frame.

heading: G SHALLOW ARCHITECTURE

text:
In order to analyze importance of the multi-layered structure reflecting the temporal dependencies between short- and long-term predictions, we compare the architecture used in our experiments to a shallow architecture which includes all predictions as outputs of the last hidden layer for the Walker2d-v2 environment in Figure 9. Based on the results in Appendix F, we reduced the amount of hidden layers to two.
H INDIVIDUAL COMPARISONS
For clarity, we provide individual comparisons between Composite TD3 and all baselines.