Off-policy evaluation for slate recommendation

Adith Swaminathan; Akshay Krishnamurthy; Alekh Agarwal; Miroslav Dudík; John Langford; Damien Jose; Imed Zitouni

Source-linked AI summary

Off-policy evaluation for slate recommendation

Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miroslav Dudík, John Langford, Damien Jose, Imed Zitouni

arXiv:1605.04812v3May 16, 2016cs.LGcs.AIstat.ML

TL;DR

Off-policy evaluation for ranked slates is difficult because general estimators require impractically large logged datasets. The paper adapts the pseudoinverse estimator to use weak reward structure, finding strong empirical performance and exponential sample savings, while noting open challenges when higher-order interactions matter.

Problem
General off-policy estimators require unrealistically large logged datasets for whole-page metrics because the number of possible slates is combinatorially large.
Method
The paper adapts the pseudoinverse estimator, assuming slate rewards decompose additively into context-dependent action-level rewards that are not observed.
Results
PI typically requires O(ℓm/ε2) samples versus mΩ(ℓ) for IPS, and experiments report strong whole-page evaluation performance over prior baselines.
Takeaways & Limitations
PI provides a favorable bias-variance tradeoff and typically outperforms baselines even on datasets and metrics that violate its assumptions.
Takeaways & Limitations
The linear reward decomposition does not capture higher-order interactions such as diversity, and tight sample-complexity analysis for broader slate spaces remains open.

Abstract

from arXiv · show

This paper studies the evaluation of policies that recommend an ordered set of items (e.g., a ranking) based on some context---a common scenario in web search, ads, and recommendation. We build on techniques from combinatorial bandits to introduce a new practical estimator that uses logged data to estimate a policy's performance. A thorough empirical evaluation on real-world data reveals that our estimator is accurate in a variety of settings, including as a subroutine in a learning-to-rank task, where it achieves competitive performance. We derive conditions under which our estimator is unbiased---these conditions are weaker than prior heuristics for slate evaluation---and experimentally demonstrate a smaller bias than parametric approaches, even when these conditions are violated. Finally, our theory and experiments also show exponential savings in the amount of required data compared with general unbiased estimators.

1 Introduction

The paper addresses off-policy evaluation for combinatorially large slates, where general unbiased estimators need impractical amounts of logged data. It introduces PI, analyzes its guarantees, and demonstrates strong empirical performance and use in learning to rank.

Whole-page metrics are difficult to evaluate because the number of possible slates grows combinatorially, so logged and target policies often choose different slates.
PI estimates slate performance under a weak additive linearity assumption while allowing context-dependent action rewards and arbitrary context representations.
PI typically needs O(ℓm/ε2) samples for error at most ε, versus mΩ(ℓ) for IPS when ranking ℓ out of m items.
Experiments on real-world search-ranking datasets report high-quality whole-page evaluation and comprehensive improvement over prior baselines.
PI is also used to impute action-level rewards for pointwise learning-to-rank optimization without requiring pointwise feedback.
The analysis provides distribution-dependent bounds without assumptions on the logging or target policy, extending prior PI analyses tailored to online data collection.

2 Setting and notation

The setting treats slate recommendation as a combinatorial contextual bandit: policies choose ordered action sets from context, and only a slate-level reward is observed. Off-policy evaluation uses logged data to estimate a target policy’s value, with DM and IPS offering different bias-variance trade-offs.

For each context, a stochastic policy selects an allowed slate of actions across slots, after which a bounded reward is observed.
Ranking: In ranking, choosing ℓ distinct items from m candidates yields |S(x)| = m!/(m − ℓ)! = mΩ(ℓ) valid slates.
Off-policy evaluation: Off-policy evaluation estimates a target policy’s value from logged context, slate, and reward triples collected by a logging policy.
Direct method: The direct method fits a parametric reward model, but model mismatch can produce bias.
IPS: IPS reweights logged examples by target-to-logging slate-probability ratios and is provably unbiased under modest assumptions.
IPS: wIPS generally reduces variance while retaining asymptotically zero bias, whereas both estimators’ variance grows with π(s|x).

3 Our approach

The approach assumes slate rewards decompose additively across context-, action-, and position-specific intrinsic rewards, then uses a pseudoinverse estimator to recover policy value from logged data. Under absolute continuity, PI is unbiased and can reduce the exponential data dependence of IPS, with accuracy improving when logging and evaluation policies overlap.

