WorksComputer Science
Bridging Neural Tangent Kernel Analysis and Reinforcement Learning for Deep Function Approximation
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.
Introduction
In the context of reinforcement learning (RL), deep Q-learning marks an important milestone by demonstrating the ability of deep neural networks to learn complex policies [22]. Prior to its introduction, combining tabular methods like Q-learning with nonlinear function approximators was notoriously unstable and prone to divergence. Deep Q-Networks (DQN) resolve these instabilities by introducing experience replay to break temporal correlations and a periodically updated target network to stabilize parameter updates. Its major breakthrough on Atari 2600 games demonstrated that RL could scale directly to high-dimensional visual domains from raw pixels [21]. Nevertheless, DQN remains susceptible to certain pitfalls in various contexts, such as overestimation bias and sample inefficiency. To address the former, double DQN (DDQN) decouple action selection from value evaluation, using the online DQN to select the greedy action and the target DQN to evaluate its value during the online network’s parameter update.
In order to better understand how these algorithmic ideas stabilize optimization during training, one can study their training dynamics directly. Observing black-box network updates empirically is often uninformative, making analytical approaches like the neural tangent kernel (NTK) essential. The NTK is a valuable tool to study deep neural networks in simple settings, yet it normally rests on assumptions that are inconsistent with the common RL training framework. Specifically, it is very natural to update parameters using batches of data instead of computing the gradient over the full dataset. In addition, many learning algorithms feature distribution shifts when new data is introduced (e.g., off-policy RL algorithms).
In this work, our first theoretical contribution is to bridge the gap between classical NTK formulations and RL training introducing a temporal-difference (TD) flow formulation that accommodates time-varying mini-batches and TD targets. For overparameterized ReLU networks (i.e., in the infinite-width limit), we derive a closed-form solution governing value function evolution. On finite state-action spaces, this solution is both strongly convex and smooth. Second, on the practical side, we leverage these properties to formulate a mathematical program, enabling off-the-shelf optimization solvers to search the state-action space globally for high-value exploration targets in a single optimization step. Third, through computational experiments, we validate the proposed NTK formulation by showing that it produces convergent, stable learning behavior, and we demonstrate that our solver-augmented exploration framework substantially improves sample efficiency over standard deep Q-learning baselines.
Literature Review
Experience replay and mini-batch dynamics Replay buffers are used in deep Q-learning to help decorrelate temporal data. Existing methods for memory management rely on empirical tuning, heuristic transformations and statistical approximations over historical samples. We review a few key contributions on the use of replay buffers.
Fedus et al. [12] provide a detailed ablation study of experience replay (ER) in order to identify key properties that make it efficient. They show that increasing capacity of the replay buffer greatly improves performance in some tasks while not affecting others. Finally, they also characterize the importance of the replay ratio across various tasks. They formulate hypotheses and validate them to obtain general practical recommendations: 1) increasing capacity and decreasing the age of the oldest policy, and 2) using -step returns in an off-policy setting. Liu & Zou [19] analyze the properties of the replay buffer on solutions to simple ODEs derived from linear neural networks. They show that the amount of memory can substantially alter the performance of the algorithm and they also derive a regime where prioritized experience replay (PER) is harmful. Our proposed extension of the NTK to multiple mini-batches allows for a continuous-time equivalent of multi-batch training. It can be used to test the same hypotheses in overparameterized networks at a reduced computational cost. Importantly, we devise a solver-augmented exploration strategy that can select state-action pairs with high TD loss under the current model predictions. Contrary to PER, we do not replay tuples with high TD loss more often, and we treat the added data simply as a new addition to a dataset.
Fujita [13] extend random reshuffling (RR) of the dataset to experience replay and show that its theoretical advantages over with-replacement strategies translates to the RL case. Di-Castro et al. [10] analyze the theoretical properties of a stochastic process that is pushed in a replay buffer and sampled. Their analysis provides theoretical tools to prove the convergence of multiple replay-based algorithms. The random reshuffling idea can be analyzed using our closed-form solution with mini-batches. While the shuffling ensures that all instances in the buffer are used in training, regardless of the age of the policy used to retrieve them, significantly more weight is attributed to instances that appear multiple times. In a deterministic environment, this can be prevented by only storing unique instances in the buffer; we use this idea in our experiments, and we sample with replacement to satisfy typical SGD assumptions.
Isele & Cosgun [15] explore different selection strategies for experiences that are stored in the buffer. They compare methods that favour surprise, reward, training distribution matching, and state space coverage. They show that training distribution matching is consistently the best approach. However, they derive a case where state space coverage is the best approach. Zhao et al. [32] propose a diversity-based experience replay (DBER) algorithm to achieve state-of-the-art results in sparse result environments. Using the closed-form solution derived via the NTK, we instead use solver-augmented exploration of the state space to select states whose predicted TD loss is high. We note, however, that we can enforce diversity by introducing no-good cuts or hamming cuts to the optimization model that is fed to the solver.
Andrychowicz et al. [3] present a novel algorithm, hindsight experience replay (HER), to improve the sample efficiency of the experience-based algorithms for sparse rewards. The goal of a replayed example is modified post-hoc to obtain a stronger signal during learning. Crowder et al. [9] apply HER to PPO and demonstrate that it dramatically accelerates the learning. The same can be said of common on-policy learning algorithms on a tested predator-prey model. Kim et al. [17] introduce symmetric replay training (SRT) in the context of combinatorial optimization problems. Their methodology modifies common RL approaches such as PPO, and even GFlowNets, that seek to obtain high-reward samples. Given a high-reward sample, a symmetric trajectory is replayed uniformly at random. This corresponds to maximizing the entropy of the distribution of trajectories ending in a given state . On all tested approaches, they show improvement in the sample efficiency and overall obtained solutions in the travelling salesman problem (TSP). Finding symmetric trajectories can be computationally hard, and we instead rely on a solver-based approach that leverages the closed-form solution of the NTK in order to select state-action pairs that have high TD loss.
Neural Tangent Kernel Analysis in RL Prior RL applications use neural network approximators purely as analytical tools to derive asymptotic global bounds. Next, we revise these results and their relation to the NTK theory.
Xu & Gu [29] prove that deep Q-learning finds the optimal policy with a convergence rate if the network approximator is sufficiently overparameterized (explicitly, wide). Their proof does not rely on the i.i.d. assumption, but requires that the data is generated from an MDP. Qiu et al. [24] devise a provably sample and computationally efficient reward-free RL algorithm, making use of nonlinear kernel and neural function approximators for single-agent MDPs. They achieve polynomial sample complexity in for a -suboptimal policy. Chen et al. [7] show that neural networks trained with noisy gradient descent and weight regularization can exhibit kernel training behaviour. They also obtain generalization bounds using mean-field analysis. They show that kernel approaches, when trained with noisy gradient, can efficiently learn functions if the initial weight distribution is not too far from the optimal weight distribution leading to interpolation on the data.
Che et al. [6] provide a theoretical analysis of overparameterized linear networks in the context of TD-learning. The authors compare the learning dynamics of various approaches to TD-learning. The first uses the same set of parameters on both sides of the TD equation; the second freezes the right-hand side (i.e. the TD target) and updates the parameters on the left-hand side, periodically updating the target parameters to the latest network parameters. Under mild assumptions, TD-learning with periodic target updates is shown to converge to an optimal solution on the training dataset (offline learning). This work covers linear networks and does not extend to deep neural networks. The results that are provided for Q-learning are in the continuous control case, and while convergence in the parameter space is established, no bounds on the error are given. As a point of comparison in § 7, we demonstrate the stable learning dynamics of overparameterized deep neural networks under varying mini-batches of data.
Lyle et al. [20] apply the theory of kernel regression in the context of TD learning. Central to their results is a closed-form solution to the gradient flow of a kernel predictor under TD error. The authors argue that the value function evaluated on novel observations depends strongly on the training data, and that the minimization of large TD errors can have a significant interference effect. This observation runs contrary to the intuition that methods that generalize well exhibit weak interference. The gradient flow in the closed-form solution updates both the left-hand and right-hand sides of the TD equation simultaneously; in other words, the TD target does not rely on a frozen instance of the predictor.
St-Arnaud et al. [27] analyze the properties of the NTK in the lazy regime. They show that, contrary to prior beliefs, the NTK leads to non-trivial predictions. By studying the NTK of infinitely-wide deep ReLU networks, it can be inferred that its eigenvalues are bounded and strictly greater than zero. In the context of stochastic gradient descent analysis, this implies that infinitely-wide deep ReLU networks exhibit both smoothness and strong convexity during training. These two properties combine to yield desirable convergence properties in mini-batch training, when the full dataset is held constant. While it is in theory intractable to train truly overparameterized networks, the existence of a closed-form solution for infinitely-wide deep ReLU networks provides us with a proxy to these models. Moreover, we show in the experiments section how to accommodate the distribution shift in the RL setting when training an NTK model. This approach can also be applied to finite-width neural networks.
Active Exploration and State Space Optimization Eysenbach et al. [11] look at the intersection of RL and planning. They devise a planning algorithm based on the current value estimates. With the obtained goal in mind, they are able to use the RL agent’s policy to guide towards that goal. The planning algorithm is run on a graph-based abstraction of the state space obtained via exploration with a RL agent; nodes are derived from observations stored in the replay buffer. However, the current value estimates are given by a black-box and no additional information can be gained. By leveraging the NTK for infinitely-wide deep ReLU networks in our work, we gain access to a closed-form solution, facilitating novel approaches in planning and exploration.
In addition to training a Q-network to maximize cumulative rewards, Simmons-Edler et al. [26] train a second neural network whose value function is induce by an auxiliary reward function that is equal to the absolute temporal difference error of the first model. Both models select training data from a shared replay buffer and together, they form a an adversarial training framework where exploration is driven by state-action pairs that lead to high cumulative temporal difference error. Their approach performs comparably or outperforms most baselines on a variety of continuous control tasks. We apply the NTK to this adversarial setup, enabling us to study the learning dynamics in the context of overparameterized networks. The existence of a closed-form solution further allows us to enhance the adversarial exploration by way of constrained optimization problem solvers.
In summary, existing literature addresses mini-batch replay through empirical sample selection, uses NTK theory strictly for asymptotic proofs, and restricts active exploration to local graph rollouts. We bridge these domains by extending NTK gradient flow to sequential mini-batches and temporal difference targets. By leveraging the smoothness and strong convexity of the closed-form NTK proxy (St-Arnaud et al., [27]), we guarantee training stability by choose time increments appropriately, and we replace local exploration heuristics with a mathematical program that optimizes across the feasible state space in a single step.
Notation
In this section, we present the notation and definitions that will be useful for the rest of this article.
Consider an -layer fully connected neural network parameterized by , where . The input dimension is , and denotes the -dimensional sphere. Let be the input. For a scalar activation function applied component-wise, the forward pass is defined recursively for layers as:
where are the pre-activations, are the post-activations, and is the width of layer .
Definition 1. The function is defined as
Definition 2. Adopting the notation of Jacot et al. [16], the functions and are defined recursively with base cases and as
Definition 2 is a normalized version of the NTK limit kernel from Jacot et al. [16]. By abuse of notation, for any and matrix , refers to the component-wise application of the function to the matrix . Moreover, given a dataset , the data matrix is formed by stacking along its rows. This yields the kernel matrices and . For parameters , the notation refers to the parameters at time . When clear from the context, any time-dependent mathematical object with subscript refers to that object evaluated at time $t.
Mini-batch training with the NTK
The typical setting for training with the NTK, namely NTK regression, uses the same dataset over the full training horizon. By exploiting the closed-form solution to the gradient flow dynamics Jacot et al. [16]; ); Arora et al. [4], one can obtain the output formula for arbitrary time . Crucially, this solution implicitly assumes that the gradient is computed over the entire dataset simultaneously. However, practical neural network training updates parameters sequentially using batches of the dataset. Thus, when adapting this sequential updating procedure to its gradient flow equivalent, we can derive the output of an infinitely-wide neural network trained on successive data batches. Mathematically, given indices of dataset batches, where , we formalize the evolution of the model output via gradient flow and changing data batches in Definition 3.1
Definition 3. Given a time horizon and a batch of data where , we call a sequence of stopping times any sequence of real numbers such that the NTK at time evolves with respect to . Specifically, the dynamics of the gradient flow are given by
where are the target values over the batch .
In Section 5, we provide Proposition 1, which shows that in the infinite-width limit, the NTK (i.e. ) does not change when replacing data batches at fixed intervals. As in Definition 3, the dynamics evolve with respect to the latest batch , however the kernel function does not vary (i.e., is independent of ). Therefore, even with a constant kernel, the specific ordering and selection of data batches significantly influences the final output of the model at the end of the horizon (time ). We underline that while standard supervised mini-batch flow assumes fixed targets , RL introduces non-stationary TD targets by default. However, in alignment with common learning approaches, we fix the TD targets during training. We describe the resulting dynamics, which we refer to as the Temporal Difference Flow formulation, in Section 5 to extend the NTK framework to RL.
Extension to RL
A stated goal of our analysis of the NTK is to offer a more realistic proxy to neural network training in order to prototype, benchmark, or even understand various RL algorithms. Prior work focuses on a fixed dataset throughout training and the differential equation underlying the learning dynamics is taken to the infinite time limit. In practice, these assumptions are not met and to this end, we endeavour to adapt the NTK analysis to a setting with varying batches of data and a finite time training schedule. Meanwhile, a realistic proxy in the RL setting must incorporate the method by which TD targets are updated over time. In light of these requirements, we provide a differential equation and its corresponding solution that satisfies the sought-after framework.
This section details key aspects of the NTK in the context of RL. First, in the infinite-width regime, the kernel stays constant throughout training, as highlighted in Proposition 1. Second, the training dynamics follow a specific differential equation given by Definition 7, from which we obtain a closed-form solution in Theorem 1. Third, the kernel is shown to exhibit invertibility and induce certain smoothness properties in the training objective. Finally, we provide an iterative procedure to compute the closed-form solution of Theorem 1 for arbitrary inputs, and we analyze the computational cost derived from training with varying mini-batches and performing early stopping.
Preliminaries In the RL setting, we have to adapt the aforementioned sequential NTK framework to account for the different nature of the temporal difference objective that we optimize. In this work, we suppose that we have a deterministic environment. In other words, given a state and an action , we can compute the next state with probability 1. In contrast to the typical learning framework introduced in the previous section, the data points come in the form of tuples , where is the state prior to the action selection, is the action taken, is the state obtained by transitioning from after taking action , and is the corresponding reward depending on . We can relate this to the typical learning notation of data by setting and . Here, the vector corresponds to the features of the data point, and acts as the label. The value is the discount factor, while the parameterized action-value network is . Given a target network frozen at time , the objective is thus to minimize the Euclidean 2-norm error for : .
Constant NTK for RL Just as in the supervised setting, taking the infinite-width limit of these overparameterized networks allows us to recover a kernel formulation. Specifically, the NTK converges to a limiting kernel as the hidden layer widths go to infinity as shown next in Proposition 1.
Proposition 1. Let be such that with probability 1 for some and let be -Lipschitz. The kernel defined by
is bounded on in the limit . Moreover, it remains constant on the interval .
The proof of Proposition 1 follows a similar treatment as Theorem 2 in Jacot et al. [16] and is provided in Appendix A. Building upon Proposition 1, we show that given a sequence of mini-batches, it is possible to obtain a closed-form solution by following the gradient flow equation on each time interval.
Flow of the Q-value function Before formalizing the main statement of this section as Theorem 1, we introduce some useful definitions.
Definition 4 (Inner product space induced by ). Let for . The inner product space induced by is the space of functions such that
The notation refers to .
Definition 5. The function given a kernel on a dataset of size is defined by
where is any dual function with respect to the inner product space induced by the dataset .
Definition 6. Let for . Let be the neighbourhood of , i.e., the admissible states that can be reached in one step from , and define the function via
and define
over the dataset by abuse of notation.
With the function space and neighborhood mechanics in place, we can now define the exact dynamics of the network under our batch-trained NTK framework.
Definition 7 (Temporal difference flow equation (TDF)). Given a sequence of stopping times and for all , the solution to the flow equation for is given by
where and , is called a solution to the temporal difference flow equation (TDF).
By solving the equation in Definition 7, we obtain a closed-form solution that gives a proxy to the Q-value approximator of an overparameterized neural network in Theorem 1. In order to simplify notation in the Theorem, we first introduce the following definition:
Definition 8. We define the function as
Definition 8 is used to compute the closed-form solution of on a sub-interval via Theorem 1.
Theorem 1. Given a sequence of stopping times and , the function has a closed-form solution given by the solution to the TDF (Definition 7) on each interval for . Given and an invertible , the closed-form solution on is given by
where for all $t\geq 0.
The time refers to a prior batch where the target network was frozen (e.g., see Mnih et al. (2015)). The closed-form solution of Theorem 1 evolves with kernel on the interval . By comparison with the supervised learning setting, Theorem 1 follows similar training dynamics within each intervals ; in contrast, the evolution of the solution sews together various pieces in a non-smooth continuous path. In that sense, the solution to TDF is not a true gradient flow solution, but rather a right-derivative counterpart since the right-hand derivative of the solution exists at each discontinuity point , while it is in fact differentiable everywhere else. Below, we detail properties of the NTK that are useful in theoretical analysis.
Properties of . We can show that the continuous-time TD error is -smooth with respect to along any interval , with since the diagonal of consists of ones. It is also -strongly convex with respect to on that interval if the smallest eigenvalue of is . The following proposition (Proposition 2) states that for a depth , the NTK is a positive definite kernel. In particular, ReLU activation and fully-connected networks yield a closed-form solution that is strongly convex and smooth on each interval.
Proposition 2 (from Jacot et al. [16]). The NTK is positive definite with probability 1 for $L\geq 2.
Computation of closed-form solution When computing the closed-form solution in Theorem 1, by inspection of the equation we can compute by recursively compute are prior stopping times. This yields the following decomposition:
from which . The values are kept in memory as they are computed, and for a new batch of data, the values are computed for . Each new is used to compute the new term that is stored in memory. The time spent to compute is , where . This is much more efficient than training a deep neural network with extremely wide hidden layers, given the condition that their width is much larger than the number of data points in the replay buffer.2
Solver-augmented exploration
The analytical proxy for neural network training dynamics that is described in section 5 provides a concise mathematical tool that can be queried for insights into its predictions. Deterministic environments that are suitable to description via constraints pave the way to new avenues for exploration in RL; we exploit the solution from Theorem 1 and formulate a search problem to gather new states that are stored in a buffer for subsequent learning.
Our algorithmic approach searches for a solution , where is the set induced by constraints on the state-action space and the variable corresponds to the description of a state-action pair . In a grid world example, the variable can be decomposed into variables and : (for a grid of size ) models each possible cell content, with different cases equivalent to different integers, while indexes the different action scenarios. Constraints are introduced to ensure that describes a a valid state. Given , the objective is to find such that the estimate is maximized or minimized. This objective contributes to surprise whenever an optimal is not part of the buffer and the TD target of is not close to the estimate. In this case, the error is corrected during the next training step. We formulate the search problem , which is passed to a MINLP solver to find 3:
where the cost corresponds to the TD target under the sample with initial value . With , it is possible to recover a solution such that the Q-value is either maximized or minimized (). The random variable can also be replaced by its mean as is the case in section 7.
The closed-form estimate is a proxy for a single batch update as we take while holding the mini-batch constant for the interval , achieving perfect interpolation on the new mini-batch. Alternatively, we could model directly via the equation of Theorem 1 by introducing additional constraints for and the corresponding mini-batches . For simplicity and to make more compact, we focus on the first use case. We observe that is a convex function component-wise; we handle the nonconvex constraints using a mixed-integer nonlinear programming (MINLP) solver running a specialized branch-and-bound algorithm [28]. With the mathematical program now defined, we introduce Algorithm 1.
Using the output of Algorithm 1, we can augment the initial dataset to define a new generalizing function. Since at each iteration in the loop we augment the dataset with by selecting the point with the highest Q-value, we obtain a sequence of high predicted value candidates across the full set . When solving and once an optimal is found, the dataset can be extended with . If Algorithm 1 is run with , the final model would indeed interpolate perfectly the whole state space as . While conceivable in theory, this is practically not achievable. However, the model gains a certain amount of surprise from the procedure at each step, as it finds the believed to have highest value.
Algorithm 1 Solver-Augmented State-Space Exploration
Input: Dataset , small ,
Draw at random
Draw or case at random
for iterations do
Solve with
Recover and observe
if TD error is high then
end if
end for
return case
Since the condition number of can be high for large , it can be useful to make a change of variable with and rewrite the objective as after solving
and removing the constraint . Expression (1) only involves the variable and if the equation is solved beforehand, the changed objective is dependent only on 4, for which both lower and upper bounds exist. Therefore, spatial branch-and-bound techniques will be able to exploit the restricted domains in their search. This simplification comes at the cost of solving (1) for , which is via Cholesky decomposition for a dense matrix. There also exist alternatives like, GMRES-based iterative refinement [5] or using higher precision floating-point numbers, that return a solution to (1) with high precision when the condition number is large.
Experiments
In this section, we perform experiments to demonstrate the usefulness of our NTK-based approach to model common RL algorithms. We focus on deep Q-learning, the simplest buffer-based algorithm whose update is modelled directly by the TD flow of Definition 7, but our method extends to other buffer-based algorithms. Prior work has already compared NTK-based approaches with neural networks [27, 18, 30] and highlighted the similitudes and differences between the two. In order to bridge the divide, we endeavour to adjust the typical NTK framework to align more closely with empirical practice and study its behaviour directly. We divide the set of experiments along two axes. In the first axis, we study the effect of training on a sequence of mini-batches, rather than on a fixed dataset, where the mini-batches are drawn from a replay buffer whose contents drift as new data is collected. In the second axis, we study the sample efficiency of introducing a MINLP solver (Gurobi 13) that optimizes the closed-form NTK estimate of the Q-value in the exploration of the state-action space (i.e., Algorithm 1). All our experiments involve the deterministic environment DoorKey from the Minigrid library [8]. This choice of environment satisfies the assumptions of our closed-form solution, namely deterministic transitions and a finite state-action space; its combinatorial structure, where the goal is reachable only after picking up a key and unlocking a door, makes exploration nontrivial. In order to alleviate the issue of the reward sparsity, we implemented a customized version of the environment, DenseDoorKey, which introduces rewards for subgoals. Details are provided in Appendix § 10.
Training with minibatch sampling
To evaluate the learning capability of the NTK approach, we study the training loss (i.e. Euclidean loss) as a function of the number of training steps for a deep Q-learning-type algorithm on the DenseDoorKey environment, where the closed-form solution of Theorem 1 replaces the network as the action-value estimator.
In order to stabilize training, we collect new data and then hold the replay buffer fixed while performing mini-batch training steps, before resuming data collection; we repeat these two steps throughout training. The time increments for each batch are decreased using a typical stochastic gradient descent schedule with . When introducing fresh data, the schedule is restarted to prevent training collapse. Moreover, the target Q-values are kept frozen and updated periodically as in regular DQN. We plot the loss in Figure 1, where we observe that the training loss peaks after introducing new data, but that it quickly falls back to near-zero.

