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

arXiv:2608.28960v1 Announce Type: new Abstract: For finite-horizon tabular CVaR reinforcement learning, prior work proves a widetilde{O}(au^{-1}sqrt{SAK}) leading regret bound for arbitrary normalized return laws and the sharper widetilde{O}(sqrt{SAK/au}) 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 au plus the value-estimation width. Substitution into the original Bernstein decomposition yields, with high probability, widetilde{O}(sqrt{SAK/au}+(SAHK^{1/4}+S^2AH)/au) regret for arbitrary normalized return laws, including atomic, mixed, and continuous laws. The au^{-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 au^{-1} dependence.

Related

• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
• ReversedQ: Opportunities for Faster Q-Learning in Episodic Online Reinforcement Learning
• A Finite Sample Analysis for Quantile Temporal Difference Learning in Distributional Reinforcement Learning
• Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

Source: arXiv cs.LG | 2026-09-01