Entropic Risk-Aware Monte Carlo Tree Search

arXiv:2601.17667 · cs.LG · Submitted 2026-01-25 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Entropic Risk-Aware Monte Carlo Tree Search".

Jane: Here's the gist of the paper. Entropic Risk-Aware Monte Carlo Tree Search proposes a provably correct Monte Carlo tree search (MCTS) algorithm for solving risk-aware Markov decision processes (MDPs) with entropic risk measure (ERM) objectives, which is significant because it provides a non-asymptotic analysis showing the algorithm is correct and enjoys polynomial regret concentration Algorithm Proposal The core contribution of the paper is the proposal of a novel and principled MCTS-based algorithm to solve risk-aware MDPs with ERM objectives, while providing a non-asymptotic analysis of its performance The algorithm mirrors risk-neutral MCTS by replacing mean value estimators at decision nodes with entropic risk measure estimators and using UCB-style exploration bonuses to ensure sufficient exploration and convergence to optimal behavior This approach leverages the dynamic programming formulations of entropic risk-aware MDPs to design a UCB-based tree search algorithm with provable performance guarantees, in contrast to previous works that lacked such theoretical guarantees Theoretical Analysis and Guarantees The paper provides a non-asymptotic analysis showing that the proposed algorithm is correct in the sense that the empirical ERM obtained at the root node converges to the optimal ERM and enjoys polynomial regret concentration This convergence is established by recursively applying results from risk-aware bandits, showing similar convergence and concentration properties for trees The analysis involves several key steps, including proving Lemma 3 and Theorem 5 to establish the necessary concentration properties at each level of the tree Risk-Aware Bandits Foundation The theoretical foundation is built upon results from non-stationary risk-aware bandits, specifically in Section 3.1, where a UCB-based algorithm for the ERMβ is proposed and analyzed under Assumption 2 Theorem 1 establishes convergence rates for this bandit setting, showing that the expected empirical ERMβ converges to the optimal limiting value µ∗ with a rate of O exp(2βR)n αξ(1−η) −1 MCTS Implementation and Results The proposed risk-aware MCTS algorithm incrementally constructs a search tree alternating between decision nodes and chance nodes, storing sampled discounted cumulative costs starting from each state-action pair Theorem 6 demonstrates that the risk-aware MCTS algorithm not only provably solves risk-aware MDPs with ERM objectives but also enjoys polynomial regret concentration Illustrative experiments compare ERM-MCTS against oracle baselines like ERM-BI and adaptations of other algorithms, showing that the method successfully trades off between risk-neutral and risk-averse behaviors Parameter Definition The recursive application of Theorem 5 to establish convergence throughout the tree requires defining parameters such as ηh = αh+1ξh+1(1−ηh+1) and ξh = αh+1 − 1 for all depth h < H The parameter θL is defined recursively as θh = max

1, h(θh+1, ξh+1, ηh+1, αh+1): to satisfy Assumption 3 at each level of the tree Empirical Validation Empirical results for the MDP-4 and Grid-MDP environments show that ERM-MCTS matches the ERMβ obtained by the oracle baseline, and for the Grid-MDP environment, it converges faster to the optimal ERMβ than ACC-MCTS The results demonstrate that as the risk sensitivity parameter β increases, ERM-MCTS exhibits increasingly risk-averse behavior Environment Details The MDP-4 environment consists of a four-state MDP where the agent trades off between a safe action leading to a medium cost state and a risky action that can lead to both low or high cost states The Grid-MDP environment is a 5 × 3 grid with an additional absorbing pitfall state, modeling risk through slippery states where transitions to the pitfall state occur with probability ε = 0.01 Software and Code The developed code for the algorithm can be found at https://github.com/PPSantos/risk-aware-mcts The complete experimental results are presented in Appendix H, which details the environments and software used Risk Measure Properties The ERMβ is defined as 1/β ln (E

exp(βz): ) or equivalently as min λ∈R Σλ + E

uβ(z − λ): where uβ(x) = 1/β (exp(βx) − 1) Lemma 7 details properties of the ERM estimator, including its convexity and attainment of a minimum in R Lemma 8 provides exponential concentration bounds for the ERM estimator, showing that P

ρˆn − ρ(x1) ≥ z: ≤ 2 exp −Cnz2 Risk-Neutral vs.

Tom: Risk-Aware A fundamental difference noted is that the analysis of the risk-aware MCTS algorithm does not follow trivially from previous works because mean and ERM estimators are inherently different, requiring novel proofs The paper explicitly argues that Hayes et al.

Jane: (2023)'s approach, while allowing for any non-linear utility function u(x) = exp(βx), lacks theoretical guarantees for the ERM setting Safe/Constrained MCTS Comparison The paper focuses on optimizing the unconstrained ERM of the distribution of discounted cumulative costs, unlike works that focus on constrained MDPs or CVaR-based safety-aware MCTS The proofs follow different lines of reasoning compared to those used by Zhang et al.

Tom: (2025) The paper concludes by proposing the first theoretically-grounded MCTS algorithm to solve risk-aware MDPs with ERM objectives, demonstrating its correctness and polynomial regret concentration It successfully trades off between risk-neutral and risk-averse behaviors while comparing its performance against other baselines References E.

Paper summary: Tom: So we're looking at this paper called Entropic Risk-Aware Monte Carlo Tree Search. Basically, the authors are proposing a Monte Carlo tree search algorithm that can solve risk-aware Markov decision processes when you're using an entropic risk measure.

Jane: That sounds pretty dense, Tom. Can you give us the main idea? What’s the big claim here about this Entropic Risk-Aware Monte Carlo Tree Search?

Tom: The main claim is that they provide a provably correct Monte Carlo tree search algorithm for solving risk-aware Markov decision processes with entropic risk measure objectives, and they show it has polynomial regret concentration.

Lu: What's interesting is that this approach mirrors the risk-neutral Monte Carlo tree search by replacing the mean value estimators at decision nodes with estimators based on the entropic risk measure, and using UCB style exploration bonuses to ensure good exploration and convergence to optimal behavior.

Meng: Okay, so it’s taking a standard MCTS setup and modifying it—replacing the usual average cost calculation with something that accounts for risk aversion—and then they prove it works theoretically. How big is this gap compared to what we usually see in these planning algorithms?

Lalam: The paper claims they leverage the dynamic programming formulations of risk-aware Markov decision processes with entropic risk objectives introduced by previous works, which is a key step in their methodology.

Tom: Right, so they’re not just throwing a new heuristic at it; they're building this UCB based tree search algorithm using those existing dynamic programming formulas for these risk-aware MDPs.

Jane: So the core of the contribution is that they provide a non-asymptotic analysis showing that their empirical entropic risk measure obtained at the root node actually converges to the optimal entropic risk measure and enjoys polynomial regret concentration.

Lu: That convergence is established by recursively applying results from risk-aware bandits, which shows similar convergence and concentration properties for trees. They prove Lemma three and Theorem five to establish these necessary concentration properties at each level of the tree <ref:2601.17667#pg3>.

Meng: But that sounds like a lot of mathematical machinery just to make sure it works; what does that mean for us when we try to deploy this on something that actually has real traffic? Does this theoretical guarantee translate into something practical for running models?

Lalam: They also provide a set of illustrative experiments comparing their risk-aware MCTS method against relevant baselines, which shows how it successfully trades off between risk-neutral and risk-averse behaviors.

Tom: The paper does compare it against ERM based bandits and other adaptations of other algorithms, showing that the ERM Monte Carlo tree search performs well. And they have specific environments like MDP-four and Grid-MDP to show this off on.

Paper summary: Jane: For instance, in the MDP-four environment, the risk-aware MCTS matches the entropic risk measure obtained by an oracle baseline, and in the Grid-MDP environment, it converges faster to that optimal entropic risk measure than ACC Monte Carlo tree search does.

Lu: It’s interesting because as you increase the risk sensitivity parameter beta, ERM Monte Carlo tree search exhibits increasingly risk-averse behavior. That shows the algorithm is actually learning and adapting its level of caution based on what it encounters in those environments.

Meng: I wonder about the parameters they define for this recursive application; they have these things like eta h and xi h, and theta L, which they define to satisfy Assumption three at each level of the tree <ref:2601.17667#pg3>. That sounds complex to manage when you're building a system that needs to run fast.

Tom: Well, those are just the definitions needed for the proof structure; they're part of establishing that provable performance guarantee you mentioned earlier, which is what sets this work apart from previous methods that lacked such theoretical guarantees.

Jane: It really does matter because it moves beyond just showing something works on a few test cases; they prove it converges to the optimal risk measure and has polynomial regret concentration. That means we have a solid mathematical foundation for using this approach instead of just guessing how good it is going to be.

Lu: The foundation is built upon results from non-stationary risk-aware bandits, specifically where a UCB based algorithm for the entropic risk measure was proposed and analyzed under Assumption two <ref:2601.17667#pg3,non-stationary risk-aware bandits>. Theorem one establishes convergence rates for that bandit setting, showing that the expected empirical entropic risk measure converges to the optimal limiting value mu star with a rate of O exp (two beta R n) / (one minus eta).

Meng: That convergence rate looks pretty strong, but what about the cost? If we're dealing with a large decision space like in those Grid-MDP environments, how does that complexity affect the runtime of this search?

Tom: The paper focuses on optimizing the unconstrained entropic risk measure of the distribution of discounted cumulative costs, which is different from works that focus on constrained MDPs or CVaR based safety-aware Monte Carlo tree search.

Jane: That distinction is important because it tells us they aren't trying to solve those harder problems right now; they are focusing on getting this core MCTS algorithm provably correct for the unconstrained case first.

Lu: The paper also provides properties of the entropic risk measure estimator, like Lemma seven and Lemma eight which detail its convexity and attainment of a minimum in R. And Lemma eight gives exponential concentration bounds for the entropic risk measure estimator, showing that P

rho hat n minus rho (xone) greater than or equal to z: is bounded by two times exp negative C nz squared.

Paper summary: Meng: Okay, so we have the theory on convergence and concentration, but what about the actual implementation cost? If we look at the software available at https://github.com/PPSantos/risk-aware-mcts, how scalable is this thing when you move from a four state MDP to something much bigger?

Tom: The code is out there for anyone to check, and they show that ERM Monte Carlo tree search can incrementally construct a search tree alternating between decision nodes and chance nodes, storing sampled discounted cumulative costs starting from each state action pair.

Jane: So the algorithm itself is designed to handle those alternating steps of decision nodes and chance nodes while keeping track of the costs. That’s a structural detail that makes it fit the MDP formulation.

Lu: The analysis involves proving Theorem six which demonstrates that this risk-aware MCTS algorithm not only provably solves risk-aware MDPs with entropic risk objectives but also enjoys polynomial regret concentration.

Meng: So, to sum up what we’ve heard, this paper proposes a novel provably correct Monte Carlo tree search for risk-aware MDPs using an entropic risk measure, and they provide non-asymptotic analysis showing it has polynomial regret concentration.

Tom: Exactly. The implication is that we finally have a way to get theoretical guarantees on how good these planning algorithms are performing when you introduce risk measures like the ERM.

Jane: And for someone just listening, it means that instead of just hoping your search algorithm finds a decent policy, we have mathematical proof that it will converge towards the optimal risk-aware behavior with a predictable rate of convergence.

Lu: This is a significant step because previous works didn't have this level of theoretical grounding when dealing with the ERM setting, and they explicitly argue that mean and ERM estimators are inherently different, requiring novel proofs.

Meng: I still have to ask what the authors themselves flag as limitations. What’s the practical thing we should watch out for when we actually try to run this in a production setting?

Tom: They focus on optimizing the unconstrained entropic risk measure of the distribution of discounted cumulative costs, which means they aren't directly solving constrained MDPs or CVaR based safety-aware MCTS right now.

Jane: So while it’s a solid theoretical result for the unconstrained case, it doesn't immediately solve those safety problems where you have hard constraints on the outcomes.

Lu: That's right, and they also note that the analysis of this risk-aware MCTS algorithm doesn't follow trivially from previous works because mean and ERM estimators are inherently different.

Meng: So, it’s a strong theoretical tool for establishing correctness in a specific setting, but we still need to figure out how to handle those real-world constraints efficiently.

Tom: That seems like the honest assessment of where the research is right now with this paper on Entropic Risk-Aware Monte Carlo Tree Search.

Conclusion: Tom: So we're wrapping up this look at Entropic Risk-Aware Monte Carlo Tree Search. The title itself is quite technical, isn't it?

Jane: It is, Tom, and when you break it down, it’s about taking something called Monte Carlo tree search and making it work for risk-aware problems using an entropic risk measure.

Tom: Exactly. And the authors of this paper have done something pretty specific here, they’ve built a provably correct algorithm for solving those risk-aware Markov decision processes with entropic objectives.

Jane: What that actually means is they aren't just guessing if their search method will find the best path; they’ve shown mathematically that the empirical risk measure you get from running their algorithm at the root node is guaranteed to converge to the true optimal risk measure.

Tom: It’s not just a hunch; it’s a proof of convergence, and they also showed polynomial regret concentration, which is a nice number for how fast the error drops.

Jane: That concentration part is key because it tells us that as you run the search longer, the performance improvement becomes predictable and reliable.

Tom: So what this does for people listening—whether you're driving or cooking—is it gives us a solid mathematical foundation for building planning algorithms that care about risk, not just average outcomes.

Jane: Right. It shows how to trade off between being risk-neutral and being risk-averse in a way that has been formally proven to converge reliably.

Tom: It’s a big step because previous works didn't have this level of theoretical backing when dealing with the entropic risk measure setup.

Jane: And it opens up a new direction for planning algorithms, showing how to use these complex risk measures in a way that is mathematically sound and predictable.

Tom: So we’ve seen the mechanics and the proof structure, but what's next for this algorithm?

Tecnico Universidade de Lisboa · Pontifícia Universidade Católica do Rio de Janeiro · Instituto Nacional de Estudos e Pesquisas Sociais

cs.LG

Submitted: 2026-01-25

Updated: 2026-11-10

Code: https://github.com/PPSantos/risk-aware-mcts

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 77/100

The gist: Entropic Risk-Aware Monte Carlo Tree Search proposes a provably correct Monte Carlo tree search (MCTS) algorithm for solving risk-aware Markov decision processes (MDPs) with entropic risk measure…

Key concepts

Entropic Risk Measure (ERM)
The ERM is a way to quantify risk that focuses on the exponential of costs. It is defined as $1/eta ext{ln}(E[ ext{exp}(eta z)])$. This measure prioritizes avoiding very high costs, making it useful for decision-making where catastrophic outcomes are more concerning than average outcomes.
Monte Carlo Tree Search (MCTS)
MCTS is a search algorithm used to make decisions in complex games or environments. ERM-MCTS adapts this by using ERM estimators instead of simple averages at decision points, guiding the search toward actions that minimize the calculated entropic risk.
Polynomial Regret Concentration
This is a theoretical guarantee showing that the algorithm's performance error (regret) grows slowly over time. Polynomial concentration means this error bound increases relatively mildly as more data is collected, ensuring reliable convergence to the optimal risk-aware solution.

Terminology

Summary

Entropic Risk-Aware Monte Carlo Tree Search proposes a provably correct Monte Carlo tree search (MCTS) algorithm for solving risk-aware Markov decision processes (MDPs) with entropic risk measure (ERM) objectives, which is significant because it provides a non-asymptotic analysis showing the algorithm is correct and enjoys polynomial regret concentration

Algorithm Proposal

The core contribution of the paper is the proposal of a novel and principled MCTS-based algorithm to solve risk-aware MDPs with ERM objectives, while providing a non-asymptotic analysis of its performance The algorithm mirrors risk-neutral MCTS by replacing mean value estimators at decision nodes with entropic risk measure estimators and using UCB-style exploration bonuses to ensure sufficient exploration and convergence to optimal behavior This approach leverages the dynamic programming formulations of entropic risk-aware MDPs to design a UCB-based tree search algorithm with provable performance guarantees, in contrast to previous works that lacked such theoretical guarantees

Theoretical Analysis and Guarantees

The paper provides a non-asymptotic analysis showing that the proposed algorithm is correct in the sense that the empirical ERM obtained at the root node converges to the optimal ERM and enjoys polynomial regret concentration This convergence is established by recursively applying results from risk-aware bandits, showing similar convergence and concentration properties for trees The analysis involves several key steps, including proving Lemma 3 and Theorem 5 to establish the necessary concentration properties at each level of the tree

Risk-Aware Bandits Foundation

The theoretical foundation is built upon results from non-stationary risk-aware bandits, specifically in Section 3.1, where a UCB-based algorithm for the ERMβ is proposed and analyzed under Assumption 2 Theorem 1 establishes convergence rates for this bandit setting, showing that the expected empirical ERMβ converges to the optimal limiting value µ∗ with a rate of O exp(2βR)n αξ(1−η) −1

MCTS Implementation and Results

The proposed risk-aware MCTS algorithm incrementally constructs a search tree alternating between decision nodes and chance nodes, storing sampled discounted cumulative costs starting from each state-action pair Theorem 6 demonstrates that the risk-aware MCTS algorithm not only provably solves risk-aware MDPs with ERM objectives but also enjoys polynomial regret concentration Illustrative experiments compare ERM-MCTS against oracle baselines like ERM-BI and adaptations of other algorithms, showing that the method successfully trades off between risk-neutral and risk-averse behaviors

Parameter Definition

The recursive application of Theorem 5 to establish convergence throughout the tree requires defining parameters such as ηh = αh+1ξh+1(1−ηh+1) and ξh = αh+1 − 1 for all depth h < H The parameter θL is defined recursively as θh = max[1, h(θh+1, ξh+1, ηh+1, αh+1)] to satisfy Assumption 3 at each level of the tree

Empirical Validation

Empirical results for the MDP-4 and Grid-MDP environments show that ERM-MCTS matches the ERMβ obtained by the oracle baseline, and for the Grid-MDP environment, it converges faster to the optimal ERMβ than ACC-MCTS The results demonstrate that as the risk sensitivity parameter β increases, ERM-MCTS exhibits increasingly risk-averse behavior

Environment Details

The MDP-4 environment consists of a four-state MDP where the agent trades off between a safe action leading to a medium cost state and a risky action that can lead to both low or high cost states The Grid-MDP environment is a 5 × 3 grid with an additional absorbing pitfall state, modeling risk through slippery states where transitions to the pitfall state occur with probability ε = 0.01

Software and Code

The developed code for the algorithm can be found at https://github.com/PPSantos/risk-aware-mcts The complete experimental results are presented in Appendix H, which details the environments and software used

Risk Measure Properties

The ERMβ is defined as 1/β ln (E[exp(βz)]) or equivalently as min λ∈R Σλ + E [uβ(z − λ)] where uβ(x) = 1/β (exp(βx) − 1) Lemma 7 details properties of the ERM estimator, including its convexity and attainment of a minimum in R Lemma 8 provides exponential concentration bounds for the ERM estimator, showing that P [ρˆn − ρ(x1) ≥ z] ≤ 2 exp −Cnz2

Risk-Neutral vs. Risk-Aware

A fundamental difference noted is that the analysis of the risk-aware MCTS algorithm does not follow trivially from previous works because mean and ERM estimators are inherently different, requiring novel proofs The paper explicitly argues that Hayes et al. (2023)'s approach, while allowing for any non-linear utility function u(x) = exp(βx), lacks theoretical guarantees for the ERM setting

Safe/Constrained MCTS Comparison

The paper focuses on optimizing the unconstrained ERM of the distribution of discounted cumulative costs, unlike works that focus on constrained MDPs or CVaR-based safety-aware MCTS The proofs follow different lines of reasoning compared to those used by Zhang et al. (2025)

Conclusion

The paper concludes by proposing the first theoretically-grounded MCTS algorithm to solve risk-aware MDPs with ERM objectives, demonstrating its correctness and polynomial regret concentration It successfully trades off between risk-neutral and risk-averse behaviors while comparing its performance against other baselines

References

E. Altman Constrained Markov Decision Processes Chapman and Hall 1999 Ming Liang Ang Eloise Y Y Lim and Joel Q L Chang Thompson sampling for gaussian entropic risk bandits CoRR abs/2105. p. 006960 2021 Philippe Artzner Freddy Delbaen Eber Jean-Marc and David Heath Coherent measures of risk Mathematical Finance 9:203 – 228, 07 1999 Peter Auer Nicolo Cesa-Bianchi and Paul Fischer Finite-time analysis of the multiarmed bandit problem Machine Learning 47(2):235–256 May 2002 Aharon Ben-Tal and Marc Teboulle Expected utility penalty functions and duality in stochastic nonlinear programming Management Science 32(11):1445–1466 1986 Aharon Ben-Tal and Marc Teboulle An old-new concept of convex risk measures The optimized certainty equivalent Mathematical Finance 17(3):449–476 2007 V S Borkar and S P Meyn Risk-sensitive optimal control for markov decision processes with monotone cost Mathematics of Operations Research 27(1):192–209 2002 Cameron B Browne Edward Powley Daniel Whitehouse Simon M Lucas Peter I Cowling Philipp Rohlfshagen Stephen Tavener Diego Perez Spyridon Samothrakis and Simon Colton A survey of monte carlo tree search methods IEEE Transactions on Computational Intelligence and AI in Games 4(1):1–43 2012 Asaf Cassel Shie Mannor and Assaf Zeevi A general approach to multi-armed bandits under risk criteria In Proceedings of the 31st Conference On Learning Theory volume 75 of Proceedings of Machine Learning Research pages 1295–1306, 2018 Hyeong Soo Chang Michael C Fu Jiaqiao Hu and Steven I Marcus An adaptive sampling algorithm for solving markov decision processes Operations Research 53(1):126–139, 2005 Joel Q L Chang and Vincent Y F Tan A unifying theory of thompson sampling for continuous risk-averse bandits Proceedings of the AAAI Conference on Artificial Intelligence 36(6):6159–6166, 2022 Yinlam Chow Aviv Tamar Shie Mannor and Marco Pavone Risk-sensitive and robust decisionmaking a cvar optimization approach In Advances in Neural Information Processing Systems volume 28 2015 Can Comer Jannis Bl uml Cedric Derstroff and Kristian Kersting Polynomial regret concentration of ucb for non-deterministic state transitions 2025 Rick Durrett Probability Theory and Examples Cambridge Series in Statistical and Probabilistic Mathematics Cambridge University Press 5 edition 2019 Monika Farsang Paul Mineiro and Wangda Zhang Conditionally risk-averse contextual bandits 2023 H Follmer and A Schied Stochastic Finance An Introduction in Discrete Time De Gruyter Textbook 2016 ISBN 9783110463453 Ayon Ghosh L A Prashanth and Krishna Jagannathan Concentration bounds for optimized certainty equivalent risk estimation 2024 Conor F Hayes Mathieu Reymond Diederik M Roijers Enda Howley and Patrick Mannion Monte carlo tree search algorithms for risk-aware and multi-objective reinforcement learning Autonomous Agents and Multi-Agent Systems 37(2):26 2023 Ronald A Howard James E Matheson Risk-sensitive markov decision processes Management Science 18(7):356–369 March 1972 Anmol Kagrecha Jayakrishnan Nair and Krishna Jagannathan Distribution oblivious risk-aware algorithms for multi-armed bandits with unbounded rewards In Advances in Neural Information Processing Systems volume 32 2019 Michael J Kearns Yishay Mansour and Andrew Y Ng A sparse sampling algorithm for nearoptimal planning in large markov decision processes In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence IJCAI ’99 page 1324–1231, 1999 Levente Kocsis Csaba Szepesvari and Jan Willemson Improved monte carlo search 2006 Martin Kurecka V aclav Nevyho stˇ enˇ y Petr Novotn y and V ´ıt Uncovsk ˇ y Threshold uct Cost-constrained monte carlo tree search with pareto curves Proceedings of the AAAI Conference on Artificial Intelligence 39(25):26569–26578, 2025 Tor Lattimore Csaba Szepesvari Bandit Algorithms Cambridge University Press 2020 doi: 10.1017/9781108571401 Jia Lin Hau Marek Petrik and Mohammad Ghavamzadeh Entropic risk optimization in discounted MDPs In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics volume 206 pages 47–76 PMLR, 25–27 Apr 2023 Alexandre Marthe Aurelien Garivier and Claire Vernade Beyond average return in markov decision processes 2024 Alexandre Marthe Samuel Bounan Aurelien Garivier and Claire Vernade Efficient risk-sensitive planning via entropic risk measures 2025 Oliver Mortensen Mohammad Sadegh Talebi Entropic risk optimization in discounted mdps Sample complexity bounds with a generative model 2025

Appendix

The appendix discusses extended related work, including risk-neutral MCTS, risk-aware multi-armed bandits, and safe/constrained MCTS Appendix A reviews previous works on risk-neutral MCTS and risk-aware multi-armed bandits Appendix B details properties of the ERM and ERM estimators, including Lemma 8 which provides exponential concentration bounds for the ERM estimator Appendix C provides a proof of Theorem 1 and Appendix D provides a proof of Theorem 2 Appendix F provides a proof of Theorem 6, which relies on recursively applying Theo.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Risk-aware MCTS algorithm for ERM objectives: The proposed algorithm is provably correct in that the empirical ERM obtained at the root node converges to the optimal ERM and enjoys polynomial regret concentration. This allows it to solve risk-aware Markov decision processes with Entropic Risk Measure (ERM) objectives.

  2. Non-stationary risk-aware bandits: The system can effectively manage non-stationary bandit problems by utilizing a UCB-based algorithm that provides convergence and concentration results, even when the underlying distributions of the arms shift over time.

  3. Non-deterministic risk-aware bandits: The AI can handle non-deterministic environments where action selection triggers an immediate cost plus a second non-stationary cost associated with a random next state, achieving provable convergence and concentration through recursive application of results from non-stationary bandits.

  4. Risk trade-off optimization: The system can compute optimal behavior that trades off expected performance and risk aversion by leveraging the Entropic Risk Measure (ERM), allowing it to be tuned towards risk-averse or risk-seeking preferences.

  5. Polynomial regret concentration for MCTS: The algorithm demonstrates polynomial regret concentration, which is crucial for providing robust performance guarantees in large decision spaces when compared to baseline methods.

Sources

Related papers