Figure 1. Training loss of the gradient flow equivalent to deep Q-learning (i.e. the NTK). Each iteration corresponds to a training step, i.e. the closed-form solution is updated via mini-batches selected from the fixed replay buffer.
The two-step process and the scheduling idea are inspired by regular SGD training, since on a fixed dataset (or batch), the Euclidean loss of the output induced by the NTK of dimension is both -smooth and -strongly convex for some . On a finite, yet large state-action space, each batch corresponds to a parameter and can be taken to be . Figure 1 shows that the Q-values are adapting to the TD targets.
Solver-augmented exploration
In this section, we take advantage of the closed-form solution of infinitely-wide deep ReLU networks to the exploration of the deterministic grid environment. Given that the DoorKey environment can be described by constraints and integer variables, we can use the solver-augmented exploration approach of § 6 to select state-action pairs with high value. We provide additional details in Appendix § 11. During the exploration of the state-action space, we call Algorithm 1 as a callback to obtain state-action pairs that are added to the replay buffer. We used Gurobi 13, leveraging its nonlinear mixed-integer solving capabilities. In order to evaluate the sample efficiency of this approach, we compare off-policy RL algorithms with and without solver callback. In addition to DQN, we use a softmax version of the Bellman operator when rolling out the policy. We refer to this approach as SQN. All algorithms use the standard hyperparameters from the stable_baselines3 codebase [25]. The solver is queried as a callback after each run of the exploratory policy. If a new state-action pair is discovered, it is added to the replay buffer and used in subsequent calls to the solver to build the internal mathematical model. We perform a total of 1000 learning steps and report the rollout policy score in Table 1. The rollout score is computed by evaluating total trajectory rewards using the learned policy.
| Algorithm | Rollout score |
| DQN | 0.0 (0.0) |
| DQN + solver | 0.10 (0.07) |
| SQN | 0.74 (0.24) |
| SQN + solver | 1.02 (0.22) |
Table 1. Average (std) rollout scores on various RL algorithms on 100 episodes in a grid.
In both cases, introducing the solver improves the rollout score. To complement Table 1, we compare policy evaluation curves of the best performing approach, SQN, with its solver-augmented version during rollouts in Figure 2. We used different training instances than in Table 1. We observe a steady increase in the performance as we perform more learning steps in both approaches, yet the addition of the solver improves the sample efficiency. While these results cannot be expected in all environments, the ability to search for high valued inputs can guide the exploration to new areas of the state-action space that are profitable. In addition, it becomes much easier to favour exploration by adding constraints that forbid the solver from returning state-action pairs it has already encountered (no-good cuts), or that force the next solution to differ from previous ones in a prescribed number of components (Hamming cuts). These constraints let us explore regions of far from the solutions previously found. In problem instances where diversity is key, this capability is especially useful.

Figure 2. Average rollout scores for SQN and SQN + solver after 1000 learning steps in a grid. The standard deviations are computed from 10 training runs for each method.
Conclusion
In this paper, we show how to apply the NTK to a reinforcement learning setting, allowing us to bridge the rich theory of overparameterized deep neural networks with off-policy learning algorithms like deep Q-learning. We demonstrate the ability to extend the NTK to varying batches of data that better align with the common practice of neural network training. Through the closed-form solution of infinitely-wide deep ReLU networks, we can also stabilize the training by satisfying typical convergence criteria in stochastic gradient descent, in combination with delayed data collection. Our approach serves as an introduction to the exploring the use of mini-batches and finite time evaluation in overparameterized neural networks. These ideas can be applied to other RL algorithms. As a future research direction, we highlight the possibility of understanding various buffer replay mechanisms and state exploration methodologies by studying the closed-form solution of the NTK. In addition, our solver-augmented exploration approach leaves a rich set of possibilities to be explored; it would be of particular interest to understand how to balance diversity with high value candidates during exploration. Moreover, a central idea is to understand how surprise affects the model predictions going forward.
Proof of Proposition 1
To prove Proposition 1, we require a generalized form of Grönwall’s lemma.
Lemma 1 (Generalized Grönwall’s lemma). Let and with . Suppose that
Then, satisfies
We can now prove Proposition 1. The proof strategy closely follows the proof of Theorem 2 from Jacot et al. [16] and we make use of implicit index summation to simplify notation.
Proof of Proposition 1. We prove the statement for and the extension to arbitrary depth follows by induction over layers. First, we have
where
The subnetwork NTKs are
We set
and we obtain the bounds
We set
From these last definitions, we obtain the bounds
We use these bounds to bound the derivative with
for some polynomial with positive coefficients. Observe that is stochastically bounded as . Using Lemma 1 and using the fact that is bounded and continuous over , we obtain uniformly bounded over . This implies that as , which in turn implies . The boundedness condition on implies that remains bounded on . To show that it remains constant, we study the derivatives :
and we derive bounds for the norms of and :
where . As , we conclude that both (2) and (3) converge to 0 because of the assumption . Finally, since is bounded, the same can be said of as .
DenseDoorKey Environment
In the DoorKey gridworld environment, an agent must reach a target state located behind a locked door, which requires first finding and picking up a key. A non-zero reward is obtained strictly upon reaching the final target state at terminal step , whereas all intermediate transitions () yield . To overcome this reward sparsity, we introduce a new reward function that targets subgoals. This is a common trick in RL and it has been demonstrated to help with sample efficiency [23]. In other cases, intrinsic rewards can also alleviate the sparse reward problem [31]. The subgoals the we introduce are: 1) picking up the key, and 2) unlocking the door, to which we attribute a reward of 0.2 and 0.4 respectively. In addition, we include intermediate rewards based on the Manhattan distance (): consider an agent in position who, after an action, transitions to position ; then, they obtain a reward equal to where is the position of the next immediate subgoal and . Note that these intermediary rewards are positive when the agent moves closer to and negative otherwise. The reward for reaching the terminal goal (green cell) is 1. We refer to the reader to Figure 3 for an illustration of the reward mechanism on a grid.

(a) (a) Initial grid potential =

(b) (b) Step toward = Key = =

(c) (c) Subgoal 1: Pickup Key

(d) (d) Subgoals 2: Unlock door
Figure 3. Sequence of rewards in the DenseDoorKey environment. The agent is represented in red. The agent receives incremental potential-based distance rewards towards active targets, along with sparse intermediate subgoal rewards upon picking up the key (+0.2), and unlocking the door (+0.4).
Mathematical model used by the solver
In reinforcement learning, active exploration traditionally relies on local, step-by-step environment rollouts or random trajectory sampling during training. In contrast, our mathematical optimization model reformulates active exploration as a global search problem over the environment’s state-action space. Our objective is to retrieve a high-value state by finding the corresponding grid and action. In this section, we detail the implementation of within the RL training procedure. In this section, we describe in detail how is implemented. Specifically, we detail for the Minigrid environment the constraints defining the set , and we also specify the explicit formulation of the constraints involving the kernel . To simplify notation, we let , where , and we let , where , . In our Minigrid environment, the grid dimensions are , where denotes the height and denotes the width.
Every Minigrid environment follows the convention that grids are tensors of shape . For any cell, the three values along the final dimension encode its object type, object colour, and state, respectively. For DoorKey grids, these values are mapped as follows:
object
colour
state .
Available actions follow the convention
turn left
turn right
move forward
pickup key
unlock door .
Grid constraints
For each grid cell and , we introduce a variable within
In simple words, these variables serve to describe the feature tuple of cell , where component denotes the object type, the object color, and the state..
We also introduce a variable for the available actions. We add big-M constraints to determine the door and key positions. We also introduce binary variables , for , indicating the presence of a door or key in cell , respectively. With these variables, we add constraints to ensure that there is one door and at most one key on the grid .
We fix the cell at position to be a green goal square. In other words,
We introduce the binary variables for to determine the agent’s position. In order to have only one agent on the grid, we add the constraint
To determine if each cell is empty, we introduce the variables for . We introduce the variables for to determine the presence of a wall. We note that DoorKey environments generate a separating wall containing a door at random between columns and . We introduce the constraints
(agent not on wall) to ensure the agent is not on a wall. The variables for correspond to the presence of a separating wall in column . The following constraints ensure 1) that there is one separating wall and 2) the separating wall consists only of wall cells or a door cell.
The agent orientation at cell is determined through variables , , , and . We further require constraints for to ensure that the agent is not on the key:
The following constraint ensure the agent is not on the goal:
The agent orientation variables can only be active if there is an agent on the same cell:
We also fix the boundary cells of the grid with , , . For each grid cell not on the boundary, we add two sets of constraints to determine its colour. The first set involves indices , corresponding to cells where the separating wall can lie:
The second set of constraints involves indices , where the separating wall cannot lie:
Finally, we introduce binary variables to model the door being open, closed, locked, and the key being carried. These variables are , , . For , we enforce the door to be in one of its three possible states if present in cell :
We introduce a constraint that enforces the door to be locked if the agent does not carry the key, and a second constraint that forces to agent to be on the left-hand side of the door if it is not open; if the door is open, the agent can be on the right-hand side of the door.
The second equation ensures that if the door is locked, the agent can only be found on the left-hand side of the separating wall. Otherwise, it is free to be on either side. The remaining grid constraints fix the state of the grid cells , i.e. a separating wall can be found:
and of the cells , i.e. outside the separating wall range of possible columns:
All the variables and constraints defined in this section form the variable vector and the constraint set appearing in .
Kernel constraints
In this section, we introduce the remaining variables and constraints derived from . The additional variables are
where variable corresponds to the variable in . We include constraint to model the data in :
and constraints to model the kernel:
The variables model the term in through the equations
where . We remark that the matrix is known beforehand and is therefore a matrix of coefficients. In addition, the variables model the arcsin terms in the definition of . This is achieve through the constraint type for variables and , where the relationship is enforced. Moreover, functions contain terms , which can lead to numerical issues when computing their derivative with respect to near or . Instead, we model these terms with constraints , since . The derivative of the cos function with respect to its input is bounded on its domain, thus numerically stable.
Additional Experimental Details
In our experiments, we train on a sequence of mini-batches . The default approach in RL is to train on data selected from the replay buffer uniformly at random, or through some prioritized replay mechanism. In these instances, the replay buffer data goes through a distribution shift. In our experiments, we noticed that by freezing exploration following the introduction of new data, we obtained a more stable training when we introduced decreasing time increments. This idea was motivated by the literature on stochastic gradient descent (SGD), where, given a fixed dataset, a schedule of decreasing learning rates guarantees convergence to a global minimum5 in the -smooth and -strongly convex setting [14]. Because our overparameterized networks satisfy these convergence assumptions, we could expect this behaviour on a fixed dataset if batches are selected uniformly at random. However, distribution shift breaks the uniformity assumption by giving more weight to tuples obtained via an older policy or a prioritized sampling. For this reason, we periodically collect new samples and between each data collection phase, we perform batch training through the closed-form solution to the TDF (Theorem 1). The training procedure is illustrated in Figure 4.
Figure 4. Piecewise continuous NTK gradient flow across mini-batch transitions. At each stopping time , mini-batch replacement causes a loss spike due to distribution shift, followed by exponential decay governed by the local strong convexity constant .
In addition to the optimization model described in Appendix § 11, we summarize the callback loop used during the solver-augmented exploration in Figure 5. While we made minimal use of diversity constraints (i.e. no-good cuts and hamming cuts), the solver-enhanced approach allows for further exploration of diversity-related ideas that are not available without the closed-form solution of the NTK. We compute the average running time of the solver callback procedure, i.e. the time to solve the optimization problem. The average time was 0.097 seconds with a standard deviation of 0.028 seconds.

