# Efficient Tree Policy with Attention-Based State Representation for Interactive Recommendation
## 3 Method
### Efficient Tree-Structured Policy  
Most of the value-based RL methods are not efficient, since they involve maximization over the action spaces, which are often very large. In contrast, policy gradient methods are more efficient in solving IRS tasks. The reason is that, in policy gradient methods, policies are represented with the state as the input and the action probabilities as the output. Unfortunately, learning such a policy network with a large number of output dimensions is always time costly since the softmax output layer requires explicit normalization over the actions [5]. Representing the output layer of the policy network with the tree-structured network can substantially reduce the computation cost in learning and evaluation, such as hierarchical softmax [44] and TPGR [5]. For TPGR, the policy network is represented by a tree-structured neural network, with each leaf node representing the output probability of the corresponding item and each none-leaf node outputs a probability for selecting the node in the below layer. The output probability of each item is calculated by multiplying the probabilities on the traversing path. One major drawback is that the computation of the probability to recommend each candidate item requires specifying the path from the root node to the corresponding leaf in the tree. Traversing the tree always needs a loop to determine the nodes in each layer, which is quite inefficient in practice. Specifically, let us first take a look at the tree structure of policy in TPGR. Denoting \(M\) as the total item number and \(c\) as the child number for each node, then based on the balanced clustering algorithm, TPGR obtains a tree-structured policy with items arranged into \(floor(M/c)\) clusters. Here, \(floor(x)\) returns the largestinteger which is no less than \(x\). Among those clusters, we have \((M\mod c)\) clusters that contains \(c+1\) items, and \((floor(M/c)-M\mod c)\) clusters that contains \(c\) items. Since the item number for each cluster denotes the output dimension for each node in the final layer of the tree policy, such distribution of items in the leaf node requires layer-to-layer traversing of the tree. As a consequence, indexing each item needs \(O(\log M)\) decision time. For IRS, calculating the top-K ranked items for both evaluation and recommendation is very common in practice. In this scenario, TPGR needs \(O(M\log M)\) decision time to obtain all the action probabilities and, finally, obtain the top-K ranked items. Such a computation method for calculating recommendation probability for candidate items lacks efficiency and is hard to parallelize. Therefore, deploying TPGR to real-world IRS is challenging. To address this challenging issue, we propose a novel complete tree to better represent the structure of the policy, as illustrated in Figure 3. In this framework, each non-leaf node of the policy tree receives the item feature list as input and contains two parts: the state representation model and a node policy network. The output of the leaf node denotes the recommendation probabilities of the corresponding items and is computed by traversing the tree from the root to this leaf. For each leaf node, clustering over items can also be used to assign similar items to one node, and thus, simplify learning. We will describe the clustering algorithm for the complete tree policy in the Appendix A.The property of a complete tree makes it easy to index each root node of the decision path. If we store each node of the tree policy in an array, given an item index \(I\), the indices of the tree node from bottom to top can be obtained as \(<I/c,I/c^{2},I/c^{3},\ldots,1>\). Therefore, we can then compute all the item recommendation probabilities based on a few simple matrix computations. Algorithm 1 illustrates the computation of item recommendation probability based on the complete tree policy. Based on this algorithm, we can then obtain all the item recommendation probabilities in \(O(\log M)\) decision time.