SOURCE-LINKED INTELLIGENCE

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

arXiv · AI, language, vision and robotics · article · Aug 29, 2026 · UTC

For finite-horizon tabular CVaR reinforcement learning, prior work proves a $\widetilde{O}(τ^{-1}\sqrt{SAK})$ leading regret bound for arbitrary normalized return laws and the sharper $\widetilde{O}(\sqrt{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, $\widetilde{O}(\s

Read original source ↗ Open in workspace

recordType

paper

region

Global