# Sampling as Bandits: Evaluation-Efficient Design for Black-Box Densities

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 55 references that are in the map.
- First posted on arXiv 1 Sep 2025.

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

- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Likelihood-free inference by ratio estimation](https://mlsanity.com/paper/1611.10242/) (2016)
- [Bayesian Optimization for Likelihood-Free Inference of Simulator-Based Statistical Models](https://mlsanity.com/paper/1501.03291/) (2015)
- [Metrizing Weak Convergence with Maximum Mean Discrepancies](https://mlsanity.com/paper/2006.09268/) (2020)
- [Sampling for Inference in Probabilistic Models with Fast Bayesian Quadrature](https://mlsanity.com/paper/1411.0439/) (2014)
- [Parallel Gaussian process surrogate Bayesian inference with noisy likelihood evaluations](https://mlsanity.com/paper/1905.01252/) (2019)
- [GPS-ABC: Gaussian Process Surrogate Approximate Bayesian Computation](https://mlsanity.com/paper/1401.2838/) (2014)
- [On Russian Roulette Estimates for Bayesian Inference with Doubly-Intractable Likelihoods](https://mlsanity.com/paper/1306.4032/) (2013)
- [Merging MCMC Subposteriors through Gaussian-Process Approximations](https://mlsanity.com/paper/1605.08576/) (2016)
- [Gaussian processes for Bayesian inverse problems associated with linear partial differential equations](https://mlsanity.com/paper/2307.08343/) (2023)
- [Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration](https://mlsanity.com/paper/2401.17037/) (2024)
- [The rational SPDE approach for Gaussian random fields with general smoothness](https://mlsanity.com/paper/1711.04333/) (2017)
- [Covariance-based rational approximations of fractional SPDEs for computationally efficient Bayesian inference](https://mlsanity.com/paper/2209.04670/) (2022)

## Abstract (arXiv)

We propose bandit importance sampling (BIS), a powerful importance sampling framework tailored for settings in which evaluating the target density is computationally expensive. BIS facilitates accurate sampling while minimizing the required number of target-density evaluations. In contrast to adaptive importance sampling, which optimizes a proposal distribution, BIS directly optimizes the set of samples through a sequential selection process driven by multi-armed bandits. BIS serves as a general framework that accommodates user-defined bandit strategies. Theoretically, the weak convergence of the weighted samples, and thus the consistency of the Monte Carlo estimator, is established regardless of the specific strategy employed. In this paper, we present a practical strategy that leverages Gaussian process surrogates to guide sample selection, adapting the principles of Bayesian optimization for sampling. Comprehensive numerical studies demonstrate the superior performance of BIS across multimodal, heavy-tailed distributions, and real-world Bayesian inference tasks involving Markov random fields.