Locality-Sensitive Experience Replay for Online Recommendation

Online Recommendation aims to find a solution that best reflects real-time interactions between users and the recommender system and apply the solution to the recommendation policy. The system needs to analyze users’ behaviors and update the recommend policy dynamically. In particular, reinforcement learning-based recommendation learns from interactions through a Markov Decision Process (MDP).

Given a recommendation problem consisting of a set of users $\mathcal{U}=\{u_{0},u_{1},\cdots u_{n}\}$, a set of items $\mathcal{I}=\{i_{0},i_{1},\cdots i_{m}\}$ and user’s demographic information $\mathcal{D}=\{d_{0},d_{1},\cdots,d_{n}\}$, MDP can be represented as a tuple $(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$, where $\mathcal{S}$ denotes the state space (i.e., the combination of the subsets of $\mathcal{I}$ and its corresponding user information) $\mathcal{A}$ denotes the action space, which represents agent’s selection during recommendation based on the state space $\mathcal{S}$, $\mathcal{P}$ denotes the set of transition probabilities for state transfer based on the action received, $\mathcal{R}$ is a set of rewards received from users, which are used to evaluate the action taken by the recommender system (each reward is a binary value to indicate whether user has clicked the recommended item or not), and $\gamma$ is a discount factor $\gamma\in[0,1]$ for the trade-off between future and current rewards.

Given a user $u$ and an initial state $s_{0}$ observed by the agent (or the recommender system), which includes a subset of item set $\mathcal{I}$ and user’s profile information $d_{0}$, a typical recommendation iteration for the user goes as follows: first, the agent takes an action $a_{0}$ based on the recommend policy $\pi_{0}$ under the observed state $s_{0}$ and receives the corresponding reward $r_{0}$—the reward $r_{0}$ is the numerical representation for user’s behavior such as click through or not; then, the agent generates a new policy $\pi_{1}$ based on the received reward $r_{0}$ and determines the new state $s_{1}$ based on the probability distribution $p(s_{\textit{new}}|s_{0},a_{0})\in\mathcal{P}$. The cumulative reward (denoted by $r_{c}$) after $k$ iterations from the initial state is as follows:

DRL-based recommender systems uses a replay buffer to store and replay old experience for training. Given the large state and action space in a recommender system, not every experiences are worth to replay (Chen et al., 2021)—replaying experience that does not contain useful information will increase the training time significantly and introduce extra uncertainty to convergence. Hence, it is reasonable to prioritize replay important experience for DRL recommender systems.

The ideal criterion for measuring the importance of a transition in RL is the amount of knowledge learnable from the transition in its current state  (Schaul et al., 2016; Horgan et al., 2018). State-of-the-art methods like AER are unsuitable for recommendation tasks that contain large, higher dimensional state and action spaces as their sampling strategies may not work properly. Thus, we propose a new experience replay method named Locality-sensitive experience replay (LSER) for online recommendation, which uses hashing for dimension reduction when sampling and storing the experiences.

We formulate the storage and sampling issue in LSER as a similarity measure problem, where LSER stores similar states into the same buckets and samples similar experiences based on state similarities. A popular way of searching similar high-dimensional vectors in Euclidean space is Locality-Sensitive Hashing (LSH), which follows the idea of Approximate Nearest Neighbor (ANN) while allocating similar items into the same buckets to measure the similarity. However, standard LSH conducts bit-sampling on the Hamming space; it requires time-consuming transformation between the Euclidean space to the Hamming space, liable to lose information. Aiming at measuring the similarity between high-dimensional vectors without losing significant information, we propose using $p$-stable distribution (Nolan, 2003) to conduct dimensionality reduction while preserving the original distance. This converts high-dimensional vectors (states) into low-dimensional representations easier to be handled by the similarity measure.

To address possible hash collision (i.e., dissimilar features may be assigned into the same bucket and recognized as similar), we introduce the formal definition of the collision probability for LSH. Then, we theoretically analyze the collision probability for $p$-stable distribution to prove that our method has a reasonable boundary for collision probability.

Here, we use a 2-state distribution, i.e., normal distribution for dimension reduction. We randomly initialize $n_{h}$ hyperplanes based on normal distribution on the projective space $\mathcal{P}^{n}$ to get the hash representation for a given state $s$, where $n$ is the dimension of the state. The hashing representation $h(s)$ for the given state $s$ is calculated as follows:

The collision probability of the above method can be represented as:

Eq.(2) formulates the information loss during the projection, where we use term $e$ to represent the quantification between the real value $p\cdot v$ and hashed results induced from $h(\textbf{v})$. Since the relative positions in original space are preserved during the hash transformation with an extra measurement $e$, the upper bound and lower bound of collision probability boundary in projective space is guarantee to be intact. That means the more dissimilar states will not receive a higher probability to be allocated into the same hash result.

Note that, when calculating the lower and upper bounds, $q$ represents $\frac{t}{c+e}$ and $\frac{t}{c-e}$, respectively. The algorithm of LSER is shown in  Algorithm 1.

In the following, we demonstrate from two perspectives that LSER can find the similar states efficiency. First, we show the efficacy of LSER with theoretical guarantee, i.e., similar states can be sampled given the current state. We formulate ‘the sampling of similar states’ as a neighbor-finding problem in the projective space and provide a theoretical proof of the soundness of LSER. Given a set of states $\mathcal{S}$, and a query $q_{s}$, LSER can quickly find a state $s\in\mathcal{S}$ within distance $r_{2}$ or determine that $\mathcal{S}$ has no states within distance $r_{1}$. Based on existing work (Indyk and Motwani, 1998), the LSH family is $(r_{1},r_{2},p_{1},p_{2})$-sensitive, i.e., we can find a distribution $\mathcal{H}$ such that $p_{1}\geq Pr_{h\sim\mathcal{H}}[h_{ab}(\textbf{u})=h_{ab}(\textbf{v})]$ when u and v are similar and $p_{2}\leq Pr_{h\sim\mathcal{H}}[h_{ab}(\textbf{u})=h_{ab}(\textbf{v})]$ when u and v are dissimilar.

Existing experience replay methods in DRL research assume that the recent experience is more informative than older experience. Therefore, they simply replace the oldest experience with the newest experience to update the experience buffer in DRL-based recomender systems without further optimization. As such, some valuable experience might be discarded, i.e., catastrophic forgetting. In contrast, we design a state-aware reward-driven experience storage strategy, which removes the experience with the lowest reward—instead of following the First-In-First-Out (FIFO) strategy—when the replay buffer is full. Formally speaking, a transition $\tau_{t}:(s_{t},a_{t},s_{t+1},r_{t})$ will be stored in the replay buffer based on the value $h_{p\in\mathcal{P}^{n}}(\tau_{t}.s_{t})$. If the replay buffer is full, the transition with the same value of $h_{p\in\mathcal{P}^{n}}(\tau_{t}.s_{t})$ but lower reward will be replaced. In practice, an indicator $m_{t}$ is stored in the transition as well to indicate when the recommendation should terminate.

Sampling strategy is another crucial component of LSER, which determines which experience should be selected for the agent to optimize in LSER. We propose a state-aware reward-driven sampling strategy that only replays the experience with the top-N highest rewards in the same hashing area; this way, the agent can quickly find the correct direction for optimization. We call our sampling strategy ‘state-aware’ because we use a hash key to encode the state and replay the experience based on the hash key. Compared with uniform sampling, our strategy has a higher chance to replay the correct experience. Here, we illustrate how to address three related challenges faced by our sampling strategy: exploitation-vs-exploration dilemma, bias annealing and non-existence dilemma.

We use Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al., 2015) as the training backbone. We choose an actor-critic network as the agent and train two parts of the actor-critic network simultaneously. The critic network aims to minimize the following loss function:

