Sampling as Bandits: Evaluation-Efficient Design for Black-Box Densities
This addresses the challenge of efficient sampling for computationally expensive models, such as in Bayesian inference, though it appears incremental as it builds on existing importance sampling and bandit methods.
The paper tackled the problem of sampling from black-box densities with expensive evaluations by introducing bandit importance sampling (BIS), which uses a sequential strategy combining space-filling designs and multi-armed bandits to reduce the number of target evaluations needed for accurate approximations.
We introduce bandit importance sampling (BIS), a new class of importance sampling methods designed for settings where the target density is expensive to evaluate. In contrast to adaptive importance sampling, which optimises a proposal distribution, BIS directly designs the samples through a sequential strategy that combines space-filling designs with multi-armed bandits. Our method leverages Gaussian process surrogates to guide sample selection, enabling efficient exploration of the parameter space with minimal target evaluations. We establish theoretical guarantees on convergence and demonstrate the effectiveness of the method across a broad range of sampling tasks. BIS delivers accurate approximations with fewer target evaluations, outperforming competing approaches across multimodal, heavy-tailed distributions, and real-world applications to Bayesian inference of computationally expensive models.