mlsanityData to 14 Oct 2026

Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP

arXiv 2212.00603 ↗First posted 1 Dec 2022cs.LG cs.AIcited by 29

Not on the map. Why?

Abstract (arXiv)

This work considers the sample complexity of obtaining an varepsilon-optimal policy in an average reward Markov Decision Process (AMDP), given access to a generative model (simulator). When the ground-truth MDP is weakly communicating, we prove an upper bound of widetilde O(H varepsilon-3 ln frac1δ) samples per state-action pair, where H := sp(h^*) is the span of bias of any optimal policy, varepsilon is the accuracy and δ is the failure probability. This bound improves the best-known mixing-time-based approaches in [Jin & Sidford 2021], which assume the mixing-time of every deterministic policy is bounded. The core of our analysis is a proper reduction bound from AMDP problems to discounted MDP (DMDP) problems, which may be of independent interests since it allows the application of DMDP algorithms for AMDP in other settings. We complement our upper bound by proving a minimax lower bound of Omega(|mathcal S| |mathcal A| H varepsilon-2 ln frac1δ) total samples, showing that a linear dependent on H is necessary and that our upper bound matches the lower bound in all parameters of (|mathcal S|, |mathcal A|, H, ln frac1δ) up to some logarithmic factors.

Key facts. Cited by 29 papers in the map (data through 14 Oct 2026). Builds on 10 of its 22 references that are in the map. First posted on arXiv 1 Dec 2022.

Builds on

10 of 22 references.

References · 10

  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  3. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  4. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  5. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  6. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
  7. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  8. 2018The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpointcited by 40
  9. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  10. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 5; 2024: 5; 2025: 10; 2026: 8.

29 papers.

Sort:

By area:

  1. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  2. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  3. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraintscited by 15
  4. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  5. 2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
  6. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 13
  7. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 12
  8. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  9. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 7
  10. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  11. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  12. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
17 more
  1. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5
  2. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 5
  3. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 4
  4. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 4
  5. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 4
  6. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  7. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 3
  8. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 3
  9. 2025Faster Fixed-Point Methods for Multichain MDPscited by 2
  10. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 2
  11. 2026Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductionscited by 2
  12. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  13. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  14. 2026Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspectivecited by 0
  15. 2026Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPscited by 0
  16. 2026Learning in Markovian bandits with non-observable states and constrained decision epochscited by 0
  17. 2026Average-Reward Policy Identification from a Single Continuing Trajectorycited by 0