# On The Expressivity of Objective-Specification Formalisms in Reinforcement Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2023.

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

- [Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems](https://mlsanity.com/paper/2405.06624/) (2024)
- [AI Alignment with Changing and Influenceable Reward Functions](https://mlsanity.com/paper/2405.17713/) (2024)
- [On Generalization Across Environments In Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2503.00799/) (2025)
- [Non-maximizing policies that fulfill multi-criterion aspirations in expectation](https://mlsanity.com/paper/2408.04385/) (2024)
- [It's a matter of timescale: non-linear utility in successor features and multi-objective planning and learning](https://mlsanity.com/paper/2608.25723/) (2026)

## Abstract (arXiv)

Most algorithms in reinforcement learning (RL) require that the objective is formalised with a Markovian reward function. However, it is well-known that certain tasks cannot be expressed by means of an objective in the Markov rewards formalism, motivating the study of alternative objective-specification formalisms in RL such as Linear Temporal Logic and Multi-Objective Reinforcement Learning. To date, there has not yet been any thorough analysis of how these formalisms relate to each other in terms of their expressivity. We fill this gap in the existing literature by providing a comprehensive comparison of 17 salient objective-specification formalisms. We place these formalisms in a preorder based on their expressive power, and present this preorder as a Hasse diagram. We find a variety of limitations for the different formalisms, and argue that no formalism is both dominantly expressive and straightforward to optimise with current techniques. For example, we prove that each of Regularised RL, (Outer) Nonlinear Markov Rewards, Reward Machines, Linear Temporal Logic, and Limit Average Rewards can express a task that the others cannot. The significance of our results is twofold. First, we identify important expressivity limitations to consider when specifying objectives for policy optimization. Second, our results highlight the need for future research which adapts reward learning to work with a greater variety of formalisms, since many existing reward learning methods assume that the desired objective takes a Markovian form. Our work contributes towards a more cohesive understanding of the costs and benefits of different RL objective-specification formalisms.