Omega-Regular Reward Machines
This work addresses the challenge of specifying complex learning objectives in reinforcement learning for agents, though it appears incremental as it combines existing formalisms.
The paper tackled the problem of designing expressive reward mechanisms for reinforcement learning beyond Markovian assumptions by introducing omega-regular reward machines, which integrate reward machines with omega-regular languages, and demonstrated effectiveness through experiments with an epsilon-optimal algorithm.
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.