Bayesian optimization for backpropagation in Monte-Carlo tree search
This work addresses efficiency in MCTS for large domains like computer Go, but it is incremental as it builds on prior attempts to improve backpropagation strategies.
The paper tackled the problem of slow convergence in Monte-Carlo tree search (MCTS) backpropagation by proposing Softmax MCTS and Monotone MCTS, which use Bayesian optimization to find optimal monotone functions, and demonstrated improved performance in computer Go experiments.
In large domains, Monte-Carlo tree search (MCTS) is required to estimate the values of the states as efficiently and accurately as possible. However, the standard update rule in backpropagation assumes a stationary distribution for the returns, and particularly in min-max trees, convergence to the true value can be slow because of averaging. We present two methods, Softmax MCTS and Monotone MCTS, which generalize previous attempts to improve upon the backpropagation strategy. We demonstrate that both methods reduce to finding optimal monotone functions, which we do so by performing Bayesian optimization with a Gaussian process (GP) prior. We conduct experiments on computer Go, where the returns are given by a deep value neural network, and show that our proposed framework outperforms previous methods.