Reward Machines (RMs) are an established mechanism in Reinforcement Learning (RL) to represent and learn sparse, temporally extended tasks with non-Markovian rewards. RMs rely on high-level information in the form of labels that are emitted by the environment alongside the observation. However, this concept requires manual user input for each environment and task. The user has to create a suitable labeling function that computes the labels. These limitations lead to poor applicability in widely adopted RL frameworks. We propose Symbolic Reward Machines (SRMs) together with the learning algorithms QSRM and LSRM to overcome the limitations of RMs. SRMs consume only the standard output of the environment and process the observation directly through guards that are represented by symbolic formulas. In our evaluation, our SRM methods outperform the baseline RL approaches and generate the same results as the existing RM methods. At the same time, our methods adhere to the widely used environment definition and provide interpretable representations of the task to the user.
Figures & tables
Figure 1: Office World environment. The discrete version is displayed. The labeled environments output the labels shown at the specific positions.
Figure 2: RM and SRM for the example task in the Office World. Self-loops with an output of zero are omitted in the RM.
Figure 3: RM and SRM of task diagonal_run for the Office World. Self-loops in the RM with zero rewards are omitted.
Figure 4: Original Mountain Car environment (left) and our version (right).
Figure 5: SRM for task ‘rml’ for our Mountain Car environment.
Figure 6: Mean10 performance values for the tasks post_inner_offices and diagonal_run in the discrete Office World (Rows 1-2), and for the tasks post_inner_offices, diagonal_run, and rml in the infinite environments (Rows 3-5).
Figure 7: LSRM mean10 performance values: Finite state space environment in the upper half and infinite state space environments in the lower half. The results for LSRM-GF are in the first row and for LSRM-FT in the second row.
Figure 8: Learned SRM by LSRM-FT for task post_inner_offices in the discrete Office World.
Figure 9: Learned SRM by LSRM-FT for task post_inner_offices in the continuous Office World. For better visualization, we apply our rounding function round′ that rounds the input value to two decimal places. The function round′ is defined by round′(x)={100⌊x⋅100⌋100⌈x⋅100⌉, if ⌊x⋅100⌋mod10≥5,, if ⌊x⋅100⌋mod10<5. The learned SRM is even closer to the SRM used in the environment than the one visualized in this figure.
Figure 10: Learned SRMs by LSRM-GF for task post_inner_offices in the discrete and continuous Office World.
We propose a Reinforcement Learning (RL) based control design framework for handling complex tasks. The approach extends the concept of Reward Machines (RM) with Signal Temporal Logic (STL) formulas that can be used for event generation. The use of STL allows not only a more efficient representation of rewards for complex tasks but also guiding the training process to converge towards behaviors satisfying specified requirements. We also propose an implementation of the framework that leverages the STL online monitoring algorithms. We illustrate the framework with three case studies (minigrid, cart-pole and high-way environments) with non-trivial tasks.
Ana María Gómez Ruiz, Thao Dang, Alexandre Donzé
UGA · VERIMAG, Université Grenoble Alpes · VERIMAG - IMAG, CNRS, UGA +1
Reward machines (RMs) inform reinforcement learning agents about the reward structure of the environment, enabling support for non-Markovian tasks and improving sample efficiency. However, learning with RMs is ill-suited for long-horizon problems where subtasks can be completed in any order. In such cases, the amount of information to learn increases exponentially with the number of unordered subtasks. We address this issue by introducing three generalisations of RMs: (1) Numeric RMs allow users to express complex tasks in a compact form. (2) In agenda RMs, states are associated with an agenda that tracks the remaining subtasks to complete. (3) Coupled RMs have coupled states associated with each subtask in the agenda. In addition, we introduce QCoRM, a new task-decomposition Q-learning-based algorithm that leverages coupled RMs and preserves global optimality guarantees in tabular settings. Our experiments across four domains -- featuring both discrete and continuous action and state spaces -- demonstrate that QCoRM scales better than baseline algorithms for long-horizon problems with unordered subtasks.
We present Pareto Q-Learning with Reward Machines (PQLRM), a multi-objective reinforcement learning algorithm for tasks whose reward structure is specified by a set of reward machines (RMs). PQLRM combines Pareto Q-Learning (PQL), which maintains sets of vector-valued Q-estimates to approximate the Pareto front, with enhancements from Q-Learning with Reward Machines (QRM), which exploits the factored automaton structure of the reward signal. This yields a multi-policy algorithm that remains sample-efficient under non-Markovian, RM-encoded rewards. Experimental trials show that PQLRM converges faster than a naive PQL baseline applied to the cross-product MDP and can synthesize Pareto-optimal policies that QRM cannot.
Linköping University, Sweden · Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStal, F-59000 Lille, France · Univ. Toulouse, INRAE-MIAT, Toulouse, France