Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation

Jiafan He, Dongruo Zhou, Quanquan Gu

In reinforcement learning (RL), success is traditionally measured using two primary metrics: Regret (the cumulative reward lost during learning) and PAC (Probably Approximately Correct) complexity (the number of samples required to find a "good enough" policy). However, neither of these metrics guarantees that an algorithm will eventually converge to the optimal policy. To address this fundamental limitation, researchers have introduced FLUTE, a novel algorithm for RL with linear function approximation that achieves Uniform-PAC guarantees—the gold standard for convergence in reinforcement learning.

The Problem: Why Standard Metrics Fall Short

When dealing with massive state spaces, RL agents rely on function approximation, such as linear models, to estimate action values. Current provably efficient algorithms for this setting typically offer one of two guarantees:

  1. Sublinear Regret: The agent makes fewer mistakes over time, but it may still make significant errors infinitely often.
  2. PAC Guarantees: The agent finds an $\epsilon$-optimal policy within a specific number of steps, but it might "forget" that policy or fail to improve as $\epsilon$ decreases.

Neither ensures true convergence to the best possible behavior. A Uniform-PAC guarantee is significantly stronger: it requires the algorithm to find an $\epsilon$-optimal policy for every possible $\epsilon$ simultaneously. This ensures the agent eventually stops making significant mistakes and remains optimal.

The Solution: FLUTE and Core Innovations

The authors propose two algorithms: UPAC-OFUL for the simpler contextual bandit setting, and FLUTE for full episodic RL in linear Markov Decision Processes (MDPs). The core innovation of FLUTE rests on two novel techniques designed to overcome the mathematical hurdles of standard confidence intervals:

  • Multi-level Partition Scheme: Standard algorithms aggregate all historical data into a single estimator. Over time, the noise in this estimator grows (manifesting as a $\log T$ term in the confidence radius), preventing strict convergence. FLUTE bypasses this "Log T trap" by partitioning historical data into different "levels" based on the samples' uncertainty or information gain. This effectively freezes the confidence radius for each level.
  • Minimax Value Function Estimator: Instead of relying on a single optimistic estimate of the reward, FLUTE maintains multiple estimators—one for each data level—and takes the minimum across them. Because each estimator is a valid upper bound on the true value, taking the minimum yields a tighter, more stable bound that facilitates uniform convergence.

Key Theoretical Results

As a purely theoretical work, the paper provides rigorous proofs for the sample complexity and efficiency of these algorithms, demonstrating that Uniform-PAC is achievable in high-dimensional spaces using linear function approximation:

  • Contextual Bandits (UPAC-OFUL): Achieves a sample complexity of $\tilde{O}(d^2/\epsilon^2)$, where $d$ is the feature dimension. This matches the performance of the well-known OFUL algorithm while adding the crucial convergence guarantee.
  • Linear MDPs (FLUTE): Achieves a sample complexity of $\tilde{O}(d^3H^5/\epsilon^2)$, where $H$ is the episode length.
  • Regret Matching: The Uniform-PAC guarantee acts as a "super-metric"—it automatically implies both a PAC bound and a high-probability regret bound. FLUTE yields a regret bound of $\tilde{O}(\sqrt{d^3H^4T})$, which is nearly identical to the state-of-the-art LSVI-UCB algorithm. This proves that achieving the stronger convergence guarantee does not require sacrificing learning efficiency.

Limitations and Future Directions

While FLUTE establishes a new theoretical benchmark, a few challenges remain. First, there is a small gap (a factor of $\sqrt{H}$) between FLUTE's regret and the absolute theoretical lower bounds, which might be closed in the future using variance-aware analysis. Second, maintaining multiple data levels and estimators introduces computational overhead, even though the number of levels only grows logarithmically ($O(\log K)$). Finally, the most significant open question is whether these Uniform-PAC results can be extended beyond linear models to general function approximation, such as the deep neural networks prevalent in modern Deep RL applications.

Summary updated

Abstract

We study reinforcement learning (RL) with linear function approximation. Existing algorithms for this problem only have high-probability regret and/or Probably Approximately Correct (PAC) sample complexity guarantees, which cannot guarantee the convergence to the optimal policy. In this paper, in order to overcome the limitation of existing algorithms, we propose a new algorithm called FLUTE, which enjoys uniform-PAC convergence to the optimal policy with high probability. The uniform-PAC guarantee is the strongest possible guarantee for reinforcement learning in the literature, which can directly imply both PAC and high probability regret bounds, making our algorithm superior to all existing algorithms with linear function approximation. At the core of our algorithm is a novel minimax value function estimator and a multi-level partition scheme to select the training samples from historical observations. Both of these techniques are new and of independent interest.
BibTeX
@inproceedings{he2021uniform,
  author = {Jiafan He and Dongruo Zhou and Quanquan Gu},
  title = {{Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=YotwCeG34E},
}
Figure