{'fraction_non_alphanumeric': 0.061956841457870955, 'fraction_numerical': 0.01518838409498088, 'mean_word_length': 4.178343949044586, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation

Motivated by the widespread use of temporal-difference (TD-) and Q-learning algorithms in reinforcement learning, this paper studies a class of biased stochastic approximation (SA) procedures under a mild"ergodic-like"assumption on the underlying stochastic noise sequence. Building upon a carefully designed multistep Lyapunov function that looks ahead to several future updates to accommodate the stochastic perturbations (for control of the gradient bias), we prove a general result on the convergence of the iterates, and use it to derive non-asymptotic bounds on the mean-square error in the case of constant stepsizes. This novel looking-ahead viewpoint renders finite-time analysis of biased SA algorithms under a large family of stochastic perturbations possible. For direct comparison with existing contributions, we also demonstrate these bounds by applying them to TD- and Q-learning with linear function approximation, under the practical Markov chain observation model. The resultant finite-time error bound for both the TD- as well as the Q-learning algorithms is the first of its kind, in the sense that it holds i) for the unmodified versions (i.e., without making any modifications to the parameter updates) using even nonlinear function approximators; as well as for Markov chains ii) under general mixing conditions and iii) starting from any initial distribution, at least one of which has to be violated for existing results to be applicable.


Introduction
Stochastic approximation (SA) algorithms nowadays are widely used in numerous areas, including statistical signal processing, communications, control, optimization, data science, machine learning, and (deep) reinforcement learning (RL). Ever since the seminal contribution [28], there have been a multitude of efforts on SA schemes, their applications, and theoretical developments; see, for instance, [18], [7], [26], [1]. On the theory side, conventional SA convergence analysis and error bounds are mostly asymptotic-that hold only in the limit as the number of iterations increases to infinity. Nevertheless, recent research efforts have gradually shifted toward developing non-asymptotic performance guarantees-that hold even for finite iterations-for SA algorithms in different settings [26], [1], [15], mainly motivated by the emerging need for dealing with massive data examples in modern large-scale optimization and statistical learning tasks.
Targeting a deeper understanding for the statistical efficiency of basic RL (e.g., TD and Qlearning) algorithms, the objective of this present paper is to derive non-asymptotic guarantees for a certain class of (biased) SA procedures. In particular, we first characterize a set of easy-to-check conditions on the nonlinear operators used in SA updates, and introduce a mild assumption on the stochastic noise sequence satisfied by a broad family of discrete-time stochastic processes. We prove a general convergence result based on a carefully constructed multi-step Lyapunov function, which relies on a number (as needed) of future SA updates to gain control over the gradient bias arising from instantaneous stochastic perturbations. For an introduction to Lyapunov theory, see e.g., [6], [27]. We further develop non-asymptotic bounds on the mean-square error of the iterates. Finally, for direct comparison to past contributions, we specialize the results for general SA algorithms to both the TD-learning as well as the Q-learning with linear function approximation, from data gathered along a single trajectory of a Markov chain. We thereby obtain finite-time error bounds for both TD and Q-learning algorithms using (non-)linear function approximators in the case of constant stepsizes, under the most general assumptions to date. The merits of our bounds are that they apply to i) the unmodified TD as well as Q-learning algorithms (in sharp contrast, e.g., a projection step is required by [9], [4], [40]); ii) nonlinear function approximators and Markov chains having general mixing rates (bounds in [4], [29], [8] were derived based on linear function approximation and geometric mixing); and, iii) Markov chains starting from any initial distribution as well as from the first iteration (meaning there is no need to wait until the Markov chain gets "close" to its unique stationary distribution as required by e.g., [4], [29], [8]).
The remainder of this paper is structured as follows. Section 2 begins with the basic background on SA and the formal problem formulation. Section 3 presents the novel multi-step Lyapunov function followed by the main results on the non-asymptotic convergence guarantees for general SA algorithms. In Section 4, we demonstrate the consequences of our main results for the problem of approximate reinforcement learning (i.e., TD(0) and Q-learning using linear function approximators), and develop finite-time error bounds. Finally, the paper is concluded with research outlook in Section 6, while technical proofs of the main results are provided in the Appendix.
Notation. Throughout the paper, lower-(upper-) case letters denote deterministic (random) quantities of suitable dimensions clear from the context, e.g., θ (Θ). Calligraphic letters stand for sets, e.g. S, symbol (·) ⊤ represents transpose of matrices or vectors, and θ 2 (or simply, θ ) denotes the Euclidean norm of vector θ. We reserve notation such as c, c ′ etc. for some constants that do not depend on any parameters of the considered MDPs, including the discount factor γ, or size of state and action spaces, and so on.

