# Learning from eXtreme Bandit Feedback

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2020.

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

- [Software-Hardware Co-design for Fast and Scalable Training of Deep Learning Recommendation Models](https://mlsanity.com/paper/2104.05158/) (2021)
- [Off-Policy Evaluation for Large Action Spaces via Embeddings](https://mlsanity.com/paper/2202.06317/) (2022)
- [Off-Policy Evaluation for Large Action Spaces via Conjunct Effect Modeling](https://mlsanity.com/paper/2305.08062/) (2023)
- [On component interactions in two-stage recommender systems](https://mlsanity.com/paper/2106.14979/) (2021)
- [Off-Policy Evaluation for Large Action Spaces via Policy Convolution](https://mlsanity.com/paper/2310.15433/) (2023)
- [Control Variates for Slate Off-Policy Evaluation](https://mlsanity.com/paper/2106.07914/) (2021)
- [On (Normalised) Discounted Cumulative Gain as an Off-Policy Evaluation Metric for Top-n Recommendation](https://mlsanity.com/paper/2307.15053/) (2023)
- [POTEC: Off-Policy Learning for Large Action Spaces via Two-Stage Policy Decomposition](https://mlsanity.com/paper/2402.06151/) (2024)
- [Top-k eXtreme Contextual Bandits with Arm Hierarchy](https://mlsanity.com/paper/2102.07800/) (2021)
- [Supporting Massive DLRM Inference Through Software Defined Memory](https://mlsanity.com/paper/2110.11489/) (2021)
- [Constrained Policy Optimization for Controlled Self-Learning in Conversational AI Systems](https://mlsanity.com/paper/2209.08429/) (2022)
- [Uncertainty-Aware Instance Reweighting for Off-Policy Learning](https://mlsanity.com/paper/2303.06389/) (2023)
- [Optimizing Novelty of Top-k Recommendations using Large Language Models and Reinforcement Learning](https://mlsanity.com/paper/2406.14169/) (2024)
- [The Digital Transformation in Health: How AI Can Improve the Performance of Health Systems](https://mlsanity.com/paper/2409.16098/) (2024)
- [Scalable and Safe Remediation of Defective Actions in Self-Learning Conversational Systems](https://mlsanity.com/paper/2305.10528/) (2023)
- [Adaptive User Journeys in Pharma E-Commerce with Reinforcement Learning: Insights from SwipeRx](https://mlsanity.com/paper/2408.08024/) (2024)
- [Context-Action Embedding Learning for Off-Policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/2509.00648/) (2025)

## Abstract (arXiv)

We study the problem of batch learning from bandit feedback in the setting of extremely large action spaces. Learning from extreme bandit feedback is ubiquitous in recommendation systems, in which billions of decisions are made over sets consisting of millions of choices in a single day, yielding massive observational data. In these large-scale real-world applications, supervised learning frameworks such as eXtreme Multi-label Classification (XMC) are widely used despite the fact that they incur significant biases due to the mismatch between bandit feedback and supervised labels. Such biases can be mitigated by importance sampling techniques, but these techniques suffer from impractical variance when dealing with a large number of actions. In this paper, we introduce a selective importance sampling estimator (sIS) that operates in a significantly more favorable bias-variance regime. The sIS estimator is obtained by performing importance sampling on the conditional expectation of the reward with respect to a small subset of actions for each instance (a form of Rao-Blackwellization). We employ this estimator in a novel algorithmic procedure -- named Policy Optimization for eXtreme Models (POXM) -- for learning from bandit feedback on XMC tasks. In POXM, the selected actions for the sIS estimator are the top-p actions of the logging policy, where p is adjusted from the data and is significantly smaller than the size of the action space. We use a supervised-to-bandit conversion on three XMC datasets to benchmark our POXM method against three competing methods: BanditNet, a previously applied partial matching pruning strategy, and a supervised learning baseline. Whereas BanditNet sometimes improves marginally over the logging policy, our experiments show that POXM systematically and significantly improves over all baselines.