# On the Expressivity of Multidimensional Markov Reward

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 13 references that are in the map.
- First posted on arXiv 22 Jul 2023.

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

- [Extrapolating Beyond Suboptimal Demonstrations via Inverse Reinforcement Learning from Observations](https://mlsanity.com/paper/1904.06387/) (2019)
- [On the Expressivity of Markov Reward](https://mlsanity.com/paper/2111.00876/) (2021)
- [Rethinking the Discount Factor in Reinforcement Learning: A Decision Theoretic Approach](https://mlsanity.com/paper/1902.02893/) (2019)

## Built on by (most cited first, 4 of 4)

- [On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks](https://mlsanity.com/paper/2401.14811/) (2024)
- [Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewards](https://mlsanity.com/paper/2310.00435/) (2023)
- [Beyond Scalar Rewards: An Axiomatic Framework for Lexicographic MDPs](https://mlsanity.com/paper/2505.12049/) (2025)
- [Illuminating the Three Dogmas of Reinforcement Learning under Evolutionary Light](https://mlsanity.com/paper/2507.11482/) (2025)

## Abstract (arXiv)

We consider the expressivity of Markov rewards in sequential decision making under uncertainty. We view reward functions in Markov Decision Processes (MDPs) as a means to characterize desired behaviors of agents. Assuming desired behaviors are specified as a set of acceptable policies, we investigate if there exists a scalar or multidimensional Markov reward function that makes the policies in the set more desirable than the other policies. Our main result states both necessary and sufficient conditions for the existence of such reward functions. We also show that for every non-degenerate set of deterministic policies, there exists a multidimensional Markov reward function that characterizes it