# Estimating Gradients for Discrete Random Variables by Sampling without Replacement

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

## Key facts

- Cited by 30 papers in the map (data through 13 Oct 2026).
- First posted on arXiv 14 Feb 2020.

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

- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [KL-Regularized Reinforcement Learning is Designed to Mode Collapse](https://mlsanity.com/paper/2510.20817/) (2025)
- [Gradient Estimation with Discrete Stein Operators](https://mlsanity.com/paper/2202.09497/) (2022)
- [Sparse Graph Learning from Spatiotemporal Time Series](https://mlsanity.com/paper/2205.13492/) (2022)
- [Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trick](https://mlsanity.com/paper/2311.12569/) (2023)
- [Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Models](https://mlsanity.com/paper/2209.04862/) (2022)
- [Storchastic: A Framework for General Stochastic Automatic Differentiation](https://mlsanity.com/paper/2104.00428/) (2021)
- [Conditional Poisson Stochastic Beam Search](https://mlsanity.com/paper/2109.11034/) (2021)
- [Coupled Gradient Estimators for Discrete Latent Variables](https://mlsanity.com/paper/2106.08056/) (2021)
- [Bayesian Nonparametrics for Offline Skill Discovery](https://mlsanity.com/paper/2202.04675/) (2022)
- [Learning Group Importance using the Differentiable Hypergeometric Distribution](https://mlsanity.com/paper/2203.01629/) (2022)
- [Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks](https://mlsanity.com/paper/2206.00583/) (2022)
- [CARMS: Categorical-Antithetic-REINFORCE Multi-Sample Gradient Estimator](https://mlsanity.com/paper/2110.14002/) (2021)
- [Asymmetric Prompt Weighting for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2602.11128/) (2026)
- [Scaling Structured Inference with Randomization](https://mlsanity.com/paper/2112.03638/) (2021)
- [Learning Discrete Structured Variational Auto-Encoder using Natural Evolution Strategies](https://mlsanity.com/paper/2205.01324/) (2022)
- [Unbiased and Efficient Sampling of Dependency Trees](https://mlsanity.com/paper/2205.12621/) (2022)
- [Revisiting the Gumbel-Softmax in MADDPG](https://mlsanity.com/paper/2302.11793/) (2023)
- [An Efficient Combinatorial Optimization Model Using Learning-to-Rank Distillation](https://mlsanity.com/paper/2201.00695/) (2021)
- [On Many-Actions Policy Gradient](https://mlsanity.com/paper/2210.13011/) (2022)
- [Rao-Blackwellised Reparameterisation Gradients](https://mlsanity.com/paper/2506.07687/) (2025)
- [Replacing thinking with tool usage enables reasoning in small language models](https://mlsanity.com/paper/2507.05065/) (2025)
- [DBsurf: A Discrepancy Based Method for Discrete Stochastic Gradient Estimation](https://mlsanity.com/paper/2309.03974/) (2023)
- [Beyond Softmax: A Natural Parameterization for Categorical Random Variables](https://mlsanity.com/paper/2509.24728/) (2025)
- [Scaling GraphLLM with Bilevel-Optimized Sparse Querying](https://mlsanity.com/paper/2602.09038/) (2026)
- [Scoring Is Not Enough: Addressing Gaps in Utility-fairness Trade-offs for Ranking](https://mlsanity.com/paper/2606.26369/) (2026)
- [Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of-K Objective](https://mlsanity.com/paper/2607.11146/) (2026)
- [Principled Top-k Selection for Language Models with Hybrid Gradients](https://mlsanity.com/paper/2610.04162/) (2026)

## Abstract (arXiv)

We derive an unbiased estimator for expectations over discrete random variables based on sampling without replacement, which reduces variance as it avoids duplicate samples. We show that our estimator can be derived as the Rao-Blackwellization of three different estimators. Combining our estimator with REINFORCE, we obtain a policy gradient estimator and we reduce its variance using a built-in control variate which is obtained without additional model evaluations. The resulting estimator is closely related to other gradient estimators. Experiments with a toy problem, a categorical Variational Auto-Encoder and a structured prediction problem show that our estimator is the only estimator that is consistently among the best estimators in both high and low entropy settings.