# On Convergence of Gradient Expected Sarsa($\lambda$)

Long Yang1, Gang Zheng1, Yu Zhang1, Qian Zheng2, Pengfei Li1 Gang Pan 1
Corresponding author.

###### Abstract

We study the convergence of $\mathtt{Expected~{}Sarsa}(\lambda)$ with linear
function approximation. We show that applying the off-line estimate (multi-
step bootstrapping) to $\mathtt{Expected~{}Sarsa}(\lambda)$ is unstable for
off-policy learning. Furthermore, based on convex-concave saddle-point
framework, we propose a convergent
$\mathtt{Gradient~{}Expected~{}Sarsa}(\lambda)$ ($\mathtt{GES}(\lambda)$)
algorithm. The theoretical analysis shows that our $\mathtt{GES}(\lambda)$
converges to the optimal solution at a linear convergence rate, which is
comparable to extensive existing state-of-the-art gradient temporal difference
learning algorithms. Furthermore, we develop a Lyapunov function technique to
investigate how the step-size influences finite-time performance of
$\mathtt{GES}(\lambda)$, such technique of Lyapunov function can be
potentially generalized to other GTD algorithms. Finally, we conduct
experiments to verify the effectiveness of our $\mathtt{GES}(\lambda)$.

## Introduction

Tabular $\mathtt{Expected~{}Sarsa}(\lambda)$ (with importance sampling) is one
of the widely used methods for off-policy evaluation in reinforcement learning
(RL), whose goal is to estimate the value function of a given target policy
via the data that is generated from a behavior policy. Due to the high-
dimensional state space, instead of tabular learning, a standard approach is
to estimate the value function with a linear function (Sutton and Barto 2018).
There is very little literature to study $\mathtt{Expected~{}Sarsa}(\lambda)$
with function approximation for off-policy learning. To our best knowledge,
Sutton and Barto (2018) (section 12.9) firstly extend _off-line_ estimate
(multi-step bootstrapping) to $\mathtt{Expected~{}Sarsa}(\lambda)$ with linear
function approximation.

Unfortunately, as pointed out by Sutton and Barto (2018) intuitively, their
off-line approach may be unstable, i.e., their way to extend
$\mathtt{Expected~{}Sarsa}(\lambda)$ with linear function approximation still
lacks a provable convergence guarantee, which is undesirable for RL. It is
critical to find the inherent essence of the above unstable appearance in
$\mathtt{Expected~{}Sarsa}(\lambda)$, which not only makes a complement for
existing off-policy learning methods but also provides some inspirations to
design a stable algorithm. Thus, extending
$\mathtt{Expected~{}Sarsa}(\lambda)$ with linear function approximation for
off-policy evaluation is a fundamental theoretical topic in RL, including: 1)
how to character the instability of off-line
$\mathtt{Expected~{}Sarsa}(\lambda)$ with linear function approximation; 2)
how to derive a convergent algorithm; 3) what convergence rate does
$\mathtt{Expected~{}Sarsa}(\lambda)$ with linear function approximation can
reach. We focus on these questions in this paper.

Our Main Works To address the above problems, we propose Theorem 1, which
characters a sufficient and necessary condition that presents stability
criteria of off-line update $\mathtt{Expected~{}Sarsa}(\lambda)$ with linear
function approximation. Theorem 1 requires the _key_ matrix (that has been
defined in (10)) keeps the negative real components. Unfortunately, due to the
discrepancy between behavior policy and target policy, off-line
$\mathtt{Expected~{}Sarsa}(\lambda)$ that is suggested by Sutton and Barto
(2018) may not satisfy the condition appears in Theorem 1, i.e., their scheme
maybe unstable. Then, we use a classic counterexample to verify the above
instability lies in the off-line update $\mathtt{Expected~{}Sarsa}(\lambda)$
with linear function approximation, see Example 1.

Furthermore, to get a stable algorithm, we derive an _on-line_ gradient
$\mathtt{Expected~{}Sarsa}(\lambda)$ ($\mathtt{GES}(\lambda)$) algorithm.
Theorem 2 shows that the proposed $\mathtt{GES}(\lambda)$ learns the optimal
solution at a linear convergence rate, which is comparable to extensive
existing state-of-the-art gradient temporal difference learning algorithms.
Although Xu et al. (2019) prove $\mathtt{TDC}$ (Sutton et al. 2009a) also
converges at a linear convergence rate, they require a projection step that is
unpractical in practice. Besides, the fussy blockwise step-size appears in (Xu
et al. 2019) is more complicated than our step-size condition. Additionally,
the results of (Dalal et al. 2018a; Lakshminarayanan et al. 2018) require an
i.i.d assumption of function parameters, our proof removes this condition and
achieve a better result than theirs. A more detailed comparison and an
adequate discussion are provided in Table 1.

Finally, inspired by Srikant and Ying (2019), Wang et al. (2019), Gupta et al.
(2019), we develop a Lyapunov function technique to establish Theorem 3, which
illustrates the relationship between the finite-time performance of
$\mathtt{GES}(\lambda)$ and step-size. Result shows that the upper-bounded
error consists of two different parts: the first error depends on both step-
size and the size of samples, and such error decays geometrically as the
samples increase; while the second error is only determined by the step-size
and it is independent of samples. Additionally, the technique of proving
Theorem 3 can be potentially generalized to other GTD algorithms.

### Notations

We use $\text{Spec}(A)$ to denote the eigenvalues of the matrix
$A\in\mathbb{C}^{p\times p}$, i.e.,
$\text{Spec}(A)=\\{\lambda_{1},\cdots,\lambda_{p}\\}$, where $\lambda_{i}$ is
the root of the characteristic equation $p(\lambda)=\text{det}(A-\lambda I)$.
We use $\mathbb{C}_{-}$ to denote the collection that contains the complex
numbers with negative real components, i.e.,

$\mathbb{C}_{-}=:\\{c\in\mathbb{C};\text{Re}(c)<0\\}.$

Let $\lambda_{\min}(A)$ and $\lambda_{\max}(A)$ be the minimum and maximum
eigenvalue of the matrix $A$ correspondingly. We use $\|A\|_{\text{op}}$ to
denote the operator norm of matrix $A$; furthermore, if $A$ is a symmetric
real matrix, then $\|A\|_{\text{op}}=\max_{1\leq i\leq p}\\{|\lambda_{i}|\\}.$
$\kappa(A)=\frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}$ is the condition
number of matrix $A$. We use $A\succ 0$ to denote a positive definite matrix
$A$.

For a function $f(x):\mathbb{R}^{p}\rightarrow\mathbb{R}$, let
$\nabla^{2}f(x)$ denote its Hessian matrix, and its convex conjugate function
$f^{\star}(y):\mathbb{R}^{d}\rightarrow\mathbb{R}$ is defined as
$f^{\star}(y)=\sup_{x\in\mathbb{R}^{p}}\\{y^{\top}x-f(x)\\}.$

######  Fact 1 ((Rockafellar 1970; Kakade et al. 2009)).

Let $f(\cdot)$ be $\alpha$-strongly convex and $\beta$-smooth, i.e.,
$f(\cdot)-\frac{\alpha}{2}\|\cdot\|_{2}^{2}$ is convex and
$\|f(u)-f(v)\|\leq\beta\|u-v\|$. If $0\leq\alpha\leq\beta$, then the following
fact holds,

(I) $f^{\star}$ is $\frac{1}{\alpha}$-smooth and $\frac{1}{\beta}$-strongly
convex.

(II) $\nabla f=(\nabla f^{\star})^{-1}$ and $\nabla f^{\star}=(\nabla
f)^{-1}$.

## Preliminary

Reinforcement learning (RL) is formalized as Markov decision processes (MDP)
which considers the tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma)$;
$\mathcal{S}$ is the space of states, $\mathcal{A}$ is the space of actions;
${P}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$,
$p_{ss^{{}^{\prime}}}^{a}=P(S_{t}=s^{{}^{\prime}}|S_{t-1}=s,A_{t-1}=a)$ is the
probability of state transition from $s$ to $s^{{}^{\prime}}$ under playing
the action $a$;
$R(\cdot,\cdot):\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{1}$ is the
expected reward function; $\gamma\in(0,1)$ is the discount factor.

The policy $\pi$ is a probability distribution on
$\mathcal{S}\times\mathcal{A}$, we use $\pi(a|s)$ to denote the probability of
playing $a$ under the state $s$. Let $\\{S_{t},A_{t},R_{t+1}\\}_{t\geq 0}$ be
generated by a given policy $\pi$, its _state-action value function_
$q^{\pi}(s,a)=\mathbb{E}_{\pi}[\sum_{t=0}^{\infty}\gamma^{t}R_{t+1}|S_{0}=s,A_{0}=a],$
where $\mathbb{E}_{\pi}[\cdot|\cdot]$ is the conditional expectation on the
actions selected according to $\pi$. Let
$\mathcal{B}^{\pi}:\mathbb{R}^{|\mathcal{S}|\times|\mathcal{A}|}\rightarrow\mathbb{R}^{|\mathcal{S}|\times|\mathcal{A}|}$
be the _Bellman operator_ :

$\displaystyle\mathcal{B}^{\pi}:q\mapsto R^{\pi}+\gamma P^{\pi}q,$ (1)

where $P^{\pi}$$\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$,
$R^{\pi}$$\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{A}|}$, their
corresponding elements are:
$[P^{\pi}]_{s,s^{{}^{\prime}}}=\sum_{a\in\mathcal{A}}\pi(a|s)p^{a}_{ss^{{}^{\prime}}},[R^{\pi}]_{s,a}=R(s,a).$
It is well-known that $q^{\pi}$ is the unique fixed point of
$\mathcal{B}^{\pi}$, i.e., $\mathcal{B}^{\pi}q^{\pi}=q^{\pi}$, which is known
as Bellman equation.

Off-Policy Evaluation Let’s consider the following trajectory $\mathcal{T}$
generated by a policy $\mu$:

$\mathcal{T}=\\{S_{0}=s,A_{0}=a,\cdots,S_{t},A_{t},R_{t+1},\cdots\\},$

where $A_{t}\sim\mu(\cdot|S_{t})$,$S_{t+1}\sim P(\cdot|S_{t},A_{t})$. In RL,
the task of off-policy evaluation is to estimate the value function of the
target policy $\pi$ via the data that is generated by an another policy $\mu$
(that is called _behavior policy_), where $\mu\neq\pi$.

######  Assumption 1.

The Markov chain induced by behavior policy $\mu$ is _ergodic_ , i.e., there
exists a stationary distribution $\xi(\cdot,\cdot)$ over
$\mathcal{S}\times\mathcal{A}$: for
$\forall(S_{0},A_{0})\in\mathcal{S}\times\mathcal{A}$,

$\displaystyle\frac{1}{n}\sum_{k=1}^{n}P(S_{k}=s,A_{k}=a|S_{0},A_{0})\overset{n\rightarrow\infty}{\rightarrow}\xi(s,a)>0.$
(2)

The ergodicity of behavior policy $\mu$ is a standard assumption in off-policy
learning (Bertsekas 2012), and it implies each-action pair can be visited
under this behavior policy $\mu$. In this paper, we use $\Xi$ to denote a
diagonal matrix whose diagonal element is $\xi(s,a)$, i.e.,

$\Xi=\text{diag}\\{\cdots,\xi(s,a),\cdots\\}.$

Temporal Difference (TD) Learning TD learning updates value function as
follows, $\forall~{}t\geq 0$,

$\displaystyle Q(S_{t},A_{t})\leftarrow Q(S_{t},A_{t})+\alpha_{t}\delta_{t},$
(3)

where $Q(\cdot,\cdot)$ is an estimate of state-action value function,
$\alpha_{t}$ is step-size and $\delta_{t}$ is TD error. Let
$Q_{t}=Q(S_{t},A_{t})$, if $\delta_{t}$ is expected TD error:

$\displaystyle\delta_{t}^{\text{ES}}=R_{t+1}+\gamma\sum_{a\in\mathcal{A}}\pi(a|S_{t+1})Q(S_{t+1},a)-Q_{t},$
(4)

then update (3) is $\mathtt{Expected~{}Sarsa}$.

Expected Sarsa($\lambda$) Sutton and Barto (2018) 111It is noteworthy that the
$\lambda$-return version of $\mathtt{Expected~{}Sarsa}$ appears in section
12.9 of (Sutton and Barto 2018) is limited in the case of linear function
case, Eq.(5) extends it to be a general case. propose a multi-step TD learning
that extends $\mathtt{Expected~{}Sarsa}$ to $\lambda$-return version: for each
$t\geq 0$,

$\displaystyle
G_{t}^{\lambda}=Q_{t}+\sum_{k=t}^{\infty}(\gamma\lambda)^{k-t}\bigg{(}\prod_{i=t+1}^{k}\frac{\pi(A_{i}|S_{i})}{\mu(A_{i}|S_{i})}\bigg{)}\delta^{\text{ES}}_{k},$
(5)

where $\delta^{\text{ES}}_{k}$ is expected TD error. For the convenience, we
set
$\prod_{i=t}^{k}\rho_{i}=\prod_{i=t}^{k}\frac{\pi(A_{i}|S_{i})}{\mu(A_{i}|S_{i})}=\rho_{t:k}$,
and $\rho_{t:t+1}=1$.

Finally, we introduce $\lambda$-operator $\mathcal{B}^{\pi}_{\lambda}$ that is
a high level view of iteration (5):

$\displaystyle\mathcal{B}^{\pi}_{\lambda}:q$ $\displaystyle\mapsto
q+\mathbb{E}_{\mu}[\sum_{k=t}^{\infty}(\lambda\gamma)^{k-t}\delta^{\text{ES}}_{k}\rho_{t+1:k}]$
(6) $\displaystyle=q+(I-\lambda\gamma P^{\pi})^{-1}(\mathcal{B}^{\pi}q-q),$
(7)

where $\mathcal{B}^{\pi}$ is defined in (1). For the limitation of space, we
provide the derivation of (7) from (6) in Appendix A.2.

### Linear Function Approximation

TD learning (3) requires a very huge table to store the estimate value
function $Q(\cdot,\cdot)$ when $|\mathcal{S}|$ is very large, which implies
tabular TD learning is considerably expensive for high-dimensional RL. We
often use a parametric function ${Q}_{\theta}(\cdot,\cdot)$ to approximate
$q^{\pi}(s,a)$, i.e.,

$q^{\pi}(s,a)\approx\phi^{\top}(s,a)\theta=:{Q}_{\theta}(s,a),$

