We propose a provably correct Monte Carlo tree search (MCTS) algorithm for solving risk-aware Markov decision processes (MDPs) with entropic risk measure (ERM) objectives. We provide a non-asymptotic analysis of our proposed algorithm, showing that the algorithm: (i) is correct in the sense that the empirical ERM obtained at the root node converges to the optimal ERM; and (ii) enjoys polynomial regret concentration. Our algorithm successfully exploits the dynamic programming formulations for solving risk-aware MDPs with ERM objectives introduced by previous works in the context of an upper confidence bound-based tree search algorithm. Finally, we provide a set of illustrative experiments to evaluate our risk-aware MCTS method, showing it successfully trades off between risk-neutral and risk-averse behavior.
Figures & tables
Figure 1: Distribution of discounted costs obtained by ERM-MCTS for different β values.
β
Algorithm
Crush
Spill
Total
1
Acc-MCTS
19 [12, 26]
21 [14, 29]
40 [30, 51]
ERM-MCTS (Ours)
17 [11, 24]
23 [15, 31]
40 [30, 50]
25
Acc-MCTS
0 [0, 0]
5 [2, 9]
5 [2, 9]
ERM-MCTS (Ours)
1 [0, 3]
6 [2, 10]
7 [3, 11]
Table 1: (Bin-Packing) Total number of accident events over 500 episodes, by event type, with [5%,95%] bootstrapped confidence intervals in brackets. Results for n=5000 MCTS iterations and KUCB=0.3 .
Figure 2: ERMβ for different algorithms as a function of the number of MCTS iterations ( n ).
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Illustration of the recursive relation between parameters {αh} , {θh} , {ηh} , and {ξh} .
Figure 4: Risk-aware MCTS pseudocode.
Figure 5: MDP-4 environment illustration.
β
ERM-BI (Oracle)
Acc-MCTS
ERM-MCTS (Ours)
0.01
0.1704 (-0.0168, +0.0174)
0.1704 (-0.0169, +0.0172)
0.1704 (-0.0171, +0.0175)
5
0.2155 (-0.0018, +0.0018)
0.2424 (-0.0233, +0.0269)
0.2151 (-0.0017, +0.0017)
25
0.2188 (-0.0010, +0.0010)
0.2863 (-0.0678, +0.0376)
0.2188 (-0.0010, +0.0010)
Appendix
Table 2: (MDP-4) ERMβ of the distribution of discounted costs obtained by different algorithms and β values for the MDP-4 environment. Results for n=5000 MCTS iterations and KUCB=0.3 . Lower is better. We highlight values whose confidence intervals overlap with the Oracle baseline confidence intervals.
Figure 6: (MDP-4) Comparison of the discounted cumulative cost distributions obtained by different approaches under the MDP-4 environment for multiple β values. Results for n=5000 MCTS iterations and KUCB=0.3 . Lower is better.
Figure 7: (MDP-4) ERMβ for different β values, KUCB values, and algorithms, as a function of the number of MCTS iterations ( n ).
β
ERM-BI (Oracle)
Acc-MCTS
ERM-MCTS (Ours)
1
0.0821 (-0.0124, +0.0139)
0.0805 (-0.0115, +0.0127)
0.0862 (-0.0121, +0.0131)
5
0.1245 (-0.0105, +0.0132)
0.1509 (-0.0159, +0.0167)
0.1252 (-0.0106, +0.0131)
25
0.1829 (-0.0055, +0.0063)
0.1864 (-0.0051, +0.0052)
0.1830 (-0.0037, +0.0043)
Appendix
Table 3: (Grid-MDP) ERMβ of the distribution of discounted costs obtained by different algorithms and β values for the Grid-MDP environment. Results for n=5000 MCTS iterations and KUCB=0.3 . Lower is better. We highlight values whose confidence intervals overlap with the Oracle baseline confidence intervals.
Figure 8: (Grid-MDP) Comparison of the discounted cumulative cost distributions obtained by different approaches under the Grid-MDP environment for two β values. Results for n=5000 MCTS iterations and KUCB=0.3 . Lower is better.
Figure 9: (Grid-MDP) ERMβ for different β values, KUCB values, and algorithms, as a function of the number of MCTS iterations ( n ).
β
Acc-MCTS
ERM-MCTS (Ours)
1
0.0532 (-0.0020, +0.0020)
0.0534 (-0.0019, +0.0020)
25
0.0718 (-0.0015, +0.0016)
0.0683 (-0.0019, +0.0019)
Appendix
Table 4: (Bin-Packing) ERMβ of the distribution of discounted costs obtained by different algorithms and β values for the Bin-Packing environment. Results for n=5000 MCTS iterations and KUCB=0.3 . Lower is better. Best values are highlighted.
Figure 10: (Bin-Packing) Comparison of the discounted cumulative cost distributions obtained by different approaches under the Bin-Packing environment for multiple β values. Results for n=5000 MCTS iterations and KUCB=0.3 . Lower is better.
Figure 11: (Bin-Packing) ERMβ for different β values, KUCB values, and algorithms, as a function of the number of MCTS iterations ( n ).
We study general-utility Markov decision processes (GUMDPs) with risk-aware objectives. In this framework, an agent aims to optimize a risk measure of the distribution of objective values, where the objective function depends on the frequency of visitation of states induced by the agent's policy. First, we motivate, propose, and formalize risk-aware GUMDPs, which enable agents and decision makers to trade off expected performance by risk aversion while benefiting from the rich set of objectives that can be cast under the framework of GUMDPs. We focus our attention on the entropic risk measure (ERM). Second, we show how we can solve risk-aware GUMDPs with ERM objectives by resorting to online planning techniques. In particular, we propose an approach based on Monte Carlo Tree Search (MCTS) to provably solve risk-aware GUMDPs up to any desired accuracy. Third, we provide a set of experimental results showcasing that our approach is successful when optimizing for a spectrum of risk-aware behaviors in the context of GUMDPs under diverse tasks (standard MDPs, maximum state entropy exploration, imitation learning, and multi-objective MDPs).
Pedro P. Santos, Fábio Vital, Alberto Sardinha +1
INESC-ID · Instituto Superior Técnico, University of Lisbon · Pontifical Catholic University of Rio de Janeiro
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.
Quynh Trinh, Trung Nguyen, Nam Nguyen +1
Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam
We study finite-horizon MDP planning under root-based (resolute) risk objectives that apply a rank-dependent functional to the distribution of total returns. Such objectives are non-linear in the return distribution and generally break Bellman optimality, so direct optimization by scenario-tree enumeration is intractable. We propose ERQDP, an enumeration-free and sampling-free method that solves a rank--quantile surrogate via exact DP (Dynamic Programming), evaluates candidate policies exactly by DP over return Probability Mass Functions (PMFs) on a discretized return grid (with an explicit rounding bound), and refines the surrogate in an anytime loop that reports an explicit upper--lower gap (certificate) for the target objective up to discretization budgets. Across tested benchmarks, ERQDP returns certified solutions or explicit residual gaps, enables fast risk-parameter sweeps with substantial runtime gains, and supports both risk-averse and risk-seeking behaviors.
Irmaan, Mirzanejad, Nadjet Bourdache +1
Mohammad · Université de Caen Normandie, ENSICAEN, CNRS, Normandie Univ, GREYC UMR 6072, France