On the Expressivity of Objective-Specification Formalisms in Reinforcement Learning
Authors: Rohan Subramani
Marcus Williams
Max Heitmann
Halfdan Holm
Charlie Griffin
Joar Max Viktor Skalse
Venue: ICLR 2024 poster (2024)
Keywords: reward hypothesis
Markov reward
multi-objective reinforcement learning
linear temporal logic
reward machines
Primary area: reinforcement learning
TL;DR: We comprehensively compare the expressivities of seventeen formalisms for specifying objectives in reinforcement learning.

Abstract: Most algorithms in reinforcement learning (RL) require that the objective is formalised with a Markovian reward function. However, it is well-known that certain tasks cannot be expressed by means of an objective in the Markov rewards formalism, motivating the study of alternative objective-specification formalisms in RL such as Linear Temporal Logic and Multi-Objective Reinforcement Learning. To date, there has not yet been any thorough analysis of how these formalisms relate to each other in terms of their expressivity. We fill this gap in the existing literature by providing a comprehensive comparison of 17 salient objective-specification formalisms. We place these formalisms in a preorder based on their expressive power, and present this preorder as a Hasse diagram. We find a variety of limitations for the different formalisms, and argue that no formalism is both dominantly expressive and straightforward to optimise with current techniques. For example, we prove that each of Regularised RL, (Outer) Nonlinear Markov Rewards, Reward Machines, Linear Temporal Logic, and Limit Average Rewards can express a task that the others cannot. The significance of our results is twofold. First, we identify important expressivity limitations to consider when specifying objectives for policy optimization. Second, our results highlight the need for future research which adapts reward learning to work with a greater variety of formalisms, since many existing reward learning methods assume that the desired objective takes a Markovian form. Our work contributes towards a more cohesive understanding of the costs and benefits of different RL objective-specification formalisms.

ON THE EXPRESSIVITY OF OBIECTIVE-PEECIICCTTION FORMALISMS IN REINETTCEMENT LEARNING
Rohan Subramani Mareus Williams" Max Heitmann S* Halfdan Holm", Charlie Griffin Joar S
"AI Safety Hub, CColmbia University, UUniversity of Oxford *Equal contribution. Correspondence to Rohan Subramani at rs4126 columbia.edu.
ABSTRACT
Most algorithms in reinforcement learning (RL) require that the objective is for- malised with a Markovian reward function. However, it is well-known that certain tasks cannot be expressed by means of objective in the Markov rewards formal- ism, motivating the study of alternative objective-specification formalisms in RL such as Linear Temporal Logic and Multi- Kulti-OOjective Reinforcement Learning. To date, there has not yet been any thorough analysis of how these formalisms relate to each other terms their expressivity. We fill this gap in the existing literature by providing a comprehensive comparison of 17 salient objective-specifictiio formalisms. We place these formalisms in a preorder based on their expressive power, and present this preorder Hasse diagram. We find variety of limita- tions for the different formalisms, and argue that no formalism is both dominantly expressive and straightforward to optimise with current techniques. For example, we prove that each of Regularised RL, (Outer) Nonlinear Markov Rewards, Reward Machines, Linear Temporal Logic, and Limit Average Rewards can express a task that the others cannot. The significance of our results is twofold. First, we identify important expressivity limitations to consider when specifying objectives for policy optimization. Second, our results highlight the need for future research which adapts reward learning to work with a greater variety of formalisms, since many existing reward learning methods assume that the desired objective takes a Markovian form. Our work contributes towards more cohesive understanding of the costs and benefits of different RL objectiie-speecfiicttinn formalisms.
INTRODUCTION
There are many ways of specifying objectives in Reinforcement Learning (RL). The most common method is to maximise the expected time-discounted sum of scalar Markovian rewards [ While this method has achieved wide-ranging success, recent work has identified practical objectives that cannot be specified using standard Markov rewards (Skalse & Abate (223): ;); Abel et al. (2022); :Bowling et al.) (2022). Numerous other formalisms have been proposed and utilised for specifying objectives in practice, including Multi-Objective RL (Hayes al. (2022); y Roijers al. (2013); Coello Coello et al.) (2002)), Maximum Entropy RL HHazan et al. (201 (9)) Mutti et al. (2023): Ziebart et al. (2008)), Linear Temporal Logic (Littman et al. (2017): ; Lahijanian et (201 1): Ding al. (201I)) [), and Reward Machines (Icarte et al. (0118); Toro learte et al. (022); Camacho et al. (2019)) ). Additionally, there are various abstract formalisms (such as arbitrary functions from trajectories to the real numbers), which are generally intractable to optimise but which capture intuitive classes of objectives.
In this paper, we comprehensively compare the expressivities of formalisms, which are listed and defined in Table We say that formalism A can express another formalism B if in all environments, can express all objectives that B can express. We formalise this notion in Section 2 Our main results summarised in Figure formalisms we consider. We find that in many cases, there is no simple answer to the question of which of two formalisms is preferable to use for policy optimisation in practice because each can
Hasse diagram displaying the relative expressivities of all the
AA reward function Markovian if it depends only on the most recent transition.

---

express objectives that the other cannot. While there are formalisms the top of our diagram that can express every formalism below them, we suspect that none of these are tractable to optimise in general. Therefore, advise RL practitioners familiarise themselves with variety of formalisms and think carefully about which to select depending on the desired use case. Our analysis describes some of the strengths and limitations of each formalism, which can be used inform this selection.
Our results are relevant not only for policy optimisation but also for reward learning. Reward learning often used when it difficult to hardcode reward function for task but easy evaluate attempts at that task. For instance, (Christiano et al. (2017)) train a reward model which incentivises an RL agent do backflips simulated environment. Notably, the structure of reward models in many prior works have implicitly assumed that the desired task is expressible with Markov rewards, since reward models output real numbers given transition as input (Christiano et al., 2017 7 Hadfield Menell et al. 2016; [Skalse et al. (023). Our findings highlight the limitations of Markov rewards and the importance of advancing reward learning methods for the other formalisms we discuss.
In Section 2 we briefly introduce core concepts from RL relevant to our paper, make the nature of our formalism comparisons precise, and define the objective-speciffattoon formalisms that we are comparing in this work. We provide our primary results in Section [ These are summarised in Figure a Hasse diagram that depicts all the expressivity relationships among the formalisms. We also present many of the theorems and propositions
which the diagram is based; the remaining statements and all proofs are found in Appendix [B] In Section 4 we discuss the implications of our findings in the context of prior research, along with limitations and directions for future work.
PRELIMINARIES
2.1
BASIC DEFINITIONS
Many of the concepts in this paper are derived from the study of Markov Decision Processes (MDPs) (Sutton& & Barto (018 An MDP is 6-tuple (S, T, R.y) where S is a set of states, AA is S x A AS is a transition function and I E AS is the initial distribution
set of actions, over states. this work, we assume S and are finite and only consider stochastic stationary policies S + AA, solutions to the MDP which stochastically output an action in any state (rewardless) trajectory is an infinite sequence & = ($0: ag. $1, a1. ) such that a, E A, 8; E S for all i. where So I. ag ((S)), 81 T( ag) and so on; denote the set of (infinite) trajectories
as = S x (A SY _ The reward function R S x A x S + R gives a reward at each time step r. R( Ct; $1+1), and y [0, 1) gives discount factor.
The return of a trajectory & for R and y is GR, = Σ R(( ae st41) and the expected return
t=
of a policy is taken over trajectories sampled using the environment and the policy: J 8 (T) Eg .z GG()).
Since we consider various ways to define an objective, we separate our decision process into an environment and an objective specification.
Definition 2.1 (E, II, Enus). We refer the 4-tuple (S A,T.) I) the environment and denote
F. We denote the set of finite environments as Enns 3 A given environment determines the
stationary-policy space I {IT π S A(A))
Using Markovian Reward R and geometric discounting factor is one way to specify an objective. However, in this work we want to compare and contrast ways to specify objectives. To do this, we introduce the notion of an objective specification.
Definition 2.2 (O, = 5). Given an environment F, an objective specification is tuple O that allows us rank policies in E Formally, O defines > H total preorder over EI Total preorders are transitive and strongly connected.
We assume that the state and action spaces finite and only consider stationary policies order make our findings more relevant to common RI. algorithms. For example, Q-learnin only has convergence guarantee for finite state and action spaces and only considers stationary policies.
We can formally define Enus, the set of environments as Erna 8, A are any two finite sets, T AS, E A(S))
(1S,A,T.1)
2

---

Definition 2.3. (MR, OMR, )) For environment E, an objective specification in the Markovian reward formalism a pair OMR = (R,7) with R: R A x + and 7 E [0, 1). The ordering over II induced by OM is given by: mi 0MR 22 = J(R,>) (T)) (
To compare different ceajective-specfficati formalisms, it will be important to consider the set of policy orderings possible in given formalism. Since the set of valid objective specifications and orderings depends on the environment, we define function Ord.
Definition 2.4 (Objective specification formalism X, Ordx and OrdMR). An objective-speccficatiion formalism X is valid if it defines a function from environments orderings over policies in that environment. Given an objective-specifien specifictiiiiinnnnnnnnn formalism X, we denote the set of possible orderings for given enviromment as Ordx (E) where Ordx (E) S P(I xII For example, Ord (e {= MMR
R: S x A S + R and E [0, 1)}.
Finally, we define a partial order expressivity relation over objective specification formalisms.
Definition 2.5 ( EXPR). We define an order over objective specification formalisms غ Exrn. For any two objective specification formalisms X and Y, X ž EXPRY if and only if X can express all policy orderings that Y can express, in all enviromments. Formally:
X = EXPRY = VE E Envs, Ordx 2 Ordy(E)
Note that > EXPR reflexive and transitive.
Like Abel et al. 2022) and Skalse & Abate 2023), we focus on the ability of formalisms to express policy orderings, as opposed to alternatives such as their ability to induce a desired optimal policy, One key reason define expressivity in this way is that it is sometimes infeasible to train agent to find an optimal policy in practice; in such cases, an objective specification more likely to provide an effective training signal if it expresses desired policy ordering than if it merely induces desired optimal policy. We motivate the choice to focus on policy orderings further in Appendix A.1
2.2 FORMALISM DEFINITIONS
In [ we present the definitions of all the formalisms we consider in this work. These definitions are supplemented with few additional details in Section 2.2. Past work related to many of these formalisms is discussed in Section 4 For formalisms which have ambiguous or varying definitions in past literature, we attempt to select the definitions that best allow for meaningful expressivity comparisons. In some cases, the appeal of these formalisms also becomes clearer the context of results and proofs.
In Appendix A.2 we argue that objective specifications all of the formalisms in Table I Iinduce total preorders the set of policies.
2.2. ADDITIONAL MACHINERY
Here, we provide few additional definitions that the formalisms in Table I depend upon. The first is for Linear Temporal Logic (LTL) formulas, which are required for specifying objectives with the LTL formalism.
Definition 2.6. Linear Temporal Logic Formula. An LTL formula is built up from a set of atomic
propositions; the logic connectives: negation (-), disjunction (V), conjunction (A) and material implication (-)); and the temporal modal operators: next (Q), always (O), eventually (+) and until (4). We take the set of atomic propositions be A x S, the set of transitions. An LTL formula ip either true false for trajectory & E = = S (A x S)"; say sp(E) 1 if the formula evaluates to true in E and (pE) if the formula evaluates to false (Littman et al. (017 y Manna & Baier & Katoen 2008
Pnueli 1992);
'The definitions in Section 2.1 use detailed indexing to clearly convey that some symbols correspond to specific environments and / or objective specifications. In other sections (particularly Appendix B we often drop these indices when the meaning of the symbols is evident.
3

---

Formalism Name
Ohjective Tuple
Types and detimitions
Policy ordering method.
For scalar lunations 71 T =
J(m)) 2 J(ma)
Markev Rewards
(R.4)
R:6%
J(z)
Ris,, 0t.11.).
7
Limit Average
(R)
R
J(H)
= N-
3g
R(se.ae.
Reward (LAR)
Linear Temporal (1.TI)
SP
LTT.
J(r) (P(E)
Detinition
Reward Machines
(U, un- bur
U is finite set of machine states function for machine states
((H) Re
RRee(sr. where 120
67,,7
R. 6 Me+1)
U/ O/ [S A R] is function ourpats reward
funerioo given machine
7. E [D, 3)
$ R ar.
Inner Nenlinear
(R.
R. S:S x
R
((z) Re
Markov Rewards
B.
E [)
Inner Multi Objective (MORR))
(k, R. (i7)
& E
J(r) = Rg (G1(5) Gx(E))) when
R
k dideenesinnal
C,(E) E ( a141) and
+
R.
1)
7:5-3
[(m 17(3)
Trajectories (FTR)
Regultzised RL (RRL)
(R,
R R:S 1.S%x A A GER A(A) 7 (0.1)
((x) Re (R(s.. af
Outer Nonlinear Markov Rewards
(R,
R:88 X A R
J(H) 1=
o R 04.)))
f:
(0.1)
Cluter
(.,7
kek
J(F) =- (K) (F)) where
(OMORL)
Multi-Ohjenne Ohjective RT.
8 A
R² is bedimensional
J((m) Eg
Σ (9.
3,5 1)
Functions from
(..3)
1: mill) + (.1
[( [(mmm)
Occupancy
(See Deliiiion
Messures (FOMR)
Fasctions from
(
& Lug
[(c) 1(4e)
(See Delinitoon A
(FILR)
Functions from
(2)
J. Is -
(FF) (ashitaar)
Policies Reals
Occagoncy Missume
(r, mm)
Em isa lotal prooeder (((IT) (ma(() (s,a) 7 Definition
t m((1) m(+2)
Orderings (OMO)
LII.AA
E1. Liz
Orderings (TLO)
(See Delinition
Gesentike Outer Ohjeeii RL.
(k, R. 7.20)
à E
J(r) = (Ji(t), where
R S A S R$ is I-dimessional
(GOMOR1)
function
J((n) Eg (R(
7 E [0,
Tı 2 52 J(m) ky J(mz)
Policy Orderings (PO)
2 1s aocal preunder on Is..A
m1 2 (directly specttied)
Table 1: This table provides the objective tuple along with definitions for all 17 formalisms considered in this paper. also explicitly states the method by which each formalism orders policies. All expectations are taken over trajectories in the environment sampled using the policy.
Next, we define occupancy measures, which are central object for the formalisms of Functions from Occupancy Measures to Reals and Occupancy Measure Orderings.
Definition 2.7. Occupancy Measures. Given policy π, environment E (S,A,T,I), and discount factor 7, the occupancy measure ( is vector in IR A||S], where:
m = A APPEas,TII
a, 8t+1 =
As the name suggests, m())) measures the extent to which a policy "occupies" each transition, in expectation, across the entirety of a trajectory.
4

---

For the formalisms of Functions from Trajectory Lotteries to Reals and Trajectory Lottery Orderings, we must define trajectory lotteries. To avoid concerns related to non- non-measurable sets that arise with generic distributions over the set of all trajectories, sequence of lotteries over finite trajectory segments.
define trajectory lotteries using infinite
Definition 2.8. Trajectory Lotteries. Let Ep be the set of all initial trajectory segments of length 2k + We write [5]x for the first 2k + 1 elements of Ç. Define La,x E A(Ex) : Lx, (Ex (so, ao ..... sk)) P.
Ex). A trajectory lottery Ln is then defined as the infinite sequence of Lk, values: Lg == (Lo.
: Li.g. L2.)...... The set of trajectory lotteries generated by
any policy in environment E' (S, A, T TJ is defined to be LIis. == {Lz/ lls,A).
3 RESULTS
In this section, we present our expres- sivity results. For each of the 289 ordered pairs of formalisms (X, Y): we prove either that X = EXPRY
or that X E EXPRY [5 Figure I de- picts the expressivity relationships between all formalisms. Note that
Thoorem 3.4
FPR
GOMORI
OMO TLO
PC: Policy Orderino
the absence of a sequence of arrows from one formalism to another is as significant as the presence of a se- quence of arrows: the presence of sequence of arrows means that the first formalism can express all policy orderings that the second can express, and the absence of sequence of ar- rows means that there exists pol- icy ordering that the second formal- ism can express and the first cannot express. considerable part of our contribution in this work is to demon- strate the expressive limitations of these formalisms, and these limita- tions are represented by the absence of arrows. In this section we will state and provide intuition for many of the nontrivial positive and nega- tive expressivity results that serve as the basis for the Hasse diagram. The
FPR: Funclons from Polkles to Reals
GOVORL: Generaliod Duant Mur-- Ulpedine
ON/C Decupency Mesuure Ordesings
Theorem 3.3
Togestory Leberr Ordening
OMORL
FOMR
FTLR
ONORL Mutk Orjectvv
FOVR: Fund Gompanyy Reals
FTUR: Furciions from Trieetory
Lifanko ta Rloda
Theorem 3.1
RAL: Regi lurbscd RR.
RRL
ONMR
INMR IMORL
FTR
CRaIR: Owter Nosiliner MR
NNVR lawe Non linesr MR
IVORL: loree Mulk Olyective RL.
FTR, Funcioon from Trojedorios to
RM
Awargge
MR
LAR
LTL
Figure This Hasse diagram displays all expressivity re- lationships between our formalisms. An arrow or chain of arrows from one formalism to another indicates that the first formalism can express all policy orderings that the second formalism can express, all environments. Arrows going both directions mean that the formalisms have the same ex- pressivity. If there is no chain of arrows from one formalism another, there are policy orderings that the latter can express and the former cannot express.
remaining results, and all proofs, can be found in Appendix B
3.1 POSITIVE RESULTS
Several of the positive connections
in the Hasse diagram are relatively trivial; these are discussed in Appendix B.I the most substantive results. Proofs for the results in this subsection are available in Appendix [.2 and referenced beside each result.
Here, we focus on
Theorem 3.1. Inner Nonlinear Markav Rewards (INMR), Inner Multi-Ohjective RI. (IMORI.,. and Functions from Trajectories to Reals (FTR) are equally expressive. Proof: B.27
is straightforward to see that IMORL can express all policy orderings that INMR can express and that FTR can express all policy orderings that IMORL can express (and we show these results
'ee study 17 formalisms, so there are 172 289 ordered pairs of formalisms. This includes the ordered pairs of a formalism with itself; trivially, any formalism can express itself. The expressivity results for some other ordered pairs of formalisms are also fairly straightforward, and many results follow from the transitivity of the expressivity relation. Table the appendix depicts all proof dependencies for these results.
5

---

explicitly in Appendix B.1. Therefore, the following proposition is sufficient to conclude that INMR, IMORL, and FTR are equally expressive:
Proposition 3.2. Any policy ordering expressible with Functions from Trajectories to Reals (FTR)
can be expressed with Inner Nonlinear Markov Rewards (INMR). Proof: B.21
Briefly, our proof demonstrates that it is possible to express an arbitrary function from trajectories to reals fETA Rt with an INMR specification (R. fINMR, 7) by selecting and so that the trajectory return function G' is injective, and then setting JINMR equal JFTR G-1, The full proof is in Appendix B.2 This proof notably relies on allowing SINMR R to be an arbitrary function that need not satisfy properties such as differentiability, continuity, nonequivalent constraints might be of interest, we choose to define a very general version of INMR; discuss the implications of this choice in the next section, and in more detail in Appendix A.4
monotonicity. Since many possible
Theorem 3.3. Outer Multi-Objective Reinforcement Learning (OMORL), Functions from Occupancy Measures to Reals (FOMR), and Functions from Trajectory Lotteries to Reals (FTLR) are equally expressive. Proof: B.24
We show that a) two policies have the same occupancy measure if and only if they generate the same trajectory lottery, and b) it is always possible to specify an OMORL objective such that two policies have the same policy evaluation vector (J(x)= == occupancy measure. Therefore, the expressivity of function from policy evaluation vectors reals is exactly the same as a function from occupancy measures to reals and a function from trajectory lotteries to reals. It is worth noting that in order to possess this expressive power, OMORL requires access to |S||A|||]] reward functions for any environment E = (S,A, T, II). It may be infeasible to specify and optimise an objective with so many reward functions in practice; in Section 4 and Appendix A.4 we discuss the possibility of restricting the number of reward functions multi-reward objective can include.
if and only if they have the same
Our third theorem is very similar to Theorem
Theorem 3.4. Generalised Outer Multi- Objective RL (GOMORL), Occupancy Measures Orderings (OMO), and Trajectory Lottery Orderings (TLO) are equally expressive. Proof: B.25
The proof of this theorem utilises the same lemmas the proof of Theorem Total preorders over policy evaluation vectors, occupancy measure, and trajectory lotteries are all equally expressive, because two policies share trajectory lottery if and only if they share occupancy measure if and only if they share a policy evaluation vector (with appropriately selected reward functions).
3.2 NEGATIVE RESULTS
All proofs for the results in this subsection can be found in Appendix B.3
Proposition 3.5. There exists policy ordering that Linear Temporal Logic (LTL) and Limit Average Rewards (LAR) can express but Reward Machines (RM) and Markov Rewards (MR) cannot express. Proof: B.26
RM specifications can only induce policy evaluation functions that are continuous (in the sense that infinitesimal changes to a policy can only lead to infinitesimal changes to the policy evaluation). Note that it must also be true that Markov Rewards (MR) can only induce continuous policy evaluation functions, because as shown in Appendix B.T RM can express any policy evaluation function that MR can express. LTL and LAR can induce discontinuous policy evaluation functions.
Proposition 3.6. There exists a policy ordering that Markov Rewards (MR) and Limit Average Rewards (LAR) can express but Linear Temporal Logic (LTL. cannol express. Proof: B.24
An LTL specification can only assign a value of sp(E) = 0 or vp{E) = to a trajectory, since an LTL formula & is either true false for any given trajectory E. MR and LAR, on the other hand, can give any saluer rewards. In certain cases, this prevents LTL from differentiating between trajectories
and lotteries over trajectories generated by policies that MR and LAR can distinguish. For instance, LTL. cannot induce any strict ordering of deterministic policies in a deterministic environment.
Proposition 3.7. There exists a policy ordering that Linear Temporal Logic (LTL) and Markov Rewards (MR) can express but Limit Average Rewards (LAR) cannot express. Proof: B.29

---

LAR cannot distinguish between policies that generate the same trajectory lottery after finite amount of time, even if the lotteries they generate over initial trajectory segments are different. LTL and MR can distinguish between policies based on differences that appear only early in trajectories.
Proposition 3.8. There exists a policy ordering that Outer Nonlinear Markov Rewards (ONMR) can express bul Functions from Trajectories Reals (FTR) cannol express. Proof: B.34
ONMR can express the objective of making a trajectory occur with at least some desired threshold probability, while being indifferent to achieving probabilities higher than the threshold. For example, this can be achieved (for particular environment and reward specification) with the wrapper function if x 2 0.5, otherwise By contrast, for an FTR specification (SFTR) to incentivise
{
fONMR(())
trajectory, srrn must assign higher value to that trajectory than others. However, this would incentivise maximizing the probability of that trajectory, not merely meeting a threshold.
Proposition 3.9. There exists policy ordering that Functions from Policies to Reals (FPR) can express but Generalised Outer Multi-Objective RI. (GOMORL) cannot express. Proof: B.36
A function from policies reals can assign different values any two distinct policies, even if they only differ on states that both policies have probability zero of ever visiting. GOMORI. cannot express preferences between policies that are identical on all states visited with nonzero probability. Proposition 3.10. There exists policy ordering that Generalised Outer Multi-Objectiin RL (GO- MORL) can express but Functions from Policies to Reals (FPR) cannot express. Proof: B.37
There exist lexicographic preference orderings of GOMORL policy evaluation vectors that cannot be represented by any real-valued function (Steen Seebach (2012).. These orderings of policy evaluation vectors can be used to express tasks in GOMORL that are inexpressible in FPR.
4 DISCUSSION AND RELATED WORK
Previous work has attempted to settle the reward hypothesis, which states that "all of what we mean by goals and purposes can be well thought of as maximization of the expected value of the cumulative sum of a received scalar signal (called reward)" (Sutton (2004)). Related to this is the von Neumann- Morgenstem (VNM) utility theorem, which states that an agent's 's preferences between lotteries over finite set of outcomes can be represented as ordered according to the expected value of a scalar utility function of the outcomes if and only if these preferences satisfy four axioms of rationality (the VNM axioms) (Von Neumann & Morgenstern (1944).. Consequently, if one's 's preferences cannot be represented by a utility function, the preferences must violate at least one of these axioms.
The VNM theorem is typically considered in the context of single-decision problems, while RL is applied to sequential decision-making. Without modification, the VNM theorem can be applied to RL settings by taking the outcome space to be finite set of (full) trajectories. It then states that an agent's preferences about lotteries over a finite number of trajectories can be expressed as a function from trajectories to the reals (i.e., in the FTR formalism) if and only if those preferences satisfy the VNM axioms. Close relatives of the FTR formalism as defined in this work have been studied in Chatterji al. (2022) and Pacchiano al. (021). though these works the formalism restricted to trajectories of finite length (among other differences). Other recent work has proven stronger statements about the required of the trajectory return function under the supposition of additional axioms for preferences over temporally extended outcomes that supplement the VNM axioms.
Pitis 20119) Shakerinava & Ravanbakhsh (2022). and [Bolling et al. (2022) all identify axioms from which it is possible to prove that preferences regarding temporally extended outcomes can be expressed using Markovian rewards. All three papers identify slightly different axioms that, when supplemented with the VNM axioms, enable this proof. One caveat is that all three papers show that preferences can be represented with a Markovian reward function along with a transition dependent discount factor, rather than the traditional constant discount factor in MDPs.
The VNM theorem and the work that has adapted it to sequential decision maaonngaaingg settings present axioms that must be violated for objective to be inexpressible with Markov rewards a function from trajectories to reals. Our work demonstrates several objectives that Markov rewards and functions from trajectories reals cannot express, which raises the question: are there reasonable
7

---

objectives that violate the axioms, or are the objectives we present unreasonable? We elaborate on this tension in Appendix A.5 particularly for violations of the VNM axioms. In our work we also assume conventional constant discount factor, but future work could compare the expressive power of formalisms that allow transition-dependent discount factors with the formalisms we consider.
Abel al. (022)) formalise task in three different ways. One is set of acceptable policies, another is an ordering over policies and the third is an ordering over trajectories. They find that for each notion of a task there exists an instance that no Markov reward function can capture. The second formalisation, policy orderings, is the one that we use, and we adapt their proof that Markov Rewards cannot express an "XOR" policy ordering to display the expressive limitations of several formalisms.
Multi-Objective RL (MORL) has received considerable attention in the literature. Silver et al. (2021) argues that maximization of scalar reward is enough drive most behaviour in natural and artificial intelligence, while Vamplew et al.] (2022) argue that multi-objective rewards are necessary. In particular, Vamplew et al. (2022) argue that scalar reward is insufficient to develop and align Artificial General Intelligence. MMuua (2023) shows that multi-dimensional reward functions are also not universally expressive; they state necessary and sufficient conditions under which a task defined as a set of acceptable policies can be expressed with a multi-dimensional reward function. They use definition of MORL where a policy is acceptable if each dimension of reward is above a given lower bound - generalise this notion for one of our formulations of MORL. Algorithms for solving multi-objective problems have been developed and used in several applications (Hayes et al. (2022
Jalalimanesh et al. (017); Castelletti et al. (2033).
(2023) demonstrate that some multi oojtii-bbecctvee, risk-sensitive, and modal tasks cannot be expressed with Markovian rewards. We analyse several formalisms related to this paper: Generalised Outer MORL (GOMORL) is based on this paper's s definition of MORL, and our Inner Nonlinear Markov Rewards (INMR) is partially motivated as generalisation for risk-sensitive tasks, We extend these definitions to study what we call Outer MORL (OMORL), Inner MORL (IMORL), and Outer Nonlincar Markov Rewards (ONMR), which enables a robust comparison of the expressive power of wrapper functions that are applied before and after taking an expected value over trajectories. Skalse & Abate (2023) also use occupancy measures a proof demonstrate limitations of Markov Rewards, and we find occupancy measures sufficiently useful tool for reasoning about formalism expressivity that we include Functions from Occupancy Measures to Reals and Occupancy Measure Orderings formalisms in our analysis. Our extensions are further justified by their relationships to other prior work: Convex RL (e.g. Zahavy et al. (2023); Mutti et al. (2023)) also referred to as RL with general utilities (Zhang al., 2020), is equivalent to Functions from Occupancy Measures to Reals (FOMR) except with a convexity constraint on the functions, and RI. with vectorial rewards (Cheung 2019 is a special case of IMORL in the time-average reward setting.
Skalse & Abate
Prior work has studied Reward Machines (RM), Limit Average Rewards (LAR), and Linear Temporal Logic (LTL) as well. Icarte et al. 2018 point out that reward machines can trivially express all objectives that Markov Rewards can express and provide rewards that depend on a finite number of features of the history so far, rather than just the most recent transition. This paper also applies RM specifications to toy tasks. [Mahadevan (996) investigates algorithms for learning goals specified with Limit Average Rewards (LAR), but we have not found any work on the expressivity of LAR.
Littman et al. (2017) study LTL,, which was previously utilised in control theory (Bacchus et al. 1970 Puterman 1994). in an RL setting. The authors mention that many common tasks can be expressed with LTL, and are sometimes easier to express with LTL than with Markov Rewards. Related to LTL Signal Temporal Logic (STL), an extension of LTL to the continuous time domain, which has a number of desirable properties (Balakrishnan & Deshmukh, 2019 Wang et al. 2023). However, in this work we focus on objective specifications in discrete environments and using discrete time, for which STL is equivalent to LTL.
When attempting to reverse engineer an agent's 's utility function from its behavior, Maximum Entropy Inverse RL makes an assumption that an agent's 's distribution over actions has maximum entropy (Ziebart et al. (2008)) Our formalism of Regularised RL relates to this concept by allowing any function of the distributions over actions be included in the RL objective.
8

---

4.1 LIMITATIONS AND FUTURE WORK
In this paper, we focus on stationary policies, and define objectives as orderings of stationary policies. In principle, however, policies can be history-dependent that is, an agent can select actions based on the history rather than just the most recent state. We make the choice to focus on stationary policies because common RL algorithms (such as Q-learning (Watkins & Dayan (1922)) derive exclusively stationary policies from state-action value functions. Many, but not all, of our expressivity results earry over to the history-dependent setting. We hope to see future research extend our study to history-dependent policies, and we discuss this topic in more detail in Appendix A..
few of our results rely heavily on the technical details of the formalisms in ways that may reduce their practical significance. For instance, Theorem 3.] relies on the ability of Inner Nonlinear Markov Rewards to utilise an arbitrary wrapper function for the trajectory return, and Theorems 3.3 and 3.4 require allowing multi-objective formalisms access to arbitarry number of reward functions. One direction for future work is to replicate our analysis under various restricting conditions; we discuss some conditions that may be of interest in Appendix A.4
Another limitation of our results that we do not assess the important tradeoff between expressivity and tractability. An important area for future work might be identify which of the more expressive formalisms considered here could be implemented in practice and provide guidance for balancing expressivity and tractability in various practical settings. The research community can address this question gradually by developing new algorithms to solve a range of problems with a variety of formalisms. Understanding the prreesivvityttactabbbnn tradeoff might also involve considering restricting conditions for the formalisms, since the conditions required to make a formalism tractable to optimise could reduce its expressivity.
Until the tractability of these formalisms is studied more carefully, it is difficult to draw clear conclusion about which formalisms are best to use in practice. more immediate takeaway from our results is that many of the formalisms are expressively incommensurable; for example, Limit Average Reward, Linear Temporal Logic, Reward Machines, Regularised RI., and Outer Nonlinear Markov Rewards can each express policy orderings that none of the others can express. This highlights the importance of carefully selecting a formalism for any task of interest; our results elucidate strengths and limitations of different formalisms that can inform these selections.
Future research can also explore reward learning with formalisms other than Markov Rewards. There have been preliminary efforts in the direction of reward learning for Reward Machines (Icarte et al. (2019)). ). Linear Temporal Logic (Neider & Gavran (2018), ), and Limit Average Reward (Wu et al. (2023), ), but given the range of objectives that show cannot be specified with Markov Rewards, it may be important to further develop reward learning alternatives that allow us to reliably express the objectives we desire across a variety of domains.
CONCLUSION
This paper provides a complete map of the relative expressivities of seventeen formalisms for specify- ing objectives in RL. We discovered meaningful expressive limitations to all of these formalisms 6 including many of the alternatives and extensions Markov rewards that have been discussed in the existing literature. We also related practical formalisms to a number of theoretical constructs, such as trajectory lotteries and occupancy measures, which help to fill out richer intuitive picture of where each formalism stands in the expressivity hierarchy. We hope our work will serve as a reference point for future discussions of these methods for specifying temporally extended objectives, as well as provide an impetus for future work that contextualises these results in light of the tradcoff between expressivity and tractability that appears both policy optimisation and reward learning.
REPRODUCIBILITY STATEMENT
All of results are theoretical. All proofs be found in Appendix B For definitions of environments, objectives, total order and formalisms see Section 2 been stated in the proofs.
Any further assumptions have
With the exception of Policy Orderings, which by our definition can express all objectives.
9

---

REFERENCES
David Abel, Will Dabney, Anna Harutyunyan, Mark K. Ho, Michael L. Littman, Doina Precup, and Satinder Singh. On the Expressivity of Markov Reward, January 2022. http://///ax
org/abs/2111 00876 arXiv:2111 .00876 [cs]
Fahiem Bacchus, Craig Boutilier, and Adam Grove. Rewarding Behaviors, Proceedings of the National Conference on Artificial Intelligence, 2, February 1970.
Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, Cambridge, Mass., 2008. ISBN 978-0-262-02649--
A. Balakrishnan and J.V. Deshmukh. Structured reward shaping using signal temporal logic specifications. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3481-3486, November 2019, IEEE. DOI: 10. 10.100//R054089722099998000 299.899350.8 URL
https://ieeeee: ore. eeee . org wwwwmoon////ooocoocoom /8668355
Michael Bowling, John D. Martin, David Abel, and Will Dabney, Settling the Reward Hypothesis, December 2022. URL
10420 arXiv:2212. 10420 [es.
math, stat].
Alberto Camacho, Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcllraith. LTL and Beyond: Formal Languages for Reward Function Specification in Reinforcement Learning. In Proceedings of the Eventy-Füghtth International Joint Conference on Artificial Intelligence, pp- 6065-6073 Macao, China, August 2019. International Joint Conferences Artificial Intelligence Organization. ISBN 978-0-9992411-447 doi: 10.24963/iccii.2119/8844 URL https:://////m /ww
ijcai. p:palloor//prrceeednng///211111
Andrea Castelletti, F. Pianosi, and Marcello Restelli. A multiobjective reinforcement learning approach to water resources systems operation: Pareto frontier approximation in a single run. Water Resources Research, 49:3476-3486, June 2013.
doi: 10.1002/wwe::22255.
Wang Chi Cheung. Regret Minimization for Reinforcement Learning with Vectorial Feedback and Complex Objectives. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019. URL /tttps://prrceeeeingg htwp://ooweeeidioo...ee..ei.eeee cc pttppppee///1////1111
pdf
Niladri S. Chatterji, Aldo Pacchiano, Peter L. Bartlett, and Michael
Jordan. On the Theory of Reinforcement Learning with Once-per-Episode Feedback. 2022. arXiv preprint arXiv:2105.14366
hltgg//bb/2105....0 14363
Paul Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences, June 2017. URL hRLp:t//////x 1706. 03 741 1xXiv:106.00744 [cs, stat] version:
abs/
Carlos A. Coello Coello, David A. Van Veldhuizen, and Gary B. Lamont. Evolutionary Algo- rithms for Solving Multi-Objective Problems, volume 5 of Genetic Algorithmss and Evolutionary Computation, Boston, MA, 2002. Springer US. ISBN 978 1 1-4777-5186-4 978-1-4757-5184 URL http: http:://iinnkssriggee.ee. www.nger.reccr..r www.//nrrrr.o///// 1007/
0. doi: 10.1007/978-1-444 0114445774444
978 47577-5118-0
Xu Chu Ding. Stephen L. Smith, Calin Belta, and Daniela Rus. LTL Control in Uncertain Envi- ronments with Probabilistic Satisfaction Guarantees, April 2011. URL htttt::://aa/...rrttttt
abs/1104. 1159 arXiv: 104. [cs, math].
Dylan Hadfield-Menell, Anca Dragan, Pieter Abbeel, and Stuart Russell. Cooperative inverse reinforcement learning, 2016. arXiv: 1606.03137 [cs.AI].
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 Abjeti-O Reinforcement Learning and Planning. Autonomous Agents and Multi-Agent Systems, 36(1):26, April 2022. ISSN 1387-2532, 1573-7454. doi: 10. 1007/ 10/.////////0000000 04458-022-09552- URL http: arxiv. /bbs/ 21 030.. 09568 mrXiv:210300955 [cs].
10

---

Elad Hazan, Sham M. Kakade, Karan Singh, and Abby Van Soest. Provably Efficient Maxi- mum Entropy Exploration, January 2019. URL U.LLattt.//axxx...rr/////////// arXiv:1812.02690 [es, stat].
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using Reward Machines for High-Level Task Specification and Decomposition Reinforcement Learning. In
Proceedings of the 35th International Conference on Machine Learning, pp. 2107-2116. PMLR,
July 2018. URL Sittps://proceedingg .mrpssmmrrr... htt.a///mm..........ss/////aarra 2640-3498.
html ISSN:
Rodrigo Toro Icarte, Ethan Waldie, Toryn Q. Klassen, R. Valenzano, Margarita P. Castro, and Sheila A. Mcllraith. Learning Reward Machines for Partially Observable Reinforcement Learning. September 2019. URL https: www. www.sticscchola...c.oo wwtp://a......g.pprrr...pe.p
laa - Waldie/
Ammar Jalalimanesh, Hamidreza Shahabi Haghighi, Abbas Ahmadi, Hossein Hejazian, and Madjid
Soltani. Multi-objective optimization of radiotherapy: distributed Q-learning and agent-based
simulation. Journal of Experimental & Theoretical Artificial Intelligence, 29(5):1071-108
September 2017. ISSN -13X.
doi: 10.
URL https Publisher: Taylor & Francis _eprint:
//doi. 1080 /29508/9928110 2017. 2017.1292319 https://doi..og//00. 100000055213XX2017....0.2
292319
M. Lahijanian, S. B. Andersson, and C. Belta. Control of Markov decision processes from PCTL specifications. In Proceedings of the 2011 American Control Conference, pp. 311-316, San Francisco, CA, June 2011. IEEE. ISBN 978- 1-4577-00811 978-1-4577700888 978-1057077777771777-777777000
8. doi: 10.1 11111///.21111599990 59909527
URL http:://eeeeplooreeee...ooo. www.:reeeeee.................
Michael L. Littman, Ufuk Topeu, Jie Fu, Charles Isbell, Min Wen, and James MacGlashan. cetiromment-Independdee
Task Specifications via GLTL, 2017. URL /tt.ttpp///arrrrr.rr///////////0
[es].
Sridhar Mahadevan. Average reward reinforcement learning: Foundations, algorithms, and empirical
results. Machine Learning, 22(1):159-195, March 1996. ISSN 1573-0565. doi: 10.1007/
14027 /ttpa////.....attpp////.oooo.. /tl.:ttppp//oooocrrr//0.0000//20
Zohar Manna and Amir Pnueli. The Temporal Logic of Reactive and Concurrent Sys- lems. Springer, New York, NY, 1992. ISBN 978-1-4612-69550 978-1-4612-0931-
7. doi:
URL
978 978-1-4612-0931-
Shuwa Miura. On the Expressivity of Multidimensional Markov Reward, July 2023. | w/wxxiv.rrgaab/////..
12184 arXiv:2307.12118 [cs].
Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Convex Rein- forcement Learning in Finite Trials. Journal of Machine Learning Research, 24(250):1-42, 2023,
.hmml
Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Challenging Common Assumptions in Convex Reinforcement Leaminng Jamuary 2023. URL http::/arxxv
org/abs/ 2202. 01511 arXiv:2202.01511 [es].
Daniel Neider and Ivan Gavran. Learning Linear Temporal Properties, September 2018. URL 03953 arXiv:1806.0390 00650033631333000003333333333333 [cs].
http://arxiv. wwtp://////aaaaoooooooo
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling RL: Reinforcement Learnng with
Trajectory Preferences. CoRR, abs/2 1111111000,0,, 2021. URL
2111. 04850)
Silviu Pitis. Rethinking the Discount Factor in Reinforcement Leamning A Decision Theoretic Ap- proach, February 2019. http: aawii.iiiiv../aa//aaaaaaaaaaaawa wwwpv/ogg//b///122.... 02893 arXiv:1902.00 1902.0299999 [es].

---

Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley and Sons, Inc., USA, edition, 1994. ISBN 0-471-61977-9.
D. M. Roijers, P. Vamplew, S. Whiteson, and R. Dazeley, A Survey of Multi-Objective Sequential Decision-Makinn Journal of Artificial Intelligence Research, 48:67-113, October 2013. ISSN 1076-9757. doi: 10. 19...377ja...397. URL hattps://wwy Jair ozg/ index. php/jair article/vies 10836
Mehran Shakerinava and Siamak Ravanbakhsh. Utility Theory for Sequential Decision Mak- ing. In Proceedings of the 39th International Conference Machine Learning, pp. 19616-19625. PMLR, June 2022. URL
shakerinava222 html] ISSN: 2640-3498.
David Silver, Satinder Singh, Doina Precup, and Richard S. Sutton. Reward is enough. Artificial Intelligence, 299: 103535, October 2021. ISSN 00043702. doi: 10.1016/j.artint 103535. URL
https:///ini
e sevier.... wwt. /ttp://ww..///eeeerree////////10
Joar Skalse, Matthew Parrugia-Roberre Stuart Russell, Alessandro Abate, and Adam Gleave. In- variance in Policy Optimisation and Partial Identifiability in Reward Learning, June 2023. URL
007475
artp:55axiii22000 arXiv:2203.0747; [es, stat].
Joar Max Viktor Skalse and Alessandro Abate. On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks. June 2023. URL
net/forum http:/oorummmiddcc//3///33//33
L.A. Steen and J.A.J. Seebach. Coumterezampple in Topology. Springer New York, 2012. ISBN 978- 1-4612-6290-9. URL httttttts///ookss wow.lss.oooooooooooooooo
Richard S. Sutton. The reward hypothesis, 2004. URL Uttphtppp//hncomplleeeeeeees net/
Flai. cs. ualberta.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT Press, edition, 2018. ISBN 978-0-262-35270-33
Rodrigo Toro Iearte, Toryn Q Klassen, Richard Valenzano, and Sheila A. Mcllraith. Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. Journal of Artificial Intelligence Research, 73:173-206 January 2022. ISSN 1076-9757. doi: 10.1613/jair..11444
URL httph:://///m. / org/ index. wwt.nnwwwpppppppppeeempppppppppp phpp jair httpaarriiieeieieeeeeeeeeee 12440
Peter Vamplew, Benjamin J. Smith, Johan Källström, Gabriel Ramos, Roxana Rădulescu, Diederik M.
Roijers, Conor F. Hayes, Fredrik Heintz, Patrick Mannion, Picter J. K. Libin, Richard Dazeley, and Cameron Foale. Scalar reward not enough: a response Silver, Singh, Precup and Sutton (2021). Autonomous Agents and Multi-Agent Systems, 36(2):41, July 2022. ISSN 1573-7454, doi: 10.
09575-5. URL/tttps://doi... http:///oooooogg//////// 1007 00w.0000//0005002222000000000000
Von Neumann and O. Morgenstern. Theory of games and economic behavior. Theory of games and economic behavior. Princeton University Press, Princeton, NJ, US, 1944. Pages: xviii, 625.
Wang, Yang. Z. An, Han, Zhang, R. Mangharam, M. Ma, and F. Miao. Multi-Agent Reinforcement Learning Guided by Signal Temporal Logic Specifications. arXiv preprint urXiv:2306.06880 2023. http::/:: wtt.aaawwww...aaa///aaaaaaa
06808
Christopher C. H. Watkins and Peter Dayan. Q-learning. Machine 1992. ISSN 1573-0565. doi: 10.1007/BF000926698. URL https::///ii.org//.... BFC0992698
May
Feiyang Wu, Jingyang Ke, and Angi Wu. Inverse Reinforcement Leammor with the Average Reward Criterion, May 2023, URL http:p///aarr...or//////20.....3 [es].
arXiv:2305.14608
Tom Zahavy, Brendan O' O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex MDPs. 2023. arXiv preprint arXiv:2106.00661. hRRpstpps:// :ttp://:////xi.i..// www.wiwww.g.........o..... 21 F106 00661
12

---

Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational Policy Gradient Method for Reinforcement Learning with General Utilities. 2020. arXiv preprint arXiv:2007.02151.
ab0 02151
Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd national conference on Artificial intelligence Volume 3, AAAI00,, pp. 57735-368-3.
Chicago, Illinois, July 2008, AAAI Press. ISBN 978-1-
13

---

GOMORE
expeess
COL-
UMN!
1.
13
14
34
8: 10
33
26
29
135355
15+
21
13
24
24
7
25
25
80
30
144
14134
14114
14:44
141344
16
13
24
7 24
7
25
RM
26
26
26 H13
26 L3
15
434
15H34
15:34
15434
13 33
15 15.44
15:344
154344
15 15
22
24
1111
24
7
INMR
13
21
21
15
21
35
H34
21434
K34
21
21 434
H34
21
2144
213344
21434)
24
7
IMORL
21
13
14
22
21
21
21
35
34
21 189
21 M334
21 1349
21 134
21
1544
21
134
21434
21 1341
21
24
22
7
241
11
FTR
15
13
15
21
21
35
34 7
34
34
34
7.
7
34
33
34-77
34
24
24
191
25
10
31
15
31 P
24
11 +1:5
ONNR
322
40
H15
40
38
34 1188
31+
30
52
24
OMORL
24
24
24
22
24 84
24
F2
24
24
11
1136
24
24
14 B
24
11
136
13
2-4
15
21
21
67
20
37
37
322
24
24
24
FILK
13
26
21
12
24
24
23 13
M
37.1
12
8
24
25
37
15
18
15
21
25
1000
20
10
110
10
10
10 P2
251
25
10
22
LD
25 +:36
25
23
25
H36
25
21
80
Table Comprehensive table of expressivity comparisons. A green cell indicates that the formalism in the ROW can express the formalism in the COLUMN, and red cell indicates that it cannot. The numbers in the cells are the numbers of the propositions which prove the result in question.

---

A APPENDIX: FURTHER DISCUSSION
A.1 POLICY ORDERINGS AS THE MEASURE OF EXPRESSIVITY
We opted to compare the expressivities of different inpective-specificatin formalisms in terms of the policy orderings they can induce because the policy ordering is the most fine-grained unit of analysis (that we are aware of) for this purpose. We explain why we believe it would be less informative to consider only formalism's 's ability to induce a desired optimal policy in Section 2. Another alternative is to consider a formalism's ' ability to induce a desired set of acceptable policies (SOAP), as proposed in Abel et al. (022). SOAPs are constructed by choosing a cutoff' value divide the policies into two classes (i.e., the acceptable and the unacceptable), and discarding all information about how the policies are ordered within each class. Thus, it is straightforward to that policy orderings contain strictly more information than do SOAPs, and so any difference in expressivity that captured by SOAP task definition is also captured by the policy ordering task definition. The latter is therefore the one that is maximally sensitive to expressive differences.
Additionally, our choice use the total preorder over policies as the unit of analysis is more continuous with the theoretical framework standardly employed in the formal theory of individual eecision-making
that context, the central question takes the form: Which preference orderings can be represented by utility function (of given sort)? For each of the formalisms considered in our paper, we ask a similar question: Which policy orderings can be represented by an objective specification in the formalism? We thought it would be valuable to maintain the parallels between these two questions in our paper (and discuss the connection explicitly in Section and Appendix A.5)
A.2 INDUCING TOTAL PREORDERS
Most of the formalisms in our work induce a scalar policy evaluation function, which in turn produces total preorder the set of policies because the ">" relation on IR is total preorder. The four formalisms that do not induce a scalar policy evaluation function (Occupancy Measure Orderings, Trajectory Lottery Orderings, Generalised Outer Multi- Mujti-Obeecttve RL, and Policy Orderings) all include a total preorder on some set in their objective specifications, and the policy orderings they produce inherit transitivity and strong connectedness from the specified total preorder.
A.3 HISTORY-DEPENDEN POLICIES
As mentioned in Section 4.1
one limitation of our work is that analysis of formalisms' ability to express orderings over the set of stationary policies may not match a similar analysis that considers orderings over the set of history-dependee results directly carry over to history-dependent policies. Firstly, if formalism A can express a stationary policy ordering that is not expressible by formalism B, then clearly A can express an ordering over history-dependent policies that B cannot. So every negative expressivity result (i.e., every red box in Table 2 carries over directly. Further, several of our positive proofs do not assume that we are considering only stationary policies. For example, all trivial results in Appendix B.] apply for distory-dependee history-dependen setting: it is fairly straightforward to show that a reward machine can provide different amounts of reward to two history-dependent policies that have the same occupancy measure, so Occupancy Measure Orderings (OMO) cannot express all history-dependent policy orderings that Reward Machines (RM) can express. This is a significant departure from our findings, in which OMO is near the top of the Hasse diagram and RM is near the bottom. We consider it interesting direction for future research to round out a comprehensive comparison of expressivity for history- dependent policies, especially given that some formalisms (such as Functions from Trajectories to Reals and Reward Machines) seem particularly well-suited to expressing tasks where history- dependent policies are essential. To support such an endeavor, we include incomplete table of expressivity relationships for history-dependent policies below (Table
policies. It is worth noting that many of our expressivity
policies as well. Unfortunately, not all of our results carry over to the
A.4 EXPRESSIVITY UNDER RESTRICTING CONDITIONS
One concern about the practical utility of some of our results as they stand is that they are largely blind to the ease or difficulty of using the theoretically available capabilities of the more expressive
15

---

formalisms for training models objectives that cannot be captured by less expressive formalisms. Some of our proofs lean heavily on technicalities of the formal definitions we offer, with little regard for whether those technicalities can reasonably be trusted to lie available to RL algorithms in practice. For example, the proof that INMR can express FTR relies on the fact that the Markovian trajectory return can be chosen be an injective function into the reals. In practice, however, computers can only store numbers with finite precision, so we cannot assume that arbitrarily close real numbers will always be distinguishable an RL algorithm.
An obvious suggestion for how this problem might be solved is to attempt to redefine each formalism in such a way that unreasonable technicalities are eliminated. Unfortunately, this strategy runs into familiar problem: virtually any formal definition of an informal concept can be "gamed" to flaunt the intended spirit of that concept. For this reason, we believe an alternative strategy might more fruitful: Replicate these results under various carefully chosen restricting conditions, whose purpose to ensure that our theoretically sound results can be trusted to hold up in practice.
We offer the following (highly incomplete) list of potential restricting conditions:
1. Introduce a cutoff to the precision of the inputs available to the functions wrapping the trajectory return(s) in INMR and IMORL, and wrapping the policy value(s) in ONMR and OMORL. This cutoff could correspond to the precision with which modern-day computers can real numbers.
2. Introduce various other constraints on these wrapper functions. For instance, we might require that they be continuous, differentiable, monotonic, analytic, or computable, among other options.
3. Introduce an upper limit to the number of reward functions that may be employed in IMORL, OMORL, and GOMORL. In particular, do not assume that this number may reach (or exceed) the number of transitions in an environment |S x A x S/.
A.5 CONNECTION TO THE VNM THEOREM
interesting to consider our results in light of the Von Neumann-Morge MoongnnnMorrenstteen (VNM) Utility Theorem. In particular, subject to a few assumptions, have the following: Any trajectory lottery ordering that cannot be induced by FTR must violate at least one of the VNM axioms.
To apply the VNM axioms, we need to restrict to an environment in which only a finite number of trajectories are possible, E - {E,, }.). Then, the VNM axioms read follows:
1. Total Preorder: Z over A(= is complete and transitive.
2. Continuity: For all Lm, Lm Lig E A(Eg) such that L,, > Lim, and Loz > Lmn, there exist a, 8 (0, such that Lzi > Lit and Lxz > Lon BL
3. Independence: For all Lx, LEgs Ling E A(EB) and for all (0,1):
Lxg > Luz > Lx, along bigabas
(Here LaM aL (1 a.M is the mixing operation.)
VNM Theorem: 2 over ((3g) respects Total Preorder, Continuity, and Independence if and only if there exists function E R such that for all La Ting E A(Ex),
Lx, ス Lag + Eg T, [u(E)] EE (u(E)]
Under the assumption that our policy preferences are determined by our preferences over trajectory- lotteries (such that T.z, T. = л1 M T2). the RHS simply states the condition that there exists an FTR objective specification, given by fETR. u, which induces this policy ordering. Thus, in an environment which there are only finitely many possible trajectories, any policy ordering that FTR cannot induce must violate either Continuity or Independence (Total Preorder is guaranteed to hold by definition). Insofar as is reasonable to evaluate policies based on the trajectory-lottert that they give rise to, and insofar our preferences over trajectory lotteries ought conform to Continuity and Independence, we might justifiably wonder whether there is much to be gained from moving up the Hasse diagram beyond FTR.
16

---

INMR
GOMORE
expeess
COL-
UMN!
1.
13
1
34
8 10
33
26
29
15+
21
13
24
24
7
25
25
80
30
144444
14134
141144
14:44
141344
16
13
24
7 24
7
25
RM
26
26
26 H13
26 L3
15 35
434
15H34
15:34
15434
13 31
15 15.34
15:344
154344
15 15
22
24
1111
24
7
INMR
13
21
21
15
21
35
H34
21434
M34
21
21
434
H34
21
2144
213344
21434)
24
7
IMORL
21
21
13
14
21
21
21
21
35
34
21 A89
21 M334
21 1349
21 134
21
1544
21
134
21434
21 1341
21
24
22
7
241
11
FTR
15
13
15
21
35
34 7
34
34
34 7.
7
34
34
34--7
34
24
24
191
25
10
31
31 31
24
19
11 +1:5
ONNR
40
10 003155
H15
40
40.11 L5
38
34 +8
52
OMORL
24
11 113
24
24
14 B
24
11
136
37
20
37
122
37
322
24
1.1
24
24
FILK
L..
13
14
26
15 21
5 21
12
24
24
25 13
+1377
M
37.1
177
12
9
25
37
15
18
15
21
A44
16
3136
11
1000
10
10 10+18
10
+
1D+B
10
10-12
23 FE
25
1D e
24
25 p:36
25
23
25
H36
13
25
80
Table 3: Incomplete table of expressivity comparisons using history-dependen policies. green cell indicates that the formalism in the ROW can express all history-dependent policy orderings that the formalism in the COLUMN can express, a red cell indicates that the formalism in the ROW cannot do this, and white cell indicates that the result not yet known. The numbers in the cells are the numbers of the propositions which prove the result in question.

---

B APPENDIX: THEOREMS AND PROOFS
B.1 TRIVIAL RESULTS OF EXPRESSIVITY(X 2 Y)
PO
TLO
Policy Ordering
FPR
GOMORL:
OMO
Objective
OMO: Ocoupancy Measure Ordarings
FTLR
GOMORL
Trajestory Lomory Orderings
Muti-Objeecvve
Oooupancy
Messures Reak
FOMR
FTR
OMORL
FTLR: Functions from Trajectory Lotterles to Reals
RRL: Regularised
ONMR Outer Non-lineer MR
IMORL
ONMR
INMR: Inner Non-lineer MR
RRL
LAR
LTL
Muts-Objective
INMR
from Trajectories
Reals
RM: Reward Machines
MR: Markov reward
Lirit Average Rewerd
Linear Tamporal Logic
MR
Figure 2: This diagram displays straightforward inclusions of formalisms that not necessarily strict. Unlike in [i the absence of sequence of arrows between two formalisms does not mean anything here. This diagram simply useful guide some basic positive results of expressivity proven in this section.
The propositions in this section are proven formally, but each proof is preceded by an intuitive argument. It will likely be helpful to have Table [ readily available for reference while reading these results and proofs.
Proposition B.1 (RM ΣEXPR MR). Any policy ordering expressible with Markov Rewards can be expressed with Reward Machines.
Intuition: A reward machine can use different reward functions depending on aspects of the history has seen so far. However, can also use constant reward function, which case is equivalent to Markov Rewards specification.
Proof. Let (RMR, 7MR) be an arbitrary MR objective specification in arbitrary environment. Then the following RM specification (U, un du, δR, 7) expresses the same policy ordering:
U {uo}
up = 240
Vs E S, (uu, 8) = ug, where S is the set of states in the environment
tz (uo, uo) = RMR
:= 7MR
18

---

Since the specified reward machine always utilises the same reward function and discount factor as the MR specification, it yields the same exact policy evaluation function.
JRA (T) = TTI.u.
Re as, 8(+1)
where Rr = (ut, u++1)
= =BEwxTT
Σ
nun R MR( au S441) since u, = uov't t and óR(20. uo) = RMM
JMR((T)
Both RM and MR derive policy orderings directly from the policy evaluation functions, so this means the two specifications induce the same policy ordering. Therefore, for any MR specification in any environment, it is possible to construct an RM specification which expresses the same policy ordering.
Proposition B.2 (INMR ΣEXPR M). Any Markovian Reward specification can be captured by an Inner Nonlinear Markovian Reward specification. (4E E Enws, Ordmn(E) = OrdINMn(E))
Intuition: If the wrapper function in INMR is set to be the identity function, then that function becomes idle, and the INMR policy evaluation function reduces the MR policy evaluation function:
Ex JINMA((T) = [f(G(E)) = Ex [G(E)] =: JMR(T)
Proof. We must show that for any environment and Markovian Reward specification OMR = 7), there there is an Inner-nonlinear specification OINMR = (R,
f.5) such that 5F,OrNMR is identical
3E,0sR We construct MINMr follows:
:= R
::R + RR is the identity (f(x)= = xt).
We can immediately that Jg,OMER R (T) JE,OINMA (T) for all E llg, and thus these two specifications induce the same policy ordering.
Proposition B.3 (LMORL ΣEXPR INM R). Any policy ordering expressible with an Inner Non- linear Markov Reward specification can expressed with an Inner Multi-Objective RI. specification.
Intuition: IMORL always choose to the reward function, wrapper function, and discount factor as INMR, and can always choose not to use more than one reward function.
Proof. Let (RINMR: JINMR MINMR) be an arbitrary INMR objective specification in an arbitrary environment. Construct the IMORL specification (k, R, f.)) as follows:
k
R = RINMR (since 1, RR = R. and R is a function from S x A to
f = FINMR
. = YINMR
We can see immediately that JIMORL (T) = JINMR(T) for all π E Igg, and thus these two specifications induce the same policy ordering.
Proposition B.4 (FTR EEXPR IMORL), Any policy ordering expressible with an Inner Multi- Objective RL specificaatin be expressed with Function from Trajectories to Reals.
19

---

The expression f(Gi(E), Gx((E) in the IMORL policy evaluation function is function from trajectories to reals.
Intuition:
Proof. Let (k, R. fIMORL. 7) be an arbitrary IMORL objective specification in an arbitrary environ-
ment. Then the following FTR specification (fFTR) expresses the same policy ordering:
(FTR(E) = FIMORL
Σ
Here, (,)),, = R(s, [t]. This is a function from trajectories to reals because trajectory Ç = { du, $1, 01....) uniquely defines (St, at $t+1) for all f.
Proposition B,5 (RRL ΣEXPR MR). Any policy ordering expressible with Markov Rewards can be expressed with Regularised RL. (E E Encs, Ord OrdRRI
Intuition: The additional term in the RRL objective, aF[[=ss)] can be set to zero by selecting 0. This makes the RRL objective identical to the MR objective.
Proof. We must show that, for any environment E' and Markovian Reward specification OMR = (R, 7). there Regularised RL Specification ORRI. (R, ã, F,5) such that Ke,OrRl identical to 38,0um We construct ORRL as follows:
R R
F: AA + any function.
ā = 0 7
We can see immediately that JE, (T) = JE,ORaU (T) for all π II. and so these two specifica- tions induce the same policy ordering.
Proposition B.6 (ONMR EEXPR MR). Any policy ordering expressible with Markov Reward specification can be expressed with an Outer Nonlinear Markov Reward specification.
Intuition: ONMR can specify the same reward function and discount factor as MR, then select the identity wrapper function so that the function does not affect anything.
Proof. Let (RMR, 7MR) be an arbitrary MR objective specification in arbitrary environment. Construct an ONMR specification (RONMR.,. as follows:
RONMR RMR
: I. is the identity function, f(x)
1ONMR = 7MR
We can immediately that Jr, JE.0ONMa (T) JE,Oua (T) for all E TTg and so these two specifications induce the same policy ordering.
Proposition B.7 (OMORL EXXP ON R). Any policy ordering expressible with an Outer Non- linear Markoy Reward specification can be expressed with an Outer Multi- Multi-Objectiive RL specification.
Intuition: The OMORL specification use the same reward function, discount factor, and wrapper function as ONMR, and can simply not use more than one reward function.
Proof. Let (RON CoWWR--oOMMR a: RR) be an arbitrary ONMR objective specification in an arbi- trary environment. Construct OMORL specification (k: R., f))) as follows:
20

---

k
RONMR (since l 1, 1R =R and is function from & =R)
f fONMR
. YONMR
We can immediately that JE, MooOo. (④) JE. 1..OONmn (T) for all Igg, and these two specifications induce the same policy ordering.
Proposition B.8 (FTLR ΣEXPR FTR). Any policy ordering expressible with Functions from Trajectories to Reals can be expressed with Functions from Trajectory Lotteries to Reals.
Intuition: One way to evaluate trajectory lottery is to assign values to each individual trajectory and then use the probabilities from the lottery take an expectation. function from trajectory lotteries to the reals that does this is equivalent to an FTR specification that assigns the same values to individual trajectories.
Let (JFTR) be arbitrary FTR objective specification in arbitrary environment, Then the following FILR specification (JETLR) expresses the same policy ordering:
Proof.
fFTLN(L=) = I [frTn(E)]
Here, Lx is the lottery over trajectories that is produced by policy x the environment. Since JFTLR(T) = feTLR(LZ), the equivalency of JETLR and JETR is immediate: JPTLA(T) fFTLR(La) EEE [fFTR(E)] =: JFTR(T).
Proposition B.9 (FPR EEXP FTLR), Any policy ordering expressible with Functions from Trajectory Lotteries to Reals can be expressed with Functions from Policies to Reals.
Intuition: An FTLR specification assigns value to each policy based on the trajectory lottery generates. This is evidently expressible a policy evaluation function.
Proof. Let (JFTLR) be an arbitrary FTLR objective specification in an arbitrary environment. Then the following FPR specification (JrrR) expresses the same policy ordering:
-FPR((T) = SFTLR((.s)
Here, La is the lottery traeectories that is produced by policy in the environment. Since JFTLR(T) = (LT) the equivalency of JETLR and JFPr is immediate.
Proposition B.10 (TLO EeXPr FTLR), Any policy ordering expressible with a Function from Trajectory Lotteries to Reals can be expressed with Trajectory Lottery Ordering.
Intuition: A function from trajectory lotteries to the reals induces total preorder because the ">" relation R is a total preorder. This same total preorder can always be expressed directly over the trajectory lotteries as well.
Proof. Let (fFTLR) be an arbitrary FTLR objective specification in an arbitrary environment. Then the following TLO specification (zz) expresses the same policy ordering:
Ln, IL Lag > fFTLR(La.) fFTLR(L..)
Here, L, is the lottery over trajectories that is produced by policy т in the environment. This > is valid total preorder Ln because it transitive and strongly connected.
21

---

Now:
Mi Corio "2 - Lig EL Lun
SETIR( 2 (FTLNN(ITT))
(FTLR((T)) 2 JFTLR((T2)
Tt E0TTR 92
Proposition B.11 (GOMORL EEXPR OMORL), ). Any policy ordering expressible with an Outer Multi- Objective RL specification can be expressed with Generalised Outer Multi- Sbititvbeeetivve RL specification.
Intuition: An OMORL specification orders policies according to the values assigned by a function from policy-evaluation vectors J(()) to the reals. A GOMORL specification can directly order the policy evaluation vectors the same way. That is, f(Ji) 2 S(J2) - Jn ZJ J2.
Proof. Let (KOMORL, f. be arbitrary OMORL objective speci-
fication in an arbitrary environment. Then the following GOMORL specification (KGoMORL, Sccomorl:"GoMondd expresses the same policy ordering:
keOMORL KOMORL = k
ReOMORL ROMORL
1GOMORL TOMORL
vJ1, E R² ((J) 2 f(22) = J1 Jn
With this specification:
का OOMORL T2 - [(J(TI)) 2 ((((m))
b ((m) EJ J(mz)
कI LoGMOOL T2
Proposition B.12 (PO ΣEXPR for any objective specification formalism F).
By definition, any policy ordering in any environment is expressible with Policy Ordering specifica- tion (Z+).
Proposition B.13 (FTR ΣEXPR LAR). Any policy ordering expressible with a Limit Average Reward specification be expressed with Function from Trajectories to Reals.
Intuition: The limit average reward is value assigned to trajectory. A function from trajectories to reals can assign the limit average reward of a particular reward function to each trajectory.
Proof. Let (R) be an arbitrary LAR objective specification in an arbitrary environment. Then the following FTR specification (frrR) expresses the policy ordering:
N-1
fFTR(E)
lim N-+0c
R(su, ae, 81+1)
N
Then:
N-1
1
JLAR(T) lim
ExTT.
R(st, ar 8141)
No00
N
22

---

We have bounded rewards, i.e. V(st, de, St+1), R(st, at, S(+1) < Rmaz. where Rmar is the maxi- mum reward assigned to any transition by the reward function. This means that the average reward converges: 1im Et= (st ae, $141
< oc. These two facts and Lebesgue's Dominated Convergence Theorem imply that we can move the expectation outside the limit. So:
(LAR(T) = Ex
lim N
Σ
R(s, a2 s1+1)
N
The expression inside the expectation equal (Frn(E), therefore:
JLAR(T)) = -ExTT [fFTR[E]] JFTR(T)
Proposition B.14 (FTR ZExpR LTL). Any policy ordering expressible with Linear Temporal Logic can be expressed with Functions from Trajectories to Reals.
Intuition: An LTL formula a function that assigns the value 0 to trajectories in which the formula false and the value to trajectories in which the formula is true. This is a special case of function from trajectories to reals.
Proof. Let (5)) an arbitrary LTL. objective specification an arbitrary environment. Then the following FTR specification (fFtR) expresses the same policy ordering:
fFTR(() = sp()
(An LTL formula assigns a truth value of 0 or 1 to any given trajectory, so formula is a function from trajectories to {0, 1). This is special case of function from trajectories to reals.)
Proposition B.15 (FTR ZEXPR RM). Any policy ordering expressible with Reward Machines (RM) can be expressed with Functions from Trajectories to Reals (FTR).
Intuition: Reward machines give step-by-step rewards in a trajectory based on aspects of the history so far. The behavior of a reward machine for an entire trajectory is fixed by the states and actions in the trajectory, so the discounted sum of rewards that reward machine yields is function from trajectories to reals.
Proof. Let (U, ug 80, 8R.7) ) be an arbitrary RM objective specification an arbitrary environment. Then the following FTR specification (SFTR) expresses the policy ordering:
SFTR(E) = E yt (U,, us41) at, St+1))
Here, is the state of the specified reward machine at time step f. This value is well-defined given U, uo, dy, and ç, because un is the starting machine state, and given a machine state at any time t, We-1 dy (U,, St, de, 8t.1). ). & specifies 8; and a, for all and given up and dG. the machine state at any time step can be derived using this rule iteratively starting from tgg-
Since i, is well-defined for all so is ōR (1,, 1.+1). and is fFTR(E).
This FTR specification induces the same policy ordering as the RM specification above:
ESt JFTR(T): = IP
[FFTR(E)]
00
E
Σ
rd (ŌR (uR, (ot1) (e,
g
(T)
23

---

Both FTR and RM derive policy orderings directly from the policy evaluation functions, this means the two specifications induce the same policy ordering.
Proposition B.16 (FTLR ΣEXPR RRL). Any policy ordering expressible with Regularised RL (RRL) can be expressed with Functions from Trajectory Lotteries to Reals (FTLR).
Two policies generate the same trajectory lottery if and only if they are identical on all states that either policy ever visits with nonzero probability. two policies are identical on all states visited with nonzero probability, then an RRL specification must assign them the same value. Therefore, a well-defined function can take a trajectory lottery as input and output the value assigned by an RRL specification all policies that generate the given trajectory lottery.
Intuition:
Proof. Let (R, at, 7) be arbitrary RRL objective specification in arbitrary environment. Then the following FTLR specification (SFTLR) expresses the same policy ordering:
fFTLA(LL) := (n) = & Eir Σ rs
aF(T(S)))
Here, Lx is the lottery over trajectories that is produced by policy π in the environment. Since JFTLR(T) == (rrrn((.z), the equality of JETLR and JRRL all policies is immediate. However, we must verify that this function from trajectory lotteries to reals well-defined, i.e. that I Laz (RI)((T) = JRRL(
Since rewards in Regularised RL are given step-by-step, the policy evaluation function can be rewritten as follows:
Ext
JRRL(T) = 7' (R(S,, A,, S141) -of
1=0
00
JRRI(TT =
Σ
PE = 8, A, 4 -- -
E
t= (=xx)"))SxAx5
Lemma B.17. If Lmy Ligg then for all L and for all (8,a,8) E Ax
P 8
[S 8, A = a, S s7 E. [St s, A: a, S1+1 =
Proof of Lemma. First recall the definition of a trajectory lottery:
Eet be the set of all initial trajectory segments of length 2(k+1). We write [e] for the first 2 1) elements of &. Define La,* A(Ex) L (Ex (so. 40, .... Sk: ax)) = PENNIIIII
Ex). A
trajectory lottery Lx then defined the infinite sequence of L Lx (Lo,z LI L2.
Now, let ss.as(,.,,s') be the set of trajectory segments of length 2(t + 2) which have (8, a,,a) 5²) as the most recently completed transition. We can then see that for given and
P P = s, A, = a, S.+1 = s'1
Σ
Let1,
Equivalently, in words, the probability that the transition (s, a, s') is taken from time step to + equal to the sum of the probabilities all the trajectory segments of length + 2 that have the transition (s, a, s') from time step / to + 1. (The reason we look at trajectory segments of length t is that time indexing starts at O, so we need / + 2 steps to get to the step indexed by 1.)
The right-hand side of this equation is fully determined by Lyp the left-hand side is also fully determined by Lę. This completes the proof of Lemma B.17
Corollary B.17.1. If Tom, Tong then for all and for all S. s] =P
1F s).
24

---

This follows straightforwardly from Lemma B.17 marginalising and s'.
Corollary B.17.2. If Lx1 Lan then for all and for all (s,a) E x A, P pl [S. 8, Ar = =a]
P. [S s, a).
This follows straightforwaardy from Lemma B.17 by marginalising over s'.
Corollary B.17.3. If Lx, Lun then Tz (s) (s) for all states that either policy ever visits with nonzero probability.
Proof of B. 17.3 First, note that if either иi or #2 ever visits state s¹ with nonzero probability, then
by 1.1 there exists l" such that Iee.. [Sp. = s*] = p p [Sp- = s' > 0. If क (s") * T2()"),
there must be an action a" such that тi (a" |s*) > 12(a"(s s*)) But by [.17.2 we know that since
Tu w: IP [S: s", A, = =a] = { n2 [S, = 8 A, a*). Thus:
; A P [S, = (a' P = [S, s s'|m=(a"|1s
P [St =s"
a²) == x (S:
s" A. a'l
{
$ [S: = mm)m (a" (8*) = (S. = 8* =2("1('''''
(by Corollary 1.17.1
(1"""""") x2(a"|s"
So the two policies must agree on s after all.
We require more lemma to show that L.z, T. (n) = Jnni
Lemma B.18. If Lm, Lx.- then for all t for all (s, a, s') E S x A S:
p.. [S A S = s²| (n' (R(s, a, a (s)])) p
8, S, S.-1
(R)sss())) a (F(T)())))) for any RRL specification (R, a.,,F,F1 F,7).
Proof of B.18
Lemma B.17 states that LT, L then for all and for all (s, a 8') ESxAX.
F [S Ar = S,1111 = PP. I s, = a, S = =s1
So it remains to be shown that p. [S: = =
(7 a, s') oF (s)))) =
F. [St = 8, A, = a, St- = 8 (7 (R(s, a, - aF((sss)))) Consider the following two cases.
Case 1: _ I [S A S =s] = 0. In this case, because both sides are equal to 0:
P PE [S a S (R' aF aF(m(()))) _...
pe. F - A -=
Case 2: F [St = s, A; = a, S = 81 > 0. In this case, Ti (s) = (2(5) by Corollary B.1.. Therefore, (7 (R(s, s') - aF aF
(s))) (F)
= (7' (R(s, (T(T)())))) and by extension:
p I. [S: s, A; = a. S.+1 5 ()'
a (F(m((s))) ...
P P. A, a, S (R(s, a, a' aF aF (s))))
Since these cases are exhaustive, this concludes the proof of the lemma.
Finally, recall that:
JRRI (T) == Σ Σ
PE S A, = = - = aF(((s)))
t= (XS
25

---

By Lemma B.18 Lx Liz (R) JARL (T2). This means that the FTLR specification given by FETLR Lx) (RRL(T) is well-defined.
Both FTLR and RRL derive policy orderings directly from the policy evaluation functions, this means the two specifications induce the same policy ordering. Therefore, we've shown that for any RRL specification in any environment, it is possible construct an FTLR specification which expresses the same policy ordering. This concludes the proof of the proposition.
Proposition B.19 (FTLR EEXPR OMORL). Any policy ordering expressible with Outer Multi- Objective RL (OMORL) can be expressed with Functions from Trajectory Lotteries Reals (FTLR).
Two policies generate the same trajectory lottery if and only if they are identical on all states that either policy ever visits with nonzero probability. If two policies are identical on all states visited with nonzero probability, then an OMORL specification must assign them the same value. Therefore, a well-defined function can take trajectory lottery as input and output the value assigned by an OMORL specification to all policies that generate the given trajectory lottery.
Intuition:
Proof. Let k, R. be an arbitrary OMORL objective specification in an arbitrary environment. Then the following FTLR specification (SFTLR) expresses the same policy ordering:
fFFLA(LL)) = JOMORL(T) == = (JI(T),... Jx(z)), where
(TT = Rgg Σ 7 (R,, 81+1))
Here, La is the lottery over trajectories that is produced by policy æ in the environment. Since JFTLN(T): == [PTLA((<z) the equivalency of JETLR and JoMoRs. immediate: JFT =
JFTLR( (.x) == (T)) However, we must verify that this function from trajectory lotteries to reals is well-defined, i.c that La, Laz = JOMORL (T1) = JOMORL(TT) A trajectory lottery and OMORL specification together fix all relevant quantities for computing (,) :=
E
Σ R'R,(Si, 0z, S4+1) for all E [k]. Given all the J; values, the OMORL specification also
fixes
Therefore, a trajectory lottery and an OMORL specification together uniquely specify a value of (OMORL(T)) = J4, and fETLR above is well-defined.
Both FTLR and OMORL derive policy orderings directly from the policy evaluation functions, so this means the specifications induce the same policy ordering. Therefore, we've ve shown that for any OMORL specification in any environment, it is possible to construct an FTLR specification which expresses the same policy ordering.
26

---

B.2 NOVEL RESULTS EXPRESIVITY (X N Y)
Lemma B.20. For any environment E (S.A,T.I), there exists reward R: xxxxxxx +R and discount factor [0, such that the trajectory return function G(g) := Σ >'((S,, Se41)
is injective.
Proof. Let X be finite set with |X| 1 and let = = X be the set of infinite sequences of members of X. Let R X + R be reward function and let E [0, 1) be discount factor. Define GR - R such that G(E) 2 (xx)).
Let the reward function R. be any injective function. Since X is finite and R. is injective, there exists positive real number M y ([R(x) R(y))). Also, since R injective, there exists nonzero positive real number m = minewee ([R(z) - Ryy)l) (for # y).
Now let Eι and & be two sequences that differ first at position s. Then:
-(E)) = Σ (R((z) - -R(y)) = 7xt ( - R(y+))
(((())
Since ε and &2 must differ at position (r - 0), the difference of rewards at that position must be at least m. Subsequently, the difference of rewards can be at most M. So we can try to compensate for the difference of m 0 by subtracting differences of M positions 0.
7M We will never be able to fully compensate if m 1-7
m(1 7) AM (*).
Note that since M m, we must have 7 <1/2.
But also, the maximum difference between reward assignments must be at least ([X) - 1) times the minimum difference, we have the constraint: M m([X] 1). Combined with (+), this entails that y < 1/|X|
Thus, for any 7 satisfying this constraint, simply take injective reward function R X (0, m,.,, mx[ 1)}. Then for any two sequences & and &g that differ anywhere, the difference between their corresponding trajectory returns G(f1) and G(E2) will be nonzero. Thus, have chosen R and such that G E > RR is injective (and we can always make it surjective by restricting the codomain to the image of E under G).
Note that this scheme will result in a very small y for large enviroments. Next we will use this lemma to prove that INMR, IMORL, and FTR are equivalent.
Inner Theorem B.21 (INMR ~EXPR IMORL ~EXP FTR (Theorem 3.1 Section Nonlinear MR (INMR), Inner Multi-Objective RL (IMORL) and Functions from Trajectories to Reals (FTR) can each express every policy ordering on any environment that the other two formalisms can express
Proof. It is trivial that IMORL can express INMR and that FTR can express IMORL and INMR, so if we prove that INMR can express FTR we have proved that the three formalisms are equivelent.
We need to show that, given any FIR objective specification (f), there exists an INMR objective specification (R, y, h) such that h o GR.
To show this, we use B.20
If the state space S and action space A are both finite, then it is always possible to specify a reward function R: S A x S + IR and a discount factor E [0, 1) such that the function GR,y E > R an injective function.
Hence, choose (R, 7) such that GR. is injective. We can also make it surjective by restricting the codomain R to the image of =\t under GR,y- Thus, we can make GR,, invertible.
Then, construct h R R as: h f G-1
27

---

As discussed previously this proof requires arbitrarily complex functions and infinite precision to hold in the general case. In many practical situations it would be reasonable to say that FTR> EXPR IMORL EXPR INMR but it is still interesting that these formalisms equivalent in the unrestricted mathematical sense.
Lemma B.22. Let JOMORR((T)
JA((T) E R for an OMORL specification OOMORL (k, R. Then for any environment E (S.A.T.I) and any FOMR specifi- cation CTrOMR;"FOMER there exists an OMORL specificatinn OOMORL = (k. R. such that JOMORL(T)) mmT).
Proof. Since m)) E RIS||A|SS and (OMORI(T) E RR, must equal |S|||||S] in order to allow JOMORL(T) m(T). Let us define |S| x |AI x |S] reward functions indexed by s' triple, as follows: Ryja (St, ams sn) = jm Here, is the Kronecker delta function:
1, if b, 0, otherwise.
bab
Essentially, reward function Razk provides reward for the transition (8i, ajj 88) and reward O for all other transitions. Also, let ? = FFOMR. Then,
(m)
Σ
P(s -1,0 = am, 8141 8n, Rijje am, 8n)
Lmm
Σ
Σ
YFOMRP = 81, ar = am, 8t41 - 8y, 6m10 Okn
Lma.
ErhomnP =3, ar 0s+ = sk)
=: =: snl
Since all components of JOMORL(T) and m(()) match, JOMORE(T) = m(T).
S Ax could very large number of reward functions and therefore in many practical situations FOMR EEXP OMORL and OMO ExPR GOMORL.
Lemma B.23. For any environment E (S,A,T,I) and discount factor m((1) m((22) La,
Lag-
Proof. Direction 1: Lg, Liz = m((1) = (m2)
Consider the set Ei {Ex Eg 33 ag o, 8k+1 s'}. Then,
(a( s, as a, 8641 = 5)) Σ
LM,
S+E=
If T.m, -Iyg then LA,5, Lk,,, Vk E N. Thus, every time-step t:
(3) -, 5))= Σ
Li,, (Ex)
Σ
Li (Ec) = PRy s, = a, =
E
E,
Therefore,
m Σ P'P (8, = 3, 0, = a. a,4111 = 8') Σ
2 P s, = = = [,)))sas)
1=
t=0
Direction 2: mi(m))) TT(22) - Lr, Lug
To prove this direction will show the contrapositive, i.e. Tom, # Tong m(m) mm(2))
28

---

Suppose Lm Lag- This means there exists state and subsequent state s' that both policies visit with the same nonzero probability such that क (s) # Ty(s). (This might be the initial state, if they diverge right away.) If they were identical every visited state, they would produce the same trajectory lottery. There must be two actions, d1 and d2 such that Tı (41 8) > T2(a1 (8) and T2 (a2l)))) > T (a2ls). For both sets of probabilities to sum to one, #i can't assign greater probability to all actions at s.
Now, considering the transition to s':
m( a1, s1, ( ) a22 85]
Pep (St = s.0, a0, 5r)
L, Ptp (8t 8, Ut 02 8/1 = 8')
Ee P (8t () 011s: s)T(5141 = =s = =1, 8: =
P m (st = s) 02/9 = s)T = =s'la; = =02,
Since we're considering stationary policies only, T (a = als; = s) = ni (a)ss) The transition function is also time independent. Therefore:
m( s'] [s s2 <1(22|s)T(s{ a2 8) E. 7¹ Pr =s) (1 8 () 02, $)
{1(a)ls)T(s' a1 8) E =8) (a (((sss) s)
Similarly,
m(Fe)ls, 01 81
(a(a|s))TC s)
m( [s, 02 s5
m2(02|))] s)T 13//a22..
From the inequalities Ty (arls) > (a)s)))) and T2 > क (ag 1s. we deduce:
x (a ss)
(ail(s))
m( وs, a1, ( (2, m( & 02 81
m(T))ss,a.. 88
m {02ss)
T2 (22l8)
Thus, m)(T)) + m(T)).
Note that this proof requires stationary policies; non-stationary policies, the above will not necessarily hold.
Theorems B.24 and B.25 follow fairly straightforwardly from Lemmas B.22 and B.23
Theorem B.24 (OMORL EXPP FOMR ~EPP FTLR (Theorem 3.3 in Section 3h). Outer Multi-
Objective RL (OMORL), Functions from Occupancy Measures to Reals (FOMR), and Functions from Trajectory Lotteries to Reals (FTLR) can each express every stationary policy ordering on any environment that the other two formalisms can express.
Proof. From lemma B.22 we can choose the OMORL reward functions Risk such that the associated Markovian policy evaluation functions Jiyk form components of the policy's s occupancy measure. If we apply the same function ʃ to both the vector of Jizk functions and the occupancy measure we get that Josone (T) (JoMoRL(T)) =
(T) From lemma B. B.23 we have that occupancy measures and trajectory lotteries uniquely determine each other and as such we can choose corresponding functions fFOMR and FFTIR such that both FOMR and FTLR induce the same policy orderings. We have now proven that OMORL, FOMR, and FTLR are equally expressive.
(*)( (
Theorem B.25 (GOMORL ~EPP OMO ~EXPR TLO (Theorem 3.4 in Section B) ). Generalised
Outer Multi- Objective RL (GOMORL), Occupancy Measures Orderings (OMO), and Trajectory Lottery Orderings (TLO) can each express every stationary policy ordering on any environment that the other two formalisms express.
29

---

Proof. A GOMORL objective specification consists of ordering the set of policy evaluation functions (JoMonL(T)) π E ]. while an OMO objective specification consists of ordering on the occupation measures [ E 1g... As in Theorem B.24 Lemma B.22 says that we can choose our reward functions Rays such that JOMORI. the same ordering to both the policy evaluation vectors and to the occupancy measures, this then results in the same induced policy ordering. From Lemma B.23 we have that occupancy measures and trajectory lotteries uniquely determine each other, so any ordering of one uniquely determines an ordering of the other. Thus, orderings over occupation measures can induce all and only those policy orderings that can be induced by orderings over trajectory lotteries. Therefore, GOMORL, OMO, and TLO are equally expressive.
mi( (T), VT E I.. Naturally, if we apply
30

---

B.3 NOVEL RESULTS NON-EXPRESSIVITY (X Y)
Proposition B.26 (RM, MR & EXPR LAR, LTL). There is an environment and an orlering over policies that environment that LAR and LTL can induce, but RM and M R cannol.
Proof by construction. Note that since reward machines are strictly more expressive than Markov Rewards (RM EXXP M Rt), we only need to show that RM 7 EXPP LAR and RM y EXPR LTL. However, the reason RM and MR cannot express LTL and LAR is the same: LAR and LTL can give J5 functions that are discontinuous The proof will proceed in three stages. First, construct the environment E and subset of policy space II' C II. Second, Lemma B.27 shows that LAR and LTL can achieve a particular ordering over IT'. Third, Lemma B.28 demonstrates that M R and RM cannot achieve that policy ordering.
the policy space, but RM and MR cannot.
aA
ac
Start
aB
SO
SA
Figure 3: A simple environment consisting of two states So and S and three actions which leads from Sy itself ,ag which leads from So to SA and ac which leads from 8, to itself. The starting state is Sp
Lemma B.27. Consider the following ordering over II' TA TB To Ya < 1 Where:
n a is the policy which takes action G.A. in state 8p
π n is the policy which takes action an in state 8o
Na is policy which takes action a.g. with probability and action 0. with probability
There exists an LAR specification and an LTL specification that each induces this ordering over II'. In particular, they do so by setting (5(Ta) 1 a 0).
(A) OLAR = (R(AAR), where R[LAR( a, 1[s sol, gives expected return
J JoLAR Ta)) 1[a - Therefore, 5LAR induces the ordering.
(B) OLTL = (1b), where (b(E) A gives expected return J5. 1/a 0]. Therefore, 2 B.AB induces the ordering.
See lemma B.27 for proof of this. Intuitively, both LAR and LTL allow a discontinuity in J at 0, allowing iA Ta for arbitrarily small, but nonzero, values of a. Any a > 0 gives some prob- ability of transitioning to A at each time-step, and therefore a certainty of transitioning and getting stuck at some point an infinite trajectory. For I.AR, R. the finite sequence of [..ARR) (*5. 0.A 80) = rewards will be dominated by the infinite sequence of R. LAR (s ac, s O rewards. For LTL. Os will be true with probability 1, and therefore -OSA will be true with probability 0. If a = the agent will always loop at Su indefinitely, getting consistent reward of in LAR. Similarly, since there is probability of entering SA, - is true.
To finish the coumter-example, it remains show that the ordering over II' cannot be captured by any objective specification O Mr or ORM- To do this, we first show that J mR (Ta) and Jg Rar (ma) must be continuous 0.
31

---

Lemma B.28. For all ORM and OMR, lim =
For proof of this lemma, see appendix B.3.2 Intuitively, for any finite-time horizon, arbitrarily small values lead to small probabilities of entering SA. Since the infinite-horizon return for M R and RM closely approximated by a finite-time horizon return, arbitrarily small values of a should lead to small changes to the expected return.
Corollary B.28.1. For all O RM and OMR if E (0,1), xB ~ .Ta. then TB ~ NA-
This corollary follows from the fact that aB ~ na implies that (((Ta)
(TB) and there- = ( Since lemma B.28 also shows that lim 15( Jā(A)), we have that (5(A)) = (TB) for any OMR or ORMS.
fore the limit is given by: lim (T( (m
Combining lemma B327 and lemmma B.28 with TA > Tg. and Ta Tg. even though LAR and LT can. Therefore, for this particular E, there an ordering over II' that LAR and LTLL can induce but M R.R. and RM cannot. This is sufficient to show that RM FEXPR LAR, RM ÉEXPR LTL. M EXXPR LAR, and M R EEXP LTL.
1.28telle tells that, M and RM cannot induce ordering
Li
B.3.1 PROOF OF LEMMA B 27
Proof of lemma B.27 (A). We will show that 18LA 1/a O). First recall that (s a, s')
s') Su = 1[st = Su su]. Next, recall the definition of JE,OrAn
JE,OLAR(FO)
lim
E
Σ
R[LAR| at 8e+1)
(by definition)
No000
N
1=
N
EST
lim
E
[1(s: =o)]
(by linearity expectation)
N N
N
E
lim
I
[: ====0] so]
(Since E[1(X) = P(X))
N
N
0=
We consider two cases. First, if a 0, then F.n [s: = = 1 for all L. Therefore JF,OLAR (TA)
lim N Σ 1 = 1. Second, if a > 0, then pe [st = =so]
(1 -1-op a)' E (1 a)¹ is the
finite sum of geometric series with 1 and
(1 a) < 1:
N-1
1 - (1
1
1
(1 - a)
JE,OLAR
lim N
aa-a)²= lim N
lim
N t=
N 1 (1 a)
N N N
Proof of lemma [8.27
(1277()) (B. We will show that J5 (Fa) 1/a =0]. First define OLTl (1))
with (bE) ASA Next, recall the definition of J J8
ET E
J JB (Ta)
(5(
(by definition)
IP
- S A
E,i PP
0SA
32

---

We consider two cases. First, a then I
since a never chosen. Second,
0, then E OSA 1, since a will eventually be chosen. {
33

---

B.3.2 PROOF LEMMA B 28
Proof of lemma B.28
We will show that
lim J5(ma)) ( a-
for all ORM and OMR. Since MR is special case of RM where | U |- 1, to prove the lemma, it will suffice show that lim,-oo (1 J AM (ma) J Ja (FA) ) = Again, recall the definition of a reward machine specification, ORM = (U, uo, oū, 8R. 7) with return given by:
Ex
J8 RAT (T) =
E
y Ra 0e, 81+1)
Here R₂ dv (ue, ue+1) and u++1 8u 8u(, st). Noting that (s de, S141) depends only 8t, at, 8(+1 and uy, we can rewrite as R' (st, ag S1+1, ue) == 5i (u (u st) a, $t+1). Furthermore, because have bounded rewards the series is absolutely convergent meaning can, we can rewrite the whole expression:
JØ
(TT
[R, Ces S111,
RM
We can then rewrite the expression in terms of the difference between expected rewards at given timestep:
18 (Ta) - J8 (TA)
Σn 1=0
(
EE
(1,
En E
[R' (1:1 un)
Label this difference 6, = IR
Fi [R'(st, ot, 88+1; u,) - F. [R((se, Ge 8t41, uz)]. We will find
particular expression for 5, First, note that there are finite number of transitions (s, a, s'). This allows us marginalise the expectation for the reward at particular timestep:
Ex [R ae, 8141, u)] Σ Psaa,et"' Th
saas
8,0,8!
Where:
E, P
Pa
=
(s 01, S6+1) (8)),
E
EE
RR' a, 8 u.) (st. aes S1+1) = (s, a, s'))
s.
Now, consider our particular and na for a E [0, 1]. At any timestep, there are only three possible transitions: (8o, a, 80), (8o, 0B, 8A), and (s ap. 8A). We can, therefore write out case-by-case t,aa expression for Ps
P P (1 a )=(+1 1+1
1, Pso.an.sa
= a(1 - a)*
1 - (1 a)*
Pso.an.sA
P P 0 otherwise
Noting that pAotA Ax0 = 1, we can write the difference between the expected rewards between n,, and TA given timestep as:
34

---

61 -
Ro 8.500 $0.0..00
+ t. 30.0 B.s
+
(I)
Note that (' ag, St+1, ue) is bounded, since S, A and U are finite. Therefore, there exists some such that RR' (st, oz, St+1, we)l S It follows that:
1
Pe sn
L,o0 ee + Pop.ania
tm L.s
s0,0 - (1 P so) bro
= th
P sA
" + 1:50
Pea
+ (1
as I I
1,50
S c 00.0
+ 10
19 + (1
=c.
(1 - a1 + +a(1
aa)² + (1- al))t)t)
2c (1 (1 -a) a(1 )
We can use this to bound the difference in J values.
20
J5 (T.) - -JERAN
Ras (TA) | -
Σ 7
7" |6,
t=
222 (1-(1-a)+aa11-0
t=
8
x
2c
(1 - a)' + a
Σ
of (1 - a)")
1=0
1=0
1=0
1
1
2c
+ (a)
1-7
1-
71 a)
1 1 7- - a)
If we have that | JBnA((T)) - JEns (Tx) 1 Z, then to show that lim (n))((TT)
J J8ns (TA) it suffices to show that lim (Z) = 0.
1
1
lim (2)
lim 2c
a=0
1
7
1
7(1 - o))
1- 71 a))
1
1
a
2c
lim
+ lim
a++
1
7(1
a))
a
1 71 a)
1
1
20
+
0
1-7
7
=0
35

---

Proposition B.29 (LAR ÉEXPR MR, LTL). There is environment and ordering policies in that environment that Markov Rewards (MR) and Linear Temporal Logic (LTL) can induce, but Limit Average Reward (LAR) cannot.
a
SA
ac
Start
SO
SC
aE
aB
aD
SB
Figure An environment consisting four states 50: SA, SB, SC and five actions a,, 0B, ac, aD d.. The starting state is so.
Proof by construction. In the environment above there are two possible deterministic policies, taking the upper path through S, and गं taking the lower path through sg. We argue that LAR cannot express the policy ordering
Ty > m
while MR and LTL can. First we will argue that LAR cannot express this policy ordering: Both policies take action ag an infinite number of times while they only take the other actions at most once.
N
J (LLAR(Tu) = lim
R(se, aes (6+1)
N-500
t=
N-1 R(so. aA + R(sA, + Σ R(sc, ag sc) ]
lim N
N
= Ri(so, ag, sc)
N
Jo lim
R(si, 04 S411)
N=
N
t=7
Σ R(sc, 8c) ]
lim
R(so, aB, aB, 8B) + R(sn,
N
-R
Meaning that JE (Tw) = 2 1L (m) and so mu ~ my Next we will show that MR can express this policy ordering: let R(50, SA) I and all other rewards == 0. Then:
5 (Tw) =
J 10 (m) 0
resulting in our desired ordering.
Next we will show that LTL can express this policy ordering: Consider the LTL predicate Q& i.e. finally & this will give reward I to all trajectories which include & and otherwise. This gives:
J (Tm) = 1
J 18 (m) 0
i.e. our desired ordering.
36

---

Proposition B.30 (LTL EEXPR MR, LAR). There is environment and ordering policies in that environment that Markov Rewards (MR) and Limit Average Reward (LAR) can induce, but Linear Temporal Logic (LTL) cannot.
aB
aA
ac
SO
Start
Figure 5: An environment with single state so with three actions a,1, and ac which all lead back to itself.
Proof by construction. Consider the deterministic policies, TA, and TC corresponding to taking actions ag or ac respectively.
We argue that LTL cannot express the policy ordering:
T > BB TC
while MR and LAR can.
First we will show that LTL cannot express this policy ordering:
HA > FB
4 (EA) > >p (EB)
10 (EA) = 1 and (E.)
(as deterministic environment)
however,
AB nC
4p (EB) > 1p (Ec) & (En) = 1 and yp (Ec)= =
(as deterministic environment)
leading to a contradiction. For deterministic policies on deterministic environments LTT. can only divide policies into two categories and as such cannot order 3 or more policies.
MR can clearly express this ordering by setting R(So, aA, so) = 1, R(so, (B, Sp) = and R. ap sp) == -1 leading to:
1
Jonn (TA) 1 ?
( = =0
J
(TC) 1-2
37

---

LAR can also clearly express this ordering by again setting R(so. AA, == 1, (sso, ag, so) = 0 and R(su, aB. su) := -1 which leads to
J8 LAn (TA) =1
J8 AM (TB) 0
J8, AR (TC) = -1
38

---

Proposition B.31 (MR. RRL ÉEXPR RM, ONMR, LTL). There is an environment and
ordering over policies in that environment that Reward Machines (RM), Outer Nonlinear MR (ONMR)
and Linear Temporal Logic (LTL) can induce, but Markov Rewards (MR) and Regularised RL (RRL)
cannot.
aA
AB
Start 50%
50% Start
SA
SB
aA
aB
Figure 6: A state environment with 2 actions a and a going from each state the other state. The initial state is random, i.e. 84 and 8g with equal probability.
Proof by construction. The figure above shows simple 2-state system where different actions a, and a are possible in each state. Let тiy denote the policy which takes action i state 8 and action j in state 8B. There are 4 possible trajectories following deterministic stationary policies, namely, (Ba)))))))" (A and (s (BBB)) which correspond to policy क ABB. TA RAA and TBB respectively.
(s (
We claim that MR and RRL cannot implement the XOR function, i.e. the policy ordering TAB ~ TAA TAA aan while RM, ONMR and LTL can.
First we will show that MR cannot express this policy ordering:
(T)B) We want describe the ordering (T J5 (TBA) > J5 (TAA) J8 BB Each trajectory only has two unique state-action pairs, and since the initial state is random, in expectation each action a policy contains will be taken 50% of the time at each time step.
This means that:
J (TAB) > (5MAR(TAA) =
00
"RiSA, AA,
(R(SA..A.8B))
rR((s,,
1=0
1=
> "R(ss, ap, >
r'((sB,
t=0
1=0
R(sp. ap, 8A) R(SA.
However,
39

---

J Jo (TBA) > J (OMB(BBB)
RR(sA an. sp)
{((5)
R aB, 8B) +
2RR(sB.
2 t=
1=
7 ((A >
1=
1=
(A R(SB,
in contradiction with the previous relation.
Next will show that Regularised RI cannot express this policy ordering either. Recall the policy evaluation function in Regularised RL:
J 5 (T) BENN T
(R(s,, ac) + (F(((s))))
t=
In the case above, maintaining full generality we can write F[T(())] = ((P(a P(an)s)) for arbitrary f: A(A) + IR. Thus, for the four deterministic policies considered above, we have:
FITAB(SA) f(1,0) 0); AB = f00,
F[TBA(SA) f(0,1); ((TBA()B) = f(1,0)
((TA)(8A)] = f(1,0); F[TAл(SB) = ((10))
F[TBB(SA)] =f(0, F(TBB(SB) f(00
Following through the same argument from above, we derive the contradictory conditions:
RRC (TAB) > J8 (TAA) = R(sB, an, 8A) + +a,(0,1) as, + af((10))
(1)
J5 (TBA)= > J8 (TBB) = R(sn,a,, a(,(1,0) > R(, + (0,01) (2)
Next will show that ONMR express this policy ordering. Recall that:
J Jo (T) f fB T.I R(ss, a1 s(,l)
Let:
R(SA) -1
0B, =
SA) R(,SA =
R(SB, aB, SA) =
f(x) |
40

---

Now:
1
1
(AAB)
2 10
2
10
JBONMA (TBA)
2 1=0
1
(BONMA(TAA) (TAA)=
10
2 1=
2
= 1OOMMR(TB))
|0
2 1=
giving us our desired policy ordering.
Next we will show that RM can do this policy ordering:
Start
uo
Ro
Ro
(S,
RA
(s,ag.s')
(s,aB,s')
UA
UB
RA
RB
RB
(s,aA.s')
(S,
(s,aB,s')
Figure 7: A reward machine which can express the desired policy ordering.
41

---

The reward machine looks above. The reward functions are:
R1 (50. SA) = 0
[su SB)
RI(AA AA. so) = 0 RI 80)
R2(50. 0,A SA)
R2(Su, CB; 8A) = 0
A1, 80)
R2 9g, sb) = 0
For TAA we first transition 6n (No, 80, a^) = UA or dn (uo, SA, 8A, = 44 depending on we start at 0 or 1. For this ER Ro we get reward. Next will always transition 5, (M,, 80. 0.) ud or 8 (uA, SA, aA) = uA which gives on R, which results in 0 reward, therefore
15 (TAA)=
For ABB first transition & (uo, 80, 80. an) un du (uo, 8A; an) = us depending if start 0 or 1. For this ,R Ro so we get no reward. Next we will always transition 6, 80, an) = up or (u aB ug which gives dR R2 which results in 0 reward, therefore
J J8 (TBB) =0
Now for T12 we instead have 8 (uo, 80. as) = 4n or d₂ (u. SA aB) = For this ÓR = Ro so we get no reward. Next we have d, U SA aB) uy or ö, (uB, 8p, aA) Us which give reward 5R (SA, aB, so) = or oR = R2(80. OA. 8A) = 1 meaning
J8 nM (TBB) = Σ 7 1 1-7
1=1
Similarly for J21 we have dul (uo, 80, aB) = ug or 8u(ug, SA, aA) = uA For this OR = Ro so we get reward. Next have da (uB,, oR = R2 OB, SA) = or oR = RI(SA, 80) meaning
nn or 6n A, 80, ug which give reward
20
J8 = Σ y 1 1-7
7
This gives desired policy ordering.
Next we will show that LTL can also express this policy ordering. We will use the shorthand of referring to atomic propositions (which we have defined to be transitions in S A x S) actions; a shorthand atomic proposition a evaluates to true at a time t and only the transition at time includes a its action.
Consider the LTL formula ((as + Qan) A (an - Qaa)), which reads "a, implies next a and an implies next a.." Clearly this is false for aAa the action taken after aa in not always a and false for TBB as the action taken after is not always a,. For TAB and πвA however. the formula true as action a always followed by ag and action ag is always followed by a.a Consequently,
J na (TAA) 0
J (TBB) 0
JØ (TAB) = -
JØ RM
(TBA) =
which gives us the desired policy ordering.
42

---

Proposition B.32 (ONMR ŽEXPR LAR). There is an environment and an ordering over policies in that environment that Limit Average Reward (LAR) can induce, but Outer Nonlinear MR (ONMR) cannot.
aA
aD
Start
ax
0
SA
aB
ac
aE
Figure 8: An environment with 2 states so and SA with 4 possible actions in state so, namely a,,, aB, ac and ox and possible actions state 8 A, namely ap and ag. The starting state is 80-
Proof by construction. Consider the enviromment above. We start state So and have deterministic policies, TA, and Te which correspond to taking action a,, or ag in state so and policies T and TH which correspond to taking action a, state so and action a or ag state 8 respectively. We also have stochastic policies defined by the conditions
(ars(ar|su) Tars(ax(5u) =
TaIs(aJ[sA) 1,
for / (A, C} and J E E).
We would like the policy ordering:
TE ~ THAE TORE ~ TOCE > TD ~ TEAD ~ TABD ~ TECD > TB > AA
This can be done in LAR by setting Rg > R > Rc > RB RA and Rx = 0. For all policies which have finite probability of taking ax, J J (T) only depends on what the the policy does in
state two meaning that: πg TEAE ~ TABE ~ TICE and ~ TOAD ROBD TeCD. Setting the rewards above completes the rest of the ordering.
Now we will show that ONMR cannot express this policy ordering:
J (FoN
= [(B [G(E)))
R₂ + 1 1000
R.j
R. 1-
Br
is possible to choose R2 such that J (m =] -5 however it is not possible to choose R2 such that both J (TarD) = J5 (TD) and J5 (TOIE) = J (TE). Let us assume we have chosen R2 such that 15 (TEIE) = J5Mn and we can therefore not make (TeI)) = (TD). (Of course, an analogous proof goes through under the contrary assumption.)
We need J (RAAD) = (FAN))(FaBD) = (BooMa(TTon) -ooowe (Tp) 40 E (0.1) so must map the ranges
43

---

(TAA): [TD)] + MM
(TED) [D)] f(J (TD) (J (ToCD))) [D]]
(TD))
Either one or more of J ( J (TB) or JOMA are equal which contradicts our desired policy ordering or one of J (TA), J wn (TB) or J mn (Tc) must be within the range which is mapped to J8 @oNMRR (TD) above. This is also against our policy ordering. Therefore ONMR cannot express this policy ordering.
44

---

Proposition B.33 (ONMR ŽEXPR LTL). There is environment and an ordering policies in that environment that Linear Temporal Logic (LTL) can induce, but Outer Nonlinear MR (ONMR) cannot.
Proof by construction. Consider the following environment, and the linear temporal logic (LTL)
formula below.
aB
aA
ac
OO
Start
Figure 9: An environment with single state so with three actions a,, a and ac which all lead back to itself.
This environment has policies Tage where [0, 10, 8
[0. and 0 [0, 1] represents the probability of taking action a,, an and ag respectively. We would like the policy ordering
Ta.99 > Top
Where: a > 0 3 0A00 >
Le assign the same reward to all policies which have positive probability of taking all three actions and the same lower reward otherwise. LTL can express this policy ordering with the following LTL formula:
a' = Ov = ov v
Aa, A ou A oac
This LTL formula reads "Eventually and eventually a and eventually ac," and is satisfied by trajectory and only if the actions a,s ag, and ac are taken some point. Since our trajectories are infinite and we only have one state, eventually taking an action is equivalent to having positive probability of taking an action. Therefore LTL. gives us:
J..,, (Ta20) Va Va>0Am 0a>0A3>0^00
J8.,, (Taz0) va=0v5 0V
Which is our desired policy ordering. Now let show that ONMR cannot express the same policy ordering:
Let
RA R(so, aA, 80)
RB = R(so, aB; So)
Rc R ac, 8p)
Either of these rewards equal (we will return the equality case below) one reward lies between the other two. To fulfill this policy ordering the ONMR function must map all MR rewards of policies which sometimes take all actions to value, lets call this Rn. The function
45

---

must also map all policies which do not do this another value, Ry. Specifically it must map all policies which only take two actions with any probability to the same value:
RA
RBB
+ Rr
1
1
RA
Rc
+ R
1-7" 1-7
RB
RC
- R.
1 1-7 1
However, also need map the range: min (AA, R.B. Rc)
mar(RA, RB, Re.) RR))
Rh
1-7
These ranges clearly overlap and no function can map the same value to two different values. In the case that two or more rewards are the same the proof is even simpler. Call the rewards which equal R and RB with Re being the other reward. The ONMR function must for instance map
1 Rc Rh 3
RA
RB
RA
Rc - RL
But these two expressions equal. Thus, prove that ONMR cannot express this policy ordering.
46

---

Proposition B.34 (FTR ÉEXPR ONMR). There is environment and an ordering over policies in that environment that Outer Nonlinear MR (ONMR) can induce, but Functions from Trajectories Reals (FTR) cannot.
Proof by construction. Consider the environment depicted in the diagram below.
Start
SO
aA
aB
SA
SB
aa
aB
Figure 10: A three-state environment with two possible trajectories corresponding to choosing 4,4 or ag in the starting state sp.
We will show that in this environment, the following ONMR specification (R, cannot be expressed with any FTR specification.
RA R(50, aA SA) 1, RB R(so, aB, SB) 0 (as depicted above)
1
[1
if
(1x) =1 r
0
if
0.99
With this specification:
l *R(se, ae, st- (t)
:
(by definition)
I.
=1
/
R RS( at 8tmm)]
(Rewards are 0 after the first step)
f (T(aalso) R(sy. as SA) + (aB (S) ag. sg))
=f(T(aalsu)(1) + (ao)ss))
= =
(1 if (aal(s)) 2
{o if (
47

---

So this ONMR specification prefers policies that satisfy (d) those which do not, and has no other preferences. Now, we will show that no FTR specification can express this policy ordering.
In this environment, there are only two possible trajectories: &A (so, G,A, (A)) and &a (sp, a, (sp. SB))). Suppose there is an FTR specification (frTR) which induces the same policy ordering the ONMR specification described above. One property this specification must satisfy is that the policy a that takes action QA deterministically must be preferred to the policy x that takes action ag deterministically.
(TA)
E E-TA,T, E [fETR(E)] (TB)
E (-ma, (FFTR(E
= (PTR(EA) > (PTR(EB)
Additionally, if Teii (aals))) Tmir (un (0) = 1/2 then to match the ONMR specification, the FTR specification should have no preference between Tiiix and TA.
(Brra(TA)) E~TA,T,1 (.FTR(() = J FT (Tmix) E~Tmis, J (FETR(())
fFTR(EA) = 2 (FTR(EA) + ( (STTR(ES)
(FTR(EA) - -SSTR(EB)
(FTR(EA) = (FTR(ER)
Since cannot simultaneously be true that fFTR(EA) fFTR({B) and fFTR((A) = fFTR(EB). this means there is no FTR specification which prefers to but has no preference between TA and min- Therefore, FTR cannot express this policy ordering, concluding the proof.
This proof highlights that the expectation in the definition of FTR limits it to linearly interpolating between the possible trajectories that a policy can produce. Meanwhile, ONMR specifications can express complex preferences over trajectory lotteries, such as setting minimum acceptable probability for trajectory.
48

---

Proposition B.35 (FTR ŽEXPR RRL). There is environment and ordering policies in that environment that Regularised RL (RRL) can induce, but Functions from Trajectories to Reals (FTR) cannot.
Start
SO
aA
SA
SB
aA
aB
Figure 11: A three-state environment with two possible trajectories corresponding to choosing a or ag in the starting state Su-
Proof by construction. J(T) = Be 2 a.) (F((ss))))
where F A(A) IR is functional of the policy's distribution over actions at a given state.
We construct an example of a task that can be expressed in Regularised RL with F[T(s)] [[][ >, (a,]s) log (aalss) (the Shannon entropy), and then prove that it cannot be expressed by any FTR objective.
Suppose we have the environment above with only two trajectories &,,, ÊB through it, both which can be reached by means of deterministic policies. Let us specify the reward function R so that both trajectories have the same discounted sum of rewards. Three possible policies are:
Deterministic policy that takes ČA with probability
T Deterministic policy that takes εs with probability
Tm Indeterministic policy that takes &A with probability and {B with probability 1 1-
Since [s)] = H [T)(ss) = 0, and G(EA) G(EB) by stipulation, J(TL) = ((TR).
Moreover, for a > O, is easy show that ((Tm) J ((LL) (TR). Thus Regularised RL in this environment can express the task 7m X aL
Now consider FTR. The policy evaluation function is: ((T) = Ee [f())] P(EA))(EA) + ((E
So:
( = [(EA) = a
J(RR) -((E) b
49

---

(mm) (f((A) + (1 - (EBB
Since p E (0, 1) the latter is a convex combination of the former and so we must have EITHER:
TR mm. x L
(a b)
TL Am < R
(b > 0)
TT.
R
(a b)
None of these gives us the policy ordering induced by the Regularised RI. specification above.
50

---

Proposition B.36 (GOMORL ŽEXPR FPR). There is an environment and ordering policies in that environment that Functions from Policies to Reals (FPR) can induce, but Generalised Outer Multi- Sillit-Objeetiee RL (GOMORL) camnot
Proof by construction. The essential idea of this proof is that FPR can express preferences between policies that are only distinct on states that neither policy ever visits, while GOMORL cannot. Consider the following environment:
aA
ac
Start
aB
SO
SA
aD
A two-state environment with two actions in the starting state 8n taking a back to itself and action 0B leading to state SA. In state 84 we have two actions leading back to itself.
Figure 12:
Now consider the following two policies within this environment, Ti and n22
Ii (a a $o) = 1, nı (a su) = 0, T (aclss)) = 1, 1,5i(a = That is, HΙ deterministically chooses a from So and ac from SA.
so) = n2 (a
0, (2(ac(sA) = 0, 0, = That is, 22 deterministically
chooses 4,4 from So and @p from SA-
The policy ordering induced by any GOMORL specificatn (k, R, ž)) cannot have any preference between and T2- To see this, first notice that both of these policies deterministically result in the trajectory (Sp, a,s $0, a.s .... This means that each the policy evaluation functions, J+(x)
for all E [k), returns the same value for both policies:
Ri(so, as, Jz(T2). 1-7
J{(T))
E S-aIT
(i,, (i, 8411]
Thus, J(m.) (mm)). Since ž) must be reflexive weak order, J((T1) 2J J((T2 and J(T2) /s [(TT). So in this environment, GOMORL must induce the ordering कi n22
Clearly, an FPR specification (JPPR) need not respect this equality. For instance, the specification could be:
[1 =
JFPn(())
else
The policy ordering this induces has क. T2, so cannot be expressed by GOMORL. This concludes the proof.
Recall that GOMORL has the same expressivity as Trajectory Lottery Orderings (TLO) and Oc- cupancy Measure Orderings (OMO), so FPR is also not expressively dominated by either of those formalisms.
51

---

Proposition B.37 (FPR ŽEXPR GOMORL). There is an environment and ordering policies that environment that Generalised Outer Oujeii-Obeective RL (GOMORL) can induce, but Functions from Policies to Reals (FPR) cannot.
Proof by construction. Consider the following environment, and the GOMORL specification (k, R, 7, x3) below.
R1=1
R₂=0
R2=0
R2=1
aA
aB
Start
R,=0 ae R2=0
SO
SA
SB
ac
aD
Ry=0
Ry=0
R2=0
R2=0
Three state system consisting of the starting state so with actions 0,4 and ac leading to 8,, the state 8 which has two actions ag and ap which lead to s and finally the state sg which has action ag leading to itself. The figure also shows the reward functions R1 which give 1 reward to action a and to everything else and R₂ which give 1 reward to action ag and to everything else.
Figure 13:
k =
R1 and R2 are included in the diagram above. R1 only rewards taking action 0,s, and R2 only rewards taking action an
= 0.99 (though this particular value is not important)
Let J, (J11, J12) E R2 and let J2 (J21, J22)- ž. specified such that J₁ ビル Jr and only if Jı1 > J21, or Jn J21 and J12 2 Jzz. This is lexicographic ordering on R
Let us clarify the policy ordering expressed by this specification, starting by writing out the policy evaluation functions.
E E
Est
R' Rs ar, (st (cml))
J(T)
=
C
RR ( az St+1)
yeary
E
E
Exx
> R2 ae, (
I
7 (R az S141)
(
The last line is true because the only transition that R2 gives nonzero reward to (so, a 8A), and the only transition that R2 gives nonzero reward to is (s a.. (which can be taken after one step, so must discounted by 7).
look at the policy ordering in terms of the probabilities assigned to a and ag. The lexicographic ordering selected turns into the following: n, 2 #2 if and only if f(m,, ) žJ J(m2) if and only if ) (aal (s)) > (a (so), or Ti (aAlso) = тh (2 ss)) and क ( SA) 2 (2 (A))
Now
Next, let show that FPR cannot express this policy ordering.
Suppose towards contradiction that (JrPR) is an FPR specification that expresses the same lex- icographic policy ordering. First, note that if J(m)) = J(m2), then J(mi) Σ, J(mz) and T(T2) v J((T), so mı オ2 according the GOMORL specification above. Therefore, for
52

---

(JEPR) to express the same policy ordering, it must be the case that J(m)) ((m2) implies [FP)(TT) = JFPR(Te). This means that JEPR. which was have assumed expresses this lexico- graphic policy ordering,
be decomposed into the GOMORL function from policies to J vectors in J: II + IR², and function from J vectors in 8² reals, fy : I2 + P. So JFPR fo J. Now we will show that no mapping f R²² + R can express the lexicographic policy ordering given by ž. above, so the supposed JPPR which expresses this policy ordering cannot exist.
For f, to express the same policy ordering as ž.. must be true that (J(m)) 2 (f((m) - J((1)) ž. J(2)). Next, let us establish a few notations and facts which will allow us to demonstrate that there is no Js which satisfies this requirement.
1. Let B, be the set of possible values for J2 that a policy can have if it has J1 = a. That is, let Bg {b R : 3r E s.t. J1(x) = a, J2( b}. where J1 and J2 are the policy evaluation functions associated with R1 and R2 from the GOMORL specification above.
In the environment we have specified, we have established that (TT = (a and Jz(m) = (ag(ss)) So (Tr x(aa(so)
[0, 1]. J2(TT = 7T (an((())) E 00 7] and since the policy's behavior in 8 is constrained by its behavior in 80. J(II)
[0, x [0, 7]. Therefore, B. = [0,>] for all E [0. 1]. Since 7 = 0.99 > 0, B, 0.99 is uncountable set. Importantly for this proof, [Ba > for all E J1 (TI. (Aithough
in this case Bg is the same for all values of a, we keep the notation Ba, as this makes the
proof applicable any environment which there are uncountable values of a such that Bal > 1.)
2. Suppose a' E (II) with a' > To induce the lexicographic policy ordering through fJ, it necessary that
fa(d' 8') b)(a,b) vb Ba, D' E Ba
3. Suppose b, E B, with v > b. To induce the lexicographic policy ordering, it is necessary that for any (II)
fs(a, > b).
4. Define fsa Ba + R as (b) = fa(a, b). Considering the range of fa denoted as (J,, let
MI, inf (Ba)) and m2,a sup(Jr.(Ba))
Let f3.. [m i,, J. subset of the reals such that f b) lies within this range for all
b E B. Given 3 the fact that |Bal >> 1 for all a E (IT), we have m2,0 > m11.-
5. For a' + a, point 2 implies that fz(a', & Iiz. for any b E Ba. By extension, a' a 11sm ne O.
6. Let = = a J(L)). We define function Int Ji (II) + Ias Int(a) IfJa where "Int" stands for interval. Note that the function Int is injective.
7. Since the rationals are dense in the reals, every closed interval of reals containing at least two distinct real numbers also contains at least one rational. Therefore, we can define function a : + Q which, when given an interval as input, outputs a rational within that interval. Owing to the disjoint nature of all [z... (from point 5), is injective.
Recall that (II) = [o. 1] is uncountable. Given the assumption that an FPR specification induces the lexicographic policy ordering, we have constructed injective functions Int J (IT) I and a + Q. Composing these, we get an injective function
σ Int J, (II) + Q
This leads contradiction: JIII is uncountable and Q is countable, there cannot be an injective function from J1 (II) to Q. Thus, FPR cannot express this lexicographic policy ordering. and GOMORL can represent policy orderings which FPR cannot.
53

---

Note that this proof does not rely heavily the specific environment depieted above the specific reward functions used by GOMORL; the only features which are relevant to the proof are that there uncountable values of J1 (TT) that each have least 2 values of J2(z). This proof also extends to lexicographic preferences with more than reward functions.
54

---

Proposition B.38 (ONMR ŽEXPR RRL). There is an environment and an ordering over policies in that environment that Regularised RL (RRL) can induce, but Outer Nonlinear Markov Reward (ONMR) cannot.
Proof by construction. Consider the following environment.
Start
SO
aA
aв
ac
SA
aD
Figure 14: A four-state environment with three possible trajectories corresponding to the choice of a, Gg or ac in the starting state sp-
Consider the Regularised RL (RRL) specification given by:
V(s,a, ES R(s,a,8')=
-
Fs][ = Ha; (aalss) 0H- (This F' and a incentivise assigning probability to as many actions as possible, which is one way of incentivising more deterministic behavior.)
0.9 (although this is unimportant)
After the first step, all policies deterministically select action ap. Let F, be the value of F[T(()] deterministically selects ap from s. Then with this RRI specification:
55

---

0
JRRL (x) Be-ar, T.I
a aF(T
1=
7 (0- (-1)F(((500I) PFD
TT
1-7
F(T((O)) + 2FD
RT
1-ク
7FD
F(o((s))
+ 1-7
DFD 1-7
(a:::((ass))))) 031 +
+
if π selects any one action deterministically
if assigns nonzero probability to exactly two actions if π assigns nonzero probability to all three actions
Now let us show that ONMR cannot express the same policy ordering.
Conceptually, the limitation of ONMR that this proof will exploit that if there are three different possible trajectories, each receiving different trajectory return, then ONMR cannot distinguish between policy that deterministically takes this intermediate trajectory and policy that produces an appropriate probabilistic mixture of the other two.
Suppose towards contradiction that (R, f. 7) is an ONMR specification that expresses this policy ordering. Let RA Rso, (...s). Rg R(so. ag. sB), Re = R(se, ac, sc), and RD R(*A, aD, 84). Without loss of generality, we can assume that we have numbered the states and actions such that RA < RB S RRc. For now, assume that RA < R.B < Ro; we will return to the equality case below. This means that Rg A + RC for some real number g E (0, 1). Re-Ra (Specificallyy, q Re-RA
Now suppose focus our attention on a class of policies of the following form:
<apls0)) 0, (a so) = (1 0)g, (ac|s0) = (1 0)
Note that an ONMR specification has fixed in advance, so the only variable is 0. Now, we will show that the ONMR specification must assign the same value all policies of this form for any 0 E [0, 1]. First, recall that 18oNMe (To) (To)) Therefore, we can analyse 1 (TO) before returning to J5ONMn' (To):
E.x
18mA((TT)
E
R' Ar, S6+1)
1==
= - + (1 0) + (1- (1100)1- + 7 Rd
1 1-
= ORB + -1-00 (10))(RR. - -(1-9)cc) + 7
1- R.D
=RRg + -11-0RBB 1- RD
RB + 1 RRD Rd
Connecting this analysis back to ONMR, we get:
J 1BoNun((T)) (JB
=1 RB 1 1- Rd
56

---

Since this is independent of 8, any ONMR specification that uses three distinct reward values for the three transitions must not have any preference between πé=1 and T0=0.5- However, the RRL specification above does have preference: 1 deterministically selects ap while 0.5 assigns nonzero probability to all three actions. So J8 (m==1)
FFD 7FD I-y i-7 J (To=o.s).
The only case left address is when the reward function R in the ONMR specification assigns the same reward to any two transitions. That is, R. R. for some o 8 E {A, B, C) a * 3. No such ONMR specification can express this RRL policy ordering either, because such specification distinguish deterministically selecting action dg or ag from assigning nonzero probability to both. Let Ta be policy that selects aa deterministically and let Ja,8 be policy that selects each of a. and a with probability 0.5.
B. E
(Fa
7 RR(ss, Ae, A1,
(0.5((( + 0.5(R,)) + 1-7
R.D.
7 RD
= Ra +
1-7
Thus,
J JoNNun =
f(J5 = JooNMn
So any ONMR specification that assigns the same reward to two transitions cannot express preference between and Ta,8. Meanwhile, the RRL specification above prefers T. to To since Ta deterministically selects a, while a assigns nonzero probability to both a, and ag- Therefore, ONMR specification (whether it assigns equal rewards to two transitions not) can express the policy ordering expressed by this RRL specification.
57

---

Proposition B.39 (RRL ŽEXPR LAR). There is environment and ordering policies in
that environment that Limit Average Reward (LAR) can induce, but Regularised RL (RRL) cannot.
aD
aA
Start
aB
SO
SA
ac
Figure 15: A 2 state environment with starting state so which has 2 actions a and a leading to 3A and state A which has an action ae leading to and an action ap leading to itself.
Proof by construction. In the figure above we have two states and SĄ. 8o has actions 0, and which both lead to 8 with reward Ra and RB respectively. 8л has actions an which takes it to itself and ag which leads to so, these have reward Rn and Ro. Let the initial state be so and with equal probability 3. There are possible deterministic limit cycles here:
Going from state to state forever via aD
Alternating between the states via 0.A and ac
Alternating between the states via ap and ac
There 4 possible deterministic policies which we will call my corresponding taking action in state 0 and action in state 1. We would like to express the policy ordering:
AD ~ BD AC > BC
This is easy do in LAR, J Joa for the different policies is:
J (TAD) = =J (TBA((TBD) R.D
(5LAR(TAC) RA + Rc
(8LA((TBC) RB + Rc
We can simply set RD RetRe and R > Rø leading the desired ordering.
2
is not possible to express this policy ordering in MR however. Looking at J8., of the different policies we get:
JE (TAD) EEWTADD [Gas((E)]
E [GMn(E)] TE [Gmn(E)]
2
1
1
RA
RD
Σ R'DD
2
2
0
J8 (TBD) = R
R +
Σ
7 RRD
2
1=0
58

---

Setting these two to be equal we get:
J JOMn (TAD) = = (
RA RB
However,
20
20
J8 (TAC) 2 1=
RR RA +
2
21+1
Rc +
2 Re +
24+ RA =
2 1=
2 t=0
1=
8
RA +
1 Re
Similarly:
1 00
1 8
Jun (TCC)
RB B
+
Re
2
2
t=
1=0
1 0
1
1 x
1 x Σ
(Bun(TAC) > Jamn((TC)
Σ
RA
RRR
Σ
7
RB
+
Rc
2
2
2
2
1=0
t=0
1=0
1
RA >
RB
RA
> RB
2 1=0
2
t=0
This contradicts R = R. Therefore MR cannot express this policy ordering meaning that MR cannot express all tasks LAR can.
With a minor modification, this proof also shows that LAR can express some tasks that Regularised RL cannot. Recall the Regularised RL policy evaluation defined as:
J (
(T) = BENT.T
(R(ss, o.) + aF (F(((())))))
t=
In this environment we have only four actions (a a. aB, ac), and so we can write F[r(s;)] as an arbitrary function of four probabilities:
aF([=(:)]] [(P(anls:), P(aals:), ((an)ss), P(acls:))
Then we have closed-form expression for each of our four policies under ORRL:
Jann (RAD) = (RA + f(. - (R (R.,0(1,,
+
(RD + 1(100000)
2
J J5nni (TBD)=
(RB + ((0,01,,0) (RD + f(1.000,0)
(RD f(1000000)
1
J8and (TAC)
(R + (00,1,0,0)
Y' ''Ro + ((0000.1)
2
2 t=0
t=0
J8am, (TBC) =
Σ
(RB + f(0,0,1,0) +
(Rc + f(0,0001))
2
2
t=0
1=
Using the first two equations allows us to get:
J J8nne (aD)) = J J (TBD)
ADD TBD
= RA + (0, 1, 0, = RB + f 00,0,1,0)
59

---

This contradicts our assumption when combined with the second equations:
TAC > BCC + .J (TAC) = J (TCC)
RA f(0 1, 0,0,0) RB + (00,0,1.0
So Regularised RL cannot express the policy ordering
TAD TBD > TAC > BC
60

---

AB
aA
ac
OO
Start
Figure 16: An environment with single state so with three actions a,, ag and ag which all lead back itself.
Proposition B.40 (ONMR ZEXPR RM). There is environment and ordering over policies in that environment that Reward Machines (RM) can induce, but Outer Nonlinear Markov Reward (ONMR) cannot.
Proof by construction. Consider the following environment, and the Reward Machine (RM) specifi- cation (U, uo, dU, ÖR,
The environment E is detailed in Figure 16
See Figure below for a specification U, uo, and dy. The transitions are labeled with actions shorthand notation, enabled by the fact that this transition function du depends only on the action. For instance, the arrow from ug to us labeled with 0 indicates that dy (ug. 8, a.. s') U. for all and s'.
{1
if u' = MABC.
(s,,
(
otherwise.
7 7 0.99
Intuitively, this RM specification gives reward exactly 1 in trajectory if and only if all three actions are taken in the trajectory, because that is when machine state UACC is visited. After giving a reward once, the machine enters state Uend and never give further rewards. The states in the reward machine keep track of which distinct actions have been taken so far (and are named accordingly). The cumulative discounted reward if any of the actions are never taken, and nonzero if all three actions are taken.
With this specification, policy that takes all three actions with nonzero probability has probability 1 of eventually taking all three actions and receiving some nonzero discounted reward when the third distinct action is taken, while all policies that assign 0 probability to least one action are guaranteed to receive 0 cumulative discounted reward. Therefore, policy that takes all three actions with nonzero probability preferred to all policies that assign probability to at least one action. We can show that it is impossible to express policy ordering that satisfies this property with ONMR. Note that much of this proof is very similar to the proof above that ONMR cannot express Regularised RL (RRL).
Suppose towards contradiction that (R, 7) is an ONMR specification that induces a policy ordering in which any policy that takes all three actions with nonzero probability is preferred to all policies that assign 0 probability to at least one action. Let Ra = R(so. a A. 8p). RB = R(sp, a, sp), and assume that we have labeled the actions
Rc R(so, ac; sn). Without loss of generality,
61

---

a8.36
aB
UA
UAB
ac
ac
ap.a
aA
aA
Start
aB
aB
a..aB.ac
u0
UB
UAC
UABC
Uend
ac
ac
aB
aA,ac
aA
UC
UBC
ag
ac
ag,ac
Figure 17: reward machine which keeps track which of the three states 8A, 8B amd &c have been visited.
such that R S. RB S Re. For now, assume that RA < RB Ro: we will return the equality case below. This means R = A + (1 - Ro for some real number E (),
Now suppose focus our attention
class of policies of the following form:
x{an(80)= = 0, (a (0) = (1 - 0)g, n (uc()0)) = (1 - 01
Note that an ONMR specification has fixed in advance, so the only variable is 0. Now, we will show that the ONMR specification must assign the same value all policies of this form for any 0 E [0, 1]. First, recall that 18oNMe (TT) f(J (Ta)). Therefore, we can analyse J 8 (Te) before returning to (0o)
J5 (50) = E.
? R((s, Ac,
J5 (TO) = 70 (OR + (1 (1-0) R)))
J (TT) = OR + +(1 - (1-0)(RRA + + (1-
J 1 = BRB +(1 B)RB
J J5 = RB
Connecting this analysis back to ONMR, we get:
J 15 (TO) = (J)
J5NNMn (TO) = f(RB)
Since ( f(RB) for E [0, 1]. any ONMR specification with different reward values for the three transitions must not have any preference between mø=1 and T0=0.5- However, the RM specification above does have a preference between these policies. TØ=1 deterministically selects a while T9=0.5 assigns nonzero probability all three actions. So J J (o.5)..5) J (mo 1)-
The only case left to address is when the reward function R in the ONMR specification assigns the same reward any transitions. That is, R., R, for some o. (4, B, C), * B. No such
62

---

ONMR specification express this RM policy ordering either, because such specification distinguish between policies that assign the same total probability to Qa and ag together, but divide that probability across the two actions differently. Let Ta.r be policy that assigns probability 0.5 to Ga. probability 0 to ag,, and probability 0.5 to the third action (call it a.). Let Ta,8.e be policy that selects each of a, and as with probability 0.25 and assigns probability 0.5 dc. Again, begin by analysing J5nn for these policies.
00
J8Ma(Ta (Ta,
(st, Ar, 8111
8
(0.5R, + 0.25R + 0.25RR))
(0.5R, + 0.5Ra))
E.
> R(s,, Ac,
J (Ta
Returning the ONMR policy evaluation function and using the fact that (a JEun (Ta,c), we get:
(a.))) = f(J5 (Fa, = [[[J (Fa,e) JBonsn (F,,))
So any ONMR specification that assigns the same reward to two transitions cannot express preference between Ta.s and Ta.B.c- Meanwhile, the RM specification above prefers &o.8,r to Ta,e, since Ra, assigns nonzero probability to all three actions while na, assigns probability 0 to ag. Therefore, no ONMR specification (whether assigns equal rewards to two transitions or not) can express the policy ordering expressed by this RM specification.
63


Reviews:
[{"review_id": "jVf3IiYPvA", "reviewer": "Reviewer_mz4B", "summary": "Um. Wow.\n\nThis paper is remarkable in many ways. The paper contributes a comprehensive set of proofs designed to show which reward formalisms in RL are distinctive and which can be subsumed by others; the central contribution of the paper is a lattice that diagrams these relationships. One conclusion from the work is that many formalisms offer distinctive capabilities, and that no single formalism is dominant.\n\nThe paper really does seem to be an incredible, detailed set of work. It is is highly theoretical, and is likely to be useful only to a select subset of researchers who are deeply steeped in RL research.\n\nI am not capable of evaluating the proofs in any sort of detail, even though I have spent many years in RL. However, the way that the paper is written, combined with the parts that I was able to evaluate, suggests a serious contribution to the literature.\n\nThe question is: is ICLR the right venue for this work? While this is probably the magnum opus of this sort of work, it's unclear how much the general ICLR community would benefit from including it in the conference proceedings.\n\nWould a journal be a better outlet?", "questions": "Why do you think that ICLR is the right venue for this work, as opposed to an RL-specific conference or a journal?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "+ Comprehensive evaluation\n+ Clearly summarized results\n+ Interesting resulting insights\n+ Well-written, despite extensive technical detail", "weaknesses": "- Likely to be useful to a very small subset of people\n- Unclear if ICLR is the right venue\n- Dense notation / writing", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vkbF37UtNF", "reviewer": "Reviewer_XNit", "summary": "This paper compares the relative expressivity of different task specification mechanisms for reinforcement learning agents. The authors set out to compare the relative expressivity of Markov rewards, limit average rewards, reward machines, linear temporal logic, regularized RL, and outer non-linear Markov rewards, and prove that each of these formalisms have a non-zero intersection, but also a non-zero exclusive component. In doing so the authors define 17 different task specification formalisms, and posit that a complete ordering over all possible policies of an agent is the most expressive (if impractical) tasks specification mechanism available for RL agents. \n\nThe authors primarily provide expressivity result as a Hasse diagram where a directed edge represents subsumption of the task specification formalism.", "questions": "1. I am curious if the authors only considered a fragment of LTL, or the entirety of LTL that allows for accpetability definitions over infinitely long trajectories\n2. I am also uncertain if ordering over stationary policies is enough to describe an LTL task that requires a memory dependent policy (usually implemented through a cross product MDP)?", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. **Timely and major significance**: The authors assertion that each of the popular reward mechanisms do not completely express all aspects of other reward formalisms is an important result, and the conclusions are supported by extensive background materials, and proofs. I also believe that the recommendation of the authors that researchers be more aware of reward specification frameworks, and algorithms catering to them is also well received. \n\n2. **Comprehensive survey of reward mechanisms**: The authors were systematic in their coverage of task specification formalisms, and have exhaustively documented each pairwise dependency. Although for presentational clarity, the proofs had to be relegated to the supplementary materials. The paper seems well indexed.", "weaknesses": "1. The authors center the discussion around ordering of stationary policies, and while it is justified in the context of the paper, and where the research effort has been directed historically, there are many instances (especially with partial observability), where non-stationary policy over observations must be implemented.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9VxrF14nyj", "reviewer": "Reviewer_Re36", "summary": "This paper surveys a wide range of objective-specification formalisms in reinforcement learning setting and establishes the theoretical expressive relationship among these formalisms. These results facilitate the choice of objective formalism for RL practitioners.", "questions": "I have no question.`", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work connects 17 objective-specification formalisms, compares their expressivity, and present results using a Hasse diagram. This contribution is clear.\n2. The discussion and review of each formalism is helpful for RL practitioners to choose specifications.", "weaknesses": "1. There are some other formal language-based specification formalisms for RL, such as Signal Temporal Logic, which is more powerful than LTL because of its robustness property, and there are a wide range of literature in this direction, see e.g., [1], [2]. The authors are encouraged to study STL formalism with others to make the comparison more thorough.\n\n2. As mentioned in Sec. 4.1, there is no tractability comparison among various formalisms, which is however very important for researchers/practitioners to decide which one they want to use.\n\n3. The writing can be further improved. For instance, some notations can be be more precise (e.g., in Def. 2.7, vector in R^|S||A||S| should be replaced by R^|S| \\times R^|A| \\times R^|S|).\n\n[1] Balakrishnan, A. and Deshmukh, J.V., 2019, November. Structured reward shaping using signal temporal logic specifications. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 3481-3486). IEEE.\n[2] Wang, J., Yang, S., An, Z., Han, S., Zhang, Z., Mangharam, R., Ma, M. and Miao, F., 2023. Multi-Agent Reinforcement Learning Guided by Signal Temporal Logic Specifications. arXiv preprint arXiv:2306.06808.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xYBLnORF5j", "reviewer": "Reviewer_EiAB", "summary": "The paper aims to provide a comprehensive picture of the expressivity of a pletora of objective specifications in RL, which include reward machines, trajectory feedbacks, multi-objective formulations among the others. The expressive power of an objective specification is measured in terms of the orderings it can induce over stationary Markovian policies in every possible environment, which is formally defined through a set of states, a set of actions, a transition kernel, and an initial state distribution.", "questions": "- Can the authors address the comment reported above?\n\n- Can the authors clarify which of the reported result is new and not directly implied by previous works?\n\n- How can be OMO more expressive than FOMR? I am probably missing something, but why we cannot take for any ordering over occupancy measures $m_1 > m_2 > ... > m_n$ a function $f: M \\to \\mathbb{R}$ such that $f(m_1) > f (m_2) > ... > f (m_3)$?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- (Significance) The paper tackles a very important question on how to specify the objective in RL. Given the recent results showing the limitations of Markovian rewards (e.g., Abel et al., 2022) and the growing popularity of alternative feedback models, such as RL from human feedback, regularized RL, and convex RL to name a few, I think this is a very relevant research line.\n- (Originality) I am not aware of previous effort in exploring the expressivity of such a comprehensive set of objective specifications.\n- (Limitations) The paper is upfront in reporting the limitations of the contribution (see Section 4.1).", "weaknesses": "- (Arbitrary analysis) The works makes a series of arbitrary choices in defining the expressivity of an objective specification (e.g., limiting the analysis to ordering of stationary policies) that are not sufficiently motivated in my opinion.\n- (Implications) While the paper provide lots of results in terms of expressivity (as defined in the paper) of the objective specifications, most of the implications of their analysis are left as future work.\n- (Related work) Given the nature of the work, which is in part a survey of objective specifications in RL, the discussion of the related literature is insufficient.\n- (Clarity) While the main messages of the paper are clear and easily accessible, some notation choices are somewhat confusing, and they also depart the objective specifications from how they are formulated in the literature in some cases.\n\nGENERAL COMMENT\n\nThe paper tackles a very important research problem, which can be coarsely rephrased as \"how can we specify the objective in RL to obtain the behaviour that we want as output of the learning process\"? However, it falls somewhat short of answering this questions, providing an analysis of a set of objective specifications in a very limited setting (full ordering of stationary policies), and without addressing the implications of their results. Some of the reported results can still be valuable, although it is not fully clear what is novel and what is already known, but I believe that a better motivation of the choices on how to evaluate expressivity is necessary to clear the bar for acceptance. Thus, I am currently providing a negative evaluation, but I will consider updating my score if the authors can convince me on why comparing objective specifications in terms of full ordering of stationary policies matters.\n\nDEFINITION OF EXPRESSIVITY\n\n(C1. Policy ordering) The paper makes clear that the expressivity of the objective specifications is evaluated only in terms of policy ordering, but I am wondering whether this is the most natural notion of task, and how can be motivated in practice. Arguably, in most of the real-world problems, what really matters is the outcome of the learning process, i.e., what policy is ultimately learned. In this view, the SOAP looks more natural (terminology from Abel et al., 2022). I think that a soft-SOAP task notion would make for a stronger case in the expressivity evaluation. Anyway, the choice of task notion has a strong impact on the expressivity overview and it shall be motivated carefully in my opinion.\n\n(C2. Stationary policies) Another weak point I see in the analysis is restricting the policy class to stationary Markovian policies. It is well-known that a Markovian reward is expressive enough to specify objectives over deterministic stationary Markovian policies, which leaves only the set of stochastic policies to the other specifications. I am wondering why one would want a stochastic policy in the first place. Typical motivations are robustness to model misspecifications and adversaries, or perhaps to make the learning problem more efficient (e.g., regularized objectives). For some of the reported objective specifications, I think that the main selling point is that they cannot be optimized by Markovian policies. For instance, FTR allows to extract optimal history-dependent policies, which can be valuable, although in the analysis turns out to be less expressive than FOMR, which does not look that useful.\n\nIMPLICATIONS\n\n(C3. Expressivity against tractability) Whereas the Section 4.1 clarifies that tractability is not considered in the analysis, this may defeat the purpose of the analysis itself. Very general models have been proposed in the past, but they intractability makes them less appealing for practitioners. For instance, the POMDP model arguably subsumes all of the objective specifications reported in the paper, but it is intractable in general.\n\nRELATED WORK\n\n(C4. Missing references) This paper is surveying a lot of objective specifications but does little to relate those with pre-existing literature. Various previous works considered extension to the standard RL model (based on Markovian rewards), such as:\n- RL with general utilities (e.g., Zhang et al., Variational policy gradient method for reinforcement learning with general utilities, 2020)\n- Convex RL (e.g., Hazan et al., Provably efficient maximum entropy exploration, 2019; Zahavy et al., Reward is enough for convex MDPs, 2021; Geist et al., Concave utility reinforcement learning: the mean-field game viewpoint, 2021; Mutti et al., Challenging common assumptions in convex reinforcement learning, 2022; Mutti et al., Convex reinforcement learning in finite trials, 2023)\n- Vectorial rewards (e.g., Cheung, Regret minimization for reinforcement learning with vectorial feedback and complex objectives, 2019)\n- Trajectory feedback (e.g., Chatterji et al., On the theory of reinforcement learning with once-per-episode feedback, 2021)\n- Duelling feedback (e.g., Saha et al., Dueling RL: Reinforcement learning with trajectory preferences, 2023)\n- Preference feedback (e.g., Xu et al., Preference-based reinforcement learning with finite-time guarantees, 2020)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)