Bayesian $\kappa$-Explorer for Minimax Model Estimation in MDPs

arXiv cs.LG Papers

Summary

The paper introduces Bayesian κ-Explorer, which places Dirichlet priors on MDP transition distributions to simplify minimax transition estimation by replacing confidence-set optimization with a closed-form posterior variance exploration signal, while retaining the Õ(T^-1/3) convergence rate of the frequentist κ-Explorer and showing lower worst-case estimation errors on Pendulum, Mountain Car, and Taxi.

arXiv:2611.25160v1 Announce Type: new Abstract: We study active exploration for minimax transition estimation in unknown Markov decision processes (MDPs). Frequentist $\kappa$-Explorer~\citep{gu2026kappa} addresses this problem through a parameterized family of exploration objectives, but requires confidence-bound constructions and joint optimization over plausible transition kernels and occupancy measures, introducing a computational burden that limits its practical applicability. We develop Bayesian $\kappa$-Explorer, which simplifies this procedure by placing Dirichlet priors on the transition distributions. Under the posterior mean estimator, the posterior expected squared $\ell_2$ error equals the total posterior variance, providing a closed-form exploration signal. The algorithm plans under the posterior mean model, eliminating confidence-set optimization. Under the stated assumptions, this simpler planning procedure retains the $\widetilde{O}(T^{-1/3})$ surrogate convergence rate of frequentist $\kappa$-Explorer. We further bound the maximum posterior variance relative to the optimal asymptotic minimax allocation benchmark. Experiments on Pendulum, Mountain Car, and Taxi demonstrate lower worst-case transition-estimation errors than the tested baselines.
Original Article
View Cached Full Text

Cached at: 11/20/26, 09:15 AM

