Provably Efficient Reinforcement Learning with General Value Function Approximation

Ruosong Wang, Ruslan Salakhutdinov, Lin F. YangarXiv 2020 · OpenReview

Introduction

Reinforcement Learning (RL) has achieved remarkable empirical milestones, particularly through the integration of deep neural networks for value function approximation. However, the theoretical understanding of these methods has historically been confined to tabular settings or linear function approximations. In tabular RL, regret bounds typically scale with the cardinality of the state space $|S|$, which is prohibitive in high-dimensional or continuous environments. While linear models offer a path forward, they require meticulously engineered features. This paper introduces $\mathcal{F}$-LSVI, a model-free Q-learning algorithm that provides the first provably efficient guarantees for general value function approximation, decoupling regret from state-space complexity.

Problem Formulation

The central challenge addressed is the design of an RL algorithm that is both statistically and computationally efficient without relying on restrictive assumptions about the environment's transition dynamics. Specifically, the authors seek to move beyond the "linear MDP" assumption, where transitions and rewards are linear functions of features. Instead, they consider a general function class $\mathcal{F}$ (e.g., neural networks) and aim for regret bounds that depend only on the intrinsic complexity of $\mathcal{F}$ and the planning horizon $H$.

The $\mathcal{F}$-LSVI Algorithm

The proposed algorithm, $\mathcal{F}$-LSVI (Least-Squares Value Iteration with function class $\mathcal{F}$), is built upon the principle of Optimism in the Face of Uncertainty (OFU). It consists of several critical components:

1. Least-Squares Value Iteration

At each iteration, the algorithm performs a least-squares optimization to find a function within $\mathcal{F}$ that best approximates the Bellman backup of the estimated value function from the subsequent time step.

2. Exploration via Stable Bonus Functions

To ensure adequate exploration of the state-action space, $\mathcal{F}$-LSVI incorporates a "bonus" term into the Q-value estimates. This bonus is derived from the "width" of a confidence region around the current function estimate, effectively incentivizing the agent to visit regions where the model's uncertainty is high.

3. Sensitivity Sampling

A significant technical innovation in this work is the use of sensitivity sampling (based on $\lambda$-sensitivity). In general function approximation, the complexity of maintaining a confidence region can grow uncontrollably as data accumulates. Sensitivity sampling acts as an importance-sampling mechanism that retains only the most "informative" state-action pairs. This reduces the computational burden while preserving the statistical validity of the optimism-based exploration.

Theoretical Contributions

The authors utilize two primary metrics to quantify the complexity of the function class $\mathcal{F}$:

  • Eluder Dimension ($d$): Unlike standard measures like VC-dimension, the eluder dimension captures the sequential nature of RL data, measuring how many observations are needed to effectively predict the value of a new point.
  • Log-Covering Numbers: Used to measure the "size" of the function class in terms of its capacity to approximate functions.

Bellman Completeness

The analysis assumes Bellman Completeness (Assumption 1), which posits that the function class $\mathcal{F}$ is closed under the Bellman operator. This ensures that the true optimal Q-function (or a close approximation) remains within the searchable space during the value iteration process.

Key Results

The primary result is a regret bound of $\tilde{O}(\text{poly}(dH)\sqrt{T})$, where $T$ is the total number of interactions.

  • State-Space Independence: The bound is notably independent of $|S|$, confirming that the algorithm's efficiency is governed by the complexity of the function class rather than the environment's size.
  • Robustness: The theory extends to misspecified settings, where the true value function lies outside $\mathcal{F}$. In such cases, the regret scales linearly with the approximation error, demonstrating the algorithm's practical robustness.

Discussion and Future Work

While $\mathcal{F}$-LSVI represents a major theoretical milestone, it relies on the existence of an ERM (Empirical Risk Minimization) oracle to solve the underlying least-squares problems. Implementing such oracles for non-convex classes like deep neural networks remains a practical challenge. Furthermore, the assumption of Bellman Completeness, while standard in literature, may only hold approximately in complex real-world tasks. Future research may focus on relaxing these assumptions or extending these provable guarantees to policy-based and actor-critic architectures.

Conclusion

By leveraging the eluder dimension and a novel sensitivity sampling technique, this work provides a rigorous foundation for RL with general value function approximation. It bridges the gap between the empirical power of deep RL and the statistical guarantees required for reliable and efficient learning in large-scale environments.

Summary updated

Abstract

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of general function approximation schemes largely remains missing. In this paper, we establish a provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class $\mathcal{F}$, our algorithm achieves a regret bound of $\widetilde{O}(\mathrm{poly}(dH)\sqrt{T})$ where $d$ is a complexity measure of $\mathcal{F}$ that depends on the eluder dimension [Russo and Van Roy, 2013] and log-covering numbers, $H$ is the planning horizon, and $T$ is the number interactions with the environment. Our theory generalizes recent progress on RL with linear value function approximation and does not make explicit assumptions on the model of the environment. Moreover, our algorithm is model-free and provides a framework to justify the effectiveness of algorithms used in practice.
BibTeX
@misc{wang2020provably,
  author = {Ruosong Wang and Ruslan Salakhutdinov and Lin F. Yang},
  title = {{Provably Efficient Reinforcement Learning with General Value Function Approximation}},
  year = {2020},
  eprint = {2005.10804},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.10804},
}
Figure