2
$\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$

Your Answer

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

Browse other questions tagged or ask your own question.