Research map / Reinforcement learning / Offline RL
Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds
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 a standard MLE-based model-based RL scheme (MLE version space plus optimistic or pessimistic planning) attains nearly horizon-free and second-order regret and sample complexity bounds in online and offline RL with general function approximation.
Problem
Whether simple model-based RL with MLE and optimistic/pessimistic planning can achieve horizon-free and variance-dependent (second-order) regret and sample complexity bounds under general nonlinear function approximation.
Approach
Uses the standard MLE-based model-based RL algorithm without variance-weighted learning; the analysis uses triangular discrimination / squared Hellinger distance with a mean-to-variance lemma, a new Eluder-dimension pigeonhole argument, and a recursion on higher-moment variance differences to remove horizon dependence.
Key results
- Online O-MBRL achieves regret O(sqrt(sum_k Var_{pi^k} * DE_1 * log(KH|P|/delta)) + DE_1 log) with no polynomial horizon dependence, and O(DE_1 log) regret under deterministic transitions.
- Offline CPPO-LR analysis gives performance gap O(sqrt(C Var_{pi*} log(|P|/delta)/K) + C log(|P|/delta)/K), completely horizon-free for finite model classes.
- For deterministic transitions the offline performance gap improves to O(C log(|P|/delta)/K), versus the worst-case 1/sqrt(K) rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MLE-based model learning with optimistic planning | O-MBRL · Online RL, finite model class | regret: O\Big(\sqrt{\sum_{k=0}^{K-1}\var_{\pi^k}\cdot\text{DE}_1(\Psi,\Scal \times \Acal,1/KH)\cdot\log(KH\left|\Pcal\right|/\de | Helped |
| Use MLE-based model learning with pessimistic planning | CPPO-LR · Offline RL, finite model class | performance gap: O\left(\sqrt{{C^{\pi^*} \var_{\pi^*}\log(|\Pcal|/\delta)}/{K} } + {C^{\pi^*}\log(|\Pcal|/\delta)}/{K}\right) | Helped |
| Apply the same MLE-based optimistic planning when transitions are deterministic | O-MBRL · Online RL with deterministic transitions | regret: O\left( \text{DE}_1(\Psi,\Scal \times \Acal,1/KH)\cdot\log(KH\left|\Pcal\right|/\delta)\log(KH)\right) | Helped |
| Apply the same MLE-based pessimistic planning when transitions are deterministic | CPPO-LR · Offline RL with deterministic transitions | performance gap: O\left({C^{\pi^*}\log(|\Pcal|/\delta)}/{K}\right) | Helped |
Surprising findings
- The offline bound is completely horizon-free, with no log H dependence, for finite model classes.
Limitations
- Extension to infinite model classes via bracketing incurs an ln(H) factor.
- The algorithms are computationally intractable due to optimism/pessimism planning over model classes.
- Model-based framework cannot capture problems solved only by model-free approaches such as linear MDPs.
Experimental setup
Metrics: regret performance gap sample complexity
Baselines: CPPO-LR EULER distributional RL second-order method
Builds on: Eluder dimension CPPO-LR triangular discrimination distributional RL second-order bounds
Closest papers by meaning
- Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies (NeurIPS 2019 · similarity 0.92)
- Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (ICLR 2019 · similarity 0.91)
- NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.90)
- Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.90)
- Towards General-Purpose Model-Free Reinforcement Learning (ICLR 2025 · similarity 0.89)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 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.