Research map / Reinforcement learning / Offline RL
Harnessing Density Ratios for 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 density ratio realizability plus value realizability yields sample-efficient online RL under coverability via a truncated-density-ratio optimistic algorithm (GLOW), and a computationally cheaper hybrid RL variant (HyGLOW) built from a generic hybrid-to-offline reduction (H2O).
Problem
Online RL with unbounded density ratios: whether density ratio modeling, which is successful in offline RL, can give provable sample-efficient online exploration under only a coverability assumption and value function realizability.
Approach
Replace squared Bellman error constraints (which need Bellman completeness) with an average, weight-function-weighted Bellman error constraint using clipped density ratios w.r.t. historical data, combined with a quadratic variance penalty and global optimism; clipping at a growing scale gamma*t is analyzed via coverability potential arguments. For hybrid RL, a reduction H2O repeatedly invokes an o
Key results
- GLOW achieves N = Õ(H^2 C_cov / ε^2 · log(|F||W|/δ)) PAC sample complexity under strong (mixture) density ratio realizability, matching coverability-based Bellman-completeness rates up to log|W|.
- Under weaker pure-policy density ratio realizability, GLOW attains Õ(H^4 C_cov^2 / ε^4) sample complexity.
- The H2O reduction gives risk Õ(H sqrt((C* + C_cov) a b / T)) for hybrid RL, and HyGLOW achieves Õ(H^2 (C_cov + C*)/ε^2) sample complexity without global optimism.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use mixture-policy density ratio realizability instead of pure-policy density ratio realizability | GLOW · Online RL | sample complexity: \(\varepsilon^{-4}\) dependence -> \(\varepsilon^{-2}\) dependence | Helped |
| Clip density ratios to handle unbounded ratios during online exploration | GLOW · Online RL | sample complexity: \(N = \wt O\prn[\bigg]{\frac{H^2 \Ccov}{\varepsilon^2} \log\prn*{\nicefrac{\abs*{\cF}\abs*{\cW}}{\delta}}}\) | Helped |
| Add a quadratic penalty for the weight function | GLOW · Online RL, strong density ratio realizability | sample complexity: \(\nicefrac{1}{\varepsilon^2}\) | Helped |
| Use offline data covering a high-quality policy and the H₂O reduction | HyGLOW · Hybrid RL | computational efficiency | Helped |
Surprising findings
- Density ratio realizability with value realizability suffices for online RL under coverability, without Bellman completeness, which is the reverse of what is typical in prior coverability results.
- Offline algorithms without pessimism (e.g., FQI, MABO) that require all-policy concentrability can, via H2O, solve the purely online setting under coverability.
Limitations
- GLOW is computationally inefficient due to global optimism.
- Pure-policy density ratio realizability gives a worse 1/eps^4 rate than the mixture version.
- Whether value realizability and coverability alone suffice for sample-efficient RL remains open.
Experimental setup
Metrics: sample complexity regret risk (suboptimality)
Baselines: GOLF OLIVE BiLin-UCB Hybrid Q-Learning PRO-RL
Builds on: coverability (Xie et al. 2023) GOLF MABO Hybrid Q-Learning
Closest papers by meaning
- Efficient Online Reinforcement Learning with Offline Data (ICML 2023 · similarity 0.91)
- A Clean Slate for Offline Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
- Horizon Reduction Makes RL Scalable (NeurIPS 2025 · similarity 0.89)
- A Perspective of Q-value Estimation on Offline-to-Online Reinforcement Learning (AAAI 2024 · similarity 0.89)
- A Snapshot of Influence: A Local Data Attribution Framework for Online Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
- Energy-Guided Diffusion Sampling for Offline-to-Online Reinforcement Learning (ICML 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.