# Off-policy Bandits with Deficient Support

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

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2020.

## Built on by (most cited first, 30 of 61)

- [Data Distillation: A Survey](https://mlsanity.com/paper/2301.04272/) (2023)
- [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)
- [Policy Learning with Adaptively Collected Data](https://mlsanity.com/paper/2105.02344/) (2021)
- [Infinite Recommendation Networks: A Data-Centric Approach](https://mlsanity.com/paper/2206.02626/) (2022)
- [A General Offline Reinforcement Learning Framework for Interactive Recommendation](https://mlsanity.com/paper/2310.00678/) (2023)
- [Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning](https://mlsanity.com/paper/2405.14335/) (2024)
- [Safe Exploration for Efficient Policy Evaluation and Comparison](https://mlsanity.com/paper/2202.13234/) (2022)
- [Exponential Smoothing for Off-Policy Learning](https://mlsanity.com/paper/2305.15877/) (2023)
- [Off-Policy Evaluation for Large Action Spaces via Policy Convolution](https://mlsanity.com/paper/2310.15433/) (2023)
- [On (Normalised) Discounted Cumulative Gain as an Off-Policy Evaluation Metric for Top-n Recommendation](https://mlsanity.com/paper/2307.15053/) (2023)
- [Local Policy Improvement for Recommender Systems](https://mlsanity.com/paper/2212.11431/) (2022)
- [Marginal Density Ratio for Off-Policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/2312.01457/) (2023)
- [Policy Learning for Off-Dynamics RL with Deficient Support](https://mlsanity.com/paper/2402.10765/) (2024)
- [Long-term Off-Policy Evaluation and Learning](https://mlsanity.com/paper/2404.15691/) (2024)
- [On Sampling Collaborative Filtering Datasets](https://mlsanity.com/paper/2201.04768/) (2022)
- [Probabilistic Rank and Reward: A Scalable Model for Slate Recommendation](https://mlsanity.com/paper/2208.06263/) (2022)
- [Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits](https://mlsanity.com/paper/2408.11202/) (2024)
- [Combining Online Learning and Offline Learning for Contextual Bandits with Deficient Support](https://mlsanity.com/paper/2107.11533/) (2021)
- [Offline Policy Optimization with Eligible Actions](https://mlsanity.com/paper/2207.00632/) (2022)
- [Learning Complementary Policies for Human-AI Teams](https://mlsanity.com/paper/2302.02944/) (2023)
- [Learning Action Embeddings for Off-Policy Evaluation](https://mlsanity.com/paper/2305.03954/) (2023)
- [Counterfactual-Augmented Importance Sampling for Semi-Offline Policy Evaluation](https://mlsanity.com/paper/2310.17146/) (2023)
- [Loss Functions for Discrete Contextual Pricing with Observational Data](https://mlsanity.com/paper/2111.09933/) (2021)
- [Variance-Optimal Augmentation Logging for Counterfactual Evaluation in Contextual Bandits](https://mlsanity.com/paper/2202.01721/) (2022)
- [Sequential Counterfactual Risk Minimization](https://mlsanity.com/paper/2302.12120/) (2023)
- [Enhancing Counterfactual Classification via Self-Training](https://mlsanity.com/paper/2112.04461/) (2021)
- [Balanced Off-Policy Evaluation for Personalized Pricing](https://mlsanity.com/paper/2302.12736/) (2023)
- [Bayesian Off-Policy Evaluation and Learning for Large Action Spaces](https://mlsanity.com/paper/2402.14664/) (2024)
- [Scalable and Robust Self-Learning for Skill Routing in Large-Scale Conversational AI Systems](https://mlsanity.com/paper/2204.07135/) (2022)

## Abstract (arXiv)

Learning effective contextual-bandit policies from past actions of a deployed system is highly desirable in many settings (e.g. voice assistants, recommendation, search), since it enables the reuse of large amounts of log data. State-of-the-art methods for such off-policy learning, however, are based on inverse propensity score (IPS) weighting. A key theoretical requirement of IPS weighting is that the policy that logged the data has "full support", which typically translates into requiring non-zero probability for any action in any context. Unfortunately, many real-world systems produce support deficient data, especially when the action space is large, and we show how existing methods can fail catastrophically. To overcome this gap between theory and applications, we identify three approaches that provide various guarantees for IPS-based learning despite the inherent limitations of support-deficient data: restricting the action space, reward extrapolation, and restricting the policy space. We systematically analyze the statistical and computational properties of these three approaches, and we empirically evaluate their effectiveness. In addition to providing the first systematic analysis of support-deficiency in contextual-bandit learning, we conclude with recommendations that provide practical guidance.