# Reward Machines for Signal Temporal Logic

arXiv: https://arxiv.org/abs/2608.13625 · HTML: https://mlsanity.com/paper/2608.13625/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 46 of its 89 references that are in the map.
- First posted on arXiv 13 Aug 2026.

## Builds on (most cited first, 30 of 46)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [A Tour of Reinforcement Learning: The View from Continuous Control](https://mlsanity.com/paper/1806.09460/) (2018)
- [Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees](https://mlsanity.com/paper/1909.05304/) (2019)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning](https://mlsanity.com/paper/1909.07299/) (2019)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [Backpropagation through Signal Temporal Logic Specifications: Infusing Logical Structure into Gradient-Based Methods](https://mlsanity.com/paper/2008.00097/) (2020)
- [Robust Online Monitoring of Signal Temporal Logic](https://mlsanity.com/paper/1506.08234/) (2015)
- [On Robustness Metrics for Learning STL Tasks](https://mlsanity.com/paper/2003.06041/) (2020)
- [Tractable Reinforcement Learning of Signal Temporal Logic Objectives](https://mlsanity.com/paper/2001.09467/) (2020)
- [A Smooth Robustness Measure of Signal Temporal Logic for Symbolic Control](https://mlsanity.com/paper/2006.05239/) (2020)
- [Arithmetic-Geometric Mean Robustness for Control from Signal Temporal Logic Specifications](https://mlsanity.com/paper/1903.05186/) (2019)
- [Control from Signal Temporal Logic Specifications with Smooth Cumulative Quantitative Semantics](https://mlsanity.com/paper/1904.11611/) (2019)
- [Mixed-Integer Programming for Signal Temporal Logic with Fewer Binary Variables](https://mlsanity.com/paper/2204.06367/) (2022)
- [Signal Temporal Logic Neural Predictive Control](https://mlsanity.com/paper/2309.05131/) (2023)
- [Formal Synthesis of Controllers for Safety-Critical Autonomous Systems: Developments and Challenges](https://mlsanity.com/paper/2402.13075/) (2024)
- [Model-Free Reinforcement Learning for Optimal Control of MarkovDecision Processes Under Signal Temporal Logic Specifications](https://mlsanity.com/paper/2109.13377/) (2021)
- [Deep reinforcement learning under signal temporal logic constraints using Lagrangian relaxation](https://mlsanity.com/paper/2201.08504/) (2022)
- [Funnel-based Reward Shaping for Signal Temporal Logic Tasks in Reinforcement Learning](https://mlsanity.com/paper/2212.03181/) (2022)
- [Model-Free Reinforcement Learning for Stochastic Games with Linear Temporal Logic Objectives](https://mlsanity.com/paper/2010.01050/) (2020)
- [Event-Based Signal Temporal Logic Synthesis for Single and Multi-Robot Tasks](https://mlsanity.com/paper/2011.00370/) (2020)
- [Signal Temporal Logic Control Synthesis among Uncontrollable Dynamic Agents with Conformal Prediction](https://mlsanity.com/paper/2312.04242/) (2023)
- [Learning Robust and Correct Controllers from Signal Temporal Logic Specifications Using BarrierNet](https://mlsanity.com/paper/2304.06160/) (2023)
- [Model-Free Learning of Safe yet Effective Controllers](https://mlsanity.com/paper/2103.14600/) (2021)
- [Reactive and Risk-Aware Control for Signal Temporal Logic](https://mlsanity.com/paper/2108.13490/) (2021)
- [An STL-based Approach to Resilient Control for Cyber-Physical Systems](https://mlsanity.com/paper/2211.02794/) (2022)
- [Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration](https://mlsanity.com/paper/2410.12136/) (2024)
- [Robust Control for Signal Temporal Logic Specifications using Average Space Robustness](https://mlsanity.com/paper/1607.07019/) (2016)
- [Prescribed Performance Control for Signal Temporal Logic Specifications](https://mlsanity.com/paper/1703.07094/) (2017)

## Abstract (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.