# Scalable Discrete Sampling as a Multi-Armed Bandit Problem

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2015.

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

- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Stochastic Multi-Armed Bandits with Control Variates](https://mlsanity.com/paper/2105.03962/) (2021)
- [Exploiting Correlated Auxiliary Feedback in Parameterized Bandits](https://mlsanity.com/paper/2311.02715/) (2023)
- [Stochastic Multi-Armed Bandits with Limited Control Variates](https://mlsanity.com/paper/2603.02100/) (2026)

## Abstract (arXiv)

Drawing a sample from a discrete distribution is one of the building components for Monte Carlo methods. Like other sampling algorithms, discrete sampling suffers from the high computational burden in large-scale inference problems. We study the problem of sampling a discrete random variable with a high degree of dependency that is typical in large-scale Bayesian inference and graphical models, and propose an efficient approximate solution with a subsampling approach. We make a novel connection between the discrete sampling and Multi-Armed Bandits problems with a finite reward population and provide three algorithms with theoretical guarantees. Empirical evaluations show the robustness and efficiency of the approximate algorithms in both synthetic and real-world large-scale problems.