On the Expressivity of Markov Reward
Authors: David Abel
Will Dabney
Anna Harutyunyan
Mark K Ho
Michael Littman
Doina Precup
Satinder Singh
Venue: NeurIPS 2021 Oral (2021)
Keywords: Reinforcement Learning
Reward Functions
Reward
Reward Hypothesis
Markov Decision Process

Abstract: Reward is the driving force for reinforcement-learning agents. This paper is dedicated to understanding the expressivity of reward as a way to capture tasks that we would want an agent to perform. We frame this study around three new abstract notions of “task” that might be desirable: (1) a set of acceptable behaviors, (2) a partial ordering over behaviors, or (3) a partial ordering over trajectories. Our main results prove that while reward can express many of these tasks, there exist instances of each task type that no Markov reward function can capture. We then provide a set of polynomial-time algorithms that construct a Markov reward function that allows an agent to optimize tasks of each of these three types, and correctly determine when no such reward function exists. We conclude with an empirical study that corroborates and illustrates our theoretical findings.

On the Expressivity of Markov Reward
David Abel DeepMind dmabel @dweeeldddeemddddcmmmmmm
Will Dabney
Anna Harutyunyan Deep
DeepMind
wdabneyyddeepmind.com
harutyunyann&deepmnndddc
Mark K. Ho
Michael L. Littman
Department of Computer Science
Department of Computer Science
Princeton University
Brown University
mho@princeton. edu
mlittman@cs brown. edu
Doina Precup
Satinder Singh
DeepMind
DeepMind baveja@deepmind. com
doinap@deepmind.com
Abstract
Reward is the driving force for reinforcement-lermingg agents. This paper is dedicated to understanding the expressivity reward as a way to capture tasks that we would want an agent to perform. We frame this study around three new abstract notions of "task" that might be desirable: (I) a set of acceptable behaviors, (2) partial ordering over behaviors, or (3) partial ordering over trajectories. Our main results prove that while reward can express many of these tasks, there exist instances of each task type that Markov reward function then provide a set of polynomial- function that allows agent to optimize tasks of each of these three types, and correctly determine when no such reward function exists. We conclude with an empirical study that corroborates and illustrates our theoretical findings.
capture. We algorithms that construct Markov reward
Introduction
How to algorithms for reinforcement learning (RL) solve problems of relevance in the world? Reward plays a significant role as a general purpose signal: For any desired behavior, task, or other characteristic of agency, there must exist reward signal that can incentivize agent to learn to realize these desires. Indeed, the expressivity of reward is taken as a backdrop assumption that frames RL, sometimes called the reward hypothesis: "...all of what the expected value of the cumulative sum of a received
mean by goals and purposes
can be well thought of as maximization scalar signal (reward)" [53, 29, 6]. In this paper, establish first steps toward systematic study of the reward hypothesis by examining the expressivity of reward as a signal. We proceed three steps.
An Account of "Task". As rewards encode tasks, goals, or desires, we first ask, "what is task?". We frame our study around thought experiment (Figure 1) involving the interactions between a designer, Alice, and learning agent, Bob, drawing inspiration from Ackley and Littman [2], Sorg [50], and Singh al. [46]. In this thought experiment, we draw distinction between how Alice thinks task (TASKQ) Q) and the means by which Alice incentivizes Bob to pursuc this task (EXpREsSION(). This distinction allows to analyze the expressivity of reward latter question, conditioned on how we answer the former. Concretely, we study three answers to the TASKQ in the context of finite Markov Decision Processes (MDPs): A task either (1) set of
answer the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

task space
World
state
action
task
leaxning signal
generator
Bob
Alice
Figure 1: Alice, Bob, and the artifacts of task definition (blue) and task expression (purple).
acceptable behaviors (policies), (2) a partial ordering over behaviors, (3) partial ordering over trajectories. Further detail and motivation for these task types is provided in Section 3, but broadly they can be viewed generalizations of typical notions of task such choice of goal optimal behavior. Given these three answers to the TASKQ, we then examine the exprexsivity of reward.
2. Expressivity of Markov Reward. The core of our study asks whether there tasks Alice would like to convey-as as captured by the answers to the TASKQ-thal admit no characterization in terms of Markov reward function. Our emphasis on Markov reward funetions, as opposed to arbitrary history- computer science, psychology. biology, and economics typically rely on notion of reward numerical proxy for the immediate worth of states of affairs (such as the financial cost of buying solar panel the fitness benefits of a phenotype). Given an appropriate way to describe states of affairs, Markov reward functions can represent immediate worth in an intuitive manner that also allows for reasoning about combinations. sequences, or re-occurrences of such states of affairs. Second, it is not clear that general history-basee rewards are reasonable target for learning as they suffer from the curse of dimensionality in the length of the history. Lastly, Markov reward functions are the standard in RL. A rigorous analysis of which tasks they can and cannot convey may provide guidance into when it is necessary to draw on alternative formulations on Markov rewards, we treat reward function as accurately expressing task just when the value function it induces an environment adheres to the constraints of a given task.
reward functions, is motivated by several factors. First, disciplines such as
problem. Given our focus
3. Main Results. We find that, for all three task types, there are environment-tas pairs for which there is no Markov reward function that realizes the task (Theorem 4)... In light of this finding, we design polynomial-time algorithms that can determine, for any given task and environment, whether a reward function exists in the environment that captures the task (Theorem 4.3). When such reward function does exist, the algorithms also return it. Finally, we conduct simple experiments with these procedures to provide empirical insight into the expressivity of reward (Section 5).
Collectively, our results demonstrate that there are tasks that cannot be expressed by Markov reward in a rigorous sense, but can efficiently construct such reward functions when they do exist (and determine when they do not). We take these findings to shed light on the nature of reward maximization as a principle, and highlight many pathways for further investigation.
2 Background
defines the problem facing an agent that learns to improve its behavior over time by interacting with its environment. We make the typical assumption that the RL problem is well modeled by an agent interacting with a finite Markov Decision Process (MDP), defined by the tuple (S, A, R, T, 7 so). An MDP gives rise deterministic behavioral policies, . S + A, and the value, V= S R. and action-value, Q" S x A + R. functions that measure their quality. We will refer to a Controlled Markov Process (CMP) as an MDP without a reward function, which we denote for environment. We assume that all reward functions are deterministic, and may be a function of either state, state- action pairs, or aatte-action-staee triples, but not history. Henceforth, we simply use "reward function" to refer to a deterministie Markov reward function for brevity, but note that more sophisticated settings beyond MDPs and deterministie Markov reward functions are important directions for future work. For more MDPs RL, see the books by Puterman [41] and Sutton and Barto [54] respectively.

---

2.1 Other Perspectives on Reward
We here briefly summarize relevant literature that provides distinct perspectives on reward.
Two Roles of Reward. As Sorg [50] identifies (Chapter 2), reward can both define the task the agent learns to solve, and define the "bread crumbs" that allow agents to efficiently learn to solve the task. This distinction has been raised elsewhere [2, 46, 47], and is similar to the extrinsic-intrinsic reward divide [45, 66]. Tools such as reward design [34, 51] or reward shaping [36] focus on offering more efficient learning in a variety of environments, so as to avoid issues of sparsity and long-tenm term credit assignment. We concentrate primarily on reward's capacity to express task, and defer learning dynamics to an (important) stage of future work.
Discounts, Expectations, and Rationality. Another important facet of reward is how it is used in producing behavior. The classical view offered by the Bellman equation (and the reward hypothesis) that the quantity of interest to maximize is expected, discounted, cumulative reward. Yet it is possible to disentangle reward from the expectation [5], to attend only to ordinal [60] or maximal rewards [26], or to adopt different forms of discounting [61, 11]. In this work, we take the standard view that agents will seek to maximize value for a particular discount factor 7, but recognize that there are interesting directions beyond these commitments, such as inspecting the limits of reward in constrained MDPs as studied by Szepesvári [56]. We also note the particular importance of work by Pitis [40], who examines the relationship between classical decision theory [59] and MDPs by incorporating additional axioms that account for stochastic processes with discounting [24, 35, 48, 49]. Drawing inspiration from Pitis [40] and Sunchag and Hutter [52]. we foresee valuable pathways for future work that further makes contact between RL and various axioms of rationality.
Preferences. In place of numerical rewards, preferences of different kinds may be used to evaluate an agent's ' behaviors, drawing from the literature preference-leannig [25] and ordinal dynamic programming [8, 35, 48). This premise gives rise to preference-bat -basd reinforcement learning (PbRL) in which an agent interacts with a CMP and receives evaluative signals in the form of preferences over states, actions, or trajectories. This kind of feedback inspires and closely parallels the task types we propose in this work. A comprehensive survey of PbRL by Wirth al. [64] identifies critical differences in this setup from traditional RL, categorizes recent algorithmic approaches, and highlights important open questions. Recent work focuses on analysing the sample efficiency of such methods [65, 38] with close connections to learning from human feedback in real time [23, 32, 7].
Teaching and Inverse RL. The inverse RL (IRL) and apprenticeship learning literature examine the problem of learning directly from behavior [37, 1]. The classical problem of IRL. is to identify which reward function (often up to an equivalence class) a given demonstrator is optimizing. We emphasize the relevance of two approaches: First, work by Syed et al. [55]. who first illustrate the applicability of linear programming [22] to apprenticeship learning; and second, work by Amin et al. [4], who examine the repeated form of IRL. The methods of IRL have recently been expanded to include variations of cooperative IRL [14], and assistive learning [43], which offer different perspectives on how to frame interactive learning problems.
Reward Misspecification. Reward is also notoriously hard specify. As pointed out by Littman et al. [30], "putting a meaningful dollar figure on scuffing a wall or dropping clean fork is chal- lenging." Along these lines, Hadfield-Ment designers create reward functions that produce unintended behavior [39]. MacGlashan et al. [33] find that numan--provided rewards tend to depend on a learning agent's 's entire policy, rather than just the current state. Further, work by Haadfeed-Mende et al. [15] and Kumar et al. [27] suggest that there are problems with reward as a learning mechanism due to misspecification and reward tampering [10]. These problems have given rise to approaches to reward learning, in which a reward function is inferred from some evidence such as behavior or comparisons thereof [20].
et al. [16] identify cases which well-intentioned
Other Notions of Task. As a final note, we highlight alternative approaches to task specification. Building on the Free Energy Principle [13, 12], Hafner et al. [17] consider a variety of task types in terms of minimization of distance to desired target distribution [3]. Alternatively, Littman et al. [30] and Li et al. [28] propose variations of linear temporal logic (LTL.) as a mechanism for specifying task to RL agents, with related literature extending LTL to the multi-task [58] and multi-agent
3

---

[18] settings, or using reward machines for capturing task structure [19]. Jothimurugan et al. [21] take similar approach and propose task specification language for RL based on logical formulas that evaluate whether trajectories satisfy the task, similar in spirit to the logical task compositions framework developed by Tasse et al. [57]. Many of these notions of task are more general than those we consider. A natural direction for future work broadens our analysis to include these kinds of task.
3 An Account of Reward's Expressivity: The TASKQ and EXPRESSIONQ
Consider an onlooker, Alice, and an earnest learning agent, Bob, engaged in the interaction pictured in Figure 1. Suppose that Alice has particular task in mind that she would like Bob to learn solve, and that Alice constructs a reward function to incentivize Bob to pursue this task. Here, Alice is playing the role of "all of what we mean by goals and purposes" for Bob pursue, with Bob playing the role of the standard soward-maximizing RI. agent.
Two Questions About Task. To give us leverage to study the expressivity of reward, it is useful to draw distinction between two stages of this process: 1) Alice thinks of a task that she would like Bob to learn to solve, and 2) Alice creates a reward function (and perhaps chooses 7) that conveys the chosen task to Bob. We inspect these two separately, framed by the following two questions. The first we call the task-definition question (TASKQ) which asks: What is a task? The second we call the task-exye exss-expression question (EXPRESSIONQ) which asks: Which learning signal can be used as a mechanism for expressing any task to Bob?
Reward Answers The EXPRESSIONQ. We suggest that it may be useful to treat reward as an answer the EXPRESSIONQ rather than the TASKQ On this view, reward is treated as an expressive language for incentivizing reward- -araaddmaximizzngg agents: Alice may attempt to translate any task into a reward function that incentivizes Bob pursue the task, no matter which environment Bob inhabits, which task Alice has chosen, or how she has represented the task to herself. Indeed, it might be the case that Alice's knowledge of the task far exceeds Bob's representational or perceptual capacity. Alice may know every detail of the environment and define the task based on this holistic vantage, while Bob must learn to solve the task through interaction alone, relying only on a restricted class of functions for modeling and decision making.
Under this view, we assess the expressivity of reward an answer to the EXPRESSIONQ conditioned on how we answer the TASKQ. For example, if the TASKQ is answered in terms of natural language descriptions of desired states of affairs, then reward may fail to convey the chosen task due to the apparent mismatch in abstraction between natural language and reward (though some work has studied such a proposal [31, 62).
3.1 Answers to the TASKQ: What is a Task?
In RL, tasks are often associated with a choice of goal, reward function (R), reward-discount pair
(R, 7), or perhaps choice of optimal policy (alongside those task types surveyed previously, such as LTL). However, it is unclear whether these constructs capture the entirety of what we mean by "task".
For example, consider the Russell and Norvig [42] grid world: A 4x3 grid with one wall, one terminal fire state, and one terminal goal state (pictured with a particular reward function Figure 4a). such an environment, how might we think about tasks? A standard view is that the task is to reach the goal as quickly as possible. This account, however, fails to distinguish between the non non-optimal behaviors, such the costly behavior of the agent moving directly into the fire and the neutral behavior of the agent spending its existence in the start state. Indeed, characterizing a task in terms of choice of n or goal fails to capture these distinctions. Our view is that suitably rich account of task should allow for the characterization of this sort of preference, offering the flexibility to scale from specifying only the desirable behavior (or outcomes) an arbitrary ordering over behaviors (or outcomes).
In light of these considerations, we propose three answers to the TASKQ that can convey general preferences over behavior or outcome: 1) A set of acceptable policies, 2) A partial ordering over policies, or 3) A partial ordering over trajectories. We adopt these three as they can capture many kinds of task while also allowing great deal of flexibility in the level of detail of the specification.

---

Name
Notation
Generalizes
Constraints Induced by g
equal: V V* (s0) Vaa (so() Elo
SOAP
llg
task-as->*
range: (50 > (s)) Vn Elll
PO
Ln
SOAP
( + T2)
Ln = v*i @ V
TO
Lr,N
fask-as-goal
(T1 + T2) E Lr,N = G(Ti: so) + ((T2:5))
Table 1: A summary of the three proposed task types. We further list the constraints that determine whether a reward function realizes each task type in an MDP, where we take @ to be one of '<, '>' or "0=,,an and G is the discounted return of the trajectory.
3.2 SOAPs, POs, and TOs
(SOAP) Set Of Acceptable Policies. A classical view of the equivalence of two reward functions is based on the optimal policies they induce. For instance, Ng et al. [36] develop potential-based reward shaping by inspecting which shaped reward signals will ensure that the optimal policy is unchanged. Extrapolating. it is natural to say that for any environment E, two reward functions are equivalent if the optimal policies they induce in E are the same. In this way, a task is viewed a choice of optimal policy. As discussed in the grid world example above, this notion of task fails to allow for the specification of the quality of other behaviors. For this reason, we generalize set of acceptable policies, defined follows.
ausk-ss-ppimmll-polie
Definition 3.1. A set of acceptable policies (SOAP) is non-empty subset the deterministic policies, 1lg S II, with 11 the set of all deterministic mappings from S to A for given E.
With one task type defined, it is important to address what it means for a reward function to properly realize, express, or capture task in a given environment. We offer the following account.
Definition 3.2. A reward function is said to realize a task T in environment E just when the start-state value (or return) induced by the reward function function exactly adheres to the constraints of T.
Precise conditions for the realization of each task type are provided alongside each task definition, with summary presented in column four of Table 1.
For SOAPs, we take the start-state value V (so) to be the mechanism by which a reward function realizes a SOAP. That is, for a given E and HIg, a reward function R is said to realize the Ilg in E when the start-state value function optimal for all good policies, and strictly higher than the start-state value of all other policies. It is clear that SOAP strictly generalizes a task in terms of choice of optimal policy, as captured by the SOAP IGG = {T*).
We note that there are two natural ways for a reward function to realize SOAP: First, each na E lgg has optimal start-state value and all other policies are sub-optimal. We call this type equal-SOAP, or just SOAP for brevity. Alternatively, we might only require that the acceptable policies are each near-optimal, but are allowed to differ in start-state value so long as they are all better than every bad policy E II That is, in this second kind, there exists an 2 0 such that every Fg E II is e-optimal start-state value, (*ppp) V (sp) S e, while all other policies are worse. We call this second realization condition SOnP We note that the range realization generalizes the equal one: Every equal-SOAP is a range-SOAP (by letting c = 0). However, there exist range-SOAL that are expressible by Markov rewards that are not realizable as an equal-SOAP. We illustrate this fact with the following proposition. All proofs are presented in Appendix B.
Proposition 3.1. There exists a CMP, E, and choice of IlG such that lg can be realized under the range-SOAP criterion, but cannot be realized under the equal-SOAP criterion.
One such CMP is pictured Figure 2b. Consider the SOAP II = { T12, T21): Under the equal- SOAP criterion, if each these three policies are made optimal, any reward function will also make T22 (the only bad policy) optimal as well. In contrast, for the range criterion, we can choose reward function that assigns lower rewards to 02 than dn in both states. In general, we take the equal-SOAP realization as canonical, as it is naturally subsumed by next task type.
5

---

(PO) Partial Ordering on Policies. Next, we suppose that Alice chooses partial ordering on the deterministic policy space. That is. Alice might identify some great policies, some good, and some bad policies to strictly avoid, and remain indifferent to the rest. POs strictly generalize equal SOAPs, as any such SOAP a special choice of PO with only two equívalence classes. We offer the following definition of a PO.
Definition 3.3. A policy order (PO) of the deterministic policies is a partial order, denoted Ln-
As with SOAPs, take the start-state value (su) induced by reward function R. as the mech- anism by which policies are ordered. That is, given E and LuI we say that a reward function R realizes Ln in E' if and only if the resulting MDP, M (E, R), produces start-state value function that orders IT according to LnI.
(TO) Partial Ordering on Trajectories. A natural generalization of goal specification enriches a notion of task to include the details of how a goal is satisfied that is, for Alice to relay some preference over trajectory space [63], is done in preference based RL [64]. Concretely, we suppose Alice specifies a partial ordering on length N trajectories of (s, a) pairs, defined as follows.
Definition 3.4. A trajectory ordering (TO) of length N N is a partial ordering Ir,N,, with each trajectory consisting of N state-action pairs, {(so, ao), ..... (ax (N-1), with so the start state.
As with PO, we say that reward function realizes a trajectory ordering Lr,N if the ordering determined by each trajectory's s cumulative discounted N N-step return from 80, denoted G(T; 80). matches that of the given L, We note that trajectory orderings can generalize goal-based tasks at the expense of larger specification. For instance, TO can convey the task, "Safely reach the goal in less than thirty steps, or just get the subgoal in less than twenty steps."
Recap. We propose to assess the expressivity of reward by first answering the TASKQ in terms of SOAPs, POs, TOs, as summarized by Table 1. We say that a task I is realized in an environment E under reward function Rt if the start-state value function (or return) produced by R imposes the constraints specified by T, and are interested in whether reward can always realize given task in any choice of E. We make a number of assumptions along the way, including: (1) Reward functions are Markov and deterministic.
(2) Policies of interest are deterministic, (3) The environment is finite CMP, (4) y is part of the environment, (5) We ignore reward's role in shaping the learning process, (6) Start-state value or return is the appropriate mechanism to determine if reward function realizes a given task. Relaxation of these assumptions is critical direction for future work.
4 Analysis: The Expressivity of Markov Reward
With our definitions and objectives in place, we now present our main results.
4.1
Express SOAPs, POs, and TOs
We first ask whether reward can always realize a given SOAP, PO, or TO, for an arbitrary E. Our first result states that the answer is "no"- are tasks that cannot be realized by any reward function.
Theorem 4.1. For each of SOAP, PO, and TO, there exist (E, I) pairs for which no Markow reward function realizes T in E.
Thus, reward is incapable of capturing certain tasks. What tasks are they, precisely? Intuitively, inexpressible tasks involve policies or trajectories that must be correlated in value in an MDP. That is, if two policies are nearly identical in behavior, is unlikely that reward can capture the PO that places them at opposite ends of the ordering. A simple example is the "always move the same direction" task in grid world, with state defined as an (z, y) pair. The SOAP He = ( TT, T,, } conveys this task, but no Markov reward function can make these policies strictly higher in value than all others.
Example: Inexpressible SOAPs. Observe the two CMPs pictured in Figure 2, depicting two kinds of inexpressible SOAPs. On the left, we consider the SOAP UG = { J. containing only the policy that executes d2 in the left state (so), and a in the right (81). This SOAP is inexpressible through reward, but only because reward cannot distinguish the start-state value of т2 and 722 since the policies differ only in an unreachable state. This is reminiscent of Axiom 5 from Pitis [40], which

---

50
31
50
(a) Steady State Case
(b) Entailment Case
Figure 2: Two CMPs in which there is SOAP that is not expressible under any Markov reward function. On the left, Ilg = { } is not realizable, as T21 can not be made better than 722 because is never reached. On the right, the XOR-like-SOAR Il. {TT2 721) is not realizable: To make these two policies optimal, entailed that T22 and W11 must optimal, too.
explicitly excludes preferences of this sort. On the right, we find a more interesting case: The chosen SOAP is similar to the XOR function, II. 112 T2 Here, the task requires that the agent choose each action in exactly one state. However, there cannot exist a reward function that makes only these policies optimal, as by consequence, both policies 11 and T22 must be optimal well.
Next, we show that Theorem 4.1 not limited to a particular choice of transition function or 7/- Proposition 4.2. There exist choices of E-T (S,A, 8o) or E = (S 8o)), together with a task T, such that there no (T, R) pair that realizes in E.. or (R,7) in E...y
This result suggests that the scope of Theorem 4.1 is actually quite broad-even if the transition function or y taken as part of the reward specification, there tasks that cannot be expressed. We suspect there are ways to give a precise characterization of all inexpressible tasks from an axiomatic perspective, which we hope to study in future work.
4.2 Constructive Algorithms: Task to Reward
We now analyze how to determine whether an appropriate reward function can be constructed for any (E, T) pair. We pose general form of the reward-design problem [34, 51, 9] as follows.
Definition 4.1. The REWARDDESIGN problem is: Given E (S, T, 7, so), and a T, output reward function Ratice that ensures T is realized in M (E, Ralice).
Indeed, for all three task types, there is an efficient algorithm for solving the reward-design problem. Theorem 4.3. The REWARDDESIGN problem can be solved in polynomial time, for any finite E, and any T, so long as reward functions with infinitely many outputs are considered.
Therefore, for any choice finite CMP, E, and a SOAP, PO, or TO, we can find a reward function that perfectly realizes the task in the given environment, if such reward function exists. Each of the three algorithms are based on forming a linear program that matches the constraints the given task type, which is why reward functions with infinitely many outputs required. Pseudo-code for SOAP-based reward design is presented in Algorithm 1. Intuitively, the algorithms compute the discounted expected-state visitation distribution for collection of policies; in the of SOAP, for instance, these policies include 1g and what we call the "fringe", the set of policies that differ from T E Il by exactly one action. Then, we use these distributions describe linear inequality constraints ensuring that the start-state value of the good policies are better than those of the fringe.
As highlighted by Theorem 4.1 there SOAPs, POs, and TOs that important to determine how the algorithms mentioned in Theorem 4.3 will handle such cases. Our next corollary illustrates that the desirable outcome is achieved: For any E and T, the algorithms will output a reward function that realizes T in F,, or output '1' when no such function exists.
realizable. Thus, it is
Corollary 4.4. For any task T and environment E, deciding whether T is expressible in E is solvable in polynomial time.
Together, Theorem 4.1 and Theorem 4.3 constitute our main results: There are environment-tas pairs in which Markov reward cannot express the chosen task for each of SOAPs, POs, and TOs. However, there are efficient algorithms for deciding whether task is expressible, and for constructing the realizing reward function when it exists. We will study the use of one of these algorithms in Section 5, but first attend to other aspects of reward's expressivity.
7

---

Algorithm SOAP Reward Design
INPUT: E = (S, 50), llc. OUTPUT: R. or L.
1: Hinge = compute_fringe(lg,
2: for gg 1gg do
> Compute state-visitation distributions.
3: Pa.i =
4: for T E Irringe do
5:
Pf. compute_exp__tte wipiittttt
6: Ceg =
D Make Equality Constraints.
7: for gg G do
8:
adg X = -9,,(800 X)
9: Cinog =(
Make Inequality Constraints.
10: for TJJ E [Ifringe do
11:
Cinoq
X +e S Po.0(50) -X)
Roat; foat siinerrprrgraamingg.............
max e, constraints Cinegy Cey)
Solve L..
13: if Fout > 0 then
Check if successful.
return Rout
14: else
return 1
4.3
Other Aspects of Reward's Expressivity
We next briefly summarize other considerations about the expressivity of reward. As noted, The- orem 4.3 requires the use of reward function that can produce infinitely many outputs. Our next result proves this requirement strict for efficient reward design.
Theorem 4.5. A variant of the REWARDDESIGN problem with finite reward oulputs is NP-hard.
We provide further details about the precise problem studied in Appendix Beyond reward functions with finitely- umitely-many outputs, we are also interested in extensions of our results to multiple envirouments. We next present positive result indicating our algorithms can extend to the case where Alice would like to design reward function for single task across multiple environments.
Proposition 4.6. For any SOAP, PO, or TO, given a finite set of CMPs, E = {Ei,..., ,,,,, with shared state-action space, there exists polynomial time algorithm that oulputs one reward function that realizes the task (when possible) in all CMPs E.
A natural follow up question to the above result asks whether task realization is closed under a set of CMPs. Our next result answers this question in the negative.
Theorem 4.7. Task realization is not closed under sets of CMPs with shared state-action space. That is, there exist choices of I and & = (Ei,..., En} such that T is realizable in each E, independently, but there is not single reward function that realizes I in all E, E & simultaneously.
Intuitively, this shows that Alice must know precisely which environment Bob will inhabit if she is to design appropriate reward function. Otherwise, her uncertainty over E may prevent her from designing a realizing reward function. We foresee iterative extensions of our algorithms in which Alice and Bob can react to one another, drawing inspiration from repeated IRI. by Amin et al. [4].
5 Experiments
We next conduct experiments to shed further light on the findings our analysis. Our focus is on SOAPs, though we anticipate the insights extend to POs and TOs as well with little complication. In the first experiment, we study the fraction of SOAPs that are expressible in small CMPs as we vary aspects of the environment task (Figure 3). In the second, we use one algorithm from Theorem 4.3

---

Estiaate of Expresdble S0AFs Num Actions
Extimate of Express ble SDVPs ve. Rumm States
Extimate of Expeescb SCAPs Vs.
66-
022
Mar, Actana
Rum Matte
(a) Vary Num. Actions
(b) Vary Num. States
Vary Y
Extressilee
Estimate Expresiible vs. Extropy (s.
Estimate Expressblle SOAPS Variety
8.
22
68
34
64-
60
03 02 05
Dibray a
(d) Vary SOAP Size
(e) Vary Entropy of T
(f) Vary the Spread of TTG
Figure 3: The approximate fraction of SOAPs that are expressible by reward in CMPs with a handful of states and actions, with 95% confidence intervals. In each plot, we vary different parameter of the environment or task illustrate how this change impacts the expressivity of reward, showing both equal (color) and range (grey) realization of SOAP.
to design a reward function, and contrast learning curves under SOAP SOAP-designed reward function compared to standard rewards. Full details about the experiments are found Appendix
SOAP Expressivity. First, we estimate the fraction of SOAPs that expressible in small envi- ronments, For each data point, we sample 200 random SOAPs and run Algorithm I described by Theorem 4.3 to determine whether each SOAP realizable in the given CMP. We ask this question for both the equal (color) variant of SOAP realization and the range (grey) variant. We inspect SOAP expressivity as we vary six different characteristics of E' or II: The number of actions, the number of states, the discount the number of good policies in each SOAP, the Shannon entropy of T at each (s, a) pair, and the "spread" of each SOAP. The spread approximates average edit distance among policies in Tīg determined by randomly permuting actions of a reference policy by a coin weighted according to the value on the x-axis. We use the same set of CMPs for each environment up to any deviations explicitly made by the varied parameter (such as y entropy). Unless otherwise stated, each CMP has four states and three actions, with fixed but randomly chosen transition function.
Results are presented in Figure 3. We find that our theory is borne out in number of ways. First, as Theorem 4.1 suggests, we find SOAP expressivity is strictly less than one nearly all cases. This is evidence that inexpressible tasks are not only found in manufactured corner cases, but rather that expressivity is a spectrum. We further observe-as predicted by Proposition 3.1-clear separation between the expressivity of range-SOAP (grey) vs. equal-SOAP (color); there many cases where we can find reward function that makes the good policies near optimal and better than the bad, but cannot make those good policies all exactly optimal. Additionally, several trends emerge as we vary the parameter of environment or task, though we note that such trends are likely specific to the choice of CMP and may not hold in general. Perhaps the most striking trend is in Figure 3f, which shows a decrease in expressivity as the SOAPs become more spread out. This quite sensible: more spread out SOAP is likely to lead to more entailments of the kind discussed in Figure 2b.
Learning with SOAP-designed Rewards. Next, we contrast the learning performance of Q- learning under a COAP-designes reward function (visualized in Figure 4a) with that of the regular goal-based reward in the Russell and Norvig [42] grid world. In this domain, there is 0.35 slip probability such that, on a 'slip' event, the agent randomly applies one of the two orthogonal action effects. The regular goal-based reward function provides +1 when the agent enters the terminal flag cell, and -1 when the agent enters the terminal fire cell. The bottom left state is the start-state, and the black cell is an impassable wall.

---

31
Learning with SOAP Reward Functions
0.8
lle
551(a)
32
35
22
Fracton
SOAP Roward Puncttion
Regular Reward Funchion
0.0
0
50
100
150
200
250
Epeedes
(a) Grid World SOAP Reward
(b) Grid World Learning
Figure 4: A SOAP-designed reward function (left) and the resulting learning curves (right) for Q- learning compared to the traditional reward function for the Russell and Norvig [42] grid world. Each series presents average performance over 50 runs of the experiment with 95% confidence intervals.
Results are presented in Figure On the right, we present a particular kind of learning curve contrasting the performance of Q-learning with the SOAP reward (blue) and regular reward (green). The y-axis measures, the end of each episode, the average (inverse) minimum edit distance between Q-learning's s greedy policy and any policy in the SOAP. Thus, when the series reaches 1.0, Q-learning's greedy policy is identical to one of the two SOAP policies. We first find that Q-learning is able to quickly learn Rg TāG under the designed reward function. We further observe that the typical reward does not induce a perfect match in policy-at at convergence, the green curve hovers slightly below the blue, indicating that the default reward function is incentivizing different policies to be optimal. This is entirely sensible, as the two SOAP policies are extremely cautious around the fire; they choose the orthogonal (and thus, safe) action in fire-ad adjaeett states, relying slip probability to progress. Lastly, as expected given the amount of knowledge contained in the SOAP, the SOAP reward function allows Q-learning to rapidly identify good policy compared to the typical reward.
6 Conclusion
We have here investigated the expressivity of Markov reward, framed around three new accounts of task. Our main results show that there exist choices of task and environment in which Markov reward cannot express the chosen task, but there are efficient algorithms that decide whether a task is expressible and construct reward function that captures the task when such function exists. We conclude with an empirical examination our analysis, corroborating the findings our theory. We take these to be first steps toward understanding the full scope of the reward hypothesis.
There are many routes forward. key direction moves beyond the task types we study here, and relaxes our core assumptions- the environment might not be finite CMP, Alice may not know the environment precisely, reward may be function of history, or Alice may not know how Bob represents state. Along similar lines, critical direction incorporates how reward impacts Bob's s learning dynamics rather than start-state value. Further, we note the potential relevance to the recent reward-is-enond hypothesis proposed by Silver et al. [44]; we foresee pathways to extend our analysis to examine this newer hypothesis, too. For instance, in future work, is important to assess whether reward is capable of inducing the right kinds of attributes of cognition, not just behavior.
Acknowledgments and Disclosure of Funding
The authors would like to thank André Barreto, Diana Borsa, Michael Bowling, Wilka Carvalho, Brian Christian, Jess Hamrick, Steven Hansen, Zac Kenton, Ramana Kumar, Katrina McKinney, Rémi Munos, Matt Overlan, Hado van Hasselt, and Ben Van Roy for helpful discussions. We would also like to thank the anonymous reviewers for their thoughtful feedback, and Brendan O' O'Donoghue for catching a typo the appendix. Michael Littman was supported in part by funding from DARPA L2M, ONR MURI, NSF FMitF, and NSF RI.
10

---

References
[1] Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the International Conference Machine learning, 2004.
[2] David Ackley and Michael L. Littman. Interactions between learning and evolution. Artificial Life I1, 1992.
[3] Sundararaman Akshay, Nathalie Bertrand, Serge Haddad, and Loic Helouet. The steady-state control problem for Markov decision processes. In Proceedings of the International Conference on Quantitative Evaluation of Systems, 2013.
[4] Kareem Amin, Nan Jiang, and Satinder Singh. Repeated inverse reinforcement learning. In Advances in Neural Information Processing Systems, 2017.
[5] Mare G. Bellemare, Will Dabney, and Rémi Munos. distributional perspective on rein- forcement learning. In Proceedings of the International Conference on Machine Learning. 2017.
[6] Brian Christian, The Alignment Problem: Machine Learning and Human Values, pages 130-131. Atlantic Books, 2021.
[7] Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, 2017.
[8] Gerard Debreu. Representation of preference ordering by numerical function. Decision Processes, 3:159-165, 1954.
[9] Daniel Dewey. Reinforcement learning and the reward engineering principle. In Proceedings of the AAAI Spring Symposium Series, 2014.
[10] Tom Everitt, Victoria Krakovna, Laurent Orseau, Marcus Hutter, and Shane Legg. Reinforce- ment learning with corrupted reward channel. In Proceedings of the International Joint Conference on Artificial Intelligence, 2017.
[11] William Fedus, Carles Gelada, Yoshua Bengio, Marc G. Bellemare, and Hugo Larochelle. Hyperbolic discounting and learning over multiple horizons. arXiv preprint arXiv: 068655 2019.
[12] Karl J. Friston. The free-energy principle: unified brain theory? Nature reviews neuroscience, 11(2):127-138, 2010.
[13] Karl J. Friston, Jean Daunizeau, and Stefan J. Kiebel. Reinforcement learning or active inference? PloS One, 4(7))e6421 2009.
[14] Dylan HadfieldMMenell, Anca Dragan, Pieter Abbeel, and Stuart Russell. Cooperative inverse reinforcement learning. In Advances in Neural Information Processing Systems, 2016.
[15] Dylan Hadfield-Menele Anca Dragan, Pieter Abbeel, and Stuart Russell. The off-switch game. In Proceedings of the International Joint Conference on Artificial Intelligence, 2017.
[16] Dylan Hadfield-Menell, Smitha Milli, Pieter Abbeel, Stuart Russell, and Anca Dragan. Inverse reward design. In Advances in Neural Information Processing Systems, 2017.
[17] Danijar Hafner, Pedro A. Ortega, Jimmy Ba, Thomas Parr, Karl Friston, and Nicolas Heess. Action and perception as divergence minimization. arXiv preprint arXiv:2009.011 01799, 2020.
[18] Lewis Hammond, Alessandro Abate, Julian Gutierrez, and Michael Wooldridge. Multi-agent reinforcement learning with temporal logic specifications. Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2021.
[19] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for legh task specification and decomposition in reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2018.
11

---

[20] Hong Jun Jeon, Smitha Milli, and Anca Dragan.
(implicit) choice: A unifying
formalism for reward learning. Advances in Neural Information Processing Systems, 2020.
[21] Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. In Advances in Neural Information Processing Systems, 2020.
[22] Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the Annual ACM Symposium on Theory of Computing, 1984.
[23] W. Bradley Knox and Peter Stone. Interactively shaping agents via human reinforcement: The TAMER framework. In Proceedings of the International Conference on Knowledge Capture, 2009.
[24] Tjalling C. Koopmans. Stationary ordinal utility and impatience. Econometrica: Journal of the Econometric Society, pages 287-309, 1960.
[25] David Kreps. Notes on the Theory of Choice. Westview Press, 1988.
[26] Sai Krishna Gottipati, Yashaswi Pathak, Rohan Nuttall, Raviteja Chunduru, Ahmed Touati, Sriram Ganapathi Subramanian, Matthew Taylor, and Sarath Chandar. Maximum reward formulation in reinforcement learning. In NeurIPS Workshop Deep Reinforcement Learning, 2020.
[27] Ramana Kumar, Jonathan Uesato, Richard Ngo, Tom Everitt, Victoria Krakovna, and Shane Legg. REALab: An embedded perspective on tampering. arXiv preprint M.Kiv:0011.08822 2020.
(28) Xiao Li, Cristian-loan Vasile, and Calin Belta. Reinforcement learning with temporal logic rewards. In Proceedings of the International Conference on Intelligent Robots and Systems, 2017.
[29] Michael L. Littman. The reward hypothesis, 2017. URL https:// coursera. the- reward- mi
[30] Michael L.. Littman, Ufuk Topcu, Jie Fu, Charles Isbell, Min Wen, and James MacGlashan. cattrrommenn-iddeeeeeeeee task specifications via GLTL. arXiv preprint /0:4.:/7740044 2017.
[31] James MacGlashan, Monica Babes-Vroman, Marie desJardins, Michael Littman, Smaranda Muresan, Shawn Squire, Stefanie Tellex, Dilip Arumugam, and Lei Yang. Grounding English commands reward functions. Proceedings of Roboties: Science and Systems, 2015.
[32] James MacGlashan, Michael L.. Littman, David L. Roberts, Robert Loftin, Bei Peng, and Matthew E. Taylor. Convergent actor critic by humans. In Proceedings of the International Conference on Intelligent Robots and Systems, 2016.
[33] James MacGlashan, Mark K. Ho, Robert Loftin, Bei Peng. Guan Wang, David L. Roberts, Matthew E. Taylor, and Michael L. Littman. Interactive learning from policy-dependent human feedback. In Proceedings of the International Conference Machine Learning. PMLR, 2017.
[34] Maja Mataric. Reward functions for accelerated learning. In Proceedings of the International Conference on Machine Learning. 1994.
[35] L. G. Mitten. Preference order dynamic programming. Management Science, 21(1):43-46. 1974.
[36] Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transforma- tions: Theory and application to reward shaping. In Proceedings of the International Conference on Machine Learning, 1999.
[37] Andrew Ng, Stuart Russell, et Algorithms for inverse reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2000.
12

---

[38] Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference- baseed reinforcement learning. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2020.
[39] Pedro A. Ortega, Vishal Maini, and the DeepMind Safety Team. Build- ing safe artificial intelligence: specification, robustness, and assur- ance, 2018.
URL
building-sane
[40] Silviu Pitis. Rethinking the discount factor in reinforcement learning: A decision theoretic approach. In Proceedings of the AAAI Conference Artificial Intelligence, 2019.
[41] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
[42] Stuart J. Russell and Peter Norvig. Artificial Intelligence: Modern Approach. Prentice-Hall, Englewood Cliffs, NJ, 1994. ISBN 0-13-103805-2
[43] Rohin Shah, Pedro Freire, Neel Alex, Rachel Freedman, Dmitrii Krasheninnikov, Lawrence Chan, Michael D. Dennis, Pieter Abbeel, Anca Dragan, and Stuart Russell. Benefits of assistance over reward learning, 2021. URL
www.ppreereeeeeeeoooreiieeeeeeee net/formm?iddDF
JBB
[44] David Silver, Satinder Singh, Doina Precup, and Richard S. Sutton. Reward is enough. Artificial Intelligence, page 103535, 2021.
[45] Satinder Singh, Andrew G. Barto, and Nuttapong Chentanez. Intrinsically motivated rein- forcement learning. Technical report, University of Massachusetts Amherst Department of Computer Science, 2005.
[46] Satinder Singh, Richard I. Lewis, and Andrew G Barto. Where do rewards come from? In Proceedings of the Annual Conference of the Cognitive Science Society, 2009.
[47] Satinder Singh, Richard L. Lewis, Jonathan Sorg, Andrew G. Barto, and Akram Helou. On sep- arating agent designer goals from agent goals: Breaking the preferences-paramettrss confound, 2010.
[48] Matthew J. Sobel. Ordinal dynamic programming. Management science, 21(9):667-775, 1975.
[49] Matthew J. Sobel. Discounting axioms imply risk neutrality. Annals of Operations Research, 208(1):417-432, 2013.
[50] Jonathan Sorg. The Optimal Reward Problem: Designing Effective Reward for Bounded Agents. PhD thesis, University of Michigan, 2011.
[51] Jonathan Sorg, Richard L. Lewis, and Satinder Singh. Reward design via online gradient ascent. Advances in Neural Information Processing Systems, 2010.
[52] Peter Sunehag and Marcus Hutter. Axioms for rational reinforcement learning. In Proceedings of the International Conference on Algorithmic Learning Theory, 2011.
[53] Richard S. Sutton. The reward hypothesis, 2004, URL http:// htttp://incoppeeteee /tt.c/ompleeeedaas.... net./ rlai. . cs. www.erta. ca/RLAAI/eeee /LAAA///eerrardropooeeeeeee html.. .hmm..
[54] Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
[55] Umar Syed, Michael Bowling, and Robert E. Schapire. Apprenticeship learning using linear programming. In Proceedings of the International Conference on Machine Learning, 2008
[56] Csaba Szepesvári. Constrained MDPs and the reward hypothesis, 2020. URL http:// readingsml wwwgspot.comm/00000.. wwwta///noonntononnniiieiaaeaaai ands-anddrewwrdd wew.-reewwadddhheesitete html.
[57] Geraud Nangue Tasse, Steven James, and Benjamin Rosman. A Boolean task algebra for reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
13

---

[58] Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcllraith. Teaching multiple tasks to an RL agent using LTL. In Proceedings of the International Conference on Autonomous Agents and Mulliagent Systems, 2018
[59] John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Prince- ton University Press, 1953.
[60] Paul Weng. Markov decision processes with ordinal rewards: Reference point- preferences. In Proceedings of the International Conference Automated Planning and Scheduling, 2011.
[61] Martha White. Unifying task specification in reinforcement learning. Proceedings of the International Conference on Machine Learning, 2017.
[62] Edward C. Williams, Nakul Gopalan, Mine Rhee, and Stefanie Tellex. Learning to parse natural language to grounded reward functions with weak supervision. In Proceedings of the International Conference on Robotics and Automation, 2018.
[63] Aaron Wilson, Alan Fern, and Prasad Tadepalli, A Bayesian approach for policy learning from trajectory preference queries. Advances in Neural Information Processing Systems, 2012.
[64] Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference-based reinforcement learning methods. The Journal of Machine Learning Research, (8(1):4945-4990 2017.
[65] Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33, 2020.
[66] Zeyu Zheng, Junhyuk Oh, Matteo Hessel, Zhongwen Xu, Manuel Kroiss, Hado van Hasselt, David Silver, and Satinder Singh. What can learned intrinsic rewards capture? In Proceedings of the International Conference Machine Learning, 2020.
14


Reviews:
[{"review_id": "qzOhZTazjd", "reviewer": "Reviewer_Qqv1", "summary": "This paper studies the ability of Markovian reward functions to represent tasks defined as a set of acceptable policies, partial ordering over policies, partial ordering over trajectories. It first provides a negative result showing that some tasks cannot be specified through a Markovian reward in some environments. Then, it designs a set of linear programs to simultaneously check if a specific task can be encoded into a Markovian reward and to compute such reward. The paper includes an empirical evaluation in a simple domain.", "questions": "", "limitations": "", "rating": 8, "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": "Post-rebuttal\n\nHaving read the rebuttal and other reviews, I am updating my evaluation from 7 to 8.\n\n---\n\nThis work is very interesting, it tackles a relevant question on the expressive power of Markovian rewards with clarity and completeness. The main results on the limitation of Markovian rewards fit nicely with the findings of recent works (e.g., Silver et al., Reward is enough, 2021), which conjecture that non-Markovianity is crucial for the expressivity of rewards. The contributions on reward design, binary rewards, and multiple environments look solid and valuable as well, whereas the proofs are carried out with novel arguments.\nI do not have any major concern about this paper, and I suggest accepting it.\nI provide below some detailed comments.\n\nDETAILED COMMENTS\n\n- I think that the main limitation of this work lies in the answers of the task-definition question (TaskQ, or \"What is a task?\"), which are somewhat arbitrary. However, the selected task specifications are reasonable, and they are general enough to cover a large portion (if not all) of the objectives that are considered in the RL literature.\n\n- The reward design methods seek for the valid reward function that maximizes epsilon, which takes slightly different meaning in the three formulations, but always acts as a slack variable on the constraints satisfaction.\nCan the authors comment on why this specification-robust reward should be preferable? Would it be fundamentally easier to solve the problem for any reward that satisfies the constraints?\n\n- From the informal definition of task provided between lines 162-165 arises quite naturally the dueling cost-minimization and goal-reaching objectives of the stochastic shortest path (SSP) problem formulation (Bertsekas and Tsitsiklis, An analysis of stochastic shortest path problems, 1991).\nDo the authors think that the SSP-MDP model could increase the expressivity of Markov reward (cost) w.r.t. the standard MDP model?\n\n- Another interesting direction for future works may study the expressivity of the convex MDP model (see, Zhang et al., Variational policy gradient method for reinforcement learning with general utilities, 2020; Zahavy et al., Reward is enough for convex MDPs, 2021), which allows to specify the objective as any convex function of the expected state visitations rather than a linear combination.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and scope of the work are well-discussed in the text.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Yg_w7jIkg4b", "reviewer": "Reviewer_JLWp", "summary": "The authors consider the problem of expressing a __task__ via a reward function and discount rate. They show that for various formalizations of what a 'task' is, there exist reward functions which cannot express that task. The authors present an efficient algorithm for deciding the expressibility of a task, and for designing such a reward function. They study certain properties of how many tasks are expressible in a given environment, and demonstrate how their approach can accelerate learning. ", "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": "This paper is well-written, addresses an important problem which has not been formally studied to-date, and presents strong technical results. I found it very clear and well-motivated, and expect it to inspire important future work. \n\nHere are some minor comments and questions:\n\n* 63: prefix 'behavioral policies' with 'deterministic'?\n* 70: 'import' -> 'important'\n* 144-147: I found the sentence structure ambiguous; it was unclear what ,\"no matter which...\" was modifying.\n* 177-178: identifying reward functions with shared optimal policy sets seems strong. Perhaps weaken the wording? Also, does reward shaping preserve the return-based ordering over policies - not just the optimal policy sets?\n* I found \"better\" SOAP confusing (195-196). Can you give a more concrete example in camera-ready?\n* What does it mean for a reward-function family to have infinitely many outputs? (I haven't checked appendix, but this should be clear in the main paper)\n\nPOST-REBUTTAL: I thank the authors for their clarifications. My score remains unchanged: clear accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No / N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "Fm7h7sRnU_Y", "reviewer": "Reviewer_8XHY", "summary": "- An exploration and a concrete answer to the question of what is a task, and a critical examination of the reward hypothesis. The approach that this paper proposes is to define a set of all possible tasks in a Controlled Markov Process (CMP), and then ask the question, does there exist a Markov reward that realizes the given task.\n\n- The paper provides answers the above question in the negative through a counter-example. In summary, the authors provide three modes of expressing the task intent: set of accetable policies (SOAP), partial ordering over policies (PO), partial ordering over trajectories (TO). The key result is that there are tasks defined as per all three methods that are not realizable as a Markov reward optimization problem\n\n- The authors finally propose a linear-programming based polynomial time reward design algorithm that generates a Markov reward for the SOAP task specification and returns Null if such a reward does not exist. ", "questions": "", "limitations": "", "rating": 8, "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": "**Overall:** This is an important submission and I strongly recommend acceptance. It tackles a fundamental question about RL, task expressivity and rewards, and proposes an important negative result, namely, even in Markov domains with task specifications defined by a set of acceptable Markov policies, there are certain tasks that cannot be represented through reward maximization paradigm.\n\n**Comments:**\n\n- Difference between 'better' and 'equal-or-better' SOAP definition: I found the definition a bit hard to follow. Specifically, a mathematical definition of  $\\epsilon$-optimal would go a long way in clearing this. I believe this distinction might be important for future analysis, considering the gap between the expressible tasks (Figure 3)\n\n- SOAP definition of tasks: A key drawback of this analysis seems to be the way of defining tasks. The SOAP framework necessitates explicit enumeration of all acceptable policies, and often this set is defined implicitly. Therefore the result that given as task and a CMP environment, reward design is a polynomial-time problem is weakened by the need to explicitly enumerate the acceptable policies. Thus the bottleneck very well might be the problem of enumerating acceptable policies and not that of designing a reward that realizes the task\n\n- Relationship between paradigms of task representation: The authors identify non-Markov tasks as out of the scope of this analysis. But I would be very curious to apply this paradigm to Manna and Pnueli's hierarchy of tasks [1], or even to the POMDP tasks. \n\n- Functional Task descriptions: SOAP, PO and TO are very general descriptions of task definitions, but task descriptions from a functional standpoint represent completion of goals or description of path constraints. While the definitions are general enough to capture all possible tasks, the set of 'practical' tasks might be a smaller subset of these, and Markov rewards might represent a larger fraction of these tasks. \n\nI believe this paper adds valuable insight to the discussion on the reward hypothesis, and warrants acceptance. My comments above are reflections on possible extensions of the work, and not a major criticism of the work as presented. I strongly believe that RL research has not concentrated enough on the source and scope of the reward functions in selecting benchmark domains with well known reward functions, and this represents an important initial step.\n\n\n\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "DofPZ5mkr9E", "reviewer": "Reviewer_jEvD", "summary": "In the reinforcement learning context, the paper proposes three possible definitions for the notion of task, as a set of acceptable policies (SOAP), a partial ordering over policies (PO), or a partial ordering over trajectories (TO). For each definition, the authors show that there exists a task and a controlled Markov process for which there is no reward function that can express that task. Furthermore, the authors notably provide a polynomial algorithm based on linear programming to find such reward function if it exists. Some experiments on random problem instances are also performed to validate the theory.", "questions": "", "limitations": "", "rating": 7, "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": "The paper is well-written and easy to understand. Although I find the theoretical results quite simple, I like very much the whole formalization that provides a clear framework for describing which situations Markov rewards could be sufficient or not to express some tasks. I think this provides a good initial formal answer to the vaguely formulated reward hypothesis. \n\nThe paper could have been strengthened by also considering conditions in SOAP, PO, or TO under which Markov rewards are sufficient. However, I believe this initial work could lead to further work, which could either refine the current results or consider more sophisticated definitions of tasks.\n\nMinor comments:\n- line 70: import\n- line 225: then\n- line 273: I think this sentence doesn't apply to PO.\n- line 274: polices\n- line 342: the there", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussion is needed since this work is more fundamental.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agree that this paper is interesting, relevant, novel, clear, well-written, and technically sound.
I congratulate the authors for their work and I invite them to modify their paper following the reviewers' suggestions.
Decision: Accept (Oral)