Abstract
Monte-Carlo Tree Search (MCTS) is a cornerstone of modern artificial intelligence, yet its theoretical foundations in stochastic environments remain underdeveloped. Traditional MCTS variants, such as UCT, often suffer from estimation biases and sub-optimal exploration strategies when applied to Markov Decision Processes (MDPs). This paper introduces Stochastic-Power-UCT, an algorithm that utilizes a power mean estimator for value backups and a polynomial exploration bonus. We provide the first rigorous proof of polynomial convergence for this class of algorithms in stochastic environments and demonstrate its empirical superiority across several benchmarks.
Introduction
Monte-Carlo Tree Search (MCTS) has achieved remarkable success in complex decision-making tasks, most notably in the domain of board games like Go and Chess. However, the transition from deterministic environments to stochastic ones—where actions lead to random outcomes—presents significant theoretical and practical challenges.
The standard Upper Confidence Bound for Trees (UCT) algorithm relies on a logarithmic exploration bonus. While widely used, this approach has been shown to possess theoretical flaws regarding the balance of exploration and exploitation over time. Furthermore, the common practice of using a simple arithmetic mean to estimate state values often leads to underestimation of the optimal value, while taking the maximum can lead to overestimation. This paper addresses these gaps by proposing a theoretically grounded and empirically robust framework for stochastic MCTS.
Methodology
The Stochastic-Power-UCT Algorithm
Stochastic-Power-UCT deviates from "vanilla" MCTS through two primary innovations designed to stabilize value estimation and ensure convergence in stochastic MDPs.
1. The Power Mean Estimator
Instead of the standard arithmetic mean, the algorithm employs a power mean to back up values within the search tree. The estimator is defined by a parameter $p$, allowing it to interpolate between different statistical behaviors:
- When $p=1$, the estimator behaves as a standard (often pessimistic) average.
- As $p \to \infty$, the estimator approaches the (often optimistic) maximum.
Empirical analysis suggests that $p=2$ (the root mean square) provides a "Goldilocks" balance, effectively focusing the search on promising branches without being overly sensitive to stochastic outliers.
2. Polynomial Exploration Bonus
Traditional UCT uses a logarithmic bonus of the form $\sqrt{\log(n)/n}$. Stochastic-Power-UCT replaces this with a polynomial exploration bonus. This shift is mathematically critical; the polynomial bonus better accounts for the non-stationary nature of the rewards at each node as the search tree expands. This adjustment allows for a rigorous inductive proof over the tree depth, establishing that the value estimate at the root converges to the optimal value at a rate of $O(n^{-1/2})$, where $n$ is the number of trajectories.
Experimental Evaluation
Environments
The proposed algorithm was evaluated against standard UCT and Fixed-Depth-MCTS across three distinct environments:
- SyntheticTree: A controlled benchmark allowing for the manipulation of depth, branching factors, and transition noise.
- FrozenLake (4x4 and 8x8): A classic OpenAI Gym stochastic grid-world where agents must navigate slippery surfaces.
- Taxi: A complex task requiring the agent to pick up and drop off passengers amidst stochastic transitions.
Key Results
The experiments yielded several significant insights:
- Performance Gains: Stochastic-Power-UCT consistently outperformed baselines in the SyntheticTree benchmarks across various configurations. In the FrozenLake 8x8 environment, the algorithm achieved higher success rates with fewer simulations than vanilla UCT.
- Optimal Parameterization: Testing confirmed that $p$ values between 2.0 and 2.2 generally yielded the highest discounted total rewards, validating the use of the power mean over simple averaging.
- Theoretical Alignment: The polynomial bonus, while necessary for the mathematical proof, also proved to be highly effective in practical application, bridging the gap between theoretical requirements and empirical performance.
Discussion and Limitations
While Stochastic-Power-UCT represents a significant step forward, certain limitations remain. The current convergence proof assumes a fixed maximum search depth ($H$), whereas many real-world applications utilize dynamic tree expansion. Additionally, the power mean calculation introduces a minor computational overhead compared to simple arithmetic averaging, though this is typically negligible compared to the cost of environment simulations or neural network evaluations.
Conclusion
Stochastic-Power-UCT provides a robust framework for MCTS in stochastic environments. By combining a power mean backup operator with a polynomial exploration bonus, the algorithm achieves both theoretical convergence and superior empirical performance. Future work will explore extending this framework to adversarial zero-sum games and integrating power mean estimators with deep learning-based value functions to tackle high-dimensional state spaces.
Summary updated