# Model-Free Reinforcement Learning for Optimal Control of MarkovDecision Processes Under Signal Temporal Logic Specifications

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 17 references that are in the map.
- First posted on arXiv 27 Sep 2021.

## Builds on (most cited first, 10 of 10)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [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)
- [On-Line Monitoring for Temporal Logic Robustness](https://mlsanity.com/paper/1408.0045/) (2014)

## Built on by (most cited first, 10 of 10)

- [Deep reinforcement learning under signal temporal logic constraints using Lagrangian relaxation](https://mlsanity.com/paper/2201.08504/) (2022)
- [Follow The Rules: Online Signal Temporal Logic Tree Search for Guided Imitation Learning in Stochastic Domains](https://mlsanity.com/paper/2209.13737/) (2022)
- [Learning Robust and Correct Controllers from Signal Temporal Logic Specifications Using BarrierNet](https://mlsanity.com/paper/2304.06160/) (2023)
- [Zero-Shot Trajectory Planning for Signal Temporal Logic Tasks](https://mlsanity.com/paper/2501.13457/) (2025)
- [Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specifications](https://mlsanity.com/paper/2311.17059/) (2023)
- [Hyperproperty-Constrained Secure Reinforcement Learning](https://mlsanity.com/paper/2508.00106/) (2025)
- [Control Synthesis of Cyber-Physical Systems for Real-Time Specifications through Causation-Guided Reinforcement Learning](https://mlsanity.com/paper/2510.07715/) (2025)
- [Feasibility-aware Learning of Robust Temporal Logic Controllers using BarrierNet](https://mlsanity.com/paper/2512.06973/) (2025)
- [Zero-Shot Signal Temporal Logic Planning with Disjunctive Branch Selection in Dynamic Semantic Maps](https://mlsanity.com/paper/2605.01222/) (2026)
- [Reward Machines for Signal Temporal Logic](https://mlsanity.com/paper/2608.13625/) (2026)

## Abstract (arXiv)

We present a model-free reinforcement learning algorithm to find an optimal policy for a finite-horizon Markov decision process while guaranteeing a desired lower bound on the probability of satisfying a signal temporal logic (STL) specification. We propose a method to effectively augment the MDP state space to capture the required state history and express the STL objective as a reachability objective. The planning problem can then be formulated as a finite-horizon constrained Markov decision process (CMDP). For a general finite horizon CMDP problem with unknown transition probability, we develop a reinforcement learning scheme that can leverage any model-free RL algorithm to provide an approximately optimal policy out of the general space of non-stationary randomized policies. We illustrate the effectiveness of our approach in the context of robotic motion planning for complex missions under uncertainty and performance objectives.