On Exploration, Exploitation and Learning in Adaptive Importance Sampling
This work addresses the efficiency of sampling methods for practitioners in statistics and machine learning, though it is incremental as it adapts bandit ideas to importance sampling.
The paper tackles the problem of balancing exploration and exploitation in adaptive importance sampling by proposing Daisee, a partition-based algorithm, and shows it achieves O(√T (log T)^(3/4)) cumulative pseudo-regret over T iterations.
We study adaptive importance sampling (AIS) as an online learning problem and argue for the importance of the trade-off between exploration and exploitation in this adaptation. Borrowing ideas from the bandits literature, we propose Daisee, a partition-based AIS algorithm. We further introduce a notion of regret for AIS and show that Daisee has $\mathcal{O}(\sqrt{T}(\log T)^{\frac{3}{4}})$ cumulative pseudo-regret, where $T$ is the number of iterations. We then extend Daisee to adaptively learn a hierarchical partitioning of the sample space for more efficient sampling and confirm the performance of both algorithms empirically.