Beyond Scalar Rewards: An Axiomatic Framework for Lexicographic MDPs
Authors: Mehran Shakerinava
Siamak Ravanbakhsh
Adam Oberman
Venue: NeurIPS 2025 spotlight ()
Keywords: expected utility theory
lexicographic expected utility
lexicographic MDP
axiomatic framework
reward hypothesis
reinforcement learning theory
Primary area: theory

Abstract: Recent work has formalized the reward hypothesis through the lens of expected utility theory, by interpreting reward as utility. Hausner's foundational work showed that dropping the continuity axiom leads to a generalization of expected utility theory where utilities are lexicographically ordered vectors of arbitrary dimension. In this paper, we extend this result by identifying a simple and practical condition under which preferences in a Markov Decision Process (MDP) cannot be represented by scalar rewards, necessitating a 2-dimensional reward function. We provide a full characterization of such reward functions, as well as the general d-dimensional case under a memorylessness assumption on preferences. Furthermore, we show that optimal policies in this setting retain many desirable properties of their scalar-reward counterparts, while in the Constrained MDP (CMDP) setting — another common multiobjective setting — they do not.

Beyond Scalar Rewards: An Axiomatic Framework for Lexicographic MDPs
Mehran Shakerinava + Siamak Ravanbakhsh 2, Adam Oberman 234
School of Computer Science, McGill University Mila Quebec Al Institute 3 Department of Mathematics and Statistics, McGill University "LawZero
Abstract
Recent work has formalized the reward hypothesis through the lens of expected utility theory, by interpreting reward utility. Hausner's foundational work showed that dropping the continuity axiom leads to generalization of expected utility theory where utilities are lexicographically ordered vectors of arbitrary dimension. In this paper, we extend this result by identifying a simple and practical condition under which preferences in Markov Decision Process (MDP) cannot be represented by scalar rewards, necessitating a 2-dimensional reward function. We provide full characterization of such reward functions, as well as the general d- dimensional case under memorylessness assumption on preferences. Furthermore, we show that optimal policies in this setting retain many desirable properties of their saalar-rwaar counterparts, while in the Constrained MDP (CMDP) setting another common multiobjective setting they do not.
Introduction
Framing decision-making as an optimization problem typically begins with specifying one or more utility functions and defining an objective with respect to these utilities. The reward hypothesis of Reinforcement Learning (RL) advocates for "maximization of the expected value of the cumulative sum of a received scalar signal" (Sutton, 2004; Sutton & Barto, 2018; Littman, 2017). Other approaches include specifying several utility functions with the objective of finding a solution whose expected utilities are Pareto optimal. In the Constrained Markov Decision Process (CMDP) framework (Altman, 1999), the goal is to maximize the expectation of a primary utility subject to constraints on the expected values of auxiliary utilities. Another approach is lexicographic optimization, where utilities are ordered by priority, and the objective is to lexicographically maximize the expected utility vector (Gábor et al., 1998).
is common to pick one such objective based on heuristics, and then study its properties and propose algorithms for it. The axiomatic approach goes in the opposite direction and characterizes family of utility functions and an objective that correspond to a set of assumptions (axioms) on our preferences. In other words, it shows the sufficiency of objective in capturing certain properties. For instance, it is well-known that a lcxicographic order cannot be scalarized, e.g., an order- preserving mapping from a lexicographically ordered square a line is not possible even though both sets have the same cardinality. In the axiomatic expected utility framework, one can show that a utility function that cannot be scalarized can always be captured by a lexicographic utility function (Hausner, 1954).
In this work, motivated by potential applications in Al safety, we show how this axiomatic approach lead to lexicographic objectives in MDPs. A lexicographic objective assumes that infinitesimal increase in the first-priority objective is preferred to any amount of increase in the second-prions objective. Such settings might appear when there is critical safety requirement that should be
"Corresoondence <mehhran.shakerinaee @ mail. megill.egl............. Work done in part while interning LawZero.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

2
R
R
4
= P(o")=0.) 001
R 10
Figure 1: An example of lexicographic planning with time-horizon T = 4 steps. The diagram depicts a 0.1 probability of unsafety when transitioning from a green, red, or blue state. also depicts the reward from gray states R. and the optimal policy as black arrows. Starting from the green state, the optimal policy is to forgo the high reward on the right side in favor increased safety and go left. Starting from the red state, since the safety of going left and right is the same, the optimal policy is to go right to get more cumulative reward. Importantly, decisions have to be based on two quantities: the probability of safety and expected cumulative reward.
prioritized above all else. Another common and practical example is when the first priority is to achieve some goal while the second priority is to minimize the time that it takes. Lexicographic objectives are also reminiscent of Asimov's Three Laws of Robotics (Asimov, 1942) where the highest priority objective is to "not injure a human being or, through inaction, allow a human being to come harm." An illustrative example of lexicographic objective presented in Fig.
1.1 Outline and Summary of Results
We begin by reviewing the relevant literature (Section 2), followed by brief summary of von Neumann-Morgensteen (vNM) expected utility theory and Hausner's lexicographic extension (Section 3). We then extend Hausner's 's result to the sequential decision-making setting (Section 4), which involves formally specifying a setting where outcomes are sequences of abstract events, and introducing axiom to structure preferences. Since Hausner's theorem does not specify the dimensionality of utility vectors, we study a simple setting that naturally leads to a 2-dimensional lexicographic utility function (Section 5), and extend this the sequential setting (Section 6). This yields a simple and interpretable recursive equation for the utility of event sequences. We then study the properties of optimal policies in lexicographic MDPs, highlighting similarities with scalar-reward MDPs and contrasting them with the CMDP framework (Section 7). We then further compare LMDPs and CMDPs (Section 8). We conclude with discussion of limitations and future work (Section 9) and concluding remarks (Section 10).
2 Related Work
Expected Utility Theory. Expected utility theory originated with Bernoulli (1738) and was for- malized axiomatically by von Neumann & Morgenstem (1947) in the context of game theory. This axiomatic approach characterizes when and why maximizing expected utility is justified. Subsequent work refined these foundations and extended them to more general settings, such as alternative formu- lations of the axioms (Jensen, 1967) and generalization from finite sets to mixture spaces (Herstein & Milnor, 1953). comprehensive account is provided by Fishburn (1982), which also contains relevant chapter lexicographic expected utility, due to Hausner (1954). In the lexicographic setting, reducing the dimensionality of utility vectors requires additional assumptions, which are often technical and unintuitive. Our work contributes natural and interpretable condition that leads to 2-dimensional lexicographic utilities.
Sequential Decision-Making and Expected Utility Theory. Classical expected utility theory typically applies only to final outcomes, abstracting away the sequential nature of decision-making and preventing utility assignment individual interactions, Recent works have extended vNM rationality axioms to sequential decision- -akiing,,,, motivated by variable discount factors (Pitis, 2019) and formalizing the reward hypothesis (Shakerinava & Ravan- bakhsh, 2022; Bowling et al., 2023). Following this axiomatic approach, we extend lexicographic expected utility theory to sequential settings, deriving structured reward functions under minimal and interpretable assumptions.
common in MDP and RL settings.

---

Lexicographic Decision-Making. Lexicographic optimization in Multi-Objective Reinforcement Learning (MORL) has been previously studied, notably by Gábor et al. (1998), and extended in Skalse et al. (2022), which present family of both action-value and policy gradient algorithms for lexicographic RL. with theoretical convergence results and empirical performance on benchmarks. In other works, Wray et al. (2015) provide a lexicographic value iteration algorithm and prove convergence under the assumption that each objective is allowed some acceptable level of slack. El Khalfi (2017) propose algorithms for finding lexicographic optimal policy in possibilistic MDPs. Hahn et al. (2021) investigate lexicographic w-regular objectives within formal verification, proposing reduction that enables model-free RL for prioritized temporal logic specifications.
Multi-Objective Decision-Making and Al Safety. The standard RL paradigm assumes that single scalar reward is sufficient for specifying goals (Silver et al., 2021). This view has been challenged by Vamplew et al. (2022), who argue that in safety-critical settings, scalar rewards can incentivize unsafe or undesirable behaviors. Lexicographic objectives have been proposed in domains such as autonomous vehicles, where safety must take strict precedence over other considerations (Zhang et al., 2022). Omohundro (2008) warns that unbounded reward maximization may give rise to dangerous instrumental drives. While scalarization methods are commonly used to combine multiple objectives, they suffer from well-known theoretical limitations (Vamplew al., 2008). Multi-objective RI. methods (Hayes et al., 2022) avoid scalarization but remain algorithmically and theoretically more challenging than the scalar case. Complementary to our axiomatic treatment, Miura (2023) analyzes the expressivity of scalar multi-dimensional rewards and gives necessary and sufficient conditions for when specified set of acceptable policies can be realized.
3 Background
3.1 Scalar Expected Utility Theory
The expected utility theory of von Neumann & Morgenstern (1947) provides axiomatic treatment of decision-making under uncertainty. Let O denote the set of outcomes. The result of a decision is always element from this set. We refer to distribution over outcomes lottery and denote the space of lotteries as (OO). The player is faced with a number of such lotteries and has to pick one. After lottery has been selected, the player receives an outcome sampled according the lottery's 's distribution.
The player supplies their preferences in the form of relation on the space of lotteries (2, ((O).. Based on this relation, we can define another relation > as p > q == not(q ž p). We also define the relation RJ p == (p Z q and q X p) and we say that and are indifferent. Its negation is denoted Gb.
We assume that the player's preferences satisfy von Neumann and Morgenstern's 's four axioms of rationality. These axioms are defined below, and we will refer to them as the vNM axioms.
Axiom 1 (Completeness). For all p, q E A(O),
p pŽ pr k
Axiom 2 (Transitivityy. For all p. g. E A(O),
x q and g ス = p p
Axiom 3 (Independence). For all p. g, r E A(O) and a E [0, 1).
ap + (1 - a)q ap (1 a)r g
The lottery op (1 agg that appears in the statement of Independence can be thought of as a compound lottery constructed by first tossing biased coin with probability of landing heads. The outcome of the coin toss determines whether we get an outcome sampled from lottery p (heads) or q (tails). Independence states that comparing compound lotteries constructed with the same biased
3

---

coin and with the same lottery for heads, is equivalent to comparing the corresponding lotteries for tails. From an algebraic standpoint, Independence can be thought of as cancellation law for the comparison of lotteries.
Axiom 4 (Continuity). For all p.q,r A(O),
p p = Ea E [0, 1]. ap + (1 - a)r x.
The Continuity axiom essentially states that, as the probabilities of a lottery vary, our valuation of the lottery changes smoothly. As will see, it is responsible for the sufficiency of scalar utilities.
Before presenting the expected utility theorem, we will need define utility and what it means for utility function to be linear.
Definition A utility function for ((O) is any function w : :(()) - R such that, for all P.q E A(O),
u(p) 2 u(g) - p 4.
(1)
Definition 2. A utility function is said to be linear if for all A
u(p) >>hhoooo p(o)u(o).
(2)
DE
We are now ready state the von Beumann-Morgenstern (vNM) expected utility theorem.
Theorem (von Neumann & Morgenstern (1947)) A relation (Z, A(O)) satisfies the vNM axioms if and only if there exists a linear utility function u A(O) TR. Moreover, u is unique up to positive affine transformations, ie., + au + b, where a > 0.
For proofs, see von Neumann & Morgenstern (1953), Fishburn (1982), or Maschler et al. (2013).
The vNM theorem identifies settings where decision-making can be optimized by maximizing the expected value of a scalar utility function. In other words, the vNM theorem is the formal basis of the well-known maximum expected utility principle.
We mention two advantages of expected utility theory over other' methods for specifying rewards. First, it separates reward specification from the mechanics of the environment, which is particularly useful when the environment is complex or unknown. Second, it enables reliable comparison of suboptimal policies. These advantages, among others, make it ideal candidate for reward specification.
3.2 Lexicographic Expected Utility Theory
An important result due to Hausner (1954) is that, if we forgo Continuity, lotteries can still be compared in terms of expected utility, but the utilities will be vectors and the comparison will be lexicographic. In lexicographic comparison, entries are compared from first to last and the first differing entry determines the order. The rest of the entries are irrelevant. The mathematical definition as follows.
Definition 3. For all E IRdd
lex = (3k [d], U1 U1 .... Mc-1 Uk-1, and Ug >> Uk).
To present the lexicographic expected utility theorem we first define what a lexicographic utility function is.
"We will occasionally abuse notation delta distribution centered (an element of A(O)). This simplification will typically occur when adding an outcome lottery evaluating its utility.
by writing o (an element of O) when we actually mean the Dirac
For example, assigning reward of to optimal actions and 0 to all other actions or ad-hoc reward shaping methods. More generally, there are many reward functions that can lead the same optimal policy. A simple case: there 3 actions a, b, We prefer notice that 6 and e are swapped. The optimal action the same in both cases. Suppose the initial policy selects action b and then we optimize it (w..t. rewards) to c. However, due to "bad" reward function. the policy actually gets worse. On the other hand, with vNM rewards, increasing expected reward is guaranteed to result in more preferred policy.
> but we reward function that satisfies r(a) r(c) r(b)- -

---

Definition 4. A lexicographic utility function for (2, A(O)) is any function w: A()) - I such that, for all p.q E A(O),
u(p) Zlex u(1)
p q.
A linear lexicographic utility function is defined in the same way as Definition 2 with addition and scalar multiplication interpreted as operations on a vector space.
We let _d be the of d lower triangular matrices with positive diagonal entries, as formally described by Eq. (5). This set will be used in the specification of affine transformations that retain lexicographic ordering.
cdxd {AE A,; 0 for <, Aa for all E [d]
(5)
We now state Hausner's lexicographic expected utility theorem.
Theorem 2 (Hausner (1954)) A relation (Z, A(O)) satisfies Completeness, Transitivity, and Independence if and only if there exist N and d-dimensional linear lexicographic utility Sunction A(O) + Rd. Moreover, is unique up to transformations of the form + Au + b, where A E pdxd and b E Rd.
For proof's see Hausner (1954) or Fishburn (1982).
Note that 1 captures the setting where Continuity satisfied and the vNM theorem applies, whereas d > 1 captures settings where Continuity is violated. Remarkably, the theorem not only recovers well-known fact that lexicographic orders cannot be scalarized, but also shows that, within the expected utility framework, any non-scalarizable utility function must admit a lexicographic representation.
Sequential Lexicographic Expected Utility
We now extend lexicographic expected utility to the sequential decision decision-making setting. In this setting, an agent sequentially collects utility instead of only receiving an outcome with some utility the end of the interaction. It is common to use the term reward instead of utility, so we will be using these terms interchangeably.
We model the agent's interaction with the environment as a Markov Decision Process (MDP) with the modification that the agent observes events from set & instead of rewards. More formally, assume that the MDP is equipped with a conditional probability distribution P x A + A(S E) of next state and event given current state and action. This setting is very general since events allowed to be any stochastic function of current state, action, and next state. The set of outcomes in this setting corresponds to sequences of events, i.e., O = E" {E} U Usen Ex, where is the empty sequence. Rewards emerge as a result of applying expected utility theory to a given preference relation distributions over sequences of events (z., A(E*)).
Without any additional assumptions, the preference relation unstructured, overlapping sequences treated entirely independent entities, and the utility of any two sequences is independently determined. We will, therefore, introduce a simple and reasonable axiom and show that leads to utility functions that take simple mathematical form.
But first, we need to introduce concatenation operator that will be used in the axiom. We will use it both for concatenating sequences and for concatenating sequence to distribution over sequences. The operator is best described with examples.
Example 1. Let (01, (01,0,,00 az), (b1, bz), and (c) be sequences of events. Then, example of concatenating to sequence is (c) (b,, b2) = (c, b,, b2). And an example concatenating to a distribution over sequences is
(aa(u,, 0z aa) 2/2(b1,b2) b2)) 1/a(c, ai, u2, 0a) + 2/3(c, bi, bz).
(6)
5

---

The axiom that we are about to introduce says that preferences are not affected by past events, As result, the agent can forget past events and only focus on optimizing future events. The axiom is version of the memorylessness axiom from Shakerinava & Ravanbakhsh (2022).
Axiom 5 (Memorylessness), For all e E, either
E e e.pZe.g = pŽg
or
vp.q E A(E"), e.pe
(8)
Events that satisfy Eq. (8) act as terminal events since future events no longer have any effect on the final outcome. We denote by Eterm the set of such events.
Theorem 3 (Sequential Lexicographic Expected Utility Theorem) A relation (Z,, A(E*)) satisfies Completeness, Transitivity, Independence, and Memorylessness if and only if there exist d E N. d-dimensional linear lexicographic utility function w. with u(e) rewards - Rd. and reward multipliers
L U {0} such that
u(e 7) r(e) I(e)u(T):
for all E and E E"
proof is provided in Appendix D.I. A point omitted from the theorem's statement, but evident in the proof, is that an event is terminal if and only if (e) O.
Theorem 3 implies MDP where rewards drepentionddependennt matrices in Ldxd and expected returns compared lexicographically: We refer to such MDPs as Lexicographic MDPs (LMDPs). Notably, the structure is more general than that of previous works (e.g.. Skalse et al. (2022)) where it typically assumed to be diagonal.
d-dimensional vectors, the "discount" factors I are
The commonly used transition- innrriedeeddee discounted rewards emerge as result of non- parameterized version of the temporal y-indifference from Bowling et al. (2023).
Axiom 6 (Temporal - Indiffeeree)) For all E, E E*, T2 EE
1
(e: TI)+ +
T (T2) (T) ~ 7-1
(e T2) + ?
7+1 (T))
7+1
7+1
where y E [0.
Theorem 4 (Discounted Lexicographic Expected Utility Theorem) A relation (2,, A(E*)) satisfies Completeness, Transitivity, Independence, and Temporal q- r-Indifference if and only if there exist d E N. a d-dimensional linear lexicographic utility function with u(E) O, and rewards r E:E + Rdd. such that
u(E ((E.7) 7) = r(() +7u())
(10)
for all E and E
proof is provided Appendix D.2. The proofs of Theorems and 4 are similar to their scalar counterparts in Shakerinava & Ravanbakhsh (2022); Bowling al. (2023) where have lifted the continuity axiom and arrived at a reward structure where rewards are vectors and (scalar) comparisons have been replaced with lexicographic comparisons.
A Single Unsafe Utility
The lexicographic expected utility theorem drawback in that it does not specify the dimen- sionality of the utility function. It also does not specify any particular subspace of IRd for the utility of outcomes. We would like have more fine-grained understanding of the structure of the utility function for specific settings of interest.

---

Therefore, in this section, we propose an intuitive axiom that results in a simple 2- 2-dimensional linear lexicographic utility function. We do so by introducing an outcome of that is 'infinitely bad,' as formalized by the next axiom. We interpret this outcome as critically unsafe outcome. Let and Safe == Ot.
O = {o o z of]
Axiom 7 (Safety First). For all p,q q e ((Osaee) and all E > 0,
sot + (1 e)P < q-
The existence such an outcome violates Continuity, To see that, p, E ((Osafe) be two safe lotteries such that p q. We now have p q > of. Then, a ajot q for all < 1 and 1. For do the sides become indifferent, Continuity is
op (1 aoot > for violated. Therefore, from now on, we assume that Continuity only holds for (>, smont)) The full set of assumptions are provided below.
Assumption The relation (2, A(O)) satisfies Completeness, Transitivity, and Independence and the relation (z, (OOste)) satisfies Continuity, The relation (Z))(O)) and of satisfy Safety First. Also, there exist 01, 02 Osafe such that 0ı 전 (non-triviality..
In this setting, lotteries can be uniquely written in the form
[a, pl = (1 a:) ap,
(11)
where [0, 1] is the probability of safety and p e ((Osate). An exception occurs when which can be addressed by fixing lottery A(Osate) and writing the (deterministic) lottery of as [0. g). making its representation unique.
Example 2. The lottery p = 1/3 of + 1/2 x + 1/6 means there is 1/3 chance of obtaining outcome o², 1/2 chance of obtaining outcome æ, and 1/6 chance of obtaining outcome y. is uniquely decomposed into the form of Eq. (11) as
2
3
1
o²
+ 3
F
+
70)
=
3 x 7")
The next lemma shows that it is possible to compare any two lotteries first by comparing the probability of safety and, if equal, performing a comparison A(Osate).
Lemma 1. For all p.g E A(O) and all a, B E [0,1].
[a, K [3, 4] > (a > 3) or (a 3 and p 2 q).
(12)
A proof is provided in Appendix D.3.
With the appropriate definitions and Lemma 1 at hand, we are now ready to prove the following theorem.
Theorem 5 (Lexicographic Expected Utility Theorem with Single Unsafe Utility) A relation (Z,, (OO) satisfies Assumption if and only if there exist a linear utility function u' A(O
IR for (k, A(Qaate) and a 2-dimensional linear lexicographic utility function AO0) - R2 such that for all o E O,
u(o) (00 (-1,0)
o O Orafer
(13)
o oz
Moreover, u is unique up to transformations of the form u + Au + b. where A E c2p² and
b E I
A proof is provided in Appendix D.4.
Example 3. A linear lexicographic utility function with a single unsafe utility is depicted in Fig. 2.
In the utility function of Eq. (13), the first dimension of the utility of lottery represents the probability of safety minus and the second dimension represents the expected utility given safety. Also note that it is 2-dimensional, as opposed to Theorem 2 which does not specify d.
7

---

U2
04
12
A
A
A(O safe
0
02
11
01
An example plotting the 2-dimensional lexicographic utility of O fo.,....0. Og. of Assuming u linear, its range will be the highlighted triangle. Note that Continuity is the main axiom responsible for utilities being mapped onto straight line. Since of does not satisfy Continuity, it gets mapped outside the line containing the set of points u( s(Osafe).
Figure 2:
Sequential Lexicographic Expected Utility with a Single Unsafe Utility
We now extend the single unsafe utility setting to the sequential setting according to the frame- work introduced in Section 4. We define Et as the events that are indifferent ot. Adding the Memorylessness axiom to our previous assumptions leads to the following theorem.
Theorem 6 (Sequential Lexicographic Expected Utility Theorem with a Single Unsafe Utility) A relation (z, ((E*)) satisfies Assumption and Memorylessness if and only if there exist rewards r & + I, reward multipliers y E + IR+, and 2-dimensional linear lexicographic utility function u: (E > IR² satisfying uuE) and
(0,r(e))
e Exerm E
ule r)
(-1,0)
CEEt otherwise
(14)
(un(F), (1+ (()))))) (())u((T)
for all events E & and sequences of events E E".
A proof is provided in Appendix D.5.
follows from Theorem that the events El terminal and result in unsafe outcome o!.
is worth noting that Eq. (14) can be somewhat simplified by assuming that terminal events lead to virtual terminal states. Observe that letting u(r) (0, 0) the third case of Eq. (14) produces the first case and letting u(r) (-1, 0) produces the second case. Therefore, we can mainly use the third case and obtain the other cases by assigning a utility of (0, 0) to safe terminal states and utility of (-1,00 0) unsafe terminal states. We also learn from Theorem 6 that each event has corresponding reward multiplier ((e) > 0. By assuming Temporal I-Indfffeeence on (Z. A ((Oste)) one can arrive at fixed cunsition-independeee discount factor (0, 1] for the second dimension.
Example Fig. depicts an example of described setting. For simplicity, we are assuming that the agent can deterministically move neighboring state and that events a stochastic function of the starting state of any transition.
Eq. (14) can also be written in the general form of Eq. (9) with d 2. Let us refer r and I from Eq. (9) and I' Specifying them follows recovers Eq. (14).
(0, r(e))
CEE-
F(e) =
(15)
(-1,0)
otherwise
c Eteria
F(e) =
r(e) ((e))
(16)
0
otherwise

---

7 Properties of Optimal Policies in Lexicographic MDPs
In this section, we examine the properties of optimal policies in the lexicographic setting, referred to as LMDPs. We highlight their similarities to the scalar MDP setting and contrast them with the CMDP framework.
The first important point of contrast is that in CMDPs, an optimal stationary policy may depend on the starting state distribution (Altman, 1999), whereas in MDPs, there exists stationary poliey that is optimal for all starting states (Puterman, 1994). We refer to this stronger notion of optimality as uniform optimality.
Next, we show that the fundamental theorem of MDPs (see Appendix A) still holds in the absence of the continuity axiom. To do so we will need to make the assumption that the diagonal entries of I'(e) are less than for all e E E. This is analogous to the assumption that the discount factor is less than 1 for MDPs
Assumption 2. For all E & and i E [4] (ia(e) <I
Theorem 7 (Fundamental Theorem of LMDPs) For every finite LMDP satisfying Assump- tion 2, policy S + A is uniformly optimal if and only if it is greedy w.r.t. Q", that is, [e>x(e) (Q* a)] lex max. (s, a) for all 8 E S.
A proof is provided in Appendix D.6. We write lex max instead of max only emphasize that the argument is a set of vectors that are compared lexicographically. Also, Q' for LMDPs is defined similar MDPs where the maximization interpreted lexicographic maximization.
Corollary 1. For every finite LMDP satisfying Assumption 2, there exists stationary deterministic uniformly optimal policy.
Proof. Any policy æ such that क (s) E arg lex max, Qs(s, a) is stationary deterministic uniformly optimal policy.
The result above mirrors the MDP setting but stands in stark contrast to CMDPs. In a CMDP, an optimal policy might need to randomize its actions, and, as mentioned before, a uniformly optimal stationary policy might not exist (Altaan, 1999; Szepesvári, 2020). The fundamental reason for these differences is that CMDPs violate both Independence and Continuity (Bowling et al., 2023, $7). whereas LMDPs violate only Continuity. In fact, has been shown that slightly weaker notion of Independence is sufficient for guaranteeing the existence of a uniformly optimal stationary policy in trees (Colaço Carr et al., 2024). We conclude that the fundamental properties of optimal policies in MDPs do not rely on the Continuity axiom.
8 Further Comparison of LMDP and CMDP
We saw some differences between LMDPs and CMDPs in the previous section. We now provide a more detailed comparison of the two frameworks.
Can any CMDP be turned into an LMDP? No. Consider the following example with three outcomes 01, 02, Oa. two utility functions u1, U2, and the constrained objective max Elui] subject to E[u2] 2 0. The utilities are specified as u(o)) ) = (4, -2), u(02) = (2, u(03) = (0, 4). Now consider the lotteries A = 1/2 01 + 1/2 03 and B = 1/2 02 + 1/2 03. Assuming linear utilities we have u(A) = (2, 1) and B(B)= = 31. Both of these lotteries satisfy the constraint. Since A has higher expected in utility it is preferred over B. Now apply independence and remove 03 from both lotteries and call the resulting (pure) lotteries A' = 0j and B' = 02. According to independence. A' should be preferred to B'. But that is not the case because the outcome on does not satisfy the constraint while 02 does, so B' is preferred to A', violating independence. Since LMDPs satisfy independence, CMDPss cannot in general be turned into LMDPs. We note that similar example is provided by Bowling et al. (2023).
Can any LMDP be turned into CMDP? Only under certain conditions. If we fix the starting state distribution and, given K priority levels, we know the optimal value of all but the lowest priority level, i.e., know Vi. .... Vi V then it is possible to turn the LMDP problem into

---

CMDP by constraining these K 1 values with the known optimal values and optimizing the lowest- priority value, i.e., max V (so]] subject to (s))] 2 V for all i E 1,.... K 1. Essentially, the first K - 1 optimization problems are turned into constraints, similar to turning max, fx) into max, subject to f(x) 2 f For example, if we were to turn an LDMP with a single unsafe outcome into a CMDP, then the CMDP would constrain the probability of the unsafe outcome, assuming access to optimal achievable probability of safety (i.e., VJ), rather than optimizing it.
Another important distinction between CMDPs and LMDPs is that CMDPs put constraints on expected outcome while LMDPs only allow constraints on specific outcomes. This means that one observes single run of a policy, in the case of an LMDP, one can evaluate this run individually and assign utility vector to it, but in the case of a CMDP, is not possible to tell if constraints are satisfied or not, and so it is not possible to evaluate single run. The root cause of this difference can be traced back to CMDP's s violation of the independence axiom.
Example 5. Consider the toy-example of a robot that needs to exit a maze. To incentivize the robot to exit as fast possible, commonly, either assign reward of -1 to each step a discount factor and assign a positive reward for escaping. Now consider maze with hazards that can possibly destroy the robot. Suppose we would like, 1st, to maximize the probability of safely exiting the maze, and 2nd, to do so as fast as possible. Now suppose we have to design a reward function for this task without having seen the maze, e.g., we do not know how likely the hazards are to destroy the robot or how large the maze is. We might try to assign a large negative reward the robot being destroyed. However, that does not adequately capture our prioritized objective. For given scalar reward function, we can always design a maze such that the robot takes a more hazardous path by making safe paths longer or hazard probabilities smaller. An LMDP can capture this objective with a 2- 2-dimensional reward function where the reward for hazardous event is (). If we were to use CMDPs for this problem, we would need to know what the optimal hazard probability is in order to set constraint on it. Additionally, changing the starting state to a point in the maze that has a different optimal hazard probability necessitates respecifying the CMDP.
Limitations and Future Work
Lexicographic objectives are only appropriate in settings where objectives cannot be traded off. Such cases may be less common in practice. Also, have proposed new algorithmic methods for solving lexicographic MDPs or RL problems. Although prior works have developed algorithms in this space (Wray al., 2015; Skalse et al., 2022), lexicographic optimization remains challenging. Furthermore, our analysis focuses on expected utility theory paradigm. In practice, when the environment is known and fixed, it may be possible to design simpler, scalar rewards that suffice for a specific task. Lexicographic objectives have potential applications in AI safety, particularly in problems of Al control. For example, primary objective might be to maintain a safety guardrail (Bengio et al., 2025), to ensure that an AI system remains confined sandbox environment, or that its influence is restricted in a controlled manner. Exploring such applications is a promising avenue for future research.
reward specification, following the
10 Conclusion
We presented a lexicographic generalization of expected utility theory for sequential decision- making, motivated by settings where objectives must be prioritized in a strict, non-compensatory order. Building on Hausner's extension of expected utility theory, we identified a simple and practical condition under which preferences cannot be captured by scalar rewards, necessitating lexicographically ordered utility vectors. We provided full characterization of such utility functions in Markov Decision Processes (MDPs) under a memorylessness assumption on preferences, including both the 2-dimensional case and the general d-dimensional case. Importantly, we showed that optimal policies in this setting retain key properties of scalar-reward MDPs, such as the existence of stationary, uniformly optimal policies, in contrast to the Constrained MDP (CMDP) framework. Our results generalize the scalar reward hypothesis while preserving the auility-mxiiizzation paradigm, offering principled foundation for lexicographic objectives in sequential decision-make -making.
10

---

Acknowledgments
We thank Mehrab Hamidi, Motahareh Sohrabi. Sékou-Oumar Kaba, Vedant Shah, Damiano For- nasiere, Gauthier Gidel, Yoshua Bengio, and the LawZero team for feedback on earlier drafts of this paper. This work was in part supported by Canada CIFAR Al Chairs and NSERC Discovery programs.
References
Altman, E. Constrained Markov decision processes. Chapman & Hall/CRC, 1999. Cited at and 9.
Asimov, I. Runaround. 1942. Cited at 2.
Bengio, Y., Cohen, M., Fornasiere, D., Ghosn, J., Greiner, P., MacDermott, M., Mindermann, S., Oberman, A., Richardson, J., Richardson, O., Rondeau, M.-A., St-Charles, P.-L., and Williams- King, D. Superintelligent agents pose catastrophic risks: Can scientist ai offer safer path? arXiv preprint arXiv: 2502.15657, 2025. Cited 10.
Berouuli,, D. Specimen theoriae novae de mensura sortis. Commentarii Academiae Scientiarum Imperialis Petropolitanae, (5):175-192 1738. Translated by L. Sommer 'Exposition of new theory on the measurement of risk', Econometrica (22):23-36, 1954. Cited at
Bowling, M., Martin, J. D., Abel, D., and Dabney, W. Settling the reward hypothesis. International Conference Machine Learning, pp. 3003-3020. PMLR, 2023. Cited at 2, 6, and 9.
Colaço Carr, J., Panangaden, P., and Precup, D. Conditions preference relations that guarantee the existence of optimal policies. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238, pp. 3916-3924 PMLR, 2024. Cited at 9.
EI Khalfi, Z. Lexicographic refinements in possibilistic sequential decision-making models. Ph1) thesis, Université Paul Sahatier- Toulouse III, 2017. Cited at 3.
Fishburn, P. The foundations of expected utility. Theory and Decision Library. Kluwer Academic, 1982. Cited at 2, 4, and 5.
Gábor, Z., Kalmár, Z., and Szepesvári, C. Multi-criteria reinforcement learning. ICML, volume 98, pp. 197-205, 1998. Cited at and 3.
Hahn, E. M., Perez, M., Schewe, S., Somenzi, F., Trivedi, A., and Wojtezak, D. Model-free reinforcement learning for lexicographic omega-regular objectives. In International symposium on formal methods, pp. 142-159, Springer, 2021. Cited at 3.
Hausner, M. Multidimensional utilities. Decision processes, pp. 167-180, 1954. Cited at 1, 2, 4, and 5.
Hayes, C. F., Rädulescu, R., Bargiacchi, E.,, Källström, J., Macfarlane, M., Reymond, M., Verstraeten, T., Zintgraf, L. M., Dazeley, R., Heintz, F., et al. A practical guide to multi-objectiv reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems, 36(1):1-52, 2022. Cited at 3.
Herstein, I. N. and Milnor, An axiomatic approach to measurable utility. Econometrica, 21(2): 291-297, 1953. Cited at 2.
Jensen, N. E. An introduction beroullian utility theory: utility functions. The Swedish Journal of Economics, 633-188, 1967. Cited at 2.
Littman, M. The reward hypothesis. https: https://iinnulll.co4442225ffff 2017. Cited at 1.
Maschler, M., Solan, E., and Zamir, S. Game Theory. Cambridge University Press, 2013. Cited at 4,
Miura, S. On the expressivity of multidimensional markov reward. arXiv preprint vrXiv:230.112184 2023. Cited at 3.
Omohundro, M. The basic drives. In Artificial General Intelligence, pp. 483-492. Springer, 2008. Cited at 3.

---

Pitis, S. Rethinking the discount factor in reinforcement learning: A decision theoretic approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7949-7956, 2019. Cited at 2.
Puterman, M. L. Markov decision processes: Discrete stochastic dynamic programming, 1994. Cited at 9.
Shakerinava, M. and Ravanbakhsh, S. Utility theory for sequential decision making. Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 19616-19625. PMLR, 2022. Cited at 2 and 6.
Silver, D., Singh, S., Precup, D., and Sutton, R. S. Reward is enough. Artificial Intelligence, pp. 103535, 2021. Cited at 3.
Skalse, J., Hammond, I.., Griffin, C., and Abate, Lexicographic multi-objectivv reinforcement learning. In Raedt, L. D. (ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pp. 3430-3436 ijeai.org, 2022. Cited at 3, 6, and 10.
Sutton, R. S. The reward hypothesis.
http///ccnnneeeidddeeeeeeeeeeeee http://eaaaccuuuaaaaraaa... ca/
RLAT/rewarddyyoohessss html, 2004. Cited 1.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018. Cited at and 20.
Szepesvári, C. Constrained mdps and the reward hypothesis. https://readingeml blogspot. com/2020/03 httt///onsttannnnnnnn.en peierraiidddddss---e and aandrewardde hypothesis
rewarddbyyoothesis httm,, 2020. Cited at 9.
Szepesvári, C. Planning in MDPs: Lecture 2 The Fundamental Theorem, 2023. URL https:
Lecture notes for CMPUT 605: Theoretical Foundations of Reinforcement Learning, University of Alberta. Cited at 20.
//rltheory. wor.gggit.b...... io/lecture not estes// motes/plannnnne -iw-aniinn---dmss/aaae
Vamplew, P., Yearwood, J., Dazeley, R., and Berry, A. On the limitations of scalarisation for multi- objective reinforcement learning of pareto fronts. Proceedings the Australasian Joint Conference on Artificial Intelligence, pp. 372-378, 2008. Cited at 3.
Vamplew, P., Smith, B. J., Källström, J., Ramos, G., Rádulescu, R., Roijers, D. M., Hayes, C. F., Heintz, F., Mannion, P., Libin, P. J., Dazeley, R., and Foale, C. Scalar reward is not enough: response to silver, singh, precup and sutton (2021). Autonomous Agents and Multi-Agent Systems, 3.
36(2), 2022. Cited
von Neumann, and Morgenstern, O. Theory of Games and Economic Behavior. Princeton University Press, 2nd edition, 1947. Cited at 2, 3, and 4.
von Neumann, J. and Morgenstern, O. Theory of Games and Economic Behavior. Princeton University Press, 3rd edition, 1953. pp. 26-29 and Appendix, pp. 617-632. Cited at 4.
Wray, K., Zilberstein, S., and Mouaddib, A.-I. Multi-objective mdps with conditional lexicographic reward preferences. In Proceedings the AAAI Conference on Artificial Intelligence, volume 29, 2015. Cited at 3 and 10.
Zhang, H., Lin, Y., Han, S., and Lv, K. Lexicographic actor-critic deep reinforcement learning for urban autonomous driving. IEEE Transactions on Vehicular Technology, 72(4):4308 4319, 2022. Cited at 3.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: A summary of the paper's contributions is provided in the introduction (Sec- tion 1.1) with references to specific sections of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper includes Limitations and Future Work section (Section 9).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: All theoretical results are accompanied by clearly stated assumptions. Proofs are provided in Appendix D.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
Soaieeee/CodeSubiiseeee aasssonnolcyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nip..co wttpccccpppccceeeeccccccccccccct wwwcc//gge//////ee /CooeSubmbii /ttecc/ggiideeoeeuuumummiiii seriisssinnoooooo oniioniyllcy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt///eerriisc..o cttp://cccc....hcccsiiiieeeeeeee
Answer: [Yes]
Justification: The paper adheres to the NeurlPS Code of Ethics. It involves only theoretical analysis and does not raise ethical concerns regarding data, privacy, fairness, misuse.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper presents foundational thcoretical contributions without immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release data, models, or assets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs were used solely to assist with writing and editing tasks, such as improving phrasing and clarity. No LLMs were used in the core research methodology, theory development, results.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy thttps:// /ttp:///eeuippeeeeeee httpeeeeww....aeeeeeeeeeeeeeeeee /c/e//ooeeeeencce//2///.... for what should or should not be described.
19

---

A Background: Reinforcement Learning
Reinforcement Learning (RL) studies the setting where an agent interacts with an environment while receiving reward signal response (Sutton & Barto, 2018). The environment typically modeled as Markov Decision Process (MDP). An MDP can be described by set of states S, set of actions A. transition and reward probabilities P( Tt+1 St, at), and discount factor 7 E [0, 1). The objective is to produce a policy S - A that maximizes expected cumulative discounted reward, that EE y/r.). The cumulative discounted reward will sometimes be referred to as return.
The expected return of starting from state and following policy л is known as the value function and is defined
V =
Ex
r'
(17)
1=0
The expected return of starting from state s, taking action a, and thereafter following policy x is known as the Q-value function and is defined as
(²
Ex
7 re
80 = 8, a0 = a
(18)
1=0
The optimal Q-value function is defined as
max
(19)
x
A policy is optimal if it satisfies state distribution. A policy æ uniformly optimal if it satisfies Q" Q*, that is, performs optimally for all starting states. An important theorem in the theory of MDPs, sometimes known as the fundamental theorem MDPs, characterizes all uniformly optimal policies of MDP.
E[Q" that is, it is optimal for a given initial
Theorem (Fundamental Theorem of MDPs) For every finite MDP, policy 8 A is uniformly optimal if and only if it is greedy w.r.. Q", that is, E (a)r(s) a)] max, (s, for all S.
See Szepesvári (2023) for proof.
B Comparison of Constraints, Penalties, and Lexicographic Optimization
Risk
P
Cost
Figure 3: (Lefft) A set of policies (light cyan region), plotted by their R, C' values. The solutions of the constrained (C), penalty (P), and lexicographic (L) methods are indicated. The lowest-risk (safest) policy is given by (L). (Right) The agent aims to reach the target. The cost C is the path length, and the risk is the portion of the path that lies within the unsafe (red) region.
In this section, we compare lexicographic optimization the constrained approach and the penalty approach. We introduce notation restricted to this section: R denotes risk (the negation of the probability of safety), and C' denotes cost (the negation the expected utility). The optimization problems corresponding the constrained (C), penalty (P), and lexicographic (L) approaches are as
20

---

follows:
min C(z), min ((a) + AR(x)
subject R(x) _
(C)
(P)
lex min (R(z),
(L)
x
The left part of Fig. 3 illustrates the optima of the different objectives over a two-dimensional set. The lexicographic minimizer yields the lowest-risk solution.
The right part of Fig. 3 illustrates a path optimization problem where and C' are defined as functions of the path The lexicographic minimizer is given by (L) and corresoonds to the green path. The penalty method (P) leads to the dotted red path, which is shorter but has a nonzero R(x).. Either path correspond to the constrained approach (C), depending on the value of 6. Using hard constraints with nonzero safety threshold or the penalty method results in path that spends a nonzero amount of time the unsafe region to reach the goal faster, resulting in the dotted red path. Using either hard constraints with a safety threshold of zero or lexicographic optimization results in the green path, which is optimal.
C Algorithmic Considerations for LMDPs
In MDPs, the optimal Q-value function a) satisfies the Bellman optimality equation:
("(s = R(s, a's + Q' aeA
8,
(20)
where R(s, a, s') E[r 8, a,a, s'] is the expected reward from the transition (s, s'). The same is true for LMDPs, where Q"(ss,) is vector, is matrix, and the maximization in Eq. (20) is lexicographic.
The (uniformly) optimal policy nt can then be derived from the optimal Q-value function as:
argmax Q' (8, a).
(21)
aEA
When 7 < 1, one can obtain Q" by iterating the Bellman optimality equation until convergence. This algorithm is known Q-value iteration.
Algorithm 7 --pppmmiimtee Q-Learning for LMDP
1: Input: LMDP with d-dimensional reward, slack R
2: Initialize: Q(s, a) + 0 for all E S, E A; step size a +- 0.1; e + 0.1
3: Sample initial state Po
4: repeat
5: (s) A
6: for = 1 to d
(+ (a A Qi(s,a)
max Qi(s,a' Ti} e'EA; (()
8:
end for
9:
Sample action a ~ Uniform(A)) + c) (nisorm(A)(s))
10:
Execute observe next state s' and reward vector R E Rd for 1 to d do (s + ()
12:
+ +y max d'EA;_,(3')
Qi(s',a)
13:
end for
14:
8 sts'
15:
until r-convergence of Q
16:
Return: x(s) < any a E (s)
Let be the number of state-action pairs. In an MDP, one can then think of the Q-value function as point in n-dimensional space. The Q-value iteration algorithm converges because one show
21

---

that the Bellman optimality equation is a contraction mapping in this space. The Banach fixed point theorem then implies convergence fixed-point.
However, the same argument fails for LMDPs because the Bellman optimality equation is not necessarily contraction mapping. To obtain convergence must accept some slack and take values that are closer than 7 as being equal. This leads to Algorithm 1.
D Proofs
D.1 Proof of Theorem 3
Theorem 3 (Sequential Lexicographic Expected Utility Theorem) A relution (Z, A(E*)) satisfies
Completeness, Transitivity, Independence, and Memorylessness if and only if there exist d E N, d-dimensional linear lexicographic ulility function u with u(e) = 0, rewards reward multipliers 1' [dxd U {0} such that
IRd, and
u(e.T) r(e)) + +(e)u((F)
(9)
for all E and E
Proof. (=) By the lexicographic expected utility theorem (Theorem 2) there exist d E N and a d-dimensional linear lexicographic utility function u. Among the possible utilityy functions we pick one such that u(e) = O. Now, by Memorylessness, preferences are either retained when an event e is prepended to lotteries, all lotteries become indifferent. We handle the cases below.
1. If retains preferences, then the relation (x, A(E*)) that their corresponding utility functions must be related by the uniqueness condition of Theorem That is, for all E E*, u(e 7) Au(T) b, where E < and Rdd. Let's name the corresponding A and b of as ((e) and r(e) respectively.
) is isomorphic to (2, e A(E*)), implying
2. If makes future lotteries indifferent, must have for all 7 E E³, u(e 7) b, where b Rd. Again, we name the corresponding of e as r(e) and, to match the format the previous case, we let l'(e) be the zero matrix 0.
In summary, for all and E", utilities are of the form
u(e T) = r(e) + ((e)u(T))
(22)
where r E Rd and P: cdxd U (0).
(+) By the lexicographic expected utility theorem (Theorem 2) the relation (z, A(E*)) corresponding to u satisfies Completeness, Transitivity, and Independence. It remains to show that X satisfies Memorylessness.
Let è E E. We consider two cases:
If ('e) 0. then by Eq. (9), u(e- T) r(e) for all T E E*, so u(e p) is constant across all lotteries E A(E"), implying e e q for all lotteries p,
2. (fT()) E caxd then for all lotteries p.q A(E*).
e. x e
- ule p) Zlex u(e-g)
(u is a lexicographic utility function) (Eq. (9)
- r(e) + I(e)u(p) Z1ex r(e) + r(e)u(g)
- u(p) Zlex u(q)
(u + T(e)u + r(e) preserves 21ex)
p x q.
(u a lexicographic utility function)
In both cases, the preference relation satisfies Memorylessness.
22

---

D.2 Proof of Theorem 4
Theorem 4 (Discounted Lexicographic Expected Utility Theorem) A relation (k, A(E)) satisfies Completeness, Transitivity, Independence, and Temporal q- "-Indifference if and only if there exist d E N. a d-dimensional linear lexicographic utility function with u(E) O, and rewards r r:E-A - Rd such that
u(e 7) = r((e) +)u()))
(10)
for all E and E
Proof. (+) By the lexicographic expected utility theorem (Theorem 2) there exist d E N and d-dimensional linear lexicographic utility function u. Among the possible utility functions we pick one such that u(æ) O. Now, letting T1 T and T2 = E in Temporal 7 Indifferencce we get that for all e E & and T E E
7+1 (e.T) r)
1
(e) + ?
7+1 (7)
(T)
7 ++1 7+1
7+1 (e. (e.T)
(8)
x+1 (e) (c)+ 2 (
1
is utility function)
7+1
7+1 u(e u(e + - u(E)
u(e) + 7+1 -t)
(u is linear)
7+1
7+1
- uee 7) u(e) + ?u(()
(u(e) = 0).
If we let r()) = u(e). then we have our result.
(=) By the lexicographic expected utility theorem (Theorem 2) the relation (Z, A(E))) corresponding to u satisfies Completeness, Transitivity, and Independence. It remains to show that X satisfies Temporal I-Idifffernnce.
For all E E, E E E" we have
uue) + 7+1 (u(ri) + u((z)) = u(e) + Y (u(TI) + u(z2)
7+1
7+1 7+1
(u(e) + (u(T))) 7+1 u(71) = 7+1 (u(e) + )u(T))) + - um))
7+1
7+1
7+1 ule (1) + 2 u(T1) 1+ج
1
u(e T2) ?
7+1 -
u(T
(Eq. (10))
)1) 7 (m))
1+4 (c (2) + ? T+و (m)
1
T+4
(u is linear)
114
Tit (e. 7)) + 1 (T)) ~
- (e π2) + - (71)
(u is a utility)
7+1
D.3
Proof of Lemma
Lemma 1. For all p.q E A(O) and all o., 3 E 10,
[a, k [3, 4] < (a> > 3) or (a = 3 and p X g).
(12)
Proof. We separate the space of possibilities into three cases:
1. If a > 8, then ja, p] has greater probability of avoiding of. By Safety First, this implies
[a, p) > [8, q]. hence (a. pl 2 [3, ql + True.
2. If a 8, then by Independence, [a, p] X [a,g] + p x ạ.
23

---

3. If < 8. then [a.p] has less probability of avoiding of. By Safety First, this implies
[a.p] < [8, q]. hence [a. pl 2 [3. ql
False.
Putting all together, we get:
[a.p] ž [3, el = (a> 3 and True) or (a B and Z 9) or (ax < B and False).
This proves the desired equivalence.
D.4 Proof of Theorem 5
Theorem 5 (Lexicographic Expected Utility Theorem with Single Unsafe Utility) A relation (z: ((O)) satisfies Assumption if and only if there exist a linear utility function u' (aQaafe) - IR for (2: ((Oaate) and a 2-dimensional linear lexicographic utility function A(O) RR?
such that for all o E EO,
(0, (o))
O OE Osale:
u(o) (-1.0)
(13)
o o
Moreover, u is unique up to transformations of the form u + Au + b, where E 2 and
b E 2
Proof. Given that u' is linear, we uniquely extend Eq. (13) into linear utility function on the entire domain. For all p E A(Osate) and a E [0. 1], u((a, pl) -a- 1,
(23)
(+) The relation (>, ((O satisfies the vNM axioms so the vNM theorem implies the existence of linear utility function u'. Showing that the function u of Eq. (23) is linear lexicographic utility function is a simple application of Lemma 1.
(+) It is straightforward to check that preferences induced by the given satisfy axioms in the way described in the theorem.
Uniqueness: Let o+ > o- be best and worst outcome in A(O respectively. Specifying the utility o o and of uniquely specifies the entire utility function. There are 5 degrees of freedom because must have ui (o+)= wi (o ). These degrees of freedom correspond the 5 degrees of freedom in A and b. Positivity of the diagonal of A stems from the requirements that uy(o*) ) (y(o and (o*) > (ot).. It is hard to verify that Au is also a linear lexicographic utility function for ((O)..
D.5 Proof of Theorem
Theorem 6 (Sequential Lexicographie Expected Utility Theorem with a Single Unsafe Utility) relation (z, A(E")) satisfies Assumption and Memorylessness if and only if there exist rewards
r r: - R reward multipliers 7 - R2,, and 2-dimensional linear lexicographic utility function u ((E*) -> IR2 satisfying uus) O and
(0, r(e))
E Exerm gt
u(e T)
(-1,0)
e Et otherwise
(14)
(u (1 un (T))r(e) +(())2(())
for all events E E and sequences of events T e E
Proof. By Theorem 5 there exists 2-dimensional linear utility function u E" - IR² where the utility of any event that indifferent of is (-1,0) and the utility of every other event (0) x RR. We let = 0)} U ({0) x R) be this set of possible utilities.
By Theorem 3, there exist rewards F : E + R and reward multipliers i: E + C2x2 U {0} such
that u(E) O and, for all E E, Et, utilities are of the form
ule 7) F(e) + +(e)u(())
(24)
24

---

Additionally, for all E ul E, we must have
F(e) [(e)x E u.
(25)
Eq. (25) puts a constraint on Fand f' Letting (0, we conclude that i(e) E U. (f + 0 (e
non-terminal), then letting x = (-1,0) we get -i(e) - f (e) E Since [e) > 0 we
conclude that Fi (e) [e) = (i) = 0, and I (e) = 1. Consequently, we must have that (e(e) (e) = 0, or equivalenty, (e) iz (e) for non-terminal events.
Finally, letting (e) == (c) and r(e) = Fi(E) we get the desired result.
D.6 Proof of Theorem 7
Theorem 7 (Fundamental Theorem of LMDPs) For every finite LMDP satisfying Assump- tion 2, policy S A is uniformly optimal if and only if it is greedy w.r.t. Q', that is, E (a) (s a)] = lex max, Q" (8, a) for all 8 E S.
Proof. The proof relies on the fundamental theorem of MDPs (Theorem 8). Let Qi be the first dimension of the Q-value function under policy and let (i, = max, Q7 (T a) for all s, This maximum exists since Qi bounded (due to 1, (e) < 1) and the space of policies MDP is compact. The fundamental theorem of MDPs says that a policy x²' is uniformly optimal and only if greedy w.r.t. Qi, that is, n'' (8) E A(argmax,
finite
These policies are essentially restricted to choosing action from a restricted set of actions at each state given by argmax, (s, a). We can therefore imagine a smaller MDP with this restricted action set at each state. All policies of this MDP optimal w.r.t the first dimension of utility.
By Theorem 3, the second dimension of utility satisfies uz(e - 7) r2(e) + (2)(()u1(7))
(22)() Since all policies in this MDP are optimal w.r.t. the first dimension of utility, (T) s, is fixed and equal V (s') s, al for all policies of the second MDP. This fixed value can be placed into the reward function without affecting Q As result, the second MDP can be viewed as scalar MDP with the following reward: re( + 2,, (V)
s.
Since the space of policies of this smaller MDP is a compact subset of the original space of policies and I'2, (e) 1, we can again invoke the fundamental theorem of MDPs for Q5. We continue like this for all d dimensions of utility. The Q-value of the final space of optimal policies is (Qi, 2i) which lexicographically dominates all Q' and is thus uniformly optimal.
25


Reviews:
[{"review_id": "sc1YcLKO3O", "reviewer": "Reviewer_7CHw", "summary": "This paper studies reinforcement learning (i.e. sequential decision-making) under lexicographic preferences functions. The authors introduce the Lexicographic MDP (LMDP), and their contributions are to extend classical expected utility theory of von Neumann & Morgenstern and of Hausner to the sequential setting. Under one additional axiom that they argue is natural for the sequential setting (Memorylessness), they establish an analogue of Hausner's lexicographic expected utility theorem -- this gives rise to vector-valued utility functions taking a recursive form similar to the classical value functions. The authors then extend this to the setting of sequential decision-making with safety constraints, establishing a \"safe\" version of the lexicographic relations with an additional axiom (Safety First). It is shown that LMDPs with the Safety First axiom (and one additional technical axiom related to discount factors) have a unique globally optimal policy, similar to MDPs and in contradistinction with the Constraint MDPs.", "questions": "1. Differentiation from Prior Work: Can you provide a detailed technical comparison explaining how your contributions differ from these prior results beyond the tweaking of the axioms? What specific novel insights does your work provide that these earlier papers did not establish?\n2. Scope of Safety Applications: Can you elaborate on the types of AI safety problems where your framework would be most appropriate and when one would choose this formalism over the Constrained MDP (or vice-versa)?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This is a theoretically interesting paper on the foundational aspects of decision-making with utilities. The motivation for studying this setting is the case when different vector-value outcomes can not be compared in a scalar fashion, i.e. there exists a strict ordering between the indices of the vector-valued outcome (maximizing the first index of the outcome takes highest precedence over any other index). The main application area that I can see is for providing a different formalism for safe decision-making. Accordingly, the authors study this case in the paper, with the axiom that there exists a single \"infinitely bad\" outcome that must be avoided at all costs. \n\nThe axioms the authors introduce are natural. The writing and presentation itself is very clear in the main text. One suggestion would be to review the abstract: it is vague does not really convey or accurately discuss the technical contributions of the paper.\n\nAs for what's missing:\n- It would have been of high value to provide more discussion and perhaps some examples on how this \"safe lexicographic decision-making\" formalism differs from the Constrained MDP. Namely, is there a toy problem or perhaps a real-life example where one should use this formalism as opposed to the Constraint MDP? The authors do establish that they differ on at least one technical level (behaviours of their optimal policies), but this does not do enough to separate the two settings. \n- Beyond this, as the authors acknowledge, it would have been interested to have some algorithmic developments (how to plan/solve the value/utility functions whose structure they have spent time working out).\n- Lastly, there seems to be some missing discussion on how this work differs from related work *on a technical level*. The authors mention the works of (Shakerinava & Ravanbakhsh, 2022) and (Bowling et al., 2023) but not precisely how their results are similar or different. From a quick glance, the contents seem to be highly related. For example, Theorem 4.2 of (Shakerinava & Ravanbakhsh, 2022) studies the exact same axioms as Theorem 3 here except with the addition of the Continuity axiom, and derives an analogous conclusion. Similarly, Theorem 4.1 of (Bowling et al., 2023) is related to Theorem 4 here but without the sequential structure, and derives an analogous conclusion. This should be clearly discussed and at a glance reduces the novelty of the contributions in this paper. \n\nI am leaving a weak accept for this paper, but would be happy to revise my score after the discussion if it turns out that I have been mistaken (or if the authors revise some of the discussion, if needed).\n\nSmaller complaints:\n- Please define lexmax_a in Theorem 7.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback and thoughtful questions. We will address the minor issues (abstract, define lex max). We respond to questions below.\n\nQ: Is there a [problem] where one should use this formalism as opposed to [CMDP]?\n\nA: We argue for an axiomatic approach to using objectives. If one accepts the independence axiom of von Neumann & Morgenstern as a natural axiom of rationality (which we the authors do), then one should use LMDPs (or MDPs if continuity is also accepted). For more comparison see also the response to first Q of reviewers ii8W and AHWB.\n\nQ: Comparison to (Shakerinava & Ravanbakhsh, 2022) and (Bowling et al. 2023)?\n\nA: This work is a natural next step for those papers. Is there a more general setup than vNM’s four axioms and what does that more general utility structure look like for MDPs? If one accepts the very natural Completeness, Transitivity, and Independence axioms then Hausner tells us that lexicographic rewards are the most general setting there is. We extend this result to MDPs and see that, similar to the scalar reward setting, lexicographic rewards take a simple recursive form.\n\nQ: Theorem 4.2 of (Shakerinava & Ravanbakhsh, 2022) vs. Theorem 3?\n\nA: The final recursive reward decomposition equation for both theorems look similar. The distinction is that in Theorem 3 rewards are vectors instead of scalars, and the factor Γ is a lower triangular matrix with positive diagonal instead of a positive scalar. A similar explanation goes for Theorem 4.1 of (Bowling et al., 2023) vs. Theorem 4. However, our Theorems 5, 6, 7 don’t have similar counterparts in these previous works.\n\nQ: What specific novel insights does your work provide that these earlier papers did not establish?\n\nA: Apart from Hausner’s work in 1954, before Bellman’s introduction of MDPs in 1957, recent prior works have largely ignored the lexicographic setting. It is only mentioned in passing in (Bowling et al. 2023). We provide a long overdue connection of Hausner’s work to MDPs and show that LMDPs (with a specific structure on the Γ matrix) provide the most general reward setting. Colloquially, the “correct” way to go beyond scalar-reward MDPs is to go to the LMDP setting (not, e.g., CMDPs).\n\nQ: AI Safety problem where this is useful?\n\nA: In AI safety, LMDPs can be appropriate when we introduce a highest-priority objective such as “do no harm.” In this setting, the agent must first minimize the probability of harm before optimizing any secondary performance criteria. This cannot be faithfully captured by scalar rewards. Also, the optimal harm threshold likely depends on the context so CMDPs cannot be used either. LMDPs offer a principled way to express such strict prioritization."}, {"review_id": "mVKzlWJVgO", "reviewer": "Reviewer_gQjL", "summary": "This paper contributes to the theory of lexicographic Markov decision processes, where the objective is to maximize a d-dimensional vector lexicographically. The paper starts by giving a background on:\n- von-Neumann-Morgenstern (vNM) expected utility theorem: only linear utility functions satisfy the four vNM axioms\n- if we let go of the “continuity” axiom, Hausner 1954 characterization theorem shows that we’ll have a $d$-dimensional linear *lexicographic* utility function for some d\nThe RL/MDP theory has largely focused on vNM utilities, and this paper lays a more generalized theory for lexicographic MDPs.\n\nBuilding on Hausner 1954, the paper proposes a memorylessness axiom (extension of Shakerinava and Ravanbakhsh, 2022), and uses this axiom along with three of the vNM axioms to prove a characterization of linear lexicographic utility functions for MDPs or sequential decision making. Similar to the discounted reward case with the vNM utilities, the paper defines a discounted reward version and proves a characterization using another axiom it introduces.\n\nNext, as an example, the paper investigates a setting where there are unsafe outcomes with infinite cost, which breaks the continuity assumption. The paper proves that this cannot be captured by vNM utilities and requires a 2-dimensional linear lexicographic utility function. The paper extends this example to the sequential setting as well.\n\nFinally, the paper proves that for lexicographic MDPs, greedy following the adapted version of Q-value function is optimal and a stationary deterministic optimal policy exists.", "questions": "None at the moment.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper is written and presented very nicely. I appreciate the clarity. Though, none of the proofs appear in the main body. Though, the paper mentions that a reader knowledgeable of the proofs follow a structure similar to that of the scalar-reward models.\n- The axiomatic analysis and the characterizations of lexicographic utility functions for MDPs is new --- though lexicographic objectives in MDPs have been investigated before.\n- I haven’t checked the proofs, but the logical path of the theorems building on top of each other seems very reasonable and sound.\n- The example with the unsafe outcome nicely illustrates that one needs lexicographic optimization. \n\nWeaknesses:\nI don’t see any critical problems, and I appreciate how clean everything is presented in the paper --- though, I haven’t checked any of the proofs yet.\n\nI’m not currently giving a higher score mainly due to that, as I understand, the paper also fairly admits that many of the proofs and ideas are taken from prior work but nicely put together in this work for the sequential decision making setting.\nThe paper itself also mentions the algorithmic/computational challenges of solving lexicographic MDPs given the existing literature.\nIt would’ve been ideal to see some new (algorithmic/computational) insight taken away from the paper that can be used to devise new algorithms or perhaps solve or better formalize new problems. Though, I think there is value in the characterizations and the defined axioms.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation of our work. Please see the other responses for some arguments in favor of the significance of our work."}, {"review_id": "SSSRxUxBcS", "reviewer": "Reviewer_AHWB", "summary": "The authors provide an extension of Markov Decision Processes (MDPs) that supports lexicographic objectives. They take an axiomatic approach by describing criteria over preferences between histories (completeness, transitivity, independence, memorylessness, and temporal $\\gamma$-indifference) and providing a representation result in the form of a linear lexicographic utility function (theorem 3 and 4). They additionally propose a \"safety first\" axiom that leads to a 2-dimensional lexicographic utility (theorem 5) which they extend to the sequential setting (theorem 6). Finally, they prove a \"fundamental theorem of LMDPs\" (theorem 7) that shows a relationship between optimal policies and the (lexicographically) optimal value function, analogous to that of MDPs, but, notably, unlike constrained MDPs.", "questions": "1. Do standard MDP algorithms work with LMDPs? What changes have to be made?\n2. Have the authors tested methods for solving LMDPs? Are there any challenges not found in the standard MDP setting?\n3. Can we state more formally what classes of problems are solved by LMDPs but not CMDPs?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- This is a high quality paper: the technical results are clearly formulated and appear correct to me.\n- The paper is clearly written: the authors do a good job of building up the results and connecting their framework/results to existing framework/results\n\nWeaknesses\n- Although the significance of the paper is gestured towards by comparing LDMPs with CMDPs and some comparision was done in the Appendix, I felt that the authors did not convincingly demonstrate how LMDPs can be used in place of scalar MDPs or CMDPs. Axiomatic definition of new classes of MDPs is a valuable exercise, however, there are practical reasons why the community uses MDPs as a standard model of sequential decision-making (e.g., we have lots of algorithms for solving MDPs). Unfortunately, the authors do not do very much to convince readers of the practical significance of not using LMDPs. In particular, I would have liked to see an LMDP of some reasonable difficultly actually be solved (e.g., a tabular and/or deep RL setting), either using a version of an MDP algorithm or a new algorithm. Even better would be to see how the CMDP formulation of the same problem leads to issues that LMDPs avoid. Currently, the authors only present a very simple lexicographic planning problem in Figure 1 and one in the appendix.\n-  Relatedly, the \"single unsafe utility\" formulation is interesting and seems promising, but this is a single specific case of the more general formulation that seems like a good parameterization but isn't empirically demonstrated. \n- The results presented are somewhat original. As far as I'm aware, there is no axiomatic derivation of lexicographic MDPs in the literature. However, the theoretical results seem to follow naturally from combining well-established results (e.g., expected utility, lexicographic expected utility, Bowling et al (2023)'s results on settling the reward hypothesis). In the end, the results feel like a straightforward exploration of a new way to specify sequential decision-making problems, but don't make the case for using this approach over any other in practice.", "was_revised": true, "final_justification": "The authors clarified why certain things were not included in the paper. I am still concerned that the absence of an algorithm for solving LMDPs will limit their usefulness to the field.", "rebuttal": "Q: Significance of LMDPs and comparison to MDP and CMDP?\n\nA: Let us provide an example. Consider the classic problem of a robot in a maze trying to escape. To incentivize the robot to escape as fast as possible we either assign a reward of -1 for each step or we use a discount factor < 1 and assign a positive reward for escaping. Now consider a maze with *hazards* that can possibly destroy the robot. We are first and foremost interested in maximizing the probability of a safe escape out of the maze. Our second priority is to do so as fast as possible. Now suppose we have to design a reward function for this task without having seen the maze, e.g., we don’t know how likely the hazards are to destroy the robot or how large the maze is. The previous approaches break down in this setup. For a scalar reward function we can always design a maze such that the robot takes a more hazardous path by making safe paths longer and making hazard probabilities smaller. To quote Rich Sutton: “Approximate the solution, not the problem.” Using discount factors or negative rewards would be an approximation of the problem in this case. The true problem is lexicographic in nature. The reward for a hazardous event is (-1, 0), the reward for a safe step is (0, -1), and the reward for escaping the maze is (0, 0). Moreover, to be able to use CMDPs for this problem, we need to know what the optimal hazard probability is in order to set a constraint on it. Additionally, changing the starting state to a point in the maze that has a different optimal hazard probability necessitates respecifying the CMDP. Working on a better approximation of the solution to LMDPs is an interesting direction that we leave for future work.\n\nQ1: Do standard MDP algorithms work with LMDPs? What changes have to be made?\n\nQ2: Have the authors tested methods for solving LMDPs? Are there any challenges not found in the standard MDP setting?\n\nA: Value iteration is not guaranteed to converge since the Bellman operator is not a contraction mapping in the lexicographic setting. Intuitively, we first need to find the set of optimal actions w.r.t. Q_1, then construct an MDP restricted to these actions, and then optimize w.r.t. Q_2. Since value iteration for Q_1 isn’t guaranteed to converge in any finite number of steps we might never get to the second stage. What is sometimes done is to have a tolerance threshold τ such that Q-values that differ less than τ are considered equal. τ can go to 0 during training. However, this is a somewhat ad-hoc approach and can be difficult to tune. A method of encouraging Q-values for different actions to be equal via some kind of regularization could be an interesting direction for future work. Similar issues appear in policy-based algorithms as well. This new open problem that we also briefly discuss in future works is also the reason we cannot have an empirical evaluation. \n\nQ3: Can we state more formally what classes of problems are solved by LMDPs but not CMDPs?\n\nA: Please see answer to first Q of reviewer ii8W."}, {"review_id": "Izoh3MsnDW", "reviewer": "Reviewer_ii8W", "summary": "This paper takes an axiomatic approach to define Lexicographic MDPs (LMDPs) and proves key properties that LMDPs satisfy. The resulting framework enjoys desirable features such as the existence of uniformly optimal deterministic policies, something not guaranteed in CMDPs. One limitation, as noted in Section 8, is the absence of algorithms for solving the proposed LMDP framework.\n\nThough I scored 3, I'm willing to raise the score if my concerns are addressed.", "questions": "* In line 124, what are the \"other methods\" being referred to?\n* In line 36:\n\n> Another common and practical example is when the first priority is to achieve some goal while the second priority is to minimize the time that it takes. Such objectives are also reminiscent of Asimov’s Three Laws of Robotics (Asimov, 1942), where the highest priority objective is to “not injure a human being or, through inaction, allow a human being to come to harm.”\n\nWhy is minimizing the time to achieve a goal aligned with Asimov's example? The connection is not clear to me.\n\n======\n\n* What does the $Q^\\star$ in Theorem 7 refer to? I think the $Q$ function is not defined for LMDPs. \n* Do you conjecture that the proposed LMDP framework satisfies a Bellman-type equation? The existence of a deterministic and uniformly optimal policy seems to suggest that such an equation might exist, which could be useful for constructing a dynamic programming algorithm.", "limitations": "The limitations are well described in Section 8.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\nThe paper is generally well-written, and the theoretical results seem solid.\nWhile no algorithm is provided, I believe that this axiomatic framework lays a strong foundation for future research on LMDPs.\n\n**Weaknesses:**\n\nThe significance of the results is not well articulated.\n\nWhat specific types of problems can this framework model compared to existing ones, like CMDPs?\nIf the LMDP framework can represent the same kinds of problems as CMDPs while guaranteeing a uniformly optimal deterministic policy, that would be a nice contribution.\nHowever, I could not find any concrete examples illustrating such cases in the paper.\nAlthough Figure 1 illustrates an example of an LMDP, it is not clearly explained how this example differs from what can be modeled by existing frameworks.\n\nExplicitly identifying problems that the proposed framework can capture but existing works cannot would strengthen the paper’s contribution.", "was_revised": true, "final_justification": "The authors explain the relationship between LMDPs and CMDPs, which addresses my main concern about the significance of the results.\n\nSince other reviewers also raised questions about the distinction from CMDPs, I suggest including a discussion on CMDPs in the camera-ready version.", "rebuttal": "We thank the reviewer for the constructive criticism and thoughtful questions. We reply to the questions below.\n\nQ: What specific types of problems can this framework model compared to existing ones, like CMDPs?\n\nA: There are CMDP problems that cannot be modeled as LMDPs. For example, any CMDP problem that leads to non-uniform optimal policy or stochastic optimal policy (and these do exist). \n\nIn general, an LMDP cannot be modeled as a CMDP. However, if we fix the starting state distribution and, given K priority levels, we know the optimal value of all but the lowest priority level – i.e., we know $V^\\star_1, …, V^\\star_{K-1}$ – then it is possible to turn the LMDP problem into a CMDP, by constraining these $K-1$ values with the known optimal values and optimizing the lowest-priority value – that is,\n$$\n\\max \\mathbb{E}[V_K(s_0)] \\text{ subject to } \\mathbb{E}[V_i(s_0)] ≥ V^\\star_i \\text{ for all } i \\in {1, …, K-1}.\n$$\nBasically, the first $K-1$ optimization problems are turned into constraints similar to turning $\\max_x f(x)$ into $\\max_x 0 \\text{ subject to } f(x) ≥ f^\\star$. We believe this to be a rather unnatural way of specifying the problem.\n\nWhen we have a single unsafe outcome, CMDP is constraining the probability of this outcome, assuming access to optimal achievable probability threshold (i.e., $V^\\star_1$) rather than optimizing it. We contend that this assumption (of access to optimal values) is a limitation of CMDP framework that LMDPs naturally address.\n\nQ1: In line 124, what are the \"other methods\" being referred to?\n\nA: We claim that vNM reward systems have advantages compared to “other”s. Another way of specifying rewards is to assign a reward of 1 to optimal actions and 0 to all other actions. It is not practical but is still a valid reward system. More generally, there are many reward functions that can lead to the same optimal policy. A simple case: there are 3 actions $a, b, c$. We prefer $a \\succ b \\succ c$ but we use a reward function that satisfies $r(a) > r(c) > r(b)$ – notice that $b$ and $c$ are swapped. The optimal action is the same but the reward function has some undesirable properties. Suppose the initial policy selects action $b$ and then we optimize it (w.r.t. rewards) to $c$ but, due to “bad” reward function, the policy actually gets worse. On the other hand, with vNM rewards, increasing expected reward is guaranteed to result in a more preferred policy. Ad-hoc reward shaping methods can also be considered to be part of the \"other\" we mentioned.\n\nThe advantage of vNM reward systems being insensitive to environment mechanics is also nicely demonstrated in the example in the response to first Q of reviewer AHWB where we want rewards that work regardless of the shape of the maze and hazard probabilities.\n\nQ2: line 36?\n\nA: They are not connected. The writing should be changed to \"... the time that it takes. **Lexicographic** objectives are also reminiscent of Asimov’s Three Laws of Robotics...\"\n\nQ3: What does the Q* in Theorem 7 refer to?\n\nA: The definition of Q* is the same as in scalar-reward MDP with the difference that maximization is w.r.t. lexicographic ordering of vectors. We will revise the text to clarify this.\n\nQ4: Do you conjecture that the proposed LMDP framework satisfies a Bellman-type equation?\n\nA: A Bellman equation does indeed exist and it is the same as the one for scalar-reward MDPs: $Q(s, a) = \\mathbb{E}[R(s, a) + \\gamma \\max_{a’} Q(s’, a’)]$ with the distinction that Q-values are vectors and maximization is w.r.t. lexicographic ordering of vectors. However, in the lexicographic case, the Bellman operator is no longer a contraction mapping, so iterating it does not give us an algorithm with convergence guarantees."}]

Author rebuttal:

Meta-review: This paper provides an axiomatic derivation of lexicographic MDPs. Lexicographic MDPs are useful to represent certain types of preferences that classic MDPs are not expressive enough to capture.

The main strength is that lexicographic MDPs, while being in their early stages of development, are a promising modelling tool, particularly for problems involving safety.

There were a couple of minor weaknesses: novelty of proof techniques, lack of sufficient comparison with constrained MDPs and basic algorithmic tractability (i.e. lack of algorithms for solving lexicographic MDPs). These were largely addressed in the discussion.

The discussion focussed on the weaknesses of the paper as above.
Decision: Accept (spotlight)