The Reward Hypothesis is False
Authors: Joar Max Viktor Skalse
Alessandro Abate
Venue: Submitted to ICLR 2023 (2023)
Keywords: the reward hypothesis
reward functions
multi-objective reinforcement learning
MORL

Abstract: The reward hypothesis is the hypothesis that "all of what we mean by goals and purposes can be well thought of as the maximisation of the expected value of the cumulative sum of a received scalar signal". In this paper, we will argue that this hypothesis is false. We will look at three natural classes of reinforcement learning tasks (multi-objective reinforcement learning, risk-averse reinforcement learning, and modal reinforcement learning), and then prove mathematically that these tasks cannot be expressed using any scalar, Markovian reward function. We thus disprove the reward hypothesis by providing many examples of tasks which are both natural and intuitive to describe, but which are nonetheless impossible to express using reward functions. In the process, we provide necessary and sufficient conditions for when a multi-objective reinforcement learning problem can be reduced to ordinary, scalar reward reinforcement learning. We also call attention to a new class of reinforcement learning problems (namely those we call "modal" problems), which have so far not been given any systematic treatment in the reinforcement learning literature.

Under review as a conference paper at ICLR 2023
THREE PROBLEM CLASSES THAT MARKOV REWARDS CANNOT EXPRESS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we study the expressivity of Markovian reward functions, and iden- tify several limitations to what they express. Specifically, we look at three classes of reinforcement learning tasks (multi-objective reinforcement learning, risk-averse reinforcement learning, and modal reinforcement learning), and then prove mathematically that most of the tasks in each of these classes cannot be ex- pressed using scalar, Markovian reward functions. In the process, we provide nec- essary and sufficient conditions for when a multi-objective reinforcement learn- ing problem can reduced to ordinary, scalar reward reinforcement learning. We also call attention to a new class of reinforcement learning problems (namely those we call "modal" problems), which have so far not been given any systematic treatment in the reinforcement learning literature. In addition, we also show that many of these problems can be solved effectively using reinforcement learning. This rules out the possibility that those problems which cannot be expressed using Markovian reward functions also are impossible to learn effectively.
INTRODUCTION
To use reinforcement learning (RL) to solve task, it is necessary to first encode that task using reward function (Sutton & Barto 2018). Usually, these reward functions are Markovian functions from state-actie coate-action--ex---taa triples reals. In this paper, we study the expressivity of Markovian reward functions, and identify several limitations to what they can express. Specifically, we will examine three classes of tasks, all of which are both intuitive understand, and useful in practical situations. We will then show that almost all tasks in each of these three classes are impossible to express using Markovian reward functions. Moreover, we also show that many of these problems can be solved effectively with RL, either by providing references to existing literature, by providing an outline of a possible approach. This rules out the possibility that those problems which cannot be expressed using Markovian reward functions also are impossible to learn effectively.
The first class of problems we look at, in Section 2 is the single-policy version of oujti-objective RL (MORL). In such a problem, the agent receives multiple reward signals, and the aim is to learn single policy that achieves an optimal trade-off of those rewards according to some criterion (Roijers) al. 2013: Liu al., 2015). For example, a single-policy MORL algorithm might attempt to maximise the rewards lexicographically (Skalse et al.] 2022b). We will look at the question of which MORL problems can be reduced to ordinary RL, by providing a scalar reward function that induces the same preferences as the original MORL problem. Moreover, we will provide a complete solution to this problem, in the form of necessary and sufficient conditions. We find that this can only be done for MORL. problems that correspond to a linear weighting of the rewards, which means that it cannot be done for the vast majority of all interesting MORL problems.
The next class of problems we look at, in Section 3 is risks-sensitive RL. There are many contexts where it is desirable to be risk averse. In economics, and related fields, this is often modelled using utility functions U R + R which are concave in some underlying quantity. Can the same thing be done with reward functions? Is it possible to take a reward function, and then create a version of that reward function which induces more risk-averse behaviour? We show that the answer is no none of the standard risk-averse utility functions can be expressed using reward functions. This demonstrates another limitation in the expressive power of Markovian rewards.

---

