Daisee: Adaptive importance sampling by balancing exploration and exploitation |
| |
Authors: | Xiaoyu Lu Tom Rainforth Yee Whye Teh |
| |
Affiliation: | 1. Amazon, London, EC2A 2FA UK;2. Department of Statistics, University of Oxford, Oxford, OX1 2JD UK |
| |
Abstract: | 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 online learning literature, we propose Daisee, a partition-based AIS algorithm. We further introduce a notion of regret for AIS and show that Daisee has cumulative pseudo-regret, where 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. |
| |
Keywords: | adaptive Monte Carlo bandit exploration and exploitation importance sampling |
|
|