Off-policy Bandits with Deficient Support

Noveen Sachdeva, Yi Su, Thorsten Joachims

TL;DR

This paper tackles the critical problem of learning from logged data in contextual bandit systems when the logging policy doesn't cover all possible actions (support deficiency). They propose and analyze three novel approaches – restricting action space, reward extrapolation, and restricting policy space – finding that policy restriction is the most effective and practical solution.

What Problem Does This Paper Address?

Many interactive systems, like recommendation engines or voice assistants, generate vast amounts of user interaction data. This data is invaluable for training new, improved policies for these systems. The standard approach for learning from this logged data is "off-policy learning," often relying on Inverse Propensity Score (IPS) weighting. However, a crucial assumption for IPS to work correctly is "full support," meaning the original logging policy must have had a non-zero probability of selecting any action in any given context. This assumption is frequently violated in real-world systems, especially when the action space is large (e.g., recommending from millions of products). When this "support deficiency" occurs, existing off-policy learning methods can fail catastrophically, leading to suboptimal or even harmful policies. This paper aims to bridge the gap between the theoretical requirements of off-policy learning and the practical realities of support-deficient data.

Methods

The authors propose and analyze three main strategies to handle support deficiency:

  1. Restricting the Action Space: This approach modifies the learned policy to assign zero probability to actions that were never taken by the logging policy in a given context. This guarantees full support for the modified policy but might overly constrain it, potentially excluding optimal actions.
  2. Reward Extrapolation: Instead of ignoring unsupported actions, this method attempts to "fill in the blanks" by estimating rewards for these actions. They propose two variants:
  3. Conservative Extrapolation: Imputes the worst possible reward (rmin) for unsupported actions, making the learning algorithm strongly disincentivize their selection.
  4. Regression Extrapolation: Uses a regression model to predict rewards for unsupported actions based on observed data. This can be effective but is susceptible to bias if the regression model is misspecified.
  5. Restricting the Policy Space: This is the most sophisticated approach. It aims to learn a policy that has a "low support divergence" from the logging policy. They introduce a formal measure of support divergence and show how to constrain the policy space to only consider policies with divergence below a certain threshold (κ). This allows for explicit control over the risk associated with support deficiency.

Datasets

The paper uses two real-world datasets for evaluation:

  • CIFAR10: A standard image classification dataset, adapted to simulate bandit feedback for multi-class classification.
  • Credit-card fraud detection dataset: Used to generate bandit data with continuous rewards, differing from the binary rewards in CIFAR10.

The authors generate various degrees of support deficiency by manipulating the logging policy's stochasticity.

Key Insights and Ideas

  • Support deficiency is a critical, widespread problem: The paper highlights that the "full support" assumption is often unrealistic, leading to catastrophic failures in standard off-policy learning methods.
  • Support divergence is a key metric: Quantifying the difference in action probabilities between the logging and target policies is crucial for understanding and mitigating the impact of support deficiency.
  • Policy restriction offers a principled way to control risk: By limiting the learned policy's support divergence, this method provides a tunable knob (κ) to balance exploration and exploitation while guaranteeing robustness against support deficiency.
  • Model misspecification is a major challenge for reward extrapolation: Methods relying on regression models for reward imputation are vulnerable to bias if the model doesn't accurately capture the underlying reward function.
  • Policy restriction is computationally efficient and robust: Unlike action restriction, it doesn't require evaluating the logging policy at test time. Crucially, it's unaffected by model misspecification, making it a strong contender.

Key Results

  • Naive IPS fails dramatically: As support deficiency increases, the performance of standard IPS-based methods degrades significantly.
  • Action restriction underperforms: While it guarantees zero support divergence, it often prunes away too many potentially good actions, limiting its effectiveness.
  • Reward extrapolation shows mixed results: Conservative extrapolation is safe but can be too pessimistic. Regression extrapolation can be good but is sensitive to model misspecification. Doubly Robust (DR) estimation, which combines regression and IPS, performs well but still relies on regression.
  • Policy restriction consistently performs well: This method is competitive with or outperforms other approaches across various levels of support deficiency and even with model misspecification. It also scales well with increasing amounts of training data.
  • Model selection for policy restriction is effective: The proposed "MinSup" criterion for selecting the policy restriction parameter (κ) performs comparably to an oracle (perfect knowledge) and is more robust to model misspecification than other model selection methods.

Limitations and Future Work

  • Computational cost of reward extrapolation: While sampling can mitigate this, evaluating all actions for reward imputation can still be computationally intensive.
  • Tuning the policy restriction parameter (κ): While MinSup provides a data-driven way to select κ, applications might have specific risk tolerance requirements that need to be considered.
  • Future work could explore: Further investigation into more robust reward extrapolation techniques, and extending these findings to more complex sequential decision-making problems beyond contextual bandits. The paper also suggests that understanding the connection between policy gradient baselines and support deficiency could lead to new insights.

Summary updated

Abstract

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.
BibTeX
@inproceedings{sachdeva2020off,
  author = {Noveen Sachdeva and Yi Su and Thorsten Joachims},
  title = {{Off-policy Bandits with Deficient Support}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  url = {https://openreview.net/forum?id=Vp4XGqDsavW},
}
Figure