A Concentration Bound for TD(0) with Function Approximation

1. Introduction

TD(0) is one of the most popular reinforcement learning (RL) algorithms for policy evaluation (Tsitsiklis and Van Roy 1997). Given a fixed policy, the algorithm is an iterative method to obtain the value function for each state under the long-term discounted reward framework. To mitigate the issues of large state spaces, the value function is often approximated using a linear combination of feature vectors. This algorithm is referred to as TD(0) with linear function approximation. In this paper, we work with online TD(0) with a single sample path of the underlying Markov chain. Our goal in this paper is to obtain a concentration bound of the form from some time on or, more precisely, for all $n\ge n_0$ for a suitably chosen $n_0$ for this algorithm.

A bound of this form was published for TD(0) as a section in our paper titled “Concentration of Contractive Stochastic Approximation and Reinforcement Learning” (Chandak et al. 2022). This paper established an all-time bound for contractive stochastic approximation with Markov noise and applied the bound to asynchronous Q-learning and TD(0). Although the main theorem and its application to asynchronous Q-learning are correct, TD(0) does not satisfy a key assumption for the main theorem,¹ and hence, the theorem was incorrectly applied to TD(0). We remove the need for that assumption in this version, giving a completely different proof tailored to the TD(0) algorithm.

The previous paper required the iterates of the stochastic approximation iteration to be bounded by a constant with probability 1. This assumption is not known to be true for the iterates of online TD(0) with function approximation for a single sample path. In fact, a common method to alleviate this issue is to project the iterates back into a ball centered around the origin (Bhandari et al. 2018, Patil et al. 2023). The key difficulty caused by the lack of this assumption is in applying martingale inequalities, which often require some restrictions on the increments of the martingale that are often not easy to verify. We do not modify the algorithm and instead adapt relaxed concentration inequalities (Chung and Lu 2006, section 8) for our problem. These bounds have an extra term given by the probability of increments going above a certain threshold (Tao and Vu 2015, proposition 34). Although the proof in this paper is restricted to TD(0), the underlying idea of using relaxed concentration inequalities is broadly applicable to other algorithms that face similar challenges because of unboundedness.

1.1. Related Works

There has been growing interest in analyzing the finite-time performance of reinforcement learning (RL) algorithms. Existing results can broadly be categorized by the type of bounds they establish. The most extensive body of work concerns expectation or mean square bounds (see, e.g., Chen et al. 2020, 2021). Another prominent line of research focuses on regret bounds, which characterize how the cumulative error grows over time—typically through almost-sure or expected regret guarantees (see, e.g., Azar et al. 2017, Jin et al. 2018, Yang and Wang 2019, Yang et al. 2020). A third class comprises high-probability or concentration bounds (see, e.g., Even-Dar and Mansour 2003, Qu and Wierman 2020, Li et al. 2023). Our work falls within this category but differs from conventional analyses that establish high-probability guarantees only for sufficiently large time n. In contrast, we derive uniform all-time bounds, that is, bounds that hold for all $n\ge n_0$ with probability at least $1-\delta$.

Specifically for TD(0), moment bounds have been established in Bhandari et al. (2018), Srikant and Ying (2019), and Chen et al. (2021). High-probability bounds have been established under various modifications of the TD(0) algorithm. These include uniform sampling from data sets (Prashanth et al. 2021), projection and tail averaging (Patil et al. 2023), and oracle access to independent and identically distributed (i.i.d.) samples of state–action–next state triplets $(s,a,s^{\prime })$ (Dalal et al. 2018, Chen et al. 2025).

One of us considered stochastic approximation involving contractive maps and martingale noise and derived maximal concentration bounds for this class of algorithms (Borkar 2022). This covered, in particular, synchronous Q-learning for discounted cost and some related schemes. In Chandak et al. (2022), we extended this work to cover “Markov noise” (Meerkov 1972) in the stochastic approximation scheme, allowing us to give bounds for the asynchronous case. As mentioned before, this work assumed almost-sure boundedness of iterates, which is not satisfied by the TD(0) algorithm. We remove the need for this assumption in our current work. Other articles aiming at bounds of these forms, such as the one we provide, are found in Chandak et al. (2023) for the LSPE algorithm and Borkar (2002), Kamal (2010), and Thoppe and Borkar (2019) for abstract stochastic approximation schemes. A recent work (Chen et al. 2025) considers all-time bounds for iterates without almost-sure boundedness, but they only consider additive and multiplicative noise and not Markovian noise as considered in this paper. Their proof technique relies on Moreau envelopes and a bootstrapping technique, which differs significantly from our work.

