mlsanityData to 14 Oct 2026

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

arXiv 2608.28960 ↗First posted 29 Aug 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

5 of 7 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents10 Mar

Other references · 4

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  3. 2022Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 26
  4. 2023Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz Dynamic Risk Measurescited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
  2. 2026Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
  3. 2024Achieving Constant Regret in Linear Markov Decision Processes
  4. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learning
  5. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
  6. 2026Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation
  7. 2025Tail Distribution of Regret in Optimistic Reinforcement Learning
  8. 2026Robust Risk-Sensitive Reinforcement Learning from Corrupted Human Feedback