# On the Expressivity of Markov Reward

arXiv: https://arxiv.org/abs/2111.00876 · HTML: https://mlsanity.com/paper/2111.00876/

## Key facts

- Cited by 71 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 83 references that are in the map.
- First posted on arXiv 1 Nov 2021.

## Builds on (most cited first, 23 of 23)

- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1606.03137/) (2016)
- [Inverse Reward Design](https://mlsanity.com/paper/1711.02827/) (2017)
- [Interactive Learning from Policy-Dependent Human Feedback](https://mlsanity.com/paper/1701.06049/) (2017)
- [Reward-rational (implicit) choice: A unifying formalism for reward learning](https://mlsanity.com/paper/2002.04833/) (2020)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [The Off-Switch Game](https://mlsanity.com/paper/1611.08219/) (2016)
- [Reinforcement Learning with a Corrupted Reward Channel](https://mlsanity.com/paper/1705.08417/) (2017)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [Preference-based Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2006.08910/) (2020)
- [Hyperbolic Discounting and Learning over Multiple Horizons](https://mlsanity.com/paper/1902.06865/) (2019)
- [Dueling Posterior Sampling for Preference-Based Reinforcement Learning](https://mlsanity.com/paper/1908.01289/) (2019)
- [A Boolean Task Algebra for Reinforcement Learning](https://mlsanity.com/paper/2001.01394/) (2020)
- [Unifying task specification in reinforcement learning](https://mlsanity.com/paper/1609.01995/) (2016)
- [What Can Learned Intrinsic Rewards Capture?](https://mlsanity.com/paper/1912.05500/) (2019)
- [Rethinking the Discount Factor in Reinforcement Learning: A Decision Theoretic Approach](https://mlsanity.com/paper/1902.02893/) (2019)
- [Action and Perception as Divergence Minimization](https://mlsanity.com/paper/2009.01791/) (2020)
- [Repeated Inverse Reinforcement Learning](https://mlsanity.com/paper/1705.05427/) (2017)
- [Multi-Agent Reinforcement Learning with Temporal Logic Specifications](https://mlsanity.com/paper/2102.00582/) (2021)
- [Maximum Reward Formulation In Reinforcement Learning](https://mlsanity.com/paper/2010.03744/) (2020)
- [REALab: An Embedded Perspective on Tampering](https://mlsanity.com/paper/2011.08820/) (2020)

## Built on by (most cited first, 30 of 71)

- [Defining and Characterizing Reward Hacking](https://mlsanity.com/paper/2209.13085/) (2022)
- [Motif: Intrinsic Motivation from Artificial Intelligence Feedback](https://mlsanity.com/paper/2310.00166/) (2023)
- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [The History and Risks of Reinforcement Learning and Human Feedback](https://mlsanity.com/paper/2310.13595/) (2023)
- [Learning Long-Term Reward Redistribution via Randomized Return Decomposition](https://mlsanity.com/paper/2111.13485/) (2021)
- [Settling the Reward Hypothesis](https://mlsanity.com/paper/2212.10420/) (2022)
- [Direct Behavior Specification via Constrained Reinforcement Learning](https://mlsanity.com/paper/2112.12228/) (2021)
- [Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2206.09421/) (2022)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [How to talk so AI will learn: Instructions, descriptions, and autonomy](https://mlsanity.com/paper/2206.07870/) (2022)
- [Language Control Diffusion: Efficiently Scaling through Space, Time, and Tasks](https://mlsanity.com/paper/2210.15629/) (2022)
- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [Eventual Discounting Temporal Logic Counterfactual Experience Replay](https://mlsanity.com/paper/2303.02135/) (2023)
- [Identifiability and generalizability from multiple experts in Inverse Reinforcement Learning](https://mlsanity.com/paper/2209.10974/) (2022)
- [Mind the Gap: Offline Policy Optimization for Imperfect Rewards](https://mlsanity.com/paper/2302.01667/) (2023)
- [Query-Policy Misalignment in Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.17400/) (2023)
- [f-Policy Gradients: A General Framework for Goal Conditioned RL using f-Divergences](https://mlsanity.com/paper/2310.06794/) (2023)
- [Three Dogmas of Reinforcement Learning](https://mlsanity.com/paper/2407.10583/) (2024)
- [Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards](https://mlsanity.com/paper/2410.12175/) (2024)
- [Aligning Robot and Human Representations](https://mlsanity.com/paper/2302.01928/) (2023)
- [LTL-Constrained Policy Optimization with Cycle Experience Replay](https://mlsanity.com/paper/2404.11578/) (2024)
- [The Provable Benefits of Unsupervised Data Sharing for Offline Reinforcement Learning](https://mlsanity.com/paper/2302.13493/) (2023)
- [A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machines](https://mlsanity.com/paper/2204.09772/) (2022)
- [Safe Deep Reinforcement Learning by Verifying Task-Level Properties](https://mlsanity.com/paper/2302.10030/) (2023)
- [Social Contract AI: Aligning AI Assistants with Implicit Group Norms](https://mlsanity.com/paper/2310.17769/) (2023)
- [On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks](https://mlsanity.com/paper/2401.14811/) (2024)
- [Utility Theory for Sequential Decision Making](https://mlsanity.com/paper/2206.13637/) (2022)
- [Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewards](https://mlsanity.com/paper/2310.00435/) (2023)
- [Orchestrating Human-AI Teams: The Manager Agent as a Unifying Research Challenge](https://mlsanity.com/paper/2510.02557/) (2025)

## Abstract (arXiv)

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.