Geordie Rose’s Post

No, p(\text{win} | S, a) under a random policy in MCTS does not converge to Q(S, a) under an optimal policy. Random policies reflect outcomes of random play, not optimal play. To approximate Q(S, a) , use heuristics or learning policies that better approximate good play, improving the simulation quality and making p(\text{win} | S, a) closer to Q(S, a) .

Geordie Rose In theory, if MCTS were run with infinite simulations and a perfect exploration strategy, it would asymptotically approximate the optimal policy. However, this is impractical in most real-world scenarios. The raw probabilities from random rollouts shouldn't be expected to directly converge to optimal Q-values. The strength of MCTS comes from its ability to focus computational resources on promising lines of play through iterative refinement, rather than from the direct estimation of optimal action values through random sampling.

There are some convergence theorems and most of them conclude the same. To ensure convergence in RL algorithms, certain conditions must be met. One of these conditions concerns the learning factor. Specifically: - The sum of the learning factors over time must equal to infinity. - The sum of the squares of the learning factors must be less than infinity. These conditions ensure that, over time, the algorithm can make significant adjustments (due to the first condition) but that these adjustments become smaller and more stable (due to the second condition). For these conditions to be satisfied, it is necessary to visit all possible states and actions infinitely no matter the policy. This follows from the law of large numbers, which guarantees that, by repeatedly visiting all states and actions, the estimates of transition probabilities and rewards approach their true values.

In a zero-sum two-player game, the probabilities p(win|S, a) obtained from random rollouts in MCTS can be good approximators of Q(s, a). While the exact numerical values may not match, the more simulations you run, the closer these probabilities will approximate Q(s, a). MCTS focuses on promising actions based on these probabilities, which helps in approximating the optimal policy π(s). Theoretically, with infinite compute and perfect exploration, the probabilities p(win|S, a) under random policy would match the quality Q(s, a) under the optimal policy. This is because infinite simulations would allow the MCTS to explore all possible outcomes comprehensively, leading to the convergence of p(win|S, a) to the true Q(s, a). However, in real-world scenarios with finite resources, the raw probabilities from random rollouts may not directly converge to optimal Q-values.