mlsanityData to 7 Oct 2026

Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game

arXiv 2205.15512 ↗First posted 31 May 2022cs.LG cs.GT stat.MLcited by 53

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

Abstract (arXiv)

Offline reinforcement learning (RL) aims at learning an optimal strategy using a pre-collected dataset without further interactions with the environment. While various algorithms have been proposed for offline RL in the previous literature, the minimax optimality has only been (nearly) established for tabular Markov decision processes (MDPs). In this paper, we focus on offline RL with linear function approximation and propose a new pessimism-based algorithm for offline linear MDP. At the core of our algorithm is the uncertainty decomposition via a reference function, which is new in the literature of offline RL under linear function approximation. Theoretical analysis demonstrates that our algorithm can match the performance lower bound up to logarithmic factors. We also extend our techniques to the two-player zero-sum Markov games (MGs), and establish a new performance lower bound for MGs, which tightens the existing result, and verifies the nearly minimax optimality of the proposed algorithm. To the best of our knowledge, these are the first computationally efficient and nearly minimax optimal algorithms for offline single-agent MDPs and MGs with linear function approximation.

Key facts. Cited by 53 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 39 of its 71 references that are in the map. First posted on arXiv 31 May 2022.

Builds on

39 of 71 references.

Closest ancestors · 13

Same direction, newest first

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  2. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  3. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  4. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  5. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  7. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  8. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  9. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  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
1 more
  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 26

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Continuous control with deep reinforcement learningcited by 3,279
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,179
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  9. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  10. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  11. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  12. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
14 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  5. 2018Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendationcited by 101
  6. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  7. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  8. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  9. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  10. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  11. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  12. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  13. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  14. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 19; 2024: 16; 2025: 8; 2026: 4.

53 papers.

Sort:

By area:

  1. 2023RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignmentcited by 672
  2. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  3. 2024DPO Meets PPO: Reinforced Token Optimization for RLHFcited by 126
  4. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  5. 2024REBEL: Reinforcement Learning via Regressing Relative Rewardscited by 66
  6. 2024The Importance of Online Data: Understanding Preference Fine-tuning via Coveragecited by 55
  7. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  8. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  9. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  10. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  11. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  12. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
38 more
  1. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  2. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 17
  3. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  4. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  5. 2023Unsupervised Behavior Extraction via Random Intent Priorscited by 13
  6. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  7. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  8. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  9. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  10. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  11. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
  12. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  13. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  14. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  15. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  16. 2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularizationcited by 8
  17. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  18. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  19. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  20. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  21. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  22. 2023Advancing RAN Slicing with Offline Reinforcement Learningcited by 5
  23. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  24. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  25. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  26. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  27. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  28. 2024Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear qπ-Realizability and Concentrabilitycited by 3
  29. 2025Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysiscited by 3
  30. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  31. 2025Learning an Optimal Assortment Policy under Observational Datacited by 2
  32. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  33. 2022Offline congestion games: How feedback type affects data coverage requirementcited by 1
  34. 2026When Do Multi-Agent Systems Outperform? Analysing the Learning Efficiency of Agentic Systemscited by 1
  35. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 1
  36. 2024Is Offline Decision Making Possible with Only Few Samples? Reliable Decisions in Data-Starved Bandits via Trust Region Enhancementcited by 0
  37. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processescited by 0
  38. 2025Oryx: a Scalable Sequence Model for Many-Agent Coordination in Offline MARLcited by 0

50 most cited of 53 All 53 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  2. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs
  3. 2020MOReL : Model-Based Offline Reinforcement Learning
  4. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian
  5. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
  6. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  7. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learning
  8. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory