Research map / Reinforcement learning / MDPs and planning
Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting
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 |
|---|---|---|---|
| Allow controlled state revisiting during online exploration | RL with linearly realizable Q* · Finite-horizon MDP with a sub-optimality gap | sample complexity scaling: polynomially in the feature dimension d, the horizon H, and the inverse sub-optimality gap 1/\taugap, but otherwise inde | Helped |
| Permit state revisiting rather than restrict sampling to standard online RL | RL with linearly realizable Q* · Online RL with a large sub-optimality gap | feasibility of sample-efficient learning | Helped |
| Use the sub-optimality gap to trigger backtracking when the UCB bonus is too large | LinQ-LSVI-UCB · Finite-horizon MDP with linearly realizable Q* | number of state revisits: K - N \le \frac{4c_{\beta}^2d^2H^5\log^2 \frac{KH}{\delta}}{\taugap^2} | Helped |
| Use gap-based revisiting with LinQ-LSVI-UCB | LinQ-LSVI-UCB · Finite-horizon MDP with linearly realizable Q* | expected regret: \frac{17c_{\beta}^{2}d^{2}H^{7}\log^{2}(KH)}{\Delta_{\mathsf{gap}}^{2}} | Helped |
| Use linear realizability of Q* without the stronger linear MDP assumption | RL with value-based linear representation · Finite-horizon MDP | assumption strength | Helped |
| Estimate the next-step Q-value without adding its UCB bonus in the theta update | LinQ-LSVI-UCB · Finite-horizon MDP with linearly realizable Q* | validity of the analysis | Helped |
Closest papers by meaning
- Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model (NeurIPS 2021 · similarity 0.93)
- An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap (NeurIPS 2021 · similarity 0.92)
- Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model (NeurIPS 2020 · similarity 0.91)
- Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs (ICLR 2023 · similarity 0.91)
- Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity (ICLR 2024 · similarity 0.90)
- Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge (AAAI 2024 · 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.