mlsanityData to 14 Oct 2026

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

arXiv 2606.16729 ↗First posted 15 Jun 2026cs.LG math.OCcited by 3

Not on the map. Why?

Abstract (arXiv)

While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model. In this work, we establish the first finite sample complexity guarantees from a single trajectory for weakly communicating average-reward MDPs. To this end, we study the dynamics of a single trajectory in weakly communicating MDPs and based on this analysis, we develop novel model-free methods. Notably, our value-based and policy-based methods provide finite sample complexity guarantees of widetildeO(1/varepsilon2) and widetildeO(1/varepsilon4) from a single trajectory in weakly communicating MDPs, respectively. Furthermore, we introduce the first model-free method that requires no prior knowledge of problem-dependent quantities for communicating MDPs.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 43 of its 85 references that are in the map. First posted on arXiv 15 Jun 2026.

Builds on

43 of 85 references.

References · 43

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  4. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  5. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  6. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  7. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  8. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  9. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  10. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  11. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  12. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
31 more
  1. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  2. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  3. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  4. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  5. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  6. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  7. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  8. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
  9. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  10. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  11. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  12. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  13. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraintscited by 15
  14. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15
  15. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 15
  16. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 14
  17. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 14
  18. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 13
  19. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 12
  20. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processescited by 9
  21. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processescited by 9
  22. 2024Truncated Variance Reduced Value Iterationcited by 8
  23. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  24. 2020Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structurecited by 6
  25. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oraclescited by 6
  26. 2025Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPscited by 4
  27. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 3
  28. 2026Policy Gradient Algorithms in Average-Reward Multichain MDPscited by 3
  29. 2025Faster Fixed-Point Methods for Multichain MDPscited by 2
  30. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2
  31. 2026Minimax-optimal Halpern iterations for Lipschitz mapscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Mapscited by 1
  2. 2026Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communicationcited by 0
  3. 2026Average-Reward Policy Identification from a Single Continuing Trajectorycited by 0