  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.
