# Expected Scalarised Returns Dominance: A New Solution Concept for Multi-
Objective Decision Making ††thanks: An earlier version of this work was
presented at the Adaptive and Learning Agents Workshop 2021 [1]. This article
extends our workshop paper with additional theoretical analysis and new
empirical results.

Conor F. Hayes National University of Ireland Galway, Ireland
<EMAIL_ADDRESS>Timothy Verstraeten Vrije Universiteit Brussel,
Belgium  Diederik M. Roijers Vrije Universiteit Brussel, Belgium  HU
University of Applied Science Utrecht, The Netherlands  Enda Howley National
University of Ireland Galway, Ireland  Patrick Mannion National University of
Ireland Galway, Ireland

###### Abstract

In many real-world scenarios, the utility of a user is derived from a single
execution of a policy. In this case, to apply multi-objective reinforcement
learning, the expected utility of the returns must be optimised. Various
scenarios exist where a user’s preferences over objectives (also known as the
utility function) are unknown or difficult to specify. In such scenarios, a
set of optimal policies must be learned. However, settings where the expected
utility must be maximised have been largely overlooked by the multi-objective
reinforcement learning community and, as a consequence, a set of optimal
solutions has yet to be defined. In this work we propose first-order
stochastic dominance as a criterion to build solution sets to maximise
expected utility. We also define a new dominance criterion, known as expected
scalarised returns (ESR) dominance, that extends first-order stochastic
dominance to allow a set of optimal policies to be learned in practice.
Additionally, we define a new solution concept called the ESR set, which is a
set of policies that are ESR dominant. Finally, we present a new multi-
objective tabular distributional reinforcement learning (MOTDRL) algorithm to
learn the ESR set in multi-objective multi-armed bandit settings.

_K_ eywords Multi-objective $\cdot$ Decision making $\cdot$ Distributional
$\cdot$ Reinforcement learning $\cdot$ Stochastic dominance

##  1 Introduction

When making decisions in the real world, decision makers must make trade-offs
between multiple, often conflicting, objectives [2]. In many real-world
settings, a policy is only executed once. For example, consider a municipality
that receives the majority of its electricity from local solar farms. To deal
with the intermittency of the solar farms, the municipality wants to build a
new electricity generation facility. The municipality are considering two
choices: building a natural gas facility or adding a lithium-ion battery
storage facility to the solar farms. Moreover, the municipality want to
minimise $CO_{2}$ emissions while ensuring energy demand can continuously be
met. Given a new energy generation facility will only be constructed once, a
full distribution over each potential outcome for capacity to meet electricity
demand and $CO_{2}$ emissions must be considered to make an optimal decision.
The current state-of-the-art multi-objective reinforcement learning (MORL)
literature focuses almost exclusively on learning polices that are optimal
over multiple executions. Given such problems are salient, to fully utilise
MORL in the real world, we must develop algorithms to compute a policy, or set
of policies, that are optimal given the single-execution nature of the
problem.

In multi-objective reinforcement learning (MORL) a user’s preferences over
objectives are represented by a utility function. In certain scenarios a
user’s preferences over objectives may be unknown; therefore, the utility
function is unknown. In this case, a user is said to be in the unknown utility
function or unknown weights scenario [3]. The unknown utility function
scenario has three phases: the learning phase, the selection phase and the
execution phase. During the learning phase a multi-objective method [4] is
used compute a set of optimal policies and the set of policies is returned to
the user. During the selection phase the utility function of the user becomes
known and a policy from the computed set is selected which best reflects their
preferences. The selected policy is then executed during the execution phase
[5].

In contrast to single-objective reinforcement learning (RL), multiple
optimality criteria exist for MORL [3]. In scenarios where the utility of the
user is derived from multiple executions of a policy, the scalarised expected
returns (SER) must be optimised. However, in scenarios where the utility of a
user is derived from a single execution of a policy, the expected utility of
the returns (or expected scalarised returns, ESR) must be optimised. The
majority of MORL research focuses on the SER criterion and linear utility
functions [6], which limits the applicability of MORL to real-world problems.
In the real world, a user’s utility function may be derived in a linear or
non-linear manner. For known linear utility functions, single-objective
methods can be used to learn an optimal policy [3]. Non-linear utility
functions do not distribute across the sums of the immediate and future
returns, which invalidates the Bellman equation [7]. Therefore, to learn
optimal policies for non-linear utility functions, strictly multi-objective
methods must be used.

For non-linear utility functions, the policies learned under the SER criterion
and the ESR criterion can be different [6, 8]. The ESR criterion has received
very little attention, to date, from the MORL community with some exceptions
[9, 10, 11, 7]. To learn optimal policies in many real-world scenarios where a
policy will be executed only once, the ESR criterion must be optimised. For
example, in a medical setting where a user has one opportunity to select a
treatment, a user will aim to maximise the expected utility of a single
outcome. However, choosing the wrong optimisation criterion (SER) for such a
scenario could potentially lead to a different policy than that which would be
learned under ESR. In the real world, like in the aforementioned scenario,
learning a sub-optimal policy could have catastrophic outcomes.

Therefore, it is crucial that the MORL community focuses on developing multi-
objective algorithms that can learn optimal policies under the ESR criterion.
Recently, a number of multi-objective methods have been implemented that can
learn a single optimal policy under the ESR criterion [7, 12]. However, in the
current MORL literature, no multi-policy algorithms exist for the ESR
criterion. In fact, a set of optimal policies for the ESR criterion has yet to
be defined.

Due to the lack of existing research for the ESR criterion, a formal
definition of the requirements to learn optimal policies under the ESR
criterion has yet to be determined. In Section 3, we define the requirements
necessary to compute policies under the ESR criterion. The applicability of
MORL to many real-world scenarios under the ESR criterion is limited because
no solution set has been defined for scenarios when a user’s utility function
is unknown. In Section 4, we show how first-order stochastic dominance can be
used to define sets of optimal policies under the ESR criterion. In Section 5,
we expand first-order stochastic dominance to define a new dominance
criterion, called expected scalarised returns (ESR) dominance. This work
proposes that ESR dominance can be used to compute a set of optimal policies,
which we define as the _ESR set_. Finally, we present a novel multi-objective
tabular distributional reinforcement learning algorithm (MOTDRL) which aims to
learn the _ESR set_ in scenarios when the utility function of the user is
unknown. We apply MOTDRL to two different multi-objective multi-armed bandit
settings where MOTDRL is able to learn the _ESR set_ in both settings.

##  2 Background

In this section we introduce necessary background material, including multi-
objective reinforcement learning, utility functions, the unknown utility
function scenario, multi-objective multi-armed bandits, commonly used
optimality criteria in multi-objective decision making, and stochastic
dominance.

###  2.1 Multi-Objective Reinforcement Learning

In multi-objective reinforcement learning (MORL) [5], we deal with decision
making problems with multiple objectives, often modelled as a multi-objective
Markov decision process (MOMDP). An MOMDP is a tuple,
$\mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{T},\gamma,\mathcal{R})$, where
$\mathcal{S}$ and $\mathcal{A}$ are the state and action spaces,
$\mathcal{T}\colon\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to\left[0,1\right]$
is a probabilistic transition function, $\gamma$ is a discount factor
determining the importance of future rewards and
$\mathcal{R}\colon\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to\mathbb{R}^{n}$
is an $n$-dimensional vector-valued immediate reward function. In multi-
objective reinforcement learning, $n>1$.

###  2.2 Utility Functions

In MORL, utility functions are used to model a user’s preferences. In this
work, utility functions map vector returns to a scalar value which represents
the user’s preferences over the returns,

$u:\mathbb{R}^{n}\rightarrow\mathbb{R},$ (1)

where $u$ is a utility function and $\textbf{R}^{n}$ is an n-dimensional
vector. Linear utility functions are widely used to represent a user’s
preferences,

$u=\sum_{i=1}^{n}w_{i}r_{i},$ (2)

where $w_{i}$ is the preference weight and $r_{i}$ is the value at position
$i$ of the return vector. However, certain scenarios exist where linear
utility functions cannot accurately represent a user’s preferences. In this
case, the user’s preferences must be represented using a non-linear utility
function.

In this paper, we consider monotonically increasing utility functions [3],
i.e.,

$(\forall\,i,V_{i}^{\pi}\geq
V_{i}^{\pi^{\prime}}\wedge\exists\,i,V_{i}^{\pi}>V_{i}^{\pi^{\prime}})\implies(\forall\,u,u(\textbf{V}^{\pi})>u(\textbf{V}^{\pi^{\prime}})),$
(3)

where $\mathbf{V}^{\pi}$ and $\mathbf{V}^{\pi^{\prime}}$ are the values of
executing policies $\pi$ and $\pi^{\prime}$ respectively.

It is important to note, a monotonically increasing utility function also
includes linear utility functions of the form in Equation 2. In certain
scenarios the utility function may be unknown, therefore we do not know the
shape of the utility function. If we assume the utility function is
monotonically increasing we know that, if the value of one of the objectives
in the return vector increases, then the utility also increases [3]. This
assumption makes it possible to determine a partial ordering over policies
when the shape of the utility function is unknown. In this work we make no
assumptions about the shape of the utility function but rather we assume the
utility function is monotonically increasing.

###  2.3 The Unknown Utility Function Scenario

In MORL, a user’s preferences over objectives can be modelled as a utility
function [3]. However, a user’s utility function is often unknown at the time
of learning or planning. In the taxonomy of multi-objective decision making
(MODeM), this is known as the unknown utility function scenario (see Figure
1), where a set of optimal policies must be computed and returned to the user
[5]. In the unknown utility function scenario there are three phases: the
learning or planning phase, the selection phase, and the execution phase. In
the learning or planning phase a multi-objective planning or learning
algorithm is deployed in a MOMDP. Given the utility function is unknown, the
MORL algorithm computes a set of optimal policies during the learning or
planning. During the selection phase, the user’s preferences over objectives
becomes known and the user selects a policy from the set of optimal policies
that best reflects their preferences. Finally, during the execution phase the
selected policy is executed.

MOMDP
---
algorithm _planning or_
---
_learning phase_
solution
---
set
utility
---
function
user
---
selection
selection phase single
---
solution
_execution_
---
_phase_
Figure 1: The unknown utility function scenario [5].

###  2.4 Multi-Objective Multi-Armed Bandits

Multi-objective multi-armed bandits (MOMAB) [13] are a natural extension of
multi-armed bandits, where each arm returns an n-dimensional reward vector
$\textbf{R}^{n}$, where n is the number of objectives. At each timestep, $t$,
the agent must select an arm, $i$, and receives a reward vector. The returns
in an MOMAB setting can be deterministic [13] or stochastic [14]. Many
algorithms focus on the MOMAB setting and learn a set of arms that are optimal
[13, 15, 16, 17].

For example, Pareto UCB-1 [13] is an algorithm that can learn a set of optimal
policies in an MOMAB setting. Pareto UCB-1 [13] initially selects each arm
once, then at each timestep the algorithm computes the mean vector of each of
the multi-objective arms and adds the upper confidence bound to the mean
return vector. Using this method Pareto UCB-1, can learn the Pareto front in
an MOMAB setting.

###  2.5 Scalarised Expected Returns and Expected Scalarised Returns

For MORL, the ability to express a user’s preferences over objectives as a
utility function is essential when learning a single optimal policy. In MORL,
different optimality criteria exist [3]. Additionally, the utility function
can be applied to the expectation of the returns, or the utility function can
be applied directly to the returns before computing the expectation.
Calculating the expected value of the return of a policy before applying the
utility function leads to the scalarised expected returns (SER) optimisation
criterion:

$V_{u}^{\pi}=u\left(\mathbb{E}\left[\sum\limits^{\infty}_{t=0}\gamma^{t}{\textbf{r}}_{t}\>\middle|\>\pi,\mu_{0}\right]\right),$
(4)

where $\mu_{0}$ is the probability distribution over possible starting states.

SER is the most commonly used criterion in the multi-objective (single agent)
planning and reinforcement learning literature [3]. For SER, a coverage set is
defined as a set of optimal solutions for all possible utility functions. If
the utility function is instead applied to the returns before computing the
expectation, this leads to the expected scalarised returns (ESR) optimisation
criterion [7, 12, 3]:

$V_{u}^{\pi}=\mathbb{E}\left[u\left(\sum\limits^{\infty}_{t=0}\gamma^{t}{\textbf{r}}_{t}\right)\>\middle|\>\pi,\mu_{0}\right].$
(5)

ESR is the most commonly used criterion in the game theory literature on
multi-objective games [6].

###  2.6 Stochastic Dominance

Stochastic dominance [18, 19] gives a partial order between distributions and
can be used when making decisions under uncertainty (see Figure 2). Stochastic
dominance is particularly useful when a distribution must be taken into
consideration rather than an expected value when making decisions. Stochastic
dominance is a prominent dominance criterion in finance, economics and
decision theory. When making decisions under uncertainty, stochastic dominance
can be used to determine the most risk averse decision. Various degrees of
stochastic dominance exist, however, in this paper we focus on first-order
stochastic dominance (FSD). FSD can be used to give a partial ordering over
random variables or random vectors to give an FSD dominant set.

Figure 2: For random variables $X$ and $Y$, $X$ $\succeq_{FSD}$ $Y$, where
$F_{X}$ and $F_{Y}$ are the cumulative distribution functions (CDFs) of $X$
and $Y$ respectively. In this case, $X$ is preferable to $Y$ because higher
utilities occur with greater frequency in $F_{X}$.

In Definition 1 we present the necessary conditions for FSD and in Theorem 1
we prove that if a random variable is FSD dominant it has at least as high an
expected value as another random variable [20]. We use the work of Wolfstetter
[20] to prove Theorem 1.

###### Definition 1

For random variables X and Y, X $\succeq_{FSD}$ Y if:

$P(X>z)\geq P(Y>z),\forall\,z$

If we consider the cumulative distribution function (CDF) of X, $F_{X}$, and
the CDF of Y, $F_{Y}$, we can say that X $\succeq_{FSD}$ Y if:

$F_{X}(z)\leq F_{Y}(z),\forall\,z.$

###### Theorem 1

If X $\succeq_{FSD}$ Y, then X has a greater than or equal expected value as
Y.

$X\succeq_{FSD}Y\implies E(X)\geq E(Y).$

###### Proof 1

By a known property of expected values the following is true for any random
variable:

$\mathbb{E}(X)=\int_{0}^{+\infty}(1-F_{X}(x))\,dx$
$\mathbb{E}(Y)=\int_{0}^{+\infty}(1-F_{Y}(x))\,dx$

Therefore, if X $\succeq_{FSD}$ Y then:

$\int_{0}^{+\infty}(1-F_{X}(x))\,dx\geq\int_{0}^{+\infty}(1-F_{Y}(x))\,dx$

Which gives,

$\mathbb{E}(X)\geq\mathbb{E}(Y).$

[20]

##  3 Expected Scalarised Returns

In contrast to single-objective reinforcement learning, different optimality
criteria exist for MORL. In scenarios where the utility of a user is derived
from multiple executions of a policy, the agent should optimise over the
scalarised expected returns (SER) criterion. In scenarios where the utility of
a user is derived from a single execution of a policy, the agent should
optimise over the expected scalarised returns (ESR) criterion. Let us
consider, as an example, a power plant that generates electricity for a city
and emits harmful $CO_{2}$ and greenhouse gases. City regulations have been
imposed which limit the amount of pollution that the power plant can generate.
If the regulations require that the emissions from the power plant do not
exceed a certain amount over an entire year, the SER criterion should be
optimised. In this scenario, the regulations allow for the pollution to vary
day to day, as long as the emissions do not exceed the regulated level for a
given year. However, if the regulations are much stricter and the power plant
is fined every day it exceeds a certain level of pollution, it is beneficial
to optimise under the ESR criterion.

The majority of MORL research focuses on linear utility functions. However, in
the real world, a user’s utility function can be non-linear. For example, a
utility function is non-linear in situations where a minimum value must be
achieved on each objective [21]. Focusing on linear utility functions limits
the applicability of MORL in real-world decision making problems. For example,
linear utility functions cannot be used to learn policies in concave regions
of the Pareto front [22]. Furthermore, if a user’s preferences are non-linear,
these are fundamentally incompatible with linear utility functions. In this
case, strictly multi-objective methods must be used to learn optimal policies
for non-linear utility functions. In MORL, for non-linear utility functions,
different policies are preferred when optimising under the ESR criterion
versus the SER criterion [8]. It is important to note that, for linear utility
functions, the distinction between ESR and SER does not exist [6].

For example, a decision maker has to choose between the following lotteries,
$L_{1}$ and $L_{2}$, which are highlighted in Table 1.

$L_{1}$
---
P($L_{1}$= R) | R
0.5 | (4, 3)
0.5 | (2, 3)

$L_{2}$
---
P($L_{2}$=R) | R
0.9 | (1, 3)
0.1 | (10, 2)

Table 1: A lottery, $L_{1}$, has two possible returns, (4, 3) and (2, 3), each
with a probability of 0.5. A lottery, $L_{2}$, has two possible returns, (1,
3) with a probability of 0.9 and (10, 2) with a probability of 0.1.

The decision maker has the following non-linear utility function:

$u(\textbf{x})=x_{1}^{2}+x_{2}^{2},$ (6)

where x is a vector returned from $\mathbf{R}$ in Table 1, and $x_{1}$ and
$x_{2}$ are the values of two objectives. Note that this utility function is
monotonically increasing for $x_{1}\geq 0$ and $x_{2}\geq 0$. Under the SER
criterion, the decision maker will compute the expected value of each lottery,
apply the utility function, and select the lottery that maximises their
utility function. Let us consider which lottery the decision maker will play
under the SER criterion:

$L_{1}:\,E(L_{1})=0.5(4,3)+0.5(2,3)=(2,1.5)+(1,1.5)=(3,3)$
$L_{1}:\,u(E(L_{1}))=(3^{2}+3^{2})=9+9=18$
$L_{2}:\,E(L_{2})=0.9(1,3)+0.1(10,2)=(0.9,2.7)+(1,0.2)=(1.9,2.9)$
$L_{2}:\,u(E(L_{2}))=(1.9^{2}+2.9^{2})=3.61+8.41=12.02$

Therefore, a decision maker with the utility function in Equation 6 will
prefer to play lottery $L_{1}$ under the SER criterion.

Under the ESR criterion, the decision maker will first apply the utility
function to the return vectors, compute the expectation, and select the
lottery to maximise their utility function. Let us consider how a decision
maker will choose which lottery to play under the ESR criterion:

$L_{1}:\,\mathbb{E}(u(L_{1}))=0.5(u(4,3))+0.5(u(2,3))=0.5(4^{2}+3^{2})+0.5(2^{2}+3^{2})$
$=0.5(25)+0.5(13)=12.5+6.5=19$
$L_{2}:\,\mathbb{E}(u(L_{2}))=0.9(u(1,3))+0.1(u(10,2))=0.9(1^{2}+3^{2})+0.1(10^{2}+2^{2})$
$=0.9(10)+0.1(104)=9+10.4=19.4$

Therefore, a decision maker with the utility function in Equation 6 will
prefer to play lottery $L_{2}$ under the ESR criterion. From the example, it
is clear that users with the same non-linear utility function can prefer
different policies, depending on which multi-objective optimisation criterion
is selected. Therefore, it is critical that the distinction ESR and SER is
taken into consideration when selecting a MORL algorithm to learn optimal
policies in a given scenario. The majority of MORL research focuses on the SER
criterion [6]. By comparison, the ESR criterion has received very little
attention from the MORL community [3, 12, 7, 6]. Many of the traditional MORL
methods cannot be used when optimising under the ESR criterion, given non-
linear utility functions in MOMDPs do not distribute across the sum of
immediate and future returns which invalidates the Bellman equation [7],

$\begin{split}\max_{\pi}\ &\mathbb{E}\left[u\left({\bf
R}_{t}^{-}+\sum_{i=t}^{\infty}\gamma^{i}{\bf r}_{i}\right)\ \middle|\
\pi,s_{t}\right]\not=\\\ &u({\bf
R}_{t}^{-})+\max_{\pi}\mathbb{E}\left[u\left(\sum_{i=t}^{\infty}\gamma^{i}{\bf
r}_{i}\right)\ \middle|\ \pi,s_{t}\right],\end{split}$ (7)

where $u$ is a non-linear utility function and $\bf{R^{-}_{t}}$ $=$
$\sum_{i=0}^{t-1}\gamma^{i}{\bf r}_{i}$.

An example of an algorithm that can learn policies for non-linear utility
functions and the ESR criterion is distributional Monte Carlo tree search
(DMCTS) [12]. Hayes et al. [12] use Monte Carlo tree search to calculate the
returns of a full policy and compute a posterior distribution over the
expected utility of individual policy executions. DMCTS achieves state of the
art performance under the ESR criterion. Hayes et al. [12] demonstrate that,
when optimising under the ESR criterion, making decisions based on a
distribution over the utility of the returns is particularly useful when
learning in realistic problems where rewards are stochastic.

However, DMCTS and other MORL algorithms that optimise for the ESR criterion
[3, 7, 9] require the utility function of a user to be known a priori. In
practice, many scenarios exist where a user’s utility function may be unknown
at the time of learning or planning. To compute policies under the ESR
criterion when a user’s utility function is unknown, a distribution over the
returns must be maintained. To highlight why a distribution over the returns
must be used when the utility function of a user is unknown, let us consider
the following example in Table 2.111Generally, in the unknown utility function
scenario a set of optimal policies is calculated. Under the ESR criterion, a
set of optimal policies has yet be defined. Therefore, this example does not
calculate a set of optimal policies but instead illustrates why a distribution
over the returns is required under the ESR criterion. We define a set of
optimal policies under the ESR criterion in a later section.

$L_{3}$
---
P($L_{3}$= R) | R
0.5 | (-20, 1)
0.5 | (20, 3)

$L_{4}$
---
P($L_{4}$=R) | R
0.9 | (0, 2)
0.1 | (5, 2)

Table 2: A lottery, $L_{3}$, has two possible returns, (-20, 1) and (20, 3),
each with a probability of 0.5. A lottery, $L_{4}$, has two possible returns,
(0, 2) with a probability of 0.9 and (5, 2) with a probability of 0.1.

To determine which lottery to play while optimising for the ESR criterion, the
utility function must first be applied, then the expected utility can be
computed (see Equation 5):

$u(L_{3})=u((-20,1))+u((20,3))$
$\mathbb{E}(u(L_{3}))=0.5(u((-20,1)))+0.5(u((20,3)))$
$u(L_{4})=u((0,2))+u((5,2))$
$\mathbb{E}(u(L_{4}))=0.9(u((0,2)))+0.1(u((5,2)))$

Given the utility function is unknown, it impossible to compute the expected
utility. Moreover, a distribution over the returns received from a policy
execution must be maintained in order to optimise for the ESR criterion.
Maintaining a distribution over the returns ensures the expected utility can
be computed once the user’s utility function becomes known at decision time.

As demonstrated above, maintaining a distribution over the returns is critical
to learning optimal policies when the utility function of a user is unknown.
Therefore, to compute a set of optimal policies under the ESR criterion it is
necessary to adopt a distributional approach.

To adopt a distributional approach to multi-objective decision making, we must
first introduce a multi-objective version of the return distribution [23]
222Bellemare et al. [23] introduce a value distribution. However given the
distribution is a distribution over the returns, not values, we prefer the
term return distribution., $\textbf{Z}^{\pi}$. A return distribution,
$\textbf{Z}^{\pi}$, is equivalent to a multivariate distribution where a
dimension exists per objective. The return distribution, $\textbf{Z}^{\pi}$,
gives the distribution over returns of a random vector [24] when a policy
$\pi$ is executed, such that,