Background and problem set-up
Consider the following nonlinear recursion with a constant stepsize ǫ > 0, starting from Θ 0 ∈ R d where Θ k ∈ R d denotes the k-th iterate, {X k ∈ R m } k∈N is a stochastic noise sequence defined on a complete probability space, and f : R d × R m → R d is a continuous function of (θ, x). In the simplest setting, for example, {X k } k is an independent and identically distributed (i.i.d.) random sequence of vectors, and f (Θ k , X k ) is a conditionally unbiased estimate of the gradient f ( Here, (F k ) k≥0 is an increasing family of σ-fields, with Θ 0 being F 0 -measurable, and f (θ, X k ) being F k -measurable. For an introduction to conditional expectation and σ-fields, see e.g., [10]. Depending on whether F 0 is a trivial σ-field, the initial guess Θ 0 can be random or deterministic. With no loss of generality, the rest of this paper works with a deterministic Θ 0 . In a more complicated setting pertaining to e.g., MDPs, {X k } k is a Markov chain assumed to have a unique stationary distribution, and f (Θ k , X k ) can be viewed as a biased estimate of some gradientf In both cases, we are prompted to assume that the following limit exists for each θ ∈ R d Taking a dynamical systems viewpoint [7], the corresponding ordinary differential equation Assume that this ODE admits an equilibrium point θ * at the origin, i.e., f (0) = 0. This assumption is made without loss of generality, as one can always shift a nonzero equilibrium point to zero by appropriate centering θ ← θ − θ * . Following the terminology in [7], [5], the recursion (1) is termed (nonlinear) stochastic approximation. Our goal here is to provide a non-asymptotic convergence analysis of the iterate sequence {Θ k } k∈N + generated by a recursion of the form (1) to the equilibrium point θ * of its corresponding ODE (3). The motivating impetus for considering recursion (1) was to gain a deeper insight into the classical TD as well as Q-learning algorithms [31] from discounted MDPs and reinforcement learning [31], [3]. It is a (biased) SA procedure for solving a fixed point equation defined by the so-called Bellman's operator [34]. As a matter of fact, a large family of TD-based algorithms, including TD(0), TD(λ), and GTD, as well as stochastic gradient descent for nonlinear least-squares estimation can be described in this form (see e.g., [19] for a detailed discussion).
Certainly, convergence guarantees of SA procedures as in (1) would not be possible without imposing assumptions on the operators f (θ, x) and f (θ). In this work, motivated by the analysis of TD-learning and related algorithms in reinforcement learning, we consider a class of SA procedures that satisfy the following properties. Assumption 1. The function f (θ, x) satisfies the globally Lipschitz condition in θ, uniformly in x, i.e., there exists a constant L 1 > 0 such that for all θ, θ ′ ∈ R d and each x ∈ X , it holds that Moreover, there exists a constant L 2 > 0 such that, for each x ∈ X , it holds for all θ where X ⊆ R m denotes the living space of the stochastic process {X k }.
It is worth mentioning that (5) is equivalent to assuming that f (0, x) satisfying (4) is uniformly bounded for all x ∈ X . To see this, suppose f (0, x) ≤f holds for all x ∈ X . From (4), it follows that f (θ, . In this regard, by defining L := max{L 1 , L 2 }, we will assume for simplicity that (4) and (5) hold with the same constant L. Assumption 2. Consider the ODE (3). There exists a twice differentiable function W (θ) that satisfies globally and uniformly the following conditions for all θ, θ ′ ∈ R d for some constants c 1 , c 2 , c 3 , c 4 > 0.
Regarding these assumptions, two remarks come in order.
In addition to Assumptions 1 and 2, to leverage the corresponding ODE to study convergence of SA procedures, we make an assumption on the stochastic perturbation sequence {X k } k∈N .
Assumption 3. For each θ ∈ R d , the random vector f (θ, X k ) is F k -measurable, and there exists a function σ(T ) : N + → R + monotonically decreasing to zero, i.e., lim T →∞ σ(T ) = 0, such that where the expectation E is taken over Simply put, Assumption 3 requires that the bias of the 'ergodic' average of any consecutive T gradient estimates {f (θ, X k )} T0+T −1 k=T0 from their limit f (θ) vanishes (at least) sublinearly in T . Indeed, this is fairly mild and more general than those studied by e.g., [1], [19], [4], [29], each of which imposes requirements on every single gradient estimate f (θ, X k ). In sharp contrast, our condition (7) can allow for large instantaneous biased gradient estimates f (Θ k , X k ) of f (Θ k ). Indeed, Assumption 3 is satisfied by a broad family of discrete-time stochastic processes, including e.g., i.i.d. random vector sequences [1], finite-state irreducible and aperiodic Markov chains [14], and Ornstein-Uhlenbeck processes [11]; whereas, existing works [1], [19], [4], [29] focus solely on one type of those stochastic processes.
3 Non-asymptotic bounds on the mean-square error In this paper, we seek to develop novel tools for proving non-asymptotic bounds on the mean-square error of the iterates {Θ k } k≥1 generated by a recursion of the form (1) (to the equilibrium point θ * = 0). Before presenting the main results, we start off by introducing an instrumental result which is the key to our novel approach to controlling the possible bias in gradient estimates of the SA procedure. Its proof is provided in Appendix A of the supplementary material. Proposition 1. Under Assumptions 1 and 3, there exists a function g ′ (k, T, Θ k ) such that the next relation holds for all T ∈ N + where the expectation is taken over Evidently, Proposition 1 offers a bound on the average gradient bias over some T > 0 iterations, which is indeed motivated by our Assumption 3. Based on the results in Proposition 1, we present the following theorem, which establishes a general convergence result that applies to any stochastic sequence {X k } k∈N satisfying Assumption 3. Theorem 1. Under Assumptions 1-3 and for any δ > 0, there exist a function W ′ (k, Θ k ) and a constant ǫ c (δ) > 0 such that the following inequalities are globally and uniformly satisfied for all ǫ ∈ (0, ǫ c ) and all k ∈ N are constants dependent on c 1 ∼ c 4 of (6) but independent of ǫ > 0. Proof of Theorem 1 is relegated to Appendix B of the supplementary material due to space limitations. Our proof builds critically on the construction of function W ′ (k, Θ k ) from the Lyapunov function W (θ) of the ODE (3). To be able to use the concentration bound in (7), we are motivated to introduce a function candidate that necessarily looks ahead to a number of T future iterates, with parameter T ∈ N + to be designed such that the gradient bias can be made affordable, given by where, to make the dependence of Θ j≥k as a function of Θ k explicit, we intentionally write Θ j = Θ j (k, Θ k ), understood as the iterate of the recursion (1) at time instant j ≥ k, with an initial condition Θ k at time k. The design parameter T ≥ 1 allows us to exploit the monotonically decreasing function σ(T ) → 0 in (9) to gain control over the gradient bias, therefore rendering the bounds (11)-(12) possible. When {X k } k is e.g., an i.i.d. random sequence [1], or a Markov chain that has approximately arrived at its steady state (i.e., after a certain mixing time of recursions) [29], they have shown it suffices to choose T = 1, that is W ′ (Θ k ) = W (Θ k ) to validate (11)- (12). For general Markov chains however, functions like W ′ (Θ k ) = W (Θ k ) may fail to yield finite-time error bounds that hold for the entire sequence {Θ k } k≥1 . In a nutshell, our novel way of constructing the Lyapunov function offers an effective tool for finite-time analysis of general SA algorithms driven by a broad family of (discrete-time) stochastic processes.
We are now ready to study the drift of W ′ (k, Θ k ), which follows from Theorem 1, and whose proof is provided in Appendix C of the supplementary material. Lemma 1. Under Assumptions 1-3, the following holds true for all ǫ ∈ (0, ǫ c ) and all k ∈ N where c ′′ 3 , c ′′ 4 > 0 are appropriate constants independent of ǫ.
Theorem 2. Under Assumptions 1-3, and choosing any stepsize ǫ ∈ (0, ǫ c ), the following finitetime error bounds hold for all k ∈ N Proof of Theorem 2 is postponed to Appendix D of the supplemental document. At this point, some observations are worth making.

Remark 4. When the general recursion
In fact, the bound in [29,Theorem 7] becomes applicable only after a mixing time of updates (i.e., for k ≥ τ ) till the Markov chain gets sufficiently 'close' to its stationary distribution; yet, in sharp contrast, our bound (15) is effective from the first iteration for Markov chains starting with any initial distribution. Furthermore, our stead-state value (the last term of (15)) scales only with the stepsize ǫ > 0 (which has removed the independence on τ from the bound in [29]), and it vanishes as ǫ → 0.
Evidently, with the bound in (15), one can easily estimate the number of data samples (e.g., the length of a Markov chain trajectory) required for the mean-square error to be of the same order as its steady-state value.

Applications to approximate reinforcement learning
We now turn to the consequences of our general results for the problem of reinforcement learning with (non-)linear function approximation (a.k.a., approximate reinforcement learning), in particular the TD-and Q-learning. Toward this objective, we begin by providing a brief introduction to discounted MDPs and basic reinforcement learning algorithms; interested readers can refer to standard sources (e.g., [31], [3]) for more background.

Background and set-up
Consider an MDP, defined by the quintuple (S, U, P, R, γ), where S is a finite set of possible states (a.k.a. state space), U is a finite set of possible actions (a.k.a. action space), P := {P u ∈ R |S|×|S| |u ∈ U} is a collection of probability transition matrices, indexed by actions u, R(s, u) : S × U → R is a reward received upon executing action u while in state s, and γ ∈ [0, 1) is the discount factor. The results along with theoretical analysis developed in this paper may be generalized to deal with infinite and compact state and/or action spaces, but we restrict ourselves to finite spaces here for an ease of exposition.
An agent selects actions to interact with the MDP (the environment) by operating a policy. Specifically, at each time step k ∈ N, the agent first observes the state S k = s ∈ S of the environment, and takes an action U k = u ∈ U by following a deterministic policy π : S → U, or a stochastic one U k ∼ π(·|S k ), where π(·|s) is a probability distribution function supported on U. The environment then moves to the next state S k+1 = s ′ ∈ S with probability P u ss ′ = Pr(S k+1 = s ′ |S k = s, U k = u), associated with which an instantaneous reward R k := R(S k , U k ) is revealed to the agent. This procedure generates a trajectory of states, actions, and rewards, namely, For a given policy π, the value function V π (s) : S → R measures the expected discounted reward obtained by starting the MDP in a given state, and then following the policy π to take actions in all subsequent iterations. More precisely, we define where the conditional expectation E is taken over the entire trajectory of observations conditioned on the initial state S 0 = s.
Postulating a canonical ordering on the elements of S, we can view V π and R π as vectors in R |S| , and P π as a matrix in R |S|×|S| . It is well known that such a function V π exists given uniformly bounded rewards {R(s, u) ≤r} s,u , and it is the unique solution to the next Bellman's equation [34,5] Evidently, if all transition probabilities {P π (s, s ′ )} s,s ′ were known, vector V π can be found by solving a system of |S| linear equations dictated by (17). But in practice, either {P π (s, s ′ )} s,s ′ are unknown or |S| is huge or even infinity, it is impossible to evaluate exactly V π . Here, the goal is to efficiently estimate the value function V π (s) by observing a single trace of the Markov chain {S 0 , S 1 , S 2 , . . .} and the associated rewards, which is to be dealt with in subsection 4.2. Since the policy π we consider in this paper will be assumed fixed, we shall drop the dependence on π in our notation for brevity. Likewise, we can define for control purpose the so-called action-value function (a.k.a., Q-function), which measures the quality of a given policy by the expected sum of discounted instantaneous rewards, conditioned on starting in a given state-action pair, and following the policy π to take subsequent actions; i.e., Naturally, we would like to choose the policy π such that the values of the Q-function are optimized. Indeed, it has been established that the Q-function associated with the optimal policy π * , yielding the optimal Q-function denoted by Q * , satisfies the following Bellman equation [3,33,37] after assuming a canonical ordering on the elements of S × U, the table Q can be treated as a matrix in R |S|×|U | . Once {Q * (s, u)} s,u becomes available, an optimal policy π * can be recovered by setting π * (s) ∈ arg max u∈U Q * (s, u) for all s ∈ S, without any knowledge about the transition probabilities. Again, in the learning context of interest, the transition probabilities {P u ss ′ } s,u,s ′ are unknown and the dimensions |S| and/or |U| can be huge or even infinity in practice, so it is not possible to exactly evaluate the Bellman equation (19). As one of the most popular solutions for finding the optimal policy, Q-learning [38] iteratively updates the estimate Q k of Q * using a single trajectory of samples {(S k , U k , S k+1 )} generated by following the policy π, according to the recursion where {0 < ǫ k < 1} is a sequence of stepsizes to be chosen by the user. Under standard conditions on the stepsizes, the sequence {Q k } converges to Q * almost surely as long as every state-action pair (s, u) ∈ S × U is visited infinitely often; see, for instance, [37,33,3,31]. However, it is well known that for many important problems of practical interest, the computational requirements of exact function estimation are overwhelming, mainly because of a large number of states and actions (i.e., Bellman's "curse of dimensionality") [3]. Instead, a popular approach in the literature has been to leverage low-dimensional parametric approximations of the value function, or the Q-function. Although contemporary nonlinear approximators such as deep neural networks [24] could lead to more powerful approximations, the simplicity of reinforcement learning with linear function approximation [31] allows us to analyze them in detail.

Temporal-difference learning with linear function approximation
In this section, we target a deeper understanding of the dynamics of TD-learning algorithms with linear function approximation. Toward this objective, we assume a linear function approximator for the true value function V (s), given by where θ ∈ R d is a parameter vector to be learned, typically having d ≪ |S|; and φ(s) ∈ R d is a fixed feature vector dictated by preselected basis functions φ 1 , φ 2 , . . . , φ d : S → R, that act on state s as follows φ(s) : Without loss of generality, we assume that all feature vectors are φ(s) ≤ 1, ∀s ∈ S [5]. For future reference, we stack up all feature vectors {φ(s)} s∈S to form the matrix We also make a standard assumption that Φ has full column rank, i.e., any redundant or irrelevant feature vectors have been removed [34] Consider the classical TD-learning for estimating the unknown parameter vector θ [30]. Starting with some Θ 0 , the simplest yet widely used TD variant, which is also known as TD(0), updates the estimate Θ k of θ according to where ǫ ∈ (0, 1) is a constant stepsize. We are interested in developing finite-time error bounds for (23), where the observed tuples {(S k , R(S k , U k ), S k+1 )} k∈N are gathered from a single trajectory of the Markov chain {S k } k∈N . To apply our results developed for general SA algorithms to TD(0) learning here, we just need to verify our working assumptions in Section 2. Let µ ∈ [0, 1) |S| also denote the stationary distribution of the Markov chain, i.e., µ = µP , and also D ∈ R |S|×|S| be a diagonal matrix holding entries of µ on its main diagonal. Upon introducing A := −ΦD(Φ − γP Φ) ⊤ and b := ΦDR, it has been shown in [34,Theorem 2] that the TD(0) algorithm with diminishing stepsizes obeying standard conditions, tracks the ODĖ as well as converges to its unique equilibrium point θ * = −A −1 b. By substituting Θ =Θ + θ * into (23), we deduce that the centered recursioñ tracks the ODEθ = Aθ, which has a unique equilibrium point at the originθ = 0. If we define it now becomes clear that the TD(0) algorithm is a special case of the stochastic recursion (1). As has also been made clear in our discussion above, the following limit exists for eachθ ∈ R d Next, let us turn to verify Assumptions 1-3.
Regarding (6b), we have that

Consider the following continuous Lyapunov equation with Hurwitz
which is well known to have a unique symmetric, positive definite solution P given any symmetric, positive definite matrix Q (e.g., [3]). So, by choosing any Q = Q ⊤ ≻ 0, we verified that (6b) holds with constant c 3 = λ min (Q)/L > 0 as well.
Lemma 2. For any finite-state, irreducible, and aperiodic Markov chain, there are constants c > 0 and ρ ∈ (0, 1) such that where µ is the steady-state distribution of {X k } k∈N , and d T V (ν, µ) denotes the total variation distance between probability measures µ and ν, defined as follows where E π [f (θ, X)] takes expectation over X = [S S ′ ] ⊤ with respect to the stationary distribution µ of the Markov chain {S k }; (35) leverages the transition probabilities {P ss ′ }; (37) uses the inequality (30) and the fact that finite-state, irreducible, and aperiodic Markov chains mix at a geometric rate η ∈ (0, 1) from any s ′ 0 ∈ S (see Lemma 2). Now, we can conclude that Assumption 3 holds with function σ(T ) := 2c/[(1 − η)T ], which indeed monotonically decreases to 0 as T → ∞.

Remark 5.
It is worth remarking that although geometric mixing is used here for ease of presentation, it is clear from (36) that Assumption 3 is satisfied by Markov chains with general mixing rates as long as T0+T k=T0+1 s∈S Pr(S k = s|S T0+1 = s ′ 0 ) − µ(s) grows sub-linearly in T ; that is, In a nutshell, the finite-time error bound in Theorem 2 applies to TD(0) learning algorithms in a generally mixing Markov chain setting, provided standard assumptions-that the reward function is uniformly bounded as max s,s ′ |R(s, u)| ≤r, the feature matrix Φ is full column rank, and all feature vectors {φ(s)} are bounded too-hold true.
Remark 6. Although the basic TD(0) learning algorithm is dealt with here, it is worth remarking that other variants of TD-learning such as TD(λ), and GTD can also be cast in the form of (1); see related treatments in e.g., [29]. Hence, our novel multistep Lyapunov approach as well as the associated nonasymptotic convergence analysis is readily applicable to general TD-learning algorithms.

Q-learning with linear function approximation
In this section, we provide an improved non-asymptotic analysis for Q-learning using linear function approximators. In this direction, we assume that the Q-function is parameterized by a linear function as follows where we have kept the notation θ ∈ R d for the parameter vector to be learned (as in the previous subsection), typically of size d ≪ |S| × |U|, the number of state-action pairs; and the feature vector ψ(s, a) ∈ R d stacks up d features produced by pre-selected basis functions {ψ ℓ (s, u) : S × U → R} d ℓ=1 . Similar to TD-learning with linear function approximation, here we can also introduce the feature matrix, given by which is assumed to have full column rank (that is, linearly independent columns) and satisfy ψ(s, u) ≤ 1 for all state-action pairs (s, u) ∈ S × U. The well-known approximate Q-learning algorithm updates the parameter vector Θ, according to the recursion (e.g., [3,31]) with some constant stepsize ǫ ∈ (0, 1). The objective here is to establish finite-time error guarantees for (41), when the observed data samples {(S k , U k , R(S k , U k ), S k+1 , U k+1 )} k∈N are collected along a single path of the Markov chain {S k } k∈N by following a deterministic policy π. Considering (42) it becomes obvious that (41) has the form of (1). To check whether our non-asymptotic error guarantees established for nonlinear SA procedures in Section 3 can be applied to Q-learning with linear function approximation or not, it, again, suffices to show that Assumptions 1-3 are satisfied by the Q-learning updates (41).
In general, Q-learning with function approximation can diverge. This is mainly because Qlearning implements off-policy 1 sampling to collect the data, which renders the expected Q-learning update possibly an expansive mapping [12]. Under appropriate regularity conditions on the sampling policy, asymptotic convergence of Q-learning with linear function approximation was established in [23], and finite-time analysis was recently given in [40,8]. In the following, we also impose some regularity conditions on the sampling policy π.

Assumption 4 ([8])
. Suppose that the Markov chain {S k } k∈N induced by policy π is irreducible and aperiodic, whose unique stationary distribution is denoted by µ. Assume that the equation F (θ) := E µ [F (θ, X)] = 0 has a unique solution θ * , and the next inequality holds for all θ ∈ R d for some constant 0 < c < 1.
Verifying Assumption 2. The ODE associated with the (centered) Q-learning update (45) iṡ for which we consider the Lyapunov candidate function W (θ) = θ 2 /2. Evidently, it follows that W (θ) ≥ 0 for allθ = 0, so (6a) holds with c 1 = c 2 = 1/2. Secondly, usingf (θ * ) = 0, we have that On the other hand, it follows for anyθ,θ ′ that Verifying Assumption 3. Let P u ss ′ be the transition probability of the Markov chain {S k } k∈N from state s to s ′ after taking action u; and let p (n) ss ′ be the n-step transition probability from state s to s ′ following policy π. Define then X k := (S k , U k , S k+1 ), and it can be verified that {X k } k∈N is a Markov chain with state space X := {x = (s, u, s ′ ) : s ∈ S, π(u|s) > 0, P u ss ′ > 0} ⊆ S × U × S. Next, we show that {X k } is aperiodic and irreducible.
Toward that end, consider two arbitrary states which corroborates that the Markov chain {X k } k is irreducible (e.g., [21,Chapter 1.3]).
To prove that {X k } k is aperiodic, we assume, for the sake of contradiction, that {X k } k is periodic with period d ≥ 2. As {X k } k has been shown irreducible, it follows readily that every state in X has the same period of d. Hence, for each state x = (s, u, s ′ ) ∈ X , it holds that p (n+1) x,x = 0 for all integers n + 1 > 0 not divisible by d. Further, we deduce for any positive integer (n + 1) not divisible by d that where the last two equalities arise from (58) and the periodicity assumption of {X k } k , respectively. It becomes evident from (59) that {S k } k is periodic too, and its period is at least d. This clearly contradicts with the assumption that {S k } k is aperiodic. Therefore, we conclude that the Markov chain {X k } k is irreducible and aperiodic provided that {S k } k is irreducible and aperiodic. Now, consider two arbitrary states x T0 = (s T0 , u T0 , s ′ T0 ), x = (s, u, s ′ ) ∈ X . It follows that x); equality (61) uses (44) and (58); and, (62) arises from the geometric mixing property of irreducible, aperiodic Markov chain {X k } k as well as (51). We have proved that Assumptions 1-3 are satisfied by Q-learning with linear function approximation, provided that certain conditions on the sampling policy and function approximators hold. Hence, the established finite-time error bound in Theorem 2 holds for Q-learning algorithms with linear function approximation.

