Comparing Non-Markovian Tasks Represented by Reward Machines

In reinforcement learning, when reward functions are learned from data, it is useful to be able to make quantitative comparisons of reward functions. The overwhelming majority of work on metrics for comparing reward functions is focused on cases where the rewards are Markovian. On the other hand, temporally extended tasks whose rewards depend on history, where the agent has to accomplish multiple steps in a correct order, are non-Markovian. A popular way of formalising non-Markovian reward functions is by using reward machines, a type of deterministic finite automaton. Building on existing work for Markovian reward functions, we introduce a family of environment-dependent pseudometrics for comparing reward machines. We compare rewards over a common space of feasible histories, making the comparisons consistent across different representations of the same task. We show zero distance coincides with task equivalence, and we establish policy regret bounds for reward machines of bounded size. Our experiments demonstrate invariance of our method to reward machine representations. Our method provides a basis for evaluating learned reward machines by how well they represent an intended task, rather than how well they reconstruct a particular automaton.