# On the (In)Tractability of Reinforcement Learning for LTL Objectives

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 47 references that are in the map.
- First posted on arXiv 24 Nov 2021.

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

- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (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)
- [Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications](https://mlsanity.com/paper/1807.06333/) (2018)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Mungojerrie: Reinforcement Learning of Linear-Time Objectives](https://mlsanity.com/paper/2106.09161/) (2021)

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

- [Provably Safe Reinforcement Learning: Conceptual Analysis, Survey, and Benchmarking](https://mlsanity.com/paper/2205.06750/) (2022)
- [Eventual Discounting Temporal Logic Counterfactual Experience Replay](https://mlsanity.com/paper/2303.02135/) (2023)
- [Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2411.00205/) (2024)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [LTLDoG: Satisfying Temporally-Extended Symbolic Constraints for Safe Diffusion-based Planning](https://mlsanity.com/paper/2405.04235/) (2024)
- [Compositional Policy Learning in Stochastic Control Systems with Formal Guarantees](https://mlsanity.com/paper/2312.01456/) (2023)
- [Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards](https://mlsanity.com/paper/2410.12175/) (2024)
- [A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs](https://mlsanity.com/paper/2310.12248/) (2023)
- [LTL-Constrained Policy Optimization with Cycle Experience Replay](https://mlsanity.com/paper/2404.11578/) (2024)
- [Diffusion Meets Options: Hierarchical Generative Skill Composition for Temporally-Extended Tasks](https://mlsanity.com/paper/2410.02389/) (2024)
- [Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives](https://mlsanity.com/paper/2202.02404/) (2022)
- [Provably Correct Automata Embeddings for Optimal Automata-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2503.05042/) (2025)
- [Hierarchical Reinforcement Learning with AI Planning Models](https://mlsanity.com/paper/2203.00669/) (2022)
- [Co-learning Planning and Control Policies Constrained by Differentiable Logic Specifications](https://mlsanity.com/paper/2303.01346/) (2023)
- [Regret-Free Reinforcement Learning for LTL Specifications](https://mlsanity.com/paper/2411.12019/) (2024)
- [Accelerated Learning with Linear Temporal Logic using Differentiable Simulation](https://mlsanity.com/paper/2506.01167/) (2025)
- [Decoupled Behavioral Cloning for Scalable Inductive Generalization in RL from Specifications](https://mlsanity.com/paper/2606.00838/) (2026)
- [Jaxolotl: A Unified High-Performance Benchmark Suite for LTL-Based Multi-Task RL](https://mlsanity.com/paper/2609.38065/) (2026)

## Abstract (arXiv)

In recent years, researchers have made significant progress in devising reinforcement-learning algorithms for optimizing linear temporal logic (LTL) objectives and LTL-like objectives. Despite these advancements, there are fundamental limitations to how well this problem can be solved. Previous studies have alluded to this fact but have not examined it in depth. In this paper, we address the tractability of reinforcement learning for general LTL objectives from a theoretical perspective. We formalize the problem under the probably approximately correct learning in Markov decision processes (PAC-MDP) framework, a standard framework for measuring sample complexity in reinforcement learning. In this formalization, we prove that the optimal policy for any LTL formula is PAC-MDP-learnable if and only if the formula is in the most limited class in the LTL hierarchy, consisting of formulas that are decidable within a finite horizon. Practically, our result implies that it is impossible for a reinforcement-learning algorithm to obtain a PAC-MDP guarantee on the performance of its learned policy after finitely many interactions with an unconstrained environment for LTL objectives that are not decidable within a finite horizon.