Joel Veness, Marc Lanctot, and Michael Bowling. Variance Reduction in Monte Carlo Tree Search. In Advances in Neural Information Processing Systems 24 (NIPS), pp. 1836–1844, 2011.
Monte-Carlo Tree Search (MCTS) has proven to be a powerful, generic planning technique for decision-making in single-agent and adversarial environments. The stochastic nature of the Monte-Carlo simulations introduces errors in the value estimates, both in terms of bias and variance. Whilst reducing bias (typically through the addition of domain knowledge) has been studied in the MCTS literature, comparatively little effort has focused on reducing variance. This is somewhat surprising, since variance reduction techniques are a well-studied area in classical statistics. In this paper, we examine the application of some standard techniques for variance reduction in MCTS, including common random numbers, antithetic variates and control variates. We demonstrate how these techniques can be applied to MCTS and explore their efficacy on three different stochastic, single-agent settings: Pig, Can't Stop and Dominion.
@InProceedings(11nips-vrmcts,
Title = "Variance Reduction in {M}onte {C}arlo Tree Search",
Author = "Joel Veness and Marc Lanctot and Michael Bowling",
Booktitle = "Advances in Neural Information Processing Systems 24 (NIPS)",
Year = "2011",
Pages = "1836--1844",
AcceptRate = "22\%",
AcceptNumbers = "305 of 1400"
)