CAB: Continuous Adaptive Blending Estimator for Policy Evaluation and Learning

Yi Su, Lequn Wang, Michele Santacatterina, Thorsten JoachimsarXiv 2018 · arXiv

Introduction

In modern digital ecosystems, from search engines to recommendation platforms, leveraging historical log data to improve system performance is a critical challenge. This process, known as Off-Policy Evaluation (OPE), aims to predict the performance of a new "target" policy using data generated by a previous "logging" policy. However, OPE is fraught with difficulties, primarily due to partial feedback—where rewards are only known for actions actually taken—and selection bias inherent in the logging policy.

The Bias-Variance Tug-of-War

Traditional OPE methods typically fall into two categories. The Direct Method (DM) employs a machine learning model to estimate rewards. While DM offers low variance, it is often plagued by high bias if the underlying model is misspecified. Conversely, Inverse Propensity Scoring (IPS) re-weights logged data to provide an unbiased estimate. However, IPS suffers from extreme variance when the target policy deviates significantly from the logging policy, leading to large importance weights.

The bias-variance tradeoff in OPE as a function of the clipping threshold M.

Continuous Adaptive Blending (CAB)

To address these limitations, researchers have introduced the Interpolated Counterfactual Estimator (ICE) family, a unified framework for OPE. Within this family, the Continuous Adaptive Blending (CAB) estimator emerges as a robust solution. CAB introduces a clipping threshold ($M$) on importance weights to manage variance.

Unlike previous "hard-switching" methods like the SWITCH estimator, CAB smoothly blends the IPS approach with DM estimates. When importance weights are low, CAB behaves like IPS; as weights exceed the threshold $M$, it adaptively incorporates reward estimates from a DM model. Crucially, CAB is continuous and sub-differentiable. This differentiability allows it to be integrated directly into gradient-based learning algorithms, enabling the training of new policies from scratch rather than just evaluating existing ones.

Experimental Validation

The efficacy of CAB was tested across diverse environments:

  • Synthetic Bandits: Standard classification datasets from the UCI Machine Learning Repository (Letter, Optdigits, Satimage, Pendigits) were converted into bandit problems.
  • Large-Scale Ranking: The Yahoo! LTR Challenge dataset was used to simulate user interactions with position bias.
  • Real-World Recommendations: Amazon Music data provided a challenging scenario where the logging policy had very limited support for the action space.

Key Results and Insights

Experimental results consistently highlighted the advantages of CAB. In Mean Squared Error (MSE) evaluations, CAB exhibited a characteristic "U-shaped" performance curve relative to the threshold $M$. By finding the optimal balance between bias and variance, CAB significantly outperformed both pure DM and pure IPS methods.

MSE performance of CAB and baseline estimators across various datasets, showing the characteristic U-shaped curve.

Furthermore, when used as a training objective, CAB achieved superior test error rates compared to IPS, clipped IPS, and Doubly Robust methods across all UCI datasets. Its continuous nature also provided greater stability during model selection compared to discontinuous estimators like SWITCH, particularly on the Yahoo! LTR dataset. In restrictive environments like Amazon Music, CAB's ability to "impute" rewards in data-sparse regions allowed it to succeed where pure importance-sampling methods failed.

Conclusion

CAB represents a significant advancement in off-policy learning by providing a smooth, differentiable bridge between reward modeling and importance sampling. While challenges remain regarding hyperparameter tuning and model sensitivity, CAB offers a more stable and accurate framework for evaluating and optimizing AI systems from logged data. Future research will explore extending these continuous blending principles to multi-step reinforcement learning problems.

Summary updated

Abstract

The ability to perform offline A/B-testing and off-policy learning using logged contextual bandit feedback is highly desirable in a broad range of applications, including recommender systems, search engines, ad placement, and personalized health care. Both offline A/B-testing and off-policy learning require a counterfactual estimator that evaluates how some new policy would have performed, if it had been used instead of the logging policy. In this paper, we identify a family of counterfactual estimators which subsumes most such estimators proposed to date. Our analysis of this family identifies a new estimator - called Continuous Adaptive Blending (CAB) - which enjoys many advantageous theoretical and practical properties. In particular, it can be substantially less biased than clipped Inverse Propensity Score (IPS) weighting and the Direct Method, and it can have less variance than Doubly Robust and IPS estimators. In addition, it is sub-differentiable such that it can be used for learning, unlike the SWITCH estimator. Experimental results show that CAB provides excellent evaluation accuracy and outperforms other counterfactual estimators in terms of learning performance.
BibTeX
@misc{su2018cab,
  author = {Yi Su and Lequn Wang and Michele Santacatterina and Thorsten Joachims},
  title = {{CAB: Continuous Adaptive Blending Estimator for Policy Evaluation and Learning}},
  year = {2018},
  eprint = {1811.02672},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.02672},
}
Figure