Counterfactual Learning to Rank

Given position bias, the pragmatic question is whether logged clicks can be used at all. The counterfactual framing says yes, provided the propensities are known: reweight each observed click by the inverse probability that its position was examined, and the resulting objective is an unbiased estimate of the objective you would have computed with complete relevance labels.

Joachims, Swaminathan and Schnabel formalised this and showed a propensity-weighted SVM optimises an unbiased estimate of a ranking risk despite being trained on biased clicks (Joachims, Swaminathan and Schnabel, 2017, Unbiased Learning-to-Rank with Biased Feedback, WSDM, arXiv:1608.04468).

The estimator

Consider the average rank of relevant documents, which we want to minimise. With complete labels it is a sum over all relevant documents; with clicks, only the clicked ones are observed, and each was observed with probability \(p_k\). The inverse propensity weighted risk

is unbiased for the full-information risk. Crucially it needs propensities only for the clicked documents, not for every document in the list, which is what makes it practical: a click at rank 10 with \(p_{10} = 0.05\) counts as 20 clicks, compensating for the 19 out of 20 times an equally relevant document there went unexamined.

The absence of a click contributes nothing, which is correct, because a non-click is ambiguous between "examined and irrelevant" and "never examined".

Where this sits relative to the alternatives

Click models (cascade, dynamic Bayesian network) take the generative route: model the user's browsing process, infer latent relevance, and train on the inferred relevance. They can capture richer behaviour than a rank-only propensity, and they inherit the risk of any generative model, that a wrong process gives confidently wrong relevance.

Online learning to rank (dueling bandit gradient descent and successors) interleaves candidate rankers in live traffic and uses the outcome to update, avoiding the propensity estimation problem entirely at the cost of experimenting on users continuously.

Counterfactual LTR sits between them: offline, so no live risk, and requiring only a propensity model rather than a full behavioural model.

When it breaks

Variance, which is the practical limit. Weights of 20 to 50 for deep clicks make a handful of observations dominate. Clipping propensities at a floor is standard, trading a bounded bias for a large variance reduction, and reporting the effective sample size alongside any offline comparison is the minimum discipline.

Trust bias breaks the factorisation. If users click top results partly because they are top, the click is not examination times relevance, and dividing by examination probability over-corrects. Affine correction models extend the framework with an additive term, at the cost of a second quantity to estimate.

Propensities must come from somewhere. Randomisation degrades user experience; intervention harvesting requires logging which ranker served each impression, which many systems do not; EM estimation assumes the model that is in doubt. This estimation step is where most implementations actually fail, well before the theory becomes the limitation.

Selection bias is untouched. The framework corrects for documents being examined with varying probability, not for documents never entering the candidate set. Candidate generation quality bounds everything downstream, and no reweighting reaches past it.

The correction assumes stationarity. Propensities estimated under last quarter's ranking and interface describe a system that no longer exists. A UI change that adds an answer box above the results changes the examination curve materially, and a stale propensity model corrects toward the wrong target.