Introduction
In the field of tabular reinforcement learning (RL), the Upper Confidence Bound for Reinforcement Learning (UCRL2) algorithm serves as a foundational approach for balancing exploration and exploitation in communicating Markov Decision Processes (MDPs). While UCRL2 has long been a benchmark for theoretical performance, its original regret bounds were often considered loose, particularly regarding their dependence on the MDP's diameter ($D$)—the maximum expected time required to travel between any two states.
This paper presents a refined theoretical analysis of UCRL2B, a variant of the original algorithm that utilizes Empirical Bernstein inequalities instead of Hoeffding bounds. By introducing advanced variance reduction techniques, the authors successfully tighten the regret bound, reducing the dependence on the diameter from linear ($D$) to square root ($\sqrt{D}$), bringing the algorithm closer to the minimax lower bounds.
The Problem: The Linear Diameter Gap
In communicating MDPs, the diameter $D$ is a critical parameter that characterizes the complexity of the environment. The original UCRL2 algorithm provides a regret bound that scales linearly with $D$ (specifically $\tilde{O}(D S \sqrt{A T})$). While subsequent research introduced UCRL2B to leverage the tighter concentration provided by Empirical Bernstein inequalities, the mathematical proofs supporting these algorithms often failed to translate that tighter concentration into a better dependence on $D$ in the leading term of the regret bound.
The primary challenge lies in the accumulation of variance over the time horizon $T$. Standard analytical techniques often result in loose bounds when summing transition probability errors, leading to a sub-optimal linear scaling with the diameter. This paper addresses this gap by re-evaluating the martingale analysis used to bound the algorithm's regret.
Methodology and Analytical Innovations
The authors focus their analysis on UCRL2B, which constructs confidence intervals based on sample variance. To achieve the tightened bound, they introduce three pivotal analytical improvements:
1. Application of Freedman’s Inequality
Traditional analyses often rely on Azuma’s inequality to bound Martingale Difference Sequences (MDS). However, Azuma’s inequality is relatively blunt as it does not account for the variance of the martingale. The authors instead employ Freedman’s inequality, which incorporates the variance of the process. This allows for significantly tighter bounds in scenarios where the variance is small, which is often the case as the agent gains more information about the MDP transitions.
2. Refined Summation Bounds
In the original UCRL2 proof, a loose application of Hölder’s inequality was used to bound the errors in transition probabilities. The authors replace this step with a more precise approach using the triangle inequality. This refinement prevents the overestimation of error terms that previously contributed to the linear $D$ dependence.
3. State-Dependent Bias Shifting
Perhaps the most critical innovation is the introduction of a dynamic variance reduction method. In standard proofs, the optimistic bias (or value function) is often shifted by a constant once per episode. The authors demonstrate that by shifting the bias by a different constant at every time step and for every visited state, they can prevent the theoretical variance terms from expanding uncontrollably. This "per-step" shifting is the mathematical mechanism that allows the diameter term $D$ to be moved inside the square root.
Key Results
The rigorous mathematical analysis culminates in a new regret bound for UCRL2B:
$$\tilde{O}(\sqrt{D \Gamma S A T})$$
Where:
- $D$: Diameter of the MDP
- $\Gamma$: Maximum number of reachable next states
- $S$: Number of states
- $A$: Number of actions
- $T$: Time horizon
This result represents a significant improvement over the original UCRL2 bound of $\tilde{O}(D S \sqrt{A T})$ and the previous UCRL2B analysis of $\tilde{O}(D \sqrt{\Gamma S A T})$. By reducing the diameter's influence to $\sqrt{D}$, the authors provide a much more optimistic and accurate theoretical guarantee for the algorithm's performance in large-scale environments.
Discussion and Limitations
While this paper marks a significant milestone in the theoretical analysis of RL algorithms, it is primarily a mathematical contribution. As a tutorial-style document for ALT 2019, it prioritizes the derivation of the bound over empirical validation. Consequently, there are no experimental results to show how these tighter bounds translate to practical performance improvements in simulated environments.
Furthermore, the analysis remains rooted in the concept of the MDP diameter. While improving the $D$ dependence is a major step forward, some modern RL theories suggest that bounds depending on the "optimal bias span" may be even more representative of true complexity than those depending on the diameter. Nevertheless, the variance reduction techniques introduced here—particularly the per-step bias shifting—provide a robust framework for future refinements in RL theory.
Summary updated