mlsanityData to 14 Oct 2026

On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks

arXiv 2401.14811 ↗First posted 26 Jan 2024cs.AI cs.LGcited by 9

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

In this paper, we study the expressivity of scalar, Markovian reward functions in Reinforcement Learning (RL), and identify several limitations to what they can express. Specifically, we look at three classes of RL tasks; multi-objective RL, risk-sensitive RL, and modal RL. For each class, we derive necessary and sufficient conditions that describe when a problem in this class can be expressed using a scalar, Markovian reward. Moreover, we find that scalar, Markovian rewards are unable to express most of the instances in each of these three classes. We thereby contribute to a more complete understanding of what standard reward functions can and cannot express. In addition to this, we also call attention to modal problems as a new class of problems, since they have so far not been given any systematic treatment in the RL literature. We also briefly outline some approaches for solving some of the problems we discuss, by means of bespoke RL algorithms.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 25 of its 43 references that are in the map. First posted on arXiv 26 Jan 2024.

Builds on

25 of 43 references.

References · 25

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2018Reward Constrained Policy Optimizationcited by 417
  3. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 337
  4. 2014A Survey of Multi-Objective Sequential Decision-Makingcited by 242
  5. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  6. 2022Defining and Characterizing Reward Hackingcited by 203
  7. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
  8. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  9. 2021Reward is enough for convex MDPscited by 84
  10. 2021On the Expressivity of Markov Rewardcited by 71
  11. 2019Reinforcement Learning with Convex Constraintscited by 60
  12. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 56
13 more
  1. 2021Scalar reward is not enough: A response to Silver, Singh, Precup and Sutton (2021)cited by 55
  2. 2018Penalizing side effects using stepwise relative reachabilitycited by 38
  3. 2019Rethinking the Discount Factor in Reinforcement Learning: A Decision Theoretic Approachcited by 32
  4. 2020Avoiding Side Effects By Considering Future Taskscited by 32
  5. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 30
  6. 2022Misspecification in Inverse Reinforcement Learningcited by 27
  7. 2020Avoiding Side Effects in Complex Environmentscited by 24
  8. 2022Lexicographic Multi-Objective Reinforcement Learningcited by 17
  9. 2020Statistically Model Checking PCTL Specifications on Markov Decision Processes via Reinforcement Learningcited by 12
  10. 2019Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewardscited by 8
  11. 2022Utility Theory for Sequential Decision Makingcited by 8
  12. 2022Learning Task Automata for Reinforcement Learning using Hidden Markov Modelscited by 7
  13. 2023On the Expressivity of Multidimensional Markov Rewardcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 3; 2026: 2.

9 papers.

  1. 2024Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systemscited by 96
  2. 2024Multi-objective Reinforcement learning from AI Feedbackcited by 10
  3. 2025On Generalization Across Environments In Multi-Objective Reinforcement Learningcited by 8
  4. 2024The Partially Observable Off-Switch Gamecited by 5
  5. 2025FairDICE: Fairness-Driven Offline Multi-Objective Reinforcement Learningcited by 2
  6. 2024Numeric Reward Machinescited by 1
  7. 2025Reinforcement Learning for Long-Horizon Unordered Tasks: From Boolean to Coupled Reward Machinescited by 0
  8. 2026AETDICE: Unified Framework and Offline Optimization for Nonlinear Multi-Objective RLcited by 0
  9. 2026Fragility of Value under Imperfect Alignmentcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2019Reinforcement Learning with Non-Markovian Rewards
  2. 2024To the Max: Reinventing Reward in Reinforcement Learning
  3. 2023Is RLHF More Difficult than Standard RL?
  4. 2026Mathematical methods of reinforcement learning
  5. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
  6. 2024Adaptive Reward Design for Reinforcement Learning
  7. 2024Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning
  8. 2025Reward Compatibility: A Framework for Inverse RL