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

arXiv: https://arxiv.org/abs/2608.28960 · HTML: https://mlsanity.com/paper/2608.28960/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 5 of its 7 references that are in the map.
- First posted on arXiv 29 Aug 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 5 of 5)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR](https://mlsanity.com/paper/2302.03201/) (2023)
- [Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2210.05650/) (2022)
- [A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2403.06323/) (2024)
- [Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measures](https://mlsanity.com/paper/2306.02399/) (2023)

## Abstract (arXiv)

For finite-horizon tabular CVaR reinforcement learning, prior work proves a widetildeO(τ-1√SAK) leading regret bound for arbitrary normalized return laws and the sharper widetildeO(√SAK/τ) 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 τ plus the value-estimation width. Substitution into the original Bernstein decomposition yields, with high probability, widetildeO(√SAK/τ+(SAHK1/4+S2AH)/τ) regret for arbitrary normalized return laws, including atomic, mixed, and continuous laws. The τ-1/2 leading term matches the expected-regret minimax lower bound 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 dependence.