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

arXiv: https://arxiv.org/abs/2608.07725 · HTML: https://mlsanity.com/paper/2608.07725/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 24 of 24)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [Regret Bounds for Reinforcement Learning via Markov Chain Concentration](https://mlsanity.com/paper/1808.01813/) (2018)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)
- [Improved Regret Bound and Experience Replay in Regularized Policy Iteration](https://mlsanity.com/paper/2102.12611/) (2021)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Achieving Tractable Minimax Optimal Regret in Average Reward MDPs](https://mlsanity.com/paper/2406.01234/) (2024)

## 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.