arXiv CSopen access

Risk-Aware General-Utility Markov Decision Processes

Cover Page

Reinforcement Learning Journal 2026

Risk-Aware General-Utility Markov Decision Processes Pedro P. Santos, Fábio Vital, Alberto Sardinha, Francisco S. Melo Keywords: Risk-aware decision-making, Reinforcement learning, Planning.

arXiv:2607.09298v1 [cs.LG] 10 Jul 2026

Summary 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 and risk aversion while benefiting from the rich set of objectives that can be cast under the framework of GUMDPs. We focus our attention to 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 MCTS-based approach 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).

Contribution(s) 1. We motivate, propose and formalize risk-aware GUMDPs, which enable agents and decision makers to trade off expected performance and risk aversion while benefiting from the rich set of objectives that can be cast under the framework of GUMDPs. Context: Previous works studied risk-neutral (expected performance) policy optimization in GUMDPs (Zahavy et al., 2021; Mutti et al., 2023; Santos et al., 2025). 2. We show how we can solve risk-aware GUMDPs by resorting to online planning techniques, proposing an MCTS-based approach to provably solve risk-aware GUMDPs up to any desired accuracy. Context: None. 3. 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 multiobjective MDPs). Context: None.

Risk-Aware General-Utility Markov Decision Processes

Risk-Aware General-Utility Markov Decision Processes Pedro P. Santos1,2 , Fábio Vital1,2 , Alberto Sardinha1,3 , Francisco S. Melo1,2 {pedro.pinto.santos, fabiovital}@tecnico.ulisboa.pt [email protected], [email protected] 1

INESC-ID Instituto Superior Técnico, University of Lisbon 3 Pontifical Catholic University of Rio de Janeiro 2

Abstract 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 riskaware 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). Code available at https://github.com/gh0stwin/risk-aware-gumdp.

1

Introduction

Markov decision processes (MDPs) (Puterman, 2014) have found a wide range of applications in different domains, ranging from optimal stopping (Chow et al., 1971), inventory management (Dvoretzky et al., 1952), or queueing control (Stidham, 1978). MDPs also play a central role in reinforcement learning (RL) (Sutton & Barto, 2018), where the agent-environment interaction is typically modelled within the MDP framework. In recent years, RL has achieved remarkable success across diverse domains (Mnih et al., 2015; Silver et al., 2017; Lillicrap et al., 2016). However, many relevant objectives cannot be easily expressed within the standard MDP framework (Abel et al., 2022). Examples include imitation learning (Hussein et al., 2017; Osa et al., 2018), pure exploration problems (Hazan et al., 2019), risk-averse RL (García et al., 2015), diverse skills discovery (Eysenbach et al., 2018; Achiam et al., 2018), and constrained MDPs (Altman, 1999; Efroni et al., 2020). To address these limitations, the framework of general-utility Markov decision processes (GUMDPs) has been proposed as a more expressive formalism capable of modelling such objectives (Santos et al., 2024). In GUMDPs, the agent’s objective is encoded as a function of the occupancy induced by a given policy, i.e., as a function of the frequency of visitation of state-action pairs induced by a given policy. GUMDPs generalize MDPs by allowing the objective function to be a non-linear function of occupancies.

Reinforcement Learning Journal

2

1

a0

a1 0

2

1 a0

a1 3

ϵ

20

a1

a0

0

(b) Abstracted environment.

Policy 1

0.6

Policy 2

0.5 0.4 0.6 0.8

1

Objective value 1−ϵ

0.7

MRE

(a) Environment illustration.

0.8

40

ytisneD

0

2026

0

5

10

Beta

(c) Objective function density (left) and respective ERMβ values (right) for two policies π1 (Policy 1) and π2 (Policy 2). Lower values are better.

Figure 1: Motivating example: Exploring three rooms.

Previous studies have been focused on studying policy optimization in GUMDPs by considering risk-neutral objectives, where the performance of a given policy is evaluated in terms of its induced expected frequency of visitation of states (Mutti et al., 2023; Santos et al., 2025; Zahavy et al., 2021; Geist et al., 2022). However, these approaches overlook the variability in the objective: for a fixed policy, the stochastic nature of the environment can lead to a distribution over possible state-action visitation frequencies, resulting in a range of potential objective values. Consequently, optimizing only for the expectation may fail to capture important aspects of the policy’s performance. Given the stochasticity of the possible outcomes, it is thus natural to consider optimizing a specific risk measure (Artzner et al., 1999) over the distribution of objective values, enabling the learned behavior to be tuned toward risk-seeking or risk-averse preferences. The entropic risk measure (ERM) (Howard & Matheson, 1972) is one of the most common risk measures, which has received considerable attention across various domains such as finance and sequential decision-making (Föllmer & Schied, 2016; Borkar & Meyn, 2002; Pagnoncelli et al., 2022; Lin Hau et al., 2023; Marthe et al., 2025; Mortensen & Talebi, 2025). As a risk-aware criterion, the ERM enables agents/decision-makers to trade off between expected performance and risk aversion, providing robustness against adverse (worst-case) outcomes. To further motivate the relevance of trading off between risk-neutral and risk-averse behaviors in the context of GUMDPs, we present the following illustrative example. Motivating example We consider the illustrative environment in Figure 1a, where a robot aims to explore three rooms as uniformly as possible (pure exploration task (Hazan et al., 2019)). Transitioning from room 1 to room 0 incurs no danger to the robot. However, attempting to transition from room 1 to room 2 may cause irreparable damage to the robot, rendering it unable to explore the environment further. The dynamics of this environment can be abstracted by the MDP in Figure 1b, where each state corresponds to one of the rooms, the actions encode the transitions between rooms, and ϵ ∈ (0, 1) is the probability of irreparable damage to the robot when attempting to transition between rooms 1 and 2. We can resort to a GUMDP to encode the agent’s objective by setting the objective function to be (minus) the entropy of the occupancy induced by any policy. Now, a riskaverse agent will not be interested in trying to explore state 2 since there exists a probability that it will get absorbed into state 3 and, thus, not being able to explore the environment further. On the other hand, a risk-seeker agent will try to visit state 2 since it may be successful, hence exploring all three rooms. In Figure 1c, we compare two policies: (i) π1 , a risk-seeking policy that attempts to visit state 2; and (ii) π2 , a risk-averse policy that does not attempt to visit state 2 and, instead, keeps alternating between states 0 and 1. The left plot shows the density of the objective values for the policies. Both policies yield very different distributions, with the risk-seeking policy π1 attaining lower (better) objective values at the cost of sometimes obtaining higher (worse) objective values. On the other hand, the risk-averse policy π2 always attains the same intermediate objective value due to its deterministic behavior. The plot on the right shows the ERMβ of both policies as a function of β ∈ (0, ∞). Higher β values correspond to more risk-averse preferences, while β approaching

Risk-Aware General-Utility Markov Decision Processes

zero reflects risk neutrality. As shown, π2 achieves a lower ERMβ value for higher β, confirming its risk-averse behavior. Conversely, as β decreases, π1 becomes the superior policy. Contributions We study risk-aware GUMDPs with ERM objectives. As a risk-aware criterion, the ERM enables agents/decision-makers to trade off between expected performance and risk aversion, providing robustness against adverse (worst-case) outcomes. Our contributions are threefold. First, we motivate, propose, and formalize risk-aware GUMDPs, which enable agents to trade off between expected performance and 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 ERM, as it has been commonly used by previous works in the context of MDPs (Borkar & Meyn, 2002; Pagnoncelli et al., 2022; Lin Hau et al., 2023; Marthe et al., 2025; Mortensen & Talebi, 2025). Second, we show how we can solve risk-aware GUMDPs with ERM objectives (ERM-GUMDP) by resorting to online planning techniques. In particular, we show that any ERM-GUMDP can be reformulated as a specific MDP — referred to as an occupancy MDP — with an ERM objective. This reformulation enables the use of online planning techniques to compute approximately optimal policies for arbitrary ERM-GUMDPs. We propose an MCTS-based approach to provably solve risk-aware GUMDPs up to any desired accuracy. Third, we provide experimental results showing that our approach successfully optimizes 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).

2

Background

2.1

Markov decision processes

MDPs (Puterman, 2014) can be defined by the tuple M = (S, A, {P a : a ∈ A}, p0 , c) where: S is the discrete state space; A is the discrete action space; {P a : a ∈ A} is a set of transition probability matrices P a for each action a ∈ A; p0 ∈ ∆(S) is the distribution of initial states; and c : S ×A → R is a cost function. The interaction between the agent and its environment, as modeled by the MDP framework, is as follows: (i) an initial state s0 is sampled from p0 ; (ii) at each step t, the agent observes the state of the environment st ∈ S and chooses an action at ∈ A. Depending on the action chosen by the agent, the MDP evolves to a new state st+1 ∈ S with probability given by P at (st , ·), and the agent receives a cost c(st , at ); and (iii) the interaction repeats infinitely. A decision rule πt specifies the action-selection mechanism at timestep t. A non-Markovian decision rule maps the history of states and actions to a probability distribution over actions, i.e., πt : S × (S × A)t → ∆(A). In contrast, a Markovian decision rule depends only on the current state and maps it to a distribution over actions, i.e., πt : S → ∆(A). Both types of decision rules can be deterministic if they map directly to actions rather than distributions: for non-Markovian rules, πt : S × (S × A)t → A, and for Markovian rules, πt : S → A. A policy π = (π0 , π1 , . . .) is a sequence of decision rules, one for each timestep. A policy is Markovian or non-Markovian if all its decision rules are Markovian or non-Markovian, respectively. Likewise, a policy is deterministic or stochastic if all its decision rules are deterministic or stochastic. We denote the set of non-Markovian policies by ΠNM , Markovian policies by ΠM , non-Markovian deterministic policies by ΠD NM , and Markovian deterministic policies by ΠD . A policy is stationary if it uses the same decision rule at M every timestep. We denote the set of stationary policies by ΠS and the set of stationary deterministic policies by ΠD S . Among the relationships between these classes, we highlight the following: (i) ΠNM D D is the most general class; (ii) ΠS ⊂ ΠM ⊂ ΠNM ; and (iii) ΠD S ⊂ ΠM ⊂ ΠNM . For a given policy π ∈ ΠNM , the interaction between the agent and the environment induces a random process (s0 , a0 , s1 , a1 , . . .). We denote by ht = (s0 , a0 , s1 , a1 , . . . , st ) the random history up to and including timestep t, and by ht = (s0 , a0 , s1 , a1 , . . . , st ) ∈ S × (S × A)t a particular realization of such a history. The random process (s0 , a0 , s1 , a1 , . . .) satisfies the following conditions: (i) P[s0 = s] = p0 (s); (ii) P[st+1 = s′ | ht , at ] = P at (st , s′ ); and (iii) P[at = a | ht ] = π(a | ht ). Let (Ω, F, Pπ ) be the probability space over trajectories (s0 , a0 , s1 , a1 , . . .) satisfying (i)–(iii), as defined in Lattimore & Szepesvári (2020). We denote a sample trajectory by ω ∈ Ω, where

Reinforcement Learning Journal

2026

ω = (s0 , a0 , s1 , a1 , . . .). We also let Pπ [st = s, at = a] be the probability of observing the stateaction pair (s, a) at timestep t under the MDP while following policy π. P∞ The expected discounted cumulative cost objective is Jγπ = E [ t=0 γ t c(st , at )] , where γ ∈ (0, 1) is the discount factor and the expectation is taken over the random trajectory of state-action pairs. The discounted state-action occupancy for policy π is defined as dπ (s, a) = (1 − γ)

∞ X

γ t Pπ [st = s, at = a] .

(1)

t=0

The expected discounted cumulative cost of policy π can be rewritten as Jγπ = c⊤ dπ , where dπ = [dπ (s0 , a0 ), . . . , dπ (s|S| , a|A| )]⊤ , c = [c(s0 , a0 ), . . . , c(s|S| , a|A| )]⊤ . We aim to find π ∗ = arg minπ∈ΠS Jγπ , which can be formulated as a linear program (Puterman, 2014). 2.2

Risk-aware MDPs

Risk-aware MDPs (Chow et al., 2015) generalize the classical MDP framework by considering π = theP associated variability of the discounted cumulative costs. This is done by considering Jγ,ρ ∞ ρ ( t=0 γ t c(st , at )) , where ρ is a risk measure (Artzner et al., 1999), computed over the random trajectory. Risk measures quantify an agent’s attitude toward uncertainty and variability in outcomes. We note that for ρ(·) = E[·] we have the standard discounted MDP objective. The risk-aware objective allows the agent to reason over the entire distribution instead of just its expectation. In this work, we consider risk-aware MDPs with an ERM objective (Howard & Matheson, 1972). The ERM of a random variable z is defined as ERMβ (z) = β1 ln (E [exp(βz)]), where parameter β ∈ (0, ∞) trades off between expected performance as β → 0 and risk-aversion as β increases. Also, the ERMβ belongs to the family of optimized certainty equivalents (OCEs) (Ben-Tal & Teboulle, 1986) since it can be equivalently defined as ERMβ (z) = minλ∈R {λ + E [u(z − λ)]} , where u(x) = β1 (exp(βx) − 1). In this work, we focus our attention on the ERMβ and, thus, we implicitly refer to the ERMβ whenever we write ρ. 2.3

General-utility MDPs

GUMDPs generalize utility specification by allowing the agent’s objective to be written in terms of the frequency of visitation of state-action pairs. This is in contrast to the standard MDPs framework, where the objective of the agent is encoded by the cost function. We define an infinite-horizon discounted GUMDP as a tuple Mf = (S, A, {P a : a ∈ A}, p0 , f ), where S, A, {P a : a ∈ A}, and p0 are defined in a similar way to the standard MDP formulation, as introduced in Sec. 2.1. The function f : ∆(S × A) → R encodes the objective of the agent, which depends on a discounted occupancy d, as defined in (1). We then aim to find π ∗ ∈ arg minπ∈ΠS f (dπ ). If f is a linear function, then we are under the standard MDP setting. If f is convex, then we are under the convex MDP/RL setting (Zahavy et al., 2021). In this work, we consider four tasks, each associated with a particular objective function: (i) cost minimization (standard MDP) (Puterman, 2014), where f (d) = c⊤ d and c ∈ R|S||A| is the column vector encoding the cost function; (ii) maximum state entropy exploration (MSEE) (Hazan et al., 2019), where f (d) = d⊤ log(d), i.e., we aim to find a policy that visits all state-action pairs as uniformly as possible; (iii) imitation learning (IL) (Abbeel & Ng, 2004), where f (d) = ∥d − dπb ∥22 with dπb ∈ ∆(S × A), i.e., we aim to find a policy such that its induced occupancy is as similar as possible to the occupancy dπb induced by a given behavior policy πb ; and (iv) multi-objective (MO) MDPs, where f (d) = g(d⊤ c1 , . . . , d⊤ ck ), where c1 , . . . , ck ∈ R|S||A| are vectorized cost functions and g is an utility function (Radulescu et al., 2019). Nevertheless, we highlight that our results apply to any task that can be modeled using the GUMDPs framework. We refer to Zahavy et al. (2021) for a comprehensive list of the different objectives considered by previous works.

Risk-Aware General-Utility Markov Decision Processes

3

Towards Risk-Aware GUMDPs

We now introduce the framework of risk-aware GUMDPs. Because risk-awareness requires reasoning about the underlying distribution of objective values, we begin by adopting a distributional perspective on GUMDPs. Similarly to distributional RL (Bellemare et al., 2023), we employ the following assumption to ensure that all random variables defined below are bounded and well-defined. Assumption 3.1. The objective f satisfies f (d) ∈ Y = [−R, R], ∀d ∈ ∆(S × A), where R ∈ R+ . 3.1

A distributional perspective on GUMDPs

For a given fixed policy π ∈ ΠNM , let dπ : Ω → ∆(S × A) be the random vector defined on the probability space (Ω, F, Pπ ) with entries dπs,a (ω) = (1 − γ)

∞ X

γ t 1(st = s, at = a).

(2)

t=0

The random vector above is well-defined since the mapping dπ is F/B(∆(S × A)) measurable, where B(∆(S × A)) denotes the Borel σ-algebra of ∆(S × A). Let also f π : Ω → Y be the random variable with support in Y such that f π (ω) = (f ◦ dπ )(ω) = f (dπ (ω)), satisfying P [f π ≤ η] = Pπ [{ω ∈ Ω : f (dπ (ω)) ≤ η}] ,

∀η ∈ Y,

where we assume f is a Borel measurable function. Essentially, the random variable f π is defined as the composition of two measurable mappings. If f is continuous, then f is Borel measurable. We refer to Figure 1c for an illustration of the density associated with the random variable f π for two arbitrary policies. As observed, the underlying distributions induced by different policies can differ substantially and, therefore, depending on the exact preferences of the decision-maker, one policy may be preferable over the other. Risk measures, such as the ERMβ , allow for the comparison between distributions induced by different policies. 3.2

Risk-aware GUMDPs

In the context of GUMDPs, we denote L the set of possible random variables with support in Y associated with each of the probability spaces (Ω, F, Pπ ), for all π ∈ ΠNM . Note that f π ∈ L for any π ∈ ΠNM . Then, we consider risk measures ρ : L → R that associate any random variable in L with a scalar value. In this work, we are particularly interested in the ERMβ , as introduced in Sec. 2.2. We aim to find π ∗ = arg min ρ(f π ). (3) π∈ΠNM

 ′ For any policy π ∈ ΠNM , we define its optimality gap as OptGap(π) = ρ (f π )−minπ′ ∈ΠNM ρ f π . Essentially, OptGap(π) measures how suboptimal a given policy π is compared to the best policy.

Policy optimization in risk-aware GUMDPs While in the context of risk-aware MDPs with ERM objectives the class of deterministic and Markovian policies, ΠD M , suffices for optimality (Lin Hau et al., 2023), this is no longer the case in the context of risk-aware GUMDPs with ERM objectives. As shown in Santos et al. (2025) in the context of GUMDPs, if ρ(·) = E[·] then the class of Markovian policies is strictly dominated by the class of non-Markovian policies. Since, in the context of risk-aware GUMDPs, as β → 0 the ERMβ approaches E[·], non-Markovian policies are also needed, in general, in the context of solving GUMDPs with ERM objectives.

Reinforcement Learning Journal

4

2026

Solving Risk-Aware GUMDPs with Online Planning

In this section, we study how to solve risk-aware GUMDPs using online planning techniques. We begin by establishing a close connection between risk-aware GUMDPs and a particular risk-aware MDP in which the agent tracks the accrued occupancy at each timestep. Leveraging this formulation, we show that solving the risk-aware MDP with online planning techniques yields approximately optimal action selection for the original risk-aware GUMDP. Assumption 4.1. The objective function f is Lf -Lipschitz, i.e., |f (d1 ) − f (d2 )| ≤ Lf ∥d1 − d2 ∥1 , for any d1 , d2 ∈ ∆(S × A). We refer to Appendix 8 for the derivation of Lf -Lipschitz constants for the objective functions considered. 4.1

Computing optimal policies by resorting to finite-horizon GUMDPs

We start by showing that we can compute an approximately optimal policy for our infinite-horizon discounted risk-aware objective (3) by resorting to a finite-horizon formulation of the same problem. π For any policy π ∈ ΠNM , let fH : Ω → Y be the random variable with support in Y such that π fH (ω) = (f ◦ dπ,H )(ω) = f (dπ,H (ω))

dπ,H s,a (ω) =

H−1 X

1−γ γ t 1(st = s, at = a). 1 − γ H t=0

(4) (5)

π Essentially, random variable fH is defined in a similar fashion to the random variable f π , but the former considers a random occupancy dπ,H that only takes into account the state-action pairs visited up to a given horizon H ∈ N. We state the following result (proof in Appendix 9).

Proposition 4.2 (Optimality gap decomposition). For arbitrary π ∈ ΠNM , it holds that n o π π′ OptGap(π) ≤ ρ(fH ) − ′min ρ(fH ) + 8Lf γ H , π ∈ΠNM | {z } = OptGapH (π)

where OptGapH (π) is the optimality gap of policy π for the truncated objective with horizon H. The result above shows that we can resort to the truncated objective to compute approximately optimal policies, up to any desired accuracy, for the infinite-horizon risk-aware objective (3). π π ), where fH is deTherefore, we focus our attention on solving π ∗ = arg minπ∈ΠNM ρ(fH fined in (4). Since we now focus on the case of finite-horizon trajectories, we assume that, for a given policy π ∈ ΠNM , the interaction between the agent and the environment gives rise to a random process (s0 , a0 , s1 , a1 , . . . , sH−1 , aH−1 ) such that: (i) P [s0 = s] = p0 (s); (ii) P [st+1 = s′ |ht , at ] = P at (st , s′ ); and (iii) P [at = a|ht ] = π(a|ht ). We thus let from now on (Ω, F , Pπ ) be the probability space over the sequence of random variables (s0 , a0 , s1 , a1 , . . . , sH−1 , aH−1 ) that satisfies conditions (i)-(iii) above. We write specific trajectories as ω ∈ Ω, with ω = (s0 , a0 , s1 , a1 , . . . , sH−1 , aH−1 ). We highlight that the probability of a given trajectory ω ∈ Ω under policy π ∈ ΠNM can be calculated as Pπ [ω] = p0 (s0 ) · π(a0 |h0 ) · P a0 (s0 , s1 ) · π(a1 |h1 ) · P a1 (s1 , s2 ) . . . P aH−2 (sH−2 , sH−1 ) · π(aH−1 |hH−1 ). 4.2

The occupancy MDP

To derive our planning algorithms for solving risk-aware GUMDPs, we make use of a finite-horizon MDP derived from the original GUMDP formulation. In particular, we consider the occupancy MDP (Santos et al., 2025), defined by the tuple MO = {SO , AO , {P aO : a ∈ A}, p0,O , cO , H}, where SO = S × O is the discrete state space and O is the set of occupancies up to length H − 1 in the original GUMDP. We let {s, o} be a state of the occupancy MDP such that s ∈ S is a state

Risk-Aware General-Utility Markov Decision Processes

from the original GUMDP and o ∈ O is a |S||A|-dimensional vector that keeps track of the running occupancy of the agent up to a given timestep. Then, AO = A is the action space and p0,O is such that p0,O ({s, o}) = p0 (s) if o = [0, . . . , 0] and zero otherwise. The dynamics are as follows: (i) component st+1 ∼ P at (·|st ) evolves according to the dynamics of the original GUMDP; and (ii) the running occupancy evolves deterministically as ot+1 (s, a) = γ t + ot (s, a) if s = st and a = at , and ot+1 (s, a) = ot (s, a) otherwise. Finally, H ∈ N denotes the horizon and the cost function cO : S × O → R is defined as ( 0  if t < H, cO ({s, o}) = 1−γ f 1−γ H o if t = H. Stationary policies πO ∈ ΠS for MO are mappings of the type πO : S ×O → ∆(A). For a given policy πO ∈ ΠS , the interaction between the agent and the occupancy MDP gives rise to a random process ({s0 , o0 }, a0 , {s1 , o1 }, a1 , . . . , {sH , oH }) associated with the probability space (ΩO , FO , PO πO ). We write specific trajectories as ωO ∈ ΩO , with ωO = ({s0 , o0 }, a0 , {s1 , o1 }, a1 , . . . , {sH , oH }).

For any policy πO ∈ ΠS , we let JπOO : ΩO → Y be the random variable with support in Y associated PH πO with the probability space (ΩO , FO , PO πO ) such that JO (ωO ) = t=0 cO ({st , ot }). We reproduce the following result from Santos et al. (2025). Lemma 4.3 (One-to-one mapping between histories in Mf and states in MO ). There exists a oneto-one mapping between histories hl = (s0 , a0 , s1 , a1 , . . . , sl ) ∈ S × (S × A)l in Mf , with 0 ≤ l ≤ H − 1, and states {s, o} ∈ S × O in MO . An important conclusion that can be derived from the result above is that there exists a one-to-one mapping between non-Markovian policies for Mf and stationary policies for MO . This is because every state in MO is uniquely associated with a particular history in Mf (and vice versa), as the result above shows. With this in mind, we now state the following results (proofs in Appendix 9). π and JπOO ). For any horizon H ∈ N and policy Lemma 4.4 (Equivalence in distribution between fH D

π π and JπOO are equal in distribution, where π ∈ ΠNM , it holds that fH = JπOO , i.e., random variables fH πO is the stationary policy for MO associated with the non-Markovian policy π for Mf . Theorem 4.5 (Solving the risk-aware Mf is “equivalent” to solving the risk-aware MO ). For a given risk measure ρ : L → R, the problem of finding a policy π ∈ ΠNM satisfying OptGapH (π) ≤ ϵ, for any ϵ ∈ R+ 0 , can be reduced to the problem of finding a policy πO ∈ ΠS satisfying  ′ π ρ (JπOO ) − min ρ JOO ≤ ϵ. ′ πO ∈ΠS

In particular, if πO∗ = arg minπO ∈ΠS ρ(JπOO ), then the corresponding non-Markovian policy  π in Mf π′

satisfies OptGapH (π) = 0. It also holds that OptGapH (π) = ρ (JπOO )−minπO′ ∈ΠS ρ JOO , where πO is the stationary policy for MO associated with the non-Markovian policy π for Mf . The result above shows that it suffices to search for an (approximately) stationary optimal policy for MO , since such a policy corresponds to a non-Markovian policy that is (approximately) optimal for Mf . In particular, such an (approximately) optimal policy for MO can be seen as a non-Markovian policy for Mf that compresses the history up to any timestep into a running occupancy. The result above shows that it suffices to keep track of the running occupancy up to any timestep in order to attain optimal behavior when solving risk-aware GUMDPs. In light of Theorem 4.5, we consider risk-aware planning algorithms to solve the occupancy MDP. Unfortunately, solving the risk-aware occupancy MDP poses some challenges. One of the key challenges is due to the fact that the size of the state space of the occupancy MDP grows combinatorially with H since every state in the occupancy MDP is associated with a possible history in Mf . Consequently, the state space of the occupancy MDP is typically very large, which precludes the use of offline planning methods. In the next section, we therefore turn to online planning approaches to implicitly compute approximately risk-aware optimal policies for the occupancy MDP.

Reinforcement Learning Journal

4.3

2026

Solving risk-aware occupancy MDPs via online planning

We aim to propose a practical algorithm to compute an approximately optimal risk-aware policy for the occupancy MDP MO , as introduced in Sec. 4.2. Since the occupancy MDP is a standard undiscounted finite-horizon MDP, we can resort to the risk-aware Monte Carlo tree search (MCTS) algorithm put forth by Santos et al. (2026), ERM-MCTS, to solve the risk-aware occupancy MDP with the ERM objective. ERM-MCTS works in a similar fashion to standard MCTS in the sense that the algorithm iteratively builds a search tree that alternates between decision nodes, where actions are selected, and chance nodes corresponding to random next states sampled from the MDP. At each iteration, ERM-MCTS refines the search tree by simulating a random trajectory in the occupancy MDP. Action-selection at each decision node st ∈ SO is given by   sp ) ( N (st ,a)   X N (st ) 1 1  (st ,a)  ln exp βxi − θt , at ∈ arg min β N (st , a) i=1 N (st , a) a∈A where N (st ) is the number of times st has been visited, N (st , a) the number of times action a has (s ,a) been selected while in st , xi t is the i-th sampled terminal cost starting from (st , a) (given that the occupancy MDP only has non-zero costs at t = H), and θt is an exploration constant. In case N (st , a) = 0 for some a ∈ A, then a is selected. We refer to Appendix 10 for the full pseudocode of the ERM-MCTS algorithm. Without loss of generality, assume we fix an initial state s0 ∈ S. We state the following result, which is a consequence of Theo. 6 in Santos et al. (2026). Theorem 4.6. There exist exploration constants (θ0 , θ1 , . . . , θH−1 ) such that, from any initial state s0 ∈ S, ERM-MCTS provably the risk-awareoccupancy  solves  MDP with an ERM objective. More P PTa (n) (s ,a) precisely, let V̂n (s0 ) = β1 ln n1 a∈A i=1 exp βxi t be the empirical ERM obtained by the ERM-MCTS algorithm after n iterations at initial state s0 , where Ta (n) denotes the number of times action a was selected at root node s0 after n iterations. Then,  ′  (b) i (a) n h o π π′ ρ JOO = ′min ρ(fH lim E V̂n (s0 ) = min ) , ′ n→∞

πO ∈ΠS

π ∈ΠNM

where: (a) follows from Theo. 6 in Santos et al. (2026) as the expected empirical ERM obtained by ERM-MCTS converges, in the limit, to the optimal ERM for the occupancy MDP; and (b) follows from Theo. 4.5.

5

Experimental Results

We empirically assess the performance of ERM-MCTS for solving risk-aware GUMDPs, investigating how ERM-MCTS trades off risk-neutral and risk-averse behavior. We describe our experimental methodology and refer to Appendix 11 for a complete description of our experiments (environments, baselines, hyperparameters, etc.). We consider four tasks: (i) cost minimization (MDP); (ii) maximum state entropy exploration (MSEE); (iii) imitation learning (IL); and (iv) multi-objective (MO) MDPs with different utility functions. The definition of the objective function for each task is given in Sec. 2.3. We consider two sets of environments: (i) illustrative environments that consist of low-dimensional GUMDPs; and (ii) high-dimensional GUMDPs consisting of grid-based environments showcasing different sources of stochasticity in order to encourage distinct types of policy behaviors. To our knowledge, we are the first work to propose an algorithm to solve risk-aware GUMDPs and, hence, there are no baselines that we can use to compare the performance of our method against. However, for the particular case of linear f (MDP), we use an oracle baseline ERM-BI to validate the performance of our ERM-MCTS algorithm. ERM-BI computes the optimal risk-aware policy for the underlying occupancy MDP using a dynamic programming approach by exploiting the dynamic decomposition of the ERMβ put forth by Lin Hau et al. (2023). All our plots are computed by aggregating the experimental results of, at least, 100 independent runs, and we refer to Tables 2 and 3 for the detailed list of our experimental hyperparameters across all environments.

Risk-Aware General-Utility Markov Decision Processes

0 c=0

a0 0.85 0.15

(0, −0.2)

(−1, 0)

1

a1

a0

c=5

a1

a0

0

2

1 a0

2

a1

a0

a1

(0, 0)

1

3

0.4

a1 4

3

0.6

0.6

0.4

2

0.2

(c1 (s), c2 (s))

(0.5, 0)

c = 20

a1

3

0

0.8

c=1

a0

(b) MSEE

4 (0, 0.2)

(c) MO

(a) MDP and IL (10% reset)

Figure 2: Illustrative environments.

Standard MDP

Maximum state entropy expl. 0.5 0.45 0.4 0.35

tsoC

0.8 0.6 0.4 0.2 0

0.1

5.0

10.0

0.1 0.05 25.0

50.0

Beta

Beta

Multi-objective (weighted)

Multi-objective (max)

−0.2

0

tsoC

0.1

−0.4

0.1

20.0

40.0

Beta

Imitation learning

0.15

0.1

0

0.2

0

0.1

40.0

80.0

Beta Multi-objective (min) 0 −0.1 −0.2 −0.3

0.1

10.0

20.0

Beta ERM-BI

0.1

20.0

50.0

Beta ERM-MCTS

Figure 3: Box plots of the costs obtained under the illustrative environments. Lower is better.

5.1

Illustrative environments

We display in Fig. 2 our illustrative environments. The MDP (Fig. 2 (a)) consists of a four-state MDP where the agent needs to tradeoff at the initial state (s0 ) between: (i) a risky action (a0 ) that can lead to a low-cost state (s2 ), but with some probability the agent ends in a high-cost state (s3 ); and (ii) a safe action (a1 ) that deterministically leads to a medium-cost state (s1 ). The agent resets to the initial state with 10% probability while not in the initial state. For the IL task (Fig. 2 (a)), the agent aims to imitate the empirical occupancy induced by the trajectory of an agent that selected twice the risky action (a0 ) and then selected the safe action (a1 ) for all the remainder timesteps. The trajectory to imitate had a rather “lucky” outcome, as it never ended up in the absorbing state (s3 ). Hence, the agent needs to trade off between imitating the behavior policy in states (s0 , s1 , s2 ) and risking being absorbed into s3 , or only imitating the behavior policy in the “less risky” states (s0 , s1 ). The MSEE task (Fig. 2 (b)) is similar to the motivating example from Sec. 1, where the agent aims to explore an environment as uniformly as possible, but there is a chance that the agent transitions to an absorbing state (s4 ). Finally, the MO-MDP (Fig. 2 (c)) is inspired by the FishWood environment (Roijers et al., 2020), where the agent needs to tradeoff between two cost functions. Each cost function penalizes different behaviors. We consider three utility functions (Hayes et al., 2022): (i) a weighted combination of the discounted cumulative costs; (ii) the maximum of the discounted cumulative costs; and (iii) the minimum of the discounted cumulative costs. In Fig. 3, we display the box plots computed for the empirical distributions of costs obtained by ERM-MCTS under different tasks and β values. To validate our algorithm, we include a costminimization task corresponding to a standard MDP. As seen, for the MDP, the box plot obtained by ERM-MCTS closely matches that obtained by the ERM-BI oracle baseline across the tested β

Reinforcement Learning Journal

2026

values, providing empirical validation of ERM-MCTS. Furthermore, across all tasks, ERM-MCTS successfully trades off risk-neutral and risk-averse behavior as a function of β. As β increases and ERM-MCTS progressively focuses on optimizing worst-case outcomes, upper whiskers and outliers (i.e., the worst outcomes) of the box plots decrease. This indicates that worst-case outcomes become less probable and that ERM-MCTS effectively computes increasingly risk-averse policies. Naturally, optimizing for worst-case outcomes typically degrades best-case or expected outcomes, as reflected by the increase in median values and in the lower whiskers and outliers as β increases. 5.2 5.2.1

Grid environments Maximum State Entropy Exploration

The MSEE task integrates a 10 × 10 grid that comprises two different types of squares: (i) normal terrain; and (ii) difficult terrain. The agent can move in all four directions, ending up in the corresponding adjacent square (if moving out-of-bounds, the agent remains in the same square). When the agent is inside a difficult terrain square, there is a pstuck probability that the agent gets stuck, which translates in canceling the selected (moving) action and thus remaining trapped in the current square. Upon getting stuck, there is an additional punstuck probability that untraps the agent allowing it to move freely again. As expected, inside normal terrain, the agent’s selected moving action is always guaranteed to occur. Due to the environment’s stochastic nature, the agent needs to consider if there are benefits in exploring certain difficult terrain squares at the expense of getting stuck, which can have a negative effect on the discounted costs received from that point onward. In Figure 4a, we report the box plots of the empirical costs obtained by ERM-MCTS with β ∈ {0.001, 1, 1000}. When β ∈ {0.001, 1}, ERM-MCTS outputs similar risk-seeking policies, as both display identical Inner Fence Interval (IFI) ranges, inside [0.1, 0.2]. Additionally, the expectation value is lower when β = 0.001, having a value of 0.167, whereas the expectation for β = 1 is 0.177. Furthermore, both policies exhibit a wide range of outliers on the upper-half of the distribution, implying that in some runs the agent got trapped for long periods of time when covering difficult terrain squares, further alluding to the potential disadvantages of having a risk-seeking behavior. Additionally, the worst outlier is higher for the policy with β = 0.001, which is expected since this policy is effectively closer to the risk-seeking (or risk-neutral) boundary in the risk-awareness spectrum. When comparing the policy obtained when β = 1000 to the the previous two (β ∈ {0.001, 1}), the range of the objective distribution becomes more concentrated as there are fewer outliers. This shows the effectiveness of the risk-averse behavior in avoiding the worst outcomes, as the highest cost is only 0.48 when setting β = 1000, vs. 0.93 using β = 0.001. The drawback of this policy manifests by inducing an average case that performs worse than policies that are more risk-seeking, where the average of the objective distributions are 0.30 and 0.167, for the policies using β = 1000 and β = 0.001, respectively. Finally, we further validate our analysis with Figure 5, which exposes the average number of timesteps spent in each square over all runs. We observe that when β = 1000, the policy navigates towards the lower-right corner to avoid difficult terrain squares altogether. As β decreases, the heatmap becomes more uniformly distributed showcasing that the policy tries to visit all squares (normal and difficult terrain) more often. 5.2.2

Imitation Learning

We reuse the MSEE environment for our IL task. Additionally, we carefully design a behavior policy that changes from risk-seeking and risk-aware behaviors at well-defined intervals. In highlevel terms, the behavior policy starts by exploring a zone containing both types of squares, followed by a period where only normal squares are visited. This procedure repeats a second time to make sure all grid squares are visited once. Furthermore, the behavior policy will not be subjected to the environment’s stochasticity, i.e., it will never get trapped when visiting difficult terrain. In this manner, we guarantee that achieving a complete match will be extremely unlikely, further leading the ERM-MCTS policy to consider when and what risks to take.

Risk-Aware General-Utility Markov Decision Processes

1 0.8 0.6

0.001

1.0

Beta

1000.0

tsoC

0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

tsoC

tsoC

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

0.4 0.2

0.002

(a) MSEE

1.0

Beta

500.0

(b) IL

0

0.125

1.0

Beta

8.0

(c) MO

Figure 4: Grid environments: box plots obtained, for different tasks, by deploying ERM-MCTS with different β values. Box plots computed for 128 independent runs. Lower is better. 0.08 0.06 0.04 0.02

Grid

Beta = 0.001

Beta = 1.0

Beta = 1000.0

Figure 5: MSEE (grid environment): leftmost grid illustrates the environment, where normal and difficult terrain are depicted in gray and black squares, respectively; the following grids showcase the average time spent in each square averaged over all (128) runs, for each β ∈ {0.001, 1, 1000}. To analyze the IL task, we compare ERM-MCTS with three different beta values, β ∈ {0.02, 1, 500}. As shown in Figure 4b, we clearly observe the same pattern reported in the MSEE task (Sec. 5.2.1): as β increases, the maximum cost obtained decreases while the expectation and median increase. Here, the expectation obtains the values 0.106, 0.109, and 0.192, while the median acquires 0.08, 0.09, and 0.18 for the policies with β = 0.02, β = 1, and β = 500, respectively. Conversely, and for the same policies, the uppermost outliers are 0.81, 0.65, and 0.44, respectively. To get a closer look at how behaviors differ as β changes, we plot, in Figure 6, the average number of runs visiting difficult terrain squares in each timestep. Interestingly, the policy with the highest β emphasizes matching the occupancy of normal squares during the first 40 time steps, as there is a negligible number of runs stepping inside difficult terrain. For the remaining time, the policy focuses more on equalizing the occupancy at difficult terrain squares, as outlined by the increased number of runs exploring such squares. We argue that such behavior is due to discounting, since it is more forgiving to get trapped closer to the end of the episode, considering that it has less impact on the discounted return. Contrastingly, the other policies (β ∈ {0.02, 1}) start visiting difficult terrain squares from the beginning of the episode. Consequently, the likelihood of getting trapped sooner and for longer periods of time increases, as hinted in Figure 4b by the wide range of outliers on the upper half of the cost distribution. 5.2.3

Multi-Objective

For the MO task, we extend the resource-gathering environment (Barrett & Narayanan, 2008), aiming at introducing challenging probabilistic dynamics that allow the modulation of policies demonstrating behaviors with different degrees of risk-awareness. In the modified environment, the agent’s objective consists in retrieving two different resources (R1 and R2 ) back to its starting location while avoiding enemies present at specific squares. Additionally, we set a slippery dynamic, where with probability pslip the agent will move perpendicularly to the selected direction. All agent objectives are modulated using the following reward functions: (i) agent receives a cost when failing to deliver R1 to the home location (the agent’s initial position); (ii) agent receives a cost when failing to delivering R2 to the home location; (iii) agent receives a cost when getting defeated by an enemy, which

Reinforcement Learning Journal

Beta

0.002

2026

1.0

500.0

snur fo .rn .gvA

60 40 30 20 10 0

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

defeated no resource resource 1 resource 2 both resources

.borp emoctuO

50

Outcome

0

20

40

60

Timestep

80

Figure 6: IL (grid environment): Average number of runs visiting difficult terrain squares in each timestep for different β values.

0.125

1.0

Beta

8.0

Figure 7: MO (grid environment): Probability of each outcome for different β values.

happens, with probability pdefeat , when visiting a square containing an enemy. Finally, we combine the three independent reward functions using a non-linear mapping that prioritizes collecting R1 over the other ones. We refer to Appendix 11.5.1 for a complete description of the dynamics, cost functions, and hyperparameters used. We simulate ERM-MCTS with β ∈ {0.125, 1, 8}. As shown in Figure 4c, the cost distributions obtained by the policies where β ∈ {0.125, 1} are highly identical. We again observe the riskseeking behavior of these policies, since, on average, the costs obtained remain concentrated near the lower bound. For instance, the expectation is 0.16 and 0.18 for β = 0.125 and β = 1, respectively. The IFI is [0.10, 0.14] in both cases. Furthermore, since during the optimization of the ERM’s objective, the expectation outweighs the upper tail of the distribution, eventually some runs conclude at the worst possible outcome, in which the agent gets defeated by an enemy. Contrastingly, the policy generated for β = 8 clearly eliminates this possible outcome. In this case, the agent never gets the cost of 1 by inducing a risk-aware behavior that most of the time prefers not to collect R1 due to its proximity to enemies and, as such, the likelihood of defeat. Therefore, the median centers around 0.87, indicating the agent never retrieved any resources to its initial position. Finally, in Figure 7, we show in more detail the frequency of outcomes that each policy achieves. As hinted previously, when β ∈ {0.125, 1} we observe a small fraction of runs where the agent gets defeated. On the other hand, the risk-averse policy (β = 8) disallows this outcome entirely by, most of the time (82%), either avoiding gathering any resources or just retrieving R2 .

6

Conclusion

We motivate, propose and formalize risk-aware GUMDPs, which allow to take advantage of the flexibility of the GUMDPs framework with respect to objective specification, while trading off expected performance and risk-aversion. To solve risk-aware GUMDPs, we first explore a connection between risk-aware GUMDPs and solving a particular risk-aware MDP, named occupancy MDP, in which the agent keeps track of the empirical frequency of visitation of state-action pairs up to the current timestep. We propose a provably correct online planning approach based on an MCTS algorithm to solve the risk-aware occupancy MDP, effectively solving the original risk-aware GUMDP problem up to any desired accuracy. We provide a set of experimental results under a set of diverse tasks showing that our approach successfully trades off risk-neutral and risk-averse behavior. Future work could investigate whether a similar approach to ours can be used to solve GUMDPs with CVaR objectives (Rockafellar et al., 2000; Chow et al., 2015). Other interesting direction is to investigate whether our approach can be extended to deal with very large/inherently continuous state spaces, e.g., by borrowing ideas from successor features (Barreto et al., 2017; Borsa et al., 2018).

Risk-Aware General-Utility Markov Decision Processes

Acknowledgments This work was supported by Portuguese national funds through the Portuguese Fundação para a Ciência e a Tecnologia (FCT) under projects UID/50021/2025 and UID/PRR/50021/2025 (INESCID multi-annual funding), as well as AI-PackBot (project number 14935, LISBOA2030-FEDER00854700). Pedro P. Santos acknowledges the FCT PhD grant 2021.04684.BD and Fábio Vital acknowledges the FCT PhD grant 2022.14163.BD. Alberto Sardinha acknowledges the CNPq Research Productivity Fellowship (PQ), with reference 312699/2025-5. The authors thank the lab managers at GAIPS for the support provided when running the computational experiments of this work. The authors also thank Jacopo Silvestrin for discussions on earlier versions of this work and Zita Marinho for feedback on the manuscript.

References Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the Twenty-First International Conference on Machine Learning, ICML ’04, pp. 1, 2004. David Abel, Will Dabney, Anna Harutyunyan, Mark K. Ho, Michael L. Littman, Doina Precup, and Satinder Singh. On the expressivity of markov reward, 2022. Joshua Achiam, Harrison Edwards, Dario Amodei, and Pieter Abbeel. Variational option discovery algorithms, 2018. E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999. Philippe Artzner, Freddy Delbaen, Eber Jean-Marc, and David Heath. Coherent measures of risk. Mathematical Finance, 9:203 – 228, 07 1999. Andre Barreto, Will Dabney, Remi Munos, Jonathan J Hunt, Tom Schaul, Hado P van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. In Advances in Neural Information Processing Systems, volume 30, 2017. Leon Barrett and Srini Narayanan. Learning all optimal policies with multiple criteria. In Proceedings of the 25th International Conference on Machine Learning, ICML ’08, pp. 41–47, 2008. Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value-at-risk criteria. Mathematical Methods of Operations Research, 74(3):361–379, Dec 2011. ISSN 1432-5217. Marc G. Bellemare, Will Dabney, and Mark Rowland. Distributional Reinforcement Learning. MIT Press, 2023. Aharon Ben-Tal and Marc Teboulle. Expected utility, penalty functions, and duality in stochastic nonlinear programming. Management Science, 32(11):1445–1466, 1986. 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. Diana Borsa, André Barreto, John Quan, Daniel J. Mankowitz, Rémi Munos, Hado van Hasselt, David Silver, and Tom Schaul. Universal successor features approximators. CoRR, abs/1812.07626, 2018. 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. Y.S. Chow, H. Robbins, and D. Siegmund. Great Expectations: The Theory of Optimal Stopping. 1971. ISBN 9780395053140.

Reinforcement Learning Journal

2026

A. Dvoretzky, J. Kiefer, and J. Wolfowitz. The inventory problem: Ii. case of unknown distributions of demand. Econometrica, 20(3):450–466, 1952. Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained mdps. CoRR, abs/2003.02189, 2020. Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function, 2018. H. Föllmer and A. Schied. Stochastic Finance: An Introduction in Discrete Time. De Gruyter Textbook. 2016. ISBN 9783110463453. Javier García, Fern, and o Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(42):1437–1480, 2015. Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Olivier Bachem, Rémi Munos, and Olivier Pietquin. Concave utility reinforcement learning: the mean-field game viewpoint, 2022. 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, 2022. Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2681–2691, 2019. Ronald A. Howard and James E. Matheson. Risk-sensitive markov decision processes. Management Science, 18(7):356–369, March 1972. Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning: A survey of learning methods. ACM Comput. Surv., 50(2), apr 2017. Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. DOI: 10.1017/9781108571401. T. Lillicrap, J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. CoRR, abs/1509.02971, 2016. 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, pp. 47–76. PMLR, 25–27 Apr 2023. Alexandre Marthe, Samuel Bounan, Aurélien Garivier, and Claire Vernade. Efficient risk-sensitive planning via entropic risk measures, 2025. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. Nature, 518(7540): 529–533, 2015. Oliver Mortensen and Mohammad Sadegh Talebi. Entropic risk optimization in discounted mdps: Sample complexity bounds with a generative model, 2025. Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Convex reinforcement learning in finite trials. Journal of Machine Learning Research, 24(250):1–42, 2023. Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J. Andrew Bagnell, Pieter Abbeel, and Jan Peters. An algorithmic perspective on imitation learning. Foundations and Trends in Robotics, 7(1–2): 1–179, 2018. ISSN 1935-8261.

Risk-Aware General-Utility Markov Decision Processes

Bernardo Pagnoncelli, Oscar Dowson, and David Morton. Multistage stochastic programs with the entropic risk measure. February 2022. Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. Roxana Radulescu, Patrick Mannion, Diederik M. Roijers, and Ann Nowé. Multi-objective multiagent decision making: A utility-based analysis and survey. CoRR, abs/1909.02964, 2019. R Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 2:21–42, 2000. {Diederik M.} Roijers, Denis Steckelmacher, and Ann Nowé. Multi-objective reinforcement learning for the expected utility of the return. 2020. 2018 Adaptive Learning Agents, ALA 2018 Co-located Workshop at the Federated AI Meeting, FAIM 2018. Pedro P. Santos, Alberto Sardinha, and Francisco S. Melo. The number of trials matters in infinitehorizon general-utility markov decision processes, 2024. Pedro P. Santos, Alberto Sardinha, and Francisco S. Melo. Solving general-utility markov decision processes in the single-trial regime with online planning, 2025. Pedro P. Santos, Jacopo Silvestrin, Alberto Sardinha, and Francisco S. Melo. Entropic risk-aware monte carlo tree search, 2026. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nature, 550(7676):354–359, 2017. Shaler Stidham. Socially and individually optimal control of arrivals to a gi/m/1 queue. Management Science, 24(15):1598–1610, 1978. Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. Tom Zahavy, Brendan O’Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. CoRR, abs/2106.00661, 2021. Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. Cautious reinforcement learning via distributional risk in the dual domain, 2020.

Reinforcement Learning Journal

2026

Supplementary Materials The following content was not necessarily subject to peer review.

7

Extended related work discussion

Previous works studied GUMDPs with risk-neutral objectives (Zahavy et al., 2021; Geist et al., 2022). Zahavy et al. (2021) reformulate GUMDPs as a two-player game involving a policy and a cost (negative reward) player, using Fenchel duality. Geist et al. (2022) connect GUMDPs and meanfield games. Still in the risk-neutral setting, subsequent works identified a key implicit assumption underlying the GUMDPs framework: the performance of a given policy may depend on the number of trials/trajectories drawn to evaluate its performance (Mutti et al., 2023; Santos et al., 2024). In fact, the previous works show that the standard formulation of GUMDPs implicitly assumes the performance of a given policy is evaluated under an infinite number of trials/trajectories, an assumption that may be violated under many interesting application domains. To address this gap, Mutti et al. (2023); Santos et al. (2025) introduce finite trials formulations for GUMDPs, allowing to find optimal risk-neutral policies with respect to a finite number of trials/trajectories. None of the works above study risk-aware settings, being focused on learning risk-neutral policies. As pointed out in the main text, some of the results in our paper build on top of results put forth by the aforementioned studies. As an example, our work relies on the occupancy MDP formulation, as described in Sec. 4.2, which was introduced in (Santos et al., 2025). In the context of risk-aware MDPs, previous works studied the optimization of risk-aware objectives such as the conditional value-at-risk Chow et al. (2015) or the ERM (Lin Hau et al., 2023; Marthe et al., 2025; Mortensen & Talebi, 2025). In the context of our work, we are focused on more general objective functions of the occupancies induced by the different policies, not only being focused on the case of linear objectives (MDPs). Nevertheless, some of the techniques we employ resemble those adopted in the context of risk-aware MDPs. As an example, it is common in the context of riskaware MDPs to extend the state space to accommodate sufficient statistics since the optimal policy depends on the history only through a certain kind of “sufficient statistic” (Bäuerle & Ott, 2011). This resembles the construction of our occupancy MDP; however, the states in the occupancy MDP do not correspond to sufficient statistics of the history but instead correspond directly to histories (Lemma 4.3). This is required since, under more general settings, optimal policies may depend arbitrarily on the history. Other works, such as Lin Hau et al. (2023), exploit discounting and consider finite-horizon objectives to compute approximately optimal policies for infinite-horizon objectives - this technique is common in the field, and we followed a similar approach in 4.2. Finally, in the context of MDPs, Zhang et al. (2020) propose a new definition of the risk of a policy (called caution) as a function of the occupancy induced by the policy. Then, the authors formulate a caution-sensitive policy optimization problem by adding the caution risk as a penalty function to the dual objective of the linear programming formulation of MDPs. The formulation proposed by the authors can itself be seen as solving a risk-neutral GUMDP, where the objective function contains a term that captures the risk of a given policy. In our work, we are instead focused on solving risk-aware GUMDPs.

8

Lipschitz constants

Standard MDP (f (d) = c⊤ d)

It holds that X |f (d1 ) − f (d2 )| = |c⊤ (d1 − d2 )| ≤ |c(s, a)||d1 (s, a) − d2 (s, a)| ≤ max |c(s, a)|∥d1 − d2 ∥1 . s,a

s,a

Maximum state entropy exploration (f (d) = d⊤ log(d)) We assume P d is lower bounded by ϵ, i.e., d(s, a) ≥ ϵ with 0 < ϵ < e−2 for all s ∈ S, a ∈ A. We let f (d) = s,a g(d(s, a)), for g(x) =

Risk-Aware General-Utility Markov Decision Processes

Table 1: Lipschitz constants for common objective functions found in the GUMDPs literature. In (†) we assume d is lower bounded by ϵ satisfying 0 < ϵ < e−2 . Objective (f (d))

Task

d⊤ c,

MDPs/RL

⊤

Lipschitz constant (L)

c ∈ R|S||A|

maxs,a |c(s, a)| | log(ϵ) + 1| (†)

d log(d)

Max. state entropy expl.

∥d − dπb ∥22 ,

Imitation learning

dπb ∈ ∆(S × A)

n1 d⊤ c1 + . . . + nk d⊤ ck c1 , . . . , ck ∈ R|S||A| n1 , . . . , n k ∈ R

Multi-objective MDPs (weighted)

4

maxs,a |c̃(s, a)| c̃ = n1 c1 + . . . + nk ck

Multi-objective MDPs (max)

f (d) = maxi∈{1,...,k} d⊤ ci c1 , . . . , ck ∈ R|S||A|

maxi∈{1,...,k} Li Li = maxs,a |ci (s, a)|

Multi-objective MDPs (min)

f (d) = mini∈{1,...,k} d⊤ ci c1 , . . . , ck ∈ R|S||A|

maxi∈{1,...,k} Li Li = maxs,a |ci (s, a)|

x log(x). We note that, g ′ (x) = log(x) + 1 and it holds for any x ∈ [ϵ, 1] that |g ′ (x)| ≤ | log(ϵ) + 1|. Thus, for any x1 , x2 ∈ [ϵ, 1] we have that

|g(x1 ) − g(x2 )| = ≤

Z x1

Z max{x1 ,x2 }

′

g (x)dx =

g ′ (x)dx

min{x1 ,x2 }

x2

Z max{x1 ,x2 } min{x1 ,x2 }

′

|g (x)| dx ≤

Z max{x1 ,x2 } min{x1 ,x2 }

|log(ϵ) + 1| dx

= |log(ϵ) + 1| |x1 − x2 |. Thus, for any d1 , d2 ∈ ∆(S × A) lower bounded by 0 < ϵ < e−2 , it holds that X

|f (d1 ) − f (d1 )| =

s,a

(a) X

≤

≤

s,a

X s,a

(g(d1 (s, a)) − g(d2 (s, a))) |g(d1 (s, a)) − g(d2 (s, a))|

|log(ϵ) + 1| |d1 (s, a) − d2 (s, a)|

= |log(ϵ) + 1| ∥d1 − d2 ∥1 were (a) follows from the triangular inequality. Imitation learning (f (d) = ∥d − dπb ∥22 ) max

d∈∆(S×A)

∥∇f (d)∥1 = 2

max

d∈∆(S×A)

It holds that ∇f (d) = 2(d − dπb ). Now, ∥d − dπb ∥1 ≤ 2

max

d1 ,d2 ∈∆(S×A)

∥d1 − d2 ∥1 = 4.

Since the function f is continuous and differentiable over the simplex, which is compact, it holds that L = 4 is a valid Lipschitz constant as it corresponds to an upper bound on the maximum magnitude of the gradient of f over ∆(S × A).

Reinforcement Learning Journal

2026

Multi-objective MDP, weighted (f (d) = n1 d⊤ c1 + . . . + nk d⊤ ck ) We note that f can be equivalently rewritten as f (d) = d⊤ c̃, where c̃ = n1 c1 + . . . + nk ck . Therefore |f (d1 ) − f (d2 )| ≤ max |c̃(s, a)|∥d1 − d2 ∥1 . s,a

Multi-objective MDP, max (f (d) = maxi∈{1,...,k} d⊤ ci ) The result follows by noting that letting L = maxi∈{1,...,k} Li yields a valid Lipschiz constant, where Li = maxs,a |ci (s, a)|, since we are taking the maximum of Lipschitz functions with Lipschitz constants L1 , . . . , Lk . Multi-objective MDP, min (f (d) = mini∈{1,...,k} d⊤ ci ) |f (d1 )−f (d2 )| =

min

i∈{1,...,k}

c⊤ i d1 −

min

i∈{1,...,k}

c⊤ i d2 ≤

It holds that max

i∈{1,...,k}

⊤ |c⊤ i d1 −ci d2 | ≤ L∥d1 −d2 ∥1 ,

where L = maxi∈{1,...,k} Li and Li = maxs,a |ci (s, a)|.

9

Supplementary materials for Sec. 4

9.1

Proof of Proposition 4.2

π Lemma 9.1. For any ω ∈ Ω, π ∈ ΠNM and H ∈ N it holds that |f π (ω) − fH (ω)| ≤ 2Lf γ H .

Proof. For any ω ∈ Ω, π ∈ ΠNM and H ∈ N it holds that π |f π (ω) − fH (ω)| = f (dπ (ω)) − f (dπ,H (ω)) (a)

≤ Lf dπ (ω)) − dπ,H (ω)) 1 (b)

= Lf (1 − γ)

= Lf

∞ X t=0

γ t dπt (ω) −

H−1 (1 − γ) X t π γ dt (ω) 1 − γ H t=0

1

∞ X
(1 − γ) t H π π γ (1 − γ )d (ω) − d (ω) + (1 − γ) γ t dπt (ω) t t 1 − γ H t=0 H−1 X

t=H

(c)

≤ Lf = Lf

H−1 X

(1 − γ) γ t (1 − γ H )dπt (ω) − dπt (ω) 1 + (1 − γ) 1 − γ H t=0

∞ X t=H

1

! γ t ∥dπt (ω)∥1

H−1 X

(1 − γ) H γ γ t ∥dπt (ω)∥1 + Lf γ H 1 − γH t=0

= 2Lf γ H , P∞ where: (a) is due to the Lf -Lipschitz assumption; in (b) we used dπ (ω) = (1 − γ) t=0 γ t dπt (ω) where dπt,(s,a) (ω) = 1(st = s, at = a) denotes the empirical occupancy induced by the trajectory ω PH−1 at timestep t and dπ,H (ω) = (1−γ)/(1−γ H ) t=0 γ t dπt (ω). Step (c) follows from the triangular inequality. π Lemma 9.2. For any policy π ∈ ΠNM and H ∈ N it holds that |ρ(fH ) − ρ (f π )| ≤ 2Lf γ H . π Proof. From Lemma 9.1 we can infer that, for any ω ∈ Ω, f π (ω) − 2Lf γ H ≤ fH (ω) ≤ f π (ω) + H π H π 2Lf γ . Thus, from the monotonicity of ρ we have that ρ(f −2Lf γ ) ≤ ρ(fH ) ≤ ρ(f π +2Lf γ H ). π Equivalently, ρ(f π ) − 2Lf γ H ≤ ρ(fH ) ≤ ρ(f π ) + 2Lf γ H , and the result follows. ∗ π ∗ Lemma 9.3. If πH = arg minπ∈ΠNM ρ(fH ), then it holds that OptGap(πH ) ≤ 4Lf γ H .

Risk-Aware General-Utility Markov Decision Processes

π Proof. As shown in Lemma 9.2, |ρ(fH ) − ρ (f π )| ≤ 2Lf γ H , for arbitrary π ∈ ΠNM . From such π π inequality, we can infer that ρ (fH ) − 2Lf γ H ≤ ρ (f π ) , ∀π ∈ ΠNM , i.e., function ρ (fH ) − 2Lf γ H π ∗ π lower bounds function ρ (f ). Let πH = arg minπ∈ΠNM ρ (fH ). It holds that

 ∗ (a) (b)  ∗  π π ρ fHH − 2Lf γ H = min ρ (fH ) − 2Lf γ H ≤ min ρ (f π ) ≤ ρ f πH , π

π

(6)

π H π where (a) followsfrom  the fact that ρ (fH ) − 2Lf γ lower bounds ρ (f ); and (b) from the fact that

minπ ρ (f π ) ≤ ρ f π

′

, ∀π ′ (from the definition of a minimum). Finally, we note that

 ∗   ∗   ∗  ∗ π π ρ f πH − ρ fHH − 2Lf γ H = ρ f πH − ρ fHH + 2Lf γ H  ∗  ∗ π ≤ ρ f πH − ρ fHH + 2Lf γ H ≤ 4Lf γ H . The above and (6) imply that  ∗  ′ ∗ ρ f π ≤ 4Lf γ H . OptGap(πH ) = ρ f πH − min ′ π

