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
Traditional reinforcement learning theory has historically been confined to "tabular" settings, where state and action spaces are small enough to be enumerated. However, modern applications like robotics or complex games involve massive or continuous state spaces, necessitating the use of function approximation. While practitioners have seen immense success with Deep Q-Learning and other neural-based methods, a rigorous theoretical understanding of how to perform efficient exploration in these nonlinear settings has remained elusive. Most existing guarantees are restricted to linear models or require strong assumptions about environment dynamics.
This work bridges the gap between empirical success and theoretical rigor by introducing a framework for provably efficient RL using general nonlinear function approximators, specifically kernels and deep neural networks.
The Optimistic LSVI Framework
The authors propose an Optimistic Least-Squares Value Iteration (LSVI) framework grounded in the "Optimism in the Face of Uncertainty" principle. By augmenting the classical least-squares objective with a Upper Confidence Bound (UCB) bonus, the agent is incentivized to explore state-action pairs where the value function estimate is uncertain.
Kernelized Optimistic LSVI (KOVI)
KOVI utilizes Reproducing Kernel Hilbert Spaces (RKHS) to represent the action-value function. The exploration bonus is derived from the posterior variance of a Gaussian process, effectively quantifying the "novelty" of a state relative to the kernel's feature mapping.
Neural Optimistic LSVI (NOVI)
NOVI extends this logic to overparameterized neural networks. By leveraging Neural Tangent Kernel (NTK) theory, the authors demonstrate that a sufficiently wide neural network behaves similarly to a linear model in a high-dimensional feature space defined by the network's gradients (tangent features). This allows for the construction of a UCB bonus based on these gradients, enabling efficient exploration in deep architectures.
Theoretical Insights
A central contribution of this research is the shift from state-dependent complexity to function-class complexity. The difficulty of learning is shown to depend not on the number of states ($S$), which may be infinite, but on the intrinsic complexity of the function class $\mathcal{F}$, denoted as $\delta_{\mathcal{F}}$. This explains why RL can succeed in continuous environments where tabular methods fail.
Furthermore, the analysis relies on Bellman Completeness, the assumption that the chosen function class is closed under the Bellman operator. This ensures that if the true value function resides within the function class, the results of iterative look-ahead steps remain representable by that same class.
Regret Analysis and Results
The primary theoretical result is that both KOVI and NOVI achieve a regret bound of $\tilde{O}(\delta_F H^2 \sqrt{T})$. This regret is sublinear in the number of episodes $T$, ensuring that the agent's policy converges toward optimality over time.
As detailed in the table above, the specific bounds vary depending on the decay properties of the kernel's spectrum (finite, exponential, or polynomial). Notably, for overparameterized neural networks, the regret includes an additional term that vanishes as the network width $m$ increases, confirming that wider networks provide better approximations of the underlying linear-like tangent space.
Limitations and Future Work
While this work provides a landmark theoretical foundation, several challenges remain:
- Overparameterization Requirements: The current theory for NOVI requires networks to be extremely wide (polynomial in $T$ and $H$), exceeding the widths typically used in practical applications.
- Computational Oracles: The neural setting assumes the existence of an optimization oracle capable of finding global minima, a task that is practically addressed by gradient descent but remains a theoretical hurdle.
- Model Misspecification: Future research is needed to address "agnostic" settings where the Bellman completeness assumption may be violated, reflecting the model misspecification often encountered in real-world deployments.
Summary updated