Polynomial Regret Concentration of UCB for Non-Deterministic State Transitions

Can Cömer, Jannis Blüml, Cedric Derstroff, Kristian KerstingarXiv 2025 · DOI · arXiv

Abstract

Monte Carlo Tree Search (MCTS) has demonstrated remarkable empirical success in complex decision-making tasks, yet theoretical guarantees for its performance in stochastic environments have remained elusive. This paper provides the first formal proof that MCTS maintains polynomial regret concentration in environments with non-deterministic state transitions. By extending existing frameworks for deterministic games, we demonstrate that MCTS converges to optimal decisions even when actions yield probabilistic outcomes. Our findings are validated through experiments on the FrozenLake benchmark, confirming that regret predictably concentrates as the number of simulations increases.

Introduction

The success of MCTS in "perfect information" games like Chess and Go is well-documented. However, real-world applications—ranging from autonomous driving to financial modeling—are rarely deterministic. In these domains, an action does not lead to a single certain state but rather a distribution of possible states influenced by environmental noise.

While MCTS is frequently applied to these stochastic problems, the theoretical foundation for its convergence was previously limited to deterministic settings. Specifically, a rigorous mathematical proof was lacking to show that "regret"—the difference between the reward of the optimal policy and the algorithm's chosen action—concentrates around zero at a predictable rate under non-deterministic transitions. This paper bridges this gap, providing the necessary guarantees for safety-critical applications where reliability must be quantified.

Methodology: Analyzing Stochastic Trees

The core contribution of this work is the extension of regret bounds from deterministic MCTS to non-deterministic, non-stationary Multi-Armed Bandits (MABs). The analysis decomposes the search process into two distinct phases:

  1. The Selection Phase: Evaluating how the Upper Confidence Bound (UCB) algorithm selects an action based on current estimates.
  2. The Transition Phase: Modeling the stochastic "jump" to the next state following an action.
The hierarchical structure of the MCTS tree under stochastic transitions, illustrating the selection and transition phases.

By employing an induction argument across the layers of the search tree, we prove that if rewards at the leaf nodes are well-behaved, the polynomial regret concentration property is preserved up to the root. This holds true even with fixed transition probabilities between states, effectively treating environmental randomness as an additional layer within the bandit framework.

Experimental Validation

To validate the theoretical findings, we conducted experiments using the FrozenLake environment (4x4 grid) from the Gymnasium library. In this benchmark, an agent must navigate to a goal while avoiding holes on a slippery surface. The environment is highly stochastic: a chosen move has only a 1/3 probability of success, with a 2/3 probability of drifting in a perpendicular direction.

The agent receives a reward of 1 for reaching the goal and 0 otherwise. We evaluated the performance of MCTS across a range of simulations, from $n = 2^{10}$ to $n = 2^{20}$.

Results and Discussion

Our empirical results align closely with the derived theoretical bounds. As the number of simulations $n$ increases, we observe two primary trends:

  1. Performance Improvement: The discounted return increases steadily, reflecting the algorithm's improving policy.
  2. Regret Concentration: Most importantly, the regret not only decreases but exhibits "concentration." As shown in the figure below, the variance between different random seeds diminishes significantly as $n$ grows, confirming that the algorithm's performance becomes more predictable and reliable.
Regret vs. number of simulations $n$. The narrowing error bars demonstrate the polynomial concentration of regret as the simulation budget increases.

These results highlight a critical distinction in MCTS theory: while earlier literature suggested exponential concentration might be possible, such bounds typically only apply to the bottom of the tree. To maintain stability across the entire tree structure, a polynomial exploration bonus in the UCB formula is required to maintain theoretical stability.

Conclusion and Future Work

This research establishes a solid theoretical footing for MCTS in stochastic environments. By proving polynomial regret concentration, we provide a mathematical basis for trusting MCTS in complex, non-deterministic domains.

However, several challenges remain. Our current proof assumes fixed transition probabilities; future work should address non-stationary transitions where environment dynamics evolve over time. Additionally, the computational cost of determining optimal constants for the exploration bonus remains high, necessitating further research into practical heuristics. Scaling these proofs to high-horizon, high-complexity domains like high-frequency trading will be a key area for future investigation.

Summary updated

Abstract

Monte Carlo Tree Search (MCTS) has proven effective in solving decision-making problems in perfect information settings. However, its application to stochastic and imperfect information domains remains limited. This paper extends the theoretical framework of MCTS to stochastic domains by addressing non-deterministic state transitions, where actions lead to probabilistic outcomes. Specifically, building on the work of Shah et al. (2020), we derive polynomial regret concentration bounds for the Upper Confidence Bound algorithm in multi-armed bandit problems with stochastic transitions, offering improved theoretical guarantees. Our primary contribution is proving that these bounds also apply to non-deterministic environments, ensuring robust performance in stochastic settings. This broadens the applicability of MCTS to real-world decision-making problems with probabilistic outcomes, such as in autonomous systems and financial decision-making.
BibTeX
@misc{comer2025polynomial,
  author = {Can Cömer and Jannis Blüml and Cedric Derstroff and Kristian Kersting},
  title = {{Polynomial Regret Concentration of UCB for Non-Deterministic State Transitions}},
  year = {2025},
  eprint = {2502.06900},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.06900},
}
Figure