Convergence of Actor-Critic with Multi-Layer Neural Networks
Authors: Haoxing Tian
Alex Olshevsky
Ioannis Paschalidis
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Actor-Critic
gradient splitting
neural network
TL;DR: This paper establish a convergence result of Actor-Critic with neural network approximation.

Abstract: The early theory of actor-critic methods considered convergence using linear function approximators for the policy and value functions. Recent work has established convergence using neural network approximators with a single hidden layer. In this work we are taking the natural next step and establish convergence using deep neural networks with an arbitrary number of hidden layers, thus closing a gap between theory and practice. We show that actor-critic updates projected on a ball around the initial condition will converge to a neighborhood where the average of the squared gradients is $\tilde{O} \left( 1/\sqrt{m} \right) + O \left( \epsilon \right)$, with $m$ being the width of the neural network and $\epsilon$ the approximation quality of the best critic neural network over the projected set.

Convergence of Actor-Critic Methods with Multi-Layer Neural Networks
Haoxing Tian, Ioannis Ch. Paschalidis, Alex Olshevsky
Department of Electrical and Computer Engineering Boston University
Boston, MA 02215, USA
(tianhx, yannisp, alexols (texols]@bu.c. @bb. edu
Abstract
The early theory of actor-critic methods considered convergence using linear func- tion approximators for the policy and value functions. Recent work has estab- lished convergence using neural network approximators with a single hidden layer. In this work deep neural networks with an arbitrary numher of hidden layers, thus closing a gap between theory and practice. We show that actor-critic updates projected around the initial condition will converge to a neighborhood where the average the squared gradients is (1/vm) + O (c), with m being the width of the neural network and the approximation quality of the best critic neural network over the projected set.
taking the natural next step and establish convergence using
ball
Introduction
Reinforcement Learning (RL) has emerged as a powerful tool for solving decision decision-making problems
in model-freee way. Among the various RL algorithmms, the Actor-Critie (AC) method (Konda &
Tsitsiklis 3999)|Barto et al. (983)) has shown great success in various domains, including robotics,
game playing, and control systems (LeCun et al. (2015); Mnih et al. (2016); Silver al. (2017). )
AC involves simultaneous updates of two networks: an actor network that employs policy gradient
(Sutton et al. (1999) to update parameterized policy, and a critic network which is driven by the Temporal Differences (TD) in the estimated value function. While AC methods with neural networks
used for both actor and critic have achieved widespread use in practice fully satisfactory analysis of their convergence guarantees is currently lacking.
In recent years, number of theoretical studies of AC have obtained provable convergence rates and performance analyses. Almost all works this area assumed linear, rather than neural network- based, approximators for both actor and critic. A "two-timescale" linear AC was analysed in Wu et al. 22020), with convergence rate of (T74)/4) where T is the total number of iterations and (+) refers to potential logarithmic terms omitted from the notation; the term "two-timescale" refers to the fact that the stepsizes for the actor update and critic update are not proportional to each other, but rather the actor steps asymptotically negligible compared the critic steps. A "single- timescale" linear AC method was considered in Olshevsky & Gharesifard (2022); Chen et al. (202T) and both works obtained convergence rate of O (7 under an i.i.d. sampling assumption on the underlying MDP. The more realistic Markov sampling case was analyzed in the recent paper Chen & Zhao 2022), which also established a convergence rate of Ô (7-0.5). All these results rehed on lnnear approximations.
To our knowledge, convergence rates for AC with neural approximators were analyzed only in two recent works Wang et al. (2019): Cayci et al. 2022). Both of these papers considered neural net-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

works with a single hidden layer. The paper Wang et al. (2019) obtained convergence rate of O ((r-0.) with a final error of O (m (m-0225) under i.id. samplin. where m is the width of hidden layer. The case of Markov sampling was considered in Cayci et al. (2022) which improved this to Ó (T-0.5) and Ô (m--.5), respectively. Further, both Wang et al. 2019); Cayci et al. (2022) con- sidered "double-loop" methods where, in the inner loop, the critic takes sufficietlyy many steps to accurately estimate Q-values. Such double-loop methods do not match prevailing practice and are considerably easier to analyze since they can shown to approximate gradient descent.
Further, Cayci et al. (2022) required a projection onto ball of radius (/2) around the initial condition. Although a full representation theory for such neural networks is unknown, this is clearly limiting as compared to Wang et al. (2019) which only required projection onto ball of constant radius. For nonlinear approximations, such projections are usually needed to stabilize the algorithm; without them, AC can diverge both in theory and practice.
Table I: Comparisons with previous work.
Projection Radius
Convergence rate
Reference
Algorithm
Sampling
Approximation
W.t.
We ct al.
2020
Two-timescale
Markov
Linear
N/A
Ô (T-9.)
N/A
Singlo-loop
Olshevsky & Gharesifard
2022
Single-limesclle
L.d.
Linear
N/A
( 0.0)
N/A
Singlo-loop
Chen et ml
2021
Single-timescale
Single-loog
1.i.'
Linear
N/A
( 0.0)
N/A
Chen & Zhao
2022
Single-timescale
Stople-Ioop
Markov
Linear
N/A
Ó 0.0)
N/A
Wang ct al.
2019
Double-loop
I.i.d.
Single hidden layer
Constant
0 (T-22)
(m--123)
OT uij
Cayci
2023
Double-loop
Markov
Single hidden layer
Decaying
① (m=00)
sufficiently large
Ours
Single-Umescull
Single-loop
Markov
Any depth
Coustant
(7-U.)
(m=)))
The main contribution of this paper is to provide the first analysis of AC with neural networks of arbi- trary depth. While replicating the earlier results of a Ô (T 0.5) convergence rate and Ô (m-0.5) er- ror, our work considers a single-loop method with proportional step-sizes (sometimes called "single- timescale"). We prove this result under Markov sampling and project onto a ball of constant radius around the initial condition. An explicit comparison of our result to previous work is given in Table [ A more technical comparison is also given later after the statement of our main result.
Our main technical tool is the so-called "gradient splitting" view of TD learning. This idea began with the paper Ollivier (2018) which observed that TD learning is exactly gradient descent when the underlying policy is such that the state transition matrix is reversible. In Liu & Olshevsky (2021), this was generalized (discussed formally later in this work) and observing that, for linear approximation, TD updates are an example of gradient splitting. Gradient splitting is closely related to gradient descent, and the two processes can be analyzed similarly. A generalization to neural TD learning was given in Tian al. (2023), which argued for an interpretation of nonlinear TD as approximate gradient splitting,
non-reversible policies by introducing the notion of "gradient splitting"
The analysis of AC that we perform in this work is trickier because both actor and critic updates rely on each other, and one must prove that the resulting errors in each process do not compound in interaction with each other. This difficulty arises because we do not consider the "double loop" case where the actor can effectively wait for the critic converge, that actor steps resemble gra- dient steps with error; rather both actor and critic update simultaneously their (imperfect) estimates. Similarly what was done in Olshevsky & Charesifard (2022), we show that ideas from control theory to prove that the resulting process converges with a so-called "small-gain" analysis.
draw on some
2 Preliminaries
We begin by standardizing notation and stating the key concepts that will enable us to formulate our results alongside all the assumptions they require.
2

---

2.1 Markov Decision Processes (MDP)
finite discounted-rewatt MDP can be described by a tuple (S, A, Penv, r, 7, where S is a finite state-space whose elements are vectors, and we use Su E S to denote the starting state; A is finite action space with cardinality na: Peuv (Penv (s)) is the transition probability matrix, where Penv (n'l [s, a) is the probability of transitioning from 8 to s' after taking action o; r + IR the reward function, where r(s,() a) stands for the expected reward state 8 and taking action and E (0, 1) is the discount factor.
S A + [0, 1] where T[ass) is the probability that the agent takes action a in state Given a policy æ,, we can define the state transition matrix P = (P* (s' (s) ()) and the state-action transition matrix Px (Pa a' (e))))))))
policy x is mapping
(s'(s)) = Penv (s (s)a)((ass) Pa d'Is, = Penv (s' a)
The stationary distribution over state-action pairs jx is defined to be a nonnegative vector with coordinates summing to one and satisfying 33 p Ps. while the stationary distribution over T Pa. The Ferron-Frobenuus theorem guarantees that states H4 is defined similarly with 44 _ n such My and μ²- cxist and unique subject to some conditions on P Px. c.g,, aperiodicity and irreducibility (Gantmacher 1964)). We use ps (s, a) to denote each entry of aa and μ (s) each entry of pla. Clearly,
(=( = (s) The value function and the Q-function of a policy is defined as:
(1)
(s) Σ (s..), a
(+ = B,,,,
Σ (T((s) L(=
Here, Ex,a,, stands for the expectation when action is chosen in state and all subsequent actions are chosen according to policy т. Throughout the paper. if π can be parameterized by 8 then we will use 0 as a subscript instead of π, c.g., by writing (s) instead of V (s).
If is parameterized by 0, the Q-values satisfy the Bellman equation
Q7 a) = a(s + Σ Pols (7((s))
(3)
saaa
which can be stated in matrix notation as
Q3 = R R+
(4)
where Q3 (s, ()) and R (R(s, ()) vectors that stack up the Q- values and rewards, respectively. We will assume rewards bounded:
Assumption 2.1 (Bounded Reward). For any 8, E S x A, r(s,a))= Tmax-
This assumption commonly adopted throughout the literature, e.g., among the previous literature in Cayci et al. (2022); Wu et al. 2222)). An obvious implication of this is an upper bound on the Q valuue for any policy:
(s, a)) < Tmax
(5)
2.2 The Policy Gradient Theorem
We introduce the quantity @e(s), commonly called the discounted occupation measure which is defined as
do(s) = Σ Po(s = =),
t=0
where Po s) is the probability of being in state s after t steps and recall that we always begin state Sp- Next, we define Φ0(88 a) as
dg(s, a) (0(()))))))))) (a(s))

---

Note that the sum of both ((s) and o(s, a) equal to (1 - 11))-1 rather than 1:
Σ (
Σ
Φ
(6)
(s,a)ESxA
Now we are prepared to state the policy gradient theorem Sutton & Barto 2018 Theorem 2.1. (Policy Gradient Theorem)
VV
Σ
Oo(s)
a
SES
aEA
is standard to write this as
VV
Σ
(6(5.0)Q2(s..
(s,0)SxAA
which can be further rewritten in matrix form as
VV
V In 2gQ2
where Dg is diagonal matrix stacking up the (s(ss, a) as its diagonal entries.
2.3 Parameterized Value Function and Policy
We will now state the various assumptions have the policies and their parametrizations. We will say that a function f - is L-Lipschitz if
[f(x) [()) < L|r yl, Va,
and diffcrentiable function f : + R is H-smooth if
V V f()) - H| yl. Vx,
We will be using a multi-layer neural network to approximate the Q values under policy. We basically follow the same setting as in Liu et (2020), with some changes as far as notation goes. Specifically, we define the following recursion
(k)
(w((t)((t-1)) for (1...., K},
Vm"
where a an activation function and (*) stands for the value of k'th layer (x S A the input to this neural network). The neural network outputs Q(s, a, w), which is defined as
Q(s (ss.a.w) w)
1 mm
6t (K).
Notice that the output linear to (() as no activation function is applied here. While this formu- lation does not have bias, it is equivalent to formulation with bias if we pad all inputs with single 1, and add an additional node to every hidden layer that propagates this to subsequent layers. We will assume that all the hidden layers have the same width which denote by m, i.e., all the matrices (k) have rows and all the vector (k)), k 2 1 are m-dimensional. The total number of layers in the neural network is denoted by K.
For simplicity, we will make the following assumption on the neural network. Throughout the paper, we will use I| for the standard L2 norm.
Assumption 2.2. (Neural architecture and initialization) Suppose the neural network satisfies the following properties:
(Input assumption) Any input to the neural network satisfies || < 1.
(Activation function assumption) a is Lipsschht and Hmoshh
(Initialization assumption) Each entry of the vector b satisfies |be| S 1, Vr, and each entry of (k) is randomly chosen from ( 1), independently across entries.

---

Liu et al. (2020) showed that with these assumptions, the following result holds with high probability which we state as an assumption for our work.
Assumption 2.3. The absolute value of each entry of x(h) (the output of layer k of the neural network) is Om (1) at initialization.
Next, we will stack up the weights of different layers into a column vector w consisting of the entries of the matrices w(1), ..... (K))) with its norm defined by
K
|
A=
where 1| F is the Frobenius norm. During the training process, only the weights w will be updated while the final weights b will be left to their initial value. For convenience, define the vector Q(w) = (Q(s, a, w)) this vector will never be actually used in the execution of any algorithm we consider due to its high dimensionality,, it will be useful in some of the arguments will make. Finally, we assume the parametrization of the policy я is smooth.
which stacks up Q(s, a, w) over all state-action pairs (s, (s,a). While
Assumption 2.4 (Smooth parametrization). For all a, the quantities naa|s,0), In 0) are I.p-iipschitz and I2 -ipsciit with respect respectively.
Note that this forces us to use a smooth activation function and rules out non-differentiable actíva- tion functions such ReLU. If RELU-like activation is needed, one could use GeLU or ELU activation (which are smooth versions of ReLU) and still satisfy the above assumption. Note, also, that this assumption implicitly assumes that all policies are exploratory in sense assigning positive probability each action, since the derivative of In æ blows up + 0.
2.4 Neural Actor-Critic
We will use Projw (-) refer to projection onto ball with constant radius around the initial condition of the critic, where
{w ||w - woll S ow), aw a constant.
We now introduce the neural AC, which updates the actor and critic parameters
a
W++1 = -rojj {we + a " 6, V Q(s,, a,, we)). θc+1 = 0: 1-
Q(s âe, wi) Vo 0t).
where & the TD error defined by
8 = r(st(( az) + 7Q(5/, d/, wx) - Q(s,, az, wx),
(8)
and the samples are obtained as follows:
1. the state 8, is generated by taking a step in the Markov chain Penv from 8t-1;
2. the action a, is chosen according the policy T[a]s,,0))
3. the next state 8/, i.e, 8141, is determined according the transition probability Pan- of the MDP;
4. the action af is an action chosen at the next state according to the policy <a]ss; Oz);
5. the state-action pair (&,, â,) is obtained by first sampling geometric random variable T with distribution {P(T = t) = (1 - 7)>² 2 0}, and second obtaining T transitions by starting at su and taking actions according to (als, f.). Note that this update has to be re-done at every step, i.e., every requires Geom(7) steps.
The above algorithm will referred to as actor-critic with Markov sampling. also possible to consider a simplified variant, where step is slightly altered as follows: the state is instead chosen i.i.d. at every step from the stationary distribution of po, of the policy ne,- This is referred as actor-critic with i.i.d. sampling.
5

---

2.4.1 Approximation Assumptions
It is evident that any performance bound on AC will depend on how well the neural network used for the critic can approximate the true value function. If we choose neural network architecture for which universal approximation theorems do not apply and it happens to poorly approximate the true Q-functions, we will likely obtain poor results. Here, we will largely sidestep this issue by defining to be the approximation quality of the critic; our final performance results will be in terms of e.
Formally, we say that the vector Q an eaapproximation to the true value function Qô, of the policy Te, if
max [Q(s.a) (s,)a S..
(s.a)ExAA
We then make the following assumption.
Assumption 2.5. (Approximation capabilities of critic) For all 0, there exists some set of weights thg which give rise an c-approximation of Q-
Note that, since we do not say what is, this assumption could well be a definition of e. Throughout the paper we will use Q7, to denote an e-approximation to Qù guaranteed by the above assumption. Thus,
Q(ūx.) = Q
Further, we will assume that th a smooth function of the sense its first and second deriva- tives.
Assumption 2.6. (Smoothness of critic approximation) Suppose there exists scalars Lu (i) and (1) such that for all 0,
|I (f)l (i), Amax V (i) I Hi)
where } stands for the largest eigenvalue.
For convenience, we define
Tow Σ
Lew (i)
H / Σ (i)
Finally, we need additional assumption on the critic neural network. It should be obvious that any analysis of actor-critic has to assume that the critic is capable of approximating the correct Q- values. One part of this was already assumed earlier in Assumption 2.5 where assumed that an approximation exists. However, it should be clear that in the nonlinear case this is insufficient: just because there exists an approximation which is good doesn't 't follow that will be found during training, which is not known converge to the global minimizer in the nonlinear case, but rather only critical point.
We thus need something to rule out the possibility that the critic training gets stuck at a bad crticial point. It turns out that it suffices assume (a quantitative version of the fact that) the critic is one-to-one map from weights to value functions.
Assumption 2.7. (State regularity) There exists some constant > 0 such that
[[((w) - Q 2 X|| - أالl
Let us parse the meaning of this assumption. Because Q(ūū) = Q7- is appropriately viewed as quantitative version of the statement that if w1 * W2. then Q(w1) Q(w2). To see why this makes sense, note that the number of states is typically many magnitudes larger than the number of parameters in the critic. For example, in many applications the number of states often corresponds to the number of images (when states are captured through images) which is astronomical. Thus Qww) will map w much higher dimensional space.
If the states 8 are generated from a probability distribution which has continuous density, and the activation functions are continuous and increasing, the chance that Q (s) Qwey (s) even for one state 8 is zero. That is why we label it "state regularity" as above (and recall that Q(w) stacks up Qu (s) for every state s).

---

On a technical level, this property ensures that critic actually finds good critic approximation in spite of the nonlinearity the update. If the features are linear, this reduces to the assumption that the features are linearly independent, an assumption which is made in all previous and related work on AC method (Wu al. (2020); Oishevsky & Gharesifard (2022): Chen & Zhao (2022); Kumar
et al. (2023)) and TTD Learning (Liu & Olshevsky (2021): Xu & Gu (2020): Cai et al. (2019). Zou
ct al. 2019)).
2.5
The Mixing of Markov Chains
It is standard to make an assumption to the effect that all the Markov chains that can arise satisfy
mixing condition. Otherwise, it is possible under Markov sampling for the state fail explore the entire state-space. This assumption, first introduced by |Bhandari et al. (2018) in TD learning,
now is commonly used in AC analysis (Olshevsky & Gharesifard (2022): Wu et al. (2020) Chen &
Zhao )2022). )
Assumption 2.8 (Markov chain mixing). There exists constants > 0 and B E (0,1) with the following property: for all 0, if we consider Markov chain generated by at TT( 8t, 8), 8t+1 Penv (-18,,a)) starting from state s, then
1l-- - r'oll2 CB VT 2 S
where p+ is the probability distribution of the state of this Markov chain after steps.
To assure AC explores every possible state, we make the following assumption: Assumption 2.9. (Exploration) Suppose there exists some constant Mmin > such that, for all 8 pg is uniformly bounded away from O. In other words,
pg 2 pmin 0, VO.
Recall that μe was defined earlier to be the stationary distribution of the transition matrix associated with the policy πe. A key point is that the constants C, 3 and Mmin in the above assumptions do not depend on 6.
We note that there is some redundancy in our assumptions. As discussed above, we require In To(a|s) to have a smooth gradient for all 8, a, which ensures that my assigns strictly positive probability every action. This implics Assumptions 2.8 and 2.9 which can therefore be made into propositions. Nevertheless, we explicitly make Assumptions and 2.9 (even though both of them actually implied by our earlier assumption) since the quantities appearing in them (specifically, the mixing time 3 and the constant (mmin) appear in various bounds we will derive.
More precisely, we follow the earlier literature by setting C to be proportional to T the typi- cal stepsize in Stochastic Gradient Descent. We call the smallest such that Cff² < 0 (T 0.5
the mixing time and denote it by Tmix- It is easy to see that Tmix = O ((1 - =) log T') The quantity Tmix will appear throughout paper.
2.6 D-norm and Dirichlet Norm in MDPs
key ingredient is our analysis is the choice of norm: we have found that a certain norm originally introduced in Ollivier (2018) significantly simplifies analysis of the problem. We next introduce this norm and state our assumptions about it.
Let D2 = diag(pe(s a)) be the diagonal matrix whose elements are given by the entries of the stationary distribution μа associated with the policy нa. Given a function f S x A + E. its D-norm is defined as
11 = D = Σ (s,,,))
(10)
(s.a)ESxA
The D-norm is similar to the Euclidean norm except each entry is weighted proportionally to the stationary distribution. We also define the Dirichlet semi-norm of f:
I|
Σ
No(s, Pols . al)s,,))((())) (()
(11)
2
(e
7

---

A semi-norm satisfies the axioms of a norm except that it may be equal to zero at a non-zeeo vector. Note that I depends on the policy both through the stationary distribution [ a) as well as through the transition matrix Po.
Finally, following Olliiier (2018), the weighted combination of the D-norm and the Dirichlet semi- norm is denoted as (f) will be defined
No(f) - + +
(12)
Note that as long as po(s,a) O, which is stated in Assumption 2.9 all 8, a, we have that (fo(f) is a valid norm.
3 Our Main Results
To simplify the expression that follow, we will adopt the notations Ar and AQ for the two losses that we want to bound in our paper:
T E [IV.
T Σ E (Q(ws)))))
Av
AQ
(13)
T
T
Intuitively, Av corresponds to the actor emror: ideally, want reach point where the gradient of the actor value function is zero. Note that, since the value function is not convex in general, the actor error is measured in terms of distance to a stationary point above.
Similarly, AQ a measure of the critic error: equals zero precisely if Q(w:), the approximator of Q-function, equals Qo,- Of course, as discussed above, the critic neural network may not be able to perfectly represent the true Q-function. Now
ready state main results.
Theorem 3.1. Consider the neural AC algorithm mentioned in Section 2.4 Suppose Assumptions 2. 2.9 hold and the step-sizes a and a are both chosen to decay proportionally to O (T-6.6). 6.0).
1. In the i.i.d. sampling case,
Av S
- +0
AQ 00 + +())+
1
+0
2. In the Markov sampling case,
(logT)}
(log [1o T)
Av 50
+O(E)+Ō VT
DQ o
+0(+)+Ō
mm
VT
mm
In all 0()) notations above, we treat factors that do not depend on T, c, m as constants.
We next provide a more detailed comparison to the previous works of (Wang et al. (2019): Cayci al. (2022) ). Our discussion partially reprises the discussion in the Introduction, but now be discussed at greater level of detail:
Arbitrary hepthhsingle-ttmeseee The main contribution of this paper to provide an anal- ysis that applies neural networks of arbitrary depth. Moreover, we do so in single- loop/single-timsseee method where the critic and actor iterate simultancously, which is matching what is typically done in practice. Such analysis is inherently more techni- cally challenging, since when the actor can wait for the critic to go through sufficiently many iterations, could argue that the resulting Q-values approximately accurate and the process resembles gradient descent.
Representability. Both previous works for the single-layer case assume the Q-function lies in some function class, which, as discussed after Assumption 6 in Farahmand et al. (2016), is one kind of "no function approximation error" assumption. By contrast, we make no such assumption: rather we allow any approximation error for the critic e, and our final result is given in terms of f.
8

---

Lower bound on m. Previous works require m, the width of neural network, to be suf- ficiently large. In Wang et al. (2019), given that m is sufficiently large. Section 3.1 and Corollary A.3 argue that the gradient, denoted by dg and éhe, can be well approximated by the "centered feature mapping corresponding to the initialization", denoted by do. In Cayci et al. (2022), this dependency is even more emphasised since the upper bound shown in Theorem could diverge with small m.
Relation to NTK theory. NTK theory (Jacot et al. 2018)) tells that neural networks get more linear as m + oc. The classic analyses of this proceed by arguing that as m - oc, the neural network stays close to its initialization during training Chizat al. (2019). In that sense, we should expect to get a convergence result for AC as m - oc, but if the critic neural network stays close to its initial condition, the algorithm will effectively be using random linear features at initialization. For this reason, it is desirable not to argue that the critic neural network always stays close its initial condition. We do not such an argument in this work, whereas both Wang et al. (2019) and Cayci et al. (2022) obtain their results by arguing that the critic neural network stays close its initial condition. This theoretical distinction is shown in Tian et al. (2023) to match what happens in simulations, which shows empirically that even for projected neural TD, the critic neural network will move to the boundary of the projection ball.
Linearization. Previous works assume some kind of lincarization around the initial point. The objective is explicitly linearized in Wang et al. (2019). In Cayci al. (2022), while the objective is not linearized, the neural networks weights are projected onto radius of size ((1/vm) around the initial point.
4 Tools in Our Analysis
4.1 Choice of Norm and Gradient Splitting
A linear function h(0) is said to be gradient splitting of a convex quadratic
(0) minimized at 0 =
(14)
\V(())
2
In other words, a splitting h()) has exactly the same inner product with the "direction to the optimal solution" as the true gradient of (() (up the factor of 1 1/2). The connection between this idea and RL. was made the following papers:
h(0))
20
In Ollivier (0088) was shown that in TD Learning, if the matrix P corresponds reversible Markov chain, then [[]( = VaN(f) for some f. This makes Neural TD easy to analyze in the reversible case as it is exactly gradient descent.
Figure 1: Key
property of gradient splitting: h(0) has the same inner product with o as V (() up to factor of 1/2.
In & Olshevsky (202), it was shown how to further use the func- tion NV-) to analyze TD learning with linear approximation when the policy is not necessarily reversible. In particular, it was shown that the mean update of TD with linear approximation is a gradient splitring of the function N().. This is one of the crucial ideas we build on in this paper.
4.2 Nonlinear Small-Gain Theorem
Inspired by Olshevsky & Gharesifard (2022), our second main tool is a nonlinear version of the small-gain theorem. Because the actor and critic update simultaneously, possibility that errors in the actor compound with errors the critic to create divergence. For example, it is conceivable that, when the policy is fixed, the critic converges to reasonable approx- imation; when the critic is fixed, the actor converges to an approximate of the stationary point; but both updating simultaneously results in divergence.
need to rule out the
The core idea of small-gain is to write these updates in such a way so that one can argue that if certain coefficients are small enough, this "intercommection" of the actor and critic systems converges. The

---

-mall-gain theorem we use is a nonlinear version of the textbook version Drazin (1992). This is widely-used trick in control theory that avoids the necessity of explicitly finding Lyapunov function.
5 Conclusion
We have provided an analysis of Neural AC using a convex combination of the D-norm and the Dirichlet semi-norm describe the error. Our main result an error rate of O (T-0. + + Ô (m -0.) under the i.dd. sampling and O T)3. + E) + O (m 0.5) under the Markov sampling for neural networks of arbitrary depth. Crucially, our proof does make assumptions that force the neural networks to stay close to their initial conditions, relying instead arguments that show that neural networks which are not "too nonlinear" will still converge to an approximate minimum.
Acknowledgments and Disclosure of Funding
This research was partially supported by the NSF under grants CCF-2200052, DMS-1664644, and 191499,, by the ONR under grant 05CH11231, by the NIH under grant UL.54 TR004130, and by Boston University.
by the DOE under grant DE-AC02-
References
Andrew G Barto, Richard S Sutton, and Charles W Anderson. Neuronlike adaptive elements that solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, (5):834-846, 1983.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-differene learning con- verges to global optima. Advances in Neural Information Processing Systems, 32, 2019.
Semih Cayci, Niao He, and R Srikant. Finite-time analysis of entropy-regulariied neural natural actor-critic algorithm. arXiv preprint arXiv:2206.0083 2022.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 25294 25307, 2021.
Xuyang Chen and Lin Zhao. Finite-time analysis of single-timescale actor-critic. arXiv preprint arXiv:2210.0992// 2022.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Philip G Drazin. Nonlinear systems. Number 10. Cambridge University Press, 1992.
Amir-massoud Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor. Reg- ularized policy iteration with nonparametric function spaces. The Journal of Machine Learning Research, 17(1):4809-488 2016.
FR Gantmacher. The theory of matrices. New York, 1964.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
10

---

Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. Machine Learning, pp. 1-35, 2023.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):36-444, 2015.
Chaoyue Liu, Libin Zhu, and Misha Belkin, On the linearity of large non-linear models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems, 33: 15954-15964, 2020.
Rui Liu and Alex Olshevsky. Temporal difference learning as gradient splitting. In International Conference on Machine Learning, pp. 6905-6913. PMLR, 2021.
Yu Mitrophanov. Sensitivity and convergence uniformly ergodic markov chains. Journal of Applied Probability, 1004)1000311014, 2005.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforeement learning. In International conference machine learning, pp. 1928-19299999 1937. PMLR, 2016.
Yann Ollivier. Approximate temporal difference learning is gradient descent for reversible policies. arXiv preprint arXiv: 1805.00869, 2018.
Alex Olshevsky and Bahman Gharesifard. A small gain analysis of single timescale actor critic. arXiv preprint arXiv:2203.0255) 2022.
David Silver, Julian Schritwieser,, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-339, 2017.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Haoxing Tian, Ioannis Paschalidis, and Alex Olshevsky. On the performance of temporal difference learning with neural networks. In The Eleventh International Conference on Learning Represen- tations, 2023.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates convergence. arXiv preprint arXiv:1909.00 150, 2019.
Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617-17628, 2020.
Pan Xu and Quanquan Gu. A finite-time analysis q-learning with neural network function ap- proximation. International Conference on Machine Learning, pp. 10555-10565. PMLR, 2020.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sampe analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019.
Dan Zwillinger. CRC standard mathematical tables and formulas. chapman and hall/CRC, 2018.

---

A Sketch of Proof
In this section we give a basic idea of how we prove Theorem 3.1 Briefly speaking, our idea contains two directions: First, the Critic error (captured by Aq) can be upper-bounded by the Actor error (captured by Av); Next, the Actor error can also be upper- bounded by the Critic error. Therefore, both errors are bounded and converge to 0. Based on this idea, our proof can be divided into three steps:
Step I: Analysis of Actor update.
In Appendix B, we first bound Av by AQ through Actor update. On one hand, by considering Actor update and comparing it with mean- mecan-path update (where we replace g by J). one would have
E 10++ 0,[ a VVØ
a. DQ.
E ||1 - [F <|1a VVV +a Doll
4
U2
(1-
(6,) (6.) T oo. (Ww)) Qa. Fi (w,, 0t) and Ug is defined in Lemma C.13 where DQ V In m
On the other hand, Lemma C.12 suggests Vø smooth w.r.t. 8. Hence,
Vo Vo. (0 0.) + Hv
2 ||0++1 0.11
Our claim is a combination of the above facts and some simple calculations:
Vo, Vōr+1
O0g
as aQ²llv) Av 5
+
(a 2 Hv
+ 00
AQ
2
T
2
a8
2 + (1 ) a 0²T
2H1
+ a0
+
2
We successfully bound Av by AQ.
Step 2: Analysis of Critic update.
In Appendix C, we next bound DQ by Av through Critic update. Here we perform classical way of analysis, which begins with
E
26 113] [1|ure
|1we+1
< EE
wg S(Or, w
2(10. wb ) wō. az f(O,, wt)) +E ||00. + 112)
fa
We treat the above three terms respectively. To address 41, by comparing with mean-pale -ath update:
E [|| wi مه + a 101 f(Or, 13]
=E ww w6 [1a] E [2a " (wa w7 )" f(we, 06)
+ a 22 [f(OO, w/ )
E 12a""w;, (w, w [f(Or, - f(w,, 0,]]
1
Now let us examine this equation carefully. I1,1 is the inner product between wa Wg and the mean-path update f(w,, 0z), which can be captured by gradient splitting; 41, decays as of so loose bound on [O,, w,) 1 is enough (See Lemma C.15 I is Markov sampling noise, which handled using the same procedure in Bhandari al. (018)).
To discuss more about how to address Markov sampling noise, the idea using Assumption 2.8 to show that, after Tmix steps, the distance between distribution of agent and the stationary distribution
12

---

decaying geometrically, and thus I13 also decays geometrically. However, there is still a lot of difficulties apply the same analysis in our work since TD(0) considered in Bhandari et al. (2018) while Actor-Critic methods is considered here. The difficulties is induced by the constant changing of policy in every time steps during training. We introduce an auxiliary chain (See the definitions before Lemma C.10) to further address the changing of policy problem inspired by Zou ict al. 2019); Wu et al. (2020); Chen & Zhao 2022)..
Now we move on to 12. we notice that the dominate term is E 2( - 16 1 (w+ -wg,) ) since
the remaining term E [2 b ) S(O,, wx) decays a²a (a comes from ||
. || which can be seen using Assumption 2.6 To handle the dominate term, we first view wp as a function of and use second order expansion as follows. Then the problem get solved after noticing that we already derive relationships on dc+1 0₂ in Step
18 (1) = u (1) + V W (i) (0.+1 0.) (0 V²)" (1) 0s).
To address Ia, we notice that it decays as "2 direct result of Assumption 2.6
Combine all the above result we can finally arrive at the relationship between AQ and Av. Step 3: Combine result from Step I and 2 by small-gain theorem.
Now are ready the Small Gain theorem. We fit the results from Step 1 and Step by the following form:
x S a1y + 02 y S b1 + b2 + b3yy..
Then, Small Gain theorem implies that y can be upper bounded by the following inequality:
2b + b3 20z01
y Σ
2a
Once we have a bound for y, we can easily compute a bound for x.
13

---

B Actor-Critic
In this section, we will review and clarify the AC algorithm being considered in this paper.
Recall that in Eq. we defined the set W as W = ( 1|w- - woll I ow) and the TD error óe as = r(st, 0r) + 7Q d/, wx) - Q(+,, ar; wx).
With de, now define function f and g such that
(15) where we denote by O2 (st, ar s/c a/) E S A 8 the tuple of Se, de, s/ oj and by Ó (e) S A the &e, âe pair. The way of sampling O₂ and Ô mentioned in Section 2.4
f(O,, me) = 6n vn ((8, (t. (t; we), g(Or, Wi, (r, = (8t,,
St, de; Vo In i (ārlét,,
With these notations, the AC update mentioned in Section Saation2.4ccmm 2.4 can be written as
a W1+1 Projw {w, + a f(O,. w.)} 0,+1 =0 1-7 g(O we 0z).
We find it useful to talk about the "mean path update". This just means that the functions [( and g(:)))) in Eq. (5) replaced by their means, assuming that (st, ae) is sampled from uo, while (Se, de) is sampled from (1 - 7)00,- More formally, the mean-path update functions f(;)) and
g(s)) are defined as
f(w,, 01)
Σ po ar) (Q a,, al (r(s), a.) + 7Q(5 w.) we) Q(st, ar wx)l
=VQ(w)) Do, (7. - (),) 2²,);
1 -1-1 10, (0,00,,,,00 w2]
g(w, 0₂) -
Elg(Or, wi 0,] V Vln)(00)" De. Q(w)),
(16)
where Fi = (w,, 0₂) and Eo.. Es, assume O2 follows μi, and Ô, follows (1 - 7000. To show the latter one, as we discussed in Section 2.4, we first sample T such that P(T = t) = (1 >)> We then perform T transition starting from Sp- This mean that by total probability.
+0c
+00
P(S = s) P sTT =t) P(T = =
=) (1-
2' PPSS =) =) ((s).
Thus, if the policy here is given by 0, it follows immediately that
p(O, = (s, a)) = - (0) 0e) = (1 (1-7) (1-7)00, Notice that under these notations, we have Ta, [n( wx, 0t)) B[g((,, wn, Fr). Algorithm details the algorithm considered in this paper.
Algorithm Actor-Critic
Require: Numbers of iterations T, learning rate a" " and a., projection set W. Initialize Oo. b, and ()()) such that [b,| S 1, Vr and every entry of (k(k) is chosen from ((0,) 1). Initialize the starting state-action pair 80, 4g-
for t {1, 2, ... , do Sample 5, ~ Penv (s]s:s)s: 111). a ~ T(a 3t, 0z), 5/ ~ (env (t), , df π (alss (odss(,0))) 0z).
Sample Ô by first sampling a random variable T with P(T 1) = (1 7) and second
obtaining T transitions by starting 8n and taking actions according π (aaas, 0.).
Compute 6, f(O,, we), g Ö., We, 0c), and update w4+1 and 0.+1 as
a
W = Projw (we + " f(O,, wo), 8.41 = 0 - 1
g wr, 02)
end for
14

---

C Auxiliary Lemmas
In this section, we will present all the auxiliary lemmas needed prove Theorem 3.1
C.1 Properties of the Neural Network
In this section, we will show that the neural network has Lipschitzness and smoothness properties. The following result is based on Liu et al. (2020) and has been talked about in Tian et al. (2023).
Lemma C.1. For any (s, a) E S x A, there exists sealars Lo(s, a). Ho(s, a) such that for w1 W2 E W.
[1Q a, w1) Q(s, a, w2)ll </ 8, a)llw> well [IV((s,,,w)) VQ(s, w2)ll <HoQ (8, a)llwr w2ll
we further define
=Q=
Σ
L)(s,a)3
HQ =
Σ Ho(s,,)3, 0,0
8.a
then LQ = 0(1) and Ho = δ
with respect to m.
Vm
Proof. The Lipschitzness property is proved in Tian et (0233) while the smoothness property is a direct result of Liu et al. (2020).
C.2 Properties of the Operator A
In this section, we will show several results about the operator No defined in Eq. Lemma C.2. For any function f defined on S x A,
-No(f) fr DolyPo I)f.
Proof. The proof is given by Lemma A.1 in Tian et al. (2023).
Lemma C.3. There exists Amin > and Xmin > 0 such that
No (Q(w) Qi) Amin || -
1ww--pl"" w
and
No (Q(ww)(Q Q Xmin 1Q(w)) - 266 07/? -- 7 x2 and Nuin is given by Xmin = (1 7)) x² T.3
where Amin
Proof. To show the first part,
No (Q(w)= - -2)) =(1 7)))((m) Q >l(@(w) Q lir
2(1 - ))))(()) Q:113
211 7) x2 || r
where the first line the definition ((--) while the last line uses Assumption 2.9
We can set
Amin = (1 - mmmn and we finish the proof for the first part.
The second part is an obvious result that simply combines the first part and Lemma
Lemma C.4. Suppose DQ = In (0.) Le. [Q(wz) Qū.]. The relationship between Dq and
No, (Q(w:) Q2,)) can be described as follows:
1Doll1 < c1 No, (Q(w)) - Q2.) + C
2L' and 02 (1-7)--
2L
where C1 (1-7)'X Xmi
15

---

Proof. One can easily show that
(1-7)Dg = (1x)))-(1-))éu, ( (s))s,, Qo, (s, a))]
As assumed in Assumption 2.4
V |iint(a|s, 0,]1 _ 4 Hence,
(1- _ 1 ((s.a) [[Q a, w.) - Qū, a)l]
Using the facts that = = [[X²].
(1 - 71 < T [(sa))(1-1))0) [1((s,, Q3, (=)
On the other hand,
[Q(s, a, w/) Qū, as. 21Q(ss wr)
Q2, (s, a) 262.
where we use Assumption 2.5 which tells us 16, (s, Q2 (s, S Hence,
(1 (1-7)9|1Po13= s 2 ((,,)))111)00 Q(s,a, w/) Qi, (8. a)]] + 2T 22.
Combine with Lemma C.3 and the fact that - p0 1
21'
(1 - 1->) v
No (Q(w)) Qi) +2L 2 2 Xmai
This finishes the proof.
C.3 Mean-value Theorem and Extensions
Lemma C.S. These following lemmas generalize the mean-value theorem to higher dimensional imput and output cases.
(a) Let h R + I be any differentiable functioo For any x, R, there exists À E (0,1) and
Ax + A)y such that
h(y) - hi w:).
(b) Let & aaa R. be any differentiable function. For any z, E R", there exists À E (0,1) and
2 Ar + (1 - A)y such that
E(v) = = x).
(c) Lel f : R - & be any differentiable function and TR.b be any vector. For any x, R2, there exists X 10 and 2 Ax + (1 A)y such that
(-((()) [(x)) = ( x),
where (2) is the Jacobian at
Proof. This proof given by Lemma A.2 Tian et al. (2023).
C.4 The Mixing of Two Markov Chains
In this section, argue that if two Markov chains satisfy Assumption 2.8 then the difference between their distributions could be very small. This is inspired by and follows the same logic as Chen & Zhao )002); Zou al. (2019). Before that, will first introduce the total variation norm for vectors and matrices, which can be used to measure a difference between distributions.
Denote f X R to be any real value function. We can define the total variation norm of f.
denoted by ||/|| TV, as
|| Σ [f()))
16

---

For matrix A, we can also define ||A|/r to be
||||TV sup TV
||f"A||
AV|TV.
f is some probability measure, since f(x) [0, 1]. is easy to conclude that ||/l|Tv = 1. Likewise, if A is Markov transition matrix, show that ||/||rv =1
The following lemma establishes the relationship between the total variation norm with the more familiar 1-norm and co-norm.
Lemma C.6. The following statements are true:
For any vector f. lifllrv= ||f]l-
b. For any matrix A, ||A||TV ||A||
Proof. The lemma obvious so we omit the proof here.
Based Assumption 2.8 we have the following result:
Lemma C.7. If the Markov chain has transition probability matrix A, then we have
|| S 1, Vt.
Further, if the Markov chain satisfies Assumption 2.8 then have
||A'|ITv S C8 Vt Tmix.
Proof. The first part of this lemma is obvious because is a stochastic (Markov) matrix and by Lemma C.6 || I/ is just the same as || -loo-
For the second part, by the definition of total variation
||||TV = sup I1llvv=
AlTv = 2 sup [I(e: - e² Al/Tv.
ij
where means the all-zero vector except 1 at the i'th entry. By Assumption 2.8
1 sup (ll(e--'')) - A'|lTv A')" I1(e;
||A'||TV
A'Ilvv CB" 1I Tmix-
2 i
The following theorem. which is inspired by Theorem 3.1 in Mitrophanov (005), is very important many analyses of AC that take Markov sampling into consideration (i.e.. Wu al. (2020); Chen
& Zhao 2022)). However, since our settings are slightly different, we provide our own version.
Lemma C.8. Suppose we have the following two Markov Chains which of both satisfy Assumption
2.8
A -
Po
Pb
B
p
B
B
p1
where p P stand for the probability at step under transition matrix A, B, respectively. The following inequality holds:
I1A ---
1 B loo, 1L 2 Tmix + 1.
l - pe pll1 S 11
2011 f1 (Tmix C-
T-
Proof. First, we prove that
1-1
AT
BT = (rd - pb B)² Bt
AT
(A B) B
Pt
Pb
1=0
17

---

by induction. Ift = 1, by definition we know
pf" 2 - _ = p A B" == (pt p8) B -A-(A-1))))
(A-B). B).
If the result holds for L - ki then when / = k +,
A T 1
Ph+1 =pk² A² A Pk
n² B
ph+1
(pk Pk
B T
B + Pk
A
(A - B)
k-1
(pt Po
Bh+1
Σ
p2" (A (A-B) B) Pb (A 13) B²
T
= (pú - Po B) T'
B
Σ
Po
(A B) Bk-
1=0
where the third line is because assume the result holds for the t k case. Now, take the total variation norm on both sides:
t-1
110/ - p. 11'TTV S <|666 - -60) T
Bd
+
Σ
po (A B) B)B² 1-1
TV
1=0
TV
1|p6
Po 1 rr ||B
TV
+ 1166
lrv |A- -Bllrv
B
TV
1=0
<0.'' Da1
b1l1 || + +IIA Blo
Tmix +
Σ CB
T=miix
3r
-C,3 1a16 - poll + ||A - Blloo
Tmix +
1
<0, 11p
Po || (mmix +C
)11A
Bl Blloo+
3
where the third line utilizes Lemma C.6 and Lemma
C.7
With Lemma C.8 we can derive many useful results. The following result is similar to Lemma 3 in Zou al. 2019), Lemma B.1 Wu et al. (2020), and Lemma B.4 Chen Zhao (2022). which shows that both of sdg the stationary distribution over states, and μgg the stationary distribution over state-action pairs, are Lipschitz with respect to
Lemma C.9. The following statements hold:
a.
I1me, - m'b,1l 111 I (Tmix + C.
1 1t.1.1110 -21l-
b.
llpo, - Mozll1 S (1 + Tmix + C 1 na m Lx - 82ll.
where na the number of actions. other words, na = |A/.
Proof. Recall the state transition matrix P is defined by Po(s'(8) Ea Penv (s'ls, (al(s 0) and
corresponding stationary distribution 1'6" 110 T P/. Use Lemma C.9 we know that
11m6, - 16,111 S &C3'1 - 16,111 + (Tmix + C 3 1l1,,
P% llo.
Notice that
PP% Phy 1oo ssup Σ Σ P Peny (s')s, 0,) ( ( 02)
< sup Σ
Penv (8)s1,))===10, 021l
= I. |10
0211.
18

---

where we use Assumption 2.4 in the second line. Hence,
11de. 16z |l S 134, p + (Tmix + C 1 na 10 02ll-
Taking 1o on both sides, we derive
1 l1,e, Pb,ll1 S (Tmix + C 1- n ma 0211.
This finishes the proof the first part.
Now, Eq. implies
11m0 M0z |1
Σ Inb, (s)T(als,0) 01) - (s)
[166 (s) 01) pbe, (s) 02) Ine, (s)a(als, (s)
nbo (8) 0211 + +1pb, 1b211
1 - n n 1,, -02l--
<(1 Tmix C
In order to show the following lemmas, we need to introduce the following auxiliary Markov chain:
1(0r a(0 Tanix
Peav
(6 Tunix
Poury
st T( (mix
8t Tmix
at- Tansse
8t- Tmix
Ot-Tam Tmix
8t Tmix
Peux, 8t Tmmi
(9e
Peuv
Pany
n(O: Tania
ãz Penr, 8141.
Otmiiix+ For reference, the original Markov chain around I. is
Tmiix +1
=(0e-Tmiv Og
Pany
x(0e-mmix)
Pene
=(0e- (mixtt)
84 Tmix
8t Tuix
Ot Taii
81 Tani
Pony
T(e Tmir +2)
Pony
Panx
=(O,)
Penx,
Ot-
+2
aeiss +2
St
8tt1.
For the consistency of notations, we will denote O, (ST; ar, 8y, al)) and Ö, (3t, Crs 8 d( where in this case we have s' = 87+1, 8 8--1 and a² aaass,07) d', ~ (als, 01- This kind of notations will immediately implies P(O E.) P(O E.).
The following lemma claims that the distribution difference between the Markov chains above will be very small.
Lemma C.10. The following statements are true:
a. For any possible T E {t - Tmixx - Tmix + +1, I.....t).
||P(S++1 E.) 10-(P(++1EE E < |((O, E - P(O, E-)Il..
b. For any possible T E {t Tmixx - Tmix 1.....t
P(PO, E.) - -P(Ō, E E))lli S 2n, L1 11 - Oe-Tmin
Timi |l| + IPP(S E - -P(Š, E -.]l
c. Consider P(O, E and P(Ō, -),
[P(O,, P(Ō, l11 s 2n L
E
E 110 0 Tmix
Tmix
19

---

Proof. For the first part,
[[((++1 E - P(5r+1 E -)1
Σ P(S++1=8') =s') - -P( =6)
< Σ
P(S, A, - a, = & Ar+1 = d') P(3, - =s, - Sr+1 = -', - =d)]
s,a,
=OO E - P(O E .)Il.
For the second part, conditioned on fi-Tmix and 81 Tii we denote
M P(S P(, 2+ SS s) 2+ 2 (en (811s, (a (x))
M2 =P(S, P)) 2, S,, s) Pany (5 (s a ( (a'ls' 0
M3 -P(S- P)P(O= =-|S, sa>(a| - mia Penv (5 18, a)T
())((a))) (a'la'', 01- (
M1 -P(Š, P),, 2, S,, (alss 0 P (s' s/ ()'('a)) O f
which will useful later. Using notations from the original Markov Chain,
P(S, = 8, A, a, Sr+1 = A =
/ P(S. = =, = a, Sr+1 = s Ar+1 =d'0,, = 2, 2zr
/ P(S+ = P() = s)t(a|ss 2x Penr (s' a) 22, ddr
-f { M2der.
Similarly, the auxiliary Markov Chain gives us
P(š, A, Sr+1 s', Art1 a0)
=P(š, = =))r(als, 1,,,, -uin Peny (5'1 a))x(a(())) 1o 0minn)
=/ P(ś+ a) P(O, 2- s))( O1- Timee r Pano a)) (s 0, Toir dār
= / Midey.
We now rephrase the left-hand side term we want to prove, ||P(O, E - P(O,
-)1l
Σ
=, P(S, = A, = =a, S,.1 Ar+1 a') =,, a, 0,
= -,,
Σ
Mr -Malder
8,0,8',a'
M1 -M2ldz+
+ Σ
M2
-Maldzr + Σ
/
M - -Mald
s,a.8',a a²
s,0, at
I1
12
For I1,
11
Σ
P(S, =)P(( = =27|S, = (=
8,a,8' aa
|T(('ss' 24x - =(a'is', 1'10,_n0,000 (l dz,
P(S, =s)P( = =21 = ()) 2+ Penv (s's, 1|,r - 0e- dz,
5,0,8' 't
nn Lu Σ
P(S, P)P z Sr 8) 1|= Or Fmre dzr
=n, I, 0r 0p-mmixll 11.
20

---

For 12,
1 = Σ
P(St = p) = 2r|5, = ( 2x) T (als, Or - Penv (8'18, a)
s,a,e',a'
(a'a'ss', Oe-Tnin )ez
Σ
P(S+ P(O = =27/5- = = |TTT ||
02 - P Penv (sn a))(a( Or Tuii ddzr
8,0,8' at
=n T Σ
P(S+ P Sr 8) 1| 0r Faix dz,
Ea [110 -O 0m-7miall
For 13,
1== E
P(S, =)] -P(S, 8) P(O, 2, s)T(als, 0 Penv P (s' a)
8,0,5',0
((d'Is',0e-Tma )dzy
Σ P(S+ = 5) - P(S, =
=|P((S E - P(š, -ll1.
Hence,
||P(O, - -l11 s L. [110, O + ||P(, E P(Š, el), which finishes the proof for part b.
It is easy to check that part implies the following:
||,(S, c P(š, E 1)l S [|P(O,-1 E P(Ō,-1 E -)
The above fact, along with the result from part b, tells us the following:
[[, E +) P(O, -111 S 2n, L, [10, 0 III ||P E (1)0:-1-)--((---. P(O,-1 e -111.
Repeat the incquality above over t to - Tmix we have
||P(O, E)) P(Ō, E -.)ll S 2n, TT
Σ
TR [1]0: 0 Tmix |1]-
C.5 Smoothness of the Value Function
The following two lemmas show that the state value function is actually smooth with respect to 6. The idea here inspired by Olshevsky Gharesifard (2022). The first lemma requires the following basic identity from Zwillinger (2018): for matrix Ag.
Ö (A5')
AA Ag
00; AA
00;
Lemma C.11. For two vectors u, E RD whose entries are bounded. Suppose
qe u² - P
Then, there exists constant Ly such that
|| s Leg
Similarly, if
d = TT - P%) -'o.
Then, there exists constant L2 such that
|| S L'g
21

---

Proof. The proof can be found in Olshevsky & Gharesifard (2022).
The following lemma, which goal in this section, claims that V is smooth with respect to 0. Lemma C.12. Vg, is Hy-smoothness with respect to 8
Proof. Using Theorem 2.1
we obtain the following result:
VVē VV
Σ (sxA)
Σ (s,0)ESxA
Σ (s.a)ESxA
Φ (s.
Σ
Φo, (s, (ls,a)Q2,C (s. a) in
(s.))SxAA
Σ (s.a)ExAA
6e,
E
Φe, (s) (s, (
(aa))SxA
Φ0, (..
Σ
(5)
(sa))SxA
(s.a)E8xA
do. (8,
V (
(A,))SXAA
Σ
60, (s,,)))) (s, Vint(als,62)
(s,0)ESXA
10b, (8,0) - Φer (s, a) (l 02)
(8.0)ESXA
We now show that all T1, T2, Ja be bounded by multiple of ||0, 02l1-
For J, by Assumption 2.4 know that V In x (raa s, f) is Lipschitz, which, together with do (s, a) s
I-y and (5,
implies that 1ı can be upper bounded by multiple of [10 101-0211 02
For Ig since Q3 satisfies Bellman equation. we can write Q7 using matrix multiplication. which is
Qi (1- R.
By Lemma C.11 this implies
(5 a) eTT (1-7Pa)-11
where es,a has only non-zero entry of corresponding to the pair (s,a). Hence, Q7 a) is Lipschitz with respect to 0.
For I3. by definition,
Po(S, = s|So = so) = e _.T..' P/ E2.
Thus,
Φ a) = (0 f) = c (I-PP% -1 (a)s(a)s
where e, has only non-zero entry of one corresponding to Again, by Lemma C.11 (8( Lipschitz with respect to 0.
22

---

C.6 Properties of the Actor Update
The following lemma shows that the incremental actor update is bounded. Lemma C.13. For g(Ot, we, 0z) and g(w,, Oc), we have the following properties: a. For g(Or, wr; 0z).
ll we, 0:)1 s Ug
where Ug 21' Loo L'ne L'x Tma.
b. For g(w,; 0z).
1 Ug 11 0t)11 s
where Ug 2L' + L'E + L/ 1-4.
Proof.
Recall that in Eq. 15 g(Or, wt, 0z) is defined to be
g(Or. wt, 0₂) (8,, ât w/) Vo T 0z)
To bound [1g(O,, we; 0.)ll. by Assumption 2.4 and Lemma C.1 we can do the following manipula- tions
( w/, 0.)1 |
V (n 0,) (Q(8,, â, w/) - Q(3,, â, wg.) + Q( des wig,)) $ Vo 0.) (Q(s,, â, we) - Q(,,, â,, wr.)))
+ +lVoelr(a,,5 s. (2) ar n6 )||
< T Lollu: xig. + Vo In 7 ( Sc, ( 0t, n
Lqo + ( 0c) (Q âz, w Q' (St, âz) + (s,,
220 + V ( 0c) (Q(se, à, w6 Q' (s),
+ + In n (ā. 1e, 0z) (St, (St, az)
<2L' + L' + L' Tmax
Because 16) implies that g (w, 0t) is some expectation of g( we, 0,) with a coefficient the second part of this lemma is direct result of the first part in Lemma C.13
C.7 Properties of the Critic Update
In this section, we will introduce some properties that find useful in analyzing critic update.
Notice that, as defined in Eq. 8). 8, actually depends on O and wy. Here we make this dependency explicitly and thus write 8, as 8(0,, wt). In this following lemma, we explore some properties of 8,-
Lemma C.14. For dc, we have the the following two results:
a. 6(0,, w) is Lo-Lippe Lipsschhii with respect to w,
18(O,, wn) 5(O,, w2)1 S Lsl[w] Wz
where La =1+7)L
b. 18(O,, w)l is upper bounded by Us.
18(O,, wi)l $ Us.
where Us 2(1 + Loo + (1 + 7) + - maxx
23

---

Proof. Using (8.
16(O,, w1) b(0,, w2)
= aI(((),; + 7 wi) Q (1, (1), - (r(se, at) +7Q(5), (y w2) - Q8t, W2))
h (Q(s),,,, w1) Q(5), di w2)) (Q(s), a,, w1) - Q(s,, w2))
<(1 + 7) L - w2ll.
where the last line uses Lemma C.1 On the other hand,
18(O,, w)) = (r(8) (0( (6. we) - (88,, 0e; w)l
= (((s)) ar) +7 (Q(s) dy w) ((( - (Q(0)) as, w) Q7(() an))
+7 (Q7(5), 04)
af) (Qb(s), ai) - (0((). + 7Q0(s, a.) 1T(s ac)
1 1+7
Smmax (1+ +1+7)) w6
(1 + 7)
Tmax
1
2
22 + +Q) + 7)
Tiaxx
where the second equation uses Assumption 2.1
Lemma
C.1 Eq. and 5q.
With the above properties of 6,, now we can further consider f. f. and F defined in Lemma C.17 Lemma C.15. For f(O,, w) defined in Eq. 15). we have the following two results:
a. [(O,,w) w) T.p-iipshitzz with respect to w, Ilf(O,, w1) - f(Or, w2)ll S L5llw] walb
where L, = -1 13 + HqUs-
b. [1, will can be upper bounded by Uy.
[|/(O,, w)ll s SUS,
where U, LqUs-
Proof. By definition.
f(O,, w) = ((O,,,)VQ(ss..))) a4. w).
Hence,
f(O,, w1) f(Or, w2)
=8(0;, w1) (Q( at, w1) 5(O,, w2 VQ(se, at, W2)
=8(0,, w1) V as, w1) 8(0,, w2) VQ (st, ae W1)
+5(O,, W22 VQ S1, ae w1) 5(O,, w2 VQ a,, W2)
= =15(Or, 50O,, w2)] VQ(st: az, wh) 5(O,, w22 (VQ(st, ar, w1) VQ 0z, wz))
For I1, by Lemma C.14 and Lemma C.1 we perform the following manipulations:
[[[((,,, wi) 50,, w2)] (*( at, wi )ll < L LoLlll - w2ll
=(1 + 1 w2ll-
For 12, by Lemma C.14 and Lemma C.I we derive |8(0,, w2) (VQ ae w1) VQ(a,, ar w2)) S UgHHo 12l1
Combining I and In we prove the first part of this lemma.
For the second part, by Lemma C.14 and Lemma C.I
[0, w)ll = 118(O,, w) VQ(ss, will $ UsLQ.
24

---

Lemma C.16. For f(w, 0) defined in 16. we have the following results:
(w, 0)ll can be upper bounded by Uy-
[1, 0)ll & UUg,
where U, = LQUs-
b. f(w, 8) is Ly-Lipschitz with respect to w,
[If(wi. f(w2, 0)11 S Lilkur w2/1
where I.g = -1 (1+)) + HqUs.
f(w,0) 0) is Li-Lischhitz with respect 0.
Ilf( 01) - f(w, 02)1 - L -B2ll.
where L = LQUs(2 + Tmix + C I- (-g))noo..
Proof. Because of Eq. 16.. the first and second part of this lemma is direct result of Lemma C.15 15 For the third part,
|| [[w, 01) - f(w,0((w))
Σ po (s,a) a) 8.0
s'aa
Σ (s, a) Σ
() (2) w)
s.a
s'.a'
[mo, (s,
- ( f(0, w)
8,0 a'.a'
Penv (s'ls, a) po (s. 01) (0.(5,a))<d115 02) -1] (1)(0,
8,0,8'
<Ug
(ono [n0, (s. 01) no, (1.
S,0.8'
where the last line is by Lemma C.15 Further notice that
|no, (sa')) (=.(s,a)
s $Imo, (s)) (0)) no, (ss
+ [1
02)1
=Mt (8, (8)0) 01) - =Ta'ls' 02)
T(a'ls 02) [ie, (s, () (s.
25

---

Hence,
Σ
(u) (s. (a'))' .2))
8,0,6' aa'
Σ
Penv (1)l
<<aals', , 82)l
8,
Σ
nom (s, a) - no, (8, (8,
a,a,"',a'
Lm 02ll
Σ
Peno (s' (s,
5,a,8',a" aa'
Σ
Penv (s' (s) 02) noo (s, - (s,
5,a,s,
-1g T. 10
0211 I1,0: - 100
(2 Tmix + C 1
mm T 110 0211
where the last line is by Lemma
C.9
This implies
1
[[f(w, 01) f(w, 02)1 S2 Tmix +
1 na 02ll
1
=LQUs(2+ + Tmix + C 1- maba1100 02l1.
Lemma C.17. Denote F(O, w. 0) = (w- (w- [f(O,w) w) - f(w. 8)]. The following results hold: F(O, O) is LFg -Lppschitz with respect 0. |F(O, w. 02) F(O, w, 02) - LFo110: 021l.
where
LF. (U, Tew I.
b. F(O, w. is LF. Lipschitz with respect to F(O,, wi, 0) F(O, w2 0)l S I L. well:
where
Lr 40 wo + 2Ug.
c. Conditioned on 0 0 and 8 +mm
E F(Or,, Wn-Tmix Or Or-n F(O,, Wt We-inixx Or - O S6 St
B[10; G 18--mixlll 10 Tamee 81 1mme++]]
Tanix
d. Conditioned 0 Tiix and St St 10-Tmi
F(O,, We-mmix Tmix: Or 0 ) 100c 9m-rmttt1] ]
< 2 CBtuin
Proof. First, we observe that
FFO, w. 02) - F(O,w,0,) 02)1
w,
(w 3" [S(O,w) w) f(w, 01)] (w ú S [S(O, w) - flw, 02)
I(w wū,) )" [f(O, w) f(w, 01) (w w ) [f(O, w) flw, 01)]
+ |w - 06,1 1r [f(0, w) - [(w,0:] (w - w6, )" [f(O, w) f(w,
(wā - w6 TT f(0. w) f(w, 01) + (w --,, " f(w, 02) f(w, 01)
=
26

---

For I1, we have
[10g - 1 [f(O, -
f(w, 0:)] f( <2U, 1.0 0211.
which is by Lemma and and Assumption 2.6
For 12, we have
(w w [f(w,02) f(w, 0:)] s 20..Li1011 0211;
which is by Lemma C.16 Combining the above two facts we end the proof of the first part. For the second part,
IF(O, w1 0) F(O, w2, 0)1
(w] 6²)²² [f(O, w1) f((1, 0)] (w2 20)²² [f(O, w2) f(wz, 0)]
S (w) x²²)² [f(O, wi) - -[(w1, 0)] - (wi w [ʃ(O, W22 - [[ww, 0)]
+ +w1 -bg)² [f(O, w2) - fw2, 8)] (w2 " [f(O, w2) f(w2, 0)]
= =l(w| - x [(](O, w1) f(O, w2)) (f(w), (0:0))--wpwp f(w2, 0w)]
+ (w] w2) )d [8(0, w2) - f(w2, 0)]
<40wL w22| + 20, [w] w2l1,
where the last line is by Lemma C.15 and Lemma C.16 For the third part, conditioned on 8 and 8t +,
E
F(Ot.
Tmir G2 Fmmr)) F(O wi Fmix Ot [mmm)))]
E
(Wi Tmii
Tiii
We: miix
F [S(Os, Wit-nii) Fmin))
[(W Tmin Oc Omimmia)]
(Wi-Tmi Tmix
Wp mmix
)T f(OO, We W
f(Wi Or Tmix) 0mxx)
E (Wi-Tmin Tmix
w6
f(O,, WT 1olt-Taii -mmse))
f(Or, Wt
200w
E
[[((0s WT 1 Fmn))
f(Or,, Wemee
220 2owWU11IP(O)) -.) P(O, -)11
E [110; 02--miz
T=ix Tmix
where we use Lemma C.15 and Lemma C.10
For the fourth part, we first denote O+ (st a s aat) such that (st, ue, miix
Penv (8'18, a) and a+ ~ (aa18', 1', Or Or-Tmin) Under this definition, we have
E [F(O+, WT Tmixx O 100= St Smix = 0.
By Assumption 2.8
we have
[[[(Se E .10 81 St-Tmix-1) - Mo Tixx 1/1 S CTTaixx -1
Hence, conditioned on Or-Tmin and 8t Tmiitt +1
E
F(O,, wi Taix Or Tunix)
F(Or. Wi Umixi Or a - F(O+, WWW- Tmin O2- mman)
E (we - úB Tanix
7 f(Or,, f(01,we-Tmm) w(-Tm)) - f(0 W W3-Tmix
220 22,,,,1IP((0 -POt( E.)
27

---

where the last line is because of Lemma C.15
However,
||P(O, E - P(O+ E -)111
Σ
P(S: s, A. = S,111 A1t1 aa) PP(S = s, A a. a, =s',At+1 a')l
Σ
PP( = s) O2 Fmmr min (5'1s a) (T (e-
P(t s)T(aass, P Peny (s a))(a) mmm
P| E.) - P(S -)1122
SCB
Hence, conditioned on 0 and 8t Tiii Twi
F(Or, Ti- Tmx)) < 20 CBBmmix
)
The following lemma, which reveals a useful property for critic update, is inspired by Olshevsky & Gharesifard (2022).
Lemma C.18. For critic updale, we have the following two results:
E (0 26 )"(we
1b + a
2 H2 ) 1|100 wp. a f(w,, 0.)
<
V2a L (lllgg 0c]l
V2(1 - 7)2
and
V2a 8² H V2 - 7)2
E [106 a [f(Or. w.) - Flur, 800] 22a
1-7
Proof. If we use æii) to denote the i'th entry of vector I,
(06, - (w: - w6 + a f(w,, 0,)) = Σ (00 (i) ((ri
1. (w) w6, + +a f(w,,,,))
We can view vig as function of 0. Using a second order expansion,
عه (i) = م i
(0 0²) + 2 (0++1 - V O₂).
If we take expectation conditioned on Fi,
[ (0++ - 0.) v² (i)(0(+1 0:)l
wg. 2b (0)FF
=E Vwgg. T(0, (0, 0c+1) -E
02
= 0 Vuig (i) g(w,, 0.) 2(1 7)2
F [o(Or, wi, 0, (1),(O, wx, 0.)
This leads to
E (1) (i) 200 (b)
+ 04
<2a (Vi), gw,,, 0.))
2(1 7) E
g( wr, wr, 0,7 v (i)g(ó,, we, F.
0 H (
<2a L., (1) 2. +
2(1 7)
28

---

where in the last line we use Assumption 2.6 and Lemma C.13 care about,
Now we go back to what we really
E (wo w6 (wr uh + a th f(w,, 0.)
E
(10g, (i) / (i)) (wre- wg. th f(w,, (1))
Σ
W6 (i) Wの (0) [uw W6 + a "h f(we, (z))
Σ
E
w (i) S (i)]Fi)
Σ [[wer - Wp
a
add Hm
Σ 20021 (n) (g 0,)113
|| wāg + aa I(wes 0,)l
2(1 7)1
a²2 U2
V2a Tno Inglgg 0c) + 22(1 - 7) .1|uce wg a ((wr, 0:]l:
where the third line is because the second term is constant conditioned on Fe. For the second part, notice that we already have the following result
<2a 82 I. (1)9 0,)112 + 91 H (1)
u (1) 2
E 1. (1)
2(1 - 74
2a L L (1)
+ a² (1)
71
2(1 - 71
where we simply bound [g 0c)l by Ug (this result is from Lemma C.13). On the other hand, by
Lemma C.15 and Lemma C.16. a rough bound for f(Or, wt) - f(w,, 0e) would be simply
[[ w.) f(we, 0b)l s 2U,-
Now we go back to what we really care about,
E
w a [f(Oe, wx) - f(w,, 0.) FF
a
E
(10g) (i) - ud... (i)) (J(O,, wx) - O()) (i)[Fr
=a 00
EE
100 (i) - F E [(f(Or, we) - Flur, 00)) [i)
<aa m
Σ E
20g (i) ش6 (F)
[(f(Or, w.) f(u,, 0.) (i)
22 (i)222
+ 99 a'*HH (.)
Sa ~
Σ
E
(s(Or,w)) - F(w,, 0.)) (1)
71-
2(1 71
V2a 1-7
a0² H U2 V2 7
U2
where the third line is because the terms are independent when conditioned on F,. The second part of this lemma is proved after we take expectation on both sides.
29

---

D Actor Update Analysis
Lemma D.1.
E Vo - Vor+1
(2
Ho²Hv)
Av 5
tc1
(a0 HH + 08
2 A
T
+ C2 a00
Hv Ha
+
ag
6² + (1 7) )
2/1
a U?
U?
2
Proof. Actor update says the following:
a
0c+1 0. 1- 1- g(0 02)
a
-0. a g(wr, 02) a g(r, 01) 1 1- g(Or, We, 0z).
By the definition of (we, 0,) in Eq. 16).
O(w,, 0.) = v In (0.) 3 To. Q(wz))
= VV (0.) T Do. [ Q(wx) - Q%.1
=V T + ( ( Po. [Q(wr) - Qa.1+
where we use the fact in Eq.(7
For simplicity, denote DQ V In I (0,) ) to. [Q(w;) - Q2.1 So far we have the following result:
a"
0++1 0, 0 VV a DQ + a g((,, 0.) T- 90, we, 0z).
On one hand, if we take expectation (conditioned on Fi) both sides, we get
E [0c+1
F, = a VVo. -a" DQ.
where we use the fact in Eq.
16 that - ( w/, 0.) = -g(we; On the other hand,
a
[10c+1 - 0,11 = ||a VV + D2l2 +
|la g(we, 01)
g(Ou, we FF
=110 VV a Dell2 + (1 7)2
4
U22
U2
1 1 ((Or, wT, 0/) = =g(we: fe). Using Lemma C.12
where we keep using E
VoL., S VØ. VV2 (0c+1 0₂) + Hy
||0.11 0.112.
2
Taking expectation (conditioned on F₂) on both sides and we obtain
E [Ve., [F/] S VV, + VVG. E [0+1 - 0c1F,) + Hy
E
[110+11 - 0.,1
2
Plug in the facts about 0c+1 O2, we know
E Ve VV
Vg. a VIVV.. 1 - a VV, DQ + Hv 1|0 0 VVV." +a D2l
2Hv
U2?
(1 7)3
We can use the facts that 2ab < a² + b² and (a + b)2 < 2a² + 26 to obtain
<Va - v' + a
2 | 1| + a
E Voeu [F
2 ||D
+ 02 Hy VV || + 82 Hv 1011= + (1 7)2
211y
02
U2
=Vo + (ao"Hy 44)
| + (ao Hy + ag
|D2l1 +
2Hy
02
U2
2
2
(1 7)2
SVG + (00 2Hy
00)
a0)
|[VV + (1 (1- 7)² R²?
2Hy U2 U2
2
+ (00 2 Hy + a6
2
(Q(w)) - Q2, + o28
30

---

where the last inequality we uses the fact from Lemma
C.4
We can rewrite it as
(2 ag av
a6
||VV,
VVo
E Vo_ Fr
+
?]- a U?
2Hv
2
2 Hy + ag) (oNoo(Q(uu)) - -Q%)) c22e
+ a4
Taking expectation on both sides and telescoping sum:
(2
0
an Hv
T
[IVV
V V Vor+
+ 02 av aa0² Hy +
a8
e² + 2HV
a 02 U2 U2
T
2
(1 - 7)2
+
(ao²Hv Hv +
0g 1
E
(Q(we)) -Q(()))(aa))
2 T
we use notations from Eq. 13. the above fact can be rewritten as
Vor+1
(00- a
060
Av S
01
+c1
aa (a Hv + a6
AQ
2
T
2
aa0210
Hv
+
ag
6²+ (1 ) U2
2/1
U?
2
31

---

E
Critic Update Analysis under the Markov Sampling Case
Lemma E.1. In the Markov sampling case,
20 m
a
Lw
1
2a
V20 Lallm//r
-2a²2 -2a (2)00
(Amnn 20w
V2
Amin
||w1
11
a Luw - 20002 1i Av
+
T
V2
V2 Tan /
+ + (1 20
92 U²
1 Amiu
2x
V
V2(1 7)2
Vw,,10 92 Hu
+ Cw,1 + Cw.2
V2" Lu V20 Lw
C2
V2(1 7)
+ Ug
(VeaLLu
a² H2u
g
+ 20
02 1 C26
(1 7) a U?
4L2
1-7 V2(1 7)2
where, for simplicity, we denote
C 16a + (L + 4a 41a 4 + a U².
and
Cw,2 = 20x a miix (I.p, + 40 (Tmix - Tm
mii I ow +4a o C
Proof. Recall the critic update
W++1 Projw (wi + az J(Or, we))
which implies
|1z+1 - W6 112 Projw {wr + a" f(O,, wi)] - 16 11?
|e t f(Or, wt) w ,11
| wā. + w - n + a² f(Oz,, w))l
< <1100 w + a f(O w1
+ +2 w )r (we w/ + a " f(Or, wx)) + 1100% -w 112
We take expectation on both sides.
E [|wt11 v6. [12]
< E [llure - wā. + a fe",fO,, w
11
(17)
E 2(20 w )
w6, + a f(O,, wi)) +E |1:0 wh 112)
l2
dg
To analyze J,, we derive
EE wu w7, + a f(Or, w2
EE ||w, uلद. 1|2 2a 12 (w:+ - w YT f(O,, we) + " w1)]1
E
[llwe ا [13] + [2a (w: - w )z [(we,, 0c)]
(18)
1111
E
w2 [f(OOr w. 2
+ E [2a " (w, wG, ya [f(O,, w.) Flw,, 0,]]]
h,2
11.3
32

---

To analyze 11,, we perform the following of manipulations:
2a 2a"(w; (wr 1 f(wr, 0.)
(wr -2a"(w:
-2a"
x/g,) (u)))) Do, (TPo. ()( Qo.)
=2a (wr v.g.) - VQQ())) Do, (7Po. ()( - Qo. + Qo. - -Q,)
- =2a" " (Q((+)) - -0,)² + (wi - wo,) (QQ(w))) (Q(()) - 0%,77 Do. - 1))Q(w))) (Q6))
+ 2a (w: -wb)) -00)) (Q(())) ( Do. (yPo. 1)( Qb,)
2a No. No. (Q(w)) Q%,) 2a (w, n6. (VQ(w)) (Q(Umia)) Do.
(TPo. - Q%,,
+ 22a (w, w6.1 ) VVQ(uu wx) " Da, Py, 1)(2%. -(
2a NN,,NN, (Q(w)) Q%,) 2a " (1 + Lo w 1l + 2a th + (1+))) 00
< - 2a No,
No. (w:) Q7,)+ 16a " 16a
+ () + 4a" (1 + LQEw
where the second line is by the definition in Eq. 19..16...0 the sixth line is by Lemma C.2 and Lemma
C.5 and the eighth line is by Lemma C.I Here, À E [0, 1] is some scalar and Wmid Xwa + (1
X So arrive at the final bound for I1,1:
2a t0 (we - ) S( 0.) S No, (Q(w;) - Q3,,)
+ 16a " (1 + 7) Lo Hoo + 4a 4a + Loco
To analyze 1,,2, conclude
a 22 [1 w1)1 S U²
To analyze 1,3, for simplicity, we denote F(O,, w. 0) = (w - =0z² [f(O,, w) f(w. 0)] We have
F(O,, wh, w,, 0,) =F(O,, we 0.) F(O,,, Wer O (mix))
+ F(Ot, Wi, O2 (l-ia
F(Or, We Tmin Oz Tmin Ot-Tmin)
Ja
+ F(Or, Wi W O1 7mix)
F F(Or, - Oc- - Tinie
Ja
+ F(Or, Wi Teaie O, Tenize
For J1, have
[F(O,, wc. wr, F(O,, We, O2 0mx SLFF1105 0m-7mix]
a T Lyn Ug
For Jz, we have
IF(Or, Wh, mmia) F(Or, Wt Taiin O < <Tr F 1l ||we We- Tmin
<a Tmixx Te Ow-
For Jz, by Lemma C.17 we have
F(Or, Wi- Oz Tmn) F(Or, Wt- Wi- P Fmm - St 3m-x+1
<Aow Σ Tenie
E Ell00 - Oz- 00- 100-mmxx 3m-1m
Aa Aalo U u Tmixe (miix 1)U
1-7
33

---

which means
E
F(O+: W Tiirs Fmix) F(Or, Wy Tmix b2 tmn |]
4o o sn Tmixx 1)Ug.
For J4, by Lemma C.17 we have
E F(O wi We- Tmin Or Tain 1e- Tmsttt)
S 20
which means
E F( T bs 0
s 20 220
Hence, for 113,, we have
[[ wr, 0.)] a Tmix (LFg + 4ow (Tmix 1)) Un
+a t Tmix Fm 20 U y C.
which implies
E [20" (w, - wib.²² - [f(Os, w.)) f( 0b]]] 2a Tmix (LF, + uo NN - 1)) Ug
1 1-7
+ 2x Tmix Lnix ow + 4a o
Hence, for I1.
[| - ūg. + a f(Os, ((O,,ww)]13] < -2a No. (Q(w,) - Qu.) + [1|wr - u. 11
16a (1 + 7) LQ HQo + +4 (1 + LI
a U² + 20 a Tmix (Lr, + 4o U ma Lix (Tmix 13)
22 miix ow + 4a ow JuU
"
No, - Q +E [||ur 1 [1 + Cw.1 Cw.2.
(19)
where, for simplicity, denote
C = 16a Lo 4a "I + L a U2
and
Cm.2 nd th a Tmix (LFo + Low (Tmix Ug
+2a 22 Tmix L ow U
1 1-7
To analyze 12, we derive
E (uăā. (b.4.)" )a (w; W6. + a add f(O,, wz))]
(1b7. w )((e (wi wo. + " f(we, 8.)) +E (108, w a [f(Oe, w.) F(w,, 0c)
12,1
12.2
To analyze 12,1 first, by lemma C.18. we already know
(106 v8... J(we wgg + +a ((w,, o.))
8² 022H, U2
<
V2a0 Lu (l 0,)1l
||w: Vs + ax f(we, 0.)
V2(1 - 7)2
12.12
12111
For 12,1,2, rough bound would be
W/ wG. + + f(w,, 0.)12 ||w w. 112
2a (w, 2aa
02) + +a f(w,,
12 0.11.
34

---

Notice that this term is very similar to what we have in (8) The two difference are (a) all the f Eq. are replaced by and (b) expectation removed. In this case, 4,3 will be and a similar bound for /1,1 and 2,2 will also hold. This implies the following result:
|w, ú2g + f(wr,, - -2a" (Q(u)) Q²,) + 1|ur u6g11 11? 16a 16aa"(1+ Lo + 4a (1 LQeo + +a U²
- 2a
No. No. (Q(we) Q6,) + Cw.1,
Amin
(20)
where the last line uses Lemma C.3
For 12,1, recall that
(gw 0b) - VV + +lll
s V + (Q( - Q2,) c262.
Hence, we have the following bound for 12,1,1:
0² H U2
22a0 To (ww 0,11
12 - 7)2
<V2a Lu VVo. + 22a Lu V (Q(w) Qb) + c262 + a²² H²²H1 Huu
V2(1 7))
Hence, we have the following result:
E (wg. - (w: we. + a. f(we, 0.))
62 Hnu
20 Tew || + V2a² Ii CaNo, (NNo, - -b.)) + cze2 +
/2(1 - 7)2
n
(Q(w)( Q7,) Cw,1 +Cw,1
Amin
1 _a Lue
No. (Q(w.) Qū,,) + 1 _ Lw
Lw VV
2a
2
V2
Amin
( 2000 No,(Q(w.)) - -Q%,) + Cw.
+ /200 Ino
(c(No:(Q(urr) (Q(w)) Qū,) + c262
Amiin
a 02 H U2
(1t 20 No.(Q(ur) Qū,) + Cmn,1
+
12(1 1 7)2 V
Amin
a Lw VV
22
1
( 20
V2"
a
Inv
Amiin
2a="
V2a0 T2antwg/
C1
Amnin
No. No. (Q(we) Q6,)
02 Hu.U²
+
V2a0 Trug TTy/csCuun CcC + eze?
1
2
Amin 20 (Qo))( - Q2,)
Amin
V2(1 2
62 H2
Cm,, + 2220 Lio C2mmm C2
+
+
V2"
V2(1 7)
35

---

After taking expectation on both sides, we know
E
u6:11 ) Wy. + th f(we, 81))
VVV. 1
2 a
1
a I
In
1 -2a""
22 Tugaa
(1)
20 ))
I (Q(ur) - -Qt.)
2
Amin
Aumin
02 H
+
V2a Trug C]Cw, + Cze?
/
1 Amin
200
20 V R [No, (Q(w))) -b.)
V2 7)2
Amin
Cw Cw,,a H2
+ V2 a Cw,1 + 22a0 Lo co +
V2(1 7)
which is the bound for 12,1-
For 12,, by Lemma C.18 we have
(VeaLLoUg 1-7
a² H²
E (105) u a [f(Or, wi) - f(w,, 80] s Ua
V2(1 - 7)2
This ends the bound for Iz, which, after combining the bound for I2,1 and I2,2, will be
E
( - ū )T(ws wp. + a=d f(Or, wx))
VV ["]
a
2
1 (11- 2000) ))
+
1
a
T
Two
1
20
+ 22 Trng/e a
)
TE [No, (Q(1e)) Q
V2
Amin
Ammin
0² H
+
V2a buy Tlu/csCuutt + CgE2
1
2
1 -2200 20
(N (
Amin
V2(1 7)2
Amin
H2u
122aLLUi
0² Hnu
+
a Cw,, V2a0 Lio c220m,
Us
V2
V2(1 7))
1-7
V2(1 7))
To analyze 13, have
E |100 16 11 <L. [110+11 - 0r112
Recall that
"(w 01) a"
8.11 - 0, = vv'v - -a Da + a
g(O,, wc)
which implies
4
E [110 11, VVla'VV,, + a
D2ll2 a
(1 (I- a U3
<2a²² (1VV + NN, (Q(w:) ) -Q7,) + +oze) + (1 7) 02 U3
4
where we use the fact that E [[ 0.) --,,(0,, wi 8.) =0. Hence,
E |10 - 11915, < 2a 1 [1VV
+a =
(Q(,) Q% cze²) ) +(1))=+1__111 ) 7/2
4L2
02
U2
After taking expectation on both side, we will arrive the bound for Is. which is
10. - w [1]] < 22 L2 E || + No. (Q(s)) Q%,} + +cze))
41.2
82 2²
U2
=1 7)
36

---

Now, go back to Eq. 17
and we obtain
E
||ae+1 10++1 12
<B
[1/21= - 26 [1 +
1
a
E VV |2] Lu + 2200212
V/2
+
V2
1
a Lw
Amin
1
2a"))
<222 +V2aLLog Lug/
91
1 (---1 2a"h!
Amin
Liac -2a"
E [No, (Q(w))-
a H
/20 P Lug
/ /ciCma + C2E2
1 -0
V B [Na, (Q(()) -Qt.)
+
-2
Amin
V2(1 7)
Amin
VC unu
+ Cw,1 + Cwpt Lu + V2a Iw cc2
V2
V2(1 - 7)
(2aaLLu
a²H V2 - 7)2
4L2 82 U?. 11- UZ
+ Us
+ -2 12 2
1-7
9.
Now, we can do telescoping sum for i T:
T
2a n
1
Liu
1
2a"h)
V2a Lu Lmp/a
20
22 L2
No. (Q.
V2
Amin
Amin
E
||w1
113]
T Σ E
a Lu + 22 1%00
[|
+
T
V2
1=1
a 02 H
+
(v20 buy (a + cze?
1 Ammin
2xx
1
2a
-Qa)))
-
22 7)2
Amin
VCw,ia0² Hnu 2un
" a + V2a Lu /o2Cw,1e2
+ Cw,1 Ow,2 +
V2
V2(1 - 7)2
+ Uy
L2
2² H²? g v2(1 - >)2
+ 82 La oze 2+
(1 7)2 a ?U
4L2
1-7
g'
which, if we adopt notations from Eq. (3), can be rewritten as
20 m
a
Tow
20
V200 Tw Twn
20 - 0000
.DQ
V2
Aquin
Amia
[||w|] - 1601 1
1
a
Lww + 20 L. Av
+
T
V2
02 Un
+
V2a0 Lu /ZalLuylaae
(/C,,1 + c22e
(Nmin - -2a
+
V2(1 7)2 V Amia
20
VDQ
Lua C2 + v Cv,1a 92 U2 9
+ +w,,1 + Cw.2 + 1
Lw + V2a Lu
V2
V2(1 7)2
U1
(VealIuUg 1-7
a² Hnu
2a 02 1
1g,cze
412
a
82 U2
V2(1 - 7)2
(1 7)2 g'
37

---

Critic Update Analysis under the i..d. Sampling Case
Lemma F.1. In the i.i.d. sampling case,
(1
2a
a
Lu
)ath)
/2a" Lu
20
-2002 Loas
Ao
V2
Ammin
Amin
|| - Wgg
11
+
a
"ww 22 22²²22y Li
Av
T
V2
0² H
(1 20
+
V200
C/Cu, + 0262
20
VAQ
Amni
V2 7)2
Amin
Lw + V2a Lu L co + v 11 62 Huu?
1
+ +ww1 +
V2
v2(1 - 7)2
412
+ 02 1 c2 71- Ug.
02 UZ.
Proof. The i.i.d. assumption implies that f(Or; wz) is replaced by f(we, 0z). This will bring change in both the analysis for I and lz.
First, will figure how the iid. sampling effect I1. Now we know that I in 18 That means, for 1 in (7)
18 is 0.
[w/ 16 + a f(O,, w < 2a No, - Qú, + I|w, 20, 113
+ 16x (1 + 7) T.Q Hoo + 40x + 7) 7) L.ea + U
2a No. (Q(w)) - Q7,)) + +||u; -07 1|2 Cw.11
where C is defined the same as before:
C 16a (1+ + 4a 4aa LQ + a 2²
Next, after removal of 12,2 term (72,2 will just be 0 if replace by Π) derive the bound for 12, which is
E (
06011 )T wb + a f(Or, (()))) wx))]
L. VVo. [2]
a
2
V2"
1
Inv
Inv
1 Amiin
)ax))
22a0 Twng
C1
Amnin
1
20
E No. (Q(w)) 2b.}]
02 Hn.U²
1
20 V [No. - (Q(w))-
+
V2a0 Trug// Tuy/esCoo CiC + aze?
2
Amin
V2(1 )
Amin
022 O2. U2
Cm,, + 2220 Lio C2mmm +
+
V2"
V2(1 7)
38

---

Based on the new bounds for I1 and 12, the critic update now gives the following:
20
L
1
20x
12a 12a
(+----
Xmmn
1
20w
20
1
-Q
V2
Amin
|||w1 16
11
a Low - 2002220 Lio Av
+
T
V2
92 U
V20 Low CrCw, coge
1
20
20
VDQ
Ammin
V2 7)2
Amin
V VC 62 Hw
+ Cw.1+ a Cw + 220 Lw Lwwesswwee
V2
v2(1 7)2
+ 02 La Laore? +
(1 (1- u
4L2
39

---

G Small Gain Theorem and Small Gain Analysis
G.1
Small Gain Theorem
Now we introduce the small gain theorem.
Lemma G.1. Suppose a and y satisfy the following two inequalities:
x Sayy + 02;
y Zbb + b2 + b
where all coefficients are non-negative. Then, y can be upper bounded by the following inequality:
2b + bg + 20²01
y
21
Proof. Proof of this lemma can be found in Olshevsky & Gharesifard (2022)
G.2 Small Gain Analysis under ii.d. Sampling
Now recall the result from Actor analysis is
Oke 2
a02 Ho²
Av
S
0:
Vort1
+
[00 Hv
2H + 06
AQ
T
2
+ ag
+ H2
a8
2 + (1 7)2 a 02 U? U?.
2Hv
2
and the one from Critic analysis is
2a
V2
a
L.
(Xmin
[1_
2a
V2a Lue Luy/ci c1
Amin
20 - -2a L
DQ
|||21 - wgg [13]
+
a
Lw
2002112 L2
Av
T
V22
02 H U2
+
V208 Lum CiCw, + 0262
- 20
20 vvQ
Amiin
V2(1 7)2
Ammin
v 1a Huu??
+ C=,1+
1
Ln + V2a Lu V
V2" /2
v2(1 7)2
02 122 c2
4L2
82 Ug.
(1 71
What we really care about the relationship between T, e and m. So from now on, we will use O()) and Ō(-) (Ō(-) hides the potential logarithm factor of m) notations and only consider these variables. First, observe the following dependency on T, m and c:
LQ =0(1,
HQ =ō 1
Vm )
L8 =0(),,
Us =(() 0(1),
L =Ō 1 / (c+1) O(1),
U, =0(e) O(1),
U, =0(e) O(1),
L, =0 ((log T + 1)(e + 1)),
LF =0 ((log T + 1)(e + 1)),
LF. =ō (() 1
+1 (c + 1)
40

---

If we choose a" = a = 1
and given that all other coefficients are independent with T and m,
vT
conclude
C = -0 0
1
[11]
= -
-
+0
+0
VT vml
VT
We can set
Av
=
AQ.
(a0² 2 Hv + ce
2 0(1)
a1
ae 2
ag² Hv
Vo Vor+zl
+ C2 (000 Hv + 2) 2² + 2Hv a u2U2
(1-7)2 =0 (i
+ +0()),
42
ag Hv
1 J Lw + 02 L2
b1
(1),
2a
a Lw (
-2a") V200 Lww/ //a (Juiia (1i -2a
22 1
v2
Amnu
3| wi 07, 113]
+ Ow.1+ + 12 a + 120
coC
T
b2
20 m
Iww
1 20²)
V20 Tw e1 Xmmn 20
22 1.2 c1
v2
Amin
y VC "2 HoU?
22 L2 L20 o2 +
"= a
412
222
V2(111)²
+
2a
1 / Tno
1 Amin
/200 T /er 20x)
(x 200")
22 1.2
O(E)) +0
V2a" L V /aCC + oge?
[1- 2a
a² H.n
1 - -a
Amin
v2(1-))²
Amin
6g
V2 L Luw (xim -2aw)
-2200 Lug/es
(xitnm 2a²h -2a L3
2a
=0 (
+ +
+0
VT
vm
Now we can apply Small Gain Theorem, where we conclude
y U50
1 0(e)
+Ô +Ô
VT
mm
and
a1y + 02
1 VT
O(e)
+0
(1))
1 m
G.3
Small Gain Analysis the Markov Sampling Case
Now recall the result from Actor analysis
010
a0 (H² Av 5
0
Vir
1r11
+
(00" Hv + a0
AQ
2
T
2
c
(ao2Hy
HV +
ag
2 2+
2Hv
7) a U21 U2
41

---

and the one from Critic analysis is
2a t
a
Luw
1 Amin
20x"
/2a V2alLm/e Empaa
20 (1
1 Amin
-2 22
DQ
V2
||w0
112]
a Luw - 20002 Av
+
T
92 U²
+
V20 Low @.CC,11
I + +o2e ( (vmina (1 20w
+
V2(1 7)2 V Amiu
1
20
VDQ
Vw,1a0 92 H
+ Cw,1 + Cw,2 v + V20
02
V2(1 - 7)
+ Ug
VVan Ln Huu g
+ 2a
02
c2c
+
(1 71 a U2
41.
1-7
V2(1 7)
If we choose a = a² = vp
and given that all other coefficients are independent with c, T and m,
we conclude
Cm,1 = δ
+0
+0
(
1 2
+0
=0(7)
v
VT
and
Cw, = 0 ((++ ((++1) (log 77)2) (10
(
+ + ((e+1)
1
log I
+1
T
vm
T
We can set
x =AV,
y Q
C1 (a. 2 Hy + 2#
01
= 0(1),
ag 2 Hy
p Vort
+ C2 (as Hy + 22) 2 =2
2Hy a 222
U2
02
(1-7]3
0
1
+
au
ax 2 Hy
VT
2
Ja Lm + 20 L2
0(1),
20
Ja0 Las
1
11 2a
/2a0 Lug/ (2 (IL 2a
22022220 L2
V2
Amii
E(||e1 - 16, 119]
v Viuia Hw
+ Cw,1 + Cw.2 + 1 I + V2al Lal /c20w,112
T'
v2(1-7)2
b2 =
V2 a Lio (11
-2a V2a /2aLLuu/ Lu
(1) -200) -2a 2 L3 Amin
Amin
Ug
V2
a² um
2a 12 22, + (1-7)2 U
1L3
1-7
/2(1-9)3
+
V2 J2 Iuw
(22-- 2 -2xm)
-V2aluu bug/
-2a0
( -2cu)
82 12
Xmii
Amain
2
1
=0
mix
+Ō + +((e) +Ō
mml)
11-2000 + a²2 H.
V2a L
a.w, + +
Amiin 20
Amin
v2(1->)²
6g
n0
L
Lw
Ami (1 -2a
V2a0 Lug/es /s
e (1in 2a - 02 L2,c
V2
+0()+ +0 (
=0
/m
42

---

Now we can apply Small Gain Theorem, where we conclude
==0 0
(log 2) (1ogT)²)
+ +(()) +
1
VT
vm
and
02 0 [log (1ogT)9) T)
O(e)) +0 0
1
a1y
VT
vm
43


Reviews:
[{"review_id": "cGuNrM5NGj", "reviewer": "Reviewer_akFw", "summary": "This paper establishes the convergence of single-timescale actor-critic with neural networks representing the value and policy with > 1 layer, strengthening over prior results in the linear setting and two-scale approaches. \n", "questions": "1. I would have loved to see a little more discussion on future directions. What are the next steps to relax? Or is it to more tightly characterize the convergence?\n\n2. How does this play with value learning when the TD objective does not correspond to a gradient descent (e.g. in off-policy learning)? ", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I will preface my review by saying that I have little background on convergence of actor-critic methods or in analyses of deep networks -- and thus not much to say about the significance of the technical advances. \n\nI found that despite this lack of background, this paper was an absolute pleasure to read. The paper is very well-written, and the authors do a great job of motivating the problem and the technical approach. Each assumption is well-motivated, and the two tools -- nonlinear gradient splitting and the nonlinear small gain theorem -- are also described in a way that is easy to understand. I wish that more theory papers were written like this!\n\nWhile I briefly looked through the proofs in the appendix, I unfortunately do not have the expertise to gauge correctness.\n", "weaknesses": "While the mechanism of the proof was very well explained in the paper, I would have liked to see some more discussion about the significance of the result and it's implications for future work. Why is this result interesting? What does it enable? Perhaps it would be useful to spend a little more time discussing the applicability of the proposed tools and theory beyond their application to AC -- what other places may these technical tools be useful? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I found that despite this lack of background, this paper was an absolute pleasure to read. The paper is very well-written, and the authors do a great job of motivating the problem and the technical approach. Each assumption is well-motivated, and the two tools -- nonlinear gradient splitting and the nonlinear small gain theorem -- are also described in a way that is easy to understand. I wish that more theory papers were written like this!\n\nThank you very much for your encouraging comments! We have done our best to make the core result of our work as accessible as possible.\n\n> I would have loved to see a little more discussion on future directions. What are the next steps to relax? Or is it to more tightly characterize the convergence?\n\nThanks for your question! We'll discuss the next steps at a level which is more speculative than what is in our submission. Note that the discussion here overlaps with our responses to some of the other reviewers. \n\n*Our ultimate goal is to create something that would actually be useful for applied RL*. While there will always be gaps between theory and practice,  we would like to have a situation where, if a particular method diverges in practice, one could always default to theoretically supported step-sizes/architectures/updates that would guarantee convergence. \n\nWe are currently quite far from this but we believe this paper is a worthwhile step forward. Our next step is to relax some of the ingredients that went into obtaining this result that do not match what practitioners do. These ingredients include:\n\n* Small fixed step-size of $O(1/\\sqrt{T})$. More generalized step-size schedules would be nice.\n* No replay buffer. In practice, replay buffers are pretty much universal in 2023. \n* Smooth activations: so Leaky ReLU, GeLU, ELU are all fine for our result, but ReLU is not. \n* No PPO-style truncation in updates. \n* Fixed projection radius. We would conjecture that while we cannot get rid of it without causing divergence or adding more assumptions, we can set the projection radius to be $\\sim \\sqrt{m}$. \n\n>  How does this play with value learning when the TD objective does not correspond to a gradient descent (e.g. in off-policy learning)?\n\nThat is a good question. We have been thinking about this for a while without making much progress; below, we summarize our current state of thinking. \n\nIn the off-policy case, we have an additional multiplicative factor that comes from the difference between behavior and policy  distribution. Ignoring the differences between gradient and gradient splittings, off-policy TD is then analogous to the update: \n\n$$x_{t+1} = x_t - \\alpha_t D \\nabla f(x_t),$$ \n\nwhere $D$ is diagonal matrix with entries which are strictly positive. Analyzing this as written above not a problem -- but unfortunately if you take the above equation and replace gradient with gradient splitting, then we have no idea how to analyze it. \n\nThis is a good juncture to emphasize that it is *not* true that we can take any arguments from convex optimization and make them work for TD by arguing that one is simply replacing gradients with gradient-splittings (a number of other reviewers were wondering about this point). Indeed, there are properties that gradients have that splittings do not, and they can make a big difference. It may still be possible to use the toolkit we use in this paper to analyze off-policy TD; however, doing so will not be straightforward and will likely require some new ideas. "}, {"review_id": "obhrax20jp", "reviewer": "Reviewer_X8JD", "summary": "The paper is a well written and clear result demonstrating the convergence of the actor critic algorithm. To my knowledge, this is the first example of global convergence of the actor critic algorithm using neural network parametrization. It is a good extension of the actor critic sample complexity analysis given in works such as Xu et.al (2020) from a linear function approximation to a neural network approximation for the value function.", "questions": "Can the existing result be extended to an infinite state space? That is not immediately clear from the analysis done here.\n\nAs a consequence of the finite state space, what is the advantage of assuming a neural network approximation here and not a tabular form of the value function?\n", "limitations": "Since this is a theoretical work which analyses existing algorithms negative societal impact is limited.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Extends well established analysis of single timescale actor critic for a linear function approximation to one with a neural network approximation for the value function. \n\nProvides better convergence bounds than current analyses of actor critic using neural network approximations, while not having the restriction in the depth of the networks that existing results have.\n\nThe paper is well written, concise and easy to follow.\n", "weaknesses": "Since a finite state space is being assumed here, the comparison to existing results  such as Wang et. al (2019) and Cayci et. al. (2022) does not seem to be valid. Both these works assume an infinite state space. Since the constant c1 is a multiple of the cardinality of the state space, an infinite state space does not seem to work for the analysis given here. \n\nThe upper bound on the norm of the Hessian of the neural network in Liu et.al (2020) is stated as a probabilistic bound. This bound is stated as deterministic in the lemma B.1.\n\nAssumption 2.7 while being obvious for a linear function approximation, has not been assumed in the works cited where a neural network approximation has been used such as Cai. et. al (2019) and Xu and Gu (2020). Thus the validity of the assumption has not been established for the setup being analyzed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Since a finite state space is being assumed here, the comparison to existing results such as Wang et. al (2019) and Cayci et. al. (2022) does not seem to be valid. Both these works assume an infinite state space. Since the constant c1 is a multiple of the cardinality of the state space, an infinite state space does not seem to work for the analysis given here. \n\nThank you for bringing this up! The answer is **yes, our analysis works for infinite state spaces with minor modifications**. \n\nWe did not view this as an important difference between our work and the previous literature at submission time, which is why the proof as written only works for finite state spaces -- as the reviewer correctly points out. But this is quite easy to fix. Indeed, let us consider Lemma B.4 where the bounds for $c_1$ (and actually also $c_2$ ) brought up by the reviewer can be made independent of the number of states. We sketch this analysis below. \n\nWe will use the notation in the paper. Our starting point is \n\n$$ (1-\\gamma) D_Q = E_{(s,a) \\sim (1-\\gamma) \\phi_{\\theta_t}} [ \\ln \\pi(a|s, \\theta_t) (Q(s,a,w_t)-Q_{\\theta_t}^*(s,a)) ].$$ \n\nUsing Assumption 2.4, we have \n\n$$(1-\\gamma) ||D_Q|| \\le L_{\\pi}' E_{(s,a) \\sim (1-\\gamma) \\phi_{\\theta_t}} [ |Q(s,a,w_t)-Q_{\\theta_t}^*(s,a)| ].$$ \n\nNext, using $(\\mathbb{E}[X])^2 \\le \\mathbb{E}[X^2]$, we conclude that \n\n$$(1-\\gamma)^2 ||D_Q||^2 \\le {L_{\\pi}'}^2 E_{(s,a) \\sim (1-\\gamma) \\phi_{\\theta_t}} [ |Q(s,a,w_t)-Q_{\\theta_t}^*(s,a)|^2 ].$$ \n\nBut also, $$|Q(s,a,w_t)-Q_{\\theta_t}^*(s,a)|^2 \\le 2 |Q(s,a,w_t) - \\hat{Q}_{\\theta_t}^*(s,a)|^2 + 2 \\epsilon^2,$$ \n\nwhere we used Assumption 2.5. Hence, \n\n$$(1-\\gamma)^2 ||D_Q||^2 \\le 2 {L_{\\pi}'}^2 (E_{(s,a) \\sim (1-\\gamma) \\phi_{\\theta_t}} [ |Q(s,a,w_t) - \\hat{Q}_{\\theta_t}^*(s,a)|^2] +\\epsilon^2).$$\n\nCombining this with Lemma B.3 and the fact that $(1-\\gamma)\\phi_{\\theta_t}(s,a) \\le 1$, we obtain \n\n$$(1-\\gamma)^2 ||D_Q||^2 \\le \\frac{2 {L_{\\pi}'}^2}{\\lambda_{\\rm min}'} N_{\\theta} ( Q(w) - \\hat{Q}^*_{\\theta} ) + 2 {L_{\\pi}'}^2 \\epsilon^2. $$\n\nWe can thus set $c_1 = \\frac{2 {L_{\\pi}'}^2}{(1-\\gamma)\\lambda_{\\rm min}'}, c_2 = \\frac{2 {L_{\\pi}'}^2}{1-\\gamma},$ and this concludes the argument. \n\nMaking the result work for infinite state spaces will require making a number of other modifications (e.g., various sums become integrals), but one can simply follow the argument we have laid out. \n\n> The upper bound on the norm of the Hessian of the neural network in Liu et.al (2020) is stated as a probabilistic bound. This bound is stated as deterministic in the lemma B.1.\n\nCorrect: we assume Assumption 2.3 holds; in Liu et.al (2020), this fact was shown to hold with high probability over the random initialization (see Lemma F.4 in Liu et.al (2020)). In the final version of our paper, we will emphasize this difference to avoid confusion. Note that this was done solely to improve presentation: otherwise, one would need to add \"with high probability over the initialization\" to our main result. \n\n> Assumption 2.7 while being obvious for a linear function approximation, has not been assumed in the works cited where a neural network approximation has been used such as Cai. et. al (2019) and Xu and Gu (2020). Thus the validity of the assumption has not been established for the setup being analyzed.\n\nOur response on this point is three-fold. *First*, and most importantly, **please see our global response which contains simulations supporting this assumption**. It is, of course, not possible to test an assumption that begins with \"for every $w$...\", but what we can do is sample a lot of different $w$'s and see whether the resulting distribution has support bounded away from zero (and it does). \n\n*Second*: actually, our assumption is *almost identical* to a similar assumption in Xu and Gu (2020), namely Assumption 5.3 in their work. Let us spell this out. \n\nIndeed, it is trivial from the definitions that their assumptions implies ours when the function approximation is linear. In the general case of nonlinear approximation, we point out that in Definition 5.1 of Xu and Gu (2020), a linearization around the initial point is performed. If we do the same, i.e., if we approximate \n\n$$Q(w) \\approx Q(w_0) + \\nabla Q(w_0) (w-w_0),$$\n\nusing the first term of the Taylor expansion, then our Assumption 2.7 becomes \n\n$$(w-\\hat{w})^T {\\nabla Q(w_0)}^T \\nabla Q(w_0) (w-\\hat{w}) \\ge \\lambda' (w-\\hat{w})^T (w-\\hat{w}).$$ \n\nNow it is clear that our Assumption 2.7 follows if the smallest eigenvalue of ${\\nabla Q(w_0)}^T \\nabla Q(w_0)$ is bounded away from $0$, which is implied by Assumption 5.3 of Xu and Gu (2020). \n\n*Third*: to see that some assumption along these lines is necessary consider the case of linear approximation. In that case, existing analyses assume that the features are non-redundant, i.e., the feature matrix $\\Phi$ (stacking up the feature vectors $\\phi(s,a)^T$) has smallest singular value which is bounded away from zero.\n\nNow how can such an assumption be generalized to the nonlinear case? One way to guarantee that a matrix $\\Phi$ has smallest singular value bounded away from zero is\n\n $$ || \\Phi w_1 - \\Phi w_2 || \\geq \\sigma || w_1 - w_2 ||,$$ \n\nfor some $\\sigma > 0$ and all $w_1, w_2$. But now this admits a straightforward generalization to the non-linear case: \n\n$$ || V(w_1) - V(w_2) || \\geq \\sigma  ||w_1 - w_2||,$$ which is slightly stronger than what we assume.\n\n**In summary,** we have made four main points in this rebuttal:\n\n* The various constants we bound can easily be made independent of $n$. \n\n* We have added experimental evidence supporting Assumption 2.7. \n\n* That assumption is almost identical to what was assumed in earlier work. Specifically, if we linearize in the same way as Xu and Gu (2020) do, then Assumption 2.7 is not as strong as what is assumed in that paper. \n\n* Assumption 2.7 is a natural way to generalize the standard non-redundancy of features assumption to the nonlinear case. \n\n"}, {"review_id": "V4Up5FM4Mq", "reviewer": "Reviewer_GAW7", "summary": "This paper presents a convergence analysis of Actor Critic method with multiply layer networks. ", "questions": "I would ask the authors to clarify the following questions, which I believe can significantly improve the paper if addressed:\n1. What are the differences for AC methods with single hidden layer networks and multiple layer networks, especially for proving the convergence? In the current version, these differences are not well explained. To improve the clarity and strengthen the paper's contribution, the authors should provide a more detailed comparison of these two methods, highlighting the specific challenges that arise when proving the convergence for each architecture. This will enable readers to better understand the significance of the proposed approach in tackling the convergence problem and its relevance in the context of existing research.\n2. The proof of convergence presented in the paper is challenging to follow, and its integration within the main context is inadequate. To improve the overall readability and accessibility of the paper, I recommend including a sketch of the proof in the main body, i.e., Section 3. This will allow readers, especially those unfamiliar with previous work on the convergence analysis of AC methods, to grasp the high-level idea behind the proof. Providing a concise outline of the proof in the main paper will enhance the paper's accessibility and make it more appealing to a broader audience.\n3. Expanding on the suggestions mentioned in point 1, once the key differences between AC methods with single hidden layer networks and multiple layer networks are clearly stated, it would greatly benefit the readers if the authors could elaborate on the key techniques utilized to address these differences and overcome the associated challenges (Section 4 in the current version is far from satisfactory). By doing so, the authors can provide valuable insights into the novelty and contributions of the proposed approach. Understanding the techniques employed to tackle specific obstacles will enable the readers to evaluate the significance of the paper more effectively and appreciate its potential impact on the field.\n\n\n-------------------\nAfter rebuttal, as the authors address most of my concerns, I would increase my score to 6. I would still suggest the authors to carefully revise the paper to make it more readable if accepted. ", "limitations": "No. The limitation is not discussed. As there are many assumptions, I suggest that the authors should discuss whether these assumptions can be relaxed, as well as the cases where these assumptions cannot hold. ", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The convergence analysis of AC with multi-layer networks is important, as AC methods with neural networks plays the core role of the success of DRL. ", "weaknesses": "The paper is difficult to follow and the writing can be significantly improved. (More in Questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for bringing these points up! Our responses are below. \n\n> What are the differences for AC methods with single hidden layer networks and multiple layer networks, especially for proving the convergence? In the current version, these differences are not well explained. To improve the clarity and strengthen the paper's contribution, the authors should provide a more detailed comparison of these two methods, highlighting the specific challenges that arise when proving the convergence for each architecture. This will enable readers to better understand the significance of the proposed approach in tackling the convergence problem and its relevance in the context of existing research.\n\nIt is accurate to say that previous work followed variations on the following strategy in the single-layer case:\n\n**(1)** Linearize around the initial point. \n\n**(2)** Argue that the linearization has singular values bounded away from zero. \n\n**(3)** As a consequence of (2), the loss decreases quickly in a neighborhood of the initial point. \n\n**(4)** Because of (3), the function never moves far away from the initial point (as loss decreases to zero, so does the size of the gradient). \n\nWe say above \"some variation\" since every paper did something slightly different. For example, sometimes instead of (1), previous works added a small projection radius (size $O(1/\\sqrt{m})$, where $m$ is the network width). \n\nTo answer the reviewer's question: we believe the argument generally fails for higher depth in point (2), which is much harder to make for a multi-layer network. But for us this is somewhat beside the point, because **we do not want to make this argument work for the larger depth case** as it will also imply the neural network stays close to initialization -- which we do not want! \n\nIndeed, a natural counter-argument regarding the value of following (1)-(4) above is that the approximation scheme is essentially linear (since the closeness of the nonlinear map and  the first-order expansion around the initial point is what allows the whole proof strategy to go through). \n\n> To improve the overall readability and accessibility of the paper, I recommend including a sketch of the proof in the main body...\n\n> ...once the key differences between AC methods with single hidden layer networks and multiple layer networks are clearly stated, it would greatly benefit the readers if the authors could elaborate on the key techniques utilized to address these differences and overcome the associated challenges...\n\nWe are happy to add this to the paper. Here is what this kind of sketch/discussion will look like. First, a sketch at the highest level of generality:\n\n**(1)** The nonlinearity of the network can be bounded in terms of the width $m$: larger width networks are \"less nonlinear.\" \n\nFormally, here we rely on the previous results of Liu et al (2020) that the norm of the Hessian of a neural network in a constant ball around a random initial point is $O(1/\\sqrt{m})$ with high probability. A linear function has zero gradient, so this bound may be informally viewed as capping \"how nonlinear\" the network is. \n\n**(2)** Analysis of linear AC is based on an iteration which says that the actor's reward $V(\\theta_t)$ decreases at each step by something proportional to $||\\nabla V(\\theta_t)||^2$, with some error terms coming from the critic approximation. We can now add an additional error term to this recursion that comes from the nonlinearity. That error term has size $O(1/\\sqrt{m})$ from item (1). \n\n**(3)** Finally, we need to argue that this error term is carried linearly into the final bound on how big $||\\nabla V(\\theta_t)||$ is at a random iterate. \n\nThe difficulty here is that both the actor and the critic are using each other's updates, so adding an error term is far from trivial -- one must somehow argue the error-prone iterations are not mutually destabilizing. \n\nNow having made this sketch, we next point out the actual equations this translates to. A quick look at our paper will show that the analysis is quite technical and requires a lot of careful estimates -- but let us forget about this and just point at the two key equations. The **first** is \n\\begin{align}\n    \\left(\\frac{\\alpha_{\\theta}}{2} - {\\alpha_{\\theta}}^2 H_V \\right) \\Delta_V\n    \\le & \\frac{E \\left[ V_{\\theta_1}^* - V_{\\theta_{T+1}}^* \\right]}{T} + c_1 \\left( {\\alpha_{\\theta}}^2 H_V + \\frac{\\alpha_{\\theta}}{2} \\right) \\Delta_Q + c_2 \\left( {\\alpha_{\\theta}}^2 H_V + \\frac{\\alpha_{\\theta}}{2} \\right) \\epsilon^2 + \\frac{2 H_V}{(1-\\gamma)^2} {\\alpha^\\theta}^2 U_g^2.\n\\end{align} Precise definitions can be found in the paper itself, but informally:\n\n* $\\Delta_V$ is the average gradient squared of the actor over $T$ iterations.\n* $\\Delta_Q$ is the average approximation error of the critic over $T$ iterations. \n* $H_V$ is a measure of the nonlinearity of the neural approximation. \n\nWhat his equation says is: *if* the critic is accurate on average, and the network is not too nonlinear, then the actor has been close to a critical point. \n\nThe **second** key equation is too long for OpenReview and pushes us above the character limit but it is Lemma D.1 in the paper. This makes the reverse argument: it argues that if the network is not too nonlinear and the actor gradients have, on average, been close to zero, then the critic average approximation error is small. Both of these key equations are conditional in character (they assert that if one thing is small, then another thing is small), but can be made unconditional using the \"small gain\" argument described in Section 4.2. \n\n> As there are many assumptions, I suggest that the authors should discuss whether these assumptions can be relaxed, as well as the cases where these assumptions cannot hold.\n\nWith the exception of Assumption 2.7, our assumptions are standard and have been used in previous works. For a discussion of Assumption 2.7, please see our global response. "}, {"review_id": "Ve6MD5NNsP", "reviewer": "Reviewer_ADfc", "summary": "This is an RL theory paper with an improved convergence bound for actor-critic methods ", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To be frank, I'm not a theory person at all and I have no idea why this paper is assigned to me. I cannot really judge the theoretical contribution of this work. By assuming all the statements are correct, I personally (from a practitioner's perspective) feel that a convergence theorem that can apply to multi-layer networks looks great. ", "weaknesses": "Out of my expertise. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's frankness! But we would like to to disagree: we think applied RL people are qualified to review RL-theory papers. \n\nIndeed, we do not want to be in a state where only RL-theory people are reviewing each other's papers: that is likely to lead to the community becoming insular and progressively more decoupled from practice. As far as this submission goes, somewhat remarkably it has 8 reviews; it could certainly benefit from feedback by someone who would consider it from a practical lens. \n\nLet us try to get the conversation started by explaining our overall agenda: our goal is to create something that would be useful for applied RL people. \n\nWhile there will always be gaps between theory and practice,  we would like to have a situation where, if a method diverges in practice, practitioners can always default to theoretically supported step-sizes/architectures/updates that would guarantee convergence. At the very least, the more practical methods could be tried again after the theoretically convergent method has been running for a while with the justification that a \"good start\" may be required for the more practical methods. \n\nWe are currently quite far from this but we believe this paper is a worthwhile step towards this goal: we obtain the first results on neural actor critic that do not assume a single-hidden-layer. Nevertheless, let us point out some simplifications we have made that were necessary for us to get this result that do not match what practitioners do:\n\n* Small fixed step-size of $O(1/\\sqrt{T})$. More generalized step-size schedules would be nice.\n* No replay buffer. In practice, replay buffers are pretty much universal in 2023. \n* Smooth activations: so Leaky ReLU, GeLU, ELU are all fine for our result, but ReLU is not. \n* No PPO-style truncation in updates. \n* Fixed projection radius. We would conjecture that while we cannot get rid of it without causing divergence or adding more assumptions, we can set the projection radius to be $\\sim \\sqrt{m}$.  \n\n\nAll of these are limitations of the current result. We are working on remedying these to bring the result closer to what occurs in practice and make the vision outlined above a reality. However, resolving any of these issues will likely require new ideas far beyond what is in the current paper (e.g., the single point in ReLU with no differentiability creates major problems that are not known to be surmountable -- at least, not without extra assumptions). \n\nWhile we do not expect an applied RL person to evaluate all the details of the proofs, it is certainly possible to evaluate both the ultimate value of the project of developing RL methods which come with convergence guarantees, as well as the place of this paper within that agenda. "}, {"review_id": "louzb31GqK", "reviewer": "Reviewer_FwfS", "summary": "This is a theoretical paper which studies actor-critic reinforcement learning algorithms in which both the actor and the critic are represented using deep neural networks with more than one hidden layer. The previous research addressed linear representations and neural networks with only one hidden layer. This paper derives convergence rates for both the actor and the critic for neural networks with more than one hidden layer.\n", "questions": "See previous box.", "limitations": "One thing to note is that I don't prove convergence rates in my work, and I did not go through the proofs to verify their correctness.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Writing is of very high quality, with well-considered notation, and sensible flow.\n\n- The problem statement is clear, and it is supported by required references.\n\n- The problem is important, and the paper furthers our understanding of the behaviour of RL with function approximation using deep neural networks.\n", "weaknesses": "- A few small typos can be found in the paper. E.g., in line 28 \"was consider in\". A few articles are also missing in various places.\n\n- In the paper, the authors emphasize the need to stay close to the initial conditions of the critic (e.g. in Sec. 2.4). This makes sense from the regularisation point of view in general, but in RL, this may mean that the optimial policy may not be found if the algorithm is forced to say close to the initial conditions. Perhaps the motivation and the consequences of staying close to the initial conditions could be clarified.\n\n- Consider Eq. (9), and assume that $\\epsilon$ is small, but higher than 0. Even if $\\epsilon$ is very small, the best action may change when a lover Q-value is allowed, i.e., the best action determined by $\\theta_t$ may be different from the best action according to $Q(s,a)$. Do the smoothness assumptions made through the paper help to cope with the change of the best action in this case? Note that small $\\epsilon$ may not be sufficient to make the result significant since the policy itself may be affected even when $\\epsilon$ is tiny.\n\nIn line 201, the authors say that $C$, $\\beta$, and $\\mu_\\min$ do not depend on $\\theta$. But, I am not sure if this is true for $\\mu_\\min$ since the stationary distribution $\\mu_\\theta$ depends on the policy. When we have deterministic actions in the MDP, some states may even have probability of zero in the stationary distribution of the ensuing Markov chain.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and questions! We'll clarify these points in the final version of the paper. Meanwhile, our point-by-point replies are below. \n\n> In the paper, the authors emphasize the need to stay close to the initial conditions of the critic (e.g. in Sec. 2.4). This makes sense from the regularisation point of view in general, but in RL, this may mean that the optimal policy may not be found if the algorithm is forced to say close to the initial conditions. Perhaps the motivation and the consequences of staying close to the initial conditions could be clarified.\n\nNote that even in TD(0) with linear function approximation, a much simpler problem than the one considered here, one needs a projection to stabilize the algorithm in theory in the presence of Markovian sampling, see e.g., the analysis in Bhandari et.al (2018). The size of the projection radius is one of the improvements of this paper, as in many other NTK-style papers, the radius is even required to be decaying with $1/\\sqrt{m}$, e.g., Cayci et.al (2022). So one of the contributions of this work is that it is much better on this point: the algorithm is required to stay a lot less close to the initial condition.\n\nIt is natural to wonder, as the reviewer does, whether this projection radius leads to issues in the sense of the critic failing to approximate the true Q-values. In our simulations, we have found that this does happen, but is not as common as perfect approximation by the critic. Please see our global response for two examples where the critic is able to perfectly approximate the true value function under our assumption, and one case where it does not. We are not aware of any theoretical results analyzing the distinctions between these cases. \n\n\n> Consider Eq. (9), and assume that is small, but higher than 0. Even if is very small, the best action may change when a lover Q-value is allowed, i.e., the best action determined by may be different from the best action according to . Do the smoothness assumptions made through the paper help to cope with the change of the best action in this case? Note that small may not be sufficient to make the result significant since the policy itself may be affected even when is tiny.\n\nThe smoothness assumptions are part of it, but note that as the reviewer points out, any $\\epsilon > 0$, no matter how small, may induce a \"discontinuity,\" in the sense that even at convergence it will cause different actions to be taken as compared to if the true $Q$-values are known. This is a particular obstacle to the analysis and smoothness assumption do not solve it by themselves. There are various bounds throughout our paper that are additive in $\\epsilon$ (e.g., Lemma B.4), and this happens exactly for the reason the reviewer outlines -- there is an additive source of error that does not go to zero even as everything converges to the optimal values. Speaking informally,  what one needs to show is that all these additive errors do not get \"amplified\" by the AC dynamics. \n\n\n> In line 201, the authors say that $C$, $\\beta$, and $\\mu_{\\rm min}$ do not depend on $\\theta$. But, I am not sure if this is true for  since the stationary distribution  depends...\n\nNote that here $\\mu_{\\rm min}$ is a uniform lower-bound for the stationary distribution independent of $\\theta$. So for this analysis, we have  assumed that $\\mu_{\\rm min}$ is bounded away from zero. In other words, we assumed the stationary distribution is bounded away from zero independently of $\\theta$. Unfortunately, if this statement is not true, then one cannot prove anything about actor-critic methods. It is easy to see that if $\\mu_{\\theta}$ corresponding to some set of states is zero, then we may never converge to the optimal policy, even in the tabular case for both actor and critic (because we might never visit those states and so will never see the rewards associated with the actions in them). "}, {"review_id": "YNQc1QxC8N", "reviewer": "Reviewer_7mQ7", "summary": "The authors prove a bound on the approximation error of sample-based actor critic learning on a more general and realistic setting, namely allowing for a NN approximator of any depth. This is a very non-trivial result and an interesting contribution to the literature.\n\nNote: I have not gone through the full proof in the appendix and thus cannot fully comment on the validity of the main contributions.", "questions": "Your final bound does not appear to be affected by the depth of the NN approximator, but clearly depth does improve approximation error. Does a tighter bound exist that takes into account depth or would depth mostly be captured in the \\epsilon error term?\n\nOn line 135, you refer to \\sigma_w, but I don't see that variable defined. What is that referring to?\n\nIn Assumption 2.6, what is the gradient of w with respect to?\n\nSmall notes:\nI would recommend having all equation statements be numbered so it's easier for readers to refer to them.\n\nI find the notation on the equation in line 161 a bit confusing, namely that Q refers to both a function that takes in weights and outputs a Q-function and the Q-function itself.\n\n", "limitations": "I don't think there are significant potential negative societal impacts of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is very well written and the ideas are clearly communicated. I especially appreciate the tables and figures to aid in explaining the approach and how it fits into the literature.\n\nThe main theorem is a very interesting theoretical result.", "weaknesses": "There are a few parts of the paper where the presentation could be improved a bit, but for the most part I thought the paper was very clearly written.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper is very well written and the ideas are clearly communicated. I especially appreciate the tables and figures to aid in explaining the approach and how it fits into the literature.\n\n> The main theorem is a very interesting theoretical result.\n\nThank you for the encouraging review! \n\n\n> Your final bound does not appear to be affected by the depth of the NN approximator, but clearly depth does improve approximation error. Does a tighter bound exist that takes into account depth or would depth mostly be captured in the $\\epsilon$ error term?\n\nIndeed, that is correct: the dependence on depth is implicitly captured in the $\\epsilon$ term. \n\n> On line 135, you refer to $\\sigma_w$, but I don't see that variable defined. What is that referring to?\n\nWe'll make this clearer in the final version of the paper; line 135 here is actually supposed to be the definition of $\\sigma_w$. That is, we can choose the projection radius $\\sigma_w$ arbitrarily. This projection radius will appear as a constant in the various $O(\\cdot)$ notations throughout the paper. \n\n> In Assumption 2.6, what is the gradient of w with respect to?\n\nWe'll make this clearer in the final version of the paper as well: in Assumption 2.6, we view $\\hat{\\omega}_{\\theta}^*$ as a function of $\\theta$, with respect to which we take the gradient. \n\n> I find the notation on the equation in line 161 a bit confusing, namely that Q refers to both a function that takes in weights and outputs a Q-function and the Q-function itself.\n\nThanks for pointing out our typo there! Indeed it should be $Q_{\\theta}^*$ instead of $Q_{\\theta}$. Throughout the paper, we use $\\theta$ to denote the parameters of the policy, while $Q_{\\theta}^*$ denote the true value functions corresponding to policy $\\pi(\\theta)$."}, {"review_id": "4ghS0B40fk", "reviewer": "Reviewer_oPsP", "summary": "The paper studies non-asymptotic convergence rate of actor-critic algorithm. The critic network is parameterized by multi-layer neural network whose activation function is assumed to be smooth, excluding ReLU operator. The actor is assumed to be general smooth non-linear function.\n\n The convergence rate for mean squared error of gradient of value function and $\\mathcal{N}$ norm of Q--unction is proved to be $\\tilde{O}(1/T^{1/2})$ with additional error term $\\epsilon^2+O(1/m^{1/2})$.", "questions": "Regarding Assumption 2.6, is such assumption on the critic approximation standard in the literature of finite time analysis of actor critic? If so, please provide some comments and citations in the paper.\n\nIn line 384, please give more detail why the state action pair is sampled from $(1-\\gamma)\\phi_{\\theta_t}$.\n\nIn line 572, what is the motivation to introduce $ w_{\\mathrm{mid}} $? I guess it allows the decomposition of the term but what meaning does each term have?\n", "limitations": "The strength that the authors argue that the analysis does not require initialization point being close to the solution, and the projection radius not dependent on the width of neural network, seems to be direct result from Tian et al., rather than being a new discovery. Moreover, the general framework of actor-critic analysis is adopted from Olshevsky et al. It is not clearly explained what the difficulties and challenges of the analysis combininng Tian et al. and Olshevsky et al.. Hence, I am currently leaning towards rejection.\n\n\nHaoxing Tian, Ioannis Paschalidis, and Alex Olshevsky. On the performance of temporal difference learning with neural networks. In The Eleventh International Conference on Learning Represen- tations, 2023.\n\nAlex Olshevsky and Bahman Gharesifard. A small gain analysis of single timescale actor critic. arXiv preprint arXiv:2203.02591, 2022.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The algorithm uses single-step size and constant projection radius, which is closer to practice than two-time scale step size and projection radius being dependent on the neural network width $m$. Moreover, the depth of the neural network can be chosen arbitrary. Overall, the authors managed to derive the convergence rate for Neural AC combining the works of Tian et al., and Olshevsky et al..", "weaknesses": "The main weakness is that the work seems to simply combine the works of Tian et al. and Olshevsky et al. It is difficult to clarify what are the challenges and contributions of combining Tian and Olshevsky et al..\n\nMoreover, the limitation of this work is that it considers smooth activation excluding the ReLU activation function.\n\nIn key ideas ( Section 4 ), is the small gain theorem different from that of Olshevsky et al.? If it is different, there should be comment on what's different, and if not, please add citation for it. Moreover, I believe the title of section 4 is not appropriate since both ideas are from Liu et al. and Olshevsky et al.. It would be better to explain the difficulties in combining the existing works.\n\n- Miscelleneous\n\nThere is grammar error in line 28, \"was consider->was considered\"\n\nIn line 99, please add citation for the policy gradient theorem.\n\nIn line 304, pleas add reference for the textbook.\n\nIn line 597, please write as a complete sentence.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The main weakness...\n \nOur contribution is not a simple combination of two papers. Even superficially, note that our paper deals with actor-critic, yet our Lyapunov function is not the same as Olshevsky et al. (which relied on square norm). Further, Olshevsky et al. was for the i.i.d. sampling case, not the more difficult Markovian sampling case considered here. Tian et al. considered Markov sampling, but Markov sampling in AC is much difficult than that in TD(0) since in AC the policy changes from step to step.\n\nLet us outline more substantively the difficulty overcome by this paper. The use of Markov sampling, and the use of multi-layer neural networks, introduces additional errors into the analysis. Whereas Olshevsky et al. was based on the analogy between actor-critic and bilevel optimization, here we have an update that can be analogized to bilevel optimization **with errors**. Dealing with this is not straightforward. In the context of AC, the main difficulty is showing the errors do not compound, but are instead carried over into the final bound. To see the difficulty, imagine the critic makes an update with errors. Those errors are then used by the actor to move in the direction of a non-optimal policy. The actor then makes a step in the direction of the new non-optimal policy, with an additional error. It is easy to see how this effort could result in the algorithm's divergence. \n\nMoreover, the situation here is fundamentally different than what we have Tian et al. which was inspired by gradient descent tools. In that case, it is simpler to show that errors do not compound since gradient descent does not have the same feedback loop as above. \n\nIt is well-understood in the optimization literature that such an error analysis can be highly nontrivial, and there are quite a few papers whose main contribution is an analysis of a standard optimization method with errors. Note that in our case, we show that the source of error that comes from the neural network enters *linearly* into the final objective ($1/\\sqrt{m}$, which is a bound on \"how nonlinear\" the neural network can get, where m is the width), as opposed to the *quadratic* way that epsilon enters into the final bound. This difference shows a nontrivial way in which the source of the errors, which governs how the errors enter into the analysis, matters. \n\n> Moreover, the limitation...\n\nIndeed, we do need the smoothness of the input-to-output map as we will use the result from Liu et al. (2020), which claims the neural network is $O(1/\\sqrt{m})$-smooth with respect to its parameters. However, many activation functions are twice differentiable (e.g., sigmoid, tanh, arctan, softplus) and one could always use a smooth approximation to a ReLU activation (e.g., GeLU or ELU). \n\n> In key ideas Section 4...\n\nThe small-gain theorem is the same as the one used in Olshevsky et al. \n\n> It would be better to explain the difficulties in combining the existing works.\n\nAs discussed above, one of the difficulty lies in Markov sampling in AC. The idea is simple, which is to assume uniform mixing and show the difference to mean-path update is geometrically decreasing based on the distance to stationary distribution is geometrically decreasing. However, this problem, which is easy to address, as shown in Bhandari et al. (2018), is difficult in AC, since the policy changes from step to step. Inspired by Zou et al. (2019); Wu et al. (2020); Chen & Zhao (2022), we introduce an auxiliary chain as the bridge from the current policy to stationary distribution. \n\nAnother difficulty lies in the generalization from single-layer neural network to multi-layer neural network. Our goal is not including linearization about initialization but using the Hessian of the neural network in our paper, as the only indicator on whether the neural network in close to a linear approximator. Though it is also addressed in Tian et al., in AC we have two sets of parameters, and they are actually coupled together. Decoupling these updates is a challenging work, and that is the reason why Assumption 2.6 comes in. \n\n> Regarding Assumption 2.6...\n\nAssumption 2.6 is crucial for our analysis because it enables us to decouple the critic parameter $\\omega$ and the actor parameter $\\theta$. As far as we know, this assumption is not included in any previous papers. This is likely the case for two reasons. First, for those of papers which only consider linear function approximation, the relationship as mentioned in Assumption 2.6 is also linear. Second, for those papers which consider neural network function approximator, they perform analysis in a double-loop setting, where the actor update is not performed until the critic network converges. Clearly, in this case the critic parameter $\\omega$ and the actor parameter $\\theta$ are *naturally decoupled* and the error term from both network also can be treated separately. Our result, to our best knowledge, is the first one that combines single-loop AC and a neural network (and we even generalize to multi-layer neural network), which requires Assumption 2.6. \n\n> In line 384...\n\nThanks for your question. We now make it more clear why the state action pair follows $(1-\\gamma)\\phi$ in Appendix A. Basically, by total probability, $P(S = s) = \\sum_{t=0}^{+\\infty} P(S = s|T = t) \\cdot P(T = t)$. The first term on the right hand side is exactly $P(S_t = s)$ and the second term equals to $(1-\\gamma)\\gamma^t$. We provide a pdf that contains a detailed proof. \n\n> In line 572 ...what meaning does each term have?\n\nWe're not sure there's a clean intuition here, i.e., a meaning for each term. In that line, we need to exploit the fact that the function will become more and more linear when the width of neural network $m$ goes larger and larger, and the application of the mid-value theorem appears in one of the steps of this. "}, {"review_id": "zJxPc8ooQh", "reviewer": "Reviewer_qbM5", "summary": "The paper proposes an analysis of the the actor critic setting with function approximator and it proves the convergence using deep neural networks with an arbitrary number of hidden layers.", "questions": "Why do the examples of off-policy divergence not apply in your analysis (see for instance Sutton and Barto intro to RL book in Section 11.2 \"Examples of Off-policy Divergence\").", "limitations": "Limitations are not really discussed and it might be that some of the claims (see questions above) are not correct.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The claims are ambitious.", "weaknesses": "The analysis of the paper sidesteps many key elements from the literature that contradicts the possibility to have a critic that provably converges when using non-linear function approximators, let alone when combined with an actor. When learning with the Bellman iterations, a compounding of errors can occur due to the non-linearity of the function approximator with respect to the parameters, which can lead to divergence even with the continuity and Lipschitz assumptions as described in the paper.\n\nThe discussion from Section 4.2 is also not convincing. \n\nAdditional comments:\n- line 77: the reward function goes into $R$, but what is R? Did the authors mean the real numbers $\\mathbb R$?\n- Many discussion points lack a precise formalization, e.g. line 248: \"Such an analysis is inherently more technically challenging, since when the actor can wait for the critic to go through sufficiently many iterations, one could argue that the resulting Q-values are approximately accurate and the process resembles gradient descent.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We welcome the opportunity to contextualize our results with respect to the earlier literature showing examples of divergence with non-linear function approximations. However, we do want to note to the reviewer that they misunderstand the state of this research area. Please see our responses below. \n\n> The analysis of the paper sidesteps many key elements from the literature that contradicts the possibility to have a critic that provably converges when using non-linear function approximators...\n\nThere is no such literature. \n\nWhat does exist are examples that show that nonlinear approximation *can* result in divergence. The earliest such example that we are aware of comes from the classic 1997 paper of Tsitsiklis & Van Roy. But this does not mean that RL with nonlinear approximations *always* diverges. This paper is just the latest of a long line of literature which develops progressively more realistic conditions under which various RL methods willl converge with nonlinear approximations. \n\n> When learning with the Bellman iterations, a compounding of errors can occur due to the non-linearity of the function approximator with respect to the parameters, which can lead to divergence even with the continuity and Lipschitz assumptions as described in the paper.\n\nIn the first part of this sentence, you have correctly described the main difficulty that any analysis of nonlinear approximation needs to overcome. \n\nBut as to the second part of your sentence, note that we have assumed more than just continuity and Lipschitzness. Among other assumptions, it is crucial for our results that the neural network is *randomly initialized*. We also make a quantitative version of an assumption that the underlying neural network maps different inputs to different outputs, which we support with simulations (see our global response). \n\n> Why do the examples of off-policy divergence not apply in your analysis (see for instance Sutton and Barto intro to RL book in Section 11.2 \"Examples of Off-policy Divergence\").\n\nNote that the version of actor-critic we consider in this paper is on-policy: after each actor update, a sample is generated using the new actor policy, and the critic takes a step using this new sample. So examples of divergence for off-policy TD are not relevant here. \n\nIt may be useful to quote from Section 11.5 of Sutton and Barto:``Semi-gradient methods may diverge under off-policy training, as we have seen earlier in this chapter, *and under contrived cases of nonlinear function approximation (Tsitsiklis and Van Roy, 1997)*'' (emphasis ours). The whole point of this paper is to come up with conditions that rule out such \"contrived cases\" of nonlinear approximation. \n\n> The discussion from Section 4.2 is also not convincing\n\nIf you are still not convinced that our results do not contradict existing work, please state precisely which specific theorem from which paper or textbook is violated by our main results. \n\nIt is perhaps worth spelling out a couple of critical ingredients in our work that enable us to obtain the result we did. First is that the critic runs not TD, but projected TD; the projection is on a set of fixed diameter, and this is important in terms of stabilizing the updates. Second, observe that nowhere in our paper do we have any result to the effect that either the critic or the actor parameters converge; instead, the *quality of the approximation* given by those parameters is bounded by\n$$ O \\left( \\frac{1}{\\sqrt{T}} + \\epsilon^2 + \\frac{1}{\\sqrt{m}}\\right),$$ where $T$ is the number of steps, $\\epsilon$ is the best possible approximation quality of the neural architecture, and $m$ is the neural network width. Here \"quality of approximation\" means both how well the critic is able to approximate the true value function of the actor's policy, and how well the actor is able to find a point where the gradient of its policy is zero. \n\nIt is entirely consistent with our results to have the parameters wander within the domain without convergence, as long as all the quality of the approximation given by the neural network remains good. For example, there may be a region where the gradient of the actor's policy is very close to zero, and nothing in our results prevents the actor's parameters from wandering within that region. \n\n\n*With all this in mind, we urge you to re-examine the contribution of our work.* Please do not hesitate to use OpenReview to contact us during the author-reviewer interaction period. \n\n> line 77: the reward function goes into R, but what is R? Did the authors mean the real numbers ?\n\nThanks for pointing out this typo! Yes here it should be the real numbers. We will change it to \\mathcal{R}. \n\n> Many discussion points lack a precise formalization, e.g. line 248: \"Such an analysis is inherently more technically challenging, since when the actor can wait for the critic to go through sufficiently many iterations, one could argue that the resulting Q-values are approximately accurate and the process resembles gradient descent.\"\n\nThe whole point of that section is to explain informally the challenges faced by our analysis. "}]

Author rebuttal:
Dear Reviewers, 

We would like to use the "global" review to provide two simulations asked for by some of the reviewers. 

*First*, one reviewer (implicitly) asks for evidence supporting our Assumption 2.7. Our attached pdf actually
shows evidence supporting the stronger assumption 

$$ || Q(w_1) - Q(w_2) || \geq \lambda ||w_1 - w_2||,$$ 

for all neural networks $Q$ generated during the actor-critic process, and all $w_1, w_2$ in the set onto which we are projecting;
crucially, $\lambda$ here is a parameter that should be bounded away from zero. Since it is impossible to test this for all $w_1,w_2$, we use  randomly chosen points. We have performed many simulations for Cartpole, MountainCar, and Acrobot (three finite-action MDPs in OpenAI Gym) and everything we have seen is consistent with being able to take $\lambda=e^{0.75}$ in the above equation. For an example of the kind of simulations we are doing, please see the three example runs in the attached PDF, where the quantity $||Q(w_1) - Q(w_2)||/||w_1 - w_2||$ is labeled as ``ratio.''

Let us take the opportunity to explain that Assumption 2.7 is a straightforward generalization of the non-redundant features assumption in linear actor-critic. Indeed, in linear AC one stacks up the feature vectors $\phi(s,a)^T$ into a matrix $\Phi$ (so that the value function can be approximated as $V \approx \Phi \theta$) and assumes that the smallest singular value of $\Phi$ is bounded away from zero. This is equivalent to non-redundancy of features (i.e., you should not be able to write one component of the vectors $\phi(s,a)^T$ as a linear combination of the other components). 

Another way to state this condition is that 

$$|| \Phi x - \Phi y || \geq \lambda ||x-y||$$

for some $\lambda$ and all $x,y$. It should now be immediate how our assumption above is a straightforward generalization of this to the nonlinear case. The discussion around this assumption in our manuscript contains several heuristic (i.e., non-rigorous) justifications for why this assumption holds, and we supplement it here with some simulations. 

*Second*, one of the reviewers brought up the possibility that initializing a random network randomly and projecting onto a ball of constant radius around that set can lead to a loss of representation abilities. That is indeed a concern (though we point out that previous works required projection on a ball of radius $O(1/\sqrt{m})$ around the initial point, where $m$ is the width, so our paper should be viewed as a step forwad to mitigate this). We show in the attached pdf (right-hand column labeled ``error'') that this does not happen in Cartpole and Acrobot, where the critic seems to be able to perfectly approximate the value function of the actor; but we also show this may happen in MountainCar where the simulations are consistent with the critic error having a floor away from zero. 



Meta-review: This paper studies the convergence rates of an actor-critic algorithm for reinforcement learning that use deep neural networks with multiple hidden layers for both the actor and the critic. It fills a gap in existing literature, primarily focusing on linear or single-layer neural network representations.  Overall, the work is well-written and represents a significant theoretical contribution to understanding actor-critic algorithms with complex neural network architectures. We request the authors to include the suggested changes/clarifications in the final version of the paper.
Decision: Accept (poster)