1.2. Outline and Notation

The rest of the paper is structured as follows. Section 2 gives a background to the TD(0) algorithm, along with the required assumptions and the stochastic approximation formulation. Section 3 states the main result and provides some insights into the result. The result is proved in Section 4. A concluding section highlights some future directions. Appendix A states a martingale inequality used in our proof, and Appendix B gives proofs for some technical lemmas. which are used to prove the main theorem.

Throughout this work, $\Vert ·\Vert$ denotes the Euclidean norm on ${\mathbb{R}}^d$, and $〈·,·〉$ denotes the inner product in ${\mathbb{R}}^d$. $\theta$ denotes the zero vector in ${\mathbb{R}}^d$. The $\mathcal{\ell }$th component of a vector x and a vector-valued function $h(·)$ are denoted by $x(\mathcal{\ell })$ and $h^{\mathcal{\ell }}(·)$, respectively.

2. Background on TD(0)

TD(0) is an algorithm for policy evaluation, that is, for learning the performance of a fixed policy, and not for optimizing over policies. Hence, a stationary policy is fixed a priori, giving us a time-homogeneous uncontrolled Markov chain $\{Y_n\}$ over a finite state space $\mathcal{S}$. The transition probabilities are given by $p(·|·)$, where the dependence on the policy is suppressed. Assume that the chain is aperiodic irreducible with the stationary distribution $\pi =[\pi (1),\dots ,\pi (S)],S=|\mathcal{S}|$. Let D denote the $S\times S$ diagonal matrix whose sth diagonal entry is $\pi (s)$. Reward $r(s)$ is received when a transition from state s takes place. Note that this reward can be stochastic as well, and the additional noise thereof can be combined with other noise terms without affecting our concentration result. For simplicity, we assume that we receive a deterministic $r(s)$. The objective is to evaluate the long-term discounted reward for each state given by the value function

Here, $0<\gamma <1$ is the discount factor. The dynamic programming equation for evaluating the same is

This can be written as the following vector equation:

for $r={[r(1),\dots ,r(S)]}^T$ and $P={[[p(s^{\prime }|s)]]}_{s^{\prime },s\in \mathcal{S}}\in {\mathbb{R}}^{S\times S}$.

The state space can often be large ($S\gg 1$), and to alleviate this “curse of dimensionality,” V is often approximated using a linear combination of d linearly independent basis functions (feature vectors) ${\varphi }_i\in {\mathbb{R}}^S,1\le i\le d$, with $S>>d\ge 1$. Also, let $\phi (s)={[{\varphi }_1(s),\dots ,{\varphi }_d(s)]}^T$ for $s\in \mathcal{S}$ denote the vector comprising components corresponding to state s in each feature. Thus, $V(s)\approx {\sum }_{i=1}^{d}x(i){\varphi }_i(s)$; that is, $V(s)\approx x^T\phi (s)$ and $V\approx \mathrm{\Phi }x$, where $x={[x(1),\dots ,x(d)]}^T$, and $\mathrm{\Phi }$ is an $S\times d$ matrix whose ith column is ${\varphi }_i$. Here, x denotes the learnable weights for the linear function approximator. Because $\{{\varphi }_i\}$ are linearly independent, $\mathrm{\Phi }$ is full rank. Substituting this approximation into the dynamic programming equation above leads to

But the right-hand side (RHS) may not belong to the range of $\mathrm{\Phi }$. So we use the following fixed point equation:

where $\mathrm{\Pi }$ denotes the projection to Range($\mathrm{\Phi }$) with respect to a suitable norm. It turns out to be convenient to take a projection with respect to the weighted norm $\Vert y{\Vert }_D≔\sqrt{y^{T}Dy}={({\sum }_{s\in \mathcal{S}}\pi (s){(y(s))}^2)}^{1/2}$ for $y\in {\mathbb{R}}^S$. The projection map with respect to this norm is

The invertibility of ${\mathrm{\Phi }}^{T}D\mathrm{\Phi }$ is guaranteed by the fact that $\mathrm{\Phi }$ is full rank. Finally, the TD(0) algorithm is given by the recursion

Here, $a(n)$ denotes the positive step-size sequence. At the end of this section, we explain how this iteration can be expected to converge to the required fixed point from (1).

2.1. Assumptions

We impose two assumptions on the algorithm. The first is about the feature vectors, and as we explain next, it does not restrict the algorithm. The second specifies the class of step sizes $a(n)$ considered, which is standard in the analysis of RL. In fact, our results hold for a broader class of step sizes than those typically required in stochastic approximation frameworks.

1. For the assumption on $\mathrm{\Phi }$, define $\mathrm{\Psi }≔{\mathrm{\Phi }}^T\sqrt{D}$, and let ${\lambda }_M$ be the largest singular value of $\mathrm{\Psi }$, that is, the square of the largest eigenvalue of $\mathrm{\Psi }{\mathrm{\Psi }}^T$ and, equivalently, of ${\mathrm{\Psi }}^T\mathrm{\Psi }$. Assume that

   $${\lambda }_M<\frac{\sqrt{2(1-\gamma )}}{(1+\gamma )}.$$(3)

   Because the feature vectors can be scaled without affecting the algorithm (the weights $x(i)$ get scaled accordingly), this assumption does not restrict the algorithm. Alternatively, the step size can be appropriately scaled as well; that is, $a(n)=b(n)c$, where $b(n)$ acts as the effective step size, and $c\phi (·)$ act as the effective feature vectors that satisfy the above assumption. This assumption can be replaced with the following assumption on the basis vectors:

   $$\Vert \phi (s)\Vert \le \frac{\sqrt{2(1-\gamma )}}{1+\gamma }\hspace{0.17em}\forall s\in \mathcal{S};$$
   that is, the ${\mathcal{\ell }}_2$ norm of each row of $\mathrm{\Phi }$ is bounded by $\sqrt{2(1-\gamma )}/(1+\gamma )$. To see this, note that
   $$\frac{\Vert \mathrm{\Psi }x{\Vert }_2}{\Vert x{\Vert }_2}=\frac{\Vert \mathrm{\Phi }x{\Vert }_D}{\Vert x{\Vert }_2}\le \frac{\Vert \mathrm{\Phi }x{\Vert }_{\infty }}{\Vert x{\Vert }_2}.$$

   Now, ${\max }_{x\ne \theta }\frac{\Vert \mathrm{\Phi }x{\Vert }_{\infty }}{\Vert x{\Vert }_2}$ is the operator norm defined with ${\mathcal{\ell }}_2$ norm for domain and ${\mathcal{\ell }}_{\infty }$ for codomain, which is equal to the maximum ${\mathcal{\ell }}_2$ norm of a row. Hence,

   $${\lambda }_M=\underset{x\ne \theta }{\max }\frac{\Vert \mathrm{\Psi }x{\Vert }_2}{\Vert x{\Vert }_2}\le \underset{x\ne \theta }{\max }\frac{\Vert \mathrm{\Phi }x{\Vert }_{\infty }}{\Vert x{\Vert }_2}=\underset{s\in \mathcal{S}}{\max }\Vert \phi (s){\Vert }_2.$$

2. $\{a(n)\}$ is a sequence of nonnegative step sizes satisfying the conditions

   $$a(n)\to 0,\hspace{0.17em}{\displaystyle \sum _{n}a}(n)=\infty$$

and is assumed to be nonincreasing; that is, $a(n+1)\le a(n)\hspace{0.17em}\forall n$. We also assume that $a(n)<1$ for all n. We further assume that $\frac{d_1}{n+1}\le a(n)\le d_3{\left(\frac{1}{n+1}\right)}^{d_2},\forall n$, where $d_1>0$ and $0<d_2\le 1$. Larger values of $d_1$ and $d_2$ and smaller values of $d_3$ improve the main result presented below. The role this assumption plays in our bounds will become clear later. Observe that we do not require the classical square-summability condition in stochastic approximation, namely, ${\sum }_{n}a{(n)}^2<\infty$. This is because the contractive nature of our iterates (Lemma 1) gives us an additional handle on errors by putting less weight on past errors. A similar effect was observed in Chandak et al. (2022). The above assumptions on the step-size sequence can be weakened so as to hold only after some $N>1$ without any changes in the analysis.

2.2. Formulation as a Stochastic Approximation Iteration

We next rearrange Algorithm (2) to separate the martingale noise and the Markov noise, and we write it as a stochastic approximation iteration:

whereand

Define the family of $\sigma$-fields ${\mathcal{F}}_n≔\sigma (x_0,Y_m,m\le n),\hspace{0.17em}n\ge 0$. Then, $\{M_n{x}_{n-1}\}$ is a martingale difference sequence with respect to $\{{\mathcal{F}}_n\}$; that is,

where $\theta$ denotes the zero vector. The term ${\tau }_1$ denotes the error because of the martingale noise term, and term ${\tau }_2$ denotes the error because of the Markov noise $\{Y_n\}$.

The following lemma shows that the function ${\sum }_{s\in \mathcal{S}}\pi (s)F(·,s)$ is a contraction. Let $〈x,x^{\prime }〉=x^T{x}^{\prime }$ and ${〈x,z〉}_D=x^{T}Dz$. Whereas the contraction property of the TD(0) algorithm is well-known (Tsitsiklis and Van Roy 1997), we obtain an explicit expression for the contraction factor.

Lemma 1.

For any $x,z\in {\mathbb{R}}^d$,

$$\Vert {\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)(F(x,s)-F(z,s))\Vert \le \alpha \Vert x-z\Vert ,$$

where

$$\alpha =\sqrt{1-\underset{x\ne \theta }{\min }\frac{\Vert \mathrm{\Phi }x{\Vert }_D^2}{\Vert x{\Vert }^2}(2(1-\gamma )-{\lambda }_M^2{(1+\gamma )}^2)}.$$

Moreover, $0<\alpha <1$, and hence, the function ${\sum }_{s\in \mathcal{S}}\pi (s)F(·,s)$ is a contraction.

The proof appears in Appendix B. The Banach contraction mapping theorem implies that ${\sum }_{s\in \mathcal{S}}\pi (s)F(·,s)$ has a unique fixed point $x^{*}$; that is, there exists a unique point $x^{*}$ such that ${\sum }_{s\in \mathcal{S}}\pi (s)F(x^{*},s)=x^{*}$. We next show that the fixed point $x^{*}$ is the required fixed point we wish to converge to. Before that, we first observe that

Then,

So $\mathrm{\Phi }{x}^{*}$ is the required fixed point of (1).

3. Main Result

Before stating the main result, we define the following two sequences. For $n\ge 0$,

Our main result is as follows:

Theorem 1.

There exist finite positive constants $c_1,c_2$ and D such that for $0<\delta \le 1,0<ϵ\le 1$, $n_0>0$ large enough to satisfy $\alpha +a(n_0)c_1<1$, and $n\ge n_0$,

1. the inequality

   $$\Vert x_m-x^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(m-1)}ϵ+\frac{a(n_0)(c_2+c_1ϵ)+\delta }{1-\alpha -a(n_0)c_1},\hspace{0.17em}\forall n_0\le m\le n,$$

   holds with probability exceeding

   $$1-2d{\displaystyle \sum _{m=n_0+1}^n{e}^{-D{\delta }^2/{\beta }_{n_0}(m-1)}}-P(\Vert x_{n_0}-x^{*}\Vert >ϵ).$$

2. In particular,

   $$\Vert x_m-x^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(m-1)}ϵ+\frac{a(n_0)(c_2+c_1ϵ)+\delta }{1-\alpha -a(n_0)c_1},\hspace{0.17em}\forall m\ge n_0,$$

holds with probability exceeding

$$1-2d{\displaystyle \sum _{m\ge n_0+1}{e}^{-D{\delta }^2/{\beta }_{n_0}(m-1n)}}-P(\Vert x_{n_0}-x^{*}\Vert >ϵ).$$

The following are some remarks about the theorem and the proof that follows.

Remark 1.

The assumption that $\delta \le 1$ and $ϵ\le 1$ is used in the proof for Lemma 3 and has been made only for simplicity. These can be taken as any positive values, with changes required only in the constant D.

Remark 2.

The term $P(\Vert x_{n_0}-x^{*}\Vert >ϵ)$ captures the unavoidable contribution of the initial condition at $n_0$. This can be bounded by combining moment bounds (Bhandari et al. 2018, Srikant and Ying 2019, Chen et al. 2021) with Markov’s inequality.

Remark 3.

In Chen et al. (2025), an all-time bound is obtained, which goes to zero as $m\uparrow \infty$. In our bound, the term $\frac{a(n_0)(c_2+c_1ϵ)+\delta }{1-\alpha -a(n_0)c_1}$ remains constant as m is increased. Here, $\delta$ can be modified to $\delta (m)$ (similar to the treatment in Chandak et al. 2022, corollary 1). But the term $a(n_0)(c_2+c_1ϵ)$ arises from our treatment of Markov noise using the Poisson equation. Note that Chen et al. (2025) do not consider the case of Markov noise, but only consider the case of additive and multiplicative noise (i.i.d. samples of state-action-next state triplets). We leave incorporating their ideas into our approach to get a bound decaying with m for Markov noise as future work.

Remark 4.

For the special case of $a(n)=\frac{d_1}{n+1}$, we combine our result with Chen et al. (2021, theorem 2.1), a mean square error bound, to get the following corollary.

Corollary 1.

Let $a(n)=d_1/(n+1)$ with sufficiently large $d_1$. Let $n_0$ be large enough to satisfy assumptions of Theorem 1 and Chen et al. (2021, theorem 2.1). Then, with probability at least $1-{\epsilon }_1-{\epsilon }_2$, we have, for all $m\ge n_0$, that

$$\Vert x_m-x^{*}\Vert =\mathcal{O}\left(\frac{1}{\sqrt{n_0}}{\log }^{1/2}\left(\frac{1}{{\epsilon }_1}\right)+\sqrt{\frac{\log (n_0)}{n_0}}\frac{1}{\sqrt{{\epsilon }_2}}\left(\frac{n_0}{m}+\frac{1}{n_0}\right)\right).$$

The proof for this corollary has been presented at the end of Appendix B. The first term here corresponds to the term $\delta$ in Theorem 1. This term has a $\sqrt{1/n_0}$ decay rate and an exponentially small tail. The second term is the contribution of the initial condition at $n_0$. We have a polynomial tail in this case, but the dependence on m and $n_0$ is stronger, as the term $(\sqrt{\log (n_0)}/\sqrt{n_0})\times (n_0/m)$ decays with m, and the other term decays as ${\log }^{1/2}(n_0)n_0^{-3/2}$.

4. Proof of the Main Result

We present the proof of the main theorem in this section. The key martingale concentration inequality used in our proof is stated in Appendix A, and proofs for the technical lemmas used in the proof are presented in Appendix B.

Proof of Theorem 1.

Define $z_n$ for $n\ge n_0$ by

$$z_{n+1}=z_n+a(n)\left({\displaystyle \sum _s\pi }(s)F(z_n,s)-z_n\right),$$

where $z_{n_0}=x_{n_0}$. Note that $\Vert x_n-x^{*}\Vert \le \Vert x_n-z_n\Vert +\Vert z_n-x^{*}\Vert$. To bound the second term, note that

$$\begin{array}{ll}{z}_{n+1}-x^{*}\hfill & =(1-a(n))(z_n-x^{*})+a(n)\left({\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)F(z_n,s)-x^{*}\right)\hfill \\ \hfill & =(1-a(n))(z_n-x^{*})+a(n){\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)(F(z_n,s)-F(x^{*},s)).\hfill \end{array}$$

The second equality follows from the fact that $x^{*}$ is a fixed point for ${\sum }_{s\in \mathcal{S}}\pi (s)F(·,s)$. Then,

$$\begin{array}{ll}\Vert z_{n+1}-x^{*}\Vert \hfill & \le (1-a(n))\Vert z_n-x^{*}\Vert +a(n)\Vert {\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)(F(z_n,s)-F(x^{*},s))\Vert \hfill \\ \hfill & \le (1-(1-\alpha )a(n))\Vert z_n-x^{*}\Vert .\hfill \end{array}$$

which finally gives us

$$\Vert z_n-x^{*}\Vert \le {\displaystyle \prod _{k=n_0}^{n-1}(1-(}1-\alpha )a(k))\Vert x_{n_0}-x^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(n-1)}\Vert x_{n_0}-x^{*}\Vert ,$$(4)

This also implies that for all $n\ge n_0$,

$$\Vert z_n\Vert \le \Vert x_{n_0}-x^{*}\Vert +\Vert x^{*}\Vert .$$(5)

Next, we give a probabilistic bound on the term $\Vert x_n-z_n\Vert$. Note that

