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

# Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning
Source: [https://arxiv.org/html/2608.07725](https://arxiv.org/html/2608.07725)
Ibne Farabi Shihab1Abu Sa\-Adat Mohamed Moon\-Im Al Ahsan2 Md Najmus Swaqeeb2 1Department of Computer Science, Iowa State University 2Department of Computer Science & Engineering, BRAC University ishihab@iastate\.edu,abu\.sa\.adat\.mohamed\.moon\.im\.al\.ahsan@g\.bracu\.ac\.bd, md\.najmus\.swaqeeb@g\.bracu\.ac\.bd

###### 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 coefficient0\.0150\.015across a finite frontier:0\.02000\.0200in a moderate regime and up to0\.02910\.0291under stronger action, diameter, and horizon conditions, a94%94\\%increase\. The limiting coefficient is132​\(A−3\)/A\\frac\{1\}\{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\.

## Introduction

Average\-reward reinforcement learning is the natural model for continuing tasks such as recommendation, queueing control, inventory management, and portfolio rebalancing, where there is no episodic reset\(Mahadevan[1996](https://arxiv.org/html/2608.07725#bib.bib45); Puterman[1994](https://arxiv.org/html/2608.07725#bib.bib14); Sutton and Barto[2018](https://arxiv.org/html/2608.07725#bib.bib15)\)\. For a communicating MDP with diameterDD,SSstates,AAactions, and horizonTT, the classical minimax scale isD​S​A​T\\sqrt\{DSAT\}\(Jakschet al\.[2010](https://arxiv.org/html/2608.07725#bib.bib1)\)\. Subsequent work developed bias\-span regularization, KL or empirical\-Bernstein confidence regions, model\-free methods, and tractable minimax\-optimal planning\(Bartlett and Tewari[2009](https://arxiv.org/html/2608.07725#bib.bib2); Fruitet al\.[2018](https://arxiv.org/html/2608.07725#bib.bib4); Zhang and Ji[2019](https://arxiv.org/html/2608.07725#bib.bib6); Fruitet al\.[2020](https://arxiv.org/html/2608.07725#bib.bib5); Boone and Zhang[2024](https://arxiv.org/html/2608.07725#bib.bib49)\)\. These papers sharpen rates and structural dependence, but a rate such asO~​\(D​S​A​T\)\\widetilde\{O\}\(\\sqrt\{DSAT\}\)does not reveal whether the certified multiplier is33,3030, or300300\.

A “leading constant” is meaningful only after normalization is fixed\. A coefficient multiplyinglog⁡\(S​A​T/δ\)\\sqrt\{\\log\(SAT/\\delta\)\}is not directly comparable with one multiplyinglog⁡\(S​A​T/δ\)\\log\(SAT/\\delta\), and a high\-probability upper coefficient is not by itself a constant\-factor match to a log\-free expected lower bound\. This distinction is material:Jakschet al\.\([2010](https://arxiv.org/html/2608.07725#bib.bib1)\)give an explicit lower coefficient0\.0150\.015under finite conditions, while their UCRL2 coefficient3434multiplies the different formD​S​A​T​log⁡\(T/δ\)DS\\sqrt\{AT\\log\(T/\\delta\)\}\.

We make four contributions\. First, we record probability mode, structural term, logarithm, horizon threshold, and side information with every constant\. Second, we derive an exact\-KL lower certificate in which testing, occupancy, navigation, and geometric terms remain explicit, and turn it into a uniform finite frontier from0\.01520\.0152to0\.02910\.0291\. Third, we specify an auditable upper\-bound ledger and identify which statistical and planning obligations must be completed before a numerical coefficient is valid\. Fourth, we redesign the empirical checks around the corrected claims: zero\-span diameter flatness, bonus\-by\-width interactions, width misspecification, and direct evaluation on the proved hard family\. Full proofs and extended experiments are supplementary\.

## Setup, Related Work, and Comparison Protocol

An average\-reward MDP isM=\(𝒮,𝒜,p,ν\)M=\(\\mathcal\{S\},\\mathcal\{A\},p,\\nu\), where rewards lie in\[0,1\]\[0,1\]\. At timett, the learner observessts\_\{t\}, choosesata\_\{t\}, receivesRt∼ν\(⋅∣st,at\)R\_\{t\}\\sim\\nu\(\\cdot\\mid s\_\{t\},a\_\{t\}\), and observesst\+1∼p\(⋅∣st,at\)s\_\{t\+1\}\\sim p\(\\cdot\\mid s\_\{t\},a\_\{t\}\)\. The explicit reward model is retained because stochastic reward uncertainty cannot in general be absorbed into a transition bonus\. For a communicating MDP, the optimal gainρ⋆\\rho^\{\\star\}is start\-state independent and an optimal biash⋆h^\{\\star\}satisfies

ρ⋆\+h⋆​\(s\)=maxa∈𝒜​\(s\)⁡\{r​\(s,a\)\+∑s′p​\(s′∣s,a\)​h⋆​\(s′\)\}\.\\rho^\{\\star\}\+h^\{\\star\}\(s\)=\\max\_\{a\\in\\mathcal\{A\}\(s\)\}\\left\\\{r\(s,a\)\+\\sum\_\{s^\{\\prime\}\}p\(s^\{\\prime\}\\mid s,a\)h^\{\\star\}\(s^\{\\prime\}\)\\right\\\}\.\(1\)The diameter isD=maxs≠s′⁡minπ⁡𝔼sπ​\[τs′\]D=\\max\_\{s\\neq s^\{\\prime\}\}\\min\_\{\\pi\}\\mathbb\{E\}\_\{s\}^\{\\pi\}\[\\tau\_\{s^\{\\prime\}\}\], the span complexity isH=1∨sp⁡\(h⋆\)H=1\\vee\\operatorname\{sp\}\(h^\{\\star\}\), and regret isℛT=T​ρ⋆−∑t=1TRt\\mathcal\{R\}\_\{T\}=T\\rho^\{\\star\}\-\\sum\_\{t=1\}^\{T\}R\_\{t\}\. The floor at one is essential: a communicating MDP can have a constant optimal bias while still containing a stochastic bandit learning problem withΩ​\(S​A​T\)\\Omega\(\\sqrt\{SAT\}\)regret\. We study𝔼​\[ℛT\]\\mathbb\{E\}\[\\mathcal\{R\}\_\{T\}\]; realized regret can be negative but is always at mostTT, which matters when converting a tail guarantee to expectation\.

The relevant average\-reward literature includes UCRL2 and its lower construction\(Jakschet al\.[2010](https://arxiv.org/html/2608.07725#bib.bib1)\), REGAL/SCAL\(Bartlett and Tewari[2009](https://arxiv.org/html/2608.07725#bib.bib2); Fruitet al\.[2018](https://arxiv.org/html/2608.07725#bib.bib4)\), EBF\(Zhang and Ji[2019](https://arxiv.org/html/2608.07725#bib.bib6)\), empirical\-Bernstein refinements\(Talebi and Maillard[2018](https://arxiv.org/html/2608.07725#bib.bib10); Bourelet al\.[2020](https://arxiv.org/html/2608.07725#bib.bib9); Fruitet al\.[2020](https://arxiv.org/html/2608.07725#bib.bib5)\), and PMEVI\-DT\(Boone and Zhang[2024](https://arxiv.org/html/2608.07725#bib.bib49)\)\. We use standard concentration and testing tools\(Boucheronet al\.[2013](https://arxiv.org/html/2608.07725#bib.bib41); Lattimore and Szepesvári[2020](https://arxiv.org/html/2608.07725#bib.bib13); Tsybakov[2009](https://arxiv.org/html/2608.07725#bib.bib40)\); the novelty lies in the finite constant ledger and the explicit balance of statistical and geometric losses\.

###### Definition 1\(Constant certificate\)\.

A constant is reported as𝖢=\(mode,structural term,log term,c,T0,side information\)\\mathsf\{C\}=\(\\text\{mode\},\\text\{structural term\},\\text\{log term\},c,T\_\{0\},\\text\{side information\}\)\. Two coefficients are directly comparable only if all entries exceptccagree\.

This rule blocks three common but invalid shortcuts: comparing expected and high\-probability constants, ignoring different powers of logarithmic factors, and treating a span\-dependent guarantee that receivesH¯\\bar\{H\}as input as directly comparable to a prior\-free diameter result\. Table[1](https://arxiv.org/html/2608.07725#Sx2.T1)therefore reports unmatched results side by side without turning their coefficient ratio into a theorem\.

Table 1:Normalization\-aware scoreboard\. Unmatched rows are not assigned a coefficient ratio\.
## A Finite\-Sample Lower\-Bound Certificate

We now give the complete lower construction\. Throughout this section,SSis even andA≥5A\\geq 5\. LetK=S/2K=S/2and index a complete binary tree𝒯\\mathcal\{T\}by0,…,K−10,\\ldots,K\-1: vertexj\>0j\>0has parent⌊\(j−1\)/2⌋\\lfloor\(j\-1\)/2\\rfloor, and its children are2​j\+12j\+1and2​j\+22j\+2whenever those indices are belowKK\. Its exact graph diameter is

L:=maxu,v∈𝒯⁡d𝒯​\(u,v\)≤2​⌈log2⁡K⌉\.L:=\\max\_\{u,v\\in\\mathcal\{T\}\}d\_\{\\mathcal\{T\}\}\(u,v\)\\leq 2\\lceil\\log\_\{2\}K\\rceil\.\(2\)Blockjjcontains a bad statexjx\_\{j\}with reward zero and a good stateyjy\_\{j\}with reward one\. Atyjy\_\{j\}, every action returns toxjx\_\{j\}with probabilityδ\\deltaand otherwise remains atyjy\_\{j\}\. Atxjx\_\{j\}, the first

actions are statistical\. A statistical action with parameterppmoves toyjy\_\{j\}with probabilityppand otherwise remains atxjx\_\{j\}\. The remaining three actions navigate to the parent, left child, and right child ofxjx\_\{j\}; a missing neighbor produces a self\-loop\. Thus every binary\-tree node uses at most three navigation actions, and the construction respects the action budget exactly\.

The baseline modelM0M\_\{0\}assignsp=δp=\\deltato every statistical action\. There are

m=K​\(A−3\)=S​\(A−3\)2m=K\(A\-3\)=\\frac\{S\(A\-3\)\}\{2\}\(4\)block–action coordinates\. AlternativeMiM\_\{i\},i∈\[m\]i\\in\[m\], changes only coordinateiifromδ\\deltatoδ\+ε\\delta\+\\varepsilon, where0<ε≤δ0<\\varepsilon\\leq\\delta\. All navigation transitions and all good\-state transitions are shared across the family\.

For a diameter budgetD\>L\+4D\>L\+4, set

δ=2D−L\.\\delta=\\frac\{2\}\{D\-L\}\.\(5\)From any good state, the expected time to its bad state is1/δ1/\\delta; traversal between bad states takes at mostLLdeterministic steps; and a baseline statistical action reaches any target good state in expected time1/δ1/\\delta\. Consequently every alternative is communicating and

D​\(Mi\)≤2δ\+L=D\.D\(M\_\{i\}\)\\leq\\frac\{2\}\{\\delta\}\+L=D\.\(6\)Equality is neither assumed nor needed: the minimax class contains all communicating MDPs with diameter at mostDD\.

If a policy remains in one two\-state block and uses transition probabilityppat the bad state, its gain is

ρ​\(p\)=pp\+δ\.\\rho\(p\)=\\frac\{p\}\{p\+\\delta\}\.\(7\)UnderMiM\_\{i\}, the optimal gain and the statistical Bellman gap are therefore

ρi=δ\+ε2​δ\+ε,g​\(δ,ε\)=2​ρi−1=ε2​δ\+ε\.\\rho\_\{i\}=\\frac\{\\delta\+\\varepsilon\}\{2\\delta\+\\varepsilon\},\\qquad g\(\\delta,\\varepsilon\)=2\\rho\_\{i\}\-1=\\frac\{\\varepsilon\}\{2\\delta\+\\varepsilon\}\.\(8\)The corresponding gain improvement over a baseline block is

ρ​\(δ\+ε\)−ρ​\(δ\)=ε2​\(2​δ\+ε\)\.\\rho\(\\delta\+\\varepsilon\)\-\\rho\(\\delta\)=\\frac\{\\varepsilon\}\{2\(2\\delta\+\\varepsilon\)\}\.\(9\)These expressions are exact\.

Table[2](https://arxiv.org/html/2608.07725#Sx3.T2)records every geometric and statistical quantity used below\. In particular, the occupancy factor depends onε/δ\\varepsilon/\\delta; replacing it uniformly by1/31/3would lower the best Pinsker coefficient below0\.0150\.015\.

Table 2:Exact lower\-bound construction ledger\. No unspecified multiplicative constant or asymptotic quantity enters the finite certificate\.The statistical calculation comparesM0M\_\{0\}with eachMiM\_\{i\}\. IfNi​\(T\)N\_\{i\}\(T\)counts selections of coordinateii, the adaptive chain rule gives

KL⁡\(ℙ0T∥ℙiT\)=𝔼0​\[Ni​\(T\)\]​kl⁡\(δ,δ\+ε\),\\operatorname\{KL\}\(\\mathbb\{P\}\_\{0\}^\{T\}\\,\\\|\\,\\mathbb\{P\}\_\{i\}^\{T\}\)=\\mathbb\{E\}\_\{0\}\[N\_\{i\}\(T\)\]\\,\\operatorname\{kl\}\\\!\\left\(\\delta,\\delta\+\\varepsilon\\right\),\(10\)where

kl⁡\(δ,δ\+ε\)=δ​log⁡δδ\+ε\+\(1−δ\)​log⁡1−δ1−δ−ε\.\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)=\\delta\\log\\frac\{\\delta\}\{\\delta\+\\varepsilon\}\+\(1\-\\delta\)\\log\\frac\{1\-\\delta\}\{1\-\\delta\-\\varepsilon\}\.\(11\)This identity remains exact under adaptive action selection\.

###### Lemma 1\(Adaptive multiple\-hypothesis certificate\)\.

For the coordinate counts defined above,

1m​∑i=1m𝔼i​\[Ni​\(T\)\]≤Tm\+T​T2​m​kl⁡\(δ,δ\+ε\)\.\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}\\mathbb\{E\}\_\{i\}\[N\_\{i\}\(T\)\]\\leq\\frac\{T\}\{m\}\+T\\sqrt\{\\frac\{T\}\{2m\}\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)\}\.\(12\)

The proof uses Pinsker’s inequality and the adaptive path divergence in \([10](https://arxiv.org/html/2608.07725#Sx3.E10)\); it does not assume that the coordinates are visited uniformly\.

The composite construction also requires control of the time used for navigation\. LetNx​\(T\)N\_\{x\}\(T\)count statistical decisions in bad states,Ny​\(T\)N\_\{y\}\(T\)count actions taken in good states, andNnav​\(T\)N\_\{\\rm nav\}\(T\)count navigation actions\. ThenT=Nx\+Ny\+NnavT=N\_\{x\}\+N\_\{y\}\+N\_\{\\rm nav\}\. Entry–exit accounting gives

δ​𝔼i​\[Ny​\(T\)\]≤\(δ\+ε\)​𝔼i​\[Nx​\(T\)\]\+1,\\delta\\mathbb\{E\}\_\{i\}\[N\_\{y\}\(T\)\]\\leq\(\\delta\+\\varepsilon\)\\mathbb\{E\}\_\{i\}\[N\_\{x\}\(T\)\]\+1,\(13\)and hence, withcε=\(2\+ε/δ\)−1c\_\{\\varepsilon\}=\(2\+\\varepsilon/\\delta\)^\{\-1\},

𝔼i​\[Nx​\(T\)\]≥cε​\(T−𝔼i​\[Nnav​\(T\)\]−1δ\)\.\\mathbb\{E\}\_\{i\}\[N\_\{x\}\(T\)\]\\geq c\_\{\\varepsilon\}\\left\(T\-\\mathbb\{E\}\_\{i\}\[N\_\{\\rm nav\}\(T\)\]\-\\frac\{1\}\{\\delta\}\\right\)\.\(14\)
Navigation cannot invalidate this occupancy bound by consuming the horizon for free\. Under alternativeii, normalize the optimal bias at the distinguished bad state and writej​\(i\)j\(i\)for its block\. An optimal bias is

hi​\(xv\)=−ρi​d𝒯​\(v,j​\(i\)\),hi​\(yv\)=hi​\(xv\)\+1−ρiδ\.h\_\{i\}\(x\_\{v\}\)=\-\\rho\_\{i\}d\_\{\\mathcal\{T\}\}\(v,j\(i\)\),\\qquad h\_\{i\}\(y\_\{v\}\)=h\_\{i\}\(x\_\{v\}\)\+\\frac\{1\-\\rho\_\{i\}\}\{\\delta\}\.\(15\)A navigation step towardj​\(i\)j\(i\)has Bellman gap zero, a step away has gap2​ρi2\\rho\_\{i\}, and a navigation self\-loop has gapρi\\rho\_\{i\}\. Along any tree path, the number of zero\-gap steps towardj​\(i\)j\(i\)is at most the number of steps away plusLL\. Therefore the total navigation Bellman gap is at least

ρi​\(Nnav​\(T\)−L\)\+\.\\rho\_\{i\}\\bigl\(N\_\{\\rm nav\}\(T\)\-L\\bigr\)\_\{\+\}\.\(16\)Moreover,

sp⁡\(hi\)≤Bh:=ρi​L\+1−ρiδ\.\\operatorname\{sp\}\(h\_\{i\}\)\\leq B\_\{h\}:=\\rho\_\{i\}L\+\\frac\{1\-\\rho\_\{i\}\}\{\\delta\}\.\(17\)
###### Theorem 2\(Finite\-sample explicit lower certificate\)\.

LetSSbe even,A≥5A\\geq 5,D\>L\+4D\>L\+4, and0<ε≤δ0<\\varepsilon\\leq\\delta, with the family defined above, and let every alternative be started from the common initial states1=x0s\_\{1\}=x\_\{0\}\(the bad state of the tree root; the bound holds verbatim for any fixed commons1s\_\{1\}, changing only the boundary term throughsp⁡\(hi\)\\operatorname\{sp\}\(h\_\{i\}\)\)\. Every learning algorithm satisfies

supM∈𝔐𝔼M​\[ℛT\]≥\\displaystyle\\sup\_\{M\\in\\mathfrak\{M\}\}\\mathbb\{E\}\_\{M\}\[\\mathcal\{R\}\_\{T\}\]\\geq\{\}g\(δ,ε\)\[cε\(T−1δ−L\)−Tm\\displaystyle g\(\\delta,\\varepsilon\)\\Bigg\[c\_\{\\varepsilon\}\\left\(T\-\\frac\{1\}\{\\delta\}\-L\\right\)\-\\frac\{T\}\{m\}−TT2​m​kl⁡\(δ,δ\+ε\)\]−Bh\.\\displaystyle\\hskip 34\.1433pt\-T\\sqrt\{\\frac\{T\}\{2m\}\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)\}\\Bigg\]\-B\_\{h\}\.\(18\)Every quantity on the right\-hand side is given explicitly in Table[2](https://arxiv.org/html/2608.07725#Sx3.T2)\.

#### Proof roadmap\.

The proof has four auditable steps\. First, the adaptive chain rule expresses the trajectory divergence betweenM0M\_\{0\}andMiM\_\{i\}as the expected number of selections of coordinateiitimes the exact Bernoulli divergence in \([10](https://arxiv.org/html/2608.07725#Sx3.E10)\); Pinsker and averaging then give Lemma[1](https://arxiv.org/html/2608.07725#Thmtheorem1)without assuming uniform visitation\. Second, the entry–exit identity \([13](https://arxiv.org/html/2608.07725#Sx3.E13)\) converts the horizon into a lower bound on statistical decisions in bad states\. Third, navigation is charged inside the original MDP: moves toward the distinguished block can be free only for at mostLLmore steps than moves away, yielding \([16](https://arxiv.org/html/2608.07725#Sx3.E16)\)\. Finally, the average\-reward performance\- difference identity charges every non\-distinguished statistical decision byg​\(δ,ε\)g\(\\delta,\\varepsilon\)and loses at mostBhB\_\{h\}through the terminal bias\. Minimizing the resulting expression over expected navigation time and applying Lemma[1](https://arxiv.org/html/2608.07725#Thmtheorem1)gives \([18](https://arxiv.org/html/2608.07725#Sx3.E18)\)\. Complete algebra and the performance\-difference derivation are in Supplementary Appendix A\.

Because \([6](https://arxiv.org/html/2608.07725#Sx3.E6)\) givesD​\(Mi\)≤DD\(M\_\{i\}\)\\leq Dfor everyMi∈𝔐M\_\{i\}\\in\\mathfrak\{M\}\(with equality neither assumed nor needed\), the certificate is a minimax statement over the*diameter\-bounded*class

ℳ≤D\(S,A\):=\{M:\\displaystyle\\mathcal\{M\}\_\{\\leq D\}\(S,A\)=\\\{M:\|𝒮\|=S,maxs⁡\|𝒜​\(s\)\|≤A,\\displaystyle\|\\mathcal\{S\}\|=S,\\ \\max\_\{s\}\|\\mathcal\{A\}\(s\)\|\\leq A,\(19\)Mcommunicating andD\(M\)≤D\}\.\\displaystyle M\\text\{ communicating and \}D\(M\)\\leq D\\\}\.namely

inf𝒜supM∈ℳ≤D​\(S,A\)𝔼M​\[ℛT\]\\displaystyle\\inf\_\{\\mathcal\{A\}\}\\sup\_\{M\\in\\mathcal\{M\}\_\{\\leq D\}\(S,A\)\}\\mathbb\{E\}\_\{M\}\[\\mathcal\{R\}\_\{T\}\]≥inf𝒜supM∈𝔐𝔼M​\[ℛT\]\\displaystyle\\geq\\inf\_\{\\mathcal\{A\}\}\\sup\_\{M\\in\\mathfrak\{M\}\}\\mathbb\{E\}\_\{M\}\[\\mathcal\{R\}\_\{T\}\]≥RHS of \([18](https://arxiv.org/html/2608.07725#Sx3.E18)\)\.\\displaystyle\\geq\\text\{RHS of \\eqref\{eq:lowercertificate\}\}\.where the infimum is over all learning algorithms𝒜\\mathcal\{A\}and the first inequality holds because𝔐⊆ℳ≤D​\(S,A\)\\mathfrak\{M\}\\subseteq\\mathcal\{M\}\_\{\\leq D\}\(S,A\)\(a supremum over the larger class dominates\), while the second is Theorem[2](https://arxiv.org/html/2608.07725#Thmtheorem2)applied to the worst algorithm\. We state the bound overℳ≤D\\mathcal\{M\}\_\{\\leq D\}rather than at an exact diameter to avoid the slight slippage against the exact\-diameter phrasing ofJakschet al\.\([2010](https://arxiv.org/html/2608.07725#bib.bib1)\): ourDDis an upper bound on the family diameter, so the certificate is a valid lower bound for the diameter\-≤D\\leq Dminimax regret\.

For numerical evaluation, setε=η​m/\(D​T\)\\varepsilon=\\eta\\sqrt\{m/\(DT\)\}and define

cLB​\(S,A,D,T\):=maxη:0<ε≤δ⁡right\-hand side of \([18](https://arxiv.org/html/2608.07725#Sx3.E18)\)D​S​A​T\.c\_\{\\rm LB\}\(S,A,D,T\):=\\max\_\{\\eta:\\,0<\\varepsilon\\leq\\delta\}\\frac\{\\text\{right\-hand side of \\eqref\{eq:lowercertificate\}\}\}\{\\sqrt\{DSAT\}\}\.\(20\)This is a deterministic one\-dimensional optimization of the exact certificate, not an empirical estimate\.

To turn the exact certificate into uniform finite statements, define

𝒢​\(S∘,A∘,d∘,C∘\):=\{S≥S∘​even,A≥A∘,D≥d∘​\(L\+1\),T≥C∘​D​S​A\}\.\\mathcal\{G\}\(S\_\{\\circ\},A\_\{\\circ\},d\_\{\\circ\},C\_\{\\circ\}\):=\\left\\\{\\begin\{aligned\} &S\\geq S\_\{\\circ\}\\text\{ even\},\\quad A\\geq A\_\{\\circ\},\\\\ &D\\geq d\_\{\\circ\}\(L\+1\),\\quad T\\geq C\_\{\\circ\}DSA\\end\{aligned\}\\right\\\}\.\(21\)HereLLis always the exact diameter of the tree belonging to the currentSS\. LetL∘L\_\{\\circ\}be the same quantity atS=S∘S=S\_\{\\circ\}, setη=2/3\\eta=2/3, and define

r∘\\displaystyle r\_\{\\circ\}=A∘−32​A∘,\\displaystyle=\\frac\{A\_\{\\circ\}\-3\}\{2A\_\{\\circ\}\},m∘\\displaystyle m\_\{\\circ\}=S∘​\(A∘−3\)2,\\displaystyle=\\frac\{S\_\{\\circ\}\(A\_\{\\circ\}\-3\)\}\{2\},n∘\\displaystyle n\_\{\\circ\}=S∘​A∘,\\displaystyle=S\_\{\\circ\}A\_\{\\circ\},u∘\\displaystyle u\_\{\\circ\}=η2​2​C∘,\\displaystyle=\\frac\{\\eta\}\{2\\sqrt\{2C\_\{\\circ\}\}\},δ∘\\displaystyle\\delta\_\{\\circ\}=2\(d∘−1\)​L∘\+d∘,\\displaystyle=\\frac\{2\}\{\(d\_\{\\circ\}\-1\)L\_\{\\circ\}\+d\_\{\\circ\}\},q∘\\displaystyle q\_\{\\circ\}=δ∘​\(1\+u∘\),\\displaystyle=\\delta\_\{\\circ\}\(1\+u\_\{\\circ\}\),c∘\\displaystyle c\_\{\\circ\}=12\+u∘,\\displaystyle=\\frac\{1\}\{2\+u\_\{\\circ\}\},v∘\\displaystyle v\_\{\\circ\}=η8​\(1−q∘\),\\displaystyle=\\frac\{\\eta\}\{\\sqrt\{8\(1\-q\_\{\\circ\}\)\}\},α∘\\displaystyle\\alpha\_\{\\circ\}=1−1d∘\.\\displaystyle=1\-\\frac\{1\}\{d\_\{\\circ\}\}\.\(22\)Also let

w∘=1−12​C∘​n∘−1C∘​d∘​n∘,β∘=c∘​w∘−1m∘−v∘\.w\_\{\\circ\}=1\-\\frac\{1\}\{2C\_\{\\circ\}n\_\{\\circ\}\}\-\\frac\{1\}\{C\_\{\\circ\}d\_\{\\circ\}n\_\{\\circ\}\},\\qquad\\beta\_\{\\circ\}=c\_\{\\circ\}w\_\{\\circ\}\-\\frac\{1\}\{m\_\{\\circ\}\}\-v\_\{\\circ\}\.\(23\)The associated analytic envelope is

c¯​\(S∘,A∘,d∘,C∘\):=\\displaystyle\\underline\{c\}\(S\_\{\\circ\},A\_\{\\circ\},d\_\{\\circ\},C\_\{\\circ\}\):=\{\}η​r∘​α∘2​\(2\+u∘\)​β∘\\displaystyle\\frac\{\\eta\\sqrt\{r\_\{\\circ\}\}\\alpha\_\{\\circ\}\}\{2\(2\+u\_\{\\circ\}\)\}\\beta\_\{\\circ\}−12\+12​d∘C∘​n∘\.\\displaystyle\-\\frac\{\\frac\{1\}\{2\}\+\\frac\{1\}\{2d\_\{\\circ\}\}\}\{\\sqrt\{C\_\{\\circ\}\}\\,n\_\{\\circ\}\}\.\(24\)The passage from Theorem[2](https://arxiv.org/html/2608.07725#Thmtheorem2)to this envelope is monotone rather than asymptotic: the regime lower\-bounds the action fractionm/\(S​A\)m/\(SA\)and geometric factor\(D−L\)/D\(D\-L\)/D, upper\-bounds the normalized perturbation and exact\-KL testing loss, and controls the flow, navigation, and terminal\- bias boundary terms uniformly\. Thus each row of Table[3](https://arxiv.org/html/2608.07725#Sx3.T3)certifies an entire infinite parameter region, not only the displayed corner point\.

###### Theorem 3\(Uniform finite constant envelope\)\.

Ifu∘≤1u\_\{\\circ\}\\leq 1,q∘<1q\_\{\\circ\}<1,w∘≥0w\_\{\\circ\}\\geq 0, andβ∘≥0\\beta\_\{\\circ\}\\geq 0, then every point in𝒢​\(S∘,A∘,d∘,C∘\)\\mathcal\{G\}\(S\_\{\\circ\},A\_\{\\circ\},d\_\{\\circ\},C\_\{\\circ\}\)satisfies

supM∈𝔐𝔼M​\[ℛT\]≥c¯​\(S∘,A∘,d∘,C∘\)​D​S​A​T\.\\sup\_\{M\\in\\mathfrak\{M\}\}\\mathbb\{E\}\_\{M\}\[\\mathcal\{R\}\_\{T\}\]\\geq\\underline\{c\}\(S\_\{\\circ\},A\_\{\\circ\},d\_\{\\circ\},C\_\{\\circ\}\)\\sqrt\{DSAT\}\.\(25\)The coefficient in \([24](https://arxiv.org/html/2608.07725#Sx3.E24)\) is a symbolic lower envelope of Theorem[2](https://arxiv.org/html/2608.07725#Thmtheorem2); it does not rely on a numerical optimizer or an asymptotic KL expansion\.

#### Uniform\-envelope proof intuition\.

Fixingη=2/3\\eta=2/3leaves four quantities to control uniformly over a regime\. First, the action fractionr=m/\(S​A\)r=m/\(SA\)and geometric factorα=\(D−L\)/D\\alpha=\(D\-L\)/Dare lower\-bounded by their corner values\. Second, the normalized perturbationu=ε/δu=\\varepsilon/\\deltaand the transition probabilityδ​\(1\+u\)\\delta\(1\+u\)are upper\-bounded, which makes the finite Bernoulli\-KL inequality valid throughout the regime\. Third,T≥C∘​D​S​AT\\geq C\_\{\\circ\}DSAcontrols the flow and navigation boundaries and bounds the testing term after normalization byTT\. Finally, the terminal\-bias loss is bounded usingBh≤\(D\+L\)/2B\_\{h\}\\leq\(D\+L\)/2andD≥d∘​\(L\+1\)D\\geq d\_\{\\circ\}\(L\+1\)\. Multiplying the nonnegative lower bounds for the regret scale and the surviving occupancy bracket, then subtracting the normalized bias boundary, gives \([24](https://arxiv.org/html/2608.07725#Sx3.E24)\)\. This is why the theorem needs the explicit checksu∘≤1u\_\{\\circ\}\\leq 1,q∘<1q\_\{\\circ\}<1,w∘≥0w\_\{\\circ\}\\geq 0, andβ∘≥0\\beta\_\{\\circ\}\\geq 0: each corresponds to a finite validity or nonnegativity condition, not a numerical tuning heuristic\.

Table 3:Certified finite constant frontier\. A row applies to every\(S,A,D,T\)∈𝒢​\(S∘,A∘,d∘,C∘\)\(S,A,D,T\)\\in\\mathcal\{G\}\(S\_\{\\circ\},A\_\{\\circ\},d\_\{\\circ\},C\_\{\\circ\}\)\. “Analytic envelope value” is the conservative symbolic envelope \([24](https://arxiv.org/html/2608.07725#Sx3.E24)\) evaluated in closed form before rounding—an exact evaluation of a lower\-bounding envelope, not the per\-instance optimized certificate \([20](https://arxiv.org/html/2608.07725#Sx3.E20)\), which is at least as large; the reported coefficients are rounded down\. The moderate regime𝒢​\(40,10,8,25\)\\mathcal\{G\}\(40,10,8,25\)gives0\.02000\.0200\(a33\.3%33\.3\\%improvement\) and is our headline finite guarantee; the action\-rich rows extend the frontier up to0\.02910\.0291, and the94%94\\%figure is the endpoint of that frontier at the stringentA≥100A\\geq 100regime\.###### Corollary 4\(Finite improvement over the published coefficient\)\.

Every row of Table[3](https://arxiv.org/html/2608.07725#Sx3.T3)gives a coefficient strictly larger than the explicit0\.0150\.015coefficient ofJakschet al\.\([2010](https://arxiv.org/html/2608.07725#bib.bib1)\)\. This is a pointwise stronger numerical lower bound on the intersection of the two stated finite regimes, not a claim that their horizon conditions are identical\. The first and third rows additionally extend the new construction to action counts below the earlier requirementA≥10A\\geq 10\. In particular,

\(S,A,D,T\)\\displaystyle\(S,A,D,T\)∈𝒢​\(40,10,8,25\)\\displaystyle\\in\\mathcal\{G\}\(0,0,8,5\)\(26\)⟹supM∈𝔐𝔼M​\[ℛT\]≥0\.0200​D​S​A​T\.\\displaystyle\\Longrightarrow\\quad\\sup\_\{M\\in\\mathfrak\{M\}\}\\mathbb\{E\}\_\{M\}\[\\mathcal\{R\}\_\{T\}\]\\geq 0200\\sqrt\{DSAT\}\.and the action\-rich row𝒢​\(24,50,8,25\)\\mathcal\{G\}\(24,50,8,25\)certifies0\.02390\.0239\. The most stringent displayed regime,𝒢​\(100,100,64,100\)\\mathcal\{G\}\(100,100,64,100\), certifies0\.02910\.0291\.

The improvement is not obtained from an asymptotic KL expansion\. It follows from the exact finite certificate and the common analytic envelope in \([24](https://arxiv.org/html/2608.07725#Sx3.E24)\); the different rows only trade population, action, diameter, and horizon thresholds\.

#### How to read the finite frontier\.

The rows of Table[3](https://arxiv.org/html/2608.07725#Sx3.T3)answer different finite\-sample questions and should not be collapsed into a single coefficient detached from its regime\. The first row shows that the construction already beats0\.0150\.015when onlyA≥5A\\geq 5is assumed, but it pays for that breadth through the conservative requirementsD≥64​\(L\+1\)D\\geq 64\(L\+1\)andT≥100​D​S​AT\\geq 100DSA\. The headline row𝒢​\(40,10,8,25\)\\mathcal\{G\}\(40,10,8,25\)gives the cleaner0\.02000\.0200certificate under moderate action, diameter, and horizon thresholds\. The0\.02910\.0291endpoint is stronger numerically but applies only in the action\-rich regimeS≥100S\\geq 100,A≥100A\\geq 100,D≥64​\(L\+1\)D\\geq 64\(L\+1\), andT≥100​D​S​AT\\geq 100DSA\. Thus the frontier is a menu of proved trade\-offs, not a claim that one row uniformly dominates every earlier result\. Comparison with the published0\.0150\.015certificate is pointwise on the intersection of the two finite regimes\. Moreover, the displayed values are rounded\-down evaluations of the common analytic envelope; the per\-instance one\-dimensional optimization in \([20](https://arxiv.org/html/2608.07725#Sx3.E20)\) can only be larger, but is not needed for the uniform theorem\.

#### Why exact finite accounting changes the coefficient\.

The coefficient is not determined by the testing inequality alone\. The exact KL term controls how often the distinguished coordinate can be identified, but the learner may also spend time in good states or navigate among blocks\. Equation \([14](https://arxiv.org/html/2608.07725#Sx3.E14)\) converts total time into bad\-state statistical decisions after charging the flow boundary1/δ1/\\delta; Equation \([16](https://arxiv.org/html/2608.07725#Sx3.E16)\) prevents navigation from consuming the horizon without regret; andBhB\_\{h\}pays for the terminal bias in the average\-reward performance\-difference identity\. Dropping any one of these terms can improve a symbolic coefficient while invalidating the finite certificate\. Conversely, replacing the exact occupancy factorcε=\(2\+ε/δ\)−1c\_\{\\varepsilon\}=\(2\+\\varepsilon/\\delta\)^\{\-1\}by a uniform1/31/3loses enough mass that the best Pinsker coefficient falls below the published0\.0150\.015benchmark\. The frontier therefore comes from balancing information, occupancy, geometry, and boundary losses under one common parameter choice, rather than from inserting an asymptotic Bernoulli expansion into a bandit lower bound\.

For context, ifS→∞S\\to\\infty,L/D→0L/D\\to 0, andT/\(D​S​A\)→∞T/\(DSA\)\\to\\inftywith fixedA≥5A\\geq 5, optimizing the limiting Pinsker expression gives

cLB∞​\(A\)=132​A−3A,c\_\{\\rm LB\}^\{\\infty\}\(A\)=\\frac\{1\}\{32\}\\sqrt\{\\frac\{A\-3\}\{A\}\},\(27\)which approaches1/321/32asA→∞A\\to\\infty\. Equation \([27](https://arxiv.org/html/2608.07725#Sx3.E27)\) is reported only as an interpretive limit; the advertised results are the finite statements in Table[3](https://arxiv.org/html/2608.07725#Sx3.T3)\.

## Auditable Upper Certificates and Comparability

The lower section is a proved result\. The upper contribution is deliberately different: it is a ledger for a possible span\-dependent proof, not a new regret theorem\. Consider an optimistic learner supplied withH¯≥H\\bar\{H\}\\geq H, count\-doubling episodes, empirical\-Bernstein reward intervals, full\-simplex transition uncertainty, and a span\-constrained planning oracle\. The deterministic reward\-radius sum is provable, but three leading obligations remain: confidence uniform over every data\-dependent bias used by the planner, an adaptive directional\-variance budget, and martingale/boundary/planning control with square\-root rather than range\-linear dependence onH¯\\bar\{H\}\. Supplementary Appendix B gives the complete algorithmic interface and ledger\.

#### Candidate interface\.

At episode starttkt\_\{k\}, letNk​\(s,a\)N\_\{k\}\(s,a\)denote the pre\-episode count and set

Lk\\displaystyle L\_\{k\}=log⁡\(cL​S​A​\(1\+tk\)2δ\),\\displaystyle=\\log\\\!\\left\(\\frac\{c\_\{L\}SA\(1\+t\_\{k\}\)^\{2\}\}\{\\delta\}\\right\),LT\\displaystyle L\_\{T\}=log⁡\(cL​S​A​\(1\+T\)2δ\)\.\\displaystyle=\\log\\\!\\left\(\\frac\{c\_\{L\}SA\(1\+T\)^\{2\}\}\{\\delta\}\\right\)\.\(28\)wherecL≥1c\_\{L\}\\geq 1is a fixed numerical peeling constant\. For fewer than two observations, the reward interval is\[0,1\]\[0,1\]and the transition set is the full simplex\. Thereafter the reward radius is \([30](https://arxiv.org/html/2608.07725#Sx4.E30)\)\. Transition uncertainty must control the direction selected by the data\-dependent optimistic bias, for example through a radius of the form

βkp​\(s,a;h\)=2​Varp^k⁡\(h\)​LkNk​\(s,a\)\+7​H¯​Lk3​\(Nk​\(s,a\)−1\),\\beta^\{p\}\_\{k\}\(s,a;h\)=\\sqrt\{\\frac\{2\\operatorname\{Var\}\_\{\\widehat\{p\}\_\{k\}\}\(h\)L\_\{k\}\}\{N\_\{k\}\(s,a\)\}\}\+\\frac\{7\\bar\{H\}L\_\{k\}\}\{3\(N\_\{k\}\(s,a\)\-1\)\},\(29\)withsp⁡\(h\)≤H¯\\operatorname\{sp\}\(h\)\\leq\\bar\{H\}\. A pointwise inequality for one fixedhhis insufficient: the event must be uniform over every bias vector reachable by the planner\. The planning subroutine must return a feasible extended\-MDP policy and bias with span at mostH¯\\bar\{H\}, preserve optimism up to a reported residual, and terminate in polynomial time\. Episodes end when a within\-episode state–action count reaches its pre\-episode count, giving the doubling sums used in Lemma[5](https://arxiv.org/html/2608.07725#Thmtheorem5)\. This interface makes the statistical and computational promises visible before any coefficient is assembled\.

#### Why the open entries matter\.

Replacing the adaptive variance in \([29](https://arxiv.org/html/2608.07725#Sx4.E29)\) by the range boundH¯2\\bar\{H\}^\{2\}yields a range\-linearH¯​S​A​T\\bar\{H\}\\sqrt\{SAT\}term rather than the desiredH¯​S​A​T\\sqrt\{\\bar\{H\}SAT\}\. Restricting the transition set to empirically observed successors can break coverage, while coordinatewise clipping of ordinary value iteration need not preserve optimism or convergence\. Thus the missing entries are not cosmetic constants: they determine whether the candidate procedure has the claimed structural rate and whether it is a valid polynomial\-time algorithm\.

###### Assumption 1\(Uniform confidence and optimism\)\.

The confidence event is uniform over all data\-dependent biases used by the planner and preserves optimism up to the reported planning error\.

The proved reward entry uses the empirical\-Bernstein radius

βkr​\(s,a\)=2​v^kr​\(s,a\)​LkNk​\(s,a\)\+7​Lk3​\(Nk​\(s,a\)−1\)\.\\beta^\{r\}\_\{k\}\(s,a\)=\\sqrt\{\\frac\{2\\widehat\{v\}^\{r\}\_\{k\}\(s,a\)L\_\{k\}\}\{N\_\{k\}\(s,a\)\}\}\+\\frac\{7L\_\{k\}\}\{3\(N\_\{k\}\(s,a\)\-1\)\}\.\(30\)with full intervals for fewer than two observations and count\-doubling episodes\.

###### Lemma 5\(Reward\-radius budget\)\.

ForT≥2T\\geq 2,

∑t=1Tβk​\(t\)r​\(st,at\)≤2\+22​S​A​T​LT\+203​S​A​LT2\.\\sum\_\{t=1\}^\{T\}\\beta^\{r\}\_\{k\(t\)\}\(s\_\{t\},a\_\{t\}\)\\leq\\frac\{2\+\\sqrt\{2\}\}\{\\sqrt\{2\}\}\\sqrt\{SATL\_\{T\}\}\+\\frac\{20\}\{3\}SAL\_\{T\}^\{2\}\.\(31\)

#### Completed reward entry\.

The square\-root coefficient in Lemma[5](https://arxiv.org/html/2608.07725#Thmtheorem5)is a deterministic consequence of the chosen episode rule\. If an episode begins with countnkn\_\{k\}and contributes at mostnkn\_\{k\}new visits, the worst geometric sequence1,2,4,…1,2,4,\\ldotsgives∑kvk/nk≤\(2\+2\)​N\\sum\_\{k\}v\_\{k\}/\\sqrt\{n\_\{k\}\}\\leq\(2\+\\sqrt\{2\}\)\\sqrt\{N\}\. Summing over state–action pairs and usingv^kr≤1/4\\widehat\{v\}\_\{k\}^\{r\}\\leq 1/4yields\(2\+2\)/2\(2\+\\sqrt\{2\}\)/\\sqrt\{2\}in front ofS​A​T​LT\\sqrt\{SATL\_\{T\}\}\. The linear Bernstein remainder, including the first two observations of each pair, contributes the conservative\(20/3\)​S​A​LT2\(20/3\)SAL\_\{T\}^\{2\}term\. These constants apply to episode\-frozen bonuses; a smaller per\-visit harmonic constant would describe a different algorithm and cannot be substituted into this ledger\.

###### Assumption 2\(Directional transition budget\)\.

For explicit constantsCp,Cp′,qpC\_\{p\},C^\{\\prime\}\_\{p\},q\_\{p\},

∑t=1Tβk​\(t\)p​\(st,at;h~k​\(t\)\)≤Cp​H¯​S​A​T​LT\+Cp′​H¯​S​A​LTqp\.\\sum\_\{t=1\}^\{T\}\\beta^\{p\}\_\{k\(t\)\}\(s\_\{t\},a\_\{t\};\\widetilde\{h\}\_\{k\(t\)\}\)\\leq C\_\{p\}\\sqrt\{\\bar\{H\}SATL\_\{T\}\}\+C^\{\\prime\}\_\{p\}\\bar\{H\}SAL\_\{T\}^\{q\_\{p\}\}\.

###### Assumption 3\(Remainder and planning budget\)\.

For explicit constantsCm,Cm′,qm,CϵC\_\{m\},C^\{\\prime\}\_\{m\},q\_\{m\},C\_\{\\epsilon\}, the martingale, episode\-boundary, and planning terms are at most

Cm​H¯​T​LT\+Cm′​H¯​S​A​LTqm\+Cϵ​T\.C\_\{m\}\\sqrt\{\\bar\{H\}TL\_\{T\}\}\+C^\{\\prime\}\_\{m\}\\bar\{H\}SAL\_\{T\}^\{q\_\{m\}\}\+C\_\{\\epsilon\}\\sqrt\{T\}\.

###### Proposition 6\(Conditional ledger composition\)\.

If a concrete algorithm proves the uniform confidence, directional\-variance, and remainder obligations with numerical constants, then with probability at least1−δ1\-\\delta,

ℛT≤CUB​H¯​S​A​T​LT\+Clow​H¯​S​A​LTq\+Cϵ​T,\\mathcal\{R\}\_\{T\}\\leq C\_\{\\rm UB\}\\sqrt\{\\bar\{H\}SATL\_\{T\}\}\+C\_\{\\rm low\}\\bar\{H\}SAL\_\{T\}^\{q\}\+C\_\{\\epsilon\}\\sqrt\{T\},\(32\)whereCUBC\_\{\\rm UB\}is the sum of the reward, transition, and martingale square\-root coefficients\. Only the reward entry is completed here; therefore no upper coefficient is claimed\.

#### Why the upper constants add rather than multiply\.

On the optimism event, the regret decomposition inserts the extended Bellman equation and separates five terms: reward estimation, directional transition estimation, the transition martingale, changes of the optimistic bias across episode boundaries, and the planning residual\. Count doubling controls the reward term and yields Lemma[5](https://arxiv.org/html/2608.07725#Thmtheorem5)\. Assumption[2](https://arxiv.org/html/2608.07725#Thmassumption2)would control the second term, while Assumption[3](https://arxiv.org/html/2608.07725#Thmassumption3)groups the remaining stochastic, boundary, and planning contributions\. After each term is placed on the common scaleH¯​S​A​T​LT\\sqrt\{\\bar\{H\}SATL\_\{T\}\}, their leading coefficients add toCUBC\_\{\\rm UB\}\. This bookkeeping rules out a common shortcut in which a local Bernstein factor is multiplied by an informal “optimism factor” while martingale and planning terms are left implicit\. It also makes the status of the result auditable: the reward coefficient is proved, the composition is proved conditionally, and the transition and planning entries remain open\. Until a single concrete polynomial\-time planner certifies those entries under one uniform confidence event, Table[4](https://arxiv.org/html/2608.07725#Sx4.T4)cannot support a numerical upper constant\.

A fixed\-algorithm expectation conversion is valid: run the completed algorithm once withδ=1/T\\delta=1/T; sinceℛT≤T\\mathcal\{R\}\_\{T\}\\leq T, the expected regret is at most the right\-hand side of \([32](https://arxiv.org/html/2608.07725#Sx4.E32)\) atδ=1/T\\delta=1/Tplus11\. Varyingδ\\deltainside a tail integral would instead vary the algorithm\. Likewise, an upper\-to\-lower ratio is a constant only when the two sides share probability mode, structural term, and logarithmic normalization\. If the upper bound retainsLT\\sqrt\{L\_\{T\}\}while the lower bound is log\-free, the correct object is a horizon\-dependent envelope, notCUB/cLBC\_\{\\rm UB\}/c\_\{\\rm LB\}alone\.

Table 4:Upper\-certificate ledger\. Open leading entries prevent a numerical upper coefficient\.###### Corollary 7\(Fixed\-algorithm expectation conversion\)\.

If Proposition[6](https://arxiv.org/html/2608.07725#Thmtheorem6)is completed for a fixed algorithm run withδ=1/T\\delta=1/T, then its expected regret is at most the right\-hand side of \([32](https://arxiv.org/html/2608.07725#Sx4.E32)\) plus11\.

The proof splits expectation over the success event and usesℛT≤T\\mathcal\{R\}\_\{T\}\\leq Ton failure\. An anytime conversion would require one fixed confidence\-sequence algorithm and its additional constants\.

###### Definition 2\(Comparable coefficient ratio\)\.

Suppose an expected lower bound and an expected upper bound use the same structural normalizationG​\(S,A,D,T\)G\(S,A,D,T\)and the same logarithmic factorΛT\\Lambda\_\{T\}\. Only then do we define the constant ratio

κ=CUBcLB\.\\kappa=\\frac\{C\_\{\\rm UB\}\}\{c\_\{\\rm LB\}\}\.If the upper bound contains a nonconstant factorΛT\\Lambda\_\{T\}absent from the lower bound, the appropriate comparison is instead the finite\-horizon envelope

κT=CUBcLB​ΛT\+upper lower\-order termscLB​G​\(S,A,D,T\)\.\\kappa\_\{T\}=\\frac\{C\_\{\\rm UB\}\}\{c\_\{\\rm LB\}\}\\Lambda\_\{T\}\+\\frac\{\\text\{upper lower\-order terms\}\}\{c\_\{\\rm LB\}G\(S,A,D,T\)\}\.\(33\)

###### Corollary 8\(No constant\-factor conclusion with an unmatched logarithm\)\.

If the lower bound iscLB​D​S​A​Tc\_\{\\rm LB\}\\sqrt\{DSAT\}and a completed upper bound on the same family isCUB​D​S​A​T​LTC\_\{\\rm UB\}\\sqrt\{DSATL\_\{T\}\}, thenCUB/cLBC\_\{\\rm UB\}/c\_\{\\rm LB\}is only a ledger diagnostic\. The full upper\-to\-lower envelope retains at least\(CUB/cLB\)​LT\(C\_\{\\rm UB\}/c\_\{\\rm LB\}\)\\sqrt\{L\_\{T\}\}until a common logarithmic normalization is proved\.

The main sources of possible upper\-bound slack are also distinct: bonus shape, valid confidence geometry, span width, and the reciprocal lower coefficient\. Replacing a span widthH¯\\bar\{H\}by diameter inflates a square\-root term byD/H¯\\sqrt\{D/\\bar\{H\}\}, while width\-linear lower\-order terms may incurD/H¯D/\\bar\{H\}; these factors should not be conflated\.

Table 5:Confirmatory outcomes\. Intervals are95%95\\%; full denominators, simultaneous corrections, and per\-family tables are in Supplementary Appendix D\.

## Controlled Diagnostics

The experiments test mechanisms implied by the corrected analysis rather than estimate a theorem constant\. RQ1–RQ3 use the same heuristic span\-clipped optimistic routine under controlled changes in bonus and supplied width\. We do not identify this routine with SCAL or PMEVI\-DT because coordinatewise clipping is not a certified planning operator\. RQ4 uses the exact family from the finite lower\-certificate section and runs every alternative\. All primary comparisons are paired and use matched horizons; environment integrity checks, uncertainty calculations, protocol tables, and negative pilots are supplementary\. RQ1 tests whether raw regret displays detectable positive diameter dependence when the optimal bias span is zero\. RQ2 isolates bonus shape from supplied planning width\. RQ3 holds the transition geometry fixed and changes only the width supplied to the heuristic planner\. RQ4 is different: it evaluates the exact proved family and checks the direction of the finite certificate\. These diagnostics test mechanisms and implementation consistency; none supplies the missing adaptive\-variance or planning proof required by Proposition[6](https://arxiv.org/html/2608.07725#Thmtheorem6)\.

#### Claim\-to\-test map\.

RQ1 targets the floor inH=1∨sp⁡\(h⋆\)H=1\\vee\\operatorname\{sp\}\(h^\{\\star\}\): when the optimal bias span is zero, a detectable positive diameter slope would contradict the intended diameter\-independent diagnostic behavior of the span\-width heuristic, whereas a null result is only absence of evidence at the tested scale\. RQ2 asks whether any observed improvement comes from the Bernstein bonus itself or from the supplied planning width; the factorial design is therefore interpreted through matched\-width contrasts rather than an unmatched headline average\. RQ3 holds the transition kernel and measured diameter fixed and varies only the supplied width, isolating the cost of conservative span knowledge\. Its square\-root fit is a local shape comparison over eight design points, not a universal regret law\. RQ4 is tied directly to Theorem[2](https://arxiv.org/html/2608.07725#Thmtheorem2): because the proof averages over allmmalternatives before taking a maximum, the check runs the complete alternative population rather than a convenient single instance\. Passing RQ4 confirms construction and certificate consistency, but the large gap between the certificate and observed regret shows that it is not evidence of practical tightness\.

#### Uncertainty and multiplicity\.

RQ1 and RQ2 report one primary paired contrast\. RQ3 uses Bonferroni\-simultaneous95%95\\%intervals over eight ratios; its RMS\-fit interval resamples paired seeds within each width ratio\. RQ4 treats the alternatives as the finite population, resampling seeds within each alternative and using simultaneous alternative\-wise bounds for the empirical maximum\.

## Discussion and Limitations

The lower result is a finite minimax certificate over communicating diameter\-≤D\\leq Dtabular MDPs, not an exact minimax constant\. Its strongest coefficients require action\-rich regimes; the broadA≥5A\\geq 5row has conservative diameter and horizon thresholds\. The upper result is an audit template, not a theorem: pointwise Bernstein bounds, empirical support restriction, or naive clipping do not resolve adaptive confidence and planning\. The span bound is supplied side information, and removing it requires a separately analysed adaptation procedure\. The experiments are controlled mechanism diagnostics of a heuristic planner and do not validate the open upper ledger or generalize beyond the studied tabular families\. The main open directions are better small\-AAfrontiers, certified prior\-free span adaptation, and a log\-matched expected upper bound under the same normalization\.

Average\-reward constants are meaningful only with their probability mode, structural term, logarithmic normalization, finite regime, and side information\. Our exact\-KL construction proves a finite lower frontier from0\.01520\.0152to0\.02910\.0291\. The upper ledger exposes the adaptive\-variance and planning certificates still needed for a valid span\-dependent coefficient\. Probability conversion and coefficient comparisons use matched normalizations, while experiments remain diagnostic rather than substitutes for theorem obligations\.

## References

- Y\. Abbasi\-Yadkori, P\. Bartlett, K\. Bhatia, N\. Lazic, C\. Szepesvári, and G\. Weisz \(2019\)POLITEX: regret bounds for policy iteration using expert prediction\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 3692–3702\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- S\. Agrawal and R\. Jia \(2017\)Posterior sampling for reinforcement learning: worst\-case regret bounds\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 1184–1194\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- P\. Assouad \(1983\)Deux remarques sur l’estimation\.Comptes Rendus de l’Académie des Sciences296\(23\),pp\. 1021–1024\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- J\. Audibert, R\. Munos, and C\. Szepesvári \(2009\)Exploration\-exploitation tradeoff using variance estimates in multi\-armed bandits\.Theoretical Computer Science410\(19\),pp\. 1876–1902\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx2.SSS0.Px1.p1.1)\.
- M\. G\. Azar, R\. Munos, and H\. J\. Kappen \(2013\)Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model\.Machine Learning91\(3\),pp\. 325–349\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- M\. G\. Azar, I\. Osband, and R\. Munos \(2017\)Minimax regret bounds for reinforcement learning\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 263–272\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- P\. L\. Bartlett and A\. Tewari \(2009\)REGAL: a regularization based algorithm for reinforcement learning in weakly communicating MDPs\.InProceedings of the Conference on Uncertainty in Artificial Intelligence \(UAI\),pp\. 35–42\.Cited by:[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9),[Table 1](https://arxiv.org/html/2608.07725#Sx2.T1.15.15.17.1.1),[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- R\. Bellman \(1957\)A Markovian decision process\.Journal of Mathematics and Mechanics6\(5\),pp\. 679–684\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- D\. P\. Bertsekas \(2012\)Dynamic programming and optimal control\.4th edition, Vol\.2,Athena Scientific\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- V\. Boone and Z\. Zhang \(2024\)Achieving tractable minimax optimal regret in average reward mdps\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 26728–26769\.External Links:[Document](https://dx.doi.org/10.52202/079017-0840),2406\.01234Cited by:[Appendix B](https://arxiv.org/html/2608.07725#A2.SSx6.p1.1),[Appendix D](https://arxiv.org/html/2608.07725#A4.SSx2.p2.2),[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9),[Table 1](https://arxiv.org/html/2608.07725#Sx2.T1.10.10.10.2),[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- S\. Boucheron, G\. Lugosi, and P\. Massart \(2013\)Concentration inequalities: a nonasymptotic theory of independence\.Oxford University Press,Oxford\.External Links:ISBN 978\-0\-19\-953525\-5,[Document](https://dx.doi.org/10.1093/acprof%3Aoso/9780199535255.001.0001),[Link](https://doi.org/10.1093/acprof:oso/9780199535255.001.0001)Cited by:[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- H\. Bourel, O\. Maillard, and M\. S\. Talebi \(2020\)Tightening exploration in upper confidence reinforcement learning\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 1056–1066\.Cited by:[Appendix D](https://arxiv.org/html/2608.07725#A4.SSx2.p2.2),[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- J\. Bretagnolle and C\. Huber \(1979\)Estimation des densités: risque minimax\.Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete47\(2\),pp\. 119–137\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- A\. N\. Burnetas and M\. N\. Katehakis \(1997\)Optimal adaptive policies for Markov decision processes\.Mathematics of Operations Research22\(1\),pp\. 222–255\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- L\. Chen, R\. Jain, and H\. Luo \(2022\)Learning infinite\-horizon average\-reward markov decision process with constraints\.InProceedings of the 39th International Conference on Machine Learning,K\. Chaudhuri, S\. Jegelka, L\. Song, C\. Szepesvári, G\. Niu, and S\. Sabato \(Eds\.\),Proceedings of Machine Learning Research, Vol\.162,pp\. 3246–3270\.External Links:[Link](https://proceedings.mlr.press/v162/chen22i.html)Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- C\. Dann and E\. Brunskill \(2015\)Sample complexity of episodic fixed\-horizon reinforcement learning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 2818–2826\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- C\. Dann, T\. Lattimore, and E\. Brunskill \(2017\)Unifying PAC and regret: uniform PAC bounds for episodic reinforcement learning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 5713–5723\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- Y\. Efroni, S\. Mannor, and M\. Pirotta \(2020\)Exploration\-exploitation in constrained MDPs\.Note:arXiv preprintExternal Links:2003\.02189,[Document](https://dx.doi.org/10.48550/arXiv.2003.02189),[Link](https://arxiv.org/abs/2003.02189)Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- R\. Fruit, M\. Pirotta, A\. Lazaric, and R\. Ortner \(2018\)Efficient bias\-span\-constrained exploration\-exploitation in reinforcement learning\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 1573–1581\.Cited by:[Appendix B](https://arxiv.org/html/2608.07725#A2.SSx6.p1.1),[Appendix D](https://arxiv.org/html/2608.07725#A4.SSx2.p2.2),[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9),[Table 1](https://arxiv.org/html/2608.07725#Sx2.T1.15.15.17.1.1),[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- R\. Fruit, M\. Pirotta, and A\. Lazaric \(2020\)Improved analysis of UCRL2 with empirical bernstein inequality\.Note:arXiv preprintExternal Links:2007\.05456,[Document](https://dx.doi.org/10.48550/arXiv.2007.05456),[Link](https://arxiv.org/abs/2007.05456)Cited by:[Appendix D](https://arxiv.org/html/2608.07725#A4.SSx2.p2.2),[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9),[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- R\. A\. Howard \(1960\)Dynamic programming and Markov processes\.The Technology Press of the Massachusetts Institute of Technology and John Wiley & Sons,Cambridge, MA and New York\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- T\. Jaksch, R\. Ortner, and P\. Auer \(2010\)Near\-optimal regret bounds for reinforcement learning\.Journal of Machine Learning Research11,pp\. 1563–1600\.Cited by:[Appendix D](https://arxiv.org/html/2608.07725#A4.SSx2.p2.2),[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9),[Introduction](https://arxiv.org/html/2608.07725#Sx1.p2.5),[Table 1](https://arxiv.org/html/2608.07725#Sx2.T1.3.3.3.4),[Table 1](https://arxiv.org/html/2608.07725#Sx2.T1.8.8.8.6),[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1),[Proof roadmap\.](https://arxiv.org/html/2608.07725#Sx3.SS0.SSS0.Px1.p2.7),[Corollary 4](https://arxiv.org/html/2608.07725#Thmtheorem4.p1.2.2)\.
- C\. Jin, Z\. Allen\-Zhu, S\. Bubeck, and M\. I\. Jordan \(2018\)Is Q\-learning provably efficient?\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 4863–4873\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- T\. Lattimore and M\. Hutter \(2012\)PAC bounds for discounted MDPs\.InProceedings of the International Conference on Algorithmic Learning Theory \(ALT\),pp\. 320–334\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- T\. Lattimore and C\. Szepesvári \(2020\)Bandit algorithms\.Cambridge University Press\.Cited by:[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- N\. Lazic, D\. Yin, Y\. Abbasi\-Yadkori, and C\. Szepesvári \(2021\)Improved regret bound and experience replay in regularized policy iteration\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 6032–6042\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- S\. Mahadevan \(1996\)Average reward reinforcement learning: foundations, algorithms, and empirical results\.Machine Learning22\(1\-3\),pp\. 159–195\.Cited by:[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9)\.
- O\. Maillard, T\. A\. Mann, and S\. Mannor \(2014\)How hard is my MDP? the distribution\-norm to the rescue\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- A\. Maurer and M\. Pontil \(2009\)Empirical Bernstein bounds and sample\-variance penalization\.InProceedings of the Conference on Learning Theory \(COLT\),Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx2.SSS0.Px1.p1.1)\.
- R\. Ortner \(2020\)Regret bounds for reinforcement learning via Markov chain concentration\.Journal of Artificial Intelligence Research67,pp\. 115–128\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- I\. Osband and B\. Van Roy \(2014\)Model\-based reinforcement learning and the eluder dimension\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- I\. Osband and B\. Van Roy \(2017\)Why is posterior sampling better than optimism for reinforcement learning?\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 2701–2710\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- Y\. Ouyang, M\. Gagrani, A\. Nayyar, and R\. Jain \(2017\)Learning unknown Markov decision processes: a Thompson sampling approach\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 1333–1342\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- M\. L\. Puterman \(1994\)Markov decision processes: discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9)\.
- P\. J\. Schweitzer \(1979\)Geometric convergence of value\-iteration in multichain Markov decision problems\.Advances in Applied Probability11\(1\),pp\. 188–217\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- M\. Simchowitz and K\. G\. Jamieson \(2019\)Non\-asymptotic gap\-dependent regret bounds for tabular MDPs\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 1153–1162\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- R\. S\. Sutton and A\. G\. Barto \(2018\)Reinforcement learning: an introduction\.2nd edition,MIT Press\.Cited by:[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9)\.
- M\. S\. Talebi and O\. Maillard \(2018\)Variance\-aware regret bounds for undiscounted reinforcement learning in MDPs\.InProceedings of the International Conference on Algorithmic Learning Theory \(ALT\),pp\. 770–805\.Cited by:[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- A\. Tewari and P\. L\. Bartlett \(2008\)Optimistic linear programming gives logarithmic regret for irreducible MDPs\.InAdvances in Neural Information Processing Systems \(NeurIPS\),pp\. 1505–1512\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- A\. B\. Tsybakov \(2009\)Introduction to nonparametric estimation\.Springer\.Cited by:[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- C\. Wei, M\. J\. Jahromi, H\. Luo, and R\. Jain \(2021\)Learning infinite\-horizon average\-reward MDPs with linear function approximation\.InProceedings of the International Conference on Artificial Intelligence and Statistics \(AISTATS\),pp\. 3007–3015\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- C\. Wei, M\. J\. Jahromi, H\. Luo, H\. Sharma, and R\. Jain \(2020\)Model\-free reinforcement learning in infinite\-horizon average\-reward Markov decision processes\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 10170–10180\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- A\. Zanette and E\. Brunskill \(2019\)Tighter problem\-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 7304–7312\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- Z\. Zhang and X\. Ji \(2019\)Regret minimization for reinforcement learning by evaluating the optimal bias function\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Introduction](https://arxiv.org/html/2608.07725#Sx1.p1.9),[Table 1](https://arxiv.org/html/2608.07725#Sx2.T1.9.9.9.2),[Setup, Related Work, and Comparison Protocol](https://arxiv.org/html/2608.07725#Sx2.p2.1)\.
- Z\. Zhang and X\. Ji \(2021\)Reinforcement learning in reward\-mixing MDPs\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Note:average\-reward span\-aware analysisCited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- Z\. Zhang and Q\. Xie \(2023\)Sharper model\-free reinforcement learning for average\-reward Markov decision processes\.InProceedings of the Thirty Sixth Conference on Learning Theory,G\. Neu and L\. Rosasco \(Eds\.\),Proceedings of Machine Learning Research, Vol\.195,pp\. 5476–5477\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p1.1)\.
- Z\. Zhang, Y\. Zhou, and X\. Ji \(2020\)Almost optimal model\-free reinforcement learning via reference\-advantage decomposition\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.
- D\. Zhou, Q\. Gu, and C\. Szepesvári \(2021\)Provably efficient reinforcement learning for discounted MDPs with feature mapping\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 12793–12802\.Cited by:[Appendix F](https://arxiv.org/html/2608.07725#A6.SSx1.p2.1)\.

## Technical Appendices of Finite Constant Frontiers and Auditable Regret Certificates for Average\-Reward Reinforcement Learning

The following appendices collect the full proofs, extended experiments, retained pilots, and reproducibility details\. They are merged here for internal review and can be separated for submission\.

## Scope of the Technical Appendices

This document contains complete proofs for the lower\- and upper\-certificate statements, full confirmatory experimental details, retained pilot results, and reproducibility information supporting the main paper\. It uses the definitions, notation, equation numbers, theorem numbers, and table labels of the main paper\. The visible appendix identifiers below are fixed for stable navigation\.

## Appendix AAppendix A: Lower\-Certificate Proofs

### A\.1 Kernel, action budget, and diameter

TheS=2​KS=2Kstates are exactly the pairs\(xj,yj\)\(x\_\{j\},y\_\{j\}\), so no auxiliary state is hidden in the construction\. A binary\-tree vertex has at most three neighbors\. Assign one navigation action to each possible parent/left\-child/right\-child edge and make absent edges self\-loops\. Together with theA−3A\-3statistical actions, every bad state has exactlyAAactions\. AllAAactions at a good state are identical copies of the return transition\. This proves the state and action entries of Table[2](https://arxiv.org/html/2608.07725#Sx3.T2)\.

For any ordered pair of states, a policy can first leave a good state if necessary, follow the unique tree path between the corresponding bad states, and repeatedly use a baseline statistical action to enter the target good state if necessary\. The three contributions are at most1/δ1/\\delta,LL, and1/δ1/\\delta, respectively\. Equation \([6](https://arxiv.org/html/2608.07725#Sx3.E6)\) follows\. A possibly faster boosted transition can only decrease a hitting time, so the same upper bound holds for every alternative\.

### A\.2 Optimal gain, bias, and navigation gaps

Fix alternativeiiand letj​\(i\)j\(i\)be the block containing its distinguished coordinate\. Definehih\_\{i\}by \([15](https://arxiv.org/html/2608.07725#Sx3.E15)\)\. At every good state,

1\+\(1−δ\)​hi​\(yv\)\+δ​hi​\(xv\)=ρi\+hi​\(yv\)\.1\+\(1\-\\delta\)h\_\{i\}\(y\_\{v\}\)\+\\delta h\_\{i\}\(x\_\{v\}\)=\\rho\_\{i\}\+h\_\{i\}\(y\_\{v\}\)\.Atxj​\(i\)x\_\{j\(i\)\}, the distinguished statistical action also satisfies equality because\(δ\+ε\)​\(1−ρi\)/δ=ρi\(\\delta\+\\varepsilon\)\(1\-\\rho\_\{i\}\)/\\delta=\\rho\_\{i\}\. At any other bad state, a navigation action towardj​\(i\)j\(i\)satisfies

hi​\(xw\)=hi​\(xv\)\+ρi\.h\_\{i\}\(x\_\{w\}\)=h\_\{i\}\(x\_\{v\}\)\+\\rho\_\{i\}\.Thus \([15](https://arxiv.org/html/2608.07725#Sx3.E15)\) andρi\\rho\_\{i\}satisfy the optimality equations\.

A baseline statistical action at any bad state has Bellman valuehi​\(xv\)\+1−ρih\_\{i\}\(x\_\{v\}\)\+1\-\\rho\_\{i\}, so its Bellman gap is2​ρi−1=g​\(δ,ε\)2\\rho\_\{i\}\-1=g\(\\delta,\\varepsilon\)\. For a navigation neighborww, the gap is

ρi​\{1\+d𝒯​\(w,j​\(i\)\)−d𝒯​\(v,j​\(i\)\)\},\\rho\_\{i\}\\\{1\+d\_\{\\mathcal\{T\}\}\(w,j\(i\)\)\-d\_\{\\mathcal\{T\}\}\(v,j\(i\)\)\\\},which equals zero toward the distinguished block and2​ρi2\\rho\_\{i\}away from it; a missing\-edge self\-loop has gapρi\\rho\_\{i\}\. Ifn−n\_\{\-\},n\+n\_\{\+\}, andn0n\_\{0\}count moves toward, moves away, and self\-loops, respectively, thenn−≤n\+\+Ln\_\{\-\}\\leq n\_\{\+\}\+L\. Hence

2​n\+\+n0≥n−\+n\+\+n0−L=Nnav​\(T\)−L,2n\_\{\+\}\+n\_\{0\}\\geq n\_\{\-\}\+n\_\{\+\}\+n\_\{0\}\-L=N\_\{\\rm nav\}\(T\)\-L,which proves \([16](https://arxiv.org/html/2608.07725#Sx3.E16)\)\. Finally, bad\-state biases lie in\[−ρi​L,0\]\[\-\\rho\_\{i\}L,0\], and every good\-state bias is obtained by adding\(1−ρi\)/δ\(1\-\\rho\_\{i\}\)/\\delta\. This proves \([17](https://arxiv.org/html/2608.07725#Sx3.E17)\)\.

### A\.3 Flow and occupancy

LetItI\_\{t\}indicate thatsts\_\{t\}is a good state\. The number of entries into good states minus the number of exits equalsIT\+1−I1I\_\{T\+1\}\-I\_\{1\}\. Conditional on the history, an entry probability is at mostδ\+ε\\delta\+\\varepsilon, while an exit probability is exactlyδ\\delta\. Taking expectations gives \([13](https://arxiv.org/html/2608.07725#Sx3.E13)\)\. SinceT=Nx\+Ny\+NnavT=N\_\{x\}\+N\_\{y\}\+N\_\{\\rm nav\},

T−𝔼i​Nnav≤\(2\+εδ\)​𝔼i​Nx\+1δ,T\-\\mathbb\{E\}\_\{i\}N\_\{\\rm nav\}\\leq\\left\(2\+\\frac\{\\varepsilon\}\{\\delta\}\\right\)\\mathbb\{E\}\_\{i\}N\_\{x\}\+\\frac\{1\}\{\\delta\},which is exactly \([14](https://arxiv.org/html/2608.07725#Sx3.E14)\)\. This argument treats navigation inside the original MDP; no free\-switching relaxation or missing simulation map is used\.

### A\.4 Exact divergence calculations

For transition parametersδ\\deltaandδ\+ε\\delta\+\\varepsilon, the exact one\-observation divergence is \([11](https://arxiv.org/html/2608.07725#Sx3.E11)\)\. Differentiating it with respect toε\\varepsilongives

∂∂ε​kl⁡\(δ,δ\+ε\)=ε\(δ\+ε\)​\(1−δ−ε\)\.\\frac\{\\partial\}\{\\partial\\varepsilon\}\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)=\\frac\{\\varepsilon\}\{\(\\delta\+\\varepsilon\)\(1\-\\delta\-\\varepsilon\)\}\.Therefore

kl⁡\(δ,δ\+ε\)=∫0εz​d​z\(δ\+z\)​\(1−δ−z\)≤ε22​δ​\(1−δ−ε\)\.\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)=\\int\_\{0\}^\{\\varepsilon\}\\frac\{z\\,dz\}\{\(\\delta\+z\)\(1\-\\delta\-z\)\}\\leq\\frac\{\\varepsilon^\{2\}\}\{2\\delta\(1\-\\delta\-\\varepsilon\)\}\.\(34\)The exact expression is used in \([20](https://arxiv.org/html/2608.07725#Sx3.E20)\); the finite upper envelope is used only to prove the uniform numerical corollary\.

The symmetric Bernoulli calculation discussed in the earlier draft is, correctly,

kl⁡\(12\+Δ,12−Δ\)\\displaystyle\\operatorname\{kl\}\\\!\\left\(\\tfrac\{1\}\{2\}\+\\Delta,\\tfrac\{1\}\{2\}\-\\Delta\\right\)=2​Δ​log⁡1/2\+Δ1/2−Δ\\displaystyle=2\\Delta\\log\\frac\{1/2\+\\Delta\}\{1/2\-\\Delta\}=8​Δ2\+323​Δ4\+O​\(Δ6\)\.\\displaystyle=8\\Delta^\{2\}\+\\frac\{32\}\{3\}\\Delta^\{4\}\+O\(\\Delta^\{6\}\)\.\(35\)The discarded intermediate expression4​Δ2/\(1/4−Δ2\)4\\Delta^\{2\}/\(1/4\-\\Delta^\{2\}\)has leading term16​Δ216\\Delta^\{2\}and is not equal to \([35](https://arxiv.org/html/2608.07725#A1.E35)\)\. More generally, an asymptotic expansion cannot establish an exact finite\-horizon coefficient unless the remainder is bounded and included\.

### A\.5 Proof of Lemma[1](https://arxiv.org/html/2608.07725#Thmtheorem1)

For anyZ∈\[0,T\]Z\\in\[0,T\],

\|𝔼i​Z−𝔼0​Z\|≤T​TV⁡\(ℙiT,ℙ0T\)≤T​12​KL⁡\(ℙ0T∥ℙiT\),\|\\mathbb\{E\}\_\{i\}Z\-\\mathbb\{E\}\_\{0\}Z\|\\leq T\\operatorname\{TV\}\(\\mathbb\{P\}\_\{i\}^\{T\},\\mathbb\{P\}\_\{0\}^\{T\}\)\\leq T\\sqrt\{\\frac\{1\}\{2\}\\operatorname\{KL\}\(\\mathbb\{P\}\_\{0\}^\{T\}\\\|\\mathbb\{P\}\_\{i\}^\{T\}\)\},where the final inequality is Pinsker’s inequality\. TakingZ=Ni​\(T\)Z=N\_\{i\}\(T\)and applying the adaptive chain rule \([10](https://arxiv.org/html/2608.07725#Sx3.E10)\) gives

𝔼i​\[Ni​\(T\)\]≤𝔼0​\[Ni​\(T\)\]\+T​12​𝔼0​\[Ni​\(T\)\]​kl⁡\(δ,δ\+ε\)\.\\mathbb\{E\}\_\{i\}\[N\_\{i\}\(T\)\]\\leq\\mathbb\{E\}\_\{0\}\[N\_\{i\}\(T\)\]\+T\\sqrt\{\\frac\{1\}\{2\}\\mathbb\{E\}\_\{0\}\[N\_\{i\}\(T\)\]\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)\}\.Averaging overii, using∑i𝔼0​\[Ni​\(T\)\]≤T\\sum\_\{i\}\\mathbb\{E\}\_\{0\}\[N\_\{i\}\(T\)\]\\leq T, and applying concavity of the square root yields

1m​∑i𝔼i​\[Ni​\(T\)\]\\displaystyle\\frac\{1\}\{m\}\\sum\_\{i\}\\mathbb\{E\}\_\{i\}\[N\_\{i\}\(T\)\]≤Tm\+Tm​12​kl⁡\(δ,δ\+ε\)\\displaystyle\\leq\\frac\{T\}\{m\}\+\\frac\{T\}\{m\}\\sqrt\{\\frac\{1\}\{2\}\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)\}×∑i𝔼0​\[Ni​\(T\)\]\\displaystyle\\hskip 36\.98857pt\\times\\sum\_\{i\}\\sqrt\{\\mathbb\{E\}\_\{0\}\[N\_\{i\}\(T\)\]\}≤Tm\+T​T2​m​kl⁡\(δ,δ\+ε\)\.\\displaystyle\\leq\\frac\{T\}\{m\}\+T\\sqrt\{\\frac\{T\}\{2m\}\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)\}\.which is \([12](https://arxiv.org/html/2608.07725#Sx3.E12)\)\.

### A\.6 Bretagnolle–Huber alternative

The Bretagnolle–Huber inequality states that for any eventEE,

ℙ0​\(E\)\+ℙi​\(Ec\)≥12​exp⁡\{−KL⁡\(ℙ0T∥ℙiT\)\}\.\\mathbb\{P\}\_\{0\}\(E\)\+\\mathbb\{P\}\_\{i\}\(E^\{c\}\)\\geq\\frac\{1\}\{2\}\\exp\\\{\-\\operatorname\{KL\}\(\\mathbb\{P\}\_\{0\}^\{T\}\\\|\\mathbb\{P\}\_\{i\}^\{T\}\)\\\}\.\(36\)It is not the square\-root total\-variation bound used above\. To obtain a count certificate, choose a thresholdu∈\(0,T\)u\\in\(0,T\)and setE=\{Ni​\(T\)\>u\}E=\\\{N\_\{i\}\(T\)\>u\\\}\. Markov’s inequality and \([10](https://arxiv.org/html/2608.07725#Sx3.E10)\) imply

ℙi​\(Ni​\(T\)≤u\)≥\\displaystyle\\mathbb\{P\}\_\{i\}\(N\_\{i\}\(T\)\\leq u\)\\geq\{\}12​exp⁡\{−𝔼0​\[Ni​\(T\)\]​kl⁡\(δ,δ\+ε\)\}\\displaystyle\\frac\{1\}\{2\}\\exp\\bigl\\\{\-\\mathbb\{E\}\_\{0\}\[N\_\{i\}\(T\)\]\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)\\bigr\\\}−𝔼0​\[Ni​\(T\)\]u\.\\displaystyle\-\\frac\{\\mathbb\{E\}\_\{0\}\[N\_\{i\}\(T\)\]\}\{u\}\.\(37\)Therefore

𝔼i​\[T−Ni​\(T\)\]≥\(T−u\)​ℙi​\(Ni​\(T\)≤u\)\.\\mathbb\{E\}\_\{i\}\[T\-N\_\{i\}\(T\)\]\\geq\(T\-u\)\\mathbb\{P\}\_\{i\}\(N\_\{i\}\(T\)\\leq u\)\.This last display does not by itself lower\-bound regret in the composite MDP:T−NiT\-N\_\{i\}includes good\-state and navigation time, whereas statistical regret is charged throughNx−NiN\_\{x\}\-N\_\{i\}\. A valid Bretagnolle–Huber improvement would need a joint event controlling bothNxN\_\{x\}andNiN\_\{i\}, followed by the navigation argument in \([16](https://arxiv.org/html/2608.07725#Sx3.E16)\)\. We retain \([37](https://arxiv.org/html/2608.07725#A1.E37)\) to distinguish the two testing tools, but Theorems[2](https://arxiv.org/html/2608.07725#Thmtheorem2)and[3](https://arxiv.org/html/2608.07725#Thmtheorem3)use Pinsker only\.

### A\.7 Proof of Theorem[2](https://arxiv.org/html/2608.07725#Thmtheorem2)

Fix alternativeMiM\_\{i\}\. The average\-reward performance\-difference identity gives

𝔼i​\[ℛT\]=𝔼i​\[∑t=1TΔi⋆​\(st,at\)\]\+𝔼i​\[hi⋆​\(sT\+1\)−hi⋆​\(s1\)\],\\mathbb\{E\}\_\{i\}\[\\mathcal\{R\}\_\{T\}\]=\\mathbb\{E\}\_\{i\}\\left\[\\sum\_\{t=1\}^\{T\}\\Delta\_\{i\}^\{\\star\}\(s\_\{t\},a\_\{t\}\)\\right\]\+\\mathbb\{E\}\_\{i\}\[h\_\{i\}^\{\\star\}\(s\_\{T\+1\}\)\-h\_\{i\}^\{\\star\}\(s\_\{1\}\)\],\(38\)whereΔi⋆\(s,a\)=ρ⋆\+hi⋆\(s\)−r\(s,a\)−p\(⋅∣s,a\)⊤hi⋆\\Delta\_\{i\}^\{\\star\}\(s,a\)=\\rho^\{\\star\}\+h\_\{i\}^\{\\star\}\(s\)\-r\(s,a\)\-p\(\\cdot\\mid s,a\)^\{\\top\}h\_\{i\}^\{\\star\}is the \(nonnegative\) Bellman gap\. The telescoping of𝔼i\[p\(⋅∣st,at\)⊤hi⋆\]=𝔼i\[hi⋆\(st\+1\)\]\\mathbb\{E\}\_\{i\}\[p\(\\cdot\\mid s\_\{t\},a\_\{t\}\)^\{\\top\}h\_\{i\}^\{\\star\}\]=\\mathbb\{E\}\_\{i\}\[h\_\{i\}^\{\\star\}\(s\_\{t\+1\}\)\]leaves exactly the boundary differencehi⋆​\(sT\+1\)−hi⋆​\(s1\)h\_\{i\}^\{\\star\}\(s\_\{T\+1\}\)\-h\_\{i\}^\{\\star\}\(s\_\{1\}\), which is at least−sp⁡\(hi\)≥−Bh\-\\operatorname\{sp\}\(h\_\{i\}\)\\geq\-B\_\{h\}in either direction\. Statistical actions other than coordinateiihave gapg​\(δ,ε\)g\(\\delta,\\varepsilon\), and \([16](https://arxiv.org/html/2608.07725#Sx3.E16)\) bounds the per\-trajectory navigation contribution byρi​\(Nnav​\(T\)−L\)\+\\rho\_\{i\}\(N\_\{\\rm nav\}\(T\)\-L\)\_\{\+\}\. Taking expectations, the mapz↦\(z−L\)\+z\\mapsto\(z\-L\)\_\{\+\}is convex, so Jensen’s inequality gives

𝔼i​\[\(Nnav​\(T\)−L\)\+\]≥\(𝔼i​Nnav​\(T\)−L\)\+\.\\mathbb\{E\}\_\{i\}\\bigl\[\(N\_\{\\rm nav\}\(T\)\-L\)\_\{\+\}\\bigr\]\\geq\\bigl\(\\mathbb\{E\}\_\{i\}N\_\{\\rm nav\}\(T\)\-L\\bigr\)\_\{\+\}\.\(39\)Writingqi=𝔼i​Nnav​\(T\)q\_\{i\}=\\mathbb\{E\}\_\{i\}N\_\{\\rm nav\}\(T\)and using \([14](https://arxiv.org/html/2608.07725#Sx3.E14)\) for the occupancy term and \([39](https://arxiv.org/html/2608.07725#A1.E39)\) for the navigation term,

𝔼i​\[ℛT\]≥\\displaystyle\\mathbb\{E\}\_\{i\}\[\\mathcal\{R\}\_\{T\}\]\\geq\{\}g​\[cε​\(T−qi−1δ\)−𝔼i​Ni​\(T\)\]\\displaystyle g\\left\[c\_\{\\varepsilon\}\\left\(T\-q\_\{i\}\-\\frac\{1\}\{\\delta\}\\right\)\-\\mathbb\{E\}\_\{i\}N\_\{i\}\(T\)\\right\]\+ρi​\(qi−L\)\+−Bh\.\\displaystyle\+\\rho\_\{i\}\(q\_\{i\}\-L\)\_\{\+\}\-B\_\{h\}\.Becauseg≤ρig\\leq\\rho\_\{i\}andcε≤1c\_\{\\varepsilon\}\\leq 1, minimizing the right\-hand side overqi≥0q\_\{i\}\\geq 0occurs atqi=Lq\_\{i\}=L: forqi≤Lq\_\{i\}\\leq Lthe negative term is minimized atLL, while forqi≥Lq\_\{i\}\\geq Lthe slope isρi−g​cε≥0\\rho\_\{i\}\-gc\_\{\\varepsilon\}\\geq 0\. Consequently

𝔼i​\[ℛT\]≥g​\[cε​\(T−1δ−L\)−𝔼i​Ni​\(T\)\]−Bh\.\\mathbb\{E\}\_\{i\}\[\\mathcal\{R\}\_\{T\}\]\\geq g\\left\[c\_\{\\varepsilon\}\\left\(T\-\\frac\{1\}\{\\delta\}\-L\\right\)\-\\mathbb\{E\}\_\{i\}N\_\{i\}\(T\)\\right\]\-B\_\{h\}\.Average overii, apply Lemma[1](https://arxiv.org/html/2608.07725#Thmtheorem1), and use that a maximum is at least an average\. This is \([18](https://arxiv.org/html/2608.07725#Sx3.E18)\)\.

The proof contains no assertion that each coordinate is visitedT/\(D​S​A\)T/\(DSA\)times and no separateΘ​\(ε​D\)\\Theta\(\\varepsilon D\)loss multiplier\. Both the information and regret effects follow from the kernel through \([10](https://arxiv.org/html/2608.07725#Sx3.E10)\) and \([8](https://arxiv.org/html/2608.07725#Sx3.E8)\)\.

### A\.8 Proof of Theorem[3](https://arxiv.org/html/2608.07725#Thmtheorem3)and Corollary[4](https://arxiv.org/html/2608.07725#Thmtheorem4)

Fix one regime𝒢​\(S∘,A∘,d∘,C∘\)\\mathcal\{G\}\(S\_\{\\circ\},A\_\{\\circ\},d\_\{\\circ\},C\_\{\\circ\}\)and setη=2/3\\eta=2/3,r=m/\(S​A\)=\(A−3\)/\(2​A\)r=m/\(SA\)=\(A\-3\)/\(2A\),α=\(D−L\)/D\\alpha=\(D\-L\)/D, andu=ε/δu=\\varepsilon/\\delta\. The heap tree for anyS≥S∘S\\geq S\_\{\\circ\}contains the heap tree atS∘S\_\{\\circ\}as a prefix, soL≥L∘L\\geq L\_\{\\circ\}\. The regime definition gives

r≥r∘,m≥m∘,S​A≥n∘,α≥α∘\.r\\geq r\_\{\\circ\},\\qquad m\\geq m\_\{\\circ\},\\qquad SA\\geq n\_\{\\circ\},\\qquad\\alpha\\geq\\alpha\_\{\\circ\}\.\(40\)Moreover,

u\\displaystyle u=η​\(D−L\)2​mD​T=η​α2​m​DT≤η​r2​C∘≤u∘,\\displaystyle=\\frac\{\\eta\(D\-L\)\}\{2\}\\sqrt\{\\frac\{m\}\{DT\}\}=\\frac\{\\eta\\alpha\}\{2\}\\sqrt\{\\frac\{mD\}\{T\}\}\\leq\\frac\{\\eta\\sqrt\{r\}\}\{2\\sqrt\{C\_\{\\circ\}\}\}\\leq u\_\{\\circ\},\(41\)δ\\displaystyle\\delta=2D−L≤2\(d∘−1\)​L\+d∘≤δ∘\.\\displaystyle=\\frac\{2\}\{D\-L\}\\leq\\frac\{2\}\{\(d\_\{\\circ\}\-1\)L\+d\_\{\\circ\}\}\\leq\\delta\_\{\\circ\}\.\(42\)Thusu∘≤1u\_\{\\circ\}\\leq 1makesε≤δ\\varepsilon\\leq\\delta, whileδ\+ε=δ​\(1\+u\)≤q∘<1\\delta\+\\varepsilon=\\delta\(1\+u\)\\leq q\_\{\\circ\}<1makes the finite KL upper bound applicable\. Alsocε=\(2\+u\)−1≥c∘c\_\{\\varepsilon\}=\(2\+u\)^\{\-1\}\\geq c\_\{\\circ\}\.

Normalize the square bracket in \([18](https://arxiv.org/html/2608.07725#Sx3.E18)\) byTT\. Its deterministic boundary terms satisfy

1δ​T=D−L2​T\\displaystyle\\frac\{1\}\{\\delta T\}=\\frac\{D\-L\}\{2T\}≤12​C∘​S​A≤12​C∘​n∘,\\displaystyle\\leq\\frac\{1\}\{2C\_\{\\circ\}SA\}\\leq\\frac\{1\}\{2C\_\{\\circ\}n\_\{\\circ\}\},LT\\displaystyle\\frac\{L\}\{T\}≤1C∘​d∘​S​A≤1C∘​d∘​n∘\.\\displaystyle\\leq\\frac\{1\}\{C\_\{\\circ\}d\_\{\\circ\}SA\}\\leq\\frac\{1\}\{C\_\{\\circ\}d\_\{\\circ\}n\_\{\\circ\}\}\.\(43\)Using \([34](https://arxiv.org/html/2608.07725#A1.E34)\), the testing term obeys

T2​m​kl⁡\(δ,δ\+ε\)\\displaystyle\\sqrt\{\\frac\{T\}\{2m\}\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)\}≤ε​T4​m​δ​\(1−δ−ε\)\\displaystyle\\leq\\frac\{\\varepsilon\\sqrt\{T\}\}\{\\sqrt\{4m\\delta\(1\-\\delta\-\\varepsilon\)\}\}=η4​D​δ​\(1−δ−ε\)\\displaystyle=\\frac\{\\eta\}\{\\sqrt\{4D\\delta\(1\-\\delta\-\\varepsilon\)\}\}≤η8​\(1−q∘\)=v∘,\\displaystyle\\leq\\frac\{\\eta\}\{\\sqrt\{8\(1\-q\_\{\\circ\}\)\}\}=v\_\{\\circ\},\(44\)whereD​δ=2​D/\(D−L\)≥2D\\delta=2D/\(D\-L\)\\geq 2\. Equations \([40](https://arxiv.org/html/2608.07725#A1.E40)\)–\([44](https://arxiv.org/html/2608.07725#A1.E44)\), together withw∘≥0w\_\{\\circ\}\\geq 0, give

cε​\(1−1δ​T−LT\)−1m−T2​m​kl⁡\(δ,δ\+ε\)≥β∘\.c\_\{\\varepsilon\}\\left\(1\-\\frac\{1\}\{\\delta T\}\-\\frac\{L\}\{T\}\\right\)\-\\frac\{1\}\{m\}\-\\sqrt\{\\frac\{T\}\{2m\}\\operatorname\{kl\}\(\\delta,\\delta\+\\varepsilon\)\}\\geq\\beta\_\{\\circ\}\.\(45\)
The exact regret scale is

g​TD​S​A​T=η​r​α2​\(2\+u\)≥η​r∘​α∘2​\(2\+u∘\)\.\\frac\{gT\}\{\\sqrt\{DSAT\}\}=\\frac\{\\eta\\sqrt\{r\}\\,\\alpha\}\{2\(2\+u\)\}\\geq\\frac\{\\eta\\sqrt\{r\_\{\\circ\}\}\\alpha\_\{\\circ\}\}\{2\(2\+u\_\{\\circ\}\)\}\.\(46\)Becauseβ∘≥0\\beta\_\{\\circ\}\\geq 0, the lower bounds in \([45](https://arxiv.org/html/2608.07725#A1.E45)\) and \([46](https://arxiv.org/html/2608.07725#A1.E46)\) can be multiplied\. Finally,

Bh\\displaystyle B\_\{h\}≤L\+1δ=D\+L2≤D​\(12\+12​d∘\),\\displaystyle\\leq L\+\\frac\{1\}\{\\delta\}=\\frac\{D\+L\}\{2\}\\leq D\\left\(\\frac\{1\}\{2\}\+\\frac\{1\}\{2d\_\{\\circ\}\}\\right\),BhD​S​A​T\\displaystyle\\frac\{B\_\{h\}\}\{\\sqrt\{DSAT\}\}≤12\+12​d∘C∘​S​A≤12\+12​d∘C∘​n∘\.\\displaystyle\\leq\\frac\{\\frac\{1\}\{2\}\+\\frac\{1\}\{2d\_\{\\circ\}\}\}\{\\sqrt\{C\_\{\\circ\}\}\\,SA\}\\leq\\frac\{\\frac\{1\}\{2\}\+\\frac\{1\}\{2d\_\{\\circ\}\}\}\{\\sqrt\{C\_\{\\circ\}\}\\,n\_\{\\circ\}\}\.\(47\)Substitution into Theorem[2](https://arxiv.org/html/2608.07725#Thmtheorem2)proves exactly \([24](https://arxiv.org/html/2608.07725#Sx3.E24)\)–\([25](https://arxiv.org/html/2608.07725#Sx3.E25)\)\.

For the seven rows of Table[3](https://arxiv.org/html/2608.07725#Sx3.T3), the exact heap diameters are respectivelyL∘=6,7,6,7,6,10,10L\_\{\\circ\}=6,7,6,7,6,10,10\. Direct substitution into \([22](https://arxiv.org/html/2608.07725#Sx3.E22)\)–\([24](https://arxiv.org/html/2608.07725#Sx3.E24)\) gives0\.01525763030\.0152576303,0\.01536624370\.0153662437,0\.01780885470\.0178088547,0\.02004577830\.0200457783,0\.02392516430\.0239251643,0\.02535533430\.0253553343, and0\.02912054340\.0291205434\. All four hypotheses of Theorem[3](https://arxiv.org/html/2608.07725#Thmtheorem3)hold in every row, and rounding each value downward gives the reported coefficients\. This proves Corollary[4](https://arxiv.org/html/2608.07725#Thmtheorem4)\.

For the asymptotic expression, letm→∞m\\to\\infty,u,L/D→0u,L/D\\to 0, andT/\(D​S​A\)→∞T/\(DSA\)\\to\\infty\. The coefficient at scaleη\\etabecomes

r4​η​\(12−η8\)\.\\frac\{\\sqrt\{r\}\}\{4\}\\eta\\left\(\\frac\{1\}\{2\}\-\\frac\{\\eta\}\{\\sqrt\{8\}\}\\right\)\.It is maximized atη=1/2\\eta=1/\\sqrt\{2\}\. Substitutingr=\(A−3\)/\(2​A\)r=\(A\-3\)/\(2A\)gives \([27](https://arxiv.org/html/2608.07725#Sx3.E27)\)\.

## Appendix BAppendix B: Upper\-Certificate Proofs

### B\.1 Complete candidate interface and audit ledger

At the start of episodekk, letNk​\(s,a\)N\_\{k\}\(s,a\)be the pre\-episode count and letr^k​\(s,a\)\\widehat\{r\}\_\{k\}\(s,a\),p^k\(⋅∣s,a\)\\widehat\{p\}\_\{k\}\(\\cdot\\mid s,a\), andv^kr​\(s,a\)\\widehat\{v\}^\{r\}\_\{k\}\(s,a\)be the empirical reward mean, transition distribution, and reward variance\. The reward radius is \([30](https://arxiv.org/html/2608.07725#Sx4.E30)\)\. Transition uncertainty is defined over the full simplex, including successors that have not yet been observed\. Ifℋk\\mathcal\{H\}\_\{k\}is the normalized bias region reachable by the planner, a formal directional confidence set is

𝒫k\(s,a\)=\{q∈ΔS:\\displaystyle\\mathcal\{P\}\_\{k\}\(s,a\)=\\bigl\\\{q\\in\\Delta\_\{S\}:\|\(q−p^k\)⊤​h\|\\displaystyle\\left\|\(q\-\\widehat\{p\}\_\{k\}\)^\{\\top\}h\\right\|\(48\)≤βkp\(s,a;h\),∀h∈ℋk\}\.\\displaystyle\\leq\\beta^\{p\}\_\{k\}\(s,a;h\),\\quad\\forall h\\in\\mathcal\{H\}\_\{k\}\\bigr\\\}\.A known structural support may be imposed, but empirical support alone may not: zero empirical count is not evidence of zero transition probability\. Equation \([48](https://arxiv.org/html/2608.07725#A2.E48)\) is statistically meaningful only after proving uniform coverage of the data\-dependent regionℋk\\mathcal\{H\}\_\{k\}, and it is algorithmically useful only after supplying a tractable separation or optimization procedure\.

The planning interface𝖲𝗉𝖺𝗇𝖯𝗅𝖺𝗇​\(ℳk,H¯,ϵk\)\\mathsf\{SpanPlan\}\(\\mathcal\{M\}\_\{k\},\\bar\{H\},\\epsilon\_\{k\}\)is required to:

1. 1\.return a feasible extended\-MDP policy and bias with span at mostH¯\\bar\{H\};
2. 2\.return gain at leastρ⋆−ϵk\\rho^\{\\star\}\-\\epsilon\_\{k\}whenever the true MDP lies inℳk\\mathcal\{M\}\_\{k\}andH¯≥H\\bar\{H\}\\geq H;
3. 3\.terminate in polynomial time and report its planning residual\.

Naive coordinatewise clipping of ordinary value iteration is not assumed to satisfy these conditions\. The concrete operator must preserve optimism and span feasibility while making \([48](https://arxiv.org/html/2608.07725#A2.E48)\) computationally accessible\.

Input:horizonTT, confidenceδ\\delta, and a certified span boundH¯≥H\\bar\{H\}\\geq H\.

1. 1\.InitializeN1​\(s,a\)=0N\_\{1\}\(s,a\)=0and the empirical reward and transition statistics\.
2. 2\.At episode starttkt\_\{k\}, form the full\-simplex confidence modelℳk\\mathcal\{M\}\_\{k\}using \([30](https://arxiv.org/html/2608.07725#Sx4.E30)\), \([29](https://arxiv.org/html/2608.07725#Sx4.E29)\), and \([48](https://arxiv.org/html/2608.07725#A2.E48)\)\.
3. 3\.Setϵk=1/tk∨1\\epsilon\_\{k\}=1/\\sqrt\{t\_\{k\}\\vee 1\}and compute \(ρ~k,h~k,π~k\)←𝖲𝗉𝖺𝗇𝖯𝗅𝖺𝗇​\(ℳk,H¯,ϵk\)\.\(\\widetilde\{\\rho\}\_\{k\},\\widetilde\{h\}\_\{k\},\\widetilde\{\\pi\}\_\{k\}\)\\leftarrow\\mathsf\{SpanPlan\}\(\\mathcal\{M\}\_\{k\},\\bar\{H\},\\epsilon\_\{k\}\)\.
4. 4\.Executeπ~k\\widetilde\{\\pi\}\_\{k\}until some within\-episode count reachesNk​\(s,a\)∨1N\_\{k\}\(s,a\)\\vee 1, thereby doubling that state–action count\.
5. 5\.Update all statistics and begin the next episode\.

Figure 1:Candidate span\-constrained optimistic learner\. The composition analysis is explicit, but a regret theorem additionally requires the open certificates in Table[6](https://arxiv.org/html/2608.07725#A2.T6)\.Table 6:Complete upper\-bound audit ledger\. A numerical upper coefficient is not reported while any leading entry remains open\. The compact main\-paper ledger summarizes these same obligations\.
### B\.2 Episode\-counting identities

The following deterministic inequalities expose the constants generated by count doubling\.

###### Lemma 9\(Doubling sums\)\.

Let an episode start with countnk≥1n\_\{k\}\\geq 1and end after at mostnkn\_\{k\}new observations of one state–action pair\. If the final count isNN, then

∑kvknk\\displaystyle\\sum\_\{k\}\\frac\{v\_\{k\}\}\{\\sqrt\{n\_\{k\}\}\}≤\(2\+2\)​N,\\displaystyle\\leq\(2\+\\sqrt\{2\}\)\\sqrt\{N\},\(49\)∑kvknk\\displaystyle\\sum\_\{k\}\\frac\{v\_\{k\}\}\{n\_\{k\}\}≤1\+log2⁡N,\\displaystyle\\leq 1\+\\log\_\{2\}N,\(50\)wherevkv\_\{k\}is the within\-episode count\. The initial zero\-count episode contributes at most one and is included in the displayed constants\.

###### Proof\.

At positive counts, the worst case for \([49](https://arxiv.org/html/2608.07725#A2.E49)\) is the geometric sequence1,2,4,…,2J1,2,4,\\ldots,2^\{J\}\. Its contributions are1,2,2,…,2J/21,\\sqrt\{2\},2,\\ldots,2^\{J/2\}, whose sum is at most2/\(2−1\)​N=\(2\+2\)​N\\sqrt\{2\}/\(\\sqrt\{2\}\-1\)\\sqrt\{N\}=\(2\+\\sqrt\{2\}\)\\sqrt\{N\}\. For \([50](https://arxiv.org/html/2608.07725#A2.E50)\), each completed doubling episode contributes at most one and there are at most1\+log2⁡N1\+\\log\_\{2\}Nsuch episodes\. ∎

Summing \([49](https://arxiv.org/html/2608.07725#A2.E49)\) over state–action pairs and applying Cauchy–Schwarz gives

∑s,a∑kvk​\(s,a\)Nk​\(s,a\)∨1≤\(2\+2\)​S​A​T\.\\sum\_\{s,a\}\\sum\_\{k\}\\frac\{v\_\{k\}\(s,a\)\}\{\\sqrt\{N\_\{k\}\(s,a\)\\vee 1\}\}\\leq\(2\+\\sqrt\{2\}\)\\sqrt\{SAT\}\.\(51\)This is the correct count calculation for episode\-frozen bonuses\. A proof based on per\-visit bonuses may replace2\+22\+\\sqrt\{2\}by a smaller harmonic\-sum constant, but that is a different algorithm\.

### B\.3 Proof of Lemma[5](https://arxiv.org/html/2608.07725#Thmtheorem5)

Because rewards lie in\[0,1\]\[0,1\],v^kr​\(s,a\)≤1/4\\widehat\{v\}^\{r\}\_\{k\}\(s,a\)\\leq 1/4\. Applying \([51](https://arxiv.org/html/2608.07725#A2.E51)\) to the square\-root term in \([30](https://arxiv.org/html/2608.07725#Sx4.E30)\) gives the deterministic bound

∑t=1T2​v^k​\(t\)r​\(st,at\)​LTNk​\(t\)​\(st,at\)∨1≤2\+22​S​A​T​LT\.\\sum\_\{t=1\}^\{T\}\\sqrt\{\\frac\{2\\widehat\{v\}^\{r\}\_\{k\(t\)\}\(s\_\{t\},a\_\{t\}\)L\_\{T\}\}\{N\_\{k\(t\)\}\(s\_\{t\},a\_\{t\}\)\\vee 1\}\}\\leq\\frac\{2\+\\sqrt\{2\}\}\{\\sqrt\{2\}\}\\sqrt\{SATL\_\{T\}\}\.\(52\)The linear empirical\-Bernstein term is bounded using \([50](https://arxiv.org/html/2608.07725#A2.E50)\)\. The final value ofCr′C^\{\\prime\}\_\{r\}must also include the zero\- and one\-observation conventions\. Fornk≥2n\_\{k\}\\geq 2,1/\(nk−1\)≤2/nk1/\(n\_\{k\}\-1\)\\leq 2/n\_\{k\}, so \([50](https://arxiv.org/html/2608.07725#A2.E50)\) gives

∑t:Nk​\(t\)​\(st,at\)≥27​LT3​\(Nk​\(t\)​\(st,at\)−1\)\\displaystyle\\sum\_\{t:N\_\{k\(t\)\}\(s\_\{t\},a\_\{t\}\)\\geq 2\}\\frac\{7L\_\{T\}\}\{3\(N\_\{k\(t\)\}\(s\_\{t\},a\_\{t\}\)\-1\)\}≤143​S​A​LT​\(1\+log2⁡T\)\.\\displaystyle\\hskip 51\.21495pt\\leq\\frac\{14\}\{3\}SAL\_\{T\}\(1\+\\log\_\{2\}T\)\.ForT≥2T\\geq 2,cL≥1c\_\{L\}\\geq 1, andδ≤1\\delta\\leq 1,1\+log2⁡T≤LT1\+\\log\_\{2\}T\\leq L\_\{T\}\. The first two observations of each state–action pair contribute at most2​S​A2SA, which is at most2​S​A​LT22SAL\_\{T\}^\{2\}\. Combining these terms with \([52](https://arxiv.org/html/2608.07725#A2.E52)\) proves \([31](https://arxiv.org/html/2608.07725#Sx4.E31)\) with the conservative coefficient14/3\+2=20/314/3\+2=20/3\.

### B\.4 Regret decomposition

Letk​\(t\)k\(t\)denote the episode containing timett\. On the event of Assumption[1](https://arxiv.org/html/2608.07725#Thmassumption1),

ℛT\\displaystyle\\mathcal\{R\}\_\{T\}=∑t=1T\(ρ⋆−Rt\)\\displaystyle=\\sum\_\{t=1\}^\{T\}\(\\rho^\{\\star\}\-R\_\{t\}\)≤∑t=1T\(ρ~k​\(t\)−Rt\)\+∑kϵk​ℓk,\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\(\\widetilde\{\\rho\}\_\{k\(t\)\}\-R\_\{t\}\)\+\\sum\_\{k\}\\epsilon\_\{k\}\\ell\_\{k\},\(53\)whereℓk\\ell\_\{k\}is the episode length\. Insert the extended Bellman equation returned by the planner and add and subtract the empirical reward, the true transition expectation ofh~k\\widetilde\{h\}\_\{k\}, and the realized next\-state bias\. This separates \([53](https://arxiv.org/html/2608.07725#A2.E53)\) into:

1. 1\.reward estimation, bounded by Lemma[5](https://arxiv.org/html/2608.07725#Thmtheorem5);
2. 2\.directional transition estimation, conditionally bounded by Assumption[2](https://arxiv.org/html/2608.07725#Thmassumption2);
3. 3\.the martingale∑t\[p\(⋅∣st,at\)h~k​\(t\)−h~k​\(t\)\(st\+1\)\]\\sum\_\{t\}\[p\(\\cdot\\mid s\_\{t\},a\_\{t\}\)\\widetilde\{h\}\_\{k\(t\)\}\-\\widetilde\{h\}\_\{k\(t\)\}\(s\_\{t\+1\}\)\];
4. 4\.within\-episode telescoping and episode\-boundary changes ofh~k\\widetilde\{h\}\_\{k\};
5. 5\.the planning residual∑kϵk​ℓk\\sum\_\{k\}\\epsilon\_\{k\}\\ell\_\{k\}\.

The last three contributions are conditionally bounded by Assumption[3](https://arxiv.org/html/2608.07725#Thmassumption3)\. This derivation explains why the coefficient is a sum of ledger entries rather than the product of the2\\sqrt\{2\}in a local Bernstein radius and an asserted factor two from optimism\.

### B\.5 Proof of Proposition[6](https://arxiv.org/html/2608.07725#Thmtheorem6)

Apply Lemma[5](https://arxiv.org/html/2608.07725#Thmtheorem5)and Assumptions[1](https://arxiv.org/html/2608.07725#Thmassumption1),[2](https://arxiv.org/html/2608.07725#Thmassumption2), and[3](https://arxiv.org/html/2608.07725#Thmassumption3)to \([53](https://arxiv.org/html/2608.07725#A2.E53)\)\. SinceH¯≥1\\bar\{H\}\\geq 1andS,A≥1S,A\\geq 1,

S​A​T​LT\\displaystyle\\sqrt\{SATL\_\{T\}\}≤H¯​S​A​T​LT,\\displaystyle\\leq\\sqrt\{\\bar\{H\}SATL\_\{T\}\},H¯​T​LT\\displaystyle\\sqrt\{\\bar\{H\}TL\_\{T\}\}≤H¯​S​A​T​LT\.\\displaystyle\\leq\\sqrt\{\\bar\{H\}SATL\_\{T\}\}\.Collecting the three square\-root coefficients givesCUB=Cr\+Cp\+CmC\_\{\\rm UB\}=C\_\{r\}\+C\_\{p\}\+C\_\{m\}\. Collecting the linear and polylogarithmic terms gives the statedClowC\_\{\\rm low\}andqq\. No term is discarded in the finite certificate\.

### B\.6 Why Assumption[2](https://arxiv.org/html/2608.07725#Thmassumption2)remains open

The difficult upper\-bound step is the adaptive directional\-variance budget\. A complete instantiation must prove, with numerical constants:

1. 1\.a confidence inequality uniform over every bias vector reachable by the planning operator;
2. 2\.a comparison between empirical and true conditional variance;
3. 3\.a trajectory\-level variance recursion that yields square\-root dependence onH¯\\bar\{H\}, rather than the crude range boundH¯​S​A​T\\bar\{H\}\\sqrt\{SAT\};
4. 4\.control of changes in the optimistic bias across episodes;
5. 5\.preservation of optimism and span feasibility by the selected planning operator\.

These are precisely the steps for which earlier span\-constrained and mitigated planning analyses are needed\(Fruitet al\.[2018](https://arxiv.org/html/2608.07725#bib.bib4); Boone and Zhang[2024](https://arxiv.org/html/2608.07725#bib.bib49)\)\. Until their numerical constants populate Table[4](https://arxiv.org/html/2608.07725#Sx4.T4), the manuscript reports an audit template rather than the unsupported value2​22\\sqrt\{2\}\.

## Appendix CAppendix C: Preliminary Pilot Results

This appendix preserves the original experimental observations while separating them from the confirmatory tests in Appendix D\. They motivated the revised protocol but are not used to validate the explicit theorem constants\.

### C\.1 Bonus\-shape pilot

Under the preliminary span\-truncated implementation, Bernstein had mean regret7599\.87599\.8and Hoeffding had mean regret8370\.48370\.4after aggregation across two families, three diameters, and several horizons\. The family\-specific means were11051\.611051\.6versus12212\.612212\.6on the cycle and4148\.04148\.0versus4528\.24528\.2on the funnel\. Under a simplified implementation without the same span and support treatment, the ordering reversed:3196\.33196\.3for Bernstein and3034\.63034\.6for Hoeffding\. Because these aggregates used only six runs, lacked paired confidence intervals, and did not match the pilot and full horizons, they are descriptive\.

Table 7:Preserved preliminary bonus results\. Confirmatory results belong in Table[12](https://arxiv.org/html/2608.07725#A4.T12)\.The original cycle horizon points were\(25,000,2510\.9\)\(25\{,\}000,2510\.9\),\(100,000,11923\.2\)\(100\{,\}000,11923\.2\), and\(200,000,18720\.7\)\(200\{,\}000,18720\.7\)for Bernstein, and\(25,000,2620\.8\)\(25\{,\}000,2620\.8\),\(100,000,12708\.1\)\(100\{,\}000,12708\.1\), and\(200,000,21308\.9\)\(200\{,\}000,21308\.9\)for Hoeffding\. Over the eightfold increase in horizon, regret increased by factors7\.467\.46and8\.138\.13, respectively, whereas a visible square\-root regime would increase by8≈2\.83\\sqrt\{8\}\\approx 2\.83\. The revised experiment therefore includes longer horizons and estimates the local log–log slope instead of describing this pilot as rate confirmation\.

### C\.2 Zero\-span diameter pilot

For diameters6\.256\.25,12\.512\.5, and25\.025\.0, the reported normalized ratiosℛT/D​S​A​T\\mathcal\{R\}\_\{T\}/\\sqrt\{DSAT\}were2\.4582\.458,2\.1732\.173, and1\.7331\.733for the span\-truncated learner and2\.3052\.305,1\.5641\.564, and1\.2211\.221for the simplified learner\. The corresponding coefficients of variation were0\.14060\.1406and0\.26680\.2668\. A decreasing normalized ratio is compatible with diameter\-independent regret and should not be called flattening\. Moreover, multiplying the ratios byD\\sqrt\{D\}shows that the implied regret scale did not remain constant for the span\-truncated pilot\. Table[9](https://arxiv.org/html/2608.07725#A4.T9)therefore tests raw regret against diameter directly\.

On the deep\-funnel family, the normalized\-ratio coefficients of variation were0\.24170\.2417and0\.23810\.2381\. The earlier text described this as a null despitesp⁡\(h⋆\)/D≈0\.04\\operatorname\{sp\}\(h^\{\\star\}\)/D\\approx 0\.04\. Because this ratio is within the regime where a width effect was expected, the null is evidence against a broad mechanism claim and motivates the larger positive\-span sweep\.

### C\.3 Fixed\-diameter span pilot

The cleanest preliminary result held the measured diameter at27\.327\.3while varying the bias span\. Over2424seeds atT=40,000T=40\{,\}000, the regret ratio between the diameter\-width and span\-width learners generally increased withD/sp⁡\(h⋆\)D/\\operatorname\{sp\}\(h^\{\\star\}\)\.

Table 8:Preserved fixed\-diameter pilot, reported as mean±\\pmstandard error\. The confirmatory study adds all eight points, simultaneous uncertainty, and model comparisons againstD/H\\sqrt\{D/H\}andD/HD/H\.The earlier proxyℛT/sp⁡\(h⋆\)​S​A​T\\mathcal\{R\}\_\{T\}/\\sqrt\{\\operatorname\{sp\}\(h^\{\\star\}\)SAT\}was between0\.730\.73and1\.481\.48\. It is not compared directly with an upper\-bound coefficient because the theorem also contains a logarithmic factor and lower\-order terms\.

### C\.4 Function\-approximation negative

A neural differential\-valueQQ\-learning pilot compared the two bonus shapes over eight seeds and40,00040\{,\}000steps\. Neither method reliably solved the procedural funnel against a persistent\-right reference rate of0\.990\.99\. Bernstein attained mean reward near2×10−42\\times 10^\{\-4\}; the Hoeffding mean of0\.0750\.075was driven by one seed at0\.5960\.596, with the other seven near10−410^\{\-4\}\. The paired difference was not significant \(t=−1\.0t=\-1\.0\)\. This negative result establishes no ordering between the tabular bonuses and is retained only as a boundary on the scope of the current study\.

## Appendix DAppendix D: Confirmatory Experimental Details

The experiments test mechanisms implied by the corrected analysis; they do not estimate a theorem constant by dropping its logarithmic or lower\-order terms\. All random\-seed comparisons are paired, all main tables report confidence intervals, and all algorithmic comparisons use identical horizons and stopping rules\. Code records the supplied span bound, planning residual, confidence\-set failures in simulation, and every constant used by the implementation\.

### Experimental protocol

RQ1 used 12 seeds, RQ2 used at least 8 seeds per cell, and RQ3 used 24 paired seeds atT=40,000T=40\{,\}000\. RQ4 used 8 seeds for each algorithmic alternative, and the deep neural pilot used 8 seeds\. NumPy experiments useddefault\_rngwith matched seeds for paired comparisons\. Transition and trajectory outputs were recorded using SHA\-1 digests, and the GPU experiments additionally fixed the corresponding PyTorch random seeds\. The complete experimental matrix is reported in Table[16](https://arxiv.org/html/2608.07725#A4.T16)\.

### Environments and baselines

We use*five*distinct controlled tabular families across the experiments, and we enumerate them separately because different research questions use different ones\.*\(F1\) Exact composite family𝔐\\mathfrak\{M\}*from the main paper’s finite lower\-certificate section: the proved lower\-bound construction \(binary\-tree navigation plus statistical actions\), used only in RQ4\.*\(F2\) Zero\-span hard\-chain family*: the hard\-cycle topology with a constant optimal bias, used as the diameter\-flatness testbed in RQ1\.*\(F3\) Zero\-span hub family*: a genuinely distinct hub/star topology, also with a constant optimal biash⋆h^\{\\star\}verified by relative value iteration \(sp⁡\(h⋆\)=0\\operatorname\{sp\}\(h^\{\\star\}\)=0to machine precision and a constant Bellman residual,verify\_rq2\_clean\.py\), introduced in RQ2 to replace an earlier zero\-span builder that aliased F2; it is*not*𝔐\\mathfrak\{M\}\.*\(F4\) Positive\-span deep funnel*\.*\(F5\) Fixed\-diameter corridor*in which rewards vary while transitions remain fixed, allowingD/HD/Hto change without changing the diameter\. F2 and F3 both havesp⁡\(h⋆\)=0\\operatorname\{sp\}\(h^\{\\star\}\)=0but distinct transition tensors \(distinct integrity\-gate hashes, Table[11](https://arxiv.org/html/2608.07725#A4.T11)\)\. Each family is evaluated over sweeps inSS,AA,TT, and eitherDDorHH\.

All experimental learners share the same codebase and episodic planning routine; the controlled configurations vary the bonus type \(empirical\-Bernstein or Hoeffding\), the supplied bias\-clip width \(span or diameter\), and the confidence specification exactly as stated in each table, and the same implementation is used across allmmalternatives in RQ4\. The planning routine is a*heuristic*span\-clipped extended value iteration: it truncates the optimistic bias to the supplied widthH⋆H^\{\\star\}under known structural support with the zero\-initialization / first\-visit rule ofverify\_spantrunc\.py\. We do*not*claim it is a certified span\-constrained operator—as the main paper’s upper\-certificate section notes, naïve clipping is not known to preserve optimism or convergence, and a sound treatment needs a ScOpt/PMEVI\-style projected operator\(Fruitet al\.[2018](https://arxiv.org/html/2608.07725#bib.bib4); Boone and Zhang[2024](https://arxiv.org/html/2608.07725#bib.bib49)\)—so RQ1–RQ3 are reported as*mechanism diagnostics*of this heuristic routine, not as evaluations of a theoretically sound algorithm\. Because the published baselines \(SCAL, empirical\-Bernstein UCRL, and PMEVI\-DT\) are likewise not re\-implemented faithfully, RQ1’s comparison columns are this same heuristic learner run under different clip widths and confidence radii rather than independent ports; we label them*mitigated span\-width variant*and*UCRL2\-style*rather than by the published algorithm names, and cite\(Jakschet al\.[2010](https://arxiv.org/html/2608.07725#bib.bib1); Fruitet al\.[2018](https://arxiv.org/html/2608.07725#bib.bib4),[2020](https://arxiv.org/html/2608.07725#bib.bib5); Bourelet al\.[2020](https://arxiv.org/html/2608.07725#bib.bib9); Boone and Zhang[2024](https://arxiv.org/html/2608.07725#bib.bib49)\)for conceptual comparison only\. When a configuration requires side information, the supplied information is stated in the table rather than hidden in the implementation\.

### RQ1: Does regret become diameter\-independent on a zero\-span family?

BecauseH=1H=1on this family, a genuinely span\-dependent leading term should not grow withDD\. Proposition[6](https://arxiv.org/html/2608.07725#Thmtheorem6)does not prove that claim for the candidate learner; it only shows how such a claim would enter a completed ledger\. The experiment therefore tests the mechanism directly\. The primary response is regret itself as a function ofDD, withSS,AA, andTTfixed\. A coefficient of variation ofℛT/D​S​A​T\\mathcal\{R\}\_\{T\}/\\sqrt\{DSAT\}is not used: under diameter\-independent regret, that normalized quantity should decay approximately as1/D1/\\sqrt\{D\}\.

Table 9:Mean regret and95%95\\%confidence intervals on the zero\-span hard\-chain family \(F2\) at a matched horizon \(S=6S=6,A=3A=3,T=20,000T=20\{,\}000,1212seeds\)\. All four columns are the*same*span\-constrained optimistic learner run under different bias\-clip widths—the span widthmax⁡\(sp⁡\(h⋆\),1\)\\max\(\\operatorname\{sp\}\(h^\{\\star\}\),1\), the diameter width, the “mitigated” span\-width variant \(identical to the span column on this zero\-span family, see text\), and a UCRL2\-style diameter\-driven confidence radius—not independent ports of the published algorithms, whose names we therefore do not use as column labels\. The main test is the slope of regret against measured diameter\.Pointwise confidence intervals do not determine whether the fitted slope is significantly positive\. The paired seed\-level regression in Table[10](https://arxiv.org/html/2608.07725#A4.T10)is therefore the inferential result\. The paper will use “fail to detect positive diameter dependence” only when the corresponding upper confidence limit includes zero; it will not interpret a nonsignificant slope as proof that the true slope is zero\.

Table 10:Required paired slope analysis for RQ1\. Confidence intervals and one\-sided tests must be computed from seed\-level regressions; they cannot be inferred from the pointwise intervals in Table[9](https://arxiv.org/html/2608.07725#A4.T9)\.The span\-constrained learner and the mitigated span\-width variant return*bit\-for\-bit identical*means and slopes \(2003/2514/2088/20882003/2514/2088/2088; slope−5\.9\-5\.9\) on this family for a deductive reason, not an implementation coincidence: whensp⁡\(h⋆\)=0\\operatorname\{sp\}\(h^\{\\star\}\)=0both clip the optimistic bias to the same widthmax⁡\(sp⁡\(h⋆\),1\)=1\\max\(\\operatorname\{sp\}\(h^\{\\star\}\),1\)=1and run the identical Bernstein, support\-restricted recipe \(see the shared call signature inverify\_rq12\.py\), so they are literally the*same*learner here\. The diameter\-width learner differs only in supplying the wider clipDD; atD=6\.25D=6\.25its regret coincides exactly \(20032003\) with the span learner’s, whereas byD≥10D\\geq 10its outputs cease to be bit\-for\-bit identical\. We are careful not to overread this: identical outputs atD=6\.25D=6\.25show the two configurations produced the same numerical trajectory there, and non\-identical outputs atD≥10D\\geq 10show only that the different supplied width*changes the numerical trajectory*—atD=10D=10the two means \(25142514vs\.25182518\) differ by only44regret units against a±240\\pm 240seed uncertainty\. We do*not*claim this establishes that the diameter clip has “begun to bind” or has any regret consequence; the slope test \(Table[10](https://arxiv.org/html/2608.07725#A4.T10)\) remains non\-significant for both widths\. Attributing the divergence to clip activation would require the diagnostics we do not yet log—the fraction of planning calls where clipping changes the bias, the action\-disagreement rate, and the maximum preclip span—which we flag as the correct follow\-up\. RQ3 isolates the width intervention on a corridor where the clipping constraint is active by construction, so the two widths cannot alias\.

### RQ2: Which ingredient produces the improvement?

We use a2×22\\times 2design crossing Bernstein versus Hoeffding confidence with span\-constrained versus diameter\-constrained planning\. All cells in this design use*known structural support*: the reachable successor set of each\(s,a\)\(s,a\)is supplied, matching the support\-restricted recipe used throughout the experiments and avoiding the exact\-soundness pitfall of empirical\-support estimation that the main paper’s upper\-certificate section warns about\. We therefore do*not*report a separate unknown\-support\-safe panel here; an empirical\-support\-only variant is not a theoretically valid baseline and is not run\.

A previous RQ2 export gave bit\-for\-bit identical regret values for the hard and zero\-span families at every cell, because the zero\-span builder aliased the hard cycle—reusing a reward\-per\-action builder cannot imply identical regret under distinct transition kernels, so those numbers were not interpretable as an algorithmic result\. We therefore replaced the zero\-span family with a genuinely distinct*hub*topology \(stillsp⁡\(h⋆\)=0\\operatorname\{sp\}\(h^\{\\star\}\)=0\) and gated the rerun on the environment audit in Table[11](https://arxiv.org/html/2608.07725#A4.T11), which now verifies distinct transition tensors and seed\-matched trajectory digests\. The gate passes, and Table[12](https://arxiv.org/html/2608.07725#A4.T12)reports the factorial from that clean run\.

Table 11:Environment\-integrity gate for RQ2 \(verify\_rq2\_clean\.py\), reported at*both*factorial configurations\(S,A\)∈\{\(10,5\),\(20,8\)\}\(S,A\)\\in\\\{\(10,5\),\(20,8\)\\\}\(each hash/diameter/digest is one specific MDP, not an aggregate\)\. The column is the raw bias spansp⁡\(h⋆\)\\operatorname\{sp\}\(h^\{\\star\}\),*not*the complexityH=1∨sp⁡\(h⋆\)H=1\\vee\\operatorname\{sp\}\(h^\{\\star\}\)\(which is by definition at least11\); the first two families genuinely havesp⁡\(h⋆\)=0\\operatorname\{sp\}\(h^\{\\star\}\)=0henceH=1H=1\. Hashes are SHA1 of the canonical transition tensorPP; trajectory digests use a fixed action sequence and random stream \(and so also reflect the reward\)\. The gate*passes at both configurations*: at each, the baseline and zero\-span rows have distinct transition hashes \(70019407vs\.5c2aa508at\(10,5\)\(10,5\);4fb01eb1vs\.142f856fat\(20,8\)\(20,8\)\) and distinct digests, fixing the earlier defect where the zero\-span builder aliased the baseline cycle\. This “baseline composite topology” is the diameter\-flatness test bed used in RQ1 below; it is*not*the exact lower\-bound family𝔐\\mathfrak\{M\}in the main paper \(which hassp⁡\(hi\)=ρi​L\+\(1−ρi\)/δ\>0\\operatorname\{sp\}\(h\_\{i\}\)=\\rho\_\{i\}L\+\(1\-\\rho\_\{i\}\)/\\delta\>0\), and we do not claim it is\. The zero\-span hub is a genuinely different*hub*topology withsp⁡\(h⋆\)=0\\operatorname\{sp\}\(h^\{\\star\}\)=0; its larger measured diameter reflects the harder\-to\-reach spokes\.†The deep funnel shares the baseline cycle’s transition tensor by construction \(it changes only the reward to concentrate value in a core\), so it has the samePP\-hash but a distinct trajectory digest and a nonzero bias span\.Table 12:Clean matched\-horizon factorial \(configs\(S,A\)∈\{\(10,5\),\(20,8\)\}\(S,A\)\\in\\\{\(10,5\),\(20,8\)\\\},T∈\{25,000,100,000,200,000\}T\\in\\\{25\{,\}000,100\{,\}000,200\{,\}000\\\},88seeds;verify\_rq2\_clean\.py, run after the integrity gate of Table[11](https://arxiv.org/html/2608.07725#A4.T11)passes\)\. Per\-family cells are mean regret over \(config, horizon, seed\); the final column is the paired Bernstein−\-Hoeffding contrast \(fixed as the primary contrast before the clean rerun\) at matched width over192192samples \(95%95\\%CI\)\. With the distinct hub zero\-span family the hard and zero\-span cells now*differ*\(e\.g\.1648416484vs\.1700717007at Bernstein/span\), unlike the earlier aliased export\. The contrast is not significant at either width \(−520±523\-520\\pm 523span,\+286±431\+286\\pm 431diameter\); Bernstein has lower regret on33of44families at the span width and22of44at the diameter width\. This is a genuinely mixed, width\-dependent result and we do not claim a bonus\-shape improvement\.This contrast—the paired Bernstein−\-Hoeffding difference at a fixed width, fixed before the clean rerun—is reported per width without pooling\. At both widths the contrast’s95%95\\%CI includes zero \(−520±523\-520\\pm 523at the span width,\+286±431\+286\\pm 431at the diameter width\), and the per\-family direction is mixed \(Bernstein lower on3/43/4families at span width,2/42/4at diameter width\)\. RQ2 therefore supports*no*claim of a bonus\-shape improvement; we report the null straight\. The earlier six\-run mixed result remains in Supplementary Appendix C as a pilot and is not pooled with this confirmatory table\.

### RQ3: How does an over\-wide span constraint affect regret?

The fixed\-diameter corridor holdsDDconstant and variesHH\. Two learners differ only in the width supplied to the heuristic span\-clipped planning routine described at the start of Appendix D; this is a mechanism diagnostic, not a claim about a certified operator\. We compare the observed penalty with bothD/H\\sqrt\{D/H\}, the prediction for a leading square\-root term, andD/HD/H, the possible prediction for a width\-linear lower\-order term\.

The preliminary sweep usedD=27\.3D=27\.3,T=40,000T=40\{,\}000, and2424seeds over four width ratios\. The penalty increased monotonically from1\.77×1\.77\\timesatD/sp⁡\(h⋆\)=2\.5D/\\operatorname\{sp\}\(h^\{\\star\}\)=2\.5to2\.62×2\.62\\timesat a ratio of13\.413\.4\(Table[13](https://arxiv.org/html/2608.07725#A4.T13)\)\. We retain it as a four\-point pilot establishing direction and rough magnitude\. The eight\-point sweep of Table[14](https://arxiv.org/html/2608.07725#A4.T14)then adds four intermediate ratios; the model form \(square\-root vs\. linear\) and analysis were*fixed before this rerun*, but we note that the four pilot ratios \(2\.5,5\.0,9\.1,13\.42\.5,5\.0,9\.1,13\.4\) are reused among the eight, so this is not a fully independent confirmatory experiment and we describe it as an extended sweep rather than a preregistered replication\. On this grid the square\-root specificationa\+b​xa\+b\\sqrt\{x\}is*preferred to*the linear specificationa\+b​xa\+bx: the bootstrap interval for the difference in fit error is0\.0260\.026\[0\.025,0\.027\]\[0\.025,0\.027\]\. Each bootstrap replicate \(i\) resamples paired seeds within each width ratio, \(ii\) recomputes the regret ratios, \(iii\) refits both models, and \(iv\) recomputes the RMSE difference\. The reproducible analysis is recorded inspan\_confirm\_modelselect\.py\. Leave\-one\-ratio\-out prediction error likewise favors the square\-root model \(0\.0980\.098vs\.0\.1300\.130mean held\-out absolute error\)\. We are careful about what this establishes: it shows the square\-root form fits these eight design points better than a linear form,*not*that the theoretical scaling law is square\-root rather than logarithmic, saturating, or another sublinear form—distinguishing those would require a wider ratio range and a model\-selection argument we do not claim\.

Table 13:Four\-point fixed\-diameter span\-width pilot \(2424seeds\)\. The two learners share the same bonus, confidence set, planner, seeds, and horizon; the penalty grows monotonically with the width ratio but the four points do not discriminate a square\-root from a linear\-width shape\.Table 14:Extended span\-width sweep \(D=27\.3D=27\.3fixed,T=40,000T=40\{,\}000,2424seeds;span\_scaling\_gpu\.py\); model form and analysis fixed before this rerun, but four of the eight ratios are reused from the pilot \(see text\), so this is an extended sweep, not a fully independent confirmatory replication\. Columns are span\-width and diameter\-width mean regret, their paired penalty \(ratio\), the simultaneous95%95\\%CI \(Bonferroni across the eight rows,z=2\.73z=2\.73\), and the residuals of aa\+b​D/Ha\+b\\sqrt\{D/H\}versusa\+b​\(D/H\)a\+b\(D/H\)fit\. The penalty grows monotonically and*sublinearly*from1\.77×1\.77\\timesto2\.62×2\.62\\times; the square\-root fit has the smaller RMS residual \(0\.0830\.083vs\.0\.1080\.108\)\. The paired\-seed bootstrap interval for the RMS difference,0\.0260\.026\[0\.025,0\.027\]\[0\.025,0\.027\],*excludes zero*, so the square\-root shape is preferred over the linear one at this scale; leave\-one\-ratio\-out mean absolute error is0\.0980\.098versus0\.1300\.130\.
### RQ4: Does observed regret respect the finite lower certificate?

We run the exact composite family𝔐\\mathfrak\{M\}and place observed regret against the finite lower certificate of \([18](https://arxiv.org/html/2608.07725#Sx3.E18)\)\. The proof first lower\-bounds the uniform average over allmmalternatives and only then uses that a maximum is at least an average\. Consequently, a run on one unspecified alternative is not a test of the certificate\. For each feasible configuration we therefore run every alternative with the same seed set and report both the alternative\-average regret and the largest alternative\-specific mean\. No upper column is reported:CpC\_\{p\}andCmC\_\{m\}remain open in the main paper’s upper\-certificate ledger, so a sum of selected completed terms is not an upper certificate\.

Table 15:Lower\-certificate evaluation on the*exact*proved family𝔐\\mathfrak\{M\}of the main paper’s exact lower\-bound family \(verify\_rq4\_exact\.py; allmmalternatives,88paired seeds each\)\. The generator implements the construction faithfully:A0=A−3A\_\{0\}=A\-3statistical actions plus three navigation actions \(parent/left/right, self\-loop if absent\) on the complete binary tree,LLthe*exact*tree diameter \(all\-pairs shortest path\),δ=2/\(D−L\)\\delta=2/\(D\-L\), andm=K​\(A−3\)=S​\(A−3\)/2m=K\(A\-3\)=S\(A\-3\)/2; the resulting\(L,m\)\(L,m\)are\(3,10\),\(5,16\),\(5,40\)\(3,10\),\(5,16\),\(5,40\), matching the construction, and the certificates102\.1102\.1,276\.4276\.4,883\.8883\.8are the*best grid\-evaluated*finite certificate—the maximum of the right\-hand side of \([18](https://arxiv.org/html/2608.07725#Sx3.E18)\) over a log\-spacedε\\varepsilongrid \(range\[δ⋅10−4,δ\]\[\\delta\\\!\\cdot\\\!10^\{\-4\},\\delta\],30003000points, exact KL\); every grid value is itself a valid certificate, so the reported entry is a valid lower bound but not certified to be the exact maximum\. These are not rounded frontier coefficients\. \(An earlier draft used a generator withA0=\(A−1\)/2A\_\{0\}=\(A\-1\)/2statistical actions,L=2​⌈log2⁡K⌉L=2\\lceil\\log\_\{2\}K\\rceil, and no navigation actions—i\.e\. not the proved family—which we have replaced\.\) Because themmalternatives are the*complete fixed population*of testing coordinates rather than a random sample, alternative\-average regret is the mean over allmmof them and its95%95\\%CI comes from a seed\-only bootstrap that holds the alternative population fixed \(resampling seeds within each fixed alternative\); the empirical maximum uses a Bonferroni\-simultaneous alternative\-wise bound\. In every configuration the certificate lies below the alternative average—the expected floor direction—but at only0\.32%0\.32\\%,0\.34%0\.34\\%, and2\.2%2\.2\\%of it \(102\.1/31882102\.1/31882,276\.4/81157276\.4/81157,883\.8/39551883\.8/39551\), so RQ4 is an*implementation\-consistency and reproducibility check*, not evidence of practical tightness or nonvacuity\.Observed alternative\-average regret above the finite certificate is the expected direction—the lower bound is a floor—so RQ4 is only an implementation\-consistency and reproducibility check, not a proof of tightness or of practical nonvacuity \(the certificate is0\.30\.3–2\.2%2\.2\\%of the observed regret\)\. A failed inequality after accounting for Monte Carlo uncertainty would indicate an implementation or certificate\-evaluation error\. A genuine lower–upper sandwich awaits a concrete upper algorithm that certifies every open entry of Table[4](https://arxiv.org/html/2608.07725#Sx4.T4), in particular the directional\-variance and planning constants\.

### Scaling, uncertainty, and span misspecification

The horizon sweep includes enough points to estimate the local log–log slope of regret againstTT\. The state and action sweeps check the claimedS​A\\sqrt\{SA\}dependence\. We additionally supplyH¯/H∈\{1,1\.25,1\.5,2,4,D/H\}\\bar\{H\}/H\\in\\\{1,1\.25,1\.5,2,4,D/H\\\}to measure the cost of conservative span knowledge\. Every family uses at least the number of seeds in Table[16](https://arxiv.org/html/2608.07725#A4.T16); these counts were fixed before inspecting the final comparisons \(we do not report a formal power calculation and do not claim one\)\. Multiplicity is corrected*within*each analysis where several statistics are read together, not by a single family across all research questions: RQ3’s simultaneous CIs use a Bonferroni factor across its eight width ratios \(z=2\.73z=2\.73\), and RQ4’s empirical\-maximum bound is Bonferroni\-simultaneous across itsmmalternatives; RQ1 and RQ2 each report a single primary paired contrast, so no correction applies there\.

Table 16:Experimental matrix and protocol, fixed before the final comparisons \(not timestamped or preregistered\)\.The earlier neural function\-approximation probe is retained as a negative pilot in Supplementary Appendix C\. It is not used to support the tabular theorem because neither bonus solved the deep exploration problem reliably\.

## Appendix EAppendix E: Reproducibility Details

#### Compute environment\.

The principal theoretical and numerical verification experiments \(RQ1, RQ2, and RQ4\) were conducted on CPU using NumPy\-based implementations\. GPU computation was used only for the RQ3 span\-scaling experiment and the deep neural function\-approximation diagnostic\. These GPU experiments were executed on AWS SageMakerml\.g5\.2xlargeinstances equipped with one NVIDIA A10G GPU with 24 GB of GPU memory and a 60 GB attached storage volume\. The corresponding GPU workflows arespan\_scaling\_gpu\.pyand the deep neural function\-approximation rerun\.

The final artifact reports the following items alongside code and raw data:

1. 1\.the exact transition and reward kernels for every environment;
2. 2\.independently computed diameter, gain, bias, and bias span;
3. 3\.every numerical confidence and planning constant;
4. 4\.the full construction and upper\-bound ledgers;
5. 5\.all seeds and per\-seed trajectories;
6. 6\.paired confidence intervals and the analysis script fixed before the final comparisons;
7. 7\.planning residuals and the supplied value ofH¯\\bar\{H\};
8. 8\.all points in every sweep, including null and negative results\.

## Appendix FAppendix F: Restored Broader Context and Constant\-Ledger Interpretation

### F\.1 Broader average\-reward and reinforcement\-learning context

The undiscounted formulation traces to dynamic programming\(Bellman[1957](https://arxiv.org/html/2608.07725#bib.bib44); Howard[1960](https://arxiv.org/html/2608.07725#bib.bib17); Schweitzer[1979](https://arxiv.org/html/2608.07725#bib.bib18); Bertsekas[2012](https://arxiv.org/html/2608.07725#bib.bib16)\)and optimal adaptive control\(Burnetas and Katehakis[1997](https://arxiv.org/html/2608.07725#bib.bib19); Tewari and Bartlett[2008](https://arxiv.org/html/2608.07725#bib.bib20)\)\. Beyond model\-based optimism, average\-reward regret has been studied through posterior sampling\(Osband and Van Roy[2017](https://arxiv.org/html/2608.07725#bib.bib23); Agrawal and Jia[2017](https://arxiv.org/html/2608.07725#bib.bib24); Ouyanget al\.[2017](https://arxiv.org/html/2608.07725#bib.bib25)\), model\-free methods\(Weiet al\.[2020](https://arxiv.org/html/2608.07725#bib.bib7); Zhang and Xie[2023](https://arxiv.org/html/2608.07725#bib.bib37)\), policy optimization\(Abbasi\-Yadkoriet al\.[2019](https://arxiv.org/html/2608.07725#bib.bib46); Lazicet al\.[2021](https://arxiv.org/html/2608.07725#bib.bib47)\), Markov\-chain concentration\(Ortner[2020](https://arxiv.org/html/2608.07725#bib.bib21)\), and function approximation\(Weiet al\.[2021](https://arxiv.org/html/2608.07725#bib.bib8); Chenet al\.[2022](https://arxiv.org/html/2608.07725#bib.bib35)\)\. The distribution\-norm view of instance hardness\(Maillardet al\.[2014](https://arxiv.org/html/2608.07725#bib.bib39)\)is complementary to our separation of statistical and geometric constants\.

The episodic and discounted settings provide related tools, including minimax sample\-complexity and regret analyses\(Azaret al\.[2013](https://arxiv.org/html/2608.07725#bib.bib27),[2017](https://arxiv.org/html/2608.07725#bib.bib3)\), PAC and gap\-dependent refinements\(Dann and Brunskill[2015](https://arxiv.org/html/2608.07725#bib.bib28); Dannet al\.[2017](https://arxiv.org/html/2608.07725#bib.bib29); Simchowitz and Jamieson[2019](https://arxiv.org/html/2608.07725#bib.bib32); Zanette and Brunskill[2019](https://arxiv.org/html/2608.07725#bib.bib31)\), efficient Q\-learning\(Jinet al\.[2018](https://arxiv.org/html/2608.07725#bib.bib30)\), reference\-advantage decompositions\(Zhanget al\.[2020](https://arxiv.org/html/2608.07725#bib.bib33); Zhang and Ji[2021](https://arxiv.org/html/2608.07725#bib.bib34)\), feature\-based discounted bounds\(Zhouet al\.[2021](https://arxiv.org/html/2608.07725#bib.bib36)\), discounted PAC guarantees\(Lattimore and Hutter[2012](https://arxiv.org/html/2608.07725#bib.bib22)\), constrained exploration\(Efroniet al\.[2020](https://arxiv.org/html/2608.07725#bib.bib26)\), and general model\-based complexity measures\(Osband and Van Roy[2014](https://arxiv.org/html/2608.07725#bib.bib48)\)\. The lower proof also draws on exact testing tools associated with Assouad and Bretagnolle–Huber\(Assouad[1983](https://arxiv.org/html/2608.07725#bib.bib43); Bretagnolle and Huber[1979](https://arxiv.org/html/2608.07725#bib.bib42)\)\.

### F\.2 Where the slack lives

The revised analysis separates two questions that were previously conflated: slack inside an upper bound and the gap between an upper and a lower certificate\.

#### Bonus shape\.

A Bernstein radius replaces a worst\-case range contribution by an empirical directional variance\. Its potential benefit is quantified by the difference betweenCpC\_\{p\}in Assumption[2](https://arxiv.org/html/2608.07725#Thmassumption2)and the corresponding Hoeffding ledger\. The square root in one local radius is not itself the final regret coefficient\(Maurer and Pontil[2009](https://arxiv.org/html/2608.07725#bib.bib11); Audibertet al\.[2009](https://arxiv.org/html/2608.07725#bib.bib12)\)\.

#### Confidence geometry\.

Fullℓ1\\ell\_\{1\}transition sets may pay for directions irrelevant to the selected bias\. A directional or structured\-support set can reduce this cost, but support information must be known or statistically certified\. Restricting the model to successors observed so far can remove the true MDP and destroy optimism\. The relevant contribution is therefore the difference between two valid confidence ledgers, not the number of currently observed successors\.

#### Span width\.

If the upper square\-root term scales asH¯​S​A​T\\sqrt\{\\bar\{H\}SAT\}, replacing a certified widthH¯\\bar\{H\}by the diameter changes that term byD/H¯\\sqrt\{D/\\bar\{H\}\}, notD/H¯D/\\bar\{H\}\. Lower\-order terms linear in the width can incur the larger ratioD/H¯D/\\bar\{H\}\. Experiments must distinguish these two regimes\.

#### Lower\-bound balance\.

The testing and perturbation balance determinescLBc\_\{\\rm LB\}\. This is not a span\-truncation factor and should not be included under that name\. If the reciprocal lower coefficient dominates the eventual upper\-to\-lower ratio, it is the dominant sandwich slack even when span width is the dominant source of looseness within a diameter\-based upper bound\.

This taxonomy yields four separately reportable quantities: the Bernstein\-versus\-Hoeffding ledger ratio, the valid\-confidence\-geometry ratio, the width penalty, and the reciprocal lower certificate\. Their product is not called an exact decomposition unless the proof shows that the factors multiply under one common normalization\.

### F\.3 Restored interpretation, limitations, and next steps

#### What is certified\.

The lower result is a finite testing certificate tied to an explicit kernel\. It includes the exact action budget, diameter upper bound, flow identity, navigation cost, bias span, and path divergence\. On the regimes in Table[3](https://arxiv.org/html/2608.07725#Sx3.T3), its certified coefficient ranges from0\.01520\.0152to0\.02910\.0291; the same analytic envelope proves every row\. The upper contribution is an audit template, not a new regret theorem\. Its ledger makes an incorrect small coefficient difficult to report because every omitted factor remains visibly open\.

#### What is not claimed\.

We do not call the result constant\-sharp while a nonconstant logarithmic mismatch remains\. We also do not claim that a zero\-span MDP is cost\-free, that empirical support is the true support, or that a coordinatewise clip is a sound replacement for a span\-constrained planning operator\. The supplied span bound is side information; replacing it by an estimator is a separate contribution whose error and constant must appear in the theorem\.

#### Interpreting span truncation\.

Span width can be the dominant source of looseness within an upper\-bound analysis whenH≪DH\\ll D, even if the reciprocal lower\-bound coefficient is numerically the dominant factor in an upper\-to\-lower sandwich\. These statements concern different comparisons\. The fixed\-diameter sweep tests the first; the constants scoreboard addresses the second\. We do not report an empirical lower–upper sandwich while the upper ledger is incomplete\.

#### Limitations and next steps\.

The present theory is tabular, and the strongest finite coefficients use action\-rich regimes\. The broadA≥5A\\geq 5row still requires conservative diameter and horizon thresholds, while reducing those thresholds trades away part of the improvement\. Directional confidence over an adaptive bias region is more demanding than a pointwise Bernstein inequality, and a certified planner is more demanding than ordinary value iteration\. The natural next steps are to improve the frontier for smallAA, obtain a prior\-free span procedure with tracked constants, and prove a log\-free expected upper analysis under the same normalization as the lower certificate\.