# Bayesian 𝜅-Explorer for Minimax Model Estimation in MDPs
Source: [https://arxiv.org/html/2611.25160](https://arxiv.org/html/2611.25160)
Xihe GuEmail:[x9gu@ucsd\.edu](mailto:[email protected])Affiliation:University of California, San Diego and University of Southern California and University of California, San DiegoTara JavidiEmail:[tjavidi@ucsd\.edu](mailto:[email protected])Affiliation:

###### Abstract

We study active exploration for minimax transition estimation in unknown Markov decision processes \(MDPs\)\. Frequentistκ\\kappa\-Explorer\([Gu et al\., 2026b](https://arxiv.org/html/2611.25160#bib.bib9)\)addresses this problem through a parameterized family of exploration objectives, but requires confidence\-bound constructions and joint optimization over plausible transition kernels and occupancy measures, introducing a computational burden that limits its practical applicability\. We develop Bayesianκ\\kappa\-Explorer, which simplifies this procedure by placing Dirichlet priors on the transition distributions\. Under the posterior mean estimator, the posterior expected squaredℓ2\\ell\_\{2\}error equals the total posterior variance, providing a closed\-form exploration signal\. The algorithm plans under the posterior mean model, eliminating confidence\-set optimization\. Under the stated assumptions, this simpler planning procedure retains the𝒪~\(T−1/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/3\}\)surrogate convergence rate of frequentistκ\\kappa\-Explorer\. We further bound the maximum posterior variance relative to the optimal asymptotic minimax allocation benchmark\. Experiments on Pendulum, Mountain Car, and Taxi demonstrate lower worst\-case transition\-estimation errors than the tested baselines\.

###### keywords

active model estimation, Bayesian exploration, minimax estimation, Markov decision processes, posterior variance

## 1Introduction

Accurately estimating the transition dynamics of an unknown Markov decision process \(MDP\) is a fundamental problem in reward\-free reinforcement learning\([Araya\-López et al\., 2011](https://arxiv.org/html/2611.25160#bib.bib4);[Tarbouriech et al\., 2020](https://arxiv.org/html/2611.25160#bib.bib1)\)\. Under a limited interaction budget, observations must be allocated according to the intrinsic estimation complexity of each state–action pair: nearly deterministic transitions require fewer samples than transitions spread across many possible next states\. To obtain uniformly accurate estimates, we therefore seek to minimize the largest transition\-estimation error across state–action pairs\([Shekhar et al\., 2020](https://arxiv.org/html/2611.25160#bib.bib5);[Shekhar et al\., 2021](https://arxiv.org/html/2611.25160#bib.bib7);[Tarbouriech et al\., 2020](https://arxiv.org/html/2611.25160#bib.bib1);[Gu et al\., 2026a](https://arxiv.org/html/2611.25160#bib.bib8)\)\.

Minimax estimation in MDPs is difficult for two distinct reasons\. First, visitation frequencies are coupled through the dynamics, so increasing visits to one state–action pair affects the sampling allocation elsewhere\. Prior work addresses coverage through state\-visitation entropy\([Hazan et al\., 2019](https://arxiv.org/html/2611.25160#bib.bib2)\), trajectory entropy\([Tiapkin et al\., 2023](https://arxiv.org/html/2611.25160#bib.bib3)\), or more general concave objectives\([Gu et al\., 2026a](https://arxiv.org/html/2611.25160#bib.bib8)\)\. However, broad coverage or matching a prescribed target does not necessarily yield the instance\-dependent allocation required for minimax estimation\. Second, the minimax objective is nonsmooth, preventing the direct application of methods designed for average estimation error or other smooth objectives\([Tarbouriech et al\., 2020](https://arxiv.org/html/2611.25160#bib.bib1)\)\.

The frequentistκ\\kappa\-Explorer framework in[Gu et al\. \(2026b\)](https://arxiv.org/html/2611.25160#bib.bib9)addresses these challenges through a family of exploration objectives, parameterized by a curvature exponentκ\\kappa, that approximate minimax estimation\. Its central principle is to prioritize state–action pairs that are intrinsically difficult to estimate and insufficiently visited, using aκ\\kappa\-powered complexity\-to\-visitation ratio as the exploration reward\. However, implementing this principle under unknown dynamics requires estimating both the transition kernel and the intrinsic complexity, together with confidence bounds for these quantities\. The resulting optimistic planning step jointly optimizes over a confidence set of transition kernels and their associated occupancy measures, introducing a computational burden that limits its practical applicability\.

In this work, we develop Bayesianκ\\kappa\-Explorer by placing independent Dirichlet priors on the transition distributions\. The posterior mean minimizes the posterior expected squaredℓ2\\ell\_\{2\}estimation error, and the resulting minimum equals the total posterior variance\. Both admit closed\-form expressions in terms of the Dirichlet posterior parameters\. The posterior variance retains the intrinsic–extrinsic structure: its numerator captures a posterior\-mean analogue of transition complexity, while its denominator incorporates the prior concentration and the sampling effort accumulated under past policies\. This characterization provides a directly computable exploration signal without separate confidence bounds on intrinsic complexity\. This approach avoids constructing confidence sets for planning and replaces joint optimization over transition kernels and occupancy measures with planning under a single model, while retaining the same convergence rate\. To the best of our knowledge, this is the first posterior\-variance\-driven exploration algorithm that combines posterior\-mean planning with a quantitative guarantee on the maximum posterior expected squared transition\-estimation error relative to the optimal asymptotic minimax allocation benchmark\.

The remainder of the paper is organized as follows\. After formulating the problem, we present Bayesianκ\\kappa\-Explorer and state its guarantee on the maximum posterior variance\. We then evaluate the algorithm on three benchmark environments, where it outperforms the tested baselines in worst\-case transition\-estimation error\. Finally, we develop the theoretical analysis and establish the guarantee by bounding its error components\.

## 2Problem Formulation

We consider a finite controlled Markov chain with state space𝒮\\mathcal\{S\},\|𝒮\|=S\|\\mathcal\{S\}\|=S, and action space𝒜\\mathcal\{A\},\|𝒜\|=A\|\\mathcal\{A\}\|=A\. At each timet=0,1,…t=0,1,\\ldots, the agent observesst∈𝒮s\_\{t\}\\in\\mathcal\{S\}, selectsat∈𝒜a\_\{t\}\\in\\mathcal\{A\}, and transitions tost\+1s\_\{t\+1\}according to an unknown kernelP⋆\(⋅∣st,at\)P^\{\\star\}\(\\cdot\\mid s\_\{t\},a\_\{t\}\)\. A stationary randomized policyπ:𝒮→Δ⁡\(𝒜\)\\pi:\\mathcal\{S\}\\to\\Delta\(\\mathcal\{A\}\)specifies the action distribution at each state, andΠ\\Pidenotes the set of such policies\.

Our goal is to estimate the entire transition kernel usingTTobservations\. We minimize the worst\-case expected squaredℓ2\\ell\_\{2\}transition\-estimation error:

max\(s,a\)∈𝒮×𝒜𝔼π\[‖P⋆\(⋅∣s,a\)−P^T\(⋅∣s,a\)‖22\],\\max\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\mathbb\{E\}\_\{\\pi\}\\\!\\left\[\\left\\\|P^\{\\star\}\(\\cdot\\mid s,a\)\-\\widehat\{P\}\_\{T\}\(\\cdot\\mid s,a\)\\right\\\|\_\{2\}^\{2\}\\right\],\(1\)where the expectation is over the trajectory generated byπ\\pi, andP^T\\widehat\{P\}\_\{T\}is an estimator of the transition kernel\. To estimate the transition probabilities, we define the transition count afterttsamples asNt​\(s,a,s′\):=∑τ=0t−1𝟏​\{sτ=s,aτ=a,sτ\+1=s′\}N\_\{t\}\(s,a,s^\{\\prime\}\):=\\sum\_\{\\tau=0\}^\{t\-1\}\\mathbf\{1\}\\\{s\_\{\\tau\}=s,\\ a\_\{\\tau\}=a,\\ s\_\{\\tau\+1\}=s^\{\\prime\}\\\}and the state–action visit count asNt​\(s,a\):=∑s′∈𝒮Nt​\(s,a,s′\)\.N\_\{t\}\(s,a\):=\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}N\_\{t\}\(s,a,s^\{\\prime\}\)\.Thus,∑s,aNt​\(s,a\)=t\\sum\_\{s,a\}N\_\{t\}\(s,a\)=t\. LetTTbe the total sampling budget\.

We adopt a Bayesian perspective and regardP⋆P^\{\\star\}as a realization of a random transition kernelPPwith independent Dirichlet priors on its rows:P\(⋅∣s,a\)∼Dir\(α0\(s,a,⋅\)\),α0\(s,a,s′\)\>0\.P\(\\cdot\\mid s,a\)\\sim\\operatorname\{Dir\}\\\!\\bigl\(\\alpha\_\{0\}\(s,a,\\cdot\)\\bigr\),\\quad\\alpha\_\{0\}\(s,a,s^\{\\prime\}\)\>0\.A classical choice is the Jeffreys prior,Dir⁡\(1/2,…,1/2\)\\operatorname\{Dir\}\(1/2,\\ldots,1/2\), whose posterior mean yields the Krichevsky–Trofimov estimator, known for its universal coding guarantees\([Krichevsky and Trofimov, 1981](https://arxiv.org/html/2611.25160#bib.bib10)\)\. We writeβ0​\(s,a\):=∑s′α0​\(s,a,s′\)\\beta\_\{0\}\(s,a\):=\\sum\_\{s^\{\\prime\}\}\\alpha\_\{0\}\(s,a,s^\{\\prime\}\)for the prior concentration andμ0​\(s′∣s,a\):=α0​\(s,a,s′\)/β0​\(s,a\)\\mu\_\{0\}\(s^\{\\prime\}\\mid s,a\):=\\alpha\_\{0\}\(s,a,s^\{\\prime\}\)/\\beta\_\{0\}\(s,a\)for the prior mean\. Together,β0\\beta\_\{0\}andμ0\\mu\_\{0\}specify the Dirichlet prior\. Letℱt:=σ⁡\(s0,a0,s1,…,at−1,st\)\\mathcal\{F\}\_\{t\}:=\\sigma\(s\_\{0\},a\_\{0\},s\_\{1\},\\ldots,a\_\{t\-1\},s\_\{t\}\)denote the observed history aftertttransitions\.

By Dirichlet conjugacy,

P\(⋅∣s,a\)∣ℱt∼Dir\(αt\(s,a,⋅\)\),αt\(s,a,s′\):=α0\(s,a,s′\)\+Nt\(s,a,s′\)\.P\(\\cdot\\mid s,a\)\\mid\\mathcal\{F\}\_\{t\}\\sim\\operatorname\{Dir\}\\\!\\bigl\(\\alpha\_\{t\}\(s,a,\\cdot\)\\bigr\),\\qquad\\alpha\_\{t\}\(s,a,s^\{\\prime\}\):=\\alpha\_\{0\}\(s,a,s^\{\\prime\}\)\+N\_\{t\}\(s,a,s^\{\\prime\}\)\.\(2\)The posterior concentration and posterior mean are

βt​\(s,a\):=∑s′αt​\(s,a,s′\)=β0​\(s,a\)\+Nt​\(s,a\),μt​\(s′∣s,a\):=αt​\(s,a,s′\)βt​\(s,a\)\.\\beta\_\{t\}\(s,a\):=\\sum\_\{s^\{\\prime\}\}\\alpha\_\{t\}\(s,a,s^\{\\prime\}\)=\\beta\_\{0\}\(s,a\)\+N\_\{t\}\(s,a\),\\qquad\\mu\_\{t\}\(s^\{\\prime\}\\mid s,a\):=\\frac\{\\alpha\_\{t\}\(s,a,s^\{\\prime\}\)\}\{\\beta\_\{t\}\(s,a\)\}\.\(3\)Since we are interested in minimizing the MSE in \([1](https://arxiv.org/html/2611.25160#S2.E1)\), we use the posterior mean as our model estimator, settingP^t:=μt\\widehat\{P\}\_\{t\}:=\\mu\_\{t\}\. It is the minimum mean squared error \(MMSE\) estimator under the Bayesian model\. The posterior mean squared error of this estimator can be expressed using the standard Dirichlet variance formula\([Kotz et al\., 2019](https://arxiv.org/html/2611.25160#bib.bib11)\):

Vt​\(s,a\)\\displaystyle V\_\{t\}\(s,a\):=𝔼\[‖P\(⋅∣s,a\)−μt\(⋅∣s,a\)‖22\|ℱt\]\\displaystyle:=\\mathbb\{E\}\\\!\\left\[\\left\\\|P\(\\cdot\\mid s,a\)\-\\mu\_\{t\}\(\\cdot\\mid s,a\)\\right\\\|\_\{2\}^\{2\}\\,\\middle\|\\,\\mathcal\{F\}\_\{t\}\\right\]\(4\)=∑s′∈𝒮Var⁡\[P⁡\(s′∣s,a\)\|ℱt\]\\displaystyle=\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}\\operatorname\{Var\}\\\!\\left\[P\(s^\{\\prime\}\\mid s,a\)\\,\\middle\|\\,\\mathcal\{F\}\_\{t\}\\right\]=∑s′∈𝒮μt​\(s′∣s,a\)​\(1−μt​\(s′∣s,a\)\)βt​\(s,a\)\+1\\displaystyle=\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}\\frac\{\\mu\_\{t\}\(s^\{\\prime\}\\mid s,a\)\\bigl\(1\-\\mu\_\{t\}\(s^\{\\prime\}\\mid s,a\)\\bigr\)\}\{\\beta\_\{t\}\(s,a\)\+1\}=ct​\(s,a\)βt​\(s,a\)\+1,\\displaystyle=\\frac\{c\_\{t\}\(s,a\)\}\{\\beta\_\{t\}\(s,a\)\+1\},wherect​\(s,a\):=1−∑s′∈𝒮μt​\(s′∣s,a\)2\.c\_\{t\}\(s,a\):=1\-\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}\\mu\_\{t\}\(s^\{\\prime\}\\mid s,a\)^\{2\}\.This expression reveals an intrinsic–extrinsic decomposition of posterior uncertainty\. The numeratorct​\(s,a\)c\_\{t\}\(s,a\)is a posterior\-mean analogue of the*intrinsic complexity*

c⋆​\(s,a\):=∑s′∈𝒮P⋆​\(s′∣s,a\)​\(1−P⋆​\(s′∣s,a\)\),c^\{\\star\}\(s,a\):=\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}P^\{\\star\}\(s^\{\\prime\}\\mid s,a\)\\bigl\(1\-P^\{\\star\}\(s^\{\\prime\}\\mid s,a\)\\bigr\),\(5\)which characterizes the statistical difficulty of estimating the next\-state distribution at\(s,a\)\(s,a\)\. Throughout the theoretical analysis, we assumec⋆​\(s,a\)\>0c^\{\\star\}\(s,a\)\>0for every\(s,a\)\(s,a\)\. The denominatorβt​\(s,a\)\+1=β0​\(s,a\)\+Nt​\(s,a\)\+1\\beta\_\{t\}\(s,a\)\+1=\\beta\_\{0\}\(s,a\)\+N\_\{t\}\(s,a\)\+1combines the prior concentration with the*extrinsic*sampling effort\. These two intrinsic and extrinsic factors together govern estimation accuracy\.

We evaluate the learned model by its worst\-case posterior uncertainty afterTTobservations:

MT:=max\(s,a\)∈𝒮×𝒜⁡VT​\(s,a\)\.M\_\{T\}:=\\max\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}V\_\{T\}\(s,a\)\.\(6\)Our goal is to design an adaptive sampling strategy that makesMTM\_\{T\}as small as possible\. In the next section, we introduce an algorithm that uses the posterior meanμt\\mu\_\{t\}and posterior uncertaintyVtV\_\{t\}to guide exploration toward reducing the maximum posterior uncertainty\. It avoids constructing separate confidence bounds for the transition kernel and its intrinsic complexity, thereby simplifying the planning problem\.

## 3Bayesianκ\\kappa\-Explorer

We introduce Bayesianκ\\kappa\-Explorer and establish an upper bound on the maximum posterior varianceMTM\_\{T\}attained by the algorithm\.

### 3\.1Algorithm

Bayesianκ\\kappa\-Explorer takes as input the priorsα0\\alpha\_\{0\}, curvature parameterκ≥1\\kappa\\geq 1, occupancy floorη\>0\\eta\>0, confidence levelδ\\delta, and episode lengthsτ1,…,τJ\\tau\_\{1\},\\ldots,\\tau\_\{J\}\. At the start of each episode, the algorithm updates the posterior using the observations collected so far, constructs an exploration reward from the posterior uncertainty, and plans under the posterior mean transition model\. The resulting policy is executed for the duration of the episode\.

#### Exploration Reward\.

Lettmt\_\{m\}denote the start time of episodemm\. At timetmt\_\{m\}, the algorithm uses the accumulated counts to compute the posterior meanμtm\\mu\_\{t\_\{m\}\}and posterior varianceVtmV\_\{t\_\{m\}\}, and assigns each state–action pair the exploration reward

rm​\(s,a\):=Vtm​\(s,a\)κ,κ≥1\.r\_\{m\}\(s,a\):=V\_\{t\_\{m\}\}\(s,a\)^\{\\kappa\},\\qquad\\kappa\\geq 1\.\(7\)Increasingκ\\kappaamplifies the reward ratio between pairs with higher and lower positive posterior variance, placing greater emphasis on the most uncertain state–action pairs\.

#### Posterior\-Mean Planning\.

Given the exploration rewardrmr\_\{m\}, we plan under the posterior mean transition kernelμtm\\mu\_\{t\_\{m\}\}\. To account for the dynamical constraints, define the stationary occupancy domain for a transition kernelppas

𝒟\(p\):=\{𝐝∈Δ\(𝒮×𝒜\):∑a∈𝒜d\(s,a\)=∑s′,a′p\(s∣s′,a′\)d\(s′,a′\),∀s∈𝒮\}\.\\mathcal\{D\}^\{\(p\)\}:=\\left\\\{\\mathbf\{d\}\\in\\Delta\(\\mathcal\{S\}\\times\\mathcal\{A\}\):\\sum\_\{a\\in\\mathcal\{A\}\}d\(s,a\)=\\sum\_\{s^\{\\prime\},a^\{\\prime\}\}p\(s\\mid s^\{\\prime\},a^\{\\prime\}\)d\(s^\{\\prime\},a^\{\\prime\}\),\\qquad\\forall s\\in\\mathcal\{S\}\\right\\\}\.\(8\)To assign strictly positive mass to every state–action pair in the planned allocation, we introduce the constrained occupancy domain forη∈\(0,1/\(2​S​A\)\)\\eta\\in\(0,1/\(2SA\)\):

𝒟η\(p\):=\{𝐝∈𝒟\(p\):d\(s,a\)≥2η,∀\(s,a\)∈𝒮×𝒜\}\.\\mathcal\{D\}\_\{\\eta\}^\{\(p\)\}:=\\left\\\{\\mathbf\{d\}\\in\\mathcal\{D\}^\{\(p\)\}:d\(s,a\)\\geq 2\\eta,\\quad\\forall\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\right\\\}\.\(9\)We assume thatη\\etais chosen small enough such that𝒟η\(μtm\)\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}is nonempty at every episode\. The planner computes the episode policy through

𝝍m∈arg​max𝐝∈𝒟η\(μtm\)∑s,arm\(s,a\)d\(s,a\),πm\(a∣s\):=ψm​\(s,a\)∑b∈𝒜ψm​\(s,b\)\.\\boldsymbol\{\\psi\}\_\{m\}\\in\\operatorname\*\{arg\\,max\}\_\{\\mathbf\{d\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}\}\\sum\_\{s,a\}r\_\{m\}\(s,a\)d\(s,a\),\\qquad\\pi\_\{m\}\(a\\mid s\):=\\frac\{\\psi\_\{m\}\(s,a\)\}\{\\sum\_\{b\\in\\mathcal\{A\}\}\\psi\_\{m\}\(s,b\)\}\.\(10\)The algorithm executesπm\\pi\_\{m\}on the true MDP forτm\\tau\_\{m\}transitions, starting from the current state, and updates the transition counts using the resulting observations\. After the final episode, it returns the posterior meanμT\\mu\_\{T\}, whereT=∑m=1JτmT=\\sum\_\{m=1\}^\{J\}\\tau\_\{m\}\. Algorithm[3\.1](https://arxiv.org/html/2611.25160#S3.SS1.SSS0.Px2)summarizes these steps\.

\{algorithm2e\}

\[H\]Bayesianκ\\kappa\-Explorer\\KwInPriorsα0\\alpha\_\{0\}, curvature parameterκ≥1\\kappa\\geq 1, occupancy lower\-bound parameterη\>0\\eta\>0, confidence levelδ\\delta, episode lengthsτ1,…,τJ\\tau\_\{1\},\\ldots,\\tau\_\{J\}\\KwOutTransition estimateP^T\\widehat\{P\}\_\{T\}Sett1←0t\_\{1\}\\leftarrow 0and initialize all transition counts to zero\\Form=1,…,Jm=1,\\ldots,JComputeμtm\\mu\_\{t\_\{m\}\}andVtmV\_\{t\_\{m\}\}using \([3](https://arxiv.org/html/2611.25160#S2.E3)\) and \([4](https://arxiv.org/html/2611.25160#S2.E4)\) Setrm​\(s,a\)←Vtm​\(s,a\)κr\_\{m\}\(s,a\)\\leftarrow V\_\{t\_\{m\}\}\(s,a\)^\{\\kappa\}for each\(s,a\)\(s,a\)Solve \([10](https://arxiv.org/html/2611.25160#S3.E10)\) for𝝍m\\boldsymbol\{\\psi\}\_\{m\}and formπm\\pi\_\{m\}Executeπm\\pi\_\{m\}forτm\\tau\_\{m\}transitions and update the counts Settm\+1←tm\+τmt\_\{m\+1\}\\leftarrow t\_\{m\}\+\\tau\_\{m\}ComputeμT\\mu\_\{T\}from the final countsreturnP^T=μT\\widehat\{P\}\_\{T\}=\\mu\_\{T\}

### 3\.2Main Guarantee

To benchmarkMTM\_\{T\}, we consider the best allocation in the constrained occupancy domain of the true kernel:

C⋆:=min𝐝∈𝒟\(P⋆\)⁡max\(s,a\)∈𝒮×𝒜​c⋆​\(s,a\)d⁡\(s,a\),𝐝⋆∈arg​min𝐝∈𝒟\(P⋆\)⁡max\(s,a\)∈𝒮×𝒜​c⋆​\(s,a\)d⁡\(s,a\),C^\{\\star\}:=\\min\_\{\\mathbf\{d\}\\in\\mathcal\{D\}^\{\(P^\{\\star\}\)\}\}\\max\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\frac\{c^\{\\star\}\(s,a\)\}\{d\(s,a\)\},\\qquad\\mathbf\{d\}^\{\\star\}\\in\\operatorname\*\{arg\\,min\}\_\{\\mathbf\{d\}\\in\\mathcal\{D\}^\{\(P^\{\\star\}\)\}\}\\max\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\frac\{c^\{\\star\}\(s,a\)\}\{d\(s,a\)\},\(11\)wheremax\(s,a\)∈𝒮×𝒜⁡c⋆​\(s,a\)d⁡\(s,a\):=\+∞\\max\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\frac\{c^\{\\star\}\(s,a\)\}\{d\(s,a\)\}:=\+\\inftyif any component of𝐝\\mathbf\{d\}is zero\. The corresponding asymptotic variance benchmark isC⋆/TC^\{\\star\}/T\. We can now state the main guarantee\.

###### Theorem 2\(Maximum posterior variance bound\)\.

Under technical Assumptions[1](https://arxiv.org/html/2611.25160#Thmassumption1)and[2](https://arxiv.org/html/2611.25160#Thmassumption2), stated below, run Algorithm[3\.1](https://arxiv.org/html/2611.25160#S3.SS1.SSS0.Px2)withκ≥1\\kappa\\geq 1and appropriately chosenη\\etaand episode lengthsτm\\tau\_\{m\}\. For everyδ∈\(0,1\)\\delta\\in\(0,1\), there exists a thresholdT0​\(δ\)T\_\{0\}\(\\delta\)such that, for everyT≥T0​\(δ\)T\\geq T\_\{0\}\(\\delta\), the following bounds hold with probability at least1−δ1\-\\delta\.

MT≤C⋆T\+\(η−1/κ−1\)C⋆T⏟finite\-κapproximation\+η−1/κ\(κ−1\)εopt\(T,δ/2\)κ​T​\(C⋆\)κ−1⏟allocation optimization\+εpost​\(T,δ/2\)⏟posterior estimation\.M\_\{T\}\\leq\{\}\\frac\{C^\{\\star\}\}\{T\}\+\\underbrace\{\\frac\{\(\\eta^\{\-1/\\kappa\}\-1\)C^\{\\star\}\}\{T\}\}\_\{\\text\{finite\-$\\kappa$ approximation\}\}\+\\underbrace\{\\frac\{\\eta^\{\-1/\\kappa\}\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta/2\)\}\{\\kappa T\(C^\{\\star\}\)^\{\\kappa\-1\}\}\}\_\{\\text\{allocation optimization\}\}\+\\underbrace\{\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta/2\)\}\_\{\\text\{posterior estimation\}\}\.\(12\)On the same event, the following bound applies for allC⋆≥0C^\{\\star\}\\geq 0:

MT≤η−1/κT​\[\(C⋆\)κ\+\(κ−1\)​εopt​\(T,δ/2\)\]1/κ\+εpost​\(T,δ/2\)\.M\_\{T\}\\leq\\frac\{\\eta^\{\-1/\\kappa\}\}\{T\}\\left\[\(C^\{\\star\}\)^\{\\kappa\}\+\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta/2\)\\right\]^\{1/\\kappa\}\+\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta/2\)\.\(13\)

The finite\-κ\\kappaterm in \([12](https://arxiv.org/html/2611.25160#S3.E12)\) comes from approximating the maximum in \([11](https://arxiv.org/html/2611.25160#S3.E11)\) by aggregating the allocation costs across state–action pairs\. For fixedη\\eta, the approximation factorη−1/κ\\eta^\{\-1/\\kappa\}tends to one asκ\\kappagrows\. The allocation optimization term reflects the surrogate objective gap between the empirical allocation and the optimal allocation\. Our analysis yields an upper boundεopt\(T,δ\)=𝒪~\(T−1/3\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)=\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/3\}\), so its contribution to the posterior variance bound is𝒪~\(T−4/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-4/3\}\)for fixedκ\\kappa,η\\eta,δ\\delta, andC⋆C^\{\\star\}\. The posterior estimation termεpost​\(T,δ\)\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\)controls the contribution of the coefficient error\. Under the visitation floor, this term is𝒪~\(T−3/2\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-3/2\}\)for fixedη\\etaandδ\\delta\. Section[5](https://arxiv.org/html/2611.25160#S5)provides the technical assumptions, the specific choice ofη\\etaandτm\\tau\_\{m\}, as well as the details of the analysis\.

## 4Experiments

We evaluate how effectively the proposed algorithm reduces the estimation error on three discretized domains compared with other methods\.

### 4\.1Experimental Setup

#### Environments\.

We evaluate transition model estimation in three tabular MDPs based on Pendulum, Mountain Car, and Taxi from the Gymnasium control suite introduced by[Brockman et al\. \(2016\)](https://arxiv.org/html/2611.25160#bib.bib12)\. InPendulum, we discretize the angle and angular velocity into ten bins each and use five torque levels, givingS=100S=100states andA=5A=5actions\. InMountain Car, we discretize position and velocity into sixteen and seven bins, respectively, and retain the three original actions, givingS=112S=112andA=3A=3\. We introduce stochastic transitions by perturbing the updated angle and angular velocity in Pendulum and the updated velocity in Mountain Car\. InTaxi, we use a variant of the original5×55\\times 5map withS=400S=400states andA=6A=6actions\. Its action perturbations act through legal Taxi transitions and respect the walls of the map\.

#### Baselines\.

We compare Bayesianκ\\kappa\-Explorer with the following exploration methods\.Randomselects an action uniformly at random at each time step,At∼𝒰⁡\(𝒜\)A\_\{t\}\\sim\\mathcal\{U\}\(\\mathcal\{A\}\)\.MaxEnt\([Hazan et al\., 2019](https://arxiv.org/html/2611.25160#bib.bib2)\)maximizes visitation entropy to encourage broad exploration\. We use the joint state–action visitation distribution so that the objective encourages coverage of both states and actions\.ModEst\_LSE\([Tarbouriech et al\., 2020](https://arxiv.org/html/2611.25160#bib.bib1)\)optimizes a log\-sum\-exp surrogate for the worst\-case transition estimation error\.Weighted\_MaxEnt\([Tarbouriech et al\., 2020](https://arxiv.org/html/2611.25160#bib.bib1)\)maximizes weighted state–action visitation entropy, assigning greater weight to transitions that are harder to estimate\.State Marginal Matching \(SMM\)\([Lee et al\., 2019](https://arxiv.org/html/2611.25160#bib.bib6)\)encourages the visitation distribution to match a target\. We adapt SMM to state–action pairs and set the target mass proportional to the estimated transition complexity of each pair\.

#### Evaluation protocol\.

We test each method with 20 random seeds in each environment\. The sampling budget is the number of observed transitionsTT, with a maximum of100,000100\{,\}000for Pendulum and Taxi and300,000300\{,\}000for Mountain Car\. We evaluate the transition estimateP^t\\widehat\{P\}\_\{t\}at each checkpoint using the worst\-caseℓ2\\ell\_\{2\}error

max\(s,a\)∈𝒮×𝒜‖P^t\(⋅∣s,a\)−P⋆\(⋅∣s,a\)‖2\.\\max\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\left\\\|\\widehat\{P\}\_\{t\}\(\\cdot\\mid s,a\)\-P^\{\\star\}\(\\cdot\\mid s,a\)\\right\\\|\_\{2\}\.We take the maximum over state–action pairs separately for each seed and then average the resulting errors across seeds\. For Taxi,P⋆P^\{\\star\}is the exact transition kernel\. For Pendulum and Mountain Car, we construct a fixed reference kernel from independent simulator samples for each state–action pair\. The reference kernels are used only for evaluation\.

### 4\.2Pendulum Case Study

Figure[1](https://arxiv.org/html/2611.25160#S4.F1)depicts the Pendulum environment whose dynamics remains challenging to estimate even after every state–action pair has been visited\. Under random actions, the pendulum frequently passes through the lower part of its swing, whereas near\-upright states with low angular velocity are harder to revisit or remain at\. Consequently, some of the states remain poorly sampled and dominate the worst\-case error\.

\\subfigure\[Pendulum\]![Refer to caption](https://arxiv.org/html/2611.25160v1/Fig/pendulum.png)\\subfigure\[Worst\-case error vs\. budget \(S=100,A=5S=100,A=5\)\]![Refer to caption](https://arxiv.org/html/2611.25160v1/Fig/Pendulum_error_legend.png)

Figure 1:Pendulum:Worst\-case transition estimation error versus sampling budget\. Orange curves correspond to Bayesianκ\\kappa\-Explorer withκ∈\{1,2,5,10,100\}\\kappa\\in\\\{1,2,5,10,100\\\}, and blue curves correspond to the baselines\. Each curve is averaged over 20 random seeds\.κ\\kappa\-Explorer addresses this imbalance through its exploration reward\. Among pairs with comparable intrinsic complexities, the score prioritizes those with fewer samples\. The planner can then choose a sequence of torques that brings the pendulum back to the desired angle and angular velocity and samples the action of interest\. In Figure[1](https://arxiv.org/html/2611.25160#S4.F1), several choices ofκ\\kappareduce the error faster than the strongest baselines during the early part of data collection\. At the largest sampling budget, all settings ofκ\\kappa\-Explorer achieve a lower worst\-case error than the best\-performing baseline\.

The effect ofκ\\kappais nonmonotonic\. Moderate values can reduce the error faster or achieve a lower final error thanκ=100\\kappa=100\. Increasingκ\\kappaconcentrates the exploration reward on the highest\-scoring pairs\. For example, if those pairs lie near the upright position, a very largeκ\\kappamay favor trajectories that use large torques \(\+2/−2\+2/\-2\) to reach them quickly\. On the other hand, transitions under smaller torques \(\+1/−1\+1/\-1\) along the way may then be neglected and remain undersampled\. This illustrates a possible mechanism for the observed trade\-off\. A moderateκ\\kappagives more weight to these additional sampling opportunities, which can help reduce the worst\-case error across all state–action pairs\.

### 4\.3Results on Mountain Car and Taxi

Figure[2](https://arxiv.org/html/2611.25160#S4.F2)compares Bayesianκ\\kappa\-Explorer with the baselines on Mountain Car and Taxi\. In both environments, all tested values ofκ\\kappaachieve lower worst\-case transition estimation errors than the baselines at larger sampling budgets\. On Mountain Car, moderate values ofκ\\kappareduce the error faster thanκ=100\\kappa=100over parts of the budget range\. On Taxi, theκ\\kappa\-Explorer curves are closer together toward the end of the run\. Overall,κ\\kappa\-Explorer outperforms the baselines at larger sampling budgets in both environments, while the sensitivity toκ\\kappadiffers between them\.

![Refer to caption](https://arxiv.org/html/2611.25160v1/Fig/comparison_shared_legend.png)Figure 2:Mountain Car and Taxi:Worst\-case transition estimation error versus sampling budget\. Orange curves show Bayesianκ\\kappa\-Explorer forκ∈\{1,2,5,10,100\}\\kappa\\in\\\{1,2,5,10,100\\\}, and blue curves show the baselines\. Each curve is averaged over 20 random seeds\.

## 5Theoretical Analysis

We prove Theorem[2](https://arxiv.org/html/2611.25160#Thmtheorem2)in three steps\. First, we relate the minimax allocation objective to the smooth surrogateUκU\_\{\\kappa\}\. Next, we bound the convergence gap of Bayesianκ\\kappa\-Explorer onUκU\_\{\\kappa\}\. Finally, we bound the posterior estimation error and combine the results\.

### 5\.1Surrogate Objective and Minimax Approximation

For strictly positive allocations𝐝∈Δ⁡\(𝒮×𝒜\)\\mathbf\{d\}\\in\\Delta\(\\mathcal\{S\}\\times\\mathcal\{A\}\)and curvature parameterκ∈ℤ\+\\kappa\\in\\mathbb\{Z\}^\{\+\}, define the concave utility

Uκ​\(𝐝\):=\{∑s,ac⋆​\(s,a\)​log⁡d⁡\(s,a\),κ=1,11−κ​∑s,ac⋆​\(s,a\)κ​d​\(s,a\)1−κ,κ\>1\.U\_\{\\kappa\}\(\\mathbf\{d\}\):=\\begin\{cases\}\\displaystyle\\sum\_\{s,a\}c^\{\\star\}\(s,a\)\\log d\(s,a\),&\\kappa=1,\\\\\[3\.0pt\] \\dfrac\{1\}\{1\-\\kappa\}\\displaystyle\\sum\_\{s,a\}c^\{\\star\}\(s,a\)^\{\\kappa\}d\(s,a\)^\{1\-\\kappa\},&\\kappa\>1\.\\end\{cases\}\(14\)The objectiveUκU\_\{\\kappa\}is concave and separable across state–action pairs\. A key property is that its gradient satisfies\(∇Uκ​\(𝐝\)\)s,a=\(cs,a⋆d⁡\(s,a\)\)κ\.\\bigl\(\\nabla U\_\{\\kappa\}\(\\mathbf\{d\}\)\\bigr\)\_\{s,a\}=\\left\(\\frac\{c^\{\\star\}\_\{s,a\}\}\{d\(s,a\)\}\\right\)^\{\\kappa\}\.

###### Proposition 3\(Finite\-κ\\kappaapproximation\)\.

Letκ\>1\\kappa\>1\. For any probability vector𝐝\\mathbf\{d\}withd⁡\(s,a\)≥ηd\(s,a\)\\geq\\etafor all\(s,a\)\(s,a\),

η1/κ​maxs,a​c⋆​\(s,a\)d⁡\(s,a\)≤\[\(1−κ\)​Uκ​\(d\)\]1/κ≤maxs,a⁡c⋆​\(s,a\)d⁡\(s,a\)\.\\eta^\{1/\\kappa\}\\max\_\{s,a\}\\frac\{c^\{\\star\}\(s,a\)\}\{d\(s,a\)\}\\leq\\bigl\[\(1\-\\kappa\)U\_\{\\kappa\}\(d\)\\bigr\]^\{1/\\kappa\}\\leq\\max\_\{s,a\}\\frac\{c^\{\\star\}\(s,a\)\}\{d\(s,a\)\}\.\(15\)

The proof is the same as that of Proposition 1 in[Gu et al\. \(2026b\)](https://arxiv.org/html/2611.25160#bib.bib9)\.

### 5\.2Convergence Analysis

We analyze the convergence of Algorithm[3\.1](https://arxiv.org/html/2611.25160#S3.SS1.SSS0.Px2)through a Frank–Wolfe\([Frank et al\., 1956](https://arxiv.org/html/2611.25160#bib.bib13)\)interpretation\. Fort≥1t\\geq 1, define the empirical visitation vector𝐝^t\\widehat\{\\mathbf\{d\}\}\_\{t\}by its componentsd^t​\(s,a\):=Nt​\(s,a\)/t\.\\widehat\{d\}\_\{t\}\(s,a\):=N\_\{t\}\(s,a\)/t\.For strictly positive𝐝^tm\\widehat\{\\mathbf\{d\}\}\_\{t\_\{m\}\}, the rescaled reward approximates∇Uκ​\(𝐝^tm\)\\nabla U\_\{\\kappa\}\(\\widehat\{\\mathbf\{d\}\}\_\{t\_\{m\}\}\)by replacingc⋆​\(s,a\)c^\{\\star\}\(s,a\)withctm​\(s,a\)c\_\{t\_\{m\}\}\(s,a\)and incorporating the prior\-dependent offset in the denominator\. Since multiplication by the positive scalartmκt\_\{m\}^\{\\kappa\}leaves the maximizers of \([10](https://arxiv.org/html/2611.25160#S3.E10)\) unchanged, the planning step can be interpreted as an approximate Frank–Wolfe linear maximization step, using an estimated gradient and a feasible occupancy domain determined by the posterior mean kernel\. For the analysis, we impose the following communicating assumption\.

###### Assumption 1\(Communicating MDP\)\.

The finite MDPℳ⋆=\(𝒮,𝒜,P⋆\)\\mathcal\{M\}^\{\\star\}=\(\\mathcal\{S\},\\mathcal\{A\},P^\{\\star\}\)is communicating: for every pair of statess,s′s,s^\{\\prime\}, there exist a policyπ\\piand a finite timet≥0t\\geq 0such that

ℙP⋆π​\(St=s′∣S0=s\)\>0\.\\mathbb\{P\}\_\{P^\{\\star\}\}^\{\\pi\}\(S\_\{t\}=s^\{\\prime\}\\mid S\_\{0\}=s\)\>0\.

With that, we establish the following convergence guarantees\.

###### Lemma 4\(Surrogate convergence rate\)\.

LetP⋆P^\{\\star\}satisfy Assumption[1](https://arxiv.org/html/2611.25160#Thmassumption1)\. Fixκ≥1\\kappa\\geq 1and let the episode lengths satisfyτm=τ1​m2,\\tau\_\{m\}=\\tau\_\{1\}m^\{2\},such thattm=∑j=1m−1τj=τ1​\(m−1\)​m​\(2​m−1\)6\.t\_\{m\}=\\sum\_\{j=1\}^\{m\-1\}\\tau\_\{j\}=\\tau\_\{1\}\\frac\{\(m\-1\)m\(2m\-1\)\}\{6\}\.Let𝐝κ⋆∈arg⁡max𝐝∈𝒟\(P⋆\)​Uκ​\(𝐝\)\\mathbf\{d\}\_\{\\kappa\}^\{\\star\}\\in\\arg\\max\_\{\\mathbf\{d\}\\in\\mathcal\{D\}^\{\(P^\{\\star\}\)\}\}U\_\{\\kappa\}\(\\mathbf\{d\}\)be the optimizer\. Assume thatη\\etais chosen such that2​η<mins,a⁡dκ⋆​\(s,a\)\.2\\eta<\\min\_\{s,a\}d\_\{\\kappa\}^\{\\star\}\(s,a\)\.Such anη\\etaexists by Lemma[6](https://arxiv.org/html/2611.25160#Thmtheorem6)in Appendix[A](https://arxiv.org/html/2611.25160#A1)\. Then, afterJJepisodes, withT=∑m=1JτmT=\\sum\_\{m=1\}^\{J\}\\tau\_\{m\}, we have, with probability at least1−δ1\-\\delta,

εopt\(T,δ\):=Uκ\(𝐝κ⋆\)−Uκ\(𝐝^T\)≤𝒪~\(T−1/3\)\.\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\):=U\_\{\\kappa\}\(\\mathbf\{d\}\_\{\\kappa\}^\{\\star\}\)\-U\_\{\\kappa\}\\\!\\left\(\\widehat\{\\mathbf\{d\}\}\_\{T\}\\right\)\\leq\\widetilde\{\\mathcal\{O\}\}\\\!\\left\(T^\{\-1/3\}\\right\)\.

The proof of Lemma[4](https://arxiv.org/html/2611.25160#Thmtheorem4)follows the same structure as that of Theorem 2 in[Gu et al\. \(2026b\)](https://arxiv.org/html/2611.25160#bib.bib9), except for the method used to boundϵm:=⟨∇Uκ​\(𝐝^tm\),𝝍m⋆−𝝍m⟩,\\epsilon\_\{m\}:=\\left\\langle\\nabla U\_\{\\kappa\}\(\\widehat\{\\mathbf\{d\}\}\_\{t\_\{m\}\}\),\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\boldsymbol\{\\psi\}\_\{m\}\\right\\rangle,which captures the optimization and estimation error induced by planning under unknown transition dynamics\. Fortm\>0t\_\{m\}\>0, define the normalized planning weights bywm​\(s,a\):=\[tm​Vtm​\(s,a\)\]κ\.w\_\{m\}\(s,a\):=\[t\_\{m\}V\_\{t\_\{m\}\}\(s,a\)\]^\{\\kappa\}\.This positive rescaling leaves the planning maximizers unchanged\. Define the occupancies selected by the posterior\-mean planner and the true\-model gradient oracle, together with their weighted discrepancy, as follows:

𝝍m∈arg​max𝐝∈𝒟η\(μtm\)⁡⟨𝐰m,𝐝⟩,𝝍m⋆∈arg​max𝐝∈𝒟η\(P⋆\)⁡⟨∇Uκ​\(𝐝^tm\),𝐝⟩,Gm:=⟨𝐰m,𝝍m⋆−𝝍m⟩\.\\boldsymbol\{\\psi\}\_\{m\}\\in\\operatorname\*\{arg\\,max\}\_\{\\mathbf\{d\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}\}\\langle\\mathbf\{w\}\_\{m\},\\mathbf\{d\}\\rangle,\\qquad\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\\in\\operatorname\*\{arg\\,max\}\_\{\\mathbf\{d\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(P^\{\\star\}\)\}\}\\left\\langle\\nabla U\_\{\\kappa\}\(\\widehat\{\\mathbf\{d\}\}\_\{t\_\{m\}\}\),\\mathbf\{d\}\\right\\rangle,\\qquad G\_\{m\}:=\\left\\langle\\mathbf\{w\}\_\{m\},\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\boldsymbol\{\\psi\}\_\{m\}\\right\\rangle\.In the frequentist analysis \(Appendix B of[Gu et al\. \(2026b\)](https://arxiv.org/html/2611.25160#bib.bib9)\), the analogous termGmG\_\{m\}is nonpositive on the eventP⋆∈ℬtmP^\{\\star\}\\in\\mathcal\{B\}\_\{t\_\{m\}\}, because the true\-model oracle occupancy𝝍m⋆\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}is feasible for the optimistic planner and both are evaluated using the same planning weights\. In contrast, in the Bayesian setting,𝝍m⋆\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}need not belong to the posterior\-mean planning domain𝒟η\(μtm\)\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}\.

We define the transition estimation error byΔmP:=maxs,a‖P⋆\(⋅∣s,a\)−μtm\(⋅∣s,a\)‖1\.\\Delta\_\{m\}^\{P\}:=\\max\_\{s,a\}\\left\\\|P^\{\\star\}\(\\cdot\\mid s,a\)\-\\mu\_\{t\_\{m\}\}\(\\cdot\\mid s,a\)\\right\\\|\_\{1\}\.We bound the resulting discrepancy using the following stability assumption with respect to the transition estimation error\.

###### Assumption 2\(Uniform occupancy stability\)\.

There exists a constantL<∞L<\\infty, independent of the policy and episode, such that for every stationary policyπ\\piwithπ⁡\(a∣s\)\>0\\pi\(a\\mid s\)\>0for all\(s,a\)\(s,a\)and every episodemm, the induced chains underP⋆P^\{\\star\}andμtm\\mu\_\{t\_\{m\}\}admit unique stationary occupancy measures satisfying‖𝐝μtmπ−𝐝P⋆π‖1≤L​ΔmP\.\\left\\\|\\mathbf\{d\}\_\{\\mu\_\{t\_\{m\}\}\}^\{\\pi\}\-\\mathbf\{d\}\_\{P^\{\\star\}\}^\{\\pi\}\\right\\\|\_\{1\}\\leq L\\Delta\_\{m\}^\{P\}\.

Assumption[2](https://arxiv.org/html/2611.25160#Thmassumption2)ensures that, for a fixed policy, the stationary occupancy measure is stable inℓ1\\ell\_\{1\}distance under small perturbations of the transition kernel\. Together with strict feasibility under the true kernel, this implies that the true\-model oracle occupancy𝝍m⋆\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}admits a feasible counterpart𝝍¯m∈𝒟η\(μtm\)\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}satisfying‖𝝍m⋆−𝝍¯m‖1≤Cocc​ΔmP,\\\|\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\\|\_\{1\}\\leq C\_\{\\rm occ\}\\Delta\_\{m\}^\{P\},whereCoccC\_\{\\rm occ\}is independent of the episode indexmm\. This result is established in Lemma[7](https://arxiv.org/html/2611.25160#Thmtheorem7)in Appendix[B](https://arxiv.org/html/2611.25160#A2)\. Therefore, we can find a𝝍¯m∈𝒟η\(μtm\)\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}that is close to𝝍m⋆\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}and also satisfies⟨𝐰m,𝝍m⟩≥⟨𝐰m,𝝍¯m⟩\\langle\\mathbf\{w\}\_\{m\},\\boldsymbol\{\\psi\}\_\{m\}\\rangle\\geq\\langle\\mathbf\{w\}\_\{m\},\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\rangle, which allows us to write

Gm=⟨𝐰m,𝝍m⋆−𝝍¯m⟩\+⟨𝐰m,𝝍¯m−𝝍m⟩⏟≤0\.G\_\{m\}=\\langle\\mathbf\{w\}\_\{m\},\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\rangle\+\\underbrace\{\\langle\\mathbf\{w\}\_\{m\},\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\-\\boldsymbol\{\\psi\}\_\{m\}\\rangle\}\_\{\\leq 0\}\.Further bounding the first term gives an upper bound ofO\(tm−1/2\)O\(t\_\{m\}^\{\-1/2\}\)onGmG\_\{m\}; details are provided in Appendix[C](https://arxiv.org/html/2611.25160#A3)\. We further conclude that, at each fixed episode and for fixed posterior failure probabilityδ\\delta,ϵm\\epsilon\_\{m\}admits anO\(tm−1/2\)O\(t\_\{m\}^\{\-1/2\}\)upper bound, with all other parameters held constant \(see Appendix[D](https://arxiv.org/html/2611.25160#A4)for details\)\. This matches theO\(tm−1/2\)O\(t\_\{m\}^\{\-1/2\}\)rate of the corresponding frequentist oracle\-error bound, while avoiding the construction of a confidence ball for planning\.

### 5\.3Posterior Coefficient Error

We next bound the remaining term, which accounts for the discrepancy between the posterior and true intrinsic complexities\.

###### Lemma 5\(Posterior coefficient error\)\.

ForT≥1T\\geq 1andδ∈\(0,1\)\\delta\\in\(0,1\), letqT​\(δ\):=log⁡\(4​S2​A​T/δ\)q\_\{T\}\(\\delta\):=\\log\(4S^\{2\}AT/\\delta\)andβmax:=maxs,a⁡β0​\(s,a\)\\beta\_\{\\max\}:=\\max\_\{s,a\}\\beta\_\{0\}\(s,a\)\. With probability at least1−δ/21\-\\delta/2under the fixed\-kernel trajectory law, ifd^T​\(s,a\)≥η\\widehat\{d\}\_\{T\}\(s,a\)\\geq\\etafor all\(s,a\)\(s,a\), then

εpost​\(T,δ\)\\displaystyle\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\):=maxs,a⁡\|cT​\(s,a\)−c⋆​\(s,a\)\|NT​\(s,a\)\+β0​\(s,a\)\+1\\displaystyle:=\\max\_\{s,a\}\\frac\{\|c\_\{T\}\(s,a\)\-c^\{\\star\}\(s,a\)\|\}\{N\_\{T\}\(s,a\)\+\\beta\_\{0\}\(s,a\)\+1\}\(16\)≤1η​T\+mins,a⁡β0​\(s,a\)\+1​\(2​S​qT​\(δ\)η​T\+2​2​βmaxη​T\)\.\\displaystyle\\leq\\frac\{1\}\{\\eta T\+\\min\_\{s,a\}\\beta\_\{0\}\(s,a\)\+1\}\\left\(\\sqrt\{\\frac\{2Sq\_\{T\}\(\\delta\)\}\{\\eta T\}\}\+\\frac\{2\\sqrt\{2\}\\,\\beta\_\{\\max\}\}\{\\eta T\}\\right\)\.

The proof of Lemma[5](https://arxiv.org/html/2611.25160#Thmtheorem5)is in Appendix[E](https://arxiv.org/html/2611.25160#A5)\. Combining the finite\-κ\\kappaapproximation bound from Proposition[3](https://arxiv.org/html/2611.25160#Thmtheorem3), the optimization error boundεopt​\(T,δ\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)from Lemma[4](https://arxiv.org/html/2611.25160#Thmtheorem4), and the posterior coefficient error boundεpost​\(T,δ\)\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\)from Lemma[5](https://arxiv.org/html/2611.25160#Thmtheorem5)yields Theorem[2](https://arxiv.org/html/2611.25160#Thmtheorem2)\. The proof is provided in Appendix[F](https://arxiv.org/html/2611.25160#A6)\.

## 6Conclusion

In this work, we build on the frequentistκ\\kappa\-Explorer algorithm introduced in[Gu et al\. \(2026b\)](https://arxiv.org/html/2611.25160#bib.bib9)and develop a Bayesian approach to minimax transition estimation in unknown MDPs\. We retain the parameterized family of exploration objectives that approximate minimax estimation and establish convergence through a Frank–Wolfe interpretation\. By placing Dirichlet priors on the transition distributions, we express posterior expected squared estimation error as a closed\-form posterior variance and use itsκ\\kappath power to guide exploration\. Planning under the posterior mean model eliminates separate confidence\-bound constructions and joint optimization over transition kernels and occupancy measures, yielding a simpler and computationally more efficient algorithm\. Under the stated assumptions, we preserve the𝒪~\(T−1/3\)\\widetilde\{\\mathcal\{O\}\}\(T^\{\-1/3\}\)surrogate convergence rate of frequentistκ\\kappa\-Explorer and bound the maximum posterior variance relative to the optimal asymptotic minimax allocation benchmark\. Experiments on Pendulum, Mountain Car, and Taxi demonstrate lower worst\-case transition\-estimation errors than the tested baselines, both early in data collection and at larger sampling budgets\.

### Generative AI Use

Generative AI tools were used to assist with revising and polishing the manuscript, developing portions of the proofs, and writing portions of the experimental code\. The authors reviewed and verified all AI\-assisted content, including the mathematical arguments and experimental code, and conducted all experiments themselves\. The authors take full responsibility for the accuracy and integrity of the final manuscript\.

###### acknowledgments\-disclosure\-of\-funding\.

We gratefully acknowledge support from ONR, the NSF TILOS AI Institute, and the UCSD Centers for Machine Intelligence, Computing, and Security \(MICS\)\.

## References

- Araya\-Lópezet al\.\(2011\)M\. Araya\-López, O\. Buffet, V\. Thomas, and F\. CharpilletActive learning of mdp models\.InEuropean Workshop on Reinforcement Learning,pp\. 42–53\.Cited by:[§1](https://arxiv.org/html/2611.25160#S1.p1.1)\.
- Brockmanet al\.\(2016\)G\. Brockman, V\. Cheung, L\. Pettersson, J\. Schneider, J\. Schulman, J\. Tang, and W\. ZarembaOpenai gym\.arXiv preprint arXiv:1606\.01540\.Cited by:[§4\.1](https://arxiv.org/html/2611.25160#S4.SS1.SSS0.Px1.p1.1)\.
- Franket al\.\(1956\)M\. Frank P\. Wolfeet al\.An algorithm for quadratic programming\.Naval research logistics quarterly3\(1\-2\),pp\. 95–110\.Cited by:[§5\.2](https://arxiv.org/html/2611.25160#S5.SS2.p1.1)\.
- Guet al\.\(2026a\)X\. Gu, U\. Mitra, and T\. JavidiFrom relative entropy to minimax: a unified framework for coverage in mdps\.arXiv preprint arXiv:2601\.11890\.Cited by:[§1](https://arxiv.org/html/2611.25160#S1.p1.1),[§1](https://arxiv.org/html/2611.25160#S1.p2.1)\.
- Guet al\.\(2026b\)X\. Gu, U\. Mitra, and T\. Javidik​a​p​p​akappa\-Explorer: a unified framework for active model estimation in mdps\.arXiv preprint arXiv:2602\.20404\.Cited by:[Appendix A](https://arxiv.org/html/2611.25160#A1.p1.1),[§1](https://arxiv.org/html/2611.25160#S1.p3.1),[§5\.1](https://arxiv.org/html/2611.25160#S5.SS1.p2.1),[§5\.2](https://arxiv.org/html/2611.25160#S5.SS2.p3.1),[§5\.2](https://arxiv.org/html/2611.25160#S5.SS2.p3.2),[§6](https://arxiv.org/html/2611.25160#S6.p1.1),[Remark 1](https://arxiv.org/html/2611.25160#Thmtheorem1.p1.1.1),[Abstract](https://arxiv.org/html/2611.25160#abstract1.1)\.
- Hazanet al\.\(2019\)E\. Hazan, S\. Kakade, K\. Singh, and A\. Van SoestProvably efficient maximum entropy exploration\.InInternational Conference on Machine Learning,pp\. 2681–2691\.Cited by:[§1](https://arxiv.org/html/2611.25160#S1.p2.1),[§4\.1](https://arxiv.org/html/2611.25160#S4.SS1.SSS0.Px2.p1.1)\.
- Kotzet al\.\(2019\)S\. Kotz, N\. Balakrishnan, and N\. L\. JohnsonContinuous multivariate distributions, volume 1: models and applications\.Vol\.1,John wiley & sons\.Cited by:[§2](https://arxiv.org/html/2611.25160#S2.p4.4)\.
- Krichevsky and Trofimov \(1981\)R\. Krichevsky and V\. TrofimovThe performance of universal encoding\.IEEE Transactions on Information Theory27\(2\),pp\. 199–207\.Cited by:[§2](https://arxiv.org/html/2611.25160#S2.p3.1)\.
- Leeet al\.\(2019\)L\. Lee, B\. Eysenbach, E\. Parisotto, E\. Xing, S\. Levine, and R\. SalakhutdinovEfficient exploration via state marginal matching\.arXiv preprint arXiv:1906\.05274\.Cited by:[§4\.1](https://arxiv.org/html/2611.25160#S4.SS1.SSS0.Px2.p1.1)\.
- Shekharet al\.\(2021\)S\. Shekhar, G\. Fields, M\. Ghavamzadeh, and T\. JavidiAdaptive sampling for minimax fair classification\.Advances in Neural Information Processing Systems34,pp\. 24535–24544\.Cited by:[§1](https://arxiv.org/html/2611.25160#S1.p1.1)\.
- Shekharet al\.\(2020\)S\. Shekhar, T\. Javidi, and M\. GhavamzadehAdaptive sampling for estimating probability distributions\.InInternational Conference on Machine Learning,pp\. 8687–8696\.Cited by:[§1](https://arxiv.org/html/2611.25160#S1.p1.1)\.
- Tarbouriechet al\.\(2020\)J\. Tarbouriech, S\. Shekhar, M\. Pirotta, M\. Ghavamzadeh, and A\. LazaricActive model estimation in markov decision processes\.InConference on Uncertainty in Artificial Intelligence,pp\. 1019–1028\.Cited by:[§1](https://arxiv.org/html/2611.25160#S1.p1.1),[§1](https://arxiv.org/html/2611.25160#S1.p2.1),[§4\.1](https://arxiv.org/html/2611.25160#S4.SS1.SSS0.Px2.p1.1)\.
- Tiapkinet al\.\(2023\)D\. Tiapkin, D\. Belomestny, D\. Calandriello, E\. Moulines, R\. Munos, A\. Naumov, P\. Perrault, Y\. Tang, M\. Valko, and P\. MenardFast rates for maximum entropy exploration\.InInternational Conference on Machine Learning,pp\. 34161–34221\.Cited by:[§1](https://arxiv.org/html/2611.25160#S1.p2.1)\.

## Appendix APositive Feasible Occupancy

###### Lemma 6\(Positive feasible occupancy\)\.

Under Assumption[1](https://arxiv.org/html/2611.25160#Thmassumption1), there exists a stationary occupancy measure𝐝¯∈𝒟\(P⋆\)\\bar\{\\mathbf\{d\}\}\\in\\mathcal\{D\}^\{\(P^\{\\star\}\)\}such that

dmin:=mins,a⁡d¯​\(s,a\)\>0\.d\_\{\\min\}:=\\min\_\{s,a\}\\bar\{d\}\(s,a\)\>0\.Consequently,𝒟η\(P⋆\)\\mathcal\{D\}\_\{\\eta\}^\{\(P^\{\\star\}\)\}is nonempty whenever0<2​η≤dmin0<2\\eta\\leq d\_\{\\min\}\.

The proof follows the same argument as that of Lemma 1 in[Gu et al\. \(2026b\)](https://arxiv.org/html/2611.25160#bib.bib9)\.

According to Lemma[6](https://arxiv.org/html/2611.25160#Thmtheorem6), a strictly positive feasible occupancy exists andc⋆​\(s,a\)\>0c^\{\\star\}\(s,a\)\>0for every\(s,a\)\(s,a\), thus any minimizer𝐝κ⋆\\mathbf\{d\}^\{\\star\}\_\{\\kappa\}must satisfy

mins,a⁡dκ⋆​\(s,a\)\>0\.\\min\_\{s,a\}d^\{\\star\}\_\{\\kappa\}\(s,a\)\>0\.Consequently, there existsη∈\(0,1/\(2​S​A\)\)\\eta\\in\(0,1/\(2SA\)\)with2​η≤mins,a⁡dκ⋆​\(s,a\)2\\eta\\leq\\min\_\{s,a\}d^\{\\star\}\_\{\\kappa\}\(s,a\)such that𝐝κ⋆∈𝒟η\(P⋆\)\\mathbf\{d\}^\{\\star\}\_\{\\kappa\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(P^\{\\star\}\)\}\.

## Appendix BFeasible Occupancy Counterpart

###### Lemma 7\(Feasible occupancy counterpart\)\.

Suppose Assumption[2](https://arxiv.org/html/2611.25160#Thmassumption2)holds\. Assume that there exist a reference occupancy𝐝¯∈𝒟\(P⋆\)\\bar\{\\mathbf\{d\}\}\\in\\mathcal\{D\}^\{\(P^\{\\star\}\)\}and a constanth\>0h\>0such that

d¯​\(s,a\)≥2​η\+hfor every​\(s,a\),\\bar\{d\}\(s,a\)\\geq 2\\eta\+h\\qquad\\text\{for every \}\(s,a\),and that𝒟η\(μtm\)\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}is nonempty at every episode\. Then, for every𝐝∈𝒟η\(P⋆\)\\mathbf\{d\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(P^\{\\star\}\)\}and every episodemm, there exists𝐝~∈𝒟η\(μtm\)\\widetilde\{\\mathbf\{d\}\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}such that

‖𝐝~−𝐝‖1≤Cocc​ΔmP,Cocc:=L⁡\(1\+2h\)\.\\\|\\widetilde\{\\mathbf\{d\}\}\-\\mathbf\{d\}\\\|\_\{1\}\\leq C\_\{\\rm occ\}\\Delta\_\{m\}^\{P\},\\qquad C\_\{\\rm occ\}:=L\\left\(1\+\\frac\{2\}\{h\}\\right\)\.In particular, the true\-model oracle occupancy𝛙m⋆\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}admits a feasible counterpart𝛙¯m∈𝒟η\(μtm\)\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}satisfying

‖𝝍m⋆−𝝍¯m‖1≤Cocc​ΔmP\.\\\|\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\\|\_\{1\}\\leq C\_\{\\rm occ\}\\Delta\_\{m\}^\{P\}\.

###### Proof\.

Fix an episodemmand an occupancy𝐝∈𝒟η\(P⋆\)\\mathbf\{d\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(P^\{\\star\}\)\}, and writeem:=L​ΔmPe\_\{m\}:=L\\Delta\_\{m\}^\{P\}\. Letπ\\piandπ¯\\bar\{\\pi\}be the stationary policies induced by𝐝\\mathbf\{d\}and𝐝¯\\bar\{\\mathbf\{d\}\}, respectively\. Both policies assign positive probability to every action at every state\. Their stationary occupancy measures under the posterior mean kernel are

𝐪:=𝐝μtmπ,𝐪¯:=𝐝μtmπ¯\.\\mathbf\{q\}:=\\mathbf\{d\}\_\{\\mu\_\{t\_\{m\}\}\}^\{\\pi\},\\qquad\\bar\{\\mathbf\{q\}\}:=\\mathbf\{d\}\_\{\\mu\_\{t\_\{m\}\}\}^\{\\bar\{\\pi\}\}\.By Assumption[2](https://arxiv.org/html/2611.25160#Thmassumption2),

‖𝐪−𝐝‖1≤em,‖𝐪¯−𝐝¯‖1≤em\.\\\|\\mathbf\{q\}\-\\mathbf\{d\}\\\|\_\{1\}\\leq e\_\{m\},\\qquad\\\|\\bar\{\\mathbf\{q\}\}\-\\bar\{\\mathbf\{d\}\}\\\|\_\{1\}\\leq e\_\{m\}\.Consequently, for every\(s,a\)\(s,a\),

q⁡\(s,a\)≥2​η−em,q¯​\(s,a\)≥2​η\+h−em\.q\(s,a\)\\geq 2\\eta\-e\_\{m\},\\qquad\\bar\{q\}\(s,a\)\\geq 2\\eta\+h\-e\_\{m\}\.
First supposeem≤he\_\{m\}\\leq h\. Although𝐪\\mathbf\{q\}need not satisfy the occupancy floor, both𝐪\\mathbf\{q\}and𝐪¯\\bar\{\\mathbf\{q\}\}belong to𝒟\(μtm\)\\mathcal\{D\}^\{\(\\mu\_\{t\_\{m\}\}\)\}\. Since this domain is convex, the mixture

𝐝~:=\(1−λm\)​𝐪\+λm​𝐪¯,λm:=emh∈\[0,1\],\\widetilde\{\\mathbf\{d\}\}:=\(1\-\\lambda\_\{m\}\)\\mathbf\{q\}\+\\lambda\_\{m\}\\bar\{\\mathbf\{q\}\},\\qquad\\lambda\_\{m\}:=\\frac\{e\_\{m\}\}\{h\}\\in\[0,1\],also belongs to𝒟\(μtm\)\\mathcal\{D\}^\{\(\\mu\_\{t\_\{m\}\}\)\}\. Moreover,

d~​\(s,a\)≥\(1−λm\)​\(2​η−em\)\+λm​\(2​η\+h−em\)=2​η\.\\widetilde\{d\}\(s,a\)\\geq\(1\-\\lambda\_\{m\}\)\(2\\eta\-e\_\{m\}\)\+\\lambda\_\{m\}\(2\\eta\+h\-e\_\{m\}\)=2\\eta\.Thus,𝐝~∈𝒟η\(μtm\)\\widetilde\{\\mathbf\{d\}\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}\. Using the fact that theℓ1\\ell\_\{1\}distance between two probability vectors is at most22, we obtain

‖𝐝~−𝐝‖1\\displaystyle\\\|\\widetilde\{\\mathbf\{d\}\}\-\\mathbf\{d\}\\\|\_\{1\}≤‖𝐪−𝐝‖1\+λm​‖𝐪¯−𝐪‖1\\displaystyle\\leq\\\|\\mathbf\{q\}\-\\mathbf\{d\}\\\|\_\{1\}\+\\lambda\_\{m\}\\\|\\bar\{\\mathbf\{q\}\}\-\\mathbf\{q\}\\\|\_\{1\}≤em\+2​emh\\displaystyle\\leq e\_\{m\}\+\\frac\{2e\_\{m\}\}\{h\}=Cocc​ΔmP\.\\displaystyle=C\_\{\\rm occ\}\\Delta\_\{m\}^\{P\}\.
Now supposeem\>he\_\{m\}\>h\. By nonemptiness, choose any𝐝~∈𝒟η\(μtm\)\\widetilde\{\\mathbf\{d\}\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}\. Then

‖𝐝~−𝐝‖1≤2<2​emh≤Cocc​ΔmP\.\\\|\\widetilde\{\\mathbf\{d\}\}\-\\mathbf\{d\}\\\|\_\{1\}\\leq 2<\\frac\{2e\_\{m\}\}\{h\}\\leq C\_\{\\rm occ\}\\Delta\_\{m\}^\{P\}\.This proves the claim in both cases\. Taking𝐝=𝝍m⋆\\mathbf\{d\}=\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}yields the stated oracle counterpart\. ∎

## Appendix CPosterior Bound on the Planning Discrepancy

###### Proposition 8\(Posterior bound on the planning discrepancy\)\.

Fix an episodemmwithtm\>0t\_\{m\}\>0\. Suppose𝐰m\\mathbf\{w\}\_\{m\}isℱtm\\mathcal\{F\}\_\{t\_\{m\}\}\-measurable,‖𝐰m‖∞≤W\\\|\\mathbf\{w\}\_\{m\}\\\|\_\{\\infty\}\\leq W, andNtm​\(s,a\)≥ν​tmN\_\{t\_\{m\}\}\(s,a\)\\geq\\nu t\_\{m\}for every\(s,a\)\(s,a\), whereW,ν\>0W,\\nu\>0are deterministic constants independent ofmm\.

Define the eventℰm:=\{ΔmP≤\(Sδ∑s,aVtm\(s,a\)\)1/2\}\.\\mathcal\{E\}\_\{m\}:=\\left\\\{\\Delta\_\{m\}^\{P\}\\leq\\left\(\\frac\{S\}\{\\delta\}\\sum\_\{s,a\}V\_\{t\_\{m\}\}\(s,a\)\\right\)^\{1/2\}\\right\\\}\.By the posterior variance identity,𝔼⁡\[\(ΔmP\)2∣ℱtm\]≤S​∑s,aVtm​\(s,a\)\.\\mathbb\{E\}\\\!\\left\[\(\\Delta\_\{m\}^\{P\}\)^\{2\}\\mid\\mathcal\{F\}\_\{t\_\{m\}\}\\right\]\\leq S\\sum\_\{s,a\}V\_\{t\_\{m\}\}\(s,a\)\.Letℋm\\mathcal\{H\}\_\{m\}be an event on which the conditions of Lemma[7](https://arxiv.org/html/2611.25160#Thmtheorem7)hold with a common deterministic constantCoccC\_\{\\rm occ\}\. Conditional Markov’s inequality therefore givesPr⁡\(ℰm∣ℱtm\)≥1−δ\.\\Pr\(\\mathcal\{E\}\_\{m\}\\mid\\mathcal\{F\}\_\{t\_\{m\}\}\)\\geq 1\-\\delta\.

Onℰm∩ℋm\\mathcal\{E\}\_\{m\}\\cap\\mathcal\{H\}\_\{m\},

Gm\+\\displaystyle G\_\{m\}^\{\+\}:=max⁡\{Gm,0\}\\displaystyle:=\\max\\\{G\_\{m\},0\\\}\(17\)≤Rm:=Cocc​W​\(Sδ​∑s,actm​\(s,a\)βtm​\(s,a\)\+1\)1/2\\displaystyle\\leq R\_\{m\}:=C\_\{\\rm occ\}W\\left\(\\frac\{S\}\{\\delta\}\\sum\_\{s,a\}\\frac\{c\_\{t\_\{m\}\}\(s,a\)\}\{\\beta\_\{t\_\{m\}\}\(s,a\)\+1\}\\right\)^\{1/2\}≤Cocc​W​S​Aδ⁡\(βmin\+ν​tm\+1\),\\displaystyle\\leq C\_\{\\rm occ\}WS\\sqrt\{\\frac\{A\}\{\\delta\(\\beta\_\{\\min\}\+\\nu t\_\{m\}\+1\)\}\},whereβmin:=mins,a⁡β0​\(s,a\)\\beta\_\{\\min\}:=\\min\_\{s,a\}\\beta\_\{0\}\(s,a\)\. For fixedδ\\delta, the final bound isO\(tm−1/2\)O\(t\_\{m\}^\{\-1/2\}\)\.

###### Proof\.

Onℋm\\mathcal\{H\}\_\{m\}, Lemma[7](https://arxiv.org/html/2611.25160#Thmtheorem7)provides𝝍¯m∈𝒟η\(μtm\)\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\in\\mathcal\{D\}\_\{\\eta\}^\{\(\\mu\_\{t\_\{m\}\}\)\}satisfying

‖𝝍m⋆−𝝍¯m‖1≤Cocc​ΔmP\.\\\|\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\\|\_\{1\}\\leq C\_\{\\rm occ\}\\Delta\_\{m\}^\{P\}\.By the optimality of the posterior\-mean planner,

Gm\\displaystyle G\_\{m\}=⟨𝐰m,𝝍m⋆−𝝍¯m⟩\+⟨𝐰m,𝝍¯m−𝝍m⟩⏟≤0\\displaystyle=\\langle\\mathbf\{w\}\_\{m\},\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\rangle\+\\underbrace\{\\langle\\mathbf\{w\}\_\{m\},\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\-\\boldsymbol\{\\psi\}\_\{m\}\\rangle\}\_\{\\leq 0\}≤W​‖𝝍m⋆−𝝍¯m‖1\\displaystyle\\leq W\\\|\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\bar\{\\boldsymbol\{\\psi\}\}\_\{m\}\\\|\_\{1\}≤Cocc​W​ΔmP\.\\displaystyle\\leq C\_\{\\rm occ\}W\\Delta\_\{m\}^\{P\}\.Since the right\-hand side is nonnegative, the same bound holds forGm\+G\_\{m\}^\{\+\}\.

Under the Bayesian model,P⋆P^\{\\star\}is the realized value of the random kernelPP\. Using‖𝐱‖12≤S​‖𝐱‖22\\\|\\mathbf\{x\}\\\|\_\{1\}^\{2\}\\leq S\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\}and the posterior variance identity gives

𝔼⁡\[\(ΔmP\)2∣ℱtm\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\(\\Delta\_\{m\}^\{P\}\)^\{2\}\\mid\\mathcal\{F\}\_\{t\_\{m\}\}\\right\]≤S∑s,a𝔼\[∥P\(⋅∣s,a\)−μtm\(⋅∣s,a\)∥22\|ℱtm\]\\displaystyle\\leq S\\sum\_\{s,a\}\\mathbb\{E\}\\\!\\left\[\\\|P\(\\cdot\\mid s,a\)\-\\mu\_\{t\_\{m\}\}\(\\cdot\\mid s,a\)\\\|\_\{2\}^\{2\}\\,\\middle\|\\,\\mathcal\{F\}\_\{t\_\{m\}\}\\right\]=S​∑s,aVtm​\(s,a\)\.\\displaystyle=S\\sum\_\{s,a\}V\_\{t\_\{m\}\}\(s,a\)\.Conditional Markov’s inequality therefore yields an eventℰm\\mathcal\{E\}\_\{m\}with posterior probability at least1−δ1\-\\deltaon which

ΔmP≤\(Sδ​∑s,aVtm​\(s,a\)\)1/2\.\\Delta\_\{m\}^\{P\}\\leq\\left\(\\frac\{S\}\{\\delta\}\\sum\_\{s,a\}V\_\{t\_\{m\}\}\(s,a\)\\right\)^\{1/2\}\.Combining the two bounds onℰm∩ℋm\\mathcal\{E\}\_\{m\}\\cap\\mathcal\{H\}\_\{m\}givesGm\+≤RmG\_\{m\}^\{\+\}\\leq R\_\{m\}\. Finally, using

Vtm​\(s,a\)=ctm​\(s,a\)βtm​\(s,a\)\+1,ctm​\(s,a\)≤1,V\_\{t\_\{m\}\}\(s,a\)=\\frac\{c\_\{t\_\{m\}\}\(s,a\)\}\{\\beta\_\{t\_\{m\}\}\(s,a\)\+1\},\\qquad c\_\{t\_\{m\}\}\(s,a\)\\leq 1,andβtm​\(s,a\)≥βmin\+ν​tm\\beta\_\{t\_\{m\}\}\(s,a\)\\geq\\beta\_\{\\min\}\+\\nu t\_\{m\}proves \([17](https://arxiv.org/html/2611.25160#A3.E17)\)\. ∎

## Appendix DBoundingϵm\\epsilon\_\{m\}

Adding and subtracting𝐰m\\mathbf\{w\}\_\{m\}in the oracle error gives, on the same event,

ϵm\\displaystyle\\epsilon\_\{m\}=Gm\+⟨∇Uκ​\(𝐝^tm\)−𝐰m,𝝍m⋆−𝝍m⟩\\displaystyle=G\_\{m\}\+\\left\\langle\\nabla U\_\{\\kappa\}\(\\widehat\{\\mathbf\{d\}\}\_\{t\_\{m\}\}\)\-\\mathbf\{w\}\_\{m\},\\,\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\boldsymbol\{\\psi\}\_\{m\}\\right\\rangle\(18\)≤Rm\+2​‖∇Uκ​\(𝐝^tm\)−𝐰m‖∞,\\displaystyle\\leq R\_\{m\}\+2\\left\\\|\\nabla U\_\{\\kappa\}\(\\widehat\{\\mathbf\{d\}\}\_\{t\_\{m\}\}\)\-\\mathbf\{w\}\_\{m\}\\right\\\|\_\{\\infty\},where we used‖𝝍m⋆−𝝍m‖1≤2\\\|\\boldsymbol\{\\psi\}\_\{m\}^\{\\star\}\-\\boldsymbol\{\\psi\}\_\{m\}\\\|\_\{1\}\\leq 2\.

Under the sampling condition,d^tm​\(s,a\)≥ν\\widehat\{d\}\_\{t\_\{m\}\}\(s,a\)\\geq\\nu, and

tm​Vtm​\(s,a\)=ctm​\(s,a\)d^tm​\(s,a\)\+\(β0​\(s,a\)\+1\)/tm≤ν−1\.t\_\{m\}V\_\{t\_\{m\}\}\(s,a\)=\\frac\{c\_\{t\_\{m\}\}\(s,a\)\}\{\\widehat\{d\}\_\{t\_\{m\}\}\(s,a\)\+\(\\beta\_\{0\}\(s,a\)\+1\)/t\_\{m\}\}\\leq\\nu^\{\-1\}\.Thus, one may takeW=ν−κW=\\nu^\{\-\\kappa\}\.

To control the gradient error, first observe that

\|ctm\(s,a\)−c⋆\(s,a\)\|≤2∥μtm\(⋅∣s,a\)−P⋆\(⋅∣s,a\)∥1≤2ΔmP\.\|c\_\{t\_\{m\}\}\(s,a\)\-c^\{\\star\}\(s,a\)\|\\leq 2\\\|\\mu\_\{t\_\{m\}\}\(\\cdot\\mid s,a\)\-P^\{\\star\}\(\\cdot\\mid s,a\)\\\|\_\{1\}\\leq 2\\Delta\_\{m\}^\{P\}\.Letbmax:=maxs,a⁡\(β0​\(s,a\)\+1\)b\_\{\\max\}:=\\max\_\{s,a\}\(\\beta\_\{0\}\(s,a\)\+1\)\. Sincec⋆​\(s,a\),ctm​\(s,a\)∈\[0,1\]c^\{\\star\}\(s,a\),c\_\{t\_\{m\}\}\(s,a\)\\in\[0,1\], we obtain

\|c⋆​\(s,a\)d^tm​\(s,a\)−ctm​\(s,a\)d^tm​\(s,a\)\+\(β0​\(s,a\)\+1\)/tm\|≤2​ΔmPν\+bmaxν2​tm\.\\left\|\\frac\{c^\{\\star\}\(s,a\)\}\{\\widehat\{d\}\_\{t\_\{m\}\}\(s,a\)\}\-\\frac\{c\_\{t\_\{m\}\}\(s,a\)\}\{\\widehat\{d\}\_\{t\_\{m\}\}\(s,a\)\+\(\\beta\_\{0\}\(s,a\)\+1\)/t\_\{m\}\}\\right\|\\leq\\frac\{2\\Delta\_\{m\}^\{P\}\}\{\\nu\}\+\\frac\{b\_\{\\max\}\}\{\\nu^\{2\}t\_\{m\}\}\.The mapx↦xκx\\mapsto x^\{\\kappa\}isκ​ν−\(κ−1\)\\kappa\\nu^\{\-\(\\kappa\-1\)\}\-Lipschitz on\[0,ν−1\]\[0,\\nu^\{\-1\}\]\. Therefore,

‖∇Uκ​\(𝐝^tm\)−𝐰m‖∞≤2​κ​ν−κ​ΔmP\+κ​bmaxνκ\+1​tm\.\\left\\\|\\nabla U\_\{\\kappa\}\(\\widehat\{\\mathbf\{d\}\}\_\{t\_\{m\}\}\)\-\\mathbf\{w\}\_\{m\}\\right\\\|\_\{\\infty\}\\leq 2\\kappa\\nu^\{\-\\kappa\}\\Delta\_\{m\}^\{P\}\+\\frac\{\\kappa b\_\{\\max\}\}\{\\nu^\{\\kappa\+1\}t\_\{m\}\}\.\(19\)Combining this bound with the planning\-discrepancy bound yields, on the same event,

ϵm≤\(Cocc\+4​κ\)​ν−κ​S​Aδ⁡\(βmin\+ν​tm\+1\)\+2​κ​bmaxνκ\+1​tm\.\\epsilon\_\{m\}\\leq\{\}\(C\_\{\\rm occ\}\+4\\kappa\)\\nu^\{\-\\kappa\}S\\sqrt\{\\frac\{A\}\{\\delta\(\\beta\_\{\\min\}\+\\nu t\_\{m\}\+1\)\}\}\+\\frac\{2\\kappa b\_\{\\max\}\}\{\\nu^\{\\kappa\+1\}t\_\{m\}\}\.\(20\)Hence, the positive partϵm\+:=max⁡\{ϵm,0\}\\epsilon\_\{m\}^\{\+\}:=\\max\\\{\\epsilon\_\{m\},0\\\}isO\(tm−1/2\)O\(t\_\{m\}^\{\-1/2\}\)at each fixed episode and fixed posterior confidence, with all other parameters held constant\.

## Appendix EProof of Lemma[5](https://arxiv.org/html/2611.25160#Thmtheorem5)

###### Proof\.

Under the fixed\-kernel law, each transition row can be sampled from its own sequence of independent draws fromP⋆\(⋅∣s,a\)P^\{\\star\}\(\\cdot\\mid s,a\)\. Writep^n\(⋅∣s,a\)\\widehat\{p\}\_\{n\}\(\\cdot\\mid s,a\)for the empirical distribution of the firstnndraws for that row\. Coordinatewise Hoeffding bounds and a union bound over theS2​AS^\{2\}Acoordinates and1≤n≤T1\\leq n\\leq Tgive an event of probability at least1−δ/21\-\\delta/2on which

∥p^n\(⋅∣s,a\)−P⋆\(⋅∣s,a\)∥2≤S​qT​\(δ\)2​n\\bigl\\\|\\widehat\{p\}\_\{n\}\(\\cdot\\mid s,a\)\-P^\{\\star\}\(\\cdot\\mid s,a\)\\bigr\\\|\_\{2\}\\leq\\sqrt\{\\frac\{Sq\_\{T\}\(\\delta\)\}\{2n\}\}simultaneously for all rows and counts\. The bound therefore applies at the adaptive countn=NT​\(s,a\)n=N\_\{T\}\(s,a\)\.

By \([3](https://arxiv.org/html/2611.25160#S2.E3)\), the posterior mean mixesp^n\\widehat\{p\}\_\{n\}andμ0\\mu\_\{0\}with prior weightβ0​\(s,a\)/\(n\+β0​\(s,a\)\)\\beta\_\{0\}\(s,a\)/\(n\+\\beta\_\{0\}\(s,a\)\)\. Two probability vectors are at Euclidean distance at most2\\sqrt\{2\}\. Also, the difference in their squared norms is at most twice their Euclidean distance\. Consequently, on the same event and forn=NT​\(s,a\)\>0n=N\_\{T\}\(s,a\)\>0,

\|cT​\(s,a\)−c⋆​\(s,a\)\|≤2​S​qT​\(δ\)n\+2​2​β0​\(s,a\)n\.\|c\_\{T\}\(s,a\)\-c^\{\\star\}\(s,a\)\|\\leq\\sqrt\{\\frac\{2Sq\_\{T\}\(\\delta\)\}\{n\}\}\+\\frac\{2\\sqrt\{2\}\\,\\beta\_\{0\}\(s,a\)\}\{n\}\.WhenNT​\(s,a\)≥η​TN\_\{T\}\(s,a\)\\geq\\eta Tfor all\(s,a\)\(s,a\), dividing this inequality byNT​\(s,a\)\+β0​\(s,a\)\+1N\_\{T\}\(s,a\)\+\\beta\_\{0\}\(s,a\)\+1and taking the maximum gives

maxs,a⁡\|cT​\(s,a\)−c⋆​\(s,a\)\|NT​\(s,a\)\+β0​\(s,a\)\+1≤1η​T\+mins,a⁡β0​\(s,a\)\+1​\(2​S​qT​\(δ\)η​T\+2​2​βmaxη​T\)\.\\max\_\{s,a\}\\frac\{\|c\_\{T\}\(s,a\)\-c^\{\\star\}\(s,a\)\|\}\{N\_\{T\}\(s,a\)\+\\beta\_\{0\}\(s,a\)\+1\}\\leq\\frac\{1\}\{\\eta T\+\\min\_\{s,a\}\\beta\_\{0\}\(s,a\)\+1\}\\left\(\\sqrt\{\\frac\{2Sq\_\{T\}\(\\delta\)\}\{\\eta T\}\}\+\\frac\{2\\sqrt\{2\}\\,\\beta\_\{\\max\}\}\{\\eta T\}\\right\)\.∎

## Appendix FProof of Theorem[2](https://arxiv.org/html/2611.25160#Thmtheorem2)

Use the joint event from Section[5\.2](https://arxiv.org/html/2611.25160#S5.SS2)on whichd^T​\(s,a\)≥η\\widehat\{d\}\_\{T\}\(s,a\)\\geq\\etafor all\(s,a\)\(s,a\)andUκ​\(dκ⋆\)−Uκ​\(d^T\)≤εopt​\(T,δ\)U\_\{\\kappa\}\(d\_\{\\kappa\}^\{\\star\}\)\-U\_\{\\kappa\}\(\\widehat\{d\}\_\{T\}\)\\leq\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)\. Given its probability bound of1−δ/21\-\\delta/2, its intersection with the event in Lemma[5](https://arxiv.org/html/2611.25160#Thmtheorem5)has probability at least1−δ1\-\\delta\.

DefineF⁡\(𝐝\)=maxs,a⁡c⋆​\(s,a\)d⁡\(s,a\)F\(\\mathbf\{d\}\)=\\max\_\{s,a\}\\frac\{c^\{\\star\}\(s,a\)\}\{d\(s,a\)\}\. On this intersection, Lemma[5](https://arxiv.org/html/2611.25160#Thmtheorem5)giveMT≤F⁡\(d^T\)/T\+εpost​\(T,δ\)M\_\{T\}\\leq F\(\\widehat\{d\}\_\{T\}\)/T\+\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\)\. Forκ\>1\\kappa\>1, Proposition[3](https://arxiv.org/html/2611.25160#Thmtheorem3)then yields the sum of the utility bound and the posterior error,

MT≤η−1/κT​\[\(1−κ\)​Uκ​\(d^T\)\]1/κ\+εpost​\(T,δ\)\.M\_\{T\}\\leq\\frac\{\\eta^\{\-1/\\kappa\}\}\{T\}\\bigl\[\(1\-\\kappa\)U\_\{\\kappa\}\(\\widehat\{d\}\_\{T\}\)\\bigr\]^\{1/\\kappa\}\+\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\)\.\(21\)Multiplying the convergence gap inequality byκ−1\\kappa\-1and rearranging, we obtain

\(1−κ\)​Uκ​\(d^T\)\\displaystyle\(1\-\\kappa\)U\_\{\\kappa\}\(\\widehat\{d\}\_\{T\}\)≤\(1−κ\)​Uκ​\(dκ⋆\)\+\(κ−1\)​εopt​\(T,δ\)\\displaystyle\\leq\(1\-\\kappa\)U\_\{\\kappa\}\(d\_\{\\kappa\}^\{\\star\}\)\+\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)≤\(1−κ\)​Uκ​\(𝐝⋆\)\+\(κ−1\)​εopt​\(T,δ\)\\displaystyle\\leq\(1\-\\kappa\)U\_\{\\kappa\}\(\\mathbf\{d\}^\{\\star\}\)\+\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)≤\(C⋆\)κ\+\(κ−1\)​εopt​\(T,δ\)\.\\displaystyle\\leq\(C^\{\\star\}\)^\{\\kappa\}\+\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)\.The second inequality uses the optimality ofdκ⋆d\_\{\\kappa\}^\{\\star\}forUκU\_\{\\kappa\}and1−κ<01\-\\kappa<0\. The third uses the upper bound in Proposition[3](https://arxiv.org/html/2611.25160#Thmtheorem3)at𝐝⋆\\mathbf\{d\}^\{\\star\}\. Substituting this into \([21](https://arxiv.org/html/2611.25160#A6.E21)\) gives

MT≤η−1/κT​\[\(C⋆\)κ\+\(κ−1\)​εopt​\(T,δ\)\]1/κ\+εpost​\(T,δ\),M\_\{T\}\\leq\\frac\{\\eta^\{\-1/\\kappa\}\}\{T\}\\left\[\(C^\{\\star\}\)^\{\\kappa\}\+\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)\\right\]^\{1/\\kappa\}\+\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\),which is \([13](https://arxiv.org/html/2611.25160#S3.E13)\)\. Forκ=1\\kappa=1, the visit floor givesη​F​\(d^T\)≤∑s,ac⋆​\(s,a\)\\eta F\(\\widehat\{d\}\_\{T\}\)\\leq\\sum\_\{s,a\}c^\{\\star\}\(s,a\), and∑s,ac⋆​\(s,a\)≤F⁡\(𝐝⋆\)=C⋆\\sum\_\{s,a\}c^\{\\star\}\(s,a\)\\leq F\(\\mathbf\{d\}^\{\\star\}\)=C^\{\\star\}by averaging the ratios with weights𝐝⋆\\mathbf\{d\}^\{\\star\}\. Hence \([13](https://arxiv.org/html/2611.25160#S3.E13)\) also holds atκ=1\\kappa=1\.

WhenC⋆\>0C^\{\\star\}\>0, concavity ofx1/κx^\{1/\\kappa\}gives, forb≥0b\\geq 0,

\[\(C⋆\)κ\+b\]1/κ≤C⋆\+bκ​\(C⋆\)κ−1\.\\left\[\(C^\{\\star\}\)^\{\\kappa\}\+b\\right\]^\{1/\\kappa\}\\leq C^\{\\star\}\+\\frac\{b\}\{\\kappa\(C^\{\\star\}\)^\{\\kappa\-1\}\}\.Takingb=\(κ−1\)​εopt​\(T,δ\)b=\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)yields

MT\\displaystyle M\_\{T\}≤η−1/κC⋆T\+η−1/κ\(κ−1\)εopt\(T,δ\)κ​T​\(C⋆\)κ−1\+εpost​\(T,δ\)\\displaystyle\\leq\\frac\{\\eta^\{\-1/\\kappa\}C^\{\\star\}\}\{T\}\+\\frac\{\\eta^\{\-1/\\kappa\}\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)\}\{\\kappa T\(C^\{\\star\}\)^\{\\kappa\-1\}\}\+\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\)=C⋆T\+\(η−1/κ−1\)C⋆T\\displaystyle=\\frac\{C^\{\\star\}\}\{T\}\+\\frac\{\(\\eta^\{\-1/\\kappa\}\-1\)C^\{\\star\}\}\{T\}\+η−1/κ\(κ−1\)εopt\(T,δ\)κ​T​\(C⋆\)κ−1\+εpost​\(T,δ\),\\displaystyle\\quad\+\\frac\{\\eta^\{\-1/\\kappa\}\(\\kappa\-1\)\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)\}\{\\kappa T\(C^\{\\star\}\)^\{\\kappa\-1\}\}\+\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\),which gives the three error terms in \([12](https://arxiv.org/html/2611.25160#S3.E12)\)\.

For the rate form, write the convergence estimate from Section[5\.2](https://arxiv.org/html/2611.25160#S5.SS2)asεopt\(T,δ\)≤KδT−1/3\\varepsilon\_\{\\mathrm\{opt\}\}\(T,\\delta\)\\leq K\_\{\\delta\}T^\{\-1/3\}, whereKδK\_\{\\delta\}is independent ofTT\. Bounding the denominator in \([16](https://arxiv.org/html/2611.25160#S5.E16)\) below byη​T\\eta Tgives

εpost\(T,δ\)≤2​S​qT​\(δ\)η3T−3/2\+2​2​βmaxη2T−2\.\\varepsilon\_\{\\mathrm\{post\}\}\(T,\\delta\)\\leq\\sqrt\{\\frac\{2Sq\_\{T\}\(\\delta\)\}\{\\eta^\{3\}\}\}\\,T^\{\-3/2\}\+\\frac\{2\\sqrt\{2\}\\,\\beta\_\{\\max\}\}\{\\eta^\{2\}\}T^\{\-2\}\.Inserting these estimates in \([12](https://arxiv.org/html/2611.25160#S3.E12)\) gives, forC⋆\>0C^\{\\star\}\>0,

MT\\displaystyle M\_\{T\}≤C⋆T\+\(η−1/κ−1\)C⋆T\\displaystyle\\leq\\frac\{C^\{\\star\}\}\{T\}\+\\frac\{\(\\eta^\{\-1/\\kappa\}\-1\)C^\{\\star\}\}\{T\}\+η−1/κ\(κ−1\)Kδκ​\(C⋆\)κ−1T−4/3\+2​S​qT​\(δ\)η3T−3/2\+2​2​βmaxη2T−2\.\\displaystyle\\quad\+\\frac\{\\eta^\{\-1/\\kappa\}\(\\kappa\-1\)K\_\{\\delta\}\}\{\\kappa\(C^\{\\star\}\)^\{\\kappa\-1\}\}T^\{\-4/3\}\+\\sqrt\{\\frac\{2Sq\_\{T\}\(\\delta\)\}\{\\eta^\{3\}\}\}\\,T^\{\-3/2\}\+\\frac\{2\\sqrt\{2\}\\,\\beta\_\{\\max\}\}\{\\eta^\{2\}\}T^\{\-2\}\.

Similar Articles