Research map / Bandits and online learning / RL theory and MDPs
Regret-Free Reinforcement Learning for Temporal Logic Specifications
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.
Proposes the first regret-free online RL algorithm for LTL controller synthesis on unknown finite MDPs, reducing general LTL to reach-avoid and learning the graph structure from a known minimum transition probability.
Problem
Learning an optimal controller for an unknown finite MDP with respect to LTL specifications, with guarantees on transient (during-learning) performance measured by regret rather than only asymptotic convergence.
Approach
An optimistic, interval-MDP-based online algorithm for reach-avoid specifications with episode-specific deadlines that split episodes into fast and slow, plus a reset mechanism for non-communicating MDPs; general LTL is reduced to reach-avoid via a DRA product once the MDP graph is learned from a known minimum transition probability.
Key results
- Regret of the reach-avoid algorithm is O(sqrt(K)) (sublinear, regret-free) with probability at least 1-2δ (Theorem 4.2).
- Full LTL synthesis algorithm (Alg. 4) achieves regret R(K)=O(sqrt(K)) with probability at least 1-δ (Theorem 5.1).
- In a gridworld reach-avoid experiment, the algorithm converges faster and in fewer episodes than the PAC-MDP algorithm of Perez et al. (2024).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ZeroReg for online policy synthesis | Unknown MDPs with reach-avoid specifications · Reach-avoid MDPs | regret: O(√K) | Helped |
| Reduce general LTL synthesis to reach-avoid synthesis using a learned graph | Unknown MDPs with general LTL specifications · General LTL specifications | regret: O(√K) | Helped |
Limitations
- Requires knowledge of a minimum nonzero transition probability p_min for graph learning.
- Regret bound scales with |S| and depends on the product state space from the DRA, which can be large.
- Empirical evaluation is limited to a gridworld with reach-avoid specifications.
Experimental setup
Benchmarks: gridworld reach-avoid environment
Metrics: regret sample complexity convergence
Baselines: Perez et al. 2024 PAC-MDP algorithm for LTL Tarbouriech et al. 2020
Builds on: UCRL2 Tarbouriech et al. 2020 goal-oriented RL Voloshin et al. 2022 PAC LTL Perez et al. 2024 PAC-MDP for LTL
Closest papers by meaning
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.88)
- Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards (NeurIPS 2024 · similarity 0.88)
- DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL (ICLR 2025 · similarity 0.88)
- Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs (NeurIPS 2024 · similarity 0.88)
- A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs (AAAI 2024 · 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.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.