betaFeedback

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 nn-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 xx. 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 O(1T)O\left(\frac{1}{\sqrt{T}}\right) 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 1ϵ2\frac{1}{\epsilon^{2}} for a ϵ\epsilon-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 CC 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 LL-layer fully connected neural network parameterized by θ={W(l)}l=0L−1\theta= \{W^{(l)}\}_{l=0}^{L-1}, where W(l)∈Rnl+1×nlW^{(l)} \in\mathbb{R}^{n_{l+1} \times n_l}. The input dimension is n0n_0, and Sn0−1S^{n_0-1} denotes the n0n_0-dimensional sphere. Let α(0)=x\alpha^{(0)} = x be the input. For a scalar activation function σ:R→R\sigma: \mathbb{R} \to\mathbb{R} applied component-wise, the forward pass is defined recursively for layers l∈{1,…,L}l \in\{1,\ldots,L\} as:

α~(l)=1nl−1W(l−1)α(l−1),α(l)=σ(α~(l))\widetilde{\alpha}^{(l)} = \frac{1}{\sqrt{n_{l-1}}}W^{(l-1)}\alpha^{(l-1)}, \qquad\alpha^{(l)} = \sigma\left(\widetilde{\alpha}^{(l)}\right)

where α~(l)\widetilde{\alpha}^{(l)} are the pre-activations, α(l)\alpha^{(l)} are the post-activations, and nln_l is the width of layer ll.

Definition 1. The function h:[−1,1]→Rh : [-1,1] \to\mathbb{R} is defined as

h(x)=xarcsin⁡(x)+1−x2π+x2.h(x) = \frac{x\arcsin(x) + \sqrt{1-x^2}}{\pi} + \frac{x}{2}.

Definition 2. Adopting the notation of Jacot et al. [16], the functions Θ∞(l):[−1,1]→R\Theta_{\infty}^{(l)} : [-1,1] \to\mathbb{R} and ρ(L):[−1,1]→R\rho^{(L)} : [-1,1] \to\mathbb{R} are defined recursively with base cases ρ(1)(x)=x\rho^{(1)}(x) = x and Θ∞(1)(x)=x\Theta_{\infty}^{(1)}(x) = x as

ρ(l)(x)=h(ρ(l−1)(x))\rho^{(l)}(x) = h\left(\rho^{(l-1)}(x)\right)
Θ∞(l)(x)=l−1lh′(ρ(l−1)(x))Θ∞(l−1)(x)+1lρ(l)(x).\Theta_{\infty}^{(l)}(x) = \frac{l-1}{l}h'\left(\rho^{(l-1)}(x)\right)\Theta_{\infty}^{(l-1)}(x) + \frac{1}{l}\rho^{(l)}(x).

Definition 2 is a normalized version of the NTK limit kernel from Jacot et al. [16]. By abuse of notation, for any g:[−1,1]→Rg : [-1,1] \to\mathbb{R} and m×nm \times n matrix AA, g(A)g(A) refers to the component-wise application of the function gg to the matrix AA. Moreover, given a dataset {xi∈Sn0−1}i=1n\{x_i \in S^{n_0-1}\}_{i=1}^n, the data matrix X∈Rn×n0X \in\mathbb{R}^{n \times n_0} is formed by stacking xiTx_i^\mathsf{T} along its rows. This yields the kernel matrices ρ(l)(XXT)\rho^{(l)}(XX^\mathsf{T}) and Θ∞(l)(XXT)\Theta_{\infty}^{(l)}(XX^\mathsf{T}). For parameters θ={W(l)}l=0L−1\theta= \{W^{(l)}\}_{l=0}^{L-1}, the notation θt\theta_t refers to the parameters at time t≥0t \ge0. When clear from the context, any time-dependent mathematical object with subscript tt 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 tt. 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 b∈{1,…,B}b \in\{1,\ldots,B\} of dataset batches, where B∈NB \in\mathbb{N}, we formalize the evolution of the model output ftf_t via gradient flow and changing data batches in Definition 3.1

Definition 3. Given a time horizon T∈R>0T \in\mathbb{R}_{>0} and a batch of data {X(b)}b∈[B]\{X^{(b)}\}_{b\in[B]} where [B]={1,…,B}[B] = \{1,\ldots,B\}, we call a sequence of stopping times any sequence of real numbers 0=t1<⋯<tB=T0 = t_1 < \cdots< t_B = T such that the NTK at time t∈[tb,tb+1[,b∈[B−1]t \in[t_b,t_{b+1}[, b \in[B-1] evolves with respect to X(b)X^{(b)}. Specifically, the dynamics of the gradient flow are given by

∂tft(x)=−Θ∞(L)(x⊤X(b)⊤)(ft(X(b))−y∗(X(b))),\partial_t f_t(x) = -\Theta_{\infty}^{(L)}\left(x^\top X^{(b)\top}\right)\left(f_t\left(X^{(b)}\right)-y^*\left(X^{(b)}\right)\right),
t∈[tb,tb+1[,b∈[B−1]t \in[t_b,t_{b+1}[, b \in[B-1]

where y∗(X(b))y^*\left(X^{(b)}\right) are the target values over the batch X(b)X^{(b)}.

In Section 5, we provide Proposition 1, which shows that in the infinite-width limit, the NTK (i.e. Θ∞(L)\Theta_{\infty}^{(L)}) does not change when replacing data batches at fixed intervals. As in Definition 3, the dynamics evolve with respect to the latest batch X(b)X^{(b)}, however the kernel function Θt(L)\Theta_t^{(L)} does not vary (i.e., is independent of tt). 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 TT). We underline that while standard supervised mini-batch flow assumes fixed targets y∗y^*, 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 ss and an action aa, we can compute the next state s′s' with probability 1. In contrast to the typical learning framework introduced in the previous section, the data points come in the form of tuples (s,a,s′,r)(s,a,s',r), where ss is the state prior to the action selection, aa is the action taken, s′s' is the state obtained by transitioning from ss after taking action aa, and rr is the corresponding reward depending on (s,a)(s,a). We can relate this to the typical learning notation of data (x,y)(x,y) by setting x=(s,a)x=(s,a) and y=ry=r. Here, the vector xx corresponds to the features of the data point, and yy acts as the label. The value γ∈]0,1]\gamma\in]0,1] is the discount factor, while the parameterized action-value network is QθtQ_{\theta_t}. Given a target network frozen at time t^\hat{t}, the objective is thus to minimize the Euclidean 2-norm error for t≥t^t \ge\hat{t}: ∥Qθt(s,a)−r(s,a)−γmax⁡a′Qθt^(s′,a′)∥22\left\|Q_{\theta_t}(s,a)-r(s,a)-\gamma\max_{a'}Q_{\theta_{\hat{t}}}(s',a')\right\|_2^2.

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 dt:Rn0→RnLd_t:\mathbb{R}^{n_0}\to\mathbb{R}^{n_L} be such that ∫0T∥dt∥X<∞\int_0^T\|d_t\|_X<\infty with probability 1 for some T>0T>0 and let σ\sigma be cc-Lipschitz. The kernel Θt(L)\Theta_t^{(L)} defined by

Θt(L)(x,x′)=∇θtQθt(x)⊤∇θtQθt(x′)\Theta_t^{(L)}(x,x')=\nabla_{\theta_t}Q_{\theta_t}(x)^\top\nabla_{\theta_t}Q_{\theta_t}(x')

is bounded on [0,T][0,T] in the limit n1,…,nL−1→∞n_1,\ldots,n_{L-1}\to\infty. Moreover, it remains constant on the interval [0,T][0,T].

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 XX). Let Xi,⋅=xi⊤X_{i,\cdot}=x_i^\top for i=1,…,ni=1,\ldots,n. The inner product space induced by XX is the space of functions Rn0→RnL\mathbb{R}^{n_0}\to\mathbb{R}^{n_L} such that

⟨f,g⟩=1n∑i=1nf(xi)⊤g(xi).\langle f,g\rangle=\frac{1}{n}\sum_{i=1}^{n}f(x_i)^\top g(x_i).

The notation ∥f∥X\|f\|_X refers to ⟨f,f⟩\sqrt{\langle f,f\rangle}.

Definition 5. The function Φκ\Phi_\kappa given a kernel κ:Rn0×n0→RnL\kappa:\mathbb{R}^{n_0\times n_0}\to\mathbb{R}^{n_L} on a dataset XX of size nn is defined by

Φκ(δ):=δ(κ(x,⋅)),\Phi_\kappa(\delta):=\delta(\kappa(x,\cdot)),

where δ\delta is any dual function with respect to the inner product space induced by the dataset XX.

Definition 6. Let Xi,⋅=xi⊤X_{i,\cdot}=x_i^\top for i=1,…,ni=1,\ldots,n. Let N(x)\mathcal{N}(x) be the neighbourhood of xx, i.e., the admissible states that can be reached in one step from xx, and define the function μt(x)∈N(x)\mu_t(x)\in\mathcal{N}(x) via

μt(x)=arg⁡max⁡x′∈N(x)Qt(x′)\mu_t(x)=\mathop{\arg\max}_{x'\in\mathcal{N}(x)}Q_t(x')

and define

μt(X)i=μt(xi)\mu_t(X)_i=\mu_t(x_i)

over the dataset XX 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 {t1,…,tB}\{t_1,\ldots,t_B\} and t^b∈{t1,…,tb}\hat{t}_b\in\{t_1,\ldots,t_b\} for all b∈[B−1]b\in[B-1], the solution QtQ_t to the flow equation for t∈[tb,tb+1[t\in[t_b,t_{b+1}[ is given by

∂tQt(x)=−(ΦΘt^b(L)(δt)),\partial_t Q_t(x)=-\left(\Phi_{\Theta_{\hat{t}_b}^{(L)}}(\delta_t)\right),

where δt=⟨dt,⋅⟩\delta_t=\langle d_t,\cdot\rangle and dt=Qt(X(b))−γQt^b∘μt^b(X(b))−R(X(b))d_t=Q_t(X^{(b)})-\gamma Q_{\hat{t}_b}\circ\mu_{\hat{t}_b}(X^{(b)})-R(X^{(b)}), 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 Λs,t(L):Rn×n0→Rn×n\Lambda_{s,t}^{(L)} : \mathbb{R}^{n \times n_0} \to\mathbb{R}^{n \times n} as

Λs,t(L)(X)=(exp⁡(−(t−s)Θs(L)(XXT))−In).\Lambda_{s,t}^{(L)}(X) = \left(\exp\left(-(t-s)\Theta_s^{(L)}\left(XX^{\mathsf{T}}\right)\right)-I_n\right).

Definition 8 is used to compute the closed-form solution of QtQ_t on a sub-interval [tb,tb+1[[t_b,t_{b+1}[ via Theorem 1.

Theorem 1. Given a sequence of stopping times {t1,…,tB}\{t_1,\ldots,t_B\} and Q0Q_0, the function QtQ_t has a closed-form solution Rn0→R\mathbb{R}^{n_0}\to\mathbb{R} given by the solution to the TDF (Definition 7) on each interval [ti,ti+1[[t_i,t_{i+1}[ for i∈[B−1]i\in[B-1]. Given t^b∈{t1,…,tb}\hat{t}_b\in\{t_1,\ldots,t_b\} and an invertible Θ∞(L)(XXT)\Theta_\infty^{(L)}\left(XX^{\mathsf{T}}\right), the closed-form solution on t∈[tb,tb+1[t\in[t_b,t_{b+1}[ is given by

Qt(x)=Θt(L)(xTX(b)T)(Θt(L)(X(b)X(b)T))−1Q_t(x)=\Theta_t^{(L)}\left(x^{\mathsf{T}}X^{(b)\mathsf{T}}\right)\left(\Theta_t^{(L)}\left(X^{(b)}X^{(b)\mathsf{T}}\right)\right)^{-1}
Λt^b,t(L)(X(b))(Qtb(X(b))−R(X(b))−γQt^b∘μt^b(X(b)))\Lambda_{\hat{t}_b,t}^{(L)}\left(X^{(b)}\right)\left(Q_{t_b}\left(X^{(b)}\right)-R\left(X^{(b)}\right)-\gamma Q_{\hat{t}_b}\circ\mu_{\hat{t}_b}\left(X^{(b)}\right)\right)
+Qtb(x),+Q_{t_b}(x),

where Θt(L)=Θ∞(L)\Theta_t^{(L)}=\Theta_\infty^{(L)} for all $t\geq 0.

The time t^\hat{t} 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 Θ∞(L)(X(b)X(b)T)\Theta_\infty^{(L)}\left(X^{(b)}X^{(b)\mathsf{T}}\right) on the interval [tb,tb+1[[t_b,t_{b+1}[. By comparison with the supervised learning setting, Theorem 1 follows similar training dynamics within each intervals [tb,tb+1[[t_b,t_{b+1}[; 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 tt, while it is in fact differentiable everywhere else. Below, we detail properties of the NTK that are useful in theoretical analysis.

Properties of Θ∞(L)\Theta_\infty^{(L)}. We can show that the continuous-time TD error is n(b)n^{(b)}-smooth with respect to tt along any interval [tb,tb+1[[t_b,t_{b+1}[, with n(b)=∣X(b)∣n^{(b)}=\lvert X^{(b)}\rvert since the diagonal of Θ∞(L)(X(b)X(b)T)\Theta_\infty^{(L)}\left(X^{(b)}X^{(b)\mathsf{T}}\right) consists of ones. It is also χ\chi-strongly convex with respect to tt on that interval if the smallest eigenvalue of Θ∞(L)(X(b)X(b)T)\Theta_\infty^{(L)}\left(X^{(b)}X^{(b)\mathsf{T}}\right) is χ>0\chi>0. The following proposition (Proposition 2) states that for a depth L≥2L\geq2, 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 Θt(L)\Theta_t^{(L)} 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 Qt(x)Q_t(x) by recursively compute QtbQ_{t_b} are prior stopping times. This yields the following decomposition:

u(x)bT:=Θ∞(L)(xTX(b)T)u(x)_b^{\mathsf{T}}:=\Theta_\infty^{(L)}\left(x^{\mathsf{T}}X^{(b)\mathsf{T}}\right)
vb:=(Θ∞(L)(X(b)X(b)T))−1Λt^b,t(L)(X(b))v_b:=\left(\Theta_\infty^{(L)}\left(X^{(b)}X^{(b)\mathsf{T}}\right)\right)^{-1}\Lambda_{\hat{t}_b,t}^{(L)}\left(X^{(b)}\right)
(Qtb(X(b))−R(X(b))−γQt^b∘μt^b(X(b))),\left(Q_{t_b}\left(X^{(b)}\right)-R\left(X^{(b)}\right)-\gamma Q_{\hat{t}_b}\circ\mu_{\hat{t}_b}\left(X^{(b)}\right)\right),

from which Qt(x)=∑1,…,b∣tb≤tu(x)bTvbQ_t(x)=\sum_{1,\ldots,b\mid t_b\leq t}u(x)_b^{\mathsf{T}}v_b. The values vbv_b are kept in memory as they are computed, and for a new batch X(b)X^{(b)} of data, the values u(xi)bu(x_i)_b are computed for xi∈X(b)x_i\in X^{(b)}. Each new u(xi)bu(x_i)_b is used to compute the new term vbv_b that is stored in memory. The time spent to compute Qt(x)Q_t(x) is O(g2(t))O(g^2(t)), where g(t)=∣{ti∣ti≤t}∣2g(t)=\lvert\{t_i\mid t_i\le t\}\rvert^2. 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 x∈Cx\in C, where CC is the set induced by constraints on the state-action space S×AS\times A and the variable xx corresponds to the description of a state-action pair x=(s,a)x=(s,a). In a grid world example, the variable xx can be decomposed into variables s^\hat{s} and a^\hat{a}: s^∈Rh×w\hat{s}\in\mathbb{R}^{h\times w} (for a grid of size h×wh\times w) models each possible cell content, with different cases equivalent to different integers, while a^∈R\hat{a}\in\mathbb{R} indexes the different action scenarios. Constraints are introduced to ensure that s^\hat{s} describes a a valid state. Given tbt_b, the objective is to find x∗∈Cx^*\in C such that the estimate Q∞(x∗)Q_\infty(x^*) is maximized or minimized. This objective contributes to surprise whenever an optimal x∗∈Cx^*\in C is not part of the buffer and the TD target of x∗x^* is not close to the estimate. In this case, the error is corrected during the next training step. We formulate the search problem Pω±(λ)P_\omega^\pm(\lambda), which is passed to a MINLP solver to find arg max⁡x∈CQ∞(x)\operatorname*{arg\,max}_{x\in C}Q_\infty(x)3:

min⁡x,y,u ∓cωTusubject toy=XxΘ∞(L)(XXT)u=Θ∞(L)(y)cωTu∈R±x∈C,\begin{aligned} \min_{x,y,u}\ &\mp c_\omega^{\mathsf{T}}u && \text{subject to}\\ &y=Xx\\ &\Theta_\infty^{(L)}(XX^{\mathsf{T}})u=\Theta_\infty^{(L)}(y)\\ &c_\omega^{\mathsf{T}}u\in\mathbb{R}^{\pm}\\ &x\in C, \end{aligned}

where the cost cωc_\omega corresponds to the TD target under the sample ω\omega with initial value R(X)+γQ0∘μ0(X)(ω)R(X)+\gamma Q_0\circ\mu_0(X)(\omega). With (Pω±(λ))(P_\omega^\pm(\lambda)), it is possible to recover a solution x∈Cx\in C such that the Q-value is either maximized or minimized (±\pm). The random variable R(X)+γQ0∘μ0(X)R(X)+\gamma Q_0\circ\mu_0(X) can also be replaced by its mean R(X(1))R(X^{(1)}) as is the case in section 7.

The closed-form estimate Q∞Q_\infty is a proxy for a single batch update as we take t→∞t\to\infty while holding the mini-batch constant for the interval [0,∞[[0,\infty[, achieving perfect interpolation on the new mini-batch. Alternatively, we could model QtQ_t directly via the equation of Theorem 1 by introducing additional constraints for t1,…,tBt_1,\ldots,t_B and the corresponding mini-batches X(1),…,X(B)X^{(1)},\ldots,X^{(B)}. For simplicity and to make Pω±(λ)P_\omega^\pm(\lambda) more compact, we focus on the first use case. We observe that Θ∞(L)\Theta_\infty^{(L)} 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 Pω±(λ)P_\omega^\pm(\lambda) now defined, we introduce Algorithm 1.

Using the output of Algorithm 1, we can augment the initial dataset XX to define a new generalizing function. Since at each iteration in the loop we augment the dataset with x∈Cx\in C by selecting the point with the highest Q-value, we obtain a sequence of high predicted value candidates across the full set CC. When solving Pω±P_\omega^\pm and once an optimal x∗x^* is found, the dataset XX can be extended with x∗x^*. If Algorithm 1 is run with m=∣C∖X∣m=\lvert C\setminus X\rvert, the final model would indeed interpolate perfectly the whole state space as t→∞t\to\infty. 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 xx believed to have highest value.

Algorithm 1 Solver-Augmented State-Space Exploration

Input: Dataset XX, small λ>0\lambda> 0, m∈Nm \in\mathbb{N}

Draw ω\omega at random

Draw ++ or −- case at random

for mm iterations do

&nbsp;&nbsp;&nbsp;&nbsp;Solve Pω±(λ)P_{\omega}^{\pm}(\lambda) with XX

&nbsp;&nbsp;&nbsp;&nbsp;Recover x∗∈Cx^{*} \in\mathcal{C} and observe R(x∗)R(x^{*})

&nbsp;&nbsp;&nbsp;&nbsp;if TD error is high then

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;X←X∪{x∗}X \leftarrow X \cup\{x^{*}\}

&nbsp;&nbsp;&nbsp;&nbsp;end if

end for

return X,ω,±X,\omega,\pm case

Since the condition number of Θ∞(L)(XXT)\Theta_{\infty}^{(L)}(XX^{\mathsf{T}}) can be high for large nn, it can be useful to make a change of variable with δω\delta_{\omega} and rewrite the objective cωTuc_{\omega}^{\mathsf{T}}u as dωTΘ∞(L)d_{\omega}^{\mathsf{T}}\Theta_{\infty}^{(L)} after solving

Θ∞(L)(XXT)dω=cω(1)\Theta_{\infty}^{(L)}(XX^{\mathsf{T}})d_{\omega}=c_{\omega} \tag*{(1)}

and removing the constraint Θ∞(L)(XXT)u=Θ∞(L)(y)\Theta_{\infty}^{(L)}(XX^{\mathsf{T}})u=\Theta_{\infty}^{(L)}(y). Expression (1) only involves the variable dωd_{\omega} and if the equation is solved beforehand, the changed objective is dependent only on Θ∞(L)(y)\Theta_{\infty}^{(L)}(y)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 dωd_{\omega}, which is O(n3)O(n^{3}) 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 KK 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 O(1b)O\left(\frac{1}{\sqrt{b}}\right). 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.

Training loss of the gradient flow equivalent to deep Q-learning

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 KK 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 n×nn \times n is both nn-smooth and χ\chi-strongly convex for some χ>0\chi> 0. On a finite, yet large state-action space, each batch corresponds to a χb\chi_b parameter and χ\chi can be taken to be χ=min⁡b∈[B]χb>0\chi= \min_{b \in[B]} \chi_b > 0. 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.

AlgorithmRollout score
DQN0.0 (0.0)
DQN + solver0.10 (0.07)
SQN0.74 (0.24)
SQN + solver1.02 (0.22)

Table 1. Average (std) rollout scores on various RL algorithms on 100 episodes in a 8×88 \times8 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 CC far from the solutions previously found. In problem instances where diversity is key, this capability is especially useful.

Average rollout scores for SQN and SQN + solver

Figure 2. Average rollout scores for SQN and SQN + solver after 1000 learning steps in a 8×88 \times8 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 u,v∈C1(]a,b[)∩C([a,b])u,v \in C^1(]a,b[) \cap C([a,b]) and F∈C1(R)F \in C^1(\mathbb{R}) with a<ba < b. Suppose that

u′(t)≤F(u(t))t∈]a,b[u'(t) \le F(u(t)) \quad t \in]a,b[
v′(t)=F(v(t))t∈]a,b[v'(t) = F(v(t)) \quad t \in]a,b[
v(0)=u(0).v(0) = u(0).

Then, u(t)u(t) satisfies

u(t)≤v(t)t∈]a,b[.u(t) \le v(t) \quad t \in]a,b[.

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 L=2L = 2 and the extension to arbitrary depth L>2L > 2 follows by induction over layers. First, we have

∂tα~(l)=ΦΘt(l)(⟨dt(l),⋅⟩)\partial_t \widetilde{\alpha}^{(l)} = \Phi_{\Theta_t^{(l)}}\left(\left\langle d_t^{(l)}, \cdot\right\rangle\right)
∂tW(l)=1nl⟨α(l),dt(l+1)⟩,\partial_t W^{(l)} = \frac{1}{\sqrt{n_l}}\left\langle\alpha^{(l)},d_t^{(l+1)}\right\rangle,

where

dt(l)={dtif l=L,σ′(α~(l))⊙((1nlW(l))Tdt(l+1))if l<L.d_t^{(l)} = \begin{cases} d_t & \text{if } l = L,\\ \sigma'\left(\widetilde{\alpha}^{(l)}\right) \odot\left(\left(\frac{1}{\sqrt{n_l}}W^{(l)}\right)^{\mathsf{T}}d_t^{(l+1)}\right) & \text{if } l < L. \end{cases}

The subnetwork NTKs are

Θt(1)=1n0(α(0))T(α(0))⊗In1\Theta_t^{(1)} = \frac{1}{n_0}\left(\alpha^{(0)}\right)^{\mathsf{T}}\left(\alpha^{(0)}\right) \otimes I_{n_1}
Θt(2)=1n1W(1)σ′(α~(1))Θt(1)σ′(α~(1))W(1)+1n1(α(1))T(α(1)).\Theta_t^{(2)} = \frac{1}{n_1}W^{(1)}\sigma'\left(\widetilde{\alpha}^{(1)}\right)\Theta_t^{(1)}\sigma'\left(\widetilde{\alpha}^{(1)}\right)W^{(1)} + \frac{1}{n_1}\left(\alpha^{(1)}\right)^{\mathsf{T}}\left(\alpha^{(1)}\right).

We set

w(l)(t)=∥1nlW(l)(t)∥2w^{(l)}(t) = \left\|\frac{1}{\sqrt{n_l}}W^{(l)}(t)\right\|_2
a(l)(t)=∥1nlα(l)(t)∥Xa^{(l)}(t) = \left\|\frac{1}{\sqrt{n_l}}\alpha^{(l)}(t)\right\|_X

and we obtain the bounds

∥dt(1)∥X≤cw(1)(t)∥dt(2)∥X=cw(1)(t)∥dt∥X\begin{aligned} \left\|d_t^{(1)}\right\|_X \le c w^{(1)}(t)\left\|d_t^{(2)}\right\|_X \\ &= c w^{(1)}(t)\left\|d_t\right\|_X \end{aligned}
∥Θt(1)∥2≤(a(0)(t))2\left\|\Theta_t^{(1)}\right\|_2 \le\left(a^{(0)}(t)\right)^2
∥Θt(2)∥2≤c2(w(1)(t))2∥Θt(1)∥2+(a(1)(t))2.\left\|\Theta_t^{(2)}\right\|_2 \le c^2\left(w^{(1)}(t)\right)^2\left\|\Theta_t^{(1)}\right\|_2 + \left(a^{(1)}(t)\right)^2.

We set

Δa(l)(t)=∥1nl(α~(l)(t)−α~(l)(0))∥X\Delta_{a}^{(l)}(t)=\left\|\frac{1}{\sqrt{n_l}}\left(\widetilde{\alpha}^{(l)}(t)-\widetilde{\alpha}^{(l)}(0)\right)\right\|_{X}
Δw(l)(t)=∥1nl(W(l)(t)−W(l)(0))∥2\Delta_{w}^{(l)}(t)=\left\|\frac{1}{\sqrt{n_l}}\left(W^{(l)}(t)-W^{(l)}(0)\right)\right\|_{2}
A(t)=a(1)(0)+Δa(1)(t)+w(0)(0)+Δw(0)(t)+a(2)(0)+Δa(2)(t)+w(1)(0)+Δw(1)(t).\begin{aligned} A(t)&=a^{(1)}(0)+\Delta_{a}^{(1)}(t)+w^{(0)}(0)+\Delta_{w}^{(0)}(t)\\ &\quad+a^{(2)}(0)+\Delta_{a}^{(2)}(t)+w^{(1)}(0)+\Delta_{w}^{(1)}(t). \end{aligned}

From these last definitions, we obtain the bounds

∂tΔa(l)(t)≤1nl∥Θt(l)∥2∥dt(l)∥X\partial_t\Delta_{a}^{(l)}(t)\leq\frac{1}{\sqrt{n_l}}\left\|\Theta_t^{(l)}\right\|_2\left\|d_t^{(l)}\right\|_X
∂tΔw(l)(t)≤1nla(l)(t)∥dt(l+1)∥X.\partial_t\Delta_{w}^{(l)}(t)\leq\frac{1}{\sqrt{n_l}}a^{(l)}(t)\left\|d_t^{(l+1)}\right\|_X.

We use these bounds to bound the derivative ∂tA(t)\partial_tA(t) with

∂tA(t)≤1n1q(w(0)(t),w(1)(t),a(1)(t),a(2)(t))∥dt∥X\partial_tA(t)\leq\frac{1}{\sqrt{n_1}}q\left(w^{(0)}(t),w^{(1)}(t),a^{(1)}(t),a^{(2)}(t)\right)\left\|d_t\right\|_X

for some polynomial qq with positive coefficients. Observe that A(0)A(0) is stochastically bounded as n1→∞n_1\to\infty. Using Lemma 1 and using the fact that qq is bounded and continuous over [0,T][0,T], we obtain A(t)A(t) uniformly bounded over [0,T][0,T]. This implies that ∂tA(t)→0\partial_tA(t)\to0 as n1→∞n_1\to\infty, which in turn implies A(t)→A(0)A(t)\to A(0). The boundedness condition on A(t)A(t) implies that Θμ(2)\Theta_{\mu}^{(2)} remains bounded on [0,T][0,T]. To show that it remains constant, we study the derivatives ∂tΘt(2)\partial_t\Theta_t^{(2)}:

∂tΘt(2)(x,x′)=∇θtΘt(2)(x,x′)⊤∂tθt\partial_t\Theta_t^{(2)}(x,x')=\nabla_{\theta_t}\Theta_t^{(2)}(x,x')^{\top}\partial_t\theta_t

and we derive bounds for the norms of ∇θtΘt(2)(x,x′)\nabla_{\theta_t}\Theta_t^{(2)}(x,x') and ∂tθt\partial_t\theta_t:

∥∂W(1)Θt(2)(x,x′)∥2≤2n1c2∥Θt(1)∥2w(1)(t)(2)\left\|\partial_{W_{(1)}}\Theta_t^{(2)}(x,x')\right\|_2\leq\frac{2}{\sqrt{n_1}}c^2\left\|\Theta_t^{(1)}\right\|_2w^{(1)}(t) \tag*{(2)}
∥∂W(0)Θt(2)(x,x′)∥2≤2n1csup⁡z∈N^∥z∥2a(1)(t),(3)\left\|\partial_{W_{(0)}}\Theta_t^{(2)}(x,x')\right\|_2\leq\frac{2}{\sqrt{n_1}}c\sup_{z\in\widehat{\mathcal{N}}}\|z\|_2a^{(1)}(t), \tag*{(3)}

where N^=⋃i{xi}∪N(xi)\widehat{\mathcal{N}}=\bigcup_i\{x_i\}\cup\mathcal{N}(x_i). As n1→∞n_1\to\infty, we conclude that both (2) and (3) converge to 0 because of the assumption ∣N^∣<∞\left|\widehat{\mathcal{N}}\right|<\infty. Finally, since A(t)A(t) is bounded, the same can be said of ∂tθ\partial_t\theta as n1→∞n_1\to\infty.

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 rt>0r_t>0 is obtained strictly upon reaching the final target state at terminal step TT, whereas all intermediate transitions (t<Tt<T) yield rt=0r_t=0. 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 (l1l_1): consider an agent in position ptp_t who, after an action, transitions to position pt+1p_{t+1}; then, they obtain a reward equal to rt+1=0.01⋅Δl1(pt,pt+1,g)r_{t+1}=0.01\cdot\Delta l_1(p_t,p_{t+1},g) where gg is the position of the next immediate subgoal and Δl1(pt,pt+1,g)=(l1(pt,g)−l1(pt+1,g))\Delta l_1(p_t,p_{t+1},g)=(l_1(p_t,g)-l_1(p_{t+1},g)). Note that these intermediary rewards are positive when the agent moves closer to gg 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 5×55\times5 grid.

Initial grid potential

(a) (a) Initial grid potential −0.01×l1(p0,g)-0.01 \times l_1(p_0,g) = −0.02-0.02

Step toward the key

(b) (b) Step toward gg = Key r1r_1 = 0.01×Δl1(p0,p1,g)0.01 \times\Delta l_1(p_0,p_1,g) = +0.01+0.01

Pickup key subgoal

(c) (c) Subgoal 1: Pickup Key rsubgoal=+0.2r_{\mathrm{subgoal}} = +0.2

Unlock door subgoal

(d) (d) Subgoals 2: Unlock door rsubgoal=+0.4r_{\mathrm{subgoal}} = +0.4

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 Pω±(λ)P_{\omega}^{\pm}(\lambda) reformulates active exploration as a global search problem over the environment’s state-action space. Our objective is to retrieve a high-value state x=(s,a)x = (s, a) by finding the corresponding grid and action. In this section, we detail the implementation of Pω±(λ)P_{\omega}^{\pm}(\lambda) within the RL training procedure. In this section, we describe in detail how Pω±(λ)P_{\omega}^{\pm}(\lambda) is implemented. Specifically, we detail for the Minigrid environment the constraints defining the set C\mathcal{C}, and we also specify the explicit formulation of the constraints involving the kernel Θ∞(L)\Theta_{\infty}^{(L)}. To simplify notation, we let [m]={1,…,m}[m] = \{1, \ldots, m\}, where m∈Nm \in\mathbb{N}, and we let [m]k={k,…,m}[m]_k = \{k, \ldots, m\}, where k≤mk \leq m, k∈Nk \in\mathbb{N}. In our Minigrid environment, the grid dimensions are h×wh \times w, where hh denotes the height and ww denotes the width.

Every Minigrid environment follows the convention that grids are tensors of shape (h,w,3)(h, w, 3). 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 →{unseen:0,empty:1,wall:2,door:4,\to\{\text{unseen}: 0, \text{empty}: 1, \text{wall}: 2, \text{door}: 4, key:5,goal:8,agent:10}key: 5, \text{goal}: 8, \text{agent}: 10\}

colour →{red:0,green:1,yellow:4,grey:5}\to\{\text{red}: 0, \text{green}: 1, \text{yellow}: 4, \text{grey}: 5\}

state →{open:0,closed:1,locked:2}\to\{\text{open}: 0, \text{closed}: 1, \text{locked}: 2\}.

Available actions follow the convention

turn left →0\to0

turn right →1\to1

move forward →2\to2

pickup key →3\to3

unlock door →5\to5.

Grid constraints

For each grid cell (i,j)∈[h]×[w](i, j) \in[h] \times[w] and k∈[3]k \in[3], we introduce a variable si,j,k∈Ns_{i,j,k} \in\mathbb{N} within

si,j,k∈{[0,10]if k=1[0,5]if k=2[0,2]if k=3.s_{i,j,k} \in\begin{cases} [0,10] & \text{if } k = 1\\ [0,5] & \text{if } k = 2\\ [0,2] & \text{if } k = 3. \end{cases}

In simple words, these variables serve to describe the feature tuple (si,j,1,si,j,2,si,j,3)(s_{i,j,1}, s_{i,j,2}, s_{i,j,3}) of cell (i,j)(i,j), where component si,j,1s_{i,j,1} denotes the object type, si,j,2s_{i,j,2} the object color, and si,j,3s_{i,j,3} the state..

We also introduce a variable a∈{0,1,2,3,5}a \in\{0, 1, 2, 3, 5\} for the available actions. We add big-M constraints to determine the door and key positions. We also introduce binary variables di,j,ki,jd_{i,j}, k_{i,j}, for (i,j)∈[h]×[w](i, j) \in[h] \times[w], indicating the presence of a door or key in cell (i,j)(i, j), respectively. With these variables, we add constraints to ensure that there is one door and at most one key on the grid .

si,j,1≤4+10×(1−di,j)(door in cell)si,j,1≥4−10×(1−di,j)∑(i,j)di,j=1(exactly one door)si,j,1≤5+10×(1−ki,j)(key in cell)si,j,1≥5−10×(1−ki,j)∑(i,j)ki,j≤1.(at most one key)\begin{aligned} s_{i,j,1} &\leq4 + 10 \times(1 - d_{i,j}) && \text{(door in cell)}\\ s_{i,j,1} &\geq4 - 10 \times(1 - d_{i,j})\\ \sum_{(i,j)} d_{i,j} &= 1 && \text{(exactly one door)}\\ s_{i,j,1} &\leq5 + 10 \times(1 - k_{i,j}) && \text{(key in cell)}\\ s_{i,j,1} &\geq5 - 10 \times(1 - k_{i,j})\\ \sum_{(i,j)} k_{i,j} &\leq1. && \text{(at most one key)} \end{aligned}

We fix the cell at position (h−1,w−1)(h-1,w-1) to be a green goal square. In other words,

sh−1,w−1,1=8,sh,w,2=1,sh,w,3=0.s_{h-1,w-1,1}=8,\quad s_{h,w,2}=1,\quad s_{h,w,3}=0.

We introduce the binary variables agent⁡i,j∈{0,1}\operatorname{agent}_{i,j}\in\{0,1\} for (i,j)∈[h−1]2×[w−1]2(i,j)\in[h-1]_2\times[w-1]_2 to determine the agent’s position. In order to have only one agent on the grid, we add the constraint

∑i=2h−1∑j=2w−1agent⁡i,j=1.\sum_{i=2}^{h-1}\sum_{j=2}^{w-1}\operatorname{agent}_{i,j}=1.

To determine if each cell is empty, we introduce the variables empty⁡i,j∈{0,1}\operatorname{empty}_{i,j}\in\{0,1\} for (i,j)∈[h−1]2×[w−1]2(i,j)\in[h-1]_2\times[w-1]_2. We introduce the variables wall⁡i,j∈{0,1}\operatorname{wall}_{i,j}\in\{0,1\} for (i,j)∈[h−1]2×[w−2]3(i,j)\in[h-1]_2\times[w-2]_3 to determine the presence of a wall. We note that DoorKey environments generate a separating wall containing a door at random between columns j=3j=3 and j=w−2j=w-2. We introduce the constraints

agent⁡i,j≤1−wall⁡i,j\operatorname{agent}_{i,j}\leq1-\operatorname{wall}_{i,j}

(agent not on wall) to ensure the agent is not on a wall. The variables col⁡j\operatorname{col}_j for j∈[w−2]3j\in[w-2]_3 correspond to the presence of a separating wall in column jj. 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.

∑j∈[w]col⁡j=1(4)\sum_{j\in[w]}\operatorname{col}_j=1 \tag*{(4)}
wall⁡i,j+di,j=col⁡j(5)\operatorname{wall}_{i,j}+d_{i,j}=\operatorname{col}_j \tag*{(5)}

The agent orientation at cell (i,j)∈[h−1]2×[w−1]2(i,j)\in[h-1]_2\times[w-1]_2 is determined through variables east⁡i,j∈{0,1}\operatorname{east}_{i,j}\in\{0,1\}, south⁡i,j∈{0,1}\operatorname{south}_{i,j}\in\{0,1\}, west⁡i,j∈{0,1}\operatorname{west}_{i,j}\in\{0,1\}, and north⁡i,j∈{0,1}\operatorname{north}_{i,j}\in\{0,1\}. We further require constraints for (i,j)∈[h−1]2×[w−2]3(i,j)\in[h-1]_2\times[w-2]_3 to ensure that the agent is not on the key:

agent⁡i,j≤1−ki,j.\operatorname{agent}_{i,j}\leq1-k_{i,j}.

The following constraint ensure the agent is not on the goal:

agent⁡h−1,w−1=1−goal⁡h−1,w−1.\operatorname{agent}_{h-1,w-1}=1-\operatorname{goal}_{h-1,w-1}.

The agent orientation variables can only be active if there is an agent on the same cell:

agent⁡i,j=east⁡i,j+south⁡i,j+west⁡i,j+north⁡i,j.\operatorname{agent}_{i,j}=\operatorname{east}_{i,j}+\operatorname{south}_{i,j}+\operatorname{west}_{i,j}+\operatorname{north}_{i,j}.

We also fix the boundary cells of the grid with si,j,1=2s_{i,j,1}=2, si,j,2=5s_{i,j,2}=5, si,j,3=0s_{i,j,3}=0. For each grid cell not on the boundary, we add two sets of constraints to determine its colour. The first set involves indices (i,j)∈[h−1]2×[w−2]3(i,j)\in[h-1]_2\times[w-2]_3, corresponding to cells where the separating wall can lie:

si,j,1=5×ki,j+2×wall⁡i,j+4×di,j+10×agent⁡i,j+empty⁡i,j.s_{i,j,1}=5\times k_{i,j}+2\times\operatorname{wall}_{i,j} +4\times d_{i,j}+10\times\operatorname{agent}_{i,j}+\operatorname{empty}_{i,j}.

The second set of constraints involves indices (i,j)∈[h−1]2×{2,w−1}(i,j)\in[h-1]_2\times\{2,w-1\}, where the separating wall cannot lie:

si,j,1=5×ki,j+10×agent⁡i,j+empty⁡i,j.s_{i,j,1}=5\times k_{i,j}+10\times\operatorname{agent}_{i,j}+\operatorname{empty}_{i,j}.

Finally, we introduce binary variables to model the door being open, closed, locked, and the key being carried. These variables are open⁡i,j∈{0,1}\operatorname{open}_{i,j}\in\{0,1\}, closed⁡i,j∈{0,1}\operatorname{closed}_{i,j}\in\{0,1\}, locked⁡i,j∈{0,1}\operatorname{locked}_{i,j}\in\{0,1\}. For (i,j)∈[h−1]2×[w−2]3(i,j)\in[h-1]_2\times[w-2]_3, we enforce the door to be in one of its three possible states if present in cell (i,j)(i,j):

di,j=open⁡i,j+closed⁡i,j+locked⁡i,j.d_{i,j}=\operatorname{open}_{i,j}+\operatorname{closed}_{i,j}+\operatorname{locked}_{i,j}.

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.

∑i=2h−1∑j=3w−2lockedi,j≥∑(i,j)ki,j\sum_{i=2}^{h-1}\sum_{j=3}^{w-2}\mathrm{locked}_{i,j} \ge\sum_{(i,j)} k_{i,j}
∑(k,l)∣l≥jagentk,l≤1−colj+∑(k,l)openk,lj∈[w−2]3.\sum_{(k,l)\mid l\ge j}\mathrm{agent}_{k,l} \le1-\mathrm{col}_{j}+\sum_{(k,l)}\mathrm{open}_{k,l} \qquad j\in[w-2]_3.

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,j)∈[h−1]2×[w−2]3(i,j)\in[h-1]_2\times[w-2]_3, i.e. a separating wall can be found:

si,j,3=1×closedi,j+2×lockedi,j+3×northi,j+2×westi,j+southi,js_{i,j,3}=1\times\mathrm{closed}_{i,j}+2\times\mathrm{locked}_{i,j} +3\times\mathrm{north}_{i,j}+2\times\mathrm{west}_{i,j}+\mathrm{south}_{i,j}

and of the cells (i,j)∈[h−1]2×{2,w−1}(i,j)\in[h-1]_2\times\{2,w-1\}, i.e. outside the separating wall range of possible columns:

si,j,3=3×northi,j+2×westi,j+southi,js_{i,j,3}=3\times\mathrm{north}_{i,j}+2\times\mathrm{west}_{i,j}+\mathrm{south}_{i,j}

All the variables and constraints defined in this section form the variable vector xx and the constraint set C\mathcal{C} appearing in Pω±(λ)P_{\omega}^{\pm}(\lambda).

Kernel constraints

In this section, we introduce the remaining variables and constraints derived from Pω±(λ)P_{\omega}^{\pm}(\lambda). The additional variables are

yi∈R,i∈[n](embedding)y_i\in\mathbb{R},\qquad i\in[n]\qquad\text{(embedding)}
eˉi∈R,i∈[n](normalization)\bar{e}_i\in\mathbb{R},\qquad i\in[n]\qquad\text{(normalization)}
norm∈R≥0\mathrm{norm}\in\mathbb{R}_{\ge0}
asinl,i∈[−π2,π2],l∈[L]2, i∈[n]\mathrm{asin}_{l,i}\in\left[-\frac{\pi}{2},\frac{\pi}{2}\right],\qquad l\in[L]_2,\ i\in[n]
ρl,i∈[−1,1],l∈[L], i∈[n]\rho_{l,i}\in[-1,1],\qquad l\in[L],\ i\in[n]
ρ^l,i∈[−1,1],l∈[L]2, i∈[n]\hat{\rho}_{l,i}\in[-1,1],\qquad l\in[L]_2,\ i\in[n]
Θl,i∈[−1,1],l∈[L], i∈[n],\Theta_{l,i}\in[-1,1],\qquad l\in[L],\ i\in[n],

where variable yy corresponds to the variable y=Xxy=Xx in Pω±(λ)P_{\omega}^{\pm}(\lambda). We include constraint to model the data in Sn0−1S^{n_0-1}:

x=concat⁡(vec⁡(s),a)(x=(s,a))x=\operatorname{concat}(\operatorname{vec}(s),a) \qquad(x=(s,a))
norm2=∥x∥22\mathrm{norm}^{2}=\lVert x\rVert_{2}^{2}
yi=xiTxi∈[n](dot product)y_i=x_i^{\mathsf{T}}x\qquad i\in[n]\qquad\text{(dot product)}
eˉi×norm=yi∥xi∥2i∈[n](normalization)\bar{e}_i\times\mathrm{norm}=\frac{y_i}{\lVert x_i\rVert_{2}} \qquad i\in[n]\qquad\text{(normalization)}

and constraints to model the kernel:

ρ1,i=eˉi,i∈[n]ρl,i=asin⁡l,i×sin⁡(asin⁡l,i)π+cos⁡(asin⁡l,i)π+sin⁡(asin⁡l,i)2,l∈[L]2,i∈[n]ρl,i′=asin⁡l,iπ+12,l∈[L]2,i∈[n]sin⁡(asin⁡l,i)=ρl−1,i,l∈[L]2,i∈[n]Θ1,i=ρ1,i,i∈[n]Θl,i=l−1lρl,i′Θl−1,i+1lρl,i,l∈[L]2,i∈[n].\begin{aligned} \rho_{1,i} &= \bar{e}_i, && i \in[n] \\ \rho_{l,i} &= \operatorname{asin}_{l,i} \times\frac{\sin(\operatorname{asin}_{l,i})}{\pi} + \frac{\cos(\operatorname{asin}_{l,i})}{\pi} + \frac{\sin(\operatorname{asin}_{l,i})}{2}, && l \in[L]_2, i \in[n] \\ \rho'_{l,i} &= \frac{\operatorname{asin}_{l,i}}{\pi} + \frac{1}{2}, && l \in[L]_2, i \in[n] \\ \sin(\operatorname{asin}_{l,i}) &= \rho_{l-1,i}, && l \in[L]_2, i \in[n] \\ \Theta_{1,i} &= \rho_{1,i}, && i \in[n] \\ \Theta_{l,i} &= \frac{l-1}{l}\rho'_{l,i}\Theta_{l-1,i} + \frac{1}{l}\rho_{l,i}, && l \in[L]_2, i \in[n]. \end{aligned}

The variables ΘL,i\Theta_{L,i} model the term Θ∞(L)(y)\Theta_{\infty}^{(L)}(y) in Pω±(λ)P_{\omega}^{\pm}(\lambda) through the equations

ΘL,i=Θ∞(L)(xiTx∥xi∥2∥x∥2).\Theta_{L,i} = \Theta_{\infty}^{(L)}\left(\frac{x_i^{\mathsf{T}}x}{\lVert x_i\rVert_2\lVert x\rVert_2}\right).

where i∈[n]i \in[n]. We remark that the matrix Θ∞(L)(XXT)\Theta_{\infty}^{(L)}(XX^{\mathsf{T}}) is known beforehand and is therefore a matrix of coefficients. In addition, the variables asin⁡l,i\operatorname{asin}_{l,i} model the arcsin terms in the definition of ρ(l)\rho^{(l)}. This is achieve through the constraint type sin⁡(α)=β\sin(\alpha)=\beta for variables α\alpha and β\beta, where the relationship arcsin⁡(β)=α\arcsin(\beta)=\alpha is enforced. Moreover, functions ρ(l)(x)\rho^{(l)}(x) contain terms 1−x2\sqrt{1-x^2}, which can lead to numerical issues when computing their derivative with respect to xx near −1-1 or 11. Instead, we model these terms with constraints cos⁡(asin⁡l,i)\cos(\operatorname{asin}_{l,i}), since 1−sin⁡2(asin⁡l,i)=cos⁡(asin⁡l,i)\sqrt{1-\sin^2(\operatorname{asin}_{l,i})}=\cos(\operatorname{asin}_{l,i}). 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 {X(b)}b=1B\{X^{(b)}\}_{b=1}^{B}. 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 nn-smooth and χ\chi-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 tbt_b, mini-batch replacement causes a loss spike due to distribution shift, followed by exponential decay governed by the local strong convexity constant χb=λmin⁡(Θ∞(L)(X(b)X(b)⊤))>0\chi_b = \lambda_{\min}\left(\Theta_{\infty}^{(L)}\left(X^{(b)}X^{(b)\top}\right)\right) > 0.

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.

Architecture of the solver-augmented exploration callback loop

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 (s∗,a∗)(s^*, a^*) for environment rollouts.

Necessity of KKT conditions

In this section, we show that the KKT conditions for Pω±(λ)P_{\omega}^{\pm}(\lambda) are necessary for a local optimum with respect to the primal variables (e.g., xx and yy). We begin by providing the constraint qualification required in the proof of necessity [2].

Definition 9 (RCPLD). Denote the equality constraints with hi(x)=0h_i(x) = 0, i∈Ii \in\mathcal{I} and the inequality constraints gj(x)≤0g_j(x) \le0, j∈Jj \in\mathcal{J}, and let J(x∗)={j∈J:gj(x∗)=0}\mathcal{J}(x^*) = \{j \in\mathcal{J} : g_j(x^*) = 0\} be the set of constraints active at x∗x^*. The relaxed constant positive linear dependence (RCPLD) condition holds if there exists a neighbourhood B(x∗,δ)={x:∥x−x∗∥2<δ}B(x^*, \delta) = \{x : \lVert x - x^*\rVert_2 < \delta\} for some δ>0\delta> 0 such that 1) the set {∇hi(x)∣i∈I}\{\nabla h_i(x) \mid i \in\mathcal{I}\} has constant rank for x∈B(x∗,δ)x \in B(x^*, \delta), and 2) for every basis of {∇hi(x∗)∣I}\{\nabla h_i(x^*) \mid\mathcal{I}\} with index set I⊆I\mathcal{I} \subseteq\mathcal{I} and for any subset J⊆J(x∗)\mathcal{J} \subseteq\mathcal{J}(x^*), the following

implication is satisfied:

∃(λ,μ)≠0, μ≥0: ∑i∈Iλi∇hi(x⋆)+∑j∈Jμj∇gj(x⋆)=0\exists(\lambda,\mu)\ne0,\ \mu\ge0:\ \sum_{i\in I}\lambda_i\nabla h_i(x^\star)+\sum_{j\in J}\mu_j\nabla g_j(x^\star)=0
⟹∀x∈B(x⋆,δ) ∃(α,β)≠0: ∑i∈Iαi∇hi(x)+∑j∈Jβj∇gj(x)=0.\Longrightarrow\quad\forall x\in B(x^\star,\delta)\ \exists(\alpha,\beta)\ne0:\ \sum_{i\in I}\alpha_i\nabla h_i(x)+\sum_{j\in J}\beta_j\nabla g_j(x)=0.

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 vv of Pω±(λ)P_{\omega}^{\pm}(\lambda), let v⋆v^\star denote the corresponding variable value in a (feasible) local optimum. Suppose the following:

  1. x⋆x^\star is such that ∥x∥2>0\lVert x\rVert_2>0 and x⋆≠±xix^\star\ne\pm x_i for all i∈[n]i\in[n];

  2. xiTxj∈[−1,1]x_i^{\mathsf T}x_j\in[-1,1] for i,j∈[n]i,j\in[n] and that xiTxj=1x_i^{\mathsf T}x_j=1 only if i=ji=j;

  3. L≥2L\ge2 so that Θ∞(L)(XXT)\Theta_{\infty}^{(L)}(XX^{\mathsf T}) 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 C(s,a)C(s,a). However, C(s,a)C(s,a) corresponds to linear equalities and inequalities. A linear combination of an arbitrary subset of these gradients that is equal to 0 at x⋆x^\star leads to a linear combination that is equal to 0 at xx. Because of this fact, the rank of {∇hi(x)∣i∈I}\{\nabla h_i(x)\mid i\in\mathcal{I}\} is constant for x∈B(x⋆,δ)x\in B(x^\star,\delta). We conclude that the constraints of (Pω±(λ))(P_{\omega}^{\pm}(\lambda)) satisfy RCPLD and that the KKT conditions are necessary for the local optimal solution.

In the statement of Theorem 2, the vectors xix_i, i∈[n]i\in[n], are normalized with unit norm, but since the unnormalized version Θ∞(L)\Theta_{\infty}^{(L)} is homogeneous component-wise [16], the statement holds in the general sense by assuming the xix_i’s and xx are not pairwise colinear. The proof of Theorem 2 also holds in the more general case where the constraints of C(s,a)C(s,a) 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 Pω±(λ)P_{\omega}^{\pm}(\lambda) (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 LL and the size of the dataset nn 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 ain,i,ρL,i,ρl,i′,Θl,ia_{\mathrm{in},i},\rho_{L,i},\rho'_{l,i},\Theta_{l,i}, a local node will also satisfy RCPLD whenever

(4L−2)n+1>∣x∣−m,(4L-2)n+1>|x|-m,

where ∣x∣=∣s∣+1|x|=|s|+1 is the length of variable xx and mm is the number of equality constraints in C(s,a)C(s,a).

Proof. The gradients ∇gj(x⋆)\nabla g_j(x^\star) for j∈Jj\in\mathcal{J} induce a cone CJC_{\mathcal{J}}, while the gradients ∇hi(x⋆)\nabla h_i(x^\star) for i∈Ii\in\mathcal{I} induce a subspace HI(x⋆)H_{\mathcal{I}}(x^\star). We suppose CJ∩HI(x⋆)≠{0}C_{\mathcal{J}}\cap H_{\mathcal{I}}(x^\star)\ne\{0\} and we observe that

span⁡({∇gj(y)∣j∈J})∩HI(y)=span⁡({∇gj(x⋆)∣j∈J})∩HI(y).(6)\operatorname{span}(\{\nabla g_j(y)\mid j\in\mathcal{J}\})\cap H_{\mathcal{I}}(y)=\operatorname{span}(\{\nabla g_j(x^\star)\mid j\in\mathcal{J}\})\cap H_{\mathcal{I}}(y). \tag*{(6)}

For vector subspaces VV and WW,

dim⁡(V∩W)=dim⁡(V)+dim⁡(W)−dim⁡(V+W).\dim(V \cap W) = \dim(V) + \dim(W) - \dim(V + W).

Therefore, subspace (4) has dimension strictly greater than zero if

dim⁡(HI(y))+dim⁡(span⁡({∇gj(y)∣j∈J}))>∣y∣⟺4Ln+∣yx∣+1+m+(4L−2)n>4Ln+1+2∣yx∣⟺(8L−2)n+∣yx∣+1+m>4Ln+1+2∣yx∣⟺(4L−2)n+1>∣yx∣−m,\begin{aligned} \dim(H_{\mathcal{I}}(y)) + \dim(\operatorname{span}(\{\nabla g_j(y) \mid j \in\mathcal{J}\})) &> |y| \\ \Longleftrightarrow\quad4Ln + |y_x| + 1 + m + (4L - 2)n &> 4Ln + 1 + 2|y_x| \\ \Longleftrightarrow\quad(8L - 2)n + |y_x| + 1 + m &> 4Ln + 1 + 2|y_x| \\ \Longleftrightarrow\quad(4L - 2)n + 1 &> |y_x| - m, \end{aligned}

where yxy_x is the section of yy indexed by variable xx. Given our initial assumption, RCPLD is satisfied in a neighbourhood of x∗x^*.

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [13]Yasuhiro Fujita. Experience replay with random reshuffling. arXiv preprint arXiv:2503.02269, 2025.arxiv.org/abs/2503.02269
  14. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_rvmhwhkx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents