Reward Machines for Signal Temporal Logic

• URL: http://arxiv.org/abs/2608.13625v1
• Date: Thu, 13 Aug 2026 04:25:07 GMT
• Title: Reward Machines for Signal Temporal Logic
• Abstract summary: Signal temporal logic (STL) provides a formal language for specifying real-time properties of real-valued observations.<n>Prior work uses STL robustness scores as rewards in reinforcement learning (RL) to obtain control policies satisfying given specifications.<n>This work introduces a novel automata-based approach that provides an efficient memory mechanism and associated Markovian rewards suitable for RL frameworks.
• Score: 17.49671322104596
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Specification-Aware Distribution Shaping for Robotics Foundation Models [0.0]
  We propose a specification-aware action distribution optimization framework that enforces a broad class of Signal Temporal Logic (STL) constraints during execution of a pretrained robotics foundation model without modifying its parameters.<n>We validate the proposed framework in simulation using a state-of-the-art robotics foundation model across multiple environments and complex specifications.
  arXiv  Detail & Related papers  (2026-03-18T17:36:46Z)
• HIPO: Instruction Hierarchy via Constrained Reinforcement Learning [57.40686733111483]
  textscHIPO is a novel alignment framework that formulates HIF as a Constrained Markov Decision Process.<n>textscHIPO elevates system prompts from mere input context to strict algorithmic boundaries.
  arXiv  Detail & Related papers  (2026-03-17T06:12:41Z)
• Beyond Short-Horizon: VQ-Memory for Robust Long-Horizon Manipulation in Non-Markovian Simulation Benchmarks [96.60530830276281]
  RuleSafe is a new articulated manipulation benchmark built upon a scalable LLM-aided simulation framework.<n>VQ-Memory is a compact and structured temporal representation that uses vector-quantized variational autoencoders.
  arXiv  Detail & Related papers  (2026-03-10T11:13:54Z)
• Semantically Labelled Automata for Multi-Task Reinforcement Learning with LTL Instructions [61.479946958462754]
  We study multi-task reinforcement learning (RL), a setting in which an agent learns a single, universal policy.<n>We present a novel task embedding technique leveraging a new generation of semantic translations-to-automata.
  arXiv  Detail & Related papers  (2026-02-06T14:46:27Z)
• Reinforcement learning with timed constraints for robotics motion planning [0.5436465344481877]
  This paper presents a unified automata-based framework for synthesizing policies in both Markov Decision Processes (MDPs) and Partially Observable Markov Decision Processes (POMDPs)<n>A simple yet expressive reward structure enforces temporal correctness while allowing additional performance objectives.<n>Results demonstrate that the proposed framework consistently learns policies that satisfy strict time-bounded requirements under transitions, scales to larger state spaces, and remains effective in partially observable environments.
  arXiv  Detail & Related papers  (2025-12-31T19:43:44Z)
• Directed Exploration in Reinforcement Learning from Linear Temporal Logic [59.707408697394534]
  Linear temporal logic (LTL) is a powerful language for task specification in reinforcement learning.<n>We show that the synthesized reward signal remains fundamentally sparse, making exploration challenging.<n>We show how better exploration can be achieved by further leveraging the specification and casting its corresponding Limit Deterministic B"uchi Automaton (LDBA) as a Markov reward process.
  arXiv  Detail & Related papers  (2024-08-18T14:25:44Z)
• Large Language Models as General Pattern Machines [64.75501424160748]
  We show that pre-trained large language models (LLMs) are capable of autoregressively completing complex token sequences. Surprisingly, pattern completion proficiency can be partially retained even when the sequences are expressed using tokens randomly sampled from the vocabulary. In this work, we investigate how these zero-shot capabilities may be applied to problems in robotics.
  arXiv  Detail & Related papers  (2023-07-10T17:32:13Z)
• STL-Based Synthesis of Feedback Controllers Using Reinforcement Learning [8.680676599607125]
  Deep Reinforcement Learning (DRL) has the potential to be used for synthesizing feedback controllers (agents) for various complex systems with unknown dynamics. In RL, the reward function plays a crucial role in specifying the desired behaviour of these agents. We provide a systematic way of generating rewards in real-time by using the quantitative semantics of Signal Temporal Logic (STL) We evaluate our STL-based reinforcement learning mechanism on several complex continuous control benchmarks and compare our STL semantics with those available in the literature in terms of their efficacy in synthesizing the controller agent.
  arXiv  Detail & Related papers  (2022-12-02T08:31:46Z)
• Funnel-based Reward Shaping for Signal Temporal Logic Tasks in Reinforcement Learning [0.0]
  We propose a tractable reinforcement learning algorithm to learn a controller that enforces Signal Temporal Logic (STL) specifications. We demonstrate the utility of our approach on several STL tasks using different environments.
  arXiv  Detail & Related papers  (2022-11-30T19:38:21Z)
• Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic [59.94347858883343]
  This paper investigates the motion planning of autonomous dynamical systems modeled by Markov decision processes (MDP) The novelty is to design an embedded product MDP (EP-MDP) between the LDGBA and the MDP. The proposed LDGBA-based reward shaping and discounting schemes for the model-free reinforcement learning (RL) only depend on the EP-MDP states.
  arXiv  Detail & Related papers  (2021-02-24T01:11:25Z)
• Model-based Reinforcement Learning from Signal Temporal Logic Specifications [0.17205106391379021]
  We propose expressing desired high-level robot behavior using a formal specification language known as Signal Temporal Logic (STL) as an alternative to reward/cost functions. The proposed algorithm is empirically evaluated on simulations of robotic system such as a pick-and-place robotic arm, and adaptive cruise control for autonomous vehicles.
  arXiv  Detail & Related papers  (2020-11-10T07:31:47Z)
• Certified Reinforcement Learning with Logic Guidance [78.2286146954051]
  We propose a model-free RL algorithm that enables the use of Linear Temporal Logic (LTL) to formulate a goal for unknown continuous-state/action Markov Decision Processes (MDPs) The algorithm is guaranteed to synthesise a control policy whose traces satisfy the specification with maximal probability.
  arXiv  Detail & Related papers  (2019-02-02T20:09:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.