Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy

Introduction

In reinforcement learning (RL) (Sutton et al. 1998), the agent aims to make sequential decisions that maximize the expected total reward through interacting with the environment and learning from the experiences, where the environment is modeled as a Markov Decision Process (MDP) (Puterman 2014). To learn a policy that achieves the highest possible total reward in expectation, the actor-critic method (Konda and Tsitsiklis 2000) is among the most commonly used algorithms. In actor-critic, the actor refers to the policy and the critic corresponds to the value function that characterizes the performance of the actor. This method directly optimizes the expected total return over the policy class by iteratively improving the actor, where the update direction is determined by the critic. In particular, recently, actor-critic combined with deep neural networks (LeCun et al. 2015) achieves tremendous empirical successes in solving large-scale RL tasks, such as the game of Go (Silver et al. 2017), StarCraft (Vinyals et al. 2019), Dota (OpenAI 2018), Rubik’s cube (Agostinelli et al. 2019; Akkaya et al. 2019), and autonomous driving (Sallab et al. 2017). See Li 2017 for a detailed survey of the recent developments of deep reinforcement learning.

Despite these great empirical successes of actor-critic, there is still an evident chasm between theory and practice. Specifically, to establish convergence guarantees for actor-critic, most existing works either focus on the bi-level setting or the two-timescale setting, which are seldom adopted in practice. In particular, under the bi-level setting (Yang et al. 2019a; Wang et al. 2019; Agarwal et al. 2019; Fu et al. 2019; Liu et al. 2019; Abbasi-Yadkori et al. 2019a; Abbasi-Yadkori et al. 2019b; Cai et al. 2019; Hao et al. 2020; Mei et al. 2020; Bhandari and Russo 2020), the actor is updated only after the critic solves the policy evaluation sub-problem completely, which is equivalent to applying the Bellman evaluation operator to the previous critic for infinite times. Consequently, actor-critic under the bi-level setting is a double-loop iterative algorithm where the inner loop is allocated for solving the policy evaluation sub-problem of the critic. In terms of theoretical analysis, such a double-loop structure decouples the analysis for the actor and critic. For the actor, the problem is essentially reduced to analyzing the convergence of a variant of the policy gradient method (Sutton et al. 2000; Kakade 2002) where the error of the gradient estimate depends on the policy evaluation error of the critic. Besides, under the two-timescale setting (Borkar and Konda 1997; Konda and Tsitsiklis 2000; Xu et al. 2020; Wu et al. 2020; Hong et al. 2020), the actor and the critic are updated simultaneously, but with disparate stepsizes. More concretely, the stepsize of the actor is set to be much smaller than that of the critic, with the ratio between these stepsizes converging to zero. In an asymptotic sense, such a separation between stepsizes ensures that the critic completely solves its policy evaluation sub-problem asymptotically. In other words, such a two-timescale scheme results in a separation between actor and critic in an asymptotic sense, which leads to asymptotically unbiased policy gradient estimates. In sum, in terms of convergence analysis, the existing theory of actor-critic hinges on decoupling the analysis for critic and actor, which is ensured via focusing on the bi-level or two-timescale settings.

However, most practical implementations of actor-critic are under the single-timescale setting (Peters and Schaal 2008a; Schulman et al. 2015; Mnih et al. 2016; Schulman et al. 2017; Haarnoja et al. 2018), where the actor and critic are simultaneously updated, and particularly, the actor is updated without the critic reaching an approximate solution to the policy evaluation sub-problem. Meanwhile, in comparison with the two-timescale setting, the actor is equipped with a much larger stepsize in the the single-timescale setting such that the asymptotic separation between the analysis of actor and critic is no longer valid.

Furthermore, when it comes to function approximation, most existing works only analyze the convergence of actor-critic with either linear function approximation (Xu et al. 2020; Wu et al. 2020; Hong et al. 2020), or shallow-neural-network parameterization (Wang et al. 2019; Liu et al. 2019). In contrast, practically used actor-critic methods such as asynchronous advantage actor-critic (Mnih et al. 2016) and soft actor-critic (Haarnoja et al. 2018) oftentimes represent both the actor and critic using deep neural networks.

Thus, the following question is left open:

Does single-timescale actor-critic provably find a globally optimal policy under the function approximation setting, especially when deep neural networks are employed?

To answer such a question, we make the first attempt to investigate the convergence and global optimality of single-timescale actor-critic with linear and neural network function approximation. In particular, we focus on the family of energy-based policies and aim to find the optimal policy within this class. Here we represent both the energy function and the critic as linear or deep neural network functions. In our actor-critic algorithm, the actor update follows proximal policy optimization (PPO) (Schulman et al. 2017) and the critic update is obtained by applying the Bellman evaluation operator only once to the current critic iterate. As a result, the actor is updated before the critic solves the policy evaluation sub-problem. Such a coupled updating structure persists even when the number of iterations goes to infinity, which implies that the update direction of the actor is always biased compared with the policy gradient direction. This brings an additional challenge that is absent in the bi-level and the two-timescale settings, where the actor and critic are decoupled asymptotically.

To tackle such a challenge, our analysis captures the joint effect of actor and critic updates on the objective function, dubbed as the “double contraction” phenomenon, which plays a pivotal role for the success of single-timescale actor-critic. Specifically, thanks to the discount factor of the MDP, the Bellman evaluation operator is contractive, which implies that, after each update, the critic makes noticeable progress by moving towards the value function associated with the current actor. As a result, although we use a biased estimate of the policy gradient, thanks to the contraction brought by the discount factor, the accumulative effect of the biases is controlled. Such a phenomenon enables us to characterize the progress of each iteration of joint actor and critic update, and thus yields the convergence to the globally optimal policy. In particular, for both the linear and neural settings, we prove that, single-timescale actor-critic finds a $O(K^{-1/2})$-globally optimal policy after $K$ iterations. To the best of our knowledge, we seem to establish the first theoretical guarantee of global convergence and global optimality for actor-critic with function approximation in the single-timescale setting. Moreover, under the broader scope of policy optimization with nonlinear function approximation, our work seems to prove convergence and optimality guarantees for actor-critic with deep neural network for the first time.

Contribution. Our contribution is two-fold. First, in the single-timescale setting with linear function approximation, we prove that, after $K$ iterations of actor and critic updates, actor-critic returns a policy that is at most $O(K^{-1/2})$ inferior to the globally optimal policy. Second, when both the actor and critic are represented by deep neural networks, we prove a similar $O(K^{-1/2})$ rate of convergence to the globally optimal policy when the architecture of the neural networks are properly chosen.

Related Work. Our work extends the line of works on the convergence of actor-critic under the function approximation setting. In particular, actor-critic is first introduced in Sutton et al. 2000; Konda and Tsitsiklis 2000. Later, Kakade 2002; Peters and Schaal 2008b propose the natural actor-critic method which updates the policy via the natural gradient (Amari 1998) direction. The convergence of (natural) actor-critic with linear function approximation are studied in Bhatnagar et al. 2008; Bhatnagar et al. 2009; Bhatnagar 2010; Castro and Meir 2010; Maei 2018. However, these works only characterize the asymptotic convergence of actor-critic and their proofs all resort to tools from stochastic approximation via ordinary differential equations (Borkar 2008). As a result, these works only show that actor-critic with linear function approximation converges to the set of stable equilibria of a set of ordinary differential equations. Recently, Zhang et al. 2019 propose a variant of actor-critic where Monte-Carlo sampling is used to ensure the critic and the policy gradient estimates are unbiased. Although they incorporate nonlinear function approximation in the actor, they only establish finite-time convergence result to a stationary point of the expected total reward. Moreover, due to having an inner loop for solving the policy evaluation sub-problem, they focus on the bi-level setting. Moreover, under the two-timescale setting, Wu et al. 2020; Xu et al. 2020 show that actor-critic with linear function approximation finds an $\varepsilon$-stationary point with $\widetilde{O}(\varepsilon^{-5/2})$ samples, where $\varepsilon$ measures the squared norm of the policy gradient. All of these results establish the convergence of actor-critic, without characterizing the optimality of the policy obtained by actor-critic.

In terms of the global optimality of actor-critic, Fazel et al. 2018; Malik et al. 2018; Tu and Recht 2018; Yang et al. 2019a; Bu et al. 2019; Fu et al. 2019 show that policy gradient and bi-level actor-critic methods converge to the globally optimal policies under the linear-quadratic setting, where the state transitions follow a linear dynamical system and the reward function is quadratic. For general MDPs, Bhandari and Russo 2019 recently prove the global optimality of vanilla policy gradient under the assumption that the families of policies and value functions are both convex. In addition, our work is also related to Liu et al. 2019 and Wang et al. 2019, where they establish the global optimality of proximal policy optimization and (natural) actor-critic, respectively, where both the actor and critic are parameterized by two-layer neural networks. Our work is also related to Agarwal et al. 2019; Abbasi-Yadkori et al. 2019a; Abbasi-Yadkori et al. 2019b; Cai et al. 2019; Hao et al. 2020; Mei et al. 2020; Bhandari and Russo 2020, which focus on characterizing the optimality of natural policy gradient in tabular and/or linear settings. However, these aforementioned works all focus on bi-level actor-critic, where the actor is updated only after the critic solves the policy evaluation sub-problem to an approximate optimum. Besides, these works consider linear or two-layer neural network function approximations whereas we focus on the setting with deep neural networks. Furthermore, under the two-timescale setting, Xu et al. 2020; Hong et al. 2020 prove that linear actor-critic requires a sample complexity of $\widetilde{O}(\varepsilon^{-4})$ for obtaining an $\varepsilon$-globally optimal policy. In comparison, our $O(K^{-1/2})$ convergence for single-timescale actor-critic can be translated into a similar $\widetilde{O}(\varepsilon^{-4})$ sample complexity directly. Moreover, when reusing the data, our result leads to an improved $\widetilde{O}(\varepsilon^{-2})$ sample complexity. In addition, our work is also related to Geist et al. 2019, which proposes a variant of policy iteration algorithm with Bregman divergence regularization. Without considering an explicit form of function approximation, their algorithm is shown to converge to the globally optimal policy at a similar $O(K^{-1/2})$ rate, where $K$ is the number of policy updates. In contrast, our method is single-timescale actor-critic with linear or deep neural network function approximation, which enjoys both global convergence and global optimality. Meanwhile, our proof is based on a finite-sample analysis, which involves dealing with the algorithmic errors that track the performance of actor and critic updates as well as the statistical error due to having finite data.

Our work is also related to the literature on deep neural networks. Previous works (Daniely 2017; Jacot et al. 2018; Wu et al. 2018; Allen-Zhu et al. 2018a; Allen-Zhu et al. 2018b; Du et al. 2018; Zou et al. 2018; Chizat and Bach 2018; Jacot et al. 2018; Li and Liang 2018; Cao and Gu 2019a; Cao and Gu 2019b; Arora et al. 2019; Lee et al. 2019; Gao et al. 2019) analyze the computational and statistical rates of supervised learning methods with overparameterized neural networks. In contrast, our work employs overparameterized deep neural networks in actor-critic for solving RL tasks, which is significantly more challenging than supervised learning due to the interplay between the actor and the critic.

Roadmap. In §2, we introduce the background of discounted MDP and actor-critic method. Then in §3, we introduce the two actor-critic methods, where the actors and critics are parameterized using linear functions and deep neural networks. The theoretical results are presented in §4.

Background

In this section, we introduce the background on discounted Markov decision processes (MDPs) and actor-critic methods.

where $\mathcal{P}(\mathcal{A})$ is the probability simplex on the action space $\mathcal{A}$ and $\theta$ is the parameter of the policy $\pi_{\theta}$. For any state-action pair $(s,a)\in{\mathcal{S}}\times\mathcal{A}$, we define the action-value function as follows,

2 Actor-Critic Method

To obtain an optimal policy $\pi^{*}$, the actor-critic method (Konda and Tsitsiklis 2000) aims to maximize the expected total reward as a function of the policy, which is equivalent to solving the following maximization problem,

where $\zeta$ is the initial state distribution, $Q^{\pi}$ is the action-value function defined in (2.2), and the family of parameterized polices $\Pi$ is defined in (2.1). The actor-critic method solves the maximization problem in (2.5) via first-order optimization using an estimator of the policy gradient $\nabla_{\theta}J(\pi)$. Here $\theta$ is the parameter of the policy $\pi$. In detail, by the policy gradient theorem (Sutton et al. 2000), we have

In this paper, we consider the following variant of the actor-critic method,

Algorithms

We consider two settings, where the actor and critic are parameterized using linear functions and deep neural networks, respectively. We consider the energy-based policy $\pi_{\theta}(a\,|\,s)\propto\exp(\tau^{-1}f_{\theta}(s,a))$, where the energy function $f_{\theta}(s,a)$ is parameterized with the parameter $\theta$. Also, for the (estimated) action-value function, we consider the parameterization $Q_{\omega}(s,a)$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$, where $\omega$ is the parameter. For such parameterizations of the actor and critic, the updates in (2.2) have the following forms.

Actor Update. The following proposition gives the closed form of $\pi_{k+1}$ in (2.2).

Let $\pi_{\theta_{k}}(a\,|\,s)\propto\exp(\tau_{k}^{-1}f_{\theta_{k}}(s,a))$ be an energy-based policy and

Then $\widetilde{\pi}_{k+1}$ has the following closed form,

for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$, where $\nu_{k}=\nu_{\pi_{\theta_{k}}}$ is the stationary state distribution of $\pi_{\theta_{k}}$.

Motivated by Proposition 3.1, to implement the actor update in (2.2), we update the actor parameter $\theta$ by solving the following minimization problem,

where $\rho_{k}=\rho_{\pi_{\theta_{k}}}$ is the stationary state-action distribution of $\pi_{\theta_{k}}$.

Critic Update. To implement the critic update in (2.2), we update the critic parameter $\omega$ by solving the following minimization problem,

Actor Update. The minimization problem in (3.1) admits the following closed-form solution,

which corresponds to a step of the natural policy gradient method (Kakade 2002).

Critic Update. The minimization problem in (3.2) admits the following closed-form solution,

respectively. With linear function approximation, the actor update in (3.6) is reduced to (3.3), while the critic update in (3.7) admits a closed form solution

which can be well approximated using state-action pairs drawn from $\rho_{\textrm{bhv}}$. See §4 for a detailed discussion.

Finally, by assembling the updates in (3.3) and (3.5), we present the linear actor-critic method in Algorithm 1, which is deferred to §B of the appendix.

2 Deep Neural Network Approximation

In this section, we consider deep neural network approximation. We first formally define deep neural networks. Then we introduce the actor-critic method under such a parameterization.

We initialize the DNN such that each entry of $W_{h}$ follows the standard Gaussian distribution $\mathcal{N}(0,1)$ for any $h\in[H]$, while each entry of $b$ follows the uniform distribution ${\rm Unif}(\{-1,1\})$. Without loss of generality, we fix $b$ during training and only optimize $\{W_{h}\}_{h\in[H]}$. We denote the initialization of the parameter $\theta$ as $\theta_{0}=(\mathop{\text{vec}}(W_{1}^{0})^{\top},\ldots,\mathop{\text{vec}}(W_{H}^{0})^{\top})^{\top}$. Meanwhile, we restrict $\theta$ within the ball $\mathcal{B}(\theta_{0},R)$ during training, which is defined as follows,

Here $\{W_{h}\}_{h\in[H]}$ and $\{W_{h}^{0}\}_{h\in[H]}$ are the weight matrices of $\theta$ and $\theta_{0}$, respectively. By (A.2), we have $\|\theta-\theta_{0}\|_{2}\leq R\sqrt{H}$ for any $\theta\in\mathcal{B}(\theta_{0},R)$. Now, we define the family of DNNs as

where $u_{\theta}$ is a DNN with depth $H$ and width $m$.

We parameterize the action-value function using $Q_{\omega}(s,a)\in\mathcal{U}(m_{\rm c},H_{\rm c},R_{\rm c})$ and the energy function of the energy-based policy $\pi_{\theta}$ using $f_{\theta}(s,a)\in\mathcal{U}(m_{\rm a},H_{\rm a},R_{\rm a})$. Here $\mathcal{U}(m_{\rm c},H_{\rm c},R_{\rm c})$ and $\mathcal{U}(m_{\rm a},H_{\rm a},R_{\rm a})$ are the families of DNNs defined in (A.3). Hereafter we assume that the energy function $f_{\theta}$ and the action-value function $Q_{\omega}$ share the same architecture and initialization, i.e., $m_{\rm a}=m_{\rm c}$, $H_{\rm a}=H_{\rm c}$, $R_{\rm a}=R_{\rm c}$, and $\theta_{0}=\omega_{0}$. Such shared architecture and initialization of the DNNs ensure that the parameterizations of the policy and the action-value function are approximately compatible. See Sutton et al. 2000; Konda and Tsitsiklis 2000; Kakade 2002; Peters and Schaal 2008a; Wang et al. 2019 for a detailed discussion.

Actor Update. To solve (3.1), we use projected stochastic gradient descent, whose $n$-th iteration has the following form,

Here $\Gamma_{\mathcal{B}(\theta_{0},R_{\rm a})}$ is the projection operator, which projects the parameter onto the ball $\mathcal{B}(\theta_{0},R_{\rm a})$ defined in (A.2). The state-action pair $(s,a)$ is sampled from the stationary state-action distribution $\rho_{k}$. We summarize the update in Algorithm 3, which is deferred to §B of the appendix.

Critic Update. To solve (3.2), we apply projected stochastic gradient descent. More specifically, at the $n$-th iteration of projected stochastic gradient descent, we sample a tuple $(s,a,r,s^{\prime},a^{\prime})$, where $(s,a)\sim\rho_{k+1}$, $r=r(s,a)$, $s^{\prime}\sim P(\cdot\,|\,s,a)$, and $a^{\prime}\sim\pi_{\theta_{k+1}}(\cdot\,|\,s^{\prime})$. We define the residual at the $n$-th iteration as $\delta(n)=Q_{\omega(n)}(s,a)-(1-\gamma)\cdot r-\gamma\cdot Q_{\omega_{k}}(s^{\prime},a^{\prime})$. Then the $n$-th iteration of projected stochastic gradient descent has the following form,

Here $\Gamma_{\mathcal{B}(\omega_{0},R_{\rm c})}$ is the projection operator, which projects the parameter onto the ball $\mathcal{B}(\omega_{0},R_{\rm c})$ defined in (A.2). We summarize the update in Algorithm 4, which is deferred to §B of the appendix.

By assembling Algorithms 3 and 4, we present the deep neural actor-critic method in Algorithm 2, which is deferred to §B of the appendix.

Finally, we remark that the off-policy actor and critic updates given in (3.6) and (3.7) can also incorporate deep neural network approximation with a slight modification, which enables data reuse in the algorithm.

Theoretical Results

In this section, we upper bound the regret of the linear actor-critic method. We defer the analysis of the deep neural actor-critic method to §C of the appendix. Hereafter we assume that $|r(s,a)|\leq r_{\max}$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$, where $r_{\max}$ is a positive absolute constant. First, we impose the following assumptions. Recall that $\rho^{*}$ is the stationary state-action distribution of $\pi^{*}$, while $\rho_{k}$ is the stationary state-action distribution of $\pi_{\theta_{k}}$. Moreover, let $\rho\in\mathcal{P}({\mathcal{S}}\times\mathcal{A})$ be a state-action distribution with respect to which we aim to characterize the performance of the actor-critic algorithm. Specifically, after $K+1$ actor updates, we are interest in upper bounding the following regret

where the expectation is taken with respect to $\{\theta_{k}\}_{k\in[K+1]}$ and $(s,a)\sim\rho$. Here we allow $\rho$ to be any fixed distribution for generality, which might be different from $\rho^{*}$.

In Assumption 4.1, $C_{\rho,\rho^{*}}$ is known as the discounted-average concentrability coefficient of the future-state-action distributions. Similar assumptions are commonly imposed in the literature (Szepesvári and Munos 2005; Munos and Szepesvári 2008; Antos et al. 2008a; Antos et al. 2008b; Scherrer 2013; Scherrer et al. 2015; Farahmand et al. 2016; Yang et al. 2019b; Geist et al. 2019; Chen and Jiang 2019).

It holds for any $\omega,\theta\in\mathcal{B}(0,R)$ that

Assumption 4.2 states that the Bellman evaluation operator maps a linear function to a linear function. Such an assumption only aims to simplify the presentation of our results. If the approximation error is nonzero, we only need to incorporate an additional bias term into the rate of convergence.

Assumption 4.3 ensures that the minimization problem in (3.2) admits a unique minimizer, which is used in the critic update. Similar assumptions are commonly imposed in the literature (Bhandari et al. 2018; Zou et al. 2019).

Under Assumptions 4.1, 4.2, and 4.3, we upper bound the regret of Algorithm 1 in the following theorem.

We assume that Assumptions 4.1, 4.2, and 4.3 hold. Let $\rho$ be a state-action distribution satisfying (ii) of Assumption 4.1. Also, for any confidence parameter $\delta\in(0,1)$ and sufficiently large number of iterations $K>0$, let $\beta=K^{1/2}$, $N=\Omega(KC_{\rho,\rho^{*}}^{2}\cdot(\phi^{*}/\sigma^{*})^{2}\cdot\log^{2}(KN/\delta))$, and the sequence of policy parameters $\{\theta_{k}\}_{k\in[K+1]}$ be generated by Algorithm 1. It holds with probability at least $1-\delta$ that

where the expectation is taken with respect $(s,a)\sim\rho$.

We sketch the proof in §5. See §D.1 for a detailed proof. ∎

Theorem 4.4 establishes an $O(K^{1/2})$ regret of Algorithm 1, where $K$ is the total number of iterations. Here $O(\cdot)$ omits terms involving $(1-\gamma)^{-1}$ and $\log|\mathcal{A}|$. To better understand Theorem 4.4, we consider the ideal setting, where we have access to the action-value function $Q^{\pi}$ of any policy $\pi$. In such an ideal setting, the critic update is unnecessary. However, the natural policy gradient method, which only uses the actor update, achieves the same $O(K^{1/2})$ regret (Liu et al. 2019; Agarwal et al. 2019; Cai et al. 2019). In other words, in terms of the iteration complexity, Theorem 4.4 shows that in the single-timescale setting, using only one step of the critic update along with one step of the actor update is as efficient as the natural policy gradient method in the ideal setting.

Furthermore, by the regret bound in (4.2), to obtain an $\varepsilon$-globally optimal policy, it suffices to set $K\asymp(1-\gamma)^{-6}\cdot\varepsilon^{-2}\cdot\log^{2}|\mathcal{A}|$ in Algorithm 1 and output a randomized policy that is drawn from $\{\pi_{\theta_{k}}\}_{k=1}^{K+1}$ uniformly. Plugging such a $K$ into $N=\Omega(KC_{\rho,\rho^{*}}^{2}(\phi^{*}/\sigma^{*})^{2}\cdot\log^{2}(KN/\delta)))$, we obtain that $N=\widetilde{O}(\varepsilon^{-2})$, where $\widetilde{O}(\cdot)$ omits the logarithmic terms. Thus, to achieve an $\varepsilon$-globally optimal policy, the total sample complexity of Algorithm 1 is $\widetilde{O}(\varepsilon^{-4})$. This matches the sample complexity results established in Xu et al. 2020; Hong et al. 2020 for two-timescale actor-critic methods. Meanwhile, notice that here the critic updates are on-policy and we draw $N$ new data points in each critic update. As discussed in §3.1, under the off-policy setting, the critic updates given in (3.7) can be implemented using a fixed dataset sampled from $\rho_{\textrm{bhv}}$, the stationary state-action distribution induced by the behavioral policy. Under this scenario, the total number of data points used by the algorithm is equal to $N$. Moreover, by imposing similar assumptions on $\rho_{\textrm{bhv}}$ as in (i) of Assumption 4.1 and Assumption 4.3, we can establish a similar $O(K^{1/2})$ regret as in (4.2) for the off-policy setting. As a result, with data reuse, to obtain an $\varepsilon$-globally optimal policy, the sample complexity of Algorithm 1 is essentially $\widetilde{O}(\varepsilon^{-2})$, which demonstrates the advantage of our single-timescale actor-critic method. Besides, only focusing on the convergence to an $\varepsilon$-stationary point, Wu et al. 2020; Xu et al. 2020 establish the sample complexity of $\widetilde{O}(\varepsilon^{-5/2})$ for two-timescale actor-critic, where $\varepsilon$ measures the squared Euclidean norm of the policy gradient. In contrast, by adopting the natural policy gradient (Kakade 2002) in actor updates, we achieve convergence to the globally optimal policy. To the best of our knowledge, we establish the rate of convergence and global optimality of the actor-critic method with function approximation in the single-timescale setting for the first time.

Furthermore, as we will show in Theorem C.5 of §B, when both the actor and the critic are represented using overparameterized deep neural networks, we establish a similar $O((1-\gamma)^{-3}\cdot\log|\mathcal{A}|\cdot K^{1/2})$ regret when the architecture of the actor and critic neural networks are properly chosen. To our best knowledge, this seems the first theoretical guarantee for the actor-critic method with deep neural network function approximation in terms of the rate of convergence and global optimality.

Proof Sketch of Theorem 4.4

In this section, we sketch the proof of Theorem 4.4. Recall that $\rho$ is a state-action distribution satisfying (ii) of Assumption 4.1. We first upper bound $\sum_{k=0}^{K}(Q^{*}(s,a)-Q^{\pi_{\theta_{k+1}}}(s,a))$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ in part 1. Then by further taking the expectation over $\rho$ in part 2, we conclude the proof of Theorem 4.4. See §D.1 for a detailed proof.

Part 1. In the sequel, we upper bound $\sum_{k=0}^{K}(Q^{*}(s,a)-Q^{\pi_{\theta_{k+1}}}(s,a))$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$. We first decompose $Q^{*}-Q^{\pi_{\theta_{k+1}}}$ into the following three terms,

To understand the intuition behind $A_{1,k}$, $A_{2,k}$, and $A_{3,k}$, we interpret them as follows.

In the sequel, we upper bound $A_{1,k}$, $A_{2,k}$, and $A_{3,k}$, respectively. To establish such upper bounds, we define the following quantities,

To understand the intuition behind $\epsilon^{\rm c}_{k+1}$, $e_{k+1}$, and $\vartheta_{k}$, we interpret them as follows.

Interpretation of $\vartheta_{k}$. As defined in (5.7), $\vartheta_{k}$ measures the difference between $\pi_{\theta_{k}}$ and $\pi_{\theta_{k+1}}$ in terms of their differences with $\pi^{*}$, which are measured by the corresponding KL-divergences. In particular, $\vartheta_{k}$ is used in characterizing $A_{1,k}$ and $A_{2,k}$ defined in (5.2) and (5.3), respectively.

We remark that $\epsilon_{k+1}^{\rm c}$ measures the statistical error in the critic update, while $\vartheta_{k}$ measures the optimization error in the actor update. As discussed above, the convergence of $A_{3,k}$ to zero implies the contraction of both the actor update and the critic update, which illustrates the “double contraction” phenomenon. Meanwhile, since $e_{k+1}$ fully characterizes $A_{3,k}$ as shown in (5) subsequently, $e_{k+1}$ plays a key role in the “double contraction” phenomenon. In particular, the convergence of $e_{k+1}$ to zero is established in (5.9) subsequently. See Figure 1 for an illustration of these quantities.

With the quantities defined in (5.5), (5.6), and (5.7), we upper bound $A_{1,k}$, $A_{2,k}$, and $A_{3,k}$ as follows,

the proof of which is deferred to Lemmas D.1, D.2, and D.3 in §D.1 of the appendix, respectively. Meanwhile, by recursively expanding (5.5) and (5.6), we have

the proof of which is deferred to Lemma D.4 in §D.1 of the appendix. By plugging (5.9) into (5), we have

To better understand (5.10) and how it relates to the convergence of $A_{3,k}$, $A_{2,k}$, and $A_{1,k}$ to zero, we discuss in the following two steps.

Step (i). We assume $\epsilon_{i}^{\rm c}=0$, which corresponds to the number of data points $N\to\infty$. Then (5.10) yields $A_{3,k}=O(\gamma^{k})$, which implies that $A_{3,k}$ defined in (5.4) converges to zero driven by the discount factor $\gamma$. As discussed above, the convergence of $A_{3,k}$ to zero also implies the contraction between $\pi_{\theta_{k}}$ and $\pi_{\theta_{k+1}}$ of the actor update and the contraction between $Q_{\omega_{k}}$ and $Q^{\pi_{\theta_{k}}}$ of the critic update, which illustrates the “double contraction” phenomenon.

Now, by plugging (5) and (5.10) into (5.1), we establish an upper bound of $\sum_{k=0}^{K}(Q^{*}(s,a)-Q^{\pi_{\theta_{k+1}}}(s,a))$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$, which is deferred to (D.1) in §D.1 of the appendix. Hence, we conclude the proof in part 1. See part 1 of §D.1 for details.

Part 2. Recall that $\rho$ is a state-action distribution satisfying (ii) of Assumption 4.1. In the sequel, we take the expectation over $\rho$ in (D.1) and upper bound each term. We first introduce the following lemma, which upper bounds $\epsilon^{\rm c}_{k+1}$ defined in (5.5).

Under Assumptions 4.2 and 4.3, with probability at least $1-\delta$, it holds for any $k\in\{0,1,\ldots,K\}$ that

where the expectation is taken with respect to $(s,a)\sim\rho_{k+1}$.

Combining Lemmas D.5 and D.6 yields Theorem 4.4. See §D.1 for a detailed proof.

References

Appendix A Deep Neural Network Approximation

In this section, we consider deep neural network approximation. We first formally define deep neural networks. Then we introduce the actor-critic method under such a parameterization.

We initialize the DNN such that each entry of $W_{h}$ follows the standard Gaussian distribution $\mathcal{N}(0,1)$ for any $h\in[H]$, while each entry of $b$ follows the uniform distribution ${\rm Unif}(\{-1,1\})$. Without loss of generality, we fix $b$ during training and only optimize $\{W_{h}\}_{h\in[H]}$. We denote the initialization of the parameter $\theta$ as $\theta_{0}=(\mathop{\text{vec}}(W_{1}^{0})^{\top},\ldots,\mathop{\text{vec}}(W_{H}^{0})^{\top})^{\top}$. Meanwhile, we restrict $\theta$ within the ball $\mathcal{B}(\theta_{0},R)$ during training, which is defined as follows,

Here $\{W_{h}\}_{h\in[H]}$ and $\{W_{h}^{0}\}_{h\in[H]}$ are the weight matrices of $\theta$ and $\theta_{0}$, respectively. By (A.2), we have $\|\theta-\theta_{0}\|_{2}\leq R\sqrt{H}$ for any $\theta\in\mathcal{B}(\theta_{0},R)$. Now, we define the family of DNNs as

where $u_{\theta}$ is a DNN with depth $H$ and width $m$.

We parameterize the action-value function using $Q_{\omega}(s,a)\in\mathcal{U}(m_{\rm c},H_{\rm c},R_{\rm c})$ and the energy function of the energy-based policy $\pi_{\theta}$ using $f_{\theta}(s,a)\in\mathcal{U}(m_{\rm a},H_{\rm a},R_{\rm a})$. Here $\mathcal{U}(m_{\rm c},H_{\rm c},R_{\rm c})$ and $\mathcal{U}(m_{\rm a},H_{\rm a},R_{\rm a})$ are the families of DNNs defined in (A.3). Hereafter we assume that the energy function $f_{\theta}$ and the action-value function $Q_{\omega}$ share the same architecture and initialization, i.e., $m_{\rm a}=m_{\rm c}$, $H_{\rm a}=H_{\rm c}$, $R_{\rm a}=R_{\rm c}$, and $\theta_{0}=\omega_{0}$. Such shared architecture and initialization of the DNNs ensure that the parameterizations of the policy and the action-value function are approximately compatible. See Sutton et al. 2000; Konda and Tsitsiklis 2000; Kakade 2002; Peters and Schaal 2008a; Wang et al. 2019 for a detailed discussion.

Actor Update. To solve (3.1), we use projected stochastic gradient descent, whose $n$-th iteration has the following form,

Here $\Gamma_{\mathcal{B}(\theta_{0},R_{\rm a})}$ is the projection operator, which projects the parameter onto the ball $\mathcal{B}(\theta_{0},R_{\rm a})$ defined in (A.2). The state-action pair $(s,a)$ is sampled from the stationary state-action distribution $\rho_{k}$. We summarize the update in Algorithm 3, which is deferred to §B of the appendix.

Critic Update. To solve (3.2), we apply projected stochastic gradient descent. More specifically, at the $n$-th iteration of projected stochastic gradient descent, we sample a tuple $(s,a,r,s^{\prime},a^{\prime})$, where $(s,a)\sim\rho_{k+1}$, $r=r(s,a)$, $s^{\prime}\sim P(\cdot\,|\,s,a)$, and $a^{\prime}\sim\pi_{\theta_{k+1}}(\cdot\,|\,s^{\prime})$. We define the residual at the $n$-th iteration as $\delta(n)=Q_{\omega(n)}(s,a)-(1-\gamma)\cdot r-\gamma\cdot Q_{\omega_{k}}(s^{\prime},a^{\prime})$. Then the $n$-th iteration of projected stochastic gradient descent has the following form,

Here $\Gamma_{\mathcal{B}(\omega_{0},R_{\rm c})}$ is the projection operator, which projects the parameter onto the ball $\mathcal{B}(\omega_{0},R_{\rm c})$ defined in (A.2). We summarize the update in Algorithm 4, which is deferred to §B of the appendix.

By assembling Algorithms 3 and 4, we present the deep neural actor-critic method in Algorithm 2, which is deferred to §B of the appendix.

Finally, we remark that the off-policy actor and critic updates given in (3.6) and (3.7) can also incorporate deep neural network approximation with a slight modification, which enables data reuse in the algorithm.

Appendix B Details of Algorithms

In this section, we summarize the algorithms in §3. We first introduce the actor-critic method with linear function approximation in Algorithm 1.

We introduce the actor-critic method with DNN approximation in Algorithm 2, which relies on Algorithms 3 and 4 for the actor and critic updates.

Appendix C Convergence Results of Algorithm 2

In this section, we upper bound the regret of the deep neural actor-critic method. Hereafter we assume that $|r(s,a)|\leq r_{\max}$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$, where $r_{\max}$ is a positive absolute constant. First, we impose the following assumptions in parallel to Assumption 4.1. Recall that $\rho^{*}$ is the stationary state-action distribution of $\pi^{*}$, while $\rho_{k}$ is the stationary state-action distribution of $\pi_{\theta_{k}}$.

Meanwhile, we impose the following assumption in parallel to Assumption 4.2.

We upper bound the regret of the deep neural actor-critic method in Algorithm 2 in the sequel. To establish such an upper bound, we first establish the rates of convergence of Algorithms 3 and 4 as follows.

For any sufficiently large $N_{\rm a}>0$, let $m_{\rm a}=\Omega(d^{3/2}R_{\rm a}^{-1}H_{\rm a}^{-3/2}\log(m_{\rm a}^{1/2}/R_{\rm a})^{3/2})$, $H_{\rm a}=O(N_{\rm a}^{1/4})$, and $R_{\rm a}=O(m_{\rm a}^{1/2}H_{\rm a}^{-6}(\log m_{\rm a})^{-3})$. We denote by $\overline{\theta}$ the output of Algorithm 3 with input $\pi_{\theta}\propto\exp(\tau^{-1}f_{\theta})$, $\theta_{0}$, $Q_{\omega}$, $\alpha$, $\beta$, $\widetilde{\tau}=(\tau^{-1}+\beta^{-1})^{-1}$, and $N_{\rm a}$. Also, let $\widetilde{f}=\widetilde{\tau}\cdot(\beta^{-1}Q_{\omega}+\tau^{-1}f_{\theta})$. With probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$ over the random initialization $\theta_{0}$, we have

Here the expectation is taken over the randomness of $\overline{\theta}$ conditioning on the initialization $\theta_{0}$ and $(s,a)\sim\rho_{\pi_{\theta}}$, where $\rho_{\pi_{\theta}}$ is the stationary state-action distribution of $\pi_{\theta}$.

Here the expectation is taken over the randomness of $\overline{\omega}$ conditioning on the initialization $\omega_{0}$ and $(s,a)\sim\rho_{\pi_{\theta}}$, where $\rho_{\pi_{\theta}}$ is the stationary state-action distribution of $\pi_{\theta}$.

Propositions C.3 and C.4 characterize the errors that arise from the actor and critic updates in Algorithm 2, respectively. In particular, if the widths $m_{\rm a}$ and $m_{\rm c}$ of the DNNs $f_{\theta}$ and $Q_{\omega}$ are sufficiently large, the errors characterized in Propositions C.3 and C.4 decay to zero at the rates of $O(N_{\rm a}^{-1/2})$ and $O(N_{\rm c}^{-1/2})$, respectively. Propositions C.3 and C.4 act as the key ingredients to upper bounding the regret of the deep neural actor-critic method.

Based on Propositions C.3 and C.4, we upper bound the regret of Algorithm 2 in the following theorem, which is in parallel to Theorem 4.4.

We assume that Assumptions C.1 and C.2 hold. Let $\rho$ be a state-action distribution satisfying (ii) of Assumption C.1. Also, for any sufficiently large $K>0$, let $N_{\rm a}=\Omega(K^{6}C_{\rho,\rho^{*}}^{4}(\phi^{*}+\psi^{*}+1)^{4}R_{\rm a}^{4})$, $N_{\rm c}=\Omega(K^{6}C_{\rho,\rho^{*}}^{4}\phi^{*4}R_{\rm c}^{4})$, $H_{\rm a}=H_{\rm c}=O(N_{\rm c}^{1/4})$, $R_{\rm a}=R_{\rm c}=O(m_{\rm c}^{1/2}H_{\rm c}^{-6}(\log m_{\rm c})^{-3})$, $m_{\rm a}=m_{\rm c}=\Omega(d^{3/2}K^{6}C_{\rho,\rho^{*}}^{12}(\phi^{*}+\psi^{*}+1)^{12}R_{\rm c}^{16}H_{\rm c}^{42}\log(m_{\rm c}^{1/2}/R_{\rm c})^{3/2})$, $\beta=K^{1/2}$, and the sequence $\{\theta_{k}\}_{k\in[K]}$ be generated by Algorithm 2. With probability at least $1-1/K$ over the random initialization $\theta_{0}$ and $\omega_{0}$, it holds that

where the expectation is taken over the randomness of $(s,a)\sim\rho$ and $\{\theta_{k+1}\}_{k\in[K]}$ conditioning on the initialization $\theta_{0}$ and $\omega_{0}$.

When the architecture of the actor and critic neural networks are properly chosen, Theorem C.5 establishes an $O(K^{1/2})$ regret of Algorithm 2, where $K$ is the total number of iterations. Specifically speaking, to establish such a regret upper bound, we need the widths $m_{\rm a}$ and $m_{\rm c}$ of the DNNs $f_{\theta}$ and $Q_{\omega}$ to be sufficiently large. Meanwhile, to control the errors of actor update and critic update in Algorithm 2, we also run sufficiently large numbers of iterations in Algorithms 3 and 4.

In terms of the total sample complexity, to simplify our discussion, we omit constant and logarithmic terms here. To obtain an $\varepsilon$-globally optimal policy, it suffices to set $K\asymp\varepsilon^{-2}$ in Algorithm 2. By plugging such a $K$ into $N_{\rm a}=\Omega(K^{6}C_{\rho,\rho^{*}}^{4}(\phi^{*}+\psi^{*}+1)^{4}R_{\rm a}^{4})$ and $N_{\rm c}=\Omega(K^{6}C_{\rho,\rho^{*}}^{4}\phi^{*4}R_{\rm c}^{4})$ as required in Theorem C.5, we have $N_{\text{a}}=\widetilde{O}(\varepsilon^{-12})$ and $N_{\text{c}}=\widetilde{O}(\varepsilon^{-12})$. Thus, to achieve an $\varepsilon$-globally optimal policy, the total sample complexity of Algorithm 2 is $\widetilde{O}(\varepsilon^{-14})$. With the modification to off-policy setting as in §3.1, the total sample complexity of Algorithm 2 is $\widetilde{O}(\varepsilon^{-12})$.

To the best of our knowledge, we establish the rate of convergence and global optimality of the actor-critic method under single-timescale setting with DNN approximation for the first time.

Appendix D Proofs of Theorems

Recall that $\rho$ is a state-action distribution satisfying (ii) of Assumption 4.1. We first upper bound $\sum_{k=0}^{K}(Q^{*}(s,a)-Q^{\pi_{\theta_{k+1}}}(s,a))$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ in part 1. Then by further taking the expectation over $\rho$ and invoking Lemma 5.1 in part 2, we conclude the proof of Theorem 4.4.

Part 1. In the sequel, we upper bound $\sum_{k=0}^{K}(Q^{*}(s,a)-Q^{\pi_{\theta_{k+1}}}(s,a))$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$. By the definition of $Q^{*}$ in (2.2), it holds for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ that

where $A_{1,k}$, $A_{2,k}$, and $A_{3,k}$ are defined as follows,

It holds for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ that

where $\vartheta_{k}$ and $\epsilon^{\rm a}_{k+1}$ are defined as follows,

We remark that $\epsilon^{\rm a}_{k+1}=0$ for any $k$ in the linear actor-critic method. Meanwhile, such a term is included in Lemma D.1 only aiming to generalize to the deep neural actor-critic method.

It holds for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ that

where $\vartheta_{i}$ is defined in (D.4) of Lemma D.1, $\epsilon_{i+1}^{\rm a}$ is defined in (D.5) of Lemma D.1, and $\epsilon^{\rm c}_{i+1}$ is defined as follows,

We remark that $\epsilon^{\rm a}_{k+1}=0$ for any $k$ in the linear actor-critic method. Meanwhile, such a term is included in Lemma D.2 only aiming to generalize to the deep neural actor-critic method.

It holds for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ that

We upper bound $e_{k+1}$ in (D.7) of Lemma D.3 using Lemma D.4 as follows.

It holds for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ that

where $\epsilon_{i}^{\rm c}(s,a)$ is defined in (D.6) of Lemma D.2 and $\epsilon_{i+1}^{\rm b}(s)$ is defined as follows,

We remark that $\epsilon^{\rm b}_{i+1}=0$ for any $i$ in the linear actor-critic method. Meanwhile, such a term is included in Lemma D.4 only aiming to generalize to the deep neural actor-critic method.

Combining Lemmas D.3 and D.4, we obtain the following upper bound of $A_{3,k}$,

Combining (D.1), (D.1), Lemma D.1 and Lemma D.2, it holds for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ that

where $\vartheta_{i}$, $\epsilon_{i+1}^{\rm a}$, $\epsilon_{i+1}^{\rm c}$, and $e_{k+1}$ are defined in (D.4) of Lemma D.1, (D.5) of Lemma D.1, (D.6) of Lemma D.2, and (D.7) of Lemma D.3, respectively. We upper bound the last term as follows,

where we use the definition of $\vartheta_{k-i}$ in (D.4) of Lemma D.1 and the non-negativity of the KL divergence in the second equality and the last inequality, respectively. By plugging (D.1) and (D.1) into (D.1), we have

We remark that $\epsilon^{\rm a}_{i+1}=\epsilon^{\rm b}_{i+1}=0$ for any $i$ in the linear actor-critic method. Meanwhile, such terms is included in (D.1) only aiming to generalize to the deep neural actor-critic method. This concludes the proof in part 1.

Part 2. Recall that $\rho$ is a state-action distribution satisfying (ii) of Assumption 4.1. In the sequel, we take the expectation over $\rho$ in (D.1) and upper bound each term. Recall that $\epsilon^{\rm a}_{i+1}=\epsilon^{\rm b}_{i+1}=0$ for any $i$ in the linear actor-critic method. Hence, we only need to consider terms in (D.1) that do not involve $\epsilon^{\rm a}_{i+1}$ or $\epsilon^{\rm b}_{i+1}$. We first upper bound terms on the RHS of (D.1) that do not involve $\epsilon^{\rm c}_{i+1}$. More specifically, for any measure $\rho$ satisfying satisfying (ii) of Assumption 4.1, we upper bound the following three terms,

We upper bound $M_{1}$, $M_{2}$, and $M_{3}$ in the following lemma.

where $M_{1}$, $M_{2}$, and $M_{3}$ are defined in (D.1).

Now, we upper bound terms on the RHS of (D.1) that involve $\epsilon^{\rm c}_{i+1}$. More specifically, for any measure $\rho$ satisfying (ii) of Assumption 4.1, we upper bound the following two terms,

We upper bound $M_{4}$ and $M_{5}$ in the following lemma.

where $M_{4}$ and $M_{5}$ are defined in (D.14).

Now, by plugging Lemmas D.5 and D.6 into (D.1), we have

Meanwhile, by changing measure from $\rho^{*}$ to $\rho_{k+1}$, it holds for any $k$ that

where $\phi_{k+1}^{*}$ is defined in Assumption 4.1. Also, by Lemma 5.1, with probability at least $1-\delta$, it holds for any $k\in\{0,1,\ldots,K\}$ that

Combining (D.1), (D.18), and the choices of parameters stated in the theorem that

which concludes the proof of Theorem 4.4.

D.2 Proof of Theorem C.5

