Abstract

We prove that a single-layer neural network trained with the online actor critic algorithm converges in distribution to a random ordinary differential equation (ODE) as the number of hidden units and the number of training steps \(\rightarrow \infty\). In the online actor-critic algorithm, the distribution of the data samples dynamically changes as the model is updated, which is a key challenge for any convergence analysis. We establish the geometric ergodicity of the data samples under a fixed actor policy. Then, using a Poisson equation, we prove that the fluctuations of the model updates around the limit distribution due to the randomly-arriving data samples vanish as the number of parameter updates \(\rightarrow \infty\). Using the Poisson equation and weak convergence techniques, we prove that the actor neural network and critic neural network converge to the solutions of a system of ODEs with random initial conditions. Analysis of the limit ODE shows that the limit critic network will converge to the true value function, which will provide the actor an asymptotically unbiased estimate of the policy gradient. We then prove that the limit actor network will converge to a stationary point.

1 Introduction↩︎

Neural network actor-critic algorithms are one of the most popular methods in deep reinforcement learning. A neural network model is trained to select the policy (the “actor") while another neural network (the”critic") is simultaneously trained to learn the value function given the actor’s policy. Specifically, the actor selects an action and, given the action, a new state transition occurs according to a Markov stochastic process and a reward (a measurement of the success/failure) is observed. The critic must learn to approximate the value function – the solution to the Bellman equation – given the actor’s policy. Given the critic’s estimate for the value function of the current policy, the actor must be updated to improve the value function (i.e., increase the expected reward). Actor-critic algorithms are well-established methods in reinforcement learning [1], [2]; the key recent advance is using (deep) neural networks as the actor/critic and training their parameters using gradient descent methods [3]–[7].
Analysis of neural network actor-critic algorithms is challenging due to: (1) the non-convexity of the neural networks, (2) the complex feedback loop between the actor and critic (the actor determines the sequence of data samples which are used to train the critic and the critic is used to train the actor), and (3) the simultaneous online updates of both the actor and critic which lead to (3A) the distribution of the data, which depends upon the actor, constantly evolving in time and (3B) the actor being updated with a noisy, biased estimate of the value function.

1.1 Convergence Analysis of Actor-critic Algorithms↩︎

1.1.0.1 ODE Methods

Various versions of actor-critic algorithms have been studied under the framework of stochastic approximation algorithms, see [2], [8]–[10] and the associated references for an extensive discussion and literature review. A common way of analysing the stability and convergence of this class of algorithms would be to show that the algorithm converges to the limit set of an associated ODE [11]–[13]. As a result, the algorithm can be studied by characterizing the limit set of the ODE [9], [14]. The references [11], [15] provide general overviews of this method. We note that the stability of the actor-critic algorithm can be established via a pure martingale argument [10].

Although our approach also connects the actor-critic algorithm with an ODE, the analysis and convergence theorem are different. Here we establish the pathwise uniform convergence of the time-rescaled trajectory of the actor-critic algorithm using weak convergence techniques [16] as the number of hidden units and training steps \(\rightarrow \infty\). The convergence to the limit ODE with a neural network actor and a neural network critic as the number of hidden units \(\rightarrow \infty\) was not previously considered in the ODE literature discussed above.

1.1.0.2 Finite time analysis

Non-asymptotic convergence rates can also be established for the actor-critic algorithm using finite-time analysis approaches. These results establish a convergence rate to a time when the optimality gap is arbitrarily small. Finite-time converge rates for actor-critic algorithms with linear approximators for the action value function have been proven in [17]–[19].

Recent advances using neural tangent kernel (NTK) analysis [20]–[23] has enabled finite-time analysis on various versions of the neural network actor-critic algorithm. Building upon the NTK results [20]–[23], [24], [25] study a “batch" version of the actor-critic algorithm where a large number of critic parameter updates are required for each actor update to ensure accurate approximation of the action-value function. A convergence result is proven when the ratio of critic updates for each actor update \(\rightarrow \infty\). In particular, [24], [25] establish that the batch actor-critic algorithm can become arbitrarily close to a stationary point within a large but finite numbers of iterations. These results do not guarantee the convergence of the actor-critic algorithm as the training time \(\to\infty\), as the parameters could escape from the global/local minimum of the loss function.

While [24], [25] study the batch version of the actor-critic algorithm – where the number of critic updates for each actor update \(\rightarrow \infty\) at each iteration – we develop a convergence analysis for online neural network actor-critic algorithm where there is a single actor and a single critic update at each iteration. The advantage of the online algorithm is that a much larger number of optimization iterations can be completed in the same computational time. The online updates introduce key mathematical differences to the analysis. The learning rates for both the actor and critic must be carefully selected in order to guarantee convergence in the online setting. In addition, the exploration policy for the actor must also be carefully designed. A two-timescale analysis to separate the timescales of the actor and critic must be applied in combination with the NTK methods. Due to the online updates, a Poisson equation must be used to analyze the fluctuations of the algorithm around its limit trajectory. The main mathematical result is also different; we characterize the limit of the neural network actor-critic algorithm as the number of training steps and hidden units \(\rightarrow \infty\), proving that it converges to the solution of a system of ODEs using weak convergence techniques. Finally, we prove that the limit ODE converges to a stationary point of the expected reward as the training time \(\rightarrow \infty\). Similar to [24], [25], this also implies that there is a finite training time such that the pre-limit algorithm converges arbitrarily close to a stationary point of the objective function.

1.2 Our Mathematical Approach↩︎

We prove that the trajectory of the time-rescaled neural network outputs converges pathwise weakly to an ODE with random initialisation as the number of hidden units \(\rightarrow \infty\). We then prove that the limit critic converges to the value function and the actor converges to a stationary point of the objective function as the training time \(\rightarrow \infty\). In particular, we show that both

the Bellman error for the critic model and
the norm of the gradient of the objective function with respect to the actor

converge to zero as the training time tends to infinity. These results are stated formally in Section 3. Our results are strictly stronger than the classical ODE approaches in [9], [14] as it provides information about the training trajectory. We prove that the trained limit neural network converges to a stationary point as the training time \(t \rightarrow \infty\). In our paper, a constant learning rate is used for the critic and a logarithmic learning rate is used for the actor, which asymptotically yield accurate value function estimates for the online actor update. These learning rates are non-standard in the classical approach (see [8], [10], [12], [15]).
The convergence to a limit ODE is a result of the neural network parameters remaining within a small neighborhood of their initial values as they train. This result is referred to as the Neural Tangent Kernel (NTK) result and was discovered in [23] for feedforward networks in supervised learning. The NTK analysis has been widely-used to study neural networks, including for reinforcement learning algorithms [26], [27]. Therefore, the evolving neural network outputs (during training) can be linearized around the initial empirical distribution of the parameters. In the reinforcement learning setting, convergence to the limit ODE with the NTK kernel requires the analysis of non-i.i.d. data samples whose distribution depend upon the neural network parameters (since the distribution of the Markov chain depends upon the actor). The actor parameter updates themselves depend upon the data samples, introducing a complex feedback loop. Our analysis requires constructing an appropriate Poisson equation to address this challenge.
We first establish the geometric ergodicity of the data samples under a fixed actor policy. Then, using the Poisson equation, we prove that the fluctuations of the model updates around the limit distribution due to the randomly-arriving data samples vanish as the number of parameter updates \(\rightarrow \infty\). Using the Poisson equation and weak convergence techniques, we prove that the actor neural network and critic neural network converge to the solutions of a system of ODEs with random initial conditions. Unlike in the classic NTK analysis of feedforward neural networks which produces a linear limit ODE, the limit ODE for the actor-critic algorithm is nonlinear. Leveraging the two timescales for the actor and critic ODEs (due to their respective learning rates), we are able to prove that the critic ODE converges to the true value function (the solution of the Bellman equation) as the training time \(t \rightarrow \infty\), which provides the actor with an asymptotically unbiased estimate of the policy gradient. We then prove that the limit actor network will converge to a stationary point of the objective function as \(t \rightarrow \infty\). Therefore, although in the pre-limit actor-critic algorithm the critic provides a noisy, biased (i.e., there is error) estimate of the value function, we are able to prove that asymptotically the critic will converge sufficiently rapidly such that the actor also converges.

1.3 Organisation of the analysis↩︎

Section 2 describes the class of actor-critic algorithms that we study. Section 3 states the main convergence results that are proven. The proof of the main result is presented in Section 5. Finally, we analyse the limit ODE as \(t \rightarrow \infty\) in Section 5 to establish the convergence of critic network to the true action-value function and the convergence of actor network to a stationary point of the expected discounted future reward.

2 Actor-Critic Algorithms↩︎

2.1 Markov Decision Processes↩︎

We will study a neural network actor-critic algorithm for the following Markov decision process (MDP).

Definition 1 (Markov decision process (MDP)). A Markov decision process \(\boldsymbol{\mathcal{M}} = (\boldsymbol{\mathcal{X}}, \boldsymbol{\mathcal{A}}, p, \rho_0, r, \gamma)\) consists of the following:

\(\boldsymbol{\mathcal{X}} \subseteq \mathbb{R}^{d_x}\), the space of all possible states of the MDP (the state space);
\(\boldsymbol{\mathcal{A}} \subseteq \mathbb{R}^{d_a}\), the space of all actions of the MDP (the action space);
\(p(x'| x,a)\), the transition kernel that gives the probability of next state being \(x'\) if the current state is \(x\) and the action \(a\) is taken;
\(\rho_0\), the distribution that characterises how the initial state and action are chosen,
\(r(x,a)\), the reward gained by taking action \(a\) at state \(x\), and
\(\gamma \in(0,1)\) being the discount factor.

Here \(\boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}} \subset \mathbb{R}^d\), where \(d = d_x + d_a\). Any elements \(\xi := (x,a) \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) are called state-action pairs.

We make the same assumptions on the MDP as the ones made in [27]:

Assumption 1 (Basic assumptions on the MDP).

Finite state space: we assume that the state space \(\boldsymbol{\mathcal{X}}\) is discrete and finite with size \(\#\boldsymbol{\mathcal{X}}\),
Finite action space: we assume that the action space \(\boldsymbol{\mathcal{A}}\) is discrete and finite with size \(\#\boldsymbol{\mathcal{A}}\), and
The reward function \(r\) is bounded in \([-1,1]\).

We denote the size of the state-action space \(\boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) as \(M = \#\boldsymbol{\mathcal{X}} \times \#\boldsymbol{\mathcal{A}}\).

2.2 Policy in the MDP↩︎

A policy \(f = f(x,a)\) specifies the probability of selecting action \(a\) at state \(x\). The policy \(f\) acts on the MDP \(\boldsymbol{\mathcal{M}}\) to induce the following Markov chain on the state-action pair \(\xi_k := (x_k, a_k)\): \[(\boldsymbol{\mathcal{M}},f): \xi_0 := (x_0, a_0) \sim \rho_0 \stackrel{p(\cdot |x_0, a_0)}{\stackrel{= p(\cdot | \xi_0)}{\xrightarrow{~~~~~~}}} x_1 \stackrel{f(x_1,\cdot)}{\xrightarrow{~~~~~~}} a_1 \stackrel{p(\cdot |x_1, a_1)}{\stackrel{= p(\cdot | \xi_1)}{\xrightarrow{~~~~~~}}} x_2 \stackrel{f(x_2, \cdot)}{\xrightarrow{~~~~~~}} a_2 \stackrel{p(\cdot |x_2, a_2)}{\stackrel{= p(\cdot | \xi_2)}{\xrightarrow{~~~~~~}}}x_3 \stackrel{f(x_3,\cdot)}{\xrightarrow{~~~~~~}} a_3 \cdots,\] which is time-homogeneous with initial distribution \(\rho_0\) and transition kernel \(f(x_{k+1}, a_{k+1}) \, p(x_{k+1} \,|\, x_k, a_k)\) from \(\xi_k = (x_k, a_k)\) to \(\xi_{k+1} = (x_{k+1}, a_{k+1})\).
The overall reward for a policy \(f\) in the MDP \(\boldsymbol{\mathcal{M}}\) is evaluated by the following state and action-value functions:

Definition 2 (State and action-value functions). The state and action-value functions of a policy \(f\) acting on MDP \(\boldsymbol{\mathcal{M}}\) is defined as follows:

the state-value function \(V^f: \boldsymbol{\mathcal{X}} \rightarrow \mathbb{R}\) is the expected discounted sum of future awards when the MDP is started from a certain state \(x\) and there is a fixed policy \(f\) for all timesteps: \[V^{f}(x) = \mathbb{E}\left[\sum_{k=0}^{\infty} \gamma^{k} r(\xi_k) \mid x_{0}=x\right],\] and
the action-value function \(V^{f}: \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}} \rightarrow \mathbb{R}\) is the expected discounted sum of future awards when the MDP is started from a certain state-action pair \((x,a)\) and there is a fixed policy \(f\) for all timesteps: \[\label{value32function} V^{f}(x,a) = \mathbb{E}\left[\sum_{k=0}^{\infty} \gamma^{k} r(\xi_k) \mid x_{0}=x, a_{0}=a\right].\tag{1}\]

Both expectations are taken with respect to the Markov chain \((\boldsymbol{\mathcal{M}},f) := (\xi_k)_{k\geq 0} = (x_k, a_k)_{k\geq 0}\).

Remark 1. These expectations are well-defined as \(\gamma \in (0,1)\) and \(r(\cdot)\) are bounded; see the remarks at the beginning of Section 2 of [27].

We define further the state and state-action visiting measures of a policy \(f\):

Definition 3 (State and state-action visiting measures, see e.g. [2], [28] and Section 2 of [27]). Let \((\boldsymbol{\mathcal{M}},f) := (x_k, a_k)_{k\geq 0}\) be the Markov chain induced when the policy \(f\) acts on the MDP \(\boldsymbol{\mathcal{M}}\). Let \(\xi = (x,a) \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) be a state-action pair of the MDP \(\boldsymbol{\mathcal{M}}\). Let

\(\mathbb{P}(x_k = x)\) be the probability that \(x_k = x\) for \((\boldsymbol{\mathcal{M}},f)\), and
\(\mathbb{P}(x_k = x, a_k = a) := \mathbb{P}(x_k = x) f(x,a)\) be the probability that \(x_k = x\) and \(a_k = a\) for \((\boldsymbol{\mathcal{M}},f)\).

Then, we define the state and state-action visiting measures respectively as \(\nu_{\rho_0}^{f}\) and \(\sigma_{\rho_0}^{f}\), such that \[\label{visiting} \nu_{\rho_0}^{f}(\{x\}) = \sum_{k=0}^{\infty} \gamma^{k} \mathbb{P}\left(x_{k}=x\right), \quad \sigma_{\rho_0}^{f}(\{ (x, a) \})= \sum_{k=0}^{\infty} \gamma^{k} \mathbb{P}\left(x_{k}=x, a_{k}=a\right),\tag{2}\]

Remark 2.

Both \((1-\gamma) \nu^f_{\rho_0}(\cdot)\) and \((1-\gamma) \sigma^f_{\rho_0}(\cdot)\) are probability measures.
Define the auxiliary Markov chain induced when the policy \(f\) acts on the MDP \(\boldsymbol{\mathcal{M}}\) in terms of the state-action pair \(\tilde{\xi}_k := (\tilde{x}_k, \tilde{a}_k)\):

\[(\boldsymbol{\mathcal{M}},f)_\mathsf{aux}: (\tilde{x}_0, \tilde{a}_0) \sim \rho_0 \stackrel{\tilde{p}(\cdot | \tilde{x}_0, \tilde{a}_0)}{\stackrel{= \tilde{p}(\cdot | \tilde{\xi}_0)}{\xrightarrow{~~~~~~}}} \tilde{x}_1 \stackrel{f(\tilde{x}_1,\cdot)}{\xrightarrow{~~~~~~}} \tilde{a}_1 \stackrel{\tilde{p}(\cdot | \tilde{x}_1, \tilde{a}_1)}{\stackrel{= \tilde{p}(\cdot | \tilde{\xi}_1)}{\xrightarrow{~~~~~~}}} \tilde{x}_2 \stackrel{f(\tilde{x}_2, \cdot)}{\xrightarrow{~~~~~~}} \tilde{a}_2 \stackrel{\tilde{p}(\cdot | \tilde{x}_2, \tilde{a}_2)}{\stackrel{= \tilde{p}(\cdot | \tilde{\xi}_2)}{\xrightarrow{~~~~~~}}}\tilde{x}_3 \stackrel{f(\tilde{x}_3, \cdot)}{\xrightarrow{~~~~~~}} \tilde{a}_3 \cdots,\] where \[\tilde{p} \left(\tilde{x}^{\prime} \mid \tilde{x}, \tilde{a} \right)=\gamma p\left(\tilde{x}^{\prime} \mid \tilde{x}, \tilde{a} \right) + (1-\gamma) \rho_0\left(\tilde{x}^{\prime}\right), \quad \forall\left(\tilde{x}, \tilde{a}, \tilde{x}^{\prime}\right) \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}} \times \boldsymbol{\mathcal{X}}\] sample from the initial distribution \(\rho_0\) with probability \(1-\gamma\) at each transition to a new state. Then \((1-\gamma) \sigma^f_{\rho_0}\) is the stationary measure of the auxiliary Markov chain \((\boldsymbol{\mathcal{M}},f)_\mathsf{aux}\). This is proven on page 36 of [2].

We make the assumption on the transition \(p\) of an MDP \(\boldsymbol{\mathcal{M}}\) to ensure ergodicity for the Markov chains \((\boldsymbol{\mathcal{M}}, f)\) and \((\boldsymbol{\mathcal{M}}, f)_\mathsf{aux}\). The assumption is stated in terms of the total variation (TV) distance. The TV distance between two probability distributions on \(\boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) with masses \(p_1\) and \(p_2\) are defined as \[d_\mathsf{TV}(p_1, p_2) = \frac{1}{2} \sum_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} |p_1(\xi) - p_2(\xi)|.\]

Assumption 2 (Ergodicity of the MDP). We assume that the Markov chains \((\boldsymbol{\mathcal{M}}, f)\) and \((\boldsymbol{\mathcal{M}}, f)_\mathsf{aux}\) are both ergodic (irreducible and aperiodic) whenever \(f\) selects every action with positive probability. As a result, both \((\boldsymbol{\mathcal{M}}, f)\) and \((\boldsymbol{\mathcal{M}}, f)_\mathsf{aux}\) have a unique stationary distribution (see section 1.3.3 of [29] and page 36 of [2]), denoted as \(\pi^{f}\) and \(\sigma_{\rho_0}^{f}\) respectively. Furthermore, we assume that both \(\pi^{f}\) and \(\sigma_{\rho_0}^{f}\) are globally Lipschitz of \(f\) with respect to the TV distance, so that there exists \(C>0\) such that for any policies \(f,f'\), \[\max(d_\mathsf{TV}(\pi^f, \pi^{f'}), d_\mathsf{TV}(\sigma^f_{\rho_0}, \sigma^{f'}_{\rho_0})) \leq d_\mathsf{TV}(f,f').\]

2.3 Online Neural Network Actor-critic Algorithm↩︎

The main goal of reinforcement learning is to learn the optimal policy \(f^*\) which maximizes the expected discounted sum of the future rewards: \[\max\limits_{f} J(f),\] where the objective function \(J(f)\) is the state-value function, weighted by the initial state-action pair: \[J(f) = \mathbb{E}\left[\sum_{k=0}^{\infty} \gamma^{k} \cdot r\left(x_{k}, a_{k}\right)\right]=\sum\limits_{x\in \boldsymbol{\mathcal{X}}} \rho_0(x) V^{f}(x) = \sum\limits_{\xi = (x,a) \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} \sigma_{\rho_0}^{f}(\xi) r(\xi),\] see also equation (2.3) of [27]. Policy-based reinforcement learning methods optimize the objective function over a class of policies \(\left\{f_{\theta} \mid \theta \in \boldsymbol{\Theta}\right\}\) based on the policy gradient theorem [30]. In practice, the value functions are unknown and must therefore also be estimated. In this paper, we study the online actor-critic algorithms, which simultaneously estimate the action-value function using a critic model and the optimal policy using an actor model at every time step of the MDP:

The actor model, acting as the approximation of an optimal policy, is defined as \[f_\theta^{N}(\xi) = \textrm{Softmax}(P^N_\theta(\xi)) = \frac{\exp(P_\theta^{N}(x,a))}{\sum\limits_{a'}\exp(P_\theta^{N}(x,a'))}, \quad \xi = (x,a)\] where \(P^N_\theta(\xi)\) is the actor network: \[\label{actor32NN} P_\theta^{N}(\xi) = \frac{1}{\sqrt{N}} \sum_{i=1}^N B^{i} \sigma \left(U^i \cdot \xi \right),\tag{3}\] parametrised by the parameters \(\theta = (B^1, \ldots, B^N, U^1, \ldots U^N)\), where \(B^i \in \mathbb{R}\) and \(U^i \in \mathbb{R}^d\).
The critic model, acting as the approximation of the unknown state-action value function for the optimal policy (approximated by the actor model), is the critic network \[\label{critic32NN} Q_\omega^{N}(\xi) = \frac{1}{\sqrt{N}} \sum_{i=1}^N C^{i} \sigma \left( W^i \cdot \xi \right),\tag{4}\] parametrised by the parameters \(\omega = (C^1, \ldots, C^N, W^1, \ldots W^N)\), where \(C^i \in \mathbb{R}\) and \(W^i \in \mathbb{R}^d\).

Remark 3. We emphasise that

The outputs of actor and critic networks \(P^N_k, Q^N_k\) could be viewed as either functions on \(\boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) or as vectors in \(\mathbb{R}^M\) indexed by elements in \(\boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\), and
\(f^N_k\) refers to the actor model (i.e., the probability distribution output of the actor network), which could be viewed as either a function of \(\boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) or as a vector in \(\mathbb{R}^M\) indexed by elements in \(\boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\).

These interpretations are interchangeable.

Assumption 3 (Activation function). The scalar function \(\sigma(\cdot): \mathbb{R} \rightarrow \mathbb{R}\), known as the activation function, is assumed to be

twice continuously differentiable (i.e. in \(C^2_b(\mathbb{R})\)) with outputs and derivatives bounded by \(1\), and
slowly increasing, such that for any \(a > 0\), \[\lim_{x\to \pm \infty} \frac{\sigma(x)}{x^a} \to 0.\]

An example would be the standard sigmoid function \(\sigma(x) = (1+e^{-x})^{-1}\).

\(\theta_k = (B^1_k, \ldots, B^N_k, U^1_k, \ldots U^N_k)\) and \(\omega_k = (C^1_k, \ldots, C^N_k, W^1_k, \ldots W^N_k)\) are the trained parameters of the actor and critic networks after \(k\) training updates. We also define \(P^N_k := P^N_{\theta_k}\), \(f^N_k := \text{Softmax}(P^N_k)\) and \(Q^N_k := Q^N_{\omega_k}\).
Our Actor-critic algorithm is online, which means that the policies used to sample state-action pairs in the MDP will change at each iteration. Similar to the coupled system in [31], [32], our version of the Actor-critic algorithm will sample two parallel sequences of state-action pairs:

the “actor" process: \[\label{artificial32MDP32samples} (\boldsymbol{\mathcal{M}}, \mathsf{Ac}): (\widetilde{x}_0, \widetilde{a}_0) \sim \rho_0 \stackrel{\tilde{p}(\cdot | \tilde{x}_0, \tilde{a}_0)}{\stackrel{= \tilde{p}(\cdot | \tilde{\xi}_0)}{\xrightarrow{~~~~~~}}} \widetilde{x}_1 \stackrel{g^N_0(\widetilde{x}_1,\cdot)}{\xrightarrow{~~~~~~}} \widetilde{a}_1 \stackrel{\tilde{p}(\cdot | \tilde{x}_1, \tilde{a}_1)}{\stackrel{= \tilde{p}(\cdot | \tilde{\xi}_1)}{\xrightarrow{~~~~~~}}} \widetilde{x}_2 \stackrel{g^N_1(\widetilde{x}_2, \cdot)}{\xrightarrow{~~~~~~}} \widetilde{a}_2 \stackrel{\tilde{p}(\cdot | \tilde{x}_2, \tilde{a}_2)}{\stackrel{= \tilde{p}(\cdot | \tilde{\xi}_2)}{\xrightarrow{~~~~~~}}}\widetilde{x}_3 \stackrel{g^N_2(\widetilde{x}_3, \cdot)}{\xrightarrow{~~~~~~}} \widetilde{a}_3 \cdots,\tag{5}\] and
the “critic" process: \[\label{origin32MDP32samples} (\boldsymbol{\mathcal{M}}, \mathsf{Cr}): (x_0, a_0) \sim \rho_0 \stackrel{p(\cdot |x_0, a_0)}{\stackrel{= p(\cdot | \xi_0)}{\xrightarrow{~~~~~~}}} x_1 \stackrel{g^N_0(x_1,\cdot)}{\xrightarrow{~~~~~~}} a_1 \stackrel{p(\cdot |x_1, a_1)}{\stackrel{= p(\cdot | \xi_1)}{\xrightarrow{~~~~~~}}} x_2 \stackrel{g^N_1(x_2, \cdot)}{\xrightarrow{~~~~~~}} a_2 \stackrel{p(\cdot |x_2, a_2)}{\stackrel{= p(\cdot | \xi_2)}{\xrightarrow{~~~~~~}}} x_3 \stackrel{g^N_2(x_3,\cdot)}{\xrightarrow{~~~~~~}} a_3 \cdots,\tag{6}\]