$\mathbb{E}\,\textbf{Z}^{\pi}=\mathbb{E}\left[\sum\limits^{\infty}_{t=0}\gamma^{t}{\textbf{r}}_{t}\>\middle|\>\pi,\mu_{0}\right].$
(8)

Moreover, a return distribution can be used to represent policies. Under the
ESR criterion, the utility-of-the-return-distribution, $Z_{u}^{\pi}$, is
defined as a distribution over the scalar utilities received from applying the
utility function to each vector in the return distribution,
$\textbf{Z}^{\pi}$. Therefore, $Z_{u}^{\pi}$ is a distribution over the scalar
utility of vector returns of a random vector received from executing a policy
$\pi$, such that,

$\mathbb{E}\,Z_{u}^{\pi}=\mathbb{E}\left[u\left(\sum\limits^{\infty}_{t=0}\gamma^{t}{\textbf{r}}_{t}\right)\>\middle|\>\pi,\mu_{0}\right].$
(9)

The utility-of-the-return-distribution can only be calculated when the utility
function is known a priori.

When the utility function of a user is unknown, a set of policies that are
optimal for all monotonically increasing utility functions must be learned.
However, for the ESR criterion, a set of optimal solutions has yet to be
defined. To learn a set of optimal policies under the ESR criterion we must
develop new methods. In Section 4 we apply first-order stochastic dominance to
determine a partial ordering over return distributions under the ESR
criterion.

##  4 Stochastic Dominance for ESR

For MORL there are two classes of algorithms: single-policy and multi-policy
algorithms [4, 3]. When the user’s utility function is known a priori, it is
possible to use a single-policy algorithm [12, 7] to learn an optimal
solution. However, when the user’s utility function is unknown we aim to learn
a set of policies that are optimal for all monotonically increasing utility
functions. The current literature on the ESR criterion focuses only on
scenarios where the utility function of a user is known [12, 7], overlooking
scenarios where the utility function of a user is unknown. Moreover, a set of
solutions under the ESR criterion for the unknown utility function scenario
[3] has yet to be defined.

Various algorithms have been proposed to learn solution sets under the SER
criterion (see Section 2.5), for example [25, 26, 27]. Under the SER
criterion, multi-policy algorithms determine optimality by comparing policies
based on the utility of expected value vectors (see Equation 4). In contrast,
under the ESR criterion it is crucial to maintain a distribution over the
utility of possible vector-valued outcomes. SER multi-policy algorithms cannot
be used to learn optimal policies under the ESR criterion because they compute
expected value vectors. It is necessary to develop new methods that can
generate solution sets for the ESR criterion with unknown utilities. The
development of methods that determine an optimal partial ordering over return
distributions is a promising avenue to address this challenge.

First-order stochastic dominance (see Section 2.6) is a method which gives a
partial ordering over random variables [20, 28]. FSD compares the cumulative
distribution functions (CDFs) of the underlying probability distributions of
random variables to determine optimality. When computing policies under the
ESR criterion, it is essential that the expected utility is maximised. To use
FSD for the ESR criterion, we must show the FSD conditions presented in
Section 2.6 also hold when optimising the expected utility for unknown
monotonically increasing utility functions.

For the single-objective case, Theorem 2 proves for random variables X and Y,
if X $\succeq_{FSD}$ Y, the expected utility of X is greater than, or equal
to, the expected utility of Y for monotonically increasing utility functions.
In Theorem 2, random variables X and Y are considered, and their corresponding
CDFs $F_{X}$, $F_{Y}$. The work of Mas-Colell et al. [29] is used as a
foundation for Theorem 2.

###### Theorem 2

A random variable, X, is preferred to a random variable, Y, for all decision
makers with a monotonically increasing utility function if, X $\succeq_{FSD}$
Y.

$X\succeq_{FSD}Y\implies\mathbb{E}(u(X))\geq\mathbb{E}(u(Y))$

###### Proof 2

If X $\succeq_{FSD}$ Y, then333CDFs with lower probability values for a given
$z$ are preferable. Figure 2 explains why this is the case.,

$F_{X}(z)\leq F_{Y}(z),\forall\,z$

Since,

$\mathbb{E}(u(X))=\int_{-\infty}^{\infty}u(z)dF_{X}(z)$
$\mathbb{E}(u(Y))=\int_{-\infty}^{\infty}u(z)dF_{Y}(z)$

When integrating both $\mathbb{E}(u(X))$ and $\mathbb{E}(u(Y))$ by parts, the
following results is generated:

$\mathbb{E}(u(X))=[u(z)F_{X}(z)]_{-\infty}^{\infty}-\int_{-\infty}^{\infty}u^{\prime}(z)F_{X}(z)\,dz$
$\mathbb{E}(u(Y))=[u(z)F_{Y}(z)]_{-\infty}^{\infty}-\int_{-\infty}^{\infty}u^{\prime}(z)F_{Y}(z)\,dz$

Given $F_{X}(-\infty)$ = $F_{Y}(-\infty)$ = 0 and $F_{X}(\infty)$ =
$F_{Y}(\infty)$ = 1, the first terms in $\mathbb{E}(u(X))$ and
$\mathbb{E}(u(Y))$ are equal, and thus

$\mathbb{E}(u(X))-\mathbb{E}(u(Y))=\int_{-\infty}^{\infty}u^{\prime}(z)F_{Y}(z)\,dz-\int_{-\infty}^{\infty}u^{\prime}(z)F_{X}(z)\,dz$

Since $F_{X}(z)\leq F_{Y}(z)$ and $u^{\prime}(z)\geq 0$ for all monotonically
increasing utility functions, then

$\mathbb{E}(u(X))-\mathbb{E}(u(Y))\geq 0$

and thus,

$\mathbb{E}(u(X))\geq\mathbb{E}(u(Y))$

A utility function maps an input (scalar or vector return) to an output
(scalar utility). Since the probability of receiving some utility is equal to
the probability of receiving some return for a random variable, X, we can
write the following:

$P(X>c)=P(u(X)>u(c)),$ (10)

where $c$ is a constant. Using the results shown in Theorem 2 and Equation 10,
the FSD conditions highlighted in Section 2.6 can be rewritten to include
monotonically increasing utility functions:

$P(u(X)>u(z))\geq P(u(Y)>u(z))$ (11)

###### Definition 2

Let X and Y be random variables. X dominates Y for all decision makers with a
monotonically increasing utility function if the following is true:

$X\succeq_{FSD}Y\Leftrightarrow$ $\forall u:\forall{v}:P(u(X)>u({v}))\geq
P(u(Y)>u({v})).$

In MORL, the return from the reward function is a vector, where each element
in the return vector represents an objective. To apply FSD to MORL under the
ESR criterion, random vectors must be considered. In this case, a random
vector (or multi-variate random variable) is a vector whose components are
scalar-valued random variables on the same probability space. For simplicity,
this paper focuses on the case in which a random vector has two random
variables, known as the bi-variate case. FSD conditions have been proven to
hold for random vectors with $n$ random variables in the works of
Sriboonchitta et al. [30], Levhari et al. [31], Nakayama et al. [32] and
Scarsini [33]. In Theorem 3, the work of Atkinson and Bourguignon [34] is
distilled into a suitable Theorem for MORL. Theorem 3 highlights how the
conditions for FSD hold for random vectors when optimising under the ESR
criterion for a monotonically increasing utility function, $u$, where
$\frac{\partial^{2}u(x_{1},x_{2})}{\partial x_{1}\partial x_{2}}\leq 0$ [35].
It is important to note Atikson and Bourguignon [34] have shown the conditions
for FSD hold for random vectors for utility functions where
$\frac{\partial^{2}u(x_{1},x_{2})}{\partial x_{1}\partial x_{2}}\geq 0$. We
plan to extend these conditions for MORL in a future work. In Theorem 3, X and
Y are random vectors where each random vector consists of two random
variables, $\textbf{X}=[X_{1},X_{2}]$ and $\textbf{Y}=[Y_{1},Y_{2}]$.
$F_{{X_{1}X{{}_{2}}}}$ and $F_{Y_{1}Y_{2}}$ are the corresponding CDFs.

###### Theorem 3

Assume that $u\ :\ \mathbb{R}_{\geq 0}\times\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ is a monotonically increasing function, with
$\frac{\partial u(x_{1},x_{2})}{\partial x_{1}}\geq 0$, $\frac{\partial
u(x_{1},x_{2})}{\partial x_{2}}\geq 0$ and
$\frac{\partial^{2}u(x_{1},x_{2})}{\partial x_{1}\partial x_{2}}\leq 0$. If,
for random vectors $\mathbf{X}$ and $\mathbf{Y}$,
$\mathbf{X}\succeq_{FSD}\mathbf{Y}$, then $\mathbf{X}$ is preferred to
$\mathbf{Y}$ by all decision makers, i.e.,

$\mathbf{X}\succeq_{FSD}\mathbf{Y}\implies\mathbb{E}(u(\mathbf{X}))\geq\mathbb{E}(u(\mathbf{Y}))$

###### Proof 3

As $\mathbf{X}\succeq_{FSD}\mathbf{Y}$, $\forall t,z$ we have

$\begin{split}&F_{\mathbf{X}}(t,z)\leq F_{\mathbf{Y}}(t,z),\\\ \text{or
}&\Delta_{F}(t,z)=F_{\mathbf{X}}(t,z)-F_{\mathbf{Y}}(t,z)\leq 0.\end{split}$

The expected utility of the random variable $\mathbf{X}$ can be written as
follows:

$\mathbb{E}\left(u(\textbf{X})\right)=\int^{\infty}_{0}\int^{\infty}_{0}u(t,z)f_{\mathbf{X}}(t,z)dtdz,$

where $f$ is the probability density function of X. Note that

$\begin{split}\Delta_{f}(t,z)&=f_{\mathbf{X}}(t,z)-f_{\mathbf{Y}}(t,z)\\\
&=\frac{\partial^{2}\Delta_{F}(t,z)}{\partial t\partial z}.\end{split}$

Using integration-by-parts (I), and the fact that
$\Delta_{F}(t,0)=\frac{\partial\Delta_{F}(0,z)}{\partial z}=0$ (Z), we obtain:

$\begin{split}&\mathbb{E}\left(u(\textbf{X})\right)-\mathbb{E}\left(u(\textbf{Y})\right)\\\
&=\int^{\infty}_{0}\int^{\infty}_{0}u(t,z)\Delta_{f}(t,z)dtdz\\\
&\stackrel{{\scriptstyle(I)}}{{=}}\int^{\infty}_{0}\left[u(t,z)\frac{\partial\Delta_{F}(t,z)}{\partial
z}\right]^{\infty}_{t=0}dz-\int^{\infty}_{0}\int^{\infty}_{0}\frac{\partial
u(t,z)}{\partial t}\frac{\partial\Delta_{F}(t,z)}{\partial z}dtdz\end{split}$
$\begin{split}&\stackrel{{\scriptstyle(I)}}{{=}}\int^{\infty}_{0}\left[u(t,z)\frac{\partial\Delta_{F}(t,z)}{\partial
z}\right]^{\infty}_{t=0}dz-\int^{\infty}_{0}\left[\frac{\partial
u(t,z)}{\partial t}\Delta_{F}(t,z)\right]^{\infty}_{z=0}dt+\\\
&\int^{\infty}_{0}\int^{\infty}_{0}\frac{\partial^{2}u(t,z)}{\partial
t\partial z}\Delta_{F}(t,z)dtdz\\\ \end{split}$
$\begin{split}&\stackrel{{\scriptstyle(Z)}}{{=}}\int^{\infty}_{0}\lim_{t\rightarrow\infty}u(t,z)\frac{\partial\Delta_{F}(t,z)}{\partial
z}dz-\int^{\infty}_{0}\lim_{z\rightarrow\infty}\frac{\partial u(t,z)}{\partial
t}\Delta_{F}(t,z)dt+\\\
&\int^{\infty}_{0}\int^{\infty}_{0}\frac{\partial^{2}u(t,z)}{\partial
t\partial z}\Delta_{F}(t,z)dtdz.\end{split}$

Given that $\frac{\partial^{2}u(t,z)}{\partial t\partial z}\leq 0$,
$\frac{\partial u(t,z)}{\partial t}\geq 0$ and $\Delta_{F}(t,z)\leq 0$, we
know that the last two terms are positive. Therefore, we can state that

$\begin{split}&\mathbb{E}\left(u(\textbf{X})\right)-\mathbb{E}\left(u(\textbf{Y})\right)\\\
&=\int^{\infty}_{0}\lim_{t\rightarrow\infty}u(t,z)\frac{\partial\Delta_{F}(t,z)}{\partial
z}dz-\int^{\infty}_{0}\lim_{z\rightarrow\infty}\frac{\partial u(t,z)}{\partial
t}\Delta_{F}(t,z)dt+\\\ \end{split}$
$\begin{split}&\int^{\infty}_{0}\int^{\infty}_{0}\frac{\partial^{2}u(t,z)}{\partial
t\partial
z}\Delta_{F}(t,z)dtdz\geq\int^{\infty}_{0}\lim_{t\rightarrow\infty}u(t,z)\frac{\partial\Delta_{F}(t,z)}{\partial
z}dz.\end{split}$

According to Lemma 2 (see Section 10), as $u(t,z)F(t,z)$ is a positive
monotonically increasing function in both $t$ and $z$, we know that:

$\begin{split}&\int^{\infty}_{0}\lim_{t\rightarrow\infty}u(t,z)\frac{\partial
F(t,z)}{\partial
z}dz=\lim_{t\rightarrow\infty}\int^{\infty}_{0}u(t,z)\frac{\partial
F(t,z)}{\partial z}dz.\\\ \end{split}$

Using integration-by-parts (I), and the fact that $\Delta_{F}(t,0)=0$ (Z), we
have:

$\begin{split}&\mathbb{E}\left(u(\textbf{X})\right)-\mathbb{E}\left(u(\textbf{Y})\right)\\\
&\geq\lim_{t\rightarrow\infty}\int^{\infty}_{0}u(t,z)\frac{\partial\Delta_{F}(t,z)}{\partial
z}dz\\\
&\stackrel{{\scriptstyle(I)}}{{=}}\lim_{t\rightarrow\infty}\left[u(t,z)\Delta_{F}(t,z)\right]^{\infty}_{0}-\lim_{t\rightarrow\infty}\int^{\infty}_{0}\frac{\partial
u(t,z)}{\partial z}\Delta_{F}(t,z)dz\\\
&\stackrel{{\scriptstyle(Z)}}{{=}}\lim_{t\rightarrow\infty}\lim_{z\rightarrow\infty}u(t,z)\Delta_{F}(t,z)-\lim_{t\rightarrow\infty}\int^{\infty}_{0}\frac{\partial
u(t,z)}{\partial z}\Delta_{F}(t,z)dz.\\\ \end{split}$

Finally, given that $\frac{\partial u(t,z)}{\partial z}\geq 0$ and
$\Delta_{F}(t,z)\leq 0$, we know that:

$\begin{split}&\mathbb{E}\left(u(\textbf{X})\right)-\mathbb{E}\left(u(\textbf{Y})\right)\\\
&\geq\lim_{t\rightarrow\infty}\lim_{z\rightarrow\infty}u(t,z)\Delta_{F}(t,z)-\lim_{t\rightarrow\infty}\int^{\infty}_{0}\frac{\partial
u(t,z)}{\partial z}\Delta_{F}(t,z)dz\\\ &\geq 0\end{split}$

Using the results from Theorem 3, Equation 11 can be updated to include random
vectors,

$P(u(\textbf{X})>u(\textbf{z}))\geq P(u(\textbf{Y})>u(\textbf{z})).$ (12)

###### Definition 3

For random vectors X and Y, X is preferred over Y by all decision makers with
a monotonically increasing utility function if, and only if, the following is
true:

$\textbf{X}\succeq_{FSD}\textbf{Y}\Leftrightarrow$ $\forall
u:(\forall{\textbf{v}}:P(u(\textbf{X})>u({\textbf{v}}))\geq
P(u(\textbf{Y})>u({\textbf{v}}))$

Using the results from Theorem 3 and Definition 3, it is possible to extend
FSD to MORL. For MORL, under the ESR criterion, the return distribution,
$\textbf{Z}^{\pi}$, is considered to be the full distribution of the returns
of a random vector received when executing a policy, $\pi$ (see Section 3),
return distributions can be used to represent policies. In this case, it is
possible to use FSD to obtain a partial ordering over policies. For example,
consider two policies, $\pi$ and $\pi^{\prime}$, where each policy has the
underlying return distribution $\textbf{Z}^{\pi}$ and
$\textbf{Z}^{\pi^{\prime}}$. If
$\textbf{Z}^{\pi}\,\succeq_{FSD}\textbf{Z}^{\pi^{\prime}}$ then $\pi$ will be
preferred over $\pi^{\prime}$.

###### Definition 4

Policies $\pi$ and $\pi^{\prime}$ have return distributions $\textbf{Z}^{\pi}$
and $\textbf{Z}^{\pi^{\prime}}$. Policy $\pi$ is preferred over policy
$\pi^{\prime}$ by all decision makers with a utility function, $u$, that is
monotonically increasing if, and only if, the following is true:

$\textbf{Z}^{\pi}\succeq_{FSD}\textbf{Z}^{\pi^{\prime}}.$

Now that a partial ordering over policies has been defined under the ESR
criterion for the unknown utility function scenario, it is possible to define
a set of optimal policies.

##  5 Solution Sets for ESR

Section 4 defines a partial ordering over policies under the ESR criterion for
unknown utility functions using FSD. In the unknown utility function scenario,
it is infeasible to learn a single optimal policy [3]. When a user’s utility
function is unknown, multi-policy MORL algorithms must be used to learn a set
of optimal policies. To apply MORL to the ESR criterion in scenarios with
unknown utility, a set of optimal policies under the ESR criterion must be
defined. In Section 5, FSD is used to define multiple sets of optimal policies
for the ESR criterion.

Firstly, a set of optimal policies, known as the undominated set, is defined.
The undominated set is defined using FSD, where each policy in the undominated
set has an underlying return distribution that is FSD dominant. The
undominated set contains at least one optimal policy for all possible
monotonically increasing utility functions.

###### Definition 5

The undominated set, $U(\Pi)$, is a sub-set of all possible policies for where
there exists some utility function, $u$, where a policy’s return distribution
is FSD dominant.

$U(\Pi)=\left\\{\pi\in\Pi\ \middle|\ \exists
u,\forall\pi^{\prime}\in\Pi:\textbf{Z}^{\pi}\succeq_{FSD}\textbf{Z}^{\pi^{\prime}}\right\\}$

However, the undominated set may contain excess policies. For example, under
FSD, if two dominant policies have return distributions that are equal, then
both policies will be in the undominated set. Given both return distributions
are equal, a user with a monotonically increasing utility function will not
prefer one policy over the other. In this case, both policies have the same
expected utility. To reduce the number of policies that must be considered at
execution time, for each possible utility function we can keep just one
corresponding FSD dominant policy; such a set of policies is called a coverage
set (CS).

###### Definition 6

The coverage set, $CS(\Pi)$, is a subset of the undominated set, $U(\Pi)$,
where, for every utility function, $u$, the set contains a policy that has a
FSD dominant return distribution,

$CS(\Pi)\subseteq U(\Pi)\wedge\left(\forall u,\exists\pi\in
CS(\Pi),\forall{\pi^{\prime}\in\Pi}:\mathbf{Z}^{\pi}\succeq_{FSD}\mathbf{Z}^{\pi^{\prime}}\right)$

In practice, a decision maker may aim to learn the smallest possible set of
optimal policies. However, FSD considered in this work does not have a strict
inequality condition. Moreover, the undominated set generated using FSD may
contain excess policies. Therefore, to compute a coverage set in practice
where each optimal policy has a unique return distribution, we define expected
scalarised returns dominance (ESR dominance). In contrast to FSD, ESR
dominance ensures that an explicitly strict inequality exists.

###### Definition 7

For random vectors X and Y, X $\succ_{ESR}$ Y for all decision makers with a
monotonically increasing utility function if, and only if, the following is
true:

$\textbf{X}\succ_{ESR}\textbf{Y}\Leftrightarrow$ $\forall
u:(\forall{\textbf{v}}:P(u(\textbf{X})>u({\textbf{v}}))\geq
P(u(\textbf{Y})>u({\textbf{v}}))$
$\wedge\exists\,\textbf{v}:P(u(\textbf{X})>u({\textbf{v}}))>P(u(\textbf{Y})>u({\textbf{v}}))).$

ESR dominance (Definition 7) extends FSD, however, ESR dominance is a more
strict dominance criterion. For FSD, policies that have equal return
distributions are considered dominant policies, which is not the case under
ESR dominance. Therefore, if a random vector is ESR dominant, the random
vector has a greater expected utility than all ESR dominated random vectors.
Theorem 4 proves that ESR dominance satisfies the ESR criterion when the
utility function of the user is unknown for all monotonically increasing
utility functions. Theorem 4 focuses on random vectors X and Y where each
random vector has two random variables, such that $\textbf{X}=[X_{1},X_{2}]$
and $\textbf{Y}=[Y_{1},Y_{2}]$. $F_{\textbf{X}}$ and $F_{\textbf{Y}}$ are the
corresponding CDFs and $\textbf{v}=[t,z]$. However, Theorem 4 can easily be
extended for random vectors with $n$ random variables
($\textbf{X}=[X_{1},X_{2},...,X_{n}]$).

###### Theorem 4

A random vector, X, is preferred to a random vector, Y, by all decision makers
with a monotonically increasing utility function if, and only if, X
$\geq_{ESR}$ Y:

$\textbf{X}\succ_{ESR}\textbf{Y}\implies\mathbb{E}(u(\textbf{X}))>\mathbb{E}(u(\textbf{Y}))$

###### Proof 4

X and Y are random vectors with $n$ random variables. If X $\succ_{ESR}$ Y the
following two conditions must be met for all $u$:

  1. 1.

$\forall{\textbf{v}}:P(u(\textbf{X})>u({\textbf{v}}))\geq
P(u(\textbf{Y})>u({\textbf{v}}))$

  2. 2.

$\exists\,\textbf{v}:P(u(\textbf{X})>u({\textbf{v}}))>P(u(\textbf{Y})>u({\textbf{v}}))$

From Definition 3, if X $\succeq_{FSD}$ Y then the following is true:

$\forall u:\forall{\textbf{v}}:P(u(\textbf{X})>u({\textbf{v}}))\geq
P(u(\textbf{Y})>u({\textbf{v}}))$

If X $\succeq_{FSD}$ Y, then, from Theorem 3, the following is true:

$\mathbb{E}(u(\textbf{X}))\geq\mathbb{E}(u(\textbf{Y}))$

If condition $1$ is satisfied, the expected utility of X is at least equal to
the expected utility of Y, then:

$\mathbb{E}(u(\textbf{X}))=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}u(\textbf{z})f_{\textbf{X}}(t,z)\,dt\,dz$
$\mathbb{E}(u(\textbf{Y}))=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}u(\textbf{z})f_{\textbf{Y}}(t,z)\,dt\,dz$

In order to satisfy condition 2, some limits must exist to give the following,

$\int_{a}^{b}\int_{c}^{d}u(t,z)f_{\textbf{X}}(t,z)\,dt\,dz>\int_{a}^{b}\int_{c}^{d}u(t,z)f_{\textbf{Y}}(t,z)\,dt\,dz$

The minimum requirement to satisfy condition 1 is:

$\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}u(t,z)f_{\textbf{X}}(t,z)\,dt\,dz=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}u(t,z)f_{\textbf{Y}}(t,z)\,dt\,dz$

If condition 1 is satisfied, to satisfy condition 2 some limits must exist:

$\int_{a}^{b}\int_{c}^{d}u(t,z)f_{\textbf{X}}(t,z)\,dt\,dz>\int_{a}^{b}\int_{c}^{d}u(t,z)f_{\textbf{Y}}(t,z)\,dt\,dz.$

Therefore,

$\int_{-\infty}^{a}\int_{-\infty}^{c}u(t,z)f_{\textbf{X}}(t,z)\,dt\,dz\,+\int_{a}^{b}\int_{c}^{d}u(t,z)f_{\textbf{X}}(t,z)\,dt\,dz\,+$
$\int_{b}^{\infty}\int_{d}^{\infty}u(t,z)f_{\textbf{X}}(t,z)\,dt\,dz>\int_{-\infty}^{a}\int_{-\infty}^{c}u(t,z)f_{\textbf{Y}}(t,z)\,dt\,dz\,+$
$\int_{a}^{b}\int_{c}^{d}u(t,z)f_{\textbf{Y}}(t,z)\,dt\,dz\,+\int_{b}^{\infty}\int_{d}^{\infty}u(t,z)f_{\textbf{Y}}(t,z)\,dt\,dz.$

Finally,

$\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}u(t,z)f_{\textbf{X}}(t,z)\,dt\,dz>\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}u(t,z)f_{\textbf{Y}}(t,z)\,dt\,dz$

if X $\succ_{ESR}$ Y, then,

$\mathbb{E}(u(\textbf{X}))>\mathbb{E}(u(\textbf{Y})).$

In the ESR dominance criterion defined in Definition 7, the utility of
different vectors is compared. However, it is not possible to calculate the
utility of a vector when the utility function is unknown. In this case, Pareto
dominance [36] can be used instead to determine the relative utility of the
vectors being compared.

###### Definition 8

A Pareto dominates ($\succ_{p}$) B if the following is true:

$\mathbf{A}\succ_{p}\mathbf{B}\Leftrightarrow(\forall
i:\mathbf{A}_{i}\geq\mathbf{B}_{i})\land(\exists
i:\mathbf{A}_{i}>\mathbf{B}_{i}).$ (13)

For monotonically increasing utility functions, if the value of an element of
the vector increases, then the scalar utility of the vector also increases.
Therefore, using Definition 8, if vector $\mathbf{A}$ Pareto dominates vector
$\mathbf{B}$, for a monotonically increasing utility function, $\mathbf{A}$
has a higher utility than $\mathbf{B}$. To make ESR comparisons between return
distributions, Pareto dominance can be used.

###### Definition 9

For random vectors X and Y, X $\succ_{ESR}$ Y for all monotonically increasing
utility functions if, and only if, the following is true:

$\textbf{X}\succ_{ESR}\textbf{Y}\Leftrightarrow$ $\forall{\bf v}:P({\bf
X}>_{P}{\bf v})\geq P({\bf Y}>_{P}{\bf v})\wedge\exists{\bf v}:P({\bf
X}>_{P}{\bf v})>P({\bf Y}>_{P}{\bf v}).$

It is also possible to calculate ESR dominance by comparing the CDFs of random
vectors. Using the CDF guarantees a higher expected utility. Using the CDF we
compare the cumulative probabilities for a given vector, where a lower
cumulative probability is preferred. ESR dominance with the CDF does not
require any information about the utility function of a user and therefore can
be used in the unknown utility function scenario.

###### Definition 10

For random vectors X and Y, X $\succ_{ESR}$ Y for all monotonically increasing
utility functions if, and only if, the following is true:

$\textbf{X}\succ_{ESR}\textbf{Y}\Leftrightarrow$ $\forall{\bf
v}:F_{\textbf{X}}({\bf v})\leq F_{\textbf{Y}}({\bf v})\wedge\exists{\bf
v}:F_{\textbf{X}}({\bf v})<F_{\textbf{Y}}({\bf v}).$

Therefore, we can use either Definition 9 or Definition 10 to calculate ESR
dominance to give a partial ordering over policies.

###### Definition 11

For return distributions $\textbf{Z}^{\pi}$ and $\textbf{Z}^{\pi^{\prime}}$
for policies $\pi$ and $\pi^{\prime}$, $\pi$ is preferred over $\pi^{\prime}$
by all decision makers with a monotonically increasing utility function if,
and only if, the following is true:

$\textbf{Z}^{\pi}\succ_{ESR}\textbf{Z}^{\pi^{\prime}}$

Using ESR dominance, it is possible to define a set of optimal policies, known
as the _ESR set_.

###### Definition 12

The _ESR set_ , $ESR(\Pi)$, is a sub-set of all policies where each policy in
the _ESR set_ is ESR dominant,

$ESR(\Pi)=\\{\pi\in\Pi\ |\
\nexists\pi^{\prime}\in\Pi:\mathbf{Z}^{\pi^{\prime}}\succ_{ESR}\mathbf{Z}^{\pi}\\}.$
(14)

The _ESR set_ is a set of non-dominated policies, where each policy in the
_ESR set_ is ESR dominant. The _ESR set_ can be considered a coverage set,
given no excess policies exist in the _ESR set_. It is viable for a multi-
policy MORL method to use ESR dominance to construct the _ESR set_.

##  6 Multi-Objective Tabular Distributional Reinforcement Learning

Traditionally in the MORL literature, multi-objective methods learn a set of
optimal solutions when the utility function of a user is unknown or hard to
specify [3, 5]. The current MORL literature focuses only on methods which
learn the optimal set of policies under the SER criterion [26, 25]. As already
highlighted, the ESR criterion has largely been ignored by the MORL community,
with a few exceptions [7, 12, 37]. In Section 6 we address this research gap
and we present a novel multi-objective tabular distributional reinforcement
learning (MOTDRL) algorithm that learns an optimal set of policies for the ESR
criterion, also known as the _ESR set_ , for multi-objective multi-armed
bandit (MOMAB) problems.

MOTDRL learns the return distribution for a policy by sampling each available
arm in a MOMAB setting and maintains a multivariate distribution over the
returns received. Given MOTDRL only considers MOMAB problem domains, MOTDRL
maintains a distribution per arm and updates the distribution after each
timestep with the return vector received from executing the sampled arm. When
optimising under the ESR criterion it is critical that a MORL method learns
the underlying distribution over the returns. Other distributional MORL
methods, such as bootstrap Thompson sampling [12], cannot be used to learn a
set of optimal policies under the ESR criterion when the utility function is
unknown. Such methods learn a distribution over the mean returns. In scenarios
where the utility function is unknown or unavailable, such methods would
invalidate the ESR criterion as a distribution over mean return vectors would
be computed. Given a distribution must be used when learning the _ESR set_ ,
new distributional MORL methods must be formulated to learn the underlying
return distributions.

MOTDRL can learn the underlying return distribution for an arm by maintaining
a tabular representation of the underlying multivariate distribution. To
maintain a tabular representation of a multivariate distribution we initialise
a $Z$-table for each arm where the $Z$-table has an axis per objective. The
$Z$-table maintains a count of the number of times a return vector is received
for a given arm. The size of each $Z$-table is initialised using the
parameters $\textbf{R}_{min}$ and $\textbf{R}_{max}$ which are the minimum and
maximum returns obtainable for any of the objectives in the given environment.
Therefore, each axis in the $Z$-table will use $\textbf{R}_{min}$ and
$\textbf{R}_{max}$ to define the length of the axis, where each index value of
the $Z$-table is initialised to $0$. Using $\textbf{R}_{min}$ and
$\textbf{R}_{max}$ as initialisation parameters, a $Z$-table can be
constructed which contains an index for all possible return vectors in a given
problem domain. Figure 3 visualises an initialised $Z$-table for a multi-
objective problem with two objectives where $\textbf{R}_{min}$ = 0 and
$\textbf{R}_{max}$ = 5.

Z | $x_{2}=0$ | $x_{2}=1$ | $x_{2}=2$ | $x_{2}=3$ | $x_{2}=4$ | $x_{2}=5$
---|---|---|---|---|---|---
$x_{1}=0$ | 0 | 0 | 0 | 0 | 0 | 0
$x_{1}=1$ | 0 | 0 | 0 | 0 | 0 | 0
$x_{1}=2$ | 0 | 0 | 0 | 0 | 0 | 0
$x_{1}=3$ | 0 | 0 | 0 | 0 | 0 | 0
$x_{1}=4$ | 0 | 0 | 0 | 0 | 0 | 0
$x_{1}=5$ | 0 | 0 | 0 | 0 | 0 | 0
Figure 3: An illustration of an initialised $Z$-table for a problem domain
with two objectives, $x_{1}$ and $x_{2}$, with each index value set to 0.

1 Input \- arm, $i$

2 Require \- $Z$-table for arm, $i$, $Z_{i}$

3 Pull arm, $i$, and observe return, R.

4 $Z_{i}($R$)$ = $Z_{i}($R$)$ \+ 1

5 $N_{i}$ = $N_{i}$ \+ 1

return $Z$-table, $Z_{i}$.

Algorithm 1 $Z$-table Update

Each $Z$-table can be used to calculate the return distribution of an arm,
which can be considered as a policy $\pi$, $\textbf{Z}^{\pi}$ (see Section 3).
At each timestep, $t$, the returns, R, received from pulling arm, $i$, are
used to update the $Z$-table. The $Z$-table is used to maintain a count of the
number of times the return, R, is received. In MOMAB problem domains, the
returns received from the execution of an arm represent the full returns of
the execution of a policy. To update the $Z$-table, the value at the index
corresponding to the return R is incremented by one. To correctly calculate
the probability of receiving return R when pulling arm $i$, a counter,
$N_{i}$, which represents the number of times arm $i$ has been pulled, must be
maintained. Each time arm $i$ is pulled, the counter $N_{i}$ is incremented by
one. Algorithm 1 outlines how the $Z$-table for each arm is updated.

MOTDRL is a multi-policy algorithm that can learn the ESR set using ESR
dominance. Using ESR dominance a partial ordering over policies can be
determined when the utility function of a user is unknown. Algorithm 2
outlines how MOTDRL learns the ESR set when the utility function of a user in
unknown in a MOMAB problem domain. In Algorithm 2 $\mathcal{A}$ is defined as
a set of available arms, the ESR set is defined as $E$, $D$ is the number of
objectives, $n$ is the total number of pulls across all arms, $N_{l}$ and
$N_{i}$ are the number of pulls of arms $j$ and $i$, and $|E^{*}|$ is the
cardinality of the ESR set, which is known a priori. When learning, the MOTDRL
algorithm has priori knowledge of $\mathcal{A}$, $\textbf{R}_{max}$ and
$\textbf{R}_{min}$. The agent must has knowledge of $\textbf{R}_{max}$ and
$\textbf{R}_{min}$ so the Z-table can be correctly initialised and the agent
must know the number of arms in $\mathcal{A}$ for action selection.

1Pull each arm $i$ in $\mathcal{A}$, $\beta$ times

2 Z-table Update(i) $\forall$ i $\in$ $\mathcal{A}$

3 repeat

4 Find $E$ such that $\forall$ i $\in$ $E$, $\forall$ $j$

5
$\textbf{Z}^{j}+\sqrt{\frac{2ln(n\sqrt[4]{D|E^{*}|})}{N_{j}}}\nsucc_{ESR}\textbf{Z}^{i}+\sqrt{\frac{2ln(n\sqrt[4]{D|E^{*}|})}{N_{i}}}$

6 Select arm a uniform randomly from $E$

7 Z-table Update(i)

8until  _stopping condition is met_ ;

Algorithm 2 Multi-Objective Tabular Distributional Reinforcement Learning

On initialisation each arm is pulled $\beta$ times. The hyperparameter $\beta$
is selected to ensure each arm is pulled sufficiently to build an initial
distribution. For optimal performance $\beta$ is set to greater than $1$. For
$\beta$ greater than $1$, MOTDRL can build a sufficient initial distribution
and can then efficiently explore each arm with the UCB1 statistic. At each
timestep, the return distribution of the policies associated with the
execution of each arm is calculated. The ESR set, $E$, is then calculated from
the resulting return distributions. Therefore, for all the non-optimal arms
$l\not\in E$, there exists an ESR dominant arm $i\in E$ that ESR dominates the
arm $l$.

