Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search
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.
Related
- Risk-Sensitive Mission Planning for Multi-Target On-Orbit Inspection via Distributional Reinforcement Learning
- Designing for Prediction: Planning Formulas for Expected Out-of-Sample R2 and r
- Multi-Sensitive Distributional Fairness: Joint Wasserstein Audits and Shapley Allocation
- Beyond Distributional Fidelity: Causal-Penalized Diffusion for Synthetic Tabular Data
- Beyond Expected Profit: How Risk Aversion Alters Learning in the Data-Driven Newsvendor
BibTeX
@misc{trinh2026beyond,
title = {{Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search}},
author = {Quynh Trinh and Trung Nguyen and Nam Nguyen and Tuan Dam},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23565},
eprint = {2610.23565},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23565},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search
AU - Quynh Trinh
AU - Trung Nguyen
AU - Nam Nguyen
AU - Tuan Dam
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23565
UR - https://arxiv.org/abs/2610.23565
AB - 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.
ER -