# Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 26 of its 55 references that are in the map.
- First posted on arXiv 16 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

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

- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [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)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Boltzmann Exploration Done Right](https://mlsanity.com/paper/1705.10257/) (2017)
- [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)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [Certified Reinforcement Learning with Logic Guidance](https://mlsanity.com/paper/1902.00778/) (2019)
- [Reinforcement Learning with Probabilistic Guarantees for Autonomous Driving](https://mlsanity.com/paper/1904.07189/) (2019)
- [STyLuS*: A Temporal Logic Optimal Control Synthesis Algorithm for Large-Scale Multi-Robot Systems](https://mlsanity.com/paper/1809.08345/) (2018)
- [Computational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning](https://mlsanity.com/paper/2107.03961/) (2021)
- [Formal Controller Synthesis for Continuous-Space MDPs via Model-Free Reinforcement Learning](https://mlsanity.com/paper/2003.00712/) (2020)
- [Optimal Probabilistic Motion Planning with Potential Infeasible LTL Constraints](https://mlsanity.com/paper/2007.14325/) (2020)
- [Perception-Based Temporal Logic Planning in Uncertain Semantic Maps](https://mlsanity.com/paper/2012.10490/) (2020)
- [Overcoming Exploration: Deep Reinforcement Learning for Continuous Control in Cluttered Environments from Temporal Logic Specifications](https://mlsanity.com/paper/2201.12231/) (2022)
- [LCRL: Certified Policy Synthesis via Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.10341/) (2022)
- [Probabilistic Motion Planning under Temporal Tasks and Soft Constraints](https://mlsanity.com/paper/1706.05209/) (2017)
- [Accelerated Reinforcement Learning for Temporal Logic Control Objectives](https://mlsanity.com/paper/2205.04424/) (2022)
- [Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives](https://mlsanity.com/paper/2202.02404/) (2022)
- [Learning Minimally-Violating Continuous Control for Infeasible Linear Temporal Logic Specifications](https://mlsanity.com/paper/2210.01162/) (2022)
- [Learning Optimal Strategies for Temporal Tasks in Stochastic Games](https://mlsanity.com/paper/2102.04307/) (2021)
- [On the Uniqueness of Solution for the Bellman Equation of LTL Objectives](https://mlsanity.com/paper/2404.05074/) (2024)

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

- [ConformalNL2LTL: Translating Natural Language Instructions into Temporal Logic Formulas with Conformal Correctness Guarantees](https://mlsanity.com/paper/2504.21022/) (2025)
- [Bridging Deep Reinforcement Learning and Motion Planning for Model-Free Navigation in Cluttered Environments](https://mlsanity.com/paper/2504.07283/) (2025)
- [A Reward-Petri-Net Interpretation of Temporal Behavior Trees](https://mlsanity.com/paper/2606.21350/) (2026)
- [Exact Model-Free Policy Iteration for Co-safe LTL Planning](https://mlsanity.com/paper/2608.05047/) (2026)
- [Reward Machines for Signal Temporal Logic](https://mlsanity.com/paper/2608.13625/) (2026)

## Abstract (arXiv)

This paper addresses the problem of learning optimal control policies for systems with uncertain dynamics and high-level control objectives specified as Linear Temporal Logic (LTL) formulas. Uncertainty is considered in the workspace structure and the outcomes of control decisions giving rise to an unknown Markov Decision Process (MDP). Existing reinforcement learning (RL) algorithms for LTL tasks typically rely on exploring a product MDP state-space uniformly (using e.g., an ε-greedy policy) compromising sample-efficiency. This issue becomes more pronounced as the rewards get sparser and the MDP size or the task complexity increase. In this paper, we propose an accelerated RL algorithm that can learn control policies significantly faster than competitive approaches. Its sample-efficiency relies on a novel task-driven exploration strategy that biases exploration towards directions that may contribute to task satisfaction. We provide theoretical analysis and extensive comparative experiments demonstrating the sample-efficiency of the proposed method. The benefit of our method becomes more evident as the task complexity or the MDP size increases.