betaFeedback

WorksComputer Science

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)O(n^{-1/2}) bound on the root value error after nn 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.

Introduction

Monte-Carlo Tree Search (MCTS) drives some of the most capable planning systems ever built, from AlphaGo [28] and AlphaZero [29] to MuZero [26]. Classical variants such as UCT [19], Fixed-Depth-MCTS [27], and Power-UCT [8] store a scalar value estimate at each edge, usually an empirical mean. This is sufficient when the objective is expected return, but it is inadequate for risk-sensitive planning. In safety-critical domains such as autonomous driving, medical treatment planning, and financial decision making, two actions can have similar means but very different lower-tail behavior.

A simple example illustrates the problem. Suppose a root action a1a_1 returns 5 deterministically, while another action a2a_2 returns 10 with probability 1/21/2 and 0 with probability 1/21/2. Both actions have the same expected value, but their lower-tail conditional value-at-risk (CVaR) is different: for small τ\tau, a1a_1 has CVaR equal to 5, whereas a2a_2 has CVaR equal to 0. A scalar mean estimate cannot distinguish these two return laws once their means are known. A risk-sensitive planner, however, should prefer a1a_1 when the objective is to protect against poor outcomes. This requires preserving distributional information at the Q-edges of the search tree.

This paper develops distributional MCTS algorithms for finite-depth risk-sensitive planning. We introduce Categorical Thompson Sampling with Optimism (CATSO) and Particle Thompson Sampling with Optimism (PATSO). Both algorithms maintain finite-support empirical backup laws at Q-edges. CATSO represents each Q-edge law using categorical atoms with Dirichlet Thompson sampling, while PATSO represents it using adaptive weighted particles. At action selection time, both algorithms draw a Thompson-sampled Q-edge law, compute its lower-tail CVaR, and add the polynomial optimism bonus of Shah et al. [27] to ensure sufficient exploration.

The algorithms keep V-nodes scalar by backing up a visit-weighted average of child Q-edge CVaR scores, so Q-edges store distributions while V-nodes propagate scalar risk-sensitive summaries. This avoids distributional V-node convolutions while still letting lower-tail information drive the search. Our main result proves an O(n−1/2)O(n^{-1/2}) root value-error bound against the finite-depth nested CVaR target (Section 5), which yields an O(n−1/2)O(n^{-1/2}) risk-sensitive simple regret. CATSO incurs an additional finite-grid discretization bias, and capped PATSO adds a tunable Wasserstein compression bias.

Our contributions are:

  • We introduce CATSO and PATSO, two non-parametric distributional MCTS algorithms that maintain empirical backup laws at Q-edges.

  • We propose a CVaR-sensitive scalar V-backup that aggregates visit-weighted child Q-edge CVaR scores rather than child Q-edge means.

  • We prove an O(n−1/2)O(n^{-1/2}) root value-error bound for the finite-depth nested CVaR target after nn rollouts, which directly upper-bounds the risk-sensitive simple regret.

  • We characterize the additional approximation terms introduced by finite CATSO grids and capped PATSO particle compression.

  • We evaluate the algorithms on stochastic planning benchmarks where mean-optimal and CVaR-optimal behavior differ.

Existing distributional MCTS methods such as DNG-MCTS [1] and D2NG-POMCP [2] rely on parametric return models, such as Gaussian or mixture distributions. In contrast, CATSO and PATSO are non-parametric: we estimate Q-edge backup laws directly from backed-up samples. This makes our methods suitable for planning problems with multimodal, skewed, or heavy-tailed return distributions, where parametric approximations can obscure the lower-tail behavior that CVaR is designed to measure.

MCTS with non-asymptotic guarantees and distributional backups. While UCT [19] established asymptotic convergence for MCTS, the breakthrough finite-sample analysis is due to Shah et al. [27], who modeled each tree node as a non-stationary bandit and proved O(n−1/2)O(n^{-1/2}) root value convergence using a polynomial exploration bonus; Dam et al. [8] extended this framework to power-mean backups. However, these analyses rely on scalar point estimates and do not capture tail risk. Existing distributional MCTS methods place parametric posteriors over returns—such as Normal-Gamma models in DNG-MCTS [1, 2] or Gaussian Wasserstein barycenters in W-MCTS [9]—or address heuristic multi-objective search [16]. Parametric assumptions can obscure lower-tail behavior in multimodal or heavy-tailed domains. Most recently, Zhang et al. [32] proposed CVaR-MCTS and a distributionally robust variant (also termed Wasserstein-MCTS, distinct from the Gaussian barycenter method of Dam et al. [9]) that optimize expected reward subject to a static cumulative-cost CVaR constraint with PAC tail-safety and regret guarantees. In contrast, CATSO and PATSO maintain non-parametric empirical backup laws at Q-edges while keeping V-nodes scalar, directly optimizing the unconstrained nested finite-depth CVaR of reward with an O(n−1/2)O(n^{-1/2}) finite-budget root value-error guarantee.

Thompson sampling in stationary vs. non-stationary CVaR bandits. Thompson sampling has been combined with MCTS over scalar or Gaussian posteriors [1, 15]. In the stationary multi-armed bandit literature, Riou and Honda [25] established logarithmic regret for Dirichlet Thompson sampling on bounded-support rewards, which Baudry et al. [3] extended to support-aware stationary CVaR bandits via multinomial grids (M-CVTS) and adaptive particles (B-CVTS). Our local bandit analysis builds on this Dirichlet convex-polytope machinery, but stationary CVaR bandit guarantees do not transfer directly to MCTS: the backed-up samples Q^t(sh,a)=rt(sh,a)+γV^τ(sh+1)\widehat{Q}_t(s_h,a)=r_t(s_h,a)+\gamma\widehat{V}^{\tau}(s_{h+1}) have a non-stationary law that drifts as the searched subtree evolves. Controlling this coupled evolution requires pairing Dirichlet CVaR Thompson sampling with a polynomial optimism bonus and establishing our three-stage proof roadmap (local non-stationary CVaR bandit concentration, one-step W1W_1-Lipschitz CVaR lifting across Q-edges, and backward induction).

Risk-sensitive RL. Beyond tree search, risk-sensitive RL has been studied through policy gradients [30, 6], distributional RL [7, 18], robust MDPs [17, 23], and Wasserstein DRO [12]. Recent theoretical work has established provably efficient episodic regret and PAC sample-complexity bounds across two primary objectives: static trajectory CVaR, including near-minimax-optimal learning [31] and reward-free CVaR exploration [22], and nested (iterated) CVaR, including tabular episodic learning [11], function approximation with human feedback [5], and generative-model sample complexity [10]. Whereas these works bound global episodic regret or offline sample complexity across full MDP state spaces, our work addresses online finite-budget Monte-Carlo tree search from a given root state s0s_0, proving non-asymptotic O(n−1/2)O(n^{-1/2}) root value-error and simple-regret guarantees for nested CVaR planning.

Setting

MDP and finite-depth planning. We consider a discounted MDP M=⟨S,A,R,P,γ⟩\mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P},\gamma\rangle, where S\mathcal{S} is the state space, A\mathcal{A} is a finite action set, R(⋅∣s,a)\mathcal{R}(\cdot\mid s,a) is a stochastic reward kernel with support in [0,Rmax⁡][0,R_{\max}],1 P(⋅∣s,a)\mathcal{P}(\cdot\mid s,a) is a stochastic transition kernel over S\mathcal{S}, and γ∈[0,1)\gamma\in[0,1) is the discount factor. MCTS plans from a root state s0s_0 by simulating depth-HH trajectories, using a fixed rollout policy πro\pi_{\mathrm{ro}} at depth HH; we write GHπro(s)=∑k≥0γkrkG_H^{\pi_{\mathrm{ro}}}(s)=\sum_{k\geq0}\gamma^k r_k for the resulting discounted return. For the analysis, every internal node has finitely many legal actions and every encountered transition kernel has finite support.

Lower-tail CVaR. For a real-valued XX and τ∈(0,1]\tau\in(0,1], the lower-tail conditional value-at-risk is

CVaR⁡τ(X):=1τ∫0τFX−1(u) du,(1)\operatorname{CVaR}_{\tau}(X):=\frac{1}{\tau}\int_{0}^{\tau}F_X^{-1}(u)\,du, \tag*{(1)}

the average of the worst τ\tau-fraction of outcomes, with CVaR⁡1(X)=E[X]\operatorname{CVaR}_{1}(X)=\mathbb{E}[X]. We also write CVaR⁡τ(P)\operatorname{CVaR}_{\tau}(P) for laws PP; for finitely supported PP, this is the discrete formula (10). The same τ\tau is used for selection, backup, and evaluation throughout. Although we state the theory for lower-tail CVaR, this is without loss of generality: upper-tail risk can be handled by applying the same framework to −X-X, equivalently using CVaR⁡‾τ(X):=−CVaR⁡τ(−X)\overline{\operatorname{CVaR}}_{\tau}(X):=-\operatorname{CVaR}_{\tau}(-X).

Finite-depth nested CVaR target. Set V~τ(sH):=CVaR⁡τ(GHπro(sH))\widetilde V_{\tau}(s_H):=\operatorname{CVaR}_{\tau}(G_H^{\pi_{\mathrm{ro}}}(s_H)) and, for h=H−1,…,0h=H-1,\ldots,0, define the Bellman-backup law

Dτ(sh,a):=L(R(sh,a,S′)+γV~τ(S′)),S′∼P(⋅∣sh,a),(2)\mathcal{D}^{\tau}(s_h,a):=\mathcal{L}\left(R(s_h,a,S')+\gamma\widetilde V^{\tau}(S')\right),\qquad S'\sim\mathcal{P}(\cdot\mid s_h,a), \tag*{(2)}

with reward sampled from R(sh,a,S′)\mathcal{R}(s_h,a,S'), and

Q~τ(sh,a):=CVaR⁡τ(Dτ(sh,a)),V~τ(sh):=max⁡a∈A(sh)Q~τ(sh,a).(3)\widetilde Q^{\tau}(s_h,a):=\operatorname{CVaR}_{\tau}\left(\mathcal{D}^{\tau}(s_h,a)\right),\qquad\widetilde V^{\tau}(s_h):=\max_{a\in\mathcal{A}(s_h)}\widetilde Q^{\tau}(s_h,a). \tag*{(3)}

Write V~τ(s0):=V~0τ(s0)\widetilde V^{\tau}(s_0):=\widetilde V^{\tau}_0(s_0). At τ=1\tau=1, (3) reduces to the standard finite-depth risk-neutral Bellman recursion; for τ<1\tau<1, it is a nested time-consistent CVaR target, distinct from the static CVaR⁡τ(∑t≥0γtrt)\operatorname{CVaR}_{\tau}\left(\sum_{t\geq0}\gamma^t r_t\right). All guarantees are stated relative to (3).

Algorithmic root value estimate. After nn rollouts, each visited Q-edge (s,a)(s,a) maintains an empirical backup law D^Ts,a(n)(s,a)\widehat{\mathcal{D}}_{T_{s,a}(n)}(s,a), where Ts,a(n)T_{s,a}(n) is its visit count, with empirical CVaR score

c^τ,n(s,a):=CVaR⁡τ(D^Ts,a(n)(s,a)).\widehat c_{\tau,n}(s,a):=\operatorname{CVaR}_{\tau}\left(\widehat{\mathcal{D}}_{T_{s,a}(n)}(s,a)\right).

The scalar V-node estimate is the visit-weighted average

V^Ts(n)τ(s):=∑a∈A(s)Ts,a(n)Ts(n)c^τ,n(s,a),(4)\widehat V^{\tau}_{T_s(n)}(s):=\sum_{a\in\mathcal{A}(s)}\frac{T_{s,a}(n)}{T_s(n)}\widehat c_{\tau,n}(s,a), \tag*{(4)}

with each action initialized before backup; V^nτ(s0)\widehat V^{\tau}_n(s_0) is the root estimate returned after nn rollouts.

Risk-sensitive simple regret. The risk-sensitive simple regret relative to (3) is

SR⁡τ(n):=E[V~τ(s0)−V^nτ(s0)],(5)\operatorname{SR}_{\tau}(n):=\mathbb{E}\left[\widetilde V^{\tau}(s_0)-\widehat V^{\tau}_n(s_0)\right], \tag*{(5)}

and our main theorem controls the stronger absolute error

Eτ(n):=E[∣V^nτ(s0)−V~τ(s0)∣]≥SR⁡τ(n),(6)\mathcal{E}_{\tau}(n):=\mathbb{E}\left[\left|\widehat V^{\tau}_n(s_0)-\widetilde V^{\tau}(s_0)\right|\right]\geq\operatorname{SR}_{\tau}(n), \tag*{(6)}

so any O(n−1/2)O(n^{-1/2}) bound on Eτ(n)\mathcal{E}_{\tau}(n) transfers to SR⁡τ(n)\operatorname{SR}_{\tau}(n).

Algorithms

We replace the scalar mean at each Q-edge with an empirical backup law, used both for risk-sensitive exploration (Thompson-sampled CVaR scores) and risk-sensitive backup (empirical Q-edge CVaR scores). VV-nodes remain scalar, propagating a visit-weighted average of child Q-edge CVaR values.

Distributional Q-Edges

On a rollout, the scalar sample stored at Q-edge (sh,a)(s_h,a) is

Q‾t(sh,a):=rt(sh,a)+γV^τ(sh+1),(7)\overline{Q}_t(s_h,a) := r_t(s_h,a) + \gamma\widehat{V}^{\tau}(s_{h+1}), \tag*{(7)}

where V^τ(sh+1)\widehat{V}^{\tau}(s_{h+1}) is the current scalar CVaR-sensitive continuation value. CATSO and PATSO differ only in how they represent the empirical law of these samples.

References

  1. [1]Aijun Bai, Feng Wu, and Xiaoping Chen. Bayesian mixture modelling and inference based on thompson sampling in monte-carlo tree search. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips.cc/paper/2013/file/846c260d715e5b854ffad5f70a516c88-Paper.pdf.
  2. [2]Aijun Bai, Feng Wu, Zongzhang Zhang, and Xiaoping Chen. Thompson sampling based monte-carlo planning in pomdps. the International Conference on Automated Planning and Scheduling, 24(1), 2014.DOI
  3. [3]Dorian Baudry, Romain Gautron, Emilie Kaufmann, and Odalric-Ambrym Maillard. Optimal thompson sampling strategies for support-aware cvar bandits. In International Conference on Machine Learning, pages 716–726. PMLR, 2021.
  4. [4]Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value-at-risk criteria. Mathematical Methods of Operations Research, 74:361–379, 2011.DOI
  5. [5]Yu Chen, Yihan Du, Pihe Hu, Siwei Wang, Desheng Wu, and Longbo Huang. Provably efficient iterated cvar reinforcement learning with function approximation and human feedback. In International Conference on Learning Representations, 2024.arxiv.org/abs/2307.02842
  6. [6]Y. Chow, A. Tamar, S. Mannor, and M. Pavone. Risk-sensitive and robust decision-making: a cvar optimization approach. In Advances in Neural Information Processing Systems, 2015.arxiv.org/abs/1506.02188
  7. [7]Will Dabney, Mark Rowland, Marc G Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.arxiv.org/abs/1710.10044
  8. [8]Tuan Dam, Odalric-Ambrym Maillard, and Emilie Kaufmann. Power mean estimation in stochastic monte-carlo tree search. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 894–918. PMLR, 15–19 Jul 2024. URL https://proceedings.mlr.press/v244/dam24a.html.arxiv.org/abs/2406.02235
  9. [9]Tuan Quang Dam, Pascal Stenger, Lukas Schneider, Joni Pajari­nen, Carlo D’Eramo, and Odalric-Ambrym Maillard. Monte-Carlo tree search with uncertainty propagation via optimal transport. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 12377–12401. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr.press/v267/dam25c.html.
  10. [10]Zilong Deng, Simon Khan, and Shaofeng Zou. Near-optimal sample complexity for iterated cvar reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, volume 258, pages 3907–3915. PMLR, 2025.arxiv.org/abs/2503.08934
  11. [11]Yihan Du, Siwei Wang, and Longbo Huang. Provably efficient risk-sensitive reinforcement learning: Iterated cvar and worst path. In International Conference on Learning Representations, 2023.arxiv.org/abs/2206.02678
  12. [12]Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115–166, 2018.arxiv.org/abs/1505.05116
  13. [13]Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3):707–738, 2015.arxiv.org/abs/1312.2128
  14. [14]Ido Greenberg, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Efficient risk-averse reinforcement learning. In Advances in Neural Information Processing Systems, volume 35, pages 32639–32652, 2022.arxiv.org/abs/2205.05138
  15. [15]Nir Greshler, David Ben Eli, Carmel Rabinovitz, Gabi Guetta, Liran Gispan, Guy Zohar, and Aviv Tamar. A bayesian approach to online planning. In Forty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum?id=NS8Z5FinY1.arxiv.org/abs/2406.02103
  16. [16]Conor F Hayes, Mathieu Reymond, Diederik M Roijers, Enda Howley, and Patrick Mannion. Risk aware and multi-objective decision making with distributional monte carlo tree search. arXiv preprint arXiv:2102.00966, 2021.arxiv.org/abs/2102.00966
  17. [17]Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257–280, 2005.DOI
  18. [18]Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning a CVaR policy. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.arxiv.org/abs/1911.01546
  19. [19]Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 1, 2006.
  20. [20]Yudong Luo, Guiliang Liu, Pascal Poupart, and Yangchen Pan. An alternative to variance: Gini deviation for risk-averse policy gradient. In Advances in Neural Information Processing Systems, volume 36, pages 60922–60946, 2023.arxiv.org/abs/2307.08873
  21. [21]Yudong Luo, Yangchen Pan, Han Wang, Philip Torr, and Pascal Poupart. A simple mixture policy parameterization for improving sample efficiency of CVaR optimization. In RLC, pages 573–592, 2024.arxiv.org/abs/2403.11062
  22. [22]Xinyi Ni, Guanlin Liu, and Lifeng Lai. Risk-sensitive reward-free reinforcement learning with cvar. In International Conference on Machine Learning, volume 235, pages 37999–38017. PMLR, 2024.
  23. [23]Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798, 2005.DOI
  24. [24]Marc Rigter, Bruno Lacerda, and Nick Hawes. Risk-averse bayes-adaptive reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 1142–1154, 2021.
  25. [25]Charles Riou and Junya Honda. Bandit algorithms based on thompson sampling for bounded reward distributions. In Algorithmic Learning Theory, pages 777–826. PMLR, 2020.
  26. [26]Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604–609, 2020.
  27. [27]Devavrat Shah, Qiaomin Xie, and Zhi Xu. Nonasymptotic analysis of monte carlo tree search. Operations Research, 70(6):3234–3260, 2022.DOI
  28. [28]David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484, 2016.DOI
  29. [29]David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–1144, 2018.DOI
  30. [30]Aviv Tamar, Yonatan Glassner, and Shie Mannor. Optimizing the cvar via sampling. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1), 2015.arxiv.org/abs/1404.3862
  31. [31]Kaiwen Wang, Nathan Kallus, and Wen Sun. Near-minimax-optimal risk-sensitive reinforcement learning with cvar. In International Conference on Machine Learning, volume 202, pages 35864–35907. PMLR, 2023.arxiv.org/abs/2302.03201
  32. [32]Zuyuan Zhang, Arnob Ghosh, and Tian Lan. Tail-risk-safe monte carlo tree search under pac-level guarantees. arXiv preprint, 2025.arxiv.org/abs/2508.05441

Paper details

vlnc:W_tb98xg3r
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents