Building Personalized Simulator for Interactive Search

1 Introduction

Online shopping platforms, such as Amazon, Taobao, and eBay, have dramatically changed people's living style. The volume of products on these platforms has grown tremendously in recent years, which escalate the need for personalized products recommendation. Extensive machine learning algorithms have been studied [Li et al., 2011; Clark, 2015; Yin et al., 2016; Liu et al., 2017] for automatic product retrieval and recommendation. However, existing research tends to treat the problem as a static one without modeling interactions with users. The shopping process in complicated because users might not be certain with their need in the beginning, therefore, a single-step solution might not be enough to meet users' requirement. In order to improve the shopping experience and help users identify their need quickly, interactive search is emerging. An illustration of interactive search can be seen in Figure 1. At each turn, the system presents a set of tags related to the product together with search results based on user queries. A user can either type new keywords or click any tag provided to update the request. Based on users' feedback, a new set of ranked products and tags would be returned.

∗Corresponding Author: zywei@fudan.edu.cn

It usually involves several steps for users to identify their need. Therefore, interactive search can be naturally formulated as a sequential decision problem. Recently, researchers have explored to utilize Reinforcement Learning (RL) based agent for product recommendation and information retrieval [Taghipour and Kardan, 2008; Zhao et al., 2018; Zheng et al., 2018; Choi et al., 2018]. The training of these models can be divided into two stages, namely, online and offline. Existing research usually trains the model in a supervised fashion offline based on historical data while the online learning is performed by interacting with real users via RL algorithms. Though promising results have been reported, the optimization objectives of offline training and online learning are different, which leads to a cold-start problem for the online usage of the agent. In order to address this issue, we propose to design a simulator to interact with the agent for its offline training.

Designing an environment simulator for online shopping platform is challenging for two reasons. First, different users have different preferences. Second, the labeled data for the offline training is usually limited. How to train the agent efficiently becomes a problem. In order to tackle these two challenges, we introduce a personalized, model-based environment simulator, which takes the users' profiles into consideration when mimicking the behavior of real users. In summary, our contribution is three-fold:

• We propose to employ an environment simulator for the offline training of the agent in interactive search.
• We propose a multi-task learning approach to model personalized user preferences based on real user profiles. Besides, we utilize a model-based RL algorithm to make full use of limited labeled data.
• Experimental results on a real-world dataset show the effectiveness of our simulator. By estimating the state transition probability, the collected dataset can be used efficiently via our simulator and the agent converges faster.

2 Task Formulation

2.1 Task

In interactive search (Figure 1), a search session is initialized by a user with his/her first query. At each turn t, the agent returns a set of ranked products (lower part) based on query qt. Meanwhile, the agent receives a set of candidate tags Tt = {t1, · · · , tntt }1 , where ntt is the number of candidate tags at turn t, and a subset of K (where K ≤ |Tt|) ranked tags (middle part) are recommended to help user search desired products. If the displayed products cannot meet the user's demand , the user can either click on one of the displayed tags or type keywords to update his/her query for a better search result. Here are some notations used in this paper:

• User u. To model different preferences of users, each user is represented as a vector u ∈ U with three features, i.e., the age, gender and purchase power.
• Query q. Each query is represented as a sequence of words q = (w1, · · · ,wnq) ∈ Q, where wi is the i-th word in q and nq is the number of words in q.
• Tag t. Each tag t = (w1, · · · ,wnt) is also a sequence of words, where nt is the number of words in tag t.

2.2 MDP Formulation

We cast this problem as a Markov Decision Process (MDP) from the agent's perspective. An MDP consists of a tuple of five elements (S, A, R, P, γ) which are defined as follows:

1 In this work, candidate tags are derived from logs via information retrieval based methods, and tag generation is not concerned.

State space S. A state st = (u, qt) ∈ S, where u ∈ U is the user who initialized this session and qt is the query at turn t. After the user clicks on a tag or types several new keywords, the state will be updated to st+1 = (u, qt+1), where the qt+1 is updated by appending the new keywords or the words of the clicked tag to qt.

Action space A. At turn t, an action at = (t1t , · · · , tKt ) ∈ A(st) is a sequence of K tags displayed to the user at turn t. Given a set of candidate tags Tt at turn t, the action space A(st) is the set of all permutations of K tags chosen from Tt.

Reward R. After the agent takes an action at given a state st, i.e., displaying a sequence of tags to the user, the user can click one of the tags or type in several keywords. The agent will receive an immediate reward rt = R(st, at) according to the feedback of the user u.

Transition probability P. p(st+1|st, at) is the probability of state transition from st to st+1 after the agent takes an action at at state st.

Discount factor γ. γ ∈ [0, 1] defines the discount factor when we measure the present value of future reward.

In RL, the policy π describes the behavior of an agent, which takes the state st as input and outputs the probability distribution over all possible actions π(at|st), ∀at ∈ A(st). The agent can be trained via RL-based algorithms, where its goal is to find an optimal policy π which maximizes the discounted cumulative reward.

3 Environment Simulator

In our task, there are three tasks that the environment needs to consider at each turn, i.e., returning a feedback to the agent, terminating or continuing the current session and transiting to a new state. Our simulator is thus designed as Figure 2 that combines three sub-tasks:

• Click: This sub-task predicts whether one of displayed tags will be clicked by the real user or not. According to the predicted result, the immediate reward will be returned to the agent.
• Terminate: This sub-task decides to terminate or continue this current search session.
• Transition: At each turn, the state will transit to a new state and this sub-task models the transitions between states.

As shown in Figure 2, the lower layers are shared across all three tasks, while the top layers are task-specific.

Shared layer. At each turn, the simulator takes the state s = (u, q) and last agent action a = (t1 , · · · , tK ) ∈ A(s) as input. Considering that the query q and all tags are a sequence of words respectively, we first use a bidirectional LSTM to encode the query and tags. Then, the order information between tags in action a is also important, so another bidirectional LSTM is employed to extract the order information between tags. The user u, query q and action a are encoded as hs,u , hs,q and hs,a via a shared layer of our simulator.

Task-specific layer. The task-specific layer of each subtask is a two fully connected layers with LeakyReLU as activation function. It takes hs,s = [hs,u , hs,q , hs,a ] as input and outputs the result of corresponding sub-task. Considering that all the three sub-tasks are classification problems, we use cross entropy as the loss function for all the three sub-tasks. Now, we can write the total loss function of our simulator as:

where Lsclick (θs ), Lstrmt (θs ) and Lstrt (θs ) are the losses of clicking, terminating and transition sub-tasks respectively.

Transition Probability Approximation

In order to use the collected data efficiently, we approximate the transition probability matrix of states. Inspired by Serban et al. [2018], rather than estimating the full transition probability p(s′ |s, a) directly, we approximate it with:

where u is the user that interacts with the agent in current session, and Z is a discrete abstract query space which meets the condition of |Z| ≪ |Q|. In other word, we estimate a userspecific transition probability matrix for each user u. In this way, the size of original transition probability matrix |A||S|2 , where |S| = |U||Q|, will be reduced to |A||U||Q|2 . Further more, by introducing the abstract query space Z, it will be further reduced to |U|(|A||Q||Z| + |Q||Z|). After the above two steps, the sample complexity for accurately estimating the transition probability will be reduced greatly.

The transition is illustrated in Figure 3. Given a user u, a state st = (u, qt) is sampled with the probability puabs (qt|zt) conditioned on an abstract query zt ∈ Z. Then the agent takes an action at ∈ A(st) according to it's policy π and receives the immediate reward rt from the environment. Conditioned on the query qt and action at, the next abstract query zt+1 is sampled with the probability puabs (zt+1|qt, at).

Algorithm 1: Building real experience buffer with abstract query.

input : fq→z(q),D = {(u, q, a, r, q′ , trmt)i}∣∣Ni=1 . output: Dr , Du ,Du z , ∀ z ∈ Z, ∀u ∈ U. 1 initialize Dr , Du , Du z , ∀z ∈ Z, ∀u ∈ U as empty set; 2 for i ← 1 to N do 3 get i-th transition (u, q, a, r, q′ , trmt) from Dr and s = (u, q), s′ = (u, q′ ); 4 z ← fq→z(q); 5 z′ ← fq→z(q′ ); 6 append (s, z, a, r, s′ , z′ , trmt) to Dr , Du , Du z respectively; 7 end

The transition distribution of z is approximated via transition sub-task of our simulator, i.e., puabs (zt+1|qt, at) ≈ ˆ pabs(zt+1|u, qt, at; θs ) = ˆ pabs(zt+1|st, at; θs ). In terms of the transition from zt to qt with the probability puabs (qt|zt), we just sample a q as qt uniformly from the pre-built buffer Du zt (see Algorithm 1), where fq→z is a known surjective function mapping from Q to Z. And this will lead to:

4 RL-based Agent

In our scenario, an action at = (t1t , · · · , tKt ) ∈ A(st) is a sequence of K tags (or sub-actions), and the number of candidate tags Tt is varying at different turns. This makes A(st) a discrete dynamic combinatorial action space. Thus, the traditional architecture of DQN that takes the state as input and outputs Q-values for each action at the output layer, is not suitable for this problem. We consider another architecture of Q-learning, named DRRN [He et al., 2016], which takes the pair of state s and action a as input and outputs the Qvalue for this pair. The architecture of our agent is similar to the shared layer of our environment simulator. The user u, query q and action a are encoded as ha,u , ha,q and ha,a respectively. Then ha,u , ha,q and ha,a are concatenated as ha . ha is then fed into a two fully connected layers to calculate the Q-value for the pair of the state and the action a.

Given a set of transitions D = {(s, a, r, s′ , trmt)i}|Ni=1 (trmt indicates whether the state s is a terminal state or not), the objective function is as follows:

where:

where Q(s, a; θa- ) is the target network with parameter θafrom some previous iteration.

The rollout simulation between the simulator and agent is described in Algorithm 2. Given a state s, the ϵ-greedy agent takes an action a = maxa∈A(s) Q(s, a; θa ) with probability

Algorithm 2: Rollout Simulation

1-ϵ and takes an action a ∈ A(s) randomly with probability ϵ. The training procedure of our agent and simulator is described in Algorithm 3. The simulator is pre-trained to minimize the total loss via supervised learning firstly (line 3) and then minimize the losses of three sub-tasks respectively (line 4). At each step, the agent is first trained with real experience replay (line 8). Then, the agent interacts with the simulator (line 9) and simulated experience replay is performed on the simulated experiences buffer (line 11).

5 Experiments

5.1 Dataset and Abstract Query

Our dataset is derived from the log of Taobao APP 2 , which is processed into transition tuple, i.e., (s, a, r, s′ , trmt). The user feature u ∈ R9 is the concatenation of three one-hot vectors, namely, age (3 categories), gender (3 categories including null value) and purchase power (3 categories). And the data distribution is shown in Figure 4. For a transition, if a user clicked on one of the recommended tags, the reward r = 1, otherwise r = 0. We have 17, 979 transitions with

2 The largest E-commerce platform in China.

Algorithm 3: Training Algorithm

• input : D, fs→z(s), T,N s ,C,m output: Agent(s; θa) 1 build Dr , Du , Du z , ∀ z ∈ Z, ∀u ∈ U with Algorithm 1; 2 initialize Agent(s; θa), Agent(s; θa-), Simulator(s, a; θs) randomly; 3 pre-train the Simulator(s, a; θs) with Dr via supervised learning to minimize Eq. 1; 4 pre-train the Simulator(s, a; θs) with Dr via supervised learning to minimize Lsclick(θs ), Lstrmt(θs ) and Lstrt(θs ) respectively; // parameters in shared layers keep fixed 5 initialize the simulated experience buffer Ds (fixed length) via Algorithm 2; 6 for i ← 1 to∞do 7 get m minibatches from Dr ; 8 update θa with m minibatches to minimize Eq. 4; 9 rollout simulation and update Ds with Algorithm 2; 10 sample m minibatches from Ds ; 11 update θa with m minibatches to minimize Eq. 4; 12 reset θa- = θa every C steps; 13 if θa are converged then break; 14 end

r = 1. However, in terms of transitions with r = 0, we cannot say that the action a derived from the log is bad because it is very likely that no click was made by the user in real world even the action is optimal. In order to reduce the noisy, only 17, 980 transitions with r = 0 sampled randomly are used.

As for abstract query Z, we first represent q as the average vector of words in q, then K-means is performed on these average vectors to assigns a cluster id for each q (20 clusters). Considering the null value of query q, we have |Z| = 20 + 1 = 21. Thus, the mapping function fq→z(q) is getting the cluster id of query q.

5.2 Experiment Setup

Implementation Details. The simulator is pre-trained before interacting with our agent and fixed unchanged while interacting with the agent. Each word is represented by word embedding (200-dim) trained on the historical queries from other scenarios of Taobao APP (∼12.7 million queries, 332,922 words) via word2vec. ϵ = 0.2, γ = 0.9,m = 5,N s = 5, T = 20, learning rate is set to 10-5 and 10-3 for the training of environment simulator and agent respectively. At each turn, the agent recommends 3 tags to the user

(i.e., K = 3). The target network of the agent is updated every 200 steps. The hidden size (both bidirectional LSTM and fully connected layers) of simulator and agent is 5 and 10. The length of simulated experiences buffer Ds is 1000.

Evaluation Metrics

We evaluate our agent for both offline and simulated online setting and compare it with different training modes. For offline evaluation, we treat the tag clicked by real user as the positive one. We borrow metrics from information retrieval, including Mean Average Precision at n (MAP@n), Normalized Discounted Cumulative Gain at n (NDCG@n) and Recall at n (Recall@n) 3 . Assuming that the number of the clicked tag is 1, we have MAP@1 = NDCG@1 = Recall@1 and only Recall is reported at position 1. It's worthy noting that only transitions with a clicked tag is used for offline evaluation.

For simulated online evaluation, we let agents trained to interact with our simulator. The metrics used include average cumulative reward and average number of turns per session. In the scenario of online shopping, it is better that users spend more time on the platform, so a larger average turn is preferred.

Baselines

We compare our model with some baselines:

• Random: Given a state s, the random agent always takes an action a ∈ A(s) randomly.
• DQN: The agent is trained with real experiences replay without interacting with the simulator (Algorithm 3 without lines 9-11).
• DQN-Sim: The agent is trained via interacting with the simulator only (Algorithm 3 without lines 7-5).
• DQN-Both: The agent is trained with both real experiences replay and the simulator (Algorithm 3).

At each training step, DQN-Both is updated with 2m batches (both real and simulated experiences), while both DQN and DQN-Sim are updated with m batches, i.e., real and simulated experiences respectively.

5.3 Experimental Results

In this section, we first compare our DQN agent with Random agent to evaluate the performance of our RL-based agents. Then, we compare the DQN agent with both DQN-Sim agent and DQN-Both agent to show that the training of the agent is converged faster and its performance is better with the assistance of the simulator.

Figure 5 shows the Recall of different agents at position 1, 2 and 3. We can see that all the RL-based agents outperform the random agent greatly on all metrics, which demonstrates the performance of our RL-based agents.

Table 2 shows the simulated online performance of different agents at training step = {4K, 10K}. As we can see, the two simulator-involved agents outperform the DQN agent in terms of both reward gained and number of turns lasted

3 Considering that there exists only one positive tag for one query (i.e., one transition), we use Recall@n rather than Precision at n (Recall@n=n×P@n in this work).

(the higher the better). At training step = 4K, the DQN-Both outperforms the two other agents. However, at training step = 10K, DQN-Sim agent reaches the best performance. The reason is that our environment simulator cannot mimic the behavior of real environment perfectly, which results in a dynamic environment for DQN-Both agent when replaying both real experiences and simulated experiences, making it difficult for DQN-Both agent to learn a optimal policy for both the real environment and simulated environment.

Table 3 shows the offline performance of different agents at training step = {2K, 4K, 10K}. At training step = 2K, 4K, both DQN-Sim agent and DQN-Both agent outperform DQN agent in a large margin. As the training continues, the gap between the DQN agent and the two simulator-involved agents is decreasing. The DQN-Sim agent, accessing the real data indirectly through our simulator, achieves comparable performance to DQN agent which indicates the effectiveness of our simulator.

More importantly, the DQN-Sim agent converges much faster than DQN agent during the training. We attribute this to the trade-off between exploration and exploitation. In other words, the real experiences buffer collected in advance is fixed during the training of the agents. Thus, the DQN agent is trained with a fixed buffer and there is no exploration of action space and state space. While the DQN-Both agent and DQN-Sim agent are trained via interacting with the simulator, during which they can have a better exploration.

We perform an experiment to reveal how the exploration can be enforced with the assistance of our simulator. We present the percentage of action space explored by the agent in terms of number of rollouts. When the number of rollouts equals to 1, it is the same as DQN with fixed real experiences. As shown in Table 4, we can see that only 3.9% of actions can be visited without experiences generated by the simulator. While the percentage of visited actions increases greatly when the simulator generated experiences are involved. The number increases with the number of rollouts.

Performance of environment simulator. The performance of our simulator on three sub-tasks are reported in Table 5. We use three metrics including recall, precision and F1 score.

6 RelatedWork

RL-based algorithms have been applied to different scenarios of recommendation. [Zhao et al., 2018] applies actor-critic algorithm to solve items recommendation involving the 2-D order between items in one page. [Zheng et al., 2018] integrates user behavior and profile information into state representation for online news recommendation with RL-based agent. [Choi et al., 2018] introduces an RL-based framework for recommendation where states are represented as grid-world obtained from bi-clustering to reduce the state space and action space. [Chen et al., 2018] employed stratified sampling and regret approximation to stabilize the learning of agent for recommendation.

To our knowledge, the agenda-based simulator [Schatzmann et al., 2007] is the first simulator for RL-based tasks, and have been widely applied in dialogue system [Wei et al., 2018; Li et al., 2017; Peng et al., 2017]. It is rule-based, where the handcrafted action space of environment simulator should be pre-defined and cannot be generalized to complex tasks (e.g., online shopping). From the perspectives of simulator and agent, the interacting process can both be treated as a sequential decision problem respectively. Thus, a simulator could be learned via inverse reinforcement learning based on experts' (users') demonstrations [Chandramohan et al., 2011]. What's more, the sequence-to-sequence architecture could also be employed to model the user simulator [Asri et al., 2016]. [Peng et al., 2018] propose a multi-task user simulator to interact with the agent. Instead of transiting into next state directly, it selects one of the pre-defined user actions and an additional state tracker is needed to update the state.

How to train the agent with collected data efficiently has attracted a lot of research. [Lu et al., 2018] introduce two approaches for data augmentation in task-completion tasks so that the agent could be trained more efficiently. Considering the model-based RL algorithms could learn a better policy from less data, state abstraction have been used to reduce the complexity of model-based RL methods [Serban et al., 2018; Jiang et al., 2015].

7 Conclusion and FutureWork

In this work, we introduce a multi-task model-based environment simulator for online shopping platform to train the RLbased agent via interactions. Experimental results on realworld dataset demonstrate that the agent can converge faster with the assistance of the simulator. Further analysis shows that agent is able to explore larger action space with experiences generated by the simulator. In future, we will explore to improve the performance of the simulator to provide a better simulation of the environment.

Acknowledgments

This work is partially funded by National Natural Science Foundation of China (No. 61751201), National Natural Science Foundation of China (No. 61702106) and Shanghai Science and Technology Commission (No. 17JC1420200, No. 17YF1427600 and No. 16JC1420401).