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

1. Introduction

• Prior work’s sharper leading rate requires a return-law density lower bound, and removing that regularity condition remained open.For general return laws, the prior bound has a weaker leading term [6].Source: §1 · p. 1
• The analysis controls the mean shortfall at the selected budget by τ plus the value-estimation width, avoiding continuity-based quantile identification.Since a [0, 1]-valued random variable’s variance is at most its mean, this gives the desired scaling.Source: §1 · p. 1
• A selected-budget self-bound yields leading-order minimax optimality for Bernstein CVaR-UCBVI over arbitrary normalized return laws, including atomic, mixed, and continuous laws.The bound combines with Wang et al.’s Bernstein regret decomposition; the leading term matches the expected-regret minimax lower bound up to logarithmic factors when lower-order terms are negligible.Source: §1 · p. 2

1.1. Related work.

• Related work covers broad static risk criteria, precommitted CVaR, optimized certainty equivalents, reward-free exploration, and dynamic risk measures.This paper addresses continuity removal for regret analysis of Bernstein CVaR-UCBVI with static trajectory-level CVaR.Source: §1.1 · p. 2

2.1. Model and objective.

• The setting is an episodic tabular MDP with known conditional reward laws, unknown transitions, and almost-surely normalized returns for every history-dependent policy.Rewards are nonnegative; the model has horizon H and K episodes.Source: §2.1 · p. 2
• The augmented state is (s, b): the initial budget is in [0, 1], and each stage updates the residual budget by subtracting the reward.Residual budgets may become negative.Source: §2.1 · p. 3

2.2. Bernstein CVaR-UCBVI.

• The exact-budget algorithm uses a backward recursion and an Fk-measurable maximizing selector, then runs a policy from the selected budget.The recursion uses a fixed measurable tie-breaking rule; the algorithm interacts with the original MDP while maintaining the scalar residual budget.Source: §2.2 · pp. 3–4

2.3. Auxiliary regret decomposition. !+

• The auxiliary regret decomposition includes ξk, the transition correction associated with the Bernstein bonus.Its formula and the bonus formula are recorded in section A.Source: §2.3 · p. 4

2 BONBERN

• Proposition 2.1 gives auxiliary bounds for the estimates on a common event with probability at least 1 − δ.The cited proposition concerns estimates generated by the stated update equations and Bernstein bonus.Source: §2 · p. 4
• Equation (2.15) holds for every episode k.Source: §2 · p. 5
• Uniformity over budgets permits evaluation at the data-dependent selected budget, and the remaining proof uses only the proposition’s inequalities.Section A restates the relevant derivation from Wang et al..Source: §2 · p. 5

3. A self-bounding shortfall

• For every episode, the selected-budget result bounds the conditional shortfall variance by τ + Wk.The lemma also bounds the conditional mean shortfall by τ + Wk.Source: §3 · p. 5
• The argument controls a lower partial moment, so mass at the selected threshold contributes zero and no quantile identification or anti-concentration is needed.Source: §3 · p. 5
• For an atomic Bernoulli return with probability τ of zero, the maximizing budget is non-unique, yet the extreme choice b = 1 has variance τ(1 − τ) ≤ τ.Source: §3 · p. 5

4. Regret analysis

• The selected-budget self-bound provides distribution-free control of cumulative trajectory variance for the regret analysis.The proof substitutes the cumulative-variance bound into the Bernstein decomposition.Source: §4 · p. 6
• Theorem 4.2 applies Bernstein CVaR-UCBVI without Assumption 5.4 to MDPs with discrete, mixed, or continuous induced return laws.The guarantee is under the tabular, known-reward, nonnegative, normalized-return model.Source: §4 · p. 6
• The discretized implementation's original-MDP regret is bounded by the Theorem 4.2 bound plus an additional term.For any requested mesh width in (0, 1), the construction can choose a mesh no larger than that width, without requiring continuity of either return law.Source: §4 · p. 7
• The discretization proof compares the grid and continuum benchmarks, with the grid containing zero so the selected-budget self-bound remains valid.The subsequent simulation, bonus, concentration, and variance steps are unchanged.Source: §4 · p. 8

5. Discussion

• The result applies to tabular MDPs with known reward laws, unknown transitions, nonnegative normalized returns, and static CVaR of the full trajectory.The grid-based implementation corollary does not alter computational complexity.Source: §5 · p. 9
• The selected-budget choices include a budget and an augmented policy that are measurable before the episode is executed.The selected pair induces a fresh return with the same conditional law as the realized episode return.Source: §5 · p. 9
• Proposition 5.1 concerns the CVaR specialization and does not establish an analogous self-bound for every OCE utility.The other oracle assumptions of Wang et al. remain unchanged.Source: §5 · p. 9
• The leading regret term is eO(sqrt(SAK/τ)) for arbitrary normalized return laws, matching the expected-regret minimax lower bound up to logarithmic factors.The lower-order terms retain τ^-1 dependence.Source: §5 · pp. 8–9

Appendix A. Derivation of the auxiliary regret bounds

• The appendix restates ingredients from Appendix G of Wang et al. in the paper’s notation and records their locations in that work.These bounds lead to Proposition 2.1.Source: Appendix A · p. 10
• The selected-budget argument enters subsequently through Lemma 3.1.Source: Appendix A · p. 10
• The empirical transition law is based on the pre-episode visits to each state-action pair.The notation also sets ℓδ = log(HSAK/δ) and b′ = b − r.Source: Appendix A · p. 10

A.1. Bernstein bonus and transition correction.

• Equation (6) of Wang et al. defines a quantity used in the derivation.Source: §A.1 · p. 10
• Lemma G.2 introduces the transition correction.Source: §A.1 · p. 10
• The confidence event is uniform over b ∈ [0, 1], and on it Theorem G.7 establishes the required pessimism invariant.Lemma G.4 gives Wk ≤ eBk; together these results yield equations (2.14) and (2.15).Source: §A.1 · p. 10

A.2. Cumulative width bound.

• The variance-independent estimate controls Pk Wk independently of the variance bound in the next subsection.The derivation uses L ≥ ℓδ.Source: §A.2 · p. 10

A.3. Population variance and regret decomposition.

• Cauchy–Schwarz and the elliptical-potential count bound contribute the factor SAL to the population-variance bound.The derivation also uses the paper’s Azuma 4 bound and that joint variance dominates the variance of a conditional mean.Source: §A.3 · p. 10
• The inner trajectory variance is identified by the law of total variance, and the regret decomposition follows from pessimism, selected-budget optimality, and evaluation of the selected-policy CVaR objective.The derivation combines these steps with Lemma G.4 and Azuma 1.Source: §A.3 · p. 11
• The decomposition does not invoke Assumption 5.4; the selected-budget self-bound controls the trajectory-variance sum that the original proof bounded using that assumption.The paper retains coefficient 74e so the absorption is valid uniformly for S, A, L ≥ 1.Source: §A.3 · p. 11

• Comparison with feasible budget 0 bounds the selected value by 1, so its conditional variance is at most its conditional mean.At budget 0, nonnegative returns give value 0; the selected budget lies in [0, 1].Source: Appendix B · p. 11
• R ≤ 2√(C1Kτ) + C1 + 2C2 follows from Assumption D.10 and equation (B.1); exact optimism removes the slack term in Wang et al.’s Theorem 3.2.Source: Appendix B · p. 12
• RegretCVaRτ(K) ≤ τ^-1R under exact optimism, giving equation (5.1).Source: Appendix B · p. 12