Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search

Quynh Trinh; Trung Nguyen; Nam Nguyen; Tuan Dam

cs.LGOct 16, 2026

Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search

Authors: Quynh Trinh, Trung Nguyen, Nam Nguyen, Tuan Dam

Organizations: Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam

Abstract

Monte-Carlo Tree Search (MCTS) typically stores only scalar mean estimates, which makes it poorly suited for tail-risk objectives such as conditional value-at-risk (CVaR). We introduce Categorical Thompson Sampling with Optimism (CATSO) and Particle Thompson Sampling with Optimism (PATSO), two distributional MCTS algorithms that maintain finite-support empirical backup laws at Q-edges. CATSO represents Q-edge laws with categorical atoms and Dirichlet Thompson sampling, while PATSO represents them with adaptive particles. Both algorithms select actions using the CVaR of a Thompson-sampled Q-edge law plus a polynomial optimism bonus, and propagate scalar continuation values through visit-weighted averages of child Q-edge CVaR scores. For the finite-depth nested CVaR planning target, we prove an $O(n^{-1/2})$ bound on the root value error after $n$ rollouts, which upper-bounds the risk-sensitive simple regret. CATSO adds a fixed-grid discretization bias, while capped PATSO adds a tunable Wasserstein compression bias. Experiments on stochastic planning benchmarks show that distributional Q-edges improve lower-tail return and reduce catastrophic outcomes when mean-optimal and risk-sensitive behavior differ.

Figures & tables

Figure 1: Comparison of CATSO (left) and PATSO (right). Both methods share rollout, expansion, and SimulateV (which backs up scalar V-nodes using a visit-weighted average of child CVaR). They differ in their Q-edge representation ( SimulateQ ): CATSO uses categorical Dirichlet atoms, whereas PATSO uses adaptive weighted particles. SelectAction relies on the CVaR of a Thompson-sampled Q-edge plus a polynomial bonus

B(n,s,a)

(Eq. ( 11 )). For expected-value planning,

\tau=1

Panel of Figure 2 — Figure 2: CVaR planning performance across environments: value gap during planning (top) and return of recommended policies (bottom) with $\pm$ standard deviation.

Figure 3: Catastrophic-event count across evaluation rollouts. Lower is better.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Notation	Meaning
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P},\gamma\rangle$	Discounted MDP with state space $\mathcal{S}$ , action space $\mathcal{A}$ , reward kernel $\mathcal{R}$ , transition kernel $\mathcal{P}$ , and discount $\gamma\in(0,1)$ .
$s_{0}$	Root state of the search tree.
$s_{h}$	State or search-tree node at depth $h$ .
$H$	Finite search depth.
$\mathcal{A}(s)$	Legal actions at state or node $s$ .
$R(s,a,S^{\prime})$	Random reward obtained after taking action $a$ in state $s$ and transitioning to $S^{\prime}$ .

Appendix

Table 1: General notation.

Environment	Algorithm	Hyperparameters
Two-level Risky Treasure	UCT	bias=auto , epsilon=0.5
	MaxUCT	bias=auto , epsilon=0.5
	PowerUCT	bias=auto , epsilon=0.5 , p=2.0
	CATSO	n_atoms=25 , optimism=2.0 , p=1.0 , cvar_tau=0.25
	PATSO	max_particles=128 , optimism=2.0 , p=1.0 , cvar_tau=0.25
Autonomous Vehicle	UCT	bias=10 , epsilon=0.2

Appendix

Table 2: Algorithm hyperparameters used for each environment. The value auto means that the code uses USE_AUTO_BIAS and computes the effective bias adaptively at runtime.

Panel of Figure 4 — Figure 4: Example risk-sensitive planning environments. Each contains a short risky route and a longer safer route; the risky route can have higher expected return but exposes the agent to catastrophic lower-tail outcomes. (2a) the map has black: highways, red: main roads, blue: streets, green: lanes (2b) S: start cell, G: goal cell, X: cliff cell, wind cell is indicated as the blue cell with an arrow points down. (2c) Red cell: guard cell, green cell: goal cell, gray cell: obstacle.

Road Type	Small Cost	Medium Cost	Large Cost
Lane	4	4	4
Street	2	3	5
Main Road	3	4	7
Highway	1	2	10

Appendix

Table 3: Cost distribution used in the Autonomous Vehicle environment.

Environment	Algorithm	CVaR Regret	CVaR Return	Catastrophic Count
Two-Level Risky Treasure	UCT	$12.000$	$-10.000\pm 0.000$	$119.84$
	MaxUCT	$12.000$	$-10.000\pm 0.000$	$120.24$
	PowerUCT	$12.000$	$-10.000\pm 0.000$	$120.26$
	CATSO	$0.020$	$\mathbf{2.000\pm 0.000}$	$\mathbf{0.00}$
	PATSO	$\mathbf{0.000}$	$\mathbf{2.000\pm 0.000}$	$\mathbf{0.00}$
Autonomous Vehicle	UCT	$7.574$	$-31.702\pm 1.229$	$2.78$

Appendix

Table 4: Performance across all environments and algorithms at final simulation budget. Best values per environment and metric are shown in bold.

Figure 5: Pseudocode for the adaptive distribution construction in SimulateQ of CATSO .

Figure 6: Peak memory and search time of CATSO, PATSO, and UCT as a function of the representation size $N$ and $U$ .

Figure 7: Planning performance of CATSO, PATSO, and UCT as a function of the representation size $N$ and $U$ .

Figure 8: Compression quality of capped PATSO relative to uncapped PATSO as a function of the particle cap $U$ .

Risk-Sensitive Planning

See all 24 papers

Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees
Oct 11, 2026Tomer Massas, Vadim IndelmanRobust Markov Decision Processes Model-Based Planning
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
Finite-Time Analysis of MCTS in Continuous POMDP Planning
May 8, 2026Da Kong, Vadim IndelmanMonte Carlo Tree Search Partially Observable Markov Decision Processes
Technion Autonomous Systems Program (TASP) · Technion – Israel Institute of Technology · Stephen B. Klein Faculty of Aerospace Engineering +1
Tail-Influence Sampling for CVaR Policy Evaluation
Sep 29, 2026Pauline Bourigault, Xiaotong Ji, Matthieu Zimmer +2Policy Evaluation Adaptive Sampling
Imperial College London · Huawei Noah’s Ark Lab · UCL Centre for AI

Oct 11, 2026J/K move · Enter open · S save

Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees

Tomer Massas, Vadim Indelman

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

Robust Markov Decision Processes Model-Based Planning Monte Carlo Tree Search

Open paper AskPDF arXiv

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.

Abstract

Risk-Sensitive Planning

Explore similar work

Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees

Finite-Time Analysis of MCTS in Continuous POMDP Planning

Tail-Influence Sampling for CVaR Policy Evaluation