mlsanityData to 7 Oct 2026

Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives

arXiv 2202.02404 ↗First posted 4 Feb 2022cs.AI cs.LO cs.ROcited by 6

Not on the map. Why?

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.

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

Builds on

26 of 57 references.

References · 26

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  3. 2016Concrete Problems in AI Safetycited by 1,582
  4. 2017Safe Reinforcement Learning via Shieldingcited by 427
  5. 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 278
  6. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 183
  7. 2016Reinforcement Learning With Temporal Logic Rewardscited by 114
  8. 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 74
  9. 2020A Composable Specification Language for Reinforcement Learning Taskscited by 68
  10. 2016Q-Learning for Robust Satisfaction of Signal Temporal Logic Specificationscited by 65
  11. 2021Compositional Reinforcement Learning from Logical Specificationscited by 65
  12. 2020Reinforcement Learning for Safety-Critical Control under Model Uncertainty, using Control Lyapunov Functions and Control Barrier Functionscited by 61
14 more
  1. 2014Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraintscited by 53
  2. 2018Logically-Constrained Reinforcement Learningcited by 50
  3. 2014A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specificationscited by 49
  4. 2019Reinforcement Learning with Non-Markovian Rewardscited by 45
  5. 2020Tractable Reinforcement Learning of Signal Temporal Logic Objectivescited by 21
  6. 2017A Policy Search Method For Temporal Logic Specified Reinforcement Learning Taskscited by 19
  7. 2019Episodic Learning with Control Lyapunov Functions for Uncertain Robotic Systemscited by 19
  8. 2020Recurrent Neural Network Controllers for Signal Temporal Logic Specifications Subject to Safety Constraintscited by 18
  9. 2021On the (In)Tractability of Reinforcement Learning for LTL Objectivescited by 18
  10. 2020Formal Controller Synthesis for Continuous-Space MDPs via Model-Free Reinforcement Learningcited by 15
  11. 2017Probabilistic Motion Planning under Temporal Tasks and Soft Constraintscited by 9
  12. 2020Reward Shaping for Reinforcement Learning with Omega-Regular Objectivescited by 4
  13. 2020Synthesis of Discounted-Reward Optimal Policies for Markov Decision Processes Under Linear Temporal Logic Specificationscited by 3
  14. 2018An Algebraic Framework for Runtime Verificationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 1; 2025: 1; 2026: 1.

6 papers.

  1. 2022Exploiting Transformer in Sparse Reward Reinforcement Learning for Interpretable Temporal Logic Motion Planningcited by 10
  2. 2025ConformalNL2LTL: Translating Natural Language Instructions into Temporal Logic Formulas with Conformal Correctness Guaranteescited by 9
  3. 2024Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Explorationcited by 3
  4. 2023Safety-Aware Task Composition for Discrete and Continuous Reinforcement Learningcited by 0
  5. 2023Searching for Optimal Runtime Assurance via Reachability and Reinforcement Learningcited by 0
  6. 2026A Reward-Petri-Net Interpretation of Temporal Behavior Treescited by 0