mlsanityData to 7 Oct 2026

VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation

arXiv 2302.12780 ↗First posted 24 Feb 2023cs.LGcited by 3

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

Abstract (arXiv)

We propose a novel algorithm for offline reinforcement learning called Value Iteration with Perturbed Rewards (VIPeR), which amalgamates the pessimism principle with random perturbations of the value function. Most current offline RL algorithms explicitly construct statistical confidence regions to obtain pessimism via lower confidence bounds (LCB), which cannot easily scale to complex problems where a neural network is used to estimate the value functions. Instead, VIPeR implicitly obtains pessimism by simply perturbing the offline data multiple times with carefully-designed i.i.d. Gaussian noises to learn an ensemble of estimated state-action value functions and acting greedily with respect to the minimum of the ensemble. The estimated state-action values are obtained by fitting a parametric model (e.g., neural networks) to the perturbed datasets using gradient descent. As a result, VIPeR only needs O(1) time complexity for action selection, while LCB-based algorithms require at least Omega(K2), where K is the total number of trajectories in the offline data. We also propose a novel data-splitting technique that helps remove a factor involving the log of the covering number in our bound. We prove that VIPeR yields a provable uncertainty quantifier with overparameterized neural networks and enjoys a bound on sub-optimality of tildeO( kappa H5/2 tilded /√K), where tilded is the effective dimension, H is the horizon length and kappa measures the distributional shift. We corroborate the statistical and computational efficiency of VIPeR with an empirical evaluation on a wide set of synthetic and real-world datasets. To the best of our knowledge, VIPeR is the first algorithm for offline RL that is provably efficient for general Markov decision processes (MDPs) with neural network function approximation.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 60 of its 89 references that are in the map. First posted on arXiv 24 Feb 2023.

Builds on

60 of 89 references.

Closest ancestors · 26

Same direction, newest first

  1. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation23 Nov
  2. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient3 Oct
  3. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward13 Jun
  4. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  5. 2022Why So Pessimistic? Estimating Uncertainties for Offline RL through Ensembles, and Why Their Independence Matters27 May
  6. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps25 Mar
  7. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  8. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learning23 Feb
  9. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  10. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization27 Nov
  11. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  12. 2021Uncertainty-Based Offline Reinforcement Learning with Diversified Q-Ensemble4 Oct
14 more
  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  2. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  3. 2021A Minimalist Approach to Offline Reinforcement Learning12 Jun
  4. 2021Uncertainty Weighted Actor-Critic for Offline Reinforcement Learning17 May
  5. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning25 Mar
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  7. 2021Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks11 Mar
  8. 2021Fast Rates for the Regret of Offline Reinforcement Learning31 Jan
  9. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  10. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  11. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  12. 2020MOPO: Model-based Offline Policy Optimization27 May
  13. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  14. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learning15 Apr

Other references · 34

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
  6. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 833
  7. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  8. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  9. 2022Diffusion Policies as an Expressive Policy Class for Offline Reinforcement Learningcited by 543
  10. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  11. 2017On Kernelized Multi-armed Banditscited by 348
  12. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
22 more
  1. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  2. 2019Batch Policy Learning under Constraintscited by 242
  3. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  4. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  5. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  6. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  7. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  8. 2017Deep Exploration via Randomized Value Functionscited by 155
  9. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 130
  10. 2019Finite Depth and Width Corrections to the Neural Tangent Kernelcited by 114
  11. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  12. 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
  13. 2019Convergence of Adversarial Training in Overparametrized Neural Networkscited by 58
  14. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  15. 2019Learning When-to-Treat Policiescited by 49
  16. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  17. 2022Bootstrapped Transformer for Offline Reinforcement Learningcited by 37
  18. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  19. 2019Neural tangent kernels, transportation mappings, and universal approximationcited by 30
  20. 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28
  21. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  22. 2022Learning Neural Contextual Bandits Through Perturbed Rewardscited by 17

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 1.

3 papers.

  1. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  2. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  3. 2025Online Optimization for Offline Safe Reinforcement Learningcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2022State-Aware Proximal Pessimistic Algorithms for Offline Reinforcement Learning
  2. 2023Neural Network Approximation for Pessimistic Offline Reinforcement Learning
  3. 2024The Virtues of Pessimism in Inverse Reinforcement Learning
  4. 2021Dealing with the Unknown: Pessimistic Offline Reinforcement Learning
  5. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
  6. 2024Diverse Randomized Value Functions: A Provably Pessimistic Approach for Offline Reinforcement Learning
  7. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity
  8. 2022Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief