Skip to content
Preprint

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

Aug 2026 · 0 citations · 51 references
Computer Science

TL;DR

An explicit finite lower certificate for communicating MDPs is derived and an auditable composition rule for a span-constrained optimistic learner is given, and valid expectation conversion and constant comparability are formalized.

Abstract

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 $\frac1{32}\sqrt{(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.

View source

Similar papers

#machine learning Preprint Sep 2026

Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require computationally inefficient algorithms or have suboptimal dependence on the number of interactions $T$. We propose, to th...

Kihyun Yu, Seoungbin Bae, Dabeen Lee · 0 citations

Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication

This work establishes explicit radius conditions under which the robust average-reward Bellman equation admits a constant-gain solution, while for total variation and Wasserstein balls, any positive radius suffices without requiring the nominal MDP to be weakly communicating.

Chen-Yu Lu, Zi-Jun Chen, Nian Si · 0 citations

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayes...

T. Goo, Kihyuk Hong · 0 citations

Learning Chance-Constrained MDPs with Bellman Distributional Certificates

This paper establishes a model-based upper bound for CCMDPs with fixed bounded successor support and access to a certified planning oracle, and gives a model-free variance-reduced policy-gradient algorithm with a finite-sample expected KKT-residual guarantee and independent validation of every accepted policy.

Chen-Bei Lu, Hong-Yu Yi · 0 citations

Optimal No-Regret Learning for Repeated Prophet Inequality

An efficient algorithm is given achieving $\widetilde O(\sqrt{T})$ expected regret, matching the lower bound up to logarithmic factors and exploiting the nesting structure of observed prefixes to preserve exploration.

Kun Wang · 0 citations
#machine learning Preprint Aug 2026

Constant Individual Regret in General Games

This work introduces \emph{ECHO-OFTRL}: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average, and leverages a new form of optimism inspired by modern filter design.

Mingyang Liu, Gabriele Farina, A. Ozdaglar · 6 citations · ⚡4

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.