Does Monte Carlo tree search qualify as machine learning?

Question

To the best of my understanding, the Monte Carlo tree search (MCTS) algorithm is an alternative to minimax for searching a tree of nodes. It works by choosing a move (generally, the one with the highest chance of being the best), and then performing a random playout on the move to see what the result is. This process continues for the amount of time allotted.

This doesn't sound like machine learning, but rather a way to traverse a tree. However, I've heard that AlphaZero uses MCTS, so I'm confused. If AlphaZero uses MCTS, then why does AlphaZero learn? Or did AlphaZero do some kind of machine learning before it played any matches, and then use the intuition it gained from machine learning to know which moves to spend more time playing out with MCTS?

Answer 1

Monte Carlo Tree Search is not usually thought of as a machine learning technique, but as a search technique. There are parallels (MCTS does try to learn general patterns from data, in a sense, but the patterns are not very general), but really MCTS is not a suitable algorithm for most learning problems.

AlphaZero was a combination of several algorithms. One was MCTS, but MCTS needs a function to tell it how good different states of the game might be (or else, it needs to simulate entire games). One way to handle this function in a game like chess or Go is to approximate it by training a neural network, which is what the Deep Mind researchers did. This is the learning component of AlphaZero.

Answer 2

John's answer is correct in that MCTS is traditionally not viewed as a Machine Learning approach, but as a tree search algorithm, and that AlphaZero combines this with Machine Learning techniques (Deep Neural Networks and Reinforcement Learning).

However, there are some interesting similarities between MCTS itself and Machine Learning. In some sense, MCTS attempts to "learn" the value of nodes from experience generated through those nodes. This is very similar to how Reinforcement Learning (RL) works (which itself is typically described as a subset of Machine Learning).

Some researchers have also experimented with replacements for the traditional Backpropagation phase of MCTS (which, from an RL point-of-view, can be described as implementing a Monte-Carlo backups) based on other RL methods (e.g., Temporal-Difference backups). A comprehensive paper describing these sorts of similarities between MCTS and RL is: On Monte Carlo Tree Search and Reinforcement Learning.

Also note that the Selection phase of MCTS is typically treated as a sequence of small Multi-Armed Bandit problems, and those problems also have strong connections with RL.

---

TL;DR: MCTS is not normally viewed as a Machine Learning technique, but if you inspect it closely, you can find lots of similarities with ML (in particular, Reinforcement Learning).

Answer 3

Welcome to the mine-field of semantic definitions within AI! According to Encyclopedia Britannica ML is a “discipline concerned with the implementation of computer software that can learn autonomously.” There are a bunch of other definitions for ML but generally they are all this vague, saying something about “learning”, “experience”, “autonomous”, etc. in varying order. There is no well-known benchmark definition that most people use, so unless one wants to propose one, whatever one posts on this needs to be backed up by references.

According to Encyclopedia Britannica’s definition the case for calling MCTS part of ML is pretty strong (Chaslot, Coulom’s et al. work from 2006-8 is used for the MCTS reference). There are two policies used in MCTS, a tree-policy and a simulation-policy. At decision time the tree-policy updates action-values by expanding the tree structure and backing up values from whatever it finds from search. There is no hard-coding on which nodes should be selected/expanded; it all comes from maximizing rewards from statistics. The nodes closer to the root appear more and more intelligent as they “learn” to mimic distributions/state and/or action-values from the corresponding ones from reality. Whether this can be called “autonomous” is an equally difficult question because in the end it’s humans who wrote the formulas/theory MCTS uses. 50 years from now it may not be called autonomous, or ML, but today it would probably at least "qualify".