  We consider the task of generating exact samples from a target distribution,
known up to normalization, over a finite alphabet. The classical algorithm for
this task is rejection sampling, and although it has been used in practice for
decades, there is surprisingly little study of its fundamental limitations. In
this work, we study the query complexity of rejection sampling in a minimax
framework for various classes of discrete distributions. Our results provide
new algorithms for sampling whose complexity scales sublinearly with the
alphabet size. When applied to adversarial bandits, we show that a slight
modification of the Exp3 algorithm reduces the per-iteration complexity from
$\mathcal O(K)$ to $\mathcal O(\log^2 K)$, where $K$ is the number of arms.
