Research map / Reinforcement learning / Policy gradient and actor-critic
On the Expressivity of Objective-Specification Formalisms in Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Compares the expressivity of 17 RL objective-specification formalisms (e.g., Markov rewards, LTL, reward machines, MORL variants) via a preorder and Hasse diagram, with theoretical proofs of expressive limitations.
Problem
Most RL objectives are formalised with Markov rewards, yet some tasks cannot be expressed that way; no thorough analysis existed of how alternative objective-specification formalisms (LTL, multi-objective RL, reward machines, etc.) compare in expressive power.
Approach
Defines expressivity as inclusion of the set of policy orderings an formalism can induce across all finite environments, then proves a complete preorder (Hasse diagram) over 17 formalisms using positive embeddings and counterexamples (e.g., XOR-style policy orderings).
Key results
- Compares 17 objective-specification formalisms over all 289 ordered pairs, proving each pair either expressible or not, and presents the result as a Hasse diagram.
- Proves that Regularised RL, (Outer) Nonlinear Markov Rewards, Reward Machines, LTL, and Limit Average Rewards can each express a task that the others cannot.
- Shows Inner Nonlinear Markov Rewards, Inner Multi-Objective RL, and Functions from Trajectories to Reals are equally expressive; Outer MORL, FOMR and FTLR are equally expressive; GOMORL, OMO and TLO are equally expressive.
Surprising findings
- Markov rewards cannot express some policy orderings that Limit Average Rewards can, and LTL and MR can express orderings that LAR cannot.
- No formalism except Policy Orderings can express all objectives; many formalisms are expressively incommensurable.
Limitations
- Focuses on stationary policies; many results may not carry over to history-dependent policies.
- Some results rely on arbitrary wrapper functions or unbounded numbers of reward functions, which may reduce practical significance.
- Does not assess the tractability of formalisms, so the expressivity-tractability tradeoff is left open.
Experimental setup
Builds on: Markov decision processes linear temporal logic reward machines von Neumann-Morgenstern utility theorem convex RL
Closest papers by meaning
- Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards (NeurIPS 2024 · similarity 0.89)
- Multi-objective Linear Reinforcement Learning with Lexicographic Rewards (ICML 2025 · similarity 0.88)
- A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs (AAAI 2024 · similarity 0.88)
- An Analytical Study of Utility Functions in Multi-Objective Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
- On Generalization Across Environments In Multi-Objective Reinforcement Learning (ICLR 2025 · similarity 0.87)
- To the Max: Reinventing Reward in Reinforcement Learning (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.