# Policy Synthesis and Reinforcement Learning for Discounted LTL

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 45 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [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)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (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)
- [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)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Transfer of Temporal Logic Formulas in Reinforcement Learning](https://mlsanity.com/paper/1909.04256/) (2019)
- [Modular Deep Reinforcement Learning with Temporal Logic Specifications](https://mlsanity.com/paper/1909.11591/) (2019)
- [Faster Statistical Model Checking for Unbounded Temporal Properties](https://mlsanity.com/paper/1504.05739/) (2015)
- [Specification-Guided Learning of Nash Equilibria with High Social Welfare](https://mlsanity.com/paper/2206.03348/) (2022)
- [Discounting in LTL](https://mlsanity.com/paper/1406.4249/) (2014)
- [LTLf Synthesis on Probabilistic Systems](https://mlsanity.com/paper/2009.10883/) (2020)

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

- [DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL](https://mlsanity.com/paper/2410.04631/) (2024)
- [Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2411.00205/) (2024)
- [Dynamic Model Predictive Shielding for Provably Safe Reinforcement Learning](https://mlsanity.com/paper/2405.13863/) (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)
- [Provably Correct Automata Embeddings for Optimal Automata-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2503.05042/) (2025)
- [Pretrained Embeddings as a Behavior Specification Mechanism](https://mlsanity.com/paper/2503.02012/) (2025)
- [Integrating Explanations in Learning LTL Specifications from Demonstrations](https://mlsanity.com/paper/2404.02872/) (2024)
- [Runtime Monitoring of Perception-Based Autonomous Systems via Embedding Temporal Logic](https://mlsanity.com/paper/2605.12651/) (2026)
- [Hyperproperty-Constrained Secure Reinforcement Learning](https://mlsanity.com/paper/2508.00106/) (2025)
- [Physics-Informed Reward Machines](https://mlsanity.com/paper/2508.14093/) (2025)
- [COOL-MC: Verifying and Explaining RL Policies for Platelet Inventory Management](https://mlsanity.com/paper/2603.02396/) (2026)
- [COOL-MC: Verifying and Explaining RL Policies for Multi-bridge Network Maintenance](https://mlsanity.com/paper/2603.07546/) (2026)
- [Live LTL Progress Tracking: Towards Task-Based Exploration](https://mlsanity.com/paper/2604.17106/) (2026)

## Abstract (arXiv)

The difficulty of manually specifying reward functions has led to an interest in using linear temporal logic (LTL) to express objectives for reinforcement learning (RL). However, LTL has the downside that it is sensitive to small perturbations in the transition probabilities, which prevents probably approximately correct (PAC) learning without additional assumptions. Time discounting provides a way of removing this sensitivity, while retaining the high expressivity of the logic. We study the use of discounted LTL for policy synthesis in Markov decision processes with unknown transition probabilities, and show how to reduce discounted LTL to discounted-sum reward via a reward machine when all discount factors are identical.