Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs

Mohammad Sadegh Talebi, Odalric-Ambrym Maillard

Abstract

Traditional regret bounds for reinforcement learning (RL) in average-reward Markov Decision Processes (MDPs) often rely on the diameter of the MDP, a global worst-case metric that frequently overestimates the difficulty of learning. This paper presents a refined analysis of the KL-UCRL algorithm, establishing tighter regret bounds that depend on the local variance of the optimal bias function rather than the global diameter. By leveraging novel transportation lemmas and KL-divergence-based confidence sets, the authors provide a high-probability regret bound of $\tilde{O}(\sqrt{S \sum_{s,a} \mathbf{V}^*_{s,a} T} + D\sqrt{T})$, bridging the gap between theoretical guarantees and the strong empirical performance of KL-based methods.

Introduction

In the study of Reinforcement Learning (RL), "regret" serves as the primary metric for evaluating an agent's efficiency, representing the cumulative difference between the rewards obtained by an optimal policy and those gathered by the learning agent. For undiscounted, infinite-horizon problems, the goal is typically to maximize the long-term average reward.

Historically, the theoretical performance of algorithms like UCRL2 has been bounded by the diameter ($D$) of the MDP—the maximum expected time required to transition between any two states under some policy. While $D$ provides a mathematically sound upper bound, it is a "global" and "worst-case" measure. In many practical environments, the diameter can be extremely large, yet the environment remains "smooth" locally, allowing agents to learn much faster than diameter-based theories suggest. This paper addresses this discrepancy by introducing variance-aware regret bounds.

The Limitations of Global Metrics

The reliance on diameter $D$ assumes that the value function (or bias function) can fluctuate significantly across the entire state space. However, in many MDPs, the optimal bias function is relatively stable. Using $D$ as a proxy for this fluctuation is a blunt instrument.

Consider an environment with a high diameter but low local variance. Previous theories would predict slow learning (high regret), whereas empirical observations of algorithms using Kullback-Leibler (KL) divergence for confidence bounds show much better performance. The core challenge is to prove that regret scales with the smoothness of the environment—specifically, the local variance $\mathbf{V}^*_{s,a}$ of the bias function—rather than the global diameter.

The KL-UCRL Framework

The authors focus their analysis on KL-UCRL, an algorithm rooted in the "Optimism in the Face of Uncertainty" (OFU) principle. KL-UCRL maintains a set of plausible transition models and selects the one that maximizes the potential reward.

The key distinction of KL-UCRL lies in its use of KL-Confidence Sets. Unlike earlier algorithms that used $L_1$ norms to create "box-shaped" uncertainty regions, KL-UCRL uses KL-divergence to define "balls" of uncertainty around transition probability estimates. This geometric choice is crucial because KL-divergence naturally captures the local curvature of the probability space, making it inherently "variance-aware."

Variance-Aware Analysis via Transportation Lemmas

The primary technical contribution of this work is a new analytical framework for bounding regret. The authors develop novel variations of the Transportation Lemma, a mathematical tool that relates the KL-divergence between two distributions to the variance of a function under those distributions.

By applying these lemmas, the authors successfully decouple the concentration of transition estimates from the specific structure of the optimal bias function. This allows them to track how the local variance $\mathbf{V}^*_{s,a}$—defined as the variance of the next-state value function—impacts the regret. Since $\sqrt{\mathbf{V}^*_{s,a}} \le D$, a bound based on variance is guaranteed to be at least as tight as one based on diameter, and often significantly tighter.

Main Results

The paper provides both a new upper bound for KL-UCRL and a corresponding minimax lower bound.

Upper Bound

The authors prove that with high probability, the regret of KL-UCRL scales as: $$\tilde{O}\left(\sqrt{S \sum_{s,a} \mathbf{V}^*_{s,a} T} + D\sqrt{T}\right)$$ This represents a substantial improvement over the previous state-of-the-art bound of $O(DS\sqrt{AT})$. The new bound demonstrates that the dominant term in the regret depends on the cumulative local variance across states and actions, rather than the product of the diameter and the state-action space.

Lower Bound

To complement the upper bound, the authors establish a new minimax lower bound of $\Omega(\sqrt{S A \mathbf{V}_{max} T})$. This result indicates that their upper bound is nearly optimal, with only a $\sqrt{S}$ factor remaining as a gap for future reconciliation.

Empirical Evidence: RiverSwim

The theoretical findings were tested using a modified version of the RiverSwim MDP. In this benchmark, an agent must choose between swimming downstream (easy, low reward) or upstream (difficult, high reward). The authors utilized an "ergodic" version of RiverSwim to satisfy the mathematical requirements of their proof.

Numerical simulations confirmed the theoretical intuition: as the number of states in the environment increased, the "variance term" remained remarkably small compared to the "diameter term." For an instance with 100 states, the diameter-based metric was approximately 1988, while the variance-based metric was only 8.5. This orders-of-magnitude difference explains why KL-based algorithms excel in environments where traditional theory predicted failure.

Conclusion and Future Work

This research provides a more nuanced understanding of reinforcement learning in average-reward MDPs. By replacing global diameter with local variance, the authors have provided a theoretical framework that more accurately reflects the practical performance of RL algorithms.

However, several avenues for future work remain:

  1. Closing the $\sqrt{S}$ Gap: Reconciling the remaining difference between the upper and lower bounds.
  2. Broadening MDP Classes: While the current proof assumes ergodicity, extending the formal proof to all "communicating" MDPs is a priority.
  3. Computational Efficiency: KL-UCRL requires solving optimization problems over KL-balls during Extended Value Iteration, which is more computationally intensive than $L_1$-based methods.

Summary updated

BibTeX
@inproceedings{talebi2018variance,
  author = {Mohammad Sadegh Talebi and Odalric-Ambrym Maillard},
  title = {{Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs}},
  booktitle = {ALT},
  year = {2018},
  url = {https://openreview.net/forum?id=fMaPq-hs4NU},
}
Figure