Source-linked AI summary
Top-K Off-Policy Correction for a REINFORCE Recommender System
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, Ed Chi
TL;DR
Industrial recommenders must learn from sparse, biased logged feedback in enormous and evolving action and user-state spaces. The paper scales REINFORCE, models behavior policies for off-policy correction, and introduces a top-K correction for multi-item recommendations. Simulations and live YouTube experiments demonstrate improved top-K recommendations, long-term satisfaction, and the value of exploration.
Problem
Recommendation learning must address biased logged feedback, where observed responses reflect recommendations selected by previous behavior policies in huge action and user-state spaces.
Method
The paper deploys REINFORCE at million-item scale, learns a mixture behavior policy for off-policy correction, and adapts correction to top-K set recommendations.
Results
The top-K correction produces significantly better top-K recommendations than standard correction in simulations and live experiments, while live experiments demonstrate exploration’s value.
Takeaways & Limitations
Scaling REINFORCE with learned logging-policy and top-K corrections provides a practical production approach for reinforcement-learning recommendation at YouTube.
Takeaways & Limitations
Importance-weight correction can have huge variance when target and behavior policies differ substantially, and sequential live experiments cannot be directly compared across earlier systems.
Abstract
from arXiv · showhide
Industrial recommender systems deal with extremely large action spaces -- many millions of items to recommend. Moreover, they need to serve billions of users, who are unique at any point in time, making a complex user state space. Luckily, huge quantities of logged implicit feedback (e.g., user clicks, dwell time) are available for learning. Learning from the logged feedback is however subject to biases caused by only observing feedback on recommendations selected by the previous versions of the recommender. In this work, we present a general recipe of addressing such biases in a production top-K recommender system at Youtube, built with a policy-gradient-based algorithm, i.e. REINFORCE. The contributions of the paper are: (1) scaling REINFORCE to a production recommender system with an action space on the orders of millions; (2) applying off-policy correction to address data biases in learning from logged feedback collected from multiple behavior policies; (3) proposing a novel top-K off-policy correction to account for our policy recommending multiple items at a time; (4) showcasing the value of exploration. We demonstrate the efficacy of our approaches through a series of simulations and multiple live experiments on Youtube.
1 INTRODUCTION
Industrial recommendation must navigate huge, evolving action and user-state spaces despite sparse feedback. The paper applies REINFORCE with off-policy and top-K corrections, and evaluates exploration in simulations and live YouTube experiments.
- Industrial recommenders must identify relevant content from huge item corpora while adapting to users’ shifting interests.
- Sparse implicit-feedback data makes learning difficult because users see only a small fraction of items and explicitly respond to fewer.The Netflix Prize dataset is cited as only 0.1% dense.
- Industrial reinforcement-learning recommendation faces millions of available items, continuously arriving new items, and continuously evolving user preferences.
- The standard correction is optimal for top-1 recommendation, whereas the top-K correction yields significantly better top-K recommendations in simulations and live experiments.
- The system scales a REINFORCE policy-gradient approach, learns behavior policies to correct logged-data bias, and uses a novel top-K correction for multiple recommendations.
- Live experiments demonstrate the value of exploration and the approaches’ contribution to improving users’ long-term satisfaction.
2 RELATED WORK
Related work spans reinforcement learning, neural recommendation, online bandits, and propensity-based off-policy learning. The paper positions its approach against scalability, stability, adaptation, and logged-feedback challenges.
- Reinforcement Learning: Policy-gradient methods are a classical RL family, while value-based methods offer seamless off-policy learning but can be unstable with function approximation.Value-based approaches often require extensive hyper-parameter tuning for stable behavior.
- Neural Recommenders: Neural recommender research commonly uses recurrent networks to incorporate temporal information and historical events into recommendation.The authors employ similar architectures to model evolving user states through interactions.
- Bandit Problems in recommender systems: Bandit algorithms address exploration–exploitation trade-offs, with contextual bandits tailoring recommendations using user context.
- Propensity Scoring and Reinforcement Learning in Recommender Systems: Off-policy learning affects policy gradients because evolving policies change the distribution used for gradient expectations.Proximal methods constrain policy updates to support monotonic-improvement guarantees, but are not applied here.
3 REINFORCE RECOMMENDER
The recommender models user interactions as a Markov Decision Process and learns a policy to maximize discounted cumulative satisfaction. REINFORCE estimates policy gradients analytically from rewards along trajectories.
- The system predicts videos to recommend from users’ historical interactions and feedback, targeting improved clicks or watch time.
- The recommendation problem is formulated as an MDP with continuous user states, discrete item actions, transitions, rewards, an initial-state distribution, and discounting.
- The policy distributes probability over items conditional on user state to maximize expected cumulative reward over policy-generated trajectories.
- The paper focuses on REINFORCE, a policy-gradient method, rather than Q-learning or black-box optimization.
- REINFORCE uses a parametrized policy and the log-trick to derive an analytical gradient of expected cumulative reward.
- Discounted future rewards reduce variance in the gradient estimate, and on-policy Monte Carlo policy-gradient estimates are unbiased.
4 OFF-POLICY CORRECTION
The paper corrects policy-gradient bias from logged recommendations by estimating behavior policies and adapting REINFORCE to pages containing multiple items. It addresses million-scale action spaces with neural policy modeling and a top-K correction whose update changes with item probability.
- Off-policy correction: Logged trajectories come from historical or mixed behavior policies, making naive policy-gradient estimates biased when policy updates are computed offline.The mismatch arises from delayed deployment and feedback collected from recommenders with substantially different policies.
- Off-policy correction: Importance weighting corrects distribution mismatch, but exact correction can have very high variance when target and behavior policies differ substantially.The estimator is unbiased when actions are sampled from the behavior policy, yet importance weights may become extremely low or high.
- Neural recommender: REINFORCE models evolving user states with a recurrent neural network and scales million-item softmax computation using sampled softmax in training and nearest-neighbor retrieval at serving.The policy uses action embeddings and a recurrent state representation; the implementation uses a simplified Chaos Free RNN for stability and computational efficiency.
- Estimating the behavior policy 𝛽: The system estimates the mixed behavior policy from logged actions with a context-dependent neural softmax rather than directly logging unavailable behavior probabilities.The behavior-policy head reuses the modeled user state while blocking its gradient from flowing into the main recurrent state model.
- Top-K off-policy correction: When π_θ(a|s) approaches 0, the top-K multiplier approaches K; when it approaches 1, the multiplier approaches 0, producing better top-K recommendations than standard correction.The correction pushes underrepresented desirable items more aggressively, then stops increasing their likelihood once they are likely to appear in the top-K.
5 EXPLORATION
Because brute-force exploration can harm production recommendations, the paper uses Boltzmann exploration to gather exploratory data while balancing exploration and exploitation. The implementation returns the most probable items and samples the remainder from lower-probability items.
- Exploration constraints: Brute-force exploration such as 𝜖-greedy is not viable in production because it could produce inappropriate recommendations and a bad user experience.The paper motivates a less disruptive exploration strategy for a system such as YouTube.
- Boltzmann exploration: Boltzmann exploration samples recommendations from π_θ instead of always selecting the K highest-probability items.This approach is intended to obtain exploratory data without negatively affecting user experience.
- Exploration–exploitation balance: The production policy returns the top K′ most probable items and samples K−K′ items from the remaining M−K′ items.This mixes exploitation of high-probability recommendations with exploration among the remaining candidates.
6 EXPERIMENTAL RESULTS
Simulations and live experiments show that off-policy correction reduces logged-data bias, while top-K correction better supports multi-item recommendations. Exploration also improved ViewTime, but sequential production experiments limit direct comparisons across components.
- 6.1.1 Off-policy correction.: Naive policy-gradient learning can mimic a poorly performing behavior policy, whereas off-policy correction avoids this bias.When the behavior policy favors low-reward items, the learned policy can become arbitrarily poor; correction addresses this effect.
- 6.1.2 Top-K off-policy correction.: Top-K correction preserves probability mass for multiple high-reward items instead of concentrating almost entirely on the top-1 item.Its multiplier decreases as an item’s policy probability becomes large, allowing the second-best item to retain mass.
- 6.2 Live Experiments: Sequential production experiments evaluate components individually because each newly deployed recommender supplies data for subsequent experiments.Consequently, later experiments cannot be directly compared with earlier systems.
- 6.2.1 Exploration.: 0.07% statistically significant ViewTime increase resulted from exploration affecting only 5% of users.The stochastic policy made rarer state-action outcomes more observable while both models received the same amount of training data.
- 6.2.2 Off-Policy Correction.: Nearly threefold more nominations came from videos outside the control model’s top ranks after off-policy correction.The corrected test model favored less-explored videos rather than reproducing the control model’s nomination distribution.
- 6.2.2 Off-Policy Correction.: 0.53% more videos were viewed in a live experiment, despite no statistically significant ViewTime change.The increase in videos viewed was statistically significant, while the ViewTime comparison was not.
- Number of actions.: K=1 reduced ViewTime by 0.66% versus K=16, K=2 narrowed the gap to 0.35%, and K=8 produced a significant +0.15% gain.K=32 performed similarly to the K=16 production baseline.
- 6.2.4 Understanding Hyperparameters.: Removing the importance-weight cap reduced ViewTime by 0.52% in a live experiment.The paper links lifting the cap to potential overfitting to a few logged actions with accidentally high reward.
7 CONCLUSION
The paper presents a policy-gradient top-K recommender using REINFORCE at YouTube, scaled to an action space of millions and running stably in production. It addresses logged-data bias with a learned logging policy and novel top-K off-policy correction, evaluated through analysis and live experiments.
- REINFORCE was scaled to an action space in the orders of millions and deployed stably in YouTube’s live production system.
- A learned logging policy and novel top-K off-policy correction address biases in logged recommendation data.
- Extensive analysis and live experiments empirically measured the importance of accounting for and addressing these underlying biases.