Scalable Discrete Sampling as a Multi-Armed Bandit Problem
This addresses scalability issues in Monte Carlo methods for researchers and practitioners in statistics and machine learning, though it is incremental as it builds on existing sampling and bandit techniques.
The paper tackles the computational burden of discrete sampling in large-scale Bayesian inference and graphical models by framing it as a multi-armed bandit problem, proposing three approximate algorithms with theoretical guarantees that show robustness and efficiency in synthetic and real-world evaluations.
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.