Research map / Reinforcement learning / MDPs and planning
Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs
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 EPRL with max-coverage sampling and elimination | PAC RL in deterministic episodic MDPs · Deterministic episodic MDPs | sample complexity: \widetilde{O}(\varphi^\star(g)); matches the instance-dependent lower bound up to an O(H^2) factor and logarithmic facto | Helped |
| Use EPRL with max-coverage sampling and elimination | PAC RL in deterministic episodic MDPs · Deterministic episodic MDPs | worst-case sample complexity: \widetilde{O}(\frac{SAH^2}{\epsilon^2}\log(1/\delta)) | Helped |
| Use max-diameter sampling instead of max-coverage sampling within EPRL (ablation) | EPRL · Synthetic deterministic MDPs, (S,A,H) = (2,2,3) | sample complexity: 2 out of 10 | Mixed |
| Use max-coverage sampling instead of max-diameter sampling within EPRL (ablation) | EPRL · Synthetic deterministic MDPs, (S,A,H) = (2,2,3) | sample complexity: 2 out of 10 | Mixed |
| Use EPRL with max-diameter rather than BPI-UCRL | PAC RL in the synthetic deterministic MDP experiments · Large values of ε/Δ_min | sample complexity: never exceeding 2 | Hurt |
| Use EPRL with max-coverage rather than BPI-UCRL | PAC RL in the synthetic deterministic MDP experiments · Large values of ε/Δ_min | sample complexity: never exceeding 3 | Hurt |
| Use either EPRL sampling rule rather than BPI-UCRL | PAC RL in the synthetic deterministic MDP experiments · Small ε/Δ_min | sample complexity: by several orders of magnitude | Helped |
| Use max-diameter sampling alone rather than alternating max-coverage and max-diameter (ablation) | EPRL · Deterministic episodic MDPs | sample complexity bound: \widetilde{O}(\sum_{(s,a,h)}H^2/\max(\overline{\Delta}_h(s,a),\overline{\Delta}_{\min}, \epsilon )^2) | Hurt |
Closest papers by meaning
- Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (NeurIPS 2017 · similarity 0.91)
- Reward-Mixing MDPs with Few Latent Contexts are Learnable (ICML 2023 · similarity 0.90)
- Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling (NeurIPS 2026 · similarity 0.90)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.89)
- Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.89)
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · 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.