To calculate ESR dominance required in Algorithm 2 at Line 2, it is critical
to compute both the PDF and CDF of the underling return distribution of a
policy. The PDF can be calculated by computing the probability of receiving
individual returns. Combining the $Z$-table and $N$ for an arm, $i$, it is
possible to compute the probability of receiving each return in a given
problem domain, since the following is true:

$f_{\textbf{X}}(x_{1},x_{2},...,x_{n})=P(\textbf{X}=x_{1},\textbf{X}=x_{2},...,\textbf{X}=x_{n})=\frac{Z_{i}(x_{1},x_{2},...,x_{n})}{N_{i}}$
(15)

Once the PDF has been computed using Equation 15, it is possible to compute
the CDF. Since the following is true:

$\begin{split}F_{\textbf{X}}(x_{1},x_{2},...,x_{n})=&P(\textbf{X}\leq
x_{1},\textbf{X}\leq x_{2},...,\textbf{X}\leq x_{n})\\\ =&\sum_{x_{a}\leq
x_{1}}\sum_{x_{b}\leq x_{2}}...\sum_{x_{k}\leq
x_{n}}P(\textbf{X}=x_{a},\textbf{X}=x_{b},...,\textbf{X}=x_{k})\\\
=&\sum_{x_{a}\leq x_{1}}\sum_{x_{b}\leq x_{2}}...\sum_{x_{k}\leq
x_{n}}\frac{Z_{i}(x_{a},x_{b},...,x_{k})}{N_{i}}\end{split}$ (16)

Using the PDF and the CDF of a return distribution it is possible to calculate
ESR dominance using Definition 9 or Definition 10. Both methods can be used to
calculate ESR dominance.

To efficiently explore all available arms, MOTDRL uses the UCB1 statistic
presented by Drugan et al. [13]. MOTDRL uses UCB1 to transform the PDF of the
underlying return distribution. MOTDRL tranforms the PDF by adding the UCB1
statistic, computed at Line 2 in Algorithm 2, to the PDF. By summing the UCB1
statistic and the PDF, the PDF is shifted relative to the value of the
computed UCB1 statistic. The CDF can then calculated based on the transformed
PDF and ESR dominance can then be computed.

Transforming the PDF using the UCB1 statistic ensures that there is sufficient
exploration of all available arms during experimentation. However, as the
number of pulls of a given arm increases the UCB1 statistic decreases, which
decreases exploration. Over time the UCB1 statistic’s effect on the PDF and
CDF becomes negligible. At such a point, MOTDRL can exploit the return
distributions learned during exploration and compute the ESR set.

Given MOTDRL is a multi-policy algorithm, MOTDRL can be used in the unknown
utility function scenario (see Figure 1). During the learning phase MOTDRL
learns the ESR set by utilising the steps in Algorithm 2. In Section 7 we
deploy MOTDRL in two multi-objective multi-armed bandit settings to show
MOTDRL can learn the ESR set. It is important to note that the experiments
presented only consider the learning phase.

##  7 Experiments

In order to evaluate the MOTDRL algorithm, we evaluate MOTDRL in multiple
settings 444It is important to note for each experiment the results of the
learning phase is presented where and a set of optimal policies is computed.
The selection phase and execution phase are not included in the evaluation of
MOTDRL.. Before experimentation we define a metric that can be used to
evaluate the performance of multi-policy ESR methods. We then evaluate MOTDRL
in a multi-objective multi-armed bandit setting. Finally, we define a new
multi-objective multi-armed bandit problem domain known as the Vaccine
Recommender System (VRS) environment and evaluate MOTDRL using the VRS
environment.

###  7.1 Evaluation Metrics

The standard metrics for MORL [4, 38, 39] are not suitable to evaluate a
multi-policy method under the ESR criterion since they are designed to
specifically evaluate SER methods. To evaluate MORL algorithms under the ESR
criterion, we adapt the coverage ratio metric used by Yang et al. [39] for the
ESR criterion. The coverage ratio evaluates the agent’s ability to recover
optimal solutions in the ESR set ($E$). If $\mathcal{F}\subseteq{R}^{m}$ is
the set of solutions found by the agent, we define the following:

$\mathcal{F}\cap_{\epsilon}E:=\\{Z^{\pi}\in\mathcal{F}\,|\,\exists
Z^{\pi^{\prime}}\in
E\,s.t\,\sup\limits_{\textbf{x}}|F_{Z^{\pi}}(\textbf{x})-F_{Z^{\pi^{\prime}}}(\textbf{x})\,|\leq\epsilon\\},$
(17)

where $\textbf{x}=[x_{1},x_{2},...,x_{D}]$ and $D$ is equal to the number of
objectives. Equation 17 uses the Kolmogorov–Smirnov statistic [40] (Equation
18), where $\sup\limits_{\textbf{x}}$ is the supremum of the set of distances.
The Kolmogorov–Smirnov statistic takes the largest absolute difference between
the two CDFs across all x values,

$\sup\limits_{\textbf{x}}|F_{Z^{\pi}}(\textbf{x})-F_{Z^{\pi^{\prime}}}(\textbf{x})|.$
(18)

The Kolmogorov–Smirnov statistic returns a minimum value of $0$ and a maximum
value of $1$. If two CDFs are equal then the Kolmogorov–Smirnov statistic will
return a value of $0$.

The coverage ratio is then defined as:

$F_{1}=2\cdot\frac{precision\cdot recall}{precision+recall},$ (19)

where precision $=|\mathcal{F}\cap_{\epsilon}E|/|\mathcal{F}|$ indicating the
fraction of optimal solutions among the retrieved solutions, and the recall
$=|\mathcal{F}\cap_{\epsilon}E|/|E|$ indicating the fraction of optimal
instances that have been retrieved over the total amount of optimal solutions
[39].

###  7.2 Multi-Objective Multi-Armed Bandit Environment

In Section 7.2 we evaluate MOTDRL in a MOMAB setting. To evaluate MOTDRL, we
consider a bi-objective MOMAB with five arms. Table 3 outlines the number of
possible outcomes obtainable when selecting a given arm and the corresponding
probabilities. Table 3 is unknown to the agent, and the agent aims to learn
each distribution per arm and prune the ESR dominated arms from consideration.
In the MOMAB setting the ESR set is known a priori where the return
distributions for $arm_{1}$ and $arm_{5}$ are ESR dominant and therefore the
ESR set only contains $arm_{1}$ and $arm_{5}$.

To evaluate MOTDRL in a MOMAB environment we set $R_{min}=0$, $R_{max}=10$,
$D$ = 2, $\beta$ = 5 and $|E^{*}|$ = 2. To compute the coverage ratio we set
$\epsilon=0.01$. All experiments in this setting are averaged over 10 runs.

$arm_{1}$
---
P(Arm 1 = R) | R
0.4 | (0, 1)
0.6 | (5, 4)

$arm_{2}$
---
P(Arm 2 = R) | R
0.85 | (1, 0)
0.15 | (3, 2)

$arm_{3}$
---
P(Arm 3= R) | R
0.75 | (2, 0)
0.25 | (4, 2)

$arm_{4}$
---
P(Arm 4 = R) | R
0.8 | (0, 1)
0.2 | (1, 2)

$arm_{5}$
---
P(Arm 5 = R) | R
0.7 | (2, 0)
0.3 | (4, 5)

Table 3: A MOMAB with 5 arms where selecting an arm has two outcomes and two
objectives. Figure 4: Results from the MOMAB environment. MOTDRL is able to
learn the ESR set as MOTDRL converges to the optimal coverage ratio since the
$F_{1}$ score reaches the maximum possible value of 1.

MOTDRL is able to learn the underlying return distributions for each arm in
the MOMAB setting. Using the return distributions for each arm, MOTDRL can
learn the ESR set in the MOMAB environment. In Figure 4, we plot the coverage
ratio as the $F_{1}$ score. MOTDRL converges to the optimal $F_{1}$ score of
$1$. MOTDRL converges to the optimal $F_{1}$ score after $100,000$ episodes.
An optimal $F_{1}$ score can only be achieved when all policies in the ESR set
have been learned by the agent.

MOTDRL computes the ESR set for the MOMAB environment during the learning
phase. The learned ESR set contains two arms; $arm_{1}$ and $arm_{5}$. Both
$arm_{1}$ and $arm_{5}$ are ESR dominant therefore any user with a
monotonically increasing utility function would prefer $arm_{1}$ or $arm_{5}$
over all other available arms in the MOMAB problem. MOTDRL will return the ESR
set to the user during the selection phase. In practice, a user will select a
policy form the ESR set which best reflects their preferences and the selected
policy will be executed.

Figure 5: Heatmaps for each return distribution in the ESR set learned by
MOTDRL in the MOMAB environment. The left heatmap describes the return
distribution for $arm_{1}$ learned by MOTDRL and the right heatmap describes
the return distribution for $arm_{5}$ learned by MOTDRL.

Given ESR dominance is a new solution concept, we utilise Figure 5, Figure 6
and Figure 7 to give the reader some intuition about ESR dominance. Figure 5
displays the return distributions in the ESR set learned by MOTDRL as
heatmaps. Each heatmap in Figure 5 corresponds to the probabilities
highlighted for $arm_{1}$ (left) and $arm_{5}$ (right) in Table 3.

Figure 6: CDFs for each policy in the ESR set learned by MOTDRL in the MOMAB
environment. The left figure describes the CDF for $arm_{1}$ learned by MOTDRL
and the right figure describes the CDF for $arm_{5}$ learned by MOTDRL.

Figure 6 displays the CDFs for each return distribution in the ESR set learned
by MOTDRL. The CDF is used to calculate ESR dominance and the CDFs in Figure 6
correspond to the CDFs of $arm_{1}$ (left) and $arm_{5}$ (right) in Table 3.

Figure 7: The CDFs for $arm_{1}$ and $arm_{5}$ intersect at multiple points.
Therefore, as per Definition 7: $arm_{1}$ $\nsucc_{ESR}$ $arm_{5}$ and
$arm_{5}$ $\nsucc_{ESR}$ $arm_{1}$.

Figure 7 describes how $arm_{1}$ $\nsucc_{ESR}$ $arm_{5}$ and $arm_{5}$
$\nsucc_{ESR}$ $arm_{1}$ given the CDFs for $arm_{1}$ and $arm_{5}$ intersect
at multiple points (see Definition 7).

Figure 8: The policies on the Pareto front (left) are different from the
expectations of the policies in the ESR set (right). In this case, a policy
that is in the ESR set is not on the Pareto front. This figure illustrate why
SER methods cannot be used to learn the ESR set.

Figure 8 highlights why the choice of optimality criteria must be take into
consideration for multi-objective decision making when the utility function of
the user is unknown. A number of SER methods use Pareto dominance to determine
a partial ordering over policies. The Pareto dominant policies, or Pareto
front, are then returned to the user. To determine the Pareto front [36] the
expectations of each arm in the MOMAB setting are calculated and the Pareto
dominant policies are determined. In Figure 8 the policies on the Pareto front
(left) have been highlighted in red, all other policies are Pareto dominated.
In the MOMAB environment outlined in Table 3, the Pareto front consists of a
single policy. Figure 8 (right) displays the expected values of the policies
in the ESR set, highlighted in green. By comparing both plots in Figure 8, it
is clear that the ESR set contains an extra policy. Therefore, in some
settings, certain policies that are optimal under the ESR criterion are
dominated under the SER criterion. Figure 8 highlights the importance of
selecting the correct optimality criterion when learning. If SER methods are
used to compute a set of optimal policies in scenarios where the ESR criterion
should be used, it is possible a sub-optimal policy may be selected by the
user at decision time. This may have adverse affects when applying multi-
policy multi-objective methods in real-world decision making settings.

###  7.3 Vaccine Recommender System

To illustrate a potential real-world use case for the ESR criterion and ESR
dominance, we define a new multi-objective multi-armed bandit environment
known as the Vaccine Recommender System. For example, in a medical setting a
doctor may only have one opportunity to select a treatment for a patient. In
this case it is necessary to optimise under the ESR criterion. Consider the
following scenario: a patient is travelling to another country where it is
required to be vaccinated for a specific disease to gain entry to the country.
There are five available vaccines, however, each vaccine will have varying
side effects (safety rating) and effectiveness. This problem has two
objectives: safety and effectiveness. Both objectives are ranked from 0 to 5,
with 0 being the worst rating and 5 being the best rating. None of the
available vaccines are 100$\%$ effective at treating the disease. When taking
each vaccine there is a chance of different outcomes occurring, for example,
there is a chance of having severe side effects (low safety rating) and a
chance of the vaccine providing the required immunity to the disease (high
effectiveness rating). Table 4 outlines each vaccine and the probability of
each outcome occurring after taking the vaccine. Table 4 is unknown to the
agent, and the agent aims to learn each distribution per vaccine and prune the
ESR dominated vaccines from consideration.

Vaccine 1 ($V_{1}$)
---
P($V_{1}$= R) | R
0.05 | (2, 0)
0.05 | (2, 1)
0.1 | (3, 2)
0.8 | (4, 2)

Vaccine 2 ($V_{2}$)
---
P($V_{2}$= R) | R
0.1 | (0, 0)
0.1 | (1, 1)
0.5 | (2, 0)
0.3 | (2, 1)

Vaccine 3 ($V_{3}$)
---
P($V_{3}$= R) | R
0.1 | (1, 0)
0.1 | (1, 3)
0.2 | (3, 4)
0.6 | (5, 4)

Vaccine 4 ($V_{4}$)
---
P($V_{4}$= R) | R
0.1 | (1, 0)
0.4 | (2, 1)
0.4 | (3, 1)
0.1 | (3, 2)

Vaccine 5 ($V_{5}$)
---
P($V_{5}$= R) | R
0.8 | (0, 0)
0.05 | (1, 1)
0.05 | (1, 2)
0.1 | (4, 0)

Table 4: A group of available vaccines that have varying outcomes. Some
vaccines have a higher chance of side effects (low safety rating), while
others are more effective at providing immunity. The objectives are ordered as
follows: R = (safety, effectiveness).

Given the utility function of the user is unknown, the MOTDRL algorithm is
used to learn the underlying return distributions for each vaccine in Table 4
and determine the ESR set. Once MOTDRL has finished learning a set of optimal
polices, in this case the ESR set, is returned to the user. When the user’s
utility function becomes known, a vaccine that maximises the user’s utility
function can be selected from the ESR set by the user.

The ESR set for the Vaccine Recommender System (VRS) environment is known a
priori. The return distributions for $V_{1}$ and $V_{3}$ are ESR dominant and
therefore $V_{1}$ and $V_{3}$ are the only distributions in the ESR set. The
VRS environment has five arms where each arm corresponds to a vaccine in Table
4. To evaluate MOTDRL in a VRS environment, we set $\textbf{R}_{min}=0$,
$\textbf{R}_{max}=10$, $D$ = 2, $\beta$ = 5 and $|E^{*}|$ = 2. All experiments
in this setting are averaged over 10 runs and each experiment lasts $200,000$
episodes. To compute the coverage ratio, we set $\epsilon=0.01$.

Figure 9: Results from the VRS environment. MOTDRL is able to learn the full
ESR set as it converges the optimal $F_{1}$ score of 1.

After sufficient sampling, MOTDRL is able to learn the underlying return
distributions for each arm in the VRS environment. Given return distributions
can be used to give a partial ordering over policies, MOTDRL can use the
return distributions for each arm to compute the ESR set in the VRS
environment. In Figure 9, we plot the coverage ratio as the $F_{1}$ score.
MOTDRL converges to the optimal $F_{1}$ score after $120,000$ episodes. Given
MOTDRL converges to the optimal $F_{1}$ score it is clear MOTDRL is able to
learn the ESR set.

Figure 10: Heatmaps for each policy in the ESR set learned by MOTDRL. The left
heatmap describes the distribution for $V_{1}$ learned by MOTDRL and the right
heatmap describes the distribution for $V_{3}$ learned by MOTDRL.

In practice, once learning has completed, MOTDRL returns the learned ESR set
for the VRS environment to the user. The learned ESR set contains two
vaccines; $V_{1}$ and $V_{3}$. Both vaccines in the ESR set are ESR dominant.
Moreover, a user with a monotonically increasing utility function will prefer
either $V_{1}$ or $V_{3}$ over all other vaccines in the VRS environment.

Similarly to Section 7.2, we utilise Figure 10 and Figure 11 to give the
reader some intuition about ESR dominance. Figure 10 presents heatmaps to
represent the policies in the ESR set learned by MOTDRL. Each heatmap
represents a return distribution learned by MOTDRL and shows the return
vectors and the corresponding probabilities. Each heatmap in Figure 10
corresponds to the probabilities highlighted for $V_{1}$ (left) and $V_{3}$
(right) in Table 4. Figure 11 displays the policies in the ESR set learned by
MOTDRL and their corresponding CDFs. Each CDF in Figure 11 corresponds to the
CDFs of the underlying return distributions of $V_{1}$ and $V_{3}$ in Table 4.

Figure 11: CDFs for each policy in the ESR set learned by MOTDRL in the VRS
environment. The left figure describes the CDF for $V_{1}$ learned by MOTDRL
and the right figure describes the CDF for $V_{3}$ learned by MOTDRL.

##  8 Related Work

The various orders of stochastic dominance have been used extensively as a
method to determine the optimal decision when making decisions under
uncertainty in economics [41], finance [42, 43], game theory [44], and various
other real-world scenarios [45]. However, stochastic dominance has largely
been overlooked in systems that learn. Cook and Jarret [46] use various orders
of stochastic dominance and Pareto dominance with genetic algorithms to
compute optimal solution sets for an aerospace design problem with multiple
objectives when constrained by a computational budget. Martin et al. [47] use
second-order stochastic dominance (SSD) with a single-objective distributional
RL algorithm [23]. Martin et al. [47] use SSD to determine the optimal action
to take at decision time, and this approach is shown to learn good policies
during experimentation.

To learn the ESR set in sequential decision making processes, like MOMDPs, new
distributional MORL methods must be formulated. Distributional Monte Carlo
tree search (DMCTS) is a state-of-the-art ESR method and uses a bootstrap
Thompson sampling method to approximate a posterior distribution over the
returns [12]. However, this method is a single policy method and relies on the
utility function of the user to be known at the time of learning or planning.
DMCTS would invalidate the ESR criterion in the unknown utility function
scenario and would therefore be unable to learn the ESR set. Distributional
methods like the C51 algorithm, proposed by Bellemare et al. [23], could
potentially be used to learn the underlying distribution of a random vector.
However C51 is a single-objective method and defining a multi-objective
version of C51 to learn the ESR set could pose significant challenges.
Replacing the distribution over returns used by C51 with a multi-variate
distribution could cause computation to increase with the number of
objectives. In this case, dedicated multi-objective distributional methods
must be formulated so that it is possible to efficiently learn the ESR set for
the ESR criterion. We highlight this as a new challenge that must be addressed
by the MORL community.

##  9 Conclusion & Future Work

MORL has been highlighted as one of several key challenges that needs to be
addressed in order for RL to be commonly deployed in real-world systems [48].
In order to apply RL to the real world the MORL community must consider the
ESR criterion. However, the ESR criterion has largely been ignored by the MORL
community, with the exception of the works of Roijers et al. [3, 7], Hayes et
al. [12, 49] and Vamplew et al. [37]. The works of Hayes et al. [49, 12] and
Roijers et al. [7] present single-policy algorithms that are suitable to learn
policies under the ESR criterion, however, prior to this work, a formal
definition of the necessary requirements to compute policies under the ESR
criterion had not previously been defined. In Section 3, we outline, through
examples and definitions, the necessary requirements to optimise under the ESR
criterion. The formal definitions outlined in Section 3 ensure that an optimal
policy can be learned when the utility function of the user is known under the
ESR criterion. However, in the real world, a user’s preferences over
objectives (or utility function) may be unknown at the time of learning [3].

Prior to this paper, a suitable solution set for the unknown utility function
scenario under the ESR criterion had not been defined. This long-standing
research gap has restricted the applicability of MORL in real-world scenarios
under the ESR criterion. In Section 4 and Section 5 we define the necessary
solution sets required for multi-policy algorithms to learn a set of optimal
policies under the ESR criterion when the utility function of a user is
unknown. In Section 6 we present a novel multi-policy algorithm, known as
multi-objective tabular distributional reinforcement learning (MOTDRL), that
can learn the ESR set in a MOMAB setting when the utility function of a user
is unknown at the time of learning. In Section 7 we evaluate MOTDRL in two
MOMAB settings and show that MOTDRL can learn the ESR set in MOMAB settings.
This work aims to answer some of the existing research questions regarding the
ESR criterion. Moreover, we aim to highlight the importance of the ESR
criterion when applying MORL to real-world scenarios. In order to successfully
apply MORL to the real world, we must implement new single-policy and multi-
policy algorithms that can learn solutions for non-linear utility functions in
various scenarios.

A promising direction for future work would be to extend the work of Hayes et
al. [12] and the work of Wang and Sebag [25]. It may be possible to build on
the aforementioned works to implement a multi-objective distributional Monte
Carlo tree search algorithm that can learn a set of optimal policies under the
ESR criterion. It is important to note that Hayes et al. [49, 12] use
bootstrap Thompson sampling to approximate a posterior distribution. This
method cannot learn the ESR set when utility function of a user is unknown,
therefore a different distributional method must be used to learn the ESR set.
Although the distributional method used by Hayes et al. [12] cannot be used to
learn the ESR set, this work is still a useful starting point.

Given distributional MORL methods are a new area of research, not much is
known about the computational requirements of maintaining a return
distribution. Therefore, it is important that a comprehensive computational
analysis of distributional MORL methods is undertaken to fully understand the
implications of maintaining a return distribution. In a future publication we
plan to perform a computational analysis for distributional MORL methods in
both bandit and sequential decision making settings.

A lack of well defined benchmarks is a significant challenge associated with
implementing any new single-policy or multi-policy algorithms under the ESR
criterion. Currently, very few ESR benchmark environments exist (e.g. Fishwood
[7]). In order to accurately evaluate single-policy and multi-policy ESR
algorithms, a suite of benchmark problem domains need to be designed. Under
the SER criterion, such benchmarks already exist, e.g. Deep Sea Treasure [4].
It is also important to highlight the need to establish new metrics to
evaluate multi-policy algorithms under the ESR criterion. As previously
mentioned, all metrics used to evaluate multi-objective algorithms are
designed for the SER criterion. In order to accurately evaluate multi-policy
algorithms under the ESR criterion, new metrics must be determined. We note
that extending the work of Zintgraf et al. [38] for the ESR criterion would be
a promising starting point.

##  10 Supplementary Material

###### Lemma 1

(Beppo Levi’s lemma [50]) Consider a point-wise non-decreasing sequence of
positive functions $f_{n}\ :\ X\rightarrow[0,+\infty]$, i.e., for every $k\geq
1$ and every $x\in X$.

$0\leq f_{n}(x)\leq f_{n+1}(x)\leq+\infty$

Set the point-wise limit of the sequence $\\{f_{i}\\}$ to be $f$. That is, for
every $x\in X$,

$\lim_{n\rightarrow+\infty}f_{n}(x)=f(x)$

Then $f$ is measurable and:

$\lim_{n\rightarrow+\infty}\int
f_{n}(x)dx=\int\lim_{n\rightarrow+\infty}f_{n}(x)dx$

###### Lemma 2

(Monotone convergence) Let $u$ be a non-negative monotonically increasing
utility function in $x$ and $y$, and $F$ the CDF of a random variables $X$ and
$Y$. Then,

