betaFeedback

WorksComputer Science

Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes

Abstract

We study the worst-case, over priors, Bayesian conditional value-at-risk (CVaR) of cumulative pseudo-regret in time-homogeneous finite-horizon episodic Markov decision processes. A high-probability guarantee for UCBVI-BF yields a prior-predictive upper bound. A lower bound follows by a three-state MDP and applying a reverse-KL inequality. For a constant number of states, the bounds have the same polynomial dependence on horizon, actions, and episodes, with a logarithmic gap in the risk level.

Introduction

High-probability regret guarantees control the likelihood of rare, large losses, whereas Bayesian expected regret averages over all possible outcomes. Conditional value-at-risk (CVaR) complements these criteria by measuring the average regret in the worst 1−α1-\alpha fraction of the distribution. For a loss XX and a risk level α∈[0,1)\alpha\in[0,1), it is defined by CVaR⁡α(X):=inf⁡η∈R{η+11−αE[(X−η)+]}\operatorname{CVaR}_{\alpha}(X) := \inf_{\eta\in\mathbb{R}}\left\{\eta+ \frac{1}{1-\alpha}\mathbb{E}[(X-\eta)^{+}]\right\}, where (x)+:=max⁡{x,0}(x)^{+} := \max\{x,0\}. Thus, CVaR⁡α(X)\operatorname{CVaR}_{\alpha}(X) accounts for both the probability and the magnitude of adverse outcomes. In particular, it can distinguish learning algorithms with similar expected regret but substantially different behavior on rare, high-regret events.

We study the smallest Bayesian CVaR regret achievable over KK episodes under the least favorable prior on a class M\mathcal{M} of episodic MDPs. More formally, we consider

RK,α(M):=sup⁡μ∈P(M)inf⁡ACVaR⁡αPμ,A(RK),(1)\mathcal{R}_{K,\alpha}(\mathcal{M}) := \sup_{\mu\in\mathcal{P}(\mathcal{M})}\inf_{\mathcal{A}}\operatorname{CVaR}^{\mathbb{P}_{\mu,\mathcal{A}}}_{\alpha}(R_K), \tag*{(1)}

Here, P(M)\mathcal{P}(\mathcal{M}) is the set of priors on M\mathcal{M}, A\mathcal{A} ranges over admissible algorithms, and RKR_K is the cumulative pseudo-regret. The law Pμ,A\mathbb{P}_{\mu,\mathcal{A}} includes the single draw M∼μM \sim\mu, the KK-episode interaction, and all transition and algorithmic randomness.

For the upper bound, we use the algorithm called UCBVI-BF, introduced by Azar et al. [1]. Although UCBVI-BF is a frequentist, prior-free algorithm, it remains a good candidate for the Bayesian optimization problem: for every prior, the best achievable Bayesian CVaR is no greater than that attained by any particular admissible algorithm. Moreover, the high-probability regret guarantee for UCBVI-BF holds uniformly over all MDPs in the class. We can therefore integrate its tail bound under an arbitrary prior and subsequently take the worst case over priors without changing the guarantee.

For the lower bound, we use the instantiation pattern for Bayesian CVaR converses in [2]. The three-state family is a bandit type construction simplified from [3]: only the first action is informative, and its Bernoulli outcome determines all later rewards.

Contributions

We give explicit upper and lower bounds for (1). The upper bound converts the UCBVI-BF tail guarantee into a bound uniform over priors. The lower bound transfers a bandit-like construction to episodic MDPs and proves the resulting Bayesian CVaR bound by reverse KL. To our knowledge, these are the first explicit bounds stated for the worst-case prior-predictive CVaR of episodic MDP pseudo-regret. The arguments establish a baseline and isolate what a sharper, MDP-specific result must improve. In particular, for a constant number of states, the upper and lower bounds on worst-case Bayesian CVaR regret match in their polynomial dependence on HH, AA, and KK, and differ only by a factor of log⁡(1/(1−α))\sqrt{\log(1/(1-\alpha))} in their dependence on the risk level. Closing this logarithmic gap, and thereby obtaining a sharp characterization, remains an open problem.

a) Minimax regret for episodic MDPs: Azar et al. [1] introduced optimistic value-iteration algorithms for tabular finite-horizon MDPs. UCBVI-BF has a model-uniform high-probability bound with leading term O~(HSAT)\widetilde{O}(\sqrt{HSAT}), T=KHT = KH, matching their minimax lower-bound scale for this model class. Our argument uses its uniform tail statement. For the more general stage-dependent setting, Jin et al. [4] gave an optimistic Q-learning bound and discussed lower bounds built from the communicating-MDP construction of Jaksch et al. [5].

b) Information-theoretic bounds for interactive learning: Chen et al. [6] developed interactive Fano, a reference-law method unifying Le Cam, Assouad, classical Fano, and DEC-based converses for adaptive data. Their fractional covering number measures how well one exploration distribution covers near-optimal decisions; combined with the DEC, it yields high-probability ExO+ bounds. Those results concern frequentist minimax regret and quantiles, whereas our reverse-KL proof is a direct prior-predictive event transfer for a finite hard family giving rise to worst case Bayesian CVaR bounds.

This work is supported by the Knut and Alice Wallenberg Foundation.

c) CVaR criteria: Risk-sensitive bandit and RL papers often place CVaR on a different random object. Tan and Weng [7] analyze the CVaR of bandit regret, while Wang et al. [8] and Du et al. [9] study environment-wise or nested CVaR objectives for returns. By contrast, [10] lower bounds CVaR under the joint prior-predictive law, and [2] instantiates this framework for Gaussian estimation and bandits. We apply that viewpoint to episodic-MDP pseudo-regret, take the worst case over priors, and strengthen the risk-level dependence on α\alpha relative to [2].

Episodic MDP Setup

Finite-horizon interaction

An episodic MDP is

M=(S,A,H,P,r,ρ),(2)M = (\mathcal{S}, \mathcal{A}, H, P, r, \rho), \tag*{(2)}

where S\mathcal{S} and A\mathcal{A} are finite sets with ∣S∣=S\lvert\mathcal{S}\rvert= S and ∣A∣=A\lvert\mathcal{A}\rvert= A, H≥2H \ge2 is the horizon, P(⋅∣s,a)P(\cdot\mid s,a) is the transition kernel, r:S×A→[0,1]r:\mathcal{S}\times\mathcal{A}\to[0,1] is a known deterministic reward function, and ρ\rho is the initial-state distribution. The same PP and rr apply at every stage and the model is fixed across episodes. The class M\mathcal{M} consists of MDPs satisfying these assumptions.

At the start of episode kk, the algorithm observes the history Hk−1\mathcal{H}_{k-1} and selects a possibly randomized, nonstationary policy πk=(πk,1,…,πk,H)\pi_k=(\pi_{k,1},\ldots,\pi_{k,H}). At stage hh,

Ak,h∼πk,h(⋅∣Sk,h),Sk,h+1∼P(⋅∣Sk,h,Ak,h).(3)A_{k,h}\sim\pi_{k,h}(\cdot\mid S_{k,h}),\qquad S_{k,h+1}\sim P(\cdot\mid S_{k,h},A_{k,h}). \tag*{(3)}

The policy may depend on hh. The value functions are

VM,hπ(s):=EMπ[∑ℓ=hHr(Sℓ,Aℓ)|Sh=s],(4)V^{\pi}_{M,h}(s):=\mathbb{E}^{\pi}_{M}\left[\sum_{\ell=h}^{H}r(S_{\ell},A_{\ell})\middle|S_h=s\right], \tag*{(4)}
VM,h∗(s):=sup⁡πVM,hπ(s).(5)V^{*}_{M,h}(s):=\sup_{\pi}V^{\pi}_{M,h}(s). \tag*{(5)}

Pseudo-regret and prior-predictive law

The cumulative pseudo-regret after KK episodes is

RK(M):=∑k=1K[VM,1∗(Sk,1)−VM,1πk(Sk,1)].(6)R_K(M):=\sum_{k=1}^{K}\left[V^{*}_{M,1}(S_{k,1})-V^{\pi_k}_{M,1}(S_{k,1})\right]. \tag*{(6)}

Since rewards belong to [0,1][0,1],

0≤RK(M)≤KH.(7)0\le R_K(M)\le KH. \tag*{(7)}

Randomness in RKR_K comes from the sampled MDP, the algorithm, and the observed trajectories. Let PAM\mathbb{P}^{M}_{A} denote the transcript law conditional on model MM. For a prior μ∈P(M)\mu\in\mathcal{P}(\mathcal{M}), define the joint prior-predictive law Pμ,A\mathbb{P}_{\mu,A} by

Pμ,A(dM,dh):=μ(dM)PAM(dh).(8)\mathbb{P}_{\mu,A}(dM,dh):=\mu(dM)\mathbb{P}^{M}_{A}(dh). \tag*{(8)}

Conditional value-at-risk

For an integrable loss XX and α∈[0,1)\alpha\in[0,1), the Rockafellar–Uryasev representation [11] defines upper-tail CVaR as

CVaR⁡α(X):=inf⁡t∈R{t+11−αE[(X−t)+]}.(9)\operatorname{CVaR}_{\alpha}(X):=\inf_{t\in\mathbb{R}}\left\{t+\frac{1}{1-\alpha}\mathbb{E}[(X-t)_{+}]\right\}. \tag*{(9)}

Thus (1) evaluates the tail of regret under the joint law (8); it does not mean that the learning algorithm itself must be Bayesian.

Main Results

Upper bound from UCBVI-BF

Let T:=KHT:=KH and

Lδ:=log⁡(5HSATδ).(10)L_{\delta}:=\log\left(\frac{5HSAT}{\delta}\right). \tag*{(10)}

The following is the high-probability result used as a black box.

Proposition 1 (UCBVI-BF). Under the assumptions above and those of Theorem 2 in [1], UCBVI-BF with confidence parameter δ∈(0,1)\delta\in(0,1) satisfies, for every M∈MM\in\mathcal{M},

PUCBVIM(RK>Bδ)≤δ,(11)\mathbb{P}^{M}_{\mathrm{UCBVI}}\left(R_K>B_{\delta}\right)\le\delta, \tag*{(11)}

where

Bδ:=30HLδSAK+2500H2S2ALδ2+4H3/2KLδ.(12)B_{\delta}:=30HL_{\delta}\sqrt{SAK}+2500H^{2}S^{2}AL_{\delta}^{2}+4H^{3/2}\sqrt{KL_{\delta}}. \tag*{(12)}

Reverse-KL lower bound

For the lower bound, consider the three-state family in Figure 1. The states and rewards are common to every MDP; the index jj only identifies the special first-stage action. Every episode starts at xx, and the transition to GG or BB is the sole random observation. The absorbing states repeat that Bernoulli outcome for the remaining H−1H-1 stages, producing value gap (H−1)ε(H-1)\varepsilon.

Figure 1. Hard MDP MjεM^{\varepsilon}_{j}. Only the action chosen at xx is informative

Theorem 4 (Bayesian CVaR lower bound). Let H≥2H \ge2, A≥2A \ge2, K≥1K \ge1, and α∈(3/4,1)\alpha\in(3/4,1). Every MDP class containing the three-state hard family satisfies

RK,α(M)≥min⁡{(H−1)K8,H−126AKlog⁡14(1−α)}.(13)\mathfrak{R}_{K,\alpha}(\mathcal{M}) \ge\min\left\{\frac{(H-1)K}{8},\frac{H-1}{2\sqrt{6}}\sqrt{AK\log\frac{1}{4(1-\alpha)}}\right\}. \tag*{(13)}

Remark 5 (Lower-bound method). The proof uses a uniform prior on the hard family and identifies an event that has probability at least 1/21/2 under a reference MDP and incurs regret of order (H−1)εK(H-1)\varepsilon K. The adaptive KL chain rule bounds the reverse-KL budget, after which reverse-KL event transfer and the tail-to-CVaR lemma give a fixed-ε\varepsilon bound. Choosing ε\varepsilon so that the transferred event fills the CVaR tail yields, Ω(HAKlog⁡(1/(1−α)))\Omega(H\sqrt{AK\log(1/(1-\alpha))}) for S=3S=3.

Discussion

Theorem 2 is a worst-case Bayesian guarantee achieved by a frequentist algorithm. Its validity depends on the model-uniform nature of (11), not on UCBVI-BF using a prior.

For S=3S=3, the leading upper and lower dependences are

upper:O~(HAKlog⁡11−α),lower:Ω(HAKlog⁡11−α).(14)\begin{aligned} \text{upper:}\quad&\widetilde{O}\left(H\sqrt{AK}\log\frac{1}{1-\alpha}\right),\\ \text{lower:}\quad&\Omega\left(H\sqrt{AK\log\frac{1}{1-\alpha}}\right). \tag*{(14)} \end{aligned}

Thus, for fixed S=3S=3 and fixed risk level, the bounds are asymptotically close in HH, AA, KK: both have the polynomial scale HAKH\sqrt{AK}, up to logarithmic and lower-order terms. However, a factor log⁡(1/(1−α))\sqrt{\log(1/(1-\alpha))} remains between them. The converse captures horizon dependence but not uncertainty across multiple states, and therefore has no nontrivial SS-dependence.

Two extensions are natural. Integrating the ExO high-probability bounds and fractional-covering analysis of [6] would extend the upper bound beyond tabular UCBVI; a risk-dependent ExO objective may improve the α\alpha-dependence. A communicating hard family in the spirit of [5] may add state dependence to the converse, but requires controlling policy-dependent state–action occupancies in the reverse-KL argument.

Proofs

Upper bound

We first prove the deterministic conversion used in the argument.

Lemma 6 (One-level tail-to-CVaR conversion). For every α∈[0,1)\alpha\in[0,1) and δ∈(0,1)\delta\in(0,1), let 0≤X≤Lmax⁡0 \le X \le L_{\max} almost surely. If P(X>Bδ)≤δ\mathbb{P}(X>B_\delta)\le\delta, then

CVaR⁡α(X)≤Bδ+Lmax⁡δ1−α.(15)\operatorname{CVaR}_{\alpha}(X)\le B_\delta+\frac{L_{\max}\delta}{1-\alpha}. \tag*{(15)}

Proof. Choose t=Bδt=B_\delta in (9). Since (X−Bδ)+≤Lmax⁡1{X>Bδ}(X-B_\delta)_+\le L_{\max}\mathbf{1}\{X>B_\delta\},

CVaR⁡α(X)≤Bδ+E[(X−Bδ)+]1−α≤Bδ+Lmax⁡δ1−α.(16)\operatorname{CVaR}_{\alpha}(X)\le B_\delta+\frac{\mathbb{E}[(X-B_\delta)_+]}{1-\alpha} \le B_\delta+\frac{L_{\max}\delta}{1-\alpha}. \tag*{(16)}

Proof of Theorem 2. Fix α∈[0,1)\alpha\in[0,1) and δ∈(0,1)\delta\in(0,1).

a) Prior-predictive tail: Proposition 1 states that, for every fixed M∈MM\in\mathcal{M},

PUCBVIM(RK>Bδ)≤δ,(17)\mathbb{P}^{M}_{\mathrm{UCBVI}}(R_K>B_\delta)\le\delta, \tag*{(17)}

with BδB_\delta given by (12). Crucially, the same threshold BδB_\delta applies to every MM; it does not depend on the prior or on the particular MDP. For any prior μ∈P(M)\mu\in\mathcal{P}(\mathcal{M}), the law of total probability under (8),

Pμ,UCBVI(RK>Bδ)=∫MPUCBVIM(RK>Bδ) μ(dM)≤∫Mδ μ(dM)=δ,(18)\mathbb{P}_{\mu,\mathrm{UCBVI}}(R_K>B_\delta)=\int_{\mathcal{M}}\mathbb{P}^{M}_{\mathrm{UCBVI}}(R_K>B_\delta)\,\mu(dM) \le\int_{\mathcal{M}}\delta\,\mu(dM)=\delta, \tag*{(18)}

because μ\mu is a probability measure. Thus the model-uniform frequentist inequality is prior-predictive for every prior.

b) CVaR conversion and optimization: Under the joint law Pμ,UCBVI\mathbb{P}_{\mu,\mathrm{UCBVI}}, boundedness (7) gives 0≤RK≤KH0\le R_K\le KH. Apply Lemma 6 to X=RKX=R_K, Lmax⁡=KHL_{\max}=KH, and the tail bound (20). We obtain

CVaR⁡αμ,UCBVI(RK)≤Bδ+KHδ1−α.(19)\operatorname{CVaR}^{\mu,\mathrm{UCBVI}}_{\alpha}(R_K)\le B_\delta+\frac{KH\delta}{1-\alpha}. \tag*{(19)}

Set δ=δα=(1−α)/(KH)∈(0,1)\delta=\delta_\alpha=(1-\alpha)/(KH)\in(0,1). Then KHδα/(1−α)=1KH\delta_\alpha/(1-\alpha)=1 and Bδα=LαB_{\delta_\alpha}=L_\alpha. Substitution into (21) gives the right-hand side of (14), uniformly in μ\mu. For each μ\mu, UCBVI-BF is an admissible algorithm, even though it does not use μ\mu. Therefore

sup⁡μinf⁡ACVaR⁡αμ,A(RK)≤sup⁡μCVaR⁡αμ,UCBVI(RK)≤right-hand side of (14).(20)\sup_{\mu}\inf_A\operatorname{CVaR}^{\mu,A}_{\alpha}(R_K) \le\sup_{\mu}\operatorname{CVaR}^{\mu,\mathrm{UCBVI}}_{\alpha}(R_K)\le\text{right-hand side of (14)}. \tag*{(20)}

This proves (14).

Lower bound

Hard MDP family

Fix A≥2A\ge2 and ε∈(0,1/4]\varepsilon\in(0,1/4]. The state space is

S={x,G,B}.(21)\mathcal{S}=\{x,G,B\}. \tag*{(21)}

The labels indicate the roles of the states: xx is the common initial state, GG is good, and BB is bad. Every episode starts from xx, so ρ=δx\rho=\delta_x. For each j∈[A]j\in[A], define MjεM^\varepsilon_j by

Pjε(G∣x,a)=12+ε1{a=j},(22)P^\varepsilon_j(G\mid x,a)=\frac{1}{2}+\varepsilon\mathbf{1}\{a=j\}, \tag*{(22)}
Equation not extracted

P^\varepsilon_j(B\mid x,a)=\frac{1}{2}-\varepsilon\mathbf{1}{a=j}.

