An Efficient Dynamic Sampling Policy For Monte Carlo Tree Search
This work addresses computational efficiency in MCTS for reinforcement learning, but it is incremental as it builds on existing tree-based search strategies.
The paper tackles the problem of efficiently allocating computational budget in Monte Carlo Tree Search (MCTS) for finite-horizon Markov decision processes by proposing a dynamic sampling tree policy, with experimental results on Tic-Tac-Toe and Gomoku showing it is more efficient than other methods.
We consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of finite-horizon Markov decision process. We propose a dynamic sampling tree policy that efficiently allocates limited computational budget to maximize the probability of correct selection of the best action at the root node of the tree. Experimental results on Tic-Tac-Toe and Gomoku show that the proposed tree policy is more efficient than other competing methods.