Slate Off-Policy Evaluation

A search page shows 10 results chosen from 100 candidates. The number of ordered slates is \(100!/90! \approx 6.3 \times 10^{19}\). A logging policy that randomises over them will almost never produce the exact slate a new ranker would show, so the slate-level importance weight \(\pi(s \mid x)/\mu(s \mid x)\) is zero on nearly every log line and enormous on the rest. Plain IPS is unbiased and useless. The rankers-and-LLM concept on this track names the problem; this one covers the estimators that make slate evaluation tractable and the assumptions each one buys it with.

The pseudoinverse estimator

Swaminathan and colleagues assume the slate's expected reward is additive over (slot, item) pairs, with per-pair contributions that may depend arbitrarily on context (Swaminathan et al., 2017, Off-policy Evaluation for Slate Recommendation, NeurIPS, arXiv:1605.04812). Represent a slate of \(\ell\) slots over \(m\) items by an indicator vector \(\mathbf{1}_s \in \{0,1\}^{\ell m}\) with a 1 at \((j, a)\) when slot \(j\) holds item \(a\). The linearity assumption is

for some unknown, context-specific vector \(\phi_x\) that is never estimated directly. Recovering \(\phi_x\) is a linear regression whose covariates are the logged slate indicators, and its minimum-norm solution involves the pseudoinverse of \(\Gamma_{\mu,x} = \mathbb{E}_{\mu}[\mathbf{1}_s \mathbf{1}_s^{\top} \mid x]\). Substituting gives the estimator

where \(q_{\pi,x} = \mathbb{E}_{\pi}[\mathbf{1}_s \mid x]\) is how often the target policy puts each item in each slot. Only slot-level marginals of the two policies enter; whole-slate probabilities never do. PI is unbiased under linearity and common support, reduces to IPS when \(\ell = 1\), and has a self-normalised variant, wPI.

A special case shows the mechanism. When slates are a Cartesian product and the logging policy samples slots independently, the estimator simplifies to

a sum of per-slot weights instead of their product. Each term is of order \(\ell m\) rather than \(m^{\ell}\). With \(m = 100\) and \(\ell = 10\), that is on the order of \(10^3\) against \(10^{20}\), and the paper's analysis gives roughly \(O(\ell m/\varepsilon^2)\) samples for error \(\varepsilon\) under \(\epsilon\)-uniform logging, an exponential saving over IPS.

What linearity covers, and the evidence

NDCG is linear in this sense: each item contributes its gain divided by a position discount. Expected reciprocal rank is not, because an item's contribution depends on whether the user was satisfied higher up. The paper's semi-synthetic study used MSLR-WEB30K, over 31,000 queries with up to 1,251 judged documents each, and evaluated both. On proprietary Bing logs it estimated two whole-page satisfaction metrics that violate linearity, time-to-success and utility rate, and PI still had lower error than IPS and a regression-tree direct method at moderate log sizes. Bias from a wrong assumption can be smaller than the variance of making no assumption.

A spectrum of assumptions

Slate estimators are best read as a ladder of user-behaviour assumptions, each trading variance for bias.

Independence (item-position) estimators assume the reward at each position depends only on the item there, so each position gets its own single-item weight. Lowest variance, strongest assumption; they follow from click models such as the position-based model (Li et al., 2018, Offline Evaluation of Ranking Policies with Click Models, KDD).

Cascade estimators assume the user scans top to bottom, so the reward at position \(k\) depends on items at positions 1 to \(k\), and the weight is a product of per-position ratios up to \(k\) (McInerney et al., 2020, Counterfactual Evaluation of Slate Recommendations with Sequential Reward Interactions, KDD). A doubly robust version adds a reward model at each position (Kiyohara et al., 2022, WSDM).

PI assumes additivity but no browsing order.

Full slate IPS assumes nothing and pays the combinatorial variance.

Which rung is right is an empirical question about users, not about estimators, and it varies by surface: a grid of thumbnails is not browsed like a list of links. Control variates can reduce PI's variance further without changing its assumption (Vlassis et al., 2021, Control Variates for Slate Off-Policy Evaluation, NeurIPS, arXiv:2106.07914).

When it breaks

Item interactions violate additivity. Showing two near-duplicate results lowers the value of both. Diversity, complementarity and substitution are exactly what whole-page optimisation is for, and PI's assumption rules them out. The resulting bias does not shrink with more data.

The logging policy must randomise at the slot level. \(\Gamma_{\mu,x}\) must cover the (slot, item) pairs the target uses. A logger that always places its top item first gives no information about any other item in slot 1, and the pseudoinverse quietly returns a minimum-norm answer for that part of the space.

Deterministic targets are fine; deterministic loggers are not. PI can evaluate a deterministic ranker, since only \(q_{\pi,x}\) is needed. It cannot learn from a deterministic logger, which is the common production reality.

Per-context pseudoinverses are costly. \(\Gamma_{\mu,x}\) is \(\ell m \times \ell m\) per context unless the logging distribution admits a closed form, as in the product and uniform-ranking cases. For large candidate sets, practitioners restrict \(m\) to a pre-filtered candidate list, which moves part of the evaluation question upstream to a stage PI does not see.