Research map / Reinforcement learning / MDPs and planning
Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance
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 PAC learning of reachability specifications in MDPs is impossible without extra information, and gives an environment-agnostic PAC-MDP algorithm when the expected conditional distance (ECD) is supplied as an input.
Problem
PAC-MDP learning from reachability specifications is impossible in general because infinite-horizon logical specifications are non-robust to environment perturbations; existing PAC results need internal environment parameters.
Approach
Introduces the expected conditional distance (ECD), an external user-supplied parameter equal to the expected length of target-reaching trajectories under a policy, which yields a lower bound showing ECD is necessary and an algorithm (approximate MDP via exploration, then value iteration over ECD-bounded policies) that is PAC-MDP with polynomial sample complexity given ECD.
Key results
- Theorem 4.2 lower bound: for ECD at least ℓ, any learner must make at least (1/2)(1-2p)(ℓ-2) non-ε-optimal outputs with probability at least p, so sample complexity must scale with ECD.
- Theorem 5.4: algorithm outputs an ε-optimal policy with ECD ≤ ℓ with probability at least 1-p, with expected sample complexity O(n^6 |A| ℓ^3 ε^-6 log(n^2|A|/p) log(n|A|ℓ/(εp))).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Provide ECD ℓ for reachability-policy learning | PAC-MDP with ECD · Reachability RL | sample complexity: O\left(n^6|A|\ell^3\varepsilon^{-6}\log \frac{n^2|A|}{p}\log \frac{n|A|\ell}{\varepsilon p}\right) | Helped |
| Learn without ECD information | Any learning algorithm for reachability · Reachability RL | number of iterations with a non-ε-optimal policy: \frac{1}{2}(1-2p)(\ell-2) | Hurt |
| Use dynamic programming with ECD discretization | Algorithm 2 · Known MDP with reachability target | runtime: O(n^4|A|\ell^7\varepsilon^{-10}) | Helped |
Surprising findings
- Lemma 4.1 shows ECD can be exponential in the smallest non-zero transition probability, even for simple MDPs.
Limitations
- No empirical evaluation; results are purely theoretical.
- Requires a simulator and the ECD value as input, which the user must supply.
- Algorithm is model-based and sample complexity has high polynomial degree (n^6).
Experimental setup
Metrics: sample complexity (theoretical)
Baselines: Fu & Topcu 2014 Ashok et al. 2019 Perez et al. 2023 Alur et al. 2023
Builds on: PAC-MDP (Kakade 2003) Yang et al. 2021 finitary PAC-MDP Fu & Topcu 2014
Closest papers by meaning
- A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs (AAAI 2024 · similarity 0.85)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.85)
- State-free Reinforcement Learning (NeurIPS 2024 · similarity 0.85)
- On the Expressivity of Objective-Specification Formalisms in Reinforcement Learning (ICLR 2024 · similarity 0.85)
- Safeguarded Progress in Reinforcement Learning: Safe Bayesian Exploration for Control Policy Synthesis (AAAI 2024 · similarity 0.85)
- Regret-Free Reinforcement Learning for Temporal Logic Specifications (ICML 2025 · similarity 0.84)
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.