Continuity-Free Near-Minimax Leading-Order Regret for CVaR-UCBVI

# Continuity-Free Near-Minimax Leading-Order Regret for CVaR-UCBVI
Source: [https://arxiv.org/html/2608.28960](https://arxiv.org/html/2608.28960)
###### Abstract\.

For finite\-horizon tabular CVaR reinforcement learning,[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)prove aO~​\(τ−1​S​A​K\)\\widetilde\{O\}\(\\tau^\{\-1\}\\sqrt\{SAK\}\)leading regret bound for arbitrary normalized return laws and the sharperO~​\(S​A​K/τ\)\\widetilde\{O\}\(\\sqrt\{SAK/\\tau\}\)rate under a density lower bound\. We show that the same Bernstein CVaR\-UCBVI algorithm attains the sharper rate without continuity assumptions\. The key is a selected\-budget self\-bound: the conditional variance of the episode shortfall is at mostτ\\tauplus the value\-estimation width\. Substitution into the original Bernstein decomposition yields, with high probability,O~​\(S​A​K/τ\+\(S​A​H​K1/4\+S2​A​H\)/τ\)\\widetilde\{O\}\(\\sqrt\{SAK/\\tau\}\+\(SAHK^\{1/4\}\+S^\{2\}AH\)/\\tau\)regret for arbitrary normalized return laws—atomic, mixed, or continuous\. Theτ−1/2\\tau^\{\-1/2\}leading term matches the expected\-regret minimax lower bound of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)up to logarithmic factors\. Thus Bernstein CVaR\-UCBVI is minimax\-optimal over the full return\-law class in the leading\-order regime; the lower\-order terms retain theirτ−1\\tau^\{\-1\}dependence\.

## 1\.Introduction

Conditional value\-at\-risk \(CVaR\) evaluates the lower tail of a return distribution and is a standard objective for risk\-sensitive reinforcement learning\. In finite\-horizon tabular Markov decision processes \(MDPs\) with normalized returns,[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)establish aS​A​K/τ\\sqrt\{SAK/\\tau\}expected\-regret lower bound on a balanced\-tree hard family and introduce CVaR\-UCBVI, an augmented\-state variant of UCBVI\[[1](https://arxiv.org/html/2608.28960#bib.bib1)\]\. Their general upper bound has leading termO~​\(τ−1​S​A​K\)\\widetilde\{O\}\(\\tau^\{\-1\}\\sqrt\{SAK\}\)\. Under their Assumption 5\.4, which requires every relevant return law to have a density uniformly bounded away from zero, the leading term improves toO~​\(S​A​K/τ\)\\widetilde\{O\}\(\\sqrt\{SAK/\\tau\}\)\. The paper explicitly leaves removal of this regularity assumption as an open problem\.

This note removes the continuity assumption from the analysis of Bernstein CVaR\-UCBVI\. The relevant term in Appendix G of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)is the cumulative conditional variance

∑k=1KVar⁡\(\(b^k−∑h=1Hrh,k\)\+\|ℱk\)\.\\sum\_\{k=1\}^\{K\}\\operatorname\{Var\}\\\!\\left\(\\left\(\\widehat\{b\}\_\{k\}\-\\sum\_\{h=1\}^\{H\}r\_\{h,k\}\\right\)^\{\+\}\\middle\|\\mathcal\{F\}\_\{k\}\\right\)\.For general return laws, their analysis bounds every summand by11; under Assumption 5\.4, it instead uses continuity to compareb^k\\widehat\{b\}\_\{k\}with a trueτ\\tau\-quantile\. Our argument shows that the*mean shortfall*atb^k\\widehat\{b\}\_\{k\}is at mostτ\\tauplus the value\-estimation width\. Since a\[0,1\]\[0,1\]\-valued random variable has variance at most its mean, the desired scaling follows without quantile identification\.

#### Contribution\.

We establish a selected\-budget self\-bound that controls each conditional shortfall variance byτ\\tauplus the value\-estimation width\. Combining this bound with the Bernstein regret decomposition of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)yields Theorem[4\.2](https://arxiv.org/html/2608.28960#S4.Thmtheorem2)for arbitrary normalized return laws, without modifying the algorithm or its confidence event\. The theorem covers atomic, mixed, and continuous return laws\. When the displayed lower\-order terms are negligible, its leading term matches the expected\-regret minimax lower bound of[Wang et al\. \[6, Corollary 3\.2\]](https://arxiv.org/html/2608.28960#bib.bib6)up to logarithmic factors, establishing leading\-order minimax optimality over the full normalized\-return class\.[AppendixA](https://arxiv.org/html/2608.28960#A1)restates the required auxiliary bounds in our notation\.

Table 1\.Leading square\-root\-in\-KKterm for Bernstein CVaR\-UCBVI\. Lower\-order terms and logarithms are omitted\.
### 1\.1\.Related work

[Bastani et al\. \[2\]](https://arxiv.org/html/2608.28960#bib.bib2)give regret guarantees for a broad class of static, trajectory\-level risk criteria\.[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)specialize to precommitted CVaR and obtain the bounds compared in[table1](https://arxiv.org/html/2608.28960#S1.T1)\.[Wang et al\. \[7\]](https://arxiv.org/html/2608.28960#bib.bib7)reduce optimized certainty equivalents to risk\-neutral RL; their sharp CVaR specialization still assumes continuously distributed returns with a density lower bound\[[7](https://arxiv.org/html/2608.28960#bib.bib7), Assumption D\.11 and Theorem D\.12\]\.[Ni et al\. \[4\]](https://arxiv.org/html/2608.28960#bib.bib4)study reward\-free exploration for CVaR, which is a different data\-collection protocol and a PAC rather than online\-regret objective\.[Liang and Luo \[3\]](https://arxiv.org/html/2608.28960#bib.bib3)analyze dynamic, recursively composed risk measures, which are time\-consistent but differ from the static CVaR of the full trajectory studied here\. This paper addresses the complementary question of removing the continuity condition from the regret analysis of Bernstein CVaR\-UCBVI for static trajectory\-level CVaR\.

## 2\.Problem setting and algorithm

### 2\.1\.Model and objective

Consider an episodic tabular MDP with state space𝒮\\mathcal\{S\}, action space𝒜\\mathcal\{A\}, sizesS=\|𝒮\|S=\|\\mathcal\{S\}\|andA=\|𝒜\|A=\|\\mathcal\{A\}\|, horizonHH, fixed initial states1s\_\{1\}, andKKepisodes\. The transition kernelP∗P^\{\*\}is unknown and the conditional reward laws are known, as in[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)\. Rewards are nonnegative\. Letℋh=\(st,at,rt\)t<h\\mathcal\{H\}\_\{h\}=\(s\_\{t\},a\_\{t\},r\_\{t\}\)\_\{t<h\}denote the history before stagehh\. Conditional on\(sh,ah\)\(s\_\{h\},a\_\{h\}\), the reward and next state are drawn independently as

rh∼R\(sh,ah\),sh\+1∼P∗\(⋅∣sh,ah\)\.r\_\{h\}\\sim R\(s\_\{h\},a\_\{h\}\),\\qquad s\_\{h\+1\}\\sim P^\{\*\}\(\\cdot\\mid s\_\{h\},a\_\{h\}\)\.The return of every history\-dependent policyπ\\piis almost surely normalized:

R⁡\(π\):=∑h=1Hrh∈\[0,1\]\.R\(\\pi\):=\\sum\_\{h=1\}^\{H\}r\_\{h\}\\in\[0,1\]\.Forτ∈\(0,1\]\\tau\\in\(0,1\], the lower\-tail CVaR of a random returnX∈\[0,1\]X\\in\[0,1\]has the representation\[[5](https://arxiv.org/html/2608.28960#bib.bib5)\]

\(2\.1\)CVaRτ⁡\(X\)=maxb∈\[0,1\]⁡\{b−τ−1​𝔼​\[\(b−X\)\+\]\}\.\\operatorname\{CVaR\}\_\{\\tau\}\(X\)=\\max\_\{b\\in\[0,1\]\}\\left\\\{b\-\\tau^\{\-1\}\\mathbb\{E\}\[\(b\-X\)^\{\+\}\]\\right\\\}\.LetCVaRτ∗=supπCVaRτ⁡\(R⁡\(π\)\)\\operatorname\{CVaR\}\_\{\\tau\}^\{\*\}=\\sup\_\{\\pi\}\\operatorname\{CVaR\}\_\{\\tau\}\(R\(\\pi\)\)\. A pair\(ρ,b\)\(\\rho,b\)induces the history\-dependent policy

πhρ,b​\(sh,ℋh\)=ρh​\(sh,b−∑t<hrt\)\.\\pi\_\{h\}^\{\\rho,b\}\(s\_\{h\},\\mathcal\{H\}\_\{h\}\)=\\rho\_\{h\}\\\!\\left\(s\_\{h\},b\-\\sum\_\{t<h\}r\_\{t\}\\right\)\.Write its return asR⁡\(ρ,b\)R\(\\rho,b\)\. The regret of the pairs\(ρ^k,b^k\)\(\\widehat\{\\rho\}\_\{k\},\\widehat\{b\}\_\{k\}\)selected by the algorithm is

\(2\.2\)RegretτRL⁡\(K\):=∑k=1K\[CVaRτ∗−CVaRτ⁡\(R⁡\(ρ^k,b^k\)\)\]\.\\operatorname\{Regret\}^\{\\mathrm\{RL\}\}\_\{\\tau\}\(K\):=\\sum\_\{k=1\}^\{K\}\\left\[\\operatorname\{CVaR\}\_\{\\tau\}^\{\*\}\-\\operatorname\{CVaR\}\_\{\\tau\}\\\!\\left\(R\(\\widehat\{\\rho\}\_\{k\},\\widehat\{b\}\_\{k\}\)\\right\)\\right\]\.
The augmented state is\(s,b\)\(s,b\)\. Its initial budget lies in\[0,1\]\[0,1\]and evolves asbh\+1=bh−rhb\_\{h\+1\}=b\_\{h\}\-r\_\{h\}; residual budgets can therefore be negative\. For an augmented policyρ\\rho, define its shortfall value at every reachable budget by

\(2\.3\)Vhρ\(s,b\):=𝔼ρ\[\(b−∑t=hHrt\)\+\|sh=s,bh=b\],VH\+1ρ\(s,b\)=b\+,V\_\{h\}^\{\\rho\}\(s,b\):=\\mathbb\{E\}\_\{\\rho\}\\\!\\left\[\\left\(b\-\\sum\_\{t=h\}^\{H\}r\_\{t\}\\right\)^\{\+\}\\middle\|s\_\{h\}=s,\\ b\_\{h\}=b\\right\],\\qquad V\_\{H\+1\}^\{\\rho\}\(s,b\)=b^\{\+\},and letVh∗​\(s,b\)=infρVhρ​\(s,b\)V\_\{h\}^\{\*\}\(s,b\)=\\inf\_\{\\rho\}V\_\{h\}^\{\\rho\}\(s,b\)\. The augmented\-state optimality identity of[Wang et al\. \[6, Theorem 5\.1\]](https://arxiv.org/html/2608.28960#bib.bib6)gives, for everyb∈\[0,1\]b\\in\[0,1\],

\(2\.4\)V1∗​\(s1,b\)=infπ​history\-dependent𝔼π​\[\(b−R⁡\(π\)\)\+\],CVaRτ∗=maxb∈\[0,1\]⁡\{b−τ−1​V1∗​\(s1,b\)\}\.V\_\{1\}^\{\*\}\(s\_\{1\},b\)=\\inf\_\{\\pi\\ \\text\{history\-dependent\}\}\\mathbb\{E\}\_\{\\pi\}\[\(b\-R\(\\pi\)\)^\{\+\}\],\\qquad\\operatorname\{CVaR\}\_\{\\tau\}^\{\*\}=\\max\_\{b\\in\[0,1\]\}\\\{b\-\\tau^\{\-1\}V\_\{1\}^\{\*\}\(s\_\{1\},b\)\\\}\.

### 2\.2\.Bernstein CVaR\-UCBVI

We summarize the exact\-budget version of Algorithm 2 of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)so that the quantities used below are defined within the note\. Letℱk\\mathcal\{F\}\_\{k\}be the complete history before episodekk, and define the pre\-episode counts and empirical transition vector by

Nk​\(s,a,s′\)\\displaystyle N\_\{k\}\(s,a,s^\{\\prime\}\):=∑i<k∑h=1H𝟏\{\(sh,i,ah,i,sh\+1,i\)=\(s,a,s′\)\},\\displaystyle:=\\sum\_\{i<k\}\\sum\_\{h=1\}^\{H\}\\mathbf\{1\}\\\{\(s\_\{h,i\},a\_\{h,i\},s\_\{h\+1,i\}\)=\(s,a,s^\{\\prime\}\)\\\},\(2\.5\)Nk​\(s,a\)\\displaystyle N\_\{k\}\(s,a\):=1∨∑s′Nk​\(s,a,s′\),\\displaystyle:=1\\vee\\sum\_\{s^\{\\prime\}\}N\_\{k\}\(s,a,s^\{\\prime\}\),P^k​\(s′∣s,a\)\\displaystyle\\widehat\{P\}\_\{k\}\(s^\{\\prime\}\\mid s,a\):=Nk​\(s,a,s′\)Nk​\(s,a\)\.\\displaystyle:=\\frac\{N\_\{k\}\(s,a,s^\{\\prime\}\)\}\{N\_\{k\}\(s,a\)\}\.SetV^H\+1,k↓​\(s,b\)=V^H\+1,k↑​\(s,b\)=b\+\\widehat\{V\}^\{\\downarrow\}\_\{H\+1,k\}\(s,b\)=\\widehat\{V\}^\{\\uparrow\}\_\{H\+1,k\}\(s,b\)=b^\{\+\}\. Forh=H,H−1,…,1h=H,H\-1,\\ldots,1, the algorithm applies the backward updates

U^h,k↓​\(s,b,a\)\\displaystyle\\widehat\{U\}^\{\\downarrow\}\_\{h,k\}\(s,b,a\):=∑s′P^k​\(s′∣s,a\)​𝔼r∼R⁡\(s,a\)​\[V^h\+1,k↓​\(s′,b−r\)\]−BONh,kBERN​\(s,b,a\),\\displaystyle:=\{\}\\sum\_\{s^\{\\prime\}\}\\widehat\{P\}\_\{k\}\(s^\{\\prime\}\\mid s,a\)\\mathbb\{E\}\_\{r\\sim R\(s,a\)\}\[\\widehat\{V\}^\{\\downarrow\}\_\{h\+1,k\}\(s^\{\\prime\},b\-r\)\]\-\\operatorname\{BON\}^\{\\mathrm\{BERN\}\}\_\{h,k\}\(s,b,a\),ρ^h,k​\(s,b\)\\displaystyle\\widehat\{\\rho\}\_\{h,k\}\(s,b\)∈arg⁡mina∈𝒜​U^h,k↓​\(s,b,a\),\\displaystyle\\in\\arg\\min\_\{a\\in\\mathcal\{A\}\}\\widehat\{U\}^\{\\downarrow\}\_\{h,k\}\(s,b,a\),\(2\.6\)V^h,k↓​\(s,b\)\\displaystyle\\widehat\{V\}^\{\\downarrow\}\_\{h,k\}\(s,b\):=max⁡\{U^h,k↓​\(s,b,ρ^h,k​\(s,b\)\),0\},\\displaystyle:=\\max\\\{\\widehat\{U\}^\{\\downarrow\}\_\{h,k\}\(s,b,\\widehat\{\\rho\}\_\{h,k\}\(s,b\)\),0\\\},U^h,k↑​\(s,b,a\)\\displaystyle\\widehat\{U\}^\{\\uparrow\}\_\{h,k\}\(s,b,a\):=∑s′P^k​\(s′∣s,a\)​𝔼r∼R⁡\(s,a\)​\[V^h\+1,k↑​\(s′,b−r\)\]\+BONh,kBERN​\(s,b,a\),\\displaystyle:=\{\}\\sum\_\{s^\{\\prime\}\}\\widehat\{P\}\_\{k\}\(s^\{\\prime\}\\mid s,a\)\\mathbb\{E\}\_\{r\\sim R\(s,a\)\}\[\\widehat\{V\}^\{\\uparrow\}\_\{h\+1,k\}\(s^\{\\prime\},b\-r\)\]\+\\operatorname\{BON\}^\{\\mathrm\{BERN\}\}\_\{h,k\}\(s,b,a\),\(2\.7\)V^h,k↑​\(s,b\)\\displaystyle\\widehat\{V\}^\{\\uparrow\}\_\{h,k\}\(s,b\):=min⁡\{U^h,k↑​\(s,b,ρ^h,k​\(s,b\)\),1\}\.\\displaystyle:=\\min\\\{\\widehat\{U\}^\{\\uparrow\}\_\{h,k\}\(s,b,\\widehat\{\\rho\}\_\{h,k\}\(s,b\)\),1\\\}\.The recursion is evaluated on all reachable residual budgets, with a fixed measurable rule for resolving ties\. The Bernstein bonus is given explicitly in[equationA\.1](https://arxiv.org/html/2608.28960#A1.E1)\. After the backward pass, the algorithm selects

\(2\.8\)b^k∈arg⁡maxb∈\[0,1\]​f^k​\(b\),f^k​\(b\):=b−τ−1​V^1,k↓​\(s1,b\)\.\\widehat\{b\}\_\{k\}\\in\\arg\\max\_\{b\\in\[0,1\]\}\\widehat\{f\}\_\{k\}\(b\),\\qquad\\widehat\{f\}\_\{k\}\(b\):=b\-\\tau^\{\-1\}\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},b\)\.As in the exact\-budget formulation of[Wang et al\. \[6, Algorithm 2\]](https://arxiv.org/html/2608.28960#bib.bib6), we use an exact\-optimization oracle: we assume that[equation2\.8](https://arxiv.org/html/2608.28960#S2.E8)admits anℱk\\mathcal\{F\}\_\{k\}\-measurable maximizer and fix one such selector\. Attainment is automatic for the finite\-grid implementation in[corollary4\.3](https://arxiv.org/html/2608.28960#S4.Thmtheorem3)\. All quantities in[equations2\.5](https://arxiv.org/html/2608.28960#S2.E5)and[2\.8](https://arxiv.org/html/2608.28960#S2.E8)are thenℱk\\mathcal\{F\}\_\{k\}\-measurable\. The episode starts fromb1,k=b^kb\_\{1,k\}=\\widehat\{b\}\_\{k\}and, forh=1,…,Hh=1,\\ldots,H, follows

ah,k\\displaystyle a\_\{h,k\}=ρ^h,k​\(sh,k,bh,k\),\\displaystyle=\\widehat\{\\rho\}\_\{h,k\}\(s\_\{h,k\},b\_\{h,k\}\),rh,k\\displaystyle r\_\{h,k\}∼R⁡\(sh,k,ah,k\),\\displaystyle\\sim R\(s\_\{h,k\},a\_\{h,k\}\),sh\+1,k\\displaystyle s\_\{h\+1,k\}∼P∗\(⋅∣sh,k,ah,k\),\\displaystyle\\sim P^\{\*\}\(\\cdot\\mid s\_\{h,k\},a\_\{h,k\}\),bh\+1,k\\displaystyle b\_\{h\+1,k\}=bh,k−rh,k\.\\displaystyle=b\_\{h,k\}\-r\_\{h,k\}\.Thus the algorithm interacts only with the original MDP while maintaining the scalar residual budget\. Expectations or variances indexed by\(ρ,b\)\(\\rho,b\)refer to this true\-MDP rollout starting from\(s1,b\)\(s\_\{1\},b\)\.

### 2\.3\.Auxiliary regret decomposition

Define

\(2\.9\)Yk\\displaystyle Y\_\{k\}:=\(b^k−∑h=1Hrh,k\)\+,\\displaystyle:=\\left\(\\widehat\{b\}\_\{k\}\-\\sum\_\{h=1\}^\{H\}r\_\{h,k\}\\right\)^\{\+\},Wk\\displaystyle W\_\{k\}:=V1ρ^k​\(s1,b^k\)−V^1,k↓​\(s1,b^k\),\\displaystyle:=V\_\{1\}^\{\\widehat\{\\rho\}\_\{k\}\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\-\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\),\(2\.10\)QK\\displaystyle Q\_\{K\}:=∑k=1KVar⁡\(Yk∣ℱk\)\.\\displaystyle:=\\sum\_\{k=1\}^\{K\}\\operatorname\{Var\}\(Y\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\)\.In particular,

\(2\.11\)𝔼⁡\[Yk∣ℱk\]=V1ρ^k​\(s1,b^k\)\.\\mathbb\{E\}\[Y\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=V\_\{1\}^\{\\widehat\{\\rho\}\_\{k\}\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\.
For later use, letξk\\xi\_\{k\}denote the transition correction associated with the Bernstein bonus\. Its formula and the bonus formula are recorded in[appendixA](https://arxiv.org/html/2608.28960#A1)\. For each realized stage, set

gh,k​\(s′\):=𝔼r∼R⁡\(sh,k,ah,k\)​Vh\+1ρ^k​\(s′,bh,k−r\)\.g\_\{h,k\}\(s^\{\\prime\}\):=\\mathbb\{E\}\_\{r\\sim R\(s\_\{h,k\},a\_\{h,k\}\)\}V\_\{h\+1\}^\{\\widehat\{\\rho\}\_\{k\}\}\(s^\{\\prime\},b\_\{h,k\}\-r\)\.Define

\(2\.12\)Bk\\displaystyle B\_\{k\}:=∑h=1H𝔼ρ^k,b^k​\[2​BONh,kBERN​\(sh,bh,ah\)\+ξk​\(sh,ah\)\|ℱk\],\\displaystyle:=\\sum\_\{h=1\}^\{H\}\\mathbb\{E\}\_\{\\widehat\{\\rho\}\_\{k\},\\widehat\{b\}\_\{k\}\}\\\!\\left\[2\\operatorname\{BON\}^\{\\mathrm\{BERN\}\}\_\{h,k\}\(s\_\{h\},b\_\{h\},a\_\{h\}\)\+\\xi\_\{k\}\(s\_\{h\},a\_\{h\}\)\\middle\|\\mathcal\{F\}\_\{k\}\\right\],\(2\.13\)𝔇K\\displaystyle\\mathfrak\{D\}\_\{K\}:=∑k=1K∑h=1HVars′∼P∗\(⋅∣sh,k,ah,k\)\(gh,k\(s′\)\)Nk​\(sh,k,ah,k\)\.\\displaystyle:=\\sum\_\{k=1\}^\{K\}\\sum\_\{h=1\}^\{H\}\\sqrt\{\\frac\{\\operatorname\{Var\}\_\{s^\{\\prime\}\\sim P^\{\*\}\(\\cdot\\mid s\_\{h,k\},a\_\{h,k\}\)\}\\\!\\left\(g\_\{h,k\}\(s^\{\\prime\}\)\\right\)\}\{N\_\{k\}\(s\_\{h,k\},a\_\{h,k\}\)\}\}\.Each variance in[equation2\.13](https://arxiv.org/html/2608.28960#S2.E13)is over a fresh next\-state draw after the realized trajectory variables have been substituted\. Thus𝔇K\\mathfrak\{D\}\_\{K\}is trajectory\-random; no conditioning onℱk\\mathcal\{F\}\_\{k\}is intended inside these one\-step variances\. Set

ℓδ:=log⁡\(H​S​A​K/δ\),L:=1∨ℓδ\.\\ell\_\{\\delta\}:=\\log\(HSAK/\\delta\),\\qquad L:=1\\vee\\ell\_\{\\delta\}\.The algorithm usesℓδ\\ell\_\{\\delta\}in its bonus; replacing it by the largerLLbelow only enlarges the published upper bounds\.

###### Proposition 2\.1\(Auxiliary bounds from[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)\)\.

For the estimates generated by[equations2\.6](https://arxiv.org/html/2608.28960#S2.E6)and[2\.7](https://arxiv.org/html/2608.28960#S2.E7)with the bonus in[equationA\.1](https://arxiv.org/html/2608.28960#A1.E1), the following bounds hold on a common event with probability at least1−δ1\-\\delta\. In particular,[equation2\.14](https://arxiv.org/html/2608.28960#S2.E14)holds for everyh,kh,kand uniformly over its state and budget arguments, while[equation2\.15](https://arxiv.org/html/2608.28960#S2.E15)holds for every episodekk:

\(2\.14\)0≤V^h,k↓​\(s,b\)\\displaystyle 0\\leq\\widehat\{V\}^\{\\downarrow\}\_\{h,k\}\(s,b\)≤Vh∗​\(s,b\),\\displaystyle\\leq V\_\{h\}^\{\*\}\(s,b\),\(2\.15\)0≤Wk\\displaystyle 0\\leq W\_\{k\}≤e​Bk,\\displaystyle\\leq\\mathrm\{e\}B\_\{k\},\(2\.16\)∑k=1KBk\\displaystyle\\sum\_\{k=1\}^\{K\}B\_\{k\}≤6​H​L\+12​S​A​H​K​L\+6​S2​A​H​L2,\\displaystyle\\leq 6HL\+12\\sqrt\{SAHKL\}\+6S^\{2\}AHL^\{2\},\(2\.17\)𝔇K\\displaystyle\\mathfrak\{D\}\_\{K\}≤S​A​L​\(2​H​L\+2​QK\),\\displaystyle\\leq\\sqrt\{SAL\(2HL\+2Q\_\{K\}\)\},\(2\.18\)RegretτRL⁡\(K\)\\displaystyle\\operatorname\{Regret\}^\{\\mathrm\{RL\}\}\_\{\\tau\}\(K\)≤6​e​τ−1​L​𝔇K\+54​e​τ−1​S​A​H​K1/4​L2\+74​e​τ−1​S2​A​H​L3\.\\displaystyle\\leq 6\\mathrm\{e\}\\,\\tau^\{\-1\}\\sqrt\{L\}\\,\\mathfrak\{D\}\_\{K\}\+54\\mathrm\{e\}\\,\\tau^\{\-1\}SAHK^\{1/4\}L^\{2\}\+74\\mathrm\{e\}\\,\\tau^\{\-1\}S^\{2\}AHL^\{3\}\.

Proposition[2\.1](https://arxiv.org/html/2608.28960#S2.Thmtheorem1)follows from Appendix G of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6);[appendixA](https://arxiv.org/html/2608.28960#A1)restates the relevant derivation in our notation\. Uniformity overbbpermits evaluation at the data\-dependent budgetb^k\\widehat\{b\}\_\{k\}\. The remainder of the proof uses the analysis only through the inequalities in Proposition[2\.1](https://arxiv.org/html/2608.28960#S2.Thmtheorem1)\.

## 3\.A self\-bounding shortfall

The main new estimate is the following lemma\.

###### Lemma 3\.1\(Selected\-budget self\-bound\)\.

On the event in Proposition[2\.1](https://arxiv.org/html/2608.28960#S2.Thmtheorem1), for every episodekk,

\(3\.1\)V^1,k↓​\(s1,b^k\)≤τ​b^k≤τ,Var⁡\(Yk∣ℱk\)≤𝔼⁡\[Yk∣ℱk\]≤τ\+Wk\.\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\\leq\\tau\\widehat\{b\}\_\{k\}\\leq\\tau,\\qquad\\operatorname\{Var\}\(Y\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\)\\leq\\mathbb\{E\}\[Y\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]\\leq\\tau\+W\_\{k\}\.

###### Proof\.

Nonnegative rewards implyV1∗\(s1,0\)=infρ𝔼ρ\[\(−∑hrh\)\+\]=0V\_\{1\}^\{\*\}\(s\_\{1\},0\)=\\inf\_\{\\rho\}\\mathbb\{E\}\_\{\\rho\}\[\(\-\\sum\_\{h\}r\_\{h\}\)^\{\+\}\]=0\. Pessimism and clipping therefore give

0≤V^1,k↓​\(s1,0\)≤V1∗​\(s1,0\)=0,0\\leq\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},0\)\\leq V\_\{1\}^\{\*\}\(s\_\{1\},0\)=0,sof^k​\(0\)=0\\widehat\{f\}\_\{k\}\(0\)=0\. Because00is feasible in[equation2\.8](https://arxiv.org/html/2608.28960#S2.E8), optimality ofb^k\\widehat\{b\}\_\{k\}yields

0≤f^k​\(b^k\)=b^k−τ−1​V^1,k↓​\(s1,b^k\)\.0\\leq\\widehat\{f\}\_\{k\}\(\\widehat\{b\}\_\{k\}\)=\\widehat\{b\}\_\{k\}\-\\tau^\{\-1\}\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\.ThusV^1,k↓​\(s1,b^k\)≤τ​b^k≤τ\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\\leq\\tau\\widehat\{b\}\_\{k\}\\leq\\tau\.

Next,0≤Yk≤b^k≤10\\leq Y\_\{k\}\\leq\\widehat\{b\}\_\{k\}\\leq 1, henceYk2≤YkY\_\{k\}^\{2\}\\leq Y\_\{k\}and

Var⁡\(Yk∣ℱk\)≤𝔼⁡\[Yk2∣ℱk\]≤𝔼⁡\[Yk∣ℱk\]\.\\operatorname\{Var\}\(Y\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\)\\leq\\mathbb\{E\}\[Y\_\{k\}^\{2\}\\mid\\mathcal\{F\}\_\{k\}\]\\leq\\mathbb\{E\}\[Y\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]\.Finally, by[equations2\.11](https://arxiv.org/html/2608.28960#S2.E11)and[2\.9](https://arxiv.org/html/2608.28960#S2.E9),

𝔼⁡\[Yk∣ℱk\]=V^1,k↓​\(s1,b^k\)\+Wk≤τ\+Wk\.\\mathbb\{E\}\[Y\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\+W\_\{k\}\\leq\\tau\+W\_\{k\}\.AlsoWk≥0W\_\{k\}\\geq 0becauseV^1,k↓≤V1∗≤V1ρ^k\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\\leq V\_\{1\}^\{\*\}\\leq V\_\{1\}^\{\\widehat\{\\rho\}\_\{k\}\}\. ∎

The lemma controls a lower partial moment rather than a CDF value\. An atom at the selected threshold may makePr⁡\(∑hrh,k≤b^k∣ℱk\)\\Pr\(\\sum\_\{h\}r\_\{h,k\}\\leq\\widehat\{b\}\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\)large, but its mass at equality contributes zero to\(b^k−∑hrh,k\)\+\(\\widehat\{b\}\_\{k\}\-\\sum\_\{h\}r\_\{h,k\}\)^\{\+\}\. This is why no quantile identification or anti\-concentration is needed\.

###### Example 3\.2\(An atomic Bernoulli return law\)\.

LetH=1H=1,R∈\{0,1\}R\\in\\\{0,1\\\}, andPr⁡\(R=0\)=τ\\Pr\(R=0\)=\\tau\. This law has no Lebesgue density, and its population CVaR objective is

b−τ−1​𝔼​\[\(b−R\)\+\]=b−τ−1​\(τ​b\)=0\(b∈\[0,1\]\)\.b\-\\tau^\{\-1\}\\mathbb\{E\}\[\(b\-R\)^\{\+\}\]=b\-\\tau^\{\-1\}\(\\tau b\)=0\\qquad\(b\\in\[0,1\]\)\.The maximizing budget is therefore non\-unique, so an argument based on a unique selected quantile is unavailable\. Nevertheless, at the extreme choiceb=1b=1,Y=\(1−R\)\+=𝟏\{R=0\}Y=\(1\-R\)^\{\+\}=\\mathbf\{1\}\\\{R=0\\\}andVar⁡\(Y\)=τ⁡\(1−τ\)≤τ\\operatorname\{Var\}\(Y\)=\\tau\(1\-\\tau\)\\leq\\tau\. Thus the self\-bound remains valid despite the non\-unique maximizing budget\.

## 4\.Regret analysis

The self\-bound yields the following distribution\-free control of cumulative trajectory variance\.

###### Proposition 4\.1\(Cumulative trajectory variance\)\.

On the event in Proposition[2\.1](https://arxiv.org/html/2608.28960#S2.Thmtheorem1),

\(4\.1\)QK≤K​τ\+e⁡\(6​H​L\+12​S​A​H​K​L\+6​S2​A​H​L2\)\.Q\_\{K\}\\leq K\\tau\+\\mathrm\{e\}\\left\(6HL\+12\\sqrt\{SAHKL\}\+6S^\{2\}AHL^\{2\}\\right\)\.

###### Proof\.

By the definition ofQKQ\_\{K\}in[equation2\.10](https://arxiv.org/html/2608.28960#S2.E10)and the episodewise bound in[equation3\.1](https://arxiv.org/html/2608.28960#S3.E1),

QK=∑k=1KVar⁡\(Yk∣ℱk\)≤∑k=1K\(τ\+Wk\)=K​τ\+∑k=1KWk\.Q\_\{K\}=\\sum\_\{k=1\}^\{K\}\\operatorname\{Var\}\(Y\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\)\\leq\\sum\_\{k=1\}^\{K\}\(\\tau\+W\_\{k\}\)=K\\tau\+\\sum\_\{k=1\}^\{K\}W\_\{k\}\.On the same event,[equation2\.15](https://arxiv.org/html/2608.28960#S2.E15)givesWk≤e​BkW\_\{k\}\\leq\\mathrm\{e\}B\_\{k\}episodewise, and[equation2\.16](https://arxiv.org/html/2608.28960#S2.E16)controls the cumulative bonuses\. Hence,

QK≤K​τ\+e​∑k=1KBk≤K​τ\+e⁡\(6​H​L\+12​S​A​H​K​L\+6​S2​A​H​L2\),Q\_\{K\}\\leq K\\tau\+\\mathrm\{e\}\\sum\_\{k=1\}^\{K\}B\_\{k\}\\leq K\\tau\+\\mathrm\{e\}\\left\(6HL\+12\\sqrt\{SAHKL\}\+6S^\{2\}AHL^\{2\}\\right\),which proves[equation4\.1](https://arxiv.org/html/2608.28960#S4.E1)\. ∎

###### Theorem 4\.2\(Continuity\-free leading\-order regret\)\.

Fixτ∈\(0,1\]\\tau\\in\(0,1\]andδ∈\(0,1\)\\delta\\in\(0,1\)\. Under the tabular, known\-reward, nonnegative, normalized\-return model of[section2](https://arxiv.org/html/2608.28960#S2), run the exact\-budget version of Algorithm 2 of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)with its Bernstein bonus\. With probability at least1−δ1\-\\delta, without Assumption 5\.4 of that paper,

\(4\.2\)RegretτRL⁡\(K\)≤25​L​S​A​Kτ\+300τ​S​A​H​K1/4​L2\+400τ​S2​A​H​L3\.\\operatorname\{Regret\}^\{\\mathrm\{RL\}\}\_\{\\tau\}\(K\)\\leq 25L\\sqrt\{\\frac\{SAK\}\{\\tau\}\}\+\\frac\{300\}\{\\tau\}SAHK^\{1/4\}L^\{2\}\+\\frac\{400\}\{\\tau\}S^\{2\}AHL^\{3\}\.Consequently,

\(4\.3\)RegretτRL⁡\(K\)=O~​\(S​A​Kτ\+S​A​H​K1/4\+S2​A​Hτ\)\\operatorname\{Regret\}^\{\\mathrm\{RL\}\}\_\{\\tau\}\(K\)=\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\frac\{SAK\}\{\\tau\}\}\+\\frac\{SAHK^\{1/4\}\+S^\{2\}AH\}\{\\tau\}\\right\)for every MDP satisfying the stated model, regardless of whether its induced return laws are discrete, mixed, or continuous\.

###### Proof\.

Substitute[equation4\.1](https://arxiv.org/html/2608.28960#S4.E1)into[equation2\.17](https://arxiv.org/html/2608.28960#S2.E17):

𝔇K2≤S​A​L​\(CLOSE\\displaystyle\\mathfrak\{D\}\_\{K\}^\{2\}\\leq SAL\\bigl\(OPEN2​K​τ\+\(2\+12​e\)​H​L\+24​e​S​A​H​K​L\+12​e​S2​A​H​L2\)\.\\displaystyle 2K\\tau\+\(2\+12\\mathrm\{e\}\)HL\+24\\mathrm\{e\}\\sqrt\{SAHKL\}\+12\\mathrm\{e\}S^\{2\}AHL^\{2\}\\bigr\)\.Usingx1\+⋯\+xm≤∑ixi\\sqrt\{x\_\{1\}\+\\cdots\+x\_\{m\}\}\\leq\\sum\_\{i\}\\sqrt\{x\_\{i\}\}ande<2\.72\\mathrm\{e\}<2\.72gives

𝔇K≤\\displaystyle\\mathfrak\{D\}\_\{K\}\\leq\{\}2​τ​S​A​K​L\+35​S​A​H​L\+66​\(S​A\)3/4​H1/4​K1/4​L3/4\\displaystyle\\sqrt\{2\\tau SAKL\}\+\\sqrt\{35SAH\}\\,L\+\\sqrt\{66\}\(SA\)^\{3/4\}H^\{1/4\}K^\{1/4\}L^\{3/4\}\(4\.4\)\+33​S3/2​A​H1/2​L3/2\.\\displaystyle\+\\sqrt\{33\}S^\{3/2\}AH^\{1/2\}L^\{3/2\}\.Insert[equation4\.4](https://arxiv.org/html/2608.28960#S4.E4)into[equation2\.18](https://arxiv.org/html/2608.28960#S2.E18)\. The first term is at most

6​e​τ−1​L​2​τ​S​A​K​L≤25​L​S​A​K/τ\.6\\mathrm\{e\}\\,\\tau^\{\-1\}\\sqrt\{L\}\\sqrt\{2\\tau SAKL\}\\leq 25L\\sqrt\{SAK/\\tau\}\.SinceS,A,H,L≥1S,A,H,L\\geq 1, the third term in[equation4\.4](https://arxiv.org/html/2608.28960#S4.E4)is at most140​τ−1​S​A​H​K1/4​L2140\\tau^\{\-1\}SAHK^\{1/4\}L^\{2\}; together with the existing54​e≤14954\\mathrm\{e\}\\leq 149coefficient, it is bounded by the second term of[equation4\.2](https://arxiv.org/html/2608.28960#S4.E2)\. The second and fourth terms in[equation4\.4](https://arxiv.org/html/2608.28960#S4.E4)contribute at most103​τ−1​S2​A​H​L3103\\tau^\{\-1\}S^\{2\}AHL^\{3\}and95​τ−1​S2​A​H​L395\\tau^\{\-1\}S^\{2\}AHL^\{3\}, respectively\. Adding the remaining74​e≤20274\\mathrm\{e\}\\leq 202coefficient gives at most\(103\+95\+202\)​τ−1​S2​A​H​L3=400​τ−1​S2​A​H​L3\(103\+95\+202\)\\tau^\{\-1\}S^\{2\}AHL^\{3\}=400\\tau^\{\-1\}S^\{2\}AHL^\{3\}\. This proves[equation4\.2](https://arxiv.org/html/2608.28960#S4.E2);[equation4\.3](https://arxiv.org/html/2608.28960#S4.E3)follows\. ∎

###### Corollary 4\.3\(Discretized implementation\)\.

For an integerm≥2m\\geq 2, setη:=m−1\\eta:=m^\{\-1\}and let

ϕη​\(r\):=min⁡\{1,η⁡⌈r/η⌉\},ℬη:=\{j​η:0≤j≤m\}\.\\phi\_\{\\eta\}\(r\):=\\min\\\{1,\\eta\\lceil r/\\eta\\rceil\\\},\\qquad\\mathcal\{B\}\_\{\\eta\}:=\\\{j\\eta:0\\leq j\\leq m\\\}\.Implement Algorithm 2 by replacing every reward withϕη​\(r\)\\phi\_\{\\eta\}\(r\), evaluating its backward recursion on the finite residual\-budget set reachable fromℬη\\mathcal\{B\}\_\{\\eta\}under the rounded rewards, and selecting

\(4\.5\)b^k∈arg⁡maxb∈ℬη​f^k​\(b\)\.\\widehat\{b\}\_\{k\}\\in\\arg\\max\_\{b\\in\\mathcal\{B\}\_\{\\eta\}\}\\widehat\{f\}\_\{k\}\(b\)\.Under the assumptions of[theorem4\.2](https://arxiv.org/html/2608.28960#S4.Thmtheorem2), the regret of the resulting sequence of policies in the original MDP is bounded by the right\-hand side of[equation4\.2](https://arxiv.org/html/2608.28960#S4.E2)plus

K​H​ητ\.\\frac\{KH\\eta\}\{\\tau\}\.For any requested mesh widthη¯∈\(0,1\)\\bar\{\\eta\}\\in\(0,1\), takingm=⌈η¯−1⌉m=\\lceil\\bar\{\\eta\}^\{\-1\}\\rceilgivesη≤η¯\\eta\\leq\\bar\{\\eta\}\. No continuity assumption is needed for either the original or discretized return law\.

###### Proof\.

WriteMη=disc⁡\(M\)M\_\{\\eta\}=\\operatorname\{disc\}\(M\)and, for a nonnegative random variableXX, define the budget\-restricted functional

CVaRτ\[0,1\]⁡\(X\):=maxb∈\[0,1\]⁡\{b−τ−1​𝔼​\[\(b−X\)\+\]\}\.\\operatorname\{CVaR\}\_\{\\tau\}^\{\[0,1\]\}\(X\):=\\max\_\{b\\in\[0,1\]\}\\left\\\{b\-\\tau^\{\-1\}\\mathbb\{E\}\[\(b\-X\)^\{\+\}\]\\right\\\}\.It agrees with ordinary CVaR whenX∈\[0,1\]X\\in\[0,1\]\. In this proof, model subscripts distinguish returns and optimal shortfall values inMMandMηM\_\{\\eta\}\.

The rounded return inMηM\_\{\\eta\}can be as large as1\+H​η1\+H\\eta, soMηM\_\{\\eta\}need not satisfy the normalization assumption of[theorem4\.2](https://arxiv.org/html/2608.28960#S4.Thmtheorem2)\. Nevertheless, the proof of that theorem applies without change toCVaRτ\[0,1\]\\operatorname\{CVaR\}\_\{\\tau\}^\{\[0,1\]\}: rewards remain nonnegative and the initial budget remains in\[0,1\]\[0,1\], so every shortfall and shortfall value used in the pessimism, simulation, concentration, and variance arguments remains in\[0,1\]\[0,1\]\. Normalization is used only to identify the restricted functional with ordinary CVaR\. The augmented optimality identity also remains valid inMηM\_\{\\eta\}, because it is a dynamic\-programming identity for the shortfall objective and does not require normalized total returns\.

Let

Cη∗\\displaystyle C\_\{\\eta\}^\{\*\}:=supb∈\[0,1\]\{b−τ−1​V1,η∗​\(s1,b\)\},\\displaystyle:=\\sup\_\{b\\in\[0,1\]\}\\\{b\-\\tau^\{\-1\}V\_\{1,\\eta\}^\{\*\}\(s\_\{1\},b\)\\\},Cηℬ\\displaystyle C\_\{\\eta\}^\{\\mathcal\{B\}\}:=maxb∈ℬη⁡\{b−τ−1​V1,η∗​\(s1,b\)\},\\displaystyle:=\\max\_\{b\\in\\mathcal\{B\}\_\{\\eta\}\}\\\{b\-\\tau^\{\-1\}V\_\{1,\\eta\}^\{\*\}\(s\_\{1\},b\)\\\},Cη,k\\displaystyle C\_\{\\eta,k\}:=CVaRτ\[0,1\]⁡\(RMη​\(ρ^k,b^k\)\)\.\\displaystyle:=\\operatorname\{CVaR\}\_\{\\tau\}^\{\[0,1\]\}\\bigl\(R\_\{M\_\{\\eta\}\}\(\\widehat\{\\rho\}\_\{k\},\\widehat\{b\}\_\{k\}\)\\bigr\)\.The proof of[theorem4\.2](https://arxiv.org/html/2608.28960#S4.Thmtheorem2)also applies with the grid benchmarkCηℬC\_\{\\eta\}^\{\\mathcal\{B\}\}\. Indeed, letbη∗b\_\{\\eta\}^\{\*\}maximize that benchmark and set

Wη,k:=V1,ηρ^k​\(s1,b^k\)−V^1,k↓​\(s1,b^k\)\.W\_\{\\eta,k\}:=V\_\{1,\\eta\}^\{\\widehat\{\\rho\}\_\{k\}\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\-\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\.Heref^k\\widehat\{f\}\_\{k\},V^1,k↓\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}, andV1,ηρ^kV\_\{1,\\eta\}^\{\\widehat\{\\rho\}\_\{k\}\}are all computed in the rounded MDP\. Pessimism, optimality in[equation4\.5](https://arxiv.org/html/2608.28960#S4.E5), and evaluation of the restricted CVaR objective atb^k\\widehat\{b\}\_\{k\}give

Cηℬ\\displaystyle C\_\{\\eta\}^\{\\mathcal\{B\}\}≤bη∗−τ−1​V^1,k↓​\(s1,bη∗\)≤b^k−τ−1​V^1,k↓​\(s1,b^k\),\\displaystyle\\leq b\_\{\\eta\}^\{\*\}\-\\tau^\{\-1\}\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},b\_\{\\eta\}^\{\*\}\)\\leq\\widehat\{b\}\_\{k\}\-\\tau^\{\-1\}\\widehat\{V\}^\{\\downarrow\}\_\{1,k\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\),Cη,k\\displaystyle C\_\{\\eta,k\}≥b^k−τ−1​V1,ηρ^k​\(s1,b^k\)\.\\displaystyle\\geq\\widehat\{b\}\_\{k\}\-\\tau^\{\-1\}V\_\{1,\\eta\}^\{\\widehat\{\\rho\}\_\{k\}\}\(s\_\{1\},\\widehat\{b\}\_\{k\}\)\.Consequently,Cηℬ−Cη,k≤τ−1​Wη,kC\_\{\\eta\}^\{\\mathcal\{B\}\}\-C\_\{\\eta,k\}\\leq\\tau^\{\-1\}W\_\{\\eta,k\}\. The grid contains00, so the selected\-budget self\-bound remains valid; all subsequent simulation, bonus, concentration, and variance steps are unchanged\. Hence

∑k=1K\(Cηℬ−Cη,k\)\\sum\_\{k=1\}^\{K\}\(C\_\{\\eta\}^\{\\mathcal\{B\}\}\-C\_\{\\eta,k\}\)is bounded by the right\-hand side of[equation4\.2](https://arxiv.org/html/2608.28960#S4.E2)\.

It remains to compare the grid and continuum benchmarks\. For a fixed history\-dependent policyπ\\pi, writeXπ=RMη​\(π\)X\_\{\\pi\}=R\_\{M\_\{\\eta\}\}\(\\pi\)and

fπ​\(b\):=b−τ−1​𝔼​\[\(b−Xπ\)\+\]\.f\_\{\\pi\}\(b\):=b\-\\tau^\{\-1\}\\mathbb\{E\}\[\(b\-X\_\{\\pi\}\)^\{\+\}\]\.Every rounded stage reward belongs toℬη\\mathcal\{B\}\_\{\\eta\}\. Therefore every possible value ofXπX\_\{\\pi\}that lies in\[0,1\]\[0,1\]also belongs toℬη\\mathcal\{B\}\_\{\\eta\}: it is either11or an integer multiple ofη\\eta\. Thusfπf\_\{\\pi\}is concave and piecewise linear on\[0,1\]\[0,1\], with all breakpoints and both endpoints inℬη\\mathcal\{B\}\_\{\\eta\}, and so

maxb∈\[0,1\]⁡fπ​\(b\)=maxb∈ℬη⁡fπ​\(b\)\.\\max\_\{b\\in\[0,1\]\}f\_\{\\pi\}\(b\)=\\max\_\{b\\in\\mathcal\{B\}\_\{\\eta\}\}f\_\{\\pi\}\(b\)\.The history\-dependent policy class in the augmented optimality identity does not depend onbb\. Consequently,

Cη∗\\displaystyle C\_\{\\eta\}^\{\*\}=supb∈\[0,1\]supπfπ​\(b\)=supπmaxb∈\[0,1\]⁡fπ​\(b\)\\displaystyle=\\sup\_\{b\\in\[0,1\]\}\\sup\_\{\\pi\}f\_\{\\pi\}\(b\)=\\sup\_\{\\pi\}\\max\_\{b\\in\[0,1\]\}f\_\{\\pi\}\(b\)\(4\.6\)=supπmaxb∈ℬη⁡fπ​\(b\)=max⁡supπb∈ℬη⁡fπ​\(b\)=Cηℬ\.\\displaystyle=\\sup\_\{\\pi\}\\max\_\{b\\in\\mathcal\{B\}\_\{\\eta\}\}f\_\{\\pi\}\(b\)=\\max\_\{b\\in\\mathcal\{B\}\_\{\\eta\}\}\\sup\_\{\\pi\}f\_\{\\pi\}\(b\)=C\_\{\\eta\}^\{\\mathcal\{B\}\}\.
The adapted policy actually executed inMMis

πh,kη​\(sh,ℋh\):=ρ^h,k​\(sh,b^k−∑t<hϕη​\(rt\)\)\.\\pi\_\{h,k\}^\{\\eta\}\(s\_\{h\},\\mathcal\{H\}\_\{h\}\):=\\widehat\{\\rho\}\_\{h,k\}\\\!\\left\(s\_\{h\},\\widehat\{b\}\_\{k\}\-\\sum\_\{t<h\}\\phi\_\{\\eta\}\(r\_\{t\}\)\\right\)\.Thus its residual budget is updated with rounded rewards\. Theorem H\.4 of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)gives

V1,η∗​\(s1,b\)≤V1,M∗​\(s1,b\)\(b∈\[0,1\]\),V\_\{1,\\eta\}^\{\*\}\(s\_\{1\},b\)\\leq V\_\{1,M\}^\{\*\}\(s\_\{1\},b\)\\quad\(b\\in\[0,1\]\),and henceCη∗≥CVaRτ∗⁡\(M\)C\_\{\\eta\}^\{\*\}\\geq\\operatorname\{CVaR\}\_\{\\tau\}^\{\*\}\(M\)\. Theorem H\.3 of that paper gives

CVaRτ⁡\(RM​\(πkη\)\)≥CVaRτ⁡\(RMη​\(ρ^k,b^k\)\)−H​ητ≥Cη,k−H​ητ,\\operatorname\{CVaR\}\_\{\\tau\}\\bigl\(R\_\{M\}\(\\pi\_\{k\}^\{\\eta\}\)\\bigr\)\\geq\\operatorname\{CVaR\}\_\{\\tau\}\\bigl\(R\_\{M\_\{\\eta\}\}\(\\widehat\{\\rho\}\_\{k\},\\widehat\{b\}\_\{k\}\)\\bigr\)\-\\frac\{H\\eta\}\{\\tau\}\\geq C\_\{\\eta,k\}\-\\frac\{H\\eta\}\{\\tau\},where the last inequality uses that full CVaR dominates its\[0,1\]\[0,1\]\-restricted counterpart\. Consequently, episodewise,

CVaRτ∗⁡\(M\)−CVaRτ⁡\(RM​\(πkη\)\)≤Cηℬ−Cη,k\+H​ητ,\\operatorname\{CVaR\}\_\{\\tau\}^\{\*\}\(M\)\-\\operatorname\{CVaR\}\_\{\\tau\}\\bigl\(R\_\{M\}\(\\pi\_\{k\}^\{\\eta\}\)\\bigr\)\\leq C\_\{\\eta\}^\{\\mathcal\{B\}\}\-C\_\{\\eta,k\}\+\\frac\{H\\eta\}\{\\tau\},where[equation4\.6](https://arxiv.org/html/2608.28960#S4.E6)was used\. Summing overkkproves the claim\. Thus Theorem H\.4 supplies the benchmark comparison, whereas Theorem H\.3 supplies the selected\-policy comparison\. ∎

## 5\.Discussion

Theorem[4\.2](https://arxiv.org/html/2608.28960#S4.Thmtheorem2)gives Bernstein CVaR\-UCBVI aτ−1/2\\tau^\{\-1/2\}leading dependence for arbitrary normalized return laws\. This term has the sameτ\\tau\- andKK\-dependence as the expected\-regret minimax lower bound of[Wang et al\. \[6, Corollary 3\.2\]](https://arxiv.org/html/2608.28960#bib.bib6)on its atomic balanced\-tree family, up to logarithmic factors\. Ignoring logarithms, the leading term dominates the two remaining terms when

K≳S2​A2​H4τ2andK≳S3​A​H2τ\.K\\gtrsim\\frac\{S^\{2\}A^\{2\}H^\{4\}\}\{\\tau^\{2\}\}\\qquad\\text\{and\}\\qquad K\\gtrsim\\frac\{S^\{3\}AH^\{2\}\}\{\\tau\}\.Ifτ\\taudecreases withKK, theτ−1\\tau^\{\-1\}lower\-order terms may continue to dominate; thus[theorem4\.2](https://arxiv.org/html/2608.28960#S4.Thmtheorem2)does not establish uniform finite\-sample optimality over all joint parameter regimes\.

The result applies to tabular MDPs with known reward laws, unknown transitions, nonnegative normalized returns, and static CVaR of the full trajectory\. Corollary[4\.3](https://arxiv.org/html/2608.28960#S4.Thmtheorem3)covers the grid\-based implementation of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6), but does not alter its computational complexity\.

###### Proposition 5\.1\(CVaR specialization of the OCE reduction\)\.

Consider Algorithm 1 of[Wang et al\. \[7\]](https://arxiv.org/html/2608.28960#bib.bib7), specialized to CVaR and to nonnegative normalized returns\. Letℱk\\mathcal\{F\}\_\{k\}contain the information available immediately before episodekkis executed, and writeV^k​\(b\):=V^1,k​\(s1,b\)\\widehat\{V\}\_\{k\}\(b\):=\\widehat\{V\}\_\{1,k\}\(s\_\{1\},b\)for the oracle’s optimistic initial value\. The algorithm selects

b^k∈arg⁡maxb∈\[0,1\]​\{b\+V^k​\(b\)\}\\widehat\{b\}\_\{k\}\\in\\arg\\max\_\{b\\in\[0,1\]\}\\\{b\+\\widehat\{V\}\_\{k\}\(b\)\\\}and an augmented policyπk\\pi^\{k\}\. These choices areℱk\\mathcal\{F\}\_\{k\}\-measurable\. LetZ⁡\(πk,b^k\)Z\(\\pi^\{k\},\\widehat\{b\}\_\{k\}\)denote a fresh return induced by the selected pair, and letZk:=∑h=1Hrh,k∈\[0,1\]Z\_\{k\}:=\\sum\_\{h=1\}^\{H\}r\_\{h,k\}\\in\[0,1\]be the realized return; conditionally onℱk\\mathcal\{F\}\_\{k\}, these variables have the same law\. SetYkOCE=\(b^k−Zk\)\+Y\_\{k\}^\{\\mathrm\{OCE\}\}=\(\\widehat\{b\}\_\{k\}\-Z\_\{k\}\)^\{\+\}and define

RegretCVaRτ⁡\(K\):=∑k=1K\[CVaRτ∗−CVaRτ⁡\(Z⁡\(πk,b^k\)\)\]\.\\operatorname\{Regret\}\_\{\\mathrm\{CVaR\}\_\{\\tau\}\}\(K\):=\\sum\_\{k=1\}^\{K\}\\left\[\\operatorname\{CVaR\}\_\{\\tau\}^\{\*\}\-\\operatorname\{CVaR\}\_\{\\tau\}\\bigl\(Z\(\\pi^\{k\},\\widehat\{b\}\_\{k\}\)\\bigr\)\\right\]\.Suppose the oracle satisfies Definition 3\.1 of[Wang et al\. \[7\]](https://arxiv.org/html/2608.28960#bib.bib7)with exact optimism,

V^k​\(b\)≥Vaug∗​\(s1,b\)\(b∈\[0,1\]\),\\widehat\{V\}\_\{k\}\(b\)\\geq V\_\{\\mathrm\{aug\}\}^\{\*\}\(s\_\{1\},b\)\\qquad\(b\\in\[0,1\]\),whereVaug∗V\_\{\\mathrm\{aug\}\}^\{\*\}is the optimal value in the CVaR augmented MDP, and also satisfies Assumption D\.10 of that paper in the form

RegretOpt⁡\(K\)≤C1​∑k=1KVar⁡\(YkOCE∣ℱk\)\+C2\.\\operatorname\{Regret\}\_\{\\mathrm\{Opt\}\}\(K\)\\leq\\sqrt\{C\_\{1\}\\sum\_\{k=1\}^\{K\}\\operatorname\{Var\}\(Y\_\{k\}^\{\\mathrm\{OCE\}\}\\mid\\mathcal\{F\}\_\{k\}\)\}\+C\_\{2\}\.Then Assumption D\.11 is unnecessary, and

\(5\.1\)RegretCVaRτ⁡\(K\)≤2​C1​Kτ\+C1\+2​C2τ\.\\operatorname\{Regret\}\_\{\\mathrm\{CVaR\}\_\{\\tau\}\}\(K\)\\leq 2\\sqrt\{\\frac\{C\_\{1\}K\}\{\\tau\}\}\+\\frac\{C\_\{1\}\+2C\_\{2\}\}\{\\tau\}\.

The proof is given in[appendixB](https://arxiv.org/html/2608.28960#A2)\. Proposition[5\.1](https://arxiv.org/html/2608.28960#S5.Thmtheorem1)concerns only the CVaR specialization; it does not assert an analogous self\-bound for every OCE utility\. In model classes with a matching CVaR lower bound, itsτ−1/2\\tau^\{\-1/2\}leading dependence is minimax\-optimal for atomic, mixed, and continuous normalized return laws\. The other oracle assumptions of[Wang et al\. \[7\]](https://arxiv.org/html/2608.28960#bib.bib7)remain unchanged\.

In summary, direct mean\-shortfall control gives the continuity\-free leading termO~​\(S​A​K/τ\)\\widetilde\{O\}\(\\sqrt\{SAK/\\tau\}\)\. It applies to atomic, mixed, and continuous normalized return laws and matches the expected\-regret minimax lower bound up to logarithmic factors\. The lower\-order terms retain theirτ−1\\tau^\{\-1\}dependence\.

## Appendix ADerivation of the auxiliary regret bounds

For completeness, this appendix restates the ingredients from Appendix G of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)in the notation used here and records the locations in their paper\. These bounds lead to Proposition[2\.1](https://arxiv.org/html/2608.28960#S2.Thmtheorem1); the selected\-budget argument enters subsequently through Lemma[3\.1](https://arxiv.org/html/2608.28960#S3.Thmtheorem1)\.

### A\.1\.Bernstein bonus and transition correction

LetP^k\(⋅∣s,a\)\\widehat\{P\}\_\{k\}\(\\cdot\\mid s,a\)be the empirical transition law based on theNk​\(s,a\)N\_\{k\}\(s,a\)pre\-episode visits\. Withℓδ=log⁡\(H​S​A​K/δ\)\\ell\_\{\\delta\}=\\log\(HSAK/\\delta\)andb′=b−rb^\{\\prime\}=b\-r, write

𝔼^k,s,a​\[g\]:=𝔼s′∼P^k​\(s,a\)r∼R⁡\(s,a\)​\[g⁡\(s′,r\)\]\.\\widehat\{\\mathbb\{E\}\}\_\{k,s,a\}\[g\]:=\\mathbb\{E\}\_\{\\begin\{subarray\}\{c\}s^\{\\prime\}\\sim\\widehat\{P\}\_\{k\}\(s,a\)\\\\ r\\sim R\(s,a\)\\end\{subarray\}\}\[g\(s^\{\\prime\},r\)\]\.Equation \(6\) of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)defines

BONh,kBERN⁡\(s,b,a\):=\\displaystyle\\operatorname\{BON\}^\{\\mathrm\{BERN\}\}\_\{h,k\}\(s,b,a\):=\{\}2​ℓδNk​\(s,a\)​Vars′∼P^k​\(s,a\)⁡\(𝔼r∼R⁡\(s,a\)​V^h\+1,k↓​\(s′,b−r\)\)\\displaystyle\\sqrt\{\\frac\{2\\ell\_\{\\delta\}\}\{N\_\{k\}\(s,a\)\}\\operatorname\{Var\}\_\{s^\{\\prime\}\\sim\\widehat\{P\}\_\{k\}\(s,a\)\}\\\!\\left\(\\mathbb\{E\}\_\{r\\sim R\(s,a\)\}\\widehat\{V\}^\{\\downarrow\}\_\{h\+1,k\}\(s^\{\\prime\},b\-r\)\\right\)\}\(A\.1\)\+2​ℓδNk​\(s,a\)​𝔼^k,s,a​\[\(V^h\+1,k↑​\(s′,b′\)−V^h\+1,k↓​\(s′,b′\)\)2\]\+ℓδNk​\(s,a\)\.\\displaystyle\+\\sqrt\{\\frac\{2\\ell\_\{\\delta\}\}\{N\_\{k\}\(s,a\)\}\\widehat\{\\mathbb\{E\}\}\_\{k,s,a\}\\\!\\left\[\\left\(\\widehat\{V\}^\{\\uparrow\}\_\{h\+1,k\}\(s^\{\\prime\},b^\{\\prime\}\)\-\\widehat\{V\}^\{\\downarrow\}\_\{h\+1,k\}\(s^\{\\prime\},b^\{\\prime\}\)\\right\)^\{2\}\\right\]\}\+\\frac\{\\ell\_\{\\delta\}\}\{N\_\{k\}\(s,a\)\}\.Lemma G\.2 introduces the transition correction

\(A\.2\)ξk​\(s,a\):=min⁡\{1,2​H​S​ℓδNk​\(s,a\)\}\.\\xi\_\{k\}\(s,a\):=\\min\\\!\\left\\\{1,\\frac\{2HS\\ell\_\{\\delta\}\}\{N\_\{k\}\(s,a\)\}\\right\\\}\.The confidence event constructed in Appendix G\.1 is uniform overb∈\[0,1\]b\\in\[0,1\]\. On this event, Theorem G\.7 establishes the required pessimism invariant, while Lemma G\.4 givesWk≤e​BkW\_\{k\}\\leq\\mathrm\{e\}B\_\{k\}\. These results yield[equations2\.14](https://arxiv.org/html/2608.28960#S2.E14)and[2\.15](https://arxiv.org/html/2608.28960#S2.E15)\.

### A\.2\.Cumulative width bound

Write

Gh,k:=2​BONh,kBERN​\(sh,k,bh,k,ah,k\)\+ξk​\(sh,k,ah,k\)\.G\_\{h,k\}:=2\\operatorname\{BON\}^\{\\mathrm\{BERN\}\}\_\{h,k\}\(s\_\{h,k\},b\_\{h,k\},a\_\{h,k\}\)\+\\xi\_\{k\}\(s\_\{h,k\},a\_\{h,k\}\)\.The first Azuma\-type bound in Appendix G\.1, labeled*Azuma 1*there and summed overhh, gives

∑k=1KBk≤6​H​ℓδ\+2​∑h=1H∑k=1KGh,k\.\\sum\_\{k=1\}^\{K\}B\_\{k\}\\leq 6H\\ell\_\{\\delta\}\+2\\sum\_\{h=1\}^\{H\}\\sum\_\{k=1\}^\{K\}G\_\{h,k\}\.Equation \(15\) of that appendix gives the variance\-independent estimate

∑h=1H∑k=1KGh,k≤6​S​A​H​K​ℓδ\+3​S2​A​H​ℓδ2\.\\sum\_\{h=1\}^\{H\}\\sum\_\{k=1\}^\{K\}G\_\{h,k\}\\leq 6\\sqrt\{SAHK\\ell\_\{\\delta\}\}\+3S^\{2\}AH\\ell\_\{\\delta\}^\{2\}\.UsingL≥ℓδL\\geq\\ell\_\{\\delta\}proves[equation2\.16](https://arxiv.org/html/2608.28960#S2.E16)\. Because this estimate does not use the empirical\-variance terms, it controls∑kWk\\sum\_\{k\}W\_\{k\}independently of the variance bound in the next subsection\.

### A\.3\.Population variance and regret decomposition

Equation \(19\) of[Wang et al\. \[6\]](https://arxiv.org/html/2608.28960#bib.bib6)corresponds to the term𝔇K\\mathfrak\{D\}\_\{K\}defined in[equation2\.13](https://arxiv.org/html/2608.28960#S2.E13)\. Cauchy–Schwarz and the elliptical\-potential count bound contribute the factorS​A​LSAL\. The paper’s*Azuma 4*bound and the fact that joint variance dominates the variance of a conditional mean then yield

𝔇K≤S​A​L​\(2​H​L\+2​∑k=1KVarρ^k,b^k⁡\(\(b^k−∑h=1Hrh\)\+\|ℱk\)\)\.\\mathfrak\{D\}\_\{K\}\\leq\\sqrt\{SAL\\\!\\left\(2HL\+2\\sum\_\{k=1\}^\{K\}\\operatorname\{Var\}\_\{\\widehat\{\\rho\}\_\{k\},\\widehat\{b\}\_\{k\}\}\\\!\\left\(\\left\(\\widehat\{b\}\_\{k\}\-\\sum\_\{h=1\}^\{H\}r\_\{h\}\\right\)^\{\+\}\\middle\|\\mathcal\{F\}\_\{k\}\\right\)\\right\)\}\.Lemma G\.9 identifies the inner trajectory variance by the law of total variance; this is[equation2\.17](https://arxiv.org/html/2608.28960#S2.E17)\.

Finally, the display immediately before the paper’s two alternative bounds on Eq\. \(19\) collects the correction term, empirical\-to\-population switching cost, and all1/Nk1/N\_\{k\}terms into the bound

27​S​A​H​K1/4​L2\+34​S2​A​H​L3\+3​L​𝔇K\.27SAHK^\{1/4\}L^\{2\}\+34S^\{2\}AHL^\{3\}\+3\\sqrt\{L\}\\,\\mathfrak\{D\}\_\{K\}\.The regret decomposition following Eq\. \(13\) in the proof of Theorem 5\.2 of[Wang et al\. \[6, Appendix G\.3, pp\. 29–30\]](https://arxiv.org/html/2608.28960#bib.bib6)gives, episodewise,

CVaRτ∗−CVaRτ⁡\(R⁡\(ρ^k,b^k\)\)≤τ−1​Wk\.\\operatorname\{CVaR\}\_\{\\tau\}^\{\*\}\-\\operatorname\{CVaR\}\_\{\\tau\}\\\!\\left\(R\(\\widehat\{\\rho\}\_\{k\},\\widehat\{b\}\_\{k\}\)\\right\)\\leq\\tau^\{\-1\}W\_\{k\}\.It follows from pessimism, optimality of the selected budget, and evaluation of the selected\-policy CVaR objective atb^k\\widehat\{b\}\_\{k\}\. Summing this inequality and combining the preceding display with Lemma G\.4 and*Azuma 1*gives

RegretτRL⁡\(K\)≤\\displaystyle\\operatorname\{Regret\}^\{\\mathrm\{RL\}\}\_\{\\tau\}\(K\)\\leq\{\}6​e​τ−1​H​L\+2​e​τ−1​\(27​S​A​H​K1/4​L2\+34​S2​A​H​L3\+3​L​𝔇K\)\\displaystyle 6\\mathrm\{e\}\\,\\tau^\{\-1\}HL\+2\\mathrm\{e\}\\,\\tau^\{\-1\}\\\!\\left\(27SAHK^\{1/4\}L^\{2\}\+34S^\{2\}AHL^\{3\}\+3\\sqrt\{L\}\\,\\mathfrak\{D\}\_\{K\}\\right\)≤\\displaystyle\\leq\{\}6​e​τ−1​L​𝔇K\+54​e​τ−1​S​A​H​K1/4​L2\+74​e​τ−1​S2​A​H​L3,\\displaystyle 6\\mathrm\{e\}\\,\\tau^\{\-1\}\\sqrt\{L\}\\,\\mathfrak\{D\}\_\{K\}\+54\\mathrm\{e\}\\,\\tau^\{\-1\}SAHK^\{1/4\}L^\{2\}\+74\\mathrm\{e\}\\,\\tau^\{\-1\}S^\{2\}AHL^\{3\},where the last inequality uses6​H​L≤6​S2​A​H​L36HL\\leq 6S^\{2\}AHL^\{3\}forS,A,L≥1S,A,L\\geq 1\. This proves[equation2\.18](https://arxiv.org/html/2608.28960#S2.E18)\. We retain the slightly looser coefficient74​e74\\mathrm\{e\}, rather than the70​e70\\mathrm\{e\}displayed by[Wang et al\. \[6, Appendix G\.4, p\. 34\]](https://arxiv.org/html/2608.28960#bib.bib6), so that the absorption is valid uniformly for allS,A,L≥1S,A,L\\geq 1; the coefficient70​e70\\mathrm\{e\}would requireS2​A​L2≥3S^\{2\}AL^\{2\}\\geq 3\. None of these steps invokes Assumption 5\.4\. In the original proof, that assumption enters only when the second bound on Eq\. \(19\) controls the trajectory\-variance sum in Eq\. \(20\)\. The selected\-budget self\-bound in[section3](https://arxiv.org/html/2608.28960#S3)controls the same sum without the assumption\.

## Appendix BProof of the OCE\-reduction extension

###### Proof of Proposition[5\.1](https://arxiv.org/html/2608.28960#S5.Thmtheorem1)\.

LetVkπk​\(b\)V\_\{k\}^\{\\pi^\{k\}\}\(b\)denote the initial value of the selected augmented policy\. For the CVaR utility

uτ​\(x\):=min⁡\{x/τ,0\},u\_\{\\tau\}\(x\):=\\min\\\{x/\\tau,0\\\},its value at the selected budget is

Vkπk​\(b^k\)=𝔼⁡\[uτ​\(Zk−b^k\)∣ℱk\]=−τ−1​𝔼​\[YkOCE∣ℱk\]\.V\_\{k\}^\{\\pi^\{k\}\}\(\\widehat\{b\}\_\{k\}\)=\\mathbb\{E\}\[u\_\{\\tau\}\(Z\_\{k\}\-\\widehat\{b\}\_\{k\}\)\\mid\\mathcal\{F\}\_\{k\}\]=\-\\tau^\{\-1\}\\mathbb\{E\}\[Y\_\{k\}^\{\\mathrm\{OCE\}\}\\mid\\mathcal\{F\}\_\{k\}\]\.Set

Δk:=V^k​\(b^k\)−Vkπk​\(b^k\)\.\\Delta\_\{k\}:=\\widehat\{V\}\_\{k\}\(\\widehat\{b\}\_\{k\}\)\-V\_\{k\}^\{\\pi^\{k\}\}\(\\widehat\{b\}\_\{k\}\)\.At budget00, nonnegative returns giveVaug∗​\(s1,0\)=0V\_\{\\mathrm\{aug\}\}^\{\*\}\(s\_\{1\},0\)=0\. Exact optimism and the stated budget rule therefore imply

b^k\+V^k​\(b^k\)≥V^k​\(0\)≥0\.\\widehat\{b\}\_\{k\}\+\\widehat\{V\}\_\{k\}\(\\widehat\{b\}\_\{k\}\)\\geq\\widehat\{V\}\_\{k\}\(0\)\\geq 0\.Only comparison with the feasible budget00is used here\. Since0≤b^k≤10\\leq\\widehat\{b\}\_\{k\}\\leq 1,

𝔼⁡\[YkOCE∣ℱk\]=τ⁡\(Δk−V^k​\(b^k\)\)≤τ⁡\(1\+Δk\)\.\\mathbb\{E\}\[Y\_\{k\}^\{\\mathrm\{OCE\}\}\\mid\\mathcal\{F\}\_\{k\}\]=\\tau\\bigl\(\\Delta\_\{k\}\-\\widehat\{V\}\_\{k\}\(\\widehat\{b\}\_\{k\}\)\\bigr\)\\leq\\tau\(1\+\\Delta\_\{k\}\)\.Moreover0≤YkOCE≤10\\leq Y\_\{k\}^\{\\mathrm\{OCE\}\}\\leq 1, so its conditional variance is at most its conditional mean\. The bounded\-regret condition in Definition 3\.1 of[Wang et al\. \[7\]](https://arxiv.org/html/2608.28960#bib.bib7), withVumax=τ−1V\_\{u\}^\{\\max\}=\\tau^\{\-1\}, gives∑kΔk≤τ−1​RegretOpt⁡\(K\)\\sum\_\{k\}\\Delta\_\{k\}\\leq\\tau^\{\-1\}\\operatorname\{Regret\}\_\{\\mathrm\{Opt\}\}\(K\)\. Consequently,

\(B\.1\)∑k=1KVar⁡\(YkOCE∣ℱk\)≤K​τ\+RegretOpt⁡\(K\)\.\\sum\_\{k=1\}^\{K\}\\operatorname\{Var\}\(Y\_\{k\}^\{\\mathrm\{OCE\}\}\\mid\\mathcal\{F\}\_\{k\}\)\\leq K\\tau\+\\operatorname\{Regret\}\_\{\\mathrm\{Opt\}\}\(K\)\.
WritingR=RegretOpt⁡\(K\)R=\\operatorname\{Regret\}\_\{\\mathrm\{Opt\}\}\(K\), Assumption D\.10 and[equationB\.1](https://arxiv.org/html/2608.28960#A2.E1)yield

R≤C1​\(K​τ\+R\)\+C2≤C1​K​τ\+R\+C12\+C2\.R\\leq\\sqrt\{C\_\{1\}\(K\\tau\+R\)\}\+C\_\{2\}\\leq\\sqrt\{C\_\{1\}K\\tau\}\+\\frac\{R\+C\_\{1\}\}\{2\}\+C\_\{2\}\.ThusR≤2​C1​K​τ\+C1\+2​C2R\\leq 2\\sqrt\{C\_\{1\}K\\tau\}\+C\_\{1\}\+2C\_\{2\}\. Under exact optimism, the optimism\-slack term in Theorem 3\.2 of[Wang et al\. \[7\]](https://arxiv.org/html/2608.28960#bib.bib7)vanishes\. SinceVumax=τ−1V\_\{u\}^\{\\max\}=\\tau^\{\-1\}for CVaR, that theorem givesRegretCVaRτ⁡\(K\)≤τ−1​R\\operatorname\{Regret\}\_\{\\mathrm\{CVaR\}\_\{\\tau\}\}\(K\)\\leq\\tau^\{\-1\}R, which is[equation5\.1](https://arxiv.org/html/2608.28960#S5.E1)\. ∎

## References

- \[1\]M\. G\. Azar, I\. Osband, and R\. Munos\(2017\)Minimax regret bounds for reinforcement learning\.InProceedings of the 34th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.70,pp\. 263–272\.External Links:[Link](https://proceedings.mlr.press/v70/azar17a.html)Cited by:[§1](https://arxiv.org/html/2608.28960#S1.p1.1)\.
- \[2\]O\. Bastani, Y\. Ma, E\. Shen, and W\. Xu\(2022\)Regret bounds for risk\-sensitive reinforcement learning\.InAdvances in Neural Information Processing Systems,Vol\.35\.Cited by:[§1\.1](https://arxiv.org/html/2608.28960#S1.SS1.p1.1)\.
- \[3\]H\. Liang and Z\. Luo\(2024\)Regret bounds for risk\-sensitive reinforcement learning with lipschitz dynamic risk measures\.InProceedings of the 27th International Conference on Artificial Intelligence and Statistics,Proceedings of Machine Learning Research, Vol\.238,pp\. 1774–1782\.External Links:[Link](https://proceedings.mlr.press/v238/liang24a.html)Cited by:[§1\.1](https://arxiv.org/html/2608.28960#S1.SS1.p1.1)\.
- \[4\]X\. Ni, G\. Liu, and L\. Lai\(2024\)Risk\-sensitive reward\-free reinforcement learning with CVaR\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 37999–38017\.External Links:[Link](https://proceedings.mlr.press/v235/ni24c.html)Cited by:[§1\.1](https://arxiv.org/html/2608.28960#S1.SS1.p1.1)\.
- \[5\]R\. T\. Rockafellar and S\. Uryasev\(2000\)Optimization of conditional value\-at\-risk\.Journal of Risk2\(3\),pp\. 21–41\.External Links:[Document](https://dx.doi.org/10.21314/JOR.2000.038)Cited by:[§2\.1](https://arxiv.org/html/2608.28960#S2.SS1.p1.3)\.
- \[6\]K\. Wang, N\. Kallus, and W\. Sun\(2023\)Near\-minimax\-optimal risk\-sensitive reinforcement learning with CVaR\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 35864–35907\.External Links:[Link](https://proceedings.mlr.press/v202/wang23m.html)Cited by:[§A\.1](https://arxiv.org/html/2608.28960#A1.SS1.p1.2),[§A\.3](https://arxiv.org/html/2608.28960#A1.SS3.p1.1),[§A\.3](https://arxiv.org/html/2608.28960#A1.SS3.p2.2),[§A\.3](https://arxiv.org/html/2608.28960#A1.SS3.p2.4),[Appendix A](https://arxiv.org/html/2608.28960#A1.p1.1),[§1](https://arxiv.org/html/2608.28960#S1.SS0.SSS0.Px1.p1.1),[§1\.1](https://arxiv.org/html/2608.28960#S1.SS1.p1.1),[Table 1](https://arxiv.org/html/2608.28960#S1.T1.2.2.1),[Table 1](https://arxiv.org/html/2608.28960#S1.T1.2.3.1),[§1](https://arxiv.org/html/2608.28960#S1.p1.1),[§1](https://arxiv.org/html/2608.28960#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.28960#S2.SS1.p1.1),[§2\.1](https://arxiv.org/html/2608.28960#S2.SS1.p2.2),[§2\.2](https://arxiv.org/html/2608.28960#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2608.28960#S2.SS2.p1.4),[§2\.3](https://arxiv.org/html/2608.28960#S2.SS3.p3.1),[Proposition 2\.1](https://arxiv.org/html/2608.28960#S2.Thmtheorem1),[Theorem 4\.2](https://arxiv.org/html/2608.28960#S4.Thmtheorem2.p1.1.1),[§4](https://arxiv.org/html/2608.28960#S4.p8.2.1),[§5](https://arxiv.org/html/2608.28960#S5.p1.1),[§5](https://arxiv.org/html/2608.28960#S5.p2.1),[Abstract\.](https://arxiv.org/html/2608.28960#abstract1.1)\.
- \[7\]K\. Wang, D\. Liang, N\. Kallus, and W\. Sun\(2025\)A reductions approach to risk\-sensitive reinforcement learning with optimized certainty equivalents\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 63636–63661\.External Links:[Link](https://proceedings.mlr.press/v267/wang25bl.html)Cited by:[Appendix B](https://arxiv.org/html/2608.28960#A2.p1.6.1),[Appendix B](https://arxiv.org/html/2608.28960#A2.p2.2.1),[§1\.1](https://arxiv.org/html/2608.28960#S1.SS1.p1.1),[Proposition 5\.1](https://arxiv.org/html/2608.28960#S5.Thmtheorem1.p1.1.1),[Proposition 5\.1](https://arxiv.org/html/2608.28960#S5.Thmtheorem1.p1.3.1),[§5](https://arxiv.org/html/2608.28960#S5.p3.1)\.