Off-policy evaluation for slate recommendation

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

• For each context, a stochastic policy selects an allowed slate of actions across slots, after which a bounded reward is observed.Source: §2 · p. 3

Ranking

• In ranking, choosing ℓ distinct items from m candidates yields |S(x)| = m!/(m − ℓ)! = mΩ(ℓ) valid slates.Source: §2 · p. 3

Off-policy evaluation

• Off-policy evaluation estimates a target policy’s value from logged context, slate, and reward triples collected by a logging policy.Source: §2.1 · p. 3

Direct method

• The direct method fits a parametric reward model, but model mismatch can produce bias.Source: §2.1 · pp. 3–4

IPS

• IPS reweights logged examples by target-to-logging slate-probability ratios and is provably unbiased under modest assumptions.Source: §2.1 · p. 4
• wIPS generally reduces variance while retaining asymptotically zero bias, whereas both estimators’ variance grows with π(s|x).Source: §2.1 · p. 4

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.Source: §3 · p. 4
• 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.Source: §3 · p. 4
• 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.Source: §3 · p. 4

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.Source: §3.1 · pp. 4–5
• 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.Source: §3.1 · p. 5

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).Source: §3.1 · p. 5

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.Source: §3.2 · pp. 5–6
• 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.Source: §3.2 · p. 6

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.Source: §4 · p. 6, §4.3 · pp. 8–9

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.Source: §4.1 · p. 7, Figure 2 · p. 7
• 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.Source: §4.1 · p. 7
• 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.Source: §4.1 · p. 8

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.Source: §4.2 · p. 8
• 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.Source: §4.2 · p. 8, Table 1 · p. 8

• 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.Source: §5 · p. 9
• Doubly robust variants and weight clipping are identified as possible ways to improve PI performance at smaller sample sizes.Source: §5 · p. 9
• Pairwise or tuple-wise reward decompositions could capture higher-order interactions such as diversity.Source: §5 · p. 9
• Tight sample-complexity analysis remains open for pseudoinverse estimation under these generalized slate spaces.Source: §5 · p. 9

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

• 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.Source: B Proof of Theorem 1 · pp. 12–13
• For π = µ, the theorem’s bound is independent of the number of actions and slots because σ2 = ρ = 1.Source: C Pseudo-inverse estimator when π = µ · p. 13, A11 A12 A21 A22 · p. 15
• When π = µ, the PI estimator reduces to an empirical average of bounded rewards.Source: C Pseudo-inverse estimator when π = µ · p. 13, A11 A12 A21 A22 · p. 15
• The proof represents the second-moment matrix in an eigenbasis and uses a block factorization to derive its pseudoinverse.Source: C Pseudo-inverse estimator when π = µ · pp. 13–14, A11 A12 A21 A22 · p. 14
• The matrix structure is simplified in product slate spaces because the covariance matrix decomposes into slot-specific blocks under conditional independence.Source: D A product slate space under a… · p. 15

• For any target policy absolutely continuous with respect to the logging policy, σ2 and ρ are bounded through a logging-policy-dependent overlap quantity.Source: E Proof of Corollary 1 · p. 16
• For uniform logging over rankings with ℓ < m, the overlap bound is mℓ−ℓ+1.Source: §E.1 · pp. 17, 19
• For uniform logging with ℓ = m, the corresponding overlap bound is m2−2m+2.Source: §E.1 · pp. 17, 19
• The proof obtains these ranking bounds by evaluating quadratic forms involving the pseudoinverse under uniform slate distributions.Source: §E.1 · pp. 17–19

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.Source: §E.2 · pp. 19–20

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).Source: §E.2 · p. 19
• 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.Source: §E.2 · p. 20
• 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.Source: §E.2 · p. 20

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.Source: F Supplementary plots for off-policy… · p. 21

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.Source: Figure 4 · p. 22, Figure 6 · p. 24, Figure 9 · p. 27

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.Source: G Off-policy optimization · p. 30

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.Source: G Off-policy optimization · p. 30

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.Source: G Off-policy optimization · pp. 30–31

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.Source: H Overlap between base-rankers · p. 31

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.Source: H Overlap between base-rankers · p. 31, Table 2 · p. 31