Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

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

Minor comments:
- line 70: import
- line 225: then
- line 273: I think this sentence doesn't apply to PO.
- line 274: polices
- line 342: the there
limitations_and_societal_impact: No discussion is needed since this work is more fundamental.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

- 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

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

**Comments:**

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

- 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

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

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

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



 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
main_review: Post-rebuttal

Having read the rebuttal and other reviews, I am updating my evaluation from 7 to 8.

---

This 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.
I do not have any major concern about this paper, and I suggest accepting it.
I provide below some detailed comments.

DETAILED COMMENTS

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

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

- 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).
Do the authors think that the SSP-MDP model could increase the expressivity of Markov reward (cost) w.r.t. the standard MDP model?

- 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.
limitations_and_societal_impact: The limitations and scope of the work are well-discussed in the text.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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. 

Here are some minor comments and questions:

* 63: prefix 'behavioral policies' with 'deterministic'?
* 70: 'import' -> 'important'
* 144-147: I found the sentence structure ambiguous; it was unclear what ,"no matter which..." was modifying.
* 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?
* I found "better" SOAP confusing (195-196). Can you give a more concrete example in camera-ready?
* 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)

POST-REBUTTAL: I thank the authors for their clarifications. My score remains unchanged: clear accept.
limitations_and_societal_impact: No / N/A
review_title: null

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)