mlsanityData to 7 Oct 2026

A Fast Convergence Theory for Offline Decision Making

arXiv 2406.01378 ↗First posted 3 Jun 2024cs.LG stat.MLcited by 0

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

Abstract (arXiv)

This paper proposes the first generic fast convergence result in general function approximation for offline decision making problems, which include offline reinforcement learning (RL) and off-policy evaluation (OPE) as special cases. To unify different settings, we introduce a framework called Decision Making with Offline Feedback (DMOF), which captures a wide range of offline decision making problems. Within this framework, we propose a simple yet powerful algorithm called Empirical Decision with Divergence (EDD), whose upper bound can be termed as a coefficient named Empirical Offline Estimation Coefficient (EOEC). We show that EOEC is instance-dependent and actually measures the correlation of the problem. When assuming partial coverage in the dataset, EOEC will reduce in a rate of 1/N where N is the size of the dataset, endowing EDD with a fast convergence guarantee. Finally, we complement the above results with a lower bound in the DMOF framework, which further demonstrates the soundness of our theory.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 31 of its 54 references that are in the map. First posted on arXiv 3 Jun 2024.

Builds on

31 of 54 references.

Closest ancestors · 15

Same direction, newest first

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  2. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps25 Mar
  3. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  4. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
  5. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  6. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  7. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  8. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  9. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  10. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency5 Feb
  11. 2021Fast Rates for the Regret of Offline Reinforcement Learning31 Jan
  12. 2020Batch Value-function Approximation with Only Realizability11 Aug
3 more
  1. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  2. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 16

  1. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  7. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  8. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
  9. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  10. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  11. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  12. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
4 more
  1. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  2. 2023On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoringcited by 15
  3. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  4. 2022Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributionscited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  2. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?
  3. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
  4. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
  5. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory
  6. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
  7. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  8. 2024On the Exponential Convergence for Offline RLHF with Pairwise Comparisons