Planning problems are among the most important and well-studied problems in artificial intelligence. They are most typically solved by tree search algorithms that simulate ahead into the future, evaluate future states, and back-up those evaluations to the root of a search tree. Among these algorithms, Monte-Carlo tree search (MCTS) is one of the most general, powerful and widely used. A typical implementation of MCTS uses cleverly designed rules, optimised to the particular characteristics of the domain. These rules control where the simulation traverses, what to evaluate in the states that are reached, and how to back-up those evaluations. In this paper we instead learn where, what and how to search. Our architecture, which we call an MCTSnet, incorporates simulation-based search inside a neural network, by expanding, evaluating and backing-up a vector embedding. The parameters of the network are trained end-to-end using gradient-based optimisation. When applied to small searches in the well-known planning problem Sokoban, the learned search algorithm significantly outperformed MCTS baselines.
This paper designs a deep learning architecture that mimics the structure of the well-known MCTS algorithm. From gold standard state-action pairs, it learns each component of this architecture in order to predict similar actions.
I enjoyed reading this paper. The presentation is very clear, the design of the architecture is beautiful, and I was especially impressed with the related work discussion that went back to identify other game search and RL work that attempts to learn parts of the search algorithm. Nice job overall.
The main flaw of the paper is in its experiments. If I understand them correctly, the comparison is between a neural network that has been learned on 250,000 trajectories of 60 steps each where each step is decided by a ground truth close-to-optimal algorithm, say MCTS with 1000 rollouts (is this mentioned in the paper). That makes for a staggering 15 billion rollouts of prior data that goes into the MCTSNet model. This is compared to 25 rollouts of MCTS that make the decision for the baseline. I suspect that generating the training data and learning the model takes an enormous amount of CPU time, while 25 MCTS rollouts can probably be done in a second or two. I'm sure I'm misinterpreting some detail here, but how is this a fair comparison?
Would it be fair to have a baseline that learns the MCTS coefficient on the training data? Or one that uses the value function that was learned with classic search? I find it difficult to understand the details of the experimental setup, and maybe some of these experiments are reported. Please clarify. Also: colors are not distinguishable in grey print.
How would the technique scale with more MCTS iterations? I suspect that the O(N^2) complexity is very prohibitive and will not allow this to scale up?
I'm a bit worried about the idea of learning to trade off exploration and exploitation. In the end you'll just allow for the minimal amount of exploration to solve the games you've already seen. This seems risky, and I suspect that UCB and more statistically principled approaches would be more robust in this regard?
Are these Sokoban puzzles easy for classical AI techniques? I know that many of them can be solved by A* search with a decent heuristic. It would be fair to discuss this.
The last sentence of conclusions is too far reaching; there is really no evidence for that claim.