# Low-variance estimation in the Plackett-Luce model via quasi-Monte Carlo sampling

arXiv: https://arxiv.org/abs/2205.06024 · HTML: https://mlsanity.com/paper/2205.06024/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 44 references that are in the map.
- First posted on arXiv 12 May 2022.

## Builds on (most cited first, 17 of 17)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [Unbiased Learning-to-Rank with Biased Feedback](https://mlsanity.com/paper/1608.04468/) (2016)
- [Constrained Bayesian Optimization with Noisy Experiments](https://mlsanity.com/paper/1706.07094/) (2017)
- [Policy Learning for Fairness in Ranking](https://mlsanity.com/paper/1902.04056/) (2019)
- [Unbiased Learning to Rank with Unbiased Propensity Estimation](https://mlsanity.com/paper/1804.05938/) (2018)
- [Evaluating Stochastic Rankings with Expected Exposure](https://mlsanity.com/paper/2004.13157/) (2020)
- [Computationally Efficient Optimization of Plackett-Luce Ranking Models for Relevance and Fairness](https://mlsanity.com/paper/2105.00855/) (2021)
- [Offline Evaluation of Ranking Policies with Click Models](https://mlsanity.com/paper/1804.10488/) (2018)
- [Estimating Position Bias without Intrusive Interventions](https://mlsanity.com/paper/1812.05161/) (2018)
- [Quasi-Monte Carlo Variational Inference](https://mlsanity.com/paper/1807.01604/) (2018)
- [Differentiable Unbiased Online Learning to Rank](https://mlsanity.com/paper/1809.08415/) (2018)
- [Policy-Gradient Training of Fair and Unbiased Ranking Functions](https://mlsanity.com/paper/1911.08054/) (2019)
- [Unifying Online and Counterfactual Learning to Rank](https://mlsanity.com/paper/2012.04426/) (2020)
- [Ranker-agnostic Contextual Position Bias Estimation](https://mlsanity.com/paper/2107.13327/) (2021)

## Built on by (most cited first, 1 of 1)

- [Fast Slate Policy Optimization: Going Beyond Plackett-Luce](https://mlsanity.com/paper/2308.01566/) (2023)

## Abstract (arXiv)

The Plackett-Luce (PL) model is ubiquitous in learning-to-rank (LTR) because it provides a useful and intuitive probabilistic model for sampling ranked lists. Counterfactual offline evaluation and optimization of ranking metrics are pivotal for using LTR methods in production. When adopting the PL model as a ranking policy, both tasks require the computation of expectations with respect to the model. These are usually approximated via Monte-Carlo (MC) sampling, since the combinatorial scaling in the number of items to be ranked makes their analytical computation intractable. Despite recent advances in improving the computational efficiency of the sampling process via the Gumbel top-k trick, the MC estimates can suffer from high variance. We develop a novel approach to producing more sample-efficient estimators of expectations in the PL model by combining the Gumbel top-k trick with quasi-Monte Carlo (QMC) sampling, a well-established technique for variance reduction. We illustrate our findings both theoretically and empirically using real-world recommendation data from Amazon Music and the Yahoo learning-to-rank challenge.