Download the full-sized PDF of Adaptive Monte Carlo IntegrationDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Adaptive Monte Carlo Integration Open Access


Other title
Online Learning
Machine Learning
Monte Carlo
Multi-armed Bandits
Type of item
Degree grantor
University of Alberta
Author or creator
Neufeld, James, P
Supervisor and department
Schuurmans,Dale (Computing Science)
Bowling, Michael (Computing Science)
Examining committee member and department
Doucet, Arnaud (Statistics, Oxford)
Szepesvari, Csaba (Computing Science)
Gyorgy, Andras (Computing Science, Imperial College London)
Department of Computing Science

Date accepted
Graduation date
Doctor of Philosophy
Degree level
Monte Carlo methods are a simple, effective, and widely deployed way of approximating integrals that prove too challenging for deterministic approaches. This thesis presents a number of contributions to the field of adaptive Monte Carlo methods. That is, approaches that automatically adjust the behaviour of the sampling algorithm to better suit the targeted integrand. The first of such contributions is the introduction of a new method, antithetic Markov chain sampling, which improves sampling efficiency through the use of simulated Markov chains. These chains effectively guide the sampling toward more influential regions of the integrand (modes). We demonstrate that this approach leads to unbiased estimators and offers significant improvements over standard approaches on challenging multi-modal integrands. We next consider the complementary task of efficiently allocating computation between a set of unbiased samplers through observations of their past performance. Here, we show that this problem is equivalent to the well known stochastic multi-armed bandit problem and, as a result, existing algorithms and theoretical guarantees transfer immediately which gives rise to new results for the adaptive Monte Carlo setting. We then extend this framework to cover an important practical condition, where each individual sampler (bandit arm) may take a random amount of computation time to produce a sample. Here, we again show that existing bandit algorithms can be applied through the use of a simple sampling trick, and prove new results which bounding the regret for any such algorithm from above. Lastly, we consider the task of combining a set of unbiased Monte Carlo estimators, with unique variances and samples sizes, into a single estimator. We show that upper-confidence approaches similar to those used in the multi-armed bandit literature lead to estimators that improve on existing solutions both theoretically and in practice. Interestingly, each of these contributions may be applied in parallel and in complement to one another to produce any number of highly adaptable, robust, and practical Monte Carlo integration algorithms.
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
Citation for previous publication
Neufeld, J., Bowling, M., and Schuurmans, D. (2015). Variance reduction via antithetic Markov chains. In Artificial Intelligence and Statistics (AISTATS).Neufeld, J., Gyo ̈rgy, A., Schuurmans, D., and Szepesva ́ri, C. (2014). Adaptive Monte Carlo via bandit allocation. In International Conference on Machine Learning (ICML).

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 8894560
Last modified: 2016:06:16 17:12:00-06:00
Filename: Neufeld_James_P_2016_03_PhD.pdf
Original checksum: 37c77ddc4ec694196c36df379944152a
Well formed: true
Valid: false
Status message: Too many fonts to report; some fonts omitted. Total fonts = 1267
Status message: Invalid destination object offset=8772287
Status message: Invalid destination object offset=8789319
Status message: Invalid destination object offset=8789319
Status message: Invalid destination object offset=8789319
File title: Introduction
Page count: 140
Activity of users you follow
User Activity Date