mlsanityData to 7 Oct 2026

Offline Primal-Dual Reinforcement Learning for Linear MDPs

arXiv 2305.12944 ↗First posted 22 May 2023cs.LGcited by 17

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

Abstract (arXiv)

Offline Reinforcement Learning (RL) aims to learn a near-optimal policy from a fixed dataset of transitions collected by another policy. This problem has attracted a lot of attention recently, but most existing methods with strong theoretical guarantees are restricted to finite-horizon or tabular settings. In constrast, few algorithms for infinite-horizon settings with function approximation and minimal assumptions on the dataset are both sample and computationally efficient. Another gap in the current literature is the lack of theoretical analysis for the average-reward setting, which is more challenging than the discounted setting. In this paper, we address both of these issues by proposing a primal-dual optimization method based on the linear programming formulation of RL. Our key contribution is a new reparametrization that allows us to derive low-variance gradient estimators that can be used in a stochastic optimization scheme using only samples from the behavior policy. Our method finds an varepsilon-optimal policy with O(varepsilon-4) samples, improving on the previous O(varepsilon-5), while being computationally efficient for infinite-horizon discounted and average-reward MDPs with realizable linear function approximation and partial coverage. Moreover, to the best of our knowledge, this is the first theoretical result for average-reward offline RL.

Key facts. Cited by 17 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 27 of its 62 references that are in the map. First posted on arXiv 22 May 2023.

Builds on

27 of 62 references.

Closest ancestors · 11

Same direction, newest first

  1. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning30 Jan
  2. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian1 Nov
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  4. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
  5. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  6. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  7. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  8. 2021Corruption-Robust Offline Reinforcement Learning11 Jun
  9. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  10. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  11. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 16

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  4. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  5. 2017A unified view of entropy-regularized Markov decision processescited by 174
  6. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  7. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  8. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  9. 2020Logistic Q-Learningcited by 34
  10. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  11. 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28
  12. 2018Scalable Bilinear π Learning Using State and Action Featurescited by 10
4 more
  1. 2019Faster saddle-point optimization for solving large-scale Markov decision processescited by 8
  2. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  3. 2022Online Learning with Off-Policy Feedbackcited by 4
  4. 2014On Minimax Optimal Offline Policy Evaluationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 8; 2026: 4.

17 papers.

Sort:

By area:

  1. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  2. 2024Performative Reinforcement Learning with Linear Markov Decision Processcited by 8
  3. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  4. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  5. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  6. 2024Offline RL via Feature-Occupancy Gradient Ascentcited by 2
  7. 2025Offline Reinforcement Learning via Inverse Optimizationcited by 2
  8. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 2
  9. 2025Offline Constrained Reinforcement Learning under Partial Data Coveragecited by 1
  10. 2025Analysis of approximate linear programming solution to Markov decision problem with log barrier functioncited by 1
  11. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 1
  12. 2026A Unifying View of Coverage in Linear Off-Policy Evaluationcited by 1
5 more
  1. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  2. 2025A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidancecited by 0
  3. 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learningcited by 0
  4. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  5. 2026Lifted Bellman Linear Programming for Offline Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  2. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
  3. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  4. 2020MOReL : Model-Based Offline Reinforcement Learning
  5. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
  6. 2023Dual RL: Unification and New Methods for Reinforcement and Imitation Learning
  7. 2022Offline Policy Optimization in RL with Variance Regularizaton
  8. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory