# Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guarantees

arXiv: https://arxiv.org/abs/2508.05441 · HTML: https://mlsanity.com/paper/2508.05441/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 54 references that are in the map.
- First posted on arXiv 7 Aug 2025.

## Builds on (most cited first, 29 of 29)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [A Survey on Model-based Reinforcement Learning](https://mlsanity.com/paper/2206.09328/) (2022)
- [Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret](https://mlsanity.com/paper/2006.13827/) (2020)
- [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023)
- [Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR](https://mlsanity.com/paper/2302.03201/) (2023)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Cooperation-Aware Reinforcement Learning for Merging in Dense Traffic](https://mlsanity.com/paper/1906.11021/) (2019)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [Modeling Other Players with Bayesian Beliefs for Games with Incomplete Information](https://mlsanity.com/paper/2405.14122/) (2024)
- [Constrained Risk-Averse Markov Decision Processes](https://mlsanity.com/paper/2012.02423/) (2020)
- [Network Diffuser for Placing-Scheduling Service Function Chains with Inverse Demonstration](https://mlsanity.com/paper/2501.05673/) (2025)
- [Learning from Random Demonstrations: Offline Reinforcement Learning with Importance-Sampled Diffusion Models](https://mlsanity.com/paper/2405.19878/) (2024)
- [Lipschitz Lifelong Monte Carlo Tree Search for Mastering Non-Stationary Tasks](https://mlsanity.com/paper/2502.00633/) (2025)
- [C-MCTS: Safe Planning with Monte Carlo Tree Search](https://mlsanity.com/paper/2305.16209/) (2023)
- [Cooperative Backdoor Attack in Decentralized Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2405.15245/) (2024)
- [Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processes](https://mlsanity.com/paper/2002.12086/) (2020)
- [Monte Carlo Tree Search Algorithms for Risk-Aware and Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2211.13032/) (2022)
- [Advantage Actor-Critic with Reasoner: Explaining the Agent's Behavior from an Exploratory Perspective](https://mlsanity.com/paper/2309.04707/) (2023)
- [Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves](https://mlsanity.com/paper/2412.13962/) (2024)
- [A Cluster-Based Weighted Feature Similarity Moving Target Tracking Algorithm for Automotive FMCW Radar](https://mlsanity.com/paper/2112.06388/) (2021)

## Built on by (most cited first, 4 of 4)

- [Agent Alpha: Tree Search Unifying Generation, Exploration and Evaluation for Computer-Use Agents](https://mlsanity.com/paper/2602.02995/) (2026)
- [Cochain Perspectives on Temporal-Difference Signals for Learning Beyond Markov Dynamics](https://mlsanity.com/paper/2602.06939/) (2026)
- [Operator-Guided Invariance Learning for Continuous Reinforcement Learning](https://mlsanity.com/paper/2605.06500/) (2026)
- [Metric-Gradient Projection for Stable Multi-Agent Policy Learning](https://mlsanity.com/paper/2605.18809/) (2026)

## Abstract (arXiv)

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 α achieves explicit tail-risk control over the expected loss in the "worst (1-α)% 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 P_varepsilons(s,a) with radius varepsilons 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.