An Analytical Study of Utility Functions in Multi-Objective Reinforcement Learning

Authors: manel  rodriguez-soto
juan a rodriguez-aguilar
maite  lopez-sanchez
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:51:11

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.

Main paper: 
 introduction: 
 Sequential decision-making problems are ubiquitous, impacting areas like autonomous driving [6] , robotics [35] , finance [3] and healthcare [4] , to name a few. Recently, Reinforcement Learning (RL) has emerged as a pivotal framework for addressing sequential decision-making tasks [11, 13] . 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 a race). However, real-world scenarios often present multiple, conflicting objectives [32] (e.g., a 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 [19, 18, 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 utilitybased and assume that there exists a utility function [10] that combines all objectives into a single one, allowing the learning agent to 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-maker can directly select the policy from the undominated set that maximises it. Thus, utility functions are widely considered a fundamental concept of MORL [31] . Utility functions capture a user's preferences over different objectives and drive the learning [22] . Hence, both concepts (utilities and preferences) are at the core of state-of-the-art MORL. 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: It assumes that for every utility function, there exists a policy optimising it. 2. On preferences: It assumes that any user preference can be expressed as a 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 [34] , 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-representative utility function, which preserves the most preferred policies as its maximal points.We expect that our theoretical results will lead to novel MORL algorithms that can 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-maximising policies. Next Section 4 characterises the family of preferences that can be represented with utility functions. Thereafter, Section 5 presents the related work. Finally, Section 6 summarises our main theoretical findings and sets paths for future research.2 Background 
single-objective reinforcement learning: 
 In single-objective reinforcement learning (RL), sequential decision-making problems are formalised as Markov decision process (MDP) [11, 27] . An MDP represents an environment in which an agent is capable of repeatedly acting upon it to make it to transition it to a different state, and immediately receive a scalar reward (representing the agent's objective) after each action: Definition 1 (Markov Decision Process). A (single-objective) 1 Markov Decision Process (MDP) is defined as a tuple ⟨S, A, R, T ⟩ 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 R : S × A × S → R, and the transition function T : S × A × S → [0, 1] specifying the probability T (s, a, s ′ ) = P(s ′ | s, a) that the next state is s ′ if an action a is performed upon the state s.An agent's behaviour in an MDP is called a policy π. A policy π(s, a) describes how likely an agent will perform action a if the agent is currently in state s. The agent's objective is to learn the policy that accumulates the maximum sum of discounted rewards. Thus, to evaluate a given policy, we need to compute the (expected) discounted sum of rewards that an agent obtains by following it. This operation is formalised by means the so-called value function V : S → R, defined as:EQUATIONwhere γ ∈ [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 2 (Optimal policy). Given an MDP M, its optimal policy π * is the policy that maximises the value function V π . Formally:EQUATIONfor every state s of the MDP M, and every policy π of M.The optimal policy is the solution concept in single-objective RL. For any MDP with a finite state and action space, at least one optimal policy exists, which is also deterministic and stationary [7] .Multi-objective reinforcement learning (MORL) deals with environments in which an agent pursues multiple objectives simultaneously (for example, in a healthcare context, the health and the autonomy of a patient). Recall that in single-objective RL, the reward function represents the agent's objective. Thus, MORL considers environments with multiple reward functions, called Multi-Objective Markov Decision Processes [19, 10] . Formally: Definition 3 (Multi-Objective MDP). An n-objective Markov Decision Process (MOMDP) is defined as a tuple ⟨S, A, ⃗ R, T ⟩ where S, A and T are the same as in an MDP, and ⃗ R : S × A × S → R n is a vector of reward functions, providing a reward function R i for each objective i ∈ {1, . . . , n}.Policies in a MOMDP are evaluated by means of a value function vector ⃗ V , defined as the vector of all value functions per objective ⃗ V (s) = (V 1 (s), . . . , V n (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 a single function. That way, the agent's goal becomes to maximise this aggregated value function.This aggregation is performed by means of a utility function u (also called a scalarisation function) [18, 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 R n ) to the real space R. With u, the agent's goal can be expressed as learning a policy that maximises the function The family of linear utility functions is especially notable. Any linear utility function l returns a weighted sum of value functions (l(u • ⃗ V )(s) = u( ⃗ V (s)).• ⃗ V )(s) = ⃗ w • ⃗ V (s).For linear utility functions, the scalarised problem of maximising l • ⃗ V can be solved with single-objective reinforcement learning algorithms 3 .While in single-objective RL there is a clear definition of the solution concept (a deterministic and stationary optimal policy), there is no equivalent for MORL. Instead, the utility function is typically assumed to be unknown, and that we only have minor assumptions about it (e.g., that it is linear or that it is monotonically increasing) [19, 22, 10] . With that in mind, the solution concept in MORL is to learn a set of candidate policies π, with each of them optimising a possible utility function u. The next Section explores typical solution concepts in MORL. 2 The presented definition of the utility function follows the Scalarised Expected Returns (SER) criterion, which is by far the most popular one in the MORL literature [10] . We focus exclusively on the SER criterion. 3 Because the linear utility function for ⃗ V also induces a utility function for ⃗ R.Notice that u( ⃗ V (s)) = ⃗ w • ⃗ V (s) = ⃗ w • E[ ∞ t=0 γ k ⃗ R t+k+1 | s] = E[ ∞ t=0 γ k ⃗ w • ⃗ R t+k+1 | s].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 to remark what it means for a policy to be maximal for a utility function. By far, the majority of the MORL community follow the so-called state-independent (SI) criterion to define optimality [19, 18, 22, 10] . Given a MOMDP, this criterion considers that a policy π * 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 S 0 ). We denote this expectation with ⃗ V SI :⃗ V π SI . = E[ ⃗ V π (S 0 )].(3) 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 RL, it can generate contradictory policies in multi-objective RL, as we will show in Example 4 below.Considering this state-independent criterion, all solution concepts for MOMDPs have been formalised exclusively for it. Thus, the state-of-the-art 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 a MOMDP M, its undominated set U (M) is defined as the set of policies for which there exists a utility function u with a maximal scalarised value.EQUATION) where Π(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 it to 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 π * that are optimal for some weight vector ⃗ w:EQUATIONwhere Π(M) is the set of policies of M.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: As 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 no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
utility optimal policies: 
 Recall that the MORL literature defines solution concepts following the state-independent criterion. However, for a proper analysis of utility functions in 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 fixed point theorem, we know that a deterministic and stationary optimal policy always exists for any finite MDP (and, thus, for every state) [7] . These theoretical properties become much weaker in multi-objective 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 a single-state level (i.e., considering a 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 a given utility function u if and only if it obtains more scalarised discounted returns than any other policy at s. Formally: Definition 7 (utility optimal policy at a state). Let M be a MOMDP with state set S. Let Π M be the set of policies of M. Let u be a utility function. Then, a policy π * ∈ Π M is optimal with respect to utility function u at state s ∈ S if and only if:EQUATIONfor every policy π ∈ Π M . We say that π * is ⟨u, s⟩-optimal for short.Example 1. Consider a MOMDP M with two states: an initial state s 1 and a terminal state s 2 .An agent can perform two actions (a 1 , a 2 ) in this environment, with rewards ⃗ R(s 1 , a 1 ) = (1, 0), ⃗ R(s 1 , a 2 ) = (0, 1) respectively. Consider the utility function u(x, y) = x+sin(y). The deterministic policy π(s 1 ) = a 1 that obtains vectorial value ⃗ V π (s 1 ) = (1, 0) is clearly ⟨u, s 1 ⟩-optimal since sin(y) < y for any y ∈ [0, 1].In the same vein as in single-objective RL, given a MOMDP, we define 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 a MOMDP with state set S. Let Π M be the set of policies of M. Let u be a utility function. Then, a policy π * ∈ Π M is optimal with respect to utility function u if and only if:EQUATIONfor every policy π ∈ Π M , and every state s ∈ S. We say that π * is u-optimal for short.Example 2. In the MOMDP in Example 1, policy π(s 1 ) = a 1 is 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 [18, 10] . Example 3 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⟩-optimal policy for any given state s. 3. That the utility function is both strictly monotonically increasing and continuously differentiable. Example 4 shows how even assuming both conditions there are utility functions without stochastic u-optimal policies.In the following Example 3 we consider the Chebyshev function (also called Tchebycheff, a wellknown utility function in MORL [17, 19, 18, 10] . The Chebyshev function returns more scalar value the nearest a given input value x is to a reference value ⃗ r. Moreover, the Chebyshev function is also monotonically increasing [18] . Example 3. Let ϵ > 0 be a small real number, ⃗ r ∈ R n a reference value, and ⃗ w ∈ R n a weight vector such that each w i ≥ 0. The Chebyshev function ψ ⃗ r,ϵ,w : R n → R is defined as [17] :EQUATIONLet M be a 2-objective deterministic MDP with three states s 1 , s 2 , and s 3 such that s 3 is the terminal state. Regarding actions, there is one possible action in s 1 , which has associated rewards ⃗ R(s 1 , a 1 ) = (1, 0). Action a 1 transitions the state to s 2 . Then, in state s 2 , there are two possible actions with associated rewards ⃗ R(s 2 , a 2 ) = (2, 20) and ⃗ R(s 2 , a 3 ) = (3, 1). All actions in s 2 transition to terminal state s 3 . This environment has two possible deterministic policies. The first policy is π1 (s 1 ) = a 1 , π 1 (s 2 ) = a 2 . This policy obtains values ⃗ V π1 (s 1 ) = (3, 20), ⃗ V π1 (s 2 ) = (2, 20). The second policy is π 2 (s 1 ) = a 1 , π 2 (s 2 ) = a 3 . This policy obtains values ⃗ V π2 (s 1 ) = (4, 1), ⃗ V π2 (s 2 ) = (3, 1). We select as reference point ⃗ r = (3.5, 20) , associated weights ⃗ w = (1, 1/19), and ϵ = 0. For this configuration we have: for policy π1 , ψ( ⃗ V π1 (s 1 )) = -0.5, ψ( ⃗ V π1 (s 2 )) = -1.5. For policy π 2 , ψ( ⃗ V π2 (s 1 )) = ψ( ⃗ V π2 (s 2 )) = -1.Clearly, π 1 is the only deterministic ⟨ψ, s 1 ⟩-optimal policy, while π 2 is the only deterministic ⟨ψ, s 2 ⟩-optimal policy. Thus, no deterministic ψ-optimal policy exists.Example 3 showed that deterministic u-optimal policies do not necessarily exist in finite MOMDPs, a fact that was already known in the MORL literature [18] . But we can go one step further: the 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, y) = √ x 2 + 1 + y 20 , which is strictly monotonically increasing for any (x, y) ∈ R + × R, and continuously differentiable in R 2 . Let M be the same 2-objective deterministic MDP from Example 3. This environment has the same two deterministic policies from Example 3. The first policy isπ 1 (s 1 ) = a 1 , π 1 (s 2 ) = a 2 , which obtains scalarised values u( ⃗ V π1 (s 1 )) ≈ 4.16, u( ⃗ V π1 (s 2 )) ≈ 3.24. The second policy is π 2 (s 1 ) = a 1 , π 2 (s 2 ) = a 3 , which obtains scalarised values u( ⃗ V π2 (s 1 )) ≈ 4.17, u( ⃗ V π2 (s 2 )) ≈ 3.21.It is easy to check that π 1 is the absolute ⟨u, s 2 ⟩-optimal policy, while π 2 is the absolute ⟨u, s 1 ⟩optimal policy. We leave the details at Appendix A.1. Thus, no stochastic u-optimal policy exists.Our third example is a finite MOMDP and a strictly monotonically increasing utility function u for which no stochastic ⟨u, s⟩-optimal policy exists for any state s. Example 5. Consider the utility function u such that if x = y, then u(x, x) = 0, and otherwise u(x, y) = 1 |x-y| . Let M be the 2-objective deterministic MDP from Example 1 with two states s 1 and s 2 such that s 1 is the initial state and s 2 is the terminal state. There are two possible actions ins 1 with associated rewards ⃗ R(s 1 , a 1 ) = (1, 0) and ⃗ R(s 1 , a 2 ) = (0, 1).Every policy of M will be of the form π(s 1 , a 1 ) = p and π(s 1 , a 2 ) = 1 -p for some p ∈ [0, 1]. The vectorial value of such policy at state s 1 will be ⃗ V π (s 1 ) = (p, 1 -p). Notice how every possible value belongs to the Pareto Front of M. Thus, any utility function is strictly monotonically increasing in M, including the one defined in this example.In particular, for any policy, its scalarised value will be u(1, 1 -p) = 1 |2p-1| . If for any policy π we have π(s 1 , a 1 ) = p < 1 2 , then the policy π ′ such that π(s 1 , a 1 ) = p + ϵ, with ϵ > 0 small enough so that p + ϵ < 1 2 obtains more scalarised value than π. Similarly, if π(s 1 , a 1 ) = p > 1 2 , we can find an alternative policy π ′ such that π(s 1 , a 1 ) = p -ϵ that obtains more scalarised value than π. Thus, no ⟨u, s 1 ⟩-optimal policy exists in this MOMDP.The result of Example 5 is specially significant because most MORL literature (with its stateindependent criterion that only considers initial states S 0 ), focuses on computing ⟨u, S 0 ⟩-optimal 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 at least one utility optimal policy for every state. In particular, we focus on stationary policies, like in single-objective RL. Formally: Problem 1. For which families of utility functions is guaranteed that a stationary ⟨u, s⟩-optimal policy will exist for every state s of every possible finite MOMDP? Problem 2. For which families of utility functions is guaranteed that a stationary u-optimal policy will exist for every possible finite MOMDP?Next, Sections 3.1 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.This Section introduces a family of utility functions that solve Problem 1. In particular, we offer a sufficient condition to guarantee the existence of a stationary ⟨u, s⟩-optimal policy for every state s of a 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 Π(M) of M. Then, for every state s of M, at least one stationary ⟨u, s⟩-optimal policy exists. Proof 1. See Appendix A.3.Continuous utility functions are one the most extensively studied and applied family of functions due to their well-behaved properties (e.g., existence of absolute maximum and minimum). Nevertheless, recall that Theorem 1 only provides sufficient conditions, and thus there might exist ⟨u, s⟩-optimal policies for discontinuous utility functions. We offer such an example in the proof of Theorem 3.Demanding that the same policy is u-optimal for some utility function u for every state of the MOMDP is a much harder problem than demanding it for a 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 4).It is already known that, for linear utility functions, we can obtain a u-optimal policy. So, the question is if we can find at least another family of utility functions for which a u-optimal policy exists. Theorem 2 presents such a family: utility functions that result from composing an affine function together with a strictly monotonically increasing function. Formally: Theorem 2. Let M be a finite multi-objective MDP M. Let u be a utility function decomposable as u(x) = h(g(x)), with g(x) : R n → R being an affine function, and h(x) : R → R being a strictly monotonically increasing function for all value functions of all policies Π(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 [18, 10] . To finish this Section, we show an example of a function composed by an affine and a strictly monotonically increasing function (that hence satisfies Theorem 2) that produces a non-linear (and non-affine) utility function for which a u-optimal policy exists. We decompose u(x, y) as u(x, y) = h(g(x, y)) with g(x, y) = x + y + 3 being affine, and h(x) = -1 x+sin(x) being strictly monotonically increasing. By Theorem 2, a u-optimal policy exists.Notice that Theorem 2 only provides sufficient conditions of utility functions u for guaranteeing the existence of u-optimal policies. In fact, Example 2 shows a non-affine utility function for which an u-optimal policy exists in a particular MOMDP.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Justification: As a 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 a 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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, a more fundamental question remains unanswered: Which user's preferences can be expressed as utility functions in a given MOMDP?We require formalising preference relations and their maximal elements in MOMDPs to answer this last question. Preference relations, also known as binary relations, allow us to express, among two elements of a set, which one we prefer [25, 14] . While the state of the art in 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] :Definition 9 (Preference relation in a MOMDP). Let M be a MOMDP of n objectives. We define a preference relation in M as any binary relation ⪰ over at least one pair of value vectors of R n . In particular, we say that:• a value function ⃗ V 1 ∈ V is weakly preferred to another value function ⃗ V 2 ∈ V if and only if ⃗ V 1 (s) ⪰ ⃗ V 2 (s) for every state s of M. In short, we denote ⃗ V 1 ⪰ M ⃗ V 2 . • a value function ⃗ V 1 ∈ V is strictly preferred to another value function ⃗ V 2 ∈ V if and only if ⃗ V 1 (s) ⪰ ⃗ V 2 (s) for every state s of M and not ⃗ V 2 (s ′ ) ⪰ ⃗ V 1 (s ′ ) for at least one state s ′ of M. In short, we denote ⃗ V 1 ≻ M ⃗ V 2 .If for two value vectors we have that ⃗V 1 (s) ⪰ ⃗ V 2 (s) and ⃗ V 2 ⪰ ⃗ V 1 (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 ⪰. Formally: Definition 10 (Representative utility function). Let M be a MOMDP, and let ⪰ be a preference relation in M. Then, we define a utility function u as representative of the preference relation ⪰ if and only if, for every pair of possible value functions ⃗ V 1 , ⃗ V 2 , and every state s of M:EQUATIONSome (but not all) preference relations have representative utility functions. However, any utility function u, is representative of some preference relation ⪰ u defined as exactly fulfilling Equation 10.In order theory, for any quasi-order (i.e., a 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 a 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. Let ⪰ be a preference relation in M that is at least reflexive and transitive (a quasi-order). Then, the value vector ⃗ V * (s) of value function ⃗ V * is a maximal element in state s if and only if for every other possible value function ⃗ V of M:EQUATIONExample 7. In finite single-objective MDPs, the optimal value V * (s) is a maximal element for every state s, for the preference relation ⪰ defined asV (s) ⪰ V ′ (s) ⇐⇒ V (s) ≥ V ′ (s).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 [8, 29, 12, 30, 24] , almost no work in 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 utility functions in general, we refer to Corollary 2 of [23] .Example 8. Consider a MOMDP M with two states: an initial state s 1 and a terminal state s 2 . An agent can perform three actions in this environment (a 1 , a 2 , a 3 ), with rewards ⃗ R(s 1 , a 1 ) = (1, 0), ⃗ R(s 1 , a 2 ) = (0, 1), and ⃗ R(s 1 , a 3 ) = (1, 1), respectively. Consider now the lexicographic order ⪰ such that objective 1 is always preferred to objective 2. Hence, ⃗ R(s 1 , a 3 ) ≻ ⃗ R(s 1 , a 1 ) ≻ ⃗ R(s 1 , a 2 ). Any linear utility function here will be of the form u α,β (x, y) = α • x + β • y. For u w to represent ≻, it must satisfy u α,β (1, 1) > u α,β (1, 0) and u α,β (1, 0) > u α,β (0, 1), for example, u 10,1 (x, y) = 10x + y.However, policies can be stochastic, and thus, we can have for instance any policy π such that π(s 1 , a 1 ) = p, π(s 1 , a 2 ) = 1 -p, with 1 ≥ p ≥ 0, which has associated value ⃗ V π (s 1 ) = (p, 1 -p). Hence, the utility function must also satisfy u(1, 0) > u(0.9, 0.1) > • • • > u(0.1, 0.9) > u(0, 1). And it needs to be absolutely precise: u(p + ϵ, 1 -p -ϵ) > u(p, 1 -p) for every ϵ > 0 arbitrarily small. Thus, it is impossible to represent the lexicographic order as a linear utility function.While lexicographic orders cannot be represented with utility functions in MOMDPs, they do have maximal elements among finite MOMDPs. A utility function that shares the exact same maximal elements as a lexicographic order would be very helpful. With such a utility function, we could still find the policies that maximise a lexicographic order with state-of-the-art 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 quasi-representative. Formally: Definition 12. Let M be an MOMDP. Let ⪰ be a preference relation ⪰ in M that is at least reflexive and transitive (a quasi-order). Let u be a utility function such that for every state s of M:EQUATIONThen, we say that u is quasi-representative of ⪰ in M. Example 9. Consider the MOMDP M in Example 8. The utility function u(x, y) = 10x + y is quasi-representative of the lexicographic order because u(1, 1) > u(1, 0) and u(1, 1) > u(0, 1).In fact, quasi-representative utility functions allow us to define an equivalence relation between utility functions. Hence, by abuse of notation, we will also say that two utility functions are quasirepresentative for a given MOMDP if and only if they share the same maximum elements for every state s of this MOMDP. Example 10. Consider the same MOMDP M and the lexicographic order ⪰ from Example 8. For example, utility functions u(x, y) = 10x + y and u ′ (x, y) = 15x + y + 30 share the same utility optimal policy (which is π(s 1 ) = a 3 ), and hence are quasi-representative for M and ⪰.Notice that if a utility function u is representative of some preference relation ⪰, it is also quasirepresentative of ⪰. Notice also that a utility function may be representative or quasi-representative of a given preference order for some MOMDP but not for other MOMDPs. Proof 3. We offer a constructive proof. For every state s, consider its set of maximal elements ⃗ V * (s) according to ⪰, which is non-empty for every state due to Condition (3). Since the preference relation is complete, for every state s all its maximal elements will share the same value (i.e., ⃗V 1 (s) = ⃗ V 2 (s) for every two ⃗ V 1 , ⃗ V 2 ∈ ⃗ V * (s)).Hence, without loss of generality, we consider that there is 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 ⪰. For every other vector x ∈ R n , set u(x) = 0. Now, by construction, for every state s we have that max⃗ V (u • ⃗ V )(s) ∈ ⃗ V * (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 to ⪰.Completeness and transitivity are very common conditions for preference relations in game theory [14] . 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 a quasi-representative 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. 
related work: 
 Most of the literature in MORL focuses on creating novel solution concepts in MORL and algorithmic methods to solve them (e.g., [28, 33, 20, 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 a 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⟩-optimal policy in our terms), but as we have proven in Example 4, this is not always the case.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 [23, 26] . Skalse et al.'s theoretical results in [23] complement ours by stating that, for every so-called objective (a preorder between policies), a uoptimal policy exists if and only if this objective can be represented with a 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 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 Examples 5 and 4.Next, Subramani et al. in [26] follow on the work in [23] , 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 to order policies differently per state, unlike our preference definition.To finish, closely related to our work, Miura in [15] tackles the problem of characterising preferences and their properties in constrained MDPs [1] . 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. While CMDPs and MOMDPs share many similarities, they belong to separate research area. The major difference between them is that a 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-making problems with multiple objectives. In MORL, the learning agent ponders between the multiple objectives by means of a 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: (1) for which utility functions an 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 MORL. Then, we provided sufficient and insufficient conditions for such a 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 quasi-representative 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 are utility optimal.We envision many directions for future research. On the theoretical side, a 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. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: As a fully theoretical paper, it poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Justification: As a fully theoretical paper, it does not use existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Next, we provide the proofs of all theoretical results of An Analytical Study of Utility Functions in Multi-Objective Reinforcement Learning that could not fit in the main paper.Example 11. Recall the utility function u(x, y) = √ x 2 + 1 + y 20 . As previously mentioned This environment has two possible deterministic policies. The first policy is 20) , and scalarised values u( ⃗ V π1 (s 1 )) ≈ 4.16, u( ⃗ V π1 (s 2 )) ≈ 3.24.π 1 (s 1 ) = a 1 , π 1 (s 2 ) = a 2 . This policy obtains values ⃗ V π1 (s 1 ) = (3, 20), ⃗ V π1 (s 2 ) = (2,The second policy isπ 2 (s 1 ) = a 1 , π 2 (s 2 ) = a 3 . This policy obtains values ⃗ V π2 (s 1 ) = (4, 1), ⃗ V π2 (s 2 ) = (3, 1), and scalarised values u( ⃗ V π2 (s 1 )) ≈ 4.17, u( ⃗ V π2 (s 2 )) ≈ 3.21.Any stochastic policy π will be of the form pπ 1 + (1 -p)π 2 with 1 ≥ p ≥ 0. That means that:• At state s 1 it will obtain value ⃗ V π (s 1 ) = (3p + 4(1 -p), 20p + (1 -p)) = (4 -p, 19p + 1), and scalarised value u( ⃗ V π (s 1 )) = (4 -p) 2 + 1 + 19p+1 20 . • At state s 2 it will obtain value ⃗ V π (s 2 ) = (2p + 3(1 -p), 20p + (1 -p)) = (3 -p, 19p + 1), and scalarised value u( ⃗ V π (s 2 )) = (3 -p) 2 + 1 + 19p+1 20 .Consider now the scalarised value of the stochastic policy π as a function u ′ (p, s) depending on the real variable p. Its derivative isEQUATIONwhere α s1 = 4, α s2 = 3. The derivative u ′ (p, s 1 ) has a root r 1 ≈ 0.958, and the derivative u ′ (p, s 2 ) has a root r 2 ≈ -0.042. Both roots are global minima, and thus u ′ (0, s 1 ) is a global maximum for [0, 1] at state s 1 , and u ′ (1, s 2 ) is a global maximum for [0, 1] at state s 2 . In other words, π 1 is the absolute ⟨u, s 2 ⟩-optimal policy, while π 2 is the absolute ⟨u, s 1 ⟩-optimal policy. Thus, no stochastic u-optimal policy exists.This Section is devoted to prove an indispensable theorem: that our 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 π, there exists another stationary policy π ′ such that, for every state s of M, it obtains the same expected returns: ⃗ V π (s) = ⃗ V π ′ (s) for every state s. Proof 4. Direct generalisation from single-objective MDPs, in which for any policy π, there is another stationary policy π ′ such that for every state s 0 it achieves the same value V π (s 0 ) = V π ′ (s 0 ). See Proposition 1.1. of [16] for a full proof for single-objective MDPs.Theorem 5. Let M be any finite MOMDP. Let u be a utility function under the SER criterion. Then:• If an ⟨u, s⟩-optimal policy π * exists for a state s of M, there is at least another stationary policy π ′ * such that π ′ * is also ⟨u, s⟩-optimal. • If an u-optimal policy π * exists for M, there is at least another stationary policy π ′ * such that π ′ * is also u-optimal.Proof 5. We only cover the first case, with the second one being analogous. Let π * be such that u( ⃗ V π * )(s) ≥ u( ⃗ V π )(s) for every state s. Then, by Lemma 4, there exists another stationary policyπ ′ * such that ⃗ V π * (s) = ⃗ V π ′ * (s) for every state s. Thus, u( ⃗ V π ′ * (s)) = u( ⃗ V π * (s)) ≥ u( ⃗ V π (s)), and so π ′ * is also u-optimal.(i) First, as Lemma 7 states, applying a strictly monotonically increasing utility function to a 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 a single-objective MDP M ′ with the scalarised reward function lu ⃗R. 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 a utility function f that can be decomposed into a strictly monotonically increasing function smi, and a linear function lu, then f (x) = smi(lu(x)) will have deterministic and stationary f -optimal policies (which will be exactly the deterministic and stationary lu-optimal policies).Next, we prove that the following two functions are quasi-representative: a function decomposable in an affine function and a strictly monotonically increasing function, and another decomposable in a linear function and a strictly monotonically increasing function.(iv) Next, Lemma 8 proves that any affine utility function af is quasi-representative of another linear utility function lu. More precisely, in every MOMDP, all af -optimal policies are also lu-optimal policies and vice-versa for the linear utility function lu defined as lu(x) = af (x) -af (0). This is because any affine function af (x) can be decomposed as af (x) = A(x) + b, with A(x) being a linear function and b = af (0), a constant.(v) Now, consider a utility function f (x) = smi(af (x)) that can be decomposed as a product of a strictly monotonically increasing utility smi function and an affine utility function af . Consider also the utility function f ′ (x) = smi(af (x) -af (0)). This second function f ′ (x) is composed by a strictly monotonically increasing function and a linear function, so as previously proven in (iii), there are deterministic and stationary f ′ -optimal policies.(vi) Then, recall that by (iv), utility functions af (x) and af (x) -af (0) are quasi-representative (i.e., they share the same optimal policies). Thus, it is clear that smi(af (x)) and smi(af (x)-af (0)) are also quasi-representative, because strictly monotonically increasing functions preserve the ordering by definition.Finally, since f ′ (x) = smi(af (x) -af (0)) has deterministic and stationary f ′ -optimal policies, and f (x) = smi(af (x)) and f ′ (x) are quasi-representative, we conclude that there are also deterministic and stationary f -optimal policies.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 we characterised sufficient conditions for utility functions to have associated optimal policies with Theorems 1 (per state), and 2 (for the whole MOMDP). Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Through the paper, we refer to a single-objective MDP simply as an MDP. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- 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. 
- Section 3 and 4 seem misaligned. (please see question 3)
questions: 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?
- 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.
- 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.
- (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: limitations: The motivation and importance of this work are appealing. However, the sufficient conditions seem to result in a too small subclass of interest.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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).
- 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).
- 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.
questions: 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.
Below, I have a few questions and constructive feedback to the authors:

1) My main concern is that the paper does not have a related work section and does not discuss many relevant related works. For instance:

[1] showed how to construct stochastic policies that are optimal w.r.t. the initial state distribution.

[2] introduced different solution sets that extend the definition of the Pareto front and can express more utility functions.

[3] and [4] showed that many multi-objective utility functions can not be expressed via Markov rewards.

[5] discusses the expressivity of many RL formalisms to represent different preferences, including MORL.

2) 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.

3) Theorem 1 seems to be a more formal definition of the result in Vamplew et al. 2009 [1].

4) 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.

5) 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.

Minor:
- Use large brackets, e..g., in Equation 1, the bracket is smaller than the summation symbol.
- In definition 3, the transition function is $\mathcal{T}$ instead of $T$. Please be consistent.

[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.

[2] Röpke, W., Hayes, C. F., Mannion, P., Howley, E., Nowé, A., and Roijers, D. M. (2023). Dis-
tributional multi-objective decision making. In Elkind, E., editor, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23.

[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.

[4] Miura, S. (2022). On the expressivity of multidimensional markov reward. In Proceedings of the
Conference on Reinforcement Learning and Decision Making.

[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: limitations: The results have some limitations that should be addressed (see Questions above). The paper has no potential negative societal impact.
paper_summary: paper_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. 

Given 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.
strength_weakness: strength_weakness: - 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.

- 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? 

- 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?
questions: 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: limitations: There are no significant potential societal negative impacts.

Comments: title: Response
Thanks for the response
comment: Thanks for the reply. I have raised my rating.
Again, I thank the authors for their insightful response. I am increasing my score since the theoretical results in the paper can be potentially useful to other researchers in the field.
This is correct: Theorem 2 proves that any function of such class is quasi-representative to another linear utility function, and thus its optimal policies belong to the convex hull. 

The usefulness of this class of utility functions is threefold, in our opinion:

1) it proves that not only linear utility functions have solution policies inside the convex hull.

2) similarly, it provides more structure to the convex hull, allowing us to identify a particular family of utility functions that belong to it.

3) In practice, Theorem 2 provides a general methodology for obtaining solution policies: if a utility function can be proved to be quasi-representative to a linear utility function, then an u-optimal policy is guaranteed to exist. Take for instance the utility function of Example 6. A priori, one would not know how to compute its u-optimal policy (or if it even exists). Thanks to Theorem 2 we know that it exists, and that it belongs to the convex hull.

To understand the significance of these results, we would also like to remark that:  it is still a complex problem to find utility functions for which an u-optimal policy always exists for any arbitrary MOMDP, and that furthermore this u-optimal policy does not belong to the convex hull. We are not aware of a single utility function for which this is true.  

Moreover, the theoretical implications of Example 4 greatly limit the   candidate families of utility functions for which a deterministic and stationary u-optimal policy is guaranteed to exist. 

In any case, we already started working on searching for utility functions with concave deterministic and stationary u-optimal policies, and hope to find results in future work.
Thank you for clarifying the proof. 

I have one last question regarding Theorem 2: You showed a class of utility functions with deterministic and stationary optimal policies. However, because of the inner affine function, it seems that this utility function can represent the same set of optimal policies as linear utility functions. In other words, given a utility function "u" decomposable as a strictly monotonically increasing function and an affine function, its optimal policy will be on the Convex Hull (Eq. 5). Is that correct? If so, why would this class of utility function be useful if it can represent the same policies as linear utility functions? If this is not correct, can you provide an example where this utility function has an optimal policy whose value is a concave region of the Pareto front/undominated set?
We agree with reviewer's point regarding the importance of designing MORL algorithms in the field. In case of acceptance or in any future iteration of the paper, we will definitely add both a discussion section of how our theorems impact algorithm design, and a related work section, following the reviewer's suggestion.


We will now provide an-indepth proof of Theorem 2. In case of acceptance we will make public this proof together with all appendix material.

(i) - First, as Lemma 7 states, applying a strictly monotonically increasing utility function to a 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 a single-objective MDP M' with the scalarised reward function "lu \dot \vec{R}". 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 please see Section 2.2 of our paper).

(iii) - These two facts together (i)+(ii) tell us: given a utility function "f" that can be decomposed into a strictly monotonically increasing function "smi", and a linear function "lu", then "f(x) = smi(lu(x))" will have deterministic and stationary f-optimal policies (which will be the deterministic and stationary lu-optimal policies).

(iv) - Next, Lemma 8 proves that any affine utility function "af" is quasi-representative of another linear utility function "lu".  More precisely, in every MOMDP,  all af-optimal policies are also lu-optimal policies and vice-versa for the linear utility function "lu" defined as lu(x) = af(x) - af(0). This is because any affine function af(x) can be decomposed as  "af(x) = A(x) + b", with A(x) being a linear function and b = af(0), a constant.

Now, consider an utility function "f(x) = smi(af(x))" that can be decomposed as a product of a strictly monotonically increasing utility "smi" function and an affine utility function "af". 

(v) - Consider also the utility function "f'(x) = smi(af(x)-af(0))". This second function f'(x) is composed by a strictly monotonically increasing function and a linear function, so by (iii), there are deterministic and stationary f'-optimal policies.

(vi) -  Then, recall that,  by (iv), utility functions "af(x)" and "af(x)-af(0)" are quasi-representative (i.e., they share the same optimal policies). Thus, it is clear that "smi(af(x))" and "smi(af(x)-af(0))" are also quasi-representative, because strictly monotonically increasing functions preserve the ordering by definition. This is a point that should have been much clearer in the paper, so we apologise for that.

Finally, since:  f'(x) = smi(af(x)-af(0)) has deterministic and stationary f'-optimal policies, and f(x)= smi(af(x)) and f'(x) are quasi-representative, we conclude that there are also deterministic and stationary f-optimal policies. This proves Theorem 2.

If there is any further doubt or unclear proof we will be happy to clarify it.
I thank the authors for their careful response to my questions and concerns. I am slightly increasing my score due to the authors' response. Below, I have a few more comments on the points raised by the authors:

**Weakness 3: I agree that algorithms for solving MORL problems are out of the scope of the paper. However, since the end goal of the field is the design of MORL algorithms, I strongly suggest adding a short discussion to the paper on how these theoretical ideas might be useful. E.g., "Theorem X implies that the community need to design novel algorithms with properties Y and Z.".

**Question 1: Thank you for providing this comparison. It is critical that these discussions are included in the final version of the paper, since they explain why previous related works are not sufficient.

**Question 4: I believe this is not the only issue in this proof. Please provide more detailed proof of Theorem 2, which currently is "Direct consequence of combining Lemma 7 and Lemma 8". It is very unclear how this is the case.
I thank the authors for taking the time to carefully read the review and write the response.

My questions on the two theorems were about sufficency vs necessary conditions. The response has made this quite clear to me. I hope that the authors will make the theorems clearer in the next iteration of the paper. 

Finally, there were some more multiobjective learning papers in mid 2000s (they were called as multicriteria RL back then). I suggest that the authors cite those papers in their paper as well for the sake of completion.