Concentration of Contractive Stochastic Approximation and Reinforcement Learning

1. Introduction

In recent years, there has been a lot of interest in obtaining bounds for finite time behavior of reinforcement learning algorithms. These are either moment bounds, for example, mean square error after finitely many samples, or high probability concentration bounds. A representative, but possibly nonexhaustive sample is as follows: Bhandari et al. (2018), Chen et al. (2020; 2021), Wang et al. (2020), Dalal et al. (2018a; b), Li et al. (2020; 2021), Even-Dar and Mansour (2004), Prashanth et al. (2021), Qu and Wierman (2020), Sidford et al. (2018), Srikant and Ying (2019), and Wainwright (2019a; b). A parallel activity in stochastic approximation theory (of which most reinforcement learning algorithms are special instances) seeks to get a concentration bound for the iterates from some time on, to be precise, “for all $n\ge n_0$ for a suitably chosen n₀” (Borkar 2002, Kamal 2010, Thoppe and Borkar 2019). See Borkar (2000) for an application to reinforcement learning.

Inspired by Chen et al. (2020), one of us considered stochastic approximation involving contractive maps and martingale noise and derived such concentration bounds “from some n₀ on” for this class of algorithms (Borkar 2021). In addition, Borkar (2021) indicated how to stitch such bounds with finite time bounds to get concentration bounds for all time. This covered, in particular, synchronous Q-learning for discounted cost and some related schemes. However, it did not cover the asynchronous case, which is of greater importance. Nor could it cover some other algorithms such as TD(0). The missing link was the absence of the so-called “Markov noise” in stochastic approximation, originally introduced in Meerkov (1972) (see also Kushner and Shwartz (1984) for a landmark article and Benveniste et al. (2012) for a book length treatment). The present work fills in this lacuna, extending the applicability of this program to a much larger class of algorithms. In fact, we work out in detail the cases of asynchronous Q-learning and TD(0).

There is also a parallel body of work that seeks bound, either finite time or asymptotic (e.g., in terms of regret) on the difference between the value function under the learned policy and the optimal value function (Jin et al. 2018, Yang and Wang 2019, Yang et al. 2020). Once again, this is distinct from our objective, which is to obtain a high probability bound valid for all time from some time on.

To clarify further, conventional concentration or sample complexity bounds get bounds, for example, mean square or “with high probability” bounds, on the error from the target after n iterations starting from time zero. The asymptotic regret bounds get an upper bound or lower bound or both on how some measure of cumulative error grows with time in an asymptotic sense. Our bounds differ from both. They are “all time bounds” in the sense that they give a high probability bound for the iterates to remain in a prescribed small neighborhood of the target for all time from some time n₀ onward. In fact, the requirement from some n₀ onward is dictated by the fact that the decreasing step size needs to be sufficiently small from n₀ on. Thus, if the step size is sufficiently small from the beginning, this qualification can be dropped. Alternatively, we can stitch our bounds with one of the existing finite time bounds to obtain all time bounds. We illustrate this possibility with an example in Section 4. The time n₀ on bound depends on the norm of the iterate at time n₀, but this in turn can be bounded in terms of the norm of the initialization. As for regret bounds, these are for cumulative error and are typically almost sure or in mean and asymptotic in nature unlike our bounds, which are from some time on, but with high probability.

The rest of the paper is organized as follows. Section 2 sets up and states the main result, also highlighting an important special case. The result is proved in Section 3. Section 4 presents some consequences of the theorem. In Section 5, we apply our main result to asynchronous Q-learning and the TD(0) algorithm. A concluding section highlights some future directions. Finally, there are two appendices: Appendix A states a martingale concentration inequality used in our proof, whereas Appendix B details a technical issue left out of the main text for ease of reading.

Throughout this work, $\Vert ·\Vert$ denotes any compatible norm on ${\mathcal{R}}^d$. We use θ to denote the zero vector in ${\mathcal{R}}^d$. The $\ell$ th component of a vector x and a vector valued function $h(·)$ are denoted by $x(\ell )$ and $h^{\ell }(·)$, respectively. We use the convention $\frac{0}{0}=0$ throughout this work.

2. Main Result

We state and prove our main theorem in this section, after setting up the notation and assumptions. The assumptions are specifically geared for the reinforcement learning applications that follow in Section 5, as will become apparent.

Consider the iteration

for $x_n={[x_n(1),\dots ,x_n(d)]}^T\in {\mathcal{R}}^d$. Here,

• The random process $\{Y_n\}$ is the Markov noise taking values in a finite state space S, that is,

  $$\begin{array}{l}P(Y_{n+1}|Y_m,x_m,m\le n)=P(Y_{n+1}|Y_n,x_n)\\ =p_{x_n}(Y_{n+1}|Y_n),\hspace{0.17em}n\ge 0,\end{array}$$
  where for each w, $p_w(·|·)$ is the transition probability of an irreducible Markov chain on S with unique stationary distribution π_w. We assume that the map $w\mapsto p_w(j|i)$ is Lipschitz in the following sense:
  $${\displaystyle \sum _{j\in S}|}{p}_w(j|i)-p_v(j|i)|\le L_1\Vert w-v\Vert ,\hspace{0.17em}\forall i\in S,w,v\in {\mathcal{R}}^d,$$
  for some $L_1>0$. This implies that the map $w\mapsto {\pi }_w(i)$ is similarly Lipschitz, that is,
  $${\displaystyle \sum _{i\in S}|}{\pi }_w(i)-{\pi }_v(i)|\le L_2\Vert w-v\Vert ,\hspace{0.17em}\forall i\in S,w,v\in {\mathcal{R}}^d,$$
  for some $L_2>0$. See part (ii) of Appendix B for some bounds on L₂.

• The random process $\{M_n(x)\}$ is, for each $x\in {\mathcal{R}}^d$, an ${\mathcal{R}}^d$-valued martingale difference sequence parametrized by x, with respect to the increasing family of σ-fields ${\mathcal{F}}_n≔\sigma (x_0,Y_m,M_m(x),x\in {\mathcal{R}}^d,m\le n),\hspace{0.17em}n\ge 0$. That is,

  $$E[M_{n+1}(x)|{\mathcal{F}}_n]=\theta ;\hspace{0.17em}\text{a}.\text{s}.;\hspace{0.17em}\forall x,n,$$(2)
  where θ denotes the zero vector. We also assume the componentwise bound:
  $$|M_n^{\ell }(x)|\le K_0(1+\Vert x\Vert );\text{a}.\text{s}.;\forall x,n,l,$$(3)
  for some $K_0>0$.

• The function $F(·)={[F^1(·),\cdots ,F^d(·)]}^T:{\mathcal{R}}^d\times S\to {\mathcal{R}}^d$ satisfies

  $$\Vert {\displaystyle \sum _{i\in S}{\pi }_w}(i)(F(x,i)-F(z,i))\Vert \le \alpha \Vert x-z\Vert ,\hspace{0.17em}\forall x,z,w\in {\mathcal{R}}^d,$$(4)
  for some $\alpha \in (0,1)$. By the Banach contraction mapping theorem, (4) implies that ${\sum }_i{\pi }_w(i)F(·,i)$ has a unique fixed point $x_w^{*}\in {\mathcal{R}}^d$ (i.e., ${\sum }_i{\pi }_w(i)F(x_w^{*},i)=x_w^{*})$. We assume that this fixed point is independent of w; that is, there exists a $x^{*}$ such that
  $${\displaystyle \sum _{i\in S}{\pi }_w}(i)F(x^{*},i)=x^{*},\hspace{0.17em}\forall w\in {\mathcal{R}}^d.$$(5)

  We also assume that the map $x\mapsto F^{\ell }(x,i)$ is Lipschitz, uniformly in i and $\ell$. Let the common Lipschitz constant be $L_3>0$, that is,

  $$|F^{\ell }(x,i)-F^{\ell }(z,i)|\le L_3\Vert x-z\Vert ,\hspace{0.17em}\forall i\in S,\ell \in \{1,\cdots ,d\},x,z\in {\mathcal{R}}^d.$$

  Furthermore, ${\tilde{F}}_n(x,Y_n)≔F(x,Y_n)+M_{n+1}(x)$ is assumed to satisfy

  $$\Vert {\tilde{F}}_n(x,Y_n)\Vert \le K+\alpha \Vert x\Vert ;\hspace{0.17em}\text{a}.\text{s}\mathrm{..}$$(6)

• The sequence $\{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 ,$$(7)
  and is assumed to be eventually nonincreasing; that is, there exists $n^{*}\ge 1$ such that $a(n+1)\le a(n)\hspace{0.17em}\forall n\ge n^{*}$. Since $a(n)\to 0$, there exists $n^{†}$ such that a(n) < 1 for all $n>n^{†}$. Observe that we do not require the classical square-summability condition in stochastic approximation, viz., ${\sum }_{n}a{(n)}^2<\infty$. This is because the contractive nature of our iterates gives us an additional handle on errors by putting less weight on past errors. A similar effect was observed in Thoppe and Borkar (2019).

We further assume that $a(n)=\mathrm{\Omega }(1/n)$. Therefore, $a(n)\ge \frac{d_1}{n}$ for all $n\ge n_1$ for some n₁ and $d_1>0$. We also assume that there exists $0<d_2\le 1$ such that $a(n)=\mathcal{O}\left({\left(\frac{1}{n}\right)}^{d_2}\right)$, that is, $a(n)\le d_3{\left(\frac{1}{n}\right)}^{d_2}$ for all $n\ge n_2$ for some n₂ and $d_3>0$. Larger values of d₁ and d₂ and smaller values of d₃ improve the main result presented later. The role this assumption plays in our bounds will become clear later. Define $N≔\max \{n^{*},n^{†},n_1,n_2\}$, that is, a(N) < 1, a(n) is nonincreasing after N, and $\frac{d_1}{n}\le a(n)\le d_3{\left(\frac{1}{n}\right)}^{d_2},\forall n\ge N$.

For $n\ge 0$, we further define

Our main result is as follows.

Theorem 1.

Let $n_0\ge N$. Then there exist finite positive constants c₁, c₂, and D, depending on $\Vert x_N\Vert$, such that for $\delta >0,\hspace{0.17em}n\ge n_0$ and $C=e^{\kappa (d)\left(K_0\left(1+\Vert x_N\Vert +\frac{K}{1-\alpha }\right)+c_2\right)}$,

• (a) the inequality

  $$\Vert x_n-x^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(n-1)}\Vert x_{n_0}-x^{*}\Vert +\frac{\delta +a(n_0)c_1}{1-\alpha },$$(8)
  holds with probability exceeding
  $$1\hspace{0.17em}-\hspace{0.17em}2d{\displaystyle \sum _{m=n_0+1}^n{e}^{-D{\delta }^2/{\beta }_{n_0}(m)}},\hspace{0.17em}0<\delta \le C,$$(9)
  $$1\hspace{0.17em}-\hspace{0.17em}2d{\displaystyle \sum _{m=n_0+1}^n{e}^{-D\delta /{\beta }_{n_0}(m)}},\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\delta >C.$$(10)

• (b) In particular,

  $$\Vert x_n-x^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(n-1)}\Vert x_{n_0}-x^{*}\Vert +\frac{\delta +a(n_0)c_1}{1-\alpha }\hspace{0.17em}\forall n\ge n_0,$$(11)
  with probability exceeding
  $$1\hspace{0.17em}-\hspace{0.17em}2d{\displaystyle \sum _{m\ge n_0+1}{e}^{-D{\delta }^2/{\beta }_{n_0}(m)}},\hspace{0.17em}0<\delta \le C,$$(12)
  $$1\hspace{0.17em}-\hspace{0.17em}2d{\displaystyle \sum _{m\ge n_0+1}{e}^{-D\delta /{\beta }_{n_0}(m)}},\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\delta >C.$$(13)

For (12) and (13), note that ${\beta }_{n_0}(m)$ is $O\left(\frac{1}{m^c}\right)$ for some constant c and therefore $e^{-D/{\beta }_{n_0}(m)}$ is summable. Furthermore, ${\sum }_{m\ge n_0}{e}^{-D/{\beta }_{n_0}(m)}\downarrow 0$ as $n_0\uparrow \infty$.

Remark 1.

An important special case of the previous theorem is when $\{Y_n\}$ is a time homogeneous and uncontrolled Markov chain. In that case

$$\begin{array}{l}P(Y_{n+1}|Y_m,x_m,m\le n)=P(Y_{n+1}|Y_n)\\ =p(Y_{n+1}|Y_n),\hspace{0.17em}n\ge 0,\end{array}$$

with unique stationary distribution π. Assumption (4) is now modified to

$$\Vert {\displaystyle \sum _{i\in S}\pi }(i)(F(x,i)-F(z,i))\Vert \le \alpha \Vert x-z\Vert ,\hspace{0.17em}x,z\in {\mathcal{R}}^d$$(14)

for some $\alpha \in (0,1)$. By the Banach contraction mapping theorem, (14) implies that ${\sum }_i\pi (i)F(·,i)$ has a unique fixed point $x^{*}\in {\mathcal{R}}^d$ (i.e., ${\sum }_i\pi (i)F(x^{*},i)=x^{*})$. Hence, we no longer need Assumption (5). The rest of the assumptions remain the same. The statement of the theorem also remains the same.

Remark 2.

The constants c₁ and c₂ depend on $\Vert x_N\Vert$, which in turn has a bound depending on $\Vert x_0\Vert$ that can be derived easily using the discrete Gronwall inequality under our assumptions. Also note that if a(n) are decreasing and $a(0)<1$, then we can take N = 0. The calculations in Appendix B show that c₁ depends on quantities that essentially depend on the mean hitting time of a fixed state, which is also related to mixing. Thus, one expects this constant to be lower for faster mixing chains. The exact dependence, however, is not simple.

3. Proof of the Main Theorem

We begin with a lemma adapted from Borkar (2021) that bounds the iterates $\{x_n\}$ using (6).

Lemma 1.

Almost surely (a.s.), ${\sup }_{n\ge N}\Vert x_n\Vert \le \Vert x_N\Vert +\frac{K}{1-\alpha }.$

Proof.

Using (6), we have

$$\begin{array}{l}\Vert x_{n+1}\Vert =\Vert (1-a(n))x_n+a(n){\tilde{F}}_n(x_n,Y_n)\Vert \\ \le (1-a(n))\Vert x_n\Vert +a(n)(K+\alpha \Vert x_n\Vert )\\ =(1-(1-\alpha )a(n))\Vert x_n\Vert +a(n)K.\end{array}$$

For $n,m\ge N$, define $\psi (n,m)≔{\prod }_{k=m}^{n-1}(1-(1-\alpha )a(k))$ if n > m and one otherwise. Because a(N) < 1, $0\le \psi (n,m)\le 1$ for all $n,m\ge N$. Then

$$\Vert x_{n+1}\Vert -\frac{K}{1-\alpha }\le (1-(1-\alpha )a(n))\left(\Vert x_n\Vert -\frac{K}{1-\alpha }\right).$$

Now $\Vert x_N\Vert \le \Vert x_N\Vert +\frac{K}{1-\alpha }=\psi (N,N)\Vert x_N\Vert +\frac{K}{1-\alpha }$. Suppose

$$\Vert x_n\Vert \le \psi (n,N)\Vert x_N\Vert +\frac{K}{1-\alpha }$$(15)

for some $n\ge N$. Then,

$$\begin{array}{l}\Vert x_{n+1}\Vert -\frac{K}{1-\alpha }\le (1-(1-\alpha )a(n))\left(\psi (n,N)\Vert x_N\Vert +\frac{K}{1-\alpha }-\frac{K}{1-\alpha }\right)\\ \le \psi (n+1,N)\Vert x_N\Vert .\end{array}$$

By induction, (15) holds for all $n\ge N$, which completes the proof of Lemma 1. □

Proof of Theorem 1.

Define z_n for $n\ge n_0$ by

$$z_{n+1}=z_n+a(n)\left({\displaystyle \sum _{i\in \mathcal{S}}{\pi }_{x_n}}(i)F(z_n,i)-z_n\right),$$(16)

where $z_{n_0}=x_{n_0}$. Then

$$\begin{array}{c}{x}_{n+1}-z_{n+1}=(1-a(n))(x_n-z_n)+a(n)M_{n+1}\\ +\hspace{0.17em}a(n)\left(F(x_n,Y_n)-{\displaystyle \sum _{i\in \mathcal{S}}{\pi }_{x_n}}(i)F(z_n,i)\right)\end{array},$$(17)

$$\begin{array}{c}=(1-a(n))(x_n-z_n)+\hspace{0.17em}a(n)M_{n+1}\\ +\hspace{0.17em}a(n)\left({\displaystyle \sum _{i\in \mathcal{S}}{\pi }_{x_n}}(i)(F(x_n,i)-F(z_n,i))\right)\\ +\hspace{0.17em}a(n)\left(F(x_n,Y_n)-{\displaystyle \sum _{i\in \mathcal{S}}{\pi }_{x_n}}(i)F(x_n,i)\right).\end{array}$$(18)

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}{c}{x}_{m+1}-z_{m+1}={\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)M_{k+1}\\ +{\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\left({\displaystyle \sum _{i\in \mathcal{S}}{\pi }_{x_k}}(i)(F(x_k,i)-F(z_k,i))\right)\\ +{\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\left(F(x_k,Y_k)-{\displaystyle \sum _{i\in \mathcal{S}}{\pi }_{x_k}}(i)F(x_k,i)\right).\end{array}$$(19)

To simplify (19), we define $V(·,·)={[V^1(·,·):V^2(·,·):\cdots \cdots :V^d(·,·)]}^T$ to be a solution of the Poisson equation:

$$V(x,i)=F(x,i)-{\displaystyle \sum _{j\in \mathcal{S}}{\pi }_x}(j)F(x,j)+{\displaystyle \sum _{j\in \mathcal{S}}{p}_x}(j|i)V(x,j),\hspace{0.17em}i\in S.$$(20)

For $i_0\in S,\hspace{0.17em}\tau ≔\min \{n>0:Y_n=i_0\}$ and $E_i[·]=E[·|Y_0=i]$, we know that

$$V_1(x,i)=E_i\left[{\displaystyle \sum _{m=0}^{\tau -1}(F(}x,Y_m)-{\displaystyle \sum _{j\in \mathcal{S}}{\pi }_x}(j)F(x,j))\right],\hspace{0.17em}i\in S,$$(21)

is a solution to the Poisson equation (lemma 4.2 and theorem 4.2 of section VI.4, pp. 85–91, of Borkar 1991). Thus, $\Vert V_1(x,i){\Vert }_{\infty }\le 2{\max }_i\Vert F(x,i){\Vert }_{\infty }{E}_i[\tau ]$. For an irreducible Markov chain with a finite state space, $E_i[\tau ]$ is finite for all i and hence the solution $V_1(x,i)$ is bounded for all x, i. For each x and $\ell$, the Poisson equation specifies $V^{\ell }(x,·)$ uniquely only up to an additive constant. Adding or subtracting a scalar $c^{\ell }(x)$ to $V^{\ell }(x,i)$ for each state i still gives us a solution of the Poisson equation. Along with the additional constraint that $V(x,i_0)=0,\hspace{0.17em}\forall x$ and for a prescribed $i_0\in S$, the system of equations given by (20) has a unique solution. Henceforth, V refers to the unique solution of the Poisson equation with $V(x,i_0)=0,\hspace{0.17em}\forall x$. For this solution, the mapping $x\mapsto V^{\ell }(x,i)$ is Lipschitz for all $i\in S,\hspace{0.17em}\ell \in \{1,\cdots d\}$ and $x\in {\mathcal{R}}^d$ with the common constant L (proof in Appendix B, part (ii)).

We define V_max as

$$V_{\mathit{max}}≔\underset{\Vert x\Vert \le \Vert x_N\Vert +\frac{K}{1-\alpha }}{\max }\underset{i\in S}{\max }\Vert V(x,i)\Vert .$$(22)

Similarly, we also define

$$V{\prime }_{\mathit{max}}≔\underset{\Vert x\Vert \le \Vert x_N\Vert +\frac{K}{1-\alpha }}{\max }\underset{i\in S,1\le \ell \le d}{\max }|V^{\ell }(x,i)|.$$(23)

Using the definition of V to simplify the last term in (19), we have

$$\begin{array}{l}{\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\left(F(x_k,Y_k)-{\displaystyle \sum _i{\pi }_{x_k}}(i)F(x_k,i)\right)\\ \text{}={\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\left(V(x_k,Y_k)-{\displaystyle \sum _j{p}_{x_k}}(j|Y_k)V(x_k,j)\right)\\ \text{}={\displaystyle \sum _{k=n_0+1}^m\chi }(m,k+1)a(k)\left(V(x_k,Y_k)-{\displaystyle \sum _j{p}_{x_{k-1}}}(j|Y_{k-1})V(x_k,j)\right)\end{array}$$(24a)

$$\hspace{0.17em}+{\displaystyle \sum _{k=n_0+1}^m\left((\chi (m,k+1)a(k)-\chi (m,k)a(k-1)){\displaystyle \sum _j{p}_{x_{k-1}}}(j|Y_{k-1})V(x_k,j)\right)}$$(24b)

$$\hspace{0.17em}+{\displaystyle \sum _{k=n_0+1}^m\chi }(m,k)a(k-1)\left({\displaystyle \sum _j{p}_{x_{k-1}}}(j|Y_{k-1})(V(x_k,j)-V(x_{k-1},j))\right)$$(24c)

$$\hspace{0.17em}+\chi (m,n_0+1)a(n_0)V(x_{n_0},Y_{n_0})-\chi (m,m+1)a(m){\displaystyle \sum _j{p}_{x_m}}(j|Y_m)V(x_m,j).$$(24d)

Define ${\tilde{V}}_k(x_k)≔V(x_k,Y_k)-{\sum }_j{p}_{x_{k-1}}(j|Y_{k-1})V(x_k,j)$ for $k\ge n_0$ and zero otherwise. This is a martingale difference sequence. We bound the norm of (24b) as follows:

$$\begin{array}{l}\Vert {\displaystyle \sum _{k=n_0+1}^m\left((\chi (m,k+1)a(k)-\chi (m,k)a(k-1)){\displaystyle \sum _{j\in S}{p}_{x_{k-1}}}(j|Y_{k-1})V(x_k,j)\right)}\Vert \\ \le \Vert {\displaystyle \sum _{k=n_0+1}^m((}\chi (m,k+1)a(k)-\chi (m,k+1)a(k-1)){\displaystyle \sum _{j\in S}{p}_{x_{k-1}}}(j|Y_{k-1})V(x_k,j))\Vert \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\Vert {\displaystyle \sum _{k=n_0+1}^m((}\chi (m,k+1)a(k-1)-\chi (m,k)a(k-1)){\displaystyle \sum _{j\in S}{p}_{x_{k-1}}}(j|Y_{k-1})V(x_k,j))\Vert \\ \le {\displaystyle \sum _{k=n_0+1}^m((}a(k-1)-a(k))\chi (m,k+1)V_{\mathit{max}})+{\displaystyle \sum _{k=n_0+1}^m((}\chi (m,k+1)-\chi (m,k))a(k-1)V_{\mathit{max}})\\ \le {\displaystyle \sum _{k=n_0+1}^m((}a(k-1)-a(k))V_{\mathit{max}})+{\displaystyle \sum _{k=n_0+1}^m((}\chi (m,k+1)-\chi (m,k))a(n_0)V_{\mathit{max}})\\ =(a(n_0)-a(m))V_{\mathit{max}}+(\chi (m,m+1)-\chi (m,n_0+1))a(n_0)V_{\mathit{max}}\\ \le 2a(n_0)V_{\mathit{max}}.\end{array}$$(25)

The third inequality follows from $a(k-1)-a(k)\ge 0$ because a(k) is a nonincreasing sequence for $k>n_0$, and $\chi (m,k+1)-\chi (m,k)$ is positive because $1\ge \chi (m,k+1)\ge \chi (m,k)$ for $m,k>n_0$, as a(k) < 1 for $k>n_0$.

We next obtain a bound on the norm of (24c). Using Lemma 1, we know that $\Vert x_n\Vert \le \Vert x_N\Vert +\frac{K}{1-\alpha },\hspace{0.17em}n\ge N$. For simplicity, define $K^{*}≔\Vert x_N\Vert +\frac{K}{1-\alpha }$. Note that $K^{*}$ is a random constant because of its linear dependence on $\Vert x_N\Vert$. Now,

$$\begin{array}{l}\Vert x_k-x_{k-1}\Vert =\Vert a(k-1)(F(x_{k-1},Y_{k-1})-x_{k-1}+M_k(x_{k-1}))\Vert \\ \le a(k-1)(\Vert {\tilde{F}}_{k-1}(x_{k-1},Y_{k-1})\Vert +\Vert x_{k-1}\Vert )\\ \le a(k-1)(K+\alpha \Vert x_{k-1}\Vert +\Vert x_{k-1}\Vert )\\ \le a(k-1)(K+(1+\alpha )K^{*})\\ \le a(n_0)(K+(1+\alpha )K^{*}).\end{array}$$

For the last inequality, $k-1\ge n_0$ and hence $a(k-1)\le a(n_0).$ Now, for any $0<k\le m$,

$$\chi (m,k)+\chi (m,k+1)a(k)=\chi (m,k+1),$$

and hence

$$\chi (m,n_0)+{\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)=\chi (m,m+1)=1.$$

This implies that

$${\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\hspace{0.17em}\le \hspace{0.17em}1.$$(26)

This implies that

$$\begin{array}{l}\Vert {\displaystyle \sum _{k=n_0+1}^m\chi }(m,k)a(k-1)\left({\displaystyle \sum _j{p}_{x_{k-1}}}(j|Y_{k-1})(V(x_k,j)-V(x_{k-1},j))\right)\Vert \\ \le {\displaystyle \sum _{k=n_0+1}^m\chi }(m,k)a(k-1)\Vert {\displaystyle \sum _j{p}_{x_{k-1}}}(j|Y_{k-1})(V(x_k,j)-V(x_{k-1},j))\Vert \\ \stackrel{(a)}{\le }La(n_0)(K+(1+\alpha )K^{*})\\ \le a(n_0)\left(L(K+2K^{*})\right).\end{array}$$(27)

Inequality (a) is obtained using the Lipschitz nature of V. Define constant $K^{†}≔L(K+2K^{*})$. Now, the norm of (24d) is directly bounded by $2a(n_0)V_{\mathit{max}}$. For simplicity, define $V_c(n_0)≔a(n_0)(4V_{\mathit{max}}+K^{†})$.

Recall that $\kappa (d)=\Vert \mathbf{1}\Vert$, where $\mathbf{1}$ is the d-vector of all ones. Define

$$\begin{array}{l}{\mathrm{\Gamma }}_k=\kappa (d)\underset{l}{\max }\left|{\displaystyle \sum _{r=n_0}^{k-1}\chi }(k,r+1)a(r)(M_{r+1}^{\ell }(x_r)+{\tilde{V}}_r^{\ell }(x_r))\right|,\\ \text{and}\hspace{0.17em}\hspace{0.17em}{\zeta }_m=\underset{n_0\le k\le m}{\max }{\mathrm{\Gamma }}_k.\end{array}$$

Returning to (19), we now have

$$\begin{array}{c}\Vert x_{m+1}-z_{m+1}\Vert \le \Vert {\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)({\displaystyle \sum _{i\in S}{\pi }_{x_k}}(i)(F(x_k,i)-F(z_k,i)))\Vert +{\mathrm{\Gamma }}_{m+1}+V_c(n_0)\\ \le \Vert {\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)({\displaystyle \sum _{i\in S}{\pi }_{x_k}}(i)(F(x_k,i)-F(z_k,i)))\Vert +{\zeta }_{m+1}+V_c(n_0)\\ \le \alpha {\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)\Vert x_k-z_k\Vert +{\zeta }_{m+1}+V_c(n_0).\end{array}$$(28)

Let $x{\prime }_m={\sup }_{n_0\le k\le m}\Vert x_k-z_k\Vert$ for $n_0\le m<n$. Then using (26) and the fact that ${\zeta }_m\le {\zeta }_n$,

$$\begin{array}{c}x{\prime }_{m+1}\le \alpha x{\prime }_m{\displaystyle \sum _{k=n_0}^m\chi }(m,k+1)a(k)+{\zeta }_n+V_c(n_0)\\ \le \alpha x{\prime }_m+{\zeta }_n+V_c(n_0).\end{array}$$(29)

Because $x{\prime }_{m+1}\ge x{\prime }_m$ and $x{\prime }_{n_0}=\theta$, we have

$$x{\prime }_m\le \frac{1}{1-\alpha }({\zeta }_n+V_c(n_0)),\hspace{0.17em}{n}_0\le m\le n.$$(30)

By Lemma 1, $|M_{n+1}^{\ell }(x_n)|\le K_0(1+\Vert x_{n_0}\Vert +\frac{K}{1-\alpha })$. Also, $|{\tilde{V}}_n^{\ell }(x_n)|\le 2V{\prime }_{\mathit{max}}$. In Theorem A.1 of Appendix A, let

$$\begin{array}{l}C=e^{\kappa (d)(K_0(1+\Vert x_{n_0}\Vert +\frac{K}{1-\alpha })+2V{\prime }_{\mathit{max}})},\hspace{0.17em}{\xi }_{m,n}=\chi (n,m+1)a(m),\\ \epsilon =1,\hspace{0.17em}{\gamma }_1=1.\end{array}$$

Next, we choose suitable γ₂ and $\omega (n)$ such that

$$\underset{n_0\le m\le n}{\max }{\xi }_{m,n}=\underset{n_0\le m\le n}{\max }\chi (n,m+1)a(m)\le {\gamma }_2\omega (n).$$

For this, we use our assumption that $\frac{d_1}{n}\le a(n)\le d_3{\left(\frac{1}{n}\right)}^{d_2},\forall n\ge n_0$, to obtain

$$\begin{array}{l}\chi (n,m+1)={\displaystyle \prod _{k=m+1}^n(1-a(}k))\le \exp \left(-{\displaystyle \sum _{k=m+1}^{n}a}(k)\right)\le \exp \left(-{\displaystyle \sum _{k=m+1}^n\frac{d_1}{k}}\right)\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\le \exp \left(-{\displaystyle {\int }_{m+1}^n\frac{d_1}{y}}dy\right)\le \exp \left(d_1(\log (m+1)-\log (n))\right)\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}={\left(\frac{m+1}{n}\right)}^{d_1}\\ \Rightarrow \underset{n_0\le m\le n}{\max }a(m)\chi (n,m+1)\le \underset{n_0\le m\le n}{\max }{d}_3{\left(\frac{1}{m}\right)}^{d_2}{\left(\frac{m+1}{n}\right)}^{d_1}\le \underset{n_0\le m\le n}{\max }{d}_3{\left(\frac{1}{m}\right)}^{d_2}{\left(\frac{2m}{n}\right)}^{d_1}.\end{array}$$

From the last inequality, ${\gamma }_2=d_3{2}^{d_1}$ and $\omega (n)={\beta }_{n_0}(n)$ satisfy the required conditions.

Then for $n_0<m\le n$, a suitable constant D > 0 and $\delta \in (0,C{\gamma }_1]$, we have

$$P({\mathrm{\Gamma }}_m\ge \delta )\le 2d{e}^{-D{\delta }^2/{\beta }_{n_0}(m)},$$

and for $\delta >C{\gamma }_1$,

$$P({\mathrm{\Gamma }}_m\ge \delta )\le 2d{e}^{-D\delta /{\beta }_{n_0}(m)}.$$

The factor d comes from the union bound along with Theorem A.1. Applying union bound again, for $\delta \in (0,C{\gamma }_1]$, we now have

$$P({\zeta }_n\ge \delta )\le 2d{\displaystyle \sum _{m=n_0+1}^n{e}^{-D{\delta }^2/{\beta }_{n_0}(m)}},$$(31)

and for $\delta >C{\gamma }_1$,

$$P({\zeta }_n\ge \delta )\le 2d{\displaystyle \sum _{m=n_0+1}^n{e}^{-D\delta /{\beta }_{n_0}(m)}}.$$(32)

Because ${\sum }_i{\pi }_{x_n}(i)F(x^{*},i)=x^{*}$,

$$z_{n+1}-x^{*}=(1-a(n))(z_n-x^{*})+a(n){\displaystyle \sum _{i\in S}{\pi }_{x_n}}(i)(F(z_n,i)-F(x^{*},i)),$$

which implies

$$\begin{array}{l}\Vert z_{n+1}-x^{*}\Vert \le (1-a(n))\Vert z_n-x^{*}\Vert +a(n)\Vert {\displaystyle \sum _{i\in S}{\pi }_{x_n}}(i)(F(z_n,i)-F(x^{*},i))\Vert \\ \le (1-(1-\alpha )a(n))\Vert z_n-x^{*}\Vert .\end{array}$$

We then have

$$\Vert z_n-x^{*}\Vert \le \psi (n,n_0)\Vert x_{n_0}-x^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(n-1)}\Vert x_{n_0}-x^{*}\Vert .$$(33)

Using (30) and the fact that $\Vert x_n-z_n\Vert \le x{\prime }_n$, we have

$$\Vert x_n-z_n\Vert \le \frac{1}{1-\alpha }({\zeta }_n+V_c(n_0)).$$(34)

This inequality along with (33) and the fact that ${\zeta }_n<\delta$ holds with probabilities given by (31) and (32), completes the proof of part (a) of Theorem 1 with constants defined as $c_1=4V_{\mathit{max}}+K^{†}$ and $c_2=2V{\prime }_{\mathit{max}}$.

For part (b) of Theorem 1, to get bounds for all $n\ge n_0$, $P({\cap }_{m=n_0+1}^{\infty }\{{\zeta }_m<\delta \})=P({\cap }_{m=n_0+1}^{\infty }\{{\mathrm{\Gamma }}_m<\delta \})$. Similar to the proof of part (a), applying union bound gives us the desired result. □

4. Some Consequences

In this section, we briefly highlight some consequences of the foregoing as in Borkar (2021). We first show that Theorem 1 implies, in particular, the almost sure convergence of the iterates to $x^{*}$.

Corollary 1.

Almost surely, $x_n\to x^{*}$

Proof.

Let $\widehat{b}(k)$ and $\delta (k)$ be two sequences such that

$$0<\widehat{b}(k)\downarrow 0\hspace{1em}\text{and}\hspace{1em}0<\delta (k)<\frac{(1-\alpha )\widehat{b}(k)}{4},\hspace{0.17em}k\ge 1.$$

Also, let $C(n,n_0,\delta )$ denote the expression on the right-hand side (RHS) of (11). Then for each $\delta =\delta (k)$ in (11), increase $n_0=n_0(k)>0$ sufficiently so that $a(n_0(k))c_1<\frac{(1-\alpha )\widehat{b}(k)}{4}$ and furthermore, (12), respectively, (13) exceed $1-\frac{1}{k^2}$. Then pick $n_1(k)>n_0(k)$ such that

$$e^{-(1-\alpha )b_{n_0(k)}(n_1(k)-1)}\Vert x_{n_0(k)}-x^{*}\Vert \le \frac{\widehat{b}(k)}{2}.$$

Thus, $C(n_1(k),n_0(k),\delta (k))<\widehat{b}(k)$. This leads to

$${\displaystyle \sum _{k}P}\left(\underset{m\ge n_1(k)}{\sup }\Vert x_m-x^{*}\Vert >\widehat{b}(k)\right)\hspace{0.17em}\le \hspace{0.17em}{\displaystyle \sum _k\frac{1}{k^2}}\hspace{0.17em}<\hspace{0.17em}\infty .$$

By the Borel-Cantelli lemma, $\Vert x_{n_1(k)}-x^{*}\Vert \le \widehat{b}(k)$ for k sufficiently large, a.s. Because $\widehat{b}(k)\downarrow 0$, it follows that $x_k\to x^{*}$ a.s. □

The proof also shows that $\{b(k)\}$ serves as a regret bound for the cost $\Vert x_n-x^{*}\Vert$, although possibly not the tightest possible. As indicated in Section 1, the foregoing can be combined with existing finite time sample complexity bounds to obtain a concentration claim for all time. The combined estimate then yields a bound on how many iterates are needed to remain within a prescribed neighborhood of the target $x^{*}$ from some time on, with probability exceeding a prescribed lower bound. Suppose one has a finite time bound of the type (Chen et al. 2020)

for a suitable $\upsilon (n)$. Let $\breve{K}=2K$ and $1>\nu >0$. Pick $\delta >0$ small enough, followed by n₀ large enough and then followed by $n_1\ge n_0$, so that for $n\ge n_0$, and, in addition, (i) the RHS of (12)/(13) exceeds $1-\frac{\nu }{2}$, and (ii) for $n\ge n_1$, the RHS of (11) does not exceed ϵ. Then, using our previous theorem:

We shall exploit this simple fact to stitch our bound for $n\ge n_0$ with that of Chen et al. (2020) for n = n₀, which allows us to bound the ν on the RHS. This allows us to estimate the number of samples n₁ required to ensure that the iterates remain in the ϵ-neighborhood of $x^{*}$ thereafter, with probability $\ge 1-\nu$.

We shall make this more precise for the special choice of $a(n)=\frac{b}{n+1},n\ge 0$, with b > 0. The derivation is adapted from Borkar (2021), included here for sake of completeness. From Chen et al. (2020), $\upsilon (n)$ above is of the form

for suitable constants $c_1,c_2,c_3>0,c_2<1,$ given explicitly in Chen et al. (2020). We assume that b > 0 satisfies the condition $b\le c_2/c_3$ required in theorem 2.1 of Chen et al. (2020). Let $\mathrm{\Gamma }≔c_{3}b$, which, because $c_2<1$ in Chen et al. (2020), leads to $\mathrm{\Gamma }<1$. Using the facts $1-x\le e^{-x}$ and ${\sum }_{m=0}^{n-1}\frac{1}{m+1}=\mathrm{\Theta }(\log n)$, and using c to denote a generic constant that can change from place to place, we have

With c as in this RHS, let n₀ satisfy

Then (35) holds. Consider the specific choice of $a(n)=b/(n+1),\hspace{0.17em}{\beta }_{n_0}(n)\le \frac{1}{n_0^{1-b/2}{n}^{b/2}}$ when $1\ge b/2$ and ${\beta }_{n_0}(n)\le 1/n$ when $1<b/2$, where $n\ge n_0$. Then the RHS of (12) exceeds $1-\frac{\nu }{2}$ if¹

Choosing n₀ as in (37) and (38), the bound (36) follows. A similar approach can be used for combining our bound with other finite time bounds to obtain an all time bound. Recall also that if $\{a(n)\}$ are monotone and sufficiently small (i.e., n = 0), our bound already holds for all time if $n_0=0$.

5. Applications to Reinforcement Learning

In this section, we apply the previous general results for two important reinforcement learning algorithms, viz., asynchronous Q-learning and TD(0), and indicate some related algorithms where they apply as well. In particular, these examples cannot be covered by the results of Borkar (2021), which does not cover Markov noise.

5.1. Asynchronous Q-Learning

We first apply the previous theorem to asynchronous Q-learning (Watkins 1989, Watkins and Dayan 1992). Consider a controlled Markov chain $\{X_n\}$ on a finite state space S₁, $|S_1|=s$, controlled by a control process $\{Z_n\}$ in a finite action space A, $|A|=r$. The controlled transition probability function $(i,j,u)\in S_1^2\times A\mapsto p(j|i,u)\in [0,1]$ satisfies ${\sum }_{j}p(j|i,u)=1\hspace{0.17em}\forall i,u.$ Thus,

The objective is to minimize the discounted cost

where $\gamma \in (0,1)$ is the discount factor and $k:S\times U\mapsto \mathcal{R}$ is a prescribed running cost function. Let a(n) > 0 be as earlier. Then the Q-learning algorithm is with arbitrary $Q_0(·,·)\ge 0$. Note that $I\{X_n=i,Z_n=u\}$ is the indicator function defined as follows:

For application of our theorem, (X_n, Z_n) together forms the Markov chain with the state space as $S_1\times A$ and the transition probabilities given by

Here $p(·|·,·)$ is as earlier, and ${\mathrm{\Phi }}_{Q_n}(·|·)$ is the randomized policy. We make the additional assumption that the graph of the Markov chain remains irreducible under all control choices. We also assume that the map $Q\mapsto {\mathrm{\Phi }}_Q(·|·)$ is Lipschitz and that ${\mathrm{\Phi }}_Q(u|i)>0$ for all $u\in A,i\in S_1$. In the case of offline Q-learning, where the policy is fixed, ${\mathrm{\Phi }}_Q$ is independent of Q and automatically satisfies this assumption. Softmax Q-learning is an example of an online learning algorithm that satisfies the assumption (Singh et al. 2000). For a given Q, the stationary distribution π_Q is ${\pi }_Q(i,u)={\pi }_{{\mathrm{\Phi }}_Q}(i){\mathrm{\Phi }}_Q(u|i)$, where ${\pi }_{{\mathrm{\Phi }}_Q}$ is the stationary distribution of states corresponding to the policy ${\mathrm{\Phi }}_Q$.

We first rearrange the iteration in (39) to get it in the form of (1) and then verify the assumptions. The iteration (39) can be rewritten as

where and

We assume that $Q_0(·,·),k(·,·)\ge 0$, and $a(n)\le 1,\hspace{0.17em}\forall n$, which implies $Q_n(·,·)\ge 0$ for all n. We make these assumptions for sake of simplicity, and they can be dropped. Define the family of σ-fields ${\mathcal{F}}_n,n\ge 0,$ by

Then $\{M_n(Q),{\mathcal{F}}_n\}$ is a martingale difference sequence for each Q satisfying (3) for $K_0=1$, as is $\{M_n(Q_n),{\mathcal{F}}_n\}$.

For ease of notation, we define $g(Q)=[g^{i,u}(Q)]$, where

Note that g(Q) is a contraction in the maximum norm with

We also define the diagonal matrix Λ_Q with values ${\pi }_Q(i,u)$, that is, the stationary probabilities of (X_n, Z_n) corresponding to the policy chosen based on Q. Then for any $Q,Q_1,Q_2\in {\mathcal{R}}^{s\times r}$:

where ${\pi }_{\mathit{min}}={\min }_{Q\in {\mathcal{R}}^{sr}}{\min }_{i,u}{\pi }_Q(i,u)$. Because the stationary distribution π_x is uniquely specified by a linear system continuously parametrized by x, it is continuous in x. Also, the facts that ${\pi }_x(i)>0\hspace{0.17em}\forall x,i,$ and x, i take values in compact sets (by Lemma 1), together imply that ${\pi }_{\mathit{min}}≔{\min }_{i,x}{\pi }_x(i)>0$. Therefore, F satisfies Assumption (4) with $\alpha =1-(1-\gamma ){\pi }_{\mathit{min}}\in (0,1)$, as ${\pi }_{\mathit{min}}\in (0,1)$. The fixed point of ${\sum }_{i,u}\pi (i,u)F(·,i,u)$ is the vector $Q^{*}$ of the true Q-values and satisfies

This implies that $g(Q^{*})=Q^{*}$. Furthermore, for any $Q\in {\mathcal{R}}^{sr}$,

Hence, Assumption (5) is also satisfied. The map $Q\mapsto F(Q,·)$ is also clearly Lipschitz. Also, $\Vert Q^{*}{\Vert }_{\infty }\le \Vert k{\Vert }_{\infty }/(1-\gamma )$. For simplicity, we assume that this bound holds for Q₀ as well and hence holds for $Q_n,\forall n\ge 0$, by induction. Thus, Assumption (6) also holds with $K=\left(\frac{\Vert k{\Vert }_{\infty }}{1-\gamma }\right)$. Then, Theorem 1 gives us the following.

Corollary 2.

Let $n_0\ge N$. Then there exist finite positive constants c₁, c₂, and D, depending on $\Vert Q_N\Vert$, such that for $\delta >0$ and $n\ge n_0$,

• (a) the inequality

  $$\Vert Q_n-Q^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(n-1)}\Vert Q_{n_0}-Q^{*}\Vert +\frac{\delta +a(n_0)c_1}{1-\alpha }$$(42)
  holds with probability exceeding
  $$1\hspace{0.17em}-\hspace{0.17em}2rs{\displaystyle \sum _{m=n_0+1}^n{e}^{-D{\delta }^2/{\beta }_{n_0}(m)}},\hspace{0.17em}0<\delta \le C,$$(43)
  $$1\hspace{0.17em}-\hspace{0.17em}2rs{\displaystyle \sum _{m=n_0+1}^n{e}^{-D\delta /{\beta }_{n_0}(m)}},\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\delta >C,$$(44)
  where $C=e^{\left(2\left(1+\Vert Q_N{\Vert }_{\infty }+\frac{\Vert k{\Vert }_{\infty }}{1-\alpha }\right)+c_2\right)}$.

• (b) In particular,

  $$\Vert Q_n-Q^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(n-1)}\Vert Q_{n_0}-Q^{*}\Vert +\frac{\delta +a(n_0)c_1}{1-\alpha }\hspace{0.17em}\forall n\ge n_0,$$(45)
  with probability exceeding
  $$1\hspace{0.17em}-\hspace{0.17em}2rs{\displaystyle \sum _{m\ge n_0+1}{e}^{-D{\delta }^2/{\beta }_{n_0}(m)}},\hspace{0.17em}0<\delta \le C,$$(46)
  $$1\hspace{0.17em}-\hspace{0.17em}2rs{\displaystyle \sum _{m\ge n_0+1}{e}^{-D\delta /{\beta }_{n_0}(m)}},\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\delta >C.$$(47)

5.2. TD(0)

We next apply Theorem 1 to the popular algorithm TD(0) for policy evaluation (Tsitsiklis and Van Roy 1997). We fix a stationary policy a priori and thus work with an uncontrolled Markov chain $\{Y_n\}$ on state space S with transition probabilities $p(·|·)$ (the dependence on the policy is suppressed). Assume that the chain is irreducible with the stationary distribution $\pi =[\pi (1),\dots ,\pi (s)],s=|S|$ and let $D≔$ the s × s diagonal matrix whose ith diagonal entry is $\pi (i)$. The dynamic programming equation is

which can be written as the following vector equation for $k={[k(1),\dots ,k(s)]}^T$ and $p={[[p(j|i)]]}_{i,j\in S}\in {\mathcal{R}}^{s\times s}$.

The term $\Upsilon$ is approximated using a linear combination of linearly independent basis functions (feature vectors) ${\varphi }_i:S\mapsto \mathcal{R},1\le i\le M$, with $s\gg M\ge 1$. Thus, $\Upsilon (i)\approx {\sum }_{m=1}^{M}r(m){\varphi }_m(i)$, that is, $\Upsilon \approx \mathrm{\Phi }r$, where $r={[r(1),\dots ,r(M)]}^T$ and $\mathrm{\Phi }$ is an s × M matrix whose ith column is ${\varphi }_i$. Because $\{{\varphi }_i\}$ are linearly independent, $\mathrm{\Phi }$ is full rank. Substituting this approximation into the previous dynamic programming equation leads to

However, the RHS may not belong to the range of $\mathrm{\Phi }$. Therefore, we use the following fixed point equation:

where Π denotes the projection to Range($\mathrm{\Phi }$) with respect to a suitable norm. Here we take projection with respect to the weighted norm $\Vert x{\Vert }_D≔{({\sum }_i\pi (i)|x(i){|}^2)}^{1/2}$ whereby the projection map is

The invertibility of ${\mathrm{\Phi }}^{T}D\mathrm{\Phi }$ is guaranteed by the fact that $\mathrm{\Phi }$ is full rank. Also, $\Vert Px{\Vert }_D\le \Vert x{\Vert }_D$ (by Jensen’s inequality) and $\Vert \mathrm{\Pi }x{\Vert }_D\le \Vert x{\Vert }_D$ (because Π is a $\Vert ·{\Vert }_D$-projection).

The TD(0) algorithm is given by the recursion

Here $\phi {(i)}^T\in {\mathcal{R}}^M$ for $i\in S$ denotes the ith row of $\mathrm{\Phi }$. We will apply our theorem to the iterates r_n using the Euclidean norm (i.e., $\Vert r{\Vert }_2={({\sum }_{i}r{(i)}^2)}^{1/2}$).

Before moving forward, we make an assumption on $\mathrm{\Phi }$, which is not restrictive as we argue later. Define $\mathrm{\Psi }≔{\mathrm{\Phi }}^T\sqrt{D}$ and let λ_M be the largest singular value of $\mathrm{\Psi }$, that is, the largest eigenvalue of $\mathrm{\Psi }{\mathrm{\Psi }}^T$ and equivalently, of ${\mathrm{\Psi }}^T\mathrm{\Psi }$. Assume that

Because the feature vectors can be scaled without affecting the algorithm (the weights r(i) get scaled accordingly), this assumption does not restrict the algorithm.

Rearrange iteration (50) as

where and

Define the family of σ-fields for $n\ge 0$:

Then $\{M_n(r),{\mathcal{F}}_n\}$ is a martingale difference sequence for each r satisfying (3) for $K_0=2\gamma \Vert \mathrm{\Phi }{\Vert }_{\infty }^2$.

Because we are working with a time-homogeneous and uncontrolled Markov chain, we can apply the special case of our theorem from Remark 1. Therefore, we need to show that Assumption (14) is satisfied. For ease of notation, we drop the subscript 2 from $\Vert r{\Vert }_2$ and let $\Vert r\Vert$ refer to the Euclidean norm. Let $〈r,r\prime 〉=r^T{r}^{\prime }$ and ${〈x,y\prime 〉}_D=x^{T}Dy$. Then,

Now,

and

Inequality (a) follows from the Cauchy-Schwarz inequality and (b) follows from the fact that $\Vert Px{\Vert }_D\le \Vert x{\Vert }_D$. Combining (54) and (55) with (53) gives us

To analyze the last term in (56), we use the fact that the operator norm of a matrix defined as $\Vert M\Vert ={\sup }_{x\ne \theta }\frac{\Vert Mx\Vert }{\Vert x\Vert }$, using the Euclidean norm for vectors, is equal to the largest singular value of that matrix. Thus,

The last inequality follows from the triangle inequality. We now invoke Assumption (51) and combine (57) with (56) as follows:

This gives us the required contraction property with contraction factor α for which an explicit expression can be obtained, using the first inequality in (58), as

As the columns of $\mathrm{\Phi }$ are linearly independent, $r\ne \theta \Rightarrow \mathrm{\Phi }r\ne \theta$ and hence $\frac{\Vert \mathrm{\Phi }r{\Vert }_D}{\Vert r\Vert }>0$ when $r\ne \theta$. Along with Assumption (51), this implies that $\alpha <1$.

Let $r^{*}$ be the fixed point for ${\sum }_i\pi (i)F(·,i)$, that is, ${\sum }_i\pi (i)F(r^{*},i)=r^{*}$. Then,

Therefore, Iteration (52) converges to the required fixed point of (48). Furthermore, Assumption (6) also holds with $K=\Vert k{\Vert }_{\infty }\Vert \mathrm{\Phi }{\Vert }_{\infty }$. The map $r\mapsto F(r,·)$ is clearly Lipschitz. Then Theorem 1 leads to the following.

Corollary 3.

Let $n_0\ge N$. Then there exist finite, positive constants c₁, c₂, and D, depending on $\Vert r_N\Vert$, such that for $\delta >0$ and $n\ge n_0$,

• (a) the inequality

  $$\Vert r_n-r^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(n-1)}\Vert r_{n_0}-r^{*}\Vert +\frac{\delta +4a(n_0)c_1}{1-\alpha }$$(59)
  holds with probability exceeding
  $$1\hspace{0.17em}-\hspace{0.17em}2M{\displaystyle \sum _{m=n_0+1}^n{e}^{-D{\delta }^2/{\beta }_{n_0}(m)}},\hspace{0.17em}0<\delta \le C,$$(60)
  $$1\hspace{0.17em}-\hspace{0.17em}2M{\displaystyle \sum _{m=n_0+1}^n{e}^{-D\delta /{\beta }_{n_0}(m)}},\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\delta >C,$$(61)
  where $C=e^{\sqrt{M}\left(2\gamma \Vert \mathrm{\Phi }{\Vert }_{\infty }^2\left(1+\Vert x_N\Vert +\frac{\Vert k{\Vert }_{\infty }\Vert \mathrm{\Phi }{\Vert }_{\infty }}{1-\alpha }\right)+c_2\right)}$.

