Is Monte Carlo Tree Search Just Every-Visit Monte Carlo Control?
Machine Learning
Summary
The authors explain that two methods used in decision-making and learning—Monte Carlo Tree Search (MCTS) and every-visit Monte Carlo (MC) control—are basically the same when you look closely. They show that what seems like different steps in MCTS are similar to steps in MC control but just described in different ways. By understanding these steps as part of one process, the authors simplify MCTS to just sampling paths and updating values, like MC control does. Their goal is to make it easier to see how these two methods relate.
Authors
Xianyi Wu
Abstract
Monte Carlo Tree Search (MCTS) and every-visit Monte Carlo (MC) control are usually presented as different methods. MCTS is described in the language of search (selection, expansion, simulation, and backup), whereas MC control is described in the language of reinforcement learning (trajectory sampling, return estimation, action-value updating, and policy improvement). This note argues that, at the level of trajectory generation and action-value updating, the distinction is largely terminological. The tree policy and rollout policy can be viewed as the learned and not-yet-learned parts of a single evolving policy; expansion corresponds to first visit and initialization; and backup is the ordinary every-visit Monte Carlo update. Under this interpretation, the four stages of MCTS reduce to two basic operations: trajectory sampling under the current policy and every-visit Monte Carlo updating. In this sense, MCTS is simply every-visit Monte Carlo control expressed in the language and data structure of search. The purpose of this note is expository: to make this equivalence explicit and easier to recognize.