Comparison to past work
Since the seminal work [30], there has been a large body of contributions on TD-learning in diverse settings. Here we shall focus on the subset of results that has established error bounds for discounted MDPs, which are most relevant for direct comparison to our results. General asymptotic results on the convergence of TD-learning algorithms with (non-)linear function approximation were given in [13], [34], [5]; and those of Q-learning (with function approximation) in [37], [33], [32], [23]. Examples of divergence with (non-)linear approximation were provided by [2], [34]. Connections between TDlearning and SA were drawn in [13], [33], and [3].
On the other hand, non-asymptotic guarantees for RL algorithms appeared only recently and remain still limited; see [16], [25], [22], [36], [39], [20], [35], [40], [8]. Finite-time analysis of TD(0) was initially investigated by [16], which, however, was pointed out to contain serious errors in the proofs by [25] and thus not included in our comparison. Finite-time performance of other TD-based algorithms such as GTD was studied by [22,36], and [20]. Refined finite-time error bounds of TD(0) were provided by [9], [19], but their results apply only to i.i.d. data samples, which, however, are difficult to acquire in practice. Dealing with the more realistic yet challenging Markov chain observation model, finite-time analysis on the mean-square error was recently studied by [4], [29], [40], [8], and [35]. Nevertheless, their bounds were derived for TD-and/or Q-learning using linear function approximators, and were based on strong geometric mixing conditions. In addition, [4] and [8] require including a projection step into the standard updates, whereas the bounds reported by [29] and [8] become applicable only after a certain mixing time of TD updates, that is, after the Markov chain gets sufficiently "close" to its stationary distribution.
In contrast, our bound in Theorem 2 not only applies to TD-and Q-learning with linear function approximation, but also using a certain class of nonlinear function approximators compliant with Assumption 1. More importantly, our non-asymptotic guarantees hold for the unmodified TD-and Q-learning (i.e., without any projection steps), as well as for Markov chains under general mixing conditions as specified in (39) and from any initial distribution.

