Research map / Reinforcement learning / MDPs and planning
Scalable Online Exploration via Coverability
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.
Proposes L1-Coverage, a policy-ensemble exploration objective tied to L1-Coverability, and derives computationally efficient planning and model-based/model-free online exploration algorithms (CODEX, CODEX.W) with a small MountainCar/Pendulum evaluation against MaxEnt.
Problem
Efficient exploration in reinforcement learning with nonlinear function approximation: designing exploration objectives that are statistically meaningful (bounded by an intrinsic complexity parameter), computationally efficient to optimize with planning, and usable for online exploration.
Approach
Defines exploration objectives as policy-ensemble optimization objectives and introduces L1-Coverage, an average-case relative-occupancy objective whose optimum (L1-Coverability) is bounded by L_infinity-Coverability; it is optimized by iteratively calling standard reward-driven policy optimization, yielding model-based (CODEX) and model-free (CODEX.W) exploration with polynomial sample complexity
Key results
- Theoretical guarantees: CODEX yields policy covers with L1-Coverage at most 12H times L_infinity-Coverability with T = O~(H^8 C^3 d log(|M|/delta)/eps^4) episodes for finite model classes.
- On MountainCar, L1-Coverage and MaxEnt reach similar entropy, but L1-Coverage attains the smallest L1-Coverability estimates among compared covers.
- On Pendulum, L1-Coverage and MaxEnt are both able to visit every state in the 8x8 discretization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use L1-Coverage instead of MaxEnt | MountainCar · MountainCar | L1-Coverability | Helped |
| Use L1-Coverage instead of MaxEnt | MountainCar · MountainCar | entropy | No clear effect |
| Use MaxEnt instead of L1-Coverage | MountainCar · MountainCar | number of states visited | Hurt |
| Use L1-Coverage or MaxEnt instead of uniform exploration | MountainCar · MountainCar | L1-Coverability | Mixed |
| Use L1-Coverage or MaxEnt instead of uniform exploration | Pendulum · Pendulum | discrete states visited | Helped |
| Use L1-Coverage instead of MaxEnt | Pendulum · Pendulum | L1-Coverability | No clear effect |
Surprising findings
- MaxEnt has higher entropy while visiting fewer states, suggesting entropy is a poor proxy for exploration.
Limitations
- Experiments are on low-dimensional classic control with discretized occupancy estimates, not high-dimensional domains.
- Theoretical sample complexity is polynomial with large exponents (e.g., H^8, eps^-4) and loses factors versus prior coverability work.
- Model-based results require realizability and proper offline estimation oracles.
Experimental setup
Datasets: MountainCarContinuous-v0 Pendulum-v0
Benchmarks: MountainCarContinuous-v0 Pendulum-v0
Metrics: unique states visited entropy of occupancy L1-Coverability estimate (muCov)
Baselines: MaxEnt uniform exploration
Builds on: Block MDP Low-Rank MDP Decision-Estimation Coefficient PSDP MaxEnt exploration
Closest papers by meaning
- The Role of Coverage in Online Reinforcement Learning (ICLR 2023 · similarity 0.92)
- Exploration in Reinforcement Learning with Deep Covering Options (ICLR 2020 · similarity 0.91)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.88)
- The Power of Resets in Online Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
- Global Optimality for Constrained Exploration via Penalty Regularization (NeurIPS 2026 · similarity 0.88)
- Occupancy-based Policy Gradient: Estimation, Convergence, and Optimality (NeurIPS 2024 · similarity 0.87)
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.