$$\begin{array}{ll}{x}_{n+1}-z_{n+1}\hfill & =(1-a(n))(x_n-z_n)+a(n)M_{n+1}{x}_n+a(n)\left(F(x_n,Y_n)-{\displaystyle \sum _s\pi }(s)F(z_n,s)\right)\hfill \\ \hfill & =(1-a(n))(x_n-z_n)+\hspace{0.17em}a(n)M_{n+1}{x}_n+\hspace{0.17em}a(n)\left({\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)(F(x_n,s)-F(z_n,s))\right)\hfill \\ \hfill & \hspace{1em}+\hspace{0.17em}a(n)\left(F(x_n,Y_n)-{\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)F(x_n,s)\right).\hfill \end{array}$$

For $n,m\ge 0$, let $\chi (n,m)={\prod }_{k=m}^n(1-a(k))$ if $n\ge m$, and one otherwise. For some $n\ge n_0$, we iterate the above for $n_0\le m\le n$ to obtain

$$\begin{array}{ll}{x}_{m+1}-z_{m+1}\hfill & ={\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)M_{k+1}{x}_k\hfill \\ \hfill & +{\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\left({\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)(F(x_k,s)-F(z_k,s))\right)\hfill \\ \hfill & +{\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\left(F(x_k,Y_k)-{\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)F(x_k,s)\right).\hfill \end{array}$$(6)

Here, we use the definition that $x_{n_0}=z_{n_0}$. We first simplify the third term above. For simplicity, we define $F(x,Y)=F_1(Y)+F_2(Y)x+x,$ where

$$F_1(Y)=\phi (Y)r(Y)\in {\mathbb{R}}^d\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{F}_2(Y)=\left(\gamma \phi (Y){\displaystyle \sum _{s^{\prime }\in \mathcal{S}}p}(s^{\prime }|Y)\phi {(s^{\prime })}^T-\phi (Y)\phi {(Y)}^T\right)\in {\mathbb{R}}^{d\times d}.$$

We define $U:\mathcal{S}\mapsto {\mathbb{R}}^d$ to be a solution of the Poisson equation

$$U(s)=F_1(s)-{\displaystyle \sum _{s^{\prime }\in \mathcal{S}}\pi }(s^{\prime })F_1(s^{\prime })+{\displaystyle \sum _{s^{\prime }\in \mathcal{S}}p}(s^{\prime }|s)U(s^{\prime }),\hspace{0.17em}s\in \mathcal{S}.$$(7)

For $s_0\in \mathcal{S}$, $\tau ≔\min \{n>0:Y_n=s_0\}$, and $E_s[\cdots ]=E[\cdots |Y_0=s]$; we know that

$$U^{\prime }(s)=E_s\left[{\displaystyle \sum _{m=0}^{\tau -1}(F_1(}{Y}_m)-{\displaystyle \sum _{s^{\prime }\in \mathcal{S}}\pi }(s^{\prime })F_1(s^{\prime }))\right],\hspace{0.17em}s\in S$$(8)

is one particular solution to the Poisson equation (see, e.g., Borkar 1991, pp. 85–91, section VI.4, lemma 4.2 and theorem 4.2). Thus, $\Vert U^{\prime }(s){\Vert }_{\infty }\le 2{\max }_{s\in \mathcal{S}}\Vert F_1(s){\Vert }_{\infty }{E}_s[\tau ]$. For an irreducible Markov chain with a finite state space, $E_s[\tau ]$ is finite for all s, and hence, the solution $U^{\prime }(s)$ is bounded for all s. For each $\mathcal{\ell }$, the Poisson equation specifies $U^{\mathcal{\ell }}(·)$ uniquely only up to an additive constant. Along with the additional constraint that $U(s_0)=0$ for a prescribed $s_0\in S$, the system of equations given by (7) has a unique solution. Henceforth, U refers to the unique solution of the Poisson equation with $U(s_0)=0$. Similarly, let $W:\mathcal{S}\mapsto {\mathbb{R}}^{d\times d}$ be the unique solution of the Poisson equation

$$W(s)=F_2(s)-{\displaystyle \sum _{s^{\prime }}\pi }(s^{\prime })F_2(s^{\prime })+{\displaystyle \sum _{s^{\prime }}p}(s^{\prime }|s)W(s),\hspace{0.17em}s\in S,$$(9)

with the additional constraint that $W(s_0)=0$ for a prescribed $s_0\in S$ as above. $\square$

The following lemma gives a simplification of the third term in (6), using the solutions of the Poisson equation stated above. Before stating the lemma, we first define $x_m^{\prime }={\sup }_{n_0\le k\le m}\Vert x_m-z_m\Vert$.

Lemma 2.

There exist positive constants $c_1,c_2$ such that for all $n_0\le m\le n$,

$$\begin{array}{ll}\hfill & {\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\left(F(x_k,Y_k)-{\displaystyle \sum _{s\in \mathcal{S}}\pi }(s)F(x_k,s)\right)\hfill \\ \hfill & =\hspace{0.17em}{\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\left({\tilde{U}}_{k+1}+{\tilde{W}}_{k+1}{x}_k\right)+{\mu }_m(n_0),\hfill \end{array}$$

where

$$\Vert {\mu }_m(n_0)\Vert \le a(n_0)(c_2+c_1{x}_m^{\prime }+c_1\Vert x_{n_0}-x^{*}\Vert ).$$

Here, ${\tilde{U}}_{k+1}$ and ${\tilde{W}}_{k+1}{x}_k$ are martingale difference sequences with respect to ${\mathcal{F}}_k$, where ${\tilde{U}}_{k+1}=U(Y_{k+1})-{\sum }_{s^{\prime }}p(s^{\prime }|Y_k)U(s^{\prime })$ and ${\tilde{W}}_{k+1}=W(Y_{k+1})-{\sum }_{s^{\prime }}p(s^{\prime }|Y_k)W(s^{\prime })$ for $k\ge n_0$ and the zero vector, respectively, or the zero matrix, otherwise.

The proof appears in Appendix B. Returning to (6), we now have

Now,

For any $0<k\le m$,

and hence,

This implies that

Using the definition of $x_m^{\prime }$, we have

Next, we wish to obtain a bound on the probability

for some $ϵ>0$ and $\delta >0$ (recall the assumption that $\alpha +a(n_0)c_1<1$). For ease of notation, here, we have defined

From (4), recall that $\Vert z_n-x^{*}\Vert \le \exp (-(1-\alpha )b_{n_0}(n-1))\Vert x_{n_0}-x^{*}\Vert a.s.,$ and hence,

Also recall that ${\sup }_{n_0\le m\le n}\Vert x_m-z_m\Vert =x_n^{\prime }$. Hence,

This implies the following relation between the probabilities of the two sets:

To compensate for the lack of an almost-sure bound on the iterates $\{x_n\}$, we adapt the proof method from Tao and Vu (2015, proposition 34) (see Chung and Lu 2006, section 8, for a detailed explanation). For this, we define $\xi =\{x_0,Y_k,k\ge 0\}$ and the “bad” set ${\mathbb{B}}_m$ as

Here, the notation $x_m^{\prime }(\xi )$ and $x_{n_0}(\xi )$ highlights the dependence of $x_m^{\prime }$ and $x_{n_0}$ on the realizations of $x_0$ and $\{Y_k\}$. Analogous notation is used for other random variables. For $\xi \notin {\mathbb{B}}_{n-1}$, let us define ${\overline{x}}_{k,n-1}(\xi )=x_k(\xi )$ and ${\overline{z}}_{k,n-1}(\xi )=z_k(\xi )$ for all k. For $\xi \in {\mathbb{B}}_{n-1}$, we define ${\overline{x}}_{k,n-1}(\xi )=x^{*}$ and ${\overline{z}}_{k,n-1}(\xi )=x^{*}$ for all k. Also, define ${\overline{x}}_{m,n-1}^{\prime }(\xi )={\sup }_{n_0\le k\le m}\Vert {\overline{x}}_{k,n-1}(\xi )-{\overline{z}}_{k,n-1}(\xi )\Vert$. Note that ${\overline{x}}_{m,n-1}^{\prime }=0$ when $\xi \in {\mathbb{B}}_{n-1}$, and ${\overline{x}}_{m,n-1}^{\prime }=x_m^{\prime }\le \mathrm{\Delta }(n_0,ϵ,\delta )$ when $\xi \notin {\mathbb{B}}_{n-1}$. The intuition behind these definitions is that ${\overline{x}}_{m,n-1}^{\prime }$ is always bounded by $\mathrm{\Delta }(n_0,ϵ,\delta )$ for all $m\le n-1$.

Note that $\xi \notin {\mathbb{B}}_{n-1}\Rightarrow {\overline{x}}_{n,n-1}^{\prime }(\xi )=x_n^{\prime }(\xi )$, which implies $P({\overline{x}}_{n,n-1}^{\prime }(\xi )\ne x_n^{\prime }(\xi ))\le P({\mathbb{B}}_{n-1}).$ Henceforth, we drop $\xi$ for ease of notation, rendering implicit the dependence of all random variables on $\xi$. Then,

Inequality (a) here follows from the observation that

which implies thatwhich gives us the required inequality. Inequality (b) follows from union bound, and inequality (c) follows from the observations that $\{\Vert x_{n_0}-x^{*}\Vert >ϵ\}\subseteq {\mathbb{B}}_{n-1}$ and $\{{\overline{x}}_{n,n-1}^{\prime }\ne x_n^{\prime }\}\subseteq {\mathbb{B}}_{n-1}$.

Now, we obtain a bound for $P({\overline{x}}_{n,n-1}^{\prime }>\mathrm{\Delta }(n_0,ϵ,\delta ))$ by induction. We first note that ${\overline{x}}_{n-1,n-1}^{\prime }$ is bounded by $\mathrm{\Delta }(n_0,ϵ,\delta )$ by definition. Hence, $P({\overline{x}}_{n,n-1}^{\prime }>\mathrm{\Delta }(n_0,ϵ,\delta ))=P(\Vert {\overline{x}}_{n,n-1}-{\overline{z}}_{n,n-1}\Vert >\mathrm{\Delta }(n_0,ϵ,\delta ))$. We first restate (11) for $m=n-1$.

Now, let $I\{·\}$ denote the indicator function, which is one when $\{·\}$ holds true, and zero otherwise.

Here, inequality (a) follows from our definition of ${\mathbb{B}}_{n-1}$ that $\Vert {\overline{x}}_{n,n-1}-{\overline{z}}_{n,n-1}\Vert =0$ when ${\xi }_{n-1}\in {\mathbb{B}}_{n-1}$ and $x_n={\overline{x}}_{n,n-1}$ when ${\xi }_{n-1}\notin {\mathbb{B}}_{n-1}$. Inequality (b) follows from the fact that when ${\xi }_{n-1}\notin {\mathbb{B}}_{n-1}$, then $x_k={\overline{x}}_{k,n-1}$ for all k, and $\Vert x_{n_0}-x^{*}\Vert \le ϵ$. Substituting the expression for $\mathrm{\Delta }(n_0,ϵ,\delta )$, we obtain the following:

When

we have

Hence,

Let us denote the probability on the right side of the inequality as $p_{n-1}$. Then,

Then, repeating the same procedure using ${\mathbb{B}}_{n-2}$, we obtain

Iterating this for $n\ge m\ge n_0+1$, we get

The probabilities $p_m$ can be bounded using standard martingale inequalities as the terms of the martingale difference sequence are almost surely bounded. The following lemma, proved in Appendix B, gives a bound on the probabilities $p_m$:

Lemma 3.

There exists positive constant D such that for $0<ϵ\le 1,0<\delta \le 1$,

$$p_m\le 2d{e}^{-D{\delta }^2/{\beta }_{n_0}(m)}.$$

Recall that d here denotes the dimension of the iterates $\{x_n\}$.

This completes the proof for the first part of Theorem 1.

Let $A_n$ be the set

Then, $\{A_n\}$ is a decreasing sequence of sets; that is, $A_{n+1}\subseteq A_n$ for all $n\ge n_0$. Now, let A be the set

Then, $A={\cap }_{n=n_0}^{\infty }{A}_n$. Hence, $P(A)={\lim }_{n\uparrow \infty }P(A_n)$. This completes the proof for Theorem 1.

5. Conclusions

In conclusion, we note some future directions. The concept of relaxed martingale concentration inequalities can be used to obtain bounds of the similar flavor for algorithms that suffer from similar issues. These include TD($\lambda$) and SSP Q-Learning. Alternatively, similar bounds can be obtained for variants of temporal difference learning (Chen et al. 2021). Another direction could be to improve the bounds in this paper to get an exponentially small tail for Markovian stochastic approximation.