An Analytical Study of Utility Functions in Multi-Objective Reinforcement Learning
Authors: Manel Rodriguez-Soto
Juan Antonio Rodriguez Aguilar
Maite López-Sánchez
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning;multi-objective decision making; multi-objective reinforcement learning;learning theory;markov decision processes
Primary area: learning_theory
TL;DR: In Multi-Objective Reinforcement Learning, we offer a characterisation of the types of preferences that can be expressed as utility functions, and the utility functions for which an associated optimal policy exists.

Abstract: Multi-objective reinforcement learning (MORL) is an excellent framework for multi-objective sequential decision-making. MORL employs a utility function to aggregate multiple objectives into one that expresses a user's preferences. However, MORL still misses two crucial theoretical analyses of the properties of utility functions: (1) a characterisation of the utility functions for which an associated optimal policy exists, and (2) a characterisation of the types of preferences that can be expressed as utility functions. As a result, we formally characterise the families of preferences and utility functions that MORL should focus on: those for which an optimal policy is guaranteed to exist. We expect our theoretical results to promote the development of novel MORL algorithms that exploit our theoretical findings.

An Analytical Study of Utility Functions in Multi-Objective Reinforcement Learning
Manel Rodriguez-Soto
Juan A. Rodriguez-Aguilar Artificial Intelligence
Artificial Intelligence
Research Institute (IIAA-CSIC)
Research Institute (IIIA-CSIC)
Bellaterra, Spain
Bellaterra, Spain
manel. wwwel..oddiigueziiia.. esic.es
jarßiiia. csic.es
Maite Lopez-Sanchez
Universitat de Barcelona (UB)
Barcelona, Spain
maite_ leiite_opezeuu.... edu
Abstract
Multi-objective reinforcement learning (MORL) excellent framework for multi-objective sequential eerision-making MORL employs utility function to aggregate multiple objectives into one that expresses user's preferences. However, MORL still misses two crucial theoretical analyses of the properties of utility functions: (1) a characterisation of the utility functions for which an associated optimal policy exists, and (2) characterisation of the types of preferences that can be expressed as utility functions. this paper, we contribute to both theoretical analyses. As a result, we formally characterise the families of preferences and utility functions that MORL should focus on: those for which an optimal policy guaranteed to exist. We expect our theoretical results to foster the development of novel MORL algorithms that exploit our theoretical findings.
1 Introduction
Sequential decision-making problems are ubiquitous, impacting areas like autonomous driving [6]
robotics (35] finance 3 and healthcare (4) to name few. Recently, Reinforcement Learning (RL)
has emerged as pivotal framework for addressing sequential decision-making tasks [3 Most
of the RL literature has focused on problems for which an agent deals with a single objective (e.g.
get rich in finance, win race). However, real-world scenarios often present multiple, conflicting objectives 332 (e.g., self-driving car must ensure safety, efficiency, and passenger comfort).
Multi-Objective Reinforcement Learning (MORL) has developed as one of the most promising frameworks for addressing multi-objective decision-making [89 22 Despite its novelty compared to single-objective RL, the current state of the art in MORL shows promising results for tackling real-world problems that are inherently multi-objective [10 32 Most MORL approaches are utility- based and assume that there exists a utility function (10) that combines all objectives into a single one, allowing the learning agent ponder between them. However, deciding the most appropriate utility function is a problem in itself. Given that, the literature on MORL focuses on learning a set of candidate policies, called the undominated set [10], which maximise all possible utility functions. In that way. once a utility function is decided, the decision sacker maker can directly select the policy from the undominated set that maximises it.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Thus, utility functions are widely considered fundamental concept of MORL 31. Utility functions capture a user's preferences over different objectives and drive the learning [2)) Hence, both concepts (utilities and preferences) are at the core of state-of-the-ar MORI. The state-of-art approach of considering the undominated set as the most general solution concept of MORL. relies on two assumptions:
1. On utilities: assumes that for every utility function, there exists policy optimising it.
2. On preferences: It assumes that any user preference can be expressed utility function.
Unfortunately, none of the assumptions is correct. There are many examples of preferences that cannot be expressed with a utility function (e.g., the lexicographic order [4], as proved in (5)). Likewise, even for problems with a finite amount of possible states and actions, there are many utility functions for which there is no optimal policy for any state (we provide an explicit example in the later sections).
These two counterexamples raise the need for answering the following two main theoretical questions: (1) for which type of utility functions are optimal policies guaranteed to exist? (2) what types of preferences can be represented as utility functions? The state of the art on MORL has not addressed these fundamental research questions so far.
Against this background, we propose an in-depth analysis of utility functions in MORL by means of the following three contributions:
1. We provide two novel MORL fundamental theoretical concepts. We introduce the first formal definition of preferences between policies in MORL and the first formal definition of utility maximisation in MORL.
2. Given a utility function in MORL, we characterise the sufficient conditions that guarantee the existence of an optimal policy maximising it.
3. We characterise under which conditions we can express preferences between policies as utility functions. These are represented by a type of function called quasi- repressrereeetativivee utility function, which preserves the most preferred policies as its maximal points.
We expect that theoretical results will lead to novel MORL algorithms that exploit the analytical properties of the utility functions introduced here.
The remainder of this paper is organised as follows. Section 2 provides the necessary background in multi-objective reinforcement learning. Then, Section 3 provides sufficient conditions to guarantee the existence of utility-mxximiiing policies. Next Section [ characterises the family of preferences that can be represented with utility functions. Thereafter, Section SectionS5presss presentss the related work. Finally, Section 6 summarises main thcoretical findings and sets paths for future research.
2 Background
2.1 Single-objective reinforcement learning
In single-objective reinforcement learning (RL), sequential decision decision-making problems are formalised as Markov decision process (MDP) [1,271 An MDP represents an environment in which an agent is capable of repeatedly acting upon it to make it to transition it to different state, and immediately receive a scalar reward (representing the agent's objective) after each action:
Definition (Markov Decision Process). A defined as tuple (S,A, R, I) of two sets and two functions: the set of states S, the set of actions A(s) available at each state s, the reward function S x T : S x A x S + [0, 1] specifying the probability T(s, a, 8') ) TP(s' _> TR, and the transition function an action a is performed upon the state s.
I Markov Decision Process (MDP) is
8, s.a)) that the next state is s' if
An agent's 's behaviour in an MDP is called policy A policy π (Ts, a) describes how likely an agent will perform action a if the agent currently in state s. The agent's objective is to learn the policy that accumulates the maximum sum of discounted rewards. Thus, to evaluate given policy, we need
Throuuhh the paper, we refer to single-objective MDP simply MDP.

---

to compute the (expected) discounted sum of rewards that an agent obtains by following it. This operation formalised by means the so-called value function V : S - E. defined as:
VT
E
7 R(S++, A4tk, S(+R+1) S 8, m]
(1)
k=
where y E [0, 1) is the discount factor, indicating how much we care about future rewards. Value functions allow us to partially order policies [27]. Hence, they allow to formalise the agent's objective as learning the policy that maximises the value function. This policy is defined as the optimal policy:
Definition (Optimal policy). Given an MDP M, its optimal policy n, is the policy that maximises the value function V Formally:
V (
for every state of the MDP M, and every policy π of M.
The optimal policy is the solution concept single-ohjective RI.. For any MDP with a finite state and action space, at least one optimal policy exists, which is also deterministic and stationary 77.
2.2 Multi-objective reinforcement learning
Multi-objective reinforcement learning (MORL) deals with environments in which an agent pursues multiple objectives simultaneously (for example, in healthcare context, the health and the autonomy of a patient). Recall that in single-ohjective RI., the reward function represents the agent's s objective. Thus, MORL considers environments with multiple reward functions, called Mulri-Ohjectio Markov Decision Processes 19 TO Formally:
Definition 3 (Multi-Objective MDP). An n-objective Markov Decision Process (MOMDP) is defined as a tuple A,,A, R.,1 T where S, A and T are the same as in an MDP, and N S x A x S + R" is vector of reward functions, providing a reward function Ra for each objective i E (l....,m..
Policies in a MOMDP are evaluated by means of a value function vector V. defined as the vector of all value functions per objective ((s) = (Vi (s)).
If not all objectives can be fully fulfilled simultaneously. the agent needs to prioritise between them. To represent an agent's ' preferences with respect to multiple objectives, most approaches in MORL assume that the value function of each objective can be aggregated into single function. That way, the agent's goal becomes to maximise this aggregated value function. This aggregation is performed by means of utility function u (also called scalarisation function) [8 22 In MORL, a utility function u is defined as a function mapping the domain of all value functions (a subset of the real coordinate space IR") the real space R. With u, the agent's goal can be expressed as learning policy that maximises the function (u (s)))= = (V(())) Formally 2
Definition 4 (Utility function). Let M be MOMDP of n objectives. Any function u R RR is utility function of M.
The family of linear utility functions is especially notable. Any linear utility function returns a weighted sum of value functions (I (s))) = vt ((s). For linear utility functions, the scalarised problem of maximising o V can be solved with single-objective reinforcement learning algorithms
While in single-objective RL there is clear definition of the solution concept (a deterministic and stationary optimal policy), there no equivalent for MORL. Instead, the utility function is typically assumed to be unknown, and that only have minor assumptions about it (e.g., that it is linear or that it is monotonically increasing) [19 [2 [0]. With that in mind, the solution concept in MORL is learn set of candidate policies n. with each of them optimising a possible utility function u. The next Section explores typical solution concepts in MORL.
"The presented definition of the utility function follows the Scalarised Expected Returns (SER) criterion, which is by far the most popular one the MORL literature [10]. We forus exclusively on the SER criterion. Beeause the linear utility function for V also induces utility function for Rř. Notice that w v(((s) T EI> 7th Retk+1 s] E| x W Rets+1 s).
a (s)
3

---

2.3 Solution concepts of MOMDPs
The solution concepts in MORL depend on how much is assumed about the utility function. If nothing is assumed, the goal is to learn the set of maximal policies for any utility function. It is important remark what means for policy to be maximal for a utility function. By far. the majority of the MORL community follow the so-called inteeinndeendden (SI) criterion to define optimality 19 18 22 TQ]. Given a MOMDP, this criterion considers that a policy nT, maximises a utility function if and only if it is maximal among the expectation of possible initial states (for some value function V and the random variable of possible initial states Sq). We denote this expectation with Vsl:
EV (So)].
Due to its simplicity, the state-independent (SI) criterion is widely used in MORL and RL in general. While it is generally innocuous in single-objective RI, it can generate contradictory policies in multi-objective RI, as we will show in Example (aanmlleeebloooo Ibelow.
Considering this vatee-nneependent criterion, all solution concepts for MOMDPs have been formalised exclusively for it. Thus, the sate-of-the-ar general solution, the undominated set, is defined as the set of policies that are maximal for at least one utility function. Formally [10]:
Definition 5 (Undominated set). Given MOMDP M, its undominated set U (MM is defined as the set of policies for which there exists a utility function u with a maximal scalarised value.
UMM = { E I(M) 3w: Vn' E I(M),, u(Vgr) 2 u(Vgi)).
(4)
where II(M) is the set of all possible policies of an MOMDP M.
We recall that the definition of undominated set makes no assumption on the structure of the utility function. If we constrain
be a linear function, then the solution concept becomes the convex hull. The convex hull of a MOMDP contains all policies that are maximal for at least one linear utility function (again, according to the SI criterion). Formally [10:
Definition 6 (Convex hull). Given an MOMDP M, its convex hull CH(M) is the subset of policies n, that are optimal for some weight vector út:
CH(M)= = { E (IM) 3&e E R" Va' E (IMM), w- VVg, 2 w- Vgl
(5)
where ([M) is the set of policies of M.
3 Utility optimal policies
Recall that the MORL literature defines solution concepts following the state-independent criterion. However, for proper analysis of utility functions MORL, we require more precise definitions considering each and every state of a MOMDP.
Furthermore, recall that, in single-objective MDPs, value functions impose a partial order over policies of an MDP (27). However, thanks to Banach's 's fixed point theorem, we know that a deterministic and stationary optimal policy always exists for any finite MDP (and, thus, for every state) 77]. These theoretical properties become much weaker in multi-objection MDPs. In particular, the Banach fixed point theorem does not generalise even for finite MOMDPs. Thus, we may have finite MOMDPs for which no optimal policy exists for any state. These "more precarious" theoretical results motivate even more the need for studying the existence of optimal policies in a MOMDP at two different levels: one at single-state level (i.e., considering single state), and another one at the all-states level (considering all states).
We begin by defining utility optimality at the state level: a given policy π is optimal at state s with respect to given utility function u if and only if it obtains more scalarised discounted returns than any other policy at Formally:
Definition (utility optimal policy at state), Let M be a MOMDP with state set S. Let II be the set of policies of M. Let u be a utility function. Then, policy n. E IIM is optimal with respect to utility function state S and only if:
(u o vaa (s) 2 (u Va (s),
(6)
for every policy II. We say that n. is (u, s) -pptimal for short.

---

Example 1. Consider a MOMDP M with two states: an initial state $1 and a terminal state $2- An agent can perform two actions (01, 02) in this environment, with rewards R(81,01) (1,0), R(si 02) (0,1) respectively. Consider the utility function u(xr, y) = x++ sin(y). The deterministic policy (81) 01 that obtains vectorial value V* = (1,0) clearly {u, 81) -optonaiaal since sin(y) y for any y E 1].
In the same vein as in single-ohjectoo RL., given MOMDP, we deñin a policy as utility optimal at the all-states level (or simply utility optimal) as a utility optimal policy in every state in the MOMDP. Formally:
Definition 8 (utility optimal policy). Let M be MOMDP with state set S. Let 11 be the set of policies of M. Let u be a utility function. Then, a policy na E 11.M is optimal with respect to utility
function u if and only if:
(u )=*)(²)) 2 (u (*),
for every policy E II-M, and every state E S. We say that n, is u-optimal for short. Example In the MOMDP in Example| policy x r(s))= = 01 u-optimal since there are only two states, and the second one is terminal.
We know that a (deterministic) u-optimal policy always exists for any linear utility function, as shown in Section 2.2 However, this is not always the case for arbitrary utility functions. The following three examples illustrate conditions that are not enough to guarantee the existence of neither deterministic nor stochastic utility optimal policies in finite MOMDPs. These conditions are:
1. That the utility function is monotonically increasing (a family of utility functions specially studied in MORL. [8 10]. Example [ illustrates how this condition is not enough to guarantee a deterministic u-optimal policy.
2. That the utility function is strictly monotonically increasing. Example 5 shows how this condition is not enough to guarantee a stochastic (u, s)-otim policy for any given state s.
3. That the utility function is both strictly monotonically increasing and continuously differ- entiable. Axample[shooee how even assuming both conditions there are utility functions without stochastic u-optimal policies.
In the following Example S we consider the Chebysher function (also called Tchebycheff. a well- known utility function in MORL [17 19 18 [Q] The Chebyshev function returns more scalar value the nearest a given input value x is to a reference value F. Moreover, the Chebyshev function is also monotonically increasing [18).
Example 3. Let > 0 be small real number, F E R² reference value, and w E R weight vector such that each w; 2 O. The Chebyshev function Vr,,, : :R"" + R defined as [7]]
(x) = -mmax wi |r; -xil+ Σ wi 1r:11:x]] r:().
(8)
Let M be a 2-objective deterministic MDP with three states 81, 82, and 83 such that 83 is the terminal state. Regarding actions, there is one possible action in $1, which has associated rewards ((s1,a)) (1. Action a1 transitions the state 82. Then, in state s2, there are two possible actions with associated rewards R((22 02) (2,20) and M(s2 aa) (3, All actions in 82 transition to terminal state 83.
This environment has two possible deterministic policies. first policy is Tı (s1) a1, TI (52) a2 This policy obtains values (* = 20), 7 (52) = (2, 20). The second policy is T2(31)
a1, x2(52) = 03- This policy obtains values (=) = 14, 7- (s2) = (3, 1). We select as
reference point F (3.5, 20), associated weights w (1, 1/19), and O. For this configuration
we have: for policy n1, ((V/T1 (s1) = 005, (V (s2)) = 1.5. For policy n2. v(V===(s))
e) (s2)) = -1. Clearly, Tı is the only deterministic (t), $1) optimall policy, while n2 is the only deterministic (v. s2) -optimal policy. Thus, no deterministic vi-optimal policy exists.
Example 3 showed that deterministic u-optimal policies do not necessarily exist in finite MOMDPs,
fact that was alrcady known in the MORL literature [18] But can go step further: the
5

---

next Example 4 shows that being finite is not enough for an MOMDP to guarantee the existence of stochastic u-optimal policies. Moreover, the utility function from Example 4 is both strictly monotonically increasing and continuously differentiable:
Example 4. Consider the utility function u(x, u) + y which is strictly monotonically 20 increasing for any (x. 9) E TR+ x RR and continuously differentiable in R2. Let M be the same 2-objective deterministic MDP from Example
This environment has the same two deterministic policies from Example 3 The first policy is T (s1) = a1; 31 (82) = 02 which obtains scalarised values u( (s1)) se 4.16, u (s)) = 3.24. The second policy is T2((1) = 01, T2(22) = 03. which obtains scalarised values u ((V=((s))) ~ 4.17, uV=TT (s2)) = 3.21.
easy to check that ai is the absolute (u, s2)-opptmal policy, while 22 is the absolute (u, 81)- optimal policy. We leave the details at Appendix A.7 Thus, no stochastic u-optimal policy exists.
Our third example is finite MOMDP and a strictly monotonically increasing utility function u for which no stochastic (u, opttmmal policy exists for any state s.
Example 5. Consider the utility function u such that if x = y, then u(x, 0, and otherwise u(x. v) = -- and 52 such that 81 is the initial state and 52 is the terminal state. There are two possible actions in $1 with associated rewards R((1, 01) = (1,0) and R(s1, a2) = (0, 1).
1 Let M be the 2-objective deterministic MDP from Example 7
with two states $1
and T (81,, 02) = 1 p for some p E [0, 1]. The vectorial value of such policy at state $1 will be (*1)s (p. 1 p)- Notice how every possible value belongs to the Pareto Front of M. Thus, any utility function is strictly monotonically increasing
Every policy of M will be of the form T (811 a1)
in M, including the one defined in this example.
In particular, for any policy, its scalarised value will be u(1, 1..1-111 12p-1]
If for any policy т we have ((81, a1) = < with > O small enough that p p+<< obtains more scalarised value than л. Similarly, if (s1,, a1) - p > 5. we can find an alternative policy n' such that (T8,,a)) = =p-é that obtains more scalarised value than т. Thus, no (u, spoommiaaal policy exists in this MOMDP.
=p< 1. then the policy nt such that π ((81, +
The result of Example 5 is specially significant because most MORL literature (with its state- independent criterion that only considers initial states So), focuses on computing (u, -o)toimall policies on strictly monotonically increasing utility functions 19 10 As we have shown in Example 5 such optimal policies are not guaranteed to exist.
Therefore, the logical next question after these three examples is to ask for which families of utility functions there exists at least one global utility optimal policy or least one utility optimal policy for every state. In particular, we focus on stationary policies, like in singlc-objective RL. Formally:
Problem 1. For which families of utility functions is guaranteed that a stationary (u. s) s)-ottia policy will exist for every state s of every possible finite MOMDP?
Problem 2. For which families of utility functions is guaranteed that stationary u-optimal policy will exist for every possible finite MOMDP?
and 3.2 focus on providing sufficient conditions to guarantee the existence of utility optimal policies in a state and utility optimal policies in general, respectively.
Next, Sections 3.1
3.1 Utility optimal policy at a state existence
This Section introduces family of utility functions that solve Problem T In particular, we offer sufficient condition to guarantee the existence of a stationary (u, s)-optimal policy for every state s of finite MOMDP. This sufficient condition is that the utility function is continuous. Formally:
Theorem 1. Let M be a finite MOMDP. Let u be a continuous utility function for all value functions of all policies II(M) of M. Then, for every state of M, at least one stationary (u, -pptimal policy exists.
Proof 1. See Appendix A.3

---

Continuous utility functions are one the most extensively studied and applied family of functions due their well-behaved properties (e.g., existence of absolute maximum and minimum). Nevertheless. recall that Theorem only provides sufficient conditions, and thus there might exist (u, s)-otimall policies for discontinuous utility functions. We offer such an example in the proof of Theorem
3.2 Utility optimal policy existence
Demanding that the same policy u-optimal for some utility function u for every state of the MOMDP is much harder problem than demanding it for given state. Thus, in this case, it is not enough that the utility function is continuously differentiable (i.e., continuous and all partial derivatives also continuous), and it is not enough that the utility function is also strictly monotonically increasing (as seen in Example
It is already known that, for linear utility functions, we can obtain a u-optimal policy. So, the question if we can find at least another family of utility functions for which u-optimal policy exists. Theorem presents such a family: utility functions that result from composing an affine function together with a strictly monotonically increasing function. Formally:
Theorem Let M be a finite multi-ohjective MDP M. Let u be utility function decomposable as u(x) = h(g(z)), with g(x)= IR" + TR being an affine function, and h(x)) IR. -> IR being strictly monotonically increasing function all value functions of all policies LI(M) of M. At least one deterministic and stationary u-optimal policy exists.
Proof 2. See Appendix A.4
Notice that, in particular, Theorem 2 also covers linear utility functions. Linear utility functions are one of the most widely applied families of utility functions in MORL [8 TQ. To finish this Section, we show an example of a function composed by an affine and strictly monotonically increasing function (that hence satisfies Theorem 2} that produces a non-linear (and non-affine) utility function
for which u-optimal policy exists.
Example 6. Consider any 2-objective MDP M where all rewards are positive (i.e. R(s a) E R+ x Ikt for all 8, a), and utility function u. defined as
1
u(æ y) x+ sin 3-nnnnnnne +
(9)
= We decompose u(x, y) as u(x, v) = h(g(x, v)) with g(x, v) = + y + being affine, and h(x) u-optimal policy exists.
1 x+sin(a] being strictly monotonically increasing. By Theorem 2
only provides sufficient conditions of utility functions u for guaranteeing the existence of u-optimal policies. In fact, Example 2 shows non-affine utility function for which an w-optimal policy exists in a particular MOMDP.
Notice that Theorem 2
4 Preference relations in MORL
In the previous section, we characterised the utility functions for which we can compute a utility optimal policy. However, as mentioned in the Introduction, more fundamental question remains unanswered: Which user's preferences can be expressed as utility functions in given MOMDP?
We require formalising preference relations and their maximal elements MOMDPs to answer this last question. Preference relations, also known as binary relations, allow us to express, among While the state of the art MORL makes no distinction between preference relations and utility functions [10], it is important to maintain them as two separate concepts. First of all, let us provide a formal definition of preference relations in MORL, inspired by 25
two elements of a set, which one we prefer 25 14]
Definition (Preference relation in MOMDP). Let M be MOMDP of n. objectives. We define preference relation in M as any binary relation over least one pair of value vectors of " In particular, say that:
7

---

a value function V1 E V is weakly preferred to another value function V22 E V if and only if (i(s)= = V2(s) for every state of M. In short, we denote V1 tM V22
a value function V2 E V is strictly preferred to another value function V22 E V if and only if (s) = (2(s)) for every state of M and not V2(s') (s(5') for at least one state s' of M. In short, we denote V1 > M V/2
If for two value vectors we have that Vi = (s) and 132 > (s),, we say that they are indifferent, and we denote it with the & symbol. Notice that this definition makes no assumption over the preference relation. We do not impose that this preference relation is a pre-order, a partial order, or a total order [9]. Considering that the MORL literature applies utility functions of all kinds, we did not want to restrict our definition.
Following the game theory literature, humans have preferences, and we (sometimes) can represent them as utility functions, but not the other way around [14]. In fact, sometimes, a utility function that fully represents our preferences may not exist. If such a utility function exists, we call it the representative utility function of preference relation Z. Formally:
Definition 10 (Representative utility function). Let M be a MOMDP, and let ł be a preference relation in M. Then, we define utility function u as representative of the preference relation ł if and only if. for every pair of possible value functions Vi, V2z and every state s of M:
(s) = Vz(s) = (uo Vi)(s) 2 (uo Vz).
(10)
Some (but not all) preference relations have representative utility functions. However, any utility function u, is representative of some preference relation 2.. defined as exactly fulfilling Equation I0
In order theory, for any quasi-order (i.c., preference relation that is at least reflexive and transitive), we can define the concept of maximal elements (9. In our case, given a preference relation ž between the value functions of MOMDP, its maximal elements would be the value functions associated with the policy that we expect the agent to learn. Formally:
Definition 11 (Maximal element). Let M be a MOMDP. Lei Z be a preference relation in M that is at least reflexive and transitive (a quasi-order). Then, the value vector Vz(s) of value function V. is a maximal element in state if and only for every other possible value function V of M:
((s) z Vs(s) = v
(11)
In finite single-objective MDPs, the optimal value V=(s) is a maximal element for every state s, for the preference relation t defined as V(s) = (s) = V(s) 2 V'(s).
Example 7.
As mentioned in the introduction above, not all preference orders in MORL can be represented as a utility function. One of the most well-known cases is the lexicographic order [5) 2]. Although
Lexicographic MORL has been studied in detail g 29 30 24] almost no work MORL (with the exception of (23)) has noticed that an associated utility function does not exist in general. Let us see through an example why the lexicographic order cannot be represented as a linear utility function.
For utlltyy functions in general, we refer to Corollary 2 of (23].
Example 8. Consider MOMDP M with two states: an initial state $1 and a terminal state 82. An agent can perform three actions in this environment (a1, u2, aa), with rewards N(sI, a.) = (1,
a())) = (0, 1), and A(s1, 03) = (1, 1), respectively. Consider now the lexicographic order z such that objective is always preferred to objective 2. Hence, R((x) ((81, uz) > R(s1, a1) > M(s1,a)).
Any linear utility function here will be of the form Vo, (x,, y) = x + B y- For uh to represent >, it must satisfy ua, (1,, > uo, (1, 0) and (1,, > ua (0, 1), for example, u10, y) =
10x + y.
However, policies can be stochastic, and thus, we can have for instance any policy т such that ((s1,a1) = p. x($1,
P. with 1 2 p 2 O, which has associated value (s()) = (p, p). Hence, the utility function must also satisfy u(1,0) > u(0.9, 0.1) > ... > u(0.1, 1.99 > ( And it needs to be absolutely precise: u(p + e, - -) > u(p, 1 - p) for every > 0 arbitrarily small. Thus, it is impossible represent the lexicographic order linear utility function.
8

---

While lexicographic orders cannot be represented with utility functions in MOMDPs, they do have maximal elements among finite MOMDPs. utility function that shares the exact same maximal elements as a lexicographic order would be very helpful. With such utility function, we could still find the policies that maximise a lexicographic order with state-of-the-ar MORL. algorithms. Having formalised maximal elements in MOMDPs for any quasi-order, we can introduce utility functions that at least preserve maximal elements. We call this kind of utility function Formally:
Definition 12.
Let M be an MOMDP. Let = be a preference relation ==j in M that is at least reflexive and transitive (a quasi-order), Let u be utility function such that for every state of M:
(s) is maximal element of at state - (s())
E arg magmax((ue (s))
(12)
P
Then, we say that u is quasi-representatiiee of in M.
Example 9. Consider the MOMDP M in Example g The utility function u(x, y) = 10x + is guasi-representative of the lexicographic order because u(1, 1) > u(1.0) 0) and u(1, > w(0, 1).
In fact, quasi rureeseepreeeneativv utility functions allow to define an equivalence relation between utility functions. Hence, by abuse of notation, we will also say that two utility functions are quasi- representative for given MOMDP if and only if they share the same maximum elements for every state & of this MOMDP.
Example 10. Consider the same MOMDP M and the lexicographic order ž from Example & For example, utility functions u(z, y) = 10x + and (z. y) = 15r + y + 30 share the same utility optimal policy (which is (s1) a3). and hence are quasi-representattie for M and Z
Notice that if a utility function u is representative of some preference relation 2, it is also quasi- representative of z. Notice also that a utility function may be representative or quasi-representative of given preference order for some MOMDP but not for other MOMDPs.
Now, given a MOMDP, what conditions must a preference order meet to be represented by a quasi- representative utility function? Essentially, it is sufficient to have maximal element for every state of the MOMDP We present now a family of preference orders for which a quasi- represstppresnttevvvee utility function always exists for every finite MOMDP:
Theorem 3. Let ž be a preference relation and M any finite MOMDP. Assume that 2 is: (1)
complete (either a - b or b ž a or Rs b for every two possible value vectors o, b of M); (2) transitive (if a > b, and b 2 then a 2 c); and (3) at least one maximal element V(s) exists for every state s of M. Then, a repesettpreeentatiive utility function exists for 2 in M.
Proof 3. We offer a constructive proof. For every state s, consider its set of maximal elements (7.)) according to 2z, which is non-empty for every state due to Condition (3). Since the preference relation is complete, for every state all its maximal elements will share the same value (i.e., Vi V2)))) for every two V,, V22 E V. (s)). Hence, without loss of generality, we consider that there a single maximal element per state. Then, the number of maximal elements is at most |S], and we can order them according to ž (we can order them because > is total and transitive). Then, set a number between 1 and |S] for each of these elements, ordered by 2. For every other vector E R", set u(x) = O. Now, by construction, for every state s we have that maxp (u ()()) E (s)).. In other words, u is a quasi-representative utility function, such that it returns the most preferred value vector for each state s according >.
Completeness and transitivity are very common conditions for preference relations in game theory [1]]. The third condition is required for MOMDPs since we are dealing with an infinite amount of policies. For instance, Example 5 showed a finite MOMDP for which there is no maximum element for any environment state.
The main takeaway from Theorem 3 is that MORL algorithms should focus on the family of preference relations that fulfils all its conditions. Such conditions are sufficient to guarantee the existence of quasi-representattive utility function, as we just proved.
The family of preference relations satisfying the conditions of Theorem 3 has examples aplenty, such as the previously mentioned family of lexicographic orders. Moreover, any continuous utility
function is representative of a total order that satisfies all conditions of Theorem 3
9

---

5
Related work
Most of the literature in MORL focuses on creating novel solution concepts in MORL and algorithmic methods to solve them (e.g.. 228
24 21).. Instead, we focus on characterising for which families of utility functions these solutions exist, a largely overlooked theoretical problem despite its relevant implications. Take for instance the work in [33,, where Van Moffaert et al. present method for computing the Pareto front of a given MOMDP. They implicitly assume that this Pareto front will always include the solution policy (a u.-oiiaal policy in our terms), but as we have proven in Example 4 this not always the case.
33
20
Then, regarding the study of preference relations in MORL, to the best of our knowledge the only other works in the literature apart from ours are 2 26 Skalse et al. 's theoretical results in [23] complement ours by stating that, for every so-called objective (a preorder between policies), u- optimal policy exists if and only if this objective can be represented with linear utility function. This aligns with our results in Theorem 2 However, they do not establish whether there may be more families of utility functions for which u-optimal policy exists, as we do with Theorem 2 Moreover, our preference definition allows for ordering policies in each state of the environment, providing more granularity than their objective definition. This difference is also significant, because allows us to identify issues in the solution concepts of MORL as we have tried to illustrate with Examples S and
Next, Subramani et al. in 26 follow on the work in 223 but they tackle a different problem than us. Their focus is on compare the expressivity of the MORL framework with other frameworks. They aim to know which objectives (defined identically to (23) can be represented on each framework. However, like (23. their objective definition does not allow them order policies differently per state, unlike our preference definition.
To finish, closely related
work, Miura in [5] tackles the problem of characterising preferences and their properties in constrained MDPs [. They define preferences as sets of acceptable policies and aim to find for which environments they can set the constraints and reward functions of constrained MDP (CMDP) for which the acceptable policies are optimal. While CMDPs and MOMDPs share many similarities, they belong to separate research area. The major difference between them is that CMDP has constraints, while an MOMDP has a utility function.
Conclusions
Multi-objective reinforcement learning (MORL) is the most promising framework for dealing with sequential decision-makee problems with multiple objectives. In MORL, the learning agent ponders between the multiple objectives by means of utility function aligned with the user's preferences. However, the state of the art in MORL has disregarded two fundamental theoretical problems related to utility functions: (I) for which utility functions associated optimal policy is guaranteed to exist? and (2) which preference relations can be expressed as a utility function?
In this paper, we contributed to the state of the art in MORL by formalising both problems for the first time and by analysing each one. For utility functions, we first formalised the concept of utility optimality in MORI. Then, we provided sufficient and insufficient conditions for such policy to exist for any finite MOMDP. For preference relations. we first formalise them for MOMDPs, and we also provide the minimal conditions to guarantee that they can be expressed as a particular type of utility function, the so-called ruass-representaaive utility functions. We expect our theoretical contributions to spark interest in both theoretical and practical MORL research. In fact, our results have direct practical consequences: to avoid contradictory policies, the MORL community needs to design algorithms that check that their learned policies utility optimal.
We envision many directions for future research. On the theoretical side, generalisation of the presented theoretical results to multi-agent multi-objective environments would be of great interest in the MORL literature 22 On the algorithmic side, we expect to see the development of algorithms that exploit our Theorems to compute utility optimal policies.
10

---

Acknowledgements
The research presented in this paper was supported by the EU-funded VALAWAI 101070930) project, the Spanish-funded VAE (# (ED22021-11125BB-C)) 113594RB-100) projects. This work was supported by grant PID2022-136787NB-U by MCIN//EV/O,
and Rhymas (# PID2020-
funded trans 110.////00...1001000000001010000 1000 1033. It was also funded by GUARDEN (101060693), Fair- AUTODEMO (SR21-00329), TAILOR (H2020-952215) Prep- Particip2.0 ( 24$03545-0011 grants 2021 SGR 00313 and 2021 SGR 00754. Maite Lopez- -ancheez belongs to the WAI research group (University of Barcelona) associated unit to CSIC by IIlA.
References
[1] E. Altman. Constrained markov decision processes, 1999.
[2] S. Barbera, P. J. Hammond, and C. Seidl, editors. Handbook of Utility Theory: Volume 1: Principles. Kluwer Academic Publishers, 1998.
[3] A. Charpentier, R. Élie, and C. Remlinger. Reinforcement learning in economics and finance. Comput. Econ., 62(1))425-462, apr 2021.
[4] A. Coronato, M. Naeem, G. De Pietro, and G. Paragliola. Reinforcement learning for intelligent healthcare applications: A survey. Artificial Intelligence in Medicine, 109:101964, 2020.
[5] G. Debreu. On the preferences characterization of additively separable utility. In A. Tangian and J. Gruber, editors, Constructing Scalar- Valued Objective Functions, pages 25-38, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
[6] B. B. Elallid, N. Benamar, A. S. Hafid, T. Rachidi, and N. Mrani. A comprehensive survey on the application of deep and reinforcement learning approaches in autonomous driving. Journal of King Saud University Computer and Information Sciences, 34(9):7366-7385 -7796, 2022.
[7] E. A. Feinberg. Total Expected Discounted Reward MDPS: Existence of Optimal Policies. John Wiley and Sons, Ltd, 2011.
[8] Z. Gábor, Z. Kalmár, and C. Szepesvári. Multi-criteria reinforcement learning. pages 197-205, 01 1998.
[9] E. Harzheim. Ordered sets, volume 7. Springer Science Business Media, 2005.
[10] C. F. Hayes, R. Rádulescu, E. Bargiacchi, J. Källström, M. Macfarlane, M. Reymond, T. Ver- straeten, L. M. Zintgraf, R. Dazeley, Heintz, E. Howley, A. A. Irissappane, P. Mannion, A. Nowé, G. Ramos, M. Restelli, P. Vamplew, and D. M. Roijers. A practical guide to multi- objective reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems, 36, 2022.
[11] L. P. Kaelbling, M. L. Littman, and A. W. Moore. Reinforcement learning: A survey. J. Artif. Int. Res., 4(1):237-285, May 1996.
[12] C. and K. Czarnecki. Urban driving with multi-objective deep reinforcement learning, In Pro- ceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 19, page 359-367, Richland, SC, 2019. International Foundation for Autonomous Agents and Multiagent Systems.
[13] Y. Li. Deep reinforcement learning: An overview, 2017. cite
[14] M. Maschler, Solan, and Zamir. Game Theory, 2nd Edition. Cambridge University Press, 2013.
[15] S. Miura. On the expressivity of multidimensional markov reward. In Proceedings of the 2022 Conference on Reinforcement Learning and Decision Making., 07 2023.
[16] E. L. Pennec. Reinforcement Learning Book of Proofs. 2023.

---

[17] P. Perny and P. Weng, On finding compromise solutions in multiobjective markov decision processes, volume 215. pages 969-970, 01 2010.
[18] D. Roijers and S. Whiteson. Multi- Multi-Objective Decision Making. Synthesis Lectures on Ar- tificial Intelligence and Machine Learning. Morgan and Claypool, California, USA, 2017. Ntt:102220/S0075HHDD 7 V01Y201704AIM0344
[19] D. M. Roijers, P. Vamplew, Whiteson, and R. Dazeley. survey of multi-objectivv sequential decision-making. J. Artif. Int. Res., 48(1):67-113, Oct. 2013.
[20] D. M. Roijers, Whiteson, and F. A. Oliehoek. Computing convex coverage sets for faster multi-objective coordination. J. Artif. Intell. Res., 52:399 443,, 2015.
[21] W. Röpke, Hayes, P. Mannion, Howley, A. Nowe, and D. Roijers. Distributional multi- objective decision making, 05 2023.
[22] R. Rädulescu, Mannion, D. M. Roijers, and A. Nowé. Multi-objective multi-agent decision making: utility-based analysis and survey. Autonomous Agents and Multi-Agent Systems, 34:1-52, 2019.
[23] J. Skalse and A. Abate. On the limitations of markovian rewards to express multi-objective, risk-sensitive, and modal tasks. In Proceedings of the Thirty-Nitth Conference on Uncertainty in Artificial Intelligence, UAI '23. JMLR.org, 2023.
[24] J. Skalse, L. Hammond, C. Griffin, and A. Abate. Lexicographic multi-objective reinforcement learning. pages 3405-3411, 07 2022.
[25] B. L. Slantchev. Game theory: Preferences and expected utility. 20012.
[26] R. Subramani, M. Williams, M. Heitmann, H. Holm, C. Griffin, and J. Skalse. On the expressiv- ity of objective-specification formalisms in reinforcement learning. In Eleventh International Conference Learning Representation. 2023.
[27] R. S. Sutton and A. G. Barto. Reinforcement learning an introduction. Adaptive computation and machine learning. MIT Press, 1998.
(28) P. Vamplew, R. Dazeley, F. Barker, and A. Kelarev. Constructing stochastic mixture policies for episodic multiobjective reinforcement learning tasks. In A. Nicholson and X. Li, editors, A/ 2009: Advances in Artificial Intelligence, pages 340-349, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
[29] P. Vamplew, R. Dazeley, C. Foale, S. Firmin, and J. Mummery. Human-aligned artificial intelligence is a multiobjective problem. Ethics and Information Technology, 20, 03 2018.
[30] P. Vamplew, C. Foale, R. Dazeley, and A. Bignold. Potential-basee multiobjective reinforcement learning approaches low-impact agents for ai safety. Engineering Applications of Artificial Intelligence, 100, 04 2021.
[31] Vamplew, C. Foale, C. F. Hayes, P. Mannion, E. Howley, R. Dazeley, S. Johnson, Källström, G. Ramos, R. Radulescu, W. Röpke, and D. M. Roijers. Utility- reinforcement learning: Unifying single-objective and multi-objectivv reinforcement learning. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS '24, page 2717-2722 Richland, SC, 2024. International Foundation for Autonomous Agents and Multiagent Systems.
[32] Vamplew, B. Smith, J. Källström, G. Ramos, R. Rädulescu, D. M. Roijers, C. Hayes, F. Heintz, P. Mannion, P. J. K. Libin, R. Dazeley, and C. Foale. Scalar reward is not enough: a response to silver, singh, precup and sutton (2021). Autonomous Agents and Multi-Agent Systems, 36(2), oct 2022.
[33] K. Van Moffaert and Nowé. Multi-ohjective reinforcement learning using sets of pareto dominating policies. J. Mach. Learn. Res., 15())3383-3312, Jan. 2014.
12

---

[34] K. Wray, S. Zilberstein, and A.-i. Mouaddib. Multi-objecttvv mdps with conditional lexico- graphic reward preferences. Proceedings of the AAAI Conference Artificial Intelligence, 29, 01 2015.
[35] W. Zhao, J. P. Queralta, and T. Westerlund. Sim-to-real transfer in deep reinforcement learning for robotics: a survey. In 2020 JEEE Symposium Series on Computational Intelligence (SSCI), pages 737-744, 2020.
13

---

A
Appendix
Next, we provide the proofs of all theoretical results of An Analytical Study of Utility Functions in Multi-Ohjective Reinforcement Learning that could not in the main paper.
A.1 Last part Example 4
Example 11. Recall the utility function u(z, v) VI 1 20
As previously mentioned This environment has two possible deterministic policies. The first policy is Ti (s1) = a1, ni ($2) = 02- This policy obtains values (7= = (3.20), VTL (82) = (2, 20), and scalarised values u(V* (s1) = 4.16, u(V (82) = 3.24.
The second policy is (s()s)
a1; (822) a3. This policy obtains values V (81)
(4, 1), (== = (3, 1), and scalarised values ul (s1)) ~ 4.17, u(V (82)) 3.21.
Any stochastic policy ı will be of the form pml + (1 - p n with 2 p 2 0. That means that:
At state $1 will obtain value v= = (3p + 4(1
p). 20p 19p+1
+ (1 p)) (4 p. 19p 1).
and scalarised value u(V" (+1)) = / p) p)2 +1
20
At state 82 it will obtain value (52) = 22p++312 p). 20p + (1 - p)) = (3 - 19p + 1), and scalarised value u( (VV))))) = v +1 19p+1
20
Consider now the sealarised value of the stochastic policy as a function u' (p, s) depending on the real variable p. Its derivative is
p- a2 ut (p. VI² 22.p + a +
19
(13)
20'
where Ctsi 4, 0' 33 The derivative u' (p. 81) has root 1ı = 0.958, and the derivative ul (p, 82) has root 12 = 0.042. Both roots are global minima, and thus u' (0,s1) is global maximum for [0, 1] at state 81, and u' (1, 82) is global maximum for [0, 1] at state 82. In other words, is the absolute (u, opptimal policy, while лı is the absolute (u, 81) -optimal policy. Thus, no stochastic w-optimal policy exists.
A.2 Preliminaries for Theorems
This Section is devoted prove indispensable theorem: that search for the utility optimal policy can be reduced to searching only among stationary policies.
Lemma 4. Let M be any finite MOMDP. Then, for every policy n, there exists another stationary policy nO such that, for every state s of M, obtains the same expected returns: (7(s) V for every state s.
Proof Direct generalisation from single-objective MDPs, in which for any policy π,, there is another stationary policy n' such that for every state Sq it achieves the same value V V*((s) V (so). See Proposition 1.1. of [16] for a full proof for single-objective MDPs.
Theorem Let M be any finite MOMDP. Let u be a utility function under the SER criterion. Then:
If an (u, s)-ptimal policy w. exists for a state of M, there is at least another stationary policy n², such that v', also (u, -optimmll
If u-optimal policy n, exists for M, there is least another stationary policy x', such that nt, is also u-optimal.
Proof 5. We only cover the first case, with the second one being analogous. Let be such that ((V==)(e (s) u(V*)( for every state Then, by Lemma there exists another stationary policy n', such that v= (s) = (s)()) (s) for every state s. Thus, u(V w. (s)) = "(V" (s)) 2 ((V*(s)) and
so n/, is also u-optimal.
14

---

Notice that Theorem need not be true for utility functions under the ESR criterion.
A.3 Proof of Theorem 1
Theorem 6. Let M be a finite MOMDP. Let u be a continuous utlityy function for all value functions of all policies IIM) of M. Then, for every state of M, least one stationary {u, s) opttiill policy exists.
Proof 6. Without loss of generalisation we only consider stationary policies thanks to Theorem
Given M, consider the polytope (i.e., n-ddimensional bounded polyhedron) formed by convex coverage CCS of M state s (which has a finite amount of deterministic stationary policies as vertices) (18].
Such polytope, by definition of CCS, envelops all images of all possible value functions at state for M. Moreover, the image of any value function at state can be expressed as a convex combination of the deterministic stationary policies of CCS at that state [8].
Since a continuous function, and the polytope formed by CCS closed and bounded, by the Extreme Value Theorem there exists a maximum value vector (s) for u in the polytope.
Since for any value vector (s) in the polytope there is an associated stochastic stationary policy [18) we can find the policy т. associated with (s) that achieves the maximum value in the polytope.
Thus, there exists (u, sp-otila policy for every state of the MOMDP.
A.4 Proof of Theorem
Lemma 7. For every finite single-objective MDP M, any utility function that is strictly monotoni- cally increasing preserves the ordering between policies. That is, for every two value functions V1 and 22, for every state
(u Vi)(s) (u (s)
Vi(s) V2(5),
(14)
(u o Vi)(s) = (u (z)(()
+
Vi(s) V2(5).
(15)
In particular, any optimal policy is also u-optimal in M and vice-versa.
Proof Direct from the definition of strictly monotonic function.
Lemma 8. For every finite single-ohjective MDP M, for any affine utility function u, there exists deterministic and stationary u-optimal policy in M.
Proof Any affine function u is reresettpreeetttttive of another linear utility function I defined as l(x) = f(x) f().. For any linear utility function I, there always exists deterministic and stationary 1-optimal policy.
With these Lemmas, we can prove that there exists a family non-linear utility functions for which an u-optimal policy exists (and moreover, the policy is deterministic and stationary): utility functions product of composing an affine function together with strietly montonically increasing function.
Theorem 9.
Let M be finite multi-objectivee MDP M. Let u be utility function decomposable as u<x) = =))(x))) with g(x) : R being an affine function, and h(x) : R. -> being strictly monotonically increasing function for all value functions of all policies II(M) of M. At least one deterministic and stationary u-optimal policy exists.
Proof 9. Direct consequence of combining Lemma and Lemma
We divide the proof in two steps. First, we prove that a function decomposable in linear function and strictly monotonically increasing function has u-optimal policies:
15

---

(i) First, as Lemma states, applying strictly monotonically increasing utility function to single-objective MDP does not modify its set of deterministic and stationary optimal policies.
(ii) Second, every linear utility function lu can transform a MOMDP M into single-objective MDP .M' with the scalarised reward function luR. Of course, all optimal policies of the single-objective MDP M' are precisely the lu-optimal policies of M (for the technical proof of this see Section 2.2 of the main paper).
(iii) These two facts together tell us: given utility function f that can be decomposed into a strictly monotonically increasing function smi, and a linear function lu, then f(x) (m)()u()) will have deterministic and stationary f-optimal policies (which will be exactly the deterministic and stationary (u-optimal policies).
Next, we prove that the following two functions are quasi-repressentatie:: a function decomposable in an affine function and strictly monotonically increasing function, and another decomposable in linear function and a strictly monotonically increasing function.
(iv) Next, Lemma 8 proves that any affine utility function of is quasi-representative of another linear utility function lu. More precisely, in every MOMDP, all af-oiiimll policies are also /u-optimal policies and vice-versa for the linear utility function (u defined as lu(x) a f (xx - (O). This is because any affine function f can be decomposed as af = A A(x) b, with A(x) being linear function and b (0), constant.
(v) Now, consider utility function f(x) (x)) that can be decomposed as product a strictly monotonically increasing utility smi function and an affine utility function af. Consider also the utility function f'(x) smi(af(x) (0)). This second function f'(x) is composed by strictly monotonically increasing function and a linear function, so as previously proven in (iii), there deterministic and stationary f'-optimal policies.
(vi) Then, recall that by (ie), utility functions (x) and af(x) (0 rusesstepreeentattve (i.e., they share the same optimal policies). Thus, it is clear that smi(af( (=)) and smi(af(x) (0)) are also quasi- seuseerrpresettative, because strictly monotonically increasing functions preserve the ordering by definition.
- (0)) has deterministic and stationary f' f'ootiaaal policies, and f(z) = sm)(af(z)) and f' (z) are quasi-representtttvv,, we conclude that there also deterministic and stationary /optimal policies.
Finally, since fz( -
16

---

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: We characterised preferences that can be expressed as utility functions with Theorem 3 and characterised sufficient conditions for utility functions to have associated optimal policies with Thheorems (per state), and (for the whole MOMDP).
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
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: a fully theoretical paper, all limitations of our theoretical results are transparent by looking at their necessary conditions.
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or 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 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 in the paper. The authors should use their best 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.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: Every Theorem and Lemma has its respective proof. Each proof lists all neces- sary previous theoretical results to be proved. Every Theorem clearly states its assumptions. Every Theorem is numbered and has its respective proof inmediately below.
Guidelines:
The answer NA means that the paper does 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 proofs 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 be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
As fully theoretical paper, the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a specific model and empirical evaluation, it may be necessary to either make it 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 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, other means that appropriate to the research performed.
also be provided via detailed
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 to reproduce that algorithm.
(b) the contribution is primarily new 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 way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe 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., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
18

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
As fully theoretical paper, the paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "cipps.c/ppulli//guu /ccodedede///o ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
As fully theoretical paper, 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 a 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: As fully theoretical paper, 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, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
19

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in 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: Justification: As a fully theoretical paper, it does not include any experiment.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:p/s///aarrss.ccoooooo///aaa
Answer: [Yes]
Justification: As fully theoretical paper, it did not include human subjects or participants, there is no dataset involved, and we envision no potential harmful consequences in society of our theorems.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is 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:
As fully theoretical paper, it poses no societal impact on itself.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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.
20

---

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 as 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:
As fully theoretical paper, it poses no such risks.
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
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?
Question:
Answer: [NA]
Justification: Justification: As a fully theoretical paper, it 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.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's '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: Justification: As a fully theoretical paper, it 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/model 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Justification: As fully theoretical paper, it does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 to the NeurIPS Code Ethics, workers involved in data collection, curation, 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: As a fully theoretical paper, it does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "SGo69WUTxf", "reviewer": "Reviewer_nkkJ", "summary": "The authors studied preference relations and utility functions, which are the main components of utility-based MORL. Many prior works assumed two things: 1) for a given preference, there exists a utility that captures the preference, and 2) for a given utility, there exists an optimal policy. The authors provide several counterexamples for these assumptions and suggest sufficient conditions for each assumption to be true.", "questions": "- Is there any interpretation for how extensively the suggested sufficient conditions cover the set of desired preferences or utilities? For example, in Theorem 1, I understand that continuous utility has a <u,s>-optimal policy, but isn't this class too small to have a <u,s>-optimal policy?\n- Theorem 2 gives a sufficient condition for a deterministic stationary <u>-optimal policy. As I understand it, this condition guarantees the same property as in single-objective MDPs: the existence of a stationary deterministic optimal policy. However, in MORL, it is common for a stationary deterministic optimal policy not to exist. Is there any sufficient condition for a stationary stochastic <u>-optimal policy (even when there is no stationary deterministic optimal policy)? I guess that this result would be more helpful for MORL field.\n- In my understanding, the constructed u in the proof of Theorem 3 is discontinuous. If this is true, then even a <u,s>-optimal policy is not guaranteed to exist according to the Theorem 1.\n- (minor) In section 4, ⪰ is used for both vector preference (V(s)) and function preference (V). I guess that these need to be distinguished in notation.", "limitations": "The motivation and importance of this work are appealing. However, the sufficient conditions seem to result in a too small subclass of interest.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "-\tThe motivation of the study is important in utility-based MORL.\n-\tThe authors provided several examples to show that a representative utility and an optimal policy may not always exist. These examples help to understand the motivation of this work.", "weaknesses": "- The suggested sufficient conditions do not seem that surprising and are quite straightforward. In particular, Theorem 2 appears to depend directly on prior results for affine utility and strict monotonicity. \n- To use Theorem 3, the relation must be a total order. In this setting, the Pareto dominance relation (x⪰Py iff xi≥yi∀i and  xi>yi∃i), which is widely used in MORL, is not applicable since it is a partial order. \n- Section 3 and 4 seem misaligned. (please see question 3)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the provided suggestions and comments. \n\nWe hope that our answers will clarify the soundness of our paper. Reviewer's rating of 3 indicates “technical flaws, weak evaluation, or inadequate reproducibility”. We consider that none of them are the case in our paper. We will rewrite the unclear parts of the paper in case of acceptance to further clarify all technical doubts.\n\n** Weakness 1:\n\nYes, Theorem 2 directly depends on previously well-known results in the MORL literature, though no one has connected them yet. Notice however that while Theorem 2 provides sufficient conditions, we also provide non-trivial proofs of insufficient conditions that complement Theorem 2 results, and other two theorems in the paper that tackle completely new topics in MORL:\n\n- Theorem 1 is the first result in MORL that characterizes when a solution policy exists in MORL for a single state (despite the concept has been used experimentally since the creation of MORL).\n- Theorem 3 is the first result in MORL that characterizes when a preference relation can be represented as a utility function (despite preference relations being used since the creation of MORL).\n- Example 4 proves that strictly monotonically increasing utility functions (despite their appeal in the MORL community) do not necessarily have a solution policy for any state (<u,s>-optimal policy in our terms). We are certain that this will be a shocking result in the community that will need to think again on their focus on monotonically increasing utility functions.\n- Example 5 proves that both strictly monotonically increasing and continuously differentiable (again, some of the most popular families of utility functions in the MORL community) do not necessarily have a global solution policy (u-optimal policy in our terms).\n\nIn summary, all these results lead us to conclude that u-optimal policies are very difficult to guarantee in general, a problem that the MORL community was still not aware of.\n\n**Weakness 2:\n\nWe argue that such weakness does not hold for the following reasons:\n\n- It is right that Theorem 3 requires a total order among policies for every state s. The reviewer is also right that Pareto-dominance only imposes a partial order among policies. \n\n- But Pareto-dominance is a “solution concept” in MORL, not a utiltiy function, nor a family of functions. Roijers and Whiteson in their textbook “Multi Objective Decision Making” [16] provide a very good explanation of the difference. \n\n- This distinction is important here, because every utility function imposes a total order among policies for every state. Proof: for every state s, the scalarized value of every policy  V^{\\pi}(s) will be a scalar number. Thus, we can totally order all policies at state s.\n\nHence, Theorem 3 applies to every possible utility function (even monotonically increasing ones, whose solution lies on the Pareto front), contrarily to what was said in weakness 2.\n\n**Question 1:\n\nRegarding the extensiveness of the sufficient conditions of our Theorems. Recall that all theorems refer to finite MOMDPs, which are the most widely used kind of MOMDPs.\n \n- Then, Theorem 1 only demands the utility function to be continuous to guarantee the existence of <u,s>-optimal policies. Continuous utility functions are the most extensively known and used family of functions, including in MORL. Notice that in particular linear utility functions, widely used in MORL, are continuous.\n\n- Theorem 2, despite its apparent simplicity, already covers one of the most “desired” utility functions: linear utility functions. Again, as previously mentioned, Theorem 2 should be observed together with Example 5, which also covers families of desired utility functions (monotonic ones) but providing negative results for them.\n\n- Finally, as previously explained, Theorem 3 applies to every utility function. It does not apply to every possible preference relation, but our conditions copy standard conditions in game theory, which we consider to be representative enough.\n\n** Question 2:\n\nFinding deterministic and stationary solution policies is very relevant and a major research topic for  MORL research. Following Roijers and Whiteson’s classification of MORL solution concepts in [16], half of them involve the computation of deterministic and stationary policies, which our Theorem 2 directly addresses.\n\nRegarding the reviewer’s concern about expanding our result to stochastic policies: This is future work for us. We have tried to find such kind of families, but so far, we have only found negative results (e.g., Example 5) that greatly reduce the space of viable policies for which a stochastic u-optimal policy would always exist. However, we consider that these negative results will also be helpful for the MORL community.\n\n\n** Question 3:\n\nWhile Theorem 1 and 3 are related results, they do not directly affect each other. Probably this was not clear enough on our part.\n \n- The constructive proof of Theorem 3 provides a discontinuous utility function. Theorem 1 guarantees that any continuous utility function will have a <u,s>-optimal policy, but does not deny that some discontinuous optimal policies may have a <u,s>-optimal policy. \n\n- Notice that having a <u,s>-optimal policy for some state s means that there is a maximum element among scalarized values of policies at state s. The utility function of Theorem 3 is specifically constructed to always have a maximum element for each state, thus guaranteeing the existence of <u,s>-optimal policies by definition. \n\n- In summary, the reviewer's inference does not hold: even though the utility function of the proof of Theorem 3 discontinuous, it is guaranteed to have a <u,s>-optimal policy.\n\n\n**Question 4:\n\nWe agree with the reviewer that this was an abuse of notation from our part. We will correct it in case of acceptance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cb80DyF22K", "reviewer": "Reviewer_WWNq", "summary": "This paper studies the expressiveness of utility functions in multi-objective reinforcement learning (MORL). In MORL, the reward function of the MDP is a vector of multiple (possibly) conflicting reward functions, and the goal of an agent is to maximize a given utility function (function mapping the vector value function to a scalar) that expresses the preferences of a user. In particular, the paper studies two problems within MORL: (i) which utility functions are guaranteed to have an associated optimal policy? (ii) whch user preferences can be expressed via some utility function? The paper shows that, for (i), a continuous utility function is enough for optimality in a given state, and utility functions decomposable as a combination of an affine and a strictly monotonically increasing function is enough for optimality in all states. Regarding (ii), the authors show that for quasi-representative preference relations that satisfy a few conditions (e.g., completeness, transitivity), a quasi-representative utility function always exists that expresses the given preference.", "questions": "In general, the paper introduces a few interesting and potentially useful theoretical results for MORL. However, the paper lacks a more in-depth discussion of how these results can be applied to design novel algorithms. This, combined with the fact that the ideas are not discussed in light of many previous results, makes the paper not yet ready for publication.\nBelow, I have a few questions and constructive feedback to the authors:\n\n1) My main concern is that the paper does not have a related work section and does not discuss many relevant related works. For instance:\n\n[1] showed how to construct stochastic policies that are optimal w.r.t. the initial state distribution.\n\n[2] introduced different solution sets that extend the definition of the Pareto front and can express more utility functions.\n\n[3] and [4] showed that many multi-objective utility functions can not be expressed via Markov rewards.\n\n[5] discusses the expressivity of many RL formalisms to represent different preferences, including MORL.\n\n2) Regarding the examples, e.g., Example 3, it would be much clearer and easy to read if the authors provided an image of the MDP as graph.\n\n3) Theorem 1 seems to be a more formal definition of the result in Vamplew et al. 2009 [1].\n\n4) Proof of Theorem 2 looks incomplete. Lemmas 7 and 8 consider single-objective MDPs, not MOMDPs. It is not clear how they can be combined to prove Theorem 2.\n\n5) Theorem 2 shows one class of non-linear utility functions that have a deterministic stationary optimal policy. However, is it possible that a more general class exists? I would suggest adding this discussion.\n\nMinor:\n- Use large brackets, e..g., in Equation 1, the bracket is smaller than the summation symbol.\n- In definition 3, the transition function is $\\mathcal{T}$ instead of $T$. Please be consistent.\n\n[1] Vamplew, P., Dazeley, R., Barker, E., and Kelarev, A. (2009). Constructing stochastic mixture policies for episodic multiobjective reinforcement learning tasks. In AI 2009: Advances in Artificial Intelligence.\n\n[2] Röpke, W., Hayes, C. F., Mannion, P., Howley, E., Nowé, A., and Roijers, D. M. (2023). Dis-\ntributional multi-objective decision making. In Elkind, E., editor, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23.\n\n[3] Skalse, J. and Abate, A. (2023). On the limitations of Markovian rewards to express multi-objective, risk-sensitive, and modal tasks. In Evans, R. J. and Shpitser, I., editors, Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence.\n\n[4] Miura, S. (2022). On the expressivity of multidimensional markov reward. In Proceedings of the\nConference on Reinforcement Learning and Decision Making.\n\n[5] Subramani, R., Williams, M., Heitmann, M., Holm, H., Griffin, C., & Skalse, J. (2023). On The Expressivity of Objective-Specification Formalisms in Reinforcement Learning. ICLR 2024.", "limitations": "The results have some limitations that should be addressed (see Questions above). The paper has no potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem studied in this paper is very relevant to the MORL community.\n- The paper is written clearly and the results are easy to follow. The authors present examples that make it easier to understand the introduced theorems.\n- The distinguishment between “preferences” and “utility functions” is, to the best of my knowledge, a novel perspective that can help the study of MORL under non-linear preferences.", "weaknesses": "- The main weakness of the paper is that it does not do a good job in discussing previous theoretical works in MORL and comparing/discussing its findings with the related literature (see below).\n- A few introduced results are not entirely novel but phrased differently than in previous works. For instance, that a stationary deterministic optimal policy may not exist for non-linear utility functions is a known result (Example 3).\n- Although the paper showed sufficient conditions for preferences being possible to express in terms of utility functions, it does not discuss how the results could be used to create or solve such utility functions in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insights and suggestions.\n\n**Weakness 2:\n\nYes, Example 3 illustrates a well-known fact in the MORL literature. In case of acceptance, we will state it. However, we wanted to include it before showing Example 4, which builds on Example 3 by providing an example of both strictly monotonically increasing and continuously differentiable function for which no u-optimal policy exists, a completely novel result.\n\n**Weakness 3:\n\nWe accept it, but we believe the topic of classifying the conditions for the existence of solutions, due to its novelty in the MORL community, deserved the entire paper (in fact, we had to struggle to fit in all the main results). Solving MORL problems is out of the scope of this paper.\n\n**Question 1:\n\nWhile the recommended papers tackle relevant MORL problems, papers [1, 2, 4, 5] aim to solve a different problem than ours. Paper [3] is the most similar to ours, but they make no distinction between <u,s>-optimal and <u>-optimal policies. This is a major difference that we will discuss in the following paragraphs.\n\nNevertheless, we do agree with the reviewer that our paper would benefit from an expanded related work section, which is currently compressed in Section 2 due to space limitations. We will include comments explaining the similarities and differences to these 5 papers upon acceptance.\n\nLet us clarify how these papers relate to ours:\n\n- Papers [1] and [2] tackle a different problem: they focus on creating novel solution concepts in MORL and methods to solve them. Instead, we focus on characterising for which families of utility functions this solution exists. In [1], they present a method for computing the Pareto front (PF) from a given state. They implicitly assume that the PF will include the <u,s>-optimal policy, but our Example 5 proves that this is not always the case.\n\n- Paper [4] tackles a complementary, though also different, problem to ours. They define preferences as sets of “acceptable policies' ' and aim to find for which environments they can set the constraints and reward functions of a constrained MDP (CMDP) for which the acceptable policies are optimal. CMDPs and MOMDPs are similar but separate research areas, being the major difference that a MOMDP does not have constraints, but a scalarization function.\n\n- Paper [3], which we were not aware of, slightly overlaps with ours. Their theoretical results complement ours by stating that, for every “objective” (preorder between policies), a <u>-optimal policy exists if and only if this objective can be represented with a linear utility function. This aligns with our results with Theorem 2. However, they do not establish whether there may be more families of utility functions for which a u-optimal policy exists, as we do with Theorem 2. Moreover, our “preference” definition allows for ordering policies in each state of the environment, providing more granularity than their “objective” definition. This difference is also significant, because it allows us to identify issues in the solution concepts of MORL as we have tried to illustrate with our examples. As a side note, we see their Corollary 2 reaches the same conclusion as us in Example 8. We will rewrite Example 8 to recognise their work.\n\n- Finally, Paper [5] follows on [3], but tackles a different problem than us. They compare the expressivity of the MORL framework with other frameworks. They aim to know which objectives can be represented on each framework. But here we tackle a different problem: we focus strictly on MOMDPs, and aim to clarify for which utility functions it makes sense to compute a u-optimal policy. Moreover, like [3], their “objective” definition does not allow them to order policies differently per state, unlike our “preference” definition.\n\n**Question 2:\n\nDue to page limitations we were not able to include figures. In case of acceptance, we will try to fit as many supporting figures to the examples as we can.\n\n**Question 3:\n\nNo, Theorem 1 is not a more formal definition of the result in [1]. These are unrelated results. While [1] provides a method for computing <u,s>-optimal policies for monotonically increasing utility functions, we prove that a <u,s>-optimal policy always exists for any continuous utility function.\n\nVamplew et al. proved that a Pareto front can be constructed from the deterministic policies of a convex coverage set (CCS). In our terms, they state that the <u,s>-optimal policy (if it exists) of any monotonically increasing utility function can be computed by first computing a CCS for state s.\n\nMeanwhile, our Theorem 1 states that for any continuous utility function, there exists a <u,s>-optimal policy. Our proof relies on the fact that all possible value vectors (at a given state) are contained in the CCS. Notice that our Example 5 is a counter-example to the methodology of [1]. Following their methodology we would not have found any <u,s>-optimal policy for the utility function of Example 5, because no <u,s>-optimal policy exists for it. This example remarks the importance of formalising <u,s>-optimal policies.\n\n**Question 4:\n\nSorry for the typo. Lemma 8 should read “For every finite multi-objective MDP, […]”. We hope that now this is clearer.\n\n**Question 5:\n\nIndeed, this is a very interesting question! We hope to study this problem in future work, because we can think of example utility functions that do not satisfy Theorem 2 conditions while also having a u-optimal policy in some MOMDPs. The theoretical implications of Example 4 make it difficult finding more families of utility functions for which a u-optimal policy always exists. We know that if another family of optimally solvable utility functions exists, they need to satisfy the Bellman optimality equation. Finding this alternative family of utility functions would be an impactful contribution to the MORL community.\n\n**Minor questions:\n\nIn case of acceptance we will make sure of correcting all typos.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5FT7WsGi8o", "reviewer": "Reviewer_59cy", "summary": "The paper considers the problem of multi-objective RL and performs a rigorous theoretical analysis on the space of optimal policies as a function of the utility functions and preferences. Specifically, in teh case of utility optimal policies, it considers two types of optimality - at the state level and at all states level. The key contribution in this sub-task of utility optimality lies in demonstrating that the more common utility function conditions such as monotonicity, differentiability and strictly montonically increasing and continuously differentiable are all insufficient to guarantee optimality. Simple counterexamples are provided for each of these cases to prove their insuffiency. \n\nGiven these observations, a signficiant contribution of the paper is in the identification of the conditions under which utility optimal policies exist for all states. Specifically, the paper identifies that a decomposable utility function of the form h(g(x)) where g is an affine function (linear with a constant) is one such condition under which the u-optimal policy exists. The second key contribution of the paper lies in teh fact that it considers user preferences, and identifies quasi-representative preference relations allows us to identify u-optimality.", "questions": "Please see the weakness part. I specifically would like to understannd the sufficiency and completeness of these conditions and if possible a discussion of the situations where these are both practical or common.", "limitations": "There are no significant potential societal negative impacts.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ The paper is written well. It idenfies the problems clearly, motivates them well and provides simple counterexamples. \n\n+ The problem addressed in this paper is an important one, that of deeply understanding multiobjective RL. It is probably the most natural setting inside RL and not enough attention is being given to this challenging task. So from that perspective, this is a very interesting read. I thank the authors for carefully constructing the problem and clearly explaning the challenges and then present their observations. \n\n+ The two observations of decomposable utility (with affine functions) and the quasi-representative preferences are quite important.", "weaknesses": "- While the paper is written well and the problems are motivated well, I would have liked to see a specific discussion on the types of settings/problems where such situations are plausible/common. For example, where would one observe this decomposable affine functions or quasi-representative preferences in real-world? It would be nice to see a section with some real examples to make this paper's analyses clearer.\n\n- While I understand that the having a decomposable utility (with affine functions) can result in u-optimality, what is unclear is that are they sufficent or complete conditions? \n\n- Same issue with the quasi-representative preferences. While they themselves can be complete and transitive, is the condition of quasi-representativeness sufficient for optimality? If so, can you expand how?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, suggestions, and feedback. We appreciate that the reviewer agrees with us in the need for addressing in more depth the theoretical aspects of multi-objective reinforcement learning.\n\nWe proceed to answer the questions:\n\n**Question 1: \n\nRegarding the types of problems that we address and their link to real-world problems. We cannot enter into much detail here, but linear utility functions (a particular kind of affine functions) represent a large majority of utility functions in real-world applications (due to their simplicity and well-known properties). To give one recent example,  Rodriguez-Soto et al. in \"Multi-objective reinforcement learning for designing ethical multi-agent environments\" (2023) showed an example gathering scenario in which agents needed to face lexicographically two objectives (one individual related to how much the agent can gather for itself, and another one ethical, related to how much it helps the community), and provided a linear utility function that was able to reach lexicographic solutions (i.e., agents learned to prioritise the ethical objective over the individual one).\n\nWe will also mention in our camera-ready version some of the practical examples of utility functions in the most recent MORL surveys, such as Hayes et al. \"A practical guide to multi‑objective reinforcement learning and planning\" (2022). These examples tackle problems route planning, water management, and wind farm control.\n\nInterestingly, another large body of work in MORL has tackled the problem of assuming an unknown utility function and trying to compute a solution set general enough to at least include a solution to this unknown function. This may lead to unexpected problems, as we have tried to show in this paper, in which we put the focus back into the utility functions themselves.\n\nRegarding preferences for which a quasi-representative utility function exists. As mentioned in the paper, the first two conditions of our Theorem 3 (Completeness and transitivity) are very common conditions for preference relations in game theory, so we expect it to cover the majority of most used preference relations. The third condition of Theorem 3 (that a maximal element exists per state) is virtually assumed by the whole MORL community since the goal is to always maximise the utility function (implicitly assuming that there exists a maximal element).\n\nIn fact, it is difficult for us to even think of an example preference relation for which a quasi-representative utility function would exist without satisfying the conditions of Theorem 3. And recall from our definition that if the utility function is not quasi-representative of the preference relation, then maximising the utility would lead to not maximising the preference relation.\n\n \n**Question 2: \n\nWe apologise if Theorem 2 was not clear enough. The conditions of Theorem 2 are only sufficient conditions, but not necessary. As a quick example, notice that for any single-state MOMDP, any <u,s>-optimal policy of this single state is also by definition a <u>-optimal policy.  Theorem 1 proves that we only need continuity to reach a <u,s>-optimal state (much more relaxed condition than being affine).\nIn future work we expect to further study the necessary conditions for a <u>-optimal policy to exist in general MOMDPs.\n\n\n**Question 3: \n\nWe hope that we are understanding the reviewer properly on this question, if not, we will correct our answer in the reviewer-author discussion.\n\nAgain, we apologise if Theorem 3 was not clear enough. Theorem 3 only provides the sufficient conditions that a preference relation needs to meet to guarantee that an associated quasi-representative utility function exists.\n\nHowever, the reviewer is right on their intuition: it is sufficient for a utility function to be quasi-representative of a preference relation in a given MOMDP to guarantee that a <u,s>-optimal policy exists for every state of the MOMDP. We did not have space in the final paper to include this result.\n\nIt is easy to prove: Theorem 3 requires the preference relation to have at least one maximal element (policy) per state. Then, if the utility function is quasi-representative of this specific preference relation, we require it to be the maximum element (policy) per state. In other words, we require it to have a <u,s>-optimal policy per state.\n\nAgain, the necessary conditions for both issues here are future work that we are eager to tackle.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates preference relations and utility functions—critical components of utility-based multiobjective RL (MORL) methods. In particular, the authors presented several counterexamples for key assumptions made in previous works and discussed sufficient conditions for each assumption to hold. They also provided several examples to show that a representative utility function and an optimal policy may not always exist. 

Reviewer nkkJ raised a few concerns, including, e.g., that Thm. 2 appears to directly depend on/extend well-known results in the MORL literature. The authors responded by pointing out that while this is true, up to this point, no one had made the connections presented in this paper. They also argued that while Thm. 2, on its own, does provide sufficient conditions, the current paper *additionally* provides non-trivial proofs of *insufficient* conditions that complement this theorem. They also argued that Thm. 1 is the first result of its type in the MORL literature. Post-rebuttal, nkkJ increased their recommendation. Overall, I agree with the authors' point of view in this case: a borderline reject vote (nkkJ's recommendation) often suggests that the paper may have technical flaws, weak evaluation, or inadequate reproducibility. I do not believe this is the case. I believe (and other reviewers share this opinion) that the examples provided in this work may give valuable insights to the MORL community.

Reviewer WWNq brought up a few other concerns, some similar to those nkkJ mentioned; e.g., that some results presented in this paper are only partially novel. As an example, it is well-known that a stationary deterministic optimal policy may not exist under non-linear utility functions. This reviewer's main concern is that the paper did not have a related work section and did not adequately discuss many relevant related works. Regarding this point, WWNq listed five papers that present theoretical findings similar to those discussed in this work. After a fruitful discussion with the authors, the reviewer chose to increase their score since "(...) the theoretical results in the paper can be potentially useful to other researchers in the field". Finally, reviewer 59cy mentioned a few potential limitations of this work but was overall satisfied with the paper's contributions and the authors' responses.

Although the consensus among the reviewers is that the ideas presented in this work are not entirely novel, it is clear that the authors successfully made important connections that had yet to be clearly discussed in the literature. Papers of this type are a valuable resource to the scientific community since they help consolidate in a centralized way a series of key insights that are meaningful and helpful to other researchers in the field. For this reason, I believe that the NeurIPS community may benefit from the discussion and insights presented in this work. The reviewers strongly encouraged the authors to address the concerns and suggestions that were brought up during the discussion phase.
Decision: Accept (poster)