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.
The authors formalize the "task" as the primary object of interest, defining three distinct types:
- Set of Acceptable Policies (SOAP): A collection of behaviors deemed "good," where the agent must select one.
- Partial Ordering over Policies (PO): A preference hierarchy (e.g., Policy A > Policy B).
- 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.
Key Results and Empirical Trends
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.
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