Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees
Authors: Tomer Massas, Vadim Indelman
Organizations: Faculty of Electrical and Computer Engineering, Technion – Israel Institute of Technology · Stephen B. Klein Faculty of Aerospace Engineering, Technion – Israel Institute of Technology · Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology
MDP planners often rely on nominal transition models that may differ from the true dynamics. Robust MDP planning accounts for this uncertainty through a set of admissible models, but doing so with limited online computation is challenging: the search tree grows exponentially with the horizon and each robust backup requires an additional optimization. Existing online robust methods remain limited in scale and offer at most probabilistic guarantees. We introduce, to the best of our knowledge, the first deterministic anytime guarantees for robust online MDP planning. We restrict computation to the sampled search tree while deterministically bounding the contribution of unsampled trajectories. For any fixed policy, we derive lower and upper bounds on the gap between its projected and true robust values under rectangular and non-rectangular uncertainty sets. Under rectangular uncertainty, we propagate these bounds through the robust Bellman operator to bound the optimal robust value. These bounds are computable from the current sampled tree, hold at every node, tighten as the sampled support expands, and converge to the robust values as full support is recovered. We develop CAR-MCTS, a bound-guided MCTS planner that uses these deterministic bounds to guide exploration, prune provably suboptimal branches, and terminate once the optimal root action is certified. The fixed-policy bounds also yield an anytime policy-evaluation mechanism that certifies the robust value of any policy, independent of how it was obtained. Experiments verify the deterministic bounds, their tightening under support expansion, substantial branch pruning, root-action certification, and convergence to the optimal robust policy. To our knowledge, this is the first scalable robust MCTS framework with anytime deterministic guarantees for both online planning and policy evaluation, without enumerating the full state space.
Figure 1: Deterministic certificates: fixed-policy evaluation and CAR-MCTS planning.
Figure 2: CAR-MCTS vs. robust planning baselines across model mismatch and planning horizons.
Figure 3: Decision time of CAR-MCTS and Robust Power UCT as ∣S∣ grows under full-support transition kernels.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Frozen Lake Map Example
Figure 5: Illustration of the ring transition model used in the Frozen Lake experiments.
Parameter
Fig. 1a
Fig. 1b
Fig. 2
Fig. 3
Grid
8×8
8×8
16×16
(10×10) – (103×103)
H
6
3
{2,5,11}
5
k
1
2
8
2n−1
β
1
1
1
0.39 – 0.99
pslip
0.3
0.2
0.01 – 0.6
0.3
ptrue
–
–
0.05
–
Appendix
Table 1: Configuration of the experiments reported in the main paper.
Figure 6: Success rate at planning depth 3 as the true environment becomes more slippery and the planner-assumed transition model varies. Columns correspond to ptrue∈{0.01,0.1,0.2,0.3} , while the x -axis shows the planner-assumed pslip . The ring radius is k=8 . 500 seeds.
Method
Samples per decision
Relative to MCTS
MCTS methods
60
1×
RSS C=2
584
9.7×
RSS C=3
1884
31.4×
RSS C=4
4368
72.8×
Appendix
Table 2: Transition samples per decision at planning depth 3 .
Figure 7: The same experiment as Figure 6 , with the ring radius reduced from k=8 to k=1 .
Figure 8: Decision time as a function of planning depth. CAR-MCTS and Robust Power UCT use 20 simulations per decision, while RSS uses branching factor C=2 . A 20 -second computation cap is imposed per decision; RSS reaches this limit at depth 6 , and deeper configurations are therefore not evaluated.
Figure 9: Fraction of decisions selecting the action that is optimal under the true transition model. Columns correspond to different values of ptrue , while the x -axis varies the planner-assumed pslip . The true model is used only for evaluation.
Figure 10: Root-action certification rate (top) and branch-pruning rate (bottom) for different grid sizes, planning budgets, and values of pslip .
Monte Carlo Tree Search (MCTS) is a powerful framework for solving complex decision-making problems, yet it often relies on the assumption that the simulator and the real-world dynamics are identical. Although this assumption helps achieve the success of MCTS in games like Chess, Go, and Shogi, the real-world scenarios incur ambiguity due to their modeling mismatches in low-fidelity simulators. In this work, we present a new robust variant of MCTS that mitigates dynamical model ambiguities. Our algorithm addresses transition dynamics and reward distribution ambiguities to bridge the gap between simulation-based planning and real-world deployment. We incorporate a robust power mean backup operator and carefully designed exploration bonuses to ensure finite-sample convergence at every node in the search tree. We show that our algorithm achieves a convergence rate of O(n−1/2) for the value estimation at the root node, comparable to that of standard MCTS. Finally, we provide empirical evidence that our method achieves robust performance in planning problems even under significant ambiguity in the underlying reward distribution and transition dynamics.
Tuan Dam, Kishan Panaganti, Brahim Driss +1
Hanoi University of Science and Technology, Hanoi, Vietnam · Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL
This paper presents a finite-time analysis for Monte Carlo Tree Search (MCTS) in Partially Observable Markov Decision Processes (POMDPs), with probabilistic concentration bounds in both discrete and continuous observation spaces. While MCTS-style solvers such as POMCP achieve empirical success in many applications, rigorous finite-time guarantees remain an open problem due to the nonstationarity and the interdependencies induced by heuristic action selection (e.g., UCB). In the discrete setting, we address these challenges by extending the polynomial exploration bonus to UCB in POMDP setting, yielding polynomial concentration bounds for the empirical value estimation at the root node. For continuous observation spaces, we introduce an abstract partitioning framework and propose a finite-time bound on partitioning loss. Under mild conditions, we prove highprobability bound on value estimates in POMDPs with continuous observation space. Specifically, we propose Voro-POMCPOW, a variant of POMCPOW with f inite-time guarantees that adaptively partitions the continuous observation space using Voronoi cells. This approach maintains a finite branching factor while preserving the original observation generator. Empirical validation demonstrates that the proposed Voro-POMCPOW shows competitive performance while providing theoretical guarantees. Although our analysis focuses on continuous POMDPs, the techniques developed herein are also applicable to continuous MDPs, closing another gap on the MDP side.
Da Kong, Vadim Indelman
Technion Autonomous Systems Program (TASP) · Technion – Israel Institute of Technology · Stephen B. Klein Faculty of Aerospace Engineering +1
You are a robot and you live in a Markov decision process (MDP) with a finite or an infinite number of transitions from state-action to next states. You got brains and so you plan before you act. Luckily, your roboparents equipped you with a generative model to do some Monte-Carlo planning. The world is waiting for you and you have no time to waste. You want your planning to be efficient. Sample-efficient. Indeed, you want to exploit the possible structure of the MDP by exploring only a subset of states reachable by following near-optimal policies. You want guarantees on sample complexity that depend on a measure of the quantity of near-optimal states. You want something, that is an extension of Monte-Carlo sampling (for estimating an expectation) to problems that alternate maximization (over actions) and expectation (over next states). But you do not want to StOP with exponential running time, you want something simple to implement and computationally efficient. You want it all and you want it now. You want TrailBlazer.
Jean-Bastien Grill, Michal Valko, Rémi Munos
SequeL team, INRIA Lille - Nord Europe, France · Google DeepMind, UK∗