Figure 5. Architecture of the solver-augmented exploration callback loop. The analytical NTK proxy constructs a smooth, strongly convex value landscape from buffer mini-batches. The MINLP solver optimizes over this landscape subject to No-Good cuts, identifying high-error state-action targets for environment rollouts.
Necessity of KKT conditions
In this section, we show that the KKT conditions for are necessary for a local optimum with respect to the primal variables (e.g., and ). We begin by providing the constraint qualification required in the proof of necessity [2].
Definition 9 (RCPLD). Denote the equality constraints with , and the inequality constraints , , and let be the set of constraints active at . The relaxed constant positive linear dependence (RCPLD) condition holds if there exists a neighbourhood for some such that 1) the set has constant rank for , and 2) for every basis of with index set and for any subset , the following
implication is satisfied:
Definition 9 [1] is a relaxed version of the CPLD constraint qualification introduced by Andreani et al. [1]. With Definition 9, we state the circumstances under which the KKT conditions are necessary for a local optimum in Theorem 2.
Theorem 2. For a primal variable of , let denote the corresponding variable value in a (feasible) local optimum. Suppose the following:
is such that and for all ;
for and that only if ;
so that is invertible.
Then, the local optimum satisfies the KKT conditions for some dual coefficients multiplying the equality and inequality constraints.
Proof. From the stationarity condition, we get that a linear combination of the gradients of the equality constraints and the active inequality constraints is equal to 0 only if the dual coefficients are all equal to 0, except (possibly) the dual coefficients of . However, corresponds to linear equalities and inequalities. A linear combination of an arbitrary subset of these gradients that is equal to 0 at leads to a linear combination that is equal to 0 at . Because of this fact, the rank of is constant for . We conclude that the constraints of satisfy RCPLD and that the KKT conditions are necessary for the local optimal solution.
In the statement of Theorem 2, the vectors , , are normalized with unit norm, but since the unnormalized version is homogeneous component-wise [16], the statement holds in the general sense by assuming the ’s and are not pairwise colinear. The proof of Theorem 2 also holds in the more general case where the constraints of are not linear; in this instance, one needs some regularity condition like quasi-normality constraint qualification. Theorem 2 guarantees that in a MIP approach to solving (e.g. a spatial branch-and-bound), the upper bound6 search in the root node is well-behaved when using first-order approximations. For example, primal-dual interior point solvers like IPOPT will converge to stationary points (local minimum or maximum, saddle point) that are feasible, and any local optimum will satisfy the KKT conditions. As shown in Corollary 1, the first-order necessary condition extends to any local node in a MIP approach whenever the depth and the size of the dataset are large enough compared to the number of variables required to model the state space.
Corollary 1. Under the same assumptions as Theorem 2, and if we propagate the bounds of variable , a local node will also satisfy RCPLD whenever
where is the length of variable and is the number of equality constraints in .
Proof. The gradients for induce a cone , while the gradients for induce a subspace . We suppose and we observe that
For vector subspaces and ,
Therefore, subspace (4) has dimension strictly greater than zero if
where is the section of indexed by variable . Given our initial assumption, RCPLD is satisfied in a neighbourhood of .
References
- [1]R Andreani, JM Martínez, and ML Schuverdт. On the relation between constant positive linear dependence condition and quasimonotonicity constraint qualification. Journal of optimization theory and applications, 125(2):473–483, 2005.DOI
- [2]Roberto Andreani, Gabriel Haeser, María Laura Schuverdt, and Paulo JS Silva. A relaxed constant positive linear dependence constraint qualification and applications. Mathematical Programming, 135(1):255–273, 2012.DOI
- [3]Marcin Andrychowicz, Dwight Crow, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Joshua Tobin, P. Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Neural Information Processing Systems, 2017. URL https://api.semanticscholar.org/CorpusID:3532908.arxiv.org/abs/1707.01495
- [4]Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019.arxiv.org/abs/1904.11955
- [5]Erin Carson and Nicholas J Higham. Accelerating the solution of linear systems by iterative refinement in three precisions. SIAM Journal on Scientific Computing, 40(2):A817–A847, 2018.DOI
- [6]Fengdi Che, Chenjun Xiao, Jincheng Mei, Bo Dai, Ramki Gummadi, Oscar A Ramirez, Christopher K Harris, A. Rupam Mahmood, and Dale Schuurmans. Target networks and over-parameterization stabilize off-policy bootstrapping with function approximation. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 6372–6396. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/che24a.html.arxiv.org/abs/2405.21043
- [7]Zixiang Chen, Yuan Cao, Quanquan Gu, and Tong Zhang. A generalized neural tangent kernel analysis for two-layer neural networks. Advances in Neural Information Processing Systems, 33:13363–13373, 2020.arxiv.org/abs/2002.04026
- [8]Maxime Chevalier-Boisvert, Bolun Dai, Mark Towers, Rodrigo Perez-Vicente, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry. Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. In Advances in Neural Information Processing Systems 36, New Orleans, LA, USA, December 2023.
- [9]Douglas C Crowder, Darrien M McKenzie, Matthew L Trappett, and Frances S Chance. Hindsight experience replay accelerates proximal policy optimization. arXiv preprint arXiv:2410.22524, 2024.arxiv.org/abs/2410.22524
- [10]Shirli Di-Castro, Shie Mannor, and Dotan Di Castro. Analysis of stochastic processes through replay buffers. In International Conference on Machine Learning, pp. 5039–5060. PMLR, 2022.
- [11]Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. Advances in neural information processing systems, 32, 2019.arxiv.org/abs/1906.05253
- [12]William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. In International conference on machine learning, pp. 3061–3071. PMLR, 2020.arxiv.org/abs/2007.06700
- [13]Yasuhiro Fujita. Experience replay with random reshuffling. arXiv preprint arXiv:2503.02269, 2025.arxiv.org/abs/2503.02269
- [14]Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023.arxiv.org/abs/2301.11235
- [15]David Isele and Akinsek Cosgun. Selective experience replay for lifelong learning. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi: 10.1609/aaai.v32i1.11595. URL https://ojs.aaai.org/index.php/AAAI/article/view/11595.DOI
- [16]Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.arxiv.org/abs/1806.07572
- [17]Hyeonah Kim, Minsu Kim, Sungsoo Ahn, and Jinkyoо Park. Symmetric replay training: Enhancing sample efficiency in deep reinforcement learning for combinatorial optimization. International Conference on Machine Learning, pp. 24110–24136, 2024.arxiv.org/abs/2306.01276
- [18]Jaehoon Lee, Sam S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks:an empirical study. In NeurIPS 2020, 2020. URL https://arxiv.org/abs/2007.15801.
- [19]Ruishan Liu and James Zou. The effects of memory replay in reinforcement learning. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 478–485, 2018. doi: 10.1109/ALLERTON.2018.8636075.DOI
- [20]Clare Lyle, Mark Rowland, Will Dabney, Marta Kwiatkowska, and Yarin Gal. Learning dynamics and generalization in deep reinforcement learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 14560–14581. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/v162/lyle22a.html.arxiv.org/abs/2206.02126
- [21]Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.arxiv.org/abs/1312.5602
- [22]Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529–533, 2015.DOI
- [23]Takato Okudo and Seiji Yamada. Reward shaping with dynamic trajectory aggregation. In 2021 International Joint Conference on Neural Networks (IJCNN), pp. 1–9, 2021. doi: 10.1109/ijcnn52387.2021.9533401.DOI
- [24]Shuang Qiu, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. On reward-free RL with kernel and neural function approximations: Single-agent MDP and Markov game. In International Conference on Machine Learning, pp. 8737–8747. PMLR, 2021.arxiv.org/abs/2110.09771
- [25]Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1–8, 2021. URL https://jmlr.org/papers/v22/20-1364.html.
- [26]Riley Simmons-Edler, Ben Eisner, Daniel Yang, Anthony Bisulco, Eric Mitchell, Sebastian Seung, and Daniel Lee. Reward prediction error as an exploration objective in deep rl. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 2816–2823. International Joint Conferences on Artificial Intelligence Organization, 7 2020. doi: 10.24963/ijcai.2020/390. URL https://doi.org/10.24963/ijcai.2020/390. Main track.
- [27]William St-Arnaud, Margarida Carvalho, and Golnoosh Farhadi. Revisiting the neural tangent kernel: the role of large width and depth. arXiv preprint arXiv:2511.07772, 2025.
- [28]Stefan Vigerske and Ambros Gleixner. SCIP: Global optimization of mixed-integer nonlinear programs in a building block architecture. Optimization Methods and Software, 33(3):563–593, 2018. doi: 10.1080/10556788.2017.1335312.
- [29]Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function approximation. In International conference on machine learning, pp. 10555–10565. PMLR, 2020.arxiv.org/abs/1912.04511
- [30]Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approximation in reinforcement learning: optimism in the face of large state spaces. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pp. 13903–13916, 2020.arxiv.org/abs/2011.04622
- [31]Mingqi Yuan, Bo Li, Xin Jin, and Wenjun Zeng. Automatic intrinsic reward shaping for exploration in deep reinforcement learning. In The Fortieth International Conference on Machine Learning (ICML), 2023. doi: 10.48550/arxiv.2301.10886. URL https://arxiv.org/abs/2301.10886.
- [32]Kaiyan Zhao, Yiming Wang, Yuyang Chen, Yan Li, Xiaoguang Niu, et al. Efficient diversity-based experience replay for deep reinforcement learning. arXiv preprint arXiv:2410.20487, 2024.arxiv.org/abs/2410.20487