{#eq:25}

For every a∈[A]a\in[A], the states GG and BB are absorbing:

P^\varepsilon_j(G\mid G,a)=1,\qquad P^\varepsilon_j(B\mid B,a)=1.

{#eq:26}

The reward function, common to the family, is

r(x,a)=0,r(G,a)=1,r(B,a)=0.(23)r(x,a)=0,\qquad r(G,a)=1,\qquad r(B,a)=0. \tag*{(23)}

The reference MDP M0M_0 has the same rewards and absorbing transitions, but

P0(G∣x,a)=P0(B∣x,a)=12for every a∈[A].(24)P_0(G\mid x,a)=P_0(B\mid x,a)=\frac{1}{2}\qquad\text{for every }a\in[A]. \tag*{(24)}

Let Fk−1:=σ(Hk−1)\mathcal{F}_{k-1}:=\sigma(\mathcal{H}_{k-1}) be the sigma-algebra generated by the transcript before episode kk, and write Ak:=Ak,1A_k:=A_{k,1}. Define

pk,j:=Pr⁡A(Ak=j∣Fk−1),Wj(K):=∑k=1Kpk,j.(25)p_{k,j}:=\Pr_{\mathcal{A}}(A_k=j\mid\mathcal{F}_{k-1}),\qquad W_j(K):=\sum_{k=1}^{K}p_{k,j}. \tag*{(25)}

Only the first action appears because later actions cannot change an absorbing state. The predictable soft count Wj(K)W_j(K) is the compensator of Nj(K):=∑k1{Ak=j}N_j(K):=\sum_k\mathbf{1}\{A_k=j\}: it sums conditional probabilities, not realized indicators. For every history,

∑j=1AWj(K)=∑k=1K∑j=1Apk,j=K.(26)\sum_{j=1}^{A}W_j(K)=\sum_{k=1}^{K}\sum_{j=1}^{A}p_{k,j}=K. \tag*{(26)}

Lemma 7 (Regret identity). Under MjεM_j^\varepsilon, the cumulative pseudo-regret is

RK,j=(H−1)ε(K−Wj(K)).(27)R_{K,j}=(H-1)\varepsilon\bigl(K-W_j(K)\bigr). \tag*{(27)}

In particular, 0≤RK,j≤(H−1)εK0\le R_{K,j}\le(H-1)\varepsilon K.

Proof. If the first-stage action is jj, the probability of entering GG is 1/2+ε1/2+\varepsilon; every other action enters GG with probability 1/21/2. Since being in GG yields one reward at each of the remaining H−1H-1 stages, the value difference between action jj and every action a≠ja\ne j is

gε=(H−1)[(12+ε)−12]=(H−1)ε.(28)g_\varepsilon=(H-1)\left[\left(\frac{1}{2}+\varepsilon\right)-\frac{1}{2}\right]=(H-1)\varepsilon. \tag*{(28)}

The policy value makes the conditioning explicit:

VMjε,1πk(x)=(H−1)[pk,j(12+ε)+(1−pk,j)12],V_{M_j^\varepsilon,1}^{\pi_k}(x)=(H-1)\left[p_{k,j}\left(\frac{1}{2}+\varepsilon\right)+(1-p_{k,j})\frac{1}{2}\right],
VMjε,1∗(x)=(H−1)(12+ε).(29)V_{M_j^\varepsilon,1}^{*}(x)=(H-1)\left(\frac{1}{2}+\varepsilon\right). \tag*{(29)}

The first line is the law of total expectation over whether Ak=jA_k=j, not a mixture over MDPs. The episode-kk pseudo-regret is therefore

gε(1−pk,j).(30)g_\varepsilon(1-p_{k,j}). \tag*{(30)}

Summing (34) over k=1,…,Kk=1,\ldots,K and using (29) proves (31). The bounds follow from 0≤Wj(K)≤K0\le W_j(K)\le K.

For ε∈(0,1/4]\varepsilon\in(0,1/4], let

με:=1A∑j=1AδMjε.(31)\mu_\varepsilon:=\frac{1}{A}\sum_{j=1}^{A}\delta_{M_j^\varepsilon}. \tag*{(31)}

Auxiliary inequalities

Lemma 8 (Reverse-KL event transfer). Let QQ and PP be probability measures, and let EE be an event. If Q(E)≥1/2Q(E)\ge1/2, then

P(E)≥14exp⁡{−2DKL(Q∥P)}.(32)P(E)\ge\frac{1}{4}\exp\{-2D_{\mathrm{KL}}(Q\mathbin\Vert P)\}. \tag*{(32)}

Proof. Write q:=Q(E)q:=Q(E) and p:=P(E)p:=P(E). If p=0p=0 while q>0q>0, then DKL(Q∥P)=+∞D_{\mathrm{KL}}(Q\mathbin\Vert P)=+\infty and (36) is trivial. For p>0p>0, data processing under ω↦1{ω∈E}\omega\mapsto\mathbf{1}\{\omega\in E\} and binary entropy h(q)≤log⁡2h(q)\le\log2 give

DKL(Q∥P)≥kl⁡(q∥p)≥qlog⁡1p−h(q)D_{\mathrm{KL}}(Q\mathbin\Vert P)\ge\operatorname{kl}(q\mathbin\Vert p)\ge q\log\frac{1}{p}-h(q)
≥12log⁡1p−log⁡2.(33)\ge\frac{1}{2}\log\frac{1}{p}-\log2. \tag*{(33)}

Rearranging and exponentiating proves (36). □\square

Lemma 9 (Tail event to CVaR). Let X≥0X\ge0, let E⊆{X≥r}E\subseteq\{X\ge r\}, and write p:=P(E)p:=\mathbb{P}(E). Then

CVaR⁡α(X)≥rmin⁡{1,p1−α}.(34)\operatorname{CVaR}_{\alpha}(X)\ge r\min\left\{1,\frac{p}{1-\alpha}\right\}. \tag*{(34)}

Proof. Monotonicity gives CVaR⁡α(X)≥CVaR⁡α(r1E)\operatorname{CVaR}_{\alpha}(X)\ge\operatorname{CVaR}_{\alpha}(r\mathbf{1}_E). For t∈[0,r]t\in[0,r], the objective in (9) for Y=r1EY=r\mathbf{1}_E is

t+p(r−t)1−α=pr1−α+t(1−p1−α).(35)t+\frac{p(r-t)}{1-\alpha}=\frac{pr}{1-\alpha}+t\left(1-\frac{p}{1-\alpha}\right). \tag*{(35)}

The affine function is minimized at t=0t=0 if p≤1−αp\le1-\alpha, and at t=rt=r otherwise. Values outside [0,r][0,r] cannot improve either endpoint. Therefore

CVaR⁡α(r1E)=rmin⁡{1,p1−α}.(36)\operatorname{CVaR}_{\alpha}(r\mathbf{1}_E)=r\min\left\{1,\frac{p}{1-\alpha}\right\}. \tag*{(36)}

□\square

Proof of the lower bound

Proof of Theorem 4. Fix α∈(3/4,1)\alpha\in(3/4,1), an arbitrary algorithm A\mathcal{A}, and an arbitrary ε∈(0,1/4]\varepsilon\in(0,1/4]. Let ZZ be the complete transcript and write Q‾0:=PAM0\overline{Q}^{0}:=P_{\mathcal{A}}^{M_0} and P‾j:=PAMjε\overline{P}^{j}:=P_{\mathcal{A}}^{M_j^\varepsilon}. Superscripts indicate laws conditional on a fixed MDP. Define joint laws on (J,Z)(J,Z) by

Q‾(J=j,Z∈D):=1AQ‾0(D),(37)\overline{Q}(J=j,Z\in D):=\frac{1}{A}\overline{Q}^{0}(D), \tag*{(37)}
P‾(J=j,Z∈D):=1AP‾j(D).(38)\overline{P}(J=j,Z\in D):=\frac{1}{A}\overline{P}^{j}(D). \tag*{(38)}

Thus JJ is uniform and independent of ZZ under Q‾\overline{Q}. Under P‾\overline{P}, draw JJ uniformly, set M=MJεM=M_J^\varepsilon, and draw Z∼PJZ\sim P^J. Consequently, for every C⊆M\mathcal{C}\subseteq\mathcal{M},

P‾(M∈C)=1A∑j=1A1{Mjε∈C}=με(C).(39)\overline{P}(M\in\mathcal{C})=\frac{1}{A}\sum_{j=1}^{A}\mathbf{1}\{M_j^\varepsilon\in\mathcal{C}\}=\mu_\varepsilon(\mathcal{C}). \tag*{(39)}

More generally,

P‾(M∈C,Z∈D)=1A∑j=1A1{Mjε∈C}Pj(D)=∫CPA(D) με(dM).(40)\overline{P}(M \in C, Z \in D)=\frac{1}{A}\sum_{j=1}^{A}\mathbf{1}\{M_j^\varepsilon\in C\}P^j(D) =\int_C P^A(D)\,\mu_\varepsilon(dM). \tag*{(40)}

Thus the pushforward of P‾\overline{P} to (M,Z)(M,Z) is Pμε,A\mathbb{P}_{\mu_\varepsilon,A}.

Step 1: A frequent large-regret event: Define E:={(j,z):Wj(K;z)≤K/2}E:=\{(j,z):W_j(K;z)\le K/2\}. For every transcript zz, (30) implies that at most one index can satisfy Wj(K)>K/2W_j(K)>K/2. Therefore at least A−1A-1 indices satisfy Wj(K)≤K/2W_j(K)\le K/2. Conditioning on ZZ under Q‾\overline{Q},

Q‾(E)=∫1A∑j=1A1{Wj(K;h)≤K2}Q0(dz)≥∫A−1AQ0(dz)=A−1A≥12.(41)\overline{Q}(E)=\int\frac{1}{A}\sum_{j=1}^{A}\mathbf{1}\left\{W_j(K;h)\le\frac{K}{2}\right\}Q^0(dz) \ge\int\frac{A-1}{A}Q^0(dz)=\frac{A-1}{A}\ge\frac{1}{2}. \tag*{(41)}

Moreover, Lemma 7 shows that on EE,

RK,j=(H−1)ε(K−Wj(K))≥(H−1)εK2=:rε.(42)R_{K,j}=(H-1)\varepsilon(K-W_j(K)) \ge\frac{(H-1)\varepsilon K}{2}=:r_\varepsilon. \tag*{(42)}

The boundedness part is 0≤RK,j≤(H−1)εK0\le R_{K,j}\le(H-1)\varepsilon K.

Step 2: Reverse-KL budget: Let Yk:=1{Sk,2=G}Y_k:=\mathbf{1}\{S_{k,2}=G\} denote the transition outcome in episode kk, and let Gk:=σ(Hk−1,Ak)\mathcal{G}_k:=\sigma(\mathcal{H}_{k-1},A_k). Conditional on Gk\mathcal{G}_k, if Ak=aA_k=a, then

Q0(Yk=1∣Gk)=12,Pj(Yk=1∣Gk)=12+ε1{a=j}.(43)Q^0(Y_k=1\mid\mathcal{G}_k)=\frac{1}{2}, \qquad P^j(Y_k=1\mid\mathcal{G}_k)=\frac{1}{2}+\varepsilon\mathbf{1}\{a=j\}. \tag*{(43)}

Applying the KL chain rule sequentially to the transcript gives

DKL(Q0∥Pj)=∑k=1KEQ0[DKL(Q0(Ak∣Fk−1)∥Pj(Ak∣Fk−1))+DKL(Q0(Yk∣Gk)∥Pj(Yk∣Gk))].(44)D_{\mathrm{KL}}(Q^0\mathbin\Vert P^j) =\sum_{k=1}^{K}\mathbb{E}_{Q^0}\left[ D_{\mathrm{KL}}\left(Q^0(A_k\mid\mathcal{F}_{k-1})\mathbin\Vert P^j(A_k\mid\mathcal{F}_{k-1})\right) +D_{\mathrm{KL}}\left(Q^0(Y_k\mid\mathcal{G}_k)\mathbin\Vert P^j(Y_k\mid\mathcal{G}_k)\right) \right]. \tag*{(44)}

The action term is zero because, conditional on the same realized history, the algorithm uses the same action kernel under both models. By (46), the observation term is zero unless Ak=jA_k=j, when it equals d(ε)d(\varepsilon). Hence, by the tower property,

EQ0[1{Ak=j}]=EQ0[pk,j],(45)\mathbb{E}_{Q^0}[\mathbf{1}\{A_k=j\}]=\mathbb{E}_{Q^0}[p_{k,j}], \tag*{(45)}
DKL(Q0∥Pj)=d(ε)EQ0[Wj(K)].(46)D_{\mathrm{KL}}(Q^0\mathbin\Vert P^j)=d(\varepsilon)\mathbb{E}_{Q^0}[W_j(K)]. \tag*{(46)}

The Bernoulli divergence is d(ε)=−12log⁡(1−4ε2)d(\varepsilon)=-\frac{1}{2}\log(1-4\varepsilon^2). For 0<ε≤1/40<\varepsilon\le1/4, the inequality −log⁡(1−x)≤x/(1−x)-\log(1-x)\le x/(1-x), with x=4ε2≤1/4x=4\varepsilon^2\le1/4, gives d(ε)≤2ε2/(1−4ε2)≤3ε2d(\varepsilon)\le2\varepsilon^2/(1-4\varepsilon^2)\le3\varepsilon^2.

Since the marginals are the same uniform law, the conditional KL chain rule for (J,Z)(J,Z) gives

DKL(Q‾∥P‾)=1A∑j=1ADKL(Q0∥Pj)=Kd(ε)A≤3Kε2A.(47)D_{\mathrm{KL}}(\overline{Q}\mathbin\Vert\overline{P}) =\frac{1}{A}\sum_{j=1}^{A}D_{\mathrm{KL}}(Q^0\mathbin\Vert P^j) =\frac{Kd(\varepsilon)}{A}\le\frac{3K\varepsilon^2}{A}. \tag*{(47)}

The factors 1/A1/A cancel inside the likelihood ratio, while the outer expectation averages the conditional KL divergences. The final equality uses (30).

Step 3: Event transfer and CVaR: Set pε:=P‾(E)p_\varepsilon:=\overline{P}(E). By (44), the premise of Lemma 8 holds with Q=Q‾Q=\overline{Q} and P=P‾P=\overline{P}. Using (51) we get,

pε≥14exp⁡{−2DKL(Q‾∥P‾)}≥14exp⁡(−6Kε2A).(48)p_\varepsilon\ge\frac{1}{4}\exp\{-2D_{\mathrm{KL}}(\overline{Q}\mathbin\Vert\overline{P})\} \ge\frac{1}{4}\exp\left(-\frac{6K\varepsilon^2}{A}\right). \tag*{(48)}

By (43), the regret under P‾\overline{P} has law Pμε,A\mathbb{P}_{\mu_\varepsilon,A}. Since (45) gives E⊆{RK≥rε}E\subseteq\{R_K\ge r_\varepsilon\}, Lemma 9 yields

CVaR⁡αPμε,A(RK)≥rεmin⁡{1,pε1−α}≥(H−1)εK2min⁡{1,exp⁡(−6Kε2/A)4(1−α)}.(49)\operatorname{CVaR}_{\alpha}^{\mathbb{P}_{\mu_\varepsilon,A}}(R_K) \ge r_\varepsilon\min\left\{1,\frac{p_\varepsilon}{1-\alpha}\right\} \ge\frac{(H-1)\varepsilon K}{2}\min\left\{1,\frac{\exp(-6K\varepsilon^2/A)}{4(1-\alpha)}\right\}. \tag*{(49)}

This holds for every ε∈(0,1/4]\varepsilon\in(0,1/4] and every algorithm.

Step 4: Tail filling and worst-case value: Put β:=1−α\beta:=1-\alpha. In (53), the full regret level rεr_\varepsilon is retained whenever −6Kε2/A≥log⁡(4β)-6K\varepsilon^2/A\ge\log(4\beta), equivalently ε2≤(A/(6K))log⁡(1/(4β))\varepsilon^2\le(A/(6K))\log(1/(4\beta)). Since α>3/4\alpha>3/4, let Λα:=log⁡(1/(4(1−α)))>0\Lambda_\alpha:=\log(1/(4(1-\alpha)))>0 and choose

ε∗:=min⁡{14,AΛα6K}.(50)\varepsilon_*:=\min\left\{\frac{1}{4},\sqrt{\frac{A\Lambda_\alpha}{6K}}\right\}. \tag*{(50)}

Then 6Kε∗2/A≤Λα6K\varepsilon_*^2/A\le\Lambda_\alpha, so e−6Kε∗2/A/(4(1−α))≥1e^{-6K\varepsilon_*^2/A}/(4(1-\alpha))\ge1. Therefore the minimum in (53) equals 11, and

CVaR⁡αPμε∗,A(RK)≥(H−1)K2min⁡{14,AΛα6K}=min⁡{(H−1)K8,H−126AKΛα}.(51)\operatorname{CVaR}_{\alpha}^{\mathbb{P}_{\mu_{\varepsilon_*},A}}(R_K) \ge\frac{(H-1)K}{2}\min\left\{\frac{1}{4},\sqrt{\frac{A\Lambda_\alpha}{6K}}\right\} =\min\left\{\frac{(H-1)K}{8},\frac{H-1}{2\sqrt{6}}\sqrt{AK\Lambda_\alpha}\right\}. \tag*{(51)}

The algorithm was arbitrary, so we may take its infimum. Since με∗\mu_{\varepsilon_*} is admissible in (1), its value lower bounds the supremum over priors. Substituting the definition of Λα\Lambda_\alpha in (55) proves (15). □

Conclusion

We established upper and lower bounds on worst-case Bayesian CVaR regret for episodic MDPs. The upper bound converts the high-probability guarantee of UCBVI-BF, while the converse applies reverse KL to a three-state MDP family. For fixed SS, the bounds match polynomially in H,A,KH,A,K, but differ by a factor of log⁡(1/(1−α))\sqrt{\log(1/(1-\alpha))} in their risk-level dependence. The lower bound also has no nontrivial SS-dependence. Closing these gaps likely requires a multistage hard family in which uncertainty and regret accumulate across states and stages.

AI Statement

The main ideas of the paper were conceived by the authors without substantial aid of generative models. OpenAI Codex was used to assist with organization, mathematical typesetting, language editing of the manuscript along with aiding with the algebraic derivations in Section V. Codex was also used to create the TikZ-code for figure. The authors are responsible for, and have independently verified, all definitions, calculations, proofs, and citations.

References

  1. [1]M. G. Azar, I. Osband, and R. Munos, “Minimax regret bounds for reinforcement learning,” in International conference on machine learning. PMLR, 2017, pp. 263–272.arxiv.org/abs/1703.05449
  2. [2]R. R. O. J. Oechtering, and M. Skoglund, “Instantiating bayesian cvar lower bounds in interactive decision making problems,” arXiv preprint arXiv:2604.12519, 2026.
  3. [3]C. Dann and E. Brunskill, “Sample complexity of episodic fixed-horizon reinforcement learning,” Advances in Neural Information Processing Systems, vol. 28, 2015.arxiv.org/abs/1510.08906
  4. [4]C. Jin, Z. Allen-Zhu, S. Bubeck, and M. Jordan, “Is q-learning provably efficient?” Advances in neural information processing systems, vol. 31, 2018.
  5. [5]P. Auer, T. Jaksch, and R. Ortner, “Near-optimal regret bounds for reinforcement learning,” Advances in neural information processing systems, vol. 21, 2008.
  6. [6]F. Chen, D. J. Foster, Y. Han, J. Qian, A. Rakhlin, and Y. Xu, “Assouad, fano, and le cam with interaction: A unifying lower bound framework and characterization for bandit learnability,” Advances in Neural Information Processing Systems, vol. 37, pp. 75 585–75 641, 2024.arxiv.org/abs/2410.05117
  7. [7]C. Tan and P. Weng, “Cvar-regret bounds for multi-armed bandits,” in Asian Conference on Machine Learning. PMLR, 2023, pp. 974–989.
  8. [8]K. Wang, N. Kallus, and W. Sun, “Near-minimax-optimal risk-sensitive reinforcement learning with cvar,” in International Conference on Machine Learning. PMLR, 2023, pp. 35 864–35 907.arxiv.org/abs/2302.03201
  9. [9]Y. Du, S. Wang, and L. Huang, “Provably efficient risk-sensitive reinforcement learning: Iterated cvar and worst path,” arXiv preprint arXiv:2206.02678, 2022.arxiv.org/abs/2206.02678
  10. [10]R. Bongole, T. J. Oechtering, and M. Skoglund, “Generalizing the fano inequality further,” arXiv preprint arXiv:2601.12027, 2026.arxiv.org/abs/2601.12027
  11. [11]R. T. Rockafellar, S. Uryasev et al., “Optimization of conditional value-at-risk,” Journal of risk, vol. 2, pp. 21–42, 2000.DOI

Paper details

vlnc:W_grgjc4p8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Codex

View statement
Looking for related papers…
Contents