<p>According to section 1.2 of <a href="https://arxiv.org/abs/1902.05213" rel="nofollow noreferrer">https://arxiv.org/abs/1902.05213</a>, there is not a published proof of the polynomial convergence rate, and even some of the proofs contained in [2] are not complete. Thus, it seems unlikely that polynomial convergence is achieved by the original UCT algorithm.</p>
<p>Note that the arxiv paper linked above was accepted to a conference as an extended abstract, indicating that the proofs contained in it have likely not been thoroughly peer-reviewed.</p>

CC BY-SA 4.0
2022-07-24T21:00:40.607Z
> "*it seems unlikely that polynomial convergence is achieved by the original UCT algorithm.*"  -- Do you mean unlikely that there is a known proof?  Or do you have some reason to think that there is a class of inputs on which the algorithm does not converge in polynomial time?
Neal Young
CC BY-SA 4.0
2022-08-08T00:10:00.120Z
Shoot. I should have been more precise. I meant the latter. I don't have time to dig in at the moment, but I believe the arxiv paper above may have some evidence that it actually does not. If someone has a bit of time to jump into the arxiv paper and make my answer more clear, that would be great!
Zach
CC BY-SA 4.0
2022-06-24T19:58:43.217Z
2022-06-24T19:58:43.217Z
Zach
<p>This is a question regarding the theoretical convergence guarantees of the UCT algorithm, a popular variation of the Monte Carlo Tree Search algorithm (used in games, planning, reinforcement learning, etc.)</p>
<p>There are two original references, both from 2006, and from the same authors.</p>
<p>[1]. <a href="http://ggp.stanford.edu/readings/uct.pdf" rel="noreferrer">http://ggp.stanford.edu/readings/uct.pdf</a></p>
<p>[2]. <a href="http://old.sztaki.hu/%7Eszcsaba/papers/cg06-ext.pdf" rel="noreferrer">http://old.sztaki.hu/~szcsaba/papers/cg06-ext.pdf</a></p>
<p>The first one states, roughly:</p>
<blockquote>
<p><strong>Theorem 5 [1]:</strong>  UCT converges to the optimal move at a polynomial rate.</p>
</blockquote>
<p>However, it provides no proof due to &quot;lack of space&quot; (most proofs in the paper are omitted). The second paper seems to study the exact same algorithm and states, roughly:</p>
<blockquote>
<p><strong>Theorem 6 [2]:</strong> UCT converges to the optimal move.</p>
</blockquote>
<p>In this case the proof is included. However, below the proof the authors state that they are unable to provide convergence rate estimates.</p>
<p>Now, UCT is widely cited via reference [1] to converge to the optimal move at a polynomial rate. My two questions are the following:</p>
<ol>
<li>Is the proof of polynomial rate convergence available somewhere?</li>
<li>Why do Theorem 5 from [1] and Theorem 6 from [2], together with the comment below it, disagree about the convergence rate?</li>
</ol>

<reference-request><machine-learning><monte-carlo><reinforcement-learning>
Polynomial convergence to optimal move of the UCT algorithm. Missing proof?
Albert Garreta
# Polynomial convergence to optimal move of the UCT algorithm. Missing proof?

(Asked by: username_0 on 2020-09-06)

This is a question regarding the theoretical convergence guarantees of the UCT algorithm, a popular variation of the Monte Carlo Tree Search algorithm (used in games, planning, reinforcement learning, etc.)

There are two original references, both from 2006, and from the same authors.

[1]. <http://ggp.stanford.edu/readings/uct.pdf>

[2]. [http://old.sztaki.hu/~szcsaba/papers/cg06-ext.pdf](http://old.sztaki.hu/%7Eszcsaba/papers/cg06-ext.pdf)

The first one states, roughly:

> **Theorem 5 [1]:** UCT converges to the optimal move at a polynomial rate.

However, it provides no proof due to "lack of space" (most proofs in the paper are omitted). The second paper seems to study the exact same algorithm and states, roughly:

> **Theorem 6 [2]:** UCT converges to the optimal move.

In this case the proof is included. However, below the proof the authors state that they are unable to provide convergence rate estimates.

Now, UCT is widely cited via reference [1] to converge to the optimal move at a polynomial rate. My two questions are the following:

1. Is the proof of polynomial rate convergence available somewhere?
2. Why do Theorem 5 from [1] and Theorem 6 from [2], together with the comment below it, disagree about the convergence rate?

**Tags:** reference-request, machine-learning, monte-carlo, reinforcement-learning

---

## 1 answers

### Answer by username_1 on 2022-06-24. Score: 2

According to section 1.2 of <https://arxiv.org/abs/1902.05213>, there is not a published proof of the polynomial convergence rate, and even some of the proofs contained in [2] are not complete. Thus, it seems unlikely that polynomial convergence is achieved by the original UCT algorithm.

Note that the arxiv paper linked above was accepted to a conference as an extended abstract, indicating that the proofs contained in it have likely not been thoroughly peer-reviewed.

> **Comments:**
> **username_2**: > "*it seems unlikely that polynomial convergence is achieved by the original UCT algorithm.*"  -- Do you mean unlikely that there is a known proof?  Or do you have some reason to think that there is a class of inputs on which the algorithm does not converge in polynomial time?  
> **username_1**: Shoot. I should have been more precise. I meant the latter. I don't have time to dig in at the moment, but I believe the arxiv paper above may have some evidence that it actually does not. If someone has a bit of time to jump into the arxiv paper and make my answer more clear, that would be great!  

---

