mlsanityData to 14 Oct 2026

Finite-Time Bounds for Average-Reward Fitted Q-Iteration

arXiv 2510.17391 ↗First posted 20 Oct 2025cs.LGcited by 2

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

Abstract (arXiv)

Although there is an extensive body of work characterizing the sample complexity of discounted-return offline RL with function approximations, prior work on the average-reward setting has received significantly less attention, and existing approaches rely on restrictive assumptions, such as ergodicity or linearity of the MDP. In this work, we establish the first sample complexity results for average-reward offline RL with function approximation for weakly communicating MDPs, a much milder assumption. To this end, we introduce Anchored Fitted Q-Iteration, which combines the standard Fitted Q-Iteration with an anchor mechanism. We show that the anchor, which can be interpreted as a form of weight decay, is crucial for enabling finite-time analysis in the average-reward setting. We also extend our finite-time analysis to the setup where the dataset is generated from a single-trajectory rather than IID transitions, again leveraging the anchor mechanism.

Key facts. Cited by 2 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 46 of its 96 references that are in the map. First posted on arXiv 20 Oct 2025.

Builds on

46 of 96 references.

Closest ancestors · 13

Same direction, newest first

  1. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs22 May
  2. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints28 Dec
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  4. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  5. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  6. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  7. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  8. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  9. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  10. 2020Batch Value-function Approximation with Only Realizability11 Aug
  11. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  12. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
1 more
  1. 2020Keep Doing What Worked: Behavioral Modelling Priors for Offline Reinforcement Learning19 Feb

Other references · 33

  1. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 840
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  4. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  5. 2018Top-K Off-Policy Correction for a REINFORCE Recommender Systemcited by 182
  6. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  7. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  8. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  9. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  10. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  11. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  12. 2020Learning and Planning in Average-Reward Markov Decision Processescited by 54
21 more
  1. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  2. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  3. 2017Misspecified Linear Banditscited by 42
  4. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  5. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  6. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  7. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  8. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  9. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  10. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
  11. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 22
  12. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  13. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15
  14. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 14
  15. 2021Optimal error bounds for nonexpansive fixed-point iterations in normed spacescited by 12
  16. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 12
  17. 2023Accelerating Value Iteration with Anchoringcited by 11
  18. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processescited by 9
  19. 2020Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structurecited by 6
  20. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  21. 2024The Star Geometry of Critic-Based Regularizer Learningcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  2. 2026Average-Reward Policy Identification from a Single Continuing Trajectorycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  2. 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
  3. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
  4. 2025From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
  5. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
  6. 2026Hitting-Time Bounds for Asynchronous Q-Learning
  7. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation
  8. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains