For UCT (Upper Confidence bounds applied to Trees), why If given infinite time and memory, UCT theoretically converges to Minimax. ?

Besides, I do not quite understand how UCT deals with the flaw of Monte-Carlo Tree Search, when a program may favor a losing move with only one or a few forced refutations, but due to the vast majority of other moves provides a better random playout score than other, better moves.


This result is stated in:

  • Kocsis, L., & Szepesvári, C. (2006, September). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Springer, Berlin, Heidelberg.

It is the content of Theorems 5 & 6. Sadly there is no detailed proof for theorem 5.

The main reference for this is:

  • Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3), 235-256.

To give you some intuition about the convergence given infinite time, you need to understand the UCB1 formula: it makes a tradeoff between exploring the best move and exploring the least explored moves. As the term for exploring the least explored move can grow arbitrariy large and the payoff is smaller than 1, if you have infinite time, you will end up exploring it infinitely many times, even if its payoff is $0$.

Therefore, at a fixed node, given infinite time, you will explore infinitely many times each possible move. Repeat this by induction : you will explore the whole tree in infinite time. So in the end, what actually matters is the score of each node, as the exploration bias will go to $0$.

In short : what removes the MCTS flaw is the fact that you have infinitely many moves, it removes the randomness.

  • $\begingroup$ ok, what do you think is the purpose of the red box in this UCT node traversal mechanism ? $\endgroup$
    – kevin
    Jul 15 '19 at 3:18
  • $\begingroup$ What do you exactly mean by payoff is bounded by 1 ? $\endgroup$
    – kevin
    Jul 15 '19 at 4:16
  • $\begingroup$ What I call payoff is the quantity $x_i/n_i$, number of wins divided by the number of visits, and as $x_i \leq n_i$, the payoff is bounded above by 1. $\endgroup$
    – GBat
    Aug 8 '19 at 17:56
  • $\begingroup$ That might be unclear : I meant smaller than 1. $\endgroup$
    – GBat
    Aug 8 '19 at 17:57

Your Answer

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

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