{'fraction_non_alphanumeric': 0.052906083663773085, 'fraction_numerical': 0.01403922409173722, 'mean_word_length': 4.075054387237128, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence

We provide non-asymptotic bounds for the well-known temporal difference learning algorithm TD(0) with linear function approximators. These include high-probability bounds as well as bounds in expectation. Our analysis suggests that a step-size inversely proportional to the number of iterations cannot guarantee optimal rate of convergence unless we assume knowledge of the mixing rate for the Markov chain underlying the policy considered. This problem is alleviated by employing the well-known Polyak-Ruppert averaging scheme, leading to optimal rate of convergence without any knowledge of the mixing rate. Furthermore, we propose a variant of TD(0) with linear approximators that incorporates a centering sequence, and we establish that it exhibits an exponential rate of convergence in expectation.


Introduction
Many stochastic control problems can be cast within the framework of Markov decision processes (MDP). Reinforcement learning (RL) is a popular approach to solve MDPs, when the underlying transition mechanism is unknown. An important problem in RL is to estimate the value function V π for a given stationary policy π. We focus on discounted reward MDPs with a high-dimensional state space S. In this setting, one can only hope to estimate the value function approximately and this constitutes the policy evaluation step in several approximate policy iteration methods, for e.g. actor-critic algorithms Konda and Tsitsiklis [2003], Bhatnagar et al. [2009].
Temporal difference learning Sutton and Barto [1998] (TD(0)) is a well-known policy evaluation algorithm that is online and works with a single sample path obtained by simulating the underlying MDP. However, the classic TD(0) algorithm uses full-state representations (i.e. it stores an entry for each state s ∈ S) and hence, suffers from the curse of dimensionality. A standard trick to alleviate this problem is to approximate the value function within a linearly parameterized space of functions, i.e., V π (s) ≈ θ T φ(s). Here θ is a tunable parameter and φ(s) is a column feature vector with dimension d << |S|. This approximation allows for efficient implementation of TD(0) even on large state spaces.
The update rule for TD(0) that incorporates linear function approximators is as follows: Starting with an arbitrary θ 0 , θ n+1 = θ n + γ n r(s n , π(s n )) + βθ T n φ(s n+1 ) − θ T n φ(s n ) φ(s n ). (1) In the above, the quantities γ n are step sizes that are chosen in advance and satisfy standard stochastic approximation conditions (see assumption (A5)). Further, r(s, a) is the instantaneous reward in state s on choosing action a and β ∈ (0, 1) is the discount factor.
In Tsitsiklis and Van Roy [1997], the authors establish that θ n governed by (1) converges almost surely to the fixed point, θ * , of the projected Bellman equation given by Φθ * = ΠT π (Φθ * ). (2) In the above, T π is the Bellman operator, Π is the orthogonal projection onto the linearly parameterized space within which we approximate the value function, and Φ is the feature matrix with rows φ(s) T , ∀s ∈ S denoting the features corresponding to state s ∈ S (see Section 2 for details). Let P denote the transition probability matrix with components p(s, π(s), s ′ ) and let Ψ be a diagonal matrix whose diagonal forms the stationary distribution (assuming it exists) of the Markov chain for the underlying policy π. Then, θ * can be written as the solution to the following system of equations (see Section 6.3 of Bertsekas [2011]) Our aim is to derive non-asymptotic bounds on θ n − θ * 2 , both in high-probability and in expectation, to quantify the rate of convergence of TD(0) with linear function approximators. To the best of our knowledge, there are no non-asymptotic bounds for TD(0) with function approximation, while there are asymptotic convergence and rate results available. Finite time analysis of TD(0) is challenging for two reasons: (1) The asymptotic limit θ * is the fixed point of the Bellman operator, which assumes that the underlying MDP is begun from the stationary distribution Ψ (whose influence is evident in (3)). However, the samples provided to the algorithm come from simulations of the MDP that are not begun from Ψ. This presents a difficulty for a finite time analysis, since we do not know exactly the number of steps after which mixing of the underlying Markov chain has occurred, and TD(0) starts to see samples from the stationary distribution. Moreover, an assumption on the mixing rate amounts to assuming (partial) knowledge of the transition dynamics of the Markov chain underlying the policy π.
(2) Standard results from stochastic approximation theory suggest that in order to obtain the optimal rate of convergence for a step size choice of γ n = c/(c + n), one has to chose the constant c carefully. In the case of TD(0), we derive this condition and point out the optimal choice for c requires knowledge of the mixing rate of the underlying Markov chain for policy π. We handle the first problem by establishing that under a mixing assumption (the same as that used to establish asymptotic convergence for TD(0) in Tsitsiklis and Van Roy [1997]), the mixing error can be handled in the nonasymptotic bound. This assumption is broad enough to encompass a reasonable range of MDP problems. We alleviate the second problem by using iterate averaging. In both cases, we are obliged to include a projection step in order to bound the effect of the error due to sampling.
One inherent problem with iterative schemes that use a single sample to update the iterate at each time step, is that of variance. This is the reason why it is necessary to carefully choose the step-size sequence: too large and the variance will force divergence; too small and the algorithm will converge, but not to the solution intended. Indeed, iterate averaging is a technique that aims to allow for larger step-sizes, while producing the same overall rate of convergence (and we show that it succeeds in eliminating the necessity to know properties of the mixing time). A more direct approach is to center the updates, and this was pioneered recently for stochastic gradient descent in convex optimization (Johnson and Zhang [2013]). We propose a variant of TD(0) that uses this approach. We give a finite-time analysis, and show that the algorithm results in an exponential convergence rate, while not requiring a projection step to bound the iterates.
Our contributions can be summarized as follows: (1) Under a set of assumptions similar to Tsitsiklis and Van Roy [1997], we provide non-asymptotic bounds, both in high probability as well as in expectation, that quantify the convergence rate of TD(0) with linear function approximators.
(2) We also propose a variant of TD(0) that incorporates a centering sequence, that can easily be used in approximate policy iteration schemes, and we show that it converges faster than the regular TD(0) algorithm in expectation.
The key insights from our finite-time analysis are: (1) With a step-size γ n = c/(c + n) where (1 − β) 2 µc ∈ (1/2, ∞), we obtain the optimal rate of convergence of the order O (1/ √ n) for the bound in expectation. Here µ is the smallest eigenvalue of the matrix Φ T ΨΦ (see Theorem 1 in Section 3) (2) To obtain the optimal rate in the high-probability bound, the choice of c requires the knowledge of the mixing rate of the underlying Markov chain for policy π (see Theorem 1). As pointed out earlier, this is problematic as it implies (partial) knowledge about the transition dynamics of the MDP.
(3) With iterate averaging, one can get rid of the dependency of c on the mixing rate and still obtain the optimal rate of convergence, both in high probability as well as in expectation (see Theorem 2).
(4) For the centered variant of TD(0), we obtain an exponential convergence rate when the underlying Markov chain mixes fast (see Theorem 3). TD(0) with function approximation is an efficient algorithm that is easy to implement on large state space problems. However, deriving convergence rate results, especially of non-asymptotic nature, requires sophisticated machinery. In particular, we base our approach on that proposed in Frikha and Menozzi [2012] (and later expanded to include iterate averaging in Fathi and Frikha [2013]). We would like to remark that asymptotic convergence rate results for TD(λ) are available in Konda [2002]. The authors establish there that TD(λ) converges asymptotically to a multi-variate Gaussian distribution N (0, Σ), where Σ is a covariance matrix that is a function of the matrix A. This rate result in the form of a central limit theorem holds true for TD(λ) when combined with iterate averaging, while the non-averaged case does not result in the optimal rate of convergence. Our results are consistent with this observation, as we establish from a finite time analysis that the non-averaged TD(0) can result in optimal convergence only if the step-size constant c in γ n = c/(c + n) is set carefully (as a function of the mixing time), while one can get rid of this dependency and still obtain the optimal rate with iterate averaging. Least squares temporal difference methods are popular alternatives to the classic TD(λ). Asymptotic convergence rate results for LSTD(λ) and LSPE(λ), two popular least squares methods, are available in Konda [2002] and Yu and Bertsekas [2009], respectively. However, to the best of our knowledge, there are no concentration bounds that quantify the rate of convergence through a finite time analysis. A related work in this direction is the finite time bounds for LSTD in Lazaric et al. [2010]. However, the analysis there is under a fast mixing rate assumption, while we provide non-asymptotic rate results without making any such assumption. We note here that assuming a mixing rate implies partial knowledge of the transition dynamics of the MDP under a stationary policy and in typical RL settings, this information is not available.

TD(0) with Linear Approximation
We consider an MDP with state space S and action space A. The aim is to estimate the value function V π for any given stationary policy π : S → A, where In the above, s t denotes the state of the MDP at time t, β ∈ (0, 1) is the discount factor, and r(s, a) denotes the instantaneous reward obtained in state s under action a. The expectation is with respect to the transition dynamics that specify the probability of transitioning from state s to s ′ under action a for any s, s ′ ∈ S and a ∈ A (we denote this probability by p(s, a, s ′ )). It is well-known that the value function V π is the solution to the fixed point relation V = T π (V ), where the Bellman operator T π is defined as TD(0) Sutton and Barto [1998] performs a fixed point-iteration using stochastic approximation: Starting with an arbitrary V 0 , update V n (s n ) := V n−1 (s n ) + γ n r(s n , π(s n )) + βV n−1 (s n+1 ) − V n−1 (s n ) , where γ n are step-sizes that satisfy standard stochastic approximation conditions.
As discussed in the introduction, while TD(0) algorithm is simple and provably convergent to the fixed point of T π for any policy, it suffers from the curse of dimensionality associated with high-dimensional state spaces. A popular approach is to parameterize the value function using a linear function approximator, i.e. for every s ∈ S, approximate V π (s) ≈ φ(s) T θ. Here φ(s) is a d-dimensional feature vector with d << |S|, and θ is a tunable parameter. Incorporating function approximation, an update rule for the TD(0) analogous to (6) is given in (1). For the purposes of analysis, we also incorporate a projection step into the algorithm, so that, for all n, θ n ≤ H.

Non-averaged case
Theorem 1. Under (A1)-(A6), we have the following: where 1 We assume an upper bound of 1 for both rewards and features for the sake of simplicity and we believe our analysis can be extended (left for future work) to the following generalized variants: (A2') The rewards satisfy E Ψ (r 2 (s, π(s))) < ∞, ∀s ∈ S; (A4') The feature vector φ k (s) for any k = 1, . . . , d and s ∈ S satisfies E Ψ (φ 2 k (s)) < ∞.
Centering Figure 1: Illustration of centering principle in CTD algorithm.
Remark 1. K 1 (n) and K 2 (n) above are O(1), i.e., they can be upper bounded by a constant. Thus, one can indeed get the optimal rate of convergence of the order O (1/ √ n) with a step-size γ n = c (c+n) . However, this rate is contingent upon on the constant c in the step-size being chosen correctly. This is problematic because the right choice of c requires the knowledge of mixing bound B(s 0 ) and knowing B(s 0 ) would imply knowledge about the transition probability matrix of the underlying Markov chain. For finite state space settings, the mixing bound B(s 0 ) can be shown to be a constant (see Section VII of Tsitsiklis and Van Roy [1997]), but one that depends on the second eigenvalue of the transition probability matrix and the latter information is unavailable in a typical RL setting.

Iterate Averaging
The idea here is to employ larger step-sizes γ n = (1 − β)(c/(c + n)) α and combine it with averaging of the iterates, i.e.,θ n+1 := (θ 1 + . . . + θ n )/n. This principle was introduced independently by Ruppert Ruppert [1991] and Polyak Polyak and Juditsky [1992], for accelerating stochastic approximation schemes. The main advantage for us is that one obtains the optimal rate of convergence without any constraint on the step-size constant c: where Proof. See Section 5.2.
Remark 2. The step-size exponent α can be chosen arbitrarily close to 1, resulting in a convergence rate of the order O (1/ √ n). However although the constants K A 1 (n) and K A 2 (n) remain O(1), there is a minor tradeoff here since a choice of α close to 1 would result in their bounding constants blowing up. One cannot choose c too large or too small for the same reasons.
Thus, iterate averaging results in the optimal rate of convergence, while having no dependency for the choice of c. This is consistent with the asymptotic convergence rate results from Konda [2002], where the authors establish the TD(λ) exhibits optimal convergence only with iterate averaging.

The Algorithm
Let X n = (s n , s n+1 ). Then, the TD(0) algorithm can be seen to perform the following fixed-point iteration: where f Xn (θ) := (r(s n , π(s n ))+βθ T φ(s n+1 )−θ T φ(s n ))φ(s n ). The limit of (14) is the solution, θ * , of F (θ) = 0, where F (θ) := ΠT π (Φθ)−Φθ. The idea behind the CTD algorithm is to use reduce the variance of the increments f Xn (θ n ), in order that larger step sizes can be used. This is achieved by choosing an extra iterateθ n , centred over the previous θ n , and using an increment of the form f Xn (θ n ) − f Xn (θ n ) + F (θ n ). This approach is inspired by a recently proposed algorithm SVRG in Johnson and Zhang [2013] for optimizing a strongly-convex function that is a finite sum of smooth functions. However, the setting for TD(0) with function approximation that we have is considerably more complicated owing to the following reasons: (i) Unlike Johnson and Zhang [2013], we do not have a function that is finite-sum of smooth functions. Instead, we have the value function which is an infinite (discounted) sum, with the individual functions making up the sum being made available in an online fashion (i.e. as new samples are generated from the simulation of the underlying MDP for policy π). (ii) The centering term in SVRG directly uses F (·), which in our case is a limit function that is neither directly accessible nor can be simulated for any given θ. (iii) Obtaining exponential convergence rate is also difficult owing to the fact that TD(0) does not initially see samples from the stationary distribution and there is an underlying mixing term that affects the rate. (iv) Finally, there are extra difficulties owing to the fact that we have a fixed point iteration, while the corresponding algorithm in Johnson and Zhang [2013] is stochastic gradient descent (SGD). The upshot of the above is that, while centering is an interesting idea for SGD, it is not straightforward to apply it to improve the convergence rate of TD(0).
The CTD algorithm that we propose overcomes the difficulties mentioned above and the overall scheme of this epoch-based algorithm is presented in Figure 1. At the start of the m th epoch, a random iterate is picked from the previous epoch, i.e.θ (m) = θ in , where i n is drawn uniformly at random in {(m − 1)M, . . . , mM }. Thereafter, for the epoch length M , CTD performs the following iteration: Set θ mM =θ (m) and for n = mM, . . . , (m+ 1)M − 1 update (0), one can choose a large (constant) stepsize γ in (15). This choice in conjunction with iterate averaging via the choice ofθ (m) results in an exponential convergence rate for CTD (see Remark 4 below).

Finite time bound
Theorem 3. Let θ * denote the solution of F (θ) = 0. Let the epoch length M of the CTD algorithm (15) be chosen such that C 1 < 1, where Then, under (A1)-(A4) and (A6), we have, In particular, if the Markov chain underlying policy π satisfies the following property: Proof. See Section 5.3. (17)

Remark 3. For finite state space settings, it is easy to see that the fast-mixing assumption
The first term on the RHS above is an artifact of function approximation, while the second and third terms reflect the convergence rate of the CTD algorithm.
Remark 5. To get the optimal rate for the CTD algorithm, we need to know the value of µ to set the step-size γ. However, we can get rid of this dependency by explicitly regularizing the problem. This would imply that we solve (A + µI)θ * = b instead of (3), where we choose µ.

Non-averaged case: Proof of Theorem 1
We split the analysis in two, first considering the bound in expectation, and second the bound in high probability. Both bounds involve a martingale decomposition, the former of the iteration (1), and the latter directly of the centered error.
Bound in expectation First we state a theorem bounding the expected error for general step-size sequences: sampling and mixing error The initial error depends on the initial point θ 0 of (1). The mixing error arises due to the fact that we don't supply samples to the TD(0) algorithm from the stationary distribution of the underlying Markov chain for policy π, while the sampling error arises out of a martingale difference sequence. These error components can be clearly seen from the first step of the proof in the sketch provided below.
Proof sketch of Theorem 4. Recall that f Xn (θ) := [r(s n , π(s n )) + βθ T n−1 φ(s n+1 ) − θ T n−1 φ(s n )]φ(s n ). The first step is to rewrite the recursion (1) as follows: where ǫ n := E(f Xn (θ n ) | F n ) − E Ψ (f Xn (θ n )) is the mixing error term, while ∆M n := f Xn (θ n ) − E(f Xn (θ n ) | F n ) is a martingale sequence (recall that F = {F n := σ(θ 1 , . . . , θ n )} is the filtration generated by the iterates θ n , n ≥ 0). The next step is to unroll (20) as follows: where A := Φ T Ψ(I − βP )Φ and Π n := n k=1 (I − γ k A). The mixing error can be bounded using (A6). However, bounding ∆M n 2 is tricky since it requires the iterate θ n to be bounded as well and the latter is complicated owing to the form of TD(0) update (1). We workaround this by assuming that the iterate is projected, i.e., θ n 2 ≤ H. The reader is referred to Appendix A.1 for the detailed proof.
In order to obtain the rates and constants presented in Theorem 1, we now specialize Theorem 4 for a particular choice of step-size sequence: γ n = (1 − β)c/(c + n). Supposing that c is chosen so that (1 − β) 2 µc > 1/2, then from the bound in expectation in Theorem 4 we have: where, in the last inequality, we have compared the sum with an integral. Similarly and the result in Theorem 1 now follows.
High probability bound Now we state a theorem bounding the error with high probability for general step-sizes: where This theorem decomposes the problem of bounding θ n − θ * 2 into bounding the deviation from its mean E θ n − θ * 2 in high probability and the size of the mean itself. The latter is already bounded by Theorem 4.
Proof Sketch of Theorem 5. Recall that z n := θ n −θ * . The first step is to rewrite z n 2 2 −E z n 2 2 as a telescoping sum of martingale differences as follows: The next step is to establish that the functions g i are Lipschitz continuous as follows: Lemma 6. Under the conditions of Theorem 5, conditioned on F i−1 , the functions g i are Lipschitz continuous in f Xi (θ i−1 ) with constants L i .
The final step is to invoke a standard martingale concentration bound using the L i -Lipschitz property of the g i functions and the assumption (A3) to obtain:

Lemma 7. Under the conditions of Theorem 5, we have
The result follows by optimizing over λ. For detailed proofs of the above lemmas, the reader is referred to Appendix A.2. Now, to derive the rate given in Theorem 1, we again specialise to the choice of step size sequence: We now find several regimes for the rate of convergence, based on the choice of c, however choosing it so that (we have used comparisons with integrals to bound the summations), and the result in Theorem 1 now follows.

Iterate Averaging: Proof of Theorem 2
In order to prove the results in Theorem 2 we again consider the case of a general step sequence. Recall that θ n+1 := (θ 1 + . . . + θ n )/n and let z n =θ n+1 − θ * . First, we directly give a bound on the error in high probability for the averaged iterates (the bound in expectation can be obtained directly from the bound in Theorem 4): Theorem 8. Under (A1)-(A3) we have, for all ǫ ≥ 0 and ∀n ≥ 1, Proof. Let ζ 1 i be the value of the averaged iterateθ i+1 at instant i and ζ 2 i be the value of the iterate θ i at instant i. Then as in the previous section, we decompose z n 2 2 − E z n 2 2 into a sum of martingale differences: where . Now we need to prove that the functions g i are Lipschitz continuous in the random inovation at time i. Let Θ i j (ζ) denote the mapping that returns the value of ζ n , given thatθ i−1 = ζ 1 and θ i = ζ 2 . Then by applying Theorem 5, we have The rest of the proof follows in a similar manner to the proof of Theorem 5. Now, in order to obtain the rates in Theorem 2, we again specialise the general results to the choice of step-size: γ n = (1 − β)(c/(c + n)) α . To bound the expected error we directly average the errors of the non-averaged iterates: and directly applying the bounds in expectation given in Theorem 4.

Lemma 9. Under conditions of Theorem 2, we have
For the rate of the bound in high probability we need to specialise the bounds for the bound in expectation in Theorem 8 for the new choice of step-size sequence. In particular, we must compute the value of the Lipschitz L i constants for our choice of step-sizes:

Lemma 10. Under conditions of Theorem 2, we have
Proof. See Appendix B.1.
Finally this lemma together with Theorem 8 completes the result.
Step 2: Bounding the variance of centred updates. Let Then, where we have used that for any random variable ξ, E( x − Ex 2 ) ≤ E( x 2 ).
For any θ, we have In the final inequality, we have used Φ T ΨΦ 2 ≤ d 2 . Plugging the above in (26), we obtain Step 3: Analysis for a particular epoch.
Taking the expected error of the n th iterate, we have: So, applying (27), we have Summing the above inequality over an epoch and noting that E Ψ,θn θ n+1 − θ * 2 2 ≥ 0, we have and hence we obtain the following by setting θ 0 =θ (m) : Step 4: Combining across epochs. Finally, we obtain (16) by unrolling (across epochs) the final recursion in the previous step.

Conclusions
TD(0) with linear function approximators is a well-known policy evaluation algorithm. While asymptotic convergence rate results are available for this algorithm, there are no finite-time bounds that quantify the rate of convergence. In this paper, we derived non-asymptotic bounds for TD(0) with linear function approximators. These include bounds both in high-probability as well as in expectation. From our results, it is observed that in order to obtain the optimal rate of convergence of the order O (1/ √ n), it is necessary to incorporate iterate averaging. This is because, to obtain the optimal rate with the classic step-size choice that is inversely proportional to the number of iterations of TD(0), it is necessary to know the mixing rate of the underlying Markov chain. We also proposed a fast variant of TD(0) that incorporates a centering sequence and established that the rate of convergence of this algorithm is exponential.
Proof. The update rule (1) can be re-written as follows: is the mixing error term, while ∆M n := f Xn (θ n ) − E(f Xn (θ n ) | F n ) is a martingale sequence. We notice that where A := Φ T Ψ(I − βP )Φ (here P = P π denotes the one-step transition probability matrix of the underlying Markov chain induced under a stationary policy π). Plugging (A.3) into (A.2), we obtain the following recursive procedure: where Π n := n k=1 (I − γ k A).
The mixing error can be bounded as follows: In particular we know from the above that ǫ n 2 ≤ 3B(s 0 ). By Jensen's inequality, we obtain where we have used the bound on ǫ 2 derived above, together with the fact that ∆M k is a martingale difference. Notice that for any vector x where we have used Lemma 1 in Tsitsiklis and Van Roy [1997] for the final equality. So we deduce that A − (1 − β)µI is positive definite by (A3), and hence By using the definition of f Xn (·), the martingale difference can be rewritten as ∆M n := βθ T n [φ(s n+1 ) − E[φ(s n+1 ) | F n ]]φ(s n ). ∆M n can now be bounded as follows: where the last inequality follows from assumption (A4), and the projection step of the algorithm. The claim now follows by plugging (A.9) and (A.10) into (A.8).
The proof is given through two lemmas. The first lemma establishes that the functions g i are Lipschitz continuous with Lipschitz constants L i , and makes use of assumption (A4). This is the crucial ingredient to invoke the concentration bound then given in Lemma 14.
Lemma 13. Recall that X n = (s n , s n+1 ) and f Xn (θ) := r(s n , π(s n )) + βθ T n−1 φ(s n+1 ) − θ T n−1 φ(s n ) φ(s n ). Then, conditioned on F i−1 , the functions g i are Lipschitz continuous in f Xi (θ i−1 ), the random innovation at time i, with constants Proof. Let Θ i j (θ) denote the mapping that returns the value of the iterate θ j at instant j, given that θ i = θ.
The second equality follows from the definition of f j . Let a j+1 : Then note that where the in the first inequality we have used that for two column vectors of equal dimension, x and y, (xy T ) T = yx T , and (xx T ) T = xx T . Now, from the tower property of conditional expectations, it follows that: By a similar argument to that used in (8) and, consequently, ǫ ′ k 2 ≤ [1 + β(3 − β)] B(s 0 ), for all k. Now Setting ∆ be the diagonal matrix with entries ∆ i,i = Φ i,1:d Φ T i,1:d . Then we find that for any vector θ: where (A.13) follows from the fact that θ T Φ T Ψ(I − Π)x = 0 since Π is a projection, (A.14) by an application of Cauchy-Schwarz inequality and from the non-expansiveness property of Π and P . (A.15) and (A.16) follow from the fact that, by (A4), the matrix ∆ − I is positive semi-definite. The final inequality (A.17) follows since (A3).
Hence we can conclude that: and, finally, we have In the following lemma, we invoke a standard martingale concentration bound using the L i -Lipschitz property of the g i functions and the assumption (A3).

Lemma 14. Under the conditions of Theorem 11, we have
The first equality above follows from (A.11), while the inequality follows from Markov inequality. Now for any bounded random variable f , and L-Lipschitz function g we have E (exp(λg(f ))) ≤ exp λ 2 L 2 /2 .
Note that each f i (θ i−1 ) is a bounded random variable by (A3), and, conditioned on and so The proof of Theorem 11 follows by optimizing over λ in (A.18).