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:
To compare them, the authors used a mix of:
- Constructive Proofs: Demonstrating how to translate an objective from one formalism into another.
- Counter-examples: Designing specific environments and tasks that one formalism can represent but another cannot.
- 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.
- 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