Reinforcement learning (RL) operates under a profound dichotomy. On one side stands a rich body of control theory providing rigorous guarantees for convergence, sample efficiency, and bounded regret. On the other side stands modern deep RL, which achieves remarkable empirical success in high-dimensional environments using deep neural networks.
The bridge between these two worlds is fractured. Most foundational theoretical guarantees rely on the assumption of tabular Markov Decision Processes (MDPs) or linear function approximation. When practitioners swap these linear models for deep, non-linear neural networks, the mathematical guarantees typically vanish. This discrepancy is known as the non-linear function approximation gap. Understanding why this gap exists—and how researchers are attempting to close it—is essential for building provably stable, large-scale autonomous systems.
Why Theory Thrives in Linear Spaces
To understand why non-linear function approximation is difficult to analyze, we must first look at why linear models are so mathematically tractable. In a linear MDP, the transition dynamics and reward functions are assumed to be linear combinations of a known feature space. This structure preserves the contraction properties of Bellman operators, preventing errors from compounding exponentially over time.
For instance, in reward-agnostic navigation, Andrea Zanette et al. demonstrated that agents can efficiently explore environments without prior reward knowledge using linear value iteration (Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration). Similarly, frequentist regret bounds for randomized exploration algorithms, such as those derived by the authors for randomized least-squares value iteration, heavily depend on low-rank or linear transitions (Frequentist Regret Bounds for Randomized Least-Squares Value Iteration).
Linearity also simplifies policy optimization. Algorithms like Optimistic Proximal Policy Optimization (OPPO), proposed by Qi Cai et al., achieve near-optimal regret bounds under adversarial rewards by assuming linear state-action features (Provably Efficient Exploration in Policy Optimization). Even finite-sample analyses for foundational methods like Bellman Residual Minimization (Finite-sample Analysis of Bellman Residual Minimization by Odalric-Ambrym Maillard et al.) or actor-critic convergence (Actor-Critic Algorithms by Vijay R. Konda et al.) traditionally require linear function approximation for the critic to guarantee stability.
The Limits of Linearity in Practice
While linear architectures are mathematically well-behaved, they lack the capacity to represent complex real-world environments. As John E. Moody et al. noted when introducing Recurrent Reinforcement Learning for financial trading, linear models fail to capture the highly non-linear, path-dependent relationships inherent in macroeconomic data (Reinforcement Learning for Trading).
Beyond representational capacity, forcing linear assumptions onto non-linear environments can introduce severe algorithmic instability. For example, off-policy learning algorithms like Tree Backup and Retrace can outright diverge when combined with function approximation, a vulnerability highlighted by Ahmed Touati et al. (Convergent TREE BACKUP and RETRACE with Function Approximation). Similarly, Ruosong Wang et al. proved that reward-free exploration becomes exponentially difficult if the underlying environment transitions are non-linear, even if the optimal value function itself happens to be linear (On Reward-Free Reinforcement Learning with Linear Function Approximation).
The Theoretical Blind Spots of Deep RL
Because extending proofs to non-linear spaces is difficult, deep reinforcement learning operates largely on heuristics that lack rigorous mathematical guarantees.
Consider how modern libraries handle policy optimization. Shuang Wu et al. revealed that while practical RL implementations often contain mathematical discrepancies regarding discount factors, they succeed because experience replay re-aligns the gradients (Understanding Policy Gradient Algorithms: A Sensitivity-Based Approach). However, the authors note that these justifications rely on tabular assumptions; it remains unknown if they hold under the limited capacity of deep neural networks. Similarly, the complex, non-linear dynamics of experience replay buffers analyzed by Ruishan Liu et al. show that buffer size heavily impacts learning stability, yet exact analytical solutions remain out of reach for deep models (The Effects of Memory Replay in Reinforcement Learning).
This theoretical blind spot extends across multiple subfields of RL:
- Exploration and Finetuning: Converting abstract exploration bonuses into stable loss functions for neural networks remains an open challenge (Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning by Tengyang Xie et al.).
- Imitation and Apprenticeship Learning: Online imitation learning algorithms provide no-regret guarantees in tabular settings, but these proofs fail when confronted with the non-convex optimization landscapes of deep networks (Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction by Wen Sun et al.; Online Apprenticeship Learning by Lior Shani et al.).
- Policy Gradients and Smoothness: Global convergence proofs for policy gradient methods often rely on tabular representations or strict smoothness assumptions (Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings by Matthew S. Zhang et al.; On the Linear convergence of Natural Policy Gradient Algorithm by Sajad Khodadadian et al.).
- Robust Optimization: Deploying robust optimization techniques to handle transition uncertainty is computationally constrained by a lack of native support for neural network function approximation (Robust $\phi$-Divergence MDPs by Chin Pang Ho).
Escaping the Linear Constraint
To bridge this gap, recent work focuses on developing algorithms designed from the ground up to support non-linear function approximation mathematically.
One strategy is to reformulate the core RL objectives into optimization problems that bypass traditional tabular constraints. For instance, Bo Dai et al. introduced SBEED, an algorithm that reformulates the Bellman equation into a smoothed primal-dual optimization problem (SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation). By doing so, they bypassed the "double-sample" issue and provided rigorous convergence guarantees for non-linear function approximation in off-policy settings.
Another approach involves expanding convergence proofs to general parameterizations. Carlo Alfano developed the Approximate Mirror Policy Optimization (AMPO) framework, proving for the first time that policy-gradient-style methods can achieve linear convergence even when using general, non-linear function approximators (A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence).
Finally, researchers are analyzing neural networks directly rather than treating them as black boxes. Baihe Huang demonstrated that reinforcement learning with two-layer neural network function approximation can be proven sample-efficient (Going Beyond Linear RL: Sample Efficient Neural Function Approximation). Crucially, this work showed that sample complexity can scale with the algebraic dimension of the network rather than the size of the state space, providing a foundational step toward a complete theoretical understanding of deep reinforcement learning.