In “Variance Reduction in Monte-Carlo Tree Search” Veness, Lanctot, and Bowling (2011) “examine the application of some standard techniques for variance reduction in” MonteCarlo Tree Search.  The variance reduction techniques included control variates, common random numbers, and antithetic variates. These techniques were applied to three games: Pig, Can’t Stop, and Dominion.  After reviewing Markov Decision Process and Upper Confidence Trees (UCT), they describe the variance reduction techniques and display charts showing the improvement of UCT for each technique and each game. The simplest game, Pig, gained the most from the variance reduction techniques, but all of the games gained from all of the techniques except no effective antithetic variate was found for Dominion.

Related Posts via Categories

• AlphaGo is changing how the Game is Played
• Counterfactual Regret Minimization
• Link: In Two Moves, AlphaGo and Lee Sedol Redefined the Future
• University of Alberta Solves Poker
• A review of “Playing Atari with Deep Reinforcement Learning”
• An AI for 2048 — Part 1
• Tetris, Reinforcement Learning, The Cross-Entropy method
• Some Poker Theorems (Part 1)
• Noxious Fumes+ : Certain Death in sqrt(h) turns
• Noxious Fumes: Certain Death in ceil((-3 + sqrt(8h + 9)) / 2) turns