mlsanityData to 7 Oct 2026

Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism

arXiv 2203.05804 ↗First posted 11 Mar 2022cs.LG cs.AI stat.MLcited by 63

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

Abstract (arXiv)

Offline reinforcement learning, which seeks to utilize offline/historical data to optimize sequential decision-making strategies, has gained surging prominence in recent studies. Due to the advantage that appropriate function approximators can help mitigate the sample complexity burden in modern reinforcement learning problems, existing endeavors usually enforce powerful function representation models (e.g. neural networks) to learn the optimal policies. However, a precise understanding of the statistical limits with function representations, remains elusive, even when such a representation is linear. Towards this goal, we study the statistical limits of offline reinforcement learning with linear model representations. To derive the tight offline learning bound, we design the variance-aware pessimistic value iteration (VAPVI), which adopts the conditional variance information of the value function for time-inhomogeneous episodic linear Markov decision processes (MDPs). VAPVI leverages estimated variances of the value functions to reweight the Bellman residuals in the least-square pessimistic value iteration and provides improved offline learning bounds over the best-known existing results (whereas the Bellman residuals are equally weighted by design). More importantly, our learning bounds are expressed in terms of system quantities, which provide natural instance-dependent characterizations that previous results are short of. We hope our results draw a clearer picture of what offline learning should look like when linear representations are provided.

Key facts. Cited by 63 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 49 of its 81 references that are in the map. First posted on arXiv 11 Mar 2022.

Builds on

49 of 81 references.

Closest ancestors · 19

Same direction, newest first

  1. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  2. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  3. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  4. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  5. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  7. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings13 May
  8. 2021Nearly Horizon-Free Offline Reinforcement Learning25 Mar
  9. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning25 Mar
  10. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  11. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  12. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
7 more
  1. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  2. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation19 Jun
  3. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  4. 2020MOPO: Model-based Offline Policy Optimization27 May
  5. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  6. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  7. 2019Behavior Regularized Offline Reinforcement Learning26 Nov

Other references · 30

  1. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
  2. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  3. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 833
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  7. 2019Batch Policy Learning under Constraintscited by 242
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  10. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  11. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
18 more
  1. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  3. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  4. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  5. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  6. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  7. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  8. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  9. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  10. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  11. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  12. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  13. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  14. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  15. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  16. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
  17. 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28
  18. 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 19; 2023: 16; 2024: 17; 2025: 6; 2026: 5.

63 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 83
  3. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  4. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  5. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  6. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  7. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  8. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  9. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  10. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  11. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  12. 2022Offline Reinforcement Learning with Differential Privacycited by 19
38 more
  1. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  2. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 17
  3. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  4. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  5. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  6. 2022Offline Reinforcement Learning with Closed-Form Policy Improvement Operatorscited by 14
  7. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  8. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  9. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  10. 2025Towards User-level Private Reinforcement Learning with Human Feedbackcited by 13
  11. 2022Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARLcited by 12
  12. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  13. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  14. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  15. 2023Differentially Private Reward Estimation with Preference Feedbackcited by 12
  16. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  17. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  18. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  19. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  20. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  21. 2022Scaling Marginalized Importance Sampling to High-Dimensional State-Spaces via State Abstractioncited by 7
  22. 2024Combining Experimental and Historical Data for Policy Evaluationcited by 6
  23. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  24. 2024Towards Robust Policy: Enhancing Offline Reinforcement Learning with Adversarial Attacks and Defensescited by 5
  25. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  26. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  27. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  28. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
  29. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  30. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  31. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  32. 2024Taming "data-hungry" reinforcement learning? Stability in continuous state-action spacescited by 3
  33. 2025Provable Zero-Shot Generalization in Offline Reinforcement Learningcited by 3
  34. 2023A Unified Framework of Policy Learning for Contextual Bandit with Confounding Bias and Missing Observationscited by 2
  35. 2024Leveraging Unlabeled Data Sharing through Kernel Function Approximation in Offline Reinforcement Learningcited by 2
  36. 2024NetworkGym: Reinforcement Learning Environments for Multi-Access Traffic Management in Network Simulationcited by 2
  37. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 2
  38. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2

50 most cited of 63 All 63 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024Diverse Randomized Value Functions: A Provably Pessimistic Approach for Offline Reinforcement Learning
  2. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
  3. 2023Model-based Offline Reinforcement Learning with Local Misspecification
  4. 2023Neural Network Approximation for Pessimistic Offline Reinforcement Learning
  5. 2022Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief
  6. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
  7. 2024Deterministic Uncertainty Propagation for Improved Model-Based Offline Reinforcement Learning
  8. 2021Revisiting Design Choices in Offline Model-Based Reinforcement Learning