mlsanityData to 7 Oct 2026

On the Expressivity of Markov Reward

arXiv 2111.00876 ↗First posted 1 Nov 2021cs.LG cs.AIcited by 71

Not on the map. Why?

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.

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

Builds on

23 of 83 references.

References · 23

  1. 2017Deep reinforcement learning from human preferencescited by 3,846
  2. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  3. 2016Cooperative Inverse Reinforcement Learningcited by 298
  4. 2017Inverse Reward Designcited by 246
  5. 2017Interactive Learning from Policy-Dependent Human Feedbackcited by 155
  6. 2020Reward-rational (implicit) choice: A unifying formalism for reward learningcited by 119
  7. 2016Reinforcement Learning With Temporal Logic Rewardscited by 114
  8. 2016The Off-Switch Gamecited by 97
  9. 2017Reinforcement Learning with a Corrupted Reward Channelcited by 68
  10. 2020A Composable Specification Language for Reinforcement Learning Taskscited by 68
  11. 2017Environment-Independent Task Specifications via GLTLcited by 67
  12. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
11 more
  1. 2019Hyperbolic Discounting and Learning over Multiple Horizonscited by 58
  2. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  3. 2020A Boolean Task Algebra for Reinforcement Learningcited by 46
  4. 2016Unifying task specification in reinforcement learningcited by 41
  5. 2019What Can Learned Intrinsic Rewards Capture?cited by 36
  6. 2019Rethinking the Discount Factor in Reinforcement Learning: A Decision Theoretic Approachcited by 32
  7. 2020Action and Perception as Divergence Minimizationcited by 31
  8. 2017Repeated Inverse Reinforcement Learningcited by 29
  9. 2021Multi-Agent Reinforcement Learning with Temporal Logic Specificationscited by 27
  10. 2020Maximum Reward Formulation In Reinforcement Learningcited by 10
  11. 2020REALab: An Embedded Perspective on Tamperingcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 19; 2023: 21; 2024: 11; 2025: 12; 2026: 5.

71 papers.

Sort:

By area:

  1. 2022Defining and Characterizing Reward Hackingcited by 184
  2. 2023Motif: Intrinsic Motivation from Artificial Intelligence Feedbackcited by 99
  3. 2023A Definition of Continual Reinforcement Learningcited by 98
  4. 2023The History and Risks of Reinforcement Learning and Human Feedbackcited by 42
  5. 2021Learning Long-Term Reward Redistribution via Randomized Return Decompositioncited by 33
  6. 2022Settling the Reward Hypothesiscited by 33
  7. 2021Direct Behavior Specification via Constrained Reinforcement Learningcited by 30
  8. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 29
  9. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 29
  10. 2023Submodular Reinforcement Learningcited by 23
  11. 2022How to talk so AI will learn: Instructions, descriptions, and autonomycited by 22
  12. 2022Language Control Diffusion: Efficiently Scaling through Space, Time, and Taskscited by 20
38 more
  1. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  2. 2023Eventual Discounting Temporal Logic Counterfactual Experience Replaycited by 18
  3. 2022Identifiability and generalizability from multiple experts in Inverse Reinforcement Learningcited by 16
  4. 2023Mind the Gap: Offline Policy Optimization for Imperfect Rewardscited by 15
  5. 2023Query-Policy Misalignment in Preference-Based Reinforcement Learningcited by 14
  6. 2023f-Policy Gradients: A General Framework for Goal Conditioned RL using f-Divergencescited by 14
  7. 2024Three Dogmas of Reinforcement Learningcited by 14
  8. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewardscited by 13
  9. 2023Aligning Robot and Human Representationscited by 11
  10. 2023The Provable Benefits of Unsupervised Data Sharing for Offline Reinforcement Learningcited by 10
  11. 2024LTL-Constrained Policy Optimization with Cycle Experience Replaycited by 10
  12. 2022A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machinescited by 9
  13. 2023Safe Deep Reinforcement Learning by Verifying Task-Level Propertiescited by 9
  14. 2023Social Contract AI: Aligning AI Assistants with Implicit Group Normscited by 9
  15. 2024On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Taskscited by 9
  16. 2022Utility Theory for Sequential Decision Makingcited by 8
  17. 2023Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewardscited by 8
  18. 2025Orchestrating Human-AI Teams: The Manager Agent as a Unifying Research Challengecited by 8
  19. 2022Designing Rewards for Fast Learningcited by 7
  20. 2022CoNSoLe: Convex Neural Symbolic Learningcited by 7
  21. 2024Directed Exploration in Reinforcement Learning from Linear Temporal Logiccited by 7
  22. 2024The Dark Side of Rich Rewards: Understanding and Mitigating Noise in VLM Rewardscited by 7
  23. 2023Learning non-Markovian Decision-Making from State-only Sequencescited by 6
  24. 2025Causally Aligned Curriculum Learningcited by 6
  25. 2022Reinforcement Learning in Practice: Opportunities and Challengescited by 5
  26. 2022Deconfounding Imitation Learning with Variational Inferencecited by 5
  27. 2024Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markovcited by 5
  28. 2022Efficient Meta Reinforcement Learning for Preference-based Fast Adaptationcited by 4
  29. 2023On the Expressivity of Multidimensional Markov Rewardcited by 4
  30. 2026Imperfect World Models are Exploitablecited by 4
  31. 2022Learning Performance Graphs from Demonstrations via Task-Based Evaluationscited by 3
  32. 2023Conditions on Preference Relations that Guarantee the Existence of Optimal Policiescited by 3
  33. 2024Rethinking Inverse Reinforcement Learning: from Data Alignment to Task Alignmentcited by 3
  34. 2025Mutual Information Tracks Policy Coherence in Reinforcement Learningcited by 3
  35. 2025Beyond Sliding Windows: Learning to Manage Memory in Non-Markovian Environmentscited by 3
  36. 2023A State Augmentation based approach to Reinforcement Learning from Human Preferencescited by 2
  37. 2023A Reminder of its Brittleness: Language Reward Shaping May Hinder Learning for Instruction Following Agentscited by 2
  38. 2023Is Feedback All You Need? Leveraging Natural Language Feedback in Goal-Conditioned Reinforcement Learningcited by 2

50 most cited of 71 All 71 (JSON)