0
$\begingroup$

How fast does Monte Carlo Tree Search converge? Is there proof that it does converge?

How does it compare to Temporal Difference learning in terms of convergence speed (assuming the evaluation step is a bit slow)?

Is there a way to exploit the information gathered during the simulation phase to accelerate MCTS?

Sorry if too many questions, if you have to choose one, please choose the last question.

$\endgroup$
2
$\begingroup$

Yes, Monte Carlo tree search (MCTS) has been proven to converge to optimal solutions, under assumptions of infinite memory and computation time. That is, at least for the case of perfect-information, deterministic games / MDPs.

Maybe some other problems were covered too by some proofs (I could intuitively imagine the proofs holding up for non-deterministic games as well, depending on implementation details)... but the classes of problems I mentioned above are what I'm sure about. The initial, classic proofs can be found in:

Much more recently the paper On Reinforcement Learning Using Monte Carlo Tree Search with Supervised Learning: Non-Asymptotic Analysis appeared on arXiv, in which I saw it is mentioned that there may have been some flaws in those original papers, but they also seem to be able to fix it and add more theory for the more "modern" variants which combine (deep) learning approaches inside MCTS.


It should be noted that, as is typically the case, all those convergence proofs are for the case where you spend an infinite amount of time running your algorithm. In the case of MCTS, you can intuitively think of the proofs only starting to hold once your algorithm has manage to build up the complete search tree, and then on top of that had sufficient time to run through all the possible paths in the tree sufficiently often for the correct values to backpropagate. This is unlikely to be realistic for most interesting problems (and if it is feasible, a simpler breadth-first search algorithm may be a better choice).


How does it compare to Temporal Difference learning in terms of convergence speed (assuming the evaluation step is a bit slow)?

If you're thinking of a standard, tabular TD learning approach like Sarsa... such approaches actually turn out to be very closely related to MCTS. In terms of convergence speed, I'd say the important differences are:

  • MCTS focusses on "learning" for a single state, the root state; all efforts are put towards obtaining an accurate value estimate for that node (and its direct children), whereas typical TD implementations are about learning immediately for the complete state-space. I suppose the "focus" of MCTS could improve its convergence speed for that particular state...
  • but the fact that the search tree (which can be viewed as its "table" of $Q$-values as you'd see in Sarsa or $Q$-learning) only slowly grows can also be a disadvantage, in comparison to tabular TD learning approaches which start out with a complete table that covers the complete state space.

Note that papers such as the last one I linked above show how MCTS can also actually use Temporal Difference learning for its backing up of values through the tree... so looking at it from a "MCTS vs TD learning" angle doesn't really make too much sense when you consider that TD learning can be used inside MCTS.


Is there a way to exploit the information gathered during the simulation phase to accelerate MCTS?

There are lots and lots of ideas like that tend to improve performance empirically. It will be difficult to say much about them in theory though. Some examples off the top of my head:

  • All Moves As First (AMAF)
  • Rapid Action Value Estimation (RAVE, also see GRAVE)
  • Move Average Sampling Technique (MAST)
  • N-Gram Selection Technique (NST)
  • Last-Good-Reply policy
  • ...

Many of them can be found in this survey paper, but it is somewhat old now (from 2012), so it doesn't include all the latest stuff.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.