where $\theta\in\mathbb{R}^{p}$ is the parameter that needs to be learned,
$\phi(s,a)=(\varphi_{1}(s,a),\varphi_{2}(s,a),\cdots,\varphi_{p}(s,a))^{\top}$,
and each $\varphi_{i}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$.
Furthermore, ${Q}_{\theta}$ can be rewritten as a version of matrix
${Q}_{\theta}=\Phi\theta\approx q^{\pi},$ where $\Phi$ is a matrix whose rows
are the state-action feature vectors $\phi^{\top}(s,a)$. In this paper, we
mainly consider extending $\lambda$-return of $\mathtt{Expected~{}Sarsa}$ (5)
with linear function approximation.

## Off-Line Gradient Expected Sarsa($\lambda$)

In this section, we use a counterexample to show the way to extend
$\mathtt{Expected~{}Sarsa}$($\lambda$) with linear function approximation via
off-line estimate is unstable for off-policy learning.

Off-Line Update Sutton and Barto (2018) provide a way to extend (5) with
linear function approximation as follows,

$\displaystyle\theta_{t+1}$
$\displaystyle=\theta_{t}+\alpha_{t}({G}^{\lambda}_{t}-Q_{\theta}(S_{t},A_{t}))\nabla
Q_{\theta}(S_{t},A_{t})$
$\displaystyle=\theta_{t}+\alpha_{t}\Big{(}\sum_{k=t}^{\infty}(\gamma\lambda)^{k-t}\delta_{k,\theta}^{\text{ES}}\rho_{t+1:k}\Big{)}\phi_{t},$
(8)

where $\alpha_{t}$ is step-size, $\phi_{t}=:\phi(S_{t},A_{t})$, and

$\delta_{k,\theta}^{\text{ES}}=R_{k+1}+\gamma\theta^{\top}_{t}\mathbb{E}_{\pi}[\phi(S_{k+1},\cdot)]-\theta^{\top}_{t}\phi_{k}.$

Furthermore, we can rewrite the expected parameter in (8):

$\displaystyle\mathbb{E}_{\mu}[\theta_{t+1}]=\theta_{t}+\alpha_{t}(A\theta_{t}+b),$
(9)

where

$\displaystyle A$
$\displaystyle=\mathbb{E}_{\mu}\Big{(}\sum_{k=t}^{\infty}(\gamma\lambda)^{k-t}\rho_{t+1:k}\phi_{t}\big{(}\gamma\mathbb{E}_{\pi}[\phi(S_{k},\cdot)]-\phi_{k}\big{)}^{\top}\Big{)}$
$\displaystyle=\Phi^{\top}\Xi(I-\gamma\lambda P^{\pi})^{-1}(\gamma
P^{\pi}-I)\Phi,$ (10) $\displaystyle b$
$\displaystyle=\mathbb{E}_{\mu}\Big{(}\sum_{k=t}^{\infty}(\gamma\lambda)^{k-t}\rho_{t+1:k}\phi_{t}R_{k+1}\Big{)}$
$\displaystyle=\Phi^{\top}\Xi(I-\gamma\lambda P^{\pi})^{-1}R.$ (11)

If $\theta_{t}$ (9) converges to a certain point $\theta^{\star}$, then
$\theta^{\star}$ satisfies the following linear system:

$\displaystyle A\theta^{\star}+b=0.$ (12)

Such $\theta^{\star}$ satisfies (12) is called _TD-fixed point_.

Stability Criteria According to Sutton et al. (2016); and Ghosh and Bellemare
(2020), we formulate the stability of the iteration (9) as the next
definition.

######  Definition 1 (Stability).

Update rule (9) is stable if $\theta_{k}$ converges to the point
$\theta^{\star}$ satisfies (12) for any initial $\theta_{0}$.

######  Theorem 1 (Stability Criteria).

Under Assumption 1, the off-line update (9) is stable if and only if the
eigenvalues of the matrix A (10) have negative real components, i.e.,

$\displaystyle\emph{Spec}(A)\subset\mathbb{C}_{-}.$ (13)

We provode its proof in Appendix B. Theorem 1 provides a sufficient and
necessary condition (13) that guarantees the stability of iteration (8).
Unfortunately, for off-policy learning, the matrix $A$ (10) can not guarantee
the condition (13) holds, which implies the iteration (8) may be divergent and
unstable. Now, we use the following example (Touati et al. 2018) to illustrate
the instability lies in the iteration (8).

######  Example 1.

For the MDP in Figure 1, we assign the features
$\\{(1,0)^{\top},(2,0)^{\top},(0,1)^{\top},(0,2)^{\top}\\}$ to the state-
action pairs
$\\{(s_{1},\mathtt{right}),(s_{2},\mathtt{right}),(s_{1},\mathtt{left}),(s_{2},\mathtt{left})\\}$,
From the dynamic transition shown in Figure 1 , we have

$P^{\pi}=\begin{pmatrix}0&1&0&0\\\ 0&1&0&0\\\ 1&0&0&0\\\
1&0&0&0\end{pmatrix},\Phi=\begin{pmatrix}1&0\\\ 2&0\\\ 0&1\\\
0&2\end{pmatrix},\Xi=\dfrac{1}{2}I_{4\times 4}.$

Then, according to (10), we have

$A=\Phi^{\top}\Xi(I-\gamma\lambda P^{\pi})^{-1}(\gamma
P^{\pi}-I)\Phi=\begin{pmatrix}\frac{6\gamma-\gamma\lambda-5}{2(1-\gamma\lambda)}&0\\\
\frac{3\gamma}{2}&-\frac{5}{2}\end{pmatrix},$

and the eigenvalues of $A$ are:
$\frac{6\gamma-\gamma\lambda-5}{2(1-\gamma\lambda)}$ and $\frac{5}{2}$. For
any initial
$\theta_{0}=\begin{pmatrix}\theta_{0,1},\theta_{0,2}\end{pmatrix}^{\top}$, let
$\mathbb{E}[\theta_{t+1}]=:(\theta_{t+1,1},\theta_{t+1,2})^{\top}$ be the
expectation of iteration (8), according to (9), the first component of
$\mathbb{E}[\theta_{t+1}|\theta_{t}]$ is:

$\displaystyle\theta_{t+1,1}=$
$\displaystyle\theta_{0,1}\prod_{i=0}^{t}\Big{(}1+\alpha_{i}\frac{6\gamma-\gamma\lambda-5}{2(1-\gamma\lambda)}\Big{)}.$
(14)

For any $\lambda\in(0,1)$, if $\gamma\in(\frac{5}{6-\lambda},1)$, then
$\frac{6\gamma-\gamma\lambda-5}{2(1-\gamma\lambda)}$ is a positive scalar,
which implies $A$ can not be a negative matrix. Furthermore, if step size
$\alpha_{t}:\sum_{i\geq 0}\alpha_{t}=\infty$, we have 222 Eq.(15) is a direct
result of the following conclusion that could be found in any calculus
textbook. Let $p_{i}=1+a_{i}$, where $a_{i}>0$, if
$\sum_{i=1}^{\infty}a_{i}=+\infty$, then
$\prod_{i=1}^{\infty}p_{i}=\prod_{i=1}^{\infty}(1+a_{i})=+\infty.$

$\displaystyle|\theta_{t+1,1}|=|\theta_{0,1}|\prod_{i=0}^{t}\Big{(}1+\alpha_{i}\frac{6\gamma-\gamma\lambda-5}{2(1-\gamma\lambda)}\Big{)}\rightarrow+\infty,$
(15)

which implies the way (8) to extend $\mathtt{Expected~{}Sarsa}$($\lambda$)
with linear function approximation via off-line estimate is unstable for off-
policy learning.

$s_{1}$$s_{2}$$\mathtt{left}$$\mathtt{right}$$0.5$$0.5$ Figure 1:
Counterexample, Two-State MDP: behavior policy $\mu(\mathtt{right}|\cdot)=0.5$
and target policy $\pi(\mathtt{right}|\cdot)=1$.

## On-Line Gradient Expected Sarsa($\lambda$)

The above discussion of the instability for off-policy learning shows that we
should abandon the off-line update (8). In this section, we provide a
convergent on-line algorithm: $\mathtt{Gradient~{}Expected~{}Sarsa(\lambda)}$
($\mathtt{GES}(\lambda)$), which is based on the popular TD fixed point
method.

The TD fixed point method (Sutton et al. 2009a; Bertsekas 2011; Dann et al.
2014) is widely used for policy evaluation and it focuses on finding the value
function satisfies

$\displaystyle\Phi\theta=\Pi\mathcal{B}_{\lambda}^{\pi}\Phi\theta,$ (16)

where $\Pi=\Phi(\Phi^{\top}\Xi\Phi)^{-1}\Phi^{\top}\Xi$. It has been shown
that if the _projected Bellman operator_ $\Pi\mathcal{B}_{\lambda}^{\pi}$ has
a fixed point $\theta^{\star}$, then it is unique (Lagoudakis and Parr 2003;
Bertsekas 2011), and such a fixed-point $\theta^{\star}$ also satisfies the
linear system (12).

Instead of using the method of value iteration according to the projected
Bellman operator $\Pi\mathcal{B}_{\lambda}^{\pi}$, we derive the algorithm on
the mean square projected Bellman equation (MSPBE) (Sutton et al. 2009a) as
follows,

$\displaystyle\min_{\theta}\text{MSPBE}(\theta,\lambda)$
$\displaystyle=:\min_{\theta}\frac{1}{2}\|\Phi\theta-\Pi\mathcal{B}^{\pi}_{\lambda}(\Phi\theta)\|^{2}_{\Xi}$
$\displaystyle=\min_{\theta}\frac{1}{2}\|A\theta+b\|^{2}_{M^{-1}},$ (17)

where $\|x\|_{\Xi}=x^{\top}\Xi x$ is a weighted norm, and
$M=\Phi^{\top}\Xi\Phi$. We provide the derivation of (17) in Appendix C.1.

Since the computational complexity of the invertible matrix $M^{-1}$ is very
large, it is too expensive to use stochastic gradient method to solve the
problem (17) directly. Let

$\displaystyle g(\omega)$
$\displaystyle=\frac{1}{2}\|\omega\|^{2}_{M}-b^{\top}\omega$ (18)
$\displaystyle\Psi(\theta,\omega)$
$\displaystyle=(A\theta+b)^{\top}\omega-\frac{1}{2}\|\omega\|^{2}_{M}=\theta^{\top}A\omega-g(\omega).$

According to Liu et al. (2015), the original problem (17) is equivalent to the
convex-concave saddle-point problem

$\displaystyle\min_{\theta}\max_{\omega}\\{\Psi(\theta,\omega)\\}.$ (19)

######  Proposition 1.

If $(\theta^{\star},\omega^{\star})$ is the solution of problem (19), then
$\theta^{\star}$ is the solution of original problem (17), i.e.,

$\theta^{\star}=\arg\min_{\theta}\emph{MSPBE}(\theta,\lambda).$

We provide the proof of Proposition 1 in Appendix C.2. Proposition 1
illustrates that the solution of (17) is contained in the problem (19).
Gradient update is a natural way to solve problem (19) (ascending in $\omega$
and descending in $\theta$):

$\displaystyle\omega_{t+1}$
$\displaystyle=\omega_{t}+\beta_{t}(A\theta_{t}+b-M\omega_{t}),$ (20)
$\displaystyle\theta_{t+1}$
$\displaystyle=\theta_{t}-\alpha_{t}A^{\top}\omega_{t},$ (21)

where $\alpha_{t},\beta_{t}$ is step-size, $t\geq 0$.

Algorithm 1 Gradient Expected Sarsa$(\lambda)$ ($\mathtt{GES}(\lambda)$)

1: Initialization: $\omega_{0}=0$, ${\theta}_{0}=0$,
$\alpha_{0}>0,\beta_{0}>0$, $T\in\mathbb{N}$.

2: ${e}_{-1}={0}$

3: for $t=0$ to $T$ do

4: Observe $\\{S_{t},A_{t},R_{t+1},S_{t+1},A_{t+1}\\}\sim\mu$

5: $\rho_{t}=\frac{\pi(A_{t}|S_{t})}{\mu(A_{t}|S_{t})}$

6: $e_{t}=\lambda\gamma\rho_{t}e_{t-1}+\phi_{t}$

7:
$\delta_{t}=R_{t+1}+\gamma{\theta}_{t}^{\top}\mathbb{E}_{\pi}\phi(S_{t+1},\cdot)-{\theta}_{t}^{\top}\phi_{t}$

8:
$\omega_{t+1}=\omega_{t}+\beta_{t}(e_{t}\delta_{t}-\phi_{t}\phi_{t}^{\top}\omega_{t})$

9:
$\theta_{t+1}=\theta_{t}-\alpha_{t}(\gamma\mathbb{E}_{\pi}[\phi(S_{t+1,\cdot})]-\phi_{t})e_{t}^{\top}\omega_{t}$

10: end for

11: Output:$\\{\theta_{t},\omega_{t}\\}_{t=1}^{T}$

However, since $A,b$, and $M$ are versions of expectations, we can not get the
transition probability in practice. A practical way is to find the unbiased
estimators of them. Let
$e_{0}=0,\rho_{t}=\frac{\pi(A_{t}|S_{t})}{\mu(A_{t}|S_{t})},e_{t}=\lambda\gamma\rho_{t}e_{t-1}+\phi_{t},\hat{b}_{t}=R_{t+1}e_{t},\hat{A}_{t}=e_{t}(\gamma\mathbb{E}_{\pi}[\phi(S_{t+1,\cdot})]-\phi_{t})^{\top},\hat{M}_{t}=\phi_{t}\phi^{\top}_{t}$.
According to the Theorem 9 of (Maei 2011), we have

$\displaystyle\mathbb{E}_{\mu}[\hat{A}_{t}]=A,\mathbb{E}_{\mu}[\hat{b}_{t}]=b,\mathbb{E}_{\mu}[\hat{M}_{t}]=M.$
(22)

Replacing the expectations in (20) and (21) by corresponding unbiased
estimates, we define the stochastic on-line implementation of (20) and (21) as
follows,

$\displaystyle\omega_{t+1}$
$\displaystyle=\omega_{t}+\beta_{t}(\hat{A}_{t}{\theta}_{t}+\hat{b}_{t}-\hat{M}_{t}\omega_{t}),$
(23) $\displaystyle\theta_{t+1}$
$\displaystyle=\theta_{t}-\alpha_{t}\hat{A}_{t}^{\top}\omega_{t}.$ (24)

We provide more details in Algorithm 1.

## Finite-Time Performance Analysis

In this section, we mainly focus on the finite-time performance of
$\mathtt{GES}(\lambda)$. Theorem 2 shows the proposed $\mathtt{GES}(\lambda)$
converges at a linear rate under a concrete step-size, which is comparable to
extensive existing state-of-the-art GTD algorithms. We have provided an
adequate comparison in Table 1 and a comprehensive discussion in the section
of related works. Furthermore, to investigate how the step-size influences
finite-time performance, we establish Theorem 3. We develop a technique of
Lyapunov function to prove Theorem 3, before we present the main result, we
provide the motivation and some necessary details of Lyapunov function.

Throughout this paper, we make two additional standard assumptions, which are
widely used in reinforcement learning (Wang et al. 2017; Bhandari et al. 2018;
Xu et al. 2019).

######  Assumption 2 (Boundedness of Feature Map, Reward).

The features $\\{\phi_{t}\\}_{t\geq 0}$ is uniformly bounded by $\phi_{\max}$.
The reward function is uniformly bounded by $R_{\max}$. The importance
sampling $\rho_{t}$ is uniformly bounded by $\rho_{\max}$.

######  Assumption 3 (Solvability of Problem).

The matrix $A$ is non-singular and _rank_ $(\Phi)=p$.

As claimed by Xu et al., (2019), Assumption 2 can be ensured by normalizing
the feature maps $\\{\phi_{t}\\}_{t\geq 1}$ and when $\mu(\cdot|s)$ is non-
degenerate for all $s\in\mathcal{S}$. Besides, Assumption 2 implies the
boundedness of the estimators $\hat{A}_{t}$, $\hat{M}_{t}$ and $\hat{b}_{t}$.
For the limitation of space, we provide more details and discussions in Remark
5 (see Appendix D.1).

Assumption 3 requires the non-singularity of the matrix $A$, which implies the
optimal parameter $\theta^{\star}=-A^{-1}b$ is well defined. The feature
matrix $\Phi$ has linearly independent columns implies the matrix $M$ is non-
singular.

### Linear Convergence Rate

We consider the first-order optimality condition of the problem (19), i.e.,
the optimal solution $(\theta^{\star},\omega^{\star})$ satisfies

$\displaystyle\begin{cases}\nabla_{\theta}\Psi(\theta^{\star},\omega^{\star})&=A^{\top}\omega^{\star}=0,\\\
\nabla_{\omega}\Psi(\theta^{\star},\omega^{\star})&=-\nabla
g(\omega^{\star})+A\theta^{\star}=0.\end{cases}$ (25)

According to the Fact 1 and the condition (25), we have

$\omega^{\star}=(\nabla g)^{-1}(A\theta^{\star})=\nabla
g^{\star}(A\theta^{\star}),$

which implies $\omega^{\star}$ can be represented by $\theta^{\star}$, thus,
we mainly focus on the performance of $\\{\theta_{t}\\}_{t\geq 1}$.

######  Theorem 2.

$\\{(\theta_{t},\omega_{t})\\}_{t\geq 0}$ is generated by Algorithm1. Let
$\Delta_{\theta_{t}}=\|\theta_{t}-\theta^{\star}\|^{2}_{2}$,
$\Delta_{\omega_{t}}=\|\omega_{t}-\nabla g^{\star}(A\theta_{t})\|^{2}_{2}$,
$\nu=\dfrac{2\kappa^{2}(A)\kappa(M)\lambda_{\max}(A)}{\lambda_{\min}(M)}$,and
$D_{t}=\nu\Delta_{\theta_{t}}+\Delta_{\omega_{t}}$. If we choose step-size
$\alpha=\frac{\lambda_{\min}(M)}{\big{(}\lambda_{\max}(M)+\lambda_{\min}(M)\big{)}\big{(}\frac{\lambda^{2}_{\max}(A)}{\lambda_{\min}(M)}+\nu\lambda_{\max}(A)\big{)}},\beta=\frac{2}{\lambda_{\max}(M)+\lambda_{\min}(M)}$,
under Assumption 1-3, we have

$\displaystyle\mathbb{E}[D_{t+1}]\leq\Big{(}1-\frac{1}{12\kappa^{3}(M)\kappa^{4}(A)}\Big{)}\mathbb{E}[D_{t}].$
(26)

Furthermore, we have

$\displaystyle\mathbb{E}[\|\theta_{t}-\theta^{\star}\|^{2}_{2}]\leq\frac{1}{\nu}\Big{(}1-\frac{1}{12\kappa^{3}(M)\kappa^{4}(A)}\Big{)}^{t}\mathbb{E}[D_{0}].$
(27)

######  Remark 1.

We provide its proof in Appendix C.3. Recall the fact
$D_{t}=\nu\Delta_{\theta_{t}}+\Delta_{\omega_{t}}\geq\nu\Delta_{\theta_{t}}$,
which implies the inequality

$\mathbb{E}[\|\theta_{t}-\theta^{\star}\|^{2}_{2}]\leq\frac{\mathbb{E}[D_{t}]}{\nu}\overset{(\ref{P_t-1})}{\leq}\dfrac{1}{\nu}\Big{(}1-\frac{1}{12}\frac{1}{\kappa^{3}(M)\kappa^{4}(A)}\Big{)}^{t}\mathbb{E}[D_{0}].$

The term $(1-\frac{1}{12}\frac{1}{\kappa^{3}(M)\kappa^{4}(A)})\in(0,1)$
implies $\mathtt{GES}(\lambda)$ produces the sequence $\\{\theta_{t}\\}_{t\geq
0}$ converges to the optimal solution at a linear convergence rate. After some
simple algebra, with a computational cost of

$\mathcal{O}\bigg{(}\max\Big{\\{}1,\frac{\lambda_{\max}(A)}{\lambda_{\max}(M)\nu}\Big{\\}}\Big{(}1-\frac{1}{12\kappa^{3}(M)\kappa^{4}(A)}\Big{)}\log\frac{1}{\delta}\bigg{)},$

the output of Algorithm 1 closes to $(\theta^{\star},\omega^{\star})$ as
follows,

$\mathbb{E}[\|\theta_{t}-\theta^{\star}\|_{2}^{2}]\leq\delta^{2},~{}~{}~{}\mathbb{E}[\|\omega_{t}-\omega^{\star}\|_{2}^{2}]\leq\delta^{2}.$

######  Remark 2.

Theorem 2 provides a concrete step-size that depends on the some unknown
parameters. As suggested by Du et al. (2017), Touati et al. (2018), and
Voloshin et al. (2019), we can use Monte Carlo method to estimate the unknown
parameters.

### A Further Analysis via Lyapunov Function.

In this section, we propose Theorem 3 that illustrates a relationship between
the performance of $\mathtt{GES}(\lambda)$ and step-size.

The proof of Theorem 3 involves a novel Lyapunov function technique, we start
by presenting the motivation behind such Lyapunov function. Let

$H=-{A}^{\top}M^{-1}{A},L=2A.$

Let $Q_{1}$ and $Q_{2}$ be the solutions of the following equations

$\displaystyle\begin{cases}-H^{\top}Q_{1}-Q_{1}H&=I\\\
M^{\top}Q_{2}+Q_{2}M&=I.\end{cases}$ (28)

Since both $M$ and $-H$ are _Hurwitz_ matrix, the solution of the linear
system (28) alway exists (Lakshminarayanan et al. 2018; Srikant and Ying
2019). Let $Q$ be a matrix as follows,

$Q=\dfrac{1}{p_{1}+p_{2}}\begin{pmatrix}p_{1}&0\\\ 0&p_{2}\end{pmatrix},$

where $p_{1}=\|Q_{1}A^{\top}\|_{op}Q_{1}$,
$p_{2}=\|Q_{2}M^{-1}AL\|_{op}Q_{2}$. Finally, we define $\varrho_{t}$ and
$z_{t}$ as follows,

$\displaystyle\varrho_{t}$
$\displaystyle=\omega_{t}-M^{-1}A\theta_{t},~{}~{}~{}z_{t}=(\theta_{t}-\theta^{\star},\varrho_{t}-\varrho^{\star})^{\top},$
(29)

where $\varrho^{\star}=\omega^{\star}-M^{-1}A\theta^{\star}$. Lyapunov
function $L(z_{t})$ is:

$\displaystyle L(z_{t})=z_{t}^{\top}Qz_{t}.$ (30)

Motivation of Lyapunov Function We consider the expected difference of
iteration (23)-(24) as follows

$\displaystyle\frac{1}{\alpha}\mathbb{E}[\theta_{t+1}-\theta_{t}|Y_{t-\tau}]=$
$\displaystyle\mathbb{E}[-\hat{A}_{t}\omega_{t}|Y_{t-\tau}]$ (31)
$\displaystyle\frac{\alpha}{\beta}\frac{\mathbb{E}[\omega_{t+1}-\omega_{t}|Y_{t-\tau}]}{\alpha}=$
$\displaystyle\mathbb{E}[\hat{A}_{t}{\theta}_{t}+\hat{b}_{t}-\hat{M}_{t}\omega_{t}|Y_{t-\tau}],$
(32)

where $Y_{t-\tau}=\\{\theta_{t-\tau},\omega_{t-\tau},X_{t-\tau}\\}$, and the
sequence $X_{t}=:\\{S_{0},A_{0},S_{1},A_{1},\cdots,S_{t},A_{t}\\}$ denotes a
Markov chain according to Algorithm 1. The expectation is conditioned
sufficiently in the past information of the underlying Markov chain.
Approximating the left parts of (31)-(32) by derivatives, then we have the
ordinary differential equation (ODE):

$\displaystyle\begin{cases}\dot{\theta}(t)=-A\omega(t),\\\
\frac{\alpha}{\beta}\dot{\omega}(t)=A{\theta}({t})+b-M\omega({t}),\end{cases}$
(33)

where $\theta(t),\omega(t)\in\mathbb{R}^{p}$ of (33) are the functions that
are defined on the continuous time $(0,\infty)$. The update rule of (23)-(24)
can be thought of as a discretization of the ODE (33) that is known as
_singular perturbation_ ODE (chapter 11 of (Khalil and Grizzle 2002)), our
goal is to provide a non-asymptotic analysis of $\mathtt{GES}(\lambda)$
according to the asymptotically stable equilibrium of ODE (33). According to
Khalil and Grizzle (2002), the following Lyapunov function $L(t)$ is widely
used as a stability criteria for the ODE (33),

$\displaystyle L(a,t)=$ $\displaystyle
a\big{(}\omega(t)-M^{-1}A\theta(t)\big{)}^{\top}Q_{2}\big{(}\omega(t)-M^{-1}A\theta(t)\big{)}$
$\displaystyle+(1-a)\theta^{\top}(t)Q_{1}\theta(t),$ (34)

where $a\in(0,1)$. Our $L(z_{t})$ (30) can be seen as a discretization of
$L(t)$ (34) after a proper choice of $a$, which inspires us to conduct the
Lyapunov function $L(z_{t})$.

######  Lemma 1.

Under Assumption 1-3, there exists a positive scalar $\tau$ such that:
$t\geq\tau$,

$\displaystyle\mathbb{E}[L(z_{t+1})]-\mathbb{E}[L(z_{t})]$
$\displaystyle\leq-\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\mathbb{E}[L(z_{t})]$
$\displaystyle~{}~{}~{}~{}~{}~{}+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2},$
(35)

where the constants
$\varkappa_{1},\varkappa_{2},\zeta=:C_{1}+\dfrac{\beta}{\alpha}C_{2},\widetilde{c_{b}}$
are defined in Appendix D.

Finally, we know

$\mathbb{E}[\|z_{t}\|_{2}^{2}]\leq(\lambda_{\min}(Q))^{-1}\mathbb{E}[L(z_{t})],$

applying the result of (35) recurrently, we have Theorem 3.

######  Theorem 3.

Let
$\eta_{1}=4\zeta^{2}\tau^{2}(\|z_{0}\|_{2}+\widetilde{c_{b}})^{2}+\|z_{0}\|_{2}^{2})$,
$\eta_{2}=\frac{2\kappa(Q)\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}}{\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}}$.
Under Assumption 1-3, there exists a positive scalar $\tau$ such that:
$t\geq\tau$,

$\displaystyle\mathbb{E}[\|z_{t}\|_{2}^{2}]$
$\displaystyle\leq\alpha^{2}\eta_{1}\Big{(}1-\frac{\alpha}{\lambda_{\max}(Q)}\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\Big{)}^{t-\tau}+\alpha\eta_{2}.$

######  Remark 3.

Recall $z_{t}=(\theta_{t}-\theta^{\star},\varrho_{t}-\varrho^{\star})^{\top}$,
then
$\mathbb{E}[\|\theta_{t}-\theta^{\star}\|^{2}_{2}]\leq\mathbb{E}[\|z_{t}\|_{2}^{2}],$
which implies the expected mean square error of $\theta_{t}-\theta^{\star}$ is
also upper-bounded by the result of Theorem 3. Furthermore, after a total
computational cost of

$\tau+\mathcal{O}\big{(}\frac{1}{\delta}\log\frac{1}{\delta}\big{)},$

the Algorithm 1 outputs $\theta_{t}$ closes to the optimal solution
$\theta^{\star}$ as follows,

$\mathbb{E}[\|\theta_{t}-\theta^{\star}\|_{2}^{2}]\leq\mathcal{O}(\tau\delta).$

######  Remark 4.

Theorem 3 shows that the upper-bounded error consists of two different parts:
the first error bound depends on both step-size and the size of samples, and
this error decays geometrically as the number of iteration increases; while
the second part is only determined by the step-sizes and it is independent of
the number of iterations.

