# Efficient Tree Policy with Attention-Based State Representation for Interactive Recommendation
## 1 Introduction  
With the prosperous development of information technology, nowadays, interactive recommender systems (IRS) play an important role in personalized services to help us discover information and satisfy our needs. TikTok's personalized video recommendations (http:www.tiktok.com, accessed on 10 April 2023), Spotify's music recommendation (http:www.spotify.com, accessed on 10 April 2023), and Amazon's product recommendation (http:www.amazon.com, accessed on 10 April 2023) are a few examples of how they have become an indispensable part in our daily lives [1; 2; 3]. Different from conventional recommendation systems, an IRS suggests items based on user behavior and consecutively refines the recommendations based on users' feedback [4; 5]. Due to the interactive nature of such recommendation settings, IRS should be able to capture the dynamic preference of users' behavior and perform planning to optimize long-term performance. Conventional recommendation methods such as matrix factorization, content-based filtering, and learning-to-rank regard the recommendation process as a static one and fail to capture thedynamic preferences of users. Furthermore, most of the conventional methods recommend items that can achieve immediate satisfaction of users, while ignoring those items that may lead to more profitable rewards in the future [6; 7; 8]. Recently, reinforcement learning (RL) [9] has shown great potential in modeling dynamic interaction behaviors and pursuing long-term rewards [10; 11]. Naturally, as a promising method, RL has been introduced into IRS to solve the aforementioned particular challenges [12; 13; 14; 15]. Typically, an RL-based IRS provides recommendations to users in an interactive way: each time, the IRS recommends a series of items to the user and the user browses these items and provides feedback; then, IRS refines the recommendation strategy and suggests new items depending on the feedback. The state modeling, which is frequently based on the users' historical behaviors, is an important part of the RL agent. Existing state representation works for IRS generally adopted unidirectional recurrent neural networks (RNN) to model the states, and encoded the states with the hidden representation of the RNN model. Such works can be found in [5; 6; 13; 16; 17]. However, real-world data are usually noisy and do not rigidly follow left-to-right orders [18; 19]. The long sequence of user historical records always contains items that are irrelevant to users' future choices, which refers to noisy patterns [20; 21]. For example, consider the user's action sequence in Figure 1. Based on their historical choices, we can infer that they are probably a science fiction fan. Besides, they may also watch some movies that are newly released or suggested by friends, as depicted in timesteps 4 and 5. In the IRS setting, the RL agent obtains the user ratings 4 and 5 at timesteps 4 and 5 with the two irrelevant items, respectively. The unidirectional RNN state representation model may be confused by the two ratings and may ignore the fact that they are a science fiction fan. This situation may be aggravated with the increase of the sequence length, as the noisy patterns vary. Some works adopted attention-based methods [4; 22] to address this issue. For example, DRR-att [4] adopts an attentive network to deal with noisy dependencies. However, DRR-att directly inputs the item vector to the attentive networks and ignores the feedback from users, which makes it difficult for dealing with long sequence data. Therefore, it is essential to design a state encoder that can handle the long and noisy sequence in real-world IRS. Furthermore, adopting RL methods for a recommendation scenario with vast discrete action space is challenging, because the IRS often contains millions of items. Factoring the large discrete action space into a considerably smaller one is an obvious solution.