Source-linked AI summary
Large-scale Interactive Recommendation with Tree-structured Policy Gradient
Haokun Chen, Xinyi Dai, Han Cai, Weinan Zhang, Xuejian Wang, Ruiming Tang, Yuzhou Zhang, Yong Yu
TL;DR
Large item sets make existing RL methods inefficient for interactive recommendation, and continuous-action approaches can mismatch the executed discrete item. TPGR uses a balanced hierarchical tree and policy gradient to select items through root-to-leaf paths, with experiments showing superior performance and significant efficiency improvement over state-of-the-art methods.
Problem
Existing RL-based recommendation methods struggle with large discrete action spaces, while DDPG-based methods can suffer inconsistency between continuous actor outputs and executed discrete actions.
Method
TPGR builds a balanced hierarchical clustering tree over items and uses policy gradients to select recommendations through root-to-leaf paths.
Results
Experiments on environments based on two real-world datasets show superior recommendation performance and significant efficiency improvement over state-of-the-art methods.
Takeaways & Limitations
TPGR reduces action-selection complexity while explicitly modeling long-run rewards and sequential patterns for large-scale interactive recommendation.
Takeaways & Limitations
The tree design assumes balanced hierarchical clustering with a common child-count structure for non-leaf nodes, except near leaves.
Abstract
from arXiv · showhide
Reinforcement learning (RL) has recently been introduced to interactive recommender systems (IRS) because of its nature of learning from dynamic interactions and planning for long-run performance. As IRS is always with thousands of items to recommend (i.e., thousands of actions), most existing RL-based methods, however, fail to handle such a large discrete action space problem and thus become inefficient. The existing work that tries to deal with the large discrete action space problem by utilizing the deep deterministic policy gradient framework suffers from the inconsistency between the continuous action representation (the output of the actor network) and the real discrete action. To avoid such inconsistency and achieve high efficiency and recommendation effectiveness, in this paper, we propose a Tree-structured Policy Gradient Recommendation (TPGR) framework, where a balanced hierarchical clustering tree is built over the items and picking an item is formulated as seeking a path from the root to a certain leaf of the tree. Extensive experiments on carefully-designed environments based on two real-world datasets demonstrate that our model provides superior recommendation performance and significant efficiency improvement over state-of-the-art methods.
Introduction
Interactive recommender systems learn from sequential user feedback, motivating reinforcement learning for long-run planning; however, large item sets make common RL methods inefficient. TPGR addresses this with a tree-structured policy that improves efficiency and recommendation effectiveness.
- Interactive recommender systems repeatedly recommend items and receive user feedback, allowing their recommendation policies to be refined during interaction.
- Multi-armed bandit approaches model interaction but assume user preferences remain unchanged and do not explicitly plan for long-run performance.
- Reinforcement learning is suited to recommendation because it models dynamic interaction while planning for long-run performance.
- Existing DQN and DDPG methods become inefficient because selecting an item requires operations over the full action space, whose size is large in interactive recommendation.
- TPGR builds a balanced hierarchical tree over items, formulates recommendation as root-to-leaf path selection, and applies policy gradients to maximize long-run rewards.
- Experiments using environments based on two real-world datasets show superior performance and significant efficiency improvement over state-of-the-art methods.
Related Work and Background
RL-based recommendation explicitly models dynamic user status and long-run performance, but standard DQN and DDPG approaches scale linearly with the number of items. TPGR uses a balanced tree over the discrete action space to reduce decision complexity while avoiding continuous-to-discrete action inconsistency.
- RL-based Recommendation: RL-based recommendation formulates recommendation as a Markov Decision Process to model dynamic user status and plan for long-run performance.
- Large Discrete Action Space Problem in RL-based Recommendation: Most RL-based models become inefficient in interactive recommendation because decision-making time grows linearly with the discrete action-space size.
- Large Discrete Action Space Problem in RL-based Recommendation: DQN selects actions by evaluating Q(s, a) over the action space, requiring |A| evaluations and making learning and utilization intractable for large action spaces.
- Large Discrete Action Space Problem in RL-based Recommendation: DDPG-based methods also apply ranking functions over all items, so their action-sampling complexity grows linearly with |A|.
- Large Discrete Action Space Problem in RL-based Recommendation: The DDPG-based continuous-action approach can reduce decision complexity from O(|A|) to O(log(|A|)) for small k, but its actor may be trained using an action different from the executed discrete action.
- Large Discrete Action Space Problem in RL-based Recommendation: TPGR represents the discrete action space with a balanced tree and top-down leaf selection, reducing decision complexity to O(d×|A|1/d) while avoiding continuous-to-discrete mapping inconsistency.
Proposed Model
TPGR models interactive recommendation as an MDP and navigates a balanced item-clustering tree with policy networks to select recommendations through root-to-leaf paths. This design preserves discrete actions while reducing decision-making complexity relative to flat action selection.
- Problem Definition: TPGR models recommendation as an MDP whose states encode historical interactions, actions select items, rewards represent user feedback, and transitions follow new interactions.Episodes are fixed-length sequences of states, actions, rewards, and subsequent states.
- Tree Construction: A balanced hierarchical clustering tree organizes items into clusters, with each leaf mapped to an item and each non-leaf node associated with a policy network.The tree is constructed by repeatedly dividing item representations into balanced clusters with branching factor c.
- Recommendation Policy: Given a state, TPGR makes top-down decisions from the root to a leaf, representing the selected item’s probability as the product of the probabilities of its d path choices.Each path consists of d choices, each selecting one of at most c child nodes.
- Policy Optimization: REINFORCE trains the policy networks to maximize expected discounted cumulative rewards using sampled trajectories and empirical action-value estimates.The training procedure updates parameters with policy-gradient terms weighted by estimated discounted returns.
- Complexity: O(d × |A|^(1/d)) decision time replaces O(|A|) flat action sampling, while TPGR retains O(|A|) space complexity.With small constant depth d, each policy network uses O(c) time and space, and sampling requires d choices.
Experiments and Results
Experiments use MovieLens and Netflix data with an offline simulator that incorporates empirical and sequential rewards. TPGR outperforms comparison methods while reducing training and decision-making time, and its performance improves as the sequential-reward trade-off increases.
- Experimental setup: Experiments use MovieLens (10M) and Netflix datasets, with users split into 80% training and 20% test sets.Episodes have length 32, and repeated items are excluded within an episode.
- Data analysis: Figure 3 shows that average ratings increase with larger consecutive positive counts and decrease with larger consecutive negative counts.These patterns motivate modeling sequential effects in the recommendation process.
- Environment simulator: The simulator normalizes ratings to [−1, 1] and combines empirical rewards with sequential rewards controlled by α.The environment samples a user and interacts until the episode ends.
- Recommendation performance: TPGR outperforms all compared methods across datasets and α settings, with p-values less than 10−6 in most significance tests.The comparisons include conventional, MAB-based, and RL-based recommendation methods.
- Recommendation performance: As α increases, TPGR's average-reward improvement over HLinearUCB becomes more significant, indicating stronger capture of sequential patterns for long-run rewards.The result directly links the trade-off factor to sequential-reward modeling.
- Efficiency: TPGR consumes much less training and decision-making time than DQN-R and DDPG-R, while DDPG-KNN cannot jointly achieve high effectiveness and efficiency across k settings.TPGR also improves both effectiveness and efficiency relative to DDPG-KNN with k=0.1N.
Conclusion
TPGR reduces the complexity of large-scale interactive recommendation through balanced hierarchical clustering and models long-run rewards and sequential patterns. Experiments on a simulator based on two public datasets report better performance and higher efficiency than state-of-the-art models.
- TPGR uses balanced hierarchical clustering over the discrete action space to reduce RL-based recommendation time complexity.The framework targets scenarios with many items and represents the action space through a tree.
- TPGR explicitly models long-run rewards and captures sequential patterns to improve recommendation rewards over time.
- Experiments on a carefully designed simulator based on two public datasets show better performance and higher efficiency than state-of-the-art models.
- Future work includes deploying TPGR in an online commercial recommender system and exploring additional clustering-tree construction schemes.
Appendices
The appendices describe balanced clustering, complexity analysis, and reward mapping used by TPGR. The tree keeps each policy network's output size proportional to the cluster count while converting scalar rewards into one-hot representations.
- Balanced clustering: The paper introduces K-means-based and PCA-based modules for constructing balanced item clusters.Their algorithmic details are given in Algorithms 3 and 4.
- Balanced clustering: Balanced clustering assigns vectors to c clusters using centroid proximity in K-means or principal-component ordering in PCA.
- Complexity analysis: With small constant depth d and c = ceil(|A|^(1/d)), each policy network has time and space complexity O(c).The time analysis derives O(a + b × c) ≃ O(c), while the space analysis derives O(a′ + b′ × c) ≃ O(c).
- Complexity analysis: The clustering tree reduces each policy network's output dimension to c rather than the full action-space size.
- Reward mapping: The reward mapping function converts rewards in (a, b] into l-dimensional one-hot vectors using floor-based indexing.The resulting vector has one element set to 1 and all others set to 0.