Answers.Body: <p>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.</p>
  <p>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:</p>
  <ul>
  <li><a href="http://www.sztaki.hu/%7Eszcsaba/papers/ecml06.pdf" rel="nofollow noreferrer">Bandit based Monte-Carlo Planning</a> by Levente Kocsis, Csaba Szepesvári</li>
  <li><a href="http://www.sztaki.hu/%7Eszcsaba/papers/cg06-ext.pdf" rel="nofollow noreferrer">Improved Monte-Carlo Search</a> by Levente Kocsis, Csaba Szepesvári, Jan Willemson</li>
  </ul>
  <p>Much more recently the paper <a href="https://arxiv.org/abs/1902.05213" rel="nofollow noreferrer">On Reinforcement Learning Using Monte Carlo Tree Search with Supervised Learning: Non-Asymptotic Analysis</a> 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 &quot;modern&quot; variants which combine (deep) learning approaches inside MCTS.</p>
  <hr />
  <p>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 <strong>complete search tree</strong>, and then on top of that had sufficient time to run through <strong>all the possible paths in the tree</strong> 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).</p>
  <hr />
  <blockquote>
  <p>How does it compare to Temporal Difference learning in terms of convergence speed (assuming the evaluation step is a bit slow)?</p>
  </blockquote>
  <p>If you're thinking of a standard, tabular TD learning approach like Sarsa... <a href="https://www.jair.org/index.php/jair/article/view/11099" rel="nofollow noreferrer">such approaches actually turn out to be very closely related to MCTS</a>. In terms of convergence speed, I'd say the important differences are:</p>
  <ul>
  <li>MCTS focusses on &quot;learning&quot; 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 &quot;focus&quot; of MCTS could improve its convergence speed for that particular state...</li>
  <li>but the fact that the search tree (which can be viewed as its &quot;table&quot; of <span class="math-container">$Q$</span>-values as you'd see in Sarsa or <span class="math-container">$Q$</span>-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.</li>
  </ul>
  <p>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 &quot;MCTS vs TD learning&quot; angle doesn't really make too much sense when you consider that TD learning can be used inside MCTS.</p>
  <hr />
  <blockquote>
  <p>Is there a way to exploit the information gathered during the simulation phase to accelerate MCTS?</p>
  </blockquote>
  <p>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:</p>
  <ul>
  <li>All Moves As First (AMAF)</li>
  <li>Rapid Action Value Estimation (RAVE, also see GRAVE)</li>
  <li>Move Average Sampling Technique (MAST)</li>
  <li>N-Gram Selection Technique (NST)</li>
  <li>Last-Good-Reply policy</li>
  <li>...</li>
  </ul>
  <p>Many of them can be found in <a href="http://www.incompleteideas.net/609%20dropbox/other%20readings%20and%20resources/MCTS-survey.pdf" rel="nofollow noreferrer">this survey paper</a>, but it is somewhat old now (from 2012), so it doesn't include all the latest stuff.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-07T19:38:23.603Z
Answers.LastActivityDate: 2022-01-13T23:15:13.017Z
Answers.LastEditDate: 2022-01-13T23:15:13.017Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>How fast does Monte Carlo Tree Search converge? Is there a proof that it converges?</p>
  <p>How does it compare to temporal-difference learning in terms of convergence speed (assuming the evaluation step is a bit slow)?</p>
  <p>Is there a way to exploit the information gathered during the simulation phase to accelerate MCTS?</p>
  <p>Sorry if too many questions, if you have to choose one, please choose the last question.</p>
  
Tags: <reinforcement-learning><comparison><monte-carlo-tree-search><convergence><temporal-difference-methods>
Title: How fast does Monte Carlo tree search converge?
UserDisplayName: ATidedHumour
ThreadText: # How fast does Monte Carlo tree search converge?
  
  (Asked by: username_0 on 2019-05-07)
  
  How fast does Monte Carlo Tree Search converge? Is there a proof that it converges?
  
  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.
  
  **Tags:** reinforcement-learning, comparison, monte-carlo-tree-search, convergence, temporal-difference-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-05-07. Score: 4 | Accepted answer
  
  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:
  
  * [Bandit based Monte-Carlo Planning](http://www.sztaki.hu/%7Eszcsaba/papers/ecml06.pdf) by Levente Kocsis, Csaba Szepesvári
  * [Improved Monte-Carlo Search](http://www.sztaki.hu/%7Eszcsaba/papers/cg06-ext.pdf) by Levente Kocsis, Csaba Szepesvári, Jan Willemson
  
  Much more recently the paper [On Reinforcement Learning Using Monte Carlo Tree Search with Supervised Learning: Non-Asymptotic Analysis](https://arxiv.org/abs/1902.05213) 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](https://www.jair.org/index.php/jair/article/view/11099). 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](http://www.incompleteideas.net/609%20dropbox/other%20readings%20and%20resources/MCTS-survey.pdf), but it is somewhat old now (from 2012), so it doesn't include all the latest stuff.
  
  
  ---
  
  