where $\theta_{\psi}$ and $\theta_{\phi}$ are the critic and actor parameters, $N$ is the size of the mini-batch from the replay buffer, $\psi_{\theta_{\psi}^{\prime}}$ and $\phi_{\theta_{\phi}^{\prime}}$ are the target critic and target actor network, respectively. We apply the Ornstein-Uhlenbeck process in the action space to introduce perturbation; this encourages the agent to explore. The target network will be updated based on the corresponding hyper-parameter $\tau$.

We conduct experiments on three widely used public simulation platforms: VirtualTB (Shi et al., 2019), RecSim (Ie et al., 2019) and RecoGym (Rohde et al., 2018), which mimic online recommendations in real-world applications.

Considering RecoGym and RecSim have limited data points and do not consider users’ dynamic interests, we select VirtualTB as the main platform for evaluations. Our model is implemented in Pytorch (Paszke et al., 2019) and all experiments are conducted on a server with two Intel Xeon CPU E5-2697 v2 CPUs with 6 NVIDIA TITAN X Pascal GPUs, 2 NVIDIA TITAN RTX and 768 GB memory. We use two two-hidden-layer neural networks with 128 hidden unit as the actor network and the critic network, respectively. $\tau$, $\gamma$, and $c$ are set to $0.001$, $0.99$ and $1e^{6}$, respectively, during experiments.

The evaluation metrics are environment-specific. For VirtualTB and RecoGym, click-through rate is used as the main evaluation metric. For RecSim, we use the built-in metric, which is a quality score, as the main evaluation metric. We compare our method with the following baselines.

• •

  Prioritized Experience Replay (PER) (Schaul et al., 2016): an experience replay method for discrete control, which uses TD-error to rank experience and a re-weighting method to conduct the bias annealing.

• •

  Dynamic Experience Replay (DER) (Luo and Li, 2020): an experience replay method designed for imitation learning, where stores both human demonstrations and previous experience. Those experiences are selected randomly without any priority.

• •

  Attentive Experience Replay (AER) (Sun et al., 2020): an experience replay method that uses attention to calculate the similarly for boosting sample efficiency with PER.

