Research map / Reinforcement learning / MDPs and planning
On Oracle-Efficient PAC RL with Rich Observations
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 |
|---|---|---|---|
| Use local value estimates with depth-first exploration, state-identity pruning, and oracle-based policy optimization | Valor · Deterministic hidden-state dynamics | trajectories for an ε-optimal policy: \tilot\left(\frac{M^3H^8K}{\epsilon^5}\log(|\Gcal||\Pi|/\delta)\log^3(1/\delta)\right) | Helped |
| Implement Olive's joint value-and-policy optimization using standard CSC, LP, and LS oracles | Olive · Tabular MDPs | computational tractability | Hurt |
| Replace joint optimization over values and policies with dynamic programming that fixes future values before optimizing the current policy | Valor · Deterministic hidden-state dynamics | oracle efficiency: O\left( \frac{MH^2}{\epsilon}\log \frac {MH}{\delta}\right) CSC oracle calls; O\left( \frac{MKH^2}{\epsilon}\log \frac { | Helped |
| Use stored local values rather than bootstrap or Monte Carlo targets | Valor · Deterministic hidden-state dynamics | realizability assumptions | Helped |
| Use bootstrap targets or Monte Carlo return targets instead of stored local values | Alternative oracle-efficient algorithms · Deterministic hidden-state dynamics | realizability assumptions | Hurt |
Closest papers by meaning
- PAC Reinforcement Learning with Rich Observations (NeurIPS 2016 · similarity 0.91)
- Computably Continuous Reinforcement-Learning Objectives Are PAC-Learnable (AAAI 2023 · similarity 0.90)
- Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality (ICML 2026 · similarity 0.90)
- PAC Reinforcement Learning for Predictive State Representations (ICLR 2023 · similarity 0.89)
- Oracle-Efficient Reinforcement Learning for Max Value Ensembles (NeurIPS 2024 · similarity 0.89)
- When is Agnostic Reinforcement Learning Statistically Tractable? (NeurIPS 2023 · similarity 0.89)
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.