# Fast Offline Policy Optimization for Large Scale Recommendation

arXiv: https://arxiv.org/abs/2208.05327 · HTML: https://mlsanity.com/paper/2208.05327/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Decision transformers and sequence modeling, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 24 of its 46 references that are in the map.
- First posted on arXiv 8 Aug 2022.

## Placed in

- Offline RL and imitation learning from data / [Decision transformers and sequence modeling](https://mlsanity.com/offlinerl/decision-transformers-and-sequence-modeling/)

## Builds on (most cited first, 24 of 24)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Variational Autoencoders for Collaborative Filtering](https://mlsanity.com/paper/1802.05814/) (2018)
- [Top-K Off-Policy Correction for a REINFORCE Recommender System](https://mlsanity.com/paper/1812.02353/) (2018)
- [Deep Reinforcement Learning in Large Discrete Action Spaces](https://mlsanity.com/paper/1512.07679/) (2015)
- [Doubly Robust Policy Evaluation and Optimization](https://mlsanity.com/paper/1503.02834/) (2015)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Doubly robust off-policy evaluation with shrinkage](https://mlsanity.com/paper/1907.09623/) (2019)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Fine-Grained Spoiler Detection from Large-Scale Review Corpora](https://mlsanity.com/paper/1905.13416/) (2019)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [Adaptive Sampled Softmax with Kernel Based Sampling](https://mlsanity.com/paper/1712.00527/) (2017)
- [Sampled Softmax with Random Fourier Features](https://mlsanity.com/paper/1907.10747/) (2019)
- [Bayesian Counterfactual Risk Minimization](https://mlsanity.com/paper/1806.11500/) (2018)
- [Distributionally Robust Counterfactual Risk Minimization](https://mlsanity.com/paper/1906.06211/) (2019)
- [The Thermodynamic Variational Objective](https://mlsanity.com/paper/1907.00031/) (2019)
- [BLOB : A Probabilistic Model for Recommendation that Combines Organic and Bandit Signals](https://mlsanity.com/paper/2008.12504/) (2020)
- [Imitation-Regularized Offline Learning](https://mlsanity.com/paper/1901.04723/) (2019)
- [Improving Offline Contextual Bandits with Distributional Robustness](https://mlsanity.com/paper/2011.06835/) (2020)
- [Relaxed Softmax for learning from Positive and Unlabeled data](https://mlsanity.com/paper/1909.08079/) (2019)

## Built on by (most cited first, 4 of 4)

- [Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning](https://mlsanity.com/paper/2405.14335/) (2024)
- [A2PO: Towards Effective Offline Reinforcement Learning from an Advantage-aware Perspective](https://mlsanity.com/paper/2403.07262/) (2024)
- [Fast Slate Policy Optimization: Going Beyond Plackett-Luce](https://mlsanity.com/paper/2308.01566/) (2023)
- [Sequential Off-Policy Learning with Logarithmic Smoothing](https://mlsanity.com/paper/2506.10664/) (2025)

## Abstract (arXiv)

Personalised interactive systems such as recommender systems require selecting relevant items from massive catalogs dependent on context. Reward-driven offline optimisation of these systems can be achieved by a relaxation of the discrete problem resulting in policy learning or REINFORCE style learning algorithms. Unfortunately, this relaxation step requires computing a sum over the entire catalogue making the complexity of the evaluation of the gradient (and hence each stochastic gradient descent iterations) linear in the catalogue size. This calculation is untenable in many real world examples such as large catalogue recommender systems, severely limiting the usefulness of this method in practice. In this paper, we derive an approximation of these policy learning algorithms that scale logarithmically with the catalogue size. Our contribution is based upon combining three novel ideas: a new Monte Carlo estimate of the gradient of a policy, the self normalised importance sampling estimator and the use of fast maximum inner product search at training time. Extensive experiments show that our algorithm is an order of magnitude faster than naive approaches yet produces equally good policies.