where the exploration policy \(g^N_k\) is defined as \[\label{ActorwithExploration} g_{k}^N(\xi) = \frac{\eta_k^N}{\#\boldsymbol{\mathcal{A}}} + (1 - \eta_k^N) \cdot f_{k}^N(\xi), \quad \xi = (x,a),\tag{7}\] and \((\eta_k^N)_{k\geq 0}\) is a sequence of exploration rates such that \(0 < \eta_k^N \leq 1\) and \(\eta_k^N \overset{k\to\infty}\to 0\). This ensures that each action in \(\boldsymbol{\mathcal{A}}\) is selected with probability at least \(\eta_k^N / \#\boldsymbol{\mathcal{A}} > 0\), and so by Assumption 2 the induced Markov chains \((\boldsymbol{\mathcal{M}}, g^N_k)\) and \((\boldsymbol{\mathcal{M}}, g^N_k)_\mathsf{aux}\) are both ergodic, and the stationary measures \(\pi^{g^N_\theta}\) and \(\sigma^{g^N_\theta}_{\rho_0}\) are well-defined (exist and are unique). This will be made precise in Lemma 10.
We will now describe the two main steps of the online actor-critic algorithm at each optimization iteration.

2.3.0.1 Step 1: Update of the critic network:

We first update the critic network’s parameters by temporal difference learning [33]. Temporal difference learning aims to take a stochastic gradient descent step at the sample critic loss with respect to the critic network parameters \(\omega_k\): \[L^{\theta_k} (\omega_k) := \sum_{\xi} \left[Y_k(\xi) - Q^{N}_k(\xi) \right]^2 \pi^{f^N_k},\] where the “target" \(Y_k\) is defined as \[Y_k(\xi) := r(\xi) + \gamma \sum_{x'} \left[\sum_{a'} Q^N_k(x',a') f^N_k(x',a')\right] p(x'\big{|}\xi)\] and \(\pi^{f^N_\theta}\) is the unique stationary distribution of the Markov chain \((\boldsymbol{\mathcal{M}}, f^N_\theta)\) as specified in Assumption 1. In fact, if \(\pi^{f^N_k}(\xi) > 0\) for all \(\xi \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) and \(L^{\theta_k}(\omega_k)=0\), then \(Q^N_k(\xi)\) satisfies the Bellman equation and hence is a value function of \(f^N_k\).

Unfortunately the stationary distribution \(\pi^{f^N_k}(\xi)\) is inaccessible, so we use \(\xi_k = (x_k, a_k)\) from the critic process \((\boldsymbol{\mathcal{M}}, \mathsf{Cr})\) as a sample of \(\pi^{f^N_k}\) to estimate and evaluate the gradient over the sample critic loss \[\ell^{\theta_k}(\omega_k) := \left[ Y_k(\xi_k) - Q^N_{\omega_k}(\xi_k) \right]^2.\] We emphasise that the critic process \((\boldsymbol{\mathcal{M}}, \mathsf{Cr})\) evolves as the following for any \(k \geq 1\): \[x_{k+1} \sim p(\cdot \,|\, \xi_k) = p(\cdot \,|\, x_k, a_k), \quad a_{k+1} \sim g^N_{\color{red} k}(x_k, \cdot).\] Further note that the term \(Y_k(\xi_k)\) involves an expectation of \(Q^N_{\omega_k}(\cdot,\cdot)\) with respect to the distribution \(f^N_{\theta_k}(\cdot, \cdot) p(\cdot \big{|} \xi_k)\), which could be replaced by the estimate \(Q(\xi_{k+1})\). Treating the target \(Y^{\theta_k}(\xi_k)\) as constant, we have the following gradient-descent-like update for the critic parameters

\[\begin{align} C^{i}_{k+1} &= C^{i}_k + \frac{\alpha^N}{\sqrt{N}} \left( r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right) \sigma \left(W^i_k \cdot \xi_k \right), \\ W^i_{k+1} &= W^i_k + \frac{\alpha^N}{\sqrt{N}} \left( r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right) C^{i}_k \sigma' \left( W^i_k \cdot \xi_k \right) \xi_k, \addtocounter{equation}{1}\label{lkygsivq} \end{align}\tag{8}\] where \(\alpha^N = 1/N\) is the scaling of the step size of parameter updates, chosen so that the parameter updates converge to a limiting ODE as \(N\to\infty\).

2.3.0.2 Step 2: Update of the actor network:

We then use the policy gradient theorem [28] to update the actor network’s parameters. The policy gradient theorem states that if a policy \(f_\theta\) is parametrised by \(\theta\), then \[\nabla_\theta V^{f_\theta}(x) = \sum_{x} \left( \sum_{k\geq 0} \mathbb{P}(x_k = x \,|\, x_0) \right) \sum_a \nabla_\theta f_\theta(x,a) V^{f_\theta}(x,a).\] Therefore \[\begin{align} \nabla_\theta J(\theta) &= \sum_{x_0} \left[ \sum_{x} \left( \sum_{k\geq 0} \mathbb{P}(x_k = x \,|\, x_0) \right) \sum_a \nabla_\theta f_\theta(x,a) V^{f_\theta}(x,a) \right] \rho_0(x_0) \\ &= \sum_{x,a,x_0} \left( \sum_{k\geq 0} f_\theta(x,a) \mathbb{P}(x_k = x \,|\, x_0) \rho_0(x_0) \right) \frac{1}{f_\theta(x,a)} \nabla_\theta f_\theta(x,a) V^{f_\theta}(x,a) \\ &= \sum_{x,a} \sigma^{f_\theta}_{\rho_0}(\{(x,a)\}) \nabla_\theta (\ln f_\theta(x,a)) V^{f_\theta}(x,a) \addtocounter{equation}{1}\label{eq:policy95gradient} \end{align}\tag{9}\] This is an expectation of the quantity \(\nabla_\theta (\ln f_\theta(x,a)) V^{f_\theta}(x,a)\) with respect to the visiting measure \(\sigma^{f_\theta}_{\rho_0}(\cdot)\). Since we do not have access to the visiting measure \(\sigma^{f_\theta}_{\rho_0}(\cdot)\), we estimate this gradient as in [17], [24] by evaluating the quantity \(\nabla_\theta (\ln f_\theta(\tilde{\xi}_k)) V^{f_\theta}(\tilde{\xi}_k)\), where \(\tilde{\xi}_k := (\tilde{x}_k, \tilde{a}_k)\) is taken from the actor process \((\boldsymbol{\mathcal{M}}, \mathsf{Ac})\) as a sample from the visiting measure \(\sigma^{f^N_k}_{\rho_0}(\cdot)\). The actor process \((\boldsymbol{\mathcal{M}},\mathsf{Ac})\) evolves as follows for any \(k \geq 1\): \[\tilde{x}_{k+1} \sim \tilde{p}(\cdot \,|\, \tilde{\xi}_k) = \tilde{p}(\cdot \,|\, \tilde{x}_k, \tilde{a}_k), \quad \tilde{a}_{k+1} \sim g^N_k(\tilde{x}_{k+1}, \cdot).\] The partial derivatives of the actor model \(f^N_\theta = \mathrm{Softmax}(P^N_\theta)\) with respect to the parameters \(\theta\) are: \[\begin{align} \frac{d}{dB^i} \ln f^N_\theta(x,a) &= \frac{d}{dB^i} \left( P^N_\theta(x,a) - \ln\left( \sum_{a'} \exp\left( P^N_\theta(x,a') \right) \right) \right) \\ &= \frac{d}{dB^i} \left( f^N_\theta(x,a) \right) - \frac{\sum_{a'} \frac{d}{dB^i} \exp\left( P^N_\theta(x,a') \right)}{\sum_{a''} \exp\left( P^N_\theta(x,a'') \right)} \\ &= \frac{d}{dB^i} \left( f^N_\theta(x,a) \right) - \frac{\sum_{a'} \exp\left( P^N_\theta(x,a') \right) \frac{d}{dB^i} P^N_\theta(x,a')}{\sum_{a''} \exp\left( P^N_\theta(x,a'') \right)} \\ &= \frac{1}{\sqrt{N}} \sigma(U^i \cdot (x,a)) - \sum_{a'} \left( \frac{\exp\left( P^N_\theta(x,a') \right)}{\sum_{a''} \exp\left( P^N_\theta(x,a'') \right)} \frac{1}{\sqrt{N}} \sigma(U^i \cdot (x,a')) \right)\\ &= \frac{1}{\sqrt{N}} \left( \sigma(U^i \cdot (x,a)) - \sum_{a'} f^N_\theta(x,a') \sigma(U^i \cdot (x,a')) \right), \addtocounter{equation}{1}\end{align}\] and \[\begin{align} \nabla_{U^i}(\ln f^N_\theta(x,a)) = \frac{1}{\sqrt{N}} \left( B^i \sigma'(U^i \cdot (x,a)) (x,a) - \sum_{a'} f^N_\theta(x,a') B^i \sigma'(U^i \cdot (x,a')) (x,a') \right). \end{align}\] In our online actor-critic algorithm, we will replace the action-value function \(V^{f_{\theta_k}}(x,a)\) by its estimate, i.e. the clipped critic \(\mathsf{clip}(Q^N_k(\cdot,\cdot))\), where \[\mathsf{clip}(x) = \max(\min(x, 2),0).\] The clipping is here to ensure that the magnitude of updates for parameters \(B^i_k\) and \(U^i_k\) are bounded. Clipping is a common technique used in practice in deep learning and is also necessary for our convergence analysis as \(N \to \infty\).

Therefore, the actor network’s parameters are updated according to: \[\begin{align} B^i_{k+1} &= B^i_k + \frac{\zeta^N_k}{N\sqrt{N}} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left( \sigma(U^i \cdot (\tilde{\xi}_k)) - \sum_{a''} f^N_k(\tilde{x}_k, a'') \sigma(U^i \cdot (\tilde{x}_k, a'')) \right), \\ U^i_{k+1} &= U^i_k + \frac{\zeta^N_k}{N\sqrt{N}} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left( B^i_k \sigma'(U^i_k \cdot (\tilde{\xi}_k)) (\tilde{\xi}_k) - \sum_{a''} f^N_k(\tilde{x}_k,a'') B^i_k \sigma'(U^i_k \cdot (\tilde{x}_k,\tilde{a}_k)) (\tilde{x}_k,a'') \right), \addtocounter{equation}{1}\label{NACActorupdates} \end{align}\tag{10}\] where \(\zeta^N_k / N\) is the learning rate.

The complete online Actor-Critic algorithm – for simultaneously training both the actor and critic networks – is summarised in Algorithm 1 below.

Figure 1: Online Actor-Critic Algorithm with Neural Network Approximation

The main contribution of this paper is to prove that the evolution of the “actor" and”critic" networks trained with this online Actor-Critic algorithm weakly converge to the solution of a limiting ODE as \(N \rightarrow \infty\). We then study the evolution the limiting ODE to characterise the convergence of the online Actor-Critic algorithm. Specifically, we are able to prove that as training time \(t \rightarrow \infty\) (A) the limit critic network converges to the true value function for the actor’s policy and (B) the limit actor network converges to a stationary point of the objective function.

Assumption 4. In practical implementation, both the “actor" and”critic" networks should contain bias parameters, and should be written in the form \[\frac{1}{\sqrt{N}} \sum_{i=1}^N C^i \sigma(\mathsf{weight}^i \cdot (x,a) + \mathsf{bias}^i),\] where \(\mathsf{bias}^i \in \mathbb{R}\). The bias parameter could be incorporated into the weight vectors by introducing an additional column of \(1\) in the state vector \(x\), so that the networks could be expressed as \[\frac{1}{\sqrt{N}} \sum_{i=1}^N C^i \sigma(\widetilde{\mathsf{weight}}^i \cdot (x',a)), \quad x' = (x,1).\] We make this as an assumption of the MDP state space \(\boldsymbol{\mathcal{X}}\). We further assume that the elements in \(\mathcal{X} \times \mathcal{A}\) are in distinct directions (as defined on page 192 of [34]).

3 Main Result↩︎

Our results are proven under some assumptions for the neural networks, MDP and learning rates.

Assumption 5. For the actor network in 3 and critic network in 4 , we assume:

The randomly initialized parameters \(\left(C^i_0, W^i_0, B^i_0, U^i_0 \right)\) are independent and identically distributed (i.i.d.) mean-zero random variables for all \(i\) with distribution \(\nu_{0}(dc,dw) \otimes \mu_0(db,dw)\), where \(\otimes\) refers to the product of measures.
\(\nu_0\) and \(\mu_0\) are absolutely continuous with respect to the Lebesgue measure,
for each \(i\), \(C^i_0\), \(W^i_0\), \(B^i_0\), \(U^i_0\) are mutually independent, and
\(\max_i(|C_0^i|, |B_0^i|, \mathbb{E}_{\nu_0}\|W^i_0\|, \mathbb{E}_{\nu_0}\|U^i_0\|) \leq 1\) and \(\mathbb{E}[C^i_0] = \mathbb{E}[B^i_0] = 0\).

We assume further that \(\nu_0 = \mu_0\) for simplicity, although this additional assumption could be easily removed.

Our convergence proof also requires a careful choice for the learning rate and exploration rate.

Assumption 6. The learning rate and exploration rate are: \[\begin{align} \label{learning32rates} \zeta_k^N &= \frac{1}{ 1 + \frac{k}{N} }, \quad \eta_k^N = \frac{1}{ 1 + \log^2 (\frac{k}{N}+1) }, \\ \text{thus, as N \rightarrow \infty,} \quad \zeta^N_{\floor{Nt}} \rightarrow \zeta_t &= \frac{1}{ 1 + t }, \quad \eta^N_{\floor{Nt}} \rightarrow \eta_t = \frac{1}{ 1 + \log^2 (t+1) }. \end{align}\tag{11}\] The learning rate and exploration rate in 11 satisfy the following properties for any integer \(n \in \mathbb{N}\): \[\begin{align} \label{hyper32property} \int_0^\infty \zeta_s ds = \infty, \quad \int_0^{\infty} \zeta^2_t dt < \infty, \quad \int_0^\infty \zeta_s\eta_s ds < \infty, \quad \lim_{t \to \infty}\frac{\zeta_t}{\eta^{n}_t} = 0. \end{align}\tag{12}\]

We prove that the outputs of the actor and critic models converge to the solution of a nonlinear ODE system as the number of hidden units for the neural networks \(N \to \infty\). We define the empirical measures \[\mu_{k}^{N}=\frac{1}{N} \sum_{i=1}^{N} \delta_{B_{k}^i, U_k^i}, \quad \nu_{k}^{N}=\frac{1}{N} \sum_{i=1}^{N} \delta_{C_{k}^i, W_k^i}.\] In addition, we define the following time-rescaled processes for any \(\xi = (x,a) \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) \[\begin{align} P^N_t(\xi) &= P_{\floor{Nt}}^{N}(\xi), \quad f_{t}^{N}(\xi) = f_{\floor{Nt}}^{N}(\xi), \quad g_{t}^{N}(\xi) = g_{\floor{Nt}}^{N}(\xi), \\ Q^N_t(\xi) &= Q_{\floor{Nt}}^{N}(\xi), \quad \mu_{t}^{N} = \mu_{\floor{Nt}}^{N}, \quad \nu_{t}^{N} = \nu_{\floor{Nt}}^{N}. \addtocounter{equation}{1}\label{eq:rescaled95updates} \end{align}\tag{13}\] Using Assumptions 3 and 5, we know that \(\mu_{0}^{N}, \nu_{0}^{N} \stackrel{d}{\rightarrow} \nu_0\) and \(P_0^N, Q_{0}^{N} \stackrel{d}{\rightarrow} \mathcal{G}, \mathcal{H}\) as \(N \rightarrow \infty\), where \(\mathcal{G}, \mathcal{H}\) are mean-zero Gaussian random variables by the law of large numbers and central limit theorem for i.i.d. random variables, respectively.
Define the state space for the time-rescaled process \(\left(\mu_{t}^{N}, \nu_t^N, P_{t}^{N}, Q_t^N \right)\): \[E = \mathcal{M}(\mathbb{R}^{1+d}) \times \mathcal{M}(\mathbb{R}^{1+d}) \times \mathbb{R}^M \times \mathbb{R}^M, \quad d = d_x + d_a, \quad M = |\mathcal{X} \times \mathcal{A}|,\] where \(\mathcal{M}(\mathbb{R}^{1+d})\) is the set of all probability measures on \(\mathbb{R}^{1+d}\). Define the space \[D_E([0, T]) = \{\text{c\`adl\`ag paths } f: [0,T] \to E\}.\] We will study the convergence of the time-rescaled process (13 ) in the space \(D_E([0,T])\) as \(N \rightarrow \infty\).

The following definitions will also be used in our analysis:

The inner-product of a measure \(\nu\) and a function \(f\) is: \[\left \langle f, \nu \right \rangle= \int f \, d\nu,\]
The kernel matrix that will appears in our limit ODE in theorem 4 is: \[A_{\xi, \xi^{\prime}} = \left\langle\sigma\left(w \cdot \xi^{\prime}\right) \sigma(w \cdot \xi) + c^{2} \sigma^{\prime}\left(w \cdot \xi^{\prime}\right) \sigma^{\prime}(w \cdot \xi) (\xi \cdot \xi^{\prime}), \nu_0(dc,dw)\right\rangle,\] where \(\xi' = (x', a')\).

The convergence of the online actor-critic algorithm is characterised by the following theorems:

Theorem 4. Let Assumptions 3 and 5 hold, and let the learning rate for the critic parameter updates be \(\alpha^{N}=\alpha/N\) for an \(\alpha > 0\). Then, the process \(\left(\mu_{t}^{N}, \nu_t^N, P_{t}^{N}, Q_t^N \right)\) converges weakly in the space \(D_E([0, T])\) as \(N \rightarrow \infty\) to the process \(\left(\mu_{t}, \nu_t, P_{t}, Q_t\right)\), so that for any \(t \in[0, T]\), any \((x, a) \in \mathcal{X} \times \mathcal{A}\), and for every \(\varphi, \bar{\varphi} \in C_{b}^{2}\left(\mathbb{R}^{1+d}\right)\), the limit process \(\left(\mu_{t}, \nu_t, P_{t}, Q_t\right)\) satisfies the random ODE: \[\label{NN32gradient32flow} \begin{align} \frac{dQ_t}{dt}(\xi) &= \alpha \sum_{\xi' = (x',a')} A_{\xi,\xi'} \left(r(\xi') + \gamma \sum_{z, a''} Q_t(z, a'') g_t(z,a'') p(z| \xi') - Q_t(\xi') \right) \pi^{g_t}(\xi'),\\ \frac{dP_t}{dt}(\xi) &= \sum_{\xi' = (x', a')} \zeta_t \mathsf{clip}(Q_t(\xi')) \left[A_{\xi,\xi'} - \sum_{a''} f_t(x',a'') A_{\xi,x',a''} \right] \sigma_{\rho_0}^{g_t}(\xi'), \\ P_0(\xi) &= \mathcal{G}(\xi), \quad Q_0(\xi) = \mathcal{H}(x, a) \\ \left\langle \varphi, \mu_{t}\right\rangle &=\left\langle \bar{\varphi}, \nu_{0}\right\rangle, \quad \left\langle \varphi, \nu_{t}\right\rangle =\left\langle \varphi, \nu_{0}\right\rangle, \end{align}\tag{14}\] where \(\mathcal{G}, \mathcal{H}\) are the weak limits of \(P^N_0\) and \(Q^N_0\), which are mean-zero Gaussian random variables, and \[f_t(\xi) = \mathrm{Softmax}(P_t(\xi)), \quad g_t(\xi) = \frac{\eta_t}{\#\boldsymbol{\mathcal{A}}} + (1-\eta_t) f_t(\xi).\]

We note the following property of the matrix \(A\) shown in the section 7 of [26]:

Lemma 1. Under Assumptions 3 and 4, the matrix \(A\) is positive definite.

Due to the matrix \(A\) being positive definite, we can prove that the limit critic network converges to the state-action value function and the limit actor network converges to a stationary point of the objective function:

Theorem 5. If the actor network \(P_t\) and critic network \(Q_t\) evolved according to the limit ODE 14 , then under assumptions 3 and 4, the critic network converges globally to the value function of the policy \(f_t = \mathrm{Softmax}(P_t)\) as \(t \to \infty\): \[\label{critic32convergence} \left\| Q_t - V^{f_t} \right\|_\infty = \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} |Q_t(\xi) - V^{f_t}(\xi)| = O(\eta_t).\tag{15}\] Moreover, the actor network converges to a stationary point: \[\label{actor32convergence} \nabla_{P} J(f_t) \overset{t\to\infty}\to 0.\tag{16}\]

Remark 6. We note that the choice of norm/distance to study the pre-limit processes \((P^N_t, Q^N_t)\) in Theorem 4 does not matter as \((P^N_t, Q^N_t) \in \mathbb{R}^{2M}\) is finite dimensional. The choice of norm for Theorem 5 does not matter for the same reason. We will use \(\|\cdot\|_\infty\) as the supremum norm as defined in 15 \[\|P - \tilde{P}\|_\infty = \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} |P(\xi) - \tilde{P}(\xi)|\] and the usual Euclidean norm \[\|P - \tilde{P}\| = \left( \sum_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} |P(\xi) - \tilde{P}(\xi)| \right)^{1/2}\] Note that the Softmax function is Lipschitz in the following sense: there exist constants \(C, C' >0\) such that for \(P, \tilde{P} \in \mathbb{R}^M\), \[d_\mathsf{TV}(\mathrm{Softmax}(P), \mathrm{Softmax}(\tilde{P})) \leq C' \|P - \tilde{P}\|_\infty.\]

4 Derivation of the limit ODEs↩︎

We use the following steps to prove convergence to the limit ODE system:

We first derive a pre-limit evolution process for the outputs of the actor and critic networks, and a-priori bounds on the magnitude of changes to the parameters at each update step. The pre-limit process will contain stochastic remainder terms with dependence on non-i.i.d. data samples.
We prove the relative compactness of the pre-limit process, which requires proofs of the compact containment and regularity of the sample paths.
We then use the Poisson equation to prove the stochastic remainder terms in the pre-limit process vanish as \(N\to+\infty\).
We prove the existence and uniqueness of the limits ODEs.
Finally, we combine the above results to prove the convergence in Theorem 4.

4.1 Evolution of the Pre-limit Processes↩︎

Before presenting the technical details of the proof, we first highlight some important details for the derivation of the limit ODE system of the neural actor-critic algorithm (algorithm 1).

Definition 4. For a random variable \(Z_N\),

\(Z_N = O_p(\beta_N)\) if \(Z_N/\beta_N\) is stochastically bounded, i.e. for any \(\epsilon > 0\), there exists \(M<\infty\) and some \(N_0 < \infty\) such that \[\mathbb{P}\left(\left|\frac{Z_N}{\beta_N}\right| > M\right) < \epsilon, \quad \forall N > N_0.\]
The notation \(Z_N = O(\beta_N)\) means there exists a constant \(C<\infty\) independent of \(N\) such that \[|Z_N| \le C |\beta_N|, \quad \forall N.\]

In the following proofs, constants \(C, C_T\) denote generic constants and we will sometimes we use \(\xi, \xi_k, \xi'_k, \tilde{\xi}_k\) to denote the state-action pairs \((x, a), (x_k, a_k), (x'_k, a'_k), (\tilde{x}_k, \tilde{a}_k)\), respectively. For the learning rate \(\alpha^N = 1/N\), the online actor-critic algorithm (algorithm 1) could therefore be written as: \[\begin{align} B^i_{k+1} &= B^i_k + \frac{\zeta^N_k}{N^{3/2}} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left( \sigma(U^i \cdot (\tilde{\xi}_k)) - \sum_{a''} f^N_k(\tilde{x}_k,a'') \sigma(U^i \cdot (\tilde{x}_k, a'')) \right), \\ U^i_{k+1} &= U^i_k + \frac{\zeta^N_k}{N^{3/2}} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left( B^i_k \sigma'(U^i_k \cdot \tilde{\xi}_k) \tilde{\xi}_k - \sum_{a''} f^N_k(\tilde{x}_k,a'') B^i_k \sigma'(U^i_k \cdot \tilde{\xi}_k) (\tilde{x}_k, a'') \right) \\ C^{i}_{k+1} &= C^{i}_k + \frac{\alpha}{N^{3/2}} \left(r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right) \sigma \left(W^i_k \cdot \xi_k \right), \\ W^i_{k+1} &= W^i_k + \frac{\alpha}{N^{3/2}} \left( r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right) C^{i}_k \sigma' \left( W^i_k \cdot \xi_k \right) \xi_k. \addtocounter{equation}{1}\label{eq:updates95repeated} \end{align}\tag{17}\]

The evolution of the actor and critic network \(Q_k^N\) can be studied by using Taylor expansions. For the critic network, one has: \[\begin{align} \label{Q32update} Q^N_{k+1}(\xi) &= Q^N_k(\xi)+\frac{1}{\sqrt{N}} \sum_{i=1}^{N} \left[(C^i_{k+1}-C_k^i) \sigma(W_{k+1}^i \cdot \xi) + (\sigma(W_{k+1}^i \cdot \xi) - \sigma(W_{k}^i \cdot \xi)) C_k^i \right] \\ &= Q^N_k(\xi)+\frac{1}{\sqrt{N}} \sum_{i=1}^{N} \bigg[(C^i_{k+1}-C_k^i) \left( \sigma(W^i_k \cdot \xi) + \sigma'(W^{i,*}_k \cdot \xi) (W^i_{k+1} - W^i_k) \cdot \xi \right) \\ &+ C_k^i \left( \sigma'(W^{i}_k \cdot \xi) (W^i_{k+1} - W^i_k) \cdot \xi + \frac{1}{2} \sigma''(W^{i,**}_k \cdot \xi) ((W^i_{k+1}-W^i_k) \cdot \xi)^2 \right) \bigg], \\ &= Q^N_k(\xi)+\frac{1}{\sqrt{N}} \sum_{i=1}^{N} \bigg[(C^i_{k+1}-C_k^i) \left( \sigma(W^i_k \cdot \xi) + C^i_k \sigma'(W^{i}_k \cdot \xi) (W^i_{k+1} - W^i_k) \cdot \xi \right) + \mathsf{error\;term}, \addtocounter{equation}{1}\end{align}\tag{18}\] where \(W^{i,*}_k\) and \(W^{i,**}_k\) are points in the line segment connecting the points \(W^i_k\) and \(W^i_{k+1}\). Substituting the parameter updates 17 , we have the following pre-limit evolution equation: \[\begin{align} Q^N_{k+1}(\xi) &= Q^N_k(\xi)+\frac{1}{\sqrt{N}} \sum_{i=1}^{N} \left[(C^i_{k+1}-C_k^i) \sigma(W_k^i \cdot \xi)+\sigma'(W_k^i \cdot \xi) C_k^i (W^i_{k+1}-W_k^i) \cdot \xi \right] + \mathsf{error\;term}\\ &= Q^N_k(\xi) + \frac{\alpha}{N^2} \left[ r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right] \\ &\phantom{=}\times \sum_{i=1}^N \left( \sigma(W^i_k \cdot \xi_k) \sigma(W^i_k \cdot \xi) + (C^i_k)^2 \sigma'(W^i_k \cdot \xi) \sigma(W^i_k \cdot \xi_k) (\xi \cdot \xi_k) \right) + \mathsf{error\;term}. \addtocounter{equation}{1}\end{align}\] If we let \[\begin{align} \mathsf{B}^N_{\xi, \xi', k} & = \frac{1}{N} \sum_{i=1}^{N} \left[ \sigma(W_k^i \cdot \xi')\sigma(W_k^i \cdot \xi) + (C_k^i)^2 \sigma'(W_k^i \cdot \xi')\sigma'(W_k^i \cdot \xi) (\xi' \cdot \xi) \right]\\ &= \langle \sigma(w \cdot \xi')\sigma(w \cdot \xi) + c^2 \sigma'(w \cdot \xi')\sigma(w \cdot \xi) (\xi' \cdot \xi), \nu_k^N \rangle, \addtocounter{equation}{1}\label{eq:B} \end{align}\tag{19}\] then \[\begin{align} Q^N_{k+1}(\xi) &= Q^N_k(\xi)+\frac{\alpha}{N} \left[ r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right] \mathsf{B}^N_{\xi,\xi_k,k} + \mathsf{error\;term}. \addtocounter{equation}{1}\label{eq:evolution95of95q951} \end{align}\tag{20}\] For the actor network, one has \[\begin{align} P^N_{k+1}(\xi) &= P^N_k(\xi) + \frac{1}{\sqrt{N}} \sum_{i=1}^{N} \left[(B^i_{k+1}-B_k^i) \sigma(U_{k+1}^i \cdot \xi) + (\sigma(U_{k+1}^i \cdot \xi) - \sigma(U_{k}^i \cdot \xi)) B_k^i \right]\\ &= P^N_k(\xi) + \frac{1}{\sqrt{N}} \sum_{i=1}^{N} \bigg[(B^i_{k+1}-B_k^i) \left( \sigma(U^i_k \cdot \xi) + \sigma'(U^{i,*}_k \cdot \xi) (U^i_{k+1} - U^i_k) \cdot \xi \right) \\ &\phantom{=}+ B_k^i \left( \sigma'(U^{i}_k \cdot \xi) (U^i_{k+1} - U^i_k) \cdot \xi + \frac{1}{2} \sigma''(U^{i,**}_k \cdot \xi) ((U^i_{k+1}-U^i_k) \cdot \xi)^2 \right) \bigg] \\ &= P^N_k(\xi) + \sum_{i=1}^{N} \frac{\zeta^N_k}{N^2} \mathsf{clip}(Q^N_k(\tilde{\xi}_{k})) \Bigg[\sigma(U_k^i \cdot \xi)\left( \sigma(U^i_k \cdot \tilde{\xi}_k) - \sum_{a''} f^N_k(\tilde{x}_k, a'') \sigma(U^i_k \cdot (\tilde{x}_k, a'')) \right) \\ &\phantom{=}+ (B_k^i)^2 \sigma'(U_k^i \cdot \xi) \left( \sigma'(U^i_k \cdot \tilde{\xi}_k) \xi^\top \tilde{\xi}_k - \sum_{a''} f^N_k(\tilde{x}_k, a'') \sigma'(U^i_k \cdot (\tilde{x}_k, a'')) ((\tilde{x}_k, a'') \cdot \xi) \right) \Bigg] \\ &\phantom{=}+ \mathsf{error\;term}, \addtocounter{equation}{1}\end{align}\] where \(U^{i,*}_k\) and \(U^{i,**}_k\) are points in the line segment connecting the points \(U^i_k\) and \(U^i_{k+1}\). We define the tensor \[\label{eq:bar95B} \begin{align} \bar{\mathsf{B}}^N_{\xi, \xi', k} &= \frac{1}{N} \sum_{i=1}^{N} \left[ \sigma(U_k^i \cdot \xi')\sigma(U_k^i \cdot \xi) + (B_k^i)^2 \sigma'(U_k^i \cdot \xi')\sigma'(U_k^i \cdot \xi) (\xi'^ \cdot\xi) \right]\\ &= \langle \sigma(u \cdot \xi')\sigma(u \cdot \xi) + b^2 \sigma'(u \cdot \xi')\sigma'(u \cdot \xi) (\xi' \cdot \xi), \mu_k^N \rangle. \end{align}\tag{21}\] Then, \[\label{eq:evolution95of95p95with95tensor} P^N_{k+1}(\xi) = P^N_k(\xi) + \frac{\zeta^N_k}{N} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left[ \bar{\mathsf{B}}^N_{\xi, \tilde{\xi}_k, k} - \sum_{a''} f^N_k(\tilde{x}_k, a'') \bar{\mathsf{B}}^N_{\xi,(\tilde{x}_k,a''),k} \right] + \mathsf{error\;term}.\tag{22}\] There are a several error terms in the above evolution equations, which we will precisely define and analyze in the next section of this paper. Specifically, we will:

prove that the increments of the parameters at each update step are bounded,
prove a-priori \(L^2\) bounds for the outputs of the actor and critic networks,
analyze the size of the error terms in the pre-limit evolution equation,
rewrite the pre-limit evolution in terms of fluctuation terms, and
study the evolution of the empirical measure of the parameters.

4.1.1 Bounds for the increments of the parameters↩︎

Lemma 2 (A-priori bounds of size of increments of parameters). For any fixed \(T>0\), any \(k\) such that \(k \leq TN\) and \(i \in [N] = \{1,...,N\}\), there exists a constant \(C_T<\infty\) that only depends on \(T\) such that \[\max\left( \left|C^i_k \right|, \mathbb{E}\|W_k^i\|, |B^i_k|, \mathbb{E}\| U_k^i \| \right) < C_T,\] and that \[\max\left( \left|C^i_{k+1} - C^i_k \right|, \left\|W^i_{k+1} - W^i_k \right\| \right) \leq \frac{C_T}{N}.\] Moreover, \[\max\left( \left|B^i_{k+1} - B^i_k \right|, \left\|U^i_{k+1} - U^i_k \right\| \right) < \frac{C_T}{N^{3/2}}\]

Proof. As \(\sigma\) is bounded by 1 by assumption 3, we have \[\max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} |Q^N_k(\xi)| = \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} \left| \frac{1}{\sqrt{N}} \sum_{i=1}^N C^i_k \sigma(W^i_k \cdot \xi) \right| \leq \frac{1}{\sqrt{N}} \sum_{i=1}^N |C^i_k|\] We may then obtain a recursive bound for \(|C^i_k|\): \[\begin{align} \left|C^i_{k+1} - C^i_k\right| &\leq \frac{\alpha^N}{\sqrt{N}} \left| r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right| \cdot \left| \sigma(W^i_k \cdot \xi_k) \right| \\ &\leq \frac{\alpha}{N^{3/2}} \left( \left| r(\xi_k) \right| + (1 + \gamma) \max_{\xi \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}} } \left| Q^N_k(\xi) \right|\right) \cdot \left| \sigma (W^i_k \cdot \xi_k) \right| \\ &{\le} \frac{\alpha}{N^{3/2}} \left( 1 + (\gamma+1) \frac{1}{\sqrt{N}} \sum_{i=1}^N |C^i_k| \right) \\ &= \frac{\alpha}{N^{3/2}} + \frac{\alpha}{N^2} \sum_{i=1}^N |C^i_k|. \addtocounter{equation}{1}\end{align}\] By recursively using the triangle inequality, and recalling that \(C^i_0\) is a bounded random variable, we have \[\begin{align} |C^i_k| \leq |C^i_0| + \sum_{j=1}^k (|C^i_j - C^i_{j-1}|) &\leq 1 + \sum_{j=1}^k \left( \frac{\alpha}{N^{3/2}} + \frac{\alpha}{N^2} \sum_{i=1}^N |C^i_{j-1}| \right) \\ &= 1 + \frac{\alpha}{N^{1/2}} + \frac{\alpha}{N^2} \sum_{j=1}^k \sum_{i=1}^N |C^i_{j-1}|. \addtocounter{equation}{1}\label{eq:recursion95bound95Cik} \end{align}\tag{23}\] Define \[\displaystyle{m_k^N = \frac{1}{N} \sum_{i=1}^N |C^i_k|}.\] Then \[m_k^N \leq \frac{1}{N} \sum_{i=1}^N \left( 1 + \frac{\alpha}{N^{1/2}} + \frac{\alpha}{N^2} \sum_{j=1}^k \sum_{l=1}^N |C^l_{j-1}| \right) \le C + \frac{\alpha}{N} \sum_{j=1}^k m_{j-1}^N.\] By the discrete Gronwall’s lemma and using \(k \le TN\), \[m_k^N \leq C\exp\left( \frac{\alpha k}{N} \right) \le C_T\] Plugging this into 23 yields \[\label{C32bound} \left|C^i_k\right| \le \left| C_0^i \right| + \frac{C}{N^{1/2}} + \frac{C}{N}\sum_{j=1}^k m_{j-1}^N \le \left| C_0^i \right| + \frac{C}{N^{1/2}} + C_T \le C_T,\tag{24}\] We could bootstrap with this a-priori bound to show that \[|C^i_{k+1} - C^i_k| \leq \frac{C}{N^{3/2}} + N \times \frac{C}{N^2} \times C_T \leq \frac{C_T}{N}.\] We can similarly get the bound for \(\left\| W_k^i \right\|\). In fact, \[\begin{align} \left\| W^i_{k+1} - W^i_k \right\| &\leq \frac{\alpha^N}{\sqrt{N}} \left| r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right| \cdot \left| C^{i}_k \sigma'\left( W^i_k \cdot \xi_k \right) \right| \|\xi_k\| \\ &\leq \frac{C_T}{N^{\frac{3}{2}}} \left( C + (\gamma+1) N^{-\frac{1}{2}} \sum_{i=1}^N |C^i_k| \right) \overset{\eqref{C32bound}}{\le} \frac{C_T}{N}, \addtocounter{equation}{1}\label{eq:diff95of95W} \end{align}\tag{25}\] Taking expectation and using assumptions 3 and 5 yields \[\mathbb{E}\left\| W^i_{k} \right\| \leq \mathbb{E}\left\| W^i_{0} \right\| + \sum_{j=0}^{k-1} \mathbb{E}\left\| W^i_{k+1} - W^i_k \right\| \leq C_T.\]

For the boundedness of parameters in the actor network, observe that \[\begin{align} |B^i_{k+1} - B^i_k| &\leq \zeta^N_k N^{-\frac{3}{2}} |\mathsf{clip}(Q^N_k(\tilde{\xi}_k))| \cdot \sup_{a''} \left| \sigma(\tilde{x}_k, a'') \right| \cdot \left( 1 + \sum_{a''} f^N_k(\tilde{x}_k, a'') \right) < \frac{C}{N^{3/2}} \addtocounter{equation}{1}\label{eq:diff95of95B} \end{align}\tag{26}\] then by telescoping series, we have for all \(k \leq NT\) \[|B^i_k| \leq |B^i_0| + C\frac{k}{N^{\frac{3}{2}}} \leq C + C \frac{T}{N^{\frac{1}{2}}} \le C_T.\] As the state-action space is finite, we also have \[\left\| U^i_{k+1} - U^i_k \right\| \leq \zeta^N_k N^{-\frac{3}{2}} \left|\mathsf{clip}(Q^N_k(\tilde{\xi}_k))\right| |B^i_k| \left(1+\sum_{a''} f^N_k (\tilde{x}_k, a'')\right) \cdot \sup_{\xi \in \mathcal{X}\times \mathcal{A}} \left\| \xi \right\| \le \frac{C_T}{N^{3/2}},\] which yields \[\mathbb{E}\left\| U^i_k \right\| \leq \mathbb{E}\left\| U^i_0 \right\| + C_T \frac{k}{N^{\frac{3}{2}}} \leq C + \frac{C_T}{N^{\frac{1}{2}}} \leq C_T, \quad \forall k \le TN.\] ◻

Lemma 3 (Increments of entries in the pre-limit kernels). For all \(k \leq NT\), \[\max_{\xi, \xi' \in \mathcal{X}\times \mathcal{A}} \max\left[ \left| \mathsf{B}^N_{\xi,\xi',k+1}-\mathsf{B}^N_{\xi,\xi',k} \right|, \left| \bar{\mathsf{B}}^N_{\xi,\xi',k+1}-\bar{\mathsf{B}}^N_{\xi,\xi',k} \right| \right] \leq \frac{C_T}{N},\] where the kernels \(\mathsf{B}^N_{\xi,\xi',k}\), \(\bar{\mathsf{B}}^N_{\xi,\xi',k}\) are defined in 19 and 21 respectively. Consequently, one could show by method of telescoping series that for all \(k \leq NT\) \[\label{pre32kernel32bound} \max_{\xi, \xi' \in \mathcal{X}\times \mathcal{A}} \max\left[ \left| \mathsf{B}^N_{\xi,\xi',k} \right|, \left| \bar{\mathsf{B}}^N_{\xi,\xi',k} \right| \right] \leq C_T,\tag{27}\]

Proof. The proof for the case of kernel \(\bar{\mathsf{B}}^N\) is exactly the same with the proof for the case of \(\mathsf{B}^N\), for which we could utilise our a-priori bound of increments \(\max(|C^i_{k+1} - C^i_k|, \left\| W^i_{k+1}-W^i_k \right\|) \leq C_T/N\) to prove our result. To the end, for all \(\xi,\xi' \in \mathcal{X}\times \mathcal{A}\), we have \[\begin{align} &\phantom{=}\left| \left \langle\sigma(w \cdot \xi') \sigma(w \cdot \xi), \, \nu^N_{k+1} - \nu^N_k \right \rangle \right| \\ &\leq \frac{1}{N} \sum_{i=1}^N \left| \sigma(W^i_{k+1} \cdot \xi') \sigma(W^i_{k+1} \cdot \xi) - \sigma(W^i_k \cdot \xi') \sigma(W^i_k \cdot \xi) \right| \\ &\leq \frac{1}{N} \sum_{i=1}^N \left[ \left| \sigma(W^i_{k+1} \cdot \xi') - \sigma(W^i_k \cdot \xi') \right| \left| \sigma(W^i_{k+1} \cdot \xi) \right| + \left| \sigma(W^i_{k+1} \cdot \xi) - \sigma(W^i_k \cdot \xi) \right| \left| \sigma(W^i_k \cdot \xi') \right| \right] \\ &\leq \frac{1}{N} \sum_{i=1}^N (|\xi'| + |\xi|) \left\| W^i_{k+1} - W^i_k \right\| \leq \frac{C_T}{N}. \addtocounter{equation}{1}\label{eq:B95increment95term951} \end{align}\tag{28}\] Similarly, \[\begin{align} &\phantom{=}\left| \left \langle c^2 \sigma'(w \cdot \xi') \sigma'(w \cdot \xi), \, \nu^N_{k+1} - \nu^N_k \right \rangle \right| \\ &\leq \frac{1}{N} \sum_{i=1}^N \left| (C^i_{k+1})^2 \sigma(W^i_{k+1} \cdot \xi') \sigma(W^i_{k+1} \cdot \xi) - (C^i_k)^2 \sigma(W^i_k \cdot \xi') \sigma(W^i_k \cdot \xi) \right| \\ &\leq \frac{1}{N} \sum_{i=1}^N \Big[\left| (C^i_{k+1})^2 - (C^i_k)^2 \right| \left| \sigma(W^i_{k+1} \cdot \xi') \right| \left| \sigma(W^i_{k+1} \cdot \xi) \right| \\ &\phantom{=}+ (C^i_k)^2\left| \sigma(W^i_{k+1} \cdot \xi') - \sigma(W^i_k \cdot \xi') \right| \left| \sigma(W^i_{k+1} \cdot \xi) \right| + (C^i_k)^2 \left| \sigma(W^i_{k+1} \cdot \xi) - \sigma(W^i_k \cdot \xi) \right| \left| \sigma(W^i_k \cdot \xi') \right| \Big] \addtocounter{equation}{1}\end{align}\] We have the control \[\left| (C^i_{k+1})^2 - (C^i_k)^2 \right| \leq \left| C^i_{k+1} - C^i_k \right|^2 + 2|C^i_k||C^i_{k+1} - C^i_k| \leq \frac{C^2_T}{N^2} + \frac{2C^2_T}{N} \leq \frac{C_T}{N}.\] By combining this with our previous analyses, we have \[\left| \left \langle c^2 \sigma'(w \cdot \xi') \sigma'(w \cdot \xi), \, \nu^N_{k+1} - \nu^N_k \right \rangle \right| \leq \frac{1}{N} \sum_{i=1}^N \left[ \frac{C_T}{N} + C_T \times \frac{C_T}{N} + C_T \times \frac{C_T}{N} \right] = \frac{C_T}{N}. \label{eq:B95increment95term952}\tag{29}\] Summing up 28 and 29 yields \(|\mathsf{B}^N_{\xi,\xi',k+1} - \mathsf{B}^N_{\xi,\xi',k}| \leq C_T/N\), uniformly in \(\xi,\xi'\). It remains for us to show that there is a \(C>0\), independent of \(T\), such that \(|B^N_{\xi,\xi',0}| \leq C\). This is clearly true by the sure boundedness of \(\sigma(\cdot), \sigma'(\cdot)\) and \(C^i_0\) as guaranteed in assumption 3 and 5. Therefore, we could consider the telescoping sum \[\left| \mathsf{B}^N_{\xi,\xi',k} \right| \leq \left| \mathsf{B}^N_{\xi,\xi',0} \right| + \sum_{j=0}^{k-1} \left| \mathsf{B}^N_{\xi,\xi',j+1} - \mathsf{B}^N_{\xi,\xi',j} \right| \leq C + N \times \frac{C_T}{N} \leq C_T,\] which completes our proof. ◻

4.1.2 \(L^2\) bounds of network outputs↩︎

Using lemma 2 and 3, we can now establish the bound for the neural networks.

Lemma 4 (A-priori \(L^2\) bound for the outputs of the critic network). For all \(k\) such that \(k \leq TN\), there is a \(C_T<\infty\) such that \[\mathbb{E}\left[ \max_{(x,a) \in \mathcal{X}\times \mathcal{A}} |Q^N_k(x,a)|^2 \right] < C_T.\]

Proof. We first prove the statement for \(k = 0\). Since \(C^i_0\) and \(\sigma(W^i_0 \cdot \xi)\) are both bounded by 1, we have \[\begin{align} \mathbb{E}\left[ \max_{\xi \in \mathcal{X}\times \mathcal{A}} |Q^N_0(\xi)|^2 \right] \leq \mathbb{E}\left[ \sum_{\xi \in \mathcal{X}\times \mathcal{A}} |Q^N_0(\xi)|^2 \right] &\leq \sum_{\xi \in \mathcal{X}\in \mathcal{A}} \mathbb{E}\left[ \frac{1}{\sqrt{N}}\sum_{i=1}^N C^i_0 \sigma(W^i_0 \cdot \xi) \right]^2 \\ &\leq \frac{C}{N} \sum_{i=1}^N \mathbb{E}\left[ C^i_0 \sigma(W^i_0 \cdot \xi) \right]^2 \leq C < \infty, \addtocounter{equation}{1}\label{eq:expectation95max95Q0} \end{align}\tag{30}\] We now provide an \(L^2\) control over the maximum increments of the outputs \(Q^N_k(\xi)\). Recall that \[\label{Q32update32bound} Q^N_{k+1}(\xi) - Q^N_k(\xi) = \frac{1}{\sqrt{N}} \sum_{i=1}^N \left[ (C^i_{k+1} - C^i_k) \sigma(W^i_{k+1} \cdot \xi) + C^i_k (\sigma(W^i_{k+1} \cdot \xi) - \sigma(W^i_{k+1} \cdot \xi)) \right],\tag{31}\] so \[\begin{align} \left| Q^N_{k+1}(\xi) - Q^N_k(\xi) \right|^2 &\overset{\mathsf{(CS)}}\leq \frac{2}{N} \left[ \left( \sum_{i=1}^N (C^i_{k+1} - C^i_k) \sigma(W^i_{k+1} \cdot \xi) \right)^2 + \left( \sum_{i=1}^N C^i_k (\sigma(W^i_{k+1} \cdot \xi) - \sigma(W^i_k \cdot \xi)) \right)^2 \right] \\ &\overset{\mathsf{(CS)}}\leq \frac{2}{N} \left[ \sum_{i=1}^N (C^i_{k+1} - C^i_k)^2 \sum_{i=1}^N \left( \sigma(W^i_{k+1} \cdot \xi) \right)^2 + \sum_{i=1}^N (C^i_k)^2 \sum_{i=1}^N \left( \sigma(W^i_{k+1} \cdot \xi) - \sigma(W^i_k \cdot \xi) \right)^2 \right] \\ &\leq 2 \left[ \sum_{i=1}^N (C^i_{k+1} - C^i_k)^2 + C_T \sum_{i=1}^N \left( \sigma(W^i_{k+1} \cdot \xi) - \sigma(W^i_k \cdot \xi) \right)^2 \right]. \addtocounter{equation}{1}\label{eq:apriori95bound95of95increment95of95Q} \end{align}\tag{32}\] Hence \[\begin{align} \left|C^i_{k+1} - C^i_k \right|^2 &\leq \frac{(\alpha^N)^2}{N} \left( r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right)^2 \left( \sigma(W^i_k \cdot \xi_k) \right)^2 \\ &\overset{\mathsf{(CS)}}\leq \frac{3\alpha}{N^3}\left[ (r(\xi_k))^2 + \gamma^2 (Q^N_k(\xi_{k+1})))^2 + \left( Q^N_k(\xi_k) \right)^2 \right] \\ &\leq \frac{3\alpha}{N^3} \left( 1 + (1+\gamma^2) \max_{\xi \in \boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}}|Q^N_k(\xi)|^2 \right) \addtocounter{equation}{1}\end{align}\] Making use of the mean-value inequality (and the fact that \(|\sigma'| \leq 1\) by assumption 3), one could show similarly \[\begin{align} &\phantom{=} |\sigma(W^i_{k+1} \cdot \xi) - \sigma(W^i_k \cdot \xi)|^2 \\ &\leq |(W^i_{k+1} - W^i_k) \cdot \xi|^2 \\ &\leq \frac{(\alpha^N)^2}{N} \left( r(\xi_k) + \gamma \sum_{a''} Q^N_k(x_{k+1},a'') g^N_k(x_{k+1},a'') - Q^N_k(\xi_k) \right)^2 \left( \sigma(W^i_k \cdot \xi_k) \right)^2 (C^i_k)^2 (\xi_k \cdot \xi)^2 \\ &\leq \frac{3\alpha C_T^2}{N^3} \left( 1 + (1+\gamma^2) \max_{\xi \in \boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}}|Q^N_k(\xi)|^2 \right), \addtocounter{equation}{1}\end{align}\] noting that \((\xi_k \cdot \xi)^2\) is bounded by some constant \(C\) as \(\xi, \xi_k\) are elements from the finite set \(\boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}\). Substituting into 32 yields \[\left| Q^N_{k+1}(\xi) - Q^N_k(\xi) \right|^2 \leq \frac{C_T}{N^2} \left( 1 + (1+\gamma^2) \max_{\xi \in \boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}}|Q^N_k(\xi)|^2 \right).\] Therefore for any \(\xi\) and \(k \leq NT\), \[\begin{align} |Q^N_k(\xi)|^2 &= \left( Q^N_0(\xi) + \sum_{j=0}^{N-1} (Q^N_{j+1}(\xi) - Q^N_j(\xi)) \right)^2 \\ &\overset{\mathsf{(CS)}}= 2\left( Q^N_0(\xi) \right)^2 + 2\left( \sum_{j=0}^{k-1} (Q^N_{j+1}(\xi) - Q^N_j(\xi)) \right)^2 \\ &\overset{\mathsf{(CS)}}\leq 2\left( Q^N_0(\xi) \right)^2 + NT \sum_{j=0}^{k-1} (Q^N_{j+1}(\xi) - Q^N_j(\xi))^2 \\ &\leq 2\max_{\xi \in \boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}} |Q^N_0(\xi)|^2 + \frac{C_T}{N} \sum_{j=0}^{k-1} \left( 1 + (1+\gamma^2) \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}}|Q^N_j(\xi)|^2 \right). \addtocounter{equation}{1}\end{align}\] Taking maximum then expectation yields \[\begin{align} \mathbb{E}\left[ \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}}|Q^N_k(\xi)|^2 \right] &\leq 2 \mathbb{E}\left[ \max_{\xi \in \boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}} |Q^N_0(\xi)|^2 \right] + \frac{C_T}{N} + \frac{C_T}{N} \sum_{j=0}^{k-1} \mathbb{E}\left[ \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}}|Q^N_j(\xi)|^2 \right] \\ &\leq C_T + \frac{C_T}{N} \sum_{j=0}^{k-1} \mathbb{E}\left[ \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}}|Q^N_j(\xi)|^2 \right]. \addtocounter{equation}{1}\end{align}\] We conclude by discrete Gronwall’s lemma that for all \(k \leq TN\): \[\mathbb{E}\left[ \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}}|Q^N_k(\xi)|^2 \right] \leq C_T \exp\left( C_T \frac{k}{N} \right) \leq C_T < +\infty.\] ◻

Lemma 5 (A-priori \(L^2\) bound for the outputs of the actor network). For all \(k\) such that \(k \leq NT\), there is a \(C_T<\infty\) such that \[\mathbb{E}\left[ \max_{(x,a) \in \mathcal{X}\times \mathcal{A}} \left|P^N_k(x,a)\right|^2 \right] < C_T.\]

Proof. Again we first prove the statement for \(k=0\). Since \(B^i_0\) and \(\sigma(W^i_0 \cdot \xi)\) are bounded by 1, \[\begin{align} \mathbb{E}\left[ \max_{\xi \in \mathcal{X}\times \mathcal{A}} |P^N_0(\xi)|^2 \right] \leq \mathbb{E}\left[ \sum_{\xi \in \mathcal{X}\times \mathcal{A}} |P^N_0(\xi)|^2 \right] &\leq \sum_{\xi \in \mathcal{X}\in \mathcal{A}} \mathbb{E}\left[ \frac{1}{\sqrt{N}}\sum_{i=1}^N B^i_0 \sigma(U^i_0 \cdot \xi) \right]^2 \\ &\leq \frac{C}{N} \sum_{i=1}^N \mathbb{E}\left[ B^i_0 \right]^2 \leq C < \infty. \addtocounter{equation}{1}\end{align}\] The increments could again be controlled by noting \[\begin{align} |P^N_{k+1}(\xi) - P^N_k(\xi)| &\leq \frac{1}{\sqrt{N}} \sum_{i=1}^{N} \left[(B^i_{k+1}-B_k^i) \sigma(U_{k+1}^i \cdot \xi) + (\sigma(U_{k+1}^i \cdot \xi) - \sigma(U_{k}^i \cdot \xi)) B_k^i \right] \\ &\leq \frac{1}{\sqrt{N}} \sum_{i=1}^{N} \left[\left| B^i_{k+1}-B_k^i \right| \left| \sigma(U_{k+1}^i \cdot \xi) \right| + \left| \sigma(U_{k+1}^i \cdot \xi) - \sigma(U_{k}^i \cdot \xi) \right| \left| B_k^i \right| \right] \end{align}\] By the mean-value inequality and the fact that both \(\sigma\) and \(\sigma'\) are bounded by 1 by assumption 3, \[|P^N_{k+1}(\xi) - P^N_k(\xi)| \leq \frac{1}{\sqrt{N}} \sum_{i=1}^{N} \frac{C_T}{N^{3/2}} = \frac{C_T}{N^{2}}.\] Therefore for all \(\xi\), \[\begin{align} |P^N_k(\xi)|^2 = \left( P^N_0(\xi) + \sum_{j=0}^{k-1} (P^N_{j+1}(\xi) - P^N_j(\xi)) \right)^2 &\leq 2 \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}}|P^N_0(\xi)|^2 + 2N \sum_{j=0}^{k-1}(P^N_{j+1}(\xi) - P^N_j(\xi))^2 \\ &\leq 2 \max_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} |P^N_0(\xi)|^2 + \frac{C_T}{N^2}. \addtocounter{equation}{1}\end{align}\] Taking supremum then expectation yields the result. ◻

4.1.3 Pre-limit evolution of the network outputs↩︎

We can now control the unspecified error terms in the pre-limit evolutions of the actor and critic networks.

Proposition 7 (Evolution of the actor and critic networks). For \(k \leq NT\), the evolution of the critic network yields, \[\begin{align} \mathbb{E}\left[ \max_\xi \left| Q^N_{k+1}(\xi) - Q^N_k(\xi) - \frac{\alpha}{N} \left( r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right) \mathsf{B}^N_{\xi,\xi_k,k} \right| \right] \leq \frac{C_T}{N^{5/2}}, \end{align}\] while the evolution of the actor network yields \[\begin{align} \max_\xi \left| P^N_{k+1}(\xi) - P^N_k(\xi) - \frac{\zeta^N_k}{N} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left( \bar{\mathsf{B}}^N_{\xi, \tilde{\xi}_k, k} - \sum_{a''} f^N_k(\tilde{x}_k, a'') \bar{\mathsf{B}}^N_{\xi,(\tilde{x}_k,a''),k} \right) \right| \leq \frac{C_T}{N^{5/2}}. \end{align}\]

Proof. We begin by noting for all \(\xi\), \[\begin{align} &\phantom{=}\left| Q^N_{k+1}(\xi) - Q^N_k(\xi) - \frac{\alpha}{N} \left( r(\xi_k) + \gamma \sum_{a''} Q^N_k(x_{k+1},a'') g^N_k(x_{k+1},a'') - Q^N_k(\xi_k) \right) \mathsf{B}^N_{\xi,\xi_k,k} \right| \\ &= \frac{1}{\sqrt{N}} \left| \sum_{i=1}^N \sigma'(W^{i,*}_k \cdot \xi) (C^i_{k+1}-C^i_k)(W^i_{k+1}-W^i_k) \cdot \xi + \frac{\sigma''(W^{i,**}_k \cdot \xi) C^i_k}{2}((W^i_{k+1}-W^i_k)\cdot \xi)^2 \right| \\ &\overset{\mathsf{(CS)}}\leq \frac{1}{\sqrt{N}} \sum_{i=1}^N \left[ \left| C^i_{k+1}-C^i_k \right| \left\| W^i_{k+1}-W^i_k \right\| \|\xi\| + C_T \left\| W^i_{k+1}-W^i_k \right\|^2 \|\xi\|^2 \right] \\ &\leq \frac{1}{\sqrt{N}} \sum_{i=1}^N \frac{C_T}{N^{3}} \left( 1+(1+\gamma) \max_{\xi \in \boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}}|Q^N_k(\xi)| \right)^2 \leq \frac{C_T}{N^{5/2}} \left( 1 + (1+\gamma)^2 \max_{\xi \in \boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}} |Q^N_k(\xi)|^2 \right) \addtocounter{equation}{1}\end{align}\] Taking maximum and expectation yields \[\begin{align} &\phantom{=}\mathbb{E}\left[ \max_\xi \left| Q^N_{k+1}(\xi) - Q^N_k(\xi) - \frac{\alpha}{N} \left( r(\xi_k) + \gamma \sum_{a''} Q^N_k(x_{k+1},a'') g^N_k(x_{k+1},a'') - Q^N_k(\xi_k) \right) \mathsf{B}^N_{\xi,\xi_k,k} \right| \right] \\ &\leq \frac{C_T}{N^{5/2}} \mathbb{E}\left[ 1 + (1+\gamma)^2 \max_{\xi \in \boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}} |Q^N_k(\xi)|^2 \right] \leq \frac{C_T}{N^{5/2}}. \addtocounter{equation}{1}\end{align}\] Similarly, for all \(\xi\), \[\begin{align} &\phantom{=}\left| P^N_{k+1}(\xi) - P^N_k(\xi) - \frac{\zeta^N_k}{N} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left( \bar{\mathsf{B}}^N_{\xi, \tilde{\xi}_k, k} - \sum_{a''} f^N_k(\tilde{x}_k, a'') \bar{\mathsf{B}}^N_{\xi,(\tilde{x}_k,a''),k} \right) \right| \\ &=\frac{1}{\sqrt{N}} \left| \sum_{i=1}^N \sigma'(U^{i,*}_k \cdot \xi) (B^i_{k+1}-B^i_k)(U^i_{k+1}-U^i_k) \cdot \xi + \frac{\sigma''(U^{i,**}_k \cdot \xi) C^i_k}{2}((U^i_{k+1}-U^i_k)\cdot \xi)^2 \right| \\ &\overset{\mathsf{(CS)}}\leq \frac{1}{\sqrt{N}} \sum_{i=1}^N \left[ \left| B^i_{k+1}-B^i_k \right| \left\| U^i_{k+1}-U^i_k \right\| \|\xi\| + C_T \left\| U^i_{k+1}-U^i_k \right\|^2 \|\xi\|^2 \right] \leq \frac{C_T}{N^{5/2}}. \end{align}\] This completes the proof. ◻

Using the notation introduced in definition 4, one could write \[\begin{align} Q^N_{k+1}(\xi) &= Q^N_k(\xi)+\frac{\alpha}{N} \left[ r(\xi_k) + \gamma \sum_{a''} Q^N_k(x_{k+1},a'') g^N_k(x_{k+1},a'') - Q^N_k(\xi_k) \right] \mathsf{B}^N_{\xi,\xi_k,k} + O_p(N^{-5/2}). \tag{33} \\ P^N_{k+1}(\xi) &= P^N_k(\xi) + \frac{\zeta^N_k}{N} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left[ \bar{\mathsf{B}}^N_{\xi, \tilde{\xi}_k, k} - \sum_{a''} f^N_k(\tilde{x}_k, a'') \bar{\mathsf{B}}^N_{\xi,(\tilde{x}_k,a''),k} \right] + O(N^{-5/2}). \tag{34} \end{align}\]

4.1.3.1 Network evolution

We recall that \(P^N_t(\xi) = P^N_{\floor{Nt}}\), \(f^N_t(\xi) = f^N_{\floor{Nt}}(\xi)\), \(g^N_t(\xi) = g^N_{\floor{Nt}}(\xi)\), \(Q^N_t(\xi) = Q^N_{\floor{Nt}}\), and define \(\mathsf{B}^N_{\xi,\xi',s} = \mathsf{B}^N_{\xi,\xi',\floor{Ns}}\) and \(\bar{\mathsf{B}}^N_{\xi,\xi',s} = \bar{\mathsf{B}}^N_{\xi,\xi',\floor{Ns}}\). We further define the fluctuation terms: \[\begin{align} M^{1,N}_t(\xi) &= -\frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} Q^N_k(\xi_k) \mathsf{B}^N_{\xi, \xi_k, k} + \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} \sum_{\xi'} Q^N_k(\xi') \mathsf{B}^N_{\xi, \xi', k} \pi^{g_k^N}(\xi'), \\ M^{2,N}_t(\xi) &= \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} r(\xi_k) \mathsf{B}^N_{\xi, \xi_k, k} - \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} \sum_{\xi'} r(\xi') \mathsf{B}^N_{\xi, \xi', k} \pi^{g_k^N}(\xi'), \\ M^{3,N}_t(\xi) &= \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} \gamma Q^N_k(\xi_{k+1}) \mathsf{B}^N_{\xi, \xi_k, k} - \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} \sum_{\xi'} \sum_{z, a''} \gamma Q^N_k(z, a'') g^N_k(z, a'') \mathsf{B}^N_{\xi, \xi', k} p(z| \xi') \pi^{g_k^N}(\xi'), \addtocounter{equation}{1}\label{eq:MNt} \end{align}\tag{35}\] then \[\begin{align} Q_t^N(\xi) &= Q_0^N(\xi) + \sum_{k=0}^{\floor{Nt}-1} [Q^N_{k+1}(\xi) - Q^N_k(\xi)] \\ &= Q_0^N(\xi) + \frac{\alpha}{N} \sum_{k=0}^{\floor{Nt}-1} \left[ r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right] \mathsf{B}^N_{\xi,\xi_k,k} + O_p(N^{-3/2}) \\ &= Q_0^N(\xi) + \frac{\alpha}{N} \sum_{k=0}^{\floor{Nt}-1} \sum_{\xi'} \mathsf{B}^N_{\xi,\xi',k} \pi^{g^N_k}(\xi') \bigg( -Q^N_k(\xi') + r(\xi') + \gamma \sum_{z,a''} Q^N_k(z,a'') g^N_k(z,a'') p(z|\xi') \bigg) \\ &\phantom{=}+ \alpha \left( M^{1,N}_t(\xi) + M^{2,N}_t(\xi) + M^{3,N}_t(\xi) \right) + O_p(N^{-3/2}) \\ &= Q_0^N(\xi) + \frac{\alpha}{N} \sum_{k=0}^{\floor{Nt}-1} \int_{k/N}^{k+1/N} \sum_{\xi'} \mathsf{B}^N_{\xi,\xi',\floor{Ns}} \pi^{g^N_{\floor{Ns}}}(\xi') \bigg( r(\xi') + \gamma \sum_{z,a''} Q^N_{\floor{Ns}}(z,a'') g^N_{\floor{Ns}}(z,a'') p(z|\xi') \\ &\phantom{=}- Q^N_{\floor{Ns}}(\xi') \bigg) \, ds + \alpha \left(M^{1,N}_t(\xi) + M^{2,N}_t(\xi) + M^{3,N}_t(\xi) \right) + O_p(N^{-3/2}) \\ &= Q_0^N(\xi) + \alpha \int_0^t \sum_{\xi'} \mathsf{B}^N_{\xi, \xi', s} \pi^{g_s^N}(\xi') \left[r(\xi') + \gamma \sum_{z, a''} Q^N_s(z, a'') g^N_s(z, a'') p(z|\xi') - Q^N_s(\xi') \right]ds\\ &\phantom{=}+ \alpha \left( M^{1,N}_t(\xi) + M^{2,N}_t(\xi) + M^{3,N}_t(\xi) \right) + O_p(N^{-3/2}). \addtocounter{equation}{1}\label{eq:Q95pre95limit} \end{align}\tag{36}\] Similarly, define the fluctuation terms \[\begin{align} \label{concentration2} M^{N}_t(\xi) &= \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} \zeta^N_k \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left[\bar{\mathsf{B}}^{N}_{\xi,\tilde{\xi}_k,k} - \sum_{a''} f^N_k(\tilde{x}_k,a'') \bar{\mathsf{B}}^{N}_{\xi,(\tilde{x}_k,a''), k} \right] \\ &- \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} \zeta^N_k \sum_{\xi'} \mathsf{clip}(Q^N_k(\xi')) \left[\bar{\mathsf{B}}^{N}_{\xi,\xi',k} - \sum_{a''} f^N_k(x', a'') \bar{\mathsf{B}}^{N}_{\xi,(x', a''),k} \right] \sigma_{\rho_0}^{g_k^N}(\xi'), \end{align}\tag{37}\] where \(\sigma_{\rho_0}^{g_k^N}(\xi')\) is the visiting measure of Markov chain as defined in 5 . Then: \[\begin{align} P^N_t(\xi) &= P^N_0(\xi) + \sum_{k=0}^{\floor{Nt}-1} (P^N_{k+1}(\xi) - P^N_k(\xi)) \\ &= P^N_0(\xi) + \sum_{k=0}^{\floor{Nt}-1} \frac{\zeta^N_k}{N} \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \left[ \bar{\mathsf{B}}_{\xi, \tilde{\xi}_k, k} - \sum_{a''} f^N_k(\tilde{x}_k, a'') \bar{\mathsf{B}}_{\xi,(\tilde{x}_k,a''),k} \right] + O(N^{-3/2}) \\ &= P^N_0(\xi) + \sum_{k=0}^{\floor{Nt}-1} \zeta^N_k \sum_{\xi'} \mathsf{clip}(Q^N_k(\xi')) \left[\bar{\mathsf{B}}^N_{\xi,\xi',k} - \sum_{a''} f^N_k(x', a'') \bar{\mathsf{B}}^N_{\xi,(x', a''),k} \right] \sigma_{\rho_0}^{g_k^N}(\xi') \\ &\phantom{=}+ \alpha M^N_t(x, a) + O(N^{-3/2}) \\ &= P^N_0(\xi) + \sum_{k=0}^{\floor{Nt}-1} \int_{k/N}^{(k+1)/N} \zeta^N_{\floor{Ns}} \sum_{\xi'} \mathsf{clip}(Q^N_{\floor{Ns}}(\xi')) \Bigg[\bar{\mathsf{B}}^{N}_{\xi,\xi',\floor{Ns}} \\ &\phantom{=}- \sum_{a''} f^N_{\floor{Ns}}(x', a'') \bar{\mathsf{B}}^{N}_{\xi,(x', a''),\floor{Ns}} \Bigg] \sigma_{\rho_0}^{g^N_{\floor{Ns}}}(\xi') + \alpha M^N_t(x, a) + O(N^{-3/2}) \\ &= P^N_0(\xi) + \int_0^t \zeta^N_{\floor{Ns}} \sum_{\xi'} \sigma_{\rho_0}^{g^N_s}(\xi') \, \mathsf{clip}(Q^N_s(\xi')) \Bigg[\bar{\mathsf{B}}^N_{\xi, \xi', s} - \sum_{a''} f^N_s(x',a'') \bar{\mathsf{B}}_{\xi, (x', a''), s} \Bigg] ds \\ &\phantom{=}+ M^N_t(\xi) + O(N^{-3/2}). \addtocounter{equation}{1}\end{align}\]

4.1.4 Evolution of empirical measure↩︎

The evolution of the empirical measure \(\nu^N_k\) can be characterized in terms of their projection onto test functions \(\varphi \in C^2_b(\mathbb{R}^{1+M})\), by Taylor’s expansion \[\begin{align} \label{Q32measure32pre32limit} \left \langle\varphi, \nu^N_{k+1} \right \rangle- \left \langle\varphi, \nu^N_k \right \rangle &= \frac{1}{N} \sum_{i=1}^N (\varphi(C^i_{k+1},W^i_{k+1}) - \varphi(C^i_k,W^i_k)) \\ &= \frac{1}{N} \sum_{i=1}^N \bigg[\partial_c \varphi(C^i_k,W^i_k) (C^i_{k+1} - C^i_k) + \partial_w \varphi(C^i_k,W^i_k) \cdot (W^i_{k+1} - W^i_k) \\ &+ \frac{1}{2} \Big(\partial^2_c \varphi(C^{i,*}_k,W^{i,*}_k) (C^i_{k+1} - C^i_k)^2 + (C^i_{k+1} - C^i_k) \partial^2_{cw} \varphi(C^{i,**}_k,W^{i,**}_k) (W^i_{k+1} - W^i_k) \\ &+ (W^i_{k+1} - W^i_k) \cdot \partial^2_{w} \varphi(C^{i,***}_k,W^{i,***}_k) (W^i_{k+1} - W^i_k) \Big)\bigg], \end{align}\tag{38}\] where \(\left( C^{i,*}_k, W^{i,*}_k \right), \left( C^{i,**}_k, W^{i,**}_k \right), \left( C^{i,***}_k, W^{i,***}_k \right)\) are points lying on the line segments connecting between \(\left( C^{i}_k, W^{i}_k \right)\) and \(\left( C^{i}_{k+1}, W^{i}_{k+1} \right)\). Substituting [NACCriticupdates] into 38 , we have \[\begin{align} \left \langle\varphi, \nu^N_{k+1} \right \rangle- \left \langle\varphi, \nu^N_k \right \rangle &= \frac{1}{N} \sum_{i=1}^N \left[ \partial_c \varphi(C^i_k,W^i_k) (C^i_{k+1} - C^i_k) + \partial_w \varphi(C^i_k,W^i_k) \cdot (W^i_{k+1} - W^i_k) \right] + O_p(N^{-2}) \\ &= \alpha N^{- \frac{5}{2}} \left( r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right) \\ &\phantom{=}\times \sum_{i=1}^N \left( \partial_c \varphi(C^i_k, W^i_k)\sigma(W^i_k \cdot \xi_k)) + C^i_k \sigma'(W^i_k \cdot \xi_k) \partial_w \varphi(C^i_k, W^i_k) \xi_k \right) + O_p(N^{-2}) \\ &= \alpha N^{-\frac{3}{2}} \left( r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right) \\ &\phantom{=}\times \left \langle\partial_c \varphi(c,w) \sigma(w \cdot \xi_k) + c \sigma'(w \cdot \xi_k) \partial_w \varphi(c,w) \xi_k, \nu^N_k \right \rangle+ O_p(N^{-3}). \addtocounter{equation}{1}\end{align}\] Therefore, the time-rescled empirical measure \(\nu^N_t := \nu^N_{\floor{Nt}}\) satisfies \[\begin{align} \left \langle\varphi, \nu^N_t \right \rangle- \left \langle\varphi, \nu^N_0 \right \rangle &= \alpha N^{-\frac{3}{2}} \sum_{k=0}^{\floor*{Nt}-1} \left( r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right) \\ &\phantom{=}\times \left \langle\partial_c \varphi(c,w) \sigma(w \cdot \xi_k) + c \sigma'(w \cdot \xi_k) \partial_w \varphi(c,w) \xi_k, \nu^N_k \right \rangle+ O_p(N^{-2}). \addtocounter{equation}{1}\end{align}\] We can similarly characterise the evolution of the empirical measure \(\mu^N_k\) in terms of their projection onto any test functions \(\varphi \in C^2_b(\mathbb{R}^{1+M})\): \[\begin{align} \left \langle\varphi, \mu^N_{k+1} \right \rangle- \left \langle\varphi, \mu^N_k \right \rangle &= \frac{1}{N} \sum_{i=1}^N \bigg[\partial_b \varphi(B^i_k,U^i_k) (B^i_{k+1} - B^i_k) + \partial_u \varphi(B^i_k,U^i_k) \cdot (U^i_{k+1} - U^i_k) \bigg]+ O_p(N^{-2}) \\ &= \frac{1}{N^{\frac{5}{2}}} \sum_{i=1}^N \zeta^N_k \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \Bigg[ \sigma(U^i_k \cdot \tilde{\xi}_k) (\partial_b \varphi(B^i_k, U^i_k) - B^i_k \partial_w\varphi(B^i_k, U^i_k) \cdot \xi_k) \\ &- \sum_{a''} f^N_k(\tilde{x}_k, a'') \sigma'(U^i_k \cdot (\tilde{x}_k, a'')) \left( \partial_b \varphi(B^i_k, U^i_k) - B^i_k \partial_w\varphi(B^i_k, U^i_k) \cdot (\tilde{x}_k, a'') \right) \Bigg] + O_p(N^{-2}) \\ &= \frac{1}{N^{\frac{3}{2}}} \xi^N_k \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \Big[ \left \langle\sigma(u \cdot \tilde{\xi}_k) (\partial_b \varphi(b,u) - b \partial_w\varphi(b,u) \cdot \xi_k), \mu^N_k \right \rangle\\ &- \sum_{a''} f^N_k(\tilde{x}_k, a'') \left \langle\sigma'(u \cdot (\tilde{x}_k, a'')) \left( \partial_b \varphi(b,u) - b \partial_w\varphi(b,u) \cdot (\tilde{x}_k, a'') \right), \mu^N_k \right \rangle\Big]+ O_p(N^{-2}), \addtocounter{equation}{1}\label{eq:P95pre95limit} \end{align}\tag{39}\] and hence \[\begin{align} \label{eq:prelimit95evolution95of95mu} \left \langle\varphi, \mu^N_t \right \rangle- \left \langle\varphi, \mu^N_0 \right \rangle &= \frac{1}{N^{\frac{3}{2}}} \sum_{k=0}^{\floor{Nt}-1} \xi^N_k \mathsf{clip}(Q^N_k(\tilde{\xi}_k)) \Big[ \left \langle\sigma(u \cdot \tilde{\xi}_k) (\partial_b \varphi(b,u) - b \partial_w\varphi(b,u) \cdot \xi_k), \mu^N_k \right \rangle\\ &- \sum_{a''} f^N_k(\tilde{x}_k, a'') \left \langle\sigma'(u \cdot (\tilde{x}_k, a'')) \left( \partial_b \varphi(b,u) - b \partial_w\varphi(b,u) \cdot (\tilde{x}_k, a'') \right), \mu^N_k \right \rangle\Big]+ O_p(N^{-1}). \end{align}\tag{40}\]

4.2 Relative Compactness↩︎

In this section, we prove the family of processes \(\left(\mu^N_t, \nu_t^N, P_t^N, Q_t^N \right)\) are relatively compact under the choice of scaling of critic parameter updates \(\alpha^N = 1/N\). Section 4.2.1 proves compact containment and Section 4.2.2 proves needed regularity. Section 4.2.3 combine these results to prove the relative compactness.

4.2.1 Compact Containment↩︎

The \(L^2\) bounds for the actor and critic networks in Lemma 4 and 5 enable us to prove that the process \((\mu^N_t, \nu^N_t, P^N_t, Q^N_t)\) is compactly bounded. As a reminder, we now treat \(P^N_t\), \(Q^N_t\) are vectors of size \(d = |\mathcal{X}\times \mathcal{A}|\), thanks to the assumption of the state-action space being finite. Letting \(E = \mathcal{M}(\mathbb{R}^{1+d}) \times \mathcal{M}(\mathbb{R}^{1+d}) \times \mathbb{R}^d \times \mathbb{R}^d\), we have

Lemma 6 (Compact Containment). For any \(\eta > 0\), there is a compact subset \(\mathcal{K}\) of \(E\) such that \[\sup_{N \in \mathbb{N}, 0 \leq t \leq T} \mathbb{P}\left[ \left( \mu^N_t, \nu_t^N, P_t^N, Q_t^N \right) \notin \mathcal{K} \right] < \eta.\]

Proof. Let \(K_L = [-L,L]^{1+d}\) denotes a compact subset in \(\mathbb{R}^{1+d}\). We then see that for any \(t \geq 0\) and \(N \in \mathbb{N}\), \[\begin{align} \mathbb{E}\left[ \nu_t^N\left( \mathbb{R}^{1+d} \setminus K_L \right) \right] &= \frac{1}{N} \sum_{i=1}^N \mathbb{P}\left( (C^i_{\floor{Nt}}, W^i_{\floor{Nt}}) \in \mathbb{R}^{1+d} \setminus K_L \right) \\ &\leq \frac{1}{N} \sum_{i=1}^N \mathbb{P}\left( \left| C^i_{\floor{Nt}} \right| + \left\| W^i_{\floor{Nt}} \right\| \geq L \right) \leq \frac{C_T}{L}, \addtocounter{equation}{1}\label{eq:simple95bound95of95nunt} \end{align}\tag{41}\] where the final step is by \(\left| C^i_{\floor{Nt}} \right| + \left\| W^i_{\floor{Nt}} \right\|\) is integrable (from Lemma 2) and Chebyshev’s inequality. We define the following subset of \(\mathcal{M}\left( \mathbb{R}^{1+d} \right)\) \[\hat{K}_L = \overline{\left\{ \nu \in \mathcal{M}\left( \mathbb{R}^{1+d} \right) \,\bigg|\, \nu\left( \mathbb{R}^{1+d} \setminus K_{(L+j)^2} \right) < \frac{1}{\sqrt{L+j}} \text{ for all } j \right \}},\] which is a closure of a tight family of measures and thus being a compact subset of \(\mathcal{M}(\mathbb{R}^{1+d})\). Observe that \[\begin{align} \mathbb{P}\left( \nu^N_t \notin \hat{K}_L \right) &\leq \mathbb{P}\left( \exists j \text{ s.t. } \nu_t^N(\mathbb{R}^{1+d} \setminus K_{(L+j)^2}) > \frac{1}{\sqrt{L+j}} \right) \\ &\leq \sum_{j=1}^\infty \mathbb{P}\left( \nu_t^N(\mathbb{R}^{1+d} \setminus K_{(L+j)^2}) > \frac{1}{\sqrt{L+j}} \right) \\ &\overset{(a)}{\leq} \sum_{j=1}^\infty \frac{\mathbb{E}\left[ \nu_t^N(\mathbb{R}^{1+d} \setminus K_{(L+j)^2}) \right]}{(L+j)^{-1/2}} \\ &\overset{(b)}{\leq} \sum_{j=1}^\infty \frac{C_T}{(L+j)^{3/2}} < \infty. \end{align}\] where step \((a)\) is from Chebyshev’s inequality and step \((b)\) from 41 . By dominated convergence theorem for infinite sum, we see that \(\sum_{j\geq 1} (L+j)^{-3/2} \to 0\) as \(L \to +\infty\), thus for any \(\eta > 0\) there is an \(L\) such that \[\sup_{N \in \mathbb{N}, t \in [0,T]} \mathbb{P}\left( \nu^N_t \notin \hat{K}_L \right) < \frac{\eta}{4}.\] With the exact same argument, we can also make \(L\) large enough such that \[\sup_{N \in \mathbb{N}, t \in [0,T]} \mathbb{P}\left( \mu^N_t \notin \hat{K}_L \right) < \frac{\eta}{4}.\] As we have shown in Lemma 4 and 5 that the \(L^2\) norm of \(P\) and \(Q\) are locally bounded, so by Chebyshev’s inequality we know for each \(\eta > 0\), there exists \(B > 0\) such that \[\sup_{N \in \mathbb{N}, t \in [0,T]} \mathbb{P}\left( Q^N_t \notin [-B,B]^{M} \right) < \frac{\eta}{4},\] and \[\sup_{N \in \mathbb{N}, t \in [0,T]} \mathbb{P}\left( P^N_t \notin [-B,B]^{M} \right) < \frac{\eta}{4}.\] Therefore, for each \(\eta > 0\), there is a compact set \(\mathcal{K} := \hat{K}_L \times \hat{K}_L \times [-B,B]^{M} \times [-B,B]^{M} \subseteq E\) such that \[\sup_{N \in \mathbb{N}, 0 \leq t \leq T} \mathbb{P}\left[ \left( \mu_t^N, \nu_t^N, P_t^N, Q_t^N \right) \notin \mathcal{K} \right] < \eta,\] which completes the proof. ◻

4.2.2 Regularity↩︎

Now we establish some regularity results for the sample paths of the process \(\left( \mu_t^N, \nu_t^N, P_t^N, Q_t^N \right)\). As in [26], we clarify the following notations:

\(q(z_1, z_2) = |z_1 - z_2| \wedge 1\) for any \(z_1, z_2 \in \mathbb{R}\).
\(\mathcal{F}^N_t\) be the \(\sigma\)-algebra generated by \(\left\{ (C^1_0, W^i_0) \right \}_{i=1}^N\) and \(\left\{ \left(\xi_j, \tilde{\xi}_j\right) \right \}_{j=0}^{\floor{Nt}-1}\).

Lemma 7. Let \(f \in C^2_b(\mathbb{R}^{1+d})\). For any \(\delta \in (0,1)\), there is a constant \(C_T < \infty\) such that for \(u \in [0,\delta]\), \(t \in [0,T]\), \[\begin{align} \mathbb{E}\left[ q\left( \left \langle f, \nu^N_{t+u}\right \rangle, \left \langle f, \nu^N_t\right \rangle \right) \,|\, \mathcal{F}^N_t \right] &\leq C_T\delta + \frac{C_T}{N^{3/2}} \\ \mathbb{E}\left[ q\left( \left \langle f, \mu^N_{t+u}\right \rangle, \left \langle f, \mu^N_t\right \rangle \right) \,|\, \mathcal{F}^N_t \right] &\leq C_T\delta + \frac{C_T}{N^{3/2}} \end{align}\]

Proof. We start by the following Taylor’s expansion for \(0 \leq s < t \leq T\): \[\begin{align} &\phantom{=}\left| \left\langle f, \nu_{t}^{N}\right\rangle-\left\langle f, \nu_{s}^{N}\right\rangle \right| \\ &=\left|\left\langle f, v_{\lfloor N t\rfloor}^{N}\right\rangle-\left\langle f, v_{\lfloor N s\rfloor}^{N}\right\rangle\right| \\ &\leq \frac{1}{N} \sum_{i=1}^{N}\left|f\left(C_{\lfloor N t\rfloor}^{i}, W_{\lfloor N t\rfloor}^{i}\right)-f\left(C_{\lfloor N s\rfloor}^{i}, W_{\lfloor N s\rfloor}^{i}\right)\right| \\ &\leq \frac{1}{N} \sum_{i=1}^{N} \left| \partial_{c} f\left( \bar{C}_{\lfloor N t\rfloor}^{i}, \bar{W}_{\lfloor N t\rfloor}^{i} \right) \right| \left| C_{\lfloor N t\rfloor}^{i}-C_{\lfloor N s\rfloor}^{i} \right| + \frac{1}{N} \sum_{i=1}^{N} \left\| \partial_{w} f\left(\bar{C}_{N,s,t}^{i}, \bar{W}_{N,s,t}^{i}\right) \right\| \left\| W_{\lfloor Nt \rfloor}^{i}-W_{\lfloor Ns \rfloor}^{i} \right\|, \addtocounter{equation}{1}\label{eq:taylor95for95nu} \end{align}\tag{42}\] where \(\bar{C}^{i}_{N,s,t}, \bar{W}^{i}_{N,s,t}\) are in the segments connecting \(C_{\lfloor Ns \rfloor}^{i}\) to \(C_{\lfloor Nt \rfloor}^{i}\) and \(W_{\left\lfloor Ns \right\rfloor}^{i}\) to \(W_{\lfloor Nt \rfloor}^{i}\) respectively.
Let’s now establish a bound on \(\left| C_{\floor{Nt}}^{i}-C_{\floor{Ns}}^{i} \right|\) for \(s<t \leq T\) with \(0<t-s \leq \delta<1\). \[\begin{align} &\mathbb{E}\left[ \left| C_{\floor{Nt}}^{i}-C_{\floor{Ns}}^{i} \right| \,|\, \mathcal{F}_{s}^{N} \right] =\mathbb{E}\left[ \left| \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \left( C_{k+1}^{i}-C_{k}^{i} \right) \right| \,|\, \mathcal{F}_{s}^{N} \right] \\ \leq& \mathbb{E}\left[ \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \frac{\alpha}{N^{\frac{3}{2}}} \left| r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right| \cdot \left| \sigma(W^i_k \cdot \xi_k) \right| \,|\, \mathcal{F}_{s}^{N} \right] \\ \leq& \frac{\alpha C}{N^{\frac{3}{2}}} \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \left( C + (\gamma+1) \mathbb{E}\left[ \sup_{\xi \in \mathcal{X}\times \mathcal{A}} |Q^N_k(\xi)| \right] \right) \\ \overset{(a)}{\leq}& \frac{C(\floor{Nt} - \floor{Ns})}{N^{\frac{3}{2}}} \left( C+(\gamma+1) C_T^{1/2} \right) \\ \leq& \frac{C_T(N(t-s)+1)}{N^{\frac{3}{2}}} \leq \frac{C_T}{\sqrt{N}} \delta + \frac{C_T}{N^{\frac{3}{2}}}. \addtocounter{equation}{1}\label{eq:Lipschitz95c} \end{align}\tag{43}\] where step \((a)\) is by Lemma 4. Similarly for \(\left\| W_{\floor{Nt}}^{i}-W_{\floor{Ns}}^{i} \right\|\) for any \(s < t \leq T\) with \(0 < t-s \leq \delta < 1\), \[\begin{align} & \mathbb{E}\left[ \left\| W_{\floor{Nt}}^{i}-W_{\floor{Ns}}^{i} \right\| \,|\, \mathcal{F}_{s}^{N} \right] = \mathbb{E}\left[ \left\| \sum_{k=\floor{Ns}}^{\floor{Nt}-1}\left( W_{k+1}^{i}-W_{k}^{i} \right) \right\| \,|\, \mathcal{F}_{s}^{N} \right] \\ \leq&\mathbb{E}\left[ \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \frac{\alpha}{N^{\frac{3}{2}}} \left| r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(x_k, a_k) \right| \cdot \left| C^i_k \right| \cdot \left| \sigma'(W^i_k \cdot \xi_k) \right| \,|\, \mathcal{F}_{s}^{N} \right] \\ \leq& \frac{\alpha C_T}{N^{\frac{3}{2}}} \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \left( C + (\gamma+1) \mathbb{E}\left[ \sup_{\xi \in \mathcal{X}\times \mathcal{A}} |Q^N_k(\xi)| \right] \right) \leq \frac{C_T}{\sqrt{N}} \delta + \frac{C_T}{N^{3/2}}, \addtocounter{equation}{1}\label{eq:Lipschitz95w} \end{align}\tag{44}\] where we have used the bound in Lemma 2 and 4 again. Combine 43 , 44 and 42 , we have for any \(0 \leq s < t \leq T\) with \(0<t-s\leq \delta < 1\) \[\label{eq:bound95for95weak95convergence95nu} \mathbb{E}\left[ \left| \left \langle f, \nu^N_t \right \rangle- \left \langle f, \nu^N_s \right \rangle \right| \right] \leq \frac{C_T}{\sqrt{N}}\delta + \frac{C_T}{N^{3/2}} \leq C_T\delta + \frac{C_T}{N^{3/2}}.\tag{45}\]

Similarly for \(\mu_t^N\), we have by Taylor’s expansion that for \(0 \leq s < t \leq T\) with \(0 \leq s < t \leq T\) that \[\begin{align} \label{eq:taylor95for95mu} &\phantom{=}\left| \left\langle f, \mu_{t}^{N}\right\rangle-\left\langle f, \mu_{s}^{N}\right\rangle \right| \\ &=\left|\left\langle f, \mu_{\lfloor N t\rfloor}^{N}\right\rangle - \left\langle f, \mu_{\lfloor N s\rfloor}^{N}\right\rangle\right| \\ &\leq \frac{1}{N} \sum_{i=1}^{N}\left|f\left(B_{\lfloor N t\rfloor}^{i}, U_{\lfloor N t\rfloor}^{i}\right)-f\left(B_{\lfloor N s\rfloor}^{i}, U_{\lfloor N s\rfloor}^{i}\right)\right| \\ &\leq \frac{1}{N} \sum_{i=1}^{N} \left| \partial_{b} f\left( \bar{B}_{\lfloor N t\rfloor}^{i}, \bar{U}_{\lfloor N t\rfloor}^{i} \right) \right| \left| B_{\lfloor N t\rfloor}^{i}-B_{\lfloor N s\rfloor}^{i} \right| + \frac{1}{N} \sum_{i=1}^{N} \left\| \partial_{u} f\left(\bar{B}_{\lfloor N t\rfloor}^{i}, \bar{U}_{\lfloor N t\rfloor}^{i}\right) \right\| \left\| U_{\lfloor Nt \rfloor}^{i}-U_{\lfloor Ns \rfloor}^{i} \right\|, \end{align}\tag{46}\] and \[\begin{align} \label{B32U32diff} \mathbb{E}\left[ \left| B_{\floor{Nt}}^{i}-B_{\floor{Ns}}^{i} \right| \,|\, \mathcal{F}_{s}^{N} \right] & \leq \frac{C}{N^{\frac{3}{2}}} \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \mathbb{E}|\mathsf{clip}(Q^N_k(\tilde{x}_k,\tilde{a}_k))| \leq \frac{C(N(t-s)+1)}{N^{\frac{3}{2}}} \leq \frac{C_T}{\sqrt{N}} \delta + \frac{C_T}{N^{\frac{3}{2}}} \\ \mathbb{E}\left[ \left\| U_{\floor{Nt}}^{i}-U_{\floor{Ns}}^{i} \right\| \,|\, \mathcal{F}_{s}^{N} \right] &\leq\mathbb{E}\left[ \sum_{k=\floor{Ns}}^{\floor{Nt}-1} CN^{-\frac{3}{2}} |\mathsf{clip}(Q^N_k(\tilde{\xi}_k))| |B^i_k| \right] \leq \frac{C_T}{\sqrt{N}} \delta + \frac{C_T}{N^{\frac{3}{2}}}, \end{align}\tag{47}\] where \(\bar{B}^{i}_{N,s,t}, \bar{U}^{i}_{N,s,t}\) are in the segments connecting \(B_{\lfloor Ns \rfloor}^{i}\) to \(B_{\lfloor Nt \rfloor}^{i}\) and \(U_{\left\lfloor Ns\right\rfloor}^{i}\) to \(U_{\lfloor Nt \rfloor}^{i}\) respectively. With the fact that the terms \(\left| \partial_b f(\bar{B}^i_{\floor{Nt}}, \bar{U}^i_{\floor{Nt}}) \right|\) and \(\left\| \partial_w f(\bar{B}^i_{\floor{Nt}}, \bar{U}^i_{\floor{Nt}}) \right\|\) are bounded in expectation, we have that that for \(0 \leq s < t \leq T\) with \(0 < t-s\leq \delta < 1\) \[\label{eq:bound95for95weak95convergence95mu} \mathbb{E}\left[ \left| \left \langle f, \mu^N_t \right \rangle- \left \langle f, \mu^N_s \right \rangle \right| \right] \leq \frac{C_T}{\sqrt{N}}\delta + \frac{C_T}{N^{3/2}} \leq C_T\delta + \frac{C_T}{N^{3/2}}.\tag{48}\] ◻

Finally, we prove the regularity of the process \(\left(P^N_t, Q^N_t\right)\) by the same method. For our convenience, we abuse notation and define \(q(z_1, z_2) = \left\| z_1 - z_2 \right\|_\infty \wedge 1\), where for \(z := (z^1, ..., z^M) \in \mathbb{R}^M\) with \(M = |\mathcal{X}\times \mathcal{A}|\), we have \(\left\| z \right\|_\infty = \max_{i=1}^M |z^i|\) is the infinity norm of the vector. ⁵

Lemma 8. We have \[\sup_{k\leq NT} \max\left( \mathbb{E}\left[ \max_\xi |Q^N_{k+1}(\xi) - Q^N_k(\xi)| \right], \max_\xi |P^N_{k+1}(\xi) - P^N_k(\xi)| \right) \leq \frac{C_T}{N}.\] With a more delicate analysis, we could show that for any \(\delta \in (0,1)\), there is a \(C_T<\infty\) such that for \(0 \leq u \leq \delta < 1\), \(t \in [0,T]\), \[\begin{align} \mathbb{E}\left( q\left( Q^N_{t+u}, Q^N_t \right) \,|\, \mathcal{F}^N_t \right) \leq C_T \delta + \frac{C_T}{N}, \\ \mathbb{E}\left( q\left( P^N_{t+u}, P^N_t \right) \,|\, \mathcal{F}^N_t \right) \leq C_T \delta + \frac{C_T}{N}. \end{align}\]

Proof. Recalling the assumption that the state-action space is finite, it suffices to prove a uniform bound for the increments of the outputs \(P^N(\xi), Q^N(\xi)\). In particular, by 33 we have \[\mathbb{E}\left[ \max_{\xi}|Q^N_{k+1}(\xi) - Q^N_k(\xi)| \right] \leq \frac{\alpha}{N} \mathbb{E}\left| r(\xi_k) + \gamma Q^N_k(\xi_{k+1}) - Q^N_k(\xi_k) \right| |\mathsf{B}^N_{\xi,\xi_k,k}| + \frac{C_T}{N^{3/2}} \leq \frac{C_T}{N} + \frac{C_T}{N^{3/2}},\] and that by 22 we have \[\max_\xi |P^N_{k+1}(\xi) - P^N_k(\xi)| \leq \frac{\zeta^N_k}{N} |\mathsf{clip}(Q^N_k(\tilde{\xi}_k))| \left| \bar{\mathsf{B}}_{\xi, \tilde{\xi}_k, k} - \sum_{a''} f^N_k(\tilde{x}_k', a'') \bar{\mathsf{B}}_{\xi,(\tilde{x}_k,a''),k} \right| + \frac{C_T}{N^{3/2}} \leq \frac{C_T}{N} + \frac{C_T}{N^{3/2}}.\] In fact, one could prove a stronger inequality. \[\begin{align} &\mathbb{E}\left[ \max_\xi \left| Q^N_t(\xi) - Q^N_s(\xi) \right| \right] \leq \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \mathbb{E}\left[ \max_\xi \left| Q_{k+1}(\xi) - Q_{k}(\xi) \right| \right] \\ &\leq \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \sup_\xi \left[ \frac{1}{\sqrt{N}} \sum_{i=1}^N \left| (C^i_{k+1}-C_k^i) \sigma(W_k^i \cdot \xi)+\sigma'(W_k^i \cdot \xi)\xi^\top (W^i_{k+1}-W_k^i)C_k^i \right|+O_p(N^{-5/2}) \right] \\ \leq& \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \left[ \frac{C}{\sqrt{N}} \sum_{i=1}^N \left( |C^i_{k+1} - C^i_k| + \left\| W^i_{k+1} - W^i_k \right\| \right) + O_p(N^{-5/2}) \right]. \end{align}\] Taking expectations and using the bounds 43 and 44 , we have \[\begin{align} \mathbb{E}\left[ \max_\xi \left| Q^N_t(\xi) - Q^N_s(\xi) \right| \,|\, \mathcal{F}^N_s \right] &\leq \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \left[ \frac{C}{\sqrt{N}} \sum_{i=1}^N \left( \mathbb{E}\left[ |C^i_{k+1} - C^i_k| + \left\| W^i_{k+1} - W^i_k \right\| \,|\, \mathcal{F}^N_s \right] \right) + \mathbb{E}[O_p(N^{-5/2})] \right] \\ &\leq \frac{C}{\sqrt{N}} \sum_{i=1}^N \left( \frac{C_T}{\sqrt{N}}\delta + \frac{C_T}{N^{3/2}} \right) \leq C_T \delta + \frac{C_T}{N}. \addtocounter{equation}{1}\end{align}\] With exactly the same arguments, we can derive \[\begin{align} \left| P^N_t(\xi) - P^N_s(\xi) \right| &=\left| P^N_{\floor{Nt}}(\xi) - P^N_{\floor{Ns}}(\xi) \right| &\leq \sum_{k=\floor{Ns}}^{\floor{Nt}-1} \left[ \frac{C}{\sqrt{N}} \sum_{i=1}^N \left( |B^i_{k+1} - B^i_k| + \left\| U^i_{k+1} - U^i_k \right\| \right) + O(N^{-5/2}) \right], \end{align}\] which together with 47 derive \[\begin{align} \mathbb{E}\left[ \max_\xi \left| P^N_t(\xi) - P^N_s(\xi) \right| \,|\, \mathcal{F}^N_s \right] &\leq C_T \delta + \frac{C_T}{N}. \end{align}\] ◻

4.2.3 sec:Proof32of32Relative32Compactness↩︎

Theorem 8.6 and Remark 8.7 in [16] provides a criterion for us to prove the relative compactness of a general stochastic process with cadlag sample paths, for which we will state without proof.

Theorem 8. Let \(E\) be a metric space equipped with the metric \(r\). Denote \(q = r \wedge 1\), and let \((X^N_t)_{\cdot}\) be a sequence of \(E\)-valued stochastic processes with cadalag sample paths. Write \(\mathcal{F}^N_t\) as the natural filtration generated by the random variables \((X^N_t)\). Then \((X^N_t)_{t\geq 0}\) is relatively compact if the following conditions hold:

(Compact containment) For any \(\eta > 0\) and (rational) \(t > 0\), there is a compact subset \(\mathcal{K} := \mathcal{K}_{\eta, t}\) of \(E\) such that \[\sup_{N \in \mathbb{N}} \mathbb{P}(X^N_t \notin \mathcal{K}) < \eta.\]
(Regularity of paths) For each \(T > 0\), there is a family of non-negative random variables \(\left\{ \gamma_N(\delta) \,:\, \delta \in (0,1) \right \}\) satisfying \[\mathbb{E}\left[ q(X^N_{t+u}, X^N_t) \,|\, \mathcal{F}^N_t \right] \leq \mathbb{E}\left[ \gamma_N(\delta) \,|\, \mathcal{F}^N_t \right], \quad t \in [0,T], \; u\in [0,\delta],\] such that \[\lim_{\delta \to 0} \limsup_{N\to\infty} \mathbb{E}[\gamma_N(\delta)] = 0.\]

We will therefore prove condition 1 and 2 in the Section 4.2.1 and Section 4.2.2 respectively.

Lemma 9. The family of processes \(\left(\mu^N_t, \nu_t^N, P_t^N, Q_t^N \right)_{N \in \mathbb{N}}\) is relative compact in \(D_E([0, T])\).

Proof. Combining the two lemmas above, we see that the process \((\mu^N, \nu^N, P^N, Q^N)\) satisfies condition 2 with \(\gamma_N(\delta)\) being a \(O(\delta)\) term plus a \(o(1)\) term with respect to \(N\). All conditions in theorem 8 is satisfied, and hence the sequence of process \((\mu^N, \nu^N, P^N, Q^N)\) is relatively compact. ◻

4.3 Identification of the Limit↩︎

With the relative compactness result in Section 4.2, we can conclude that \((\mu^N, \nu^N, P^N, Q^N)\) contains a sub-sequence that converges weakly. To prove the convergence in Theorem 4, we need to identify the potential limit points, which involves showing the error terms \(M^N_t, M^{i,N}_t \overset{N\to\infty}\to 0\) in probability for \(i = 1,2,3\). Then the desired convergence comes from the uniqueness of the limit ODEs.

We begin by some notations.

For any \(k \ge 0\), we let \(\mathbb{P}^N_k\) and \(\Pi_k\) be the transition kernel of \((\boldsymbol{\mathcal{M}}, g^N_k)\) and \((\boldsymbol{\mathcal{M}}, g^N_k)_\mathsf{aux}\) respectively, so that \[\label{2dim32transition} \begin{align} \mathbb{P}^N_{k}((x, a) \to (x', a'))&= p(x'|x, a) g^N_k(x', a'),\\ \Pi^N_{k} ((x, a) \to (x', a')) &= \tilde{p}(x'| x, a) g^N_k(x', a'). \end{align}\tag{49}\] We highlight the superscript \(N\) in transition probability \(\mathbb{P}^N_{k}, \Pi^N_k\) comes from the pre-limit neural network \(P_k^N\).
Let \(\pi^{g^N_k}\) and \(\sigma_{\rho_0}^{g^N_k}\) denote the stationary distributions of \((\boldsymbol{\mathcal{M}}, g^N_k)\) and \((\boldsymbol{\mathcal{M}}, g^N_k)_\mathsf{aux}\) respectively, whose existence and uniqueness are given by Assumption 2. The initial distribution \(\rho_0\) in \(\sigma_{\rho_0}^{g^N_k}\) may be omitted when the context is clear.
Define the \(\sigma\)-field of events generated by the joint Actor and Critic processes up to \(n\)-th step be \[\mathscr{F}_n = \sigma(\xi_k, \tilde{\xi}_k)_{k\leq n}, \quad (\xi_k)_{k\geq 0} \sim (\boldsymbol{\mathcal{M}},\mathsf{Cr}), \, (\tilde{\xi}_k)_{k\geq 0} \sim (\boldsymbol{\mathcal{M}},\mathsf{Ac}).\] Then \(\mathbb{P}^N_k\) and \(\Gamma^N_k\) each induces an operator acting on any Borel function \(h(\cdot): \mathcal{X} \times \mathcal{A} \to \mathbb{R}\) \[\label{transition32integral} \begin{align} \mathbb{P}_k^N h(\xi) &:= \sum_{\xi' \in \boldsymbol{\mathcal{X} \times \mathcal{A}}} h(\xi') \mathbb{P}_k^N(\xi \to \xi') \\ \Pi_k^N h(\xi) &:= \sum_{\xi' \in \boldsymbol{\mathcal{X} \times \mathcal{A}}} h(\xi') \Pi_k^N(\xi \to \xi'), \end{align}\tag{50}\]

4.3.1 Poisson Equations↩︎

Now we rigorously derive the limit ODEs by using a Poisson equation [27], [31], [32], [35], which can be comprehended as the limit of the Kolmogorov forward equation (Fokker-Planck equation [36]–[38]) for stochastic process, to bound the fluctuations terms around the trajectory of the limit ODE. Such analysis is needed as the fluctuation terms evolve as the actor and critic networks evolve, which further depend on the non-i.i.d data samples from the Markov chains 5 and 6 . We first prove \[\lim_{N\to \infty}\mathbb{E}\sup_{t\in [0,T]}\left| M_t^N(x,a) \right| = 0, \quad \forall (x,a) \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}.\] Using a similar method, we can also prove the convergence of \(M_t^{1,N}, M_t^{2,N},\) and \(M_t^{3,N}\).

It is known that a finite state Markov chain which is irreducible and non-periodic has a geometric convergence rate to its stationary distribution [39]. We are able to prove a uniform geometric convergence rate for the Markov chains in our paper under the time-evolving actor policy updated using the actor-critic algorithm 1.

Lemma 10. Let \(\Pi^{N,n}_k\) denote the \(n\)-step transition matrix under derived from transition probability \(\Pi^N_k\) with \(\Pi^{N,0}_k(\xi,\xi') = \mathbb{1}_{\xi'=\xi}\). Then, for any fixed \(T> 0\), there exists an integer \(n_0\) such that the following uniform estimates hold for all policies \(\{g^N_k\}_{0 \le k\le NT}\) and \(N \in \mathbb{N}\) for the algorithm 1.

Lower bound for the stationary distribution: \[\label{lower32bound} \inf_{k \le NT} \sigma^{g^N_k}(x, a) \ge C \epsilon_T^{n_0}, \quad \forall (x, a) \in \boldsymbol{\mathcal{X} \times \mathcal{A}},\tag{51}\] where \(C, \epsilon_T>0\) are positive constants.
Uniform geometric ergodicity: \[\label{geometric} \sup_{ k \le NT } \| \Pi^{N, n}_k(\xi \to \cdot) - \sigma^{g^N_k}(\cdot) \| \le (1-\beta_T)^{\lfloor \frac{n}{n_0} \rfloor} \quad \forall \xi \in \boldsymbol{\mathcal{X} \times \mathcal{A}},\tag{52}\] where \(\beta_T \in (0,1)\) is a positive constant, and the norm \(\|\cdot \|\) is the usual total variation norm.

The proof of the above lemma is exactly the same as the lemma A.4 of [26].Then, using the same method as in Lemma 10, we can prove a similar result for the MDP \(\boldsymbol{\mathcal{M}}\) with exploration policy \(g^N_k\).

Corollary 1. Let \(\mathbb{P}^{N,n}_k\) denote the \(n\)-step transition matrix under policy \(g^N_k\) with \(\mathbb{P}^{N,0}_k(\xi,\xi') = \mathbb{1}_{\{\xi'=\xi\}}\). Then, for any fixed \(T < \infty\), there exists an integer \(n_0\) and a constant \[\label{exploration32lower32bound} C = C(n_0) := \inf_{x, a, x'} \sum_{\xi_1, \cdots, \xi_{n_0-1}} p(x_1|x,a) \cdots p(x'|x_{n_0-1}, a_{n_0-1}) > 0,\tag{53}\] such that the following uniform estimate holds for all \(\{g^N_k\}_{0 \le k\le NT}\) and \(N \in \mathbb{N}\) for the update algorithm 1:

Lower bound for the stationary distribution: \[\label{uniform32bound2} \inf_{k \le NT} \pi^{g^N_k}(x, a) \ge C \left( \eta_{\lfloor NT \rfloor}^N \right)^{n_0}, \quad \forall (x,a) \in \boldsymbol{\mathcal{X} \times \mathcal{A}}.\tag{54}\]
Uniform geometric ergodicity: \[\label{geometric2} \sup_{k \le NT} \| \mathbb{P}^{N, n}_k(\xi \to \cdot) - \pi^{g^N_k}(\cdot) \| \le (1-\beta_T)^{\lfloor \frac{n}{n_0} \rfloor} \quad \forall \xi \in \boldsymbol{\mathcal{X} \times \mathcal{A}},\tag{55}\] where \(\beta_T = C \left(\eta_{\lfloor NT \rfloor}^N \right)^{n_0} \in (0,1)\) is a positive constant.

Without loss of generality, we assume that the value of \(n_0\) in lemma 10 and 1 are the same. In order to prove the stochastic fluctuation term vanishes as \(N \rightarrow \infty\), we solve the system of Poisson equations associated with the Markov chains \((\boldsymbol{\mathcal{M}}, g^N_k)\) and \((\boldsymbol{\mathcal{M}}, g^N_k)_\mathsf{aux}\), which relates their transition kernels with their unique stationary distributions. We will only analyse the Markov chain \((\boldsymbol{\mathcal{M}}, g^N_k)_\mathsf{aux}\) here as the analysis for \((\boldsymbol{\mathcal{M}}, g^N_k)\) is identical. The system of Poisson equations associated with \((\boldsymbol{\mathcal{M}}, g^N_k)_\mathsf{aux}\) is defined as followed:

Definition 5 (Poisson equations). Let \(N \in \mathbb{N}\), \(T> 0\) and \(k \le NT\). The Poisson equations corresponding to the chain induced by transition kernel \(\Pi^{N}_k\) state-action seeks a function \(\nu^N_{k,\xi}(\cdot) : \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}} \to \mathbb{R}\) for each state-action pairs \(\xi = (x,a)\), such that \[\label{poisson} \nu^N_{k,\xi}(\xi') - \Pi^N_{k} \nu^N_{k,\xi}(\xi') = \mathbb{1}_{\{ \xi' = \xi\}} - \sigma^{g^N_k}(\xi), \quad \forall \xi' \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}.\tag{56}\]

Lemma 11 (Existence of solution to the Poisson equations). The Poisson equations 56 admits a uniformly bounded solution \[\label{nu} \nu^N_{k,\xi}(\xi') := \sum_{n\ge 0} \left[ \Pi^{N, n}_{k} (\xi' \to \xi) - \sigma^{g^N_k}(\xi) \right],\tag{57}\] and there exists a constant \(C_T\) (which only depends on \(T\)) such that \[\label{uniform} \sup_{k \le NT} \max_{\xi,\xi' \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}} \left|\nu^N_{k,\xi}(\xi') \right| \leq C_T.\tag{58}\]

Remark 9. For the purposes of our later analysis, it is enough to find a uniformly bounded solution \(\nu_\theta\) which satisfies 57 . Therefore, we do not establish the uniqueness of solution to the Poisson equation 56 here.

Proof. (of lemma 11). Due to the uniform geometric convergence rate 52 for all \(k \le NT\) in Lemma 10, there exists a \(\beta_T>0\) (independent with \(k\)) such that for any \(\xi' \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\) \[\label{uniform32ergodicity} \left|\Pi^{N, n}_{k}(\xi' \to \xi) - \sigma^{g^N_k}(\xi) \right| \le (1-\beta_T)^{\lfloor \frac{n}{n_0} \rfloor}, \quad\forall k \le NT\tag{59}\] which can be used to show the convergence of the series in 57 . Consequently, \(\nu^N_{k,\xi}\) is well-defined and uniformly bounded as in 58 . In fact, \[\left|\nu^N_{k,\xi}(\xi')\right| \le \sum_{n\ge 0} \left| \Pi^{N,n}_{k} (\xi' \to \xi) - \sigma^{g^N_k}(\xi) \right| \leq \sum_{n \ge 0}(1-\beta_T)^{\lfloor \frac{n}{n_0} \rfloor} \le C_T.\] Finally, we can verify that \(\nu^N_{k,\xi}\) is a solution to the Poisson equation 56 by observing that \[\begin{align} \Pi^{N}_{k} \nu^N_{k,\xi}(\xi') &= \sum_{y} \nu^N_{k,\xi}(y)\Pi^N_{k}(\xi' \to y)\\ &= \sum_y \left(\sum_{n\ge 0} \left[\Pi^{N, n}_k (y \to \xi) - \sigma^{g^N_k}(\xi) \right] \right) \Pi^N_{k}(\xi' \to y) \\ &\overset{(a)}{=} \sum_{n\ge 0} \left( \sum_y \left[ \Pi^{N, n}_{k}(y\to\xi) - \sigma^{g^N_k}(\xi) \right] \Pi^N_{k}(\xi' \to y) \right) \\ &= \sum_{n\ge 0} \left[\Pi^{N,n+1}_{k} (\xi' \to \xi) - \sigma^{g^N_k}(\xi) \right] \\ &= \nu^N_{k,\xi}(\xi') - (\mathbb{1}_{\{ \xi' = \xi\}} - \sigma^{g^N_k}(\xi)), \end{align}\] where the step \((a)\) uses 59 and the Dominated Convergence Theorem. ◻

Using the Poisson equation [poisson32equation], we can prove that the fluctuations of the data samples around a dynamic visiting measure \(\sigma^{g^N_k}\) decay when the iteration steps becomes large.

Lemma 12. Let \((\tilde{\xi}_k)_{k\geq 0}\) be the Actor process \((\boldsymbol{\mathcal{M}},\mathsf{Ac})\). Then for any fixed state action pair \(\xi = (x,a)\) and \(T > 0\), \[\label{online32convergence} \lim_{N \to \infty} \mathbb{E}\left| \frac{1}{N}\sum_{ k=0 }^{c(T,N)} \left[ \mathbb{1}_{\{ \tilde{\xi}_{k} = \xi\}} - \sigma^{g^N_k}(\xi)\right] \right|^2 = 0,\tag{60}\] where \(c(T,N)\) is a positive integer that depends on \(T\) and \(N\) such that \(c(T,N) \leq \lfloor NT \rfloor - 1\).

Proof. Without loss of generality we assume \(c(T,N) = \lfloor NT \rfloor - 1\). We define the error \(\epsilon_k\) to be \[\begin{align} \epsilon_{k} :=& \mathbb{1}_{\{ \tilde{\xi}_{k+1} = \xi\}} - \sigma^{g^N_k}(\xi) \\ =&\nu^N_{k,\xi}(\tilde{\xi}_{k+1}) - \Pi^N_{k} \nu^N_{k,\xi}(\tilde{\xi}_{k+1})\\ =& \nu^N_{k,\xi}(\tilde{\xi}_{k+1}) - \Pi^N_{k} \nu^N_{k,\xi} (\tilde{\xi}_{k}) + \Pi^N_{k} \nu^N_{k,\xi}(\tilde{\xi}_k) - \Pi^N_{k} \nu^N_{k,\xi} (\tilde{\xi}_{k+1}), \addtocounter{equation}{1}\end{align}\] where we have used the definition of the Poisson equation 56 . Define \(\psi^N_{k,\xi}(\cdot) := \Pi^N_k \nu^N_{k,\xi}(\cdot)\), so that \[\epsilon_{k} = \nu^N_{k,\xi}(\tilde{\xi}_{k+1}) - \Pi^N_{k} \nu^N_{k,\xi} (\tilde{\xi}_{k}) + \psi^N_{k,\xi}(\tilde{\xi}_k) - \psi^N_{k,\xi} (\tilde{\xi}_{k+1}).\] Then \[\begin{align} \sum_{k=0}^{\lfloor NT \rfloor -1} \epsilon_{k}=& \sum_{k=0}^{\lfloor NT \rfloor-1} \left[ \nu^N_{k,\xi}(\tilde{\xi}_{k+1}) - \Pi^N_{k} \nu^N_{k,\xi}(\tilde{\xi}_{k}) \right] + \sum_{k=0}^{\lfloor NT \rfloor-1} \left[\psi^N_{k,\xi}(\tilde{\xi}_{k})-\psi^N_{k,\xi}(\tilde{\xi}_{k+1}) \right] \\ =& \sum_{k=0}^{\lfloor NT \rfloor-1} \left[\nu^N_{k,\xi}(\tilde{\xi}_{k+1})-\Pi^N_{k} \nu^N_{k,\xi}(\tilde{\xi}_{k})\right] + \sum_{k=1}^{\lfloor NT \rfloor-1} \left[\psi^N_{k,\xi}(\tilde{\xi}_{k}) - \psi^N_{k-1,\xi}(\tilde{\xi}_{k})\right] \\ &\phantom{=}+ \psi^N_{0,\xi}(\tilde{\xi}_{0}) - \psi^N_{\lfloor NT \rfloor-1,\xi}(\tilde{\xi}_{\lfloor NT \rfloor}). \addtocounter{equation}{1}\end{align}\] Define \[\begin{align} \epsilon_{k}^{(1)} &= \left[ \nu^N_{k,\xi}(\tilde{\xi}_{k+1}) - \Pi^N_{k} \nu^N_{k,\xi}(\tilde{\xi}_{k}) \right], \\ \epsilon_{k}^{(2)} &= \left[\psi^N_{k,\xi} (\tilde{\xi}_{k})-\psi^N_{k-1,\xi}(\tilde{\xi}_{k})\right], \\ \rho_{\lfloor NT \rfloor ; 0} &= \psi^N_{0,\xi}(\tilde{\xi}_{0}) - \psi^N_{\lfloor NT \rfloor-1, \xi}(\tilde{\xi}_{\lfloor NT \rfloor}), \end{align}\] such that \[\label{decompose} \frac{1}{N}\sum_{k=0}^{\lfloor NT \rfloor-1} \epsilon_{k} = \frac{1}{N} \sum_{k=0}^{\lfloor NT \rfloor-1} \epsilon_{k}^{(1)} + \frac{1}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} \epsilon_{k}^{(2)} + \frac{1}{N} \rho_{\lfloor NT \rfloor ; 0},\tag{61}\] We proceed by the following:

the first term could be bounded by the martingale property,
the second term could be bounded using the uniform geometric ergodicity and Lipschitz continuity, and
the remainder term could be bounded using the uniform bound established in lemma 11.

For the first term in 61 , note that \[\mathbb{E}\left[\nu^N_{k,\xi}(\tilde{\xi}_{k+1}) \,\Big|\, \mathscr{F}_{k}\right] = \Pi^N_{k} \nu^N_{k,\xi}(\tilde{\xi}_{k}).\] Therefore \(\mathbb{E}[\epsilon^{(1)}_k \,|\, \mathscr{F}_k] = 0\), and the process \[\sum_{k=0}^{n-1} \epsilon_k^{(1)}\] is a martingale with respect to the filtration \((\mathscr{F}_n)_{n\geq 0}\). In fact, for \(k < k'\), \[\mathbb{E}[\epsilon^{(1)}_{k} \epsilon^{(1)}_{k'}] = \mathbb{E}[\epsilon^{(1)}_k \mathbb{E}[\epsilon^{(1)}_{k'} \,|\, \mathscr{F}_k]] = \mathbb{E}[\epsilon^{(1)}_k \mathbb{E}[\mathbb{E}[\epsilon^{(1)}_{k'} \,|\, \mathscr{F}_{k'}] \,|\, \mathscr{F}_k]] = 0.\] Moreover, \[\mathbb{E}\left| \Pi^N_{k} \nu^N_{k,\xi}(\tilde{\xi}_{k})\right|^{2} \leq \mathbb{E}\left| \nu^N_{k,\xi}(\tilde{\xi}_{k+1}) \right|^{2},\] as the conditional expectation is a contraction in \(L^{2}\). Therefore \[\begin{align} \mathbb{E}\left| \frac{1}{N} \sum_{k=0}^{\lfloor NT \rfloor-1} \epsilon_k^{(1)} \right|^2 &= \frac{1}{N^2} \sum_{k=0}^{\lfloor NT \rfloor-1} \mathbb{E}\left| \epsilon^{(1)}_k \right|^{2} \\ &= \frac{1}{N^2} \sum_{k=0}^{\lfloor NT \rfloor-1} \mathbb{E}\left| \Pi^N_{k} \nu^N_{k,\xi}(\tilde{\xi}_{k})-\nu_{k}(\tilde{\xi}_{k+1})\right|^{2} \\ &\leq \frac{4}{N^2} \sum_{k=0}^{\lfloor NT \rfloor-1}\mathbb{E}\left|\nu^N_{k,\xi}(\tilde{\xi}_{k+1})\right|^{2} \overset{(a)}{\le} \frac{4C_T}{N}, \addtocounter{equation}{1}\end{align}\] where the step (a) is by the uniform boundedness 58 . Thus, for any \(T >0\), \[\label{error1} \lim_{N \to \infty} \mathbb{E}\left| \frac{1}{N} \sum_{k=0}^{\lfloor NT \rfloor-1} \epsilon_k^{(1)} \right|^2 = 0.\tag{62}\]

For the second term of 61 , by the uniform geometric ergodicity 52 , for any fixed \(\gamma_0>0\) we can choose \(N_0\) large enough such that \[\sup_{k \le NT} \left(\sum_{n = \lfloor N_0T \rfloor}^{\infty} \left| \Pi^{N, n}_{k}(y \to \xi) - \sigma^{g^N_k}(\xi) \right| \right)^2 < \gamma_0, \quad \forall y \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}} \\\] \[\begin{align} &\left| \frac{1}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} \epsilon_{k}^{(2)} \right|^2 \\ =& \left| \frac{1}{N} \sum_{k=1}^{\lfloor NT \rfloor-1}\left[\psi^N_{k,\xi}(\tilde{\xi}_{k}) - \psi^N_{k-1,\xi}(\tilde{\xi}_{k})\right] \right|^2 \\ \leq& C\left| \frac{1}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} \left[\sum_{n=1}^{ \lfloor N_0T \rfloor -1} \left[\Pi_{k}^{N, n}\left(\tilde{\xi}_k \to \xi\right)- \sigma^{g^N_k}(\xi)\right]-\sum_{n=1}^{ \lfloor N_0T \rfloor -1} \left[\Pi_{k-1}^{N, n}\left(\tilde{\xi}_k\to \xi\right)-\sigma^{g^N_{k-1}}(\xi)\right]\right] \right|^2 + C_T \gamma_{0} \\ \le& C\left| \frac{1}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} \sum_{n=1}^{\lfloor N_0 T \rfloor -1} \left[\Pi_{k}^{N, n}\left(\tilde{\xi}_k \to \xi\right)- \Pi_{k-1}^{N, n}\left(\tilde{\xi}_k \to \xi\right)\right] \right|^2 + C \frac{\lfloor N_0T \rfloor}{N}\left| \sum_{k=1}^{\lfloor NT \rfloor-1} \left[\sigma^{g^N_k}(\xi)-\sigma^{g^N_{k-1}}(\xi)\right] \right|^2 + C_T \gamma_{0}\\ :=& I^N_1 + I^N_2 + C_T \gamma_0. \addtocounter{equation}{1}\label{lipschitz32bound} \end{align}\tag{63}\] Noting that for any finite \(n\), \(\Pi_{k}^{N, n}\) is Lipschitz continuous in \(P_k^N\) and use the Lipschitz conitinuity of softmax transformation, we have \[\begin{align} I_1^N &\le C\frac{ \lfloor N_0T \rfloor}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} \left\|g^N_{k}-g^N_{k-1} \right\|^2 \le \frac{ \lfloor N_0T \rfloor}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} C \left[ \left|\eta^N_{k}-\eta^N_{k-1}\right|^2 + \left\|P^N_{k}-P^N_{k-1}\right\|^2 \right] \overset{(a)}{\le} \frac{C_T}{N^2},\\ I_2^N &\le C\frac{ \lfloor N_0T \rfloor}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} \left\|g^N_{k} - g^N_{k-1} \right\|^2 \le \frac{ \lfloor N_0T \rfloor}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} C \left[ \left|\eta^N_{k}-\eta^N_{k-1}\right|^2 + \left\|P^N_{k}-P^N_{k-1}\right\|^2 \right] \overset{(a)}{\le} \frac{C_T}{N^2}, \end{align}\] where step \((a)\) is by Lemma 8 and the constant \(C_T\) only depends on the fixed \(N_0, T\). Thus, when \(N\) is large enough, \[\left|\frac{1}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} \epsilon_{k}^{(2)} \right|^2 \leq C_T \gamma_{0}\] Since \(\gamma_{0}\) is arbitrary, \[\label{error2} \lim _{N \rightarrow \infty} \mathbf{E}\left|\frac{1}{N} \sum_{k=1}^{\lfloor NT \rfloor-1} \epsilon_{k}^{(2)}\right|^2=0\tag{64}\] For the last term of 61 , the boundedness of \(\nu^N_{0,\xi}(\cdot)\) and \(\nu^N_{\lfloor NT \rfloor - 1,\xi}(\cdot)\) as established in lemma [poisson32equation] immediately implies \[\lim_{N\to \infty} \frac{1}{N} \rho_{\lfloor NT \rfloor ; 0} = 0,\] which together with 62 and 64 completes the proof of 60 . ◻

Now we can show the convergence of the stochastic fluctuation terms from the actor update.

Lemma 13. For any \(\xi =(x,a)\) and the stochastic error \(M_t^N\) defined in 37 , we have \[\label{actor32fluctuation32disappear} \lim _{N \rightarrow \infty} \sup _{t \in(0, T]} \mathbb{E}\left|M_{t}^{N}(\xi)\right|=0.\tag{65}\]

Proof. The proof of 65 consists of two parts. We first set up a bound for the difference of the actor’s update. Define \[\bar{H}^N_{\xi, \xi', k} := \zeta^N_k \mathsf{clip}(Q^N_k(\xi')) \left[\bar{\mathsf{B}}^{N}_{\xi,\xi',k} - \sum_{a''} f^N_k(x',a'') \bar{\mathsf{B}}^{N}_{\xi,(x',a''), k}\right].\] If we can prove \[\label{actor32diff} \left| \bar{H}^N_{\xi, \xi', k+1} - \bar{H}^N_{\xi, \xi', k} \right| \le \frac{C_T}{N}\tag{66}\] Then we can use Lemma 12 to prove that as the training step becomes large, the fluctuations of the data samples around the stationary distribution will disappear, completing our proof.
() To bound the difference 66 , note that \[\begin{align} & \left| \bar{H}^N_{\xi, \xi', k+1} - \bar{H}^N_{\xi, \xi', k} \right| \\ \leq& |\zeta^N_{k+1} - \zeta^N_k| \left| \mathsf{clip}(Q^N_{k+1}(\xi')) \left[\bar{\mathsf{B}}^{N}_{\xi,\xi',k+1} - \sum_{a''} f^N_{k+1}(x',a'') \bar{\mathsf{B}}^{N}_{\xi,(x',a''), k+1} \right] \right| \\ +& \zeta^N_k \left| \mathsf{clip}(Q^N_{k+1}(\xi')) - \mathsf{clip}(Q^N_k(\xi')) \right| \left| \bar{\mathsf{B}}^{N}_{\xi,\xi',k+1} - \sum_{a''} f^N_{k+1}(x',a'') \bar{\mathsf{B}}^{N}_{\xi,(x',a''), k+1} \right| \\ +& \zeta^N_k \left| \mathsf{clip}(Q^N_k(\xi')) \right| \left| \left[\bar{\mathsf{B}}^{N}_{\xi,\xi',k+1} - \sum_{a''} f^N_{k+1}(x',a'') \bar{B}^{N}_{\xi,(x',a''), k+1} \right] - \left[\bar{\mathsf{B}}^{N}_{\xi,\xi',k} - \sum_{a''} f^N_k(x',a'') \bar{\mathsf{B}}^{N}_{\xi,(x',a''), k} \right] \right| \\ :=& I_1^N + I_2^N + I_3^N. \end{align}\] For the first term, \[\label{actor32diff32first32term} I_1^N \le C_T |\zeta^N_{k+1} - \zeta^N_k| \le C_T \left( \frac{1}{1+\frac{k}{N}} - \frac{1}{1+\frac{k+1}{N}} \right) = \frac{C_T}{N\left( 1+\frac{k}{N} \right)\left( 1+\frac{k+1}{N} \right)} \le \frac{C_T}{N}.\tag{67}\] Then noting that the function \(\mathsf{clip}(.)\) is 1-Lipschitz (i.e. \(|\mathsf{clip}(x) - \mathsf{clip}(y)| \leq |x-y|\)), we have \[\label{actor32diff32second32term} I_2^N \le \frac{C_T}{N} \left| \bar{\mathsf{B}}^{N}_{\xi,\xi',k+1} - \sum_{a''} f^N_k(x',a'') \bar{\mathsf{B}}^{N}_{\xi,(x',a''), k+1} \right| \le \frac{C_T}{N}.\tag{68}\] Finally, by lemma 3 we know that for any \(k \leq NT\), \[\sup_{\xi,\xi' \in \mathcal{X}\times \mathcal{A}} \left| \bar \mathsf{B}^N_{\xi, \xi', k+1} - \bar \mathsf{B}^N_{\xi, \xi', k} \right| \leq \frac{C_T}{N}.\] Hence, \[\begin{align} I_3^N &\le C\left| \left[\bar{\mathsf{B}}^{N}_{\xi,\xi',k+1} - \sum_{a''} f^N_{k+1}(x',a'') \bar{\mathsf{B}}^{N}_{\xi,(x',a''), k+1} \right] - \left[\bar{\mathsf{B}}^{N}_{\xi,\xi',k} - \sum_{a''} f^N_k(x',a'') \bar{\mathsf{B}}^{N}_{\xi,(x',a''), k} \right] \right| \\ &\leq C\Bigg[ \left| \bar{\mathsf{B}}^{N}_{\xi,\xi',k+1} - \bar{\mathsf{B}}^{N}_{\xi,\xi',k} \right| + \sum_{a''} \left| f^N_{k+1}(x',a'') - f^N_{k}(x',a'') \right| \cdot \left| \bar{\mathsf{B}}^N_{\xi,(x',a''),k+1} \right| \\ &+ \sum_{a''} f^N_k(x',a'') \left| \bar{\mathsf{B}}^N_{\xi,(x',a''),k+1} - \bar{\mathsf{B}}^N_{\xi,(x',a''),k} \right| \Bigg] \\ &\leq C\left( 1+\sum_{a''} f^N_k(x',a'') \right) \sup_{\xi' \in \mathcal{X}\times\mathcal{A}} \left| \bar{\mathsf{B}}^{N}_{\xi,\xi',k+1} - \bar{\mathsf{B}}^{N}_{\xi,\xi',k} \right| + C \left\| P_{k+1}^N - P_k^N \right\| \leq \frac{C_T}{N}. \addtocounter{equation}{1}\label{actor32diff32third32term} \end{align}\tag{69}\] Combining 67 , 68 and 69 , we can conclude 66 .

() Now we can prove the convergence 65 . We let \(K := K(N) \in \mathbb{N}\), such that \(1 \ll K(N) \ll N\) (i.e. \(K(N) \to +\infty\) and \(K(N)/N \to 0\) as \(N \to \infty\)). We further define \(\Delta=t/K\). Then \[\begin{align} M_{t}^{N}(\xi) &= \frac{1}{N} \sum_{k=0}^{\floor{Nt}-1} \left( \bar{H}^N_{\xi,\tilde{\xi}_k,k} - \sum_{\xi'\in\boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}} \bar{H}^N_{\xi,\xi',k} \sigma^{g^N_k}(\xi') \right) \\ &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \left( \bar{H}^N_{\xi,\tilde{\xi}_k,k} - \sum_{\xi'\in\boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}} \bar{H}^N_{\xi,\xi',k} \sigma^{g^N_k}(\xi') \right) + r^N_t(\xi), \end{align}\] where \[\begin{align} r^N_t(\xi) = \frac{1}{N} \sum_{k=K\floor{N\Delta}}^{\min((K+1)\floor{N\Delta}-1, \floor{Nt}-1)} \left( \bar{H}^N_{\xi,\tilde{\xi}_k,k} - \sum_{\xi'\in\boldsymbol{\mathcal{X}}\times\boldsymbol{\mathcal{A}}} \bar{H}^N_{\xi,\xi',k} \sigma^{g^N_k}(\xi') \right). \end{align}\] The terms \(H^N_{\xi,\xi',k}\) are bounded by some constant \(C_T > 0\) as the kernel entries \(|\bar{\mathsf{B}}^N_{\xi,\xi',k}|\) are bounded, so are the summands. Thus \[|r^N_t(\xi)| \leq \frac{\floor{N\Delta}}{N} C_T \leq \frac{TC_T}{K}.\] We could further break down \(M^N_t(\xi)\) as followed: \[\begin{align} M^N_t(\xi) - r^N_t(\xi) &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \bigg[ \left( \bar{H}^N_{\xi,\tilde{\xi}_k,k} - \bar{H}^N_{\xi,\tilde{\xi}_k,j\floor{N\Delta}} \right) \\ &\phantom{=}+ \left( \bar{H}^N_{\xi,\tilde{\xi}_k,j\floor{N\Delta}} - \sum_{\xi'} \bar{H}^N_{\xi,\xi',j\floor{N\Delta}} \sigma ^{g^N_k}(\xi') \right) + \sum_{\xi'} \left( \bar{H}^N_{\xi,\xi',j\floor{N\Delta}} - \bar{H}^N_{\xi,\xi',k} \right) \sigma^{g^N_k}(\xi')\bigg] \\ &= J^N_{1,t}(\xi) + J^N_{2,t}(\xi) + J^N_{3,t}(\xi), \addtocounter{equation}{1}\end{align}\] where \[\begin{align} J^N_{1,t}(\xi) &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \left( \bar{H}^N_{\xi,\tilde{\xi}_k,k} - \bar{H}^N_{\xi,\tilde{\xi}_k,j\floor{N\Delta}} \right) \\ J^N_{2,t}(\xi) &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \left( \bar{H}^N_{\xi,\tilde{\xi}_k,j\floor{N\Delta}} - \sum_{\xi'} \bar{H}^N_{\xi,\xi',j\floor{N\Delta}} \sigma ^{g^N_k}(\xi') \right) \\ J^N_{3,t}(\xi) &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \sum_{\xi'} \left( \bar{H}^N_{\xi,\xi',j\floor{N\Delta}} - \bar{H}^N_{\xi,\xi',k} \right) \sigma^{g^N_k}(\xi'). \end{align}\] Using 66 , we have \[\begin{align} \max\left( \left| \bar{H}^N_{\xi, \tilde{\xi}_k, k} - \bar{H}^N_{\xi, \tilde{\xi}_k, j\floor{\Delta N}} \right|, \, \sum_{\xi'} \left| \bar{H}^N_{\xi, \xi', k} - \bar{H}^N_{\xi, \xi', j\floor{\Delta N}} \right| \sigma^{g^N_k}(\xi') \right) &\leq \sup_{\xi,\xi'} |\bar{H}^N_{\xi, \xi', k} - \bar{H}^N_{\xi, \xi', j\floor{\Delta N}}|\\ &\leq \frac{C_T (k-j\lfloor\Delta N\rfloor)}{N}. \addtocounter{equation}{1}\end{align}\] Therefore, \[\begin{align} \label{actor32diff32estimation} \max(J^N_{1,t}(\xi), J^N_{3,t}(\xi)) &\leq \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j \lfloor N\Delta \rfloor}^{(j+1)\lfloor\Delta N\rfloor-1} C_T \frac{k-j\lfloor N\Delta\rfloor}{N} \\ &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=0}^{\lfloor\Delta N\rfloor-1} \frac{C_T k}{N}\\ &\leq \frac{C_T}{N} \sum_{j=0}^{K-1} \frac{\floor{N\Delta}^2}{N} \\ &= \frac{KC_T \floor{N\Delta}^2}{N^2} \leq KC_T \Delta^2 = C_T K\left( \frac{t}{K} \right)^2 \leq \frac{C_T}{K}. \addtocounter{equation}{1}\end{align}\tag{70}\] To control \(J^N_{2,t}(\xi)\), we note that \[\bar{H}^N_{\xi, \tilde{\xi}_k, j\floor{N\Delta}} - \sum_{\xi' \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}} \bar{H}^N_{\xi, \xi', j\floor{N\Delta}} \sigma^{g^N_{k}}(\xi') = \sum_{\xi'} \bar{H}^N_{\xi, \xi', j\floor{N\Delta}} \left[ \mathbb{1}_{\{ \tilde{\xi}_k = \xi'\}} - \sigma^{g^N_{k}}(\xi')\right],\] so one could control \(J^N_{2,t}(\xi)\) by the uniform boundedness of \(\bar{H}^N_{\xi, \xi', j\floor{\Delta N}}\) and lemma 12. Indeed, \[\begin{align} \left| J^N_{2,t}(\xi) \right| &= \left| \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\lfloor N\Delta \rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \sum_{\xi'} \bar{H}^N_{\xi, \xi', j\floor{N\Delta}} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \sigma^{g^N_k}(\xi')\right] \right| \\ &= \left|\frac{1}{N} \sum_{j=0}^{K-1} \sum_{\xi'} \bar{H}^N_{\xi, \xi', j\floor{N\Delta}} \sum_{k=j\lfloor N\Delta \rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \sigma^{g^N_k}(\xi')\right] \right|\\ &\le C_T \sum_{\xi'}\left| \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\lfloor N\Delta \rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \sigma^{g^N_k}(\xi')\right] \right|, \\ &= C_T \sum_{\xi'}\left| \frac{1}{N} \sum_{k=0}^{K\lfloor N\Delta \rfloor-1} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \sigma^{g^N_k}(\xi')\right] \right|, \addtocounter{equation}{1}\end{align}\] which together with Lemma 12 derive \[\lim_{N \to \infty} \mathbb{E}\left| J^N_{2,t}(\xi) \right|^2 = 0.\] Collecting our results, we have shown that \[\sup _{t \in(0, T]} \mathbb{E}\left|M_{t}^{N}(\xi)\right| \leq \frac{C_T}{K(N)} \overset{N\to\infty}\to 0\] by the assumption that \(1 \ll K(N)\). ◻

Following the same method, we can finish proving the convergence of the stochastic fluctuation terms from the dynamics of the critic network.

Lemma 14. For any \(\xi =(x,a)\) and the stochastic error \(M_t^{i, N}, i=1,2,3\) defined in 35 , we have \[\label{critic32fluctuation32disappear} \lim _{N \rightarrow \infty} \sup _{t \in(0, T]} \mathbb{E}\left|M_{t}^{i, N}(\xi)\right|=0, \quad i=1,2,3.\tag{71}\]

Proof. As in the proof for the decay of \(M_t^N\), we use two steps to prove the result.

Prove that the fluctuations of the data samples around a dynamic stationary distribution \(\pi^{g_k}\) decay when the number of iteration steps becomes large. Actually, with exactly the same approach as in Lemma 12, we can prove for any fixed state action pair \(\xi = (x,a), \forall T> 0\) \[\label{online32convergence322} \lim_{N \to 0} \mathbb{E}\left| \frac{1}{N}\sum_{k=0}^{ \lfloor NT \rfloor - 1 } \left[ \mathbb{1}_{\{ \xi_{k} = \xi\}} - \pi^{g_k}(\xi)\right] \right|^2 = 0.\tag{72}\]
Use the same method as in Lemma 13 to prove the stochastic fluctuation terms vanish as \(N \rightarrow \infty\).

We first look at \(M_t^{3, N}\) and the proof for \(M_t^{1, N}, M_t^{2, N}\) is the same. Recalling the notation in 50 , we have \[\begin{align} M^{3,N}_t(\xi) &= \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} \gamma \left[Q^N_k(\xi_{k+1}) - \mathbb{P}_k^N Q_k^N(\xi_k) \right] B^N_{\xi, \xi_k, k} \\ &\phantom{=}+ \frac{1}{N}\sum_{k=0}^{\floor*{Nt}-1} \gamma \left[ \mathbb{P}_k^N Q_k^N(\xi_k) B^N_{\xi, \xi_k, k} - \sum_{\xi'} \mathbb{P}_k^N Q_k^N(\xi') B^N_{\xi, \xi', k} \pi^{g_k^N}(\xi') \right]\\ &:= I^{1,N}_t(\xi) + I^{2,N}_t(\xi). \addtocounter{equation}{1}\end{align}\] To control \(I^{1,N}_t(\xi)\), we first define \[\epsilon_k := \left[ Q^N_k(\xi_{k+1}) - \mathbb{P}_k^N Q_k^N(\xi_k) \right] B^N_{\xi, \xi_k, k}.\] Since \[\mathbb{E}\left[Q^N_k \left(\xi_{k+1} \right) \mid \mathscr{F}_{k}\right] = \mathbb{P}^N_{k} Q^N_{k}\left(\xi_{k}\right),\] hence \[\sum_{k=0}^{n-1} \epsilon_k\] is a martingale with respect to the filtration \(\mathscr{F}_n\). Since the conditional expectation is a contraction in \(L^{2}\), we have \[\mathbb{E}\left| \mathbb{P}^N_{k} Q^N_{k}\left(\xi_{k}\right) \right|^{2} \leq \mathbb{E}\left| Q^N_k(\xi_{k+1}) \right|^{2}.\] Then, \[\begin{align} \mathbb{E}\left| \frac{1}{N} \sum_{k=0}^{\lfloor NT \rfloor-1} \epsilon_k \right|^2 &=\frac{1}{N^2} \sum_{k=0}^{\lfloor NT \rfloor-1} \mathbb{E}\left| \mathbb{P}^N_{k} Q^N_{k}\left(\xi_{k}\right) - Q^N_k(\xi_{k+1}) \right|^{2}\\ & \leq \frac{4}{N^2} \sum_{k=0}^{\lfloor NT \rfloor-1}\mathbb{E}\left| Q^N_k(\xi_{k+1}) \right|^{2} \overset{(a)}{\le} \frac{C_T}{N}, \addtocounter{equation}{1}\end{align}\] where step \((a)\) follows from 27 and Lemma 4. Thus, for any \(T >0\), \[\lim_{N \to \infty} \mathbb{E}\left| I_t^{1, N} \right| = \lim_{N \to \infty} \gamma \mathbb{E}\left| \frac{1}{N} \sum_{k=0}^{\lfloor NT \rfloor-1} \epsilon_k \right| = 0.\]

For \(I^{2, N}_t\), we define as in the proof of Lemma 13 \[H^N_{\xi, \xi', k} := \mathbb{P}_k^N Q_k^N(\xi') B^N_{\xi, \xi', k} = \sum_{z, a''} Q_k^N(z, a'') g^N_k(z, a'') p(z| \xi') B^N_{\xi, \xi', k}.\] By Lemma 3 and 4, we have the bound \[\label{critic32l232bound} \sup _{0 \leq k \leq\lfloor T N\rfloor} \sup _{\xi' \in \mathcal{X} \times \mathcal{A}} \mathbb{E}\left| H^N_{\xi, \xi', k} \right|^2 \le C_T.\tag{73}\] Furthermore, by Lemma 3 and 8, \[\begin{align} \mathbb{E}\left| H^N_{\xi, \xi', k+1} - H^N_{\xi, \xi', k} \right|^2 &\le \sum_{z, a''} \mathbb{E}\left| Q_{k+1}^N(z, a'') g^N_{k+1}(z, a'') \mathsf{B}^N_{\xi, \xi', k+1} - Q_k^N(z, a'') g^N_k(z, a'') \mathsf{B}^N_{\xi, \xi', k} \right|^2 \\ &\le 3 \sum_{z, a''} \left| \left( Q^N_{k+1}(z, a'') - Q^N_k(z, a'') \right) g^N_{k+1}(z, a'') \mathsf{B}^N_{\xi, \xi', k+1} \right|^2 \\ &+ 3 \sum_{z, a''} \left| Q_{k}^N(z, a'') \mathsf{B}^N_{\xi, \xi', k+1} \left( g^N_{k+1}(z, a'') - g^N_{k}(z, a'') \right) \right|^2 \\ &+ 3 \sum_{z, a''} \left| Q_{k}^N(z, a'') g^N_{k}(z, a'') \left( \mathsf{B}^N_{\xi, \xi', k+1} - \mathsf{B}^N_{\xi, \xi', k} \right) \right|^2 \\ &\le \frac{C_T}{N^2}, \addtocounter{equation}{1}\end{align}\] so \[\label{critic32difference32l132bound} \sup _{0 \leq k \leq\lfloor T N\rfloor-1} \sup _{\xi' \in \mathcal{X} \times \mathcal{A}} \mathbb{E}\left| H^N_{\xi, \xi', k+1} - H^N_{\xi, \xi', k} \right| \le \left( \sup _{0 \leq k \leq\lfloor T N\rfloor-1} \sup _{\xi' \in \mathcal{X} \times \mathcal{A}} \mathbb{E}\left| H^N_{\xi, \xi', k+1} - H^N_{\xi, \xi', k} \right|^2 \right)^{\frac{1}{2}} \le \frac{C_T}{N}.\tag{74}\]

Then following the step () in the proof of Lemma 13, now we can prove the convergence \(I_t^{2,N}(\xi)\). We let \(K := K(N) \in \mathbb{N}\) such that \(1 \ll K \ll N\) and define \(\Delta = t/K\). Then, we can decompose \(I_t^{2,N}(\xi)\) into the following terms: \[I^{2,N}_t(\xi) = J^N_{1,t}(\xi) + J^N_{2,t}(\xi) + J^N_{3,t}(\xi) + r^N_t(\xi),\] where \[\begin{align} J^N_{1,t}(\xi) &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \left( H^N_{\xi,\tilde{\xi}_k,k} - H^N_{\xi,\tilde{\xi}_k,j\floor{N\Delta}} \right) \\ J^N_{2,t}(\xi) &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \left( H^N_{\xi,\tilde{\xi}_k,j\floor{N\Delta}} - \sum_{\xi'} H^N_{\xi,\xi',j\floor{N\Delta}} \pi^{g^N_k}(\xi') \right) \\ J^N_{3,t}(\xi) &= \frac{1}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \sum_{\xi'} \left( H^N_{\xi,\xi',j\floor{N\Delta}} - H^N_{\xi,\xi',k} \right) \pi^{g^N_k}(\xi') \\ r^N_t(\xi) &= \frac{1}{N} \sum_{k=K\floor{N\Delta}}^{\min((K+1)\floor{N\Delta}-1, \floor{Nt}-1)} \left( H^N_{\xi,\tilde{\xi}_k,k} - \sum_{\xi'} H^N_{\xi,\xi',k} \pi^{g^N_k}(\xi') \right). \end{align}\] Again, we have \[\begin{align} |r^N_t(\xi)|^2 &\leq \frac{\floor{N\Delta}}{N^2} \sum_{k=K\floor{N\Delta}}^{\min((K+1)\floor{N\Delta}-1, \floor{Nt}-1)} \left( H^N_{\xi,\tilde{\xi}_k,k} - \sum_{\xi'} H^N_{\xi,\xi',k} \pi^{g^N_k}(\xi') \right)^2 \\ &\leq \frac{2\Delta}{N} \sum_{k=K\floor{N\Delta}}^{\min((K+1)\floor{N\Delta}-1, \floor{Nt}-1)} \left[ \left( H^N_{\xi,\tilde{\xi}_k,k} \right)^2 + \sum_{\xi'} \left( H^N_{\xi,\xi',k} \pi^{g^N_k}(\xi') \right)^2 \right] \\ &\leq \frac{2\Delta}{N} \sum_{k=K\floor{N\Delta}}^{\min((K+1)\floor{N\Delta}-1, \floor{Nt}-1)} \left[ \left( H^N_{\xi,\tilde{\xi}_k,k} \right)^2 + \sum_{\xi'} \left( H^N_{\xi,\xi',k} \right)^2 \pi^{g^N_k}(\xi') \right], \end{align}\] so by 73 , \[\mathbb{E}|r^N_t(\xi)|^2 \leq \frac{C_T \Delta \floor{N\Delta}}{N} \leq C_T \Delta^2 \leq \frac{C_T}{K^2}.\] Moreover, \[\begin{align} \mathbb{E}[J^N_{1,t}(\xi)]^2 &\leq \frac{K \floor{N\Delta}}{N^2} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \mathbb{E}\left[ H^N_{\xi,\tilde{\xi}_k,k} - H^N_{\xi,\tilde{\xi}_k,j\floor{N\Delta}} \right]^2 \\ &\leq \frac{T}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \left( \frac{C_T(k - j\floor{N\Delta})}{N} \right)^2 \\ &\leq \frac{T}{N} \sum_{j=0}^{K-1} \sum_{k=0}^{\floor{N\Delta}-1} \left( \frac{kC_T}{N} \right)^2 \\ &\leq \frac{TC^2_T}{3N^3} \sum_{j=0}^{K-1} \floor{N\Delta}^3 \leq KC_T \Delta^3 \leq \frac{C_T}{K^2}. \addtocounter{equation}{1}\end{align}\] We can similarly control \(J^N_{3,t}(\xi)\) as followed: \[\begin{align} \mathbb{E}[J^N_{3,t}(\xi)]^2 &\leq \frac{K\floor{N\Delta}}{N}\sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \mathbb{E}\left[ \sum_{\xi'} \left( H^N_{\xi,\xi',j\floor{N\Delta}} - H^N_{\xi,\xi',k} \right) \pi^{g^N_k}(\xi') \right]^2 \\ &\leq \frac{K\floor{N\Delta}}{N}\sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \mathbb{E}\left[ \sum_{\xi'} \left( H^N_{\xi,\xi',j\floor{N\Delta}} - H^N_{\xi,\xi',k} \right)^2 \pi^{g^N_k}(\xi') \right] \\ &\leq \frac{T}{N} \sum_{j=0}^{K-1} \sum_{k=j\floor{N\Delta}}^{(j+1)\floor{N\Delta}-1} \left( \frac{C_T(k - j\floor{N\Delta})}{N} \right)^2 \leq \frac{C_T}{K^2}. \addtocounter{equation}{1}\end{align}\] Finally, note that \[H^N_{\xi, \tilde{\xi}_k, j\floor{\Delta N}} - \sum_{\xi' \in \mathcal{X} \times \mathcal{A}} H^N_{\xi, \xi', j\floor{\Delta N}} \pi^{g^N_{k}}(\xi') = \sum_{\xi'} H^N_{\xi, \xi', j\floor{\Delta N}} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \pi^{g^N_{k}}(\xi')\right].\] Thus, \[\begin{align} \label{l232bound} \mathbb{E}\left| J^N_{2,t}(\xi) \right| &= \frac{1}{N} \mathbb{E}\left| \sum_{j=0}^{K-1} \sum_{k=j\lfloor N\Delta \rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \sum_{\xi'} H^N_{\xi, \xi', j\floor{N\Delta}} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \pi^{g^N_k}(\xi')\right] \right| \\ &\leq \frac{1}{N} \mathbb{E}\left| \sum_{j=0}^{K-1} \left( \max_{\xi'} H^N_{\xi, \xi', j\floor{N\Delta}} \right) \sum_{k=j\lfloor N\Delta \rfloor}^{(j+1)\lfloor N\Delta\rfloor-1} \sum_{\xi'} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \pi^{g^N_k}(\xi')\right] \right|\\ &\overset{\text{(CS)}}\leq \frac{1}{N} \mathbb{E}\left[ \left( \sum_{j=0}^{K-1} \left( \max_{\xi'} H^N_{\xi, \xi', j\floor{N\Delta}} \right)^2 \right)^{1/2} \left( \sum_{j=0}^{K-1} \left( \sum_{k=j\lfloor N\Delta \rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \sum_{\xi'} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \pi^{g^N_k}(\xi')\right] \right)^2 \right)^{1/2} \right] \\ &\overset{\text{(CS)}}\leq \frac{1}{N} \left[ \mathbb{E}\left( \sum_{j=0}^{K-1} \left( \max_{\xi'} H^N_{\xi, \xi', j\floor{N\Delta}} \right)^2 \right) \mathbb{E}\left( \sum_{j=0}^{K-1} \left( \sum_{k=j\lfloor N\Delta \rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \sum_{\xi'} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \pi^{g^N_k}(\xi')\right] \right)^2 \right) \right]^{1/2} \\ &\overset{\eqref{critic32l232bound}}\leq \frac{KC_T}{N} \left[ \mathbb{E}\left[ \frac{1}{K}\sum_{j=0}^{K-1} \left( \sum_{k=j\lfloor N\Delta\rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \sum_{\xi'} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \pi^{g^N_k}(\xi')\right] \right)^2 \right] \right]^{1/2} \\ &= \frac{KC_T \floor{N\Delta}}{N} \left[ \mathbb{E}\left[ \frac{1}{K}\sum_{j=0}^{K-1} \left( \frac{1}{\floor{N\Delta}}\sum_{k=j\lfloor N\Delta\rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \sum_{\xi'} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \pi^{g^N_k}(\xi')\right] \right)^2 \right] \right]^{1/2} \\ &\leq TC_T \underbrace{\left[ \mathbb{E}\left[ \frac{1}{K}\sum_{j=0}^{K-1} \left( \frac{1}{\floor{N\Delta}}\sum_{k=j\lfloor N\Delta\rfloor}^{(j+1)\lfloor N\Delta \rfloor-1} \sum_{\xi'} \left[ \mathbb{1}_{\{ \xi_k = \xi'\}} - \pi^{g^N_k}(\xi')\right] \right)^2 \right] \right]^{1/2}}_{\to 0} \\ &\overset{n\to\infty}\to 0, \addtocounter{equation}{1}\end{align}\tag{75}\] where step (CS) is by Cauchy-Schwartz inequality. Combining 72 , 73 and 75 , we have \[\lim_{N \to \infty} \mathbb{E}\left| I^N_{3,j} \right| = 0.\] Consequently \(\mathbb{E}|I^{2,N}_t(\xi)| \to 0\), and so is \(M^{3,N}_t(\xi)\). The proof of the convergence for \(M_t^{1, N}, M_t^{2, N}\) are exactly the same for \(M_t^{3, N}\). The proof is completed. ◻

Let \(\rho^N\) denotes the probability measure of \(\left(\mu_t^N, \nu_t^N, P_t^N, Q_t^N\right)_{0\le t \le T}\), which takes value in the set of probability measures \(\mathcal{M}\left(D_E([0,T])\right)\). From the relative compactness result in Section 4.2, we know that the sequence pf measures \(\{ \rho^N \}_{N \in \mathbb{N}}\) contains a subsequence \(\rho^{N_k}\) that converges weakly. Now we can prove the limit points of any convergence subsequence \(\rho^{N_k}\) will satisfies the limiting ODEs 14 .

Lemma 15. Let \(\rho^N\) be the probability measure of \((\mu^N, \nu^N, P^N, Q^N)\). We restrict ourselves to a convergent subsequence \(\rho^{N_k}\) which converges to some limit point \(\rho = (\mu, \nu, P, Q)\). Then \(\rho\) is a Dirac measure on \(D_E([0,T])\) such that \((\mu, \nu, P, Q)\) satisfies the limiting ODEs 14 .

Proof. For any sequence of time-points \(0\leq s_1 < s_2 < ... < s_p \leq t\), functions \(\varphi, \bar{\varphi} \in C^2_b(\mathbb{R}^{1+d})\), \(\phi_1,...,\phi_p, \bar{\phi}_1,...,\bar{\phi}_p \in C_b(\mathbb{R}^{1+d})\) and \(\psi_1,...,\psi_p,\bar{\psi}_1,...,\bar{\psi}_p \in C_b(\mathcal{X}\times\mathcal{A})\), and consider a map \(F: D_E([0,T]) \to \mathbb{R}^+\), defined as \[F(\mu,\nu,P,Q) = F_1(\mu) + F_2(\nu) + F_3(\mu,\nu,P,Q) + F_4(\mu,\nu,P,Q),\] where \[\begin{align} F_1(\mu) &= \left| \left( \left \langle\bar{\varphi}, \mu_t \right \rangle- \left \langle\bar{\varphi}, \mu_0 \right \rangle \right) \times \prod_{j=1}^p \left \langle\bar{\phi}_j, \mu_{s_j} \right \rangle \right|, \\ F_2(\nu) &= \left| \left( \left \langle\varphi, \nu_t \right \rangle- \left \langle\varphi, \nu_0 \right \rangle \right) \times \prod_{j=1}^p \left \langle\phi_j, \nu_{s_j} \right \rangle \right|, \\ F_3(\mu,\nu,P,Q) &= \sum_{\xi\in\mathcal{X}\times\mathcal{A}} \Bigg| Q_t(\xi) - Q_0(\xi) - \alpha \int_0^t \sum_{\xi' = (x',a')} \left( r(\xi') + \gamma \sum_{z,a''} Q_s(z,a'')g_s(z,a'')p(z|\xi') - Q_s(x',a') \right) \nonumber \\ &\phantom{=}\times \left( \left \langle\sigma(w \cdot \xi')\sigma(w \cdot \xi) + c^{2} \sigma^{\prime}\left(w \cdot \zeta^{\prime}\right) \sigma^{\prime}(w \cdot \zeta) \zeta \cdot \zeta^{\prime}, \nu_s \right \rangle \right) \, \pi^{g_s}(\xi') \, ds \Bigg| \times \prod_{j=1}^p |\psi_j(Q_{s_j})|, \\ F_4(\mu,\nu,P,Q) &= \sum_{\xi\in\mathcal{X}\times\mathcal{A}} \Bigg| P_t(\xi) - P_0(\xi) - \int_0^t \sum_{\xi' = (x',a')} \zeta_s Q_s(\xi') \sigma^{g_s}(x',a') \Bigg(\left \langle\sigma(w\cdot\zeta') \sigma(w\cdot\zeta) + c^2 \sigma'(w\cdot\xi) \sigma(w\cdot\xi) (\xi'\cdot\xi), \mu_s \right \rangle\nonumber \\ &\phantom{=}- \sum_{a''} f_s(x',a'') \left \langle\sigma(w\cdot\zeta') \sigma(w\cdot\zeta) + c^2 \sigma'(w\cdot\xi) \sigma(w\cdot\xi) (\xi'\cdot\xi), \mu_s \right \rangle\Bigg) \, ds \Bigg| \times \prod_{j=1}^p |\bar{\psi}_j(P_{s_j})|, \end{align}\] where \[f_t = \mathrm{Softmax}(P_t), \quad g_t = \frac{\eta_t}{d_a} + (1-\eta_t) f_t\] Then we have \[\mathbb{E}_{\rho^N}[F(\mu,\nu,P,Q)] = \mathbb{E}\left[ F(\mu^N, \nu^N, P^N, Q^N) \right]\] Let us analyse each terms of \(\mathbb{E}\left[ F(\mu^N, \nu^N, P^N, Q^N) \right]\) one by one. Firstly, 48 and the boundedness of \(\bar{\phi}_j\) yields \[\mathbb{E}[F_1(\mu^N)] \leq C \mathbb{E}\left| \left \langle\bar{\varphi}, \mu^N_t \right \rangle- \left \langle\bar{\varphi}, \mu^N_0 \right \rangle \right| \leq \frac{C_T}{\sqrt{N}} + \frac{C_T}{N^{3/2}} \overset{N\to\infty}\to 0.\] Similarly, 48 and the boundedness of \(\phi_j\) yields \[\mathbb{E}[F_2(\nu^N)] \leq C \mathbb{E}\left| \left \langle\varphi, \nu^N_t \right \rangle- \left \langle\varphi, \nu^N_0 \right \rangle \right| \leq \frac{C_T}{\sqrt{N}} + \frac{C_T}{N^{3/2}} \overset{N\to\infty}\to 0.\] To study the next two term, we define \[f^N_t = \mathrm{Softmax}(P^N_t), \quad \tilde{g}^N_t = \frac{\eta_t}{d_a} + (1-\eta_t) f^N_t,\] \[\begin{align} E^{1,N}_t(\xi) &= \int_0^t \sum_{\xi'} \mathsf{B}^N_{\xi,\xi',s} (\pi^{\tilde{g}^N_s}(\xi') - \pi^{g^N_s}(\xi')) \left[ r(\xi') + \gamma \sum_{z,a''} Q^N_s(z,a'') \tilde{g}^N_s(z,a'')p(z|\xi') - Q^N_s(\xi') \right] \, ds, \\ E^{2,N}_t(\xi) &= \int_0^t \sum_{\xi'} \mathsf{B}^N_{\xi,\xi',s} \pi^{g^N_s}(\xi') \gamma \sum_{z,a''} Q^N_s(z,a'') (\tilde{g}^N_s(z,a'') - g^N_s(z,a''))p(z|\xi') \, ds. \end{align}\] Then by 36 : \[\begin{align} &\phantom{=}F_3(\mu^N, \nu^N, P^N, Q^N) \\ &= \sum_{\xi\in\mathcal{X}\times\mathcal{A}} \Bigg| Q^N_t(\xi) - Q^N_0(\xi) - \alpha \int_0^t \sum_{\xi'} \mathsf{B}^N_{\xi,\xi',s} \pi^{\tilde{g}^N_s}(\xi') \left[ r(\xi') + \gamma \sum_{z,a''} Q^N_s(z,a'') \tilde{g}^N_s(z,a'')p(z|\xi') - Q^N_s(\xi') \right] \, ds \Bigg| \times \prod_{j=1}^p |\psi_j(Q_{s_j})| \\ &= \sum_{\xi\in\mathcal{X}\times\mathcal{A}} \Bigg| Q^N_t(\xi) - Q^N_0(\xi) - \alpha \int_0^t \sum_{\xi'} \mathsf{B}^N_{\xi,\xi',s} \pi^{g^N_s}(\xi') \left[ r(\xi') + \gamma \sum_{z,a''} Q^N_s(z,a'') g^N_s(z,a'')p(z|\xi') - Q^N_s(\xi') \right] \, ds \\ &\phantom{=}+ E^{1,N}_t(\xi) + E^{2,N}_t(\xi) \Bigg|\times \prod_{j=1}^p |\psi_j(Q_{s_j})| \\ &\overset{\eqref{eq:Q95pre95limit}}= \sum_{\xi \in \boldsymbol{\mathcal{X}}\times \boldsymbol{\mathcal{A}}} \alpha \left| M^{1,N}_t(\xi) + M^{2,N}_t(\xi) + M^{3,N}_t(\xi) + E^{1,N}_t(\xi) + E^{2,N}_t(\xi) + O_p(N^{-1/2}) \right| \times \prod_{j=1}^p |\psi_j(Q_{s_j})|. \addtocounter{equation}{1}\end{align}\] Recall by Assumption 2 that the stationary measures \(\pi^g\) are globally Lipschitz in \(g\), so for any \(\xi'\) and \(s \leq NT\) \[\begin{align} |\pi^{\tilde{g}^N_s}(\xi') - \pi^{g^N_s}(\xi')| &\leq C\sup_{\xi'} |\tilde{g}^N_s(\xi') - g^N_s(\xi')| \\ &\leq C|\eta^N_{\floor{Ns}} - \eta^N_s| \\ &=\frac{C}{1+\log^2(\frac{\floor{Ns}}{N}+1)} - \frac{C}{1+\log^2(s+1)} \\ &\leq C\left( \log^2(s+1) - \log^2\left( \frac{\floor{Ns}}{N}+1) \right) \right) \\ &\leq C\left( \log^2\left( \frac{\floor{Ns} + 1}{N}+1 \right) - \log^2\left( \frac{\floor{Ns}}{N}+1) \right) \right) \leq \frac{C}{N}, \addtocounter{equation}{1}\end{align}\] owing to the fact that \(\log^2(\cdot)\) is 1-Lipschitz. We therefore have \[\begin{align} \mathbb{E}[E^{1,N}_t(\xi)] &\leq \frac{C}{N} \mathbb{E}\left[ \int_0^t \sum_{\xi'} |\mathsf{B}^N_{\xi,\xi',s}| \left[ |r(\xi')| + \gamma \sum_{z,a''} |Q^N_s(z,a'')| |g^N_s(z,a'')| p(z|\xi') - Q^N_s(\xi') \right] \, ds \right] \\ &\leq \frac{1}{N} \mathbb{E}\left[ TC_T \sup_{\xi}|Q^N_s(\xi)| \right] \leq \frac{C_T}{N}, \end{align}\] and \[\begin{align} E^{2,N}_t(\xi) &= \frac{C}{N} \mathbb{E}\left[ \int_0^t \sum_{\xi'} \mathsf{B}^N_{\xi,\xi',s} \pi^{g^N_s}(\xi') \gamma \sum_{z,a''} |Q^N_s(z,a'')| p(z|\xi') \, ds \right] \leq \frac{1}{N} \mathbb{E}\left[ TC_T \sup_{\xi}|Q^N_s(\xi)| \right] \leq \frac{C_T}{N}. \end{align}\] Finally, we have \[\mathbb{E}[F_3(\mu^N, \nu^N, P^N, Q^N)] \leq C \sum_{\xi} \left[ \mathbb{E}|M^{1,N}_t(\xi)| + \mathbb{E}|M^{2,N}_t(\xi)| + \mathbb{E}|M^{3,N}_t(\xi)| + \mathbb{E}|E^{1,N}_t(\xi)| + \mathbb{E}|E^{2,N}_t(\xi)| \right] \overset{N\to\infty}\to 0.\] To study the final term, we define \[\begin{align} E^{3,N}_t(\xi) = \int_0^t \zeta_s \sum_{\xi'} (\sigma_{\rho_0}^{\tilde{g}^N_s}(\xi') - \sigma_{\rho_0}^{g^N_s}(\xi')) \, \mathsf{clip}(Q^N_s(\xi')) \left[\bar{\mathsf{B}}^N_{\xi, \xi', s} - \sum_{a''} f^N_s(x',a'') \bar{\mathsf{B}}^N_{\xi, (x', a''), s} \right] ds, \\ E^{4,N}_t(\xi) = \int_0^t (\zeta^N_{\floor{Ns}} - \zeta_s) \sum_{\xi'} \sigma_{\rho_0}^{g^N_s}(\xi') \, \mathsf{clip}(Q^N_s(\xi')) \left[\bar{\mathsf{B}}^N_{\xi, \xi', s} - \sum_{a''} f^N_s(x',a'') \bar{\mathsf{B}}^N_{\xi, (x', a''), s} \right] ds, \end{align}\] Then \[\begin{align} F_4(\mu^N,\nu^N,P^N,Q^N) &= \sum_{\xi \in\mathcal{X}\times\mathcal{A}} \Bigg| P^N_t(\xi) - P^N_0(\xi) - \int_0^t \sum_{\xi'} \zeta_s Q^N_s(\xi') \sigma^{\tilde{g}^N_s}(\xi') \left[\bar{\mathsf{B}}^N_{\xi, \xi', s} - \sum_{a''} f^N_s(x',a'') \bar{\mathsf{B}}_{\xi, (x', a''), s} \right] \, ds \Bigg| \\ &\phantom{=}\times \prod_{j=1}^p |\bar{\psi}_j (P_{s_j})|,\\ &= \sum_{\xi\in\mathcal{X}\times\mathcal{A}} \Bigg| P^N_t(\xi) - P^N_0(\xi) - \int_0^t \sum_{\xi'} \zeta_{\floor{Ns}} Q^N_s(\xi') \sigma^{g^N_s}(\xi') \left[\bar{\mathsf{B}}^N_{\xi, \xi', s} - \sum_{a''} f^N_s(x',a'') \bar{\mathsf{B}}_{\xi, (x', a''), s} \right] \, ds \\ &\phantom{=}+ E^{3,N}_t(\xi) + E^{4,N}_t(\xi) \Bigg| \times \prod_{j=1}^p |\bar{\psi}_j (P_{s_j})|,\\ &= \sum_{\xi\in\mathcal{X}\times\mathcal{A}} |E^{3,N}_t(\xi) + E^{4,N}_t(\xi) + M^N_t(\xi) + O(N^{-1/2})| \times \prod_{j=1}^p |\bar{\psi}_j (P_{s_j})|. \end{align}\] Notice that the stationary measures \(\sigma^g\) are globally Lipschitz in \(g\) by Assumption 2, so using a similar argument, we prove that \[|\sigma^{\tilde{g}^N_s}(\xi') - \sigma^{g^N_s}(\xi')| \leq \frac{C}{N}. \addtocounter{equation}{1}\] In addition, we have \[\sup_{\xi,\xi'} \left| \bar{\mathsf{B}}^N_{\xi, \xi', s} - \sum_{a''} f^N_s(x',a'') \bar{\mathsf{B}}^N_{\xi, (x', a''), s} \right| \leq \sup_{\xi,\xi'} \left[ \left| \bar{\mathsf{B}}^N_{\xi, \xi', s} \right| + \sum_{a''} f^N_s(x',a'') \left| \bar{\mathsf{B}}_{\xi, (x', a''), s} \right| \right] \leq C_T\] as a result of \(\bar{B}^N_{\xi,\xi',s}\) being uniformly bounded by Lemma 3 whenever \(s \leq T\). Therefore for any \(t \leq T\), \[\begin{align} E^{3,N}_t(\xi) \leq T \times \frac{C_T}{N} \times 2 \times C_T = \frac{C_T}{N}. \end{align}\] Similarly, \[\begin{align} \left| E^{4,N}_t(\xi) \right| &\leq C_T \int_0^T \left| \zeta^N_{\floor{Ns}} - \zeta_s \right| \, ds \\ &\leq \sum^{\floor{NT}-1}_{k=0} \int_{k/N}^{(k+1)/N} \left| \frac{1}{1+k/N} - \frac{1}{1+s} \right| \, ds \\ &\leq C_T \sum^{\floor{NT}-1}_{k=0} \frac{1}{N^2} = \frac{C_T}{N}. \end{align}\] Combining with the boundedness of \(\tilde{\phi}_p\), we have \[F_4(\mu^N,\nu^N,P^N,Q^N) \leq C\sum_\xi \left[ \mathbb{E}|E^{3,N}_t(\xi)| + \mathbb{E}|E^{4,N}_t(\xi)| + \mathbb{E}|M^{N}_t(\xi)| + O(N^{-1/2}) \right] \overset{N\to\infty}\to 0.\] Combining the above analysis yields: \[\mathbb{E}_{\rho^N}[F(\mu,\nu,P,Q)] \overset{N\to\infty}\to 0.\] But since \(F\) is uniformly bounded, by bounded convergence theorem, we have \[\begin{align} \mathbb{E}_{\rho}[F(\mu,\nu,P,Q)] = 0. \end{align}\] This holds for any choice of the test functions \(\varphi, \bar{\varphi}, \phi_j, \bar{\phi}_j, \psi_j, \bar{\psi}_j\), so we know that \(\rho\) is a Dirac measure concentrated on a solution that satisfies the evolution equation. ◻

4.4 Existence and uniqueness of solutions to limit ODEs↩︎

To complete the proof, if suffices to show that there exists a unique solution for the ODEs 14 . Here we treat \((Q,P)\) as a vector of size \(2M\) with \(M=\#\boldsymbol{\mathcal{X}}\times \#\boldsymbol{\mathcal{A}}\) as defined in assumption 1. \[\label{limit32ODE32fix32starting} \frac{d}{dt} \begin{pmatrix} Q_t \\ P_t \end{pmatrix} = F(t,Q_t,P_t) = \begin{pmatrix} F_1(t,Q_t,P_t) \\ F_2(t,Q_t,P_t) \end{pmatrix}\tag{76}\] where the first \(M\) entries \(F(Q,P)\) are specified as \[\begin{align} F_1(t,Q,P)(x,a) = \alpha \sum_{x', a'} \bar A_{x,a,x',a'} \pi^{g_t(P)}(x', a') \left(r(x', a') + \gamma \sum_{z, a''} Q(z, a'') [g_t(P)](z,a'') p(z| x', a') - Q(x', a') \right) \end{align}\] and the remaining \(M\) entries are specified as \[\begin{align} F_2(t,Q,P)(x,a) = \sum_{x', a'} \zeta_t \mathsf{clip}(Q(x', a')) \left[A_{x, a, x', a'} - \sum_{a''} [f(P)](x',a'') A_{x,a,x',a''} \right] \sigma^{g_t(P)}(x', a'). \end{align}\] Here the notation \(f(P)\) and \(g_t(P)\) denote the (probability) vectors in \(\mathbb{R}^{M}\): \[\begin{align} [f(P)](x,a) = \mathrm{Softmax}(P)(x,a) &= \frac{\exp\left( P(x,a) \right)}{\sum_{a''} \exp\left( P(x,a) \right)} \\ [g_t(P)](x,a) &= \frac{\eta_t}{|\mathcal{A}|} + (1-\eta_t) [f(P)](x,a). \end{align}\] We will show the global existence of solution for \(t \in [0,\infty)\) by taking the usual route of showing that \(F(Q,P)\) is locally Lipschitz and linearly bounded.

Lemma 16. Let \(\left\| \cdot \right\|_\infty\) the the infinity norm as defined in remark 6. Then for all \(R > 0\), there is a constant \(C_R > 0\) that only depends on \(R\) such that for all \((Q,P), (\tilde{Q}, \tilde{P})\) lying in the open \(R\)-ball, we have \[\label{eq:local95lipschitz} \left\| F(t,Q,P) - F(t,\tilde{Q},\tilde{P}) \right\|_\infty \leq C_R \left\| (Q,P) - (\tilde{Q}, \tilde{P}) \right\|_\infty, \quad \forall t \geq 0.\tag{77}\] Moreover, there is a constant \(C > 0\) such that for all \(Q,P\), we have \[\label{eq:linearly95bounded} \left\| F(t,Q,P) \right\|_\infty \leq C \left\| (Q,P) \right\|_\infty + C, \quad \forall t \geq 0.\tag{78}\] Therefore, \(F\) is locally Lipschitz and linearly bounded and for any fixed starting point \((Q_0, P_0)\), there exists the unique solution for ODE 76 .

We emphasise that the above lemma will also be true for any other norms on \(\mathbb{R}^{2M}\), as pointed out in remark 6, as any norms in \(\mathbb{R}^{2M}\) are equivalent with \(\|\cdot\|_\infty\).

Proof. Let us first prove equation 78 . Note that the tensor \(\bar A_{\xi,\xi'}\) is uniformly bounded by assumptions 3 and 5. Thus \[\begin{align} |F_1(t,Q,P)(x,a)| &\leq C \sum_{x', a'} \pi^{g_t(P)}(x',a') \left( |r(x', a')| + \gamma \sum_{z, a''} |Q(z, a'')| g(z,a'') p(z|x', a') + |Q(x', a')| \right) \\ &\leq C \sup_{x',a'} |r(x',a')| + C\gamma \sup_{z,a''} |Q(z,a'')| + C\gamma \sup_{x', a'} |Q(x',a')| \\ &\leq C + C \left\| (Q,P) \right\|_\infty. \end{align}\] It is also clear that \[\begin{align} |F_2(t,Q,P)(x,a)| &\leq C \sup_{x, a} |\mathsf{clip}(Q(x,a))| \leq C \end{align}\] This shows that \(F\) is linearly bounded.

To prove the local Lipschitz condition 77 , note that for all \(x,a\), \[\begin{align} \label{F132diff} &\left| F_1(t, Q,P)(x, a) - F_1(t, \tilde{Q},\tilde{P})(x,a) \right| \\ \leq& \alpha \sum_{x', a'} |A_{x,a,x',a'}| \left| \pi^{g_t(P)}(x', a') - \pi^{g_t(\tilde{P})}(x', a') \right| \underbrace{\left| r(x', a') + \gamma \sum_{z, a''} Q(z, a'') [g_t(P)](z,a'') p(z| x', a') - Q(x', a') \right|}_{\leq C + (\gamma+1)R} \\ +& \alpha \sum_{x', a'} |A_{x,a,x',a'}|\pi^{g_t(\tilde{P})}(x', a') \left| \sum_{z, a''} \gamma(Q(z, a'')[g_t(P)](z,a'') - \tilde{Q}(z,a'') [g_t(\tilde{P})](z,a''))p(z| x', a') - (Q(x', a') - \tilde{Q}(x', a')) \right|. \end{align}\tag{79}\] Using the Lipschitz continuity of the softmax function and Assumption 2, we know \[\begin{align} \label{F132first32term} \sup_{x,a} |[\pi^{g_t(P)}](x,a) - [\pi^{g_t(\tilde{P})}](x,a)| &\leq C \sup_{x,a} |[g_t(P)](x,a) - [g_t(\tilde{P})](x,a)| \\ &= C \sup_{x,a} |[f(P)](x,a) - [f(\tilde{P})](x,a)| \\ &\leq C \left\| P - \tilde{P} \right\|_\infty. \end{align}\tag{80}\] Note that for all \(z, a''\) \[\begin{align} \label{F132second32term} &\left| Q(z, a'')[g_t(P)](z,a'') - \tilde{Q}(z,a'') [g_t(\tilde{P})](z,a'') \right| \\ \leq& \left| Q(z, a'') \right| \cdot \left| [g_t(P)](z,a'') - [g_t(\tilde{P})](z,a'') \right| + [g_t(\tilde{P})](z,a'') \cdot \left| Q(z, a'') - \tilde{Q}(z,a'') \right| \\ \leq& CR\left( \sup_{z,a''} \left| P(z,a'')-\tilde{P}(z,a'') \right| \right) + \sup_{z,a''}\left| Q(z,a'')-\tilde{Q}(z,a'') \right| \\ \leq& CR \left\| (Q,P)-(\tilde{Q},\tilde{P}) \right\|_\infty. \end{align}\tag{81}\] Combining 79 , 80 and 81 , we have \[\left| [F_1(t, Q, P)](x,a) - [F_1(t, \tilde{Q}, \tilde{P})] \right| \leq C_R \left\| (Q,P)-(\tilde{Q},\tilde{P}) \right\|_\infty.\] Similarly for \(F_2\), \[\begin{align} \label{F232diff} & \left| [F_2(t, Q,P)](x, a) - [F_2(t, \tilde{Q},\tilde{P})](x,a) \right| \\ \leq& \sum_{x', a'} \zeta_t \left| \mathsf{clip}(Q(x', a'))-\mathsf{clip}(\tilde{Q}(x', a')) \right| \sigma^{g_t(P)}(x', a') \left| A_{x, a, x', a'} - \sum_{a''} [f(P)](x',a'') A_{x,a,x',a''} \right| \\ +& \sum_{x', a'} \zeta_t \left| \mathsf{clip}(\tilde{Q}(x', a')) \right| \left| \sigma^{g_t(P)}(x', a') - \sigma^{g_t(\tilde{P})}(x', a') \right| \left| A_{x, a, x', a'} - \sum_{a''} [f(P)](x',a'') A_{x,a,x',a''} \right| \\ +& \sum_{x', a'} \zeta_t \left| \mathsf{clip}(\tilde{Q}(x', a')) \right| \sigma^{g_t(\tilde{P})}(x', a') \left| \sum_{a''} ([f(P)](x',a'') - [f(\tilde{P})](x',a'')) A_{x,a,x',a''} \right| \\ \leq& C \left\| (Q,P)-(\tilde{Q},\tilde{P}) \right\|_\infty. \end{align}\tag{82}\] We therefore show that \(F\) is locally Lipschitz if we restrict \((Q,P)\) to be inside a \(R\)-ball for any \(R<\infty\).

The linear boundedness of \(F\) can guarantee that the solution grows almost exponentially. In fact, we have \[\left\| (Q_t,P_t) \right\| \leq \left\| (Q_0, P_0) \right\| + \int_0^t (C + \left\| (Q_s, P_s) \right\| C) \, ds \leq (\left\| (Q_0, P_0) \right\| + Ct) + C \int_0^t \left\| (Q_s,P_s) \right\| \, ds.\] which, together with Grönwall’s inequality, implies \[\label{exp32growth} \left\| (Q_t,P_t) \right\| \leq (\left\| (Q_0, P_0) \right\| + Ct) e^{Ct}.\tag{83}\] Suppose the above evolution equation possesses two solutions \((Q, P)_t, (\tilde{Q},\tilde{P})_t\) that satisfies \(Q_0 = \tilde{Q}_0\) and \(P_0 = \tilde{P}_0\). Then we have \[\frac{d}{dt}\left\| (Q_t,P_t) - (\tilde{Q}_t, \tilde{P}_t) \right\|^2 \leq 2 \left\| (Q_t,P_t) - (\tilde{Q}_t, \tilde{P}_t) \right\| \cdot \left\| F(t,Q_t,P_t) - F(t,\tilde{Q}_t, \tilde{P}_t) \right\|.\] Using 80 , 82 , 83 and replacing \(R\) in 80 by the norm \(\left\| (Q_t,P_t) \right\|\) in 83 , we can show that \[\frac{d}{dt}\left\| (Q_t,P_t) - (\tilde{Q}_t, \tilde{P}_t) \right\|^2 \leq \underbrace{(C + (C + Ct) e^{Ct})}_{H(t)} \left\| (Q_t,P_t) - (\tilde{Q}_t, \tilde{P}_t) \right\|^2.\] Therefore, by Gronwall’s inequality, we have \[\left\| (Q_t,P_t) - (\tilde{Q}_t, \tilde{P}_t) \right\|^2 \leq \left\| (Q_0,P_0) - (\tilde{Q}_0, \tilde{P}_0) \right\|^2 \exp\left( \int_0^t H(s) \, ds \right) = 0,\] which guarantee uniqueness. ◻

4.5 Proof of convergence↩︎

With the above preparations, now we can finish the proof of Theorem 4. Rrecall the sequence of probability measure \(\rho^N\) being the law of \(\left(\mu_t^N, \nu_t^N, P_t^N, Q_t^N\right)_{0\le t \le T}\). We have shown by relative compactness that every subsequence of \(\rho^N\) posesses a further subsequence that weakly converges to the \(\rho = (\mu, \nu, P, Q)\), which is the unique solution of the limit ODEs 14 . Therefore by Prokhorov’s Theorem (see [16], [40] for details), \(\rho^N\) weakly converges to \(\rho\), and thus we can conclude that the process \(\left(\mu_t^N, \nu_t^N, P_t^N, Q_t^N\right)_{0\le t \le T}\) weakly converges to \(\rho\).

5 Analysis of the limiting ODE↩︎

We have already set up the limit ODEs for the algorithm 1 and now we struy the convergence of the limit ODEs 14 . To improve the readilibity, we first clarify some notations.

From their definitions in 1 , \(V^{f}(x)\) and \(V^{f}(x,a)\) are related via the formula \[V^{f}(x)=\sum_a V^{f}(x, a)f(x,a).\]
Recalling the state and state-action visiting measures \(\nu^{f}\) and \(\sigma^{f}\) defined in 2 , we have \(\sigma_\mu^{f}(x, a)=f(x, a) \cdot \nu_\mu^{f}(x)\). By [2], the stationary distribution of \(\boldsymbol{\widetilde{\mathcal{M}}}\) is the corresponding visitation measure of \(\boldsymbol{\mathcal{M}}\). And for the MDP start from a fixed state \(x_0\), the visiting measures are denoted by \(\nu^f_{x_0}(\cdot), \sigma^f_{x_0}(\cdot, \cdot)\)
Let the advantage function of policy \(f\) denoted by \[A^{f}(x, a) = V^{f}(x, a)-V^{f}(x),\quad \forall (x, a) \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}},\]

We recall that the gradient of a policy \(f\) parametrised by some parameter \(\theta\) can be evaluated in terms of the visiting measure 2 according to the policy gradient theorem 9 : \[\label{policy32gradient32theorem} \nabla_{\theta} J(f_{\theta}) = \sum_{x,a} \sigma^{f_{\theta}}(x,a) V^{f_{\theta}}(x,a) \nabla_{\theta} \log f_{\theta}(x,a),\tag{84}\] Assume that \(f = \text{softmax}(P)\) be the softmax policy parametrised directly by the values \(P(x,a)\), so that \[\label{softmax32NN32policy} f(x,a) = \frac{\exp\left( P(x,a) \right)}{\sum_{a''} \exp\left( P(x,a) \right)}.\tag{85}\] Then the gradient \(\nabla_P J(f)\) can be evaluated using the following formula.

Lemma 17. Define \(\partial_{x,a} J(f) := \frac{\partial J(f)}{\partial P(x,a)}\) and then for the policy 85 , by policy gradient theorem 84 , we have \[\label{policy32gradient} \partial_{x,a} J(f) = \sigma_{\rho_0}^{f}(x,a) A^{f}(x,a).\tag{86}\]

Proof. By the policy gradient theorem 84 , we have \[\begin{align} \label{element} \partial_{x,a} J(f) &= \sum_{x', a'} \nu_{\rho_0}^{f_\theta}(x') f(x', a') \mathbb{1}_{\{ x' = x\}} \left[ \mathbb{1}_{\{ a' = a\}} - f(x', a) \right] V^{f}(x', a') \\ &= \sum_{a'} \nu_{\rho_0}^{f}(x)f(x, a') \left[ \mathbb{1}_{\{ a' = a\}} - f(P)(x, a) \right] V^{f}(x, a') \\ &= \nu_{\rho_0}^{f}(x)f_\theta(x, a) V^{f}(x, a) - \nu_{\rho_0}^{f}(x)f(x, a) \left[ \sum_{a'}f(x, a') V^{f}(x, a') \right]\\ &= \nu_{\rho_0}^{f}(x)f(x, a) A^{f}(x, a)\\ &= \sigma_{\rho_0}^{f}(x, a) A^{f}(x, a). \end{align}\tag{87}\] ◻

5.1 Critic Convergence↩︎

Now we prove convergence of the critic 15 , which states that the critic model will converge to the state-action value function during training. We first derive an ODE for the difference between the critic and the value function. Then, we use a comparison lemma, a two time-scale analysis, and the properties of the learning and exploration rates 12 to prove the convergence of the critic to the value function.

Recall that the value function \(V^{g_t}\) satisfies the Bellman equation \[\label{Bellman32equation} r(x,a) + \gamma \sum_{z, a''} V^{g_t}(z,a'') g_t(z, a'') p(z| x,a) - V^{g_t}(x,a) = 0.\tag{88}\] Define the difference \[\phi_t = Q_t - V^{g_t}.\] Without loss of generality, we initialize the ODE as \(\bar Q_0 = 0\). We can then finish the proof for the convergence for the critic.

Proof of 15 . We first prove the convergence of \(\|Q_t - V^{g_t}\|\) and then by the decay of the exploration rate \(\epsilon_t\) we can get the convergence of \(\|Q_t - V^{f_t}\|\). Combining 14 and 88 , we get the ODE for \(\phi_t\) \[\begin{align} \frac{d \phi_t}{dt}(x,a) &= - \alpha \sum_{x', a'} A_{x,a, x', a'} \pi^{g_t}(x', a') \phi_t(x', a') \\ &+ \alpha \gamma \sum_{x', a'} A_{x,a, x', a'} \pi^{g_t}(x', a') \sum_{z, a''} \phi_t(z, a'') g_t(z,a'') p(z| x', a') \\ &- \frac{d}{dt} V^{g_t}(x,a). \end{align}\]

Let \(\odot\) denote element-wise multiplication. Then, \[\frac{d \phi_t}{dt} = - \alpha A ( \pi^{g_t} \odot \phi_t ) + \alpha \gamma A ( \pi^{g_t} \odot \Gamma_t ) + \frac{\partial V^{g_t}}{\partial g} \frac{d g_t}{d t},\] where \(\Gamma_t(x', a') = \displaystyle \sum_{z, a''} \phi_t(z, a'') g_t(z,a'') p(z| x', a')\). Define the process \[\label{Yt} Y_t = \frac{1}{2} \phi_t^{\top} A^{-1} \phi_t.\tag{89}\] Differentiating yields \[\begin{align} \label{Yeqn0} \frac{d Y_t}{d t} &= \phi_t^{\top} A^{-1} \frac{d \phi_t}{d t} \\ &= - \alpha \phi_t^{\top} \pi^{g_t} \odot \phi_t + \alpha \gamma \phi_t^{\top} \pi^{g_t} \odot \Gamma_t + \phi_t^{\top} A^{-1} \frac{\partial V^{g_t}}{\partial g} \frac{d g_t}{d t}. \end{align}\tag{90}\] The second term on the last line of (90 ) becomes: \[\begin{align} &\left| \phi_t^{\top} \pi^{g_t} \odot \Gamma_t \right| \\ =& \bigg{|} \sum_{x', a'} \phi_t(x', a') \pi^{g_t}(x', a') \sum_{z, a''} \phi_t(z, a'') g_t(z, a'') p(z | x', a') \bigg{|} \notag \\ =& \bigg{|} \sum_{x', a'} \sum_{z, a''} \phi_t(z, a'') \phi_t(x', a') g_t(z, a'') p(z | x', a') \pi^{g_t}(x', a') \bigg{|} \notag \\ \leq& \sum_{x', a'} \sum_{z, a''} \bigg{|} \phi_t(z, a'') \phi_t(x', a') \bigg{|} g_t(z, a'') p(z | x', a') \pi^{g_t}(x', a') \notag \\ \leq& \frac{1}{2} \sum_{x', a'} \sum_{z, a''} \bigg{(} \phi_t(z, a'')^2 + \phi_t(x', a')^2 \bigg{)} g_t(z, a'') p(z | x', a') \pi^{g_t}(x', a') \notag \\ =& \frac{1}{2} \sum_{z, a''} \phi_t(z, a'')^2 \sum_{x', a'} g_t(z, a'') p(z | x', a') \pi^{g_t}(x', a') + \frac{1}{2} \sum_{x', a'} \phi_t(x', a')^2 \pi^{g_t}(x', a') \sum_{z, a''} g_t(z, a'') p(z | x', a') \notag \\ =& \frac{1}{2} \sum_{z, a''} \phi_t(z, a'')^2 \pi^{g_t}(z, a'') + \frac{1}{2} \sum_{x', a'} \phi_t(x', a')^2 \pi^{g_t}(x', a') \notag \\ =& \sum_{x', a'} \phi_t(x', a')^2 \pi^{g_t}(x', a'). \end{align}\] where we have used Young’s inequality, the fact that \(\displaystyle \sum_{z, a''} g_t(z, a'') p(z | x', a') = 1\) for each \((x', a')\), and \(\displaystyle \sum_{x', a'} g_t(z, a'') p(z | x', a') \pi^{g_t}(x', a') = \pi^{g_t}(z, a'')\). Therefore, \[\begin{align} \frac{d Y_t}{d t} \leq - \alpha (1 - \gamma) \pi^{g_t} \cdot \phi_t^2 + \phi_t^{\top} A^{-1} \frac{\partial V^{g_t}}{\partial g} \frac{d g_t}{d t} , \label{Yeqn} \end{align}\tag{91}\] where \(\phi_t^2\) is an element-wise square. By the limit ODEs in 14 , we have for any \((x,a)\) \[\label{theta32uniform32bound} \left| \frac{dP_t}{dt}(x,a) \right| = \left| \sum_{x', a'} \zeta_t \mathsf{clip}(Q_t(x', a')) \left[A_{x, a, x', a'} - \sum_{a''} f_t(x',a'') A_{x,a,x',a''} \right] \sigma^{f_t}(x', a')\right| \le C\zeta_t\tag{92}\] For any state \(x_0\), define \[\partial_{P(x, a)} V^{f}(x_0) := \frac{\partial V^{f}(x_0) }{\partial P(x,a)}.\] Then, for the exploration policy 7 , by the policy gradient theorem we have \[\begin{align} \label{gradient32value} \left| \partial_{P(x, a)} V^{g_t}(x_0) \right|&= \left| \sum_{x',a'} \sigma_{x_0}^{g_t}(x',a') V^{g_t}(x',a') \partial_{P(x, a)} \log g_t(x',a') \right| \\ &\le C \sum_{x', a'} \left| \partial_{P(x,a)} \log g_t(x',a') \right| \\ &= C (1-\eta_t) \sum_{x', a'} \frac{f_t(x',a')}{g_t(x',a')} \left| \partial_{P(x,a)} \log f_t(x',a') \right| \\ &\overset{(a)}{\le} C, \end{align}\tag{93}\] where step \((a)\) is by \[\frac{f_{t}(x',a')}{g_{\bar\theta_t}(x',a')} = \frac{f_{t}(x',a')}{ \frac{\eta_t}{d_A} + (1 - \eta_t) \cdot f_{t}(x', a')} \le C\] and \[\left| \partial_{P(x, a)} \log f_{t}(x',a') \right| = \left| \mathbb{1}_{\{ x' = x\}} \left[ \mathbb{1}_{\{ a' = a\}} - f_t(x', a) \right] \right| \le 2.\] The relationship between the value functions \[\label{value32relation} V^{f_t}(x_0, a_0) = r(x_0, a_0) + \gamma \sum_{x'} V^{f_t}(x') p(x'| x_0, a_0), \quad \forall (x_0, a_0),\tag{94}\] can be combined with 93 to derive \[\label{state32action32bound} \left\|\nabla_P V^{g_t}(x,a)\right\| \le C, \quad \forall (x, a).\tag{95}\] Combining 92 and 95 , \[\label{zetaBound} \left|\frac{dV^{g_t}}{dt}(x,a)\right| = \left|\nabla_P V^{g_t}(x,a) \cdot \frac{d P_t}{dt}\right| \le \left\|\nabla_P V^{g_t}(x,a)\right\| \cdot \left\| \frac{d P_t}{dt} \right\| \le C \zeta_t,\tag{96}\] where \(C>0\) is a constant independent with \(T\).

Combining 91 , 96 , we have \[\begin{align} \label{critic} \frac{d Y_t}{d t} & \le - \alpha (1 - \gamma) \min_{x,a} \{ \pi^{g_t}(x,a) \} Y_t+ C \phi_t^{\top} \zeta_t \\ &\le - \alpha C\eta^{n_0}_t (1 - \gamma) Y_t + C \phi_t^{\top} \zeta_t\\ &\le - C \eta^{n_0}_t Y_t + \frac{ \eta^{n_0}_t }{ \eta^{n_0}_t } \| \phi_t \| C\zeta_t \\ &\le - C \eta^{n_0}_t Y_t + \| \phi_t \|^2 \eta^{2n_0}_t + \frac{C\zeta_t^2}{\eta_t^{2n_0}} \\ &= - \eta^{n_0}_t ( C - 2\eta^{n_0}_t )Y_t + \frac{C\zeta_t}{\eta^{2n_0}_t} \zeta_t. \end{align}\tag{97}\] Since \(\eta^{n_0}_t \to 0\) and \(\frac{\zeta_t}{\eta^{2n_0}_t} \to 0\) as \(t \to \infty\), there exists \(t_0 \ge 2\) such that \[\frac{dY_t}{dt} \le -C \eta^{n_0}_t Y_t + \zeta_t, \quad t \ge t_0,\] where the \(C\) is a constant independent with \(t\). Noting that \(\frac{\zeta_t}{\eta^{n_0}} \to 0\) as \(t \to \infty\), we know for any \(\epsilon_0 > 0\), there exists \(t_0 \ge t_0\) such that \[\frac{d(Y_t-\epsilon_0)}{dt} \le -C \eta^{n_0}_t \left( Y_t - \frac{\zeta_t}{\eta_t^{n_0}} \right) \le -C \eta^{n_0}_t \left( Y_t - \epsilon_0 \right), \quad t \ge t_0,\] By multiplying the integral factor \(\exp{\left\{ \int_{t_0}^t C \eta_s^{n_0} ds\right\}}\), we get \[\frac{d}{dt} \left( \exp{\left\{ \int_{t_0}^t C \eta_s^{n_0} ds\right\}} \cdot (Y_t-\epsilon_0) \right) \le \exp{\left\{ \int_{t_0}^t C \eta_s^{n_0} ds\right\}} \cdot \left( \frac{d(Y_t-\epsilon_0)}{dt} + C \eta^{n_0}_t \left( Y_t - \epsilon_0 \right) \right) \le 0, \quad t \ge t_0,\] which derives \[Y_t-\epsilon_0 \le \exp{\left\{ -\int_{t_0}^t C \eta_s^{n_0} ds\right\}} \cdot (Y_{t_0}-\epsilon_0) \to 0, \quad \text{as} \quad t \to \infty.\] Thus we get for any \(\epsilon_0 > 0\), there exists \(t_0 > 0\), such that \(Y_t \le 2 \epsilon_0\) for any \(t\ge t_0\), which brings us the desired convergence for \(\phi_t\).

By the policy gradient theorem, we have \[\frac{\partial V^f(x_0)}{\partial_{f(x,a)}} = V^{f}(x,a) \sigma_{x_0}^{f}(x).\] Thus, by the relationship 94 , \[\frac{\partial V^f(x_0, a_0)}{\partial_{f(x,a)}} = \gamma \sum_{x'} V^{f(x,a)} \sigma_{x'}^f(x) p(x'| x_0, a_0) \le C.\] Then, for any \((x, a) \in \boldsymbol{\mathcal{X}} \times \boldsymbol{\mathcal{A}}\), there exists \(\widetilde{t} \in [0,1]\) such that \[\begin{align} \label{exploration32decay} \left|V^{g_t}(x, a) - V^{f_t}(x ,a)\right| = \left|\nabla_f V^{ \widetilde{t}f_t + (1-\widetilde{t})g_t}(x, a) \cdot \left[ g_t - f_t \right]\right| \le C\eta_t, \end{align}\tag{98}\] Finally, combining 15 and 98 , we obtain 15 . ◻

5.2 Actor Convergence↩︎

Now we show that the actor converges to a stationary point. We introduce the following notation: \[\begin{align} \widehat{\nabla}_P J(f_t) &:= \sum_{x,a} \sigma_{\rho_0}^{g_t}(x, a) \bar Q_t(x,a)\nabla_P \log f_t(x,a), \\ \widehat{\partial}_{P(x,a)} J(f_t)&:= \sum_{x,a} \sigma_{\rho_0}^{g_t}(x, a) \bar Q_t(x,a)\partial_{P(x,a)} \log f_t(x,a). \end{align}\] By the policy gradient theorem, using the similar approach as in Lemma 17 for the softmax policy \(f = \text{softmax}(P)\) we have \[\begin{align} \widehat{\partial}_{P(x,a)} J(f_t) =& \sum_{x',a'} Q_t(x',a') \sigma_{\rho}^{g_t}(x',a') \widehat{\partial}_{P(x,a)} J(f_t) \log f_t(x',a') \\ = & \sigma_{\rho_0}^{g_t}(x,a)\left[ Q_t(x,a) - \sum_{a'}Q_t(x,a')f(x,a') \right] \end{align}\]

By the same method in [27] and the following lemmas, we can prove \(\|\nabla_P J(f_t)\| \to 0, \quad t \to \infty\).

Lemma 18. Let \(Y_t, W_t\) and \(Z_t\) be three functions such that \(W_t\) is nonnegative. Asuume there exists \(t_0 \ge 0\) such that \[\label{iteration} \frac{dY_t}{dt} \ge W_t +Z_t, \quad t\ge t_0\tag{99}\] and that \(\int_{t_0}^{\infty} Z_t dt\) converges. Then either \(Y_t \to \infty\) or else \(Y_t\) converges to a finite value and \(\int_0^{\infty} W_t dt < \infty\).

We may modify the above lemma so that the dichotomy holds whenever 99 holds for \(t \geq T\). Now we can prove the convergence for the actor.

Proof of theorem 5. Let \(f\) be the softmax policy in 85 , by the proof of Lemma \(7\) in [41], we know that the eigenvalues of the Hessian matrix of \(J(f_\theta)\) w.r.t. \(P\) are smaller than \(L :=\frac{8}{(1-\gamma)^3}\) and thus \(\nabla_P J(f)\) is \(L\)-Lipschitz continuous with respect to \(P\).

For the limit ode of \(P_t\) in 14 , define \[Y_t := A^{-1} P_t\] Then \[\begin{align} \frac{dY_t}{dt}(x,a) &= \sum_{z, b} \left(A^{-1}\right)_{x,a,z,b} \frac{dP_t}{dt}(z, b) \\ &= \sum_{z, b} \left(A^{-1}\right)_{x,a,z,b} \sum_{x', a'} \zeta_t \mathsf{clip}(Q_t(x', a')) \left[A_{z, b, x', a'} - \sum_{a''} f_t(x',a'') A_{z,b,x',a''} \right] \sigma_{\rho_0}^{g_t}(x', a')\\ &= \zeta_t \sum_{x', a'} \mathsf{clip}(Q_t(x', a')) \sigma_{\rho_0}^{g_t}(x', a') \left[ \sum_{z, b} \left( A^{-1}\right)_{x,a,z,b} A_{z, b, x', a'} - \sum_{z,b,a''} f_t(x',a'') \left( A^{-1}\right)_{x,a,z,b} A_{z,b,x',a''} \right]\\ &= \zeta_t \sum_{x', a'} \mathsf{clip}(Q_t(x', a')) \sigma_{\rho_0}^{g_t}(x', a') \left[ \mathbb{1}_{\{ x' = x,\;a' = a\}} - \sum_{a''} f_t(x',a'') \mathbb{1}_{\{ x' = x,\;a'' = a\}} \right]\\ &= \zeta_t \mathsf{clip}(Q_t(x, a)) \sigma_{\rho_0}^{g_t}(x, a) -\sum_{a'} \mathsf{clip}(Q_t(x, a')) \sigma_{\rho_0}^{g_t}(x, a')f_t(x, a)\\ &= \zeta_t \sigma_{\rho_0}^{g_t}(x,a)\left[ \mathsf{clip}(Q_t(x,a)) - \sum_{a'} \mathsf{clip}(Q_t(x,a')) f_t(x,a') \right]. \end{align}\] Thus we get the ode for \(Y_t\): \[\begin{align} \frac{dY_t}{dt}(x, a) = \zeta_t \sigma_{\rho_0}^{g_t}(x,a)\left[ \mathsf{clip}(Q_t(x,a)) - \sum_{a'} \mathsf{clip}(Q_t(x,a')) f_t(x,a') \right] \end{align}\] Since we know that \(\left\| Q_t - V^{f_t} \right\| \to 0\), we know that there is a \(T\) for which \(\mathsf{clip}(Q_t) = Q_t\) whenever \(t \geq T\). Thus we have \[\frac{dP_t}{dt} = \zeta_t A {\hat{\nabla}}_{P} J(f_t) \quad t \geq T\] By chain rule and note that \(A\) is a positive definiteness matrix, we get for all \(t \geq T\): \[\begin{align} \frac{d}{dt} J(f_t) &= \nabla_P J(f_t) \cdot \frac{dP_t}{dt} \ge C \zeta_t \lambda_1 \|\nabla_P J(f_t)\|^2 - C\zeta_t \eta_t \end{align}\] Then, by Lemma 18 and the assumption in 11 , we can show that either \(J(f_t)\to \infty\) or \(J(f_t)\) converges to a finite value and \[\label{key32bound} \int_0^{+\infty} \zeta_t\|\nabla_P J(f_t)\|^2dt < \infty.\tag{100}\]

Note that \(J(f) = \mathbb{E}_{f}\left[\sum_{k=0}^{+\infty} \gamma^k r(x_k, a_k)\right]\). Therefore, the objective function \(J\) is bounded by Assumption 1 and thus we know \(J(f_t)\) converges to a finite value and 100 is valid.

If there existed an \(\epsilon_0 >0\) and \(\bar t >0\) such that \(\|\nabla_P J(f_t)\| \ge \epsilon_0\) for all \(t \ge \bar t\), we would have \[\int_{\bar t}^{+\infty} \zeta_t\|\nabla_P J(f_t)\|^2dt \ge \epsilon_0^2 \int_{\bar t}^{+\infty} \zeta_tdt = \infty,\] which contradicts 100 . Therefore, \(\displaystyle \liminf_{t\to \infty}\|\nabla_P J(f_t)\| = 0\). To show that \(\displaystyle \lim_{t\to \infty}\|\nabla_P J(f_t)\| = 0\), assume the contrary; that is \(\displaystyle \limsup_{t\to \infty}\|\nabla_P J(f_t)\| > 0\). Then we can find a constant \(\epsilon_1>0\) and two increasing sequences \(\{a_n\}_{n\ge 1}, \{b_n\}_{n\ge 1}\) such that \[\begin{align} a_1 <b_1 <a_2 <b_2 <a_3 <b_3 < \cdots,\\ \|\nabla_P J(f_{a_n})\| < \frac{\epsilon_1}{2},\quad \|\nabla_P J(f_{b_n})\| > \epsilon_1. \end{align}\] Define the following cycle of stopping times: \[\begin{align} t_n &:= \sup\{s | s\in (a_n, b_n),\; \|\nabla_P J(f_s)\| < \frac{\epsilon_1}{2} \},\\ i(t_n) &:= \inf\{s | s\in (t_n, b_n),\; \|\nabla_\theta J(f_s)\| > \epsilon_1 \}. \end{align}\] Note that \(\|\nabla_P J(f_t)\|\) is continuous against \(t\), thus we have \[\begin{align} \label{property} &a_n \le t_n < i(t_n) \le b_n \\ &\|\nabla_P J(f_{t_n})\| = \frac{\epsilon_1}{2}, \quad \|\nabla_P J(f_{i(t_n)})\| =\epsilon_1\\ &\frac{\epsilon_1}{2} \le \|\nabla_P J(f_s)\| \le \epsilon_1, \quad s\in(t_n, i(t_n)). \end{align}\tag{101}\] Then, by the \(L\)-Lipschitz property of the gradient, we have for any \(t_n\) \[\begin{align} \frac{\epsilon_1}{2} &= \|\nabla_P J(f_{i(t_n)})\| - \|\nabla_P J(f_{t_n})\|\\ &\le \| \nabla_P J(f_{i(t_n)}) - \nabla_P J(f_{t_n}) \|\\ &\le L\| P_{i(t_n)} - P_{t_n} \|\\ &\le C \int_{t_n}^{i(t_n)} \zeta_s\| \nabla_P J(f_s)\| ds + C \int_{t_n}^{i(t_n)} \zeta_s \|\widehat{\nabla}_P J(f_s) - \nabla_P J(f_s)\|ds \\ &\le C \epsilon_1 \int_{t_n}^{i(t_n)} \zeta_s ds + C \int_{t_n}^{i(t_n)} \zeta_s \eta_s ds. \end{align}\] From this and by 12 it follows that \[\label{key2} \frac{1}{2L} \le \liminf_{n\to \infty} \int_{t_n}^{i(t_n)} \zeta_s ds.\tag{102}\]

Using 101 , we see that \[J(f_{\bar\theta_{i(t_n)}}) - J(f_{\bar\theta_{t_n}}) \ge C_1 (\frac{\epsilon_1}{2})^2 \int_{t_n}^{i(t_n)} \zeta_s ds - C_2\int_{t_n}^{i(t_n)} \zeta_s\eta_s ds.\] Due to the convergence of \(J(f_{\theta_{t_n}})\) and the assumption of the learning rate, this implies that \[\lim_{n\to \infty} \int_{t_n}^{i(t_n)} \zeta_s ds = 0,\] which contradicts 102 and thus the convergence to the stationary point is proven. ◻

Acknowledgement↩︎

This research has been supported by the EPSRC Centre for Doctoral Training in Mathematics of Random Systems: Analysis, Modelling and Simulation (EP/S023925/1).

References↩︎

[1]

Vijaymohan R. Konda and John Tsitsiklis. Actor-critic algorithms. In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.

[2]

Vijaymohan R. Konda. Actor-critic algorithms (ph. d. thesis). Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2002.

[3]

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature (London), 518(7540):529–533, 2015.

[4]

Raghuram Bharadwaj Diddigi, Prateek Jain, Prabuchandran K. J, and Shalabh Bhatnagar. Neural network compatible off-policy natural actor-critic algorithm. In 2022 International Joint Conference on Neural Networks (IJCNN), pages 1–10, 2022.

[5]

Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning, 2016.

[6]

Shalabh Bhatnagar, Mohammad Ghavamzadeh, Mark Lee, and Richard S Sutton. Incremental natural actor-critic algorithms. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.

[7]

Jan Peters and Stefan Schaal. Natural actor-critic. Neurocomputing, 71(7):1180–1190, 2008. Progress in Modeling, Theory, and Application of Computational Intelligenc.

[8]

Vijaymohan R. Konda and Vivek S. Borkar. Actor-critic type learning algorithms for markov decision processes. SIAM Journal on Control and Optimization, 38(1):94–123, 1999.

[9]

V. S. Borkar and S. P. Meyn. The o.d.e. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447–469, 2000.

[10]

Vijay R. Konda and John N. Tsitsiklis. On actor-critic algorithms. SIAM Journal on Control and Optimization, 42(4):1143–1166, 2003.

[11]

Albert. Benveniste, Michel. Metivier, and Pierre. Priouret. Adaptive Algorithms and Stochastic Approximations. Stochastic Modelling and Applied Probability, 22. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st ed. 1990. edition, 1990.

[12]

Vivek S. Borkar. Stochastic approximation with two time scales. Systems & Control Letters, 29(5):291–294, 1997.

[13]

Vivek S. Borkar. Asynchronous stochastic approximations. SIAM Journal on Control and Optimization, 36(3):840–851, 1998.

[14]

Dotan Di Castro and Ron Meir. A convergent online single time scale actor critic algorithm. Journal of Machine Learning Research, 11(11):367–410, 2010.

[15]

Vivek S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint Second Edition. Texts and Readings in Mathematics, 48. Hindustan Book Agency, Gurgaon, 1st ed. 2022. edition, 2022.

[16]

Stewart N Ethier and Thomas G Kurtz. Markov processes: characterization and convergence, volume 282. John Wiley & Sons, 2009.

[17]

Tengyu Xu, Zhe Wang, and Yingbin Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms, 2020.

[18]

Yue Frank Wu, Weitong ZHANG, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17617–17628. Curran Associates, Inc., 2020.

[19]

Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. Machine learning, 2023.

[20]

Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008.

[21]

Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.

[22]

Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.

[23]

Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.

[24]

Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01150, 2019.

[25]

Semih Cayci, Niao He, and R. Srikant. Finite-time analysis of entropy-regularized neural natural actor-critic algorithm, 2022.

[26]

Justin Sirignano and Konstantinos Spiliopoulos. Asymptotics of reinforcement learning with neural networks. Stochastic Systems, 2021.

[27]

Ziheng Wang and Justin Sirignano. Global convergence of the ode limit for online actor-critic algorithms in reinforcement learning. arXiv preprint arXiv:2108.08655, 2021.

[28]

Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.

[29]

Gregory F Lawler. Introduction to stochastic processes. Chapman and Hall/CRC, 2018.

[30]

Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.

[31]

Ziheng Wang and Justin Sirignano. Continuous-time stochastic gradient descent for optimizing over the stationary distribution of stochastic differential equations. arXiv preprint arXiv:2202.06637, 2022.

[32]

Ziheng Wang and Justin Sirignano. A forward propagation algorithm for online optimization of nonlinear stochastic differential equations. arXiv preprint arXiv:2207.04496, 2022.

[33]

Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279–292, 1992.

[34]

Yoshifusa Ito. Nonlinearity creates linear independence. Advances in Computational Mathematics, 5(1):189–203, 1996.

[35]

Étienne Pardoux and Yu Veretennikov. On the poisson equation and diffusion approximation. i. The Annals of Probability, 29(3):1061–1085, 2001.

[36]

Jian-Guo Liu, Ziheng Wang, Yantong Xie, Yuan Zhang, and Zhennan Zhou. Investigating the integrate and fire model as the limit of a random discharge model: a stochastic analysis perspective. Mathematical Neuroscience and Applications, 1, 2021.

[37]

Jian-Guo Liu, Ziheng Wang, Yuan Zhang, and Zhennan Zhou. Rigorous justification of the fokker–planck equations of neural networks based on an iteration perspective. SIAM Journal on Mathematical Analysis, 54(1):1270–1312, 2022.

[38]

Grigorios A Pavliotis. Stochastic processes and applications. Springer, 2016.

[39]

Sean P Meyn and Richard L Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.

[40]

Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, 2013.

[41]

Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820–6829. PMLR, 2020.

Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK (samuel.lam@maths.ox.ac.uk).↩︎
Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK (Justin.Sirignano@maths.ox.ac.uk).↩︎
Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK (wangz1@math.ox.ac.uk).↩︎
Author order is alphabetical.↩︎
The choice of the norm does not matter here as the process \((P^N_t, Q^N_t)\) lives in a finite-dimensional space.↩︎

Weak Convergence Analysis of Online Neural Actor-Critic Algorithms