mlsanityData to 14 Oct 2026

Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning

arXiv 2310.01380 ↗First posted 2 Oct 2023cs.LG math.OC stat.MLcited by 9

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

Offline reinforcement learning (RL), where the agent aims to learn the optimal policy based on the data collected by a behavior policy, has attracted increasing attention in recent years. While offline RL with linear function approximation has been extensively studied with optimal results achieved under certain assumptions, many works shift their interest to offline RL with non-linear function approximation. However, limited works on offline RL with non-linear function approximation have instance-dependent regret guarantees. In this paper, we propose an oracle-efficient algorithm, dubbed Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI), for offline RL with non-linear function approximation. Our algorithmic design comprises three innovative components: (1) a variance-based weighted regression scheme that can be applied to a wide range of function classes, (2) a subroutine for variance estimation, and (3) a planning phase that utilizes a pessimistic value iteration approach. Our algorithm enjoys a regret bound that has a tight dependency on the function class complexity and achieves minimax optimal instance-dependent regret when specialized to linear function approximation. Our work extends the previous instance-dependent results within simpler function classes, such as linear and differentiable function to a more general framework.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 51 of its 62 references that are in the map. First posted on arXiv 2 Oct 2023.

Builds on

51 of 62 references.

Closest ancestors · 20

Same direction, newest first

  1. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation24 Feb
  2. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning30 Jan
  3. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints28 Dec
  4. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation23 Nov
  5. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian1 Nov
  6. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient3 Oct
  7. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  8. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  9. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  10. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  11. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  12. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
8 more
  1. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  2. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  3. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  5. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  7. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  8. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct

Other references · 31

  1. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  5. 2016Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collectioncited by 316
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  7. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  10. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  11. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
19 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  3. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  4. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  5. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  6. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  7. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  8. 2018Practical Contextual Bandits with Regression Oraclescited by 93
  9. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  10. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  11. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  12. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  13. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
  14. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  15. 2017Active Learning for Cost-Sensitive Classificationcited by 41
  16. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  17. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  18. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32
  19. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 4; 2025: 2; 2026: 2.

9 papers.

  1. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 33
  2. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  3. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  4. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 10
  5. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  6. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 6
  7. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 4
  8. 2025Bellman Calibration for V-Learning in Offline Reinforcement Learningcited by 3
  9. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 3

Similar, not cited

Close in wording, no citation either way

  1. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward
  2. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning
  3. 2026Pessimistic Auxiliary Policy for Offline Reinforcement Learning
  4. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learning
  5. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learning
  6. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs
  7. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes
  8. 2025Semi-pessimistic Reinforcement Learning