We follow the proof of Theorem 4.4 in §D.1. Following similar arguments when deriving (D.1) in §D.1, we have

Now, it remains to upper bound each term on the RHS of (D.2). We introduce the following error propagation lemma.

where $\epsilon_{k+1}^{\rm a}$ and $\epsilon_{k+1}^{\rm b}$ are defined in (D.5) and (D.8), respectively, $\phi^{*}_{k}$ and $\psi^{*}_{k}$ are defined in Assumption C.1.

Following from Lemma E.4, with probability at least $1-O(H_{\rm c})\exp(-\Omega(H_{\rm c}^{-1}m_{\rm c}))$, we have $|Q_{\omega_{0}}|\leq 2$. Also, from the fact that $|r(s,a)|\leq r_{\max}$, we know that $|Q^{*}|\leq r_{\max}$. Therefore, for any measure $\rho$, we have

Also, by changing the index of summation, we have

where $c(t)$ is defined in Assumption C.1. Further, by Lemma D.7 and interchanging the summation on the RHS of (D.23), we have

By similar arguments in the derivation of (D.2), we have

where we use the definition of $C_{\rho,\rho^{*}}$ from Assumption C.1 in the last inequality. Now, combining (D.2), (D.2), and (D.2), we have

Following from similar arguments when deriving (D.2), we have

Now, by plugging (D.2), (D.2), (D.25), (D.2), and (D.2) into (D.2), with probability at least $1-O(H_{\rm c})\exp(-\Omega(H_{\rm c}^{-1}m_{\rm c}))$, we have

Meanwhile, following from Propositions C.3 and C.4, it holds with probability at least $1-1/K$ that

Combining (D.31), (D.2), and the choices of parameters stated in the theorem, it holds with probability at least $1-1/K$ that

which concludes the proof of Theorem C.5.

Appendix E Supporting Results

In this section, we provide some supporting results in the proof of Theorems 4.4 and C.5. We introduce Lemma E.1, which applies to both Algorithms 1 and 2. To introduce Lemma E.1, for any policy $\pi$ and action-value function $Q$, we define $\widetilde{\pi}(a\,|\,s)\propto\exp(\beta^{-1}Q(s,a))\cdot\pi(a\,|\,s)$.

For any $s\in{\mathcal{S}}$ and $\pi^{\dagger}$, we have

By the definition of the KL divergence, it holds for any $s\in{\mathcal{S}}$ that

Meanwhile, for the term on the RHS of (E), we have

which concludes the proof of Lemma E.1. ∎

In the proofs of Propositions C.3 and C.4 in §F.2 and §F.3, respectively, we utilize the linearization of DNNs. We introduce some related auxiliary results here. First, we define the linearization $\bar{u}_{\theta}$ of the DNN $u_{\theta}\in\mathcal{U}(w,H,R)$ as follows,

where $\theta_{0}$ is the initialization of $u_{\theta}$. The following lemmas characterize the linearization error.

Suppose that $H=O(m^{1/12}R^{-1/6}(\log m)^{-1/2})$ and $m=\Omega(d^{3/2}R^{-1}H^{-3/2}\cdot\log(m^{1/2}/R)^{3/2})$. Then with probability at least $1-\exp(-\Omega(R^{2/3}m^{2/3}H))$ over the random initialization $\theta_{0}$, it holds for any $\theta\in\mathcal{B}(\theta_{0},R)$ and any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ that

See the proof of Lemma A.5 in Gao et al. 2019 for a detailed proof. ∎

Suppose that $H=O(m^{1/12}R^{-1/6}(\log m)^{-1/2})$ and $m=\Omega(d^{3/2}R^{-1}H^{-3/2}\cdot\log(m^{1/2}/R)^{3/2})$. Then with probability at least $1-\exp(-\Omega(R^{2/3}m^{2/3}H))$ over the random initialization $\theta_{0}$, it holds for any $\theta\in\mathcal{B}(\theta_{0},R)$ and any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$ that

By mean value theorem, there exists $t\in$, which depends on $\theta$ and $(s,a)$, such that

where we use Cauchy-Schwarz inequality in the first inequality. This concludes the proof of Lemma E.3. ∎

We denote by $x^{(h)}$ the output of the $h$-th layer of the DNN $u_{\theta}\in\mathcal{U}(m,H,R)$, and $x^{(h),0}$ the output of the $h$-th layer of the DNN $u_{\theta_{0}}\in\mathcal{U}(m,H,R)$. The following lemma upper bounds the distance between $x^{(h)}$ and $x^{(h),0}$.

With probability at least $1-\exp(-\Omega(R^{2/3}m^{2/3}H))$ over the random initialization $\theta_{0}$, for any $\theta\in\mathcal{B}(\theta_{0},R)$ and any $h\in[H]$, we have

Also, with probability at least $1-O(H)\exp(-\Omega(H^{-1}m))$ over the random initialization $\theta_{0}$, for any $\theta\in\mathcal{B}(\theta_{0},R)$ and any $h\in[H]$, it holds that

The first inequality follows from Lemma A.5 in Gao et al. 2019, and the second inequality follows from Lemma 7.1 in Allen-Zhu et al. 2018b. ∎

Appendix F Proofs of Propositions

We consider the Lagrangian of the above program,

where $\lambda(\cdot)$ is the dual parameter, which is a function on ${\mathcal{S}}$. Now, by plugging in

we have the following optimality condition,

for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$. Note that $\log(\sum_{a^{\prime}\in\mathcal{A}}\exp(\tau_{k}^{-1}f_{\theta_{k}}(s,a^{\prime})))$ is only a function of $s$. Thus, we have

for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$, which concludes the proof of Proposition 3.1.

F.2 Proof of Proposition C.3

We define the local linearization of $f_{\theta}$ as follows,

where we use the fact that $\Gamma_{\mathcal{B}(\theta_{0},R_{\rm a})}$ is a contraction mapping in the first inequality. We upper bound term (i) and term (ii) on the RHS of (F.2) in the sequel.

Upper Bound of Term (i). By Cauchy–Schwarz inequality, it holds that

where we use the fact that $\theta(n),\theta_{*}\in\mathcal{B}(\theta_{0},R_{\rm a})$ in the last inequality. Further, by the definitions in (F.2), it holds that

where we use (F.1) in the second equality. Combining (F.2) and (F.2), we obtain the following upper bound of term (i),

Upper Bound of Term (ii). We now upper bound term (ii) on the RHS of (F.2). It holds by Cauchy-Schwarz inequality that

We upper bound term (ii).a, term (ii).b, and term (ii).c in the sequel.

Meanwhile, by the definition of $g_{n}$ in (F.2), it holds that

We first upper bound $f_{\theta}$ as follows,

where $x^{(H_{\rm a})}$ is the output of the $H_{\rm a}$-th layer of the DNN $f_{\theta}$. Further combining Lemma E.4, it holds with probability at least $1-O(H_{\rm a})\exp(-\Omega(H_{\rm a}^{-1}m_{\rm a}))$ that

Following from similar arguments, with probability at least $1-O(H_{\rm a})\exp(-\Omega(H_{\rm a}^{-1}m_{\rm a}))$, we have

Combining Lemma E.2, (F.10), (F.11), (F.12), and (F.13), it holds with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$ that

which establishes an upper bound of term (ii).a.

Upper Bound of Term (ii).b. It holds that

We upper bound the three terms on the RHS of (F.2) in the sequel, respectively.

For the term $\|f_{\theta(n)}\nabla_{\theta}f_{\theta_{0}}-\bar{f}_{\theta(n)}\nabla_{\theta}f_{\theta_{0}}\|_{2}$ on the RHS of (F.2), following from Lemmas E.2 and E.3, it holds with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$ that

