On the Expressivity of Markov Reward

This research explores the expressivity of Markov reward functions in capturing various tasks within reinforcement learning.

It introduces three task types—sets of acceptable behaviors, partial orderings over behaviors, and partial orderings over trajectories—and demonstrates that while Markov rewards can express many tasks, there are instances where they cannot.

The study also provides algorithms to determine if a task can be captured by a Markov reward function and to construct such a function when possible.