  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.
