🤖 AI

Reward Machines for Signal Temporal Logic

This paper proposes a novel automata-based approach that constructs a timed alternating automaton from Signal Temporal Logic specifications to generate Markovian rewards for reinforcement learning, effectively overcoming the state space expansion issues of traditional robustness-based methods and achieving higher policy satisfaction rates.

Original authors: Alper Kamil Bozkurt, Shangtong Zhang, Yuichi Motai

Published 2026-08-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alper Kamil Bozkurt, Shangtong Zhang, Yuichi Motai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a complex city. You don't want to write a rigid script for every possible traffic jam or pothole; instead, you want to give it a set of high-level rules, like "always stop at red lights" or "eventually reach the park, but do it within five minutes." This is the world of Signal Temporal Logic (STL). Think of STL as a very precise, mathematical language that lets humans describe these time-sensitive rules for machines that deal with real numbers, like speed, temperature, or position. It's not just about whether the robot did the right thing; it's about how well it did it. Did it stop just in time, or did it slam on the brakes? This "robustness" score is crucial because the real world is messy and noisy.

Now, imagine trying to teach this robot using Reinforcement Learning (RL). This is like training a dog with treats: the robot tries actions, gets a reward if it does well, and learns from its mistakes. The problem is that STL rules often depend on the entire history of what happened. For example, "if you leave the park, you must return within one minute." To know if the robot is failing, you have to remember exactly when it left. In standard RL, the robot usually only looks at the now. If you force it to remember every single step of its past to check the rules, the memory required explodes, making the learning process impossible for long or complex tasks. This paper tackles that exact headache: how to teach a robot complex, time-sensitive rules without drowning it in a sea of past memories.

The authors, Alper Kamil Bozkurt, Shangtong Zhang, and Yuichi Motai, propose a clever solution they call Reward Machines for Signal Temporal Logic. Instead of forcing the robot to memorize its entire history, they build a special "helper machine" (a Reward Machine) that acts like a smart, ticking stopwatch and a checklist combined. Here is how it works:

First, they translate the complex English-like rules (STL) into a visual map called an OCATA (One-Clock Alternating Timed Automaton). Imagine this map as a board game with different zones. Some zones are "good" (accepting), and some are "bad." The map has special rules: sometimes the robot has to choose one path (like a fork in the road), and sometimes it has to split into two versions of itself to check two things at once (like a clone army checking two doors).

The magic happens when they turn this map into a Reward Machine. As the robot moves through the real world, this machine tracks its progress on the map.

It keeps score: If the robot is in a "good" zone on the map, the machine gives it a small treat (a reward). If it's in a "bad" zone, it gets nothing.
It manages memory: Instead of the robot remembering every step, the machine remembers the state of the map. It keeps a list of "clones" (copies of the robot's state) whenever the rules get complicated. If a rule says "you must return within 1 minute," the machine starts a timer for that specific clone. If the timer runs out, that clone gets a "fail" signal.
It handles uncertainty: The real world is fuzzy. The machine doesn't just say "yes" or "no" to a rule; it calculates the probability of satisfying it, similar to how a weather forecast gives a percentage chance of rain. This makes the learning process smoother and more robust against noise.

By combining the robot's current situation with the state of this helper machine, the problem becomes simple again. The robot no longer needs to remember the past; it just needs to look at its current position and the helper machine's current checklist. This makes the learning process "Markovian," a fancy way of saying the future depends only on the present, which is exactly what standard AI learning tools need to work efficiently.

The researchers tested this idea in several simulated environments, ranging from a simple balancing pole (CartPole) to complex robotic arms (like the Fetch and Adroit robots). They compared their new method against older approaches that tried to teach robots by simply stacking up past observations (like looking at a stack of photos) or using complex memory networks (like a brain with a short-term memory).

The results were promising. In their simulations, the new STL-RM approach learned to follow the rules faster and more reliably than the older methods.

For simple rules, it performed just as well as the best competitors.
For complex rules involving strict time limits (like the "return within one minute" scenario), the older methods struggled significantly, often failing to learn the task at all. The STL-RM, however, mastered these tasks quickly.
The robots trained with this method didn't just satisfy the rules; they satisfied them with a larger "safety margin," meaning they were less likely to accidentally break the rules due to small errors or noise.

The authors note that while their method is much more efficient than trying to remember the whole history, it does have a limit. The "helper machine" has a finite amount of memory slots. If a task requires tracking dozens of simultaneous timers, the machine might run out of space. However, for the tasks they tested, it worked beautifully.

In short, this paper suggests that by building a specialized, memory-efficient "co-pilot" for the robot that translates complex time-based rules into simple rewards, we can teach autonomous systems to follow strict, real-world safety and timing constraints much more effectively than before. It's a step toward making AI agents that are not just smart, but also reliably obedient to the complex, time-sensitive rules of our physical world.

Technical Summary: Reward Machines for Signal Temporal Logic

Problem Statement

The paper addresses the challenge of synthesizing control policies for systems with unknown dynamics that must satisfy complex, real-time specifications defined in Signal Temporal Logic (STL). While STL provides a rigorous language for specifying real-valued, time-constrained behaviors and offers a quantitative "robustness" score, using this score directly as a reward in Reinforcement Learning (RL) is problematic.

The core difficulty lies in the history-dependent semantics of STL robustness. The satisfaction of an STL formula often depends on the entire execution trace (e.g., "eventually, the system must stay within a region for 5 seconds"). This violates the Markov property, a fundamental assumption in standard RL frameworks where rewards depend only on the current state. Existing solutions attempt to restore the Markov property by augmenting the state space with the entire history of visited states. However, this leads to an intractable state space explosion, particularly for long-horizon specifications with nested temporal operators. Alternatively, prior work restricts the logic to limited fragments of STL, sacrificing expressiveness. There is currently no model-free approach that handles full STL specifications while avoiding intractable history augmentation.

Methodology

The authors propose a novel automata-based framework that constructs Reward Machines (RMs) to provide efficient memory and Markovian rewards for RL agents. The methodology proceeds in three main stages:

1. Translation to One-Clock Alternating Timed Automata (OCATAs)

The authors model the control system as a Semi-Markov Decision Process (SMDP) to explicitly handle stochastic, real-valued time durations between observations. They translate the given STL specification into a One-Clock Alternating Timed Automaton (OCATA).

OCATA Structure: Unlike standard deterministic automata, OCATAs support disjunctive (existential/nondeterministic) and conjunctive (universal) transitions.
Semantics: Disjunctive transitions allow the automaton to "guess" a path to acceptance, while conjunctive transitions spawn multiple computation threads that must all satisfy the specification.
Acceptance: The automaton uses a Büchi acceptance condition, requiring that accepting locations be visited infinitely often.

2. Construction of STL-Reward Machines (STL-RMs)

The OCATA is converted into an STL-RM, which acts as a memory mechanism and reward generator.

Memory List: The RM maintains a list of memory entries, where each entry tracks a specific "copy" of the OCATA state (location and clock valuation) and its associated probability mass.
Handling Branching:
- Nondeterminism (Disjunction): Resolved by $\epsilon$ -actions selected by the RL agent.
- Conjunction: When a conjunctive transition occurs, the probability mass of the parent state is split among the child states. If a transition involves a clock reset, a new memory entry is created; otherwise, the probability mass is redistributed among existing entries.
Robustness Integration: To handle observation perturbations, the authors introduce a probabilistic interpretation of predicate satisfaction. Instead of binary true/false transitions, they use a Cumulative Distribution Function (CDF) to calculate the probability of satisfying a predicate based on the observed signal value. This creates "differentiable" transitions that encourage robust satisfaction.
Reward Generation: The RM outputs a scalar reward based on the probability mass residing in accepting locations. The reward function is designed such that maximizing the expected cumulative return corresponds to maximizing the probability of satisfying the Büchi condition.

3. Product Construction for Markovian RL

The SMDP and the STL-RM are composed into a Product MDP.

State Augmentation: The state space of the product MDP is the Cartesian product of the environment state, the time duration, and the RM's memory list.
Markovian Property: By including the memory list in the state, the reward function becomes Markovian (dependent only on the current augmented state), allowing the use of standard off-the-shelf RL algorithms (e.g., PPO).
Theoretical Guarantee: The authors prove that if a policy achieves the maximum expected return of 1 in the product MDP, it satisfies the original STL specification with probability 1.

Key Contributions

Novel Automata-Based Framework: The paper introduces a method to learn controllers from full STL specifications by compiling them into OCATAs and subsequently into Reward Machines. This approach models stochastic systems as SMDPs and adopts event-based STL semantics.
Efficient Memory and Markovian Rewards: The proposed STL-RM provides a compact memory mechanism (tracking automaton locations and clock valuations) that induces Markovian rewards. This avoids the intractable state expansion associated with full history augmentation while maintaining compatibility with standard RL algorithms.
Robustness-Aware Transitions: The framework incorporates robustness to observation perturbations by using probabilistic transitions derived from differentiable reward concepts, rather than relying solely on binary satisfaction.
Theoretical and Empirical Validation: The authors formalize that maximizing the cumulative reward in their framework guarantees specification satisfaction with probability 1. Empirically, they demonstrate that their approach learns policies faster and achieves higher satisfaction rates and robustness scores compared to history-based baselines (observation stacking and recurrent networks) across various control environments.

Experimental Results

The authors evaluated STL-RM on five benchmark environments (CartPole, Reacher, Pusher, Fetch, Adroit) using two types of STL specifications:

Partial Specification: Unbounded temporal operators (sequencing and safety).
Full Specification: Includes bounded-time stability requirements (requiring the system to return to a central region within a specific time window).

Findings:

Performance: STL-RM (and its discrete variant) consistently outperformed baselines (Stacking with various window sizes and LSTM-based recurrent policies) in terms of satisfaction rates and robustness scores, particularly on the Full Specification.
Scalability: While baselines struggled significantly with the bounded-time requirements of the full specification (due to the difficulty of learning temporal context from raw history), STL-RM converged to near-optimal policies.
Robustness: The continuous, robustness-aware variant of STL-RM generally achieved higher robustness scores than the discrete variant, suggesting that probabilistic transitions encourage policies that satisfy specifications with larger safety margins.

Significance and Claims

The paper claims to solve a critical bottleneck in model-free control synthesis: the inability of standard RL to handle the history-dependent nature of full STL specifications without incurring prohibitive computational costs.

Expressiveness: Unlike prior work restricted to specific fragments of STL, this approach supports full STL with arbitrarily nested temporal operators.
Efficiency: By using automata-based memory rather than raw history stacking, the method avoids the "state explosion" problem, making it feasible for long-horizon tasks.
Practicality: The framework is compatible with existing RL tools (e.g., PPO) and does not require a system model.
Limitations: The authors modestly acknowledge that the memory capacity is finite. In scenarios with many simultaneous temporal obligations, the memory list could grow large, potentially requiring pruning or more compact representations (e.g., interval-based) in future work.

The paper concludes that automata-based reward design is a promising direction for synthesizing controllers from expressive temporal logic specifications in complex, model-free environments.