On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces

Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, Michael I. Jordan

Abstract

The classical theory of reinforcement learning (RL) has focused on tabular and linear representations of value functions. Further progress hinges on combining RL with modern function approximators such as kernel functions and deep neural networks, and indeed there have been many empirical successes that have exploited such combinations in large-scale applications. There are profound challenges, however, in developing a theory to support this enterprise, most notably the need to take into consideration the exploration-exploitation tradeoff at the core of RL in conjunction with the computational and statistical tradeoffs that arise in modern function-approximation-based learning systems. We approach these challenges by studying an optimistic modification of the least-squares value iteration algorithm, in the context of the action-value function represented by a kernel function or an overparameterized neural network. We establish both polynomial runtime complexity and polynomial sample complexity for this algorithm, without additional assumptions on the data-generating model. In particular, we prove that the algorithm incurs an $\tilde{\mathcal{O}}(\delta_{\mathcal{F}} H^2 \sqrt{T})$ regret, where $\delta_{\mathcal{F}}$ characterizes the intrinsic complexity of the function class $\mathcal{F}$, $H$ is the length of each episode, and $T$ is the total number of episodes. Our regret bounds are independent of the number of states, a result which exhibits clearly the benefit of function approximation in RL.

Introduction

Reinforcement learning (RL) has achieved remarkable empirical milestones in complex environments, from mastering board games like Go to navigating intricate digital worlds in StarCraft II. These successes are largely driven by the integration of deep neural networks to approximate value functions. However, the theoretical foundation for these methods has historically been limited to tabular settings—where states are discrete and few—or linear settings, where value functions are simple linear combinations of features.

In real-world applications, state spaces are often continuous or effectively infinite, rendering tabular methods obsolete. Furthermore, linear models often lack the expressive power to capture complex environment dynamics. The central challenge lies in balancing the exploration-exploitation tradeoff: how can an agent efficiently explore a massive state space using non-linear models without succumbing to the "curse of dimensionality"? This paper addresses this gap by providing a framework for RL with powerful non-linear approximators that is both computationally and statistically efficient.

Methodology: Optimistic Least-Squares Value Iteration

The authors propose two primary algorithms based on an optimistic version of Least-Squares Value Iteration (LSVI), utilizing the "Optimism in the Face of Uncertainty" (OFU) principle. This principle encourages the agent to explore unknown but potentially high-reward regions by acting as if the environment is as favorable as current data allows.

1. Kernelized Optimistic LSVI (KOVI)

KOVI is designed for scenarios where the value function resides in a Reproducing Kernel Hilbert Space (RKHS). It employs kernel ridge regression to estimate the value function and incorporates a Upper Confidence Bound (UCB) bonus term derived from Gaussian Process theory. This bonus term effectively guides exploration in uncertain areas of the state-action space.

2. Neural Optimistic LSVI (NOVI)

NOVI extends this framework to overparameterized two-layer neural networks. It leverages the Neural Tangent Kernel (NTK) framework, which demonstrates that sufficiently wide neural networks behave similarly to kernel methods during training. NOVI uses projected gradient descent for updates and constructs exploration bonuses based on the network's "tangent features."

Theoretical Guarantees and Key Results

The most significant contribution of this work is the proof that regret bounds can be entirely independent of the number of states. Instead, the regret depends on the intrinsic complexity of the function class $\mathcal{F}$, denoted as $\delta_{\mathcal{F}}$. This complexity is a function of the covering number and the effective dimension of the data.

Both KOVI and NOVI achieve sublinear regret, specifically $\tilde{\mathcal{O}}(\delta_{\mathcal{F}} H^2 \sqrt{T})$, ensuring that the agent's average performance converges to the optimal policy over time. The framework is "model-free," meaning it does not require explicit assumptions or learning of the environment's transition probabilities.

Regret bounds for various function classes under the proposed framework.

As shown in the table above, the framework provides concrete bounds for various kernel types. The learning rate is directly impacted by the "smoothness" of the kernel, with specific rates derived for finite spectrum, exponential decay, and polynomial decay kernels. Notably, the overparameterized neural network bound includes an additional term that vanishes as the network width $m$ increases.

Discussion and Limitations

While this work provides a rigorous bridge between deep learning and RL theory, several challenges remain:

  • Overparameterization: The NOVI results rely on the NTK regime, requiring extremely wide networks. Practical deep RL often utilizes narrower, deeper architectures where the NTK approximation may be less precise.
  • Bellman Completeness: The analysis assumes "Bellman closedness," meaning the function class is robust enough that applying the Bellman operator doesn't push the function outside the class. Relaxing this for misspecified models is a key area for future research.
  • Computational Resources: Although the runtime is polynomial, kernel methods can be memory-intensive due to the need to store and invert large matrices. Future iterations could benefit from "sketching" or other approximation techniques to enhance scalability.

In conclusion, this research establishes that provably efficient RL is possible with complex non-linear function approximation, offering a theoretical justification for the success of deep RL in large-scale applications.

Summary updated

Abstract

The classical theory of reinforcement learning (RL) has focused on tabular and linear representations of value functions. Further progress hinges on combining RL with modern function approximators such as kernel functions and deep neural networks, and indeed there have been many empirical successes that have exploited such combinations in large-scale applications. There are profound challenges, however, in developing a theory to support this enterprise, most notably the need to take into consideration the exploration-exploitation tradeoff at the core of RL in conjunction with the computational and statistical tradeoffs that arise in modern function-approximation-based learning systems. We approach these challenges by studying an optimistic modification of the least-squares value iteration algorithm, in the context of the action-value function represented by a kernel function or an overparameterized neural network. We establish both polynomial runtime complexity and polynomial sample complexity for this algorithm, without additional assumptions on the data-generating model. In particular, we prove that the algorithm incurs an $\tilde{\mathcal{O}}(\delta_{\mathcal{F}} H^2 \sqrt{T})$ regret, where $\delta_{\mathcal{F}}$ characterizes the intrinsic complexity of the function class $\mathcal{F}$, $H$ is the length of each episode, and $T$ is the total number of episodes. Our regret bounds are independent of the number of states, a result which exhibits clearly the benefit of function approximation in RL.
BibTeX
@misc{yang2020function,
  author = {Zhuoran Yang and Chi Jin and Zhaoran Wang and Mengdi Wang and Michael I. Jordan},
  title = {{On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces}},
  year = {2020},
  eprint = {2011.04622},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.04622},
}
Figure