Omega-Regular Reward Machines
Ernst Moritz Hahn Mateo Perez Sven Schewe Fabio Somenzi Ashutosh Trivedi Dominik Wojtczak
Reinforcement learning (RL) is a powerful approach for training agents to
perform tasks, but designing an appropriate reward mechanism is critical to its
success. However, in many cases, the complexity of the learning objectives goes
beyond the capabilities of the Markovian assumption, necessitating a more
sophisticated reward mechanism. Reward machines and omega-regular languages are
two formalisms used to express non-Markovian rewards for quantitative and
qualitative objectives, respectively. This paper introduces omega-regular
reward machines, which integrate reward machines with omega-regular languages
to enable an expressive and effective reward mechanism for RL. We present a
model-free RL algorithm to compute epsilon-optimal strategies against
omega-egular reward machines and evaluate the effectiveness of the proposed
algorithm through experiments.