Research map / Reinforcement learning / Offline RL
Pessimistic Nonlinear Least-Squares Value Iteration for Offline 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.
Proposes PNLSVI, an oracle-efficient pessimistic LSVI-type algorithm with variance-weighted nonlinear regression for offline RL with general function approximation, achieving instance-dependent regret with sqrt(log N) dependence on function class size.
Problem
Offline RL with non-linear (general) function approximation lacks instance-dependent regret guarantees, and prior nonlinear methods have worse function-class complexity dependence.
Approach
Combines variance-weighted nonlinear least-squares regression, a separate dataset split to estimate the conditional variance via first- and second-moment regressions, and pessimistic value iteration with a D^2-divergence-based bonus; a reference-advantage decomposition yields sqrt(log N) dependence on function class cardinality.
Key results
- Regret bound scales as tilde O(sqrt(log N)) in function class cardinality, improving the tilde O(log N) of prior differentiable-function-class work (PFQL) and resolving its open problem.
- When specialized to linear MDPs, the bound reduces to tilde O(sqrt(d)) times sum of expected elliptical norms, matching the known lower bound and claimed minimax optimal instance-dependent regret.
- Assumes uniform data coverage (l-infinity-type), which the authors show is weaker than the coverage assumption of PFQL for differentiable classes and the linear feature-covariance coverage.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| variance-weighted regression with estimated variance (PNLSVI) vs. unweighted regression | PNLSVI for nonlinear function approximation · offline RL theory (regret bound) | regret dependence on function class cardinality | Helped |
| reference-advantage decomposition in the analysis of PNLSVI | PNLSVI analysis · offline RL theory (regret bound) | regret dependence on function class complexity | Helped |
| PNLSVI specialized to linear MDPs | PNLSVI with linear function class · offline linear MDP (instance-dependent regret) | regret bound order | No clear effect |
| weaker uniform coverage assumption (l2-type) than differentiable-class assumption of PFQL | PNLSVI theory · differentiable function class coverage | assumption strength | No clear effect |
Limitations
- Relies on a uniform data coverage assumption that the authors acknowledge can be strong in practice.
- Requires function class to be finite (cardinality N) in the main analysis; infinite classes handled via covering numbers.
- Requires sufficiently large dataset size K and a bonus oracle that is only implementable via binary search with a finite number of regression oracle calls for convex classes.
Experimental setup
Metrics: suboptimality bound (theoretical regret)
Baselines: LinPEVI-ADV PFQL Bellman-consistent pessimism ATAC CORAL Reformulated LP
Builds on: pessimistic value iteration (PEVI) variance-weighted ridge regression (Zhou et al. 2021) PFQL LinPEVI-ADV D^2-divergence
Closest papers by meaning
- Is Pessimism Provably Efficient for Offline RL? (ICML 2021 · similarity 0.94)
- Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.92)
- Exclusively Penalized Q-learning for Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.90)
- Enhancing Value Function Estimation through First-Order State-Action Dynamics in Offline Reinforcement Learning (ICML 2024 · similarity 0.90)
- Neural Network Approximation for Pessimistic Offline Reinforcement Learning (AAAI 2024 · similarity 0.90)
- Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning (ICML 2024 · similarity 0.90)
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.