On Tackling Complex Tasks with Reward Machines and Signal Temporal Logics

Ana María Gómez Ruiz; Thao Dang; Alexandre Donzé

cs.AIApr 9, 2026

On Tackling Complex Tasks with Reward Machines and Signal Temporal Logics

Authors: Ana María Gómez Ruiz, Thao Dang, Alexandre Donzé

Organizations: UGA · VERIMAG, Université Grenoble Alpes · VERIMAG - IMAG, CNRS, UGA · CNRS, VERIMAG, Université Grenoble Alpes

Abstract

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.

Figures & tables

Figure 1

Fig. 1 : The minigrid environment Unlockenv with bigger grid size.

Panel of Figure 3 — Fig. 2 : Reward machine of the Minigrid agent

Panel of Figure 4 — Fig. 3 : Results from training an agent in the Unlock environment from a extended grid size 12x12 in MiniGrid. Blue: vanilla; orange: RM state in observation with STL specification during training.

Grid Size	Algorithm	Mean Reward $\pm$ Std	Mean Len Episode $\pm$ Std
6	Specs	$0.9494\pm 0.0221$	$16.2\pm 7.09$
6	Vanilla	$0.1756\pm 0.3927$	$238.2\pm 111.36$
7	Specs	$0.9720\pm 0.0062$	$12.2\pm 2.68$
7	Vanilla	$0.9715\pm 0.0060$	$12.4\pm 2.61$
8	Specs	$0.9631\pm 0.0128$	$21.0\pm 7.28$
8	Vanilla	$0.7670\pm 0.4290$	$121.2\pm 218.63$

TABLE I : Performance comparison per grid size of RM+STL vs Vanilla

Panel of Figure 6 — Fig. 4 : Results achieved by the trained models when evaluated on larger grid sizes.

Fig. 5 : The cart-pole environment, augmented with target regions A and B defined as STL predicates $\mu_{A}$ and $\mu_{B}$ .

Panel of Figure 8 — Fig. 6 : Reward machines of the cart pole: $\mathsf{R}^{1}$ encodes the task to go to region A and then to region B and stay there. $\mathsf{R}^{2}$ enforces episode termination when the formula $\varphi_{\text{stuck}}$ defined in formula ( 1 ) is true.

Fig. 7 : Test results of a single episode using the sub-optimal trained model (i) and using a successfully trained one (ii).

Fig. 8 : Results for 10 training instances with (green) and without (gray)

\mathsf{R}^{2}

encoding STL formula

\varphi_{\text{stuck}}

as terminal condition. With

\mathsf{R}^{2}

, the performance of the policy consistently reaches an accumulated reward of 3.000, indicating that the task is successfully completed, whereas with only

\mathsf{R}^{1}

, the performance of some policies remains around 800, indicating that only the region A is reached in most episodes.

Formula	$hz$	Interpretation
$\mu_{danger}^{i}=\|x^{i}\|<.1\wedge\|y^{i}\|<.1$	0	car $i$ is in front and too close
$\mu_{danger}=\vee_{i=1}^{4}\ \mu_{danger}^{i}$	0	A car is in front and too close
$\varphi_{tail}=\Box_{[0,10]}\ \mu_{danger}$	10	Too close for too long
$\mu_{fast}=v^{ego}_{x}>25$	0	ego vehicle goes fast
$\varphi_{lazy}=\Box_{[0,10]}\ \neg\mu_{fast}$	10	safe for 10 steps
$\varphi_{fast}$ = $\Diamond_{[0,85]}\Box_{[0,15]}\ \mu_{fast}$	100	always accelerates eventually

TABLE II : Formulas characterizing driving behaviors and used in the RM in Figure 9 . Short horizon formula (

hz\leq 10

) are used as event formulas. Long horizon formulas (

hz=100

) are for agent evaluation past training.

Panel of Figure 12 — Fig. 9 : Reward machine and formulas for the highway-env environment.

Fig. 10 : Training results for different values of rewards and penalties. Every 1e5 steps, the agent is tested for 100 episodes and all formulas are evaluated to give a complete picture of the current performance. All values lead to improving performance, lower values of

p_{left}

increase the rate of satisfaction of

\varphi_{right}

, which is consistent with the formulas and RM.

Hyperparameter	Value
Total Timesteps	$5\times 10^{5}$
Learning Rate ( $\alpha$ )	$3\times 10^{-4}$
Rollout Steps ( $n_{steps}$ )	2048
Batch Size	64
Optimization Epochs ( $n_{epochs}$ )	10
Discount Factor ( $\gamma$ )	0.99

TABLE III : PPO Training Hyperparameters

Explore similar work

Reward Machines for Signal Temporal Logic
Aug 13, 2026Alper Kamil Bozkurt, Shangtong Zhang, Yuichi MotaiReward Design for RL RL Control
Department of Computer Science, University of Virginia, Charlottesville, VA, USA
Tractable Reinforcement Learning for Full Class of Signal Temporal Logic Specifications Using Spatiotemporal Tube Reward
Sep 23, 2026Vaishnavi Jagabathula, P Sangeerth, Pushpak JagtapRobotic RL Reinforcement Learning
Centre for Cyber-Physical Systems, IISc, Bangalore, India
Reinforcement Learning with Symbolic Reward Machines
Mar 3, 2026Thomas Krug, Daniel NeiderReinforcement Learning Sparse-Reward RL
TU Dortmund University · Research Center Trustworthy Data Science and Security

Aug 13, 2026J/K move · Enter open · S save

Reward Machines for Signal Temporal Logic

Alper Kamil Bozkurt, Shangtong Zhang, Yuichi Motai

Department of Computer Science, University of Virginia, Charlottesville, VA, USA

Reward Design for RL RL Control Signal Temporal Logic Reinforcement Learning

Open paper AskPDF arXiv

Signal temporal logic (STL) provides a formal language for specifying real-time properties of real-valued observations, along with a quantitative robustness score for monitoring satisfaction. Control synthesis from STL specifications is of interest since manual controller design becomes infeasible as real-world systems grow in complexity. Moreover, many modern autonomous and AI-enabled systems lack accurate and complete system models, which makes optimization-based synthesis approaches unsuitable and motivates learning-based control. Prior work uses STL robustness scores as rewards in reinforcement learning (RL) to obtain control policies satisfying given specifications; however, robustness depends on execution history, leading to intractable state space expansion for general long-horizon specifications with arbitrarily nested temporal operators. This work introduces a novel automata-based approach that provides an efficient memory mechanism and associated Markovian rewards suitable for RL frameworks. Our approach constructs a timed alternating automaton from the given STL specifications, augments the state space with automaton locations and clock valuations, and derives rewards from the automaton acceptance condition. We empirically demonstrate that our approach learns policies that achieve higher robustness scores and satisfaction rates than those learned by existing approaches using robustness-based rewards.

Abstract

Explore similar work

Reward Machines for Signal Temporal Logic

Tractable Reinforcement Learning for Full Class of Signal Temporal Logic Specifications Using Spatiotemporal Tube Reward

Reinforcement Learning with Symbolic Reward Machines