A Refined Analysis of UCBVI

Simone Drago, Marco Mussi, Alberto Maria Metelli

A Refined Analysis of UCBVI

Abstract

This paper presents a refined theoretical analysis of the Upper Confidence Bound Value Iteration (UCBVI) algorithm for tabular reinforcement learning. By tightening concentration inequalities and reducing multiplicative constants in exploration bonuses, the authors demonstrate that UCBVI achieves significantly lower regret in practice compared to state-of-the-art algorithms like MVP, which often suffer from large constants despite their order-optimal theoretical guarantees.

Addressing the "Constant" Problem in RL Theory

In reinforcement learning (RL) theory, researchers typically focus on "order-optimal" regret—ensuring the error grows at the slowest possible rate (e.g., $\tilde{O}(\sqrt{HSAT})$). However, Big-O notation often hides multiplicative constants that can make a theoretically "perfect" algorithm practically useless. For instance, the MVP algorithm achieves order-optimality across all time horizons but introduces massive constants that hinder its real-world utility. This work revisits UCBVI to minimize these "hidden" constants, bridging the gap between theoretical tightness and empirical performance.

Methods: Refining Exploration Bonuses

The authors perform a refined analysis of UCBVI, focusing on two types of exploration bonuses:

  1. Chernoff-Hoeffding (CH) Bonus: Based on basic concentration inequalities.
  2. Bernstein-Freedman (BF) Bonus: A more sophisticated bonus that accounts for the variance of the value function, allowing for tighter exploration.

The core contribution is a tighter proof. By re-deriving concentration inequalities and regret decompositions, the authors identified and corrected errors in previous literature, lowering the constants. For the BF bonus, they reduced key multiplicative factors (e.g., from $\sqrt{8}$ to $\sqrt{4}$), resulting in the improved UCBVI-BF-I variant.

Empirical Results

The theoretical refinements translate directly into faster convergence. By proving that smaller bonuses are sufficient for optimism, the agent avoids redundant exploration and converges to the optimal policy more quickly.

Cumulative regret across different horizons (H) and total episodes (K). UCBVI-BF-I consistently demonstrates the lowest regret compared to original UCBVI and MVP.

As shown in the figure above, UCBVI-BF-I significantly outperforms the original UCBVI and the state-of-the-art MVP across various settings. The reduction in exploration bonuses led to an empirical regret approximately 1.87 times lower than the original version.

Hard Exploration: The RiverSwim Benchmark

The benefits of refined constants are most apparent in "hard exploration" tasks like RiverSwim, where an agent must endure many steps without reward to reach a high-payoff state.

Cumulative regret in the RiverSwim environment. MVP exhibits linear regret (failing to learn), while UCBVI variants achieve sub-linear regret.

In RiverSwim, the MVP algorithm fails to learn an effective policy within the given timeframe, exhibiting linear regret. In contrast, the well-tuned UCBVI-BF-I maintains a sub-linear regret trend, successfully navigating the environment's challenges due to its more efficient, constant-aware exploration strategy.

Conclusion

This work underscores the importance of "constant-aware" analysis in RL. While currently limited to tabular settings, the principles of minimizing multiplicative factors in theoretical bounds can lead to substantial practical gains. Future work could extend these techniques to function approximation settings, further narrowing the divide between RL theory and practice.

Summary updated

Abstract

In this work, we provide a refined analysis of the UCBVI algorithm (Azar et al., 2017), improving both the bonus terms and the regret analysis. Additionally, we compare our version of UCBVI with both its original version and the state-of-the-art MVP algorithm. Our empirical validation demonstrates that improving the multiplicative constants in the bounds has significant positive effects on the empirical performance of the algorithms.
BibTeX
@misc{drago2025refined,
  author = {Simone Drago and Marco Mussi and Alberto Maria Metelli},
  title = {{A Refined Analysis of UCBVI}},
  year = {2025},
  eprint = {2502.17370},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.17370},
}
Figure