# Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 57 references that are in the map.
- First posted on arXiv 4 Feb 2022.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Reinforcement Learning for Safety-Critical Control under Model Uncertainty, using Control Lyapunov Functions and Control Barrier Functions](https://mlsanity.com/paper/2004.07584/) (2020)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/1801.08099/) (2018)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Tractable Reinforcement Learning of Signal Temporal Logic Objectives](https://mlsanity.com/paper/2001.09467/) (2020)
- [A Policy Search Method For Temporal Logic Specified Reinforcement Learning Tasks](https://mlsanity.com/paper/1709.09611/) (2017)
- [Episodic Learning with Control Lyapunov Functions for Uncertain Robotic Systems](https://mlsanity.com/paper/1903.01577/) (2019)
- [Recurrent Neural Network Controllers for Signal Temporal Logic Specifications Subject to Safety Constraints](https://mlsanity.com/paper/2009.11468/) (2020)
- [On the (In)Tractability of Reinforcement Learning for LTL Objectives](https://mlsanity.com/paper/2111.12679/) (2021)
- [Formal Controller Synthesis for Continuous-Space MDPs via Model-Free Reinforcement Learning](https://mlsanity.com/paper/2003.00712/) (2020)
- [Probabilistic Motion Planning under Temporal Tasks and Soft Constraints](https://mlsanity.com/paper/1706.05209/) (2017)
- [Reward Shaping for Reinforcement Learning with Omega-Regular Objectives](https://mlsanity.com/paper/2001.05977/) (2020)
- [Synthesis of Discounted-Reward Optimal Policies for Markov Decision Processes Under Linear Temporal Logic Specifications](https://mlsanity.com/paper/2011.00632/) (2020)
- [An Algebraic Framework for Runtime Verification](https://mlsanity.com/paper/1802.03775/) (2018)

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

- [ConformalNL2LTL: Translating Natural Language Instructions into Temporal Logic Formulas with Conformal Correctness Guarantees](https://mlsanity.com/paper/2504.21022/) (2025)
- [Exploiting Transformer in Sparse Reward Reinforcement Learning for Interpretable Temporal Logic Motion Planning](https://mlsanity.com/paper/2209.13220/) (2022)
- [Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration](https://mlsanity.com/paper/2410.12136/) (2024)
- [Safety-Aware Task Composition for Discrete and Continuous Reinforcement Learning](https://mlsanity.com/paper/2306.17033/) (2023)
- [Searching for Optimal Runtime Assurance via Reachability and Reinforcement Learning](https://mlsanity.com/paper/2310.04288/) (2023)
- [A Reward-Petri-Net Interpretation of Temporal Behavior Trees](https://mlsanity.com/paper/2606.21350/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) is a popular approach for robotic path planning in uncertain environments. However, the control policies trained for an RL agent crucially depend on user-defined, state-based reward functions. Poorly designed rewards can lead to policies that do get maximal rewards but fail to satisfy desired task objectives or are unsafe. There are several examples of the use of formal languages such as temporal logics and automata to specify high-level task specifications for robots (in lieu of Markovian rewards). Recent efforts have focused on inferring state-based rewards from formal specifications; here, the goal is to provide (probabilistic) guarantees that the policy learned using RL (with the inferred rewards) satisfies the high-level formal specification. A key drawback of several of these techniques is that the rewards that they infer are sparse: the agent receives positive rewards only upon completion of the task and no rewards otherwise. This naturally leads to poor convergence properties and high variance during RL. In this work, we propose using formal specifications in the form of symbolic automata: these serve as a generalization of both bounded-time temporal logic-based specifications as well as automata. Furthermore, our use of symbolic automata allows us to define non-sparse potential-based rewards which empirically shape the reward surface, leading to better convergence during RL. We also show that our potential-based rewarding strategy still allows us to obtain the policy that maximizes the satisfaction of the given specification.