Source-linked AI summary
Offline A/B testing for Recommender Systems
Alexandre Gilotte, Clément Calauzènes, Thomas Nedelec, Alexandre Abraham, Simon Dollé
TL;DR
Offline counterfactual evaluation is intended to estimate recommender-policy uplift from historical data before costly online A/B tests. The paper proposes two capped-importance-sampling variants with finer bias modelling and benchmarks them against online business metrics. The experiments show that more local bias models improve estimator performance over global correction and CIS.
Problem
Traditional offline counterfactual estimators do not provide a satisfying bias-variance compromise for personalized product recommendation, while online A/B tests are costly and slow.
Method
The paper proposes two capped-importance-sampling variants with finer-scale bias modelling and benchmarks offline uplift estimates against online A/B-test metrics.
Results
More local bias models improve performance: the piecewise estimator outperforms the global estimator, and the pointwise estimator outperforms the piecewise estimator.
Takeaways & Limitations
The benchmark supports using locally modelled bias corrections to obtain more accurate offline estimates for real personalized recommendation systems.
Takeaways & Limitations
Doubly robust estimation remains close to importance sampling when conditional reward variance is high, such as sparse click rewards, and CIS lacks a practical bias-variance setting.
Abstract
from arXiv · showhide
Before A/B testing online a new version of a recommender system, it is usual to perform some offline evaluations on historical data. We focus on evaluation methods that compute an estimator of the potential uplift in revenue that could generate this new technology. It helps to iterate faster and to avoid losing money by detecting poor policies. These estimators are known as counterfactual or off-policy estimators. We show that traditional counterfactual estimators such as capped importance sampling and normalised importance sampling are experimentally not having satisfying bias-variance compromises in the context of personalised product recommendation for online advertising. We propose two variants of counterfactual estimates with different modelling of the bias that prove to be accurate in real-world conditions. We provide a benchmark of these estimators by showing their correlation with business metrics observed by running online A/B tests on a commercial recommender system.
1 INTRODUCTION
Online A/B tests provide informed rollout decisions but are slow and costly, motivating offline counterfactual evaluation. Traditional estimators face difficult bias-variance trade-offs, prompting two capped-importance-sampling variants.
- Motivation: Online A/B tests compare production and new technologies through randomized experiments, but typically require several weeks and production-ready prototypes.These costs prevent rapid iteration on new recommender-system ideas.
- Motivation: Offline rank-based metrics rely on heavy assumptions, including product independence and translating feedback such as clicks into supervised tasks.Counterfactual estimators instead use randomized historical data to estimate business comparisons between systems.
- Counterfactual evaluation: Counterfactual or off-policy estimators estimate the expected reward of a test policy from logs collected under the production policy.Examples include BIS, CIS, NIS, and DR.
- Counterfactual evaluation: Importance-sampling estimators differ in bias-variance trade-offs, while capped importance sampling lowers variance by clipping weights but can introduce loosely controlled bias.The paper focuses on improving this trade-off for personalized product recommendation.
- Contribution: The paper proposes two capped-importance-sampling variants designed to achieve low bias under more realistic conditions and evaluates them on real personalized recommendation systems.It compares offline estimator values with metrics observed in real online A/B tests.
2 SETTTING AND NOTATION
The paper models personalized product recommendation as ranking sets of products for users. A recommendation policy is a probability distribution over possible top-K rankings, with rewards representing user responses such as clicks or purchases.
- Recommendation setting: The task displays a personalized set of products to users on e-commerce websites or advertising banners.Because product slots have different performance, the task is formalized as ranking rather than only top-K retrieval.
- Recommendation setting: A recommendation policy is a distribution over top-K rankings, with examples including Bradley-Terry-Luce and Plackett-Luce models.More generally, the paper also considers Thurstonian models.
- Recommendation setting: Given contextual features and eligible products, the system assigns probabilities to rankings and receives a bounded reward for the selected ranking.The reward can represent a click or purchase, with r ∈[0,rmax].
3 ONLINE AND OFFLINE A/B TESTING
Online A/B testing estimates the value difference between production and test policies using randomized populations and observed rewards. Offline testing must estimate the test policy’s reward from historical production-policy logs, typically via importance sampling.
- Online A/B testing: Online A/B tests randomly assign units to production or test populations and compare their average business value using rewards such as clicks or revenue.The unit may be an internet user, recommendation opportunity, or server.
- Online A/B testing: The comparison target is the average treatment effect, defined as the average value difference between test policy πt and production policy πp.The policies are denoted πt and πp throughout the paper.
- Online A/B testing: Online estimates use two datasets collected from the randomized test and production populations, then compute empirical reward averages for statistical decision-making.The empirical average of rewards over each dataset provides the basis for the estimated difference.
- Offline A/B testing: Offline A/B testing has one historical i.i.d. dataset collected under production policy πp, so the test policy’s reward cannot be directly estimated from its own data.Importance sampling estimates the target-policy reward using rewards gathered under the behavior policy.
- Offline A/B testing: Importance sampling is unbiased, but its variance depends on the difference between πt and πp and can be unbounded in the large top-K ranking action space.Variance-reduction variants remain high-variance, motivating clipping as a bias-for-variance trade-off.
4 REDUCING ESTIMATORS VARIANCE
The section examines variance-reduction estimators for offline recommender evaluation, emphasizing the bias-variance limits of control variates, normalization, and capped importance sampling. It motivates estimators that explicitly model capping bias to obtain better practical trade-offs.
- Control Variates: Control variates reduce estimation variance by using a correlated random variable with known expectation, but require strong external knowledge for substantial gains.The doubly robust estimator uses a reward model as a control variate, yet its benefit depends on correlation between predicted and actual rewards.
- Control Variates: Doubly robust estimation can have lower variance than importance sampling when its reward model is well correlated with observed rewards.In recommendation systems, accurate action-dependent reward models are difficult because the action space is very large.
- Control Variates: For sparse click rewards, predicted rewards correlate weakly with outcomes, making doubly robust estimation close to importance sampling and limiting variance reduction.The paper gives expected per-action rewards around 10^-3 in display advertising while observed clicks are typically 0 or 1.
- Normalised Importance Sampling: Normalised importance sampling is biased but consistent, with lower variance than basic importance sampling initially; as data grows, its variance reduction diminishes.Its normalizing constant is the sum of importance weights and equals the dataset size in expectation.
- Capping Weights: Capping importance weights lowers variance at the cost of bias, with zero and max capping behaving similarly in the reported recommendation setting.The experiments report max-capping results because the two capping methods produced very similar outcomes.
- No Good Practical Trade-off for CIS: No practical CIS capping value provides a sufficiently narrow confidence interval because reducing bias requires much larger caps than reducing variance.The reported experiment finds good variance below 10^2 but good bias above 10^23, motivating estimators that model capping bias.
5 MODELLING THE BIAS
The paper models capping bias at increasingly local scales, from global normalization to context-based stratification and pointwise estimation. These approaches target lower bias under realistic recommendation conditions while addressing partition choice, sample scarcity, and policy-distribution mismatch.
- Global and local bias models: CIS cannot provide both low variance and provably low bias, motivating estimators that model capping bias at different scales.NCIS models bias globally, while the proposed contextual estimator models it at the state level.
- Global and local bias models: NCIS uses global proportional rescaling, which can be biased when reward and capped importance weights are correlated through customer subgroups.The paper gives registered versus unknown customers as a counterexample: NCIS estimates 1.8 instead of the true 2.1, below the production reward 1.9.
- Contextual normalization: Local NCIS conditions normalization on context to remove the largest bias term when reward is more correlated with pre-existing intent than with the recommendation.The method is motivated by unsolicited recommendations acting on a user's existing context and intent.
- Piecewise constant model: Stratification partitions contexts and estimates expected reward separately within each group using a restricted NCIS estimator.The partition should be independent of the tested policy; it may use handcrafted context splits or a learned value function.
- Piecewise constant model: A value-function-based partition reduces within-group reward dependence on context and controls group sizes, increasing samples per group and reducing estimation problems.This benefit requires fitting the value function on a separate dataset.
- Pointwise model: Pointwise estimation is difficult because exact context matches are rare, continuous contexts may have no matches, and action marginalization can be computationally infeasible.The paper therefore uses sampling from the tested policy and rejection-sampling methods, including Midzuno-Sen, for probability estimation.
- Practical constraints: When test and production context distributions overlap poorly, the effective sample size can become much larger than the capping value, causing high variance.For max capping, the paper proposes lowering the capping value when overlap is insufficient.
6 EXPERIMENTS
The experiments benchmark offline uplift estimators against online A/B-test outcomes on 39 commercial recommender-system tests, comparing correlation and decision quality. More local bias models improve correlation and reduce false negatives, while PointNCIS also improves computational efficiency for sparse rewards.
- 6.1 Dataset: 39 online A/B tests and a click-based metric benchmark offline uplift estimates against online A/B-test ground truth.The dataset contains a few hundred billion recommendations, with high-variance rewards because clicks are rare.
- 6.2 Estimators: The benchmark compares CIS, NCIS, PieceNCIS, and PointNCIS, using c = 100 and excluding high-variance non-capped estimators.The offline comparison uses control-population data, where production is the logging policy and the test policy is evaluated.
- 6.4 False positive VS False negative rate: PointNCIS is preferred because its performance and computation-efficiency improvements exceed those of the other estimators.Unlike NCIS and PieceNCIS, PointNCIS only needs to read positive examples, which is advantageous when rewards are sparse.
- 6.3 Correlation in Online / Offline Uplifts: More local bias models improve uplift correlation: NCIS improves over CIS, PieceNCIS over NCIS, and PointNCIS over PieceNCIS.The ordering is attributed to progressively more local bias correction.
- 6.4 False positive VS False negative rate: The false negative rate falls from 0.64 for CIS to 0.33 for NCIS, while precision and correlation improve further with local estimators.PointNCIS has better correlation than PieceNCIS, although their precision is quite similar.
7 CONCLUSION
The paper identifies sub-optimality in traditional counterfactual estimators for recommender systems and introduces estimators with better bias-variance trade-offs. A benchmark on a large commercial recommender system supports their practical value, while future work targets further variance reduction.
- Traditional counterfactual estimators exhibit sub-optimality properties in recommender-system settings.
- The paper introduces estimators with better bias-variance trade-offs than traditional Normalised Capped Importance Sampling.
- A benchmark evaluates the offline estimators using experiments on a large commercial recommender system.
- Future work will investigate combining recommendation policies to make their mixture closer to the test policy and reduce estimator variance.
A.1 Analysis of the bias of the NCIS estimator
The appendix analyzes NCIS asymptotically and explains its bias-correction effect relative to CIS. The analysis also extends to PieceNCIS and treats the zero-capping case separately.
- The appendix analyzes the asymptotic behavior and bias of the Normalised Capped Importance Sampling estimator.
- The numerator and denominator of NCIS converge using means of independent identically distributed random variables.
- NCIS reduces CIS bias by approximating performance on the capped volume with performance on the non-capped volume.
- The analysis is extended to PieceNCIS, while zero capping receives a separate asymptotic treatment.
A.2 Analysis under varying capping parameter
The appendix studies whether changing the capping parameter can control PointNCIS weights. Max-capping can ensure a bound, whereas zero-capping cannot guarantee the same property.
- The analysis asks whether a modified capping parameter can keep PointNCIS weights below a chosen cap.
- For max-capping, any action and cap c > 1 admit a modified parameter such that the resulting weight is at most c.
- Zero-capping cannot guarantee bounded modified weights for all parameter values.
- A two-action counterexample demonstrates cases where modified weights are zero, normalized, or exceed the cap depending on the parameter range.
A.3 Additional figures
Figure 5 compares offline and online uplift decisions across A/B tests, distinguishing correct decisions from false positives and false negatives.
- Each box represents an A/B test, with offline uplift confidence bounds on the horizontal axis and online uplift confidence bounds on the vertical axis.Both axes use the same scale; each bound is a 90% confidence bound.
- Green dotted boxes indicate right decisions, orange dashed boxes false positives, and red plain boxes false negatives.