Model assumptions: The linearity assumption makes slate value a sum of unobserved action-level rewards that may vary arbitrarily across contexts.It rules out interactions among different slate actions while avoiding assumptions about how intrinsic rewards depend on context features.
Model assumptions: The slate indicator vector represents slot-action choices, and the context-specific intrinsic reward vector weights those choices to determine slate value.PI does not attempt to accurately estimate the intrinsic reward vector or model its dependence on context.
Model assumptions: Absolute continuity requires the logging policy to assign positive probability to every slate the target policy may choose.This support condition is also required by IPS for unbiased off-policy evaluation.
The pseudoinverse estimator: PI replaces whole-slate propensity weighting with pseudoinverse-based recovery of action-level contributions from logged slate rewards.The estimator is motivated by a linear regression formulation using the logged action indicators and rewards.
The pseudoinverse estimator: If the linearity and absolute-continuity assumptions hold, PI is unbiased for the target policy value.The expectation is over logged examples sampled independently from the logging policy.
Examples and efficiency: For product slate spaces, PI divides by individual slot-action probabilities, making each outer-sum term O(ℓm) rather than m^Ω(ℓ) for IPS.For rankings with ℓ = m and uniform logging, the corresponding summands are O(m^2).
Error and data requirements: PI typically needs O(ℓm/ε^2) samples for error at most ε, compared with m^Ω(ℓ) for IPS.Finite-sample confidence also depends on average and worst-case overlap between the logging and target policies.
Error and data requirements: With ε-uniform logging in the analyzed settings, PI changes IPS's Ω(m^ℓ) data dependence to O(mℓ).The bound is obtained for suitably small exploration mixtures with the uniform slate distribution.

4 Experiments

Experiments evaluate PI for slate off-policy estimation and policy optimization on semi-synthetic and search-ranking data. PI is robust across conditions, competitive for learning to rank, and effective despite some violations of its linearity assumption.

4.3 Real-world experiments: Real-world search-log experiments evaluate PI on whole-page time-to-success and utility-rate metrics that do not satisfy the linearity assumption.The evaluation uses randomly sampled slates from pre-filtered document sets, including 77 queries and 22K logged examples.
4.1 Semi-synthetic evaluation: The semi-synthetic study varies reward metrics, slate-space sizes, and target-logging combinations across 40 experimental conditions, evaluating RMSE over sample size.The aggregate plots summarize normalized RMSE across 10 target-logging combinations at 600k and 60k samples.
4.1 Semi-synthetic evaluation: PI robustly outperforms weighted IPS across experimental conditions, while direct methods can plateau or degrade as they overfit the logging distribution.With very small datasets, direct methods may be preferable because of lower variance; PI performs comprehensively better given enough data.
4.1 Semi-synthetic evaluation: PI remains meaningful as slate spaces grow, whereas weighted IPS fails to produce meaningful estimates and barely improves with additional data.PI is biased for ERR because ERR does not satisfy the linearity assumption, but remains useful in larger slate spaces.
4.2 Semi-synthetic policy optimization: PI converts page-level rewards into per-slot targets for pointwise learning to rank, enabling whole-page metric optimization without relevance labels.The resulting model greedily constructs a slate from slot-action scores; without linearity, the imputed targets may not yield the best possible learned policy.
4.2 Semi-synthetic policy optimization: On MSLR-WEB10K, PI-OPT is competitive with supervised learning for NDCG and substantially superior for ERR, while both are slightly below LambdaMART on NDCG@3.PI-OPT uses page-level rewards, whereas the supervised baseline uses annotated relevance judgments.

5 Discussion

The PI estimator offers a favorable bias–variance tradeoff for slate off-policy evaluation, including when its linearity assumption is violated. The paper identifies higher-order decompositions as a direction for relaxing this assumption, but leaves tight sample-complexity analysis open.

PI typically outperforms all baselines even on datasets and metrics where its linearity assumptions are violated.The empirical analysis reports this advantage particularly at smaller sample sizes, while describing the overall tradeoff as favorable.
Doubly robust variants and weight clipping are identified as possible ways to improve PI performance at smaller sample sizes.
Pairwise or tuple-wise reward decompositions could capture higher-order interactions such as diversity.
Tight sample-complexity analysis remains open for pseudoinverse estimation under these generalized slate spaces.

A Proof of Proposition 1

The proof of Proposition 1 characterizes the pseudoinverse estimator through the logging policy’s support and moment matrix. It establishes the algebraic relationship needed for the estimator’s expectation analysis.

The support of the logging policy is encoded in a binary matrix whose rows represent supported slates.
The matrix multiplied by the feature representation enumerates slate-level value vectors over slates with positive logging probability.
The null spaces of the second-moment matrix and support matrix coincide, linking the estimator’s moment structure to supported slates.
The proof reduces the proposition to analyzing the expectation of a single estimator term.

B Proof of Theorem 1

The proof of Theorem 1 derives concentration for the PI estimator using Bernstein’s inequality and analyzes its moment structure through matrix decompositions. It also establishes a simple special case when target and logging policies coincide.

Bernstein’s inequality is applied to a centered sum after bounding its per-term variance and range.The variance is bounded by σ2, while reward boundedness helps control the range.
For π = µ, the theorem’s bound is independent of the number of actions and slots because σ2 = ρ = 1.
When π = µ, the PI estimator reduces to an empirical average of bounded rewards.
The proof represents the second-moment matrix in an eigenbasis and uses a block factorization to derive its pseudoinverse.
The matrix structure is simplified in product slate spaces because the covariance matrix decomposes into slot-specific blocks under conditional independence.

E Proof of Corollary 1

The proof of Corollary 1 bounds PI’s concentration parameters using overlap between logging and target policies, then specializes the result to uniformly randomized ranking policies. The resulting expressions depend on the number of actions and slots.

For any target policy absolutely continuous with respect to the logging policy, σ2 and ρ are bounded through a logging-policy-dependent overlap quantity.
For uniform logging over rankings with ℓ < m, the overlap bound is mℓ−ℓ+1.
For uniform logging with ℓ = m, the corresponding overlap bound is m2−2m+2.
The proof obtains these ranking bounds by evaluating quadratic forms involving the pseudoinverse under uniform slate distributions.

E.2 Proof of Corollary 1

The proof bounds the overlap-dependent quantity needed for Corollary 1 by applying Claim 3 to logging and target covariance matrices. This yields an O(ℓm/ε) bound for both product and ranking slate spaces.

Proof of Claim 3: Claim 3 compares two symmetric positive semidefinite matrices when Null(A) ⊆ Null(B).The proof represents each matrix through its symmetric positive semidefinite square root and uses range and projection relationships.
Proof of Corollary 1: The corollary applies Claim 3 with A = Γν,x and B = Γµε,x to bound ¯ρµε,x.The proof notes that the two covariance matrices have equal null spaces because the support of µ(· | x) is included in the support of ν(· | x).
Proof of Corollary 1: For both product and ranking slate spaces, ¯ρµε,x = O(ℓm/ε).The product-space bound uses Eq. (18), while the ranking-space bound uses Proposition 4 before applying Theorem 1.
Proof of Corollary 1: The resulting upper bound, combined with Proposition 3, completes the proof of Theorem 1.The proof substitutes the overlap bound into the theorem statement after treating both slate-space cases.

F Supplementary plots for off-policy evaluation on semi-synthetic data

The supplementary experiments plot RMSE as logged-data size increases across slate spaces, logging policies, target policies, and page-level metrics. The figures vary both logging concentration and slate-space size.

Experimental configurations: The experiments vary NDCG versus ERR, slate spaces (100, 10) versus (10, 5), three logging policies, two target policies, and temperature α.NDCG satisfies the linearity assumption, whereas ERR does not; α = 0 is uniform, while larger α values produce peaked logging distributions.
Large slate spaces: Figures 4, 9, and 10 use slate space (100, 10) under uniform or moderately peaked logging conditions.Their panels distinguish lassobody and treebody targets, while columns distinguish NDCG and ERR.

G Off-policy optimization

The off-policy optimization experiments compare SUP with PI-OPT on MSLR-WEB10K using regression-based models trained from query-document features. PI-OPT creates position-specific regression targets from logged samples.

Experimental setup: SUP and PI-OPT are compared on the MSLR-WEB10K dataset using all query-document features in each training fold.SUP uses regression targets from Section 4.2, while an additional SUP-rel variant regresses to raw relevance judgments.
PI-OPT: PI-OPT forms one regression example per query-document-position triplet by concatenating document features with a position one-hot encoding.Each logged query produces an estimate ˆφj(x, a) for every candidate document and position, providing the regression targets.
Optimization procedure: Both methods use gradient-boosted regression trees with 1,000-tree ensembles and up to 70 leaves per tree.SUP then ranks candidates by predicted scores; PI-OPT uses a greedy procedure to fill slate positions after invalid pairs are removed.

H Overlap between base-rankers

This section measures how similar the four base-rankers are by comparing retrieved-document overlap and Kendall’s tau over the union of retrieved documents.

Base-rankers: The four base-rankers are lassotitle, lassobody, treetitle, and treebody.The comparison concerns the top-ℓ rankings with ℓ = 10 in the semi-synthetic experiments.
Similarity measures: Table 2 reports average overlap of retrieved document sets and Kendall’s tau for every ranker pair.Overlap includes its standard deviation, while Kendall’s tau is computed over documents retrieved by either ranker.