Conclusions
In this paper, we provided a non-asymptotic analysis for a class of biased SA algorithms driven by a broad family of stochastic perturbations, which include as special cases e.g., i.i.d. random sequences of vectors and ergodic Markov chains. Taking a dynamical systems viewpoint, our approach has been to design a novel multistep Lyapunov function that involves future iterates to control the gradient bias. We proved a general convergence result based on this multistep Lyapunov function, and developed non-asymptotic bounds on the mean-square error of the iterate generated by the SA procedure to the equilibrium point of the associated ODE. Subsequently, we illustrated this general result by applying it to obtain finite-time error bounds for the unmodified TD-and Q-learning with linear function approximation, where data are gathered along a single trajectory of a Markov chain. Our bounds hold for Markov chains with general mixing rates and any initial distribution, as well as from the first iteration. Although the focus here has been on biased SA procedures with constant stepsizes, our non-asymptotic results can be extended to accommodate time-varying stepsizes as well. Our future work will also aim at generalizing this novel analysis to SARSA and distributed RL algorithms.
On the other hand, note from (8) that which, in conjunction with (63), suggests that we can write By taking expectation of both sides of (66) conditioned on the σ-field F k , along with the fact that Θ k is F k -measurable, we obtain where the last inequality follows from Lemma 3 as well as the property of the averaged operator f in (7) under our working Assumption 3. This concludes the proof.

B Proof of Theorem 1
We prove this theorem by carefully constructing function for W ′ (k, Θ k ) from W (Θ k ) (recall under our working assumption 2 that W (Θ k ) exists and satisfies properties (75)-(6c)). Toward this objective, let us start with the following candidate where, to make the dependence of Θ j≥k on Θ k explicit, we maintain the notation Θ j = Θ j (k, Θ k ), which is understood as the state of the recursion (1) at time instant j ≥ k, with an initial condition Θ k at time instant k.
In the following, we will show that there exists and also determine a value for the parameter T ∈ N + such that the inequalities (11) and (12) are satisfied.
For ease of exposition, we start by proving the second inequality (12). To this end, observe from the definition of W ′ (k, Θ k ) in (68) that where the last equality is due to the fact that Θ k (k, Θ k ) = Θ k .
To upper bound the term in (69), we will focus on bound the first term W (Θ k+T (k, Θ k )). Recall from (8) that based on which we can find the second-order Taylor expansion of W (Θ k+T (k, Θ k )) (which is twice differentiable under Assumption 2) around Θ k , as follows where we have employed the so-called mean-value theorem, suggesting that (70) holds with Θ ′ k := Θ k + η ǫT f (Θ k ) + g ′ (k, T, Θ k ) for some constant η ∈ [0, 1].
Next, we will pursue an upper bound for each individual term on the right hand side of (70) by conditioning on the σ-field F k . Again, using the fact that Θ k is F k -measurable and invoking (6b), we have that One can further verify the following bounds In particular, (72) uses the Cauchy-Schwartz inequality, (73) calls for Proposition 1, and the last one follows from the inequality θ ( θ + 1) ≤ 2( θ 2 + 1). As far as the last term of (69) is concerned, it is clear that where (75) leverages the upper bound on the Hessian matrix of W (θ) arising from the property (6c), (76) follows from the inequality a + b 2 ≤ 2( a 2 + b 2 ) for any real-valued vectors a, b ∈ R d , and (77) uses the Lipschitz property of function f (θ) that can be easily verified since f (θ, x) is Lipschitz in θ.
In the sequel, we will show that there exist parameters ǫ > 0 and T ≥ 1 such that the coefficient of (80) obeys c 3 − c 4 ρ(T, ǫ) > 0. Formally, such a result is summarized in Proposition 2 below, whose proof is relegated to Appendix G.
As such, by taking any δ < c3 c4 , feasible parameter values T δ and ǫ δ can be obtained according to (127) and (129), respectively. Now by choosing it follows that Furthermore, it is straightforward to deduce from (81) and (82) that If we now let c ′ 4 := c 4 LT * , then (80) confirms that Finally, recalling (69), we deduce that concluding the proof of (12). Now, we turn to show the first inequality. It is evident from the properties of W (Θ k ) in Assumption 2 that where the second inequality follows from (6a), and the last equality from the fact that Θ k (k, Θ k ) = Θ k . Therefore, by taking c ′ 1 = c 1 , we have shown that the first part of inequality (11) holds true. For the second part, it follows that yielding by means of telescoping series Using further the inequality (a + b) 2 ≤ 2(a 2 + b 2 ), we deduce that Taking advantage of the properties of W (Θ k ) in Assumption 2 and (91), it follows that Let us now examine the two coefficients of (92) more carefully. Note that where both (93) and (94) follow from the mean-value theorem (1 + ǫL) j−k = 1 + (j − k)ǫL + 1 2 (j − k − 1)(1 + ǫ ′ j−k L) j−k−2 (ǫL) 2 for any j − k ≥ 1 and some constants ǫ ′ j ∈ [0, ǫ]. According to Proposition 2, or more specifically, the inequalities (84) and (85), we see that ǫ ′ j ≤ ǫ ≤ ǫ c for all 1 ≤ j ≤ T − 1.