Polynomial convergence to optimal move of the UCT algorithm. Missing proof?

Question

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?

Answer 1

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.