Research map / Reinforcement learning / MDPs and planning
Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes
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 reward-free covering exploration with CoverTraj and least-squares value iteration | Linear MDP reward-free policy identification · Linear MDP reward-free RL | sample complexity (episodes): prior rates: \cO(\frac{d^3 H^6}{\epsilon^2}) and \cO(\frac{d^3 H^5}{\epsilon^2}); proposed leading rate: \widetilde{\cO} | Helped |
| Provide access to the reward function during exploration | Linear MDP policy identification · Linear MDP reward-free versus reward-aware RL | dimension dependence of sample complexity: reward-free upper bound: \widetilde{\cO}(d^2 H^5/\epsilon^2); reward-aware lower bound: \Omega(d^2 H^2/\epsilon^2) | No clear effect |
| Collect feature-direction samples in visitation-probability-stratified sets using first-order regret exploration | CoverTraj in linear MDPs · Linear MDP covering exploration | episodes to cover feature directions: complexity scales as 2^i · d/γ_i^2 rather than with the inverse squared visitation probability | Helped |
| Replace first-order regret minimization with a minimax-regret algorithm (ablation) | CoverTraj · Linear MDP covering exploration | sample complexity (episodes): non-first-order final complexity: \widetilde{\cO}(\frac{d^4 H^8}{\epsilon^2}); first-order approach: \widetilde{\cO}(\fr | Hurt |
Closest papers by meaning
- On Reward-Free Reinforcement Learning with Linear Function Approximation (NeurIPS 2020 · similarity 0.95)
- Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs (ICML 2023 · similarity 0.93)
- Towards Minimax Optimal Reward-free Reinforcement Learning in Linear MDPs (ICLR 2023 · similarity 0.93)
- Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.92)
- How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach (NeurIPS 2024 · similarity 0.91)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.90)
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.