Research map / Reinforcement learning / MDPs and planning
A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs
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.
Introduces ω-PAC, a model-based PAC RL algorithm for LTL and ω-regular objectives in MDPs, using a new ε-recurrence time to bound the trajectory length needed for finite samples to reflect infinite behavior.
Problem
PAC learning of policies maximizing LTL / omega-regular satisfaction probability in MDPs, where infinite-horizon undiscounted objectives are sensitive to small transition-probability changes so state/action counts alone do not yield polynomial sample bounds.
Approach
Defines the ε-recurrence time (the trajectory length after which the recurrent BSCC behavior of a finite trajectory matches its infinite extension with prob. ≥1-ε) and uses it, with an optimistic R-MAX-style model that treats unknown state-action pairs as accepting sinks, to get a model-based PAC algorithm whose sample complexity is polynomial in |S|, |A|, T, 1/ε, 1/δ.
Key results
- On the gridworld (|S|=12, |A|=4, T=19, ε=1/20, δ=1/10), ω-PAC takes about 40 minutes and no run produced a non-optimal policy under the theorem's k.
- On the chain example (|S|=8, |A|=2, T=8), small k typically suffices, with learned policies' satisfaction probabilities examined over 20 runs for different k.
- Theoretical sample complexity is C = Õ(|S|^3 |A| T^3 / ε^4), and the policy is 6ε-optimal with probability ≥1-δ.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the theorem-suggested threshold k | ω-PAC · Gridworld example | runtime: approximately $40$ minutes | Hurt |
| Use smaller k values rather than the theorem-suggested threshold | ω-PAC · Chain example | probability of satisfaction | No clear effect |
Surprising findings
- The k prescribed by theory appears needlessly large in practice; a small k typically suffices in the chain experiments.
Limitations
- Bounds on k and sample complexity are loose; the theoretical k is large (Õ(|S|^2 T^2/ε^2)).
- Requires knowledge of the ε-recurrence time T (or an upper bound derived from p_min), which is a structural parameter of the MDP.
- Restricted to acceptance conditions admitting positional optimal policies (Büchi, parity, Rabin); Muller needs extension.
Experimental setup
Benchmarks: gridworld example (LTL GF s and GF g) chain example
Metrics: probability of satisfaction of learned policy runtime
Builds on: R-MAX Hoeffding's inequality good-for-MDPs automata Mungojerrie
Closest papers by meaning
- Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards (NeurIPS 2024 · similarity 0.92)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.88)
- On the Expressivity of Objective-Specification Formalisms in Reinforcement Learning (ICLR 2024 · similarity 0.88)
- Periodic agent-state based Q-learning for POMDPs (NeurIPS 2024 · similarity 0.88)
- Regret-Free Reinforcement Learning for Temporal Logic Specifications (ICML 2025 · similarity 0.88)
- Omega-Regular Decision Processes (AAAI 2024 · 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.