The Impact of Approximation Errors on Warm-Start Reinforcement Learning: A Finite-time Analysis
Authors: Hang Wang
Sen Lin
Junshan Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Reinforcement Learning
Finite-time Analysis
Approximation Error
Warm Start

Abstract: Warm-Start reinforcement learning (RL), aided by a prior policy obtained from offline training, is emerging as a  promising RL approach for practical applications. Recent empirical studies have demonstrated that the performance of Warm-Start RL can be improved \textit{quickly} in some cases but become \textit{stagnant} in other cases, calling for  a fundamental understanding, especially when the function approximation is used. To fill this void, we take a finite time analysis approach to quantify the impact of approximation errors on the learning performance of Warm-Start RL. Specifically, we consider the widely used Actor-Critic (A-C) method with a prior policy.  We first quantify the approximation errors in the Actor update and the Critic update, respectively. Next, we cast the Warm-Start A-C algorithm   as Newton's method with perturbation, and study the impact of the approximation errors on the finite-time learning performance with inaccurate Actor/Critic updates. Under some general technical conditions, we obtain lower bounds on the sub-optimality gap of the Warm-Start A-C algorithm to quantify the impact of the bias and error propagation. We also derive the upper bounds, which provide insights on achieving the desired finite-learning performance in the Warm-Start A-C algorithm.

Under review as a conference paper at ICLR 2023
THE IMPACT OF APPROXIMATION ERRORS ON WARM- START REINFORCEMENT LEARNING: A FINITE-TIME ANALYSIS
Anonymous authors Paper under double-blind review
ABSTRACT
Warm-Start reinforcement learning (RL), aided by prior policy obtained from offline training, is emerging as promising RL approach for practical applications. Recent empirical studies have demonstrated that the performance of Warm-Start RL can be improved quickly in some cases but become stagnant in other cases, calling for fundamental understanding, especially when the function approximation is used. To fill this void, we take a finite time analysis approach to quantify the impact of approximation errors on the learning performance of Warm-Start RI. Specifically, we consider the widely used Actor-Critic (A-C) method with a prior policy. We first quantify the approximation errors in the Actor update and the Critic update, respectively. Next, we cast the Warm-Start A-C algorithm as Newton's 's method with perturbation, and study the impact of the approximation errors on the finite-time learning performance with inaccurate Actor/Critic updates. Under some general technical conditions, we obtain lower bounds on the sub-optimality gap of the Warm-Start A-C algorithm to quantify the impact of the bias and error propagation. We also derive the upper bounds, which provide insights on achieving the desired finite-learning performance in the Warm-Star Start A-C algorithm.
INTRODUCTION
Online reinforcement learning (RL) (Kaelbling et al.) 1996] Sutton & Barto 2018) often faces the formidable challenge of high sample complexity and intensive computational cost (Kumar et al. 2020 Xie al., 2021), which hinders its applicability
real-world tasks. Indeed, this is the case in portfolio management (Choi et al.) 2209). vehicles control (Wu et al. 2017 Shalev-Shwarz
al.] (016) and other time-sensitive settings Li 2017 / Gareta & Fernández] [205). 1..... To tackle this
challenge, Warm-Start RL has recently garnered much attention (Nair et al. 2020; Gelly & Silver 2007 [Uchendu et al. 2022). by enabling online policy adaptation from an initial policy pre-trained
using offline data (e.g., via behavior cloning offline RL). One main insight of Warm-Star RL is that online learning can be significantly accelerated, thanks to the bootstrapping by an initial policy.
Despite the encouraging empirical successes (Silver et al. 2017 2018 Uchendu et al. 2022
fundamental understanding of the learning performance of Warm-Start RL. is lacking, especially in the practical settings with function approximation by neural networks. In this work, focus the widely used Actor-Critic (A-C) method (Grondman et al. 2012) Peters & Schaal 2008). which combines the merits of both policy iteration and value iteration approaches (Sutton & Barto 2018) and has great potential for RL applications (Uchendu et al.) 2022). Notably, in the framework of abstract dynamic programming (ADP) (Bertsekas) (022a)) the policy iteration method (Sutton et al.) 1999) has been studied extensively, for warm-start learning under the assumption of accurate updates. In such setting, policy iteration can be regarded as a second-order method in convex optimization (Grand-Clément) 2021) from the perspective of ADP, and can achieve super-linear convergence rate (Santos Rust 2004; Puterman & Brumelle, 1979 Boyd et al., 2004]. Nevertheless, when the A-C method is implemented in practical applications, the approximation errors are inevitable in the Actor/Critic updates due to many implementation issues, including function approximation using neural networks, the finite sample size, and the finite number of gradient iterations. Moreover, the error propagation from iteration to iteration may exacerbate the 'slowing down' of the convergence and have intricate impact therein. Clearly, the (stochastic) accumulated errors may throttle the

---

Under review as a conference paper at ICLR 2023
convergence rate significantly and degrade the learning performance dramatically (Fujimoto et al.) 2018; Uehara et al. [02T] Dalal et al., 2020 Doan et al. 2019). Thus, it is of great importance to characterize the learning performance of Warm-Start RL in practical scenarios; and the primary objective of this study is to take steps to build a fundamental understanding of the impact of the approximation errors on the finite-time sub-optimality gap for the Warm-Start A-C algorithm, i.e.,
Whether and under what conditions online learning (e.g., A-C) can be significantly accelerated by a warm-start policy from offline RL?
To this end, we address the question two steps: (1) We first focus on the characterization of the approximation errors via finite time analysis, based on which we quantify its impact on the sub-optimality gap of the A-C algorithm in Warm-Start RL. In particular, we analyze the A-C algorithm in a more realistic setting where the samples are Markovian in the rollout trajectories for the Critic update (different from the widely used i.i.d. assumption). Further, we consider that the Actor update and the Critic update take place on the single-time scale, indicating that the time-scale decomposition is not applicable to the finite-time analysis here. We tackle these challenges using recent advances on Bernstein's 's Inequality for Markovian samples (Jiang al., 2018 Fan al. 202 By delving into the coupling due to the interleaved updates of the Actor and the Critic, we provide upper bounds on the approximation errors in the Critic update and the Actor update of online exploration, respectively, from which we pinpoint the root causes of the approximation errors.
(2) We analyze the impact of the approximation errors on the finite-time learning performance of Warm-Start A-C. Based on the approximation error characterization we treat the Warm-Start A-C algorithm as Newton's 's method with perturbation, and study the impact of the approximation errors on the finite-time learning performance of Warm-Start A-C. For the case when the approximation errors are biased, we derive lower bounds on the sub-optimality gap, which reveals that even with a sufficiently good warm-start, the performance gap of online policy adaptation to the optimal policy is still bounded away from zero when the biases are not negligible. Further, we also derive the upper bounds, which shed light on designing Warm-Start A-C to achieve desired tnite-time learning performance. We present the experiments results to further elucidate our findings in Appendix K
Related Work. (Warm-Start RL) AlphaZero (Silver et al. 2017) is one of the most remarkable successes in Warm-Star Start RL. In a line of very recent works (Gupta et al.; 20s0e[]speert et al., (002)(Kim al. 2013) on Warm-Start RL, the policy is initialized via behavior cloning from offline data and then is fine-tuned with online reinforcement learning. A variant of this scheme is proposed in Advanced Weighted Actor Critic (Nair et al. 2020) which enables quick learning of skills across a suite of benchmark tasks. In the same spirit, Offline-Online Ensemble (Lee et al. (2022) leverages multiple Q-functions trained pessimistically offline as the initial function approximation for online learning. Jump-stan start RL (Uchendu et al., 2022) utilizes a guided-polie to initialize online RL in the early phase with a separate online exploration-poligy The -oolieyy-poyyyyy will be abandoned as the online exploration-policy improves. However, fundamental characterization of the finite-time performance of Warm-Start RL is still lacking. Recent work (Xie et al. 202T) provides a quantitative understanding on the policy fine-tuning problem in episodic Markov Decision Processes (MDPs) and establishes the lower bound for the sample complexity, where no function approximation is used. Our work aims take steps to quantify the impact of approximation error on online RL. when warm-start policy is given.
Actor-Critic as Newton's Method) The intrinsic connection between the A-C method and Newton's method can be traced back to the convergence analysis of policy iteration in MDPs with continuous action spaces (Puterman & Brumelle, 1979). The connection is further examined later in special MDP with discretized continuous state space Santos & Rust 2004). Recent work (Bertsekas) 2022b) points out that the success of Warm- Start RL, e.g., AlphaZero, can be attributed to the equivalence between policy iteration and Newton's 's method in the ADP framework, which leads to the superlinear convergence rate for online policy adaptation. Under the generalized differentiable assumption, has also been proved theoretically that policy iteration is the instances of semi-smooth Newton-type methods to solve the Bellman equation (Gargiani et al. 2022). While some prior works (Grand- Clément 1) have provided theoretical investigation of the connections between policy iteration and Newton's 's Method, the studies are carried out in the abstract dynamic programming (ADP) framework, assuming accurate updates in iterations. Departing from the ADP framework, this work treats the A-C algorithm as Newton's 's method in the presence of approximation errors, and focuses on the finite-time learning performance of Warm-Start RI.
2

---

Under review as a conference paper at ICLR 2023
(Finite-time analysis for Actor-Critic methods) Among the existing works the finite time analysis of A-C methods with function approximation, Yang et al. 2019) establishes the global convergence under the linear quadratic regulator. (Wang et al. 2020) proves the convergence behavior when both Actor and Critic are approximated by overparameterized neural networks. (Kumar et al. 2019) considers the sample complexity under i.i.d. assumptions where the Actor update and Critic update can be 'decoupled'. Khodadadian et al. (2022) considers the two-timescale setting with Markovian samples. (Fu et al.] (020) focuses on the more general single-time scale setting but constrains the policy function approximation in the energy based function class.
2 BACKGROUND
Markoy Decision Processes. We consider a MDP defined by a tuple (S,A, where S = {1,2, ,n), < Do and A (1,2, A), A
represent the finite state space and finite action space, respectively. P(s'ss.)= S x A x S + [0 is the probability of the transition from state to state s' by applying action and (s,a) : S + IR is the corresponding reward. E (0, 1) is the discount factor. At each step t, an agent moves from the current state St to next state 8141 by taking an action a, following the policy π + AA and receives the reward rt. In the Warm- Start RL, we assume that the initial policy is given, e.g., in the form of a neural network (Li 2017 and obtained by offline training. For brevity, we use bold symbols r= E R [r*]= r(s, (())
and Pa E Rax=; [P"],..' A P(s'|s, (()) to denote the reward vector and the transition matrix
induced by policy æ. We further denote by d" - [0, 1] and p" :S x A + [0, the stationary
state distribution and state-action transition distribution induced by policy и. We use po to represent the initial state distribution. We use || || or ||2 to represent the 2-norm.
Value Functions. For any policy т, define the value function v (s) : + R as (T)) = B 1 ()) 1E /'r s] to measure the average accumulative reward star- We define Q-function (*,, S x A R as
ing from state 8 by following policy (s) = E E T'rr|s0 = 8, do = a] to represent the expected return when the action a chosen at the state By using the transition matrix and reward vector defined above, we have the compact form of the value function vx = = - 'rr,.
PT) rr, where I E R2xn is the identity matrix and vr' E IR" is the value vector with the component-wiss values [u"]. 2 v=(s),, with (sT
(s) & The main objective is to find an optimal policy x" such that the value function is maximized, i.c.,
max Ex-po [u" (s) - max (expp)arrz(1))) 1QT (0=((((s
In what follows, we use both Q-function and value function ess) for convenience, and the relation between the two is given in Eqn. (2).
Bellman Operator. For w E R", define the Bellman evaluation operator T R" + IR" and the Bellman operator T : R - 1R" as
(T) -T + T(v) = max(r= + + = = mmx (v).
It is well known that the Bellman operator T' is contraction mapping and has order- preservng property. Note that the Bellman operator T may not be differentiable everywhere due to the max operator, and the value v' of the optimal policy x² is the only fixed point of the Bellman operator T (Puterman 2014). From the definition of the Bellman Evaluation Operator T"T, we have v" to be the fixed point of Th i.e., dx (v").)
2.1 POLICY ITERATION AS NEWTON'S 'S METHOD IN ABSTRACT DYNAMIC PROGRAMMING
Policy iteration carries out policy learning by alternating between two steps: policy improvement and policy evaluation. At time f, the policy evaluation step seeks to learn the value function = for the current policy Te by solving the fixed point equation of the Bellman evaluation operator:
v = T (v).
Denote 8, " for simplicity. Then in the policy improvement step, new policy æe-1 is obtained by maximizing the learnt value function on in the policy evaluation step, in a greedy manner, i.c.,
1 arg max T (v.).
(4)
3

---

Under review as a conference paper at ICLR 2023
Critic Update
Actor Update
arg max (122)
7,
arg max (v5
x+3
arg max (1
1
As+3
x
approsimation
Value function
approximation
Policy
The approximation errors from Critic update (E,) and Actor update (E.) are carried forward and may get amplified due to accumulation. (To distinguish the approximation errors between Critic update and Actor update, we use tilde symbol and the value vector obtained in the presence of Critic update error. We use hat symbol above the variables to represent the results with approximation eтror in Actor update.)
Figure I: Illustration of error propagation effect in the A-C method:
above variables, such as policy मे and value vector G, to represent the policy
To introduce the connection between policy iteration and Newton's s Method, we first define operator F w - セ T(b) for convenience. As in (Grand-Clémentt 2021 Puterman 2014), F can be treated as the "gradient" of an unknown function. Under the assumption that F F(v) is differentiable at v. the Jacobian Ju of F at v can be obtained as Ju = I ? Pr(u), where π (w)) - arg max, (v)). Note that J = (7 Px())) is invertible (Puterman 2014). Since it can be shown that T (I P M1 F Jun Trees for the policy evaluation of TT+11 we have that, 2 0T 0 -Jppl Jo 2 T + J.r. Tre41 = atr -
(5) which indicates that the analytic representation of policy iteration in the abstract dynamic program- ming framework reduces to Newton's 's Method. It is worth mentioning that the convergence behavior of policy iteration near the optimal value v" cannot be directly obtained by using the results from convex optimization (Boyd et al. (004) since the Bellman operator T may not be differentiable at any given value vector The full proof is included in Appendix A
2.2 AN ILLUSTRATIVE EXAMPLE OF THE ERROR PROPAGATION IN ACTOR- UPDATES
The A-C method can be viewed as a generalization of policy iteration in ADP, where the Critic update corresponds the policy evaluation of the current policy and the Actor update performs the policy improvement. In practice, function approximation (e.g., via neural networks) is often used to approximate both the Critic and the Actor, which inevitably incurs approximation errors for the policy update and evaluation. More importantly, the approximation errors could propagate along with the iterative updates in the A-C method. We have the illustrative example to get a more concrete sense of the impact of the approximation errors the policy update.
As illustrated in Figure [ for a given policy ne with the underlying true policy value ot' we denote Th as the learnt value estimation of Th in the Critic step. We further denote π++1 and 7441 as the greedy policy obtained in the Actor update Eqn. (4) by using th and U" respectively. Let ft41 be the policy estimation of 7 with function approximation in the Actor step. Intuitively, T++1 is the underlying true policy update from गy using one step policy iteration without any error, Te+11 is the policy update from n, with approximation errors in the Critic update, and म.+1 is the policy update from Te with approximation errors in both the Critic step and the Actor step. To characterize the impact of the approximation errors on the policy update, i.c., the difference between u and uft-1, we evaluate the Critic error, i.e., the difference between J and a 5f and the Actor error, i.e., the difference between v T and R in a separate manner. More specifically, to quantify the Critic error, we can first have the following update based on the same reasoning with Eqn. (5)
tel1 U.
J 5.
(v. (Ti.41 + + (Pri.i A vz J T (v:)
where T(xx) = T + 7 PP...10 or and Js. = -I-PPru Denote the approximation error (random variable) in the Bellman operator T and the Jacobian Ju by ET,, and E i.e.,
T(v:) - T(w:) =(r + Px 22) (T 1 + PP Pet4 v.) & Er,
J- J -(I
where it is clear that both error terms stem from the function approximation emrors in the Critic update. To quantify the Actor error, we assume that
v hett 3 + Ea,bs
(6)
4

---

Under review as a conference paper at ICLR 2023
where Ex, is the error term. Therefore, by casting the A-C method Newton's method with perturbation, we can characterize the approximation errors on the policy update:
v - -z Ec,t Ea.t.
Er,))rr and Ea.t capture the impact of the approximation error from Critic update step and Actor update step, respectively. Intuitively, as illustrated in Figure [ both errors from the previous update in the A-C method may propagate the next update and thus affect the convergence behavior of the algorithm substantially, in contrast to idealized policy iteration without approximation errors. This phenomenon has also been observed in the empirical results (Fujimoto et al., 2018 Thrun & Schwartz 1993). In this work, we strive to systematically analyze the impact of the approximation errors, through (1) detailed characterization of the approximation errors in the Critic update and the Actor update in Section Sattioonnnam and (2) a thorough analysis of the error propagation effect and biases in Section 4
where Ec. - - - T(ve))
The illustration of our analysis available Appendix A
CHARACTERIZATION OF APPROXIMATION ERRORS
Actor-Critic Methods with Function Approximation. In what follows, we consider that the policy is parameterized by E O which in general corresponds to non- non-linear function class. Following (Konda & Tsitsiklis 1999] Peters & Schaal 2008 Kumar et 2019 2020 Santos & Rust 2004)), the Q-function is parameterized by a linear function class with base function Φ(s, a) and parameter E Ω Rd i.e., Qu (s, a) = w' Φ(s, a). We note that the modeling of the Q-function via linear value function is often used to extract insight in the A-C method. Similar to the policy iteration, the update in the A-C method alternates between the following two steps
Critic update: The Critic updates its parameter w to evaluate the current policy Tr, e.g., through m-step (m 2 1) Bellman evaluation operator T to the current Q-function estimator (namely, m-step return), which leads to the following update rule at time step t,
m-
Q4+1(8, a) EET, - 7)
Σ ==0
2' (si, + 7 Qui (8m; | 880 = 8, 00
(7)
W1+1 f- arg min E ((s,))=p (Q++1(5, T ((s a))²
(8)
Actor update: The Actor is updated through greedy step to maximize Q-function Quiii Pumiirie. i.e.
Te+1 f- arg max (s.a)=p" (s,
3.1 APPROXIMATION ERROR IN THE CRITIC UPDATE
Solving the minimization problem in Eqn. ( involves the expectation over the stationary state- action distribution nT induced by the current policy Te, which can be approximated by sample average in in practice. Therefore, we consider the Critic update below based on two groups of samples, {(5t, a:) and { where 7i = {si 01 Ti, which are collected by following n,
w411 = =Ta{ (ΣN de (st, ai) o (8), (8).
ΣN (1-7)_m0 /r1, +7 (s), (s). a.,) di (st, al
(10)
where I is the projection operator onto the Critic parameter space Ω with radius R in Rdd. Since the samples in each trajectory Tj are obtained via rolllouts, in general the samples in each trajectory follow Markovian process (Dalal et al., (2018] Kumar al. (011). We further assume the samples are from the stationary distribution induced by the current policy.
In what follows, we use and Wi distinguish the difference between the sample-based update and the solution from Eqn. (8), such that the approximation error in the Critic update can be quantified as QQu, Q- We first impose the following standard assumptions on the Bellman evaluation operator T the base function o and the MDP.
We remark that our analysis framework and theoretical results are able he applied to off-policy setting with the extra assumption the hehavior policy. We include the details in Appendix L.
5

---

Under review as a conference paper at ICLR 2023
Assumption 1. For given Critic parameter and policy parameter 8, the following condition holds:
inf E [((II0)'') Qu - 6) (s,a)] 0,
West
where pae the stationary state-action transition probability induced by policy mg-
Assumption | (Fu et al. 2020) indicates that the solution the Critic update given in Eqn. (8) lies in the Critic parameter space S2. We note that this assumption is used for ease of exposition, and our results can modified by incorporating an additional constant term when this assumption does not hold. The proof sketch in this case can be found in Appendix [
Assumption 2. The base function & in the Critic satisfies the following two conditions: (1) [lo(s, a)ll S 1, A (s, a) E S x A; and (2) the smallest singular value for Eplo(s, a)o(s a) lower bounded by a positive constant a² for any stationary state-action transition distribution p.
Assumption 2 is widely used in the A-C method to guarantee that the minimization in Eqn. 8 can
be attained by a unique minimizer (Fu et al. 2020 Bhandari et al.] 2018 Agarwal et al. 2021).
conditions: (1) The reward is upper bounded by a positive constant maax for all (s, a) E S x A; and (2) the stationary state-action transition matrix P has non-zero spectral gap X, > 0 for all æ.
Assumption 3. The reward r(s, a) satisfies the following
The first condition Assumption is often used for discounted MDPs to ensure a finite value function (Thrun & Schwartz, 1993 Fujimoto et al.] 2018: Fu et al. 2020). Moreover, since the samples in the same trajectories are generally correlated, the second condition is adopted to guarantee the concentration properties of the Markov chain, which is generally true for the stationary Markov chain (Jiang et al. 2018
Ortner
2020 Amit et al. 2020).
For any À E [0, 1). let (1 (1 + A) - A), 0:2 (A) 5/(1 A) where 0z (0) 1/3. Define
Fm. y /agra max (eeeaax(nnn (max{ Az, -0)² In? p-2man (max Ar, .0) In ( Ar, 00) lnp
+ Tmax-
Then have the following main result on the approximation error in the Critic update step. Proposition (Approximation Error in Critic Update). Under Assumptions
|
2
the following
inequality holds with probability least 1 p, for any > 0, (8,a) E A:
El (s, a) - Qa, (s, a)]] (m
2 log 3N
P + V ONZ 4d
log"
p 4d
2 N
log 4d
VN(o
where d is the dimension of the Critic parameter w and R is the radius of Critic parameter space Q as defined in Eqn. (T)..
Proposition I establishes the upper bound for the approximation error in the Critic update, which encapsulates the impact of the finite sample size and the finite-step rollout with Bellman evaluation operator 7 It can be seen from Proposition that in order to obtain an accurate evaluation of the policy, we can increase the sample size N in the update Eqn. (T)) and have more steps of rollout with Bellman evaluation operator 2 We remark that Proposition considers the correlation across samples, and we appeal to the recent advances in Bernstein's 's Inequality for Markovian samples (Jiang
ett al. (Fan et al. 2021b) to tackle this challenge. The proof of Proposition can be found in Appendix and Appendix C
3.2 APPROXIMATION ERROR IN THE ACTOR UPDATE
In practice, the greedy search step for solving Eqn. g is generally approximated by multiple (e.g.. N₂) steps of policy gradient. Based on the policy gradient theorem (Silver et al. 2014; [Sutton et al. 1999), we can have the following update gradient step & [1, Na in the t-th Actor update:
θr1 = 6r, ON,N. = 6.+1,
"L, where is the learning rate. For simplicity, we drop the subscript in 0r, when no confusion will arise and denote p² = As in the Critic update, we sample trajectory with length / by following the current policy no., i.e., {81. 01, 82, 02 ... St, at), to approximate the expectation in Eqn. III Then we can have that
0 = 02 + aE, aE (s.a)>=" T9. [Quz4s (s. oalo).
(11)
0 0k+1 =0p + at Ei= (3t, a,) VOTO, (a. (z)(s:)] 02 + a(Cka1 + Ckaz) + tafk. (12)

---

Under review as a conference paper at ICLR 2023
where Ck,,1 C,,t,2 and f are defined as follows
C,,,,1 : E1 (s ai V VoTT, (ay s.)) Qin. (8s; VoTo, (a,ls:)),
= 1 (Q w1 (8i, ai VoTo, (ails:) - Q (8i, ai) VoTO, (a:ls:)),
fK. f=,t:=1/1E> QTa² (5s; a;) VaTe, (ails:).
Here Ck,r.1 captures the error resulted from using samples to estimate expectation in the Critic update. Based on our result in Proposition I with high probability, this term will go to 0 when have infinite samples or infinite rollout length m. Note that ((T=)))))) = Qw... (Critic update) and limm-+so (T ym ""u QT4, And Ck. implies the approximation error when applying the Bell- man operator limited (m) times. This term will go to O when m + 00. fE. is an unbiased estimation of the gradient of (ssp)))ppt TQ (s,a) a)], i.e., E[fx,1 = (s,,))~p= (QT (s, a) VoTo, (a|s)]-
Based on Eqn. (2). it is clear that the Actor update with the approximation error resulted from the Critic update can be viewed a stochastic gradient update with some perturbation Ck.t
CR..,1 + Ck Denote 0++ as the solution of the Eqn. (9). For ease of exposition, we use h(w, 0) denote the objective function in the Actor update:
h(w, 0) E(sa))<p'
(Qw a)] E (s)].
(13)
Note that h is a function of Actor parameter for given Critic parameter w. Next, we quantify the approximation error in the Actor update in terms of the gap h(wr41, (7+1) h(wi+1, 0441).
Recall that Proposition D gives upper bound for the approximation error E. lQ - -2x ll in the Critic update, which has direct impact on Ck,t- Based on Proposition!] [ we have the following two lemmas for the upper bounds on the bias term = ac and the error term 3 = Su. + Cz.t E(Cr.e] e in the stochastic gradient update Eqn. [22 respectively. The proof of Lemmas I and can be found in
Appendix D and respectively.
Lemma 1 boundedd noise). Suppose Assumptions 1
3 hold. Then with probability at least
1 - p. [| < ||Vgh(ws, 0) b1l² + o2, v0, where o is a constant and depends on p.
Lemma (ça-bounded bias). Suppose Assumptions 1 2 hold. Then with probability least 1 - p.
|bb| 5², v0, where 5² 2 0 is a constant and depends on
Denote the score function (alss))) == (oto(als) and we impose the following standard assumptions.
Assumption 4. For any 0, 0' E Rdd and state-action pair (s, a) E x A, there exist positive constants
T.p, Ca and Cx such that the following holds: (1) 1100 thbr < T 0' ll; (2) | S C. and ||TV is the notal-variation distance.
(3) [[TT(- ( (-Is)]l S 11 0' where
We remark that the smoothness and bounded property of the score function as stated in the (1) and (2) in Assumption 4 are widely adopted the literature (Xu et al.) 2020a (6| Zou et al. 2019 Agarwal al. 22020; Kumar al. 2019), and it has been shown (Xu et al.) 2020a) that (3) in Assumption
can be satisfied for any smooth policy with bounded action space.
For the sake of tractability, we next give the following two lemmas about the smoothness and Polyak- Lojasiewicz Condition on the objective function h1, 0). The proof can be found in Appendix F
Lemma 3 (L-smoothness). Suppose Assumption 4 hold. Then function h(,, 0) is bounded from below by an infimum inf E R, differentiable and V h is L-Lipschitz i.e., [|Vh(,, 0) Vh(w, Th(w,8'll=
LI 0l], V w., 0, 0'.
Lemma 4 (JuPPL). IfVh(w, 0) + O, then we have
Vh(w, 0)1 2 /MhWw, 0*) hww, (,www))))) 0)) 2 0,
1 Next present the upper bound of the approximation error in the Actor update. Let S ZL Proposition 2 (Approximation Error in Actor Update). Given the updated Actor parameter 0,-1, the following inequality holds with probability at least 1 p:
Ee [wl 07) - fww, 011 S (1 - ax) No (h(w, 02) lew,, 0: 0c-1)) + G² 2a
2μ
where 2², <², and fa are defined in Lemma Lemma Lemma and Lemma 4 respectively.
Proposition reveals that due to the bias and noise induced by the Critic approximation error, running more gradient iterations do not necessarily guarantee the convergence to the optimal policy Ta; Note that Lemmas and i (Ajallocian & Stich 2020) are given in the form of assumptions, whereas in this work, we justify that both assumptions hold with high probability and prove Proposition 2 and the proof can be found in Appendix G
7

---

Under review as a conference paper at ICLR 2023
4 IMPACT OF APPROXIMATION ERRORS AND WARM-START POLICY ON FINITE-TIME LEARNING PERFORMANCE
We next quantify the impact of the approximations errors on the sub-optimality gap of the Warm- Start A-C method with inaccurate Actor/Critic updates. We first cast the A-C method as Newton's s Method with perturbation, and then present both the finite-time upper bound and lower bound on the finite-time learning performance in Section 4.1
Actor-Critic Method as Newton's Method with Perturbation. As mentioned earlier, the Critic update follows Eqn. (TO) with finite samples and finite step rollout with Bellman evaluation operator T and the Actor update follows Eqn. (12). Given the policy ne at time I, we denote the resulting policy of one A-C update #1+1- Recall that we use #1+1 denote the policy attained the max in T(=*:) as illustrated in Figure Furthermore, we define the following notations for case of our discussion: (1) Denote Ev,t- = v * = as the approximation error the Actor update: (2) Denote E T TRc:1 as the error in the reward vector, which is induced by the approximation error in the Actor update step: (3) Denote Ep = Pu++: PRE+i as the error in the transition matrix
P; (4) Denote E = v. J where Jé. = I - P and Jj = I - -PP
Following the same line as in Section 2.2 we treat the A-C algorithm as Newton's method with perturbation E,, i.e.,
v = th (J (v T(b**)) - Et) ;= 0² -((1,
(14)
where E(t) is the stochastic estimator of Newton's 's update L(t) JØr. T (vx))) and
(1 which can be further decomposed into bias and Martingale difference noise follows:
E, = E., + (v (Fr.. + Re+. a² 1)) J (Er TE
B(t) EE(((t) - C(t) = E[E,], ((t)) AC(t) E(C(t)] =, E[E,]
We have few observations in order. It can be that the perturbation & results from both Actor approximation error (e.g., E,,, Ep)s) and Critic approximation error (e.g., Ev,z). More importantly, the learnt Q function in the Critic update Eqn. (TO) is biased in general due to finite rollout steps m, which further leads to the biased gradients in the Actor update Eqn. (TT) (Kumar et al.) 2019). Clearly, the estimation bias plays an important role in affecting the learning performance, especially when deep neural networks are used as function approximations, which has been extensively investigated using empirical studies (Fujimoto et al. 2018 Hirwing et al., 2018 Van Hasselt et al., 2016).
Next, we examine the bias B(t) based on the approximation errors in the Actor/Critic updates. the approximation error in the Critic/Actor updates,
Combining the results in Proposition [ and on [
we have the following result on the bias (()). A full derivation is given in Appendix H
Proposition 3 (Upper Bound on the Bias). Suppose Assumption holds. Let S.(+) be an open ball of radius There exist positive constants Ls, and e, such that when O.+1 E S. (0;41), the following holds for any 0,
[B(()]] < E, [| 0++1) - 0+11)l
4.1 FINITE- TIME LEARNING PERFORMANCE AND ERROR PROPAGATION EFFECT
Lower Bound on Performance Gap. Aiming to understand "whether online learning can be accelerated by a warm-start policy", we first derive a lower bound to quantify the impact of the bias and the error propagation. By unrolling the recursion of the Newton update (with perturbation) Eqn. (14), we obtain the following theorem.
Theorem 1. The lower bound of |E[r"' - - satisfies that
E [00 D ae+++]]
|| 2 1 Pe11 - o²0) Ei= 7² P,B(L - BB)l,,
(15)
where P = E [II 1 P
)] and no is the warm-start policy.
Error Propagation and Accumulation. It can be seen form Theorem I that the bias terms (B(t))
add up over time, and the propagation effect of the bias terms is encapsulated by the last two terms on the right side of Eqn. (15). Clearly, the first term on the right side, corresponding the impact of
8

---

Under review as a conference paper at ICLR 2023
the warm-start policy To, diminishes with A-C updates. To get more concrete sense of Theorem
we consider the following special settings. (1) When the bias is always positive, i.., Btt) > 0 for all
t 2 O, the lower bound Theorem is always positive, i.e., || [0- .++ 2 [|](0)] > 0. In this case, the sub-optimal gap remains bounded away from zero. Similar conclusion can be made when the bias is always negative. (2) When the bias term can be either positive or negative, the lower bound is shown as Eqn. (15). In this case, the learning performance of the A-C algorithm largely depends on the behavior of the Bias term. It can be seen from Theorem ] that even when the warm-star policy is near-optimal, it is still challenging to guarantee that online fine-tuning can improve the policy if the approximation error is not handled correctly. We note that this has also been
observed empirically (Nair et al. 2020 Lee al. 2022).
Upper Bound on Performance Gap. In order to derive the upper bound on the sub-optimality gap, we first introduce the following standard assumption on the Jacobian Ju in the analysis of policy iteration (Puterman & Brumelle 1979, Grand-Clément 2021).
Assumption 5. For some q > 0 there exists a constant 0 < Ly < too such that | - J l| S Ls||o v'Il
I1 V n,
and there is a constant 0 < M < too such that || | S M, V..
Denote He := | JJa. - Jo.11 Clearly, we have H, is upper bounded by H, <. M MMM w*'l" from Assumption 5
Next, We present the finite-time time-time upper bound in Theorem 2
Theorem 2. Suppose Assumption 5 holds. Then we have that for any t >> O,
Biu - <
H ==
-| - 1 0 +
Σ II H
[B[ - 0)I + |B(t]l.
Under what conditions online learning can be accelerated by the warm-start policy? The upper bound in Theorem sheds light on the impact of warm-start policy no (the first term) and the bias {B(()) (the last two terms), thereby providing guidance on how to achieve desired finite-time learning performance. Specifically, consider the case when the approximation error is unbiased. Clearly,
we have ||E[u*++1 o'Ill S (II'- Hr-:) ||0" b
I]. which decreases quickly if the warm-start
policy To is close to the optimal policy л²" This observation corroborates the most recent empirically finding, where the online RL is able to further improve the warm-star policy by few adaptation steps (Silver et al.] 2017 [Bertskkas] [202aa] Kalashnikov al. 2018). More generally, when the bias B(() o O, the upper bound hinges heavily on the biases the approximation errors, even when the strm-start policy To is close to the optimal policy. In this case, recall the result the upper bound of the bias B(t) in proposition 3 where we establish the connection between the bias and the approximation error. As expected, in order to reduce the performance gap, it is essential to decrease the bias in the approximation error, which can be achieved by increasing gradient steps and sample sizes. The proof of Theorem I [and are relegated to the Appendix [] respectively. The experiments results and analysis on the Gridworld benchmark can be found in Appendix K
5 CONCLUSION
In this work, we take a finite-time analysis approach to quantify the impact of approximation errors on the learning performance of Warm-Start A-C method with a given prior policy. By delving into the intricate coupling between the updates of the Actor and the Critic, we first provide upper bounds on the approximation errors in both the Critic update and Actor update of online adaptation, respectively. where the recent advances on Bernstein's 's Inequality are leveraged to deal with the sample correlation therein. Based on these results, we next cast the Warm-Start A-C method as Newton's 's method with perturbation, which serves as the foundation for characterizing the impact of the approximation errors on the finite-time learning performance of Warm-Start A-C. In particular, we derive lower bounds on the sub-optimality gap under biased approximation errors, indicating that the performance gap can be bounded away from zero even for Warm-Star A-C with good prior policy. And we also provide upper bounds on the sub-optimality gap, which provides guidance on the design of Warm-Star RL for achieving desired finite-time learning performance.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pp. 64-66. PMLR, 2020.
Alckh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22(98): 1-76, 2021.
Ahmad Ajalloeian and Sebastian U Stich. On the convergence of SGD with biased gradients. arXiv preprint arXiv:2008.0000 2020.
Ron Amit, Ron Meir, and Kamil Ciosek. Discount factor as a regularizer reinforcement learning. In International conference on machine learning, pp. 269-278. PMLR, 2020.
Dimitri Bertsekas. Abstract Dynamic Programming, Athena Scientific, 2022a.
Dimitri Bertsekas. Lessons from Alphazero for Optimal, Model Predictive, and Adaptive Control. Athena Scientific, 2022b.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference learning theory, pp. 1691-1692. PMLR, 2018.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex Optimization. Cambridge university press, 2004.
James Choi, David Laibson. Brigitte Madrian, and Andrew Metrick. Reinforcement learning and savings behavior. The Journal of finance, 64(6):2515-2534 2009.
Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two two-timescale stochastic approximation with applications to reinforcement learning. In Conference On Learning Theory, pp. 1999-1233. PMLR, 2018.
Gal Dalal, Balazs Szorenyi, and Gugan Thoppe. A tale of two-timescale reinforcement learning with the tightest finite-time bound. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3701-3708, 2020.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, pp. (626-16334 PMLR, 2019.
Stefan Elfwing. Eiji Uchibe, and Kenji Doya. Sigmoid-weighted linear units for neural network function approximation in reinforcement learning. Neural Networks, 107:3-11, 2018.
Jianqing Fan, Bai Jiang, and Qiang Sun. Hoeffding's 's inequality for general markov chains and its applications statistical learning. Journal of Machine Learning Research, 22(139):1-35, 2021a. URL http:/ttp:///t jmir wwg///////oooo papers/ sappers/v2220 /////222/999/// 19 - 9tmml
Jianqing Fan, Bai Jiang, and Qiang Sun. Hoeffding's ' inequality for general markov chains and its
applications to statistical learning. Journal of Machine Learning Research, 22(139):1-35, 2021b.
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timesent actor-critic provably finds globally optimal policy. In International Conference on Learning Representations, 2020.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International conference on machine learning, pp. 1587-1596. PMLR, 2018
Javier Garcia and Fernando Fernández. A comprchensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
Matilde Gargiani, Andrea Zanelli. Dominic Liao-McPherson TH Summers, and John Lygeros. Dynamic programming through the lens of semismooth newton-type methods. IEEE Control Systems Letters, 2022.
10

---

Under review as a conference paper at ICLR 2023
Sylvain Gelly and David Silver. Combining online and offline knowledge in UCT. In Proceedings of the 24th international conference on Machine learning, pp. 273-280, 2007.
Julien Grand-Clément. From convex optimization to MDPs: review of first-order, second-order and quasi-newton methods for MDPs. arXiv preprint ar 2 104. 10677, 2021.
Ivo Grondman, Lucian Busoniu, Gabriel AD Lopes, and Robert Babuska. A survey of actor-critic reinforcement learning: Standard and natural policy gradients. IEEE Transactions on Systems, Man, and Cybereetcss, Part C (Applications and Reviews), 42(6):129111077, 2012.
Abhishek Gupta, Vikash Kumar, Corey Lynch, Sergey Levine, and Karol Hausman. Relay policy learning: Solving long- long-horizon tasks via imitation and reinforcement learning. In Conference on Robot Learning. pp. 1025-1037. PMLR, 2020.
Auke Ijspeert, Jun Nakanishi, and Stefan Schaal. Learning attractor landscapes for learning motor primitives. Advances in neural information processing systems, 15, 2002.
Bai Jiang, Qiang Sun, and Jianqing Fan. Bernstein's 's inequality for general markov chains. arXiv preprint 1tXiv:1805.1072) 2018.
Leslie Pack Kaelbling, Michael I. Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237-285, 1996.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforcement learning for vision-basee based robotic manipulation. In Conference Robot Learning, pp. 651-673. PMLR, 2018.
Sajad Khodadadian, Thinh T Doan, Justin Romberg, and Siva Theja Maguluri. Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions Automatic Control, 2022.
Beomjoon Kim, demonstrations. Advances in Neural Information Processing Systems, 26, 2013.
Farahmand, Joelle Pineau, and Doina Precup. Learning from limited
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. Advances in Neural Information Processing Systems, 33: 18560-18572, 2020.
Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. arXiv preprint arXiv:1910.08412. 2019.
Seunghyun Lee, Younggyo Seo, Kimin Lee, Pieter Abbeel, and Jinwoo Shin. Offline-to-online reinforcement learning via balanced replay and pessimistic q-ensemble. In Conference on Robot Learning, pp. 1702-1712. PMLR, 2022.
David A Levin and Yuval Peres.
Markov Chains and Mixing Times, volume 107. American
Mathematical Soc., 2017.
Pascal Lezaud. Chernoff- -tye bound for finite markov chains. Annals of Applied Probability, pp. 849-867, 1998.
Yuxi Li. Deep reinforcement learning: An overview. arXiv preprint arXiv: 2017.
Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.00359, 2020.
Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2003.
Ronald Ortner. Regret bounds for reinforcement learning via markov chain concentration. Joumna of Artificial Intelligence Research, 67:1 15-128, 2020.

---

Under review as a conference paper at ICLR 2023
Jan Peters and Stefan Schaal. Natural actor-critie, Neurocomputing,
2008.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Martin L Puterman and Shelby L. Brumelle. On the convergence of policy iteration in stationary dynamic programming. Mathematics of Operations Research, 4(1):60-69, 1979.
Manuel S Santos and John Rust. Convergence properties of policy iteration. SIAM Journal on
Control and Optimization, 42(6):2094-2115, 2004.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arX1v:1610.03295,, 2016.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference machine learning, pp. 387-395. PMLR, 2014.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Gracpel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint 1rXiv:1712.011 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Sebastian Thrun and Anton Schwartz. Issues in using function approximation for reinforcement learn- ing. In Proceedings of the 1993 Connectionist Models Summer School Hillsdale, NJ. Lawrence Erlbaum, volume 6, 1993.
Ikechukwu Uchendu, Ted Xiao, Yao Lu, Banghua Zhu, Mengyuan Yan, Joséphine Simon, Matthew Bennice, Chuyuan Fu, Cong Ma, Jiantao Jiao, et al. Jump-start reinforcement learning. arXiv preprint 02X2v22204.02372. 2022.
Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie, Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint arXiv:2102.02981. 2021.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI conference artificial intelligence, volume 30, 2016.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference Learning Representations, 2020. /ttpppp:/ppeeeeeeeeeeeeet/ttaraa
Cathy Wu, Aboudy Kreidieh, Kanaad Parvate, Eugene Vinitsky, and Alexandre M Bayen. Flow: Architecture and benchmarking for reinforcement learning traffic control. arXiv preprint arXiv:1710.05465, 10, 2017.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34, 2021.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for actor-critic algorithms. arXiv preprint a0Xiv:2004.1 12956, 2020a.
12

---

Under review as a conference paper at ICLR 2023
Tengyu Xu, Zhe Wang. and Yingbin Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint MtXiv:2005.03557 2020b.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. Advances neural information processing systems, 32, 2019.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. simite-sample analysis for SARSA with linear function approximation. Advances neural information processing systems, 32, 2019.
13

---

Under review as a conference paper at ICLR 2023
Appendix
A EXAMPLES IN SECTION 2.2
In this section, we elaborate further on the illustrative example in Section 2.2 We use the notation defined in Figure !
Policy Iteration as Newton's Method. Based on (Puterman & Brumelle, 1979 Grand-Clémeer 2021), we first build the relation between policy iteration and Newton's Method in the abstract dynamic programming (ADP) framework, assuming accurate updates.
From the definition of the value function v, we have that for any policy n,
x" Tx + PP Recall the definition of Bellman evaluation operator (*) and the Bellman operator T(.), T (v) -x + Pru, T(v) = max r + 7 pP,) = max T (*))). (v).
x
It follows that
a++1 J yne Fa+t1
th n + J Jame T7+4
nt Jo Jon + Jo
0 J (-PRet + v))
0t J (-PRe11 + (1- (1-7Pa PT111
th J (v -P -7 -P m
t J (w - (T()))))
(16)
where J, = I - 1 Pa(()) and (v) attains the max in ((v). Eqn. (16) establishes a connection between policy iteration under ADP and Newton's Method. Specifically, if we assume function F v + v T(v) (/v() is differentiable at any vector visited by policy iteration, then we have 0 J F(v:). which exactly the update of the Newton's Method in convex optimization (Boyd et al. 2004). Due to the fact that (-)) may not be differentiable at all v in policy iteration, the assumptions on the Lipschitzness of + Ju is commonly used to prove the convergence of the policy iteration (see Assumption 5). Following the same line, next we show the case when function approximation is used in the A-C algorithm.
A-C Updates with Function Approximation. Consider the illustration example in Section 2.2 Next we outline the main differences between the A-C update with function approximation and the policy iteration in the ADP framework, and cast A-C based policy iteration with function approximation as Newton's 's Method with perturbation. Specifically,
2= Tu++1
=h J-1 J Jo + J-1 17441 1741
=
(-Piet + J,i,0")
b
(-Ti + +(I - (Prr.)) 0T
pcc
Tv - (F + tyP ,²²²))
T
v T (0T
where Ju+. = P (((tt)) and π (v) attains the max T(x) (not T(x)), with the following two
operators defined as
T(v)) f + PPrmi
T(v)) G + P Ur.
14

---

Under review as a conference paper at ICLR 2023
Assumption
Characterization of Approximation Errors In the Cribic Update
Characterization Approximation Errors In the Actor Update
Projection on the Crètc parameter spase
Lomma
Lemrnn
Assumption
Proposition
bourded Noise
Assumplion
[ -emoollhrees)
Proposition
Base function Crttic update
Approximation Error In the Critic update
Scare function the Actor updale
Approximation Enro Actor update
Lemma
Acsumption
bounded
j- PL Condition
Reward and state Iransition matrix
Proposition
Upper bound of the bisses (B(n)
Theorem
Theorem 2
The Lower Bound of Ely
The Upper Bound of Bly* yfv!l
Impact Approximation Errors and Warm-start Policy on Finite time Leaminng Performance
Figure 2:
Illustration of the theoretical analysis.
For convenience, let Er,, and y denote the approximation errors the Bellman operator T and the Jacobian Ju, i.e., T(w)) - T(w)) =(raet1 + y P vz) - (N + y pP Uz) - ET,,,
J J_1 =(1 7 P ( 1-1 (I - :PrC )1 Eg
and define
0 dct1 Jets + Ea,ts
where E,, capture the error induced by inaccurate policy improvement (the greedy step, e.g., Eqn. p in the Actor update. Then we have that
1 Je+1 8xt Jo 1 T (b)*))
v. (J Ej,1) (v. T(v)) - ET,)
e1 J (v. T(vi)) EE,,(V1 T(v)) (Jr: E
Exact Newton Step
Perturbation
A V: v, (v. - ((ve)) +
Exact Newton Step
1++1 + Es.
nutshell, we have that
1 =- = + Ec,t + Ea,t.
where
Eo,t EEpler-- -((v:) (J=,' + ETt)
B PROOF OF BERNSTEIN'S INEQUALITY WITH GENERAL MAKOVIAN SAMPLES
In this section, provide the proof of Bernstein's Inequality with General Makovian samples following the proof in Theorem (Jiang et al. 2018).
With bit abuse of notation,let denote the stationary distribution of the Markov chain (X,)221- We define <hh) = f h<=)=<d)) to be the integral of function with respect to π. Let 22(T) = {h (h?) < } be the Hilbert space of gquuare-interalle functions and C2(T) = (h E C2
(h) = 0} be the subspace of mean zero functions. Let P be the Markov transition matrix of its
15

---

Under review as a conference paper at ICLR 2023
underlying (state space) graph and P be its adjoint in the Hilbert space. Let X(P) E |0. 1] be the operator norm of P on C2( TT) and (P) E [-1. be the rightmost spectral value of PP+P*)/2
Then the right spectral gap of P is defined as 1 X, (Levin & Peres] 2017) (We remark that in Assumption [ we assume the absolute spectral gap is non-zero, which implies the right spectral gap is also non-zero. This is true since -1 X I À I 1.). Let F² denote the multiplication operator of function e² + eh(x), In the Hilbert space L2 (T(),, define the norm of function h to be || / (h, h) Furthermore, we introduce the norm of linear operator T L2(T)) as || = (ll'hhh ||h]|= = 1}.
We first restate Bernstein's 's Incquality with General Makovian Samples ŞJiang et al. 2018 in the following theorem. Let ai (A) = (1 A)/(1 - A), (A) = 5/(1 X) and a2 (0) /3.
Theorem 3 (Bernstein's 's Inequality with General Makovian Samples). Suppose {X; (2) 1 is station-
ary Markov chain with invariant distribution क and non-zero right spectral gap 1- X, 0, and + x xi-c, c] is a function with x(ʃ) = O. Let o² = T(²²). Then, for any 0 S t< (1 - max(A (r. 05)/5c
and any > O.
n
S exp (-ai (max {Ar, 0}) x² + 02 (max {rr 0l) )e).
nc²/2
P
f(.)) >
(17)
Proof. Step 1. Establish the upper bound of Et VEETToO S(xo].
Let I x + 1 be the fucntion mapping x to and let II be the projection operator onto 1, i.c., g + (h, I <h)]. Define the León-Perron operator to be P.- > (1 >)],, E [0, 1). Then we recall the following lemma (Lemma 2, (Jiang et al. 2018 on the stationary Markov chain (Fan et al.. 2021a).
Lemma 5. Let { be stationary Markov chain with invariant measure and non-zero right spectral gap 1 - Ar > O. For any bounded function f and any t E R.
E ee' (222% f(Xi)] I | max
E1//2
Lemma 6 indicates that it is sufficient to prove the upper bound of E [e' E? SxXx]] by proving the
upper bound of |
Pimax(A...0 /igts//PmmxxA..... Ef Ets/2
To this end, we first invoke the following lemma (Lemma JTang al.
2018 construct Zn lim Et Etfe/2
such that for any X E [0, || 1 /
Lemma 6. For function f x E 8 + x c) such that T(f) = c, π (f)) 02. Let [.] be the ceiling
function and Fa(z)) f(a)te c/3k
- 141/5k Then Fx takes at most 6k + possible values and satisfies that for any bounded linear operator T acting on the Hilbert Space C2(T) and any E R.
35 -c. Let ft = Je [c-)(1e)
|| 14/2TE
||
E fal22
lim ko
Assume that the Markov chain {.i.e21. E X' is generated by the León-Perrow operator Px. It follows that (fth21 = (Xx:)<)) is Markov chain in the state space y fa (2). We recall the following lemma (Lemma 7, (Jiang et al. 2018)) on the relation between the two Markov chains.
Lemma 7. Let PA be the León-Perron operator with À E [o, 1) on state space X. Let f be function on X. On the finite state space y = {v E f(X): : T(f f(x) = yt) > 0}, define a transition matrix Qx = AI +1 A)IUT with transition vector μ consisting of elements a(xx f(x) = v}) for yiny. Let E denote the diagonal matrix with elements etv : E y. Then we have,
12 (///2/Et///11
12/22xE
16

---

Under review as a conference paper at ICLR 2023
1 / by the expansion the largest eigenvalue of the perturbed Markov operator E P as series Specifically, we recall the following result (Lezaud 1998).
Next, we bound the term
Lemma 8. Consider a reversible, irreducible Markov chain on finite state space X. Let D be the diagonal matrix with (f(x) x E }} and ( "D /m for any m 2 with D = T. Assume the invariant distribution of the Markov chain is π and the second largest eigenvalue of the transition
matrix P is Dy < 1. Let = (2][TC) -1- -xx))=++
for some Oo such that
(<(m) S || c0-00 vm 2
Let Zo -I1, Denote the largest eigenvalue of PE by B(t) and Z (1 P P II. Z65
-2, j
2 (() and ((m), m be
g(m)
=
m
1
Σ
trace (T(n))z(h) T.(())) z(hp!)
P
m, ki Then we have the following expansion on ((t).
p=1
t2
tho=p-1,k220
B(() = Σ
3 m pm 14 < la-
m
Follow the same line as in (Lezaud 1998) (Page 854-856), denote x² =²=10 =1f and c c= co 2 ||| D|] (defined in Lemma 8). then we have the following upper bound of B(t).
B(t) = 3((0) + g(0 + Σ 8 mm
m=2
(fm) t
o
Xt
5ct
m-1
+1+0+
m!
5c
Ax
8
(fm) pm
0C
2 Xt
5ct
m--1
S exp
m!!
5c
dr
o² Xt2
S exp
tc -1-tc)
+
Xr - 5cl
exp(s1(() (1) 92(1))
(18)
Now ready derive the bound for the term E [et fx(x.). Following the results in Lemma we consider a sequence of f such that,
111 P E
lim ft / P g f fr/all
Next, we construct the finite state space counterpart of each pair of ix/ 12 PA wts/ and π by Lemma
7 i.c..
22 E f+/2 :- =111E
Let the random variable in the state space Vk be Yk, then the mean and variance of Yj is
Eyen, x (f== fe(x)) = =>}) (fe) 0 and Eyer, (fo: fa( = w}} x² = s
For each k; applying Eqn. 18) gives us
fz
2t2
FDON < exp
(6 -tc) + 1 Xr 5ct
17

---

Under review as a conference paper at ICLR 2023
Note that as h + oc, we have क
Pb + xf2) = o². Then we have the upper bound for each
operator
i.c., for any E (0, (/5//P,,'1
S exp(sn + +2((1)
where 9i and 92 are defined in Eqn. (88)
Consequently, obtain the upper bound for E [et [((x)]] as follows, E [ R(X.)). E7 - f(00)]
("22² (c - 1 tc) + 1- mmx Ar, 0} 5ct
no²
no² max { (Ar, 0}{²
S exp
d2
Step 2 Use the convex analysis argument derive the Bernstein's Inequality.
We first restate the following lemma (Lemmaa 9, (Jiang et al. 2018)) on the terms 9 and g2.
Lemma 9. For À E [0, 1), let (1( = " (e - tc) and 92(() =
no² max max 0)x2
then for
--max((,..) 0). -cct"
any 0 S (1 /cc the Frechet conjugates (91 92)" satisfy the following inequalities.
e²
(1+
5ce
sup if E (0,1): (g) + (c) 0gt<(1-A)/5c
fle - (1) (2)) 2
2
1-x
+ 1-X
if 0: (01 + 92)" (c) (c) 2 2
0 0E CE
2
3
By the Chernoff bound, we have,
- -log
(X,)) -0 Σ Am1
2 n x sup (te (t) - 92(())
n
IER
Notice that gi (t) ( and g2()) 0(12) as 0, then for some
have le gt)
(2())= > 0. Meanwhile, when S 0, we have le - (t) (t) < 0. Thus, we can obtain that,
sup {Le g1 (1) (2) : 0} sup (1e- (1) (2) : E IR. = (01 + 92)" (c).
Letting À max (Ar, 0}, (A) = (1 + ()
- a2) = 5/(1 >) and a2 1/3 yields. ne²
n This concludes the proof.
Σ (x))) S exp (-a, (max {Ar 07) 0² + 02 (max (Ap,0)) cc
sexp
(19)
C PROOF OF PROPOSITION 1
Let W++1 = [T((#+1), and assume [ a)ll < uniformly (see Assumption I
Based on the
approach in Appendix G.1 (Fu et al. 2020), it suffices upper bound ||w2+1 4 2- Observe that
||w++1 W1+1ll2 < -1000 ølll2 || ||ō ull2 + 1
11 10
where & and are given as follows:
き- =
& (st, (st, (
1=1
(Epr
[0(x, a)) ()))
N
① =
(1
7)
Y Pns + 7"' Qui (s),,, (m)))))))) o (st.m alm)
N
1=1
E
(1-7)
(7 + PT Qui (Sms am)) 0( M(0m, am) am)
ptt1
18

---

Under review as a conference paper at ICLR 2023
Recall that the following assumptions are in place: (1) Spectral norm [| a)ll S 1, Φ a) E R (2) |r(s, a}l I Tmax and F = Eg, a); (3) || l22 S R and (4) the minimum singular value of the matrix Ep a)((s, J) t 2 is uniformly lower bounded by o². can be shown that || _.4.
Next, we derive the bound by appealing to Bernstein's 's Inequality with General Makovian samples. Following Theorem 2 (Jiang et al. 2018) (The proof of Bernstein's ' Incquality can be found in Appendix B). let be the invariant distribution (which is relevant to the current policy T&) of the stationary Markov chain {ra] Suppose that it has non-zero right spectral gap 1 X > 0. Let of ( (dr). Then, we have that for any 0:
mc² /2
Ps.
Σ 1=1
(ri F) >
S exxp
on (max (Ar, 0}) o² + 02 (max (Ar, 0}) Timaxe) (Tai
if ===0
where (A) = x
a²(
5
if E (),
1-A
We conclude that with probability at least p.
ag (max {A,.03} Imp² 2ma, (max {),, 0}) Inp as (max fAr, 07) lnp
F == Fm.
m
1=0
It follows that with probability at least - p.
| S (1 - 7mm + + n R,
Further, note that
||o1|2 5 (1 - (1 +7 R.
Since the minimum singular value of --1 is no less than 5 w.h.p. when N is large enough, we have that
|101|2 2
For convenience, define
N X
(3), ar) (8L, (
X 2 (Eper [o(s,a)o(s,
1=1
and define
N
2 2 - X =
Sz:
(20)
1=1
Sk A (d -X), N
(21)
where St, k = 1, ... N are independent. Next, we derive the uniform bound on the spectral norm of each summand as follows: 2
|| I XII S (1 II [|x]) S N
To this end, we bound the matrix variance statistic V(Z):
V(2) (
Σ E|
19

---

Under review as a conference paper at ICLR 2023
Note that the variance of each summand is given by
E k
=
N2
E| f1llbul1? "p0"" T - -60xx - X - xx
N22
E L
| - -x
N2
X.
N2
Combining the above, we conclude that
1
0
E X.
N
Observe that
||||| = | 1Ill2 S E 0l ||| =
Ello1 S 1.
Since the spectral norm is the variance statistic given by appealing to Bernstein's 's Inequality, we have that
v(Z) - N
|X||
-t²
P( 2 1 <2dexp
X
+
2F
N
3N
2
2
E ||| SV
|| log(2d) + log(2d)
N
3N
2 log(2d) +
2
3N (2d(..).
N
This is to say, with probability at least 1 - p/2, the following holds:
X -XX111= <
2
log
+
4
log²
P
2
log
P
3N
4d
9N2
4d
N
4d
In a nutshell, we have that
$ $ 1
=118 1 - 112
= 188-((8 - -X)X 112
= [ - x2)012
2
( 118 - -xl12
4
(3.
2
log
P
+
log²
p
log p
VN (a+)3
3N
4d
9
4d
N
4d
Similarly, the following inequality holds with probability at least 1 - p/2:
82
+ 1) where d is the dimension of vector s, 81 satisfying
| 10-012 5 3
log 2(d
p
+
V
9
log²
2 + 1)
p
-28g log
2(d + 1)
2/4 ((1
(F
+ F) + -27 m R) and 82 |E u
82 < - ((mm (lim - Fl + m =())
7 Immax + 7 R' F/.
20

---

Under review as a conference paper at ICLR 2023
Summarizing, we have that
| @t+1ll2 ll2 -
1
110
-
u12 +|
1 -10012
$ 30
81 log
2(d + 1)
p
VV
87
log
2(d+1)
p
+ 1)
28p log
2(d +
p
4((1 - 7m + t))
2
4
2
log
log
2
log
VN(o')²
3N
4d
9N2
4d
N
4d
which indicates that with probability least 1 1-p,
4((1 7m + + R))
4
P
2
p
Qwn+s Quoti
log
log"
log
VN(o*)2
3NV
4d
V
9N22
4d
N
4d
ccQ
(22)
Remark. In the case when Assumption [ does not hold, i..., we have
inf
E. y( : o) (s, a)] C1.
GEN
where e₁ 0 a constant. Let W (()+)))) ) recall that a denotes the solution of Eqn.
8
and
denotes the sample- based solution, then we have
14a+11 - Qürtnl = ci
From Eqn.
22
we obtain that,
Quii1 QQ1111 SeQ Eq
Then the difference between the sample-based solution and the underlying true solution of Eqn.
is,
1Qmm Qiecn S EQ c1.
Note that when Assumption 1 Tholds,
Qatti = =Qi141
D PROOF OF LEMMA
Recall 3= fk,t O..t E[Ck.]] - E[fx.r] We also have the following definitions:
C 11/l > (Qun,, (st, (ails.) Qür.. (st, Voro,
Ck,1, 1 Σ
(or QTO (s,, VoTOL (allss))))
faLe 11/l Σ
The (si, a; V VOTO, (ailsi),
1=1
CK. 20k,,1 + +Ck.12
Next we evaluate Elll + Ck. - E(Ct,) el as follows:
[1 + Ck E(Ck.r) E(
=(She + Ck,) + Ct,)) + (E(Ck..) + E(fe.)) E(fx,)))
- -((kee (E. B[fx,)))
S(fki CK.((f. + Cx,)) + =(f..))
(23)
21

---

Under review as a conference paper at ICLR 2023
Note that Ck, and fa.e both bounded above since Q-function is bounded and (aT)(als) is bounded (see Assumption 4 ie., [V sCpp
2
[[Q(s,)]I - 7
Σ Tmax Tiax
Then we have the following bounds for CR,t and fk.e
|| 2C,. Tmax
llfk,ell S Ceb 1
Tmax
Taking expectation over both sides of the inequality 23 we have that
El ||| [[Cr,d] + elf + El(fa, CR,)) Ck ".
Let M, and /² E((ffe, (a,e) C Then we have that
|[||a|] < M, || +o",
where depends probability p as indicated in Eqn. (2)
E
PROOF OF LEMMA 2
Recall that b b= E(Ck.t) and
C == + Ck
-1/1 Σ
(Quen (8i, VoTT, (ails)) - Qüe (8i, VoTO, (a.ls:)
7=1
(Qüsz (8ts as) VerTe, (a/ls,) QT (,), (c(ls)))
Next, we evaluate ||b|[2 Observe that (see also Appendix D
Tmax
||C s 20 1 1-7
Let ( 2 1- ||. Then we have
|bb| = |E[Ck,,]1 E[
F PROOF OF LEMMA 3 AND LEMMA 4
[Lemma 3] Given Critic parameter w in the objective function, it can be seen that Vh(u,, 0) Vh(w, 0')ll < Q VT V |I. Since value function is bounded (e.g.. Qmax) and the score function V is Lmoohh (ref. Assumption 6), the constant in Assumption 4 can be easily determined by L QmaxLeg
[Lemma 4] Since the objective function is finite, let hmax maXa h(0,w), h maax maxg=0- h(0, ((0,w), In the case when the gradient is non-zero, let gmin ming Vh, then can determine 1
Pmna > 0.
G PROOF OF PROPOSITION 2
Observe that the Actor updates use the biased stochastic gradient methods (SGD). For simplicity, we adopt the following notations to study the Actor update:
0k+1 0% a (VV(w,, 0x) + b(t) (())).
(24)
where b(t) E(Cr.]] is the bias, the step size, and
== fk, + Ck E(Cr.l] E(fe,.]
the zero-mean noise. Note that the objective function h(w, 0%) is a function 6. Denote the optimal value (in this iteration of the Actor update) by h(w,,0").
22

---

Under review as a conference paper at ICLR 2023
We prove the following lemma the modified version of the descent lemma for smooth function (cf.
(Ajalloeian & Stich 2020; Nesterov )003)).
Lemma 10. Suppose Assumption and hold. Then. for any stepsize a Σ [M,++)] the following
inequality holds with probability at least p:
a L²L 0² 2 2
[lb(w, 0x+1) hww, 0x)]
[VVh(w,
Observe that under the Pl.-condition (Assumption 4. we have the following recursion:
a²L 0².
(w,, 0c+1) hww, 0²) - (1 ax) 0k) hew,, 0*)) + 2 -
(25)
2
By applying Eqn. 25 recursively, obtain the desired results in Proposition 2
H PROOF OF PROPOSITION 3
We first prove the following lemma on the relation between Actor parameter 0 and the objective function h(w,0) 0).
Lemma 11. There exist a contant Ln > and an open ball S,(0;) such that for any 0, E (ot)
the following holds for any > O.
E Ell n" =']] S Ln ((w.)))).
Proof. By Taylor's expansion, we have
luw,, 0*) = huw, 0,) + (l( - 0.) + o(110; Ocll). Condition, it follows that Vhh 0) 2 2p(h(w, 8*) h(w, 0)) = Lg for all O. Note that Lg > 0 when 0 + 0" Then have that
Since h(w,)) satisfies
h(w, 07) - h[w, 0.) = [WW( (0) 0.) + o(110- 0cll)l
2 Vh (w, 0,) (6)
0.)1 - Io(110 0,1D)
2 I.g 10 Oell T.. 0ell
= (bn l0. Oell.
where the last inequality the fact that there exists such that when ||0, 071 S |o(110; 0,113l = To 10 ll, To Tig.
Taking expectation over both sides gives
E[h(w, 07) hww,
=(Lg - Lo) Ell0 - 0ell
2(4g L.) E 0.l1
Then conclude that the parameter of interest Lp.
CN
LA
0.
Lg
Lo
where C₁ is defined in Assumption
We are ready to present the proof of Proposition 3 Based on the definition of Ej,, and & we derive the upper bound for each term respectively.
Ej = - -P =(I PP...)) 1-1 (yPr.. PP (I P
(P
Observe that value function a is smooth and upper bounded. We denote the smoothness parameter by Ly, the upper bound by || < Viaxx and the smoothness of the reward function by Ly.
By taking the norm both sides and applying Assumption 3 and we obtain
||& |1 < 2 T, Tue Me+1
#
TV- TT-
23

---

Under review as a conference paper at ICLR 2023
Further, observe that
E = Tast1 + P 0a (rrmm + Preet )²
Pit+1 Ph (PPret) Preei )
By taking the norm of both sides and applying Assumption
5 we obtain
||& = || - Ta++il |l + ( Pre,) )0011
(L, + > #1t1llVV
:= LT Lmax
Recall the definition of & given
& = - ( - - + Eg,(
Taking the norm and expectation on both sides yields that
|[ < E|| =E |1 T(x**)) + Joh Ep, + E
< Ell T++1 [|[]],
where Lg = (2V K + L.Pa) M I. L, + ML,, + +V/aax > is constant. Since Met1 = T741 the greedy solution, we thereby complete the proof of Proposition
I PROOF OF THEOREM 1
Following the value function update rule, have
y .t4:
0h (J (v*1 Ex)
0 (I(t) + Ei)
= x ((t).
Then, the difference between ac+1 and w² is given by
a² v # =0" at + J (n T(x)*)) + E
(26)
Observe the following result holds for any t..
(v - T((**)) (v" -(v")) > J (0 v²).
(27)
Recall our decomposition of the value function update is given as L(t) C(t) +
Č(t) E(C(()
+ -
Martingalc Difference Noise: A(te)
Bias: B(t)
Plugging Eqn. 27 into Eqn. 26
obtain
e Rels
=0" f + 0. - )) (T +
(I J Jot (v" -²*) + BBt) +N((t)
=YP (v" a²t)= + B(t) + +t))).
Taking expectation on both sides yields that
Elp" 3e4
u 27
P Mets (v" (u" " + B(t).
24

---

Under review as a conference paper at ICLR 2023
Applying the above inequality recursively gives that
E [00 -
27
E
Prott-1
(00 - (0--00 070)
]]
1-1
+
E
P Pieni
(Bit - (()(t-)))-- B(t)
1=1
1=0
1+
Po-1(0- -000000~00 + Σ -)) B(),
-00)++
(28)
with PA+ E [ITioo Pr., Pi .) Taking norm both sides of Eqn.
28 yields the desired
results.
J PROOF OF THEOREM 2
Based on the update rule of the value function, we have
v =J Jine (v" v²x) ) + J (v T(v*t)) + E
SJ 6, Jo, (v" xx*) - J Ju (0" 0 El
SJ [Jo. - Jo- (v" - - ) + Et:
which implies that
E'v-
v +r+1
1 J [Jo. Jo- (0= - ) + B(t).
Then, taking norm on both sides of the inequality above gives
Elv" 21 *]| S $1 [Je. Jo-1 (0" 0ḥt) + B(t)ll-
(29)
Let H, 11, Jss Jo-] ||. It follows from Assumption that
H. s MT 0²
where L, is defined in Assumption 5
Hence, we have that
E 0 +++
w'll b. J1l - Jo- 11| - v² + [IB(t)]
(30)
By applying Eqn.
30
recursively, we conclude that
E|p
II km0
Hi-
|E[ - 00 ]|1 + Σ
II Hi-j
[[B(1 - i)ll [|B(||]-
1m1
K EXPERIMENTS
A Summary of Theoretical Results. This work aims to provide a comprehensive answer to the question of "'whether and under what conditions online learning (e.g., the general algorithm like AC) can be significantly accelerated by warm-start policy from offline RL". Our key observations are as follows.
(1) Our results in Theorem and Theorem 2 point out that the warm-start policy goes hand- by-hand with the approximation error to influence the learning performance (see the table below for the summary). The intricate relationship between the warm-start policy and the approximation error can be identified by studying the structure of the bounds in Theorem 4 and Theorem 5, where the warm-start policy not only has impact on the first term (e.g., 0" =0 ) but also the bias propagation through Ho == || [Jon Jo-] ||. Meanwhile, the biases have impact on the effect of the warm-start policy (the first term in the bounds) through H, directly.
(2) In Theorem 1, we point out that the bias terms have direct impact on "whether the warm-start policy is able to facilitate the online learning". For instance, "even when the warm-start
25

---

Under review as a conference paper at ICLR 2023
policy is nearly-optimal", there is still no guarantee that online fine-tuning can improve the policy much if there exist biases in the approximation errors in online Actor and Critic updates and these biases are not dealt with properly. To clarify further, consider the case when the bias is always positive, i.e., B() > O for all & 2 0, the lower bound is always positive and bounded away from zero.
(3) In Theorem 2, we aim to answer the question: "under what conditions online learning can be significantly accelerated by a warm-start policy?". Consider the case when the approximation error is unbiased (such that the A-C can be viewed as the Newton's ' Method).
||0" - v=a ||, which can decrease Clearly, we have ||E[ - =0'] & (T--HH--))
quickly as long as the warm-start policy Ta not far away from the optimal policy x² and also satisfies Assumption 5. Intuitively, this result shows that "the imperfections of the warm-start policy can be 'washed out' by the (superlinear) Newton step" and corroborates with the observation in the very recent literature (Bertsekas, 2022b.). We remark that this phenomenon has not been formalized by previous works on the A-C algorithm.
B(t)
|[((t)] > 0
when the distance be- tween To and n²" is small
The warm-star start can facilitate the online convergence (Theorem (
Biases can throttle the convergence significantly due the accumula- tion effect (Theorem T (Empirical
(Empirical (tudies et al. 2017:2018)
studies: Uchendu et al. (2022))
when the distance be- tween To and n² is relatively large
The impertections of the warm- start can be "washed out" by on- line learning (Theorem Eqn. (30)) (Empirical studies: Bert- sekas 2022b)
The warm-start policy goes hand-by- hand with the approximation error to influence the learning performance
Empirical Results. We consider experiments over the Gridworld benchmark task. In particular, we consider the following sizes of the grid to represent different problem complexity, i.e., 10 x 10, 15 15 and 20 x 20. The goal of the agent is to find a way (policy) to travel from a specified start location, e.g., the red square in Fig. 3 to an assigned target location, e.g., the red hexagram in Fig. 3 such that the (discounted) accumulative reward along the way maximized. Specifically, the action space contains 4 discrete actions, namely, up, down, left, right, which are represented as 1,2,3,4 in the algorithm, respectively. The reward in the goal state is defined as 10 and in the bad state e.g., the black cube in Fig. Bl is -6. The rest of the states result in the reward -1. The discounting factor is set as 7 = 0.9. We consider the grid with 10 rows and 10 columns such that the state space has 100 states. The transition properties of the environment is as follows: the agent will transfer to next state following the chosen action with probability 0.7; the agent will go left of the desired action with probability 0.15 and go right with with probability 0.15. For each experiment, the shaded area represents a standard deviation of the average evaluation over 5 training seeds.
Specifically, we consider the following A-C algorithm to solve the Gridworld benchmark task,
Critic Update: The Critic updates its value by applying the Bellman evaluation operator (?") for m-times (m > 1), i.e., given policy n, the 1-th step A-C update.
ett + 1) =
(31)
Actor Update: The Actor updates the policy by greedy step to maximize the learnt v value, i.e.,
n' = arg max T (v(( + 1)).
(32)
Impact of the Warm-Start Policy, We first consider the impact of the Warm-Star policy in the ideal setting, where both the Critic update and Actor update is nearly accurate as in ADP. In this case, we let m be large enough, e.g., m 1000, in the Critic update Eqn. (3T). As observed in Fig. a 'good' Warm-Start policy can efficiently accelerate the learning process, e.g., it only takes two iterations to convergence with a Warm-Start policy. Meanwhile, in all three cases, the performance gap [t) - o'|l decays over time which reflects our discovery in Theorem 2 Specifically, when the Warm-Start policy is not 'good' enough (or even Warm-Start), the A-C algorithm can still be able to improve the learning performance overtime (see e.g., the first term on the right side of the upper bound in Theorem 2)
26

---

Under review as a conference paper at ICLR 2023
Impact of the Approximation Error in the Critic Update. We evaluate the impact of the approxi- mation error in the Critic update on the convergence behavior by two approaches. (1) First, we study the Critic update with finite time Bellman evaluation, e.g., 500, 50, 20, 5. As shown in Fig. 5 the inaccurate Critic update impacts the convergence behavior as expected. The case when m = shows that the finite time Bellman evaluation may contribute the slower convergence. (2) Next, we consider the general case when there is approximation error in the Critic update. In particular, we add the uniform noise e(t) the value function with different bias, cle(.E
0.5, 1, Meanwhile, we also consider the case when the bias can be either +0.5 or - 0.5 in the learning process, e.g.. E(e(t)] = 0.5 with probability 0.5 and Eje(t)] = -0.5 with probability 0.5. The resulting convergence behavior is presented in Fig- 6 Notably, it can be clearly seen that both the positive and negative bias may result in an error floor and 'prevent' the algorithm from converging to the optimal (e.g., the last two terms of the lower bound in Theorem (T). The experiment results in Fig. (6 corroborate our theoretical findings in Theorems
and
Impact of the Approximation Error in the Actor Update. We investigate the learning performance of the A-C algorithm under inaccurate Actor update. In particular, we add the perturbation on the learnt policy in Eqn. 32 as follows,
(olicy(s), Policy(s) = (aandi(],, (),,) 1 -
P.
where Policy(s) denotes the action should the agent take at the current state s following the learnt policy and randi([1, 4]) is random function to choose the action 1, 3, uniformly. Thus, with probability p. the agent will choose the action follow the current policy while with probability the agent will choose random action. By setting different p. we show in Fig- thhat the approximation error in the Actor update may significantly degrade the learning performance. Mcanwhile, Fig. 7 also indicates that decreasing bias can be helpful to improve the learning performance (see the red and green lines in Fig. 7p. This observation also verifies our results in Theorem
L OFF-POLICY A-C ALGORITHEM AS NEWTON'S s METHOD WITH PERTURBATION
We note that the actor and critic updates in Eqn. (9) and Eqn. (8) are general template that admits both off- and on-policy method. More specifically, denote the target policy by mar and the behavior policy by Taky- When the off-policy menthod is used, then the updates in Eqn. (9) and Eqn. (8) are given by
W++1 +- arg min (e. [Qu (8, w To
E
(a) x Gridworld.
(b) x 15 Gridworld.
(c) 15 15 Gridworld.
Figure 3: Gridworld benchmark with different sizes. The colors specify the 'goodness" measure of the state, i.e., the darker color cubes are with lower v(s) value and the agent should avoid those areas. The horizontal lines and vertical lines in each cube point to the direction the agent should take, i.c.. policy at every state. Fig. 3(a) Fig. 3(b) and Fig. 3(c) show the learning results after 50 iterations of A-C update.
27

---

Under review as a conference paper at ICLR 2023
Learning Performance
Learning Performance
Learning Performance
100
100
Warm-Start
Warm-Start
Warmm
Warm-Start with one fteration
Warm-Start with one fteration
80
Warm-Start with one Iteration
Warm-Start with two ieerations
Warm-Start with two ilerations
Warm-Start with two iterations
40
[|vit)-v/I
||vit-vv|/
20
20
0
6
8
10
2
4
8
10
2
8
10
Iteration
Iteration t
Iteration t (c) 15 x 15 Gridworld.
(a) 10 10 Gridworld.
(b) 15 x 15 Gridworld.
Figure 4: The impact of the Warm-Start Policy when no approximation errors in Actor update and Critic update. The convergence behavior given different initial policy, i.c., a random policy (no
Warm-Start), a Warm-Start policy obtained by running the A-C algorithm for one iteration and two
iterations. The æ-axis represents the A-C update step and y-axis is the value of the norm ||x(t)) "
Learning Performance
Learning Performance
Learning Performance
100
m-550
m-500
m--500
60
m=50
60
m=
80
m=50
[[vi)-- 11
m=5
[|vttt-v ||
m==5
[|vitt-vil
m==5
40
40
20
20-
15
15
Iteration
Iteration t
Iteration
(a) 10 10 Gridworld.
(b) 15 15 Gridworld.
(c) 20 20 Gridworld.
Figure 5: Learning performance vs. rollout length.
Learning Performance
Learning Performance
Learning Performance
100
120
bise
bise
bisa
bies 0.5
bics 0.5
bics
bics 1
bias
bies--1
biese-0.6.t0
[[vt))vv
60
bies--1
bie5s00.5.+0.5
[|vit)-vi]
bass-1
bras=-0.5 0.5,00.
40
20
20
20
10
15
20
15
20
Iteration 1
Iteration
Iteration
(a) 10 x 10 Gridworld.
(b) 15 15 Gridworld.
(c) 20 20 Gridworld.
Figure 6: Illustration of the lower bound in Theorem
Learning Performance
Learning Performance
Learning Performance
100
No
No
No
80
80
p=
p
[[v0)-V]
40
D-0.2
[|vtt-v/|
60
D-0.2
[|vttt-vll
60
D-0.
40
40
20
15
20
10
15
20
10
15
20
Iteration t
Iteration
Iteration
(a) 10 x 10 Gridworld.
(b) 15 x 15 Gridworld.
(c) 20 x 20 Gridworld.
Figure 7: Convergence behavior vs. Approximation Error in the Actor Update.
28

---

Under review as a conference paper at ICLR 2023
T+++1 < arg max E (s.a))=pma) (uu+t, (s,
This is in contrast to the updates given below when the on-policy method used:
We+1 arg min F [Qustayyy (8. w <b(s a)) "0(s,a))
TE+1 < arg max (a(r)))p [Quetr a)]
One major challenge of the off- oolipolicy analysis lies in the fact that the behavior policy can be arbitrary Sutton et al. (1999 Sutton & Barto (2018) and hence impossible to develop unifying framework. For example, the behavior policy can be obtained by human demonstration (a similar idea used in an early version of AlphaGo), deriving from the target policy in Q-leariigg/DQN
from previous behavior policy. Meanwhile, the key drawback of off-policy method is that it does not stably interact with the function approximation and is generally of greater variance and slower convergence rate Sutton & Barto (2018). 8). In this regard, modern off-policy deep RL requires techniques such as growing batch learning. importance sampling or ensemble method stabilize the algorithm. Thus, for case of exposition, we only include the on-policy analysis in our work.
Our framework and theoretical results are able to be applied to off-polios setting with the extra assumption the behavior policy. In particular, the neighborhood of the target policy, i.c., in each Actor and Critic update step,
assume the behavior policy is in
|[Enhvttr,eel = M L Tbhv, < Cht, where Ctu 2 0 is constant. In this way, setting as a Newton Method with perturbation, i.e.,
write the A-C update in the off-policy
Uxnr1+11 = - Mo (Vmunt ()) - E,,,
where & is the perturbation which captures the approximation error from Actor update, Critic update and the behavior policy. Explicitly, we have the perturbation with the following form.
Rets & = Ev,t + ( - (Fre.s + +yP P x(11)) - (E + Eshe tar,t + 7EEr + Ebhro t
Thus, the off-policy analysis is similar to the on-policy case but with the "error' induced by the behavior policy.
M ONE-PAGE REVISION (SEE NEXT PAGE)
29

---

Under review as a conference paper at ICLR 2023
Assumption
Characterization of Approximation Errors In the Cribic Update
Characterization Approximation Errors In the Actor Update
Projection on the Crètc parameter spase
Lomma
Lemrna
Assumption
Proposition
bourded Noise
Assumplion
[
-emoollhrees)
Proposition
Base function Crttic update
Approximation Error In the Critic update
Scare function the Actor updale
Approximation Enro Actor update
Lemma
Acsumption
bounded
j- PL Condition
Reward and state Iransition matrix
Proposition
Upper bound of the bisses (B(n)
Theorem
Theorem 2
The Lower Bound of Ely
The Upper Bound of Bly yfv!l
Impact Approximation Errors and Warm-start Policy on Finite time Leaminng Performance
Figure 8: Illustration of the theoretical analysis.
In Section 3. We add the illustration of the theoretical analysis Fig. to make this work more accessible to broader audience.
In Section 4. We add Table to summarize the key observations from our main results (Theorem) and Theorem
B(() -
|B((] >
when the distance be- tween To and n² is small
The warm-start can facilitate the
Biases throttle the convergence significantly due to the accumula- tion effect (Theorem T (Empirical
online convergence (Theorem 2}
(Empirical Suudies/Silver al.
2017)
studies: Uchendu et al. (2022))
when the distance be- tween To and n² is relatively large
The imperfections of the warm-
The warm-start policy goes hand-by- hand with the approximation enror to influence the learning performance
start can be "washed out" by on- line learning (Theorem 2 Eqn. (30)) (Empirical studies: Bert sekas 2022b))
Table The learning performance given different warm-start policy and biases setting In Theorem 1, we point out that the bias terms have direct impact on "whether the warm-starl policy is able to facilitate the online learning". For instance, "even when the warm-start policy nearly-optimal", there is still guarantec that online fine-tuning can improve the policy much if there exist biases in the approximation errors in online Actor and Critic updates and these biases are not dealt with properly. To clarify further, consider the case when the bias is always positive, i.e., BBt) lower bound is always positive and bounded away from zero. In Theorem 2, we aim to answer the question: "under what conditions online learning policy?". Consider the case when the approximation error is unbiased (such that the A-C can be viewed as the Newton's Method). Clearly, we have [E(pa111 o'lll (I-:ooH--))
for all 2 0, the
be significantly accelerated by warm-start
||0 8 []. which decrease quickly long the warm-start policy To is not far away from the optimal policy N²" and also satisfies Assumption 5. Intuitively, this result shows that "the imperfections the warm-start policy can be 'washed out' by the (superlinear) Newton step" and corroborates with the observation in the very recent literature (Bertsekas, 2022b.). We remark that this phenomenon has not been formalized by previous works on the A-C algorithm.
30


Reviews:
[{"review_id": "y6J47K9kHS", "reviewer": "Reviewer_gGbf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the influence of warm-start in actor-critic algorithms. The authors provide a finite-time analysis of the impact of the approximation error and the sub-optimality of the initial policy. ", "summary_of_the_review": "I don't have any other major comments besides the comments above. Here're some specific questions. \n\n- What's the rate of $\\prod_{i=0}^t H_{t-i}$ in Theorem 5? Should we expect it to be decreasing exponentially fast w.r.t. t?\n- What does the `warm start' exactly mean? Does it mean by eq. (8) we could get a closed-form solution of the critic update instead of a one-step update? If that's the case, the analysis should not be claimed as a single-time scale analysis since the critic is updated completely until the actor update.\n- Again, compared with the closed-form update of the critic, can we use the two-time scale [1] update to provide more efficiency?\n- In the proof of Theorem 4, why does the first inequality after `plugging Eqn. 27 into Eqn 26 holds? How do we control the $\\mathcal E_t$ by $\\mathcal B(t)$ and $\\mathcal N(t)$?\n- The authors mentioned the actor-critic algorithm could be treated as a perturbed Newton method. Is there any relationship between this understanding and the natural actor-critic algorithm where [2] provides some theoretical analysis? It would be helpful to give some brief discussion.\n\nAfter all, I found this paper valuable and would suggest acceptance\n\n[1] Wu, Yue Frank, et al. \"A finite-time analysis of two time-scale actor-critic methods.\" Advances in Neural Information Processing Systems 33 (2020): 17617-17628.\n\n[2] Khodadadian, Sajad, et al. \"Finite sample analysis of two-time-scale natural actor-critic algorithm.\" IEEE Transactions on Automatic Control (2022).\n\n", "strength_and_weaknesses": "### Strength:\n\n- This paper is overall well-written and easy to follow\n- Treating actor-critic algorithms as a perturbed Newton method is novel and provides many helpful insights\n\n### Weakness\n\n- The proof of Theorem 2 is similar to the proof in policy gradient methods leaving some control of approximation error. The authors is expected to highlight why this analysis is novel given the existing analysis in PG.\n- The impact of warm-start is not fully addressed in the theorems. In detail, in Theorem 2 and Theorem 4, the sub-optimality $h(\\omega, \\theta_t^*) - h(\\omega, \\theta_{t-1})$ is exponentially decreasing, which is similar with conventional analysis in optimization. I wonder why the author emphasizes the term `warm start' in this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "oa12CFT9sJ", "reviewer": "Reviewer_7KE9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a theoretical understanding to the advantage of using warm-start in Actor-Critic (AC) type RL algorithms. The authors achieve this by establishing finite-time bounds of warm-start AC algorithms, which explicitly capture the impact of using warm-start. In terms of technical approach, the authors cast the AC algorithm as a Newton’s method with perturbation and bound the critic error and the actor error separately.", "summary_of_the_review": "While the authors use different terminology, the paper essentially shows that the initial condition shows up in the bias term (or optimization error term) in AC algorithm, which is a stochastic approximation algorithm, and hence using warn start can reduce that bias term. This does not seem surprising to me as similar results were well-established in stochastic approximation literature, with applications in SGD, RL algorithms such as TD-learning, and policy-gradient type algorithms. In addition, some assumptions are too strong. In view of these two points, I feel this paper in its current form is not publishable at ICLR.", "strength_and_weaknesses": "Major Comments:\n\n(1) The AC type algorithm the authors study is a stochastic approximation algorithm for maximizing the cumulative reward. In stochastic approximation, usually the finite-time bound consists of two terms, one is called bias (or optimization error), and the other is called variance (or statistical error) [1,2,3]. The bias captures how much away in expectation the iterates are from the desired limit, and the variance captures the noise error. It is well-known in stochastic approximation literature that the bias depends on the distance between the initial condition (e.g., the warm start policy in the case of AC) and the limit, and the variance depends on the batch sample size. While the terminology is different, It seems that the authors rediscovered this phenomenon in the special case of AC, which is not surprising. \n\n[1] Srikant, R., & Ying, L. (2019, June). Finite-time error bounds for linear stochastic approximation andtd learning. In Conference on Learning Theory (pp. 2803-2830). PMLR.\n\n[2] Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization methods for large-scale machine learning. Siam Review, 60(2), 223-311.\n\n[3] Agarwal, A., Kakade, S. M., Lee, J. D., & Mahajan, G. (2021). On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift. J. Mach. Learn. Res., 22(98), 1-76.\n\n(2) Some assumptions are too strong and can never be satisfied. For example, in Assumption 2, assuming the smallest eigenvalue of $E_\\rho[\\phi(s,a)\\phi(s,a)^\\top]$ is bounded below by $\\sigma^*$ is only possible for a specific $\\rho$ but not for all $\\rho$. Consider a $\\rho$ with an entry that is close to one and all other entries close to zero, the corresponding smallest eigenvalue of $E_\\rho[\\phi(s,a)\\phi(s,a)^\\top]$ can be made arbitrarily close to zero. Also, Assumption 3 (2) does not hold if deterministic policies are considered.\n\nMinor Comments:\n\n(1) Section 2 paragraph 1: I don't think the analysis allows for $\\gamma=1$. Is this a typo?\n\n(2) The paragraph after Eq. (4), saying that \"F can be viewed as the gradient of an unknown function.\" is not correct. Since the second derivative of $F$ (provided it is twice differentiable) may not be symmetric, F in general cannot be viewed as a gradient. It is well-known that value-based algorithms such as Q-learning are not stochastic gradient descent/ascent algorithms.\n\n(3) Eq. (5) is not clear. I need to go back and read (Grand-Cle ́ment, 2021) to understand this equation. Probably more details are needed.\n\n(4) Eq. (8) is confusing. The parameter $w_{t+1}$ is on both left and right of the equation.\n\n(5) In the statement of Theorem 1, on the left-hand side, since $Q$ is a vector, I believe the authors should use a suitable norm instead of an absolute value.\n\n(6) In the paragraph after Theorem 1, more steps of rollout can only partially decrease the error. In order to make the error arbitrarily small, one has to increase the sample size. Therefore, the \"either increase N or increase m\" statement is scientifically inaccurate. \n\n(7) In Theorem 2, why is there an expectation in a high probability bound? Also, where is $p$ in the bound?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "kSqj0LMWb2", "reviewer": "Reviewer_uKPa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a finite-time analysis of Actor-Critic (A-C) methods for reinforcement learning. First, the paper provides an upper bound to the error of the critic update due to function approximation and sample estimates. Then, it provides an upper bound to the error of the actor update due to approximating the greedy step with several steps of policy gradient, and due to the bias and noise coming from the approximation error of the critic update. Finally, the paper studies the error propagation through subsequent iterations of the A-C method, providing both a lower bound and an upper bound that relates the error to the value of the initial (warm-start) policy and an additive bias term.", "summary_of_the_review": "Since I am not familiar with the previous works in the finite-time analysis of A-C methods, it is hard for me to judge whether the contribution is substantial. Nevertheless, I followed the main steps of the error propagation argument, and both the assumptions and the obtained upper bounds seem pretty reasonable to me. Speculating on the novelty of the Markovian samples analysis and the explicit dependence of the final bound with the value of the initial policy, I am leaning towards a positive evaluation for this paper, but I provide a borderline score that reflects my limited confidence rather than clear weaknesses in the paper.", "strength_and_weaknesses": "After Discussion\n\nI want to thank again the authors for their clarifications and remarkable effort in improving the paper following reviewers' suggestions. Unfortunately, the discussion revealed some important concern over the result in Theorem 2: The upper bound still includes random variables, which means that convergence rate and sample complexity cannot be straightforwardly derived. Thus, I am updating my score to a slightly negative evaluation. However, I still believe that this paper will be a nice contribution with an additional effort to make Theorem 2 more informative.\n\n----\n\n\n*Strengths*\n- Providing a deeper understanding of the properties of A-C methods is paramount, given that it is widely used in practice;\n- The analysis consider the dependence between samples drawn from the MDP instead of the common i.i.d. assumption;\n- The main result directly connects the error with the value of the initial policy.\n\n*Weaknesses*\n- The paper is rather technical, tweaking the presentation to make it accessible to a broader audience could benefit its impact;\n- The warm-start setting does not seem to be crucial for the analysis;\n- The analysis consider expectations estimated through samples averages, but it does not specify how the samples are collected.\n\n*Comments*\n\n(Warm-start setting) From the title, abstract, and introduction, the reader is inclined to believe that the warm-start setting will play a crucial role in the analysis. Instead, from my understanding, the warm-start policy only affects the results through the value $v^{\\pi_0}$ in the Theorem 5. It is not clear to me whether it is essential for $\\pi_0$ to be warm-started, or the result would hold for a randomly initialized policy as well. Are the properties of the warm-start policy crucial for the analysis? E.g., does it matter that the policy is coming from its own optimization process, or perhaps that it displays good coverage properties as in (Xie et al., 2021)?\n\n(Samples averages and Markovian samples) The paper claims to introduce refined results that account for the dependence between the samples (called Markovian samples) rather than assuming i.i.d. samples, which is unattainable in practice without a generative model. However, it is not clear to me how the samples are actually collected. Do they come from a batch of episodes or a single long trajectory? I guess the former setting would further complicate the analysis, inducing additional bias and noise coming from the sampling procedure. For the latter setting instead: Why the divergence between the initial state distribution and the stationary distribution does not appear in the bounds (see Theorem 12 in Fan, Jiang, Sun (2021))? Are we assuming that the samples are directly coming from the stationary distribution here, so that we can neglect mixing considerations? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KF--YrESpe", "reviewer": "Reviewer_528u", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors take a finite-time analysis approach to quantify the impact of approximation errors on the learning performance ofWarm-Start A-C method with a given prior policy. By delving into the\nintricate coupling between the updates of the Actor and the Critic, the paper first provides upper bounds on the approximation errors in both the Critic update and Actor update of online adaptation, respectively,\nwhere the recent advances on Bernstein’s Inequality are leveraged to deal with the sample correlation therein.", "summary_of_the_review": "The paper seems to contain interesting results. \nThe overall presentation needs to be improved further. \nMoreover, the authors need to discuss more the advantage of the proposed analysis compared to existing ones.", "strength_and_weaknesses": "\nThe paper seems to present interesting results. \nIn terms of presentation, there seem exist some room for further improvements. \nIn section 2.2, the authors explain AC method, which is a stochastic RL method. \nHowever, when explaining how the error propagates, the derivation process uses a perfectly deterministic manner. \nTherefore, it is rather confuzing. \nThe same points apply to section 3. \nThe AC method is expressed in a deterministic manner with exact expectations. \nTherefore, the title of sections need to be changed and the discussions need to be changed. \n\nIn eq (10), it is not clear how hard it is to project parameters into the parameter space. Some discussions may be needed.\n\nIn Theorem 1, it is not clear if the result is for the deterministic update in eq (8) or it is for the batch-based stochastic AC in eq (10).\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject