Model-Based Reinforcement Learning with Adversarial Training for Online Recommendation

  • 2019-11-13 01:40:22
  • Xueying Bai, Jian Guan, Hongning Wang
  • 0

Abstract

Reinforcement learning is effective in optimizing policies for recommendersystems. Current solutions mostly focus on model-free approaches, which requirefrequent interactions with a real environment, and thus are expensive in modellearning. Offline evaluation methods, such as importance sampling, canalleviate such limitations, but usually request a large amount of logged dataand do not work well when the action space is large. In this work, we propose amodel-based reinforcement learning solution which models the user-agentinteraction for offline policy learning via a generative adversarial network.To reduce bias in the learnt policy, we use the discriminator to evaluate thequality of generated sequences and rescale the generated rewards. Ourtheoretical analysis and empirical evaluations demonstrate the effectiveness ofour solution in identifying patterns from given offline data and learningpolicies based on the offline and generated data.

 

Quick Read (beta)

Model-Based Reinforcement Learning with Adversarial Training for Online Recommendation

Xueying Bai, Jian Guan §, Hongning Wang
Department of Computer Science, Stony Brook University
§ Department of Computer Science and Technology, Tsinghua University
Department of Computer Science, University of Virginia
[email protected], [email protected]
[email protected]
Both authors contributed equally.
Abstract

Reinforcement learning is effective in optimizing policies for recommender systems. Current solutions mostly focus on model-free approaches, which require frequent interactions with a real environment, and thus are expensive in model learning. Offline evaluation methods, such as importance sampling, can alleviate such limitations, but usually request a large amount of logged data and do not work well when the action space is large. In this work, we propose a model-based reinforcement learning solution which models the user-agent interaction for offline policy learning via a generative adversarial network. To reduce bias in the learnt policy, we use the discriminator to evaluate the quality of generated sequences and rescale the generated rewards. Our theoretical analysis and empirical evaluations demonstrate the effectiveness of our solution in identifying patterns from given offline data and learning policies based on the offline and generated data.

 

Model-Based Reinforcement Learning with Adversarial Training for Online Recommendation


  Xueying Bai, Jian Guanthanks: Both authors contributed equally. §, Hongning Wang Department of Computer Science, Stony Brook University § Department of Computer Science and Technology, Tsinghua University Department of Computer Science, University of Virginia [email protected], [email protected] [email protected]

\@float

noticebox[b]33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada.\[email protected]

1 Introduction

Recommender systems are widely used to recommend items that users would be interested in among the huge amount of content on the internet. However, because of users’ different interests and behaviors, only a small fraction of items are viewed by each user with even less feedback recorded. This gives relatively little information on user-recommender interactions for such a large state and action space chen2019top, and thus brings challenges to serve users with their favored items at the appropriate time based on historical interactions. Therefore, it is important to develop approaches to learn users’ preferences from the sparse user feedback such as clicks and purchases he2016fast, and explore unobserved interactions koren2009matrix to further improve recommenders.

Users’ interests can be short-term or long-term and reflected by different types of feedback wu2017returning. For example, clicks are generally considered as short-term feedback which reflects users’ immediate interests during the interaction, while purchase reveals users’ long-term interests which usually happen after several clicks. Considering both users’ short-term and long-term interests, we frame the recommender system as a reinforcement learning (RL) agent, which aims to maximize users’ overall long-term satisfaction without sacrificing the recommendations’ short-term utility shani2005mdp.

Classical model-free RL methods require collecting large quantities of data by interacting with the environment, e.g., a population of users. Therefore, without interacting with real users, a recommender cannot easily probe for reward in previously unexplored regions in the state and action space. However, it is prohibitively expensive for a recommender to interact with users for reward and model updates, because bad recommendations (e.g., for exploration) hurt user satisfaction and increase the risk of user drop out. In this case, it is preferred for a recommender to learn a policy by fully utilizing the logged data that is acquired from other policies instead of direct interactions with users. For this purpose, in this work we take a model-based learning approach, in which we simultaneously estimate a model of user behavior from the offline data and use it to interact with our learning agent to obtain an improved policy.

Model-based RL has a strong advantage of being sample efficient and helping reduce noise in offline data. However, such an advantage can easily diminish due to the inherent bias in its model approximation of the real environment. Moreover, dramatic changes in subsequent policy updates impose the risk of decreased user satisfaction, i.e., inconsistent recommendations across model updates. To address these issues, we introduce adversarial training into a recommender’s policy learning from offline data. The discriminator is trained to differentiate simulated interaction trajectories from real ones so as to debias the user behavior model and improve policy learning. To the best of our knowledge, this is the first work to explore adversarial training over a model-based RL framework for recommendation. We theoretically and empirically demonstrate the value of our proposed solution in policy evaluation. Together, the main contributions of our work are as follows:

  • To avoid the high interaction cost, we propose a unified solution to more effectively utilize the logged offline data with model-based RL algorithms, integrated via adversarial training. It enables robust recommendation policy learning.

  • The proposed model is verified through theoretical analysis and extensive empirical evaluations. Experiment results demonstrate our solution’s better sample efficiency over the state-of-the-art baselines 11 1 Our implementation is available at https://github.com/JianGuanTHU/IRecGAN.

2 Related Work

Deep RL for recommendation There have been studies utilizing deep RL solutions in news, music and video recommendations lu2016partially; liebman2015dj; zheng2018drn. However, most of the existing solutions are model-free methods and thus do not explicitly model the agent-user interactions. In these methods, value-based approaches, such as deep Q-learning mnih2015human, present unique advantages such as seamless off-policy learning, but are prone to instability with function approximation sutton2000policy; mnih2013playing. And the policy’s convergence in these algorithms is not well-studied. In contrast, policy-based methods such as policy gradient learning1998introduction remain stable but suffer from data bias without real-time interactive control due to learning and infrastructure constraints. Oftentimes, importance sampling munos2016safe is adopted to address the bias but instead results in huge variance chen2019top. In this work, we rely on a policy gradient based RL approach, in particular, REINFORCE williams1992simple; but we simultaneously estimate a user behavior model to provide a reliable environment estimate so as to update our agent on policy.

Model-based RL Model-based RL algorithms incorporate a model of the environment to predict rewards for unseen state-action pairs. It is known in general to outperform model-free solutions in terms of sample complexity deisenroth2013survey, and has been applied successfully to control robotic systems both in simulation and real world deisenroth2011pilco; meger2015learning; morimoto2003minimax; deisenroth2011learning. Furthermore, Dyna-Q sutton1990integrated; peng2018deep integrates model-free and model-based RL to generate samples for learning in addition to the real interaction data. gu2016continuous extended these ideas to neural network models, and peng2018deep further apply the method on task-completion dialogue policy learning. However, the most efficient model-based algorithms have used relatively simple function approximations, which actually have difficulties in high-dimensional space with nonlinear dynamics and thus lead to huge approximation bias.

Offline evaluation The problems of off-policy learning munos2016safe; precup2000eligibility; precup2001off and offline policy evaluation are generally pervasive and challenging in RL, and in recommender systems in particular. As a policy evolves, so does the distribution under which the expectation of gradient is computed. Especially in the scenario of recommender systems, where item catalogues and user behavior change rapidly, substantial policy changes are required; and therefore it is not feasible to take the classic approaches schulman2015trust; achiam2017constrained to constrain the policy updates before new data is collected under an updated policy. Multiple off-policy estimators leveraging inverse-propensity scores, capped inverse-propensity scores and various variance control measures have been developed thomas2016data; swaminathan2015self; swaminathan2015batch; gilotte2018offline for this purpose.

RL with adversarial training yu2017seqgan propose SeqGAN to extend GANs with an RL-like generator for the sequence generation problem, where the reward signal is provided by the discriminator at the end of each episode via a Monte Carlo sampling approach. The generator takes sequential actions and learns the policy using estimated cumulative rewards. In our solution, the generator consists of two components, i.e., our recommendation agent and the user behavior model, and we model the interactive process via adversarial training and policy gradient. Different from the sequence generation task which only aims to generate sequences similar to the given observations, we leverage adversarial training to help reduce bias in the user model and further reduce the variance in training our agent. The agent learns from both the interactions with the user behavior model and those stored in the logged offline data. To the best of our knowledge, this is the first work that utilizes adversarial training for improving both model approximation and policy learning on offline data.

3 Problem Statement

The problem is to learn a recommender that recommends items to maximize cumulative rewards of an online recommendation system by efficiently utilizing offline data. We address this problem with a model-based reinforcement learning solution, which also needs to capture users’ behavior patterns.

Problem A recommender is formed as a learning agent to generate actions under a policy, where each action gives a recommendation list with k items. Every time through interactions between the agent and the environment (i.e., users of the system), a set Ω of n sequences Ω={τ1,,τn} is recorded, where τi is the i-th sequence containing agent actions, user behaviors and rewards: τi={(a0i,c0i,r0i),(a1i,c1i,r1i),,(ati,cti,rti)}, rti represents the reward on ati (e.g., make a purchase), and cti is the associated user behavior corresponding to agent’s action ati (e.g., click on a recommended item). For simplicity, in the rest of paper, we drop the superscript i to represent a general sequence τ. Based on the observed sequences, a policy π is learnt to maximize the expected cumulative reward 𝔼τπ[t=0Trt], where T is the end time of τ.

Assumption To narrow the scope of our discussion, we study a typical type of user behavior, i.e., clicks, and make following assumptions: 1) at each time a user must click on one item from the recommendation list; 2) items not clicked in the recommendation list will not influence the user’s future behaviors; 3) rewards only relate to clicked items. For example, when taking the user’s purchase as reward, purchases can only happen on the clicked items.

Learning framework In a Markov Decision Process, an environment consists of a state set S, an action set A, a state transition distribution P:S×A×S, and a reward function fr:S×A, which maps a state-action pair to a real-valued scalar. In this paper, the environment is modeled as a user behavior model 𝒰, and learnt from offline log data. S is reflected by the interaction history before time t, and P captures the transition of user behaviors. In the meanwhile, based on the assumptions mentioned above, at each time t, the environment generates user’s click ct on items recommended by an agent 𝒜 in at based on his/her click probabilities under the current state; and the reward function fr generates reward rt for the clicked item ct.

Our recommendation policy is learnt from both offline data and data sampled from the learnt user behavior model, i.e., a model-based RL solution. We incorporate adversarial training in our model-based policy learning to: 1) improve the user model to ensure the sampled data is close to true data distribution; 2) utilize the discriminator to scale rewards from generated sequences to further reduce bias in value estimation. Our proposed solution contains an interactive model constructed by 𝒰 and 𝒜, and an adversarial policy learning approach. We name the solution as InteractiveRecGAN, or IRecGAN in short. The overview of our proposed solution is shown in Figure 1.

Figure 1: Model overview of IRecGAN. 𝒜, 𝒰 and 𝒟 denote the agent model, user behavior model, and discriminator, respectively. In IRecGAN, 𝒜 and 𝒰 interact with each other to generate recommendation sequences that are close to the true data distribution, so as to jointly reduce bias in 𝒰 and improve the recommendation quality in 𝒜.

4 Interactive Modeling for Recommendation

We present our interactive model for recommendation, which consists of two components: 1) the user behavior model 𝒰 that generates user clicks over the recommended items with corresponding rewards; and 2) the agent 𝒜 which generates recommendations according to its policy. 𝒰 and 𝒜 interact with each other to generate user behavior sequences for adversarial policy learning.

User behavior model Given users’ click observations {c0,c1,,ct-1}, the user behavior model 𝒰 first projects the clicked item into an embedding vector 𝐞u at each time 22 2 As we can use different embeddings on the user side and agent side, we use the superscript u and a to denote this difference accordingly.. The state 𝐬tu can be represented as a summary of click history, i.e., 𝐬tu=hu(𝐞0u,𝐞1u,𝐞t-1u). We use a recurrent neural network to model the state transition P on the user side, thus for the state 𝐬tu we have,

𝐬tu=hu(𝐬t-1u,𝐞t-1u),

hu(,) can be functions in the RNN family like GRU chung2014empirical and LSTM hochreiter1997long cells. Given the action at={at(1),at(k)}, i.e., the top-k recommendations at time t, we compute the probability of click among the recommended items via a softmax function,

𝐕c=(𝐖c𝐬tu+𝐛c)𝐄tu,p(ct|𝐬tu,at)=exp(𝐕ic)/j=1|at|exp(𝐕jc) (1)

where 𝐕ck is a transformed vector indicating the evaluated quality of each recommended item at(i) under state 𝐬tu, 𝐄tu is the embedding matrix of recommended items, 𝐖c is the click weight matrix, and 𝐛c is the corresponding bias term. Under the assumption that target rewards only relate to clicked items, the reward rt for (𝐬tu, at) is calculated by:

rt(𝐬tu,at)=fr((𝐖r𝐬tu+𝐛r)𝐞tu), (2)

where 𝐖r is the reward weight matrix, 𝐛r is the corresponding bias term, and fr is the reward mapping function and can be set according to the reward definition in specific recommender systems. For example, if we make rt to be the purchase of a clicked item ct, where rt=1 if it is purchased and rt=0 otherwise, fr can be realized by a Sigmoid function with binary output.

Based on Eq (1) and (2), taking the categorical reward, the user behavior model 𝒰 can be estimated from the offline data Ω via maximum likelihood estimation:

maxτiΩt=0Tilogp(cti|𝐬tui,ati)+λplogp(rti|𝐬tui,cti), (3)

where λp is a parameter balancing the loss between click prediction and reward prediction, and Ti is the length of the observation sequence τi. With a learnt user behavior model, user clicks and reward on the recommendation list can be sampled from Eq (1) and (2) accordingly.

Agent The agent should take actions based on the environment’s provided states. However, in practice, users’ states are not observable in a recommender system. Besides, as discussed in oh2017value, the states for the agent to take actions may be different from those for users to generate clicks and rewards. As a result, we build a different state model on the agent side in 𝒜 to learn its states. Similar to that on the user side, given the projected click vectors {𝐞0a,𝐞2a,𝐞t-1a}, we model states on the agent side by 𝐬ta=ha(𝐬t-1a,𝐞t-1a), where 𝐬ta denotes the state maintained by the agent at time t, ha(,) is the chosen RNN cell. The start state 𝐬0a for the first recommendation is drawn from a distribution ρ. We simply denote it as 𝐬0 in the rest of our paper. We should note that although the agent also models states based on users’ click history, it might create different state sequences than that on the user side.

Based on the current state 𝐬ta, the agent generates a size-k recommendation list out of the entire set of items as its action at. The probability of item i to be included in at under the policy π is:

π(iat|𝐬ta)=exp(𝐖ia𝐬ta+𝐛ia)j=1|C|exp(𝐖ja𝐬ta+𝐛ja), (4)

where 𝐖ia is the i-th row of the action weight matrix 𝐖a, C is the entire set of recommendation candidates, and 𝐛ia is the corresponding bias term. Following chen2019top, we generate at by sampling without replacement according to Eq (4). Unlike pmlr-v97-chen19f, we do not consider the combinatorial effect among the k items by simply assuming the users will evaluate them independently (as indicated in Eq (1)).

5 Adversarial Policy Learning

We use the policy gradient method REINFORCE williams1992simple for the agent’s policy learning, based on both generated and offline data. When generating τ^0:t={(a^0,c^0,r^0),,(a^t,c^t,r^t)} for t>0, we obtain a^t=𝒜(τ^0:t-1c) by Eq (4), c^t=𝒰c(τ^0:t-1c,a^t) by Eq (2), and r^t=𝒰r(τ^0:t-1c,c^t) by Eq (1). τc represents clicks in the sequence τ and (a^0,c^0,r^0) is generated by 𝐬0a and 𝐬0u. The generation of a sequence ends at the time t if c^t=cend, where cend is a stopping symbol. The distributions of generated and offline data are denoted as g and data respectively. In the following discussions, we do not explicitly differentiate τ and τ^ when the distribution of them is specified. Since we start the training of 𝒰 from offline data, it introduces inherent bias from the observations and our specific modeling choices. The bias affects the sequence generation and thus may cause biased value estimation. To reduce the effect of bias, we apply adversarial training to control the training of both 𝒰 and 𝒜. The discriminator scores are also used to rescale the generated rewards r^ for policy learning. Therefore, the learning of agent 𝒜 considers both sequence generation and target rewards.

5.1 Adversarial training

We leverage adversarial training to encourage our IRecGAN model to generate high-quality sequences that capture intrinsic patterns in the real data distribution. A discriminator 𝒟 is used to evaluate a given sequence τ, where 𝒟(τ) represents the probability that τ is generated from the real recommendation environment. The discriminator can be estimated by minimizing the objective function:

-𝔼τdatalog(𝒟(τ))-𝔼τglog(1-𝒟(τ)). (5)

However, 𝒟 only evaluates a completed sequence, while it cannot directly evaluate a partially generated sequence at a particular time step t. Inspired by yu2017seqgan, we utilize the Monte-Carlo tree search algorithm with the roll-out policy constructed by 𝒰 and 𝒜 to get sequence generation score at each time. At time t, the sequence generation score q𝒟 of τ0:t is defined as:

q𝒟(τ0:t)={1Nn=1N𝒟(τ0:Tn),τ0:TnMC𝒰,𝒜(τ0:t;N)t<T𝒟(τ0:T)t=T (6)

where MC𝒰,𝒜(τ0:t;N) is the set of N sequences sampled from the interaction between 𝒰 and 𝒜.

Given the observations in offline data, 𝒰 should generate clicks and rewards that reflect intrinsic patterns of the real data distribution. Therefore, 𝒰 should maximize the sequence generation objective 𝔼𝐬0uρ[(a0,c0,r0)g𝒰(c0,r0|𝐬0u,a0)q𝒟(τ0:0)], which is the expected discriminator score for generating a sequence from the start state. 𝒰 may not generate clicks and rewards exactly the same as those in offline data, but the closeness of its generated data to offline data is still an informative signal to evaluate its sequence generation quality. By setting q𝒟(τ0:t)=1 at any time t for offline data, we extend this objective to include offline data (it becomes the data likelihood function on offline data). Following yu2017seqgan, based on Eq (1) and Eq (2), the gradient of 𝒰’s objective can be derived as,

𝔼τ{g,data}[t=0Tq𝒟(τ0:t)Θu(logpΘu(ct|𝐬tu,at)+λplogpΘu(rt|𝐬tu,ct))], (7)

where Θu denotes the parameters of 𝒰 and Θa denotes those of 𝒜. Based on our assumption, even when 𝒰 can already capture users’ true behavior patterns, it still depends on 𝒜 to provide appropriate recommendations to generate clicks and rewards that the discriminator will treat as authentic. Hence, 𝒜 and 𝒰 are coupled in this adversarial training. To encourage 𝒜 to provide needed recommendations, we include q𝒟(τ0:t) as a sequence generation reward for 𝒜 at time t as well. As q𝒟(τ0:t) evaluates the overall generation quality of τ0:t, it ignores sequence generations after t. To evaluate the quality of a whole sequence, we require 𝒜 to maximize the cumulative sequence generation reward 𝔼τ{g,data}[t=0Tq𝒟(τ0:t)]. Because 𝒜 does not directly generate the observations in the interaction sequence, we approximate Θa(t=0Tq𝒟(τ0:t)) as 0 when calculating the gradients. Putting these together, the gradient derived from sequence generations for 𝒜 is estimated as,

𝔼τ{g,data}[t=0T(t=tTγt-tq𝒟(τ0:t))ΘalogπΘa(ctat|𝐬ta)]. (8)

Based on our assumption that only the clicked items influence user behaviors, and 𝒰 only generates rewards on clicked items, we use πΘa(ctat|sta) as an estimation of πΘa(at|sta), i.e., 𝒜 should promote ct in its recommendation at time t. In practice, we add a discount factor γ<1 when calculating the cumulative rewards to reduce estimation variance chen2019top.

5.2 Policy learning

Because our adversarial training encourages IRecGAN to generate clicks and rewards with similar patterns as offline data, and we assume rewards only relate to the clicked items, we use offline data as well as generated data for policy learning and treat the offline rewards as an estimation of the rewards of πΘa. Given data τ0:T={(a0,c0,r0),,(aT,cT,rT)}, including both offline and generated data, the objective of the agent is to maximize the expected cumulative reward 𝔼τ{g,data}[RT], where RT=t=0Trt. In the generated data, due to the difference in distributions of the generated and offline sequences, the generated reward r^t calculated by Eq (2) might be biased. To reduce such bias, we utilize the sequence generation score in Eq (6) to rescale generated rewards: rts=q𝒟(τ0:t)r^t, and treat it as the reward for generated data. The gradient of the objective is thus estimated by:

𝔼τ{g,data}[t=0TRtΘalogπΘa(ctat|𝐬ta)],Rt=t=tTγt-tq𝒟(τ0:t)rt (9)

Rt is an approximation of RT with γ as the discount factor. Overall, the user behavior model 𝒰 is updated only by the sequence generation objective defined in Eq (7) on both offline and generated data; but the agent 𝒜 is updated by both sequence generation and target rewards. Hence, the overall reward for 𝒜 at time t is q𝒟(τ0:t)(1+λrrt), where λr is the weight for cumulative target rewards. The overall gradient for 𝒜 is thus:

𝔼τ{g,data}[t=0TRtaΘalogπΘa(ctat|𝐬ta)],Rta=t=tTγt-tq𝒟(τ0:t)(1+λrrt) (10)

6 Theoretical Analysis

For one iteration of policy learning in IRecGAN, we first train the discriminator 𝒟 with offline data, which follows Pdata and was generated by an unknown logging policy, and the data generated by IRecGAN under πΘa with the distribution of g. When Θu and Θa are learnt, for a given sequence τ, by proposition 1 in goodfellow2014generative, the optimal discriminator 𝒟 is 𝒟*(τ)=Pdata(τ)Pdata(τ)+Pg(τ).

Sequence generation Both 𝒜 and 𝒰 contribute to the sequence generation in IRecGAN. 𝒰 is updated by the gradient in Eq (7) to maximize the sequence generation objective. At time t, the expected sequence generation reward for 𝒜 on the generated data is: Eτ0:tg[q𝒟(τ0:t)]=Eτ0:tg[𝒟(τ0:T|τ0:t)]. The expected value on τ0:t is: 𝔼τg[Vg]=𝔼τg[t=0Tq𝒟(τ0:t)]=t=0T𝔼τ0:tg[𝒟(τ0:T|τ0:t)]. Given the optimal 𝒟*, the sequence generation value can be written as:

𝔼τg[Vg]=t=0T𝔼τ0:tg[Pdata(τ0:T|τ0:t)Pdata(τ0:T|τ0:t)+Pg(τ0:T|τ0:t)]. (11)

Maximizing each term in the summation of Eq (11) is an objective for the generator at time t in GAN. According to goodfellow2014generative, the optimal solution for all such terms is Pg(τ0:T|s0)=Pdata(τ0:T|s0). It means 𝒜 can maximize the sequence generation value when it helps to generate sequences with the same distribution as data. Besides the global optimal, Eq (11) also encourages 𝒜 to reward each Pg(τ0:T|τ0:t)=Pdata(τ0:T|τ0:t), even if τ0:t is less likely to be generated from Pg. This prevents IRecGAN to recommend items only considering users’ immediate preferences.

Value estimation The agent 𝒜 should also be updated to maximize the expected value of target rewards Va. To achieve this, we use discriminator 𝒟 to rescale the estimation of Va on the generated sequences, and we also combine offline data to evaluate Va for policy πΘa:

𝔼τπΘa[Va]=λ1t=0T𝔼τ0:tgPdata(τ0:t)Pdata(τ0:t)+Pg(τ0:t)r^t+λ2t=0T𝔼τ0:tdatart, (12)

where r^t is the generated reward by 𝒰 at time t and rt is the true reward. λ1 and λ2 represent the ratio of generated data and offline data during model training, and we require λ1+λ2=1. Here we simplify P(τ0:T|τ0:t) as P(τ0:t). As a result, there are three sources of biases in this value estimation:

Δ=r^t-rt,δ1=1-PπΘa(τ0:t)/Pg(τ0:t),δ2=1-PπΘa(τ0:t)/Pdata(τ0:t).

Based on different sources of biases, the expected value estimation in Eq (12) is:

𝔼τπΘa[Va]= λ1t=0T𝔼τ0:tgPπΘa(τ0:t)Pg(τ0:t)Δ+rt2-(δ1+δ2)+λ2t=0T𝔼τ0:tdata(PπΘa(τ0:t)Pdata(τ0:t)+δ2)rt
= VaπΘa+t=0T𝔼τ0:tπΘawtΔ+t=0T𝔼τ0:tdataλ2δ2rt-t=0T𝔼τ0:tπΘa(λ1-wt)rt,

where wt=λ12-(δ1+δ2). Δ and δ1 come from the bias of user behavior model 𝒰. Because the adversarial training helps to improve 𝒰 to capture real data patterns, it decreases Δ and δ2. Because we can adjust the sampling ratio λ1 to reduce wt, wtΔ can be small. The sequence generation rewards for agent 𝒜 encourage distribution g to be close to data. Because δ2=1-PπΘa(τ0:t)Pg(τ0:t)Pg(τ0:t)Pdata(τ0:t), the bias δ2 can also be reduced. It shows our method has a bias controlling effect.

7 Experiments

In our theoretical analysis, we can find that reducing the model bias improves value estimation, and therefore improves policy learning. In this section, we conduct empirical evaluations on both real-world and synthetic datasets to demonstrate that our solution can effectively model the pattern of data for better recommendations, compared with state-of-the-art baselines.

7.1 Simulated Online Test

Subject to the complexity and difficulty of deploying a recommender system with real users for online evaluation, we use simulation-based studies to first investigate the effectiveness of our approach following zhao2019model; pmlr-v97-chen19f.

Simulated Environment We synthesize an MDP to simulate an online recommendation environment. It has m states and n items for recommendation, with a randomly initialized transition probability matrix P(sS|ajA,siS). Under each state si, an item aj’s reward r(ajA|siS) is uniformly sampled from the range of 0 to 1. During the interaction, given a recommendation list including k items selected from the whole item set by an agent, the simulator first samples an item proportional to its ground-truth reward under the current state si as the click candidate. Denote the sampled item as aj, a Bernoulli experiment is performed on this item with r(aj) as the success probability; then the simulator moves to the next state according to the state transition probability p(s|aj,si). The special state s0 is used to initialize all the sessions, which do not stop until the Bernoulli experiment fails. The immediate reward is 1 if the session continues to the next step; otherwise 0. In our experiment, m,n and k are set to 10, 50 and 10 respectively.

Offline Data Generation We generate offline user logs denoted by doff with the simulator. We especially control the bias and variance in doff by changing the logging policy and the size of doff to compare the performance of different models. We adopt three different logging policies: 1) uniformly random policy πrandom, 2) maximum reward policy πmax, and 3) mixed reward policy πmix. Specifically, πmax recommends the top k items with the highest ground-truth reward under the current simulator state at each step, while πmix randomly selects k items with either the top 20%-50% ground-truth reward or the highest ground-truth reward under a given state. In the meanwhile, we vary the size of doff from 200 to 10,000.

(a) πrandom(200)
(b) πrandom(10,000)
(c) πmax(10,000)
(d) πmix(10,000)
Figure 2: Online evaluation results of [email protected] and cumulative rewards. We varied different logging policies and the size of simulated offline data.
Figure 3: Online learning results of [email protected] and [email protected]

Baselines We compared our IRecGAN with the following baselines: 1). LSTM: only the user behavior model trained on offline data; 2). PG: only the agent model trained by policy gradient on offline data; 3). LSTMD: the user behavior model in IRecGAN, updated by adversarial training.

Experiment Settings The hyper-parameters in all models are set as follows: the item embedding dimension is set to 50, the discount factor γ in value calculation is set to 0.9, the scale factors λr and λp are set to 3 and 1. We apply 2-layer LSTM units with 512-dimension hidden states. The ratio of generated training samples and offline data for each training epoch is set to 1:10. We use an RNN based discriminator in all experiments with details provided in the appendix.

Online Evaluation After we finish model and baselines training on doff, we deploy the learnt policy to interact with the simulator for online evaluation. We calculated [email protected] to measure the average proportion of the top r relevant items in ground-truth that are actually recommended by an agent (i.e., in its top k recommendations) across all the time steps. The results of [email protected] under different configurations of offline data generation are reported in Figure 2. LSTM outperforms policy gradient under πrandom, because under this logging policy every item has an equal chance to be observed (i.e., full exploration), LSTM better recognizes each item’s true reward via maximum likelihood estimation. A similar comparison is observed between our user model and agent model: LSTMD can capture the true reward even with much fewer data. Under πmax and πmix, it is easy for all models to recognize items with the highest reward. But the low [email protected] suggests that they fail to capture the overall preference as the items with lower reward are less likely to be clicked. This becomes more serious under πmix that requires a model to differentiate top relevant items from those with moderate reward. By generating more training data via adversarial training, our model performed better than baselines.

After offline training, the average cumulative rewards for all methods are also evaluated and reported in the rightmost bars of Figure 2. The cumulative rewards are calculated by generating 1000 sequences with the environment and take average of their cumulative rewards. IRecGAN has a larger average cumulative reward than other methods under all configurations except πrandom with 200 offline sequences. However, on πrandom(200) it has less variance than other methods, which indicates the robustness of IRecGAN when the volume of offline data is limited.

Online Learning To evaluate our model’s effectiveness in reducing the bias of value estimation in a more practical setting, we execute online and offline learning alternately. Specifically, we separate the learning into two stages: first, the agents can directly interact with the simulator to update their policies, and we only allow them to generate 200 sequences in this stage; then they turn to the offline stage to reuse their generated data for offline learning. We iterate these two stages and record their recommendation performance during the online learning stage. We compare with the following baselines: 1) PG-online with only online learning, 2) PG-online&offline with online learning and reusing the generated data via policy gradient for offline learning, and 3) LSTM-offline with only offline learning. We train all the models from scratch and report the performance of [email protected] and [email protected] over 20 iterations in Figure 3. We can observe that LSTM-offline performs worse than all RL methods, especially in the later stage, due to its lack of exploration. PG-online improves slowly with a high variance, as it does not reuse the generated data. Compared with PG-online&offline, IRecGAN has better convergence and coverage because of its reduced value estimation bias. We also find that [email protected] is harder to improve. The key reason is that as the model identifies the items with high rewards, it tends to recommend them more often; this gives those less relevant items less chance to be explored, which is in a similar situation to our online evaluation experiments under πmax and πmix. Our model-based RL training alleviates this bias to a certain extend by generating more training sequences, but it cannot totally alleviate it. This reminds us to focus on explore-exploit trade-off in model-based RL in our future work.

7.2 Real-world Offline Test

We also use a large-scale real-world recommendation dataset from CIKM Cup 2016 to evaluate the effectiveness of our proposed solution for offline reranking. We filtered out sessions of length 1 or longer than 40 and items that have never been clicked. We selected the top 40,000 most popular items to construct our recommendation candidate set. We randomly selected 65,284/1,718/1,820 sessions for training/validation/testing purposes, where the average length of sessions is 2.81/2.80/2.77 respectively. The percentage of recorded recommendations that lead to a purchase is 2.31%/2.46%/2.45%. We followed the same setting as in our simulation-based study in this experiment.

Baselines In addition to the baselines we compared in our simulation based study, we also include the following state-of-the-art solutions for recommendation: 1). PGIS: the agent model estimated with importance sampling on offline data to reduce bias; 2). AC: an LSTM model whose setting is the same as our agent model but trained with actor-critic algorithm lillicrap2015continuous to reduce variance; 3). PGU: the agent model trained using offline and generated data, without adversarial training; 4). ACU: AC model trained with both offline and generated data, without adversarial training.

Evaluation Metrics All the models were applied to rerank the given recommendation list at each step of testing sessions in offline data. We used [email protected] ([email protected] and [email protected]) to compare different models’ recommendation performance, where we define the clicked items as relevant. In addition, because the logged recommendation list was not ordered, we cannot assess the original logging policy’s performance in the offline data.

Table 1: Rerank evaluation on real-world recommendation dataset.
Model LSTM LSTMD PG PGIS AC PGU ACU IRecGAN
[email protected] (%) 32.89±0.50 33.42±0.40 33.28±0.71 28.13±0.45 31.93±0.17 34.12±0.52 32.43±0.22 35.06±0.48
[email protected] (%) 8.20±0.65 8.55±0.63 6.25±0.14 4.61±0.73 6.54±0.19 6.44±0.56 6.63± 0.29 6.79±0.44

Results

The results of the offline rerank evaluation are reported in Table 1. With the help of adversarial training, IRecGAN achieved encouraging improvement against all baselines. This verifies the effectiveness of our model-based reinforcement learning, especially its adversarial training strategy for utilizing the offline data with reduced bias. Specially, we compare the results of PG, PGIS, PGU, and IRecGAN. PGIS did not perform as well as PG partially because of the high variance introduced by importance sampling. PGU was able to fit the given data more accurately than PG since there are many items for recommendation and the collected data is limited. However, PGU performed worse than IRecGAN because of the biased user behavior model. And with the help of the discriminator, IRecGAN reduces the bias in the user behavior model to improve value estimation and better policy learning. This is also reflected on its improved user behavior model: LSTMD outperformed LSTM, given both of them are for user behavior modeling.

8 Conclusion

In this work, we developed a practical solution for utilizing offline data to build a model-based reinforcement learning agent for recommendation, with reduced model bias. We introduce adversarial training for joint user behavior model learning and policy update. Our theoretical analysis shows our solution’s promise in reducing bias; our empirical evaluations in both synthetic and real-world recommendation datasets verify the effectiveness of our solution. Several directions left open in our work, including balancing explore-exploit in policy learning with offline data, incorporating richer structures in user behavior modeling, and exploring the applicability of our solution in other off-policy learning scenarios, such as conversational systems.

References

Appendix

1   Details of Discriminator Model

We adopt an RNN-based discriminator 𝒟 for our IRecGAN framework, and model its hidden states by 𝐬td=hd(𝐬t-1d,𝐞t-1d), where 𝐬td denotes the hidden states maintained by the discriminator at time t and 𝐞t-1d is the embeddings used in the discriminator side. And we add a multi-layer perceptron which takes as input the hidden states to compute a score through a Sigmoid layer indicating whether the trajectory looks like being generated by real users as follows:

D(τ0:T) =Sigmoid[1Tt=0T𝐞d(catmax)𝐞d(ct)(Wprt+bp)]
catmax =argmaxcat(𝐖d𝐬td+𝐛d)𝐞(c)

where catmax can be seen as the user’s favorite item of the given at, and should be as close to ct as possible for real user. To ensure the gradient backpropagation, we use Softmax with a temperature 0.1 to approximate the argmax function. Other hyper parameters are set the same with the experiment setting depicted in section 7.1. The optimization target of 𝒟 is formulated as in Eq (5).

2   Algorithm

\SetAlgoLined\KwInOffline data; an agent model 𝒜; a user behavior model 𝒰; a discriminator 𝒟. Initialize an empty simulated sequences set Bs and a real sequences set Br. Initialize 𝒰,𝒜 and 𝒟 with random parameters. Pre-train 𝒰 by maximizing Eq (3). Pre-train 𝒜 via the policy gradient of Eq (10) using only the offline data. 𝒜 and 𝒰 simulate m sequences and add them to Bs. Add m trajectories to real data set Br. Pre-train 𝒟 according to Eq (5) using Br and Bs.
\Fore1 \KwToepoch \Forr-steps Empty Bs and then generate m simulated sequences and add to Bs. Compute q𝒟(τ0:t) at each step t by Eq (6). Extract λ2λ1m sequences into Br. Update U via the policy gradient of Eq (7) with B=[Bs,Br]. Update A via the policy gradient of Eq (10) with B=[Bs,Br]. \Ford-steps Empty Bs, then generate m simulated sequences by current 𝒰, 𝒜 and add to Bs. Empty Br and add m sequences from the offline data. Update 𝒟 according to Eq (5) for i epochs using Br and Bs.
\algorithmcfname 1 IRecGAN