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 fraction of the distribution. For a loss and a risk level , it is defined by , where . Thus, 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 episodes under the least favorable prior on a class of episodic MDPs. More formally, we consider
Here, is the set of priors on , ranges over admissible algorithms, and is the cumulative pseudo-regret. The law includes the single draw , the -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 , , and , and differ only by a factor of in their dependence on the risk level. Closing this logarithmic gap, and thereby obtaining a sharp characterization, remains an open problem.
Related work
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 , , 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 relative to [2].
Episodic MDP Setup
Finite-horizon interaction
An episodic MDP is
where and are finite sets with and , is the horizon, is the transition kernel, is a known deterministic reward function, and is the initial-state distribution. The same and apply at every stage and the model is fixed across episodes. The class consists of MDPs satisfying these assumptions.
At the start of episode , the algorithm observes the history and selects a possibly randomized, nonstationary policy . At stage ,
The policy may depend on . The value functions are
Pseudo-regret and prior-predictive law
The cumulative pseudo-regret after episodes is
Since rewards belong to ,
Randomness in comes from the sampled MDP, the algorithm, and the observed trajectories. Let denote the transcript law conditional on model . For a prior , define the joint prior-predictive law by
Conditional value-at-risk
For an integrable loss and , the Rockafellar–Uryasev representation [11] defines upper-tail CVaR as
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 and
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 satisfies, for every ,
where
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 only identifies the special first-stage action. Every episode starts at , and the transition to or is the sole random observation. The absorbing states repeat that Bernoulli outcome for the remaining stages, producing value gap .
Figure 1. Hard MDP . Only the action chosen at is informative
Theorem 4 (Bayesian CVaR lower bound). Let , , , and . Every MDP class containing the three-state hard family satisfies
Remark 5 (Lower-bound method). The proof uses a uniform prior on the hard family and identifies an event that has probability at least under a reference MDP and incurs regret of order . 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- bound. Choosing so that the transferred event fills the CVaR tail yields, for .
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 , the leading upper and lower dependences are
Thus, for fixed and fixed risk level, the bounds are asymptotically close in , , : both have the polynomial scale , up to logarithmic and lower-order terms. However, a factor remains between them. The converse captures horizon dependence but not uncertainty across multiple states, and therefore has no nontrivial -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 -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 and , let almost surely. If , then
Proof. Choose in (9). Since ,
Proof of Theorem 2. Fix and .
a) Prior-predictive tail: Proposition 1 states that, for every fixed ,
with given by (12). Crucially, the same threshold applies to every ; it does not depend on the prior or on the particular MDP. For any prior , the law of total probability under (8),
because 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 , boundedness (7) gives . Apply Lemma 6 to , , and the tail bound (20). We obtain
Set . Then and . Substitution into (21) gives the right-hand side of (14), uniformly in . For each , UCBVI-BF is an admissible algorithm, even though it does not use . Therefore
This proves (14).
Lower bound
Hard MDP family
Fix and . The state space is
The labels indicate the roles of the states: is the common initial state, is good, and is bad. Every episode starts from , so . For each , define by
P^\varepsilon_j(B\mid x,a)=\frac{1}{2}-\varepsilon\mathbf{1}{a=j}.
For every , the states and are absorbing:
P^\varepsilon_j(G\mid G,a)=1,\qquad P^\varepsilon_j(B\mid B,a)=1.
The reward function, common to the family, is
The reference MDP has the same rewards and absorbing transitions, but
Let be the sigma-algebra generated by the transcript before episode , and write . Define
Only the first action appears because later actions cannot change an absorbing state. The predictable soft count is the compensator of : it sums conditional probabilities, not realized indicators. For every history,
Lemma 7 (Regret identity). Under , the cumulative pseudo-regret is
In particular, .
Proof. If the first-stage action is , the probability of entering is ; every other action enters with probability . Since being in yields one reward at each of the remaining stages, the value difference between action and every action is
The policy value makes the conditioning explicit:
The first line is the law of total expectation over whether , not a mixture over MDPs. The episode- pseudo-regret is therefore
Summing (34) over and using (29) proves (31). The bounds follow from .
For , let
Auxiliary inequalities
Lemma 8 (Reverse-KL event transfer). Let and be probability measures, and let be an event. If , then
Proof. Write and . If while , then and (36) is trivial. For , data processing under and binary entropy give
Rearranging and exponentiating proves (36).
Lemma 9 (Tail event to CVaR). Let , let , and write . Then
Proof. Monotonicity gives . For , the objective in (9) for is
The affine function is minimized at if , and at otherwise. Values outside cannot improve either endpoint. Therefore
Proof of the lower bound
Proof of Theorem 4. Fix , an arbitrary algorithm , and an arbitrary . Let be the complete transcript and write and . Superscripts indicate laws conditional on a fixed MDP. Define joint laws on by
Thus is uniform and independent of under . Under , draw uniformly, set , and draw . Consequently, for every ,
More generally,
Thus the pushforward of to is .
Step 1: A frequent large-regret event: Define . For every transcript , (30) implies that at most one index can satisfy . Therefore at least indices satisfy . Conditioning on under ,
Moreover, Lemma 7 shows that on ,
The boundedness part is .
Step 2: Reverse-KL budget: Let denote the transition outcome in episode , and let . Conditional on , if , then
Applying the KL chain rule sequentially to the transcript gives
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 , when it equals . Hence, by the tower property,
The Bernoulli divergence is . For , the inequality , with , gives .
Since the marginals are the same uniform law, the conditional KL chain rule for gives
The factors 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 . By (44), the premise of Lemma 8 holds with and . Using (51) we get,
By (43), the regret under has law . Since (45) gives , Lemma 9 yields
This holds for every and every algorithm.
Step 4: Tail filling and worst-case value: Put . In (53), the full regret level is retained whenever , equivalently . Since , let and choose
Then , so . Therefore the minimum in (53) equals , and
The algorithm was arbitrary, so we may take its infimum. Since is admissible in (1), its value lower bounds the supremum over priors. Substituting the definition of 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 , the bounds match polynomially in , but differ by a factor of in their risk-level dependence. The lower bound also has no nontrivial -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]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]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]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]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]P. Auer, T. Jaksch, and R. Ortner, “Near-optimal regret bounds for reinforcement learning,” Advances in neural information processing systems, vol. 21, 2008.
- [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]C. Tan and P. Weng, “Cvar-regret bounds for multi-armed bandits,” in Asian Conference on Machine Learning. PMLR, 2023, pp. 974–989.
- [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]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]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]R. T. Rockafellar, S. Uryasev et al., “Optimization of conditional value-at-risk,” Journal of risk, vol. 2, pp. 21–42, 2000.DOI
