# Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards

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

## Key facts

- Cited by 14 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 16 of its 45 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, 16 of 16)

- [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)
- [On the Expressivity of Markov Reward](https://mlsanity.com/paper/2111.00876/) (2021)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [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)
- [Certified Reinforcement Learning with Logic Guidance](https://mlsanity.com/paper/1902.00778/) (2019)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [Eventual Discounting Temporal Logic Counterfactual Experience Replay](https://mlsanity.com/paper/2303.02135/) (2023)
- [On the (In)Tractability of Reinforcement Learning for LTL Objectives](https://mlsanity.com/paper/2111.12679/) (2021)
- [Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guarantees](https://mlsanity.com/paper/2305.01381/) (2023)
- [Optimal Probabilistic Motion Planning with Potential Infeasible LTL Constraints](https://mlsanity.com/paper/2007.14325/) (2020)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs](https://mlsanity.com/paper/2310.12248/) (2023)

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

- [HypRL: Reinforcement Learning of Control Policies for Hyperproperties](https://mlsanity.com/paper/2504.04675/) (2025)
- [Accelerated Learning with Linear Temporal Logic using Differentiable Simulation](https://mlsanity.com/paper/2506.01167/) (2025)
- [Zero-Shot Instruction Following in RL via Structured LTL Representations](https://mlsanity.com/paper/2602.14344/) (2026)
- [SpecRLBench: A Benchmark for Generalization in Specification-Guided Reinforcement Learning](https://mlsanity.com/paper/2604.24729/) (2026)
- [Average Reward Reinforcement Learning for Omega-Regular and Mean-Payoff Objectives](https://mlsanity.com/paper/2505.15693/) (2025)
- [Zero-Shot Instruction Following in RL via Structured LTL Representations](https://mlsanity.com/paper/2512.02633/) (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)
- [Stochastic Minimum-Cost Reach-Avoid Reinforcement Learning](https://mlsanity.com/paper/2605.11975/) (2026)
- [Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality](https://mlsanity.com/paper/2605.24740/) (2026)
- [HyPOLE: Hyperproperty-Guided Multi-Agent Reinforcement Learning under Partial Observation](https://mlsanity.com/paper/2606.30966/) (2026)
- [Exact Model-Free Policy Iteration for Co-safe LTL Planning](https://mlsanity.com/paper/2608.05047/) (2026)
- [Q-Learning for Reachability in MEC-Free MDPs](https://mlsanity.com/paper/2610.01781/) (2026)

## Abstract (arXiv)

Linear temporal logic (LTL) and, more generally, ω-regular objectives are alternatives to the traditional discount sum and average reward objectives in reinforcement learning (RL), offering the advantage of greater comprehensibility and hence explainability. In this work, we study the relationship between these objectives. Our main result is that each RL problem for ω-regular objectives can be reduced to a limit-average reward problem in an optimality-preserving fashion, via (finite-memory) reward machines. Furthermore, we demonstrate the efficacy of this approach by showing that optimal policies for limit-average problems can be found asymptotically by solving a sequence of discount-sum problems approximately. Consequently, we resolve an open problem: optimal policies for LTL and ω-regular objectives can be learned asymptotically.