Research map / Reinforcement learning / MDPs and planning
Computably Continuous Reinforcement-Learning Objectives Are PAC-Learnable
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require the objective to be uniformly continuous | General reinforcement-learning objectives · Information-theoretic setting | PAC-learnability | Helped |
| Require the objective to be computable | General reinforcement-learning objectives · Computation-theoretic setting | PAC-learnability | Helped |
| Apply the computability condition to a simple reward-machine objective | Simple reward machine · Reinforcement learning | PAC-learnability | Helped |
| Apply the computability condition to the LTL-in-the-limit objective | LTL-in-the-limit objective · Reinforcement learning | PAC-learnability | Helped |
| Apply the computability condition to a GLTL formula objective | GLTL objective · Reinforcement learning | PAC-learnability | Helped |
| Use an objective that is discontinuous and non-computable but constant in value across policies in finite-state DTMCs | Constructed environment-generic objective · Reinforcement learning | PAC-learnability | No clear effect |
Closest papers by meaning
- A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs (AAAI 2024 · similarity 0.90)
- Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance (ICML 2024 · similarity 0.89)
- Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards (NeurIPS 2024 · similarity 0.87)
- Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability (NeurIPS 2025 · similarity 0.87)
- Oracle-Efficient Reinforcement Learning for Max Value Ensembles (NeurIPS 2024 · similarity 0.87)
- On the Expressivity of Objective-Specification Formalisms in Reinforcement Learning (ICLR 2024 · similarity 0.86)
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.