Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guarantees
Zuyuan Zhang, Arnob Ghosh, Tian Lan · 2025
Read Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guarantees by Zuyuan Zhang, Arnob Ghosh, Tian Lan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05441.txt.
Introduction
Zuyuan Zhang and co-authors make Monte Carlo tree search, a planning method for games and robots, safer against rare bad outcomes. Planning by average return can hide extreme losses, a real risk in high stakes tasks. Past fixes use rough risk scores or hard cost caps, with no firm tail promise.
Their 2025 paper gives two variants. One builds a tail risk measure called CVaR into the search, which caps expected loss in the worst slice of cases. The other adds a Wasserstein buffer around the risk guess to fix bias from few samples. Both carry proof backed safety promises at a set confidence level, plus regret bounds. Tests beat baselines on reward and stability.
Catalog record
| CREATOR | Zuyuan Zhang, Arnob Ghosh, Tian Lan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05441
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guarantees Zuyuan Zhang, Arnob Ghosh, Tian Lan Abstract Making decisions with respect to just the expected returns in Monte Carlo Tree Search (MCTS) cannot account for the potential range of high-risk, adverse outcomes associated with a decision. To this end, safety-aware MCTS often consider some constrained variants – by introducing some form of mean risk measures or hard cost thresholds. These approaches fail to provide rigorous tail-safety guarantees with respect to extreme or high- risk outcomes (denoted as tail-risk), potentially resulting in serious consequence in high-stake scenarios. This paper addresses the problem by developing two novel solutions. We first propose CVaR-MCTS, which embeds a coherent tail risk measure, Conditional Value-at-Risk (CVaR), into MCTS. Our CVaR-MCTS with parameter α \alpha achieves explicit tail-risk control over the expected loss in the "worst ( 1 − α ) % (1-\alpha)\% scenarios." Second, we further address the estimation bias of tail-risk due to limited samples. We propose Wasserstein-MCTS (or W-MCTS) by introducing a first-order Wasserstein ambiguity set 𝒫 ε s ( s , a ) \mathcal{P}_{\varepsilon_{s}}(s,a) with radius ε s \varepsilon_{s} to characterize the uncertainty in tail-risk estimates. We prove PAC tail-safety guarantees for both CVaR-MCTS and W-MCTS and establish their regret. Evaluations on diverse simulated environments demonstrate that our proposed methods outperform existing baselines, effectively achieving robust tail-risk guarantees with improved rewards and stability. 1 Introduction Monte - Carlo Tree Search (MCTS) has delivered state - of - the - art performance in a variety of sequential decision - making domains, including board games [ 1 , 2 , 3 ] , real - time strategy games [ 4 ] , and robotic or classical planning tasks [ 5 , 6 , 7 ] . Its success stems from a principled balance of exploration and exploitation—typically realized via UCT - style selection rules—together with sample - efficient simulation, expansion, and back - propagation phases. Standard MCTS, however, optimizes expected return only; it is blind to rare but catastrophic cost or safety. Ignoring such tail-risk cost can be disastrous in safety - critical settings, e.g. autonomous driving [ 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 ] or medical decision support [ 18 , 19 , 20 ] , where a single high - impact failure cost may outweigh many high successes. Addressing this limitation calls for MCTS variants that reason explicitly about the extreme end of the return distribution on the cost in addition to the average reward. Recent work on constrained Markov decision processes (CMDPs) seeks to maximise expected reward while keeping the long - run average cost below a prescribed threshold. Although useful, this risk - neutral criterion offers no protection against low - probability, high - impact losses—the tail of the cost distribution that matters most in safety - critical settings. A few papers have begun to study risk - constrained MDPs, but current algorithms lack finite - time performance guarantees and, crucially, have not been integrated with MCTS. Within the MCTS literature itself, several so - called Constrained MCTS (C - MCTS) variants have emerged: Threshold - UCT [ 21 ] heuristically prunes branches whose cumulative cost exceeds a hard cap; Cost - Constrained MCTS [ 22 ] trains an offline “safety critic” to veto risky actions; and Distributional MCTS [ 18 ] maximizes a non - linear utility over the return distribution. Though useful, these solutions mostly focus on some form of mean cost or hard cost thresholds, and did not provide rigorous tail-risk guarantees while ensuring sub-linear regret. In this paper, we are focusing on the following question: Can we achieve a sub-linear regret with provable tail-risk satisfaction guarantee for risk-constrained MCTS? Estimating tail - risk metrics—such as Conditional Value - at - Risk (CVaR)—from a finite number of samples is intrinsically challenging, because CVaR depends on the sparsely populated extreme quantiles of the return distribution. On top of that, a viable algorithm must strike a careful balance between maximizing reward and enforcing the risk constraint, further compounding the difficulty. First , we introduce CVaR–MCTS , which incorporates the coherent tail–risk metric Conditional Value–at–Risk (CVaR) [ 23 ] into the UCT search routine. For a user–specified confidence level \alpha\in(0,1) , CVaR evaluates the expected cost conditioned on being in the worst (1-\alpha)\% of outcomes: \operatorname{CVaR}_{\alpha}(Z)\;=\;\mathbb{E}\!\bigl[\,Z\mid Z\,\geq\,\operatorname{VaR}_{\alpha}(Z)\bigr], where Z denotes the random return (or cost) and \operatorname{VaR}_{\alpha}(Z) is the \alpha –quantile. A smaller \alpha probes deeper into the tail, producing a more conservative assessment. Embedding this criterion within MCTS yields decisions that explicitly control extreme losses rather than merely optimizing the mean. CVaR–MCTS employs online Lagrangian dual updates to balance exploration, exploitation, and adherence to the \text{CVaR}_{\alpha} constraint, capping the expected loss in the worst (1-\alpha)\,\% of outcomes. We show that for any \delta\in(0,1) , after T node expansions \Pr\!\bigl[\text{CVaR}_{\alpha}(Z_{T})\leq\text{Threshold}\bigr]\;\geq\;1-\delta, and the algorithm attains a regret of at most \tilde{\mathcal{O}}(\sqrt{T}) , providing finite - time tail - safety with sub - linear regret guarantee. Unfortunately, CVaR-MCTS still relies on quantile estimates from limited samples; in early exploration or when the environment drifts, estimation bias may lead to temporary constraint violations. To curb finite - sample bias, we surround each empirical return distribution with a first - order Wasserstein ball \mathcal{P}_{\varepsilon_{s}}(s,a)=\bigl\{\widetilde{P}:W_{1}(\widetilde{P},\widehat{P}_{N(s)})\leq\varepsilon_{s}\bigr\},\quad\varepsilon_{s}=\varepsilon_{0}/\sqrt{N(s)}, where N(s) is the number of times state s is visited. We then optimize the worst - case CVaR within this set. We show that for any \delta\in(0,1) , \Pr\!\Bigl[\,\sup_{\widetilde{P}\in\mathcal{P}_{\varepsilon_{s}}}\!\text{CVaR}_{\alpha}^{\widetilde{P}}(C_{H})\leq\boldsymbol{\tau}\Bigr]\geq 1-\delta, so W - MCTS remains tail - safe under distributional shifts. Further, The algorithm satisfies \text{Regret}(T)=\tilde{\mathcal{O}}(L_{C}\varepsilon_{0}\sqrt{T}), where L_{C} is the Lipschitz constant dependent on the risk-measure. This tightens as \varepsilon_{s}\!\downarrow with more node visits, preserving CVaR safety satisfaction while maintaining sub - linear regret. In summary, this paper advances state-of-the-art C-MCTS solutions from two aspects: (i) enabling MCTS with PAC tail-safety guarantees by CVaR-MCTS; and (ii) further improving the guarantee under finite samples by W-MCTS with first-order Wasserstein ambiguity sets. The results lay a solid foundation for safely deploying MCTS-based agents in high-stake scenarios. Extensive experiments across various benchmarks validate that our proposed CVaR-MCTS and W-MCTS effectively control tail-risk, consistently outperforming existing risk-sensitive methods in terms of both safety and efficiency. 2 Background Safe RL. Traditional reinforcement learning methods, such as Q-learning [ 24 ] , DQN [ 25 ] , PPO [ 26 ] and so on [ 27 , 28 , 29 , 30 , 31 , 32 , 33 ] , typically focus on reward maximization while ignoring safety factors present in real-world scenarios. While efficient risk-sensitive RLs [ 34 , 35 , 36 ] have been proposed, they again focus on maximizing the tail-risk measures of the reward ignoring the safety constraints. To address this issue, the Constrained Markov Decision Process (CMDP) was proposed and has become the foundation for many SafeRL algorithms. Based on this framework, methods such as Constrained Policy Optimization (CPO) [ 37 ] , Lyapunov-based RL (LRL) [ 38 ] , Primal-dual-based approaches [ 39 , 40 , 41 , 42 , 43 ] , and LP-based approaches [ 41 ] have been proposed. Risk-constrained MDPs have also been considered [ 44 , 45 , 46 , 47 , 48