mlsanityData to 14 Oct 2026

Finding good policies in average-reward Markov Decision Processes without prior knowledge

arXiv 2405.17108 ↗First posted 27 May 2024cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

We revisit the identification of an varepsilon-optimal policy in average-reward Markov Decision Processes (MDP). In such MDPs, two measures of complexity have appeared in the literature: the diameter, D, and the optimal bias span, H, which satisfy H≤ D. Prior work have studied the complexity of varepsilon-optimal policy identification only when a generative model is available. In this case, it is known that there exists an MDP with D simeq H for which the sample complexity to output an varepsilon-optimal policy is Omega(SAD/varepsilon2) where S and A are the sizes of the state and action spaces. Recently, an algorithm with a sample complexity of order SAH/varepsilon2 has been proposed, but it requires the knowledge of H. We first show that the sample complexity required to estimate H is not bounded by any function of S,A and H, ruling out the possibility to easily make the previous algorithm agnostic to H. By relying instead on a diameter estimation procedure, we propose the first algorithm for (varepsilon,δ)-PAC policy identification that does not need any form of prior knowledge on the MDP. Its sample complexity scales in SAD/varepsilon2 in the regime of small varepsilon, which is near-optimal. In the online setting, our first contribution is a lower bound which implies that a sample complexity polynomial in H cannot be achieved in this setting. Then, we propose an online algorithm with a sample complexity in SAD2/varepsilon2, as well as a novel approach based on a data-dependent stopping rule that we believe is promising to further reduce this bound.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 19 of its 26 references that are in the map. First posted on arXiv 27 May 2024.

Builds on

19 of 26 references.

References · 19

  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2020Adaptive Reward-Free Explorationcited by 77
  3. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  4. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
  5. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  6. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  7. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  8. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  9. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  10. 2022Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Errorcited by 32
  11. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  12. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
7 more
  1. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  2. 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 25
  3. 2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 16
  4. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  5. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  6. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5
  7. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 6; 2026: 7.

13 papers.

Sort:

By area:

  1. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 5
  2. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  3. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 3
  4. 2025Auto-exploration for online reinforcement learningcited by 3
  5. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 3
  6. 2026Policy Gradient Algorithms in Average-Reward Multichain MDPscited by 3
  7. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  8. 2025Policy Testing in Markov Decision Processescited by 2
  9. 2026Asymptotically Optimal Sequential Testing with Markovian Datacited by 2
  10. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 2
  11. 2025Towards Blackwell Optimality: Bellman Optimality Is All You Can Getcited by 1
  12. 2026Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPscited by 0
1 more
  1. 2026Average-Reward Policy Identification from a Single Continuing Trajectorycited by 0