Bridging Neural Tangent Kernel Analysis and Reinforcement Learning for Deep Function Approximation

William St-Arnaud, Margarida Carvalho, Golnoosh FarnadiarXiv 2026 · arXiv

TL;DR

This paper bridges the gap between theoretical deep learning and practical reinforcement learning (RL) by extending Neural Tangent Kernel (NTK) analysis to handle time-varying mini-batches and temporal-difference (TD) targets. By deriving a closed-form solution for how value functions evolve during training, the authors create a "solver-augmented exploration" strategy that uses global optimization to find high-value states, significantly improving sample efficiency in sparse-reward environments.

What Problem Does This Paper Address?

While deep reinforcement learning (DRL) has achieved massive success, the internal "learning dynamics"—how and why a neural network changes its weights to represent a value function—remain a black box. In supervised learning, the Neural Tangent Kernel (NTK) has emerged as a powerful tool to describe these dynamics for infinitely wide networks.

However, RL presents two major hurdles for standard NTK theory:

  1. Non-stationary Targets: In RL, the "labels" (TD targets) change as the agent learns, unlike the fixed labels in supervised learning.
  2. Distribution Shift: RL agents use replay buffers and mini-batches, meaning the data distribution the network sees is constantly drifting.

The authors aim to provide a theoretical framework that accounts for these "messy" real-world RL training practices while leveraging the analytical power of the NTK.

Methods

The paper introduces two major innovations:

  1. Temporal-Difference Flow (TDF) Formulation: The authors extend the NTK gradient flow (which describes how network outputs change over time) to accommodate sequential mini-batches and moving TD targets. They derive a closed-form solution for the value function $Q_t$ in the infinite-width limit. This solution is "piecewise continuous," showing how the network's predictions evolve as it processes one batch after another.
  2. Solver-Augmented Exploration: Leveraging the fact that their NTK proxy is both smooth and strongly convex, the authors turn exploration into a mathematical programming problem. Instead of relying on random actions (like $\epsilon$-greedy) or local rollouts, they formulate a Mixed-Integer Nonlinear Programming (MINLP) problem. They use a global solver (Gurobi) to search the entire feasible state-action space for points that maximize the predicted Q-value or "surprise" (TD error), then add these specific points to the replay buffer.

Datasets

The authors evaluate their approach on a deterministic grid-world environment:

  • Minigrid DoorKey: A challenging environment where an agent must find a key, unlock a door, and reach a goal.
  • DenseDoorKey: A customized version introduced by the authors to alleviate extreme reward sparsity. It adds intermediate rewards for subgoals (picking up the key, unlocking the door) and uses Manhattan distance-based potential rewards to guide the agent.

Key Insights and Ideas

  • The Power of the Proxy: Even though we don't actually train infinitely wide networks, the closed-form NTK solution provides a highly accurate "analytical proxy." This allows researchers to study training stability and convergence without the noise of empirical black-box testing.
  • Stability through Scheduling: The authors found that training an NTK-based RL agent can be stabilized by using a decreasing time-increment schedule (similar to a learning rate decay in SGD) and periodically freezing target networks, mirroring successful empirical tricks like those used in DQN.
  • Global vs. Local Exploration: Traditional exploration is "local"—the agent wanders around its current position. By using a solver, the agent can "jump" to any valid state in the environment that the current model predicts will be highly informative, effectively "teleporting" its attention to where the learning signal is strongest.

Key Results

  • Theoretical Validation: The authors demonstrate that their TDF formulation produces stable, convergent learning behavior. As shown in their training loss plots, the Euclidean loss spikes when new data is introduced (due to distribution shift) but rapidly decays toward zero.
  • Performance Boost: In the 8x8 grid experiments, the solver-augmented version of Soft Q-Learning (SQN + solver) achieved a rollout score of 1.02, compared to 0.74 for standard SQN.
  • Sample Efficiency: The solver-augmented approach significantly improved the agent's ability to find and learn from profitable areas of the state-action space, leading to faster convergence than standard deep Q-learning baselines.

Limitations and Future Work

  • Deterministic Constraints: The current solver-augmented exploration relies on the environment being describable via mathematical constraints (e.g., grid coordinates, binary states). Extending this to high-dimensional visual inputs or stochastic environments remains a challenge.
  • Computational Overhead: While the solver calls are relatively fast (~0.1 seconds), solving complex MINLPs for every exploration step could become a bottleneck in more complex environments.
  • Future Directions: The authors suggest exploring how to better balance "diversity" (exploring new areas) with "high-value" targets (exploiting known good areas) within the solver framework, and investigating how "surprise" can be better modeled to guide the agent.

Summary updated

Abstract

Despite their widespread success across machine learning, the learning dynamics and generalization properties of neural networks remain poorly understood. The neural tangent kernel (NTK) provides an analytical characterization of the learning dynamics of infinitely wide neural networks and serves as a useful proxy for finite-width networks in supervised learning. In this work, we extend the NTK framework to reinforcement learning (RL) by introducing a temporal-difference (TD) flow formulation that accommodates time-varying mini-batches and TD targets, yielding a closed-form solution for value function evolution in an overparametrized setting. We also devise an optimization-based state-space exploration method that leverages the closed-form solution, coupled with constraints on the environment, to model the set of feasible states. On a deterministic grid environment, we validate that the proposed RL-based NTK formulation is indeed learning efficiently and adapting to the distribution shift in the training data distribution, and we demonstrate that the resulting exploration strategy improves sample efficiency. To our knowledge, this is the first work to extend NTK theory to characterize the learning dynamics of RL training with time-varying mini-batches and TD updates.
BibTeX
@misc{starnaud2026bridging,
  author = {William St-Arnaud and Margarida Carvalho and Golnoosh Farnadi},
  title = {{Bridging Neural Tangent Kernel Analysis and Reinforcement Learning for Deep Function Approximation}},
  year = {2026},
  eprint = {2611.03435},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03435},
}
Figure