For the term $\|f_{\theta(n)}\nabla_{\theta}f_{\theta(n)}-f_{\theta(n)}\nabla_{\theta}f_{\theta_{0}}\|_{2}$ on the RHS of (F.2), following from (F.13) and Lemma E.2, with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$, we have

For the term $\|\widetilde{\tau}\cdot(\beta^{-1}Q_{\omega}+\tau^{-1}f_{\theta})\cdot(\nabla_{\theta}f_{\theta_{0}}-\nabla_{\theta}f_{\theta(n)})\|_{2}$ on the RHS of (F.2), we first upper bound $\widetilde{\tau}\cdot(\beta^{-1}Q_{\omega}+\tau^{-1}f_{\theta})$ as follows,

where we use (F.12), (F.13), and the fact that $\widetilde{\tau}^{-1}=\beta^{-1}+\tau^{-1}$. Further combining Lemma E.2, it holds with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$ that

Now, combining (F.2), (F.16), (F.17), and (F.18), it holds with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$ that

which establishes an upper bound of term (ii).b.

Upper Bound of Term (ii).c. It holds that

Further combining Lemma E.2, it holds with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$ that

which establishes an upper bound of term (ii).c.

Now, combining (F.2), (F.14), (F.19), and (F.20), we have

which is an upper bound of term (ii) on the RHS of (F.2).

By plugging the upper bound of term (i) in (F.8) and the upper bound of term (ii) in (F.21) into (F.2), combining (F.19), with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$, we have

Rearranging terms in (F.2), it holds with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$ that

By telescoping the sum and using Jensen’s inequality in (F.2), we have

where the last line comes from the choices that $\alpha=N_{\rm a}^{-1/2}$ and $H_{\rm a}=O(N_{\rm a}^{1/4})$. Further combining Lemma E.3 and using triangle inequality, we have

By the definition of $\theta_{*}$ in (F.3), we know that

By plugging the definition of $\bar{g}_{*}^{e}$ into (F.25), we have

Meanwhile, by the fact that $\theta_{0}=\omega_{0}$, we have

where the second line comes from $\widetilde{\tau}^{-1}=\beta^{-1}+\tau^{-1}$. Note that $\theta\in\mathcal{B}(\theta_{0},R_{\rm a})$, $\omega\in\mathcal{B}(\omega_{0},R_{\rm c})$, $\theta_{0}=\omega_{0}$, and $R_{\rm a}=R_{\rm c}$, we know that $\widetilde{\tau}\cdot(\beta^{-1}\omega+\tau^{-1}\theta)\in\mathcal{B}(\theta_{0},R_{\rm a})$. Therefore, with probability at least $1-\exp(-\Omega(R_{\rm a}^{2/3}m_{\rm a}^{2/3}H_{\rm a}))$ we have

where the first inequality comes from (F.26), and the last inequality comes from Lemma E.3 and the fact that $R_{\rm c}=R_{\rm a}$, $m_{\rm c}=m_{\rm a}$, and $H_{\rm c}=H_{\rm a}$. Combining (F.24) and (F.2), by triangle inequality, we have

which finishes the proof of Proposition C.3.

F.3 Proof of Proposition C.4

The proof is similar to that of Proposition C.3 in §F.2. For the completeness of the paper, we present it here. We define the local linearization of $Q_{\omega}$ as follows,

We upper bound term (iii) and term (iv) on the RHS of (F.3) in the sequel.

Upper Bound of Term (iii). By Hölder’s inequality, it holds that

where we use the fact that $\omega(n),\omega_{*}\in\mathcal{B}(\omega_{0},R_{\rm c})$ in the last line. Further, by the definitions in (F.3), it holds that

where the second equality comes from (F.28), and the last equality comes from the fact that the expectation is only taken to the state-action pair $(s_{0},a_{0})$. Combining (F.3) and (F.3), we obtain the following upper bound of term (i),

Upper Bound of Term (iv). We now upper bound term (iv) on the RHS of (F.3). It holds by Cauchy-Schwarz inequality that

We upper bound term (iv).a, term (iv).b, and term (iv).c in the sequel.

Upper Bound of Term (iv).a. We now upper bound term (iv).a on the RHS of (F.3). By expanding the square, we have

Meanwhile, by the definition of $g_{n}$ in (F.3), it holds that

We first upper bound $Q_{\omega}$ as follows,

where $x^{(H_{\rm c})}$ is the output of the $H_{\rm c}$-th layer of the DNN $Q_{\omega}$. Further combining Lemma E.4, it holds that

Combining Lemma E.2, (F.36), (F.37), (F.38), and (F.39), we have

Upper Bound of Term (iv).b. We now upper bound term (iv).b on the RHS of (F.3). It holds that

We now upper bound the three terms on the RHS of (F.3) in the sequel, respectively.

where we use (F.38) and the fact that $|r(s,a)|\leq r_{\max}$ for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$. Further combining Lemma E.2, with probability at least $1-\exp(-\Omega(R_{\rm c}^{2/3}m_{\rm c}^{2/3}H_{\rm c}))$, we have

Now, combining (F.3), (F.42), (F.43), and (F.3), it holds with probability at least $1-\exp(-\Omega(R_{\rm c}^{2/3}m_{\rm c}^{2/3}H_{\rm c}))$ that

Upper Bound of Term (iv).c. We now upper bound term (iv).c on the RHS of (F.3). It holds that

Further combining Lemma E.2, it holds that

Combining (F.3), (F.40), (F.45), and (F.46), we obtain the following upper bound for term (iv) on the RHS of (F.3),

We continue upper bounding (F.3). By plugging (F.34) and (F.47) into (F.3), it holds with probability at least $1-\exp(-\Omega(R_{\rm c}^{2/3}m_{\rm c}^{2/3}H_{\rm c}))$ that

Rearranging terms in (F.3), it holds with probability at least $1-\exp(-\Omega(R_{\rm c}^{2/3}m_{\rm c}^{2/3}H_{\rm c}))$ that

By telescoping the sum and using Jensen’s inequality in (F.3), we have

where the last line comes from the choices that $\eta=N_{\rm c}^{-1/2}$ and $H_{\rm c}=O(N_{\rm c}^{1/4})$. Further combining Lemma E.3 and using triangle inequality, we have

From the fact that $\widetilde{Q}\in\mathcal{U}(m_{\rm c},H_{\rm c},R_{\rm c})$ by Assumption C.2, we know that $\widetilde{Q}=Q_{\widetilde{\omega}}$ for some $\widetilde{\omega}\in\mathcal{B}(\omega_{0},R_{\rm c})$. Therefore, by (F.51), with probability at least $1-\exp(-\Omega(R_{\rm c}^{2/3}m_{\rm c}^{2/3}H_{\rm c}))$, we have

where we use Lemma E.3 in the last inequality. Now, combining (F.50) and (F.52), by triangle inequality, with probability at least $1-\exp(-\Omega(R_{\rm c}^{2/3}m_{\rm c}^{2/3}H_{\rm c}))$, we have

which concludes the proof of Proposition C.4.

Appendix G Proofs of Lemmas

Here, we use the fact that the projection $\Gamma_{R}(\cdot)$ is a contraction in the first inequality, and triangle inequality in the second inequality. Also, for notational convenience, we denote by $\widehat{\Phi}$, $\Phi$, $\widehat{v}$, and $v$ in (G.1) as follows,

By the fact that $\|\varphi(s,a)\|_{2}\leq 1$, $|r(s,a)|\leq r_{\max}$, and $\|\omega_{k}\|_{2}\leq R$ we have

Now, following from matrix Bernstein inequality (Tropp 2015) and Assumption 4.3, with probability at least $1-p/2$, we have

where $\sigma^{*}$ is defined in Assumption 4.3. Similarly, with probability at least $1-p/2$, we have