Under review as a conference paper at ICLR 2023
The last class of problems we look at, in Section 4 is something we call modal tasks. These tasks where the agent is evaluated not only based on what trajectories it generates, but also based on what it could have done along those trajectories. For example, consider the instruction "you should always be able to return to the start state". We provide a formalisation of such tasks, argue that there are many situations in which these tasks could be useful, and finally prove that these tasks also typically cannot be formalised using ordinary reward functions.
In Section 5 we discuss how to solve tasks from each of these classes using RL. We provide ref- erences to existing literature, and then sketch both an approach for learning a wide class of MORL problems, and an approach for learning wide class of modal problems. Finally, in Section 6 we discuss the significance and limitations of our results, together with ways to extend them.
1.1 RELATED WORK
There has been few recent papers which examine the expressivity of Markovian reward functions. The first of these is the work by Abel et al. (202T), who point to three different ways to formalise the notion of "task" (namely, as set of acceptable policies, as an ordering over policies, or as an ordering over trajectories). They then demonstrate that each of these classes contains at least one instance which cannot be expressed using reward function (by using the fact that the set of all optimal policies forms a convex set, and the fact that the reward function is Markovian). They also provide algorithms which compute reward functions for these types of tasks, by constructing linear program. We greatly extend their work by providing new results that are significantly stronger.
Another important paper is the work by Vamplew et al. (2022), , who argue that there are many important aspects of intelligence which can be captured by MORL, but not by scalar RL. Like them, we also argue that MORL is genuine extension of scalar RL, but our approach is quite different. They focus on the question of whether MORL or (scalar) RI. is a better foundation for the development of general intelligence (considering feasibility, safety, and etc), and they provide qualitative arguments and biological evidence. By contrast, we are more narrowly focused on what incentive structures can be expressed by MORL and scalar RL, and our results are mathematical.
There is also other relevant work that is less strongly related. For example, Icarte et al. (0022) point out that there are certain tasks which cannot be expressed using Markovian rewards, and propose a way extend their expressivity by augmenting the reward function with an automaton that they call a reward machine Similar approaches have also been used by e.g. Haaaabbiig et al. (0000)) HHmmondd et al. (202T). There are also other ways to extend Markovian rewards to more general setting, such as convex RL, as studied by c.g. Hazan et al. (2019); Zhang et al. (2020); Zahavy et al. (202)): Geist iet al. (2022); Mutti al. (2022). and vectorial RL, studied by e.g. Cheung (2019a b). Also related is the work by Skalse et al. (2022c), who show that there are certain re relationships that are never satisfied by any pair of reward functions. This paper can also be seen relating earlier work on characterising what kinds of preference structures can be expressed using utility functions, such as the famous work by yon Neumann & Morgenstern| (1947), and other work in game theory.
There is a large literature on (the overlapping topics of) single-policy MORL,, constrained RI, and risk-sensitive RL. Some notable examples of this work includes Achiam et al. (2017); Chow et al. (017);; Miryooseli et al. (2019); Tessler et al. (2019): Skalse et al. (202bb). This existing literature typically Tocuses on the creation of algorithms for solving particular MORL problems, and has so far not tackled the problem of characterising when MORL problems can be reduced to scalar RL. Modal RL has (to the best of our knowledge) never been discussed explicitly in the literature before. However, it relates to some existing work, such side-effect avoidance (Krakovna et al., 2018 2020
Turner et al.) 2020), and the work by Wang et al. (2020).
1.2 PRELIMINARIES
The standard RL setting is formalised using Markov Decision Processes (MDPs), which are tuples (S, A, T, No, R 7) where S is a set of states, A is a set of actions, S x A ~ S is transition function, Mu is an initial state distribution over S, R : S x A x S ~ RR a reward function, where R(s, s') is the reward obtained if the agent moves from state to s' by taking action o, and 7 E (0, 1) is a discount factor. Here, f X ~s Y denotes a probabilistic mapping f from X to Y. A state is terminal if 7 (s,, a) = s and R(s, a, 8) 0 for all a. trajectory & is path 8o, 40. 81... ... in an
2

---

Under review as a conference paper at ICLR 2023
MDP that possible according to Mi and We use G to denote the trajectory returnfunctionn where
G(E) = a =i== y'r.. A policy is a mapping _ : ~s A. and II the set of all policies. Given a policy
æ. its value function V S + R is the function where (s) is the expected future discounted reward when following π from 8, and its Q-function Q" S x A + R = Es [R(s, a, S") + y. VV'(").. The policy evaluation function J : 11 + IR is ( = Es [V (S.)]. If a policy maximises J, then say that this policy is optimal. We denote optimal policies by n,, and their value function and Q-function by V and Q". Moreover, given an MDP M,, we say that M's policy
order is the ordering < II induced by T < m2 comprehensive overview, see Sutton & Barto 2018
J(m)) (TT2 for all Tı, n2. For more
In this paper, will say that reward function R is trivial if J(1)) ((T2) for all Ti, 22- Moreover, we say that Rj and Rg are equivalent if J1 (1() < (1(22) = (2(TT) < (2(22) for all IT, T2, and that they are opposites if (1() < (T(2) - J2(TT) > J2(TT2 for all TT, m2.
MORL problems are formalised using Multi-Objective MDPs (MOMDPs), which are tuples (S,A, T, Mo, R. 7). The only place where MOMDPs differ from MDPs are R, which is func- tion R: S A x S ~ R that, for each transition s, a, s', returns k different rewards (for some k). We denote the reward function that returns the i'th component of R as R₁, and use V." "7 Jr. Gi, etc, to refer to its value functions, Q-functions, evaluation function, return function, etc. Since there may not be any single policy which maximises each component of Ił, a MORL problem additionally needs rule for how to combine and trade off each reward.
1.3 A REMARK ON "TASKS"
In order to determine if a given task can be expressed by Markovian reward functions, we must first determine what means for a reward function to express a task. One answer to this question is to say that a task corresponds to desired policy オ, and that reward function R expresses the task if i is optimal under (possibly with the additional requirement that the only policy that is optimal under Rt. With this definition, we find that any task can be expressed as Markovian reward function, at least as long as ı stationary and deterministic (see Appendix BB.
Another possible definition is to say that task corresponds to an ordering < on II, which encodes a preference ordering over all policies, and that a reward function I expresses the task if J orders II according to <. It is primarily this latter definition that we will use in this paper. The main reason for this is that it often is impossible to find the optimal policy in complex environments. This means that it is not enough for R to have the right optimal policy; it must also induce the right preferences between the (sub-optimal) policies that the policy optimisation algorithm actually considers. The only way robustly ensure that this is the case is if R induces the right policy ordering.
These are not the only two reasonable definitions. As mentioned previously, more definitions can be found in Abel al. 2021).
2 MULTI-OBJECTIVE REINFORCEMENT LEARNING
In this section, we examine the MORL setting. We first need a general definition of what a single- policy MORL problem is. Recall that a MOMDP (S. As T, No. R. 7) by itself has no one canonical objective to maximise. We therefore introduce the notion of a MORL objective:
Definition 1. A MORL objective over k rewards is a function O that takes k policy evaluation functions J ..... Js and returns a (total) ordering to over the set of all policies II.
Given MOMDP M (S. tells us when a policy is preferred over another. We use <- to denote the policy ordering that is obtained when we apply O to M's policy evaluation functions. For the purposes of this paper, we will not need to impose any further requirements on <o. For example, we will not insist that Ko must have a greatest element in IT, or that #1 <o To whenever γ. is Pareto improvement over æ1, etc, even though reasonable MORL objective presumably would have these properties. We next give few examples of some interesting MORL objectives:
R,,), a MORL objective O gives us ordering over II that
Definition 2. Given Jy...Jy. Jy. the LexMax objective
<iex is given by Tı X Liax T2 if and only if there is an E {1 ...m) such that J.(m1) Jr J((T)), and (m( 12( for i.
3

---

Under review as a conference paper at ICLR 2023
Definition 3. Given J1. the MaxMin objective Kwin is given by TT Kusin min; 1(( < min; (T()))
T22
Definition 4. Given J1 J...JJk Jk. and some cm...Cm Cm E R. the MaxSat objective seat is given by Ti Ssac T2 if and only if the number of rewards that satisfy J((T1) 2 ci is larger than the number of rewards that satisfy J(( Ct.
Definition 5, Given J1, J2 and some c E IR, the ConSat objective Acon is given by T Acon T2 if and only if either J1 (TI) < cand (I(T)) < (T2)), or if JI(T)), Ji (1 c cnd J2( < (2())).
In other words, the LexMax objective has lexicographic preferences over Ri... Rm so that policies are first ordered by their expected discounted Ri -rward, and then policies that obtain the same expected discounted -reward are ordered by their expected discounted Rtzreward, and so on. The MaxMin objective orders policies by their worst performance according to any of Rı R... (which could be used to obtain worst-case guarantees). The MaxSat objective only cares about whether policy reaches certain threshold for each reward, and ranks policies based on how many thresholds they reach. The ConSat objective wants to maximise J2. but under the constraint that J1 reaches certain threshold. These MORL objectives are simply a short list of illustrative examples, demonstrating the flexibility of the framework. A few more examples are given in Appendix [D] We next need to define what means reduce a MORL problem to a (scalar) RL problem:
Definition 6. MOMDP M (S, T, Po, R, 7) with objective O is equivalent to the MDP M (S, T, (R,)) if and only if M 's policy order is -gy.
Note that M must have the same states, actions, transition function, initial state distribution, and discount factor, as M. This definition therefore says that M with O is equivalent to M if M is given by replacing I8 = (Ri... ... Rx) with single reward function Rt and it induces the same preferences between all policies as .(J)...J.). We can now derive necessary and sufficient conditions for when a MORL problem can be reduced to reward RL problem.
Theorem 1. If MOMDP M AS No: R. with objective O is equivalent MDP M (S, A, T. Po, RR, 7), then J(m) E Wi (:(TT ( for some wn ... wk E R. Moreover, M with O is also equivalent to the MDP with reward R(s, a, 8') Σx= w/ (s,
Proof. Suppose M with O is equivalent an MDP M (8, A, t, No; IR. 7). First, let m : II I|SS|A be the function that maps each policy π the (Siim))-dimensionall vector where
m( a] =
PPPennSs = s, A. = a).
1=
Moreover, for a reward function R, let R E SRIII be the ||| -immennnaia vector where
R(s, a) Es [R(s,,, S')
Note that we now have that ((z) = m(T) R. for any reward function R. Recall also that multipli- cation by an [S]]-A-ddimensoon any reward function R, we can express its policy evaluation function II - as L m, where is a linear function. In particular, J = L a m, and J, = L, o m for each of R, E R.
vector induces linear function over RIS||A| This means that, for
From the definition of MORL objectives, we have that J(x) is a function of J (T ... (T). This, in turn, means that ī(v) is a function of (ı) (.. Lx (v), for any V E Im (m). Let M be the ([ST[A] x -))dimensional matrix that maps each vector e E |RSSIA to (L) (( (in other words, the matrix whose rows are R R2) Since L(v) is a function of (v) L.(v). we have that L can be expressed as f o M for some function f. Since 7 is a linear function, and since M linear transformation, we that f must be a linear function as well. This means that there are wi...wy w/ E & such that [xx) = Ei=1 ue; Tg, which implies that L(v) = Em we L((v), and further that J(T) Ek_ W; J.( This completes the first part.
Next, let R(s, a, s') = Σ i kw; R, a, s'). Straightforward algebra shows that J(TT) Et_ wa JT(z). Now, since J = J, and since M with O is equivalent to M, we have that M with O is equivalent to the MDP with reward R. This completes the second part.
4

---

Under review as a conference paper at ICLR 2023
This theorem effectively tells that only linear MORL objectives can be represented using scalar- reward RL! This imposes a harsh limitation on what kinds of tasks can be encoded using scalar rewards. Theorem [ also has the following corollary, which is useful for demonstrating when some MORL objective cannot be expressed using scalar reward functions. Given an ordering < over II dependent some evaluation functions JI...Jk: Jk. say that function U IT R represents
T1 < n2. We say that U is a linear representation if U(T) = f(E W4 (T)) for some wi... ... W. R and some f that is strictly monotonic.
< if (TT) < (TT2) +
JI) has a non-lineur representation U, and M is MOMDP whose J- functions are J1 ...... ......y, Jb. then M with O is not equivalent to any MDP.
Corollary 1. If (Ji (Jk...Jk)
Proof. Assume for contradiction that M with O is equivalent the MDP M (S,A, Mo, RR 7)- Then J represents O(J1 ... Jk), and this in turn means that U must be strictly monotonic in J. Moreover, Theorem implies that j = Ex wi Ji for some we .... E IR. However, this contradicts assumptions.
Therefore, we can prove that M with O not equivalent to any MDP by finding a non-linear representation of <a- We will now show that none of the MORL objectives given in Definition 2 can be expressed using single-objective RL, except in a few degenerate edge cases.
Theorem 2. There no MDP equivalent to M with LexMax, as long as M has at least two reward functions that are neither trivial, equivalent, opposites.
Proof. Suppose M with LexMax is equivalent to M = (S, Mo, R, 7). Let be the smallest number such that Rg non-trivial, and let j be the smallest number greater than such that R2 is non-trivial, and not equivalent to or opposite of R,, Then there are IT, T2 such that J:(T)) = J (T2) and (11) < (T2), which means that Xixe T2. Moreover, since J represents <izx. it follows that there π, T such that J,(T) < Jx('') and ((T) > J(x'). Then Theorem 1 in Skalse et al. 2022ch implies that R₃ is equivalent R. However, then J(T) JTT2), which means that J cannot represent M
Theorem 3. There is MDP equivalent to M with MaxMin, unless M has a reward function R, such that J=( $ (T) for all j E (1... .. and all n.
Proof. O.M. is represented by the function U(T) JiTT. Moreover, if M has no reward function R; such that (T) S (T) for all j E {1...k] k} and all æ then this representation is non-linear. Corollary T then implies that M with MaxMin is not equivalent to any MDP
Theorem 4. There is no MDP equivalent to M with MaxSat, as long as M has at least one reward R2 where (1)T < c; and (x(T)) 2 c. for some TT, 52 II.
Proof. Note that (MM is represented by the function U(T) = Σ 1[)(()) 2 G). where [T) 2 ci] is the function that is equal to 1 when J.(T)) 2 C. and O otherwise. Moreover, U is not strictly monotonic any function that is linear in J1 J.. Corollary [ thus implies that M with MaxSat is not equivalent any MDP.
Theorem 5. There is no MDP equivalent M with ConSat, unless either R₁ and R2 are equiv- alent, or max, [T( S
min, [ + c). More- over, this representation is non-linear, unless either Rí and R2 are equivalent, or max, J (TT S c. Corollary then implies that M with ConSat is not equivalent to any MDP.
Proof. O.M. is represented by U(T) ( (f)
else J2(x) else
Theorem 2 show that none of the MORL objectives given in Definition 25 can be expressed using single-objective RL, except in few degenerate cases where those MORL objectives are uninterest- ing. This demonstrates that there no satisfactory way to reduce MORL problems to sewlar-reward RI. (and hence that scalar RL is unable express many natural task specifications).
5

---

Under review as a conference paper at ICLR 2023
3 RISK-SENSITIVE REINFORCEMENT LEARNING
The next area will look at is that of risk-sensitive reinforcement learning. An ordinary RL agent tries to maximise the expectation of its reward function. However, there are many cases where is natural want the agent to be risk-averse. In economies, risk-aversion is typically modelled by using utility functions (c) that are concave in some relevant quantity c (which might be money, for example). A natural question is then whether similar trick may be used with reward functions? That is, given a reward function R1 and a concave function f. can we construct a reward function R2 such that G5( = (C) for all trajectories ?? We will examine this question.
Some of the most common risk aversee utility functions includes exponential utility, isoelastic utility, and quadratic utility. The exponential utility function is given by (cc) -eec where a > is parameter controlling the degree of risk aversion. The isoelastic utility function is given by U(c) = ci-o, for a > 0, a + 1, or by U(c)= = In(c) (corresponding to the case when a = 1). The quadratic utility function is given by (c) = C- ac?, where > 0. Since this function is decreasing for sufficiently large c, its domain is typically restricted to (-o0, 1/2a]. We will examine each of these, and show that none of them can be expressed using reward functions.
In this section, we will consider the domain of G to be the set of all coherent trajectories, not the set of trajectories which are possible under some transition function т. In other words, we consider the set of all trajectories to be (S x A) The reason for this is that we do not want to presume any prior knowledge of the environment. If restrict the set of trajectories we consider, then some risk-averse utility functions can become possible to express (consider the case of a tree-shaped MDP, for example). Finally, we will say that R is constant if it has a constant value for all s, a, s'.
To prove our results, we will make use of three lemmas. The proofs of these lemmas are fairly long, but not very illuminating, and so we have relegated them Appendix A
Lemma 1. If R is non-constant, then for any state s there exists trajectories C1. Sa starting in s such that G(()) + G( G((2) + G(Ca), and G(Ci) + G(Ga).
Lemma 2. If G2(E) (() for all & and some f. then for any transition (s, ss) and any trajectory ( starting in s' R2(s, a, = fRR (s, a, s') + +GG (G) - (C).
Lemma 3. For any non-constant reward R1 and any f that is injective on range (G)) for any y range(R) (R) and any y E (0, 1) there are at most two distinct 2 22 such that f + +xx1) (f)) = [y + 7222) 7f (x2) then there is no reward R2 such that G2 f() for all g.
Using these lemmas, we can now derive our main results:
Theorem 6. For any non-constant reward function Rı and any constant + O, there is no reward function R2 such that Gz(E) = -c for all valid trajectories 5.
Proof. With f(x)= = -=" the expression in Lemma 3 becomes (en()+ + 7e" The deriva-
tive of this expression with respect to x is -a((-e(0+77) + e0²), which has only one root when
Y * 0 and a # O. This means that there can be at most two distinct values I1, 22 such that
(1++)o)))) ty - (o)+) + ge Since -ea is injective, we can thus apply Lemma 3
which completes the proof.
Theorem 7. For any non-constant reward function Rí and any constant a > 0, a: o 1, there is no reward function R2 such that Gz(E) = Gr(E)1-a for all valid trajectories E.
Proof. With f(x) x1-a, the expression in Lemma becomes (y + (12)(1-)) -21-0 The derivative of this expression with respect to x is (a l] - (71 + y) -a), which has only one root when > + 0 and & [0, This means that there can be at most two distinct values 21, 22 such that (y + (1-a) q-t - (y 7x22) (1-a) yar2 p Since æl-a is injective, we can
thus apply Lemma 3. which completes the proof.
Theorem 8. For any non-constant reward function R,, there no reward function R such that Gz(E) = (n))((() for all valid trajectories

---

Under review as a conference paper at ICLR 2023
Proof. With f(x) In(x), the expression in Lemma
becomes 1n(y+)))) In(x). The derivative
of this expression with respect to x is (1/(2) + y/z)
1/z), which has only one root when y # O.
Since In (z) is injective, we can thus apply Lemma 3 which completes the proof.
n
Theorem 9. For any non-constant reward function R₃ and any a > O where maxę G1(5)= S there is no reward function R2 such that G2(E) GE (Gi(g) for all &.
1 2n'
Proof. With f(x) = x - axx,, the expression in Lemma 3 becomes y + a(y + yx)?? This is second polynomial, which means that there be most two distinct values 21, 22 such that y + 7-1 al + ) = y + 722 - a(y + )²2)²² Moreover, if max; G5) S - then
2a
f() = x - ox is injective on range Gi). We can thus apply Lemma
We can thus see that Lemma 3 is quite flexible It allows us to rule out many modifications to G' as impossible, including all the standard risk-averse utility functions. It would be desirable to strengthen these results, and provide necessary and sufficient conditions for when is possible to construct a reward Rg such that G2( (() for some function f and some (non-constant) reward R1. We consider this to be an important question for further work.
4 MODAL REINFORCEMENT LEARNING
The final class of tasks we will examine is one which we have decided refer to as modal tasks. Before we give formal definition of this class, we will first provide some intuition. In analytic philosophy, a distinction is made between categorical facts and modal facts. In short, categorical facts only concern what is true in actuality, whereas modal facts concern what must be true, could have been true, or cannot be true, etc. For example, it is a categorical fact that the Eiffel Tower is brown, and a modal fact that it could have had a different colour. It is (arguably) categorical fact that the number 3 is prime, and a modal fact that it could not have been otherwise. To give another example, there is difference between stating that nothing can travel faster than light and that nothing does travel faster than light - the former statement, which is modal, is stronger than the latter, which is categorical. One can further distinguish between different kinds of possibility (e.g. logical vs physical possibility, etc), and discussions about modality also involves topics such as causality and counterfactuals, etc. A complete treatment of this subject is far beyond the scope of this paper, but for an overview, see e.g. Menzel (2021).
Modality does of course relate to modal logic, but it also relates to temporal logic. In particular, computational tree logic (CTL), and its extensions, can express many modal statements.
The intuition behind this section that a reward function always expressed in terms of categorical facts, whereas many tasks are naturally expressed in terms of modal facts. For example, consider an instruction such as "you should always be able to return to the start state". This instruction seems quite reasonable, but it is not obvious how to translate it into a reward function. Note that this instruction is not telling the agent to actually return to the start state, it merely says that it should maintain the ability to do so. To give a few other examples, consider instructions such as "you should never enter a state from which it is possible to quickly enter an unsafe state", "you should always be able to press the emergency shutdown button", or "you should never enter state where you would be unable to receive a feedback signal".. These instructions all seem very reasonable, and they are expressed in terms of what should be possible impossible along the trajectory of the agent, rather than in terms of what in fact occurs along that trajectory. Given this background motivation, we can now give formal definition of modal tasks:
Definition 7. Given a set of states S and a set of actions A, a modal reward function RD is function R S x A and a transition function J over S and A, and returns real number.
(S x A us S) - R which takes two states s, s' E S, an action a E A,
R (s, a, s',') an environment whose transition function is 7. Here we allow Rº an unrestricted dependence on T, to make our results as general as possible, even if a practical algorithm for solving modal tasks presumably would require restrictions Modal reward functions can be used to express instructions such as those we gave above. For example, a simple case might be "you get 1 reward if you reach this goal state, and -1 reward if
7) is the reward that is obtained when transitioning from state s to s' using action a in
what this dependence can look like (see Appendix E).
7

---

Under review as a conference paper at ICLR 2023
you ever enter state from which you cannot reach the initial state". This reward depends on the transition function, because the transition function determines from which states you can reach the initial state. As usual, Rº then induces Q-function Qo, value function Vo, and evaluation function Jo, etc. We say that a modal reward R and an ordinary reward R are contingently equivalent given transition function if Jo and J induce the same ordering of policies given т, and that they robustly equivalent if j and J induce the same ordering of policies for all T. We use R$ to denote the reward function R2 (s, a') = R (s, a, s', (T). We will also use the following definition:
Definition 8. A modal reward function R is trivial there is a reward function R such that for all R and R2 have the same policy ordering under T.
The intuition here is that a trivial modal reward function does not actually depends on r in any important sense. Note that this is not necessarily say that R R for all т. For example, it could be the case that R is a scaled version of R, or that R& and R differ by potential shaping Ng et al. (199),, or that R& is modified in a way such that (ss [ (s. a, S") = (s)) [R a, S") since none of these differences affect the policy ordering.
Theorem 10. For any modal reward Ro and any transition frantioionfunncion T, there exists a reward function R that is contingently equivalent to R given Moreover, unless R is trivial, there is no reward function that is robustly equivalent to R
Proof. This is straightforward. For the first part, simply let R(s, s²) R (s,,,s',T)) The second part is immediate from the definition of trivial modal reward functions.
In other words, every modal task can be expressed with ordinary reward function in each particular environment, but no reward function expresses a (non-trivial) modal task in all environments. Is this enough? We argue that it is not, because the construction of R& will invariably be laborious, and require detailed knowledge of the environment. For example, consider the task "you should always be able to return to the start state"; here, constructing R, would amount to manually enumerating all the states from which the start state is reachable. This is very much against the spirit of reinforcement learning, where much of the point is that we want to be able to specify tasks which can be pursued in unknown environments. In short, a method which requires a model of the environment is arguably not reinforcement learning method. We thus argue that reward functions are unable to capture modal tasks in a satisfactory way.
One remaining question might be why one would want to express instructions for reinforcement learning agents in terms of modal properties. After all, what benefit is there to the instruction "never enter a state from which it is possible to quickly enter an unsafe state" over the instruction "never enter an unsafe state"? One reason that the former task might lead to behaviour that is more robust to changes in the environment. For example, if an RL agent is trained in a simulated environment, and deployed the real world, then it seems like would be preferable to tell the agent to avoid risky states, rather than unsafe states, since imperfections in the simulation could lead to an underestimation of the risk involved. Another example is the existing work on avoiding side effects (Krakovna et al., 2018 2020 Turner et al. 2020), which it is natural to express in modal terms. This work can be viewed as being aimed at making the behaviour of an RL agent more robust to misspecification of the reward function.
SOLVING "INEXPRESSIBLEF TASKS
We have pointed to three classes of tasks which cannot be expressed using reward functions (namely multi-objective tasks, risk-sensitive tasks, and modal tasks). A natural next question is whether these tasks could be solved using RI., or whether only the tasks which correspond to Markovian reward functions can be effectively learnt? We discuss this issue below.
In short, it is possible to design RL algorithms for tasks in each of these categories. Multi-objective reinforcement learning is well-explored, with many existing algorithms (see Section I.I). Most of these algorithms are designed to solve a specific MORL objective: for example, Skalss et al. (002b)) solve the LexMax objective, and Tessler al. (2019) solve the ConSat objective. There is (to the best of our knowledge) not yet any algorithm for the solving e.g. the MaxMin objective, but there no good reason to believe that such algorithm could not be made. Similarly, there existing
8

---

Under review as a conference paper at ICLR 2023
algorithms for risk- RL (e.g. Chow et al. (2017). and even algorithms that solve certain modal tasks (Krakovna et al. 2018: 2020 Turner et al. 20200 Wang et al. (020).
It should also be possible to design algorithms which can flexibly solve many different tasks from the classes we have discussed (instead of having to be designed for just one particular task). For example, suppose MORL objective can be represented by function U R - R, such that Ti < Ø2 when ( < (T2) ... ...J. (T2)). and that U is differentiable. We give few examples of such objectives Appendix D including e-g. a "soft" version of MaxMin. With such an objective, if we have a policy that is differentiable with respect to some parameters 0, then should be possible compute the gradient of U ( J..(())))) with respect to 6, and then use a policy gradient method to increase U. This means that it should be possible to design an actor-critte algorithm which can solve any differentiable MORI. objective. We consider the development and evaluation of such methods to be promising direction for further work.
We outline a possible approach for solving a wide class of modal tasks Appendix E
DISCUSSION
In this paper, we have studied the ability of Markovian reward functions to express different kinds of problems. We have looked three classes of tasks; multi-objective tasks, risk-sensitive tasks, and modal tasks, and found that Markovian reward functions are unable to express most of the tasks in each of these three classes. We have also provided necessary and sufficient conditions for when Langle-policy MORL problem can be expressed using single reward function (which, as it turns out, almost never), and also drawn attention to a class of tasks which have just barely been explored previously (namely modal tasks). Finally, we have also shown that many of these problems still can be solved with RI., and even outlined some methods for how to extend these solutions.
There are several ways to extend our work. First of all, while we have given many examples of tasks which cannot be formalised using Markovian reward functions, we have not given a general charac- terisation of what reward functions are or are not able to express. It would be very desirable to have a set of intuitive necessary and sufficient conditions, which exactly describe those policy orderings that can be expressed using reward functions, similar to what the VNM axioms provide in the case of utility functions. We outline some initial steps towards such a characterisation in Appendix [ Note that the VNM axioms themselves cannot be directly applied to RI., see Appendix C Additionally, would also be desirable to provide necessary and sufficient conditions for when it is possible to
construct a reward R2 such that G2(E) f(G) (() for some function and some (non-constant)
reward R, as we discussed at the end of Section 3
Our work also provides strong motivation for developing more RL algorithms that learn tasks which cannot be expressed using Markovian reward functions. There are several ways to to this. In section [ we outline an approach for learning any differentiable MORL objective using policy gradients, and in Appendix E. we outline approach for learning a large class of modal tasks. It would also be very interesting to explore more general ways to express RI. tasks, and study their expressivity. For example, it would be interesting to know if (and to what extent) MORL tasks can be expressed using reward machines (Icarte et al. 2022), and similar.
REFERENCES
David Abel, Will Dabney, Anna Harutyunyan, Mark K. Ho, Michael L. Littman, Doina Precup, and Satinder Singh. On the expressivity of markov reward, 2021. URL httph:t///////. http:ss//axxxv.orrg.
abs/ 208//111..0 00876
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML' 17, pp. 22-31. JMLR.org, 2017.
Wang Chi Cheung. Exploration-explootttii trade-off in reinforcement learning on online markov decision processes with global concave rewards, 2019a. URL https: // //arxvvv..v///////////.aa//aaa.v org/ abs/ i 1905. 66466

---

Under review as a conference paper at ICLR 2023
Wang Chi Cheung. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019b. URL htt.tttts///ppoceeeeee///
neuri wttprlis..pppppe/ppeee hcc/ppaper/2111//111e pdf
Yinlam Chow, Mohammad Ghavamzadch, Lucas Janson, and Marco Pavone. Risk-constrained re- inforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(1): 6070-6120, 2017.
Matthieu Geist, Julien Pérolat, Mathieu Laurière. Romuald Elic, Sarah Perrin, Oliver Bachem, Rémi Munos, and Olivier Pictquin. Concave utility reinforcement learning: The mean-field game view- point. In Proceedings of the 2/st International Conference on Autonomous Agents and Mul- fiagent Systems, AAMAS '22, pp. 489-497, Richland, SC, 2022. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450392136.
L. Hammond, A. Abate, J. Gutierrez, and M. Wooldridge. Multi-agent reinforcement learning with temporal logic specifications. In Proceedings of the 20th International Conference Au- tonomous Agents and MultiAgent Systems, pp. 583-592, 2021.
M. Hasanbeig, D. Kroening, and A. Abate. Deep reinforcement learning with temporal logics. In Proceedings of FORMATS, LNCS 12288, pp. 1-22, 2020.
Elad Hazan, Sham M. Kakade, Karan Singh, and Abby van Soest. Provably efficient maximum entropy exploration. In 36th International Conference on Machine Learning, ICML 2019, 36th International Conference Machine Learning, ICML 2019, pp. 4774-4786. International Ma- chine Learning Society (IMLS). January 2019. 36th International Conference on Machine Learn- Conference date: 09-06-201 Through 15-06-2019.
ing, ICML 2019;
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A. Mcllraith. Reward ma- chines: Exploiting reward function structure in reinforcement learning. Journal of Artificial In- telligence Research, 73:173-208 jan 2022. doi: 10.1613/jair.1.122 1.1444..
Victoria Krakovna, Laurent Orseau, Ramana Kumar, Miljan Martic, and Shane Legg. Penalizing side effects using stepwise relative reachability, 2018. URL https:
1106601186
Victoria Krakovna, Laurent Orseau, Richard Ngo, Miljan Martic, and Shane Legg. Avoiding side effects by considering future tasks, 2020. |
org/ abs 2010. 0.00000000 07877
C. Liu, Xu, and D. Hu. Multiobjectivve reinforcement learning: A comprehensive overview. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 45(3):385 -388899--,,00 2015.
Christopher Menzel. Possible Worlds. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Fall 2021 edition, 2021.
Sobhan Miryoosefi, Kianté Brantley, Hal Daumé III, Miroslav Dudík, and Robert E. Schapire. Rein- forcement learning with convex constraints. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 14070-14079, 2019.
Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Challenging common assumptions convex reinforcement learning. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2022.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the Sixteenth International Con- ference Machine Learning, pp. 278-287 Bled, Slovenia, 1999. Morgan Kaufmann Publishers Inc.
D. M. Roijers, P. Vamplew, S. Whiteson, and R. Dazeley. A survey of multi-objective sequential Decision-making Journal of Artificial Intelligence Research, 48:67-113, 10 2013. ISSN 1076- 9757. doi: 10. 10.1i13// /ttpa///././//./////.oo/..oo.o.. wwwoi.org/10..0
3987
10

---

Under review as a conference paper at ICLR 2023
Satinder Singh, Tommi Jaakkola, Michael L. Littman, and Csaba Szepesvári. Convergence results for single-step on-policy reinforeement-lcaniig algorithms. Machine Learning, 38:287-308, 2000.
Joar Skalse, Matthew Corrugia-Robers.. Stuart Russell, Alessandro Abate, and Adam Gleave. Invariance in policy optimisation and partial identifiability in reward learning, 2022a. URL
https://arxiv. https///aaxiivoor//aaoo... ats wttp///////.....////////
Joar Skalse, Lewis Hammond, Charlie Griffin, and Alessandro Abate. Lexicographic multi-objective reinforcement learning. In Lud De Raedt (ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 3430-3436. International Joint Conferences Artificial Intelligence Organization, 7 2022b. doi: (0.24963fjccai.2222/776 URL https:
Main Track.
Joar Skalse, Niki Howe, Krasheninnikov Dima, and David Krueger. Defining and characterizing reward hacking. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2022c.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
Chen Tessler, Daniel J. Mankowitz, and Shie Mannor. Reward constrained policy optimization. In Proceedings of the 7th International Conference on Learning Representations. 2019.
Alex Turner, Neale Ratzlaff, and Prasad Tadepalli. Avoiding side effects in complex envi- ronments. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 21406-21415. Curran As- sociates, Inc., 2020. htuphtttsss/pprocedii..sss neuripss......p.pp.pp..........e httpps.ccppppppp cc/papprr/220//ille 155000285553544451100ffa------23
pdf
Peter Vamplew, Benjamin J. Smith, Johan Källström, Gabriel Ramos, Roxana Rádulescu, Diederik M. Roijers, Conor F. Hayes, Fredrik Heintz, Patrick Mannion, Pieter K. Libin, Richard Dazeley, and Cameron Foale. Scalar reward is not enough: response silver, singh, precup and sutton (2021). Autonomous Agents and Multi-Agent Systems, 36(2):1, Jul 2022. ISSN 1573-7454, doi: 02.10077/10458-02--05555 610458-022-09575-2
URL /
J. von Neumann and O. Morgenstern. Theory of games and economic behavior. Princeton University Press, 1947.
Yu Wang, Nima Roohi, Matthew West, Mahesh Viswanathan, and Geir Dullerud. Statistically model checking petl specifications markov decision processes via reinforcement learning. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 1392-1397, 2020. doi: 10. 1109/CDDC424402200005333399
Tom Zahavy, Brendan O'Donoguue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps, 2021.
00661
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvári, and Mengdi Wang. Variational policy gradient method for reinforeement learning with general utilities. Advances in Neural Information Processing Systems, 2020-December, 2020. ISSN 1049-5258.

---

Under review as a conference paper at ICLR 2023
A PROOFS OF LEMMAS
In this Appendix, we provide the proofs of the lemmas from Section 3
Lemma 1. If R is non-constant, then any state 8 there exists trajectories Çi, S2, S3 starting in s such that G((1) + G((2). G((2) + G(C3), and G(Ci) + G((3).
Proof. First note that if R is non-constant, then there must be some state s and some trajectories &, &2 starting in such that G(51) + G(E2) (this follows from Theorem 3.8 in Skalse et al. 2022a
We will establish that there is E3 starting in s such that G(Ex) + G(51) and G(Es) #0 ((2)). and
then show that this implies that such trajectories exist for all states.
Suppose for contradiction that for any E3 starting in s. either G((a) = G(Ei) or G((a) = G( Consider a transition (s, a, s). and let = ()),,)) + E and Ç2 (s, a, s) + f2; will do case enumeration, and show that either G(G)) or G((2) must be distinct from both G(E) and G(
Note that G((+) = R(s, a, 8) + GG(() and G((2) = R(s,a,s) + GG(2))
Case 1: G((i)= = G(ÉI), G((2) - G(Ez). If R(s, a. 8) +7((E) - G(ÉI) then R(s, 8) = (1 G(E)) and similarly, if R(s, a,)) G((2 = G(fz) then 8) = (1 (fE2). This is a contradiction, since G(f1) # G(Ez) and x
Case 2: G(()) G((2) G(E)). If R(s, a, s) +,G(E)) G(Ei) then R(s, a, 8) = (1 ----- G(E)) Using R(s,a, 8) + GG((2) = G(E)), we get (1()) + +G((() = G(()) By rearranging, we get (G(()) G(f2)) 0. This is a contradiction, since G(5)) # G((2) and y + 0.
Case 3: G((1) G((2) = G(E2). This is analogous to Case 2.
Case G((1) G(Ez). G((²) G( If a, s) + G(( = G(E2) then R(s, a, = then R(s, a. s) = G( - G(E.) Combining this, and rearranging, gives (1+7)G(()) = ((2). This is a contradiction, since G(G)) * G(E2) and y * 1.
G((2) - G((2), and similarly. if R(s, +G(() G(E)
This exhausts all cases, which means that if R is non-constant, then there must be some state s and some trajectories Ç1. (2, S3 starting in s such that G((i) # G((2), G(22) * G(Ga), and G(Ci) of G(Ga). Finally, note that this means that we can construct such trajectories for any state 8', by simply composing a transition (s', a,, 8) with each of C1: C2. C3.
Lemma 2. If Gz(L)) = (G) for all & and some f. then for any transition (s, a, s') and any trajectory Ç starting in s Re(s, a, s') ) = (R11 (G(() (((((()))
Proof. Suppose that G2(E) f(G for all trajectories &. Let (s. a, s²) be arbitrary transition, let ( be an arbitrary trajectory starting in 8', and let E = (s, a, 8') + C. We have that G2(E) = 82( GG(C)) and also that G2(E) = (()) which implies that
(s a, s') + G2((() = (G).
Since Gı(g)= Rs( 8") + GG) this implies that
R + G2(() f(Ri(s,a, (()) ((((())
By using the fact that G2(C) = f(G)(()). and rearranging, we get that Rz(s.a,s') f(i a, +x((()) - (f(G)(())
-f(((()))(((((((())
Since (s,a, a,,s) and were chosen arbitrarily, this completes the proof.
Lemma 3. For any non-constant reward Ri and any f that is injective on range(Gr) (1)). for any range R1) and any E (0, 1) there are at most two distinct 21,22 such that fly + yx1) 7f = fl + 7322) (x2)) then there no reward R2 such that Gz(E) = f(Gi(E)) for all
Proof.
Suppose for contradiction that G2(E) = f(Gi(E)) for all E. Let (s, a, 8') be an arbitrary transition. Applying Lemma 2 we get that
Ra(s, = [(Ri((RRR) + (()
12

---

Under review as a conference paper at ICLR 2023
for all trajectories starting in s'. For clarity, let Gc( and y as, so that fly + y²) -x) By assumption, there can be at most two distinct values I1, T2 such that f (f(z)) f(y + yx2) - -f However, Lemma [ iimplies that there are at least three Ç1, S2, Sa starting in s' with distinct values of G1- Since f is injective on range(G.) this means that there least three distinct values of for which f(y + 7/) 1000---- (=) must be constant (and equal to (2,s, a, s'), which is contradiction.
B TOWARDS NECESSARY AND SUFFICIENT CONDITIONS
In this paper, we have provided several examples of "natural" policy orderings which cannot be represented using a reward function. It would be desirable to have a set necessary and sufficient conditions to characterise those orderings over II that can be expressed by reward functions, similar to that provided by the VNM axioms (the VNM axioms themselves do not provide this, see Ap- pendix Cp. We consider this to be important topic for future work. In this section, will discuss a few interesting properties which are shared by all policy orderings which can be represented by re- ward functions. We believe that these examples will help with building an intuition for what reward functions can and cannot express.
We would first like to point that, while it seems difficult to characterise the policy orderings which can be expressed by reward functions, it is fairly straightforward to exactly characterise the sets of policies II that can be optimal under some reward function:
Proposition A set of policies il is the optimal policy set for some reward function if and only if there is a function o : S + ((A) / Ø that maps each state to a (non-empty) set of " "optimal actions" ", and π E T1 if and only if su)p((((()) S o(s).
Proof. For the "if" part, consider the reward function R. where R(s, a, s¹) = if a o(s). and R(s, a, s') = -1 otherwise. The "only if" part follows from the fact that the optimal Q-function Q is the same for all optimal policies, so we can let o(s) arg max, Q" (s(ss)). a).
L
This immediately lets us rule out many policy orderings as inexpressible. For example, consider the task "always go in the same direction" - this task cannot be expressed as a reward function, because any policy that mixes the actions of two other optimal policies must itself optimal. also shows that Markovian reward functions cannot be used to encourage stochastic policies. For example, there no Markovian reward function under which "play rock, paper, and scissors with equal probability" is the unique optimal policy.
The next thing we would like to point out that no reward function can express an ordering over II that has countable number of equivalence classes (except trivial reward functions, which have only one equivalence class). This simple fact also rules out many orderings.
Proposition If is non-trivial then J has an uncountable number of equivalence classes.
Proof. This follows from the intermediate value theorem, and the fact that ./ is continuous in II.
This simple observation can be used to e.g. create an alternative proof Theorem 4 which says that the MaxSat objective cannot be represented objectives such as e.g. (TT) = mippgs) G(E), which evaluates policies according to the worst trajectory in their support, cannot be represented (since any policy then has the same value as some deterministic policy, and since there is only a finite number of deterministic policies).
(scalar) reward function. It also shows that
C A DIGRESSION ON THE VON NEUMANN-MORGENSTENR AXIOMS
The famous VNM axioms, due to von Neumann & Morgenstern 1947). provide necessary and sufficient conditions for when a utility function can be used to represent preference ordering for lotteries finite choice set. In MDP, a policy induces distribution over trajectories, and a reward function assigns a value to each trajectory. One might then wonder the VNM axioms could provide necessary and sufficient conditions for when ordering over IT can be realised using
13

---

Under review as a conference paper at ICLR 2023
reward function. This is not the case, and in this appendix, briefty point out why. These results are not novel to this paper, but are instead provided to help with intuition building.
First of all, the VNM theorem assumes that the choice set is finite, whereas in an MDP, the number of trajectories is (countably) infinite. There are preferences between distributions over countable choice sets which satisfy the VNM axioms, but which utility functions Second, not all distributions over trajectories can be represented as a policy (unless allow both the policy and the transition function to be non-stationary). Third, there is special structure to how a reward function assigns value to a trajectory. and not all functions 3-t + R can be represented in this way. This means that the VNM axioms are not applicable RL. However, may still be possible to provide similar intuitive necessary and sufficient conditions for the RL case. We consider this to an important topic for future work.
nonetheless not be represented using
D MORE MORL OBJECTIVES
In this Appendix, we give even more examples of MORL objectives, and some comments on how to construct them - the purpose of this is mainly just to show how rich this space is. First, similar to the MaxMin objective, we might want to judge policy according its best performance:
Definition 9. Given JI...J%, the MaxMax objective -Max is given by I XMax 2
max; J: (T) < max; (T22).
We would next like to point out that it is possible to create smooth versions of almost any MORL objective. In Section 5 we outline an approach for learning any continuous, differentiable MORL objective, so this is quite useful. We begin with a soft version of the MaxMax objective:
Definition 10. Given J1 Jy and a > O, the Soft MaxMax objective <Maxsort is given by
k
JuaKSoeL (T) =
Σ ((T))))))))
adi(t)
This is of course not the only way to continuously approximate MaxMax, it is just an example of one way of doing it. Here a controls how "sharp" the approximation is the larger a is, the closer Juaxsott: gets the sharp max function, and the smaller is, the closer gets to the arithmetic mean function (so by varying we can continuously interpolate between them). Similarly, we can also create a smooth version of MaxMin:
Definition 11. Given J1 ...J. Jy and a > O, the Soft MaxMin objective KMinsore is given by
Juinsoft (T)
(aT)e-aJiC
e (aal((t))))
As before, the larger a is, the closer Jeinsort gets the sharp min function, and the smaller is,
the closer it gets to the arithmetic mean function We can also smoothen MaxSat:
Definition 12. Given J1 JI...Je
N..JJJ. Jk C1 ....Ck. Ck. and a > 0, the Soft MaxSat objective Ksatsoft is
(
Jaatsoft (T) Σ 1=1
The larger a is, the closer Jsat gets to the sharp MaxSat function (and the smaller a gets, the closer JsatSoft gets flat 0.5). And, again, this is of course not the only way to create smooth version of MaxSat. It is unclear if it is possible to create a smooth version of ConSat without having any prior knowledge of (a lower bound of) the value of min, J1 (T)) but with this value it should be reasonably straightforward (see the construction in Theorem 5). As for LexMax, we can of course create smooth approximation of it by taking linear approximation of the weights, but here would need some prior knowledge of max, J (TT) max, (T).
For example, consider the ordering that prefers all distributions with infinite support over all distributions with finite support, and which is indifferent between any two distributions in either of these classes.
14

---

Under review as a conference paper at ICLR 2023
E A METHOD FOR SOLVING MODAL TASKS
In this Appendix, we give an outline of one possible method for solving modal tasks. We mainly want to show that it is feasible learn modal tasks, and so we only provide solution sketch; the task of implementing and evaluating this method is something we leave as topic for future work.
We will first define a restricted class of modal tasks, which both very expressive, and also more amenable to learning than the more general version given in Definition
Definition 13. An affordance consists of a reward function and a discounl factor, (R,7), 7). and an affordance-based reward is a function R -S x A x 8 x RR28 - RR that is continuous in the last 2k arguments. An infordance-basee MDP is a tuple (S, A. No. R .7, (R. 2)).).). where the reward given for transitioning from s to s' via a is R (s, a, V.* is the optimal value function of the i'th affordance.
Vi Vs) (s). ... (5'), where
This definition requires some explanation, In psychology (and other fields, such as user interface design), an affordance is, roughly, a perceived possible action, perceived way use object. For example, if you see a button, then the fact that you can press that button, and expect something to happen, is part of how you perceive it, in a way that might not be the case if you could somehow show the button to a premodern human. It can also be used to refer to choice or action that is perceived as available in some context (without being tied to an object). Here, we are using it to refer to task that could be performed in an MDP. The intuition is that R is allowed to depend on what could be done from s and s', in addition to the state features of s and s'.
Before outlining an algorithm, let us first give a few examples of how to formalise modal tasks within this framework. First consider the instruction "you should always be able to return to the start state". We can formalise this using reward function Rt that gives 1 reward if the start state entered, and otherwise, and pair it up with a discount parameter y that is very close to 1. We where
could then set R to, for example, R (s, s', (s), (s') = R(s, a, s') tan R describes some base task. In this way, no reward is given if the start state cannot be reached from s'. Next, consider the instruction "never enter a state from which it is possible to quickly enter an unsafe state"' To formalise this, let R1 give reward if an unsafe state is entered, and 0 otherwise, and let y correspond a very high discount rate (e.g. 0.7). We could then set Rº to, for example, Rº (s, s', V=))) = R(s, s') 5') - (s'(,,, where R again describes some base task.
These examples show that our laffordance-basedd able to formalise many natural modal tasks in satisfactory way, including most of our motivating examples P However, the definition could of course be made more general. For example, we could allow the affordances to themselves be based on affordance-based reward functions, etc. However, it is not clear if this would bring much benefit in practice.
MDPs are quite flexible, and that they should be
Let us now outline an approach for solving affordance-based MDPs using reinforcement learn- ing, specifically using an action-value method. First, let the agent maintain k + 1 Q-functions, Q& Jp,Qi...,, Qi. one for Ro and one for each affordance (R, 7²). Next, we suppose that the agent updates each of Qi....,QP QQ using an off-policy update rule, such as Q-learning; this will ensure that Qi...., Qk converge to their true values (i.c. to Qi ... QD), as long as the agent ex- plores infinitely often. Note that the use of an pollcy update rule is crucial. Next, let the agent update Qo as if it were an ordinary Markovian reward function, using the reward R(s, a, s') = R a, s', Vi (s)... (s). Vi(s').. ... va((s)), where (s(s) is given by max, Qi ()). In other words, we let it update Q³ using an estimate of the true value of Ro, expressed in terms of its current estimates of Vi ... VV. The fact that Q1...., Q& converge Qi, Qi, and the fact that Ro is continuous in its value function arguments, will ensure that the estimate It also converges to the true value of R The update rule used for Qo could be either on- oolpoiicy or off-policy We then suppose that the agent selects its actions by applying a Bandit algorithm to Qo, and that this Bandit algorithm is greedy in the limit, but also explores infinitely often, usual.
This algorithm should be able to learn to optimise the reward in any affordance- MDP. In the tabular case, it should be possible (and reasonably straightforward) to prove that it always converges to an optimal policy (assuming that appropriate learning rates are used, etc), using Lemma 1 in
This arguahly excludes "you should never enter state where you would be unable to receive feedback signal". However, this instruction only makes sense in multi-agent setting.
15

---

Under review as a conference paper at ICLR 2023
Singh et al. (2000). We would also expect it to perform well in practice, when used with function approximators (such as neural networks). However, we leave the task of implementing and properly evaluating this approach as topic for future work.
There are also several ways that this algorithm could be tweaked or improved. For example, the algorithm we have described is action-value algorithm, but the same approach could of course be used to make an actor-critic algorithm instead. We also suspect that there could be interesting modifications one could make the exploration strategy of the algorithm. If standard Bandit algorithm (such as e-greedy) is used, then the agent will mostly take actions that are optimal under its current estimate of Q In the ordinary case, this is good, because it leads the agent spend more time in the parts of the MDP that are relevant for maximising the reward. However, in this MDP case, there is worry that it could lead the agent to neglect the parts of the (affordance- that are relevant for learning more about Vi ... V which might slow down the learning. Again, we leave such developments for future work, since our aim here only is to show that is feasible to learn non-trivial modal tasks.
We also want to point out that the work by Wang et al. (2020) could provide another starting point for learning modal tasks using RL. In their work, they present some RL-based methods for determining whether a specification in Probabilistic Computational Tree Logic (PCTL) holds in an MDP. PCTL be used to specify many kinds of properties of states in MDPs which depend on the transition function, including e.g. what states can and cannot be reached from a particular state, and with what probability, etc. We therefore specify non-trivial modal tasks by providing number of PCTL formulas, and allowing the reward function to depend on the truth values of these formulas. That is, could consider a setup that is analogous "affordances" are replaced by PCTL formulas. It should then be possible to learn tasks specified in this manner by using the techniques of Wang et al. (2020) learn the values of the PCTL formulas, and then using ordinary RL to train on the resulting reward function.
that which we give in Definition 13 but where the
16


Reviews:
[{"review_id": "cB0Toe6Puzu", "reviewer": "Reviewer_UtAh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper discusses three types of problems where the goal cannot be expressed as scalar values in MDP (MORL where the objective cannot be expressed as weighted sums of individual objectives, trajectory-wise risk-sensitive problems, and modal problems). They also propose potential solutions for modal problems and discussed relevant literature for solving MORL and risk-sensitive problems.", "summary_of_the_review": "I’m not yet convinced by the arguments about modal problems, and I also think that risk-sensitive problems are limited by the expressivity of MDP, not necessarily because the reward hypothesis is False. I am interested in hearing the author’s response, and would either revise my review or suggest that the authors adjust the claim of the paper to be less strong than the “reward hypothesis is False”.\n", "strength_and_weaknesses": "Strengths:\n1. The paper is very well written and easy to follow. The introduction follows a clear narrative that takes the reader through all the class of problems and considerations. The subsequent sections also follow a consistent structure. Despite being dense in theorems, it’s easy to navigate.\n2. The paper offers mathematical insight into each theorem in plain language. This also highlights the significance and logical progression of different theorems in this work.\n3. Beyond showing MDPs where the goal cannot be expressed as scalar values, the author also devises solutions for these problems in section 5 as well as the appendix (modal problems).\n\n\nWeakness:\nI believe that the paper would be stronger if the author could address the following questions. Because there is a wide range of interpretations of the reward hypothesis, I hereby divide my questions into “philosophical” and “technical” ones:\n\nPhilosophical:\n1. Response by Sutton et al. The authors’ argument for refuting the reward hypothesis is based on the fact that not all “goals and purposes” can be represented by scalar reward. This reminds me of one of Rich Sutton’s responses that goals ultimately lead to some desired behavior/policies. And one can trivially design a reward function to describe such optimal policy by penalizing actions that are not in the behavior. I wonder if the authors disagree with this. This may also be a point worth clarifying in the paper.\n2. It’s not that the hypothesis is False, it’s MDP’s fault. One of the main reasons that risk-averse learning and modal learning fail the reward hypothesis is because they contradict the Markov assumption. I.e. for risk-averse learning, the reward depends on the agents’ future actions and for modal learning, the reward depends on the transition function. Since the reward hypothesis, as cited, does not imply Markov conditions, I wonder if the authors should narrow the claim to “The reward hypothesis is false under the Markov assumption”?\n3. Undesirable/unsatisfactory is not impossible. In modal learning, the author points out that constructing a scalar reward function for modal learning is “undesirable” as it requires an enumeration of all the states and actions and detailed knowledge of the environment. However, if I understand correctly, it is still “possible” and there exists such a scalar reward function in any specific env. Sutton et al noted this in their post saying “is it always beneficial to describe goals as rewards in practice? Probably not.” I believe this doesn’t refute the original reward hypothesis that constructing a reward function is possible. Please let me know if I didn’t understand this part correctly.\n\nTechnical:\n1. Non-differentiable MORL problem. The authors mention in section 5 that MORL problems with differentiable U can be solved via existing solvers. However, if I understand correctly, MaxSat is a non-differentiable MORL problem. Do the authors have any suggestions for solving this problem?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "aCYRv6yf5aF", "reviewer": "Reviewer_dSf2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper operationalizes the reward hypothesis as: Any task of interest can be captured as the maximization of the expected sum of a scalar reward signal R(s, a, s’). They then show several ways in which this hypothesis fails:\n\n1. Many natural task formulations such as “Do X, but break ties according to Y” can be formulated using multi-objective reinforcement learning. The policy ordering induced by such a formulation cannot be expressed by any reward signal R(s, a, s’).\n2. It is common to be risk-sensitive in pursuit of some goal: for example, if M() captures the amount of money you have, then you often care a lot if M() becomes very low or zero, but don’t care as much if M() increases by a similar amount. In economics this is often handled by transforming M() into some new function M’, such as M’(x) = -exp(αM(x)). In RL, we might similarly want to choose a risk-averse policy that corresponds to a Q function Q’(s, a) = -exp(αQ(s, a)). However, barring uninteresting edge cases, there is no reward function R’ that induces Q’, due to the sequential nature of the task and how R’ is _summed_ to get Q’.\n3. We may want task specifications that depend on counterfactuals and possibilities, e.g. “accomplish X while remaining _able to reach_ the start state”. These can be formalized as reward functions that depend on the transition function. While it is of course possible to encode this as a regular reward function for a given transition function, there is no regular reward function that works for all transition functions (again barring uninteresting edge cases).", "summary_of_the_review": "This paper provides clear technical results arguing against a commonly-held hypothesis. While I do have some nitpicks, they are just that: nitpicks.", "strength_and_weaknesses": "Strengths:\n1. The paper adds to the literature showing that the reward hypothesis is false (as previously demonstrated by Abel et al, which received an Outstanding Paper at NeurIPS, and discussed informally in the AI alignment community, e.g. [1]). To my knowledge, while the specific failures shown in this paper were generally suspected to be issues with the reward hypothesis, this is the first time they have been shown formally. I find the risk aversion result particularly strong.\n\nWeaknesses:\n1. In its discussion of MORL, the paper primarily analyzes policy orderings, even though what we typically care about in practice is the chosen policy. When considering the chosen policy, there is a significantly stronger argument that a linear combination of (history-based) rewards captures what we want (discussed below).\n2. I found the “modal reward” section discussion to be fairly unconvincing, as it is not clear why we should care about robust equivalence rather than contingent equivalence (discussed further below).\n\n**MORL**\n\nI think there is a fairly strong argument for single-objective learning given _trajectory-based_ rewards, based on applications of decision theory to decision-procedures over trajectories (i.e. policies). Specifically:\n\n1. We assume that when considering each $R_i(\\xi)$ individually, we would like to choose trajectories on the basis of expected value under $R_i$. When S and A are finite, and we have a finite horizon length, this can be justified by the VNM theorem, since there are only a finite number of trajectories. Of course, this may require transformations to encode e.g. risk-aversion (such as switching from amount of money to log(amount of money), to be risk-averse w.r.t.money).\n2. Similarly we assume that our final decision-procedure after aggregating should also choose trajectories on the basis of expected value under some reward function (once again, this is just saying that it should be VNM-rational).\n3. We make the hopefully-uncontroversial assumption that if all of the $R_i$ are indifferent between two trajectories, then so too is our final decision-procedure.\n4. The Harsanyi Aggregation Theorem [2] then says that our decision-procedure can be represented as maximizing the weighted linear sum of the various $R_i$.\n5. The (history-dependent) policy that maximizes the weighted linear sum of the various $R_i$ is obviously consistent with this decision-procedure, and so is a good target to learn, which can be done with single-objective RL\n\n(I have read Appendix C and I do not think this argument falls prey to any of the mistakes you mention there. Still, I have not checked the argument carefully; there could be some problem.)\n\nOf course, this does not save the reward hypothesis (as you define it) because it requires us to use _trajectory-based_ rewards, whereas you operationalize the reward hypothesis as using _Markovian_ rewards. Nonetheless, I think it is worth mentioning this argument in favor of single-objective RL (if only in an appendix).\n\nWhat happens if you try to run your argument on this construction? The first obstacle is that I am using trajectory-based rewards while your argument assumes Markovian rewards. However, I would guess that your argument applies just as well to trajectory-based rewards, as the key linearity-based arguments would still apply.\n\nIn that case, your result would say that for specific MORL objectives, the resulting policy ordering cannot be expressed by a single trajectory-based reward. One possibility is that the MORL objectives choose policies that are not consistent with a VNM-rational decision-procedure over trajectories, violating step 2 of my argument; if this were the case I would take that as a strike against MORL objectives rather than a strike against the reward hypothesis.\n\nHowever, the more likely scenario is that both claims are simultaneously true. My argument only makes claims about the final decision-procedure over trajectories, i.e. the _optimal_ policy chosen by the single trajectory-based reward. It could indeed be the case that the ordering over other, non-optimal policies is different between the MORL objective and any possible trajectory-based reward. However in this case it is unclear why I should care. Ultimately we only obtain and deploy one policy; why should I care what the ordering over other policies is?\n\n**Modal rewards**\n\nIt is not clear to me why we should ask for robust equivalence instead of contingent equivalence. As I understand it, your argument for this claim is:\n\n> the construction of R♢τ will invariably be laborious, and require detailed knowledge of the environment. For example, consider the task “you should always be able to return to the start state”; here, constructing R♢τ would amount to manually enumerating all the states from which the start state is reachable. This is very much against the spirit of reinforcement learning, where much of the point is that we want to be able to specify tasks which can be pursued in unknown environments. \n\nHowever, it is unclear to me how you do any better with a modal reward function: how do you write down R(s, a, s’, τ) in full generality? I’m not familiar with all of the references you cite, but in e.g. Krakovna et al., 2018; 2020a, Turner et al., 2020, and your own Appendix E, there is no R(s, a, s’, τ) that gets written down and then maximized; rather the algorithms work by automatically building the contingently-equivalent reward R(s, a, s’) by learning it from experience. Why should we not think of this as “writing down the contingently-equivalent reward, and then maximizing that”?\n\nThe one difference that I see is that the contingently-equivalent reward is built _at the same time_ that the policy is learned, but this is surely just an efficiency improvement: you could also design methods that first learned the contingently-equivalent reward, and then maximized it. Given that the reward hypothesis (as you have operationalized and analyzed it) is primarily about what is theoretically possible; an argument that depends entirely on an efficiency difference does not seem appropriate.\n\n(You might also say that the fact that you have to learn the reward means it is very hard to provide in practice, which is a strike against the reward hypothesis, but in the introduction you emphasize that the reward hypothesis is about what can be done _in principle_ and not about what is difficult to do in practice.)\n\nMinor issues:\n\nLemma 1 is false as stated: given some s’, the reward could be constant on the states reachable from s’, while being non-constant on states unreachable from s’. In the proof, the issue arises here:\n\n> Finally, note that this means that we can construct such trajectories for any state s′, by simply composing a transition ⟨s′, a, s⟩ with each of ζ1, ζ2, ζ3.\n\nThis doesn’t work if that transition is impossible (as in the preliminaries you require trajectories to be “possible according to µ0 and τ”). (If you remove this requirement I would expect this breaks other proofs.)\n\n[1] Ngo, Richard. “Coherent behaviour in the real world is an incoherent concept.”\n\n[2] Harsanyi, John C. \"Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility.\" Journal of political economy 63.4 (1955): 309-321.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "_GSCXhKPCC", "reviewer": "Reviewer_abfw", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper is about the reward hypothesis (roughly that a reinforcement learning agent would only need one scalar signal to learn \"any\" task) and wants to show that this is not the case for many problems. The main portion of the paper consists of three settings (multi-objective, risk-averse and modal) and in each of these settings some formalizations and some properties are defined (and somewhat proven). The paper is purely theoretical.\n", "summary_of_the_review": "This paper has several interesting things to say, about a topic that is currently active, but it is unclear what are the contributions, and furthermore it tries to do too many things in one paper without (almost) any illustrations, nor experiments, and overall the main portions sound not too novel at all, given the current state of the art in RL.", "strength_and_weaknesses": "The main strength of the paper is the topic, which receives a lot of attention in the last few years: reward functions, what can they do, what is their expressivity, how can they be learned/engineered/constructed, model/problem classes, and how to employ them in typical RL frameworks.\n\nHowever, the paper does not really deliver on its main promises stated early in the paper (and the title). I guess it is fairly well known that, in principle, many situations exist where reward functions are multi-dimensional, or dependend on time or previous states, or something else, and then it is not possible to reduce it simply to a single scalar. However, for many (all?) problems it can be done, but typically with an exponential blowup in the parameters of the RL problem. For example, in the sub-area of non-Markovian reward functions, which is highly related to the \"modal setting\" in Section 4, problems with highly complex, non-Markovian reward functions can systematically be \"compiled\" into regular (single scalar, Markovian) problems by compiling necessary sequences of states (and actions) into a new state space (which is typically exponentially larger than the original). In this case the new problem can be solved using standard methods in deep RL, without any loss in accuracy or the possibility of finding an optimal solution, at a cost of a much increased state space, and accompanying measures like need for generalization, shaping rewards, longer learning times, and so on. Similar things can be said about the other two frameworks treated in the paper.\n\nThe main weakness of the paper is that it is highly unclear what the contributions are. The paper talks about well-known frameworks, and connects it more or less to RL, but without writing about what are contributions, new insights, and connections to the literature. For RL experts, I think most of it is very intuitive to read, and even interesting in the more general sections 1 and 5, but for me it is unclear how this paper advances the state-of-the-art and understanding of the reward hypothesis (relative to the literature). Furthermore, Sections 3 and 4 are even less worked out than Section 2, and only contain some initial thoughts. The modal RL is only sketched briefly, and does not connect well to the growing literature on combinations of RL and formal verification tools (like PCTL and temporal formalisms). Section 2 should first show the state-of-the-art in MORL, and then do additional things. Overall, all the methods are not illustrated nor motivated well, and also domain descriptions (examples) nor experimental evaluations or illustrations are incorporated. The paper as a whole has interesting bits and fragments, but as a paper, in this time and sub-area, it does not do well as \"a research paper\" since it is too unfocused and to unclear about its achievements.\n\nSome other things:\n- Since the paper is quite unfocused, I feel the related work is too. It is unclear why exactly this set of references is chosen.\n- The preliminaries are ok, and formalisations too, but some \"operations research\" style formalizations are chosen (G,J,..) and it is good to connect (maybe) more literally to Sutton and Barto who have a more AI-oriented flavor of notation.\n- Why not illustrate Sections 3 and 4 more with AI-oriented examples, in well-known domains, or even with some experimental part? This would help a lot in motivating these formalizations. Page 9 says \"we have given many examples\" but I feel this is really missing.\n- The modal setting should be much more connected to the current trend to combine RL with verification tools, and it should get more space (maybe a separate paper) to really explain the setting in full detail.\n- Section 5 should at least discuss in more detail how typically one can still \"compile\" problems to single-scalar problems, with the necessary trade-offs in model size, solution times, and so on.\n- Too much detail is deferred to appendices, especially on page 9. The major part of the story should be in the paper itself though, and appendices should provide some further detail. The balance is off here. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UfTrnKRvEG", "reviewer": "Reviewer_Y3kp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper tries to disprove the reward hypothesis mathematically by showing some classes of tasks cannot be expressed using any scalar Markovian reward function. They showcase a set of multi-objective reward functions, risk averse utility functions that can’t be reduced to an equivalent scalar reward function. They also introduce a new class of RL tasks, namely,  modal tasks where the reward is dependent on the transition function", "summary_of_the_review": "The paper definitely provides more insight into discussing the reward hypothesis and the extent to which it can be flexible but there are other aspects that need to be clarified (mentioned in the strengths and weaknesses section) in order to firmly disprove the reward hypothesis. Even in regards to the modal tasks, additional details are needed to clarify the dependency of the reward function and the transition function. Due to these reasons, I would incline towards not accepting this paper.\n", "strength_and_weaknesses": "Strengths \nThe paper does provide sound proofs that some of the multi objective and risk averse based reward functions cannot be reduced, ceteris paribus, to an equivalent scalar Markovian reward function.\n\nWeaknesses/Questions\n\n1. The paper states that ‘In other words, it is the hypothesis that any natural task can be expressed as a reward signal’. The definition of a natural task can vary significantly. It would also bring up the question of whether the corresponding objective functions are ‘natural’ or if they are part of ‘what we mean by goals and purposes’.\n\n2. I think there should be clarification on why the state space has to be the same between the original and modified MDPs to showcase that the reward hypothesis holds. \n\n3.This also leads to the question of if there are scalar rewards conditioned on the objectives then would that be equivalent to the original MORL or Risk Sensitive RL reward functions or if there are reward function approximators that approximate such equivalent rewards then would the reward hypothesis hold. Could there even be such approximators?\n\n4. Coming to modal reward function, there isn’t a specific example that showcases how the reward function might be dependent on the transition function.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "EZ3biCZpqkl", "reviewer": "Reviewer_p6jG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper investigates tasks in which the \"reward hypothesis\" is not the most appropriate framework. The authors demonstrate three types of objectives: MORL,  risk sensitive RL, and Modal objectives, that cannot mathematically be reduced to a singular MDP formulation.", "summary_of_the_review": "\nThis study can be seen as an extension of the work Abel et al 2021, by providing 3 new and interesting tasks that scalar rewards cannot express. \n\nWith reorganization and rigorous framing, this paper can potentially be an interesting one to the community. ", "strength_and_weaknesses": "The mathematical demonstrations are themselves interesting and curious in their own right. The main conclusions for each of the 3 individual objective functions appear to be justified. \n\nHowever, their main purpose in this paper, as formulated by the authors, is to serve to disprove the \"reward hypothesis\" and this framing is the problematic part. \n\nThe first problem with the framing of in terms of the reward hypothesis is that in Sutton & Barto itself, this statement is explicitly stated to be an informal or guiding idea rather than a solid dictum. The second problem is that the reward hypothesis is broadly about the idea that goals can be formulated as rewards, and is therefore agnostic to the methods used to achieve this control problem or even the formulation of the setting itself (whether MDP or otherwise). Therefore, mathematical proofs about the nonequivalence of MDP RL and the 3 objective functions considered cannot disprove this statement (which itself, was informal to begin with), and framing this as a disproving is flashy but doesn't necessarily contribute to the advancement of this field. \n\nIt is not to say that the paper did not demonstrate some interesting things. Examining expressivity of singular reward functions/MDPs is a cool question, and within this more targetted focus, this paper brings some interesting new demonstrations.\n\nAll in all, the authors should either provide clarifications to rigorously justify their current framing (i.e. disproving) or, they can amend their whole manuscript angle to be closer to what the authors actually demonstrated -- i.e. that these other objective functions are nonexpressible in an (S,A, reward) MDP.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "DzBlBXBZtTH", "reviewer": "Reviewer_UBdX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the ability of Markovian rewards to express tasks in some generalized RL settings, namely multi-objective RL, risk-averse RL, and the so-called modal RL. The tasks are intended as total policy ordering (multi-objective RL, modal RL) or total trajectory ordering (risk-averse RL). The paper provides examples of tasks that cannot be expressed by a Markovian reward, which they claim is a refutation of the reward hypothesis. The paper include several ancillary results, such as providing necessary and sufficient conditions for when a multi-objective RL task can be expressed through a Markovian reward, and a formulation of the modal RL problem, in which the tasks are expressed in modal terms (a notion close to counterfactuals) instead of categorical terms.", "summary_of_the_review": "This paper is an interesting read, and it includes several ancillary results that can have significant value. Nevertheless, I believe that this paper cannot be accepted in its current form, as the presentation is centered on a result that is not novel. I would suggest the authors to reformulate the paper putting less emphasis on the refutation of the reward hypothesis, and more on the actual original contribution. E.g., modal RL seems a very interesting idea to expand, and some interesting ideas about how to approach them are relegated to the Appendix. Also the characterization of the necessary and sufficient conditions for which multi-objective RL cannot be casted as a standard RL problem are interesting, and they could provide a valuable contribution on their own.", "strength_and_weaknesses": "*Strengths*\n- Overall clarity. The paper is well-written and easy to follow;\n- Originality (partial). The paper provides an original formulation of the so-called modal RL problem, which might deserve its own characterization, as well as interesting insights on multi-objective RL formulations, and when those are not harder than standard RL.\n\n*Weaknesses*\n- Novelty. The result that is presented as the major take of the work, i.e., that Markovian rewards cannot express all the possible notion of tasks, is not novel, as it was already substantiated in (Abel et al., 2021);\n- Presentation. The paper includes several potentially interesting results that take a backseat with respect to the (unsurprising) refutation of the reward hypothesis;\n- Motivation. The analysis includes some arbitrary choices that lack a clear motivation, such as total policy ordering as to express the notion of task.\n\n*Main Concerns*\n\n(C1) Presentation. I do not understand the choice of the authors of presenting this paper as a formal refutation of the reward hypothesis. Abel et al. (2021) already demonstrated that some notion of tasks cannot be expressed through a Markovian reward function. Whereas the authors are right to say that their analysis mostly rely on different arguments, the major take is neither surprising or novel.\n\n(C2) Notion of Task. I do not think the reward hypothesis ever mentioned policy ordering in the definition of \"goals and purposes\". One could argue that the actual goal of the learning process is to find an optimal policy, and that the expressivity of the reward should be evaluated in terms of the optimal policies it can induce. Nonetheless, Abel et al. (2021) demonstrated that also this weaker notion of task (which they call set of admissible policies) cannot be always expressed through a Markovian reward. The refutation argument of this paper does not include this result instead.\n\n*Other Comments*\n\n(C3) Generalization to average reward and finite-horizon.\nTo my knowledge, both the results presented in this paper and (Abel et al., 2021) are limited to the discounted RL setting. Do the authors believe that similar results could be generalized to the average reward setting, i.e., infinite horizon but without discounting, and the episodic setting, in which the reward function is often non-stationary?\n\n(C4) Sufficiency of Markovian deterministic policies.\nWhile it is well-known that the class of deterministic Markovian policies are sufficient to optimize any Markovian reward in the discounted setting, it is not clear what policy class we should consider for the presented generalized RL settings (multi-objective, risk-averse, modal RL). Do they also admit an optimal deterministic Markovian policy?\n\n(C5) A \"universal\" problem setting.\nThe paper shows that some notion of tasks cannot be expressed through a Markovian reward function. Do the authors believe it might exist a more general (and tractable) problem setting that include all of the presented notions of task? Perhaps the convex RL formulation (Hazan et al., 2019; Zhang et al., 2020), where the learning objective is expressed as a convex/concave function of the state-action distribution, can be an interesting candidate. Another is the vectorial reward formulation by (Cheung, 2019).\n\n(C6) Modal RL.\nI am not really familiar with the notion of modal tasks, but the modal RL seems an original and interesting formulation to me. Can the authors provide a deeper characterization of this problem formulation? What kind of tasks it can express? E.g., it clearly subsumes standard RL tasks, what about multi-objective tasks or other generalization? Are the three presented problem setting non-overlapping in terms of expressivity?\n\n(C7) Choice of the problem settings.\nThe choice of the problem settings to present in against the reward hypothesis is kind of arbitrary, and it is not clear why they have been preferred over constrained RL, pure exploration (e.g., maximum state entropy), imitation learning (as divergence minimization) or any other generalization.\n\n(C8) Related works.\nI believe that some additional works could be at least mentioned in the paper, such as the convex RL formulation and vectorial reward formulation, which are interesting generalization of the Markovian reward, as well as other papers considering non-Markovian rewards (e.g., through reward machines, for which I am not an expert and I cannot provide valuable references).\n\nConvex RL:\n- Hazan et al., Provably efficient maximum entropy exploration, 2019;\n- Zhang et al., Variational policy gradient method for reinforcement learning with general utilities, 2020;\n- Zahavy et al., Reward is enough for convex MDPs, 2021;\n- Geist et al., Concave utility reinforcement learning: The mean-field game viewpoint, 2022;\n- Mutti et al., Challenging common assumptions in convex reinforcement learning, 2022.\n\nVectorial rewards:\n- Cheung, Exploration-exploitation trade-off in reinforcement learning on online markov decision processes with global concave rewards, 2019;\n- Cheung, Regret minimization for reinforcement learning with vectorial feedback and complex objectives, 2019.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject