Research map / Reinforcement learning / MDPs and planning
Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that omega-regular and LTL RL objectives can be reduced in an optimality-preserving way to limit-average reward machines (with unknown transitions), and that the resulting average-reward RL problem can be solved in the limit via a sequence of PAC discounted-reward problems.
Problem
Reinforcement learning with LTL and omega-regular objectives in MDPs with unknown transition probabilities lacks provably optimal learning guarantees, since neither LTL nor limit-average objectives are PAC learnable.
Approach
Translates omega-regular objectives (via a deterministic Rabin automaton) into limit-average reward machines that track the DRA state, the set of observed transitions, and a status flag, rewarding accepting simple end components; then reduces limit-average RL to a sequence of discounted PAC RL problems with increasing discount factors and decreasing epsilon and delta.
Key results
- Shows a negative result: no reward function over S x A x S can be optimality-preserving for omega-regular objectives, even with known transitions.
- Main theorem: an optimality-preserving translation from omega-regular objectives to limit-average reward machines exists, with unknown transitions, though its size is exponential in general.
- Shows almost-sure convergence in the limit: a sequence of PAC discounted RL solutions with gamma_k=1-1/k, epsilon_k=1/k, delta_k=1/k^2 yields limit-average optimal policies eventually.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add finite memory with a reward machine instead of using a memoryless reward function | Translation of ω-regular objectives to limit-average rewards · General finite MDPs with unknown transition probabilities | preservation of acceptance-optimal policies | Helped |
| use a memoryless reward function without reward-machine state | Translation of ω-regular objectives to limit-average rewards · General MDPs | preservation of acceptance-optimal policies | Hurt |
| solve a sequence of increasingly accurate discounted-sum problems with discount factors approaching 1 | Limit-average reward reinforcement learning · General MDPs, including multichain MDPs | asymptotic limit-average optimality | Helped |
Surprising findings
- Optimality-preserving translation from omega-regular objectives to simple reward functions is impossible even when transition probabilities are fully known.
Limitations
- Only finite state and action MDPs with fully observable states are considered.
- General translation is exponential in size; conjectured minimal only in the known-support case.
- No finite-time complexity guarantees since average-reward RL is not PAC learnable.
Experimental setup
Builds on: reward machines deterministic Rabin automata product MDP PAC discounted RL
Closest papers by meaning
- A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs (AAAI 2024 · similarity 0.92)
- On the Expressivity of Objective-Specification Formalisms in Reinforcement Learning (ICLR 2024 · similarity 0.89)
- DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL (ICLR 2025 · similarity 0.88)
- Regret-Free Reinforcement Learning for Temporal Logic Specifications (ICML 2025 · similarity 0.88)
- One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Multi-objective Linear Reinforcement Learning with Lexicographic Rewards (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.