On the Expressivity of Objective-Specification Formalisms in Reinforcement Learning

Thank you for your feedback! Our responses are as follows:

(C1. Policy ordering) We compare the expressivities of formalisms in terms of policy orderings because the policy ordering is the most fine-grained unit of analysis for this purpose. SOAPs are constructed by taking a policy ordering, choosing a cutoff point to divide the policies into two classes (i.e., those above and below the cutoff), and then discarding all information about how the policies are ordered within each class. Thus, any difference in expressivity that is captured by an equal-SOAP or range-SOAP (also terminology from Abel et al., 2022) is captured by the policy ordering task definition. We will edit the paper to discuss this and other motivations for using policy orderings in more detail.

(C2. Stationary policies) Markov reward can make any deterministic stationary policy optimal, but cannot express all orderings of deterministic stationary policies; for example, see the proof of Proposition A.31 in our appendix. Also, note that many of our results directly carry over to history-dependent policies; if a formalism A can express a stationary policy ordering which is not expressible by formalism B, then clearly A can express an ordering over history-dependent policies that B cannot. So every negative expressivity result carries over directly. Further, several of our positive proofs do not assume that we are considering only stationary policies. We will make edits to underscore this point and indicate what work remains to be done to round out the results for history-dependent policies. While many results carry over, rounding out these results would still be a significant undertaking which is out of scope for our work. This is an interesting direction for future research, especially given your point that some formalisms are well-suited to expressing tasks where history-dependent policies are essential. We hope that by adding further details about which of our results carry over to the history-dependent case we make our contribution more significant and lessen the amount of work remaining to complete the history-dependent analysis.

(C3. Expressivity against tractability) Tractability is crucial, but analysing the tractability of each formalism would be a massive undertaking. Much of the existing RL literature can be construed as an attempt to establish the practical tractability of the MDP formalism. It is therefore not feasible to tackle this question in our paper. Many formalisms we compare are studied in the literature, and past work we reference does give an indication of the tractability of these formalisms. We hope that the tractability of the formalisms in our comparison will become clearer over time as new algorithms are proposed and applied to more problems. We also think our expressivity comparison is a valuable contribution by itself. For instance, our work can help an RL practitioner identify a formalism that can express their task of interest and seek out an appropriate algorithm. If no existing algorithms are suitable for the task, this can prompt further research. The Skalse et al., 2022 paper “Lexicographic Multi-Objective Reinforcement Learning” is an example of research of this sort: lexicographic objectives are expressible with GOMORL but not with Markovian rewards, and the paper provides algorithms for solving them. We will edit the paper to better convey a) the reasons we are unable to provide a thorough account of tractability and b) why our work is still a valuable step that future work can build on.

(C4. Missing references) Thank you for providing this list of references. We construed Related Work as a section to discuss the formalisms that we were studying, but after seeing your comment, we believe it is sensible to point to formalisms beyond those that we consider to highlight that we haven’t considered all interesting formalisms. We will make these edits.

(Clarity) Notational departures from the literature are motivated by a need to use comparable notations for the formalisms that we are comparing. We certainly want to make our results as clear and accessible as possible, so any pointers to specific notational choices that are difficult to parse would be appreciated.

Questions:

1. We attempt to address your comments above.
2. Most of our results are novel, unless mentioned in the Related Work. Unfortunately, it is difficult to fully disentangle original work from previous work since our proofs often rely on a combination of existing and novel ideas.
3. In brief, you could have something akin to a lexicographic order over a set of occupancy measures, and there would be no function from occupancy measures to reals that preserves this order. See Proposition A.37 in our appendix (from which this results follows) for details.

Please let us know if our response and planned edits address your concerns and if you have any other suggestions. We hope that you will consider increasing your score.

I want to thank the authors for their detailed replies and for taking my concerns in serious consideration.

We likewise thank you for your engagement, and for your detailed review of the paper!

While I think that extending the analysis to history-dependent policies may clear the bar for acceptance, I cannot judge those changes without looking at them.

We have submitted a modified version of the paper that includes our partial analysis of history-dependent policies. The most relevant parts are a paragraph in the Limitations and Future Work subsection (4.1), Appendix A.3 (referenced in Section 4.1), and Table 3 (referenced in Appendix A.3). We will add that we actually have more results for history-dependent policies prepared than appear in the updated paper, since some additional results rely on proofs that we do not have time to type up before the end of the discussion period. We appreciate that you cannot weight this very heavily given that it is not included in the current submission, but there are only 12 white boxes (representing missing results) in our most up-to-date internal version of Table 3, and we can certainly make that adjustment later if the paper is accepted.

Can the authors name a practical application where a policy ordering is needed?

The discussion of policy orderings is complicated, and we will provide two strands of argument in favor of our choice.

First: In most real-world situations, we cannot find a globally optimal policy. For example, this is typically not feasible in robotics tasks, or when optimising a language model to exhibit some behaviour (such as politeness, etc). For this reason, if we want a task specification to robustly incentivise desirable behaviour, then it is important that this task specification expresses the correct preferences between the (sub-optimal) policies that the policy optimisation algorithm in fact may generate. One way to see the practical importance of this consideration is to note that MORL is very common in practice. One of the main reasons for this is that the MORL formulation makes it easier to describe how certain trade-offs should be made, and this is captured by the fact that MORL can express policy orderings which scalar Markov rewards cannot. For this reason, we think it is informative and relevant to consider the policy orderings which a task specification method is able to capture.

Second: We appreciate that by choosing policy orderings as our task notion there is the possibility of finding a greater number of expressive differences between formalisms than would have been found with the use of SOAPs, and this gives rise to the concern that these “extra” expressive differences may lack practical significance. However, we believe that the negative results we provide in the paper point to interesting limitations of the different formalisms, and one of the following must be true: either those expressive differences would have also been seen under the SOAP task notion, in which case the use of policy orderings makes no difference to the discovered expressivity relationship; or those differences would have been invisible to the SOAP task notion, in which case use of SOAPs would have concealed from us the interesting limitations that we discovered. Insofar as you agree that the proofs of our negative results reveal meaningful insights about the expressive limitations of the different formalisms, the use of POs rather than SOAPs is at worst a harmless choice and at best even the superior choice. (Note also that many interesting expressive limitations of Markovian rewards are already visible under a SOAP formulation — so that is not merely a quirk of our choice of policy orderings as the task notion.)

In any case, while we agree that other problem formulations can also be relevant, we do not think that this fact alone is sufficient ground for rejection of the paper.

First of all, we would like to thank reviewer Re36 for their feedback! Our responses to your comments are as follows:

1. The main reason for why we have not considered STL in this work is that we are focusing on discrete environments (i.e., environments with discrete time, where the set of states and the set of actions are both finite). Most of the objective specification methods that we consider are best suited for discrete environments, and in such environments, STL is equivalent to LTL. A generalisation to environments with continuous time would be interesting, but we consider it to be out of scope for this work. We will however amend the text to provide references to recent work on STL in RL.
2. Tractability is crucial, but analysing the tractability of each formalism would be a massive undertaking. Much of the existing RL literature can be construed as an attempt to establish the practical tractability of the MDP formalism. It is therefore not feasible to tackle this question in our paper. Many formalisms we compare are studied in the literature, and past work we reference does give an indication of the tractability of these formalisms. We hope that the tractability of the formalisms in our comparison will become clearer over time as new algorithms are proposed and applied to more problems. We also think our expressivity comparison is a valuable contribution by itself. For instance, our work can help an RL practitioner identify a formalism that can express their task of interest and seek out an appropriate algorithm. If no existing algorithms are suitable for the task, this can prompt further research. The Skalse et al., 2022 paper “Lexicographic Multi-Objective Reinforcement Learning” is an example of research of this sort: lexicographic objectives are expressible with GOMORL but not with Markovian rewards, and the paper provides algorithms for solving them. We will edit the paper to better convey a) the reasons we are unable to provide a thorough account of tractability and b) why our work is still a valuable step that future work can build on.
3. We are certainly keen to improve the presentation and the notation if you could give us examples of places where this is unclear. Note that $\mathbb{R}^{|S||A||S|}$ is isomorphic to $\mathbb{R}^{|S|} \times \mathbb{R}^{|A|} \times \mathbb{R}^{|S|}$, so there is no mathematical reason to substitute these.

We hope that this clarifies our contributions and the choices that we made. Please let us know if our response and planned edits address your concerns and if you have any other suggestions. We also hope that you will consider increasing your score.

First of all, we would like to thank reviewer XNit for their review! Our responses to your comments and questions are as follows:

Weaknesses:

1. We aim to address your concern about nonstationary policies below in our response to your second question.

Questions:

1. We consider the full version of LTL, i.e. the version that considers infinitely long trajectories.
2. In our paper we define a task to be an ordering of stationary policies, and so stationary policy orderings are (trivially) capable of expressing any LTL task so defined. That is why the formalism of stationary policy orderings (PO) expressively dominates LTL in our results. However, as you rightly indicate, certain objective specifications in LTL (and other formalisms) are of interest primarily for their behaviour on memory-dependent policies, and it is regrettable that we were unable to consider orderings over the set of memory-dependent policies as well as over the set of Markovian policies. We chose to focus on Markovian policies because these are assumed by many common RL algorithms. Also, it should be noted that many of our results straightforwardly carry over to memory-dependent policies. In particular, all our negative expressivity results carry over directly (if a formalism X can express an ordering over Markovian policies that is not expressible in a formalism Y, then this trivially implies that X can express an ordering over the broader class of memory-dependent policies that is not expressible in Y), and many of our proofs establishing positive expressivity relationships apply equally well when the class of policies is expanded to include memory-dependent policies. We will edit the paper to underscore this point, and indicate what work remains to be done to round out the results for memory-dependent policies (which is, however, outside the scope of our work).

We hope that this answers your questions!

First of all, we would like to thank reviewer mz4B for their review! Our responses to your comments and question are below.

We believe our work is potentially relevant to anyone interested in training AI systems to solve novel sequential decision-making tasks, since the strengths and limitations we identify for formalisms may be relevant for a variety of such tasks. Therefore, we hope that our results are of interest to a substantial portion of the general ICLR community. However, depending on the reception of the paper, we may consider extending it to a journal submission.

We appreciate that the writing can be somewhat dense in places, though this is commensurate with the density of formal results in our paper, which makes this style of writing difficult to avoid. However, we will work on making the text more accessible by incorporating the feedback from the reviewers.