Research map / Reinforcement learning / MDPs and planning
The Power of Resets in Online Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that online RL with local simulator access (resets to previously seen states) enables sample-efficient learning under coverability with only Q*-realizability (SimGolf), and gives a computationally efficient value-function-based algorithm RVFS under pushforward coverability, with applications to Exogenous Block MDPs.
Problem
Online RL with general function approximation typically cannot exploit simulator access efficiently; it is unclear which states to revisit, and existing local-simulator guarantees are limited to linear function approximation.
Approach
Use local simulator access to directly estimate squared Bellman error backups (avoiding double sampling and Bellman completeness) within a GOLF-style global optimism scheme (SimGolf), and build core-sets guided by value-function tests for a computationally efficient recursive search (RVFS).
Key results
- SimGolf learns epsilon-optimal policies with Q*-realizability and coverability using about H^5 C_cov^2 log(|Q|/delta)/epsilon^4 episodes.
- RVFS is computationally efficient (reduces to convex optimization over the value class) with sample complexity about C_push^8 H^23 A epsilon^-13 under pushforward coverability.
- General ExBMDPs are shown learnable with local simulator access via SimGolf with complexity about H^5 S^3 A^3 log|Phi|/epsilon^4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add local simulator access to online reinforcement learning | SimGolf for MDPs with low coverability · MDPs with low coverability | sample complexity | Helped |
| Use randomized rounding of Bellman backups | RVFS^exo · Weakly correlated Exogenous Block MDPs | learnability under decoder realizability | Helped |
Surprising findings
- The authors conjecture that Q*-realizability plus coverability alone are not sufficient for polynomial sample complexity in vanilla online RL, which would separate online RL from RL with local simulators.
Limitations
- SimGolf is computationally inefficient because it relies on global optimism.
- RVFS requires stronger assumptions (pushforward coverability and V*-realizability with a Delta-gap or V^pi-realizability) than SimGolf.
- Polynomial dependence on problem parameters is loose; no empirical evaluation.
Experimental setup
Metrics: sample complexity suboptimality gap
Baselines: GOLF Go-Explore MCTS AlphaZero
Builds on: GOLF DMQ Go-Explore coverability
Closest papers by meaning
- Exploiting the Replay Memory Before Exploring the Environment: Enhancing Reinforcement Learning Through Empirical MDP Iteration (NeurIPS 2024 · similarity 0.89)
- How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach (NeurIPS 2024 · similarity 0.88)
- Online Reinforcement Learning in Non-Stationary Context-Driven Environments (ICLR 2025 · similarity 0.88)
- Planning, Fast and Slow: Online Reinforcement Learning with Action-Free Offline Data via Multiscale Planners (ICML 2024 · similarity 0.88)
- Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RL (NeurIPS 2024 · similarity 0.88)
- Hybrid Inverse Reinforcement Learning (ICML 2024 · similarity 0.88)
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.