• •

  Selective Experience Replay (SER) (Isele and Cosgun, 2018): an experience replay method for lifelong machine learning, which employs LSTM as the experience buffer and selectively stores experience.

• •

  Hindsight Experience Replay (HER) (Andrychowicz et al., 2017): an experience replay method that replays two experience (one successful, one unsuccessful) each time.

For AER, PER, SER and HER, We use the same training strategy as LSER. For DER, we use its original structure to run experiments without human demonstrations. The size of the replay buffer is set to $1,000,000$ for VirtualTB and $10,000$ for RecSim and RecoGym. The number of episodes for our experiments is set to $90,000$ for VirtualTB and $1,000$ for RecSim and RecoGym. Note that only PER, AER and SER contains a prioritize operation to rank or store the experience.

Results for the three platforms (Fig 3) demonstrate our method (LSER) outperformed the baselines: LSER yields significant improvements on VirtualTB, which is a large and sparse environment; while AER, DER, PER and SER find a correct policy within around $50,000$ episodes, ours takes around $30,000$ episodes; HER does not perform well because it introduces too much failed experience and has a slow learning process; DER introduces the human demonstration into the vanilla ER which is hard to acquire for recommendation task.

Applying PER to DDPG slightly outperforms applying DER to DDPG, which is consistent with observations by previous work (Novati and Koumoutsakos, 2019; Sun et al., 2020). As PER was originally designed for Deep Q-learning, it uses the high TD-error to indicate the high informative experience for the value-network. When applying PER into DDPG, which is an actor-critic based algorithm, the sampled experience is also used to update the policy network. Those experiences with high TD-error normally diverge far away from the current policy and harm the updates of the policy-network. In contrast, LSER selects experience according to the similary with the current state. This preference for on-distribution states tends to discard experiences that contain old states and stabilize the training process of the policy network. AER does not perform as well as PER in VirtualTB because it heavily relies on the attention mechanism to calculate the similarity score between states. LSER’s $\epsilon$-greedy method can enforce agent to do more exploration when user’s interest shift.

All methods gained similar results on RecSim and RecoGym because all methods can iterate all possible combinations of states and actions. Fig. 3(b), 3(c) and 3(d) show that LSER is slightly better and more stable than the baselines on RecSim and RecoGym. Since the two platforms are quite small¹¹1RecoGym only contains 100 users and 10 products; RecSim contains 100 users and 20 products., similarity matching and $\epsilon$-greedy do not significantly improve performance.

We report the running time of the selected experience replay methods in Table 1 to evaluate the efficiency of LSER. LSER outperforms all While performing poorly on RecSim and RecoGym, it is faster than most of the baselines. In comparison, LSER introduces extra running time in small environments (e.g, RecSim and RecoGym) than large environments. For VirutalTB, AER takes much longer time than all other methods, due to attention calculation (Kitaev et al., 2020).

We further investigate the effect of LSER’s store and sampling strategy by replacing our store strategy with the normal strategy and our sampling strategy with random sampling. The results of our ablation study are shown in Fig. 3(f), where LSER-P denotes LSER with the replaced store strategy and LSER-S denotes the LSER with the replaced sampling strategy. We found the sample strategy played the most critical role in achieving good performance, as LSER-S underperformed LSER significantly. The store strategy also contributed to the better performance. LSER-P was less stable (indicated by a wider error bar). but outperformed LSER at $\sim 30,000$ episodes, due to occurrence of sub-optimal policies.

In our method, the number of hyperplanes is critical to determine the length of the result hash-bits of a given state. Longer hash-bits can provide more accurate similarity measurement result but low efficiency, while shorter hash-bits can increase efficiency but decrease the accuracy. It’s a trade-off which needs a middle-point to balance between efficiency and accuracy. We want to answer the following question:“Does increase the hyperplanes always boost the recommendation performance?” and find out the optimal number.

We report the experimental results in VirtualTB, where we evaluate the effect by varying number hyperplanes in LSER (shown in Fig 4). The results on the other two platforms show the similar pattern.

The performance gradually increases with more hyperplanes, but it levels off or even drops when number of hyperplanes reaches 20.

Fig 3(a) shows LSER suffers instability after reaching the first peak at episode $\sim 50,000$. Different from the other methods, LSER can quickly reach the optimal policy but suffers fluctuation. That indicates $\epsilon$-greedy tends to lead the agent towards learning from low-priority experience after the optimal policy is reached. We alleviate the issue by adjusting the value of $\epsilon$. Here, we tried $\epsilon=\{0,0.9,0.99,1\}$ to determine the best choice of the $\epsilon$ on VirtualTB. The results are shown in Fig. 3(e), where $\epsilon=1$ corresponds to greedy sampling while $\epsilon=0$ refers to randomly sampling. Besides, we provide an intervention strategy to stabilize the training process—the agent will stop exploration once the test reward is higher than a reward threshold $T_{r}$. This strategy allows the agent to find an near-optimal policy at an early stage. We examined the performance under $T_{r}$=0.95, which delivers a better training process.