Algorithm |  Step-size |  Convergence Rate |  TD Fixed Point
---|---|---|---
$\mathtt{TD}(0)$ (Nathaniel et al. 2015) |  $\alpha_{t}=\mathcal{O}({t^{-\eta}})$ $\eta\in(0,1)$ | $\mathcal{O}\big{(}\dfrac{1}{\sqrt{T}}\big{)}$ | $\Phi^{\top}\Xi(\gamma P^{\mu}-I)\Phi\theta^{\star}=-b$
$\mathtt{TD}(0)$ (Dalal et al. 2018a) |  $\sum_{t=1}^{\infty}\alpha_{t}=\infty$ |  $\mathcal{O}\big{(}\dfrac{1}{T^{\eta}}\big{)}$ $\eta\in(0,1)$ | $\Phi^{\top}\Xi(\gamma P^{\mu}-I)\Phi\theta^{\star}=-b$
$\mathtt{TD}(0)$ (Lakshminarayanan et al. 2018) |  Constant |  $\mathcal{O}\big{(}\dfrac{1}{T}\big{)}$ | $\Phi^{\top}\Xi(\gamma P^{\mu}-I)\Phi\theta^{\star}=-b$
$\mathtt{GTD}(0)$ (Dalal et al. 2018b) |  $\sum_{t=1}^{\infty}\alpha_{t}=\infty$,$\frac{\beta_{t}}{\alpha_{t}}\rightarrow 0$ |  $\mathcal{O}\big{(}\big{(}\dfrac{1}{T}\big{)}^{\frac{1-\kappa}{3}}\big{)}$ $\kappa\in(0,1)$ | $\Phi^{\top}\Xi(\gamma P^{\pi}-I)\Phi\theta^{\star}=-b$
$\mathtt{GTD}(0)$/$\mathtt{GTD2}$/$\mathtt{TDC}$ (Dalal et al. 2020) |  $\alpha_{t}=\frac{1}{t^{\eta_{1}}}$,$\beta_{t}=\frac{1}{t^{\eta_{2}}}$ $0<\eta_{2}<\eta_{1}<1$ | $\mathcal{O}\big{(}\dfrac{1}{T^{\eta_{1}}}\big{)}$ | $\Phi^{\top}\Xi(\gamma P^{\pi}-I)\Phi\theta^{\star}=-b$
$\mathtt{GTB}(\lambda)$ (Touati et al. 2018) |  $\alpha_{t},\beta_{t}=\mathcal{O}(\frac{1}{t})$ | $\mathcal{O}\Big{(}\dfrac{1}{T}\Big{)}$ | $\Phi^{\top}\Xi(I-\gamma\lambda P^{\mu})^{-1}(\gamma P^{\pi}-I)\Phi\theta^{\star}=-b$
$\mathtt{SARSA}$ (Zou et al. 2019) |  $\alpha_{t}=\mathcal{O}(\frac{1}{t})$ | $\mathcal{O}\Big{(}\dfrac{\log^{3}(T)}{T}\Big{)}$ | $\Phi^{\top}\Xi(\gamma P^{\mu}-I)\Phi\theta^{\star}=-b$
$\mathtt{TDC}$ (Xu et al. 2019) |  $\max\\{\alpha_{t}\log(\frac{1}{\alpha_{t}}),\alpha_{t}\\}$ $\leq\min\\{\frac{\|\theta_{0}-\theta^{\star}\|_{2}}{2^{t-1}},C\\}$ | Linear | $\Phi^{\top}\Xi(\gamma P^{\pi}-I)\Phi\theta^{\star}=-b$
$\mathtt{TDC}$ (Kaledin et al. 2020) |  $\alpha_{t}=\frac{1}{t^{v}}$, $\beta_{t}=\frac{1}{t}$ $v\in(0,1)$ | $\mathcal{O}(\dfrac{1}{T})$ | $\Phi^{\top}\Xi(\gamma P^{\pi}-I)\Phi\theta^{\star}=-b$
$\mathtt{GES(\lambda)}$ Theorem 2 |  Constant | $\mathcal{O}\big{(}(1-\frac{C}{12})^{T}\big{)}$ | $\Phi^{\top}\Xi(I-\gamma\lambda P^{\pi})^{-1}(\gamma P^{\pi}-I)\Phi\theta^{\star}=-b$
Table 1:  Comparison of GTD family algorithms over performance measurement
$\mathbb{E}\|\theta_{T}-\theta^{\star}\|_{2}^{2}$.

## Related Works

In this section, we review existing finite-time performance of GTD algorithms
over $\|\theta_{T}-\theta^{\star}\|_{2}^{2}$.

Although the asymptotic analysis of GTD family has been established in (Sutton
et al. 2009a, b; Maei 2011), which holds only in the limit as the number of
iterations increases to infinity, and we can not get the information of
convergence rate from asymptotic results. This is the main reason why we focus
on the finite-time performance over $\|\theta_{T}-\theta^{\star}\|_{2}^{2}$.
It is noteworthy that Liu et al. (2015) firstly introduce _primal-dual gap
error_ to measure the convergence of GTD algorithm, we provide the discussion
of finite-time primal-dual gap error analysis in Appendix E.

Nathaniel et al. (2015) proves that $\mathtt{TD(0)}$ (Sutton 1988) converges
at $\mathcal{O}(\frac{1}{\sqrt{T}})$ with the step-size
$\alpha_{t}=\mathcal{O}(\frac{1}{t^{\eta}})$, $\eta\in(0,1)$. Later, Dalal et
al. (2018a) further explore the property of $\mathtt{TD(0)}$, they prove the
convergence rate of $\mathtt{TD(0)}$ achieves
$\mathcal{O}(e^{-\frac{\lambda}{2}T^{1-\eta}}+\frac{1}{T^{\eta}})$, but it
never reaches $\mathcal{O}(\frac{1}{T})$, where $\eta\in(0,1)$, $\lambda$ is
the minimum eigenvalue of the matrix $A^{\top}+A$. Lakshminarayanan et al.,
(2018) show $\mathtt{TD(0)}$ converges at $\mathcal{O}(\frac{1}{T})$ with a
more relaxed step-size than the works of (Nathaniel et al. 2015; Dalal et al.
2018a), it only requires a constant step-size. Recently, Dalal et al. (2018b)
proves $\mathtt{GTD(0)}$ family algorithm (Sutton et al. 2009b) converges at
$\mathcal{O}((\frac{1}{T})^{\frac{1-\kappa}{3}})$, but nerve reach
$\mathcal{O}(\frac{1}{T})$, where $\kappa\in(0,1)$. A very similar convergence
rate appears in (Dalal et al. 2020), which considers $\mathtt{TDC}$ and
$\mathtt{GTD2}$. Touati et al. (2018) propose
$\mathtt{GTB}(\lambda)$/$\mathtt{GRetrace}(\lambda)$, they prove the
convergence rate of $\mathtt{GTB}(\lambda)$/$\mathtt{GRetrace}(\lambda)$
reahches $\mathcal{O}(\frac{1}{T})$. Zou et al. (2019) show $\mathtt{SARSA}$
with linear function approximation converges at the rate of
$\mathcal{O}\big{(}\frac{\log^{3}(T)}{T}\big{)}$. Recently, Kaledin et al.
(2020) further develop two timescale stochastic approximation with Markovian
noise, and they show that $\mathtt{TDC}$ converges at a rate of
$\mathcal{O}(\frac{1}{T})$ if $\alpha_{t}=\frac{1}{t^{v}}$,
$\beta_{t}=\frac{1}{t}$, $v\in(0,1)$.

Theorem 2 illustrates our $\mathtt{GES}(\lambda)$ achieves a linear
convergence rate, thus $\mathtt{GES}(\lambda)$ converges faster than all above
gradient TD learning algorithms theoretically. Although Xu et al., (2019)
prove $\mathtt{TDC}$ also converges at a linear convergence rate, they require
a fussy blockwise diminishing step-size condition:
$\max\\{\alpha_{t}\log(\frac{1}{\alpha_{t}}),\alpha_{t}\\}\leq\\{\min\\{\frac{\|\theta_{0}-\theta^{\star}\|_{2}}{2^{t-1}},C\\}$,
$\alpha_{t}=\mathcal{O}({\frac{1}{({t+1})^{\eta_{1}}}})$,
$\beta_{t}=\mathcal{O}({\frac{1}{({t+1})^{\eta_{2}}}})$,
$0<\eta_{2}<\eta_{1}<1$, where $C$ is a constant. Apparently, our Theorem 2
requires a simpler condition of step-size than Xu et al., (2019). It is
noteworthy that our Theorem 2 does not require an additional projection step
(that is unnecessary in practice) that appears in (Xu et al. 2019).

Significantly, the finite-time performances of (Dalal et al. 2018a;
Lakshminarayanan et al. 2018) requires an additional assumption that all the
samples required to update the function parameters are i.i.d. In this paper,
we remove this condition and achieve a better result than theirs.

## Experiments

In this section, we test the capacity of $\mathtt{GES}(\lambda)$ for off-
policy evaluation in three typical domains: MountainCar, Baird Star (Baird
1995), Two-State MDP (Touati et al. 2018). We compare $\mathtt{GES}(\lambda)$
with three state-of-art algorithms: $\mathtt{GQ}(\lambda)$ (Maei and Sutton
2010), $\mathtt{ABQ}(\zeta)$ (Mahmood et al. 2017b), $\mathtt{GTB}(\lambda)$
(Touati et al. 2018) over two typical measurements: MSPBE and mean square
error (MSE). We choose those three algorithms as baselines since they are all
learning via expected TD-error $\delta_{t}^{\text{ES}}$, which is same as
$\mathtt{GES}(\lambda)$.

Feature Map and Parameters Recall the states and actions of MountainCar:
$\mathcal{S}=\\{(\mathtt{Velocity},\mathtt{Position})\\}=[-0.07,0.07]\times[-1.2,0.6]$,
$\mathcal{A}=\\{\mathtt{left},\mathtt{neutral},\mathtt{right}\\}$. In this
example, if $\mathtt{Velocity}>0$, we use behavior policy
$\mu=(\frac{1}{100},\frac{1}{100},\frac{98}{100})$,
$\pi=(\frac{1}{10},\frac{1}{10},\frac{8}{10})$; else
$\mu=(\frac{98}{100},\frac{1}{100},\frac{1}{100})$,
$\pi=(\frac{8}{10},\frac{1}{10},\frac{1}{10})$. Since the state space is
continuous, we use an open _tile coding_
333http://incompleteideas.net/rlai.cs.ualberta.ca/RLAI/RLtoolkit/tilecoding.html
software to extract feature of states. We set the number of tilings to be 4,
and there are no white noise features. The performance is an average 5 runs,
and each run contains 5000 episodes. As suggested by Sutton and Barto (2018),
we set all the initial parameters to be 0, which is optimistic about causing
extensive exploration.

The Baird Star is an episodic seven states MDP with two actions:
$\mathtt{dashed}$ action and $\mathtt{solid}$ action. In this example, we set
the behavior policy $\mu(\cdot|\mathtt{dashed})=\frac{6}{7}$,
$\mu(\cdot|\mathtt{solid})=\frac{1}{7}$ and target policy
$\pi(\cdot|\mathtt{solid})=1$. We choose the feature map matrix as follows
$\Phi=\begin{pmatrix}&2I_{7\times 7}&\mathbbm{1}_{7\times 1}&\bm{0}_{7\times
8}\\\ &\bm{0}_{7\times 8}&2I_{7\times 7}&\mathbbm{1}_{7\times
1}\end{pmatrix}$, where $\bm{0}$ denotes a matrix whose elements are all $0$,
and $\mathbbm{1}_{7\times 1}$ denotes a vector whose elements are all $1$. The
dynamics of Two-State MDP is presented in Example 1. We set $\lambda=0.99$,
$\gamma=0.99$ in all the experiments. The MSPBE/MSE distribution is computed
over the combination of step-size,
$(\alpha_{t},\frac{\beta_{t}}{\alpha_{t}})\in[0.1\times
2^{j}|j=-10,-9,\cdots,-1,0]^{2}$.

Figure 2:  Comparison between a constant step-size and $\frac{1}{\sqrt{t}}$.

Figure 3:  MSPBE and MSE comparison on MountainCar.

Effect of Step-size Figure 2 shows the comparison of the empirical MSPBE
performance between a constant step-size and the decay step-size
$\mathcal{O}(\frac{1}{\sqrt{t}})$. Result of Figure 2 illustrates that the
$\mathtt{GES}(\lambda)$ with a proper constant step-size converges
significantly faster than the learning with step-size
$\mathcal{O}(\frac{1}{\sqrt{t}})$, which also supports Theorem 2: learning
with a proper constant step-size can reach a very faster rate.

Comparison of Empirical MSPBE and MSE In this section, we use empirical
$\text{MSPBE}=\frac{1}{2}\|\hat{b}+\hat{A}\theta\|^{2}_{\hat{M}^{-1}}$ to
evaluate the performance, where we evaluate $\hat{A}$, $\hat{b}$, and
$\hat{M}$ according to their unbiased estimators by Monte Carlo method with
5000 episodes, and our implementation of MSPBE is inspired by (Touati et al.
2018). Besides, we also compare the performance over a common measurement
empirical MSE:
$\text{MSE}=\|\Phi\theta-q^{\pi}\|^{2}_{\Xi}/\|q^{\pi}\|^{2}_{\Xi}$, where
$q^{\pi}$ is estimated by simulating the target policy $\pi$ and averaging the
discounted cumulative rewards over trajectories. The combination of step-size
for MSE is the same as previous empirical MSPBE.

Results in Figure 3 to 5 show that our $\mathtt{GES}(\lambda)$ learns faster
with a better performance than $\mathtt{GQ}(\lambda)$, $\mathtt{ABQ}(\zeta)$
and $\mathtt{GTB}(\lambda)$. Besides, $\mathtt{GES}(\lambda)$ converges with a
lower variance. In the Two-State MDP and Baird Star experiments,
$\mathtt{GES}(\lambda)$ outperforms the baselines slightly. This is because
both Two-State MDP and Baird Star are relatively easy; many gradient TD
learning could learn a convergent result. While the advantage of
$\mathtt{GES}(\lambda)$ over baselines becomes more significant in the
MountainCar domain, which shows that $\mathtt{GES}(\lambda)$ is more robust
than baselines in the more difficult task.

Figure 4:  MSPBE and MSE comparison on Baird Star.

Figure 5:  MSPBE and MSE comparison on Two-State MDP.

## Conclusion

We propose $\mathtt{GES}(\lambda)$ that extends
$\mathtt{Expected~{}Sarsa}(\lambda)$ with linear function approximation. We
prove $\mathtt{GES}(\lambda)$ learns the optimal solution at a linear
convergence rate, which is comparable to extensive GTD algorithms. The primal-
dual gap error of $\mathtt{GES}(\lambda)$ matches the best-known theoretical
results, but we require a simpler condition of step-size. Finally, we conduct
experiments to verify the effectiveness of $\mathtt{GES}(\lambda)$.

## References

  * Baird (1995) Baird, L. 1995.  Residual algorithms: Reinforcement learning with function approximation.  In _ICML_ , 30–37.
  * Bertsekas (2011) Bertsekas, D. P. 2011.  Temporal difference methods for general projected equations.  _IEEE Transactions on Automatic Control_ 56(9): 2128–2139.
  * Bertsekas (2012) Bertsekas, D. P. 2012.  _Dynamic Programming and Optimal Control_ , volume 2.  Athena scientific Belmont, MA.
  * Bhandari et al. (2018) Bhandari, J.; Russo, D.; Singal, R.; et al. 2018.  A finite time analysis of temporal difference learning with linear function approximation.  _COLT_ .
  * Dalal et al. (2018a) Dalal, G.; Szorenyi, B.; Thoppe, G.; and Mannor, S. 2018a.  Finite sample analyses for td(0) with function approximation.  In _AAAI2018_.
  * Dalal et al. (2018b) Dalal, G.; Szorenyi, B.; Thoppe, G.; and Mannor, S. 2018b.  Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning.  In _COLT_.
  * Dalal et al. (2020) Dalal, G.; Szorenyi, B.; Thoppe, G.; et al. 2020.  A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound.  _AAAI_ .
  * Dann et al. (2014) Dann, C.; Neumann, G.; Peters, J.; et al. 2014.  Policy evaluation with temporal differences: A survey and comparison.  _JMLR_ 15(1): 809–883.
  * Du et al. (2017) Du, S. S.; Chen, J.; Li, L.; Xiao, L.; and Zhou, D. 2017.  Stochastic variance reduction methods for policy evaluation.  _ICML_ .
  * Du and Hu (2019) Du, S. S.; and Hu, W. 2019.  Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity.  _AISTATS_ .
  * Geist and Scherrer (2014) Geist, M.; and Scherrer, B. 2014.  Off-policy learning with eligibility traces: A survey.  _JMLR_ .
  * Ghosh and Bellemare (2020) Ghosh, D.; and Bellemare, M. G. 2020.  Representations for Stable Off-Policy Reinforcement Learning.  _ICML_ .
  * Gupta et al. (2019) Gupta, H.; Srikant, R.; Ying, L.; et al. 2019.  Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning.  In _NeurIPS_ , 4704–4713.
  * Kakade et al. (2009) Kakade, S.; Shalev-Shwartz, S.; Tewari, A.; et al. 2009.  On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization .
  * Kaledin et al. (2020) Kaledin, M.; Moulines, E.; Naumov, A.; Tadic, V.; and Wai, H.-T. 2020.  Finite time analysis of linear two-timescale stochastic approximation with Markovian noise.  _COLT_ .
  * Khalil and Grizzle (2002) Khalil, H. K.; and Grizzle, J. W. 2002.  _Nonlinear systems_ , volume 3.  Prentice hall Upper Saddle River, NJ.
  * Lagoudakis and Parr (2003) Lagoudakis, M. G.; and Parr, R. 2003.  Least-squares policy iteration.  _JMLR_ 4: 1107–1149.
  * Lakshminarayanan et al. (2018) Lakshminarayanan, C.; Szepesvari; Csaba; et al. 2018.  Linear Stochastic Approximation: How Far Does Constant Step-Size and Iterate Averaging Go?  In _AISTATS_.
  * Liu et al. (2015) Liu, B.; Liu, J.; Ghavamzadeh, M.; Mahadevan, S.; and Petrik, M. 2015.  Finite-Sample Analysis of Proximal Gradient TD Algorithms.  In _UAI_.
  * Maei (2011) Maei, H. R. 2011.  _Gradient temporal-difference learning algorithms_.  Ph.D. thesis, University of Alberta Edmonton, Alberta.
  * Maei and Sutton (2010) Maei, H. R.; and Sutton, R. S. 2010.  GQ($\lambda$): A general gradient algorithm for temporal-difference prediction learning with eligibility traces.  In _Proceedings of the third conference on artificial general intelligence_ , volume 1, 91–96.
  * Mahmood et al. (2017b) Mahmood, A. R.; Yu, H.; Sutton, R. S.; et al. 2017b.  Multi-step off-policy learning without importance sampling ratios.
  * Nathaniel et al. (2015) Nathaniel, K.; Prashanth, L.; Prashanth, L.; et al. 2015.  On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence.  In _ICML_.
  * Nemirovski et al. (2009) Nemirovski, A.; Juditsky, A.; Lan, G.; and Shapiro, A. 2009.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on optimization_ 19(4): 1574–1609.
  * Precup, Sutton, and Singh (2000) Precup, D.; Sutton, R. S.; and Singh, S. P. 2000.  Eligibility Traces for Off-Policy Policy Evaluation.  In _International Conference on Machine Learning_ , 759–766. Citeseer.
  * Rockafellar (1970) Rockafellar, R. T. 1970.  _Convex analysis_.  28\. Princeton university press.
  * Rubinstein and Kroese (2016) Rubinstein, R. Y.; and Kroese, D. P. 2016.  _Simulation and the Monte Carlo method_ , volume 10.  John Wiley & Sons.
  * Srikant and Ying (2019) Srikant; and Ying, L. 2019.  Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning.  In _COLT_.
  * Sutton (1988) Sutton, R. S. 1988.  Learning to predict by the methods of temporal differences.  _Machine learning_ 3(1): 9–44.
  * Sutton and Barto (1998) Sutton, R. S.; and Barto, A. G. 1998.  _Reinforcement learning: An introduction_.  MIT press Cambridge.
  * Sutton and Barto (2018) Sutton, R. S.; and Barto, A. G. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Sutton et al. (2009a) Sutton, R. S.; Maei, H. R.; Precup, D.; Bhatnagar, S.; Silver, D.; Szepesvári, C.; and Wiewiora, E. 2009a.  Fast gradient-descent methods for temporal-difference learning with linear function approximation.  In _ICML_.
  * Sutton et al. (2009b) Sutton, R. S.; Maei, H. R.; Szepesvári, C.; et al. 2009b.  A Convergent $O(n)$ Temporal-difference Algorithm for Off-policy Learning with Linear Function Approximation.  In _NeurIPS_.
  * Sutton et al. (2016) Sutton, R. S.; Mahmood, A. R.; White, M.; et al. 2016.  An emphatic approach to the problem of off-policy temporal-difference learning.  _JMLR_ 17(1): 2603–2631.
  * Thomas (2015) Thomas, P. S. 2015.  _Safe reinforcement learning_.  Ph.D. thesis, University of Massachusetts Libraries.
  * Touati et al. (2018) Touati, A.; Bacon, P.-L.; Precup, D.; and Vincent, P. 2018.  Convergent Tree-Backup and Retrace with Function Approximation.  In _ICML_.
  * Voloshin et al. (2019) Voloshin, C.; Le, H. M.; Jiang, N.; and Yue, Y. 2019.  Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning.  _arXiv preprint arXiv:1911.06854_ .
  * Wang et al. (2019) Wang, G.; Li, B.; Giannakis, G. B.; et al. 2019.  A multistep Lyapunov approach for finite-time analysis of biased stochastic approximation.  _arXiv preprint arXiv:1909.04299_ .
  * Wang et al. (2017) Wang, Y.; Chen, W.; Liu, Y.; Ma, Z.-M.; and Liu, T.-Y. 2017.  Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting.  In _Advances in Neural Information Processing Systems(NeurIPS)_.
  * Xu et al. (2019) Xu, T.; Zou, S.; Liang, Y.; et al. 2019.  Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples.  In _NeurIPS_.
  * Zou et al. (2019) Zou, S.; Xu, T.; Liang, Y.; et al. 2019.  Finite-sample analysis for SARSA with linear function approximation.  In _NeurIPS_.

##  Appendix A Appendix A: Importance Sampling and $\lambda$-Operator

For the discussion of off-policy learning, we need the background of
importance sampling. Thus, the basic common conclusion about importance
sampling (IS) and pre-decision importance sampling (PDIS) (Precup, Sutton, and
Singh 2000) is necessary.

### A.1. Off-Policy Learning via Importance Sampling

Usually, we require that every action taken by $\pi$ is also taken by $\mu$,
which is often called _coverage_ (Sutton and Barto 2018) in reinforcement
learning.

######  Assumption 4 (Coverage).

$\forall~{}(s,a)\in\mathcal{S}\times\mathcal{A}$, we require that
$\pi(a|s)>0\Rightarrow\mu(a|s)>0$.

The difficulty of off-policy roots in the discrepancy between target policy
$\pi$ and behavior policy $\mu$ —-we want to learn the target policy while we
only get the data generated by behavior policy. One technique to hand this
discrepancy is _importance sampling_ (IS) (Rubinstein and Kroese 2016). Let
$\tau_{t}^{h}=\\{S_{t},A_{t},R_{t+1}\\}_{t\geq 0}^{h}$ be a trajectory with
finite horizon $h<\infty$. Let $\rho_{t:k}=\prod_{i=t}^{k}\rho_{i}$ denote the
_cumulated importance sampling ratio_ , where
$\rho_{i}=\frac{\pi(A_{i}|S_{i})}{\mu(A_{i}|S_{i})}$ and $k\leq h$. Let
$G_{t}^{h}=\sum_{k=0}^{h-t-1}\gamma^{k}R_{k+t+1}$, under Assumption 4 the IS
estimator $G_{t}^{\text{IS}}=\rho_{t:h-1}G^{h}_{t}$ is a unbiased estimation
of $q^{\pi}$. However, it is known that IS estimator suffers from large
variance of the product $\rho_{t:h-1}$ (Sutton and Barto 1998). Pre-decision
importance sampling (PDIS) (Precup, Sutton, and Singh 2000)
$G_{t}^{\text{PDIS}}=\sum_{k=0}^{h-t-1}\gamma^{k}\rho_{t:t+k}R_{t+k+1}$ is a
practical variance reduction method without introducing bias, i.e.
$\mathbb{E}_{\mu}[G_{t}^{\text{PDIS}}|S_{t}=s,A_{t}=a]=q^{\pi}(s,a)$.

$\displaystyle\mathbb{E}_{\mu}[\rho_{t:h-1}G_{t}^{h}]=$
$\displaystyle\mathbb{E}_{\mu}[\underbrace{\rho_{t:h-1}R_{t+1}+\rho_{t:h-1}\gamma
R_{t+2}+\cdots+\rho_{t:h-1}\gamma^{h-t-1}R_{h}}_{\overset{\text{def}}{=}G_{t}^{\text{IS}}~{}~{}\text{IS-
return}}]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\mu}[\underbrace{\rho_{t}R_{t+1}+\rho_{t:t+1}\gamma
R_{t+2}+\cdots+\rho_{t:h-1}\gamma^{h-t-1}R_{h}}_{\overset{\text{def}}{=}G_{t}^{\text{PDIS}}~{}~{}\text{PDIS-
return}}]=\mathbb{E}_{\mu}[\sum_{k=0}^{h-t-1}\gamma^{k}\rho_{t:t+k}R_{t+k+1}].$

For the equation
$\mathbb{E}_{\mu}[G_{t}^{\text{IS}}]=\mathbb{E}_{\mu}[G_{t}^{\text{PDIS}}]$,
please see(Precup, Sutton, and Singh 2000) or section 5.9 in (Sutton and Barto
2018).

######  Lemma 2 (Section 3.10, (Thomas 2015); Section 5.9, (Sutton and Barto
2018)).

Let $\tau_{t}^{h}=\\{S_{k},A_{k},R_{k+1}\\}_{k=t}^{h}$ be the trajectory
generated by behavior policy $\mu$, for a given policy $\pi$ and under
Assumption 4, the following holds,

$\displaystyle\mathbb{E}_{\mu}[\rho_{t:h-1}R_{t+k}]=\mathbb{E}_{\mu}[\rho_{t:t+k-1}R_{t+k}].$
(36)

Lemma 2 implies that for any time $t+k~{}(k\geq 0)$, the importance sampling
factors after $t+k$ have no effect in the expectation, thus the following
holds: for all $k\geq 0$,

$\displaystyle\mathbb{E}_{\mu}[\rho_{t:h-1}R_{t+k}]=\mathbb{E}_{\mu}[\rho_{t:t+k-1}R_{t+k}]=\mathbb{E}_{\pi}[R_{t+k}].$
(37)

### A.2. Derivation of Eq.(7)

###### Proof.

$\displaystyle
q+\mathbb{E}_{\mu}[\sum_{k=t}^{\infty}(\lambda\gamma)^{k-t}\delta^{\text{ES}}_{k}\rho_{t+1:k}]\overset{(\ref{app1_lemma_corr})}{=}$
$\displaystyle
q+\mathbb{E}_{\pi}[\sum_{k=t}^{\infty}(\lambda\gamma)^{k-t}\delta^{\text{ES}}_{k}]$
$\displaystyle=$ $\displaystyle q+(I-\lambda\gamma
P^{\pi})^{-1}(\mathcal{B}^{\pi}q-q),$ (38)

Eq. (38) is a common result in RL, for the details of

$\mathbb{E}_{\pi}[\sum_{k=t}^{\infty}(\lambda\gamma)^{l-t}\delta^{\text{ES}}_{k}]=(I-\lambda\gamma
P^{\pi})^{-1}(\mathcal{B}^{\pi}q-q),$

please refer to (Geist and Scherrer 2014) or Section 6.3.9 in (Bertsekas
2012). ∎

##  Appendix B Appendix B: Proof of Theorem 1

Theorem 1(Stability Criteria) _Under Assumption 1, the off-line update (9) is
stable if and only if the eigenvalues of the matrix A (10) have negative real
components, i.e.,_

$\displaystyle\emph{Spec}(A)\subset\mathbb{C}_{-}.$ (39)

Before we present the details of its proof, we need some notations of the
matrix. Recall $\text{Spec}(A)$ are the eigenvalues of the matrix
$A\in\mathbb{C}^{p\times p}$, we use $\rho(A)$ to denote its spectral radius
of the matrix $A$, i.e.,

$\rho(A)=\sup_{\lambda\in\text{Spec}(A)}\\{|\lambda|\\}.$

###### Proof.

Recall $A=\Phi^{\top}\Xi(I-\gamma\lambda P^{\pi})^{-1}(\gamma P^{\pi}-I)\Phi,$
and $\theta^{\star}$ satisfies

$A\theta^{\star}+b=0,$

which implies

$\displaystyle\theta_{t+1}-\theta^{\star}=\theta_{t}-\alpha(A\theta_{t}+b)-\theta^{\star}=(I+\alpha
A)(\theta_{t}-\theta^{\star}).$

Applying above result of recurrently, we have

$\displaystyle\theta_{t}-\theta^{\star}=(I+\alpha
A)^{t}(\theta_{0}-\theta^{\star}),$ (40)

which implies if the iteration (40) converges, if and only if

$\rho(I+\alpha A)<1.$

Furthermore, if the iteration (40) is stable, if and only if $\rho(I+\alpha
A)<1$. If there is a step-size $\alpha>0$ such that $\rho(I+\alpha A)<1$, then
we have $\text{Spec}(A)\subset\mathbb{C}_{-}$. Conversely, if
$\text{Spec}(A)\subset\mathbb{C}_{-}$, and let

$\alpha=\inf_{\lambda\in\text{Spec}(A)}\Big{\\{}\dfrac{\text{Re}(\lambda)}{|\lambda|}\Big{\\}},$

then $\rho(I+\alpha A)<1$. ∎

##  Appendix C Appendix C

### C.1: Proof of Eq.(17)

For a given policy $\pi$, $Q_{\theta}=\Phi\theta$, then by the definition of
MSPBE objection function, we have,

$\displaystyle\text{MSPBE}(\theta,\lambda)$
$\displaystyle=\|Q_{\theta}-\Pi\mathcal{B}_{\lambda}^{\pi}Q_{\theta}\|^{2}_{\Xi}$
$\displaystyle=\|\Pi
Q_{\theta}-\Pi\mathcal{B}_{\lambda}^{\pi}Q_{\theta}\|^{2}_{\Xi}$
$\displaystyle=\|\Phi^{T}\Xi(Q_{\theta}-\mathcal{B}_{\lambda}^{\pi}Q_{\theta})\|^{2}_{({\Phi^{T}\Xi\Phi})^{-1}}$
$\displaystyle=\|\Phi^{T}\Xi(I-\lambda\gamma P^{\pi})^{-1}(\Phi\theta-\gamma
P^{\pi}\Phi\theta-R^{\pi})\|^{2}_{({\Phi^{T}\Xi\Phi})^{-1}}$
$\displaystyle=\|\Phi^{T}\Xi(I-\lambda\gamma P^{\pi})^{-1}\big{(}(I-\gamma
P^{\pi})\Phi\theta-R^{\pi}\big{)}\|^{2}_{({\Phi^{T}\Xi\Phi})^{-1}}$
$\displaystyle=\|b+A\theta\|^{2}_{({\Phi^{T}\Xi\Phi})^{-1}},$ (41)

where $A=\Phi^{T}\Xi(I-\lambda\gamma P^{\pi})^{-1}(\gamma
P^{\pi}-I)\Phi,b=\Phi\Xi(I-\lambda\gamma P^{\pi})^{-1}r.$

### C.2: Proof of Proposition 1

Proposition 1 If $(\theta_{\star},\omega_{\star})$ is the solution of the
problem (19), then $\theta_{\star}$ is the solution of original problem (17),
i.e.,

$\theta_{\star}=\arg\min_{\theta}\text{MSPBE}(\theta,\lambda).$

###### Proof.

If
$\omega_{\star}=\arg\max_{\omega}{(A\theta+b)^{\top}\omega-\frac{1}{2}\|\omega\|_{M}^{2}}$,
then $\omega_{\star}=M^{-1}(A\theta+b)$. Taking $\omega_{\star}$ into (19),
then (19) is reduced to $\min_{\theta}\frac{1}{2}\|A\theta+b\|^{2}_{M^{-1}}$.
Now, let $\theta_{\star}$ be the solution of (19), then we have

$\theta_{\star}=\min_{\theta}\frac{1}{2}\|A\theta+b\|^{2}_{M^{-1}}=\arg\min_{\theta}\text{MSPBE}(\theta,\lambda).$

∎

### C.3: Proof of Theorem 2

Theorem 2 Let $\\{(\theta_{t},\omega_{t})\\}_{t=0}^{T}$ be generated by
Algorithm1. Recall $g(\omega)$ has been defined in (18) and $\theta^{\star}$
is the optimal solution of (17). Let
$\nu=\dfrac{2\kappa^{2}(A)\kappa(M)\sigma_{\max}(A)}{\sigma_{\min}(M)}$,
$\Delta_{\theta_{t}}=\|\theta_{t}-\theta_{\star}\|^{2}_{2}$,
$\Delta_{\omega_{t}}=\|\omega_{t}-\nabla g^{\star}(A\theta_{t})\|^{2}_{2}$,
and $D_{t}=\nu\Delta_{\theta_{t}}+\Delta_{\omega_{t}}$. Under Assumption 1,
and we assume $\emph{rank}(\Phi)=p$. Let

$\alpha=\dfrac{\sigma_{\min}(M)}{\big{(}\sigma_{\max}(M)+\sigma_{\min}(M)\big{)}\big{(}\frac{\sigma^{2}_{\max}(A)}{\sigma_{\min}(M)}+\nu\sigma_{\max}(A)\big{)}},\beta=\dfrac{2}{\sigma_{\max}(M)+\sigma_{\min}(M)},$

under Assumption 1, we have

$\displaystyle\mathbb{E}[D_{t+1}]\leq\Big{(}1-\dfrac{1}{12}\dfrac{1}{\kappa^{3}(M)\kappa^{4}(A)}\Big{)}\mathbb{E}[D_{t}].$
(42)

Furthermore, we have

$\mathbb{E}[\|\theta_{t}-\theta_{\star}\|^{2}_{2}]\leq\dfrac{1}{\nu}\Big{(}1-\dfrac{1}{12}\dfrac{1}{\kappa^{3}(M)\kappa^{4}(A)}\Big{)}^{t}\mathbb{E}[D_{0}].$

###### Proof.

The proof is inspired by a general analysis that appears in (Du and Hu 2019);
we refer the reader to that reference for further technical details.

Firstly, we apply Theorem 3.1 of (Du and Hu 2019) to achieve (42), which
requires us to check $g(\omega)$ is a Lipschitz-smooth and strongly convex
function. Recall $g(\omega)=\frac{1}{2}\|\omega\|^{2}_{M}-b^{\top}\omega$, for
any $\omega_{1}$, $\omega_{2}$, we have

$\displaystyle\|\nabla g(\omega_{1})-\nabla
g(\omega_{1})\|_{2}=\|M(\omega_{1}-\omega_{2})\|_{2}\leq\|M\|_{\text{op}}\|\omega_{1}-\omega_{2}\|_{2}\overset{(\textbf{a})}{=}\sigma_{\max}(M)\|\omega_{1}-\omega_{2}\|_{2},$
(43)

where the last equation (a) of (43) holds since
$M=\mathbb{E}_{\mu}[\phi_{t}\phi_{t}^{\top}]=\Phi^{\top}\Xi\Phi$ is a positive
symmetric matrix if $\text{rank}(\Phi)=p$, then

$\|M\|_{\text{op}}=\max\\{\lambda_{1},\lambda_{2},\cdots,\lambda_{p}\\}=\sigma_{\max}(M).$

Eq.(43) implies $g(\omega)$ is $\sigma_{\max}(M)$-smooth function. Under
Assumption 1, $\Xi\succ 0$; recall rank$(\Phi)$$=$$p$, so
$M=\Phi^{\top}\Xi\Phi\succ 0$, then $\nabla^{2}g(\omega)=M$ implies

$\nabla^{2}g(\omega)-\sigma_{\min}(M)I\succ 0,$

thus $g(\omega)$ is a $\sigma_{\min}(M)$-strongly convex function. Let step-
size satisfy the following condition

$\alpha=\dfrac{\sigma_{\min}(M)}{\big{(}\sigma_{\max}(M)+\sigma_{\min}(M)\big{)}\big{(}\frac{\sigma^{2}_{\max}(A)}{\sigma_{\min}(M)}+\nu\sigma_{\max}(A)\big{)}},\beta=\dfrac{2}{\sigma_{\max}(M)+\sigma_{\min}(M)},$

then according to Theorem 3.1 of (Du and Hu 2019), we have

$\mathbb{E}[D_{t+1}]\leq\Big{(}1-\dfrac{1}{12}\dfrac{1}{\kappa^{3}(M)\kappa^{4}(A)}\Big{)}\mathbb{E}[D_{t}].$

Furthermore, the fact
$D_{t}=\nu\Delta_{\theta_{t}}+\Delta_{\omega_{t}}\geq\nu\Delta_{\theta_{t}}$
implies

$\mathbb{E}[\|\theta_{t}-\theta_{\star}\|^{2}_{2}]\leq\frac{\mathbb{E}[D_{t}]}{\nu}\overset{(\ref{P_t})}{\leq}\dfrac{1}{\nu}\Big{(}1-\frac{1}{12}\frac{1}{\kappa^{3}(M)\kappa^{4}(A)}\Big{)}^{t}\mathbb{E}[D_{0}].$

Therefore the proof is completed. ∎

######  Corollary 1.

Consider all the conditions and notations in Theorem 2, the output of
Algorithm 1 closes to $(\theta^{\star},\omega^{\star})$ as follows,

$\mathbb{E}[\|\theta_{t}-\theta^{\star}\|_{2}^{2}]\leq\delta^{2},~{}~{}~{}\mathbb{E}[\|\omega_{t}-\omega^{\star}\|_{2}^{2}]\leq\delta^{2},$

if after a computational cost of

$\mathcal{O}\bigg{(}\max\Big{\\{}1,\frac{\lambda_{\max}(A)}{\lambda_{\max}(M)\nu}\Big{\\}}\Big{(}1-\frac{1}{12\kappa^{3}(M)\kappa^{4}(A)}\Big{)}\log(\frac{1}{\delta})\bigg{)}.$

###### Proof.

Furthermore, recall $\omega^{\star}=(\nabla g)^{-1}(A\theta^{\star})=\nabla
g^{\star}(A\theta^{\star})$, then we have

$\displaystyle\|\omega_{t}-\omega^{\star}\|_{2}\leq$
$\displaystyle\|\omega_{t}-\nabla g^{\star}(A\theta_{t})\|_{2}+\|\nabla
g^{\star}(A\theta_{t})-\omega^{\star}\|_{2}$ $\displaystyle\leq$
$\displaystyle\Delta_{\omega_{t}}+\|\nabla
g^{\star}(A\theta_{t})-g^{\star}(A\theta^{\star})\|_{2}$ $\displaystyle\leq$
$\displaystyle\Delta_{\omega_{t}}+\dfrac{\lambda_{\max}(A)}{\lambda_{\max}(M)}\Delta_{\theta_{t}}\leq\max\Big{\\{}1,\dfrac{\lambda_{\max}(A)}{\lambda_{\max}(M)\nu}\Big{\\}}D_{t}.$

Since
$\mathbb{E}[D_{t+1}]\leq\Big{(}1-\frac{1}{12}\frac{1}{\kappa^{3}(M)\kappa^{4}(A)}\Big{)}\mathbb{E}[D_{t}]$,
then we have

$\mathbb{E}[\|\omega_{t}-\omega^{\star}\|_{2}]\leq\max\Big{\\{}1,\dfrac{\lambda_{\max}(A)}{\lambda_{\max}(M)\nu}\Big{\\}}\mathbb{E}[D_{t+1}]\leq\max\Big{\\{}1,\dfrac{\lambda_{\max}(A)}{\lambda_{\max}(M)\nu}\Big{\\}}\Big{(}1-\dfrac{1}{12}\dfrac{1}{\kappa^{3}(M)\kappa^{4}(A)}\Big{)}^{t}\mathbb{E}[D_{0}].$

If, $\mathbb{E}[\|\omega_{t}-\omega^{\star}\|_{2}]\leq\delta$, then the times
of update at least

$\mathcal{O}\bigg{(}\max\Big{\\{}1,\frac{\lambda_{\max}(A)}{\lambda_{\max}(M)\nu}\Big{\\}}\Big{(}1-\frac{1}{12\kappa^{3}(M)\kappa^{4}(A)}\Big{)}\log(\frac{1}{\delta})\bigg{)}.$

This conclude the result of Remark 1. ∎

##  Appendix D Appendix D: Proof of Theorem 3

### D.1: Some Preliminaries

Assumption 2 (Boundedness of Feature Map, Reward) _The features
$\\{\phi_{t}\\}_{t\geq 0}$ is uniformly bounded by $\phi_{\max}$. The reward
function is uniformly bounded by $R_{\max}$. The importance sampling
$\rho_{t}$ is uniformly bounded by $\rho_{\max}$. _

######  Remark 5.

Assumption 2 implies the boundedness of $\hat{A}_{t}$, $\hat{M}_{t}$ and
$\hat{b}_{t}$. In fact,

$\|\hat{M}_{t}\|_{op}^{2}=\|\phi_{t}\phi^{\top}_{t}\|_{op}^{2}\leq(p\sqrt{p}\phi^{2}_{\max})^{2}=:C^{2}_{M},$

where we use a basic fact for matrix: for each $A\in\mathbb{R}^{p\times p}$,
we have $\|A\|_{op}\leq p\sqrt{p}\|A\|_{\infty}$. The boundedness of
$\hat{M}_{t}$ also imply the boundedness of $M$, i..e,

$\|M\|_{op}\leq C_{M}.$

Furthermore, since $M=\Phi^{\top}\Xi\Phi$ and $\text{rank}(\Phi)=p$, thus,
both $M$ and $M^{-1}$ are all positive define matrix, then, there exists a
positive scalar ${C}_{M^{-1}}$ such that

$\|M^{-1}\|_{op}\leq C_{M^{-1}}.$

Recall $e_{t}=\lambda\gamma\rho_{t}e_{t-1}+\phi_{t}$, then

$\|e_{t}\|_{2}^{2}=\big{\|}\sum_{k=0}^{t}(\gamma\lambda)^{t-k}\rho_{k+1:t}\phi_{k}\big{\|}_{2}^{2}\leq\Big{(}\frac{\phi_{\max}}{1-\gamma\lambda\rho_{\max}}\Big{)}^{2}=:C^{2}_{e}.$

Since then,

$\displaystyle\|\hat{b}_{t}\|_{2}^{2}=$
$\displaystyle\|R_{t+1}e_{t}\|_{2}^{2}\leq R^{2}_{\max}C^{2}_{e}=:C^{2}_{b},$
$\displaystyle\|\hat{A}_{t}\|_{2}^{2}=$
$\displaystyle\|e_{t}(\gamma\mathbb{E}_{\pi}[\phi(S_{t+1,\cdot})]-\phi_{t})^{\top}\|^{2}_{2}\leq(\gamma+1)^{2}C^{2}_{e}\phi^{2}_{\max}=:C^{2}_{A}.$

Above results also imply the boundedness of $A$ and $b$, i.e.,

$\|A\|_{op}\leq C_{A},~{}~{}\text{and}~{}~{}\|b\|_{2}\leq C_{b}.$

######  Lemma 3 ((Gupta et al. 2019)).

Consider the matrix $A$ as follows

$A(x)=\dfrac{1}{a_{1}+a_{2}}\begin{pmatrix}a_{2}&-a_{1}a_{2}\\\
-a_{1}a_{2}&\dfrac{1}{x}a_{1}-xya_{1}\end{pmatrix},$

where $a_{1},a_{2},c,y>0$. Then we have

$\lambda_{\min}(A(x))\geq\kappa_{1}-\kappa_{2}x,$

where $\kappa_{1}=\dfrac{a_{2}}{a_{1}+a_{2}}$ and $\kappa_{2}$ is a constant
that only depends on $a_{1},a_{2}$ and $x$.

### D.2: Proof of Lemma 1

Lemma 1 _Under Assumption 1-3, there exists a positive scalar $\tau$ such
that: $t\geq\tau$,_

$\displaystyle\mathbb{E}[L(z_{t+1})]-\mathbb{E}[L(z_{t})]$
$\displaystyle\leq-\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\mathbb{E}[L(z_{t})]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2},$

_where $\varkappa_{1},\varkappa_{2},\zeta,\widetilde{c_{b}}$ are constants
that we will concretize them later. _

We define

$\displaystyle\hat{H}_{t}$
$\displaystyle=-\hat{A}_{t}^{\top}M^{-1}{A},~{}~{}~{}~{}H=-{A}^{\top}M^{-1}{A},$
$\displaystyle\hat{L}_{t}$
$\displaystyle=\hat{A}_{t}+\hat{M}_{t}M^{-1}A,~{}~{}~{}~{}L=2A.$

By the boundedness of the previous term, we have

$\displaystyle\|\hat{H}_{t}\|_{op}$
$\displaystyle\leq\|\hat{A}_{t}^{\top}M^{-1}{A}\|_{op}\leq
C^{2}_{A}C_{M^{-1}},$ $\displaystyle\|\hat{L}_{t}\|_{op}$
$\displaystyle\leq\|\hat{A}_{t}\|_{op}+\|\hat{M}_{t}M^{-1}A\|_{op}\leq
C_{A}+C_{M}C_{M^{-1}}C_{A},~{}\|L\|_{op}\leq 2C_{A}.$

Furthermore, let $Q_{1}$ and $Q_{2}$ be the solutions of the following
equations

$\displaystyle\begin{cases}H^{\top}Q_{1}+Q_{1}H&=-I\\\
M^{\top}Q_{2}+Q_{2}M&=I,\end{cases}$ (44)

since both $M$ and $L$ are Hurwitz matrix, then solution of (44) always
exists. Furthermore, we define a matrix $P$ as follows,

$\displaystyle
Q=\begin{pmatrix}\dfrac{\|Q_{1}A^{\top}\|_{op}}{\|Q_{1}A^{\top}\|_{op}+\|Q_{2}M^{-1}AL\|_{op}}Q_{1}&0\\\
0&\dfrac{\|Q_{2}M^{-1}AL\|_{op}}{\|Q_{1}A^{\top}\|_{op}+\|Q_{2}M^{-1}AL\|_{op}}Q_{2}\end{pmatrix}.$
(45)

We define

$\displaystyle\varrho_{t}$
$\displaystyle=\omega_{t}-M^{-1}A\theta_{t},~{}~{}~{}z_{t}=\begin{pmatrix}\theta_{t}-\theta^{\star}\\\
\varrho_{t}-\varrho^{\star},\end{pmatrix}.$ (46)

where $\varrho_{\star}=\omega^{\star}-M^{-1}A\theta^{\star}$. Let $L(z_{t})$
be the following Lyapunov function,

$\displaystyle L(z_{t})=z_{t}^{\top}Qz_{t}.$ (47)

###### Proof.

Recall the update (23) and (24):

$\omega_{t+1}=\omega_{t}+\beta(\hat{A}_{t}{\theta}_{t}+\hat{b}_{t}-\hat{M}_{t}\omega_{t}),~{}~{}\theta_{t+1}=\theta_{t}-\alpha\hat{A}_{t}^{\top}\omega_{t},$

we can rewrite $z_{t}$ (46) as the following recursion:

$\displaystyle z_{t+1}=z_{t}+\alpha(\tilde{G}_{t}z_{t}+\tilde{g}_{t}),$ (48)

where

$\displaystyle\tilde{G}_{t}=\begin{pmatrix}\hat{H}_{t},&-\hat{A}^{\top}_{t}\\\
-M^{-1}A\hat{H}_{t}+\dfrac{\beta}{\alpha}\hat{L}_{t}&M^{-1}A\hat{A}^{\top}_{t}-\dfrac{\beta}{\alpha}\hat{M}_{t}\end{pmatrix},\tilde{g}_{t}=\begin{pmatrix}0\\\
\dfrac{\beta}{\alpha}\hat{b}_{t}\end{pmatrix}.$ (49)

Let $\tilde{G}_{\infty}=:\lim_{t\rightarrow\infty}\tilde{G}_{t}$ and
$\tilde{g}_{\infty}=:\lim_{t\rightarrow\infty}\tilde{g}_{t}$. Furthermore, we
define

$\displaystyle{G}_{\infty}=\lim_{t\rightarrow\infty}\mathbb{E}[\tilde{G}_{t}]=\begin{pmatrix}{H},&{A}^{\top}\\\
-M^{-1}AH+\dfrac{\beta}{\alpha}L&M^{-1}A{A}^{\top}-\dfrac{\beta}{\alpha}M\end{pmatrix},{g}_{\infty}=\begin{pmatrix}0\\\
-\dfrac{\beta}{\alpha}b\end{pmatrix}.$

Boundedness of $\tilde{G}_{t}$, $\tilde{G}_{\infty}$, $\tilde{g}_{t}$,
$\tilde{g}_{\infty}$.

$\displaystyle\|\tilde{G}_{t}\|_{op}\leq\|\hat{H}_{t}\|_{op}+\|\hat{A}_{t}\|_{op}+\|M^{-1}A\hat{H}_{t}\|_{op}+\Big{\|}\dfrac{\beta}{\alpha}\hat{L}_{t}\Big{\|}_{op}+\|M^{-1}A\hat{A}_{t}\|_{op}+\Big{\|}\dfrac{\beta}{\alpha}\hat{M}_{t}\Big{\|}_{op}.$

Recall the boundedness of $\hat{H}_{t},\hat{A}_{t},M^{-1},A,\hat{L}_{t}$ and
$\hat{M}_{t}$, then the following holds

$\displaystyle\|\tilde{G}_{t}\|_{op}$
$\displaystyle\leq\underbrace{2C^{2}_{A}C_{M^{-1}}+C_{A}+C^{3}_{A}C^{2}_{M^{-1}}}_{=:C_{1}}+\dfrac{\beta}{\alpha}\Big{(}\underbrace{C_{A}+C_{M}C_{M^{-1}}C_{A}+C_{M}}_{=:C_{2}}\Big{)}=C_{1}+\dfrac{\beta}{\alpha}C_{2}=:\zeta.$
(50)

Furthermore, we have

$\|\tilde{G}_{\infty}\|_{op}\leq\zeta,\|\tilde{g}_{t}\|_{2}\leq\dfrac{\beta}{\alpha}c_{b}=C_{2}\dfrac{\beta}{\alpha}\dfrac{c_{b}}{C_{2}}\leq\dfrac{c_{b}}{C_{2}}\zeta=:\widetilde{c_{b}}\zeta,~{}~{}\|\tilde{b}_{\infty}\|_{2}=0.$

Recall (48), we have

$\displaystyle\|z_{t+1}-z_{t}\|_{2}\leq\alpha\|\tilde{G}_{t}z_{t}+\tilde{g}_{t}\|_{2}\leq\alpha\zeta(\|z_{t}\|_{2}+\widetilde{c_{b}}).$
(51)

Furthermore, according to the same analysis of Lemma 3 in (Srikant and Ying
2019), we have

$\displaystyle\|z_{\tau}-z_{0}\|_{2}$ $\displaystyle\leq
2\alpha\zeta\tau\|z_{0}\|_{2}+2\alpha\zeta\tau\widetilde{c_{b}},$
$\displaystyle\|z_{\tau}-z_{0}\|_{2}$ $\displaystyle\leq
4\alpha\zeta\tau\|z_{\tau}\|_{2}+4\alpha\zeta\tau\widetilde{c_{b}},$
$\displaystyle\|z_{\tau}-z_{0}\|^{2}_{2}$ $\displaystyle\leq
32\alpha^{2}\zeta^{2}\tau^{2}\|z_{\tau}\|^{2}_{2}+32\alpha^{2}\zeta^{2}\tau^{2}\widetilde{c_{b}}^{2}.$

Recall (51), we have

$\displaystyle\big{|}(z_{t+1}-z_{t})^{\top}P(z_{t+1}-z_{t})\big{|}\leq\lambda_{\max}(Q)\|z_{t+1}-z_{t}\|^{2}_{2}\leq\lambda_{\max}(Q)(\alpha\zeta(\|z_{t}\|_{2}+\widetilde{c_{b}}))^{2}\leq
2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)(\|z_{t}\|_{2}^{2}+\widetilde{c_{b}}^{2}),$

where the last inequality holds since $(a+b)^{2}\leq 2(a^{2}+b^{2})$. Let

$X_{t}=:\\{S_{0},A_{0},S_{1},A_{1},\cdots,S_{t},A_{t}\\},$

after some careful calculations, we have: for all $t\geq\tau$,

$\displaystyle\Big{|}\mathbb{E}\Big{[}z_{t}^{\top}\Big{(}P{G}_{\infty}z_{t}-\dfrac{1}{\alpha}(z_{t+1}-z_{t})\Big{)}\Big{|}z_{t-\tau},X_{t-\tau}\Big{]}\Big{|}$
$\displaystyle=$
$\displaystyle\Big{|}\mathbb{E}\Big{[}z_{t}^{\top}\Big{(}P{G}_{\infty}z_{t}-\tilde{G}_{t}z_{t}\Big{)}\Big{|}z_{t-\tau},X_{t-\tau}\Big{]}\Big{|}\leq\zeta(1+\lambda_{\max}(Q))\mathbb{E}[\|z_{t}\|^{2}_{2}|z_{t-\tau},X_{t-\tau}]$
(52)

For $t\geq\tau$, we have

$\displaystyle\mathbb{E}[L(z_{t+1})-L(z_{t})|z_{t-\tau},X_{t-\tau}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[z_{t+1}^{\top}Pz_{t+1}-z_{t}^{\top}Pz_{t}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[(z_{t+1}-z_{t})^{\top}P(z_{t+1}-z_{t})+2z_{t}^{\top}P(z_{t+1}-z_{t})|z_{t-\tau},X_{t-\tau}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\underbrace{(z_{t+1}-z_{t})^{\top}P(z_{t+1}-z_{t})}_{\leq
2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)(\|z_{t}\|_{2}^{2}+\widetilde{c_{b}}^{2})}+2z_{t}^{\top}P(z_{t+1}-z_{t}-\alpha
G_{\infty}z_{t})+2\alpha z_{t}^{\top}PG_{\infty}z_{t}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}[2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)(\|z_{t}\|_{2}^{2}+\widetilde{c_{b}}^{2})+2z_{t}^{\top}P(z_{t+1}-z_{t}-\alpha
G_{\infty}z_{t})+2\alpha z_{t}^{\top}PG_{\infty}z_{t}|z_{t-\tau},X_{t-\tau}].$
(53)

Furthermore, since
$\mathbb{E}[z_{t}^{\top}PG_{\infty}z_{t}|z_{t-\tau},X_{t-\tau}]\leq-\lambda_{\min}(\Sigma)\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}],$
where $\lambda_{\min}(\Sigma)$ is the smallest eigenvalue of the the following
matrix $\Sigma$:

$\Sigma=\begin{pmatrix}\dfrac{\xi_{2}}{\xi_{1}+\xi_{2}}&-\dfrac{\xi_{1}\xi_{2}}{\xi_{1}+\xi_{2}}\\\
-\dfrac{\xi_{1}\xi_{2}}{\xi_{1}+\xi_{2}}&\dfrac{\xi_{1}\Big{(}\frac{\beta}{\alpha}-2\|Q_{2}A^{\top}M^{-1}A\|_{op}\Big{)}}{\xi_{1}+\xi_{2}}\end{pmatrix},$

and $\xi_{1}=2\|Q_{1}A^{\top}\|_{op}$, and $\xi_{2}=2\|Q_{2}M^{-1}AL\|_{op}$.
Recall the result of Lemma 3, we have

$\displaystyle\lambda_{\min}(\Sigma)\geq\dfrac{\xi_{2}}{\xi_{1}+\xi_{2}}-\dfrac{\alpha}{\beta}\varkappa_{1}=:\varkappa_{1}-\dfrac{\alpha}{\beta}\varkappa_{2},$
(54)

where
$\varkappa_{1}=\dfrac{\xi_{2}}{\xi_{1}+\xi_{2}}=\dfrac{\|Q_{1}A^{\top}\|_{op}}{\|Q_{2}M^{-1}AL\|_{op}+\|Q_{1}A^{\top}\|_{op}}$,
$\varkappa_{2}$ is a constant depends on $\xi_{1},\xi_{2}$ and
$\dfrac{\alpha}{\beta}$.

From the result of (52) and (53), we have

$\displaystyle\mathbb{E}[L(z_{t+1})-L(z_{t})|z_{t-\tau},X_{t-\tau}]$
$\displaystyle\leq$ $\displaystyle
2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}+2\alpha\mathbb{E}[z_{t}^{\top}PG_{\infty}z_{t}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle+2\underbrace{\mathbb{E}[z_{t}^{\top}P(z_{t+1}-z_{t}-\alpha
G_{\infty}z_{t})|z_{t-\tau},X_{t-\tau}]}_{=2\alpha\mathbb{E}\big{[}z_{t}^{\top}P\big{(}\dfrac{z_{t+1}-z_{t}}{\alpha}-G_{\infty}z_{t}\big{)}\big{|}z_{t-\tau},X_{t-\tau}\big{]}}$
$\displaystyle\overset{(\ref{app-d-bound-01})}{\leq}$ $\displaystyle
2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}+2\alpha\mathbb{E}[z_{t}^{\top}PG_{\infty}z_{t}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle+2\alpha\zeta(1+\lambda_{\max}(Q))\mathbb{E}[\|z_{t}\|^{2}_{2}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle\overset{(\ref{app-d-02})}{\leq}$ $\displaystyle
2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}-2\alpha\lambda_{\min}(\Sigma)\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle+2\alpha\zeta(1+\lambda_{\max}(Q))\mathbb{E}[\|z_{t}\|^{2}_{2}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle\leq$ $\displaystyle
2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}-2\alpha\Big{(}\varkappa_{1}-\dfrac{\alpha}{\beta}\varkappa_{2}\Big{)}\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle+2\alpha\zeta(1+\lambda_{\max}(Q))\mathbb{E}[\|z_{t}\|^{2}_{2}|z_{t-\tau},X_{t-\tau}]$
$\displaystyle=$
$\displaystyle\Big{(}-2\alpha\big{(}\varkappa_{1}-\dfrac{\alpha}{\beta}\varkappa_{2}\big{)}+2\alpha\zeta(1+\lambda_{\max}(Q))+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\Big{)}\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}$
$\displaystyle\leq$
$\displaystyle\Big{(}-\alpha\big{(}\varkappa_{1}-\dfrac{\alpha}{\beta}\varkappa_{2}\big{)}\Big{)}\mathbb{E}[\|z_{t}\|_{2}^{2}|z_{t-\tau},X_{t-\tau}]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}$
(55)

where the last (55) holds since we need an additional condition as follows,

$\Big{(}-\alpha\big{(}\varkappa_{1}-\dfrac{\alpha}{\beta}\varkappa_{2}\big{)}+\alpha\zeta(1+\lambda_{\max}(Q))+\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\Big{)}\leq
0.$

∎

### D.3: Proof of Theorem 3

###### Proof.

Lemma 1 implies

$\displaystyle\mathbb{E}[L(z_{t+1})]-\mathbb{E}[L(z_{t})]$
$\displaystyle\leq-\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\mathbb{E}[\|z_{t}\|_{2}^{2}]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}$
$\displaystyle\leq-\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\dfrac{1}{\lambda_{\max}(Q)}\mathbb{E}[L(z_{t})]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}.$

Rewrite above equation, we have

$\mathbb{E}[L(z_{t+1})]\leq\bigg{(}1-\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\dfrac{1}{\lambda_{\max}(Q)}\bigg{)}\mathbb{E}[L(z_{t})]+2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2},$

i.e., we have

$\mathbb{E}[L(z_{t+1})]-\dfrac{2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}}{\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\dfrac{1}{\lambda_{\max}(Q)}}\leq\bigg{(}1-\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\dfrac{1}{\lambda_{\max}(Q)}\bigg{)}\Bigg{(}\mathbb{E}[L(z_{t})]-\dfrac{2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}}{\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\dfrac{1}{\lambda_{\max}(Q)}}\Bigg{)}.$

Rewrite above equation, we have

$\mathbb{E}[L(z_{t+1})]-\dfrac{2\alpha^{2}\zeta^{2}\lambda^{2}_{\max}(P)\widetilde{c_{b}}^{2}}{\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}}\leq\bigg{(}1-\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\dfrac{1}{\lambda_{\max}(Q)}\bigg{)}\Bigg{(}\mathbb{E}[L(z_{t})]-\dfrac{2\alpha^{2}\zeta^{2}\lambda^{2}_{\max}(P)\widetilde{c_{b}}^{2}}{\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}}\Bigg{)}.$

To simplify notations, we introduce

$u=1-\alpha\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\dfrac{1}{\lambda_{\max}(Q)},v={2\alpha^{2}\zeta^{2}\lambda_{\max}(Q)\widetilde{c_{b}}^{2}}.$

Furthermore, applying above equation recursively, we have

$\mathbb{E}[L(z_{t})]\leq
u^{t-\tau}\mathbb{E}[L(z_{\tau})]+v\dfrac{1-u^{t-\tau}}{1-u}\leq
u^{t-\tau}\mathbb{E}[L(z_{\tau})]+\dfrac{v}{1-u}.$

Then, the following equation holds

$\displaystyle\mathbb{E}[\|z_{t}\|_{2}^{2}]\leq\dfrac{1}{\lambda_{\min}(P)}\mathbb{E}[L(z_{t})]\leq\dfrac{1}{\lambda_{\min}(P)}\Big{(}u^{t-\tau}\mathbb{E}[L(z_{\tau})]+\dfrac{v}{1-u}\Big{)}.$
(56)

Additionally,

$\displaystyle\mathbb{E}[L(z_{\tau})]\leq\lambda_{\max}(Q)\mathbb{E}[\|z_{\tau}\|_{2}^{2}]$
$\displaystyle\leq\lambda_{\max}(Q)(\mathbb{E}[\|z_{\tau}-z_{0}\|_{2}^{2}]+\|z_{0}\|_{2}^{2})$
$\displaystyle\leq\lambda_{\max}(Q)((2\alpha\zeta\tau\|z_{0}\|_{2}+2\alpha\zeta\tau\widetilde{c_{b}})^{2}+\|z_{0}\|_{2}^{2})$
$\displaystyle=\lambda_{\max}(Q)(4\alpha^{2}\zeta^{2}\tau^{2}(\|z_{0}\|_{2}+\widetilde{c_{b}})^{2}+\|z_{0}\|_{2}^{2}).$

Taking it to (56), we have

$\displaystyle\mathbb{E}[\|z_{t}\|_{2}^{2}]$
$\displaystyle\leq\dfrac{\lambda_{\max}(Q)}{\lambda_{\min}(P)}u^{t-\tau}(4\alpha^{2}\zeta^{2}\tau^{2}(\|z_{0}\|_{2}+\widetilde{c_{b}})^{2}+\|z_{0}\|_{2}^{2})+\dfrac{1}{\lambda_{\min}(P)}\dfrac{v}{1-u}$
(57)
$\displaystyle=\alpha^{2}\zeta^{2}u^{t-\tau}\underbrace{\kappa(P)(4\zeta^{2}\tau^{2}(\|z_{0}\|_{2}+\widetilde{c_{b}})^{2}+\|z_{0}\|_{2}^{2})}_{=:\eta_{1}}+\alpha\underbrace{\kappa(P)\dfrac{2\lambda_{\max}(Q)\widetilde{c_{b}}^{2}}{\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}}}_{=:\eta_{2}}$
$\displaystyle=\alpha^{2}\eta_{1}\bigg{(}1-\dfrac{\alpha}{\lambda_{\max}(Q)}\Big{(}\frac{1}{2}\varkappa_{1}-\frac{\alpha}{\beta}\varkappa_{2}\Big{)}\bigg{)}^{t-\tau}+\alpha\eta_{2}.$

∎

##  Appendix E Appendix E: Performance over Primal-Dual Gap Error

According to Nemirovski et al., (2009), we can measure the convergence of
problem (19) by _primal-dual gap error_.

######  Definition 2 (Primal-Dual Gap Error).

Recall $\Psi$ defined in (18), the primal-dual gap error
$\epsilon_{\Psi}(\theta,\omega)$ at each solution $(\omega,\theta)$ is defined
as:

$\epsilon_{\Psi}(\theta,\omega)=\max_{\omega^{{}^{\prime}}}\Psi(\theta,\omega^{{}^{\prime}})-\min_{\theta^{{}^{\prime}}}\Psi(\theta^{{}^{\prime}},\omega).$

######  Theorem 4 (Convergence of Algorithm 1).

Under Assumption 1-2. Consider the sequence
$\\{(\theta_{t},\omega_{t})\\}_{t=1}^{T}$ generated Algorithm 1. Let $C$ be a
constant defined in (61), step-size
$\alpha_{t}=\beta_{t}=\dfrac{2}{C\sqrt{5t}}$ and
$\tilde{\theta}_{T}=\dfrac{\sum_{t=1}^{T}\alpha_{t}\theta_{t}}{\sum_{t=1}^{T}\alpha_{t}}$,
$\tilde{\omega}_{T}=\dfrac{\sum_{t=1}^{T}\alpha_{t}\omega_{t}}{\sum_{t=1}^{T}\alpha_{t}}$.
Then primal-dual gap error
$\epsilon_{\Psi}(\tilde{\theta}_{T},\tilde{\omega}_{T})$ is upper-bounded by

$\displaystyle\mathbb{E}[\epsilon_{\Psi}(\tilde{\theta}_{T},\tilde{\omega}_{T})]\leq
C{\sqrt{\dfrac{5}{T}}}.$ (58)

Furthermore, for any $\delta\in(0,\frac{2}{e})$, the following holds with
probability at least $1-\delta$,

$\displaystyle\epsilon_{\Psi}(\tilde{\theta}_{T},\tilde{\omega}_{T})\leq
C{\sqrt{\dfrac{5}{T}}\Big{(}8+2\log\dfrac{2}{\delta}\Big{)}}.$ (59)

###### Proof.

The proof of Theorem 4 relies on some results in the section 3.1 of
(Nemirovski et al. 2009), we refer the reader to that reference for further
technical details. Let $\widehat{G}(\theta,\omega)$ be the stochastic gradient
vector of $\Psi(\theta,\omega)$:

$\widehat{G}(\theta,\omega)=\begin{pmatrix}\hat{g}_{\theta}(\theta,\omega)\\\
\hat{g}_{\omega}(\theta,\omega)\end{pmatrix}=\begin{pmatrix}\hat{A}_{t}\omega\\\
\hat{A}_{t}\theta+\hat{b}_{t}-\hat{M}_{t}\omega\end{pmatrix}.$

According to Nemirovski et al., (2009), we need to check: I)
$\widehat{G}(\theta,\omega)$ is an unbiased estimate of the gradient of
$\Psi({\theta,\omega})$; II) $\mathbb{E}[\|\widehat{G}(\theta,\omega)\|]$ is
uniformly bounded on the region $D_{\theta}\times D_{\omega}$.

From (22), $\hat{g}_{\theta}(\theta,\omega)$ and
$\hat{g}_{\omega}(\theta,\omega)$ are the unbiased estimates of
$\partial_{\theta}\Psi({\theta,\omega})$ and
$\partial_{\omega}\Psi({\theta,\omega})$ correspondingly:

$\displaystyle\mathbb{E}[\widehat{G}(\theta,\omega)]=\begin{pmatrix}\mathbb{E}[\hat{g}_{\theta}(\theta,\omega)]\\\
\mathbb{E}[\hat{g}_{\omega}(\theta,\omega)]\end{pmatrix}=\begin{pmatrix}\partial_{\theta}\Psi({\theta,\omega})\\\
\partial_{\omega}\Psi({\theta,\omega})\end{pmatrix}.$ (60)

Furthermore, we should check for each $(\theta_{k},\omega_{k})$, the terms
$\mathbb{E}[\hat{g}_{\theta}(\theta_{k},\omega_{k})]$ and
$\mathbb{E}[\hat{g}_{\omega}(\theta_{k},\omega_{k})]$ are uniformly bounded:

$\displaystyle\mathbb{E}[\|\hat{g}_{\omega}(\theta_{k},\omega_{k})\|_{2}^{2}]$
$\displaystyle=\mathbb{E}[\|\hat{A}_{t}{\theta}_{t}+\hat{b}_{t}-\hat{M}_{t}\omega_{t}\|_{2}^{2}]\leq
C^{2}_{b}+C^{2}_{A}\text{diam}^{2}(D_{\theta})+C^{2}_{M}\text{diam}^{2}(D_{\omega})\overset{\text{def}}{=}\widetilde{C}^{2}_{1},$
$\displaystyle\mathbb{E}[\|\hat{g}_{\theta}(\theta_{k},\omega_{k})\|_{2}^{2}]$
$\displaystyle=\mathbb{E}[\|\hat{A}_{t}\omega\|_{2}^{2}]\leq
C^{2}_{A}\text{diam}^{2}(D_{\omega})\overset{\text{def}}{=}\widetilde{C}^{2}_{2},$

where “diam” is short for diameter. Let $C$ be a constant:

$\displaystyle
C=4\text{diam}^{2}(D_{\omega})\widetilde{C}^{2}_{1}+\text{diam}^{2}(D_{\theta})\widetilde{C}^{2}_{2}.$
(61)

Then, according to Eq.(3.15) in (Nemirovski et al. 2009), the result (58)
holds. Furthermore, by the Proposition 3.2 of (Nemirovski et al. 2009), for
any $\eta>1$:

$\mathbb{P}\Big{[}\epsilon_{\Psi}(\tilde{\theta}_{T},\tilde{\omega}_{T})>C\dfrac{8+2\eta}{\sqrt{T}}\Big{]}\leq
2e^{-\eta},$

which implies for any $\delta\in(0,\frac{2}{e})$, the result (59) holds with
probability at least $1-\delta$. ∎

######  Discussion 1 (Comparison with Existing Works over Primal-Dual Gap
Error).

Liu et al. (2015) firstly derive $\mathtt{GTD}$ via convex-concave saddle-
point formulation, and their optimal convergence rate reaches
$\mathbb{E}[\epsilon_{\Psi}(\tilde{\theta}_{T},\tilde{\omega}_{T})]=\mathcal{O}({1}/{\sqrt{T}})$.
Later, Wang et al.(2017) extends the work of Liu et al.(2015), they suppose
the data is generated from Markov processes rather than I.I.D assumption. Wang
et al.(2017) prove the convergence rate
$\mathbb{E}[\epsilon_{\Psi}(\tilde{\theta}_{T},\tilde{\omega}_{T})]=\mathcal{O}\bigg{(}\dfrac{\sum_{t=1}^{T}\alpha^{2}_{t}}{\sum_{t=1}^{T}\alpha_{t}}\bigg{)}$,
the optimal convergence rate also reaches $\mathcal{O}({1}/{\sqrt{T}})$, where
they require step-size satisfies $\sum_{t=1}^{\infty}\alpha_{t}=\infty$,
$\dfrac{\sum_{t=1}^{T}\alpha^{2}_{t}}{\sum_{t=1}^{T}\alpha_{t}}\leq\infty$.
Our work, i.e., Theorem 4 matches the best-known theoretical results Wang et
al.(2017), while we point out a simpler and concrete step-size.

##  Appendix F Appendix F: Additional Details of Experiments

For the limitation of space, in this section, we present all the details of
experiments.

MountainCar Since the state space of mountaincar domain is continuous, we use
the open tile coding software
http://incompleteideas.net/rlai.cs.ualberta.ca/RLAI/RLtoolkit/tilecoding.html
to extract feature of states.

In this experiment, we set the number of tilings to be 4 and there are no
white noise features. The performance is an average 5 runs and each run
contains 5000 episodes. We set $\lambda=0.99$, $\gamma=0.99$. The MSPBE/MSE
distribution is computed over the combination of step-size,
$(\alpha_{t},\frac{\beta_{t}}{\alpha_{t}})\in[0.1\times
2^{j}|j=-10,-9,\cdots,-1,0]^{2}$, and $\lambda=0.99$. Following suggestions
from Section10.1 in (Sutton and Barto 2018), we set all the initial state-
action values to be 0, which is optimistic to cause extensive exploration.

Baird Example The Baird example considers the episodic seven-state, two-action
MDP. The $\mathtt{dashed}$ action takes the system to one of the six upper
states with equal probability, whereas the $\mathtt{solid}$ action takes the
system to the seventh state. The behavior policy $b$ selects the
$\mathtt{dashed}$ and $\mathtt{solid}$ actions with probabilities
$\frac{6}{7}$ and $\frac{1}{7}$, so that the next-state distribution under it
is uniform (the same for all nonterminal states), which is also the starting
distribution for each episode. The target policy $\pi$ always takes the solid
action, and so the on-policy distribution (for $\pi$) is concentrated in the
seventh state. The reward is zero on all transitions. The discount rate is
$\gamma=0.99$. The feature $\phi(\cdot,{\mathtt{dashed}})$ and
$\phi(\cdot,{\mathtt{solid}})$ are defined as follows,

$\displaystyle\phi(\mathtt{s_{1}},{\mathtt{dashed}})$
$\displaystyle=(2,0,0,0,0,0,0,1,0,0,0,0,,0,,0,0,0,0)$
$\displaystyle\phi(\mathtt{s_{2}},{\mathtt{dashed}})$
$\displaystyle=(0,2,0,0,0,0,0,1,0,0,0,0,,0,,0,0,0,0)$ $\displaystyle\cdots$
$\displaystyle\phi(\mathtt{s_{7}},{\mathtt{dashed}})$
$\displaystyle=(0,0,0,0,0,0,2,1,0,0,0,0,,0,,0,0,0,0),$ (62)
$\displaystyle\phi(\mathtt{s_{1}},{\mathtt{solid}})$
$\displaystyle=(0,0,0,0,0,0,0,0,2,0,0,0,,0,,0,0,0,1)$
$\displaystyle\phi(\mathtt{s_{2}},{\mathtt{solid}})$
$\displaystyle=(0,0,0,0,0,0,0,0,0,2,0,0,,0,,0,0,0,1)$ $\displaystyle\cdots$
$\displaystyle\phi(\mathtt{s_{7}},{\mathtt{solid}})$
$\displaystyle=(0,0,0,0,0,0,0,0,0,0,0,0,,0,,0,0,2,1).$ (63)