• (b) In particular,

  $$\Vert r_n-r^{*}\Vert \le e^{-(1-\alpha )b_{n_0}(n-1)}\Vert r_{n_0}-r^{*}\Vert +\frac{\delta +a(n_0)c_1}{1-\alpha }\hspace{0.17em}\forall n\ge n_0,$$(62)
  with probability exceeding
  $$1\hspace{0.17em}-\hspace{0.17em}2M{\displaystyle \sum _{m\ge n_0+1}{e}^{-D{\delta }^2/{\beta }_{n_0}(m)}},\hspace{0.17em}0<\delta \le C,$$(63)
  $$1\hspace{0.17em}-\hspace{0.17em}2M{\displaystyle \sum _{m\ge n_0+1}{e}^{-D\delta /{\beta }_{n_0}(m)}},\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\delta >C.$$(64)

Remark 3.

We mention in passing other reinforcement learning algorithms where analogous results can be derived, specifically the asynchronous cases of the examples thereof from Borkar (2021). The first is the asynchronous version of the Q-learning problem for stochastic shortest path problem (Abounadi et al. 2002) with running cost $k(·,·)\ge 0$, which can be analyzed along the lines of the previous discounted cost Q-learning using the fact that the corresponding dynamic programming operator is a contraction w.r.t. a weighted max-norm (Bertsekas and Tsitsiklis 1989, exercise 3.3, p. 325). The asynchronous version of the postdecision scheme (Powell 2007) for discounted cost can likewise be covered by the previous framework. In case of the previous and the asynchronous Q-learning scheme for discounted cost studied earlier, it is the asynchrony that puts them beyond the ambit of Borkar (2021), necessitating the extension to Markov noise presented here. In case of TD(0), however, Markov noise is already embedded into the scheme itself.

Remark 4.

Stochastic gradient descent with Lipschitz gradient can also be thought of as a fixed-point seeking scheme for a contraction map, as shown in Borkar (2021). Specifically, if the gradient $\nabla f(x)$ is continuously differentiable with a bounded Jacobian (i.e., the Hessian ${\nabla }^{2}f(x)$) that is positive definite with its least eigenvalue uniformly bounded away from zero, then for sufficiently small a > 0, $-a\nabla f(x)=(x-x\nabla f(x))-x$, where the map $x\mapsto x-a\nabla f(x)$ is a contraction w.r.t. the euclidean norm. stochastic gradient descent with Markov noise has been studied in Doan et al. (2020), Sun et al. (2018), Wang and Liu (2016), and so on. However, our focus here has been in contractive iterates arising in reinforcement learning for approximate dynamic programming.

6. Conclusions

In conclusion, we point out some future directions. Some extensions, for example, to TD$(\lambda )$ for $\lambda >0$, may not be very difficult. However, extensions to other cost criteria such as average or risk-sensitive cost are because their dynamic programming operators are not contractions. Nevertheless, that does not rule out the possibility of building up on these ideas to cover more general ground that will subsume such cases. There are also several other variants of reinforcement learning algorithms left out in this work where even for the discounted cost one might get results in similar spirit, although not of exactly similar form. Finally, such arguments may pave way for regret bounds for reinforcement learning schemes. This needs to be further explored.