mlsanityData to 14 Oct 2026

Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning

arXiv 2608.07725 ↗First posted 7 Aug 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Average-reward reinforcement-learning regret is known up to logarithmic factors, but the numerical content of published guarantees is difficult to compare because probability mode, structural parameter, logarithmic normalization, prior information, and planning assumptions differ. We introduce a constant-aware comparison protocol and derive an explicit finite lower certificate for communicating MDPs. The construction is a binary tree of two-state blocks; its proof uses exact trajectory-level Bernoulli KL divergence and keeps action budget, diameter, occupancy, navigation cost, and terminal bias explicit. A common closed-form envelope improves the published coefficient 0.015 across a finite frontier: 0.0200 in a moderate regime and up to 0.0291 under stronger action, diameter, and horizon conditions, a 94% increase. The limiting coefficient is frac132√(A-3)/A. For upper bounds, we give an auditable composition rule for a span-constrained optimistic learner, but do not claim a coefficient while adaptive directional-variance and planning certificates remain open. We also formalize valid expectation conversion and constant comparability. Controlled diagnostics test diameter dependence, bonus-by-width interactions, span misspecification, and the finite lower certificate on its exact family.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 24 of its 51 references that are in the map. First posted on arXiv 7 Aug 2026.

Builds on

24 of 51 references.

References · 24

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  4. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  5. 2020Exploration-Exploitation in Constrained MDPscited by 149
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  8. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  9. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  10. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  11. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  12. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
12 more
  1. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  2. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  3. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  4. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  5. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
  6. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 29
  7. 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 25
  8. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  9. 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
  10. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  11. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  12. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  2. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  3. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
  4. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach
  5. 2024Achieving Constant Regret in Linear Markov Decision Processes
  6. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  7. 2024Optimistic Q-learning for average reward and episodic reinforcement learning
  8. 2026Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values