mlsanityData to 14 Oct 2026

Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints

arXiv 2212.13861 ↗First posted 28 Dec 2022cs.LG math.OC stat.MLcited by 15

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

Abstract (arXiv)

Offline reinforcement learning (RL) aims to find an optimal policy for Markov decision processes (MDPs) using a pre-collected dataset. In this work, we revisit the linear programming (LP) reformulation of Markov decision processes for offline RL, with the goal of developing algorithms with optimal O(1/√n) sample complexity, where n is the sample size, under partial data coverage and general function approximation, and with favorable computational tractability. To this end, we derive new error bounds for both the dual and primal-dual formulations of the LP, and incorporate them properly as constraints in the LP reformulation. We then show that under a completeness-type assumption, O(1/√n) sample complexity can be achieved under standard single-policy coverage assumption, when one properly relaxes the occupancy validity constraint in the LP. This framework can readily handle both infinite-horizon discounted and average-reward MDPs, in both general function approximation and tabular cases. The instantiation to the tabular case achieves either state-of-the-art or the first sample complexities of offline RL in these settings. To further remove any completeness-type assumption, we then introduce a proper lower-bound constraint in the LP, and a variant of the standard single-policy coverage assumption. Such an algorithm leads to a O(1/√n) sample complexity with dependence on the value-function gap, with only realizability assumptions. Our properly constrained LP framework advances the existing results in several aspects, in relaxing certain assumptions and achieving the optimal O(1/√n) sample complexity, with simple analyses. We hope our results bring new insights into the use of LP formulations and the equivalent primal-dual minimax optimization for offline RL, through the error-bound induced constraints.

Key facts. Cited by 15 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 12 of its 62 references that are in the map. First posted on arXiv 28 Dec 2022.

Builds on

12 of 62 references.

Closest ancestors · 5

Same direction, newest first

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  2. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  3. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimation21 Jun
  4. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  5. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 7

  1. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 274
  2. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
  3. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 188
  4. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  5. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  6. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  7. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 25

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 7; 2024: 4; 2025: 2; 2026: 2.

15 papers.

Sort:

By area:

  1. 2024RLHF from Heterogeneous Feedback via Personalization and Preference Aggregationcited by 74
  2. 2023When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learningcited by 26
  3. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 18
  4. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  5. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 10
  6. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  7. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  8. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  9. 2024A Unified Linear Programming Framework for Offline Reward Learning from Human Demonstrations and Feedbackcited by 4
  10. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  11. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 3
  12. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
3 more
  1. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 2
  3. 2023Offline Reinforcement Learning with Additional Covering Distributionscited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  2. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  4. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
  5. 2026Offline-Online Reinforcement Learning for Linear Mixture MDPs
  6. 2025Offline Constrained Reinforcement Learning under Partial Data Coverage
  7. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs
  8. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction