Reward machines are automata that can represent non-Markovian reward functions. We introduced them in an ICML 2018 paper, also shown in the list of publications below. See also our work on LTL and reinforcement learning.