$\int\lim_{y\rightarrow+\infty}u(x,y)F(x,y)dx=\lim_{y\rightarrow+\infty}\int
u(x,y)F(x,y)dx.$

###### Proof 5

Let $g_{n}(x)=u(x,n)F(x,n)$. As $u$ and $F$ are positive monotonically
increasing functions in $n$, the function $g_{n}$ is also positive and
monotonically increasing, i.e.,

$0\leq g_{n}(x)\leq g_{n+1}(x)\leq+\infty$

According to Beppo Levi’s lemma (see Lemma 1), the limit of the integral of
$g_{n}(x)$ in $x$ is the integral of its limit, i.e.,

$\lim_{n\rightarrow+\infty}\int
g_{n}(x)dx=\int\lim_{n\rightarrow+\infty}g_{n}(x)dx.$

## Acknowledgements

Conor F. Hayes is funded by the National University of Ireland Galway Hardiman
Scholarship. This research was supported by funding from the Flemish
Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI)
Vlaanderen” program.

## Conflict of interest

The authors declare that they have no conflict of interest.

## References

  * [1] Conor F. Hayes, Timothy Verstraeten, Diederik M. Roijers, Enda Howley, and Patrick Mannion.  Dominance criteria and solution sets for the expected scalarised returns.  In Proceedings of the Adaptive and Learning Agents workshop at AAMAS 2021, 2021.
  * [2] Peter Vamplew, Benjamin J Smith, Johan Kallstrom, Gabriel Ramos, Roxana Radulescu, Diederik M Roijers, Conor F Hayes, Fredrik Heintz, Patrick Mannion, Pieter JK Libin, et al.  Scalar reward is not enough: A response to silver, singh, precup and sutton (2021).  arXiv preprint arXiv:2112.15422, 2021.
  * [3] Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley.  A survey of multi-objective sequential decision-making.  Journal of Artificial Intelligence Research, 48:67–113, 2013.
  * [4] Peter Vamplew, Richard Dazeley, Adam Berry, Rustam Issabekov, and Evan Dekker.  Empirical evaluation methods for multiobjective reinforcement learning algorithms.  Machine Learning, 84:51–80, 07 2011.
  * [5] Conor F. Hayes, Roxana Rădulescu, Eugenio Bargiacchi, Johan Källström, Matthew Macfarlane, Mathieu Reymond, Timothy Verstraeten, Luisa M. Zintgraf, Richard Dazeley, Fredrik Heintz, Enda Howley, Athirai A. Irissappane, Patrick Mannion, Ann Nowé, Gabriel Ramos, Marcello Restelli, Peter Vamplew, and Diederik M. Roijers.  A practical guide to multi-objective reinforcement learning and planning.  Autonomous Agents and Multi-Agent Systems, 36(1):26, 2022.
  * [6] Roxana Rădulescu, Patrick Mannion, Diederik M. Roijers, and Ann Nowé.  Multi-objective multi-agent decision making: a utility-based analysis and survey.  Autonomous Agents and Multi-Agent Systems, 34(10), 2020.
  * [7] Diederik M Roijers, Denis Steckelmacher, and Ann Nowé.  Multi-objective reinforcement learning for the expected utility of the return.  In Proceedings of the Adaptive and Learning Agents workshop at FAIM 2018, 2018.
  * [8] Roxana Rădulescu, Patrick Mannion, Yijie Zhang, Diederik M Roijers, and Ann Nowé.  A utility-based analysis of equilibria in multi-objective normal-form games.  The Knowledge Engineering Review, 35, 2020.
  * [9] Federico Malerba and Patrick Mannion.  Evaluating tunable agents with non-linear utility functions under expected scalarised returns.  In Multi-Objective Decision Making Workshop (MODeM 2021), 2021.
  * [10] Peter Vamplew, Cameron Foale, and Richard Dazeley.  The impact of environmental stochasticity on value-based multiobjective reinforcement learning.  In Neural Computing and Applications, 2021.
  * [11] Mathieu Reymond, Conor Hayes, Diederik M Roijers, Denis Steckelmacher, and Ann Nowé.  Actor-critic multi-objective reinforcement learning for non-linear utility functions.  In Multi-Objective Decision Making Workshop (MODeM 2021), 2021.
  * [12] Conor F Hayes, Mathieu Reymond, Diederik M Roijers, Enda Howley, and Patrick Mannion.  Distributional monte carlo tree search for risk-aware and multi-objective reinforcement learning.  In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, volume 2021. IFAAMAS, 2021 In Press.
  * [13] M. M. Drugan and A. Nowe.  Designing multi-objective multi-armed bandits algorithms: A study.  In The 2013 International Joint Conference on Neural Networks (IJCNN), pages 1–8, 2013.
  * [14] Peter Auer, Chao-Kai Chiang, Ronald Ortner, and Madalina Drugan.  Pareto front identification from stochastic bandit feedback.  In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 939–947, Cadiz, Spain, 09–11 May 2016. PMLR.
  * [15] Doruk Öner, Altuğ Karakurt, Atilla Eryılmaz, and Cem Tekin.  Combinatorial multi-objective multi-armed bandit problem, 2018.
  * [16] Diederik M Roijers, Luisa M Zintgraf, and Ann Nowé.  Interactive thompson sampling for multi-objective multi-armed bandits.  In International Conference on Algorithmic DecisionTheory, pages 18–34. Springer, 2017.
  * [17] Saba Yahyaa and Bernard Manderick.  Thompson sampling for multi-objective multi-armed bandits problem.  In Proceedings, page 47. Presses universitaires de Louvain, Elsevier, 2015.
  * [18] Josef Hadar and William R. Russell.  Rules for ordering uncertain prospects.  The American Economic Review, 59(1):25–34, 1969.
  * [19] Vijay S. Bawa.  Optimal rules for ordering uncertain prospects.  Journal of Financial Economics, 2(1):95 – 121, 1975.
  * [20] Elmar Wolfstetter.  Topics in Microeconomics: Industrial Organization, Auctions, and Incentives.  Cambridge University Press, 1999.
  * [21] David O’Callaghan and Patrick Mannion.  Exploring the impact of tunable agents in sequential social dilemmas.  arXiv preprint: arXiv:2101.11967, 2021.
  * [22] Peter Vamplew, John Yearwood, Richard Dazeley, and Adam Berry.  On the limitations of scalarisation for multi-objective reinforcement learning of pareto fronts.  In Wayne Wobcke and Mengjie Zhang, editors, AI 2008: Advances in Artificial Intelligence, pages 372–378, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * [23] Marc G Bellemare, Will Dabney, and Rémi Munos.  A distributional perspective on reinforcement learning.  In International Conference on Machine Learning, pages 449–458, Sydney, 2017. PMLR.
  * [24] Richard S. Sutton and Andrew G. Barto.  Reinforcement Learning: An Introduction.  A Bradford Book, Cambridge, MA, USA, 2018.
  * [25] Weijia Wang and Michèle Sebag.  Multi-objective Monte-Carlo tree search.  In Steven C. H. Hoi and Wray Buntine, editors, Proceedings of Machine Learning Research, volume 25, pages 507–522, Singapore, Nov 2012. PMLR.
  * [26] Kristof Van Moffaert and Ann Nowé.  Multi-objective reinforcement learning using sets of pareto dominating policies.  Journal of Machine Learning Research, 15(107):3663–3692, 2014.
  * [27] Diederik M. Roijers, Shimon Whiteson, and Frans A. Oliehoek.  Linear support for multi-objective coordination graphs.  In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’14, page 1297–1304, Richland, SC, 2014. International Foundation for Autonomous Agents and Multiagent Systems.
  * [28] Haim Levy.  Stochastic dominance and expected utility: Survey and analysis.  Management Science, 38(4):555–593, 1992.
  * [29] Andreu Mas-Colell, Michael Dennis Whinston, Jerry R Green, et al.  Microeconomic theory, volume 1.  Oxford university press New York, 1995.
  * [30] Songsak Sriboonchitta, Wing-Keung Wong, s Dhompongsa, and Hung Nguyen.  Stochastic Dominance and Applications to Finance, Risk and Economics.  Chapman and Hall/CRC, 10 2009.
  * [31] David Levhari, Jacob Paroush, and Bezalel Peleg.  Efficiency analysis for multivariate distributions.  The Review of Economic Studies, 42(1):87–91, 1975.
  * [32] H. Nakayama, T. Tanino, and Y. Sawaragi.  Stochastic dominance for decision problems with multiple attributes and/or multiple decision-makers.  IFAC Proceedings Volumes, 14(2):1397 – 1402, 1981.  8th IFAC World Congress on Control Science and Technology for the Progress of Society, Kyoto, Japan, 24-28 August 1981.
  * [33] Marco Scarsini.  Dominance conditions for multivariate utility functions.  Management Science, 34(4):454–460, 1988.
  * [34] A. B. Atkinson and F. Bourguignon.  The Comparison of Multi-Dimensioned Distributions of Economic Status.  The Review of Economic Studies, 49(2):183–201, 04 1982.
  * [35] Scott F. Richard.  Multivariate risk aversion, utility independence and separable utility functions.  Management Science, 22(1):12–21, 1975.
  * [36] Vilfredo Pareto.  Manuel d’Economie Politique, volume 1.  Giard, Paris, 1896.
  * [37] Peter Vamplew, Cameron Foale, and Richard Dazeley.  The impact of environmental stochasticity on value-based multiobjective reinforcement learning.  In Neural Computing and Applications, 2021.
  * [38] Luisa M. Zintgraf, Timon V. Kanters, Diederik M. Roijers, F. Oliehoek, and Philipp Beau.  Quality assessment of morl algorithms: A utility-based approach.  In Benelearn 2015: Proceedings of the 24th Annual Machine Learning Conference of Belgium and the Netherlands, 2015.
  * [39] Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan.  A generalized algorithm for multi-objective reinforcement learning and policy adaptation.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [40] D. A. Darling.  The kolmogorov-smirnov, cramer-von mises tests.  The Annals of Mathematical Statistics, 28(4):823–838, 1957.
  * [41] E. Choi and Stanley Johnson.  Stochastic dominance and uncertain price prospects.  Center for Agricultural and Rural Development (CARD) at Iowa State University, Center for Agricultural and Rural Development (CARD) Publications, 55, 01 1988.
  * [42] Mukhtar M. Ali.  Stochastic dominance and portfolio analysis.  Journal of Financial Economics, 2(2):205–229, 1975.
  * [43] Vijay S. Bawa.  Safety-first, stochastic dominance, and optimal portfolio choice.  The Journal of Financial and Quantitative Analysis, 13(2):255–271, 1978.
  * [44] Peter C Fishburn.  Non-cooperative stochastic dominance games.  International Journal of Game Theory, 7(1):51–61, 1978.
  * [45] Vijay S. Bawa.  Research bibliography-stochastic dominance: A research bibliography.  Manage. Sci., 28(6):698–712, June 1982.
  * [46] Laurence Cook and Jerome Jarrett.  Using stochastic dominance in multi-objective optimizers for aerospace design under uncertainty.  In American Institute of Aeronautics and Astronautics Journal, 01 2018.
  * [47] John Martin, Michal Lyskawinski, Xiaohu Li, and Brendan Englot.  Stochastically dominant distributional reinforcement learning.  In International Conference on Machine Learning, pages 6745–6754. PMLR, 2020.
  * [48] Gabriel Dulac-Arnold, Nir Levine, Daniel J. Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester.  Challenges of real-world reinforcement learning: definitions, benchmarks and analysis.  In Machine Learning, 2021.
  * [49] Conor F Hayes, Mathieu Reymond, Diederik M Roijers, Enda Howley, and Patrick Mannion.  Risk-aware and multi-objective decision making with distributional monte carlo tree search.  In: Proceedings of the Adaptive and Learning Agents workshop at AAMAS 2021), 2021.
  * [50] Norbert Schappacher.  Beppo levi and the arithmetic of elliptic curves.  The Mathematical Intelligencer, 18(1):57––69, 1996.