# Offline Primal-Dual Reinforcement Learning for Linear MDPs

arXiv: https://arxiv.org/abs/2305.12944 · HTML: https://mlsanity.com/paper/2305.12944/

## Key facts

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

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 27 of 27)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Adversarially Trained Actor Critic for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02446/) (2022)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Reinforcement Learning via Fenchel-Rockafellar Duality](https://mlsanity.com/paper/2001.01866/) (2020)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [Logistic Q-Learning](https://mlsanity.com/paper/2010.11151/) (2020)
- [Online learning in MDPs with linear function approximation and bandit feedback](https://mlsanity.com/paper/2007.01612/) (2020)
- [Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian](https://mlsanity.com/paper/2211.00716/) (2022)
- [On the Optimality of Batch Policy Optimization Algorithms](https://mlsanity.com/paper/2104.02293/) (2021)
- [Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning](https://mlsanity.com/paper/2301.12714/) (2023)
- [Scalable Bilinear π Learning Using State and Action Features](https://mlsanity.com/paper/1804.10328/) (2018)
- [Faster saddle-point optimization for solving large-scale Markov decision processes](https://mlsanity.com/paper/1909.10904/) (2019)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [On Minimax Optimal Offline Policy Evaluation](https://mlsanity.com/paper/1409.3653/) (2014)
- [Online Learning with Off-Policy Feedback](https://mlsanity.com/paper/2207.08956/) (2022)

## Built on by (most cited first, 17 of 17)

- [Corruption Robust Offline Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2402.06734/) (2024)
- [Performative Reinforcement Learning with Linear Markov Decision Process](https://mlsanity.com/paper/2411.05234/) (2024)
- [On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond](https://mlsanity.com/paper/2401.03301/) (2024)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2406.11686/) (2024)
- [Offline Reinforcement Learning via Inverse Optimization](https://mlsanity.com/paper/2502.20030/) (2025)
- [Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL](https://mlsanity.com/paper/2506.20904/) (2025)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Offline RL via Feature-Occupancy Gradient Ascent](https://mlsanity.com/paper/2405.13755/) (2024)
- [Finite-Time Bounds for Average-Reward Fitted Q-Iteration](https://mlsanity.com/paper/2510.17391/) (2025)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [Offline Constrained Reinforcement Learning under Partial Data Coverage](https://mlsanity.com/paper/2505.17506/) (2025)
- [Analysis of approximate linear programming solution to Markov decision problem with log barrier function](https://mlsanity.com/paper/2509.19800/) (2025)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)
- [A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance](https://mlsanity.com/paper/2505.04494/) (2025)
- [Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2512.04958/) (2025)
- [Lifted Bellman Linear Programming for Offline Reinforcement Learning](https://mlsanity.com/paper/2609.24489/) (2026)

## 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.