Proof of Proposition 4.2 ∗ ∗ π is optimal with respect to the truncated objective. It ), i.e., πH Proof. Let πH = arg minπ∈ΠNM ρ(fH holds that,  ′ OptGap(π) = ρ (f π ) − ′min ρ f π π ∈ΠNM

 ′ = ρ (f π ) − ′min ρ f π π ∈ΠNM

(a)

 ′ ∗ ∗ ≤ ρ (f π ) − ρ(f πH ) + ρ(f πH ) − ′min ρ f π π ∈ΠNM

(b)

∗

≤ ρ (f π ) − ρ(f πH ) + 4Lf γ H

(c)

∗

π π ≤ |ρ (f π ) − ρ (fH )| + ρ (fH ) − ρ(f πH ) + 4Lf γ H (d)

∗

(e)

π∗

(f)

π∗

π ≤ 2Lf γ H + ρ (fH ) − ρ(f πH ) + 4Lf γ H π∗

∗

π ≤ 2Lf γ H + ρ (fH ) − ρ(fHH ) + ρ(fHH ) − ρ(f πH ) + 4Lf γ H π ≤ 2Lf γ H + ρ (fH ) − ρ(fHH ) + 2Lf γ H + 4Lf γ H n o π π′ = ρ(fH ) − ′min ρ(fH ) + 8Lf γ H , π ∈ΠNM

∗

where (a) follows from adding and subtracting ρ(f πH ) and applying the triangular inequality; (b) π follows from Lemma 9.3; (c) follows from adding and subtracting ρ (fH ) and applying the trianπ∗ gular inequality; (d) follows from Lemma 9.2; (e) follows from adding and subtracting ρ(fHH ) and applying the triangular inequality; and (f) follows from Lemma 9.2. 9.2

Proof of Lemma 4.4

π Proof. Random variable fH , as defined in (4), is associated with the probability space (Ω, F , Pπ ) πO and random variable JO , as introduced in Sec. 4.2, is associated with the probability space

Reinforcement Learning Journal

2026

πO π (ΩO , FO , PO πO ). Random variables fH and JO are equal in distribution if, for any y ∈ Y, πO π Pπ [fH ≤ y] = PO πO [JO ≤ y].

We start by noting that, for any trajectory ωO = ({s0 , o0 }, a0 , {s1 , o1 }, a1 , . . . , {sH , oH }) ∈ ΩO , a0 PO πO [ωO ] = p0,O ({s0 , o0 }) · πO (a0 |{s0 , o0 }) · PO ({s0 , o0 }, {s1 , o1 }) · . . . a

· πO (aH−1 |{sH−1 , oH−1 }) · PO H−1 ({sH−1 , oH−1 }, {sH , oH }).

(a)

= p0 (s0 ) · 1(o0 = [0, . . . , 0]) · πO (a0 |{s0 , o0 }) · P a0 (s0 , s1 ) · 1(o1 = σ(s0 , o0 , a0 )) · . . .

· πO (aH−1 |{sH−1 , oH−1 }) · P aH−1 (sH−1 , sH ) · 1(oH = σ(sH−1 , oH−1 , aH−1 ))

(b)

= p0 (s0 ) · 1(o0 = [0, . . . , 0]) · π(a0 |h0 ) · P a0 (s0 , s1 ) · 1(o1 = σ(s0 , o0 , a0 )) · . . . · π(aH−1 |hH−1 ) · P aH−1 (sH−1 , sH ) · 1(oH = σ(sH−1 , oH−1 , aH−1 ))

(c)

= Pπ [ω] · P aH−1 (sH−1 , sH ) · 1(o0 = [0, . . . , 0]) · 1(o1 = σ(s0 , o0 , a0 )) · . . . · 1(oH = σ(sH−1 , oH−1 , aH−1 )),

where in (a) we note that component o of the state is initialized as a zero vector and then deterministically evolves according to σ; any sequence of o-vectors that does not evolve according to σ has zero probability under probability measure PO πO . In (b) we used the fact that any stationary policy πO ∈ ΠS for MO can be mapped to a particular non-Markovian policy π ∈ ΠNM in Mf . In (c) we recall that, for ω = (s0 , a0 , s1 , a1 , . . . , sH−1 , aH−1 ), Pπ [ω] = p0 (s0 ) · π(a0 |h0 ) · P a0 (s0 , s1 ) · π(a1 |h1 ) · P a1 (s1 , s2 ) . . . P aH−2 (sH−2 , sH−1 ) · π(aH−1 |hH−1 ). Now, for any y ∈ Y and stationary policy πO ∈ ΠS , it holds that πO πO O PO πO [JO ≤ y] = PπO [{ωO : JO (ωO ) ≤ y}] X πO = PO πO [ωO ]1 (JO (ωO ) ≤ y) ωO ∈ΩO

X

=

ωO ∈ΩO

X

=

ωO ∈ΩO

(a)

=

    1−γ PO [ω ]1 f o ≤ y O H πO 1 − γH Pπ [ω] · P aH−1 (sH−1 , sH ) · 1(o0 = [0, . . . , 0]) · 1(o1 = σ(s0 , o0 , a0 )) · . . .

X ωO ∈ΩO

    1−γ o · 1(oH = σ(sH−1 , oH−1 , aH−1 ))1 f ≤ y H 1 − γH Pπ [ω] · P aH−1 (sH−1 , sH ) · 1(o0 = [0, . . . , 0]) · 1(o1 = σ(s0 , o0 , a0 )) · . . .

· 1(oH = σ(sH−1 , oH−1 , aH−1 ))1 f dπ,H (ω) ≤ y X X

(b) X = Pπ [ω] 1 f dπ,H (ω) ≤ y P aH−1 (sH−1 , sH )· ω∈Ω

o0 ,o1 ,...,oH ∈O sH ∈S

1(o0 = [0, . . . , 0]) · 1(o1 = σ(s0 , o0 , a0 )) · . . . · 1(oH = σ(sH−1 , oH−1 , aH−1 )) X

(c) = Pπ [ω] 1 f dπ,H (ω) ≤ y ω∈Ω

=

X ω∈Ω

=

X ω∈Ω

π Pπ [ω] 1 (fH (ω) ≤ y) π Pπ [{ω : fH (ω) ≤ y}]

π = Pπ [fH ≤ y] ,

Risk-Aware General-Utility Markov Decision Processes

   

1−γ where in (a) we noted that, for any ωO ∈ ΩO , 1 f 1−γ ≤ y = 1 f dπ,H (ω) ≤ y . In H oH (b), we split the sum over ωO ∈ ΩO as a sum over ω ∈ Ω, a sum over each possible vector o ∈ O across all timesteps, and a sum over the final state sH ∈ S (not included in ω). We also rearranged the sums by noting that some terms do not depend on some of the sums. In (c) we note that the inner sums over the o-vectors and sH equal one. 9.3

Proof of Theorem 4.5 D

π Proof. From Lemma 4.4, for any horizon H ∈ N and policy π ∈ ΠNM , it holds that fH = JπOO , where πO is the stationary policy for MO associated with the non-Markovian policy π for Mf . Thus, for π any risk-measure ρ : L → R, it holds that ρ(fH ) = ρ(JπOO ). Also, from Lemma 4.3 there exists a one-to-one mapping between non-Markovian policies for Mf and stationary policies for MO since every state in MO is uniquely associated with a particular history in Mf (and vice versa). Given these two results, we have that, for any π ∈ ΠNM ,  ′  ′ π π π ρ JOO , OptGapH (π) = ρ (fH ) − ′min ρ fH = ρ (JπOO ) − min ′ π ∈ΠNM

and the conclusion follows.

πO ∈ΠS

Reinforcement Learning Journal

10

2026

ERM-MCTS pseudocode

We display in Algorithm 1 the pseudocode for the ERM-MCTS algorithm. Algorithm 1 ERMβ -MCTS for finite-horizon MDPs with terminal costs. Inputs: s0 (root node), H (horizon), n (number of MCTS iterations), and {θt }t∈{1,...,H−1} (exploration constants). Initialization: X(st ,a) = [ ], ∀t ∈ {0, . . . , H − 1}, st ∈ S, a ∈ A (Initialize list to store sampled terminal costs starting from (st , a)). N (st ) = 0, N (st , a) = 0, ∀t ∈ {0, . . . , H − 1}, s ∈ S, a ∈ A (Initialize visitation counters). 1: for j ∈ n do 2: for t ∈ {0, . . . , H − 1} do 3: if N (st , a) = 0 for some a ∈ A then at = a. 4: else 5: Select an action according to: ) ( r√ N (st ) 6: at ∈ arg mina∈A ρ̂(st ,a),N (st ,a) − θt N (st ,a) ,    PN (s ,a) (s ,a) 7: where ρ̂(st ,a),N (st ,a) = β1 ln N (s1t ,a) i=1 t exp βxi t . 8: end if 9: Sample and transition to next state st+1 ∼ POat (·|st ). 10: end for 11: At depth H observe terminal cost cO (sH ). 12: for t ∈ {H − 1, . . . , 0} do 13: Update visitation counters: 14: N (st ) = N (st ) + 1. 15: N (st , at ) = N (st , at ) + 1. 16: Store sampled terminal cost: (s ,a ) 17: Store xNt(stt,at ) = cO (sH ) in X(st ,at ) . 18: end for 19: end for

11

Experimental Results

Our code is available at https://github.com/gh0stwin/risk-aware-gumdp. 11.1

Baselines

In the context of standard MDPs, the ERM-BI baseline exploits the dynamic programming decompositions of the ERM put forth by (Lin Hau et al., 2023). In particular, Lin Hau et al. (2023) show that the optimal value function V ∗ = {Vt∗ }t∈{0,...,H} and the optimal policy π ∗ = {πt∗ }t∈{0,...,H−1} satisfy, for all s ∈ S, 
∗ Vt∗ (s) = min ERMβγ t ct (s, a) + γVt+1 (s′ ) , ∀t ∈ {0, . . . , H − 1}, VH∗ (s) = cH (s), a∈A 
∗ ∗ πt (s) = arg min ERMβγ t ct (s, a) + γVt+1 (s′ ) , ∀t ∈ {0, . . . , H − 1}. a∈A

In the context of standard MDPs, we perform backward induction from timestep t = H backwards until timestep t = 0 to extract the optimal risk-aware policy. We also note that the occupancy MDP is undiscounted (i.e., γ = 1) and, hence, βγ t = β for all timesteps.

Risk-Aware General-Utility Markov Decision Processes

11.2

Hyperparameters

For implementation purposes, we let the ERM-MCTS parameters θt = θ for all t ∈ {0, . . . , H −1}, see Sec. 4.3. We display in Tables 2 and 3 the hyperparameters used in our experiments, where N denotes the number of independent runs of ERM-MCTS, n is the number of MCTS iterations per timestep for ERM-MCTS, and θ is the ERM-MCTS exploration constant. Under MDPs, we also run N independent runs of the oracle baseline ERM-BI. Environment

γ (Discount)

H (Horizon)

N (Num. runs)

n (MCTS iter.)

θ (Expl. const.)

MDP

0.9

20

100

500

1

MSEE

0.9

20

100

500

1

IL

0.9

20

100

2 000

1

MO

0.99

20

100

500

1

Table 2: Hyperparameters used for the illustrative environment experiments.

Environment

γ (Discount)

H (Horizon)

N (Num. runs)

n (MCTS iter.)

MSEE

0.99

200

128

1024

IL

0.99

99

128

1024

MO

0.99

40

128

1024

θ (Expl. const.) √ 2 √ 2 √ 2

Table 3: Hyperparameters used for the grid environment experiments.

11.3

Illustrative environments

We display in Fig. 2 an overview of the illustrative environments. In the remainder of this section, we detail the GUMDPs used for each task, regarding their state space, action space, dynamics, and cost function used. 11.3.1

Standard MDP (Fig. 2 (a))

We employ a four-state MDP where the agent needs to tradeoff at the initial state (s0 ) between: 1. a risky action (a0 ) that can lead to a low-cost state (s2 ), but with some probability the agent ends in a high-cost state (s3 ); and 2. a safe action (a1 ) that deterministically leads to a medium-cost state (s1 ). The agent resets to the initial state with 10% probability while not in the initial state. The cost function is given by c = [c(s0 ), c(s1 ), c(s2 ), c(s3 )] where c(s0 ) = 0, c(s1 ) = 41 , c(s2 ) = ⊤ 1 20 , c(s3 ) = 1. We let f (d) = d c. 11.3.2

Maximum State Entropy Exploration (Fig. 2 (b))

The task is similar to the motivating example from Sec. 1, where the agent aims to explore an environment as uniformly as possible but there is chance that the agent transitions to an absorbing state (s4 ). The agent starts at state s1 . We let f (d) = d⊤ log(d). 11.3.3

Imitation Learning (Fig. 2 (a))

The dynamics of this environment are the same as the standard MDP (Appendix 11.3.1). The agent aims to imitate the empirical occupancy induced by the trajectory of an agent that selected twice the risky action (a0 ) under the standard MDP and then selected the safe action (a1 ) for all the remainder timesteps. The trajectory to imitate had a rather lucky outcome, as it never ended up in

Reinforcement Learning Journal

2026

Table 4: Grid environment parameters used in the MSEE and IL task. Grid positions are defined using 0-based indexing and (0, 0) position it at the top-left corner. Parameter

Value

Grid size Agent starting position Difficult terrain positions

10 × 10 (9, 0) (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (8, 3), (9, 3), (1, 5), (1, 6), (1, 7), (1, 8), (2, 5), (2, 6), (2, 7), (2, 8), (7, 5), (3, 5), (3, 9), (9, 1), (5, 2) 0.1 0.01

ptrap puntrap

the absorbing state (s3 ). Hence, the agent needs to trade off between imitating the behavior policy in states (s0 , s1 , s2 ) and risking being absorbed into s3 , or only imitating the behavior policy in the less risky states (s0 , s1 ). To be precise, the empirical occupancy to imitate is dπb (s0 , a0 ) = 0.20605099, dπb (s0 , a1 ) = 0.30175732, dπb (s1 , a0 ) = 0.17054104, dπb (s1 , a1 ) = 0.15004508, dπb (s2 , a0 ) = 0.10245629, dπb (s2 , a1 ) = 0.0829896, dπb (s3 , a0 ) = 0.0, dπb (s3 , a1 ) = 0.0. We let f (d) = ∥d − dπb ∥22 . 11.3.4

Multi-Objective MDP (Fig. 2 (c))

The environment is inspired by the FishWood environment (Roijers et al., 2020), where the agent needs to trade off between two cost functions. Each cost function penalizes different behaviors. The cost function c1 is defined as c1 (s0 ) = 0, c1 (s1 ) = −1, c1 (s2 ) = 0.5, c1 (s3 ) = 0, c1 (s4 ) = 0. The cost function c2 is defined as c2 (s0 ) = 0, c2 (s1 ) = 0, c2 (s2 ) = 0, c2 (s3 ) = −0.2, c2 (s4 ) = 0.2. The agent starts at state s0 . Any action at states s1 , s2 , s3 , and s4 takes the agent deterministically back to the initial state. We consider three utility functions: (i) weighted, where f (d) = d⊤ c1 + d⊤ c2 ; (ii) max, where f (d) = max(d⊤ c1 , d⊤ c2 ); and (iii) min, where f (d) = min(d⊤ c1 , 2 · d⊤ c2 ). 11.4 11.4.1

Grid Environments Maximum State Entropy Exploration

Table 4 contains the hyperparameters used in the environment employed in the MSEE task. The environment dynamics are described in Sec. 5.2.1. 11.5

Imitation Learning

We reuse the environment and corresponding hyperparameters defined in the MSEE task (Appendix 11.4.1). Additionally, we compute the occupancy of the behavioral policy dπb after the agent performing the sequence of actions depicted in Figure 8. As already mentioned in Sec. 5.2.2, we ensure that the behavior policy never gets trapped inside difficult terrain squares. Under this approach we make sure that ERM-MCTS can model different behaviors (with distinct risk awareness) by considering which difficult terrain squares to visit, if any. 11.5.1

Multi-Objective

As stated in Sec. 5.2.3, we use the resource-gathering environment (Barrett & Narayanan, 2008) as our multi-objective task. Here, the agent has three objectives to maximize. The first two objectives address picking and delivering resources R1 and R2 to the home location, respectively. The last objective attends to the possibility of the agent getting defeated when stepping inside squares that contain enemies. Aiming to model the necessary information that is required for the reward functions, we define the environment state as a 5-tuple, s = ((x, y), hR1 , hR2 , hstart , henemy ). Where

Risk-Aware General-Utility Markov Decision Processes

Grid Figure 8: IL (grid environment): Sequence of actions taken by the behavior policy πb . Agent starts in position (9, 0), assuming 0-based indexing and (0, 0) position it at the top-left corner. (x, y) ∈ N2 holds the agent’s position, hR1 , hR2 ∈ {0, 1} assign if the agent is carrying the corresponding resource, hstart ∈ {0, 1} indicates whether the agent left the initial position, and henemy ∈ {0, 1} indicates if a clash with an enemy occurred. Regarding environment dynamics, the agent can move in all directions, plus we define a slippery condition where, with pslip probability, the agent moves instead perpendicularly to the selected direction. Additionally, resources are collected when the agent enters the resource’s square, setting hr = 1, where r ∈ {R1 , R2 }. Furthermore, when the agent steps inside a square that contains an enemy, with pdefeat probability, henemy becomes 1. In the case when henemy = 1, the agent loses immediately and transitions to an absorbing state until the end of the episode. Regarding reward modeling, we define three different reward functions r 1 , . . . , r 3 ∈ R|S||A| , where all entries are 0 except in specific states: (i) For r 1 , the states s ∈ {((xhome , yhome ), 1, 0, 1, 0), ((xhome , yhome ), 1, 1, 1, 0)} receive 1 to compensate for delivering R1 to the agent’s home position (xhome , yhome ). (ii) Analogously, r 2 accounts for the cases where R2 gets transported to (xhome , yhome ), thus assigning the states s ∈ {((xhome , yhome ), 0, 1, 1, 0), ((xhome , yhome ), 1, 1, 1, 0)} with reward 1.

(iii) To account for when the agent loses as the consequence of an enemy clash, r 3 sets the reward to −1 for any state s having henemy = 1. Subsequently, we combine all rewards by applying the following non-linear function, f (d) =
21 ⊤ 1 r⊤ + r⊤ 1d 2 d + r 3 d. With f (d) , we assign higher priority when retrieving R1 , e.g., simulating it being more valuable than R2 . The environment hyper-parameters are defined in Table 5. 11.6

Compute

The illustrative environments were simulated on a laptop CPU (Intel 11th Gen i5-1135G7) with 16 GB of RAM. Additionally, the experiments for the grid environments were deployed on a server with a dual CPU (AMD EPYC 9224 24-Core) and 770 GB of RAM. In the latter, due to the large number of CPUs, we effectively parallelize every experiment, allocating one CPU per independent run. Tables 6 and 7 display the runtime obtained when running ERM-MCTS on the illustrative and grid environments, respectively.

1 Transforming this objective to handle costs, 1

⊤ ⊤ ⊤ 2 sign(c⊤ 1 d)|c1 d| + c2 d + c3 d.

we first set ci = −r i , ∀i ∈ {1, . . . , 3} and then use f (d) =

Reinforcement Learning Journal

2026

Table 5: Grid environment parameters for the resource-gathering environment (MO task). Grid positions are defined using 0-based indexing and (0, 0) position it at the top-left corner. Parameter

Value

Grid size Agent starting position Home position (xhome , yhome ) R1 position R2 position Enemies positions pslip pdefeat

5×5 (4, 2) (4, 2) (0, 2) (1, 4) (0, 3), (1, 2) 0.05 0.025

Table 6: ERM-MCTS runtime on illustrative environments. Environment

Runtime

MDP MSEE IL MO (weighted) MO (max) MO (min)

(140.50 ± 6.22) s (165.75 ± 25.73) s (897.75 ± 66.13) s (136.50 ± 1.80) s (134.75 ± 7.76) s (142.25 ± 4.76) s

Table 7: ERM-MCTS runtime on grid environments. Environment

Runtime

MSEE IL MO

(2302.19 ± 30.89) s (593.00 ± 10.35) s (318.18 ± 17.31) s