6
$\begingroup$

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

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?
$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ > "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? $\endgroup$
    – Neal Young
    Commented Jul 24, 2022 at 21:00
  • $\begingroup$ 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! $\endgroup$
    – Zach
    Commented Aug 8, 2022 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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