Research map / Reinforcement learning / MDPs and planning
Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs
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.
Develops two computationally efficient hybrid RL algorithms for linear MDPs (an online-to-offline PAC method, RAPPEL, and an offline-to-online regret method, HYRULE) that beat the offline and online minimax-style bounds without single-policy concentrability.
Problem
Whether hybrid RL (offline plus online data) can provably beat the known offline-only and online-only lower bounds in linear MDPs without single-policy concentrability, for both PAC and regret settings.
Approach
Partition state-action space into offline-covered and online-needed parts; use reward-agnostic exploration (OPTCOV) to fill coverage gaps and then pessimistic offline RL (LinPEVI-ADV+) for PAC, and warm-start LSVI-UCB++ with offline data for regret, analyzing each partition separately with a truncation argument to keep H^3 horizon dependence.
Key results
- RAPPEL error bound sqrt(c_off d H^4/N_off)+sqrt(d_on d H^4/N_on), with a second bound improving horizon/dimension dependence, improving on the prior hybrid linear MDP bound sqrt(d^2H^7/N) by at least H^{3/2}.
- HYRULE regret bound sqrt(c_off^2 d H^3 N_on^2/N_off)+sqrt(d_on d H^3 N_on), improving on the prior hybrid regret bound by a factor of at least H^2 and on the online minimax regret sqrt(d^2H^3T) when offline data is plentiful.
- In Tetris experiments, hybrid data (200 offline + 100 online trajectories) gave the most conducive dataset for learning compared with offline-only or online-only data under adversarial behavior policy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RAPPEL to augment offline data with reward-agnostic online exploration before pessimistic offline learning | Linear MDPs · Linear MDPs (PAC error) | suboptimality gap: at least a factor of H^{3/2} | Helped |
| Add online exploration samples to the offline dataset before pessimistic offline RL | RAPPEL · Linear MDPs (PAC error) | suboptimality gap | Helped |
| Warm-start online RL with parameters estimated from offline data | HYRULE · Linear MDPs (regret) | regret: H^3 | Helped |
| Use HYRULE rather than online-only learning | Linear MDPs · Linear MDPs (regret) | regret | Helped |
| Initialize OPTCOV with 200 trajectories from a uniform behavior policy | OPTCOV · Tetris coverage | coverage (inverse minimum eigenvalue) | Helped |
| Initialize OPTCOV with 200 trajectories from an adversarial behavior policy rather than no offline data | OPTCOV · Tetris coverage | coverage (inverse minimum eigenvalue) | Helped |
| Use a hybrid dataset of offline and online trajectories for policy learning | LinPEVI-ADV · Tetris | policy value | Helped |
| Warm-start LSVI-UCB++ with an offline dataset | LSVI-UCB++ · Tetris | regret | Helped |
Surprising findings
- Hybrid RL with adversarially collected offline data still achieves better exploration coverage than online-only exploration.
Limitations
- Burn-in costs are non-trivial, inherited from OPTCOV and the truncation argument.
- Does not achieve a single algorithm improving both offline and online rates simultaneously.
- Horizon dependence H^3 not fully reached for the offline partition in offline RL (open problem).
Experimental setup
Datasets: scaled-down Tetris environment (offline data generated from uniform and adversarial behavior policies)
Benchmarks: scaled-down Tetris
Metrics: coverage (inverse minimum eigenvalue) policy value (negative excess height) regret
Baselines: LSVI-UCB++ LinPEVI-ADV Xie et al. 2022 hybrid RL
Builds on: LinPEVI-ADV LSVI-UCB++ OPTCOV FORCE
Closest papers by meaning
- Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds (ICLR 2025 · similarity 0.90)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.90)
- Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.90)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.90)
- Hybrid Reinforcement Learning from Offline Observation Alone (ICML 2024 · similarity 0.89)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 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.