# Efficient Tree Policy with Attention-Based State Representation for Interactive Recommendation
## 2 Literature Review
### Dealing with Large Discrete Action Space in Reinforcement Learning  
Most RL methods become less effective when facing tasks with large discrete action spaces, as the search space of finding the optimal policies grows exponentially with the increase of actions. To address this problem, one common strategy is to reduce the large action spaces into a considerable one. For example, [PERSON] et al. [39] proposed a method that can first factorize the action space as negative free energies and then adopt an ensemble method to learn the policy. Similarly, [PERSON] et al. [40] proposed a method that represented each action in binary format and optimized a value function associated with each bit. [PERSON] et al. [41] showed that the performance of RL method can be improved when the action spaces are pre-categorized. Another popular method is to first map the large discrete action space to a smaller continuous action space and then select the discrete actions based on the similarity between continuous action spaces, such as DDPG-KNN [23] and Calca [16]. However, those methods are inefficient when mapping the actions, as the nearest neighbor search may be time costly. More recently, [PERSON] et al. [42] proposed a method that can learn the action representations during RL process, which can factorize the action space into a solvable level. Although this method is effective and scalable for solving tasks with large discrete action spaces, training such a model is inefficient, as it involves integral calculating over the probability distribution of actions. [PERSON] et al. [43] proposed DHCRS, a hierarchical RL method that adopted two DQN agents for addressing the large action space problem. DHCRS divided the items into categories and the high-level DQN agent selects a category and the low-level DQN agent recommends a certain item within this category. However, in practice, the amount of items in each category is not always equal, and adopting the same DQN agent for different categories may affect the overall efficiency in learning.  
Alternatively, designing specific neural networks to facilitate learning the tasks in large action space is another popular strategy. For instance, DRN [24] and DEERS [6] adopt a refined DQN [25] network to learn the policies with large action spaces. However, learning for DQN-based solutions involves a maximum operation among the actions, whose time complexity grows linearly with the number of actions. Moreover, [PERSON] et al. [16] adopted a deconvolution layer that maps the action space into a matrix. [PERSON] et al. [5] proposed TPGR, which uses a balanced tree-structured policy to simplify the policies with large action space, and thus, improves the efficiency in both learning and decision making. However, TPGR is less efficient when learning online. The parameters in TPGR policy networks grow exponentially with the depth of the tree. Backpropagating such a number of parameters is computationally costly when the depth of the tree-structured policy is large [44].  
In addition, when making decisions, TPGR needs to calculate the product of the probability of making each choice via each layer. This mechanism makes it inefficient when getting the top-K ranking actions, which is very common in IRS.