On The Expressivity of Objective-Specification Formalisms in Reinforcement Learning

Rohan Subramani, Marcus Williams, Max Heitmann, Halfdan Holm, Charlie Griffin, Joar Skalse

TL;DR

This paper provides the first comprehensive "expressivity map" for 17 different ways to specify objectives in reinforcement learning (RL), ranging from standard Markov rewards to Linear Temporal Logic (LTL). The authors prove that many popular formalisms are incommensurable—meaning each can express unique tasks that the others cannot—highlighting a fundamental tradeoff between a formalism's power and its ease of optimization.

What Problem Does This Paper Address?

Most RL algorithms assume the goal is to maximize a Markovian reward function, where the reward depends only on the most recent state transition. However, many real-world goals are non-Markovian (e.g., "visit A then B, but never C") or involve complex trade-offs (Multi-Objective RL).

While researchers have proposed numerous alternative "formalisms" to specify these goals—such as Reward Machines, LTL, and Regularized RL—there has been no systematic study of how they relate. Can LTL express everything a Reward Machine can? Is Multi-Objective RL strictly more powerful than standard scalar rewards? This paper fills that gap by providing a formal framework to compare the expressive power of these methods.

Methods

The authors define expressivity based on policy orderings. A formalism $X$ is considered at least as expressive as $Y$ if, in any environment, $X$ can represent every possible ranking of policies that $Y$ can. This is a more rigorous metric than simply looking at whether two formalisms induce the same optimal policy, as it considers the entire "training signal" provided to an agent.

The researchers analyzed 17 salient formalisms, summarized in the table below:

Table of the 17 objective-specification formalisms considered in the paper.

To compare them, the authors used a mix of:

  1. Constructive Proofs: Demonstrating how to translate an objective from one formalism into another.
  2. Counter-examples: Designing specific environments and tasks that one formalism can represent but another cannot.
  3. Hasse Diagrams: A visual tool used to represent the resulting partial ordering (preorder) of expressivity.

Datasets

As a theoretical work, this paper does not use standard empirical datasets like ImageNet or Atari. Instead, the "datasets" consist of mathematical constructions of environments. The authors designed several minimal, illustrative environments (e.g., Figures 3, 4, 5, and 6 in the paper) to prove that certain policy orderings are impossible for specific formalisms to capture.

Key Insights and Ideas

  • The Incommensurability of Popular Methods: One of the most striking findings is that many "advanced" formalisms are incommensurable. For example, LTL, Reward Machines, Limit Average Rewards, and Regularized RL each have unique expressive capabilities. You cannot simply swap one for the other without losing the ability to specify certain types of goals.
  • Discontinuity is a Divider: Formalisms like LTL and Limit Average Rewards can represent "discontinuous" objectives—where a tiny change in a policy leads to a massive jump in its evaluation. Standard Markov Rewards and Reward Machines are restricted to continuous evaluations, which limits their power.
  • The VNM Connection: The authors link their findings to the von Neumann-Morgenstern (VNM) utility theorem. They show that any objective that cannot be expressed as a function of trajectory lotteries must violate fundamental axioms of rationality, such as continuity or independence.
  • No "Silver Bullet": The formalisms at the very top of the expressivity hierarchy (like arbitrary functions of policies) are generally intractable to optimize. The paper argues that there is currently no formalism that is both highly expressive and straightforward to solve with modern RL techniques.

Key Results

The core result is the Hasse diagram (Figure 1), which maps the power of all 17 formalisms.

Figure 1: This Hasse diagram displays all expressivity re- lationships between our formalisms. An arrow or chain of arrows from one formalism to another indicates that the first formalism can express all policy orderings that the second formalism can express, in all environments. Arrows going both directions mean that the formalisms have the same ex- pressivity. If there is no chain of arrows from one formalism to another, there are policy orderings that the latter can express and the former cannot express.
  • Equivalence Classes: The authors proved that several seemingly different formalisms are actually identical in power. For instance, Inner Multi-Objective RL (IMORL) is expressively equivalent to Functions from Trajectories to Reals (FTR).
  • Limitations of Markov Rewards: The paper reinforces that Markov Rewards (MR) sit near the bottom of the hierarchy. Many common tasks, like the "XOR" task (preferring an agent to do either A or B, but not both), are provably impossible to represent with MR.
  • Quantified Gaps: The authors provide a comprehensive table (Table 2 in the appendix) detailing 289 pairs of comparisons, proving exactly where arrows should and should not exist in the expressivity map.

Limitations and Future Work

  • Stationary vs. History-Dependent Policies: The primary analysis focuses on stationary policies (actions based only on the current state). The authors note that the expressivity map might shift if history-dependent policies are considered, as some formalisms (like Reward Machines) are specifically designed to handle history.
  • Tractability Trade-offs: The paper focuses purely on what can be expressed, not how hard it is to learn. A major direction for future work is identifying the "sweet spot" on the Hasse diagram where expressivity is high but optimization remains feasible.
  • Reward Learning: The results suggest that current reward learning methods (which often assume a Markovian reward) are fundamentally limited. The authors call for new research into learning LTL formulas, Reward Machines, or other non-Markovian objectives from human feedback.

Summary updated

Abstract

Most algorithms in reinforcement learning (RL) require that the objective is formalised with a Markovian reward function. However, it is well-known that certain tasks cannot be expressed by means of an objective in the Markov rewards formalism, motivating the study of alternative objective-specification formalisms in RL such as Linear Temporal Logic and Multi-Objective Reinforcement Learning. To date, there has not yet been any thorough analysis of how these formalisms relate to each other in terms of their expressivity. We fill this gap in the existing literature by providing a comprehensive comparison of 17 salient objective-specification formalisms. We place these formalisms in a preorder based on their expressive power, and present this preorder as a Hasse diagram. We find a variety of limitations for the different formalisms, and argue that no formalism is both dominantly expressive and straightforward to optimise with current techniques. For example, we prove that each of Regularised RL, (Outer) Nonlinear Markov Rewards, Reward Machines, Linear Temporal Logic, and Limit Average Rewards can express a task that the others cannot. The significance of our results is twofold. First, we identify important expressivity limitations to consider when specifying objectives for policy optimization. Second, our results highlight the need for future research which adapts reward learning to work with a greater variety of formalisms, since many existing reward learning methods assume that the desired objective takes a Markovian form. Our work contributes towards a more cohesive understanding of the costs and benefits of different RL objective-specification formalisms.
BibTeX
@inproceedings{subramani2024expressivity,
  author = {Rohan Subramani and Marcus Williams and Max Heitmann and Halfdan Holm and Charlie Griffin and Joar Skalse},
  title = {{On The Expressivity of Objective-Specification Formalisms in Reinforcement Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=qr4ECbGcSj},
}
Figure