Research map / Reinforcement learning / MDPs and planning
Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces
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.
Proves fast O(1/n) and O(log T) rates for value-based RL in continuous state-action spaces under two stability conditions (Bellman and occupation-measure stability), showing quadratic dependence on Bellman residuals and instantiating them for linear function approximation.
Problem
Sample complexity of RL in continuous state-action spaces is usually 1/sqrt(n) (offline) and sqrt(T) regret (online); the paper asks when much faster rates hold.
Approach
Introduces two Lipschitz-type stability conditions (Bellman operator stability and occupation-measure stability under the optimal policy's measure) that make the value gap scale with the squared Bellman residual, rather than linearly, yielding 1/n rates offline and log T regret online; shows these hold for linear function approximation via curvature of the action-feature set.
Key results
- Under stability conditions, the value gap is bounded by a quantity proportional to the squared Bellman residual, improving offline rates from n^{-1/2} to n^{-1}.
- For ridge-based FQI with linear features, the sample complexity is roughly d^{3/2} H^3 / epsilon, compared with d^2 H^3 / epsilon^2 from Zanette et al.
- Online regret improves from sqrt(T) to log T under the stated stability conditions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply stability conditions that make value sub-optimality quadratic in Bellman residuals | Continuous-state/action offline RL · Continuous-state/action offline RL | value-gap rate: n^{-\frac{1}{2}} -> n^{-1} | Helped |
| Apply stability conditions to bound online regret | Continuous-state/action online RL · Continuous-state/action online RL | cumulative regret rate: \sqrt{T} -> \log T | Helped |
| Use linear methods with well-chosen basis functions | Offline linear value-based method · Mountain Car | value sub-optimality rate: 1/\sqrt{\ensuremath{n}} -> 1/\ensuremath{n} | Helped |
| Use stability-based fast-rate analysis with ridge-based FQI | Ridge-based FQI · Linear function approximation, offline RL | sample complexity: \frac{\ensuremath{d}^2 \ensuremath{H}^3}{\epsilon^2} -> \frac{\ensuremath{d}^{\frac{3}{2}} \ensuremath{H}^3}{\epsilon} + | Helped |
Surprising findings
- Neither pessimism nor optimism is required once a sufficiently accurate pilot estimate is available.
- Standard 1/epsilon^2 lower bounds for offline RL do not contradict the fast rates because their hard instances violate the stability conditions.
Limitations
- null
Experimental setup
Metrics: value gap sample complexity regret
Baselines: pessimistic actor-critic (Zanette et al.) standard 1/sqrt(n) slow-rate analyses sqrt(T) regret analyses
Builds on: fitted Q-iteration telescope inequality for value gap
Closest papers by meaning
- Enhancing Value Function Estimation through First-Order State-Action Dynamics in Offline Reinforcement Learning (ICML 2024 · similarity 0.88)
- Learning to Stabilize Online Reinforcement Learning in Unbounded State Spaces (ICML 2024 · similarity 0.88)
- Sleeping Reinforcement Learning (ICML 2025 · similarity 0.87)
- Pausing Policy Learning in Non-stationary Reinforcement Learning (ICML 2024 · similarity 0.87)
- From Static Policies to Adaptive Priors in Offline Reinforcement Learning (NeurIPS 2026 · similarity 0.87)
- A Theoretical Framework for Partially-Observed Reward States in RLHF (ICLR 2025 · 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.