On the Expressivity of Markov Reward (Extended Abstract)

David Abel, Will Dabney, Anna Harutyunyan, Mark K. Ho, Michael L. Littman, Doina Precup, Satinder Singh

Abstract

While the "reward hypothesis" suggests that any goal can be captured by a scalar reward signal, this paper proves that standard Markov rewards—the kind used in almost all reinforcement learning—have fundamental limits. The authors demonstrate that certain tasks simply cannot be expressed as Markov rewards and provide a polynomial-time algorithm to determine if a specific task is "rewardable" in a given environment.

Introduction

In Reinforcement Learning (RL), the standard assumption is that any desired behavior can be elicited by designing an appropriate reward function. Specifically, practitioners almost exclusively use Markov reward functions, where the reward $R(s, a)$ depends only on the current state and action. However, the theoretical bounds of what these functions can actually express remain poorly understood.

Conceptual framework of task specification and reward design.

The authors formalize the "task" as the primary object of interest, defining three distinct types:

  1. Set of Acceptable Policies (SOAP): A collection of behaviors deemed "good," where the agent must select one.
  2. Partial Ordering over Policies (PO): A preference hierarchy (e.g., Policy A > Policy B).
  3. Partial Ordering over Trajectories (TO): Preferences over specific action sequences.

The core research question is: Does there always exist a Markov reward function that makes the "good" behaviors optimal while ensuring "bad" behaviors remain sub-optimal?

Methodology

The paper employs a rigorous framework combining formal logic and optimization:

  • Theoretical Proofs: Theorem 3.1 establishes that for every task type, there exist environment-task pairs that no Markov reward function can capture.
  • Linear Programming (LP) Formulation: The search for a valid reward function is framed as a feasibility problem. For any finite environment and task, a Linear Program can be constructed to find a valid reward. If the LP is infeasible, the task is mathematically impossible to express with Markov rewards in that specific environment.
  • Polynomial-Time Verification: Theorem 3.2 provides a constructive algorithm that either outputs a valid reward function or proves its non-existence in polynomial time.

The authors evaluate their framework using synthetic Controlled Markov Processes (CMPs) and specific "corner case" MDPs designed to illustrate failure modes like XOR-style preferences.

Toy examples of inexpressibility and empirical trends across different environment parameters.

Key findings include:

  • The Entailment Problem: Inexpressibility often arises from "value correlation." If two policies are structurally similar, a Markov reward may be forced to assign them similar values. If the task requires one to be optimal and the other sub-optimal, a conflict occurs.
  • Impact of Environment Dynamics: Interestingly, increasing the "entropy" (randomness) of transitions often makes tasks easier to express. Stochasticity likely "de-correlates" policy values, providing more degrees of freedom for reward design.
  • Task Complexity: As the "SOAP Size" increases or the "Spread" (diversity of acceptable behaviors) grows, the probability of finding a valid Markov reward decreases significantly.
  • Equal vs. Range Realization: Requiring all "good" policies to have the exact same value (Equal-SOAP) is much more restrictive than simply requiring them to be better than bad ones (Range-SOAP).

Conclusion

This work highlights that Markov rewards are not a universal language for task specification. While they are computationally convenient, they possess inherent expressive limitations that can lead to "reward hacking" or the inability to specify complex preferences. The provided polynomial-time algorithm offers a practical tool for researchers to audit their reward structures before deployment.

Summary updated

Abstract

Reward is the driving force for reinforcement-learning agents. We here set out to understand the expressivity of Markov 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": (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 perform each task type, and correctly determine when no such reward function exists.
BibTeX
@inproceedings{abel2022expressivity,
  author = {David Abel and Will Dabney and Anna Harutyunyan and Mark K. Ho and Michael L. Littman and Doina Precup and Satinder Singh},
  title = {{On the Expressivity of Markov Reward (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/730},
}
Figure