# A Unified Off-Policy Evaluation Approach for General Value Function

Tengyu Xu
The Ohio State University
<EMAIL_ADDRESS>
&Zhuoran Yang
Princeton University
<EMAIL_ADDRESS>
Zhaoran Wang
Northwestern University
<EMAIL_ADDRESS>
&Yingbin Liang
The Ohio State University
<EMAIL_ADDRESS>

###### Abstract

General Value Function (GVF) is a powerful tool to represent both the
predictive and retrospective knowledge in reinforcement learning (RL). In
practice, often multiple interrelated GVFs need to be evaluated jointly with
pre-collected off-policy samples. In the literature, the gradient temporal
difference (GTD) learning method has been adopted to evaluate GVFs in the off-
policy setting, but such an approach may suffer from a large estimation error
even if the function approximation class is sufficiently expressive. Moreover,
none of the previous work have formally established the convergence guarantee
to the ground truth GVFs under the function approximation settings. In this
paper, we address both issues through the lens of a class of GVFs with causal
filtering, which cover a wide range of RL applications such as reward
variance, value gradient, cost in anomaly detection, stationary distribution
gradient, etc. We propose a new algorithm called GenTD for off-policy GVFs
evaluation and show that GenTD learns multiple interrelated multi-dimensional
GVFs as efficiently as a single canonical scalar value function. We further
show that unlike GTD, the learned GVFs by GenTD are guaranteed to converge to
the ground truth GVFs as long as the function approximation power is
sufficiently large. To our best knowledge, GenTD is the first off-policy GVF
evaluation algorithm that has global optimality guarantee.

##  1 Introduction

The value function, which represents the expected accumulation of reward [39],
serves as a reliable performance metric of policy in the reinforcement
learning (RL) tasks [38, 22], In many RL applications, however, looking at
only the value function is not enough. For example, in the risk-sensitive
domains such as health care and financial assets, the variance of "reward-to-
go" rather than the value function, i.e., the mean of "reward-to-go", is a
more suitable performance metric. As another example, to obtain a variance-
reduced or bias-reduced policy gradient estimator [14, 56, 18], in addition to
the value function, the information of "gradient of value function" is also
required. Moreover, in continuous control domain with differentiable and
deterministic policy, the computation of policy gradient is only possible
through "action/state-value gradient" [34, 8, 12], etc. All the aforementioned
metrics can be viewed as predicative knowledge of certain cumulative "signals"
(possibly high-dimensional, e.g., the gradient of value function), and thus
naturally fall into the framework of forward GVFs (refers to forward general
value functions) [44, 52, 29]. One typical approach to evaluate GVFs, is to
learn from samples that pre-collected from one or more behavior policies,
which yields an off-policy method. In practice, multiple forward GVFs are
usually evaluated jointly at the same time due to their interrelationships
[44, 33].

In contrast to forward GVFs defined based on predictive knowledge, the
backward GVF represents retrospective knowledge, which captures the
accumulation of signals from the past to the present time [65]. Although the
concept of the backward GVF has not been formally proposed until very recently
[65], it is rooted in a number of important RL applications such as anomaly
detection [65], emphatic weight learning [42, 65] and evaluation of gradient
of logarithmic stationary distribution [25, 56, 18]. Differently from the
forward GVF, for which the Bellman operator can be defined independently from
the sampling distribution [33, 38, 40], the Bellman operator of the backward
GVF is only valid if the sampling exactly follows the on-policy stationary
distribution [65]. Due to such a reason, off-policy evaluation of the backward
GVF is much more challenging than that of the forward GVF.

In previous studies, the gradient temporal difference (GTD) learning [41, 22],
one of the most popular off-policy methods in value function evaluation, has
been adopted to solve both the forward and backward GVF evaluation problems
[44, 33, 64]. GTD adopts the mean squared projected Bellman error (MSPBE) as
its optimization objective and takes the expectation over the behavior policy,
which does not exactly reflect the desirable evaluation under the target
policy. As a result, GTD can encounter serious issues in GVF evaluation
problems. First, the optimal point to which GTD converges can be far away from
the ground truth value of GVFs. It becomes worse when multiple GVFs are
evaluated simultaneously, because the error of one GVF evaluation can be
further amplified across other GVFs’ evaluation due to their inherent
correlations. In the literature, no provable bound has been established on
such an error, which can, in fact, be unbounded for some cases (see [19,
Example 1]). Second, for high-dimensional GVFs evaluations, the landscape
geometry of the GTD objective function can be ill-conditioned [22], which
could slow down the convergence of GTD significantly. As demonstrated by our
empirical results in Section 5, GTD can suffer from both the large estimation
error and the slow convergence rate, which further suggests that GTD may not
be a good choice for GVFs evaluation tasks. This motivates our paper to
address the following question:

  * $\bullet$

Can we design a new off-policy approach for multiple interrelated and high-
dimensional GVFs evaluation problems, which is guaranteed to converge fast and
converge to the ground truth GVFs?

Our Contributions. In this paper, we investigate the problem of evaluating
multiple interrelated GVFs jointly. Rather than studying different GVFs on a
case-by-case basis, we explore the class of "GVFs with causal filtering",
which captures a common structural feature shared by GVFs in a wide range of
RL applications (see Appendix B). (a) We prove that both forward and backward
GVFs with causal filtering are the unique fixed point of their corresponding
general Bellman operator (GBO) (defined for multiple high-dimensional GVFs),
which is shown to have a contraction property with respect to a properly
constructed norm metric. (b) Based on such a property of GVFs, we propose a
new algorithm GenTD to solve off-policy GVFs evaluation problem. GenTD
introduces a density ratio to adjust the behavior distribution and further
incorporates a policy-agnostic approach GenDICE/GradientDICE [60, 65] for
estimating the density ratio jointly with GVF evaluation. (c) In the linear
function approximation setting, we show that GenTD converges to the globally
optimal point at the rate of $\mathcal{O}(1/T)$, with conditional number
independent from the dimension of GVFs. Such a result implies that GenTD
learns multiple interrelated possibly high-dimensional GVFs as efficiently as
TD learning for a single canonical scalar value function. (d) We further show
that unlike GTD, GenTD are guaranteed to converge to the ground truth GVFs as
long as the function expressive power is sufficiently large. To our best
knowledge, GenTD is the first off-policy GVF evaluation algorithm that has
gound truth guarantee. (e) Our experiments further demonstrate that GenTD
converges much faster than GTD, and more importantly, converges to ground
truth, whereas GTD can stay far way from the ground truth GVF value.

Related Work. The forward GVF was first introduced in [44] to represent a set
of accumulation of general signals with possibly time-varying discount
factors. The forward GVF was later used to represent a set of interrelated
predictions [33, 9, 37, 23]. It has been observed that some RL metrics such as
variance, gradient of value function, state/action value gradient can also be
viewed as forward GVFs [47, 14, 56, 18, 34, 44, 52, 29, 8, 5]. In previous
works, both TD learning and GTD have been used to evaluate forward GVFs in the
on- and off-policy settings [44, 33], respectively. A more comprehensive
review of studies of forward GVFs has been provided in [31]. The backward GVF
was formally defined in [65]. Some previous works have also considered metrics
that can be represented as accumulations of signals in the reverse time
direction, such as emphatic weighting, page ranking cost, and derivative of
logarithmic stationary distribution [61, 63, 25, 58, 10]. Another track of
research has focused on evaluation of a general scalar function in the off-
policy setting [4, 59, 16], whereas the focus of this paper is on the
evaluation of multiple high-dimensional GVFs.

The theoretical studies of off-policy GVFs evaluation algorithms are rather
limited. So far, only the asymptotic convergence guarantee (without the
convergence rate characterization) of GTD has been established in both the
forward and backward GVFs evaluation settings [33, 65]. The convergence rate
of GTD has only been established in [57, 7, 17, 6, 53, 21] for the simple
canonical value function evaluation setting, which is a special case of
forward GVFs. However, as pointed out in [19, 10, 26], the optimal point of
GTD may suffer from possibly unbounded approximation error, which is not
desirable in practice. In contrast, we propose a new off-policy GVFs
evaluation algorithm, which can solve a wide range of forward and backward
GVFs evaluation problems, with convergence rate characterization and
guaranteed optimality with respect to the ground truth GVF value.

##  2 Markov Decision Process and General Value Function

We consider an infinite-horizon Markov Decision Process (MDP) with a state
space $\mathcal{S}$, an action space $\mathcal{A}$, a reward function
$r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, a transition kernel
$\mathsf{P}:\mathcal{S}\times\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$, a
discounted factor $\gamma\in(0,1)$, and an initial distribution
$\mu_{0}:\mathcal{S}\rightarrow[0,1]$. An policy $\pi(a|s)$ is the probability
of taking action $a$ at state $s$. At time step $t$, an agent at a state
$s_{t}$ selects an action $a_{t}$ according to $\pi(\cdot|s_{t})$, receives a
reward $r(s_{t},a_{t})$, and transits to state $s_{t+1}$ according to
$\mathsf{P}(\cdot|s_{t},a_{t})$. The state-action transition kernel is defined
as
$\mathsf{P}_{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$,
in which
$\mathsf{P}_{\pi}((s,a),(s^{\prime},a^{\prime}))=\mathsf{P}(s^{\prime}|s,a)\pi(a^{\prime}|s^{\prime})$.
When the MDP is ergodic, we define $\mu_{\pi}$ as the state-action stationary
distribution which satisfies:
$\mu_{\pi}^{\top}\mathsf{P}_{\pi}=\mu_{\pi}^{\top}$. For such an MDP, we
define the discounted accumulation of reward as the "reward-to-go":
$J_{\pi}=\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})$. The state-action value
function (i.e., Q-function) is defined as
$Q_{\pi}(s,a)=\mathbb{E}[J_{\pi}|(s_{0},a_{0})=(s,a)]$, and the state value
function (i.e., V-function) is defined as
$V_{\pi}(s)=\mathbb{E}[Q_{\pi}(s,a)|s]$. Note that $Q_{\pi}(s,a)$ satisfies
the following Bellman equation

$\displaystyle
Q_{\pi}=\mathcal{T}_{\pi}Q_{\pi}=R+\gamma\mathsf{P}_{\pi}Q_{\pi},$ (1)

where $\mathcal{T}_{\pi}$ is the Bellman operator, and $Q_{\pi}$, and
$R\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ are vectors obtained via
stacking $Q_{\pi}(s,a)$ and $r(s,a)$ over state-action space
$\mathcal{S}\times\mathcal{A}$. We introduce a function of $(s,a)$ (possibly
in the vector form) as $v(s,a)\in\mathbb{R}^{d}$ ($d\geq 1$). Consider a
distribution $\xi(\cdot)$ over $\mathcal{S}\times\mathcal{A}$. We define the
$\xi$–norm of $v\in\mathbb{R}^{d|\mathcal{S}||\mathcal{A}|}$ as
$\left\|v\right\|_{\xi}=\sqrt{\sum_{(s,a)}\xi(s,a)\left\|v(s,a)\right\|_{2}^{2}}$,
where $v$ is obtained by stacking the function $v(s,a)$ over
$\mathcal{S}\times\mathcal{A}$. It has been proved that $\mathcal{T}_{\pi}$ is
$\gamma$–contraction in $\mu_{\pi}$–norm, i.e.,
$\left\|\mathcal{T}_{\pi}v-\mathcal{T}_{\pi}v^{\prime}\right\|_{\mu_{\pi}}\leq\gamma\left\|v-v^{\prime}\right\|_{\mu_{\pi}}$
and $Q_{\pi}$ is the unique fixed point of $\mathcal{T}_{\pi}$ [40, 38, 50].
In the sequel, we denote $\mathsf{I}_{d}$ as the identity matrix with the
dimension $d$ and $\otimes$ as the Kronecker product. We further define
$U_{\pi}=\text{diag}(U_{\pi,1},\cdots,U_{\pi,k})$, in which
$U_{\pi,i}=\text{diag}(\mu_{\pi})\otimes\mathsf{I}_{d_{i}}$ for
$i=\\{1,\cdots,k\\}$, and $P_{\pi}=\text{diag}(P_{\pi,1},\cdots,P_{\pi,k})$,
in which $P_{\pi,i}=\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{i}}$.

###  2.1 Forward General Value Function

Consider a set of the state-action general value functions (GVFs)
$G_{\pi}=[G_{\pi,1}^{\top},\cdots,G_{\pi,k}^{\top}]^{\top}$, where each GVF
$G_{\pi,i}$ is defined as the accumulation of a corresponding signal
$C_{i}(s,a)\in\mathbb{R}^{d_{i}}$ given by

$\displaystyle\textstyle
G_{\pi,i}(s,a)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma_{i}^{t}C_{i}(s_{t},a_{t})\big{|}(s_{0},a_{0})=(s,a),\pi\right],$
(2)

where $\gamma_{i}\in(0,1)$ is a discount factor associated with $C_{i}$. Since
$C_{i}(s,a)\in\mathbb{R}^{d_{i}}$ (for each $(s,a)$) can be high-dimensional,
$G_{\pi,i}(s,a)$ can also be high-dimensional for each $(s,a)$. Clearly, the
Q-function is a special GVF associated with a scalar signal. Since $G_{\pi}$
is defined as the accumulation of the signal $C_{i}$ in a forward direction
from the current time step $t$ to the future $\infty$, we call $G_{\pi}$ as
"forward GVF".

In many RL applications, GVFs share a commen structure of causal filtering
[44], i.e., each $C_{i}(s,a)$ (associated with $G_{\pi,i}$) depends on the
lower-indexed value functions $G_{\pi,1},\cdots,G_{\pi,i-1}$ in the set. As a
concrete example, suppose the policy is parametrized by a smooth function
$\pi_{w}$, where the parameter $w\in\mathbb{R}^{d_{w}}$. In addition to the
Q-function $Q_{\pi}$, the gradient $\nabla_{w}Q_{\pi}(s,a)$ of the Q-function
w.r.t. $w$ arises as a GVF of interest in several important applications such
as variance reduced policy gradient [14] and on- and off-policy policy
optimization [56, 34, 18, 5]. In such a case, let $G_{\pi,1}=Q_{\pi}$ and
$G_{\pi,2}=\nabla_{w}Q_{\pi}$. Further, it has been shown in [56, 18, 5] that
the signal $C_{2}(s,a)$ associated with $\nabla_{w}Q_{\pi}$ is given by
$C_{2}(s,a)=\gamma\mathbb{E}[Q_{\pi}(s^{\prime},a^{\prime})\nabla_{w}\log(\pi_{w}(s^{\prime},a^{\prime}))|s,a]$,
which depends on the lower-indexed $G_{\pi,1}=Q_{\pi}$. Hence, such a GVF
vector has the causal filtering structure. Appendix B provides further details
about this example and more such GVF examples in RL. More formally, we define
the forward GVF with causal filtering as follows.

######  Definition 1 (Forward GVF with causal filtering).

For a given policy $\pi$, a forward GVF
$G_{\pi}=[G_{\pi,1}^{\top},\cdots,G_{\pi,k}^{\top}]^{\top}$ with causal
filtering are associated with signals satisfying

$\displaystyle\textstyle
C_{i}=B_{i}+\sum_{j=1}^{i-1}A_{i,j}G_{\pi,j}\quad\text{for }\;2\leq i\leq k,$

where $C_{i}$ and $G_{\pi,j}$ are obtained by respectively stacking
$C_{i}(s,a)\in\mathbb{R}^{d_{i}}$ and $G_{\pi,j}(s,a)\in\mathbb{R}^{d_{i}}$
over $\mathcal{S}\times\mathcal{A}$,
$B_{i}\in\mathbb{R}^{d_{i}|\mathcal{S}||\mathcal{A}|}$ is an observable
signal, and the coefficient matrix
$A_{i,j}\in\mathbb{R}^{d_{i}|\mathcal{S}||\mathcal{A}|\times
d_{j}|\mathcal{S}||\mathcal{A}|}$ captures how the $j$-th GVF $G_{\pi,j}$
affects the $i$-th accumulation signal $C_{i}$. Further, $B_{i}$ and $A_{i,j}$
are bounded for all $i,j=1,\cdots,k$ to ensure $G_{\pi,i}$ to be well defined.

Definition 1 indicates that all GVFs are interrelated with a causal filtering
structure, i.e., each signal $C_{i}$ is a linear function of all lower-indexed
$G_{\pi,l}$ for $1\leq l<i$. Such a structure also captures the core nature of
the TD net [45], in which the prediction of one node may depend on the outputs
from some previous nodes. Definition 1 also implies that the forward GVF
$G_{\pi}=[G^{\top}_{\pi,1},\cdots,G^{\top}_{\pi,k}]^{\top}$ with causal
filtering satisfies the following lower-triangular Bellman equation given by

$\displaystyle G_{\pi}=\mathcal{T}_{G,\pi}G_{\pi}=B+M_{\pi}G_{\pi},$ (3)

where where $\mathcal{T}_{G,\pi}$ denotes the forward general Bellman operator
(GBO), and

$\displaystyle B=\left[\begin{array}[]{c}B_{1}\\\ B_{2}\\\ \vdots\\\
B_{k}\end{array}\right],\quad
M_{\pi}=\left[\begin{array}[]{cccc}\gamma_{1}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{1}}]&0&\cdots&0\\\
A_{2,1}&\gamma_{2}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{2}}]&\cdots&0\\\
\vdots&\vdots&&\vdots\\\
A_{k,1}&A_{k,2}&\cdots&\gamma_{k}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{k}}]\end{array}\right].$

Clearly, the canonical value function $Q_{\pi}$ and Bellman operator
$\mathcal{T}_{\pi}$ defined in eq. 1 is a special case of $G_{\pi}$ and
$\mathcal{T}_{G,\pi}$ defined in eq. 3.

###  2.2 Backward General Value Function

In contrast to the forward GVF defined in the last section, which represents
the predictive knowledge, in some RL scenarios, we also want to capture the
retrospective knowledge (see Appendix B for concrete examples), which
represents the accumulation of signals that have been collected from the past.
Consider a set of GVFs
$\hat{G}_{\pi}=[\hat{G}_{\pi,1}^{\top},\cdots,\hat{G}_{\pi,k}^{\top}]^{\top}$,
where each GVF $\hat{G}_{\pi,i}$ is defined as the backward accumulation of a
vector signal $\hat{C}_{i}(s,a)\in\mathbb{R}^{d_{i}}$ given by

$\displaystyle\textstyle\hat{G}_{\pi,i}(s,a)=\mathbb{E}\big{[}\sum_{t=-\infty}^{0}\gamma_{i}^{-t}\hat{C}_{i}(s_{t},a_{t})\big{|}(s_{0},a_{0})=(s,a),\pi\big{]}.$
(4)

To distinguish from the forward GVF $G_{\pi,i}$ defined in eq. 2, we denote
$\hat{G}_{\pi,i}$ as the backward GVF. For general purpose, we also consider
the causal filtering setting for $\hat{G}_{\pi}$, in which each
$\hat{C}_{i}(s,a)$ depends on the lower-indexed value functions
$\hat{G}_{\pi,1},\cdots,\hat{G}_{\pi,i-1}$ in the set. We define the backward
GVF with causal filtering as follows.

######  Definition 2 (Backward GVF with causal filtering).

For a given policy $\pi$, a backward GVF
$\hat{G}_{\pi}=[\hat{G}_{\pi,1},\cdots,\hat{G}_{\pi,k}]$ with causal filtering
are associated with signals satisfying

$\displaystyle\textstyle\hat{C}_{i}={B}_{i}+\sum_{j=1}^{i-1}{A}_{i,j}\hat{G}_{\pi,j}\quad\text{for
}\;2\leq i\leq k,$

where $\hat{C}_{i}$ and $\hat{G}_{\pi,j}$ are obtained by respectively
stacking $\hat{C}_{i}(s,a)\in\mathbb{R}^{d_{i}}$ and
$\hat{G}_{\pi,j}(s,a)\in\mathbb{R}^{d_{i}}$ over
$\mathcal{S}\times\mathcal{A}$,
${B}_{i}\in\mathbb{R}^{d_{i}|\mathcal{S}||\mathcal{A}|}$ is an observable
signal, and the coefficient matrix
${A}_{i,j}\in\mathbb{R}^{d_{i}|\mathcal{S}||\mathcal{A}|\times
d_{j}|\mathcal{S}||\mathcal{A}|}$ captures how the $j$-th GVF
$\hat{G}_{\pi,j}$ affects the $i$-th accumulation signal $\hat{C}_{i}$.
Further, ${B}_{i}$ and ${A}_{i,j}$ are bounded for all $i,j=1,\cdots,k$ to
ensure $\hat{G}_{\pi,i}$ to be well defined.

For an ergodic MDP that starts from $-\infty$, we have
$(s_{t-1},a_{t-1})\sim\mu_{\pi}(\cdot)$,
$(s_{t},a_{t})\sim\mathsf{P}_{\pi}(\cdot|s_{t-1},a_{t-1})$, and
$(s_{t},a_{t})\sim\mu_{\pi}(\cdot)$ for all $-\infty<t<\infty$. The Bayes’
theorem implies that

$\displaystyle
P((s_{t-1},a_{t-1})|(s_{t},a_{t}))=\frac{\mu_{\pi}(s_{t-1},a_{t-1})\mathsf{P}_{\pi}((s_{t},a_{t})|(s_{t-1},a_{t-1}))}{\mu_{\pi}(s_{t},a_{t})}.$
(5)

The reverse conditional probability in eq. 5 together with the definition of
backward GVF in Definition 2 implies that the backward GVFs
$\hat{G}_{\pi}=[\hat{G}^{\top}_{\pi,1},\cdots,\hat{G}^{\top}_{\pi,k}]^{\top}$
with causal filtering satisfies

$\displaystyle\hat{G}_{\pi}=\hat{\mathcal{T}}_{G,\pi}\hat{G}_{\pi}={B}+\hat{M}_{\pi}\hat{G}_{\pi},$
(6)

where $\hat{\mathcal{T}}_{G,\pi}$ denotes the backward general Bellman
operator, and

$\displaystyle{B}=\left[\begin{array}[]{c}{B}_{1}\\\ {B}_{2}\\\ \vdots\\\
{B}_{k}\end{array}\right],\,\,\hat{M}_{\pi}=\left[\begin{array}[]{cccc}\gamma_{1}\hat{P}_{\pi,1}&0&\cdots&0\\\
{A}_{2,1}&\gamma_{2}\hat{P}_{\pi,2}&\cdots&0\\\ \vdots&\vdots&&\vdots\\\
{A}_{k,1}&{A}_{k,2}&\cdots&\gamma_{k}\hat{P}_{\pi,k}\end{array}\right],\,\text{where}\,\hat{P}_{\pi,i}=U^{-1}_{\pi,i}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{i}}]U_{\pi,i}.$

Disscusion and Applications. GVFs with causal filtering can cover a number of
important RL applications. We discuss in detail in Appendix B to show how the
variance of "reward-to-go", gradient of value function, and state/action value
function fall into the framework of forward GVFs in Definition 1, and anomaly
detection and gradient of logarithmic stationary distribution fall into the
framework of backward GVFs in Definition 2, respectively.

##  3 Off-Policy Evaluation of GVFs: Formulation and Algorithm

###  3.1 Problem Formulation

In this paper, we study the GVF evaluation problem for a target policy $\pi$.
We focus on the behavior-agnostic off-policy setting, in which we have access
only to samples generated from an off-policy (i.e., a behavior policy) with
the distribution $\mathcal{D}$, i.e.,
$(s_{j},a_{j},B_{j},s^{\prime}_{j})\sim\mathcal{D}$ $(j>0)$. Specifically, the
state-action pair $(s_{j},a_{j})$ is sampled from a possibly unknown
distribution $D(\cdot):\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$,
$B_{j}=[B_{1}(s_{j},a_{j}),\cdots,B_{k}(s_{j},a_{j})]$ is an observable signal
vector, and the successor state $s^{\prime}_{i}$ is sampled from
$\mathsf{P}(\cdot|s_{i},a_{i})$. Without loss of generality, we consider the
case in which $D(s,a)>0$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. Our
goal is to design an efficient algorithm to estimate $G_{\pi}$ (or
$\hat{G}_{\pi}$) given the sample set
$\\{(s_{j},a_{j},B_{j},s^{\prime}_{j})\\}_{j>0}$.

###  3.2 Linear Function Approximation

When $|\mathcal{S}|$ is large, a linear function can be used to approximate
the GVF: $G_{\pi,i}(s,a)\approx
G_{\pi,i}(\theta_{i};s,a)=\theta^{\top}_{i}\phi_{i}(s,a)=[\phi_{i}(s,a)^{\top}\otimes\mathsf{I}_{d_{i}}]\text{vec}(\theta^{\top}_{i})$,
where $\phi_{i}(s,a)\in\mathbb{R}^{K_{i}}$ is the feature vector, and
$\theta_{i}\in\mathbb{R}^{K_{i}\times d_{i}}$ is a learnable weight matrix. In
the sequel, we omit $\pi$ in $G_{\pi,i}$ and use the notation $G_{i}$. Without
loss of generality, we assume that $\left\|\phi_{i}(s,a)\right\|_{2}\leq 1$
for all $i=1,\cdots,k$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$. The linear
approximation can then be written as
$G_{i}(\theta_{i})=[{\rm\Phi}_{i}\otimes\mathsf{I}_{d_{i}}]\text{vec}(\theta_{i}^{\top})$,
where ${\rm\Phi}_{i}$ is the base matrix obtained by stacking
$\phi_{i}(s,a)^{\top}$ over $\mathcal{S}\times\mathcal{A}$. To ensure the
uniqueness of the solution $\theta_{i}$, we assume that ${\rm\Phi}_{i}$ has
linearly independent columns. The joint vector of GVFs can be denoted as
$[G_{1}^{\top}(\theta_{1}),\cdots,G_{k}^{\top}(\theta_{k})]^{\top}$, which is
captured by the joint parameters
$\theta=[\text{vec}(\theta_{1}^{\top})^{\top},\cdots,\text{vec}(\theta_{k}^{\top})^{\top}]^{\top}\in\mathbb{R}^{\sum_{i=1}^{k}K_{i}d_{i}}$.
Then the function approximation of GVFs can be written more compactly as
$G(\theta)={\rm\Phi}\theta$, where ${\rm\Phi}={\rm
diag}([{\rm\Phi_{1}}\otimes\mathsf{I}_{d_{1}}],\cdots,[{\rm\Phi_{k}}\otimes\mathsf{I}_{d_{k}}])$.
For each $(s,a)$, the linear function approximation associated with each
$(s,a)$ can be written as $G(\theta;s,a)=\phi(s,a)\theta$, where
$\phi(s,a)={\rm
diag}([\phi_{1}(s,a)^{\top}\otimes\mathsf{I}_{d_{1}}],\cdots,[\phi_{k}(s,a)^{\top}\otimes\mathsf{I}_{d_{k}}])$.
We define the linear function space spanned by the columns of the feature
matrix ${\rm\Phi}$ as $\mathcal{F}_{\rm\Phi}=\\{{\rm\Phi}\theta|\theta\in
R_{\theta}\\}$, in which $R_{\theta}$ is a convex set. Given the function
class $\mathcal{F}_{\rm\Phi}$, the evaluation problem of GVFs amounts to
searching for a parameter $\theta^{*}\in R_{\theta}$ such that $G(\theta^{*})$
approximates $G_{\pi}$ (or $\hat{G}_{\pi}$) well. In the sequel, we use
$\bar{\mathcal{T}}_{G,\pi}$ to represent $\mathcal{T}_{G,\pi}$ or
$\hat{\mathcal{T}}_{G,\pi}$, interchangeably, based on the context.

###  3.3 A New Off-policy GVF Evaluation Approach and Comparison to GTD

#### Drawbacks of GTD.

In previous works, the gradient TD (GTD) method [41, 22] has been used for
policy evaluation (including GVF evaluation) in the off-policy setting [33,
64, 65, 56]. GTD adopts the Mean Squared Projected Bellman Error (MSPBE) for
GVF evaluation with linear function approximation, which is given by

$\displaystyle\hat{\theta}^{*}=\operatorname*{argmin}_{\theta\in
R_{\theta}}\text{MSPBE}(\theta)\triangleq\mathbb{E}_{D}\left[\left\|G(\theta;s,a)-{\rm\Gamma}_{\mathcal{F}_{\rm\Phi},D}\bar{\mathcal{T}}_{G,\pi}G(\theta;s,a)\right\|_{2}^{2}\right].$
(7)

where ${\rm\Gamma}_{\mathcal{F}_{\rm\Phi},D}$ denotes the projection operator
onto the space $\mathcal{F}_{\rm\Phi}$ w.r.t. the
$\left\|\cdot\right\|_{D}$–norm, i.e., for any vector function $f(s,a)$ of
$(s,a)$, we have ${\rm\Gamma}_{\mathcal{F}_{\rm\Phi},d}f=G(\theta_{f})$, in
which $\theta_{f}=\operatorname*{argmin}_{\theta\in
R_{\theta}}\left\|f-G(\theta)\right\|_{D}$. One drawback of GTD is that the
expectation in the objective function is taken over the off-policy sampling
distribution $D(\cdot)$, which does not exactly reflect the desirable
evaluation under the target policy. As the result, the optimal point of GTD
($\hat{\theta}^{*}$) can still have a large approximation error with respect
to the ground truth value of GVF, even if the approximation function class is
arbitrarily expressive. More detailed discussion about GTD is provided in
Appendix C.

#### Generalized Temporal Difference (GenTD) Learning.

In this work, we propose a novel unified approach to evaluate both the forward
and backward GVFs in the off-policy setting, which we refer to as generalized
temporal difference (GenTD) learning. Specifically, we aim to learn
$\theta^{*}$ for GVF evaluation by minimizing the mean-squared projected
general Bellman error (MSPGBE) defined as

$\displaystyle\theta^{*}=\operatorname*{argmin}_{\theta\in
R_{\theta}}\text{MSPGBE}(\theta)\triangleq\mathbb{E}_{\mu_{\pi}}\left[\left\|G(\theta;s,a)-{\rm\Gamma}_{\mathcal{F}_{\rm\Phi},\mu_{\pi}}\bar{\mathcal{T}}_{G,\pi}G(\theta;s,a)\right\|_{2}^{2}\right],$
(8)

where recall that $\bar{\mathcal{T}}_{G,\pi}$ represents the GBO of either
forward or backward GVFs. In contrast to GTD, the objective function in eq. 8
takes the expectation over the stationary distribution $\mu_{\pi}$ of the
target distribution, which precisely captures the desired goal of GVF
evaluation under the target policy. On the other hand, such an objective does
cause implementation challenge, because the data samples are generated by the
behavior policy, so that estimators based on such data directly can incur a
large bias error. To solve such an issue, we will apply the density ratio
$\rho(s,a)=\mu_{\pi}(s,a)/D(s,a)$ to adjust the distribution and further adopt
the GenDICE/GradientDICE method proposed in [60, 62] to estimate $\rho(s,a)$
during the execution of the algorithm.

To describe our algorithm GenTD (see Algorithm 1), we first note that eq. 8
implies the following optimality condition for $\theta^{*}$,

$\displaystyle\langle
G(\theta^{*};\cdot)-\bar{\mathcal{T}}_{G;\pi}G(\theta^{*};\cdot),f(\cdot)-G(\theta^{*};)\rangle_{\mu_{\pi}}\geq
0,\quad\forall f\in\mathcal{F}_{\rm\Phi},$

or equivalently

$\displaystyle\langle g(\theta^{*}),\theta-\theta^{*}\rangle\geq
0,\quad\forall\theta\in R_{\theta},$ (9)

where
$g(\theta)={\rm\Phi}^{\top}U_{\pi}(G(\theta)-\bar{\mathcal{T}}_{G,\pi}G(\theta))$.
The variational inequality theory [20, Chapter 3] suggests that under an
appropriately chosen stepsize $\alpha_{t}$, the update
$\theta_{t+1}={\rm\Gamma}_{R_{\theta}}(\theta_{t}-\alpha_{t}g(\theta_{t}))$
converges to the optimal point $\theta^{*}$, where ${\rm\Gamma}_{R_{\theta}}$
denotes the projection operator onto the set $R_{\theta}$ in terms of the
Euclidean norm. However, since it is intractable to explicitly compute
$g(\theta)$ in practice, we usually estimate $g(\theta)$ using random samples.
In the off-policy setting, consider a sample $x=(s,a,s^{\prime},a^{\prime})$,
in which $(s,a)\sim D(\cdot)$, $s^{\prime}\sim\mathsf{P}(\cdot|s,a)$, and
$a^{\prime}\sim\pi(\cdot|s^{\prime})$, we can formulate the following update
rule:

$\displaystyle\theta_{t+1}=\theta_{t}-\alpha_{t}\hat{\rho}(s,a)g(x,\theta_{t}),$
(10)

where $\hat{\rho}(s,a)$ is an approximation of the density ratio
$\rho(s,a)=\mu_{\pi}(s,a)/D(s,a)$,
$g(x,\theta)=-\phi(s,a)^{\top}\delta(x,\theta)$ for forward GVFs and
$g(x,\theta)=-\phi(s^{\prime},a^{\prime})^{\top}\delta(x,\theta)$ for backward
GVFs, where $\delta(x,\theta)$ is the temporal difference error defined as
$\delta(x,\theta)=B(s,a)+m(x)\phi(s^{\prime},a^{\prime})\theta-\phi(s,a)\theta$
for forward GVFs, and
$\delta(x,\theta)={B}(s^{\prime},a^{\prime})+\hat{m}(x)\phi(s,a)\theta-\phi(s^{\prime},a^{\prime})\theta$
for backward GVFs. Here $m$ and $\hat{m}$ are matrices that capture the
correlations between difference estimations in forward and backward GVFs
evaluation settings, respectively. Here we adopt the GenDICE/GradientDICE
method that proposed in [60, 62] to learn $\rho(s,a)$. In previous works,
GenDIC/GradientDICE has only been used for estimating the scalar value
$\mathbb{E}_{\mu_{\pi}}[r(s,a)]$ in the off-policy setting [60, 65, 49]. Our
work is the first to adapt this method to solve the more challenging off-
policy GVFs evaluation problem.

#### Learning Density Ratio.

GenDICE/GradientDICE estimates the density ratio $\rho(s,a)$ via solving the
following min-max problem [60, 62]:

$\displaystyle\min_{\rho}\max_{f,\eta}L(\hat{\rho},f,\eta)\coloneqq\mathbb{E}_{\mathcal{D}}[\hat{\rho}(f^{\prime}-f)]-\frac{1}{2}\mathbb{E}_{\mathcal{D}}[f^{2}]+\mathbb{E}_{\mathcal{D}}[\eta\hat{\rho}-\eta]-\frac{1}{2}\eta^{2}.$
(11)

We parameterize both $\rho$ and $f$ by linear function approximation with
linearly independent features $\psi\in\mathbb{R}^{d_{\rho}}$, i.e.,
$\hat{\rho}(s,a;w_{\rho})=\psi(s,a)^{\top}w_{\rho}$ and
$\hat{f}(s,a;w_{f})=\psi(s,a)^{\top}w_{f}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. To guarantees the stability of the
density ratio learning, we assume that the matrix
$A=\mathbb{E}_{\mathcal{D}\cdot\pi}[\psi(\psi-\psi^{\prime})^{\top}]$ is non-
singular. Note that this assumption can be removed by adding an
$l_{2}$–regularizer in eq. 11.

In GenTD (see Algorithm 1), we estimate the density ratio via updating the
parameter $w_{\rho,t}$ iteratively. The density estimator
$\hat{\rho}(s_{t},a_{t};w_{\rho_{t}})=\psi(s_{t},a_{t})^{\top}w_{\rho_{t}}$ is
then used to reweight the update $g(x_{t},\theta_{t})$. As we will show in the
next section, even though the estimation of $\rho(s,a)$ is not always accurate
during the training, Algorithm 1 can still converge to $\theta^{*}$.

Comparison between GenTD and GTD. Compared with GTD, our GenTD has the
following two advantages. First, since GTD does not adjust the distribution
mismatch of sampling, the optimal point of GTD can suffer from large
approximation error with respect to the ground truth GVFs even with highly
expressive function classes. In contrast, the optimum of GenTD is guaranteed
to converge to the ground truth GVFs with sufficiently expressive function
classes. Second, GTD needs to update a high-dimensional auxiliary parameter
$w$ simultaneously with $\theta$ to stabilize the convergence, where
$w\in\mathbb{R}^{\sum_{i=1}^{k}K_{i}d_{i}}$ has the same dimension as $\theta$
(note that $d_{i}$ can be large in the high dimensional regime). Such an
update of $w$ can be very costly. In contrast, GenTD introduces only low-
dimensional auxiliary parameters
$[w_{\rho},w_{f},\eta]\in\mathbb{R}^{2d_{\rho}+1}$ for density ratio
estimation, which is more efficient.

Algorithm 1 Generalized TD Learning (GenTD)

Initialize: Approximator parameters $w_{f,0}$, $w_{\rho,0}$ and $\theta_{0}$

for $t=0,\cdots,T-1$ do

Obtain sample $(s_{t},a_{t},C_{t},s^{\prime}_{t})\sim\mathcal{D}_{d}$ and
$a^{\prime}_{t}\sim\pi(\cdot|s^{\prime}_{t})$

$\bar{\delta}_{t}=\psi_{t}^{\top}\theta_{\rho,t}(\psi^{\prime}_{t}-\psi_{t})$

$\eta_{t+1}=w_{\rho,t}+\beta_{t}(\psi_{t}^{\top}w_{\rho,t}-1-\eta_{t})$

$w_{f,t+1}=w_{f,t}+\beta_{t}(\bar{\delta}_{t}-\psi^{\top}_{t}w_{f,t}\psi_{t})$

$w_{\rho,t+1}={\rm\Gamma}_{R_{\rho}}\left(w_{\rho,t}-\beta_{t}(\psi^{\prime\top}_{t}w_{f,t}\psi_{t}-\psi_{t}^{\top}w_{f,t}\psi_{t}+\eta_{t}\psi_{t})\right)$

$\theta_{t+1}={\rm\Gamma}_{R_{\theta}}\left(\theta_{t}-\alpha_{t}[w_{\rho,t}^{\top}\psi(s_{t},a_{t})]g(x_{t},\theta_{t})\right)$

Forward GVF:
$g(x,\theta)=-\phi(s,a)^{\top}(B(s,a)+m(x)\phi(s^{\prime},a^{\prime})\theta-\phi(s,a)\theta)$

Backward GVF:
$g(x,\theta)=-\phi(s^{\prime},a^{\prime})^{\top}({B}(s^{\prime},a^{\prime})+\hat{m}(x)\phi(s,a)\theta-\phi(s^{\prime},a^{\prime})\theta)$

end for

##  4 Main Theorems

In this section, we characterize the convergence rate and optimality guarantee
for GenTD. To this end, we first establish a contraction property for the
general Bellman operator (GBO) of interest here. Although the contraction
property has been proven in the canonical value function settings [50, 65], it
is unclear whether such a property still holds for multiple interrelated and
high-dimensional GVFs. We will next show that only under a properly chosen
norm, such a property holds for both forward and backward GVFs with causal
filtering. This is the first result of such a type.

Consider the GVFs vector
$G_{\pi}=[G^{\top}_{\pi,1},\cdots,G^{\top}_{\pi,k}]^{\top}$. We define a norm
$\left\|\cdot\right\|_{\mu_{\pi},\alpha}$ associated with a weighting vector
$\alpha=[\alpha_{1},\cdots,\alpha_{k}]\in\Delta_{k}$, where $\Delta_{k}$
denotes the simplex in $k$-dimensional space, as

$\displaystyle{\textstyle\left\|G_{\pi}\right\|_{\mu_{\pi},\alpha}=\sum_{i=1}^{k}\alpha_{i}\left\|G_{\pi,i}\right\|_{\mu_{\pi}}\,\text{where}\,\,\,0<\alpha_{i}\leq
1\quad\text{for all}\,\,\,i\,\,\,\text{and}\,\,\,\sum_{i=1}^{k}\alpha_{i}=1}.$
(12)

We also define $\gamma_{\max}:=\max_{i=1\cdots,k}\gamma_{i}$, which is
strictly less than $1$.

######  Proposition 1 (Contraction of Forward/Backward GBO).

For any
${G}_{\pi},{G}^{\prime}_{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\sum_{i=1}^{k}K_{i}d_{i}}$,
there exists a weighting vector $\alpha$ such that

$\displaystyle\left\|\bar{\mathcal{T}}_{G,\pi}{G}_{\pi}-\bar{\mathcal{T}}_{G,\pi}{G}^{\prime}_{\pi}\right\|_{\mu_{\pi},\alpha}\leq\gamma_{G}\left\|{G}_{\pi}-{G}^{\prime}_{\pi}\right\|_{\mu_{\pi},\alpha},$
(13)

where $\gamma_{G}=(1+\gamma_{\max})/2$ and $\bar{\mathcal{T}}_{G,\pi}$ can be
either $\mathcal{T}_{G,\pi}$ (forward GBO, eq. 3) or
$\hat{\mathcal{T}}_{G,\pi}$ (backward GBO, eq. 6).

Despite the correlations between GVFs, Proposition 1 shows that the
contraction property is still preserved under a properly chosen norm for
${\mathcal{T}}_{G,\pi}$ and $\hat{\mathcal{T}}_{G,\pi}$ in forward and
backward GVF settings, respectively. The norm can vary for different GVFs.
Proposition 1 also implies that both forward and backward GVFs ($G_{\pi}$ and
$\hat{G}_{\pi}$) can be identified as unique fixed point of their
corresponding GBOs.

Based on Proposition 1, we next establish the monotonicity property for our
GenTD algorithm, if it takes the population update
$g(\theta)={\rm\Phi}^{\top}U_{\pi}(G(\theta)-\bar{\mathcal{T}}_{G,\pi}G(\theta))$.

######  Proposition 2 (Monotonicity).

Consider the globally optimal point $\theta^{*}$ defined in eq. 9. There
exists a constant $\lambda_{G}$ such that for all $\theta\in R_{\theta}$, we
have

$\displaystyle\langle
g(\theta^{*})-g(\theta),\theta^{*}-\theta\rangle\geq\lambda_{G}\left\|\theta-\theta^{*}\right\|_{F}^{2},$
(14)

where $\lambda_{G}:=(1-\gamma_{\max})\min_{1\leq i\leq k}\zeta_{i}$ and
$\zeta_{i}:=\lambda_{\min}({\rm\Phi}^{\top}_{i}U_{\pi}{\rm\Phi}_{i})$.

Proposition 2 implies the contraction property of $g(\theta)$. It guarantees
that $\theta$ moves towards a globally optimal point $\theta^{*}$ if it is
updated along the direction $-g(\theta)$. Proposition 2 generalizes the
monotonicity property to a much broader class of interrelated and multi-
dimensional GVF evaluation, which is far more beyond TD learning for the value
function evaluation studied in [50, 65]. The following theorem characterizes
the convergence rate of GenTD.

######  Theorem 1.

Consider the GenTD update in Algorithm 1. Let the stepsize
$\alpha_{t}={\rm\Theta}(t^{-1})$ and $\beta_{t}={\rm\Theta}(t^{-1})$. We have

$\displaystyle\mathbb{E}[\left\|\theta_{T}-\theta^{*}\right\|_{F}^{2}]\leq\mathcal{O}\left(\frac{\left\|\theta_{0}-\theta^{*}\right\|_{F}^{2}}{T^{2}}\right)+\mathcal{O}\left(\frac{1}{\lambda^{3}_{G}T}\right)+\mathcal{O}\left(\frac{\varepsilon_{\rho}}{\lambda^{2}_{G}}\right),$
(15)

where
$\varepsilon_{\rho}=\sqrt{\mathbb{E}_{\mathcal{D}\cdot\pi}[\hat{\rho}(s,a;w^{*}_{\rho})-\rho(s,a)]^{2}}$
is the approximation error introduced by the density ratio learning, with
$w^{*}_{\rho}$ being the global optimal point of $L(\hat{\rho},f,\eta)$
defined in eq. 11.

Theorem 1 shows that GenTD converges to the globally optimal point
$\theta^{*}$ at a rate $\mathcal{O}(1/T)$. The convergence speed of $\theta$
also depends on the conditional number $\lambda_{G}$, where the converge
becomes faster as $\lambda_{G}$ increases. Specifically, the R.H.S. of eq. 15
consists of three terms. The first term corresponds to the initialization
error, which delays as fast as $\mathcal{O}(1/T^{2})$. The second term
corresponds to the variance error, which dominates the convergence rate of
GenTD to be $\mathcal{O}(1/T)$. The last term corresponds to a non-vanishing
optimality gap, which is introduced by the function approximation error in the
density ratio estimation, and decreases as the expressive power of the
approximation function class $\\{\hat{\rho}(w_{\rho}):w_{\rho}\in R_{\rho}\\}$
increases. The convergence analysis of GenTD is more challenging than that of
TD learning [2, 7, 36] and GTD [57, 17], as we need to handle an additional
approximation error introduced by the dynamically changing density ratio
estimator $\hat{\rho}(w_{\rho_{t}})$.

Theorem 1 establishes the convergence of GenTD to the globally optimal point
$\theta^{*}$ of the objective function in eq. 8, which provides the value
estimation $G(\theta^{*})$ for the GVFs. We are then interested in
characterizing how close such an estimation is to the ground truth GVF
$G_{\pi}$, which is our ultimate goal of evaluation. We characterize this in
the following theorem.

######  Theorem 2 (Convergence of GenTD to Ground Truth).

Consider $\theta^{*}$ defined in eq. 8. Suppose the same conditions in
Proposition 1 and Proposition 2 hold. We have

$\displaystyle\left\|G(\theta^{*})-G_{\pi}\right\|_{\mu_{\pi},\alpha}\leq\frac{1}{1-\gamma_{G}}\left\|{\rm\Gamma}_{\mathcal{F}_{\rm\Phi},\mu_{\pi}}G_{\pi}-G_{\pi}\right\|_{\mu_{\pi},\alpha}.$
(16)

Theorem 2 indicates that the distance between the optimal estimation
$G(\theta^{*})$ and the true GVF $G_{\pi}$ is upper bounded by the
approximation error of the function class $\mathcal{F}_{\rm\Phi}$ for the
ground truth GVF $G_{\pi}$ (note that
${\rm\Gamma}_{\mathcal{F}_{\rm\Phi},\mu_{\pi}}G_{\pi}$ denotes the projection
of $G_{\pi}$ to the function approximation class $\mathcal{F}_{\rm\Phi}$).
Hence, Theorem 2 guarantees that $G(\theta^{*})$ can be as close as possible
to the true GVF $G_{\pi}$, as long as the function class
$\mathcal{F}_{\rm\Phi}$ is sufficiently expressive. In particular, if
$\mathcal{F}_{\rm\Phi}$ is complete, i.e., there exists
$G_{\theta}\in\mathcal{F}_{\rm\Phi}$ such that $G_{\theta}=G_{\pi}$, then
GenTD is guaranteed to converge exactly to the ground truth $G_{\pi}$.

Comparison between GenTD and GTD. If $\mathcal{F}_{\rm\Phi}$ is complete, GTD
performs similarly to GenTD and is guaranteed to converge to the ground truth
$G_{\pi}$ (see Section C.2 for the proof). The major difference between GenTD
and GTD occurs when $\mathcal{F}_{\rm\Phi}$ is not complete. In such a case,
our GenTD still maintains the desirable performance as guaranteed by Theorem
2, but the optimal point of GTD (i.e., $\hat{\theta}^{*}$ in eq. 7) does not
have guaranteed convergence to the ground truth. As shown in [19, 10, 26],
even in the value function evaluation setting (a special case of forward GVF
evaluation) the approximation error $||G(\hat{\theta}^{*})-G_{\pi}||_{D}$ of
GTD can be arbitrarily poor even if $\mathcal{F}_{\rm\Phi}$ can represent the
true value function arbitrarily well (but not exactly). Such a disadvantage of
GTD is mainly due to the distribution mismatch in its objective function as we
discuss in Section 3.3.

In the backward GVFs evaluation setting, GTD can perform even worse. As we
show in the following example, GTD may fail to learn the ground truth
$G_{\pi}$ even if the function class $\mathcal{F}_{\rm\Phi}$ is complete. Note
that for such a case, GenTD converges to the ground truth as guaranteed by
Theorem 2.

######  Example 1 (GTD Fails for Complete $\mathcal{F}_{\rm\Phi}$).

Consider a three-state Markov chain, with transition kernel
$\mathsf{P}=[[0.1,0.9,0],[0.1,0,0.9],[0,0.1,0.9]]^{\top}$, discount factor
$\gamma=0.99$, and the reward function $R=[1,0,1]^{\top}$. The back value
function in this MDP is given by $\bar{V}=[8.1555,9.0389,9.0184]^{\top}$.
Suppose GTD is applied to solving the evaluation problem with the parameter
space $R_{\theta}=\mathbb{R}$. Then, there exists an off-policy distribution
$D$ such that using the perfect bases
${\rm\Phi}=[8.1555,9.0389,9.0184]^{\top}$, the optimal point
$\bar{\theta}^{*}$ learned by GTD still has non-zero approximation error,
i.e., $||{\rm\Phi}\bar{\theta}^{*}-\bar{V}||_{D}\geq 3$.

##  5 Experiments

We conduct empirical experiments to answer the following two questions: (a)
can GenTD evaluate both the forward and backward GVFs efficiently? (2) how
does GenTD compare with GTD in terms of the convergence speed and the quality
of the estimation results?

Figure 1: Comparison between GenTD and GTD for the tasks of evaluating
$\nabla_{w}Q_{\pi}$ and $\nabla_{w}\log\mu_{\pi}$.

In our experiments, we consider a variant of Baird’s counterexample [1, 40]
with 7 states and 2 actions (see Figure 2 in Appendix A). We study the problem
of evaluating two high-dimensional GVFs, the gradient of Q-function:
$\nabla_{w}Q_{\pi}\in\mathbb{R}^{14}$ (forward GVF), and the gradient of
logarithmic stationary distribution:
$\nabla_{w}\log(\mu_{\pi})\in\mathbb{R}^{14}$ (backward GVF), associated with
a soft-max policy parameterized by $w\in\mathbb{R}^{14}$. We consider two
types of feature matrices ${\rm\Phi}$ for estimating the GVFs: complete
feature (CFT) and incomplete feature (INCFT), where CFT has large enough
expressive power so that the ground true GVF can be fully expressed by the
function class $\mathcal{F}_{\rm\Phi}$, whereas INCFT does not have enough
expressive power and cannot capture the ground true GVF exactly. The discount
factor $\gamma$ is set to be $0.99$ in all tasks, and all curves in the plots
are averaged over 20 independent runs. The detailed experimental setting is
provided in Appendix A.

The learning curves for GenTD and GTD are provided in Figure 1. We evaluate
their performances based on the estimation error with respect to the ground
truth GVF: $\left\|{\rm\Phi}\theta_{t}-{G}_{\pi}\right\|_{\mu_{\pi}}$. Note
that both $\nabla_{w}Q_{\pi}$ and $\nabla_{w}\log\mu_{\pi}$ can be exactly
computed in this tabular setting, so that the estimator error of the ground
truth can be computed. For the task of $\nabla_{w}Q$ evaluation, GenTD
converges considerably faster and much closer to the ground truth (i.e.,
smaller estimation error) than GTD. which can be attributed to the larger
conditional number $\lambda_{G}$ of GenTD. For the task of
$\nabla_{w}\log\mu_{\pi}$ evaluation, GenTD moves fast towards the ground
truth GVF, whereas GTD, although still converges, stays far away from the
ground truth GVF even with CFT, which matches with our Example 1. As we
discuss in Section 4, this is because GTD in the backward GVF evaluation
setting has distribution mismatch in its objective function, which can
significantly shift the optimal point from the ground truth GVF.

##  6 Conclusion

We studied the off-policy evaluation problem of both forward and backward
GVFs. We focused on the class of GVFs with casual filtering, which covers a
wide range of multiple interrelated and possibly high-dimensional GVFs. We
first showed that GVFs in such a class is the fixed point of a general Bellman
operator. Based on such a property, we proposed a new off-policy algorithm
called GenTD. GenTD evaluates GVFs efficiently by jointly updating the GVF
approximation parameter and a density ratio estimator, which adjusts the
mismatch of the behavior policy and assists the convergence to the ground
truth GVFs. We show that GenTD provably converges to the globally optimal
point, and such an optimal point is guaranteed to converge to the ground truth
GVFs as long as the function expressive power is sufficiently large. For
future work, it is interesting to study nonlinear function approximation for
GVFs evaluation.

##  7 Acknowledgement

The work of T. Xu and Y. Liang was supported in part by the U.S. National
Science Foundation under the grants CCF-1801855, CCF-1761506 and CCF-1900145.

## References

  * [1] L. Baird.  Residual algorithms: reinforcement learning with function approximation.  In Machine Learning Proceedings, pages 30–37. 1995.
  * [2] J. Bhandari, D. Russo, and R. Singal.  A finite time analysis of temporal difference learning with linear function approximation.  In Proc. Conference on Learning Theory (COLT), pages 1691–1692, 2018.
  * [3] Q. Cai, Z. Yang, J. D. Lee, and Z. Wang.  Neural temporal-difference and q-learning provably converge to global optima.  In Proc. Neural Information Processing Systems (NeurIPS), 2019.
  * [4] Y. Chandak, S. Niekum, B. C. da Silva, E. Learned-Miller, E. Brunskill, and P. S. Thomas.  Universal off-policy evaluation.  arXiv preprint arXiv:2104.12820, 2021.
  * [5] G. Comanici, D. Precup, A. Barreto, D. K. Toyama, E. Aygün, P. Hamel, S. Vezhnevets, S. Hou, and S. Mourad.  Knowledge representation for reinforcement learning using general value functions.  OpenReview, 2018.
  * [6] G. Dalal, B. Szorenyi, and G. Thoppe.  A tale of two-timescale reinforcement learning with the tightest finite-time bound.  In Proc. AAAI Conference on Artificial Intelligence (AAAI), volume 34, pages 3701–3708.
  * [7] G. Dalal, B. Szörényi, G. Thoppe, and S. Mannor.  Finite sample analyses for TD (0) with function approximation.  In Proc. AAAI Conference on Artificial Intelligence (AAAI), 2018\.
  * [8] P. D’Oro and W. Jaśkowski.  How to learn a useful critic? model-based action-gradient-estimator policy optimization.  arXiv preprint arXiv:2004.14309, 2020.
  * [9] C. Downey, A. Hefny, B. Li, B. Boots, and G. Gordon.  Predictive state recurrent neural networks.  In Proc. Neural Information Processing Systems (NeurIPS), pages 6055–6066, 2017.
  * [10] A. Hallak and S. Mannor.  Consistent on-line off-policy evaluation.  In Proc. International Conference on Machine Learning (ICML), pages 1372–1383, 2017.
  * [11] E. Hazan, S. Kakade, K. Singh, and A. Van Soest.  Provably efficient maximum entropy exploration.  In International Conference on Machine Learning, pages 2681–2691, 2019.
  * [12] N. Heess, G. Wayne, D. Silver, T. Lillicrap, Y. Tassa, and T. Erez.  Learning continuous control policies by stochastic value gradients.  arXiv preprint arXiv:1510.09142, 2015.
  * [13] R. A. Horn and C. R. Johnson.  Matrix analysis.  Cambridge University Press, 2012.
  * [14] J. Huang and N. Jiang.  From importance sampling to doubly robust policy gradient.  In Proc. International Conference on Machine Learning (ICML), pages 4434–4443, 2020.
  * [15] A. Jain, G. Patil, A. Jain, K. Khetarpal, and D. Precup.  Variance penalized on-policy and off-policy actor-critic.  arXiv preprint arXiv:2102.01985, 2021.
  * [16] N. Jiang and L. Li.  Doubly robust off-policy value evaluation for reinforcement learning.  In Proc. International Conference on Machine Learning (ICML), pages 652–661, 2016.
  * [17] M. Kaledin, E. Moulines, A. Naumov, V. Tadic, and H.-T. Wai.  Finite time analysis of linear two-timescale stochastic approximation with markovian noise.  In Proc. Conference on Learning Theory (COLT), pages 2144–2203, 2020.
  * [18] N. Kallus and M. Uehara.  Statistically efficient off-policy policy gradients.  arXiv preprint arXiv:2002.04014, 2020.
  * [19] J. Kolter.  The fixed points of off-policy TD.  In Proc. Advances in Neural Information Processing Systems (NIPS), volume 24, pages 2169–2177, 2011.
  * [20] G. Lan.  First-order and Stochastic Optimization Methods for Machine Learning.  Springer, 2020.
  * [21] B. Liu, J. Liu, M. Ghavamzadeh, S. Mahadevan, and M. Petrik.  Finite-sample analysis of proximal gradient TD algorithms.  In UAI, pages 504–513, 2015.
  * [22] H. R. Maei.  Gradient temporal-difference learning algorithms.  PhD thesis, University of Alberta, 2011.
  * [23] A. R. Mahmood and R. S. Sutton.  Representation search through generate and test.  In Proc. AAAI Workshop: Learning Rich Representations from Low-Level Sensors, 2013.
  * [24] S. Mannor and J. N. Tsitsiklis.  Algorithmic aspects of mean–variance optimization in markov decision processes.  European Journal of Operational Research, 231(3):645–653, 2013\.
  * [25] T. Morimura, E. Uchibe, J. Yoshimoto, J. Peters, and K. Doya.  Derivatives of logarithmic stationary distributions for policy gradient reinforcement learning.  Neural computation, 22(2):342–376, 2010.
  * [26] R. Munos.  Error bounds for approximate policy iteration.  In Proc. International Conference on Machine Learning (ICML), volume 3, pages 560–567, 2003.
  * [27] A. Ruszczyński.  Risk-averse dynamic programming for markov decision processes.  Mathematical programming, 125(2):235–261, 2010.
  * [28] M. Sato, H. Kimura, and S. Kobayashi.  TD algorithm for the variance of return and mean-variance reinforcement learning.  Transactions of the Japanese Society for Artificial Intelligence, 16(3):353–362, 2001.
  * [29] T. Schaul and M. Ring.  Better generalization with forecasts.  In Proc. International Joint Conference on Artificial Intelligence (IJCAI), pages 1656–1662, 2013.
  * [30] W. F. Sharpe.  Mutual fund performance.  The Journal of business, 39(1):119–138, 1966.
  * [31] C. Sherstan.  Representation and general value functions.  PhD thesis, University of Alberta, 2020.
  * [32] S. M. Shortreed, E. Laber, D. J. Lizotte, T. S. Stroup, J. Pineau, and S. A. Murphy.  Informing sequential clinical decision-making through reinforcement learning: an empirical study.  Machine Learning, 84(1-2):109–136, 2011.
  * [33] D. Silver.  Gradient temporal difference networks.  In European Workshop on Reinforcement Learning, pages 117–130, 2013\.
  * [34] D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller.  Deterministic policy gradient algorithms.  In Proc. International Conference on Machine Learning (ICML), pages 387–395, 2014.
  * [35] M. J. Sobel.  The variance of discounted Markov decision processes.  Journal of Applied Probability, pages 794–802, 1982.
  * [36] R. Srikant and L. Ying.  Finite-time error bounds for linear stochastic approximation andtd learning.  In Proc. Conference on Learning Theory (COLT), pages 2803–2830, 2019.
  * [37] W. Sun, A. Venkatraman, B. Boots, and J. A. Bagnell.  Learning to filter with predictive state inference machines.  In Proc. International Conference on Machine Learning (ICML), pages 1197–1205, 2016.
  * [38] R. S. Sutton.  Learning to predict by the methods of temporal differences.  Machine Learning, 3(1):9–44, 1988.
  * [39] R. S. Sutton.  The grand challenge of predictive empirical abstract knowledge.  In Proc. IJCAI Workshop on Grand Challenges for Reasoning from Experiences, 2009.
  * [40] R. S. Sutton and A. G. Barto.  Reinforcement Learning: An introduction.  MIT press, 2018.
  * [41] R. S. Sutton, H. R. Maei, D. Precup, S. Bhatnagar, D. Silver, C. Szepesvári, and E. Wiewiora.  Fast gradient-descent methods for temporal-difference learning with linear function approximation.  In Proc. International Conference on Machine Learning (ICML), pages 993–1000, 2009.
  * [42] R. S. Sutton, A. R. Mahmood, and M. White.  An emphatic approach to the problem of off-policy temporal-difference learning.  The Journal of Machine Learning Research, 17(1):2603–2631, 2016\.
  * [43] R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 1057–1063, 2000.
  * [44] R. S. Sutton, J. Modayil, M. Delp, T. Degris, P. M. Pilarski, A. White, and D. Precup.  Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction.  In Proc. International Conference on Autonomous Agents and Multiagent Systems, pages 761–768, 2011.
  * [45] R. S. Sutton and B. Tanner.  Temporal-difference networks.  volume 17, pages 1377–1384, 2004.
  * [46] A. Tamar, D. Di Castro, and S. Mannor.  Policy gradients with variance related risk criteria.  In Proc. International Conference on Machine Learning (ICML), pages 1651–1658, 2012.
  * [47] A. Tamar, D. Di Castro, and S. Mannor.  Learning the variance of the reward-to-go.  The Journal of Machine Learning Research, 17(1):361–396, 2016.
  * [48] A. Tamar and S. Mannor.  Variance adjusted actor critic algorithms.  arXiv preprint arXiv:1310.3697, 2013.
  * [49] Z. Tang, Y. Feng, L. Li, D. Zhou, and Q. Liu.  Doubly robust bias reduction in infinite horizon off-policy estimation.  arXiv preprint arXiv:1910.07186, 2019.
  * [50] J. N. Tsitsiklis and B. Van Roy.  Analysis of temporal-diffference learning with function approximation.  In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 1075–1081, 1997.
  * [51] J. N. Tsitsiklis and B. Van Roy.  Average cost temporal-difference learning.  In Proc. IEEE Conference on Decision and Control, volume 1, pages 498–502, 1997.
  * [52] A. White et al.  Developing a predictive approach to knowledge.  2015\.
  * [53] T. Xu and Y. Liang.  Sample complexity bounds for two timescale value-based reinforcement learning algorithms.  In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 811–819, 2021.
  * [54] T. Xu, Z. Wang, and Y. Liang.  Improving sample complexity bounds for (natural) actor-critic algorithms.  In Proc. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
  * [55] T. Xu, Z. Wang, and Y. Liang.  Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms.  arXiv preprint arXiv:2005.03557, 2020.
  * [56] T. Xu, Z. Yang, Z. Wang, and Y. Liang.  Doubly robust off-policy actor-critic: convergence and optimality, 2021\.
  * [57] T. Xu, S. Zou, and Y. Liang.  Two time-scale off-policy TD learning: Non-asymptotic analysis over markovian samples.  In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 10633–10643, 2019.
  * [58] H. Yao and D. Schuurmans.  Reinforcement ranking.  arXiv preprint arXiv:1303.5988, 2013.
  * [59] J. Zhang, A. Koppel, A. S. Bedi, C. Szepesvari, and M. Wang.  Variational policy gradient method for reinforcement learning with general utilities.  arXiv preprint arXiv:2007.02151, 2020.
  * [60] R. Zhang, B. Dai, L. Li, and D. Schuurmans.  Gendice: generalized offline estimation of stationary values.  arXiv preprint arXiv:2002.09072, 2020.
  * [61] S. Zhang, W. Boehmer, and S. Whiteson.  Generalized off-policy actor-critic.  In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 2001–2011, 2019.
  * [62] S. Zhang, B. Liu, and S. Whiteson.  GradientDICE: rethinking generalized offline estimation of stationary values.  In Proc. International Conference on Machine Learning (ICML), pages 11194–11203, 2020.
  * [63] S. Zhang, B. Liu, H. Yao, and S. Whiteson.  Provably convergent off-policy actor-critic with function approximation.  In Proc. International Conference on Machine Learning (ICML), 2020\.
  * [64] S. Zhang, B. Liu, H. Yao, and S. Whiteson.  Provably convergent two-timescale off-policy actor-critic with function approximation.  In Proc. International Conference on Machine Learning (ICML), pages 11204–11213, 2020.
  * [65] S. Zhang, V. Veeriah, and S. Whiteson.  Learning retrospective knowledge with reverse reinforcement learning.  Proc. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.

Supplementary Materials

##  Appendix A Specification of Experiments

The Baird’s counterexample [1, 40] is shown in Figure 2. There are two actions
represented by solid line and dash line, respectively. The the dash action
leads to states 1-6 with equal probability and a reward $+1$, and solid action
always leads to state 7 and a reward $0$. The behavior distribution over the
state-action space $(s,a)$ is given as

$\displaystyle
D(\cdot)=\begin{cases}D(s_{1},a_{1})=0.2,\quad&D(s_{1},a_{2})=0.1,\\\
D(s_{2},a_{1})=0.2,\quad&D(s_{2},a_{2})=0.1,\\\
D(s_{3},a_{1})=0.04,\quad&D(s_{3},a_{2})=0.04,\\\
D(s_{4},a_{1})=0.04,\quad&D(s_{4},a_{2})=0.04,\\\
D(s_{5},a_{1})=0.04,\quad&D(s_{5},a_{2})=0.04,\\\
D(s_{6},a_{1})=0.04,\quad&D(s_{6},a_{2})=0.04,\\\
D(s_{7},a_{1})=0.04,\quad&D(s_{7},a_{2})=0.04,\end{cases}$

Figure 2: A variant of Baird’s counterexample.

where $s_{i}$ denotes state "$i$" ($i=1,\cdots,7$), $a_{1}$ denotes the dash
action and $a_{2}$ denotes the solid action. We consider the soft-max policy
given as

$\displaystyle\pi_{w}(s_{i},a_{j})=\frac{\exp(w_{2(i-1)+j})}{\exp(w_{2(i-1)+1})+\exp(w_{2(i-1)+2})},\quad
i=\\{1,\cdots,7\\},\,\,j=\\{1,2\\},$

where $w\in\mathbb{R}^{14}$ is the parameter of the policy given as

$\displaystyle
w^{\top}=[0.0,1.8,0.0,1.8,0.0,1.8,0.0,1.8,0.0,1.8,0.0,1.8,0.0,1.8].$

The complete feature (CFT), incomplete feature (INCFT) and the learning rate
for each task are given as follows:

  * •

Evaluation of $\nabla_{w}Q_{\pi}$ (forward GVF). In this task, we need to
evaluate both $Q_{\pi}$ and $\nabla_{w}Q_{\pi}$ (see Section B.1 for detailed
discussion about correlation between $Q_{\pi}$ and $\nabla_{w}Q_{\pi}$). Let
the complete feature matrix ${\rm\Phi}$ be the identity matrix, i.e.,
${\rm\Phi}=I\in\mathbb{R}^{14\times 14}$. We let CFT for each $(s,a)$ be one
of the rows of ${\rm\Phi}$. We further remove one column of ${\rm\Phi}$ to
obtain the incomplete feature matrix
${\rm\Phi}^{\prime}\in\mathbb{R}^{14\times 13}$. We let INCFT for each $(s,a)$
be one of the rows of ${\rm\Phi}^{\prime}$. For GenTD, the learning rate for
updating $w_{\rho}$ and $\theta$ are $0.01$ and $0.005$, respectively. We use
the same CFT and INCFT for the density ratio estimation as those for the
$\nabla_{w}Q_{\pi}$ estimation. For GTD, the learning rate for both the main
parameter $\theta$ and the auxiliary parameter $w$ are $0.005$.

  * •

Evaluation of $\nabla_{w}\log\mu_{\pi}$ (backward GVF). Section B.2 has
detailed discussion about such a GVF. Note that this task corresponds to the
setting where $\gamma=1$. As discussed in Appendix G, the ground true GVF in
this setting is in the space perpendicular to the vector
$e=[1,\cdots,1]^{\top}\in\mathbb{R}^{14}$. Here we use singular value
decomposition (SVD) to obtain the complete feature matrix
${\rm\Phi}\in\mathbb{R}^{14\times 13}$ such that ${\rm\Phi}\theta\neq Ce$ for
all $\theta\neq 0$ and $C\neq 0$. We let CFT for each $(s,a)$ be one of the
rows of ${\rm\Phi}$. We further remove one column of ${\rm\Phi}$ to obtain the
incomplete feature matrix ${\rm\Phi}^{\prime}\in\mathbb{R}^{14\times 12}$. We
let INCFT for each $(s,a)$ be one of the rows of ${\rm\Phi}^{\prime}$. For
GenTD, the learning rate for updating $w_{\rho}$ and $\theta$ are $0.05$ and
$0.005$, respectively. We use the same CFT and INCFT for the density ratio
estimation as those used in the above $\nabla_{w}Q_{\pi}$ estimation task. For
GTD, the learning rate for both the main parameter $\theta$ and the auxiliary
parameter $w$ are $0.005$.

##  Appendix B Examples of Forward and Backward GVFs

In this section, we present a number of example forward and backward GVF in RL
applications.

###  B.1 Examples of Forward GVFs

The forward GVF in Definition 1 arises naturally in the following RL
applications.

Case I: Variance of Reward-To-Go.  In risk-sensitive domains such as finance,
process control and clinical decision making [30, 24, 48, 46, 27, 28, 35, 15],
in addition to the mean $J_{\pi}$ of the "reward-to-go", we are also
interested in the variance of $J_{\pi}$ [30, 32], which is given by
$\text{Var}[J_{\pi}|(s_{0},a_{0})=(s,a)]=H_{\pi}(s,a)-Q^{2}_{\pi}(s,a)$, where
$H_{\pi}$ is the second moment of $J_{\pi}$, i.e.,
$H_{\pi}(s,a)=\mathbb{E}[J_{\pi}^{2}|(s_{0},a_{0})=(s,a),\pi]$. [47] shows
that $H_{\pi}$ satisfies

$\displaystyle H_{\pi}=R^{2}+2\gamma
M_{R}\mathsf{P}_{\pi}Q_{\pi}+\gamma^{2}\mathsf{P}_{\pi}H_{\pi},$ (17)

where $R$ is defined in Section 2, $M_{R}={\rm
diag}(R)\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$.
Equation 17 implies that $H_{\pi}$ is the mean of the accumulation of signal
$C(s,a)=r(s,a)^{2}+2\gamma\mathbb{E}[Q_{\pi}(s^{\prime},a^{\prime})|s,a]$ with
discounted factor $\gamma^{2}$. Since $C(s,a)$ is a function of the reward
$r(s,a)$ and value function $Q_{\pi}(s,a)$, we consider the joint vector of
$Q_{\pi}$ and $H_{\pi}$ as $G_{\pi}$, i.e.,
$G_{\pi}=[Q^{\top}_{\pi},H^{\top}_{\pi}]^{\top}$. We have that $G_{\pi}$
satisfies the general Bellman equation in eq. 3 with $B$ and $M_{\pi}$
specified as

$\displaystyle B=\left[\begin{array}[]{c}R\\\ R^{2}\end{array}\right],\quad
M_{\pi}=\left[\begin{array}[]{cc}\gamma\mathsf{P}_{\pi}&0\\\ 2\gamma
M_{R}\mathsf{P}_{\pi}&\gamma^{2}\mathsf{P}_{\pi}\end{array}\right].$ (22)

We consider the setting in which reward is bounded, i.e., $r(s,a)\leq C_{R}$
for all $(s,a)\in\mathcal{S}\times\mathcal{A}$.

Case II: Gradient of Q-function. Suppose that the policy is parametrized by a
smooth function $\pi_{w}$, in which $w\in\mathbb{R}^{d_{w}}$ is the parameter.
Then the gradient $\nabla_{w}Q_{\pi}(s,a)$ of the Q-function w.r.t $w$ plays
an important role in several RL applications such as variance reduced policy
gradient [14] and on- and off-policy policy optimization [56, 34, 18, 5].
Specifically, [56, 18, 5] show that $\nabla_{w}Q_{\pi}$ satisfies:

$\displaystyle\nabla_{w}Q_{\pi}=\gamma[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{w}}][\nabla_{w}{\rm\Pi}_{\pi_{w}}\cdot
Q_{\pi}]+\gamma[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{w}}]\nabla_{w}Q_{\pi},$
(23)

where
$\nabla_{w}{\rm\Pi}_{\pi_{w}}\in\mathbb{R}^{d_{w}|\mathcal{S}||\mathcal{A}|}$
is obtained by stacking $\nabla_{w}\log(\pi(s,a))$ over
$\mathcal{S}\times\mathcal{A}$, i.e.,
$[\nabla_{w}{\rm\Pi}_{\pi_{w}}](s,a)=\nabla_{w}\log(\pi_{w}(s,a))$, and
$[\nabla_{w}{\rm\Pi}_{\pi_{w}}\cdot
Q_{\pi}]\in\mathbb{R}^{d_{w}|\mathcal{S}||\mathcal{A}|}$ is element-wise
product between $\nabla_{w}{\rm\Pi}_{\pi_{w}}$ and $Q_{\pi}$, i.e.,
$[\nabla_{w}{\rm\Pi}_{\pi_{w}}\cdot
Q_{\pi}](s,a)=\nabla_{w}\log(\pi_{w}(s,a))Q_{\pi}(s,a)$. Equation 23 implies
that $\nabla_{w}Q_{\pi}$ is the mean of the accumulation of signal
$C(s,a)=\gamma\mathbb{E}[Q_{\pi}(s^{\prime},a^{\prime})\nabla_{w}\log(\pi_{w}(s^{\prime},a^{\prime}))|s,a]$
with the discounted factor $\gamma$. Let
$G_{\pi}=[Q^{\top}_{\pi},\nabla_{w}Q^{\top}]^{\top}$. We have that $G_{\pi}$
satisfies the general Bellman equation in eq. 3 with $B$ and $M_{\pi}$
specified as

$\displaystyle B=\left[\begin{array}[]{c}R\\\ 0\end{array}\right],\quad
M_{\pi}=\left[\begin{array}[]{cc}\gamma\mathsf{P}_{\pi}&0\\\
\gamma[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{w}}]{\rm
diag}(\nabla_{w}{{\rm\Pi}}_{\pi_{w}})&\gamma\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{w}}\end{array}\right],$
(28)

where ${\rm
diag}(\nabla_{w}{{\rm\Pi}}_{\pi_{w}})\in\mathbb{R}^{d_{w}|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
is obtained by arranging $\nabla_{w}\log(\pi(s,a))\in\mathbb{R}^{d_{w}}$
diagonally. Without loss of generality, we assume that the score function is
bounded [40, 43, 54], i.e.,
$\left\|\nabla_{w}\log(\pi_{w}(s,a))\right\|_{2}\leq C_{\rm\Pi}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

Case III: Stochastic Value Gradient. The stochastic value gradient (SVG)
method combines advantages of model-based and model-free methods, in which
both the estimated model and value function are updated to evaluate the policy
gradient [12]. In the framework of SVG, the reward $r(s,a)$ is differentiable
with respect to both $s\in\mathbb{R}^{d_{s}}$ an $a\in\mathbb{R}^{d_{a}}$, the
stochastic policy takes the form $a=\pi(s,w)+\eta$, and the transition
probability is modelled as $s^{\prime}=f(s,a)+\xi$, where
$\pi:\mathcal{S}\rightarrow\mathcal{A}$ and
$f:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$ are deterministic
mappings, $w\in\mathbb{R}^{d_{w}}$ is the policy parameter, and $\eta\sim
P(\eta)$ and $\xi\sim P(\xi)$ are noise variables. We abbreviate the partial
differentiation using subscripts as $g_{x}\triangleq\partial g/\partial x$.
The gradient of the $Q$-function w.r.t the policy parameter $w$ is given by
[12]

$\displaystyle Q_{s}$
$\displaystyle=(R_{s}+{\rm\Pi}_{s}R_{a})+\gamma({\rm\Pi}_{s}F_{a}+F_{s})([\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{s}}]Q_{s}),$
$\displaystyle Q_{a}$ $\displaystyle=R_{a}+\gamma
F_{a}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{s}}]Q_{s}+\gamma[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{a}}]Q_{a},$
$\displaystyle\nabla_{w}Q_{\pi}$
$\displaystyle={\rm\Pi}_{w}Q_{a}+\gamma[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{w}}]\nabla_{w}Q_{\pi},$
(29)

where $R_{s}\in\mathbb{R}^{d_{s}|\mathcal{S}||\mathcal{A}|}$ and
$R_{a}\in\mathbb{R}^{d_{a}|\mathcal{S}||\mathcal{A}|}$ are vectors obtained
via stacking partial derivatives $r_{s}(s,a)\in\mathbb{R}^{d_{s}}$ and
$r_{a}(s,a)\in\mathbb{R}^{d_{a}}$ over $(s,a)\in\mathcal{S}\times\mathcal{A}$,
and ${\rm\Pi}_{s}={\rm
diag}(\pi_{s})\in\mathbb{R}^{d_{s}|\mathcal{S}||\mathcal{A}|\times
d_{a}|\mathcal{S}||\mathcal{A}|}$, ${\rm\Pi}_{w}={\rm
diag}(\pi_{w})\in\mathbb{R}^{d_{w}|\mathcal{S}||\mathcal{A}|\times
d_{a}|\mathcal{S}||\mathcal{A}|}$, $F_{s}={\rm
diag}(f_{s})\in\mathbb{R}^{d_{s}|\mathcal{S}||\mathcal{A}|\times
d_{s}|\mathcal{S}||\mathcal{A}|}$, and $F_{a}={\rm
diag}(f_{a})\in\mathbb{R}^{d_{a}|\mathcal{S}||\mathcal{A}|\times
d_{s}|\mathcal{S}||\mathcal{A}|}$ are Jacobian matrices. Consider GVF defined
as $G_{\pi}=[Q^{\top}_{s},Q^{\top}_{a},\nabla_{w}Q^{\top}_{\pi}]^{\top}$.
Consider the normalized setting in which ${\rm\Pi}_{s}F_{a}+F_{s}=\mathbf{I}$.
Then $G_{\pi}$ satisfies the general Bellman equation in eq. 3 with $B$ and
$M_{\pi}$ specified by

$\displaystyle B$
$\displaystyle=\left[\begin{array}[]{c}R_{s}+{\rm\Pi}_{s}R_{a}\\\ R_{a}\\\
{\rm\Pi}_{w}Q_{a}\end{array}\right],\quad
M_{\pi}=\left[\begin{array}[]{ccc}\gamma[\mathsf{P}_{\pi}\otimes\mathsf{I}_{s}]&0&0\\\
\gamma
F_{a}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{s}]&\gamma[\mathsf{P}_{\pi}\otimes\mathsf{I}_{a}]&0\\\
0&{\rm\Pi}_{w}&\gamma[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{w}}]\end{array}\right].$
(36)

We consider the setting in which $\left\|f_{a}(s,a)\right\|_{F}\leq C_{a}$ and
$\left\|\pi_{w}(s,a)\right\|_{F}\leq C_{w}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

###  B.2 Examples of Backward GVFs

The backward GVF in Definition 2 also arises in the following important RL
applications.

Case IV: Anomaly Detection. [65] has systemically discussed the application of
retrospective knowledge in anomaly detection. Let $i(s,a)$ be the cost that an
agent consumes when taking action $a$ at state $s$, and $e_{\pi}(s,a)$ be the
cost that an agent is expected to consume given the current status when
following a predefined policy $\pi$. If the actual cost of the agent deviates
too much from $e_{\pi}$, the agent may likely encounter anomalous events. For
simplicity, we consider the setting when $\gamma(s,a)=\gamma$. It can be shown
that $e_{\pi}$ satisfies the following equation

$\displaystyle e_{\pi}=i+\gamma
U^{-1}_{\pi}\mathsf{P}^{\top}_{\pi}U_{\pi}e_{\pi}.$ (37)

Clearly, eq. 37 satisfies the general backward Bellman equation in eq. 6 by
letting $B=i$, $M_{\pi}=\gamma\mathsf{P}_{\pi}$, and $\hat{G}_{\pi}=e_{\pi}$.

Case V: Gradient of Logarithmic Stationary Distributions. In the policy
parameterization setting, the gradient of logarithmic stationary distribution
$\nabla_{w}\log\mu_{\pi}(s,a)$ has been used in policy gradient estimation
[18, 56, 25] and maximum entropy exploration [11]. It has been shown in [25,
56] that $\nabla_{w}\log\mu_{\pi}(s,a)$ satisfies the following equation

$\displaystyle{\rm\Psi}_{\pi}=\nabla_{w}{\rm\Pi}_{\pi_{w}}+U^{-1}_{\pi}[\mathsf{P}_{\pi}^{\top}\otimes\mathsf{I}_{d_{w}}]U_{\pi}{\rm\Psi}_{\pi},$
(38)

where ${\rm\Psi}_{\pi}$ is obtained via stacking
$\nabla_{w}\log(\mu_{\pi}(s,a))$ over $\mathcal{S}\times\mathcal{A}$, i.e.,
$[{\rm\Psi}_{\pi}](s,a)=\nabla_{w}\log(\mu_{\pi_{w}}(s,a))$. Here,
$\nabla_{w}\log\mu_{\pi}$ can be viewed as a backward accumulation of the
signal $C(s,a)=\nabla_{w}\log(\pi(s,a))$ with the discounted factor
$\gamma=1$. Define the backward GVF as $\hat{G}_{\pi}={\rm\Psi}_{\pi}$. It is
clear that $\hat{G}_{\pi}$ satisfies the general backward Bellman equation in
eq. 6 with $B$ and $M_{\pi}$ specified by

$\displaystyle B=\nabla_{w}{\rm\Pi}_{\pi_{w}},\qquad
M_{\pi}=\mathsf{P}_{\pi}^{\top}\otimes\mathsf{I}_{d_{w}}.$ (39)

Note that since $\gamma_{\max}=1$ in the general Bellman equation in eq. 38,
the result in Proposition 1 may not hold in such a setting, i.e., GBO may not
be a contraction here. However, as we will show in appendix G, when the base
matrix ${\rm\Phi}$ satisfies the "non-constant parameterization" assumption,
we can establish results similar to Proposition 2 and Theorem 3 for the
evaluation of $\nabla_{w}\log\mu_{\pi}$.

##  Appendix C Gradient Temporal Difference Learning (GTD)

The GTD algorithm has been used for GVF evaluation in [44, 33]. So far, only
the asymptomatic convergence (not the convergence rate) has been studied in
[33]. In this section, we present the GTD algorithm for GVF evaluation and
characterize the finite-time convergence rate for GTD. We define the dimension
of parameter $\theta$ as $d_{g}=\sum_{i=1}^{k}K_{i}d_{i}$. In the sequel, we
denote the MSPBE with parameter $\theta$ as $J(\theta)$. Note that the MSPBE
in eq. 7 can be rewritten as

$\displaystyle J(\theta)$
$\displaystyle=\frac{1}{2}\left\|\mathbb{E}_{D}[g(x,\theta)]\right\|_{C^{-1}}^{2},\,\,C\triangleq\begin{cases}\mathbb{E}_{D}[(\phi(s,a)^{\top}\phi(s,a))]\quad&\text{(forward
GVF)}\\\
\textstyle{\mathbb{E}_{D}[(\phi(s^{\prime},a^{\prime})^{\top}\phi(s^{\prime},a^{\prime}))]}&\text{(backward
GVF)}\end{cases},$ (40)

where

$\displaystyle
g(x,\theta)\triangleq\begin{cases}-\phi(s,a)^{\top}(B(s,a)+m(x)\phi(s^{\prime},a^{\prime})\theta-\phi(s,a)\theta)&\text{(forward
GVF)}\\\
-\phi(s^{\prime},a^{\prime})^{\top}({B}(s^{\prime},a^{\prime})+\hat{m}(x)\phi(s,a)\theta-\phi(s^{\prime},a^{\prime})\theta)&\text{(backward
GVF)}\end{cases},$

where the matrices $m(\cdot)$ and $\hat{m}(\cdot)$ are defined in eq. 10. The
gradient of $J(\theta)$ is given as

$\displaystyle-\nabla
J(\theta)=\mathbb{E}_{D}[g(x,\theta)-h(x,\theta)],\,\,h(x,\theta)\triangleq\begin{cases}\phi(s^{\prime},a^{\prime})^{\top}m(x)\phi(s,a)w(\theta)&\text{(forward
GVF)}\\\
\textstyle{\phi(s,a)^{\top}\hat{m}(x)\phi(s^{\prime},a^{\prime})w(\theta)}&\text{(backward
GVF)}\end{cases}$

in which $w(\theta)=C^{-1}\mathbb{E}_{D}[g(x,\theta)]\in\mathbb{R}^{d_{g}}$.
Note that we can not estimate $\nabla J(\theta)$ directly due to the "double
sampling" issue, i.e., $w(\theta)$ cannot be estimated via sampling. In GTD,
an auxiliary parameter $w_{t}$ is introduced, which is updated simultaneously
with $\theta_{t}$ to approximate $w(\theta_{t})$ [41, 22]. We present the
update of GTD in Algorithm 2.

Algorithm 2 GTD

Initialize: Approximator parameters $w_{0}$, and $\theta_{0}$

for $t=0,\cdots,T-1$ do

Obtain sample $(s_{t},a_{t},B_{t},s^{\prime}_{t})\sim\mathcal{D}$ and
$a^{\prime}_{t}\sim\pi(\cdot|s^{\prime}_{t})$

$w_{t+1}=w_{t}-\beta_{t}(g(x_{t},\theta_{t})-l(x_{t},w_{t}))$

forward GVF: $l(x_{t},w_{t})=\phi(s_{t},a_{t})^{\top}\phi(s_{t},a_{t})w_{t}$

backward GVF:
$l(x_{t},w_{t})=\phi(s^{\prime}_{t},a^{\prime}_{t})^{\top}\phi(s^{\prime}_{t},a^{\prime}_{t})w_{t}$

$\theta_{t+1}={\rm\Gamma}_{R_{\theta}}\left(\theta_{t}+\alpha_{t}(g(x_{t},\theta_{t})-h(x_{t},\theta_{t}))\right)$

forward GVF:
$h(x_{t},w_{t})=\phi(s^{\prime}_{t},a^{\prime}_{t})^{\top}m(x_{t})\phi(s_{t},a_{t})w_{t}$

backward GVF:
$h(x_{t},w_{t})=\phi(s_{t},a_{t})^{\top}\hat{m}(x_{t})\phi(s^{\prime}_{t},a^{\prime}_{t})w_{t}$

end for

###  C.1 Convergence Rate of GTD

We make the following assumptions, which have also been adopted in the
convergence analysis of GTD in the canonical value function evaluation setting
[57, 55, 41, 22].

######  Assumption 1.

In both forward and backward GVF evaluation settings, the matrix $C$ in eq. 40
is non-singular.

######  Assumption 2.

We define the matrix $\hat{A}$ in the following way: (1) in the forward GVF
evaluation setting:
$\hat{A}=\mathbb{E}_{\mathcal{D}\cdot\pi}[\phi(s,a)^{\top}(m(x)\phi(s^{\prime},a^{\prime})-\phi(s,a))]$;
(2) in the backward GVF evaluation setting,
$\hat{A}=\mathbb{E}_{\mathcal{D}\cdot\pi}[\phi(s^{\prime},a^{\prime})(\hat{m}(x)\phi(s,a)-\phi(s^{\prime},a^{\prime}))]$.
We require $\hat{A}$ to be non-singular in both the forward and backward GVF
settings.

We define the optimal point $\bar{\theta}^{*}$ for GTD as

$\displaystyle\langle\nabla
J(\bar{\theta}^{*}),\theta-\bar{\theta}^{*}\rangle\geq 0,\quad\forall\theta\in
R_{\theta},$

which is the optimality condition for minimizing $J(\theta)$. The following
theorem characterizes the convergence rate of GTD to $\bar{\theta}^{*}$.

######  Theorem 3.

Consider the GTD update in Algorithm 2. In both the forward and backward GVF
evaluation settings, suppose 1-2 hold. Let the stepsize
$\alpha_{t}={\rm\Theta}(t^{-1})$ and $\beta_{t}={\rm\Theta}(t^{-1})$. We have

$\displaystyle\mathbb{E}\left[\left\|{\theta}_{T}-\bar{\theta}^{*}\right\|_{2}^{2}\right]\leq\mathcal{O}\left(\frac{\left\|\theta_{0}-\bar{\theta}^{*}\right\|_{2}^{2}}{T^{2}}\right)+\mathcal{O}\left(\frac{1}{\lambda_{G}^{\prime
2}T}\right),$

where $\lambda^{\prime}_{G}>0$ is the conditional number of GTD defined in eq.
124 of Appendix H.

Theorem 1 shows that GTD converges to the globally optimal point
$\bar{\theta}^{*}$ at a rate of $\mathcal{O}(1/T)$. The convergence speed of
$\theta_{t}$ depends on the conditional number $\lambda^{\prime}_{G}$, which
decreases as $\lambda^{\prime}_{G}$ decreases. Differently from the
conditional number $\lambda_{G}$ of GenTD, which has a guaranteed lower bound
from zero as given in Proposition 2, there exists no guaranteed lower bound
for $\lambda^{\prime}_{G}$ even in the canonical value function evaluation
setting. Thus, the converge speed of GTD could be very slow as
$\lambda^{\prime}_{G}$ could be arbitrarily small.

###  C.2 Global Optimum of GTD and Proof of Example 1

For simplicity, we consider scenarios when the function approximation class
$\mathcal{F}_{\rm\Phi}$ is complete. We show that the global optimum of GTD
exhibits very different properties in the forward and backward GVF evaluation
settings.

We first show that in the forward GVF evaluation setting, the global optimum
${\rm\Phi}\bar{\theta}^{*}$ of GTD equals the ground truth GVF. Since the
function space $\mathcal{F}_{\rm\Phi}$ is complete, there exists a parameter
$\theta_{\text{true}}\in R_{\theta}$ such that
${\rm\Phi}\theta_{\text{true}}=G_{\pi}$, which implies
$J(\theta_{\text{true}})=0$. Since $J(\theta)\geq 0$ for all $\theta\in
R_{\theta}$ and $J(\theta)$ is strongly-convex, $J(\theta)=0$ if and only if
$\theta=\bar{\theta}^{*}$, which implies
$\theta_{\text{true}}=\bar{\theta}^{*}$.

In the backward GVFs evaluation setting, we provide an example (see Example 1
in Section 4) to show that GTD can fail to learn the ground truth $G_{\pi}$
even if the function class $\mathcal{F}_{\rm\Phi}$ is complete. We next
present the proof for such an example.

###### Proof of Example 1.

The backward value function can be obtained as follows

$\displaystyle\bar{V}=U^{-1}(I-\gamma\mathsf{P}^{\top})^{-1}\mathsf{P}^{\top}UR=[8.1555,9.0389,9.0184]^{\top}.$

The fixed point of GTD is given by

$\displaystyle\bar{\theta}^{*}=\bar{A}^{-1}\bar{b},$

where

$\displaystyle\bar{A}=\gamma{\rm\Phi}^{\top}\mathsf{P}^{\top}\bar{D}^{\prime}{\rm\Phi}-{\rm\Phi}^{\top}\bar{D}^{\prime}{\rm\Phi},\qquad\bar{b}={\rm\Phi}^{\top}\mathsf{P}^{\top}\bar{D}R,$
(41)

where $\bar{D}=\text{diag}(D)$, $\bar{D}^{\prime}=\text{diag}(D^{\prime})$ and
$D^{\prime\top}=D^{\top}P$. Also note that the base matrix
${\rm\Phi}=[8.1555,9.0389,9.0184]^{\top}$ and the off-policy sampling
distribution $D=[1/3,1/3,1/3]^{\top}$. We can obtain

$\displaystyle\bar{A}=-9.9422,\qquad\bar{b}=5.9904,$

which implies

$\displaystyle\bar{\theta}^{*}=\frac{-b}{A}=0.6025.$ (42)

Note that the perfect base matrix $[8.1555,9.0389,9.0184]^{\top}$ can fully
represent $\bar{V}_{\pi}$, with parameter $\theta_{\text{true}}=1$. However,
eq. 42 shows that the global optimum of GTD
$\bar{\theta}^{*}\neq\theta_{\text{true}}$, which introduces a non-zero
approximation error:

$\displaystyle\left\|{\rm\Phi}\bar{\theta}^{*}-\bar{V}\right\|_{D}=3.7848.$

∎

The above example demonstrates a drawback of GTD, which can fail to learn the
ground truth $G_{\pi}$ even if the function class $\mathcal{F}_{\rm\Phi}$ is
complete. Such an issue does not occur for the GenTD algorithm proposed in
this paper, which converges to the ground truth as guaranteed by Theorem 2 in
Section 4.

##  Appendix D Proofs of Propositions 1 and 2

###  D.1 Supporting Lemmas

We provide the following lemmas, which are useful for the proofs of
Propositions 1 and 2.

######  Lemma 1.

For any $v\in\mathbb{R}^{d|\mathcal{S}||\mathcal{A}|}$,we have
$\left\|[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d}]v\right\|_{U_{\pi}}\leq\left\|v\right\|_{U_{\pi}}$.

###### Proof.

Consider the square of
$\left\|[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d}]v\right\|_{U_{\pi}}$. We have

$\displaystyle\left\|[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d}]v\right\|_{U_{\pi}}^{2}$
$\displaystyle=v^{\top}[\mathsf{P}^{\top}_{\pi}\otimes\mathsf{I}_{d}]U_{\pi}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d}]v$
$\displaystyle=\sum_{i=1}^{|\mathcal{S}||\mathcal{A}|}\mu_{\pi}(i)\left\|\sum_{j=1}^{|\mathcal{S}||\mathcal{A}|}\mathsf{P}_{\pi}(j|i)v_{j}\right\|_{2}^{2}$
$\displaystyle\leq\sum_{i=1}^{|\mathcal{S}||\mathcal{A}|}\mu_{\pi}(i)\sum_{j=1}^{|\mathcal{S}||\mathcal{A}|}\mathsf{P}_{\pi}(j|i)\left\|v_{j}\right\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{|\mathcal{S}||\mathcal{A}|}\sum_{j=1}^{|\mathcal{S}||\mathcal{A}|}\mu_{\pi}(i)\mathsf{P}_{\pi}(j|i)\left\|v_{j}\right\|_{2}^{2}$
$\displaystyle=\sum_{j=1}^{|\mathcal{S}||\mathcal{A}|}\mu_{\pi}(i)\left\|v_{j}\right\|_{2}^{2}$
$\displaystyle=\left\|v\right\|_{U_{\pi}}^{2},$

where the first inequality follows from Jensen’s inequality and the fourth
equality follows from the property of the stationary distribution
$\mu^{\top}_{\pi}\mathsf{P}_{\pi}=\mu^{\top}_{\pi}$. ∎

We provide the follow lemma to characterize a similar property in backward GVF
evaluation setting.

######  Lemma 2.

For any $v\in\mathbb{R}^{d|\mathcal{S}||\mathcal{A}|}$,we have
$\left\|U^{-1}_{\pi}[\mathsf{P}^{\top}_{\pi}\otimes\mathsf{I}_{d}]U_{\pi}v\right\|_{U_{\pi}}\leq\left\|v\right\|_{U_{\pi}}$.

###### Proof.

Consider the square of
$\left\|U^{-1}_{\pi}[\mathsf{P}^{\top}_{\pi}\otimes\mathsf{I}_{d}]U_{\pi}v\right\|_{U_{\pi}}$.
We have

$\displaystyle\left\|U^{-1}_{\pi}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d}]U_{\pi}v\right\|_{U_{\pi}}^{2}$
$\displaystyle=v^{\top}[U^{-1}_{\pi}[\mathsf{P}^{\top}_{\pi}\otimes\mathsf{I}_{d}]U_{\pi}]^{\top}U_{\pi}[U^{-1}_{\pi}[\mathsf{P}^{\top}_{\pi}\otimes\mathsf{I}_{d}]U_{\pi}]v$
$\displaystyle=\sum_{j=1}^{|\mathcal{S}||\mathcal{A}|}\mu_{\pi}(j)\left\|\sum_{i=1}^{|\mathcal{S}||\mathcal{A}|}\frac{\mu_{\pi}(i)\mathsf{P}_{\pi}(j|i)}{\mu_{\pi}(j)}v(i)\right\|_{2}^{2}$
$\displaystyle\leq\sum_{j=1}^{|\mathcal{S}||\mathcal{A}|}\mu_{\pi}(j)\sum_{i=1}^{|\mathcal{S}||\mathcal{A}|}\frac{\mu_{\pi}(i)\mathsf{P}_{\pi}(j|i)}{\mu_{\pi}(j)}\left\|v(i)\right\|_{2}^{2}$
$\displaystyle=\sum_{j=1}^{|\mathcal{S}||\mathcal{A}|}\mu_{\pi}(i)\left\|v(i)\right\|_{2}^{2}\sum_{i=1}^{|\mathcal{S}||\mathcal{A}|}\mathsf{P}_{\pi}(j|i)$
$\displaystyle=\sum_{j=1}^{|\mathcal{S}||\mathcal{A}|}\mu_{\pi}(i)\left\|v(i)\right\|_{2}^{2}$
$\displaystyle=\left\|v\right\|_{U_{\pi}}^{2},$

where the first inequality follows from the Jensen’s inequality. ∎

###  D.2 Proof of Proposition 1

We first consider the forward GBO setting. Recall the following definition of
GBO $\mathcal{T}_{G,\pi}$ in eq. 3

$\displaystyle G_{\pi}=\mathcal{T}_{G,\pi}G_{\pi}=B+M_{\pi}G_{\pi},$

where

$\displaystyle B=\left[\begin{array}[]{c}B_{1}\\\ B_{2}\\\ \vdots\\\
B_{k}\end{array}\right],\quad
M_{\pi}=\left[\begin{array}[]{cccc}\gamma_{1}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{1}}]&0&\cdots&0\\\
A_{2,1}&\gamma_{2}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{2}}]&\cdots&0\\\
\vdots&\vdots&&\vdots\\\
A_{k,1}&A_{k,2}&\cdots&\gamma_{k}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{k}}]\end{array}\right].$

Let
${G}^{\prime}_{\pi},{G}^{\prime\prime}_{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\sum_{i=1}^{k}K_{i}d_{i}}$
be two vectors, and let $\Delta_{G}=[\Delta_{1},\cdots,\Delta_{k}]$, where
$\Delta_{i}=G^{\prime}_{\pi,i}-G^{\prime\prime}_{\pi,i}$. We have

$\displaystyle\mathcal{T}_{\pi}G_{\pi}^{\prime}-\mathcal{T}_{\pi}G^{\prime\prime}_{\pi}=M_{\pi}\Delta_{G}=\left[\begin{array}[]{c}\gamma_{1}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{1}}]\Delta_{1}\\\
A_{2,1}\Delta_{1}+\gamma_{2}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{2}}]\Delta_{2}\\\
\vdots\\\
\sum_{j=1}^{k-1}A_{k,j}\Delta_{j}+\gamma_{k}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{k}}]\Delta_{k}\end{array}\right].$
(47)

Recall that $A_{i,j}$ is bounded for all $i,j$. Thus, there exists a constant
$0<C_{A}<\infty$ such that $\left\|A_{i,j}\right\|_{U_{\pi}}\leq C_{A}$ for
all $i,j$. Without loss of generality, we assume $C_{A}>1$. Let $\alpha$ be
the solution of the following matrix function

$\displaystyle Fx=f,$ (48)

where $F\in\mathbb{R}^{k\times k}$ and $f\in\mathbb{R}^{k}$ are specified as

$\displaystyle
F=\left[\begin{array}[]{cccccc}-\frac{1-\gamma}{2}&C_{A}&C_{A}&\cdots&C_{A}&C_{A}\\\
0&-\frac{1-\gamma}{2}&C_{A}&\cdots&C_{A}&C_{A}\\\ \vdots&\vdots&&\vdots\\\
0&0&0&\cdots&-\frac{1-\gamma}{2}&C_{A}\\\
1&1&1&\cdots&1&1\end{array}\right],\qquad f=\left[\begin{array}[]{c}0\\\ 0\\\
\vdots\\\ 0\\\ 1\end{array}\right].$

It can be checked that the solution of eq. 48 is strictly positive, i.e., if
$F\alpha=f$, then we have $\alpha_{l}>0$ for $1\leq l\leq k$. Recalling the
definition of $\left\|\cdot\right\|_{\mu_{\pi},\alpha}$– norm, we have

$\displaystyle\left\|M_{\pi}\Delta_{G}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle=\gamma_{1}\alpha_{1}\left\|[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{1}}]\Delta_{1}\right\|_{\mu_{\pi}}+\alpha_{2}\left\|A_{2,1}\Delta_{1}+\gamma_{2}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{2}}]\Delta_{2}\right\|_{\mu_{\pi}}$
$\displaystyle\quad+\cdots+\alpha_{k}\left\|\sum_{j=1}^{k-1}A_{k,j}\Delta_{j}+\gamma_{k}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{k}}]\Delta_{k}\right\|_{\mu_{\pi}}$
$\displaystyle\leq\gamma_{1}\alpha_{1}\left\|[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{1}}]\Delta_{1}\right\|_{\mu_{\pi}}+\alpha_{2}\left\|A_{2,1}\Delta_{1}\right\|_{\mu_{\pi}}+\cdots+\alpha_{k}\left\|A_{k,1}\Delta_{1}\right\|_{\mu_{\pi}}$
$\displaystyle\quad+\gamma_{2}\alpha_{2}\left\|[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{2}}]\Delta_{2}\right\|_{\mu_{\pi}}+\alpha_{3}\left\|A_{3,2}\Delta_{2}\right\|_{\mu_{\pi}}+\cdots+\alpha_{k}\left\|A_{k,2}\Delta_{2}\right\|_{\mu_{\pi}}$
$\displaystyle\quad+\cdots$
$\displaystyle\quad+\gamma_{k}\alpha_{k}\left\|[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{k}}]\Delta_{k}\right\|_{\mu_{\pi}}$
$\displaystyle\leq\left(\gamma\alpha_{1}+C_{A}\sum_{i=2}^{k}\alpha_{i}\right)\left\|\Delta_{1}\right\|_{\mu_{\pi}}+\left(\gamma\alpha_{2}+C_{A}\sum_{i=3}^{k}\alpha_{i}\right)\left\|\Delta_{2}\right\|_{\mu_{\pi}}+\cdots+\gamma\alpha_{k}\left\|\Delta_{k}\right\|_{\mu_{\pi}}$
$\displaystyle\leq\frac{1+\gamma}{2}\alpha_{1}\left\|\Delta_{1}\right\|_{\mu_{\pi}}+\frac{1+\gamma}{2}\alpha_{2}\left\|\Delta_{2}\right\|_{\mu_{\pi}}+\cdots+\gamma\alpha_{k}\left\|\Delta_{k}\right\|_{\mu_{\pi}}$
$\displaystyle\leq\frac{1+\gamma}{2}\left(\sum_{i=1}^{k}\alpha_{i}\left\|\Delta_{i}\right\|_{\mu_{\pi}}\right)$
$\displaystyle=\frac{1+\gamma}{2}\left\|\Delta_{G}\right\|_{\mu_{\pi},\alpha},$
(49)

where the first inequality follows from the triangle inequality, the second
inequality follows from the fact that $A_{i,j}$ is bounded and Lemma 1, and
the third inequality follows from the definition of $\gamma$ and the fact that
$\alpha$ is the solution of eq. 48. Obviously, eq. 49 implies the following
property,

$\displaystyle\left\|\mathcal{T}_{\pi}G^{\prime}_{\pi}-\mathcal{T}_{\pi}G^{\prime\prime}_{\pi}\right\|_{\mu_{\pi},\alpha}\leq\frac{1+\gamma}{2}\left\|G^{\prime}_{\pi}-G^{\prime\prime}_{\pi}\right\|_{\mu_{\pi},\alpha},$

which completes the proof in the forward GBO evaluation setting.

We next consider the backward GBO setting, where $\hat{\mathcal{T}}_{G,\pi}$
is defined in eq. 5. Following steps similar to those from eq. 47 – eq. 49, we
can obtain

$\displaystyle\left\|\hat{\mathcal{T}}_{\pi}G_{\pi}-\hat{\mathcal{T}}_{\pi}G^{\prime}_{\pi}\right\|_{\mu_{\pi},\alpha}=\left\|M_{\pi}\Delta_{G}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle=\gamma_{1}\alpha_{1}\left\|U^{-1}_{\pi,1}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{1}}]U_{\pi,1}\Delta_{1}\right\|_{\mu_{\pi}}+\alpha_{2}\left\|A_{2,1}\Delta_{1}+\gamma_{2}U^{-1}_{\pi,2}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{2}}]U_{\pi,2}\Delta_{2}\right\|_{\mu_{\pi}}+\cdots$
$\displaystyle\quad+\alpha_{k}\left\|\sum_{j=1}^{k-1}A_{k,j}\Delta_{j}+\gamma_{k}U^{-1}_{\pi,k}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{k}}]U_{\pi,k}\Delta_{k}\right\|_{\mu_{\pi}}$
$\displaystyle\leq\gamma_{1}\alpha_{1}\left\|U^{-1}_{\pi,1}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{1}}]U_{\pi,1}\Delta_{1}\right\|_{\mu_{\pi}}+\alpha_{2}\left\|A_{2,1}\Delta_{1}\right\|_{\mu_{\pi}}+\cdots+\alpha_{k}\left\|A_{k,1}\Delta_{1}\right\|_{\mu_{\pi}}$
$\displaystyle\quad+\gamma_{2}\alpha_{2}\left\|U^{-1}_{\pi,2}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{2}}]U_{\pi,2}\Delta_{2}\right\|_{\mu_{\pi}}+\alpha_{3}\left\|A_{3,2}\Delta_{2}\right\|_{\mu_{\pi}}+\cdots+\alpha_{k}\left\|A_{k,2}\Delta_{2}\right\|_{\mu_{\pi}}$
$\displaystyle\quad+\cdots$
$\displaystyle\quad+\gamma_{k}\alpha_{k}\left\|U^{-1}_{\pi,k}[\mathsf{P}_{\pi}\otimes\mathsf{I}_{d_{k}}]U_{\pi,k}\Delta_{k}\right\|_{\mu_{\pi}}$
$\displaystyle\leq\left(\gamma\alpha_{1}+C\sum_{i=2}^{k}\alpha_{i}\right)\left\|\Delta_{1}\right\|_{\mu_{\pi}}+\left(\gamma\alpha_{2}+C\sum_{i=3}^{k}\alpha_{i}\right)\left\|\Delta_{2}\right\|_{\mu_{\pi}}+\cdots+\gamma\alpha_{k}\left\|\Delta_{k}\right\|_{\mu_{\pi}}$
$\displaystyle\leq\frac{1+\gamma}{2}\alpha_{1}\left\|\Delta_{1}\right\|_{\mu_{\pi}}+\frac{1+\gamma}{2}\alpha_{2}\left\|\Delta_{2}\right\|_{\mu_{\pi}}+\cdots+\gamma\alpha_{k}\left\|\Delta_{k}\right\|_{\mu_{\pi}}$
$\displaystyle\leq\frac{1+\gamma}{2}\left(\sum_{i=1}^{k}\alpha_{i}\left\|\Delta_{i}\right\|_{\mu_{\pi}}\right)$
$\displaystyle=\frac{1+\gamma}{2}\left\|\Delta_{G}\right\|_{\mu_{\pi},\alpha},$
(50)

where the first inequality follows from the triangle inequality, the second
inequality follows from the fact that $A_{i,j}$ is bounded and Lemma 2, and
the third inequality follows from the definition of $\gamma$ and the fact that
$\alpha$ is the solution of eq. 48. Equation 50 implies the following

$\displaystyle\left\|\hat{\mathcal{T}}_{\pi}G^{\prime}_{\pi}-\hat{\mathcal{T}}_{\pi}G^{\prime\prime}_{\pi}\right\|_{\mu_{\pi},\alpha}\leq\frac{1+\gamma}{2}\left\|G_{\pi}^{\prime}-G^{\prime\prime}_{\pi}\right\|_{\mu_{\pi},\alpha},$

which completes the proof in the backward GBO evaluation setting.

###  D.3 Proof of Proposition 2

We first consider the forward GFV setting. Recall the linear function
approximation of $G_{\pi}$ is given by

$\displaystyle G(\theta)={\rm\Phi}\theta,$

where

$\displaystyle{\rm\Phi}=\left[\begin{array}[]{cccc}{\rm\Phi}_{1}\otimes\mathsf{I}_{d_{1}}&0&\cdots&0\\\
0&{\rm\Phi}_{2}\otimes\mathsf{I}_{d_{2}}&\cdots&0\\\ \vdots&\vdots&&\vdots\\\
0&0&\cdots&{\rm\Phi}_{k}\otimes\mathsf{I}_{d_{k}}\end{array}\right],\quad\theta=\left[\begin{array}[]{c}\text{vec}(\theta_{1}^{\top})\\\
\text{vec}(\theta^{\top}_{2})\\\ \vdots\\\
\text{vec}(\theta^{\top}_{k})\end{array}\right].$

Folloing the definition of $g(\theta)$ in eq. 9, we have

$\displaystyle-g(\theta)$
$\displaystyle={\rm\Phi}^{\top}U_{\pi}(\mathcal{T}_{G,\pi}G(\theta)-G(\theta))$
$\displaystyle={\rm\Phi}^{\top}U_{\pi}((M_{\pi}-I){\rm\Phi}\theta+B)$
$\displaystyle=G\theta+g,$

where $G={\rm\Phi}^{\top}U_{\pi}(M_{\pi}-I){\rm\Phi}$ and
$g={\rm\Phi}^{\top}U_{\pi}B$. Since the monotonicity depends only on the
matrix $G$, we next proceed to show that $G$ is Hurwitz. For the matrix $G$,
we have

$\displaystyle G$
$\displaystyle={\rm\Phi}^{\top}U_{\pi}(M_{\pi}-I){\rm\Phi}=\left[\begin{array}[]{cccc}A_{1}&0&\cdots&0\\\
N_{2,1}&A_{2}&\cdots&0\\\ \vdots&\vdots\\\
N_{k,1}&N_{k,2}&\cdots&A_{k}\end{array}\right],$ (55)

where
$A_{i}=[{\rm\Phi}_{i}^{\top}U_{\pi,i}(\gamma_{i}\mathsf{P}_{\pi}-I){\rm\Phi}_{i}]\otimes\mathsf{I}_{d_{i}}$
and $N_{i,j}$ is a matrix that depends on ${\rm\Phi}_{i}$, ${\rm\Phi}_{j}$,
$\mathsf{P}_{\pi}$ and $\mu_{\pi}$. We have the following equations hold:

$\displaystyle\text{eig}(G)$
$\displaystyle=\\{\text{eig}(A_{1}),\cdots,\text{eig}(A_{k})\\},$ (56)
$\displaystyle\text{eig}(A_{i})$
$\displaystyle=\text{eig}({\rm\Phi}_{i}^{\top}U_{\pi,i}(\gamma_{i}\mathsf{P}_{\pi}-I){\rm\Phi}_{i}),$
(57)
$\displaystyle\max\\{\text{eig}({\rm\Phi}_{i}^{\top}U_{\pi,i}(\gamma_{i}\mathsf{P}_{\pi}-I){\rm\Phi}_{i})\\}$
$\displaystyle=-(1-\gamma)\zeta_{i},$ (58)

where $\zeta_{i}$ is defined in Proposition 2, the first equation follows
because the eigenvalue of a matrix is determined by the eigenvalues of its
diagonal block matrices [13], the second equation follows from the fact that
$\text{eig}(M\otimes\mathsf{I}_{d})=\text{eig}(M)$ for any matrix $M$ and
positive integer $d$, and the last follows from [2, Lemma 1, Lemma 3].
Combining eq. 56–(58), we can obtain equation

$\displaystyle\max\\{\text{eig}(G)\\}\leq-(1-\gamma)\min_{i}\zeta_{i}=-\lambda_{G}<0,$
(59)

which completes the proof in the forward GVF setting.

We next consider the backward GVF setting. Following the steps similar to
those for deriving eq. 55, we can obtain $-g(\theta)=\hat{G}\theta+\hat{g}$,
where $\hat{g}={\rm\Phi}^{\top}P^{\top}_{\pi}U_{\pi}B$. For the matrix
$\hat{G}$, we have

$\displaystyle\hat{G}={\rm\Phi}^{\top}P_{\pi}^{\top}(\hat{M}_{\pi}-I)U_{\pi}{\rm\Phi}=\left[\begin{array}[]{cccc}\hat{A}_{1}&0&\cdots&0\\\
\hat{N}_{2,1}&\hat{A}_{2}&\cdots&0\\\ \vdots&\vdots\\\
\hat{N}_{k,1}&\hat{N}_{k,2}&\cdots&\hat{A}_{k}\end{array}\right],$ (64)

where
$\hat{A}_{i}=[{\rm\Phi}_{i}^{\top}(\gamma_{i}\mathsf{P}^{\top}_{\pi}-I)U_{\pi,i}{\rm\Phi}_{i}]\otimes\mathsf{I}_{d_{i}}$
and $\hat{N}_{i,j}$ is a matrix that depends on ${\rm\Phi}_{i}$,
${\rm\Phi}_{j}$, $\mathsf{P}_{\pi}$ and $\mu_{\pi}$. Following the steps
similar to those in eq. 56–(59) and using the result in the verification of
[65, item (c) in Assumption 2], we have

$\displaystyle\max\\{\text{eig}(G)\\}\leq-(1-\gamma)\min_{i}\zeta_{i}=-\lambda_{G}<0,$

which completes the proof in the backward GVF setting.

##  Appendix E Proof of Theorem 1

###  E.1 Supporting Lemmas

We first develop the property for the update of $w_{\rho}$ in Algorithm 1.
Given a sample $(s_{t},a_{t},B_{t},s^{\prime}_{t})\sim\mathcal{D}$ and
$a^{\prime}_{t}\sim\pi(\cdot|s^{\prime}_{t})$, we introduce the following
definitions.

$\displaystyle P_{t}$
$\displaystyle=\left[\begin{array}[]{ccc}\psi_{t}^{\top}\psi_{t}&(\psi_{t}-\psi^{\prime}_{t})\psi^{\top}_{t}&0\\\
-\psi_{t}(\psi^{\top}_{t}-\psi^{\prime\top}_{t})&0&\psi_{t}\\\
0&-\psi^{\top}_{t}&1\end{array}\right],\qquad
p_{t}=\left[\begin{array}[]{c}0\\\ 0\\\ 1\end{array}\right].$ (71)

Consider the matrix $P_{t}$ and vector $p_{t}$, we have the following holds

$\displaystyle\left\|P_{t}\right\|_{F}^{2}$
$\displaystyle=\left\|\psi_{t}^{\top}\psi_{t}\right\|_{F}^{2}+2\left\|(\psi_{t}-\psi^{\prime}_{t})\psi^{\top}_{t}\right\|_{F}^{2}+2\left\|\psi_{t}\right\|_{F}^{2}+1$
$\displaystyle\leq 9C^{4}_{\psi}+2C^{2}_{\psi}+1,$ (72)

where $C_{\psi}$ is the upper bound on the feature fector $\psi(\cdot)$, i.e.,
$\left\|\psi(s,a)\right\|_{2}\leq C_{\psi}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$, which implies
$\left\|P_{t}\right\|_{F}\leq C_{P}$, where

$\displaystyle C_{P}=\sqrt{9C^{4}_{\psi}+2C^{2}_{\psi}+1}.$ (73)

For the vector $p_{t}$, it can be checked easily that
$\left\|p_{t}\right\|_{2}\leq 1$.

We also define $P=\mathbb{E}_{\mathcal{D}\cdot\pi}[P_{t}]$ and
$p=\mathbb{E}_{\mathcal{D}\cdot\pi}[p_{t}]$, i.e.,

$\displaystyle P$
$\displaystyle=\left[\begin{array}[]{ccc}\mathbb{E}_{\mathcal{D}\cdot\pi}[\psi^{\top}\psi]&\mathbb{E}_{\mathcal{D}\cdot\pi}[(\psi-\psi^{\prime})\psi^{\top}]&0\\\
-\mathbb{E}_{\mathcal{D}\cdot\pi}[\psi(\psi^{\top}-\psi^{\prime\top})]&0&\mathbb{E}_{\mathcal{D}\cdot\pi}[\psi]\\\
0&-\mathbb{E}_{\mathcal{D}\cdot\pi}[\psi^{\top}]&1\end{array}\right],\qquad
p=\left[\begin{array}[]{c}0\\\ 0\\\ 1\end{array}\right].$ (80)

Note that

$\displaystyle\left[\begin{array}[]{c}\nabla_{w_{f}}L(\hat{\rho},\hat{f},\eta)\\\
\nabla_{w_{\rho}}L(\hat{\rho},\hat{f},\eta)\\\
\nabla_{\eta}L(\hat{\rho},\hat{f},\eta)\end{array}\right]=-(P\kappa+p).$

It has been shown in [62, Theorem 2] that the real parts of all eigenvalues of
$P$ are strictly positive, which guarantees that there exists a positive
constant $\lambda_{P}$ such that

$\displaystyle\langle
Px,x\rangle\geq\lambda_{P}\left\|x\right\|_{2}^{2}\quad\text{for all}\quad
x\in\mathbb{R}^{2d_{\rho}}.$ (81)

We also define
$\kappa_{t}=[w_{f,t}^{\top},w_{\rho,t}^{\top},\eta_{t}]^{\top}$. The update of
density ratio learning can be rewritten as

$\displaystyle\kappa_{t+1}=\kappa_{t}-\beta_{t}\zeta(x_{t},\kappa_{t}),$

where $\zeta(x_{t},\kappa_{t})=P_{t}\kappa_{t}+p_{t}$. We also define the
population update as
$\zeta(\kappa_{t})=\mathbb{E}_{D\cdot\pi}[\zeta(x,\kappa_{t})]=P\kappa_{t}+p$.
Without loss of generality, we assume that there exists a positive constant
$C_{\kappa}$ such that $\left\|\kappa^{*}\right\|_{2}\leq C_{\kappa}$, where
$\kappa^{*}$ is the global optimum of the density ratio learning defined as

$\displaystyle\langle\zeta(\kappa^{*}),\kappa-\kappa^{*}\rangle\leq
0,\quad\forall\kappa\in\mathbb{R}^{d_{\rho}}\times R_{\rho}\times\mathbb{R}.$
(82)

The following lemma, often referred to as the "three-points" lemma,
characterizes the incremental updating progress of $\kappa_{t}$ with
projection, a proof of which can be found in [20, Lemma 3.1].

######  Lemma 3.

Consider the update of $w_{f,t}$, $w_{{\rho,t}}$ and $\eta_{t}$ in Algorithm
1. For all $\kappa\in\mathbb{R}^{M}\times R_{\rho}\times\mathbb{R}$, we have
the following holds

$\displaystyle\beta_{t}\langle\zeta(x_{t},\kappa_{t}),\kappa_{t+1}-\kappa\rangle+\frac{1}{2}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}^{2}\leq\frac{1}{2}\left\|\kappa_{t}-\kappa\right\|_{2}^{2}-\frac{1}{2}\left\|\kappa_{t+1}-\kappa\right\|_{2}^{2}.$
(83)

Similarly to Lemma 3, we also have the following "three-points lemma" for the
iteration of $\theta_{t}$.

######  Lemma 4.

Consider the update of $\theta_{t}$ in Algorithm 1. For all $\theta\in
R_{\theta}$, we have the following holds

$\displaystyle-\alpha_{t}\langle\hat{\rho}(x_{t},w_{\rho,t})g(x_{t},\theta_{t}),\theta_{t+1}-\theta\rangle+\frac{1}{2}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}^{2}\leq\frac{1}{2}\left\|\theta_{t}-\theta\right\|_{2}^{2}-\frac{1}{2}\left\|\theta_{t+1}-\theta\right\|_{2}^{2},$
(84)

where $\hat{\rho}(x_{t},w_{\rho,t})$ is defined in eq. 10.

The following lemma characterizes the smoothness of $\zeta(\cdot)$.

######  Lemma 5.

For any $\kappa,\kappa^{\prime}\in\mathbb{R}^{d_{\rho}}\times
R_{\rho}\times\mathbb{R}$, we have

$\displaystyle\left\|\zeta(\kappa)-\zeta(\kappa^{\prime})\right\|_{2}\leq
C_{P}\left\|\kappa-\kappa^{\prime}\right\|_{2},$

where $C_{P}$ is defined in eq. 73.

###### Proof.

Recalling the definition of $\zeta(\kappa)=P\kappa+p$, we can obtain the
following

$\displaystyle\left\|\zeta(\kappa)-\zeta(\kappa^{\prime})\right\|_{2}=\left\|P(\kappa-\kappa^{\prime})\right\|_{2}\leq\left\|P\right\|_{2}\left\|\kappa-\kappa^{\prime}\right\|_{2}\leq
C_{P}\left\|\kappa-\kappa^{\prime}\right\|_{2},$

which completes the proof. ∎

Similarly, the following lemma characterizes the smoothness of
$g(\theta)=\mathbb{E}_{\mu_{\pi}}[g(x,\theta)]$.

######  Lemma 6.

In both the forward and backward GVF evaluation settings, for any
$\theta,\theta^{\prime}\in\mathbb{R}^{d_{\rho}}$, we have

$\displaystyle\left\|g(\theta)-g(\theta^{\prime})\right\|_{2}\leq
C_{g}\left\|\theta-\theta^{\prime}\right\|_{F},$

where $C_{g}=(d_{g}C_{\phi}C_{m}+1)C_{\phi}$.

###### Proof.

First consider the forward GVF evaluation setting. Recall the definition of
$g(\theta)$ and $x=(s,a,s^{\prime},a^{\prime})$, we have

$\displaystyle
g(\theta)=\mathbb{E}_{\mu_{\pi}}[\phi(s,a)^{\top}(B(x)+m(x)\phi(s^{\prime},a^{\prime})\theta-\phi(s,a)\theta)],$

which implies

$\displaystyle\left\|g(\theta)-g(\theta^{\prime})\right\|_{2}$
$\displaystyle=\left\|\mathbb{E}_{\mu_{\pi}}[\phi(s,a)(m(x)\phi(s^{\prime},a^{\prime})(\theta-\theta^{\prime})+\phi(s,a)(\theta^{\prime}-\theta))]\right\|_{2}$
$\displaystyle\leq\mathbb{E}_{\mu_{\pi}}[(\left\|\phi(s,a)\right\|_{F}\left\|m(x)\right\|_{F}+1)\left\|\theta^{\prime}-\theta\right\|_{2}\left\|\phi(s,a)\right\|_{F}]$
$\displaystyle\leq C_{g}\left\|\theta-\theta^{\prime}\right\|_{2}.$ (85)

Following the steps similar to those in eq. 85, we can also prove that
$\left\|g(\theta)-g(\theta^{\prime})\right\|_{2}\leq
C_{g}\left\|\theta-\theta^{\prime}\right\|_{F}$ holds in the backward GVF
evaluation setting. ∎

The following lemma characterizes the monotonicity of $\zeta(\cdot)$.

######  Lemma 7.

We have the following holds

$\displaystyle\langle\zeta(\kappa),\kappa-\kappa^{*}\rangle\geq\lambda_{P}\left\|\kappa-\kappa^{*}\right\|_{2}^{2},\quad\forall\kappa\in\mathbb{R}^{d_{\rho}}\times
R_{\rho}\times\mathbb{R}.$

###### Proof.

Recall that $P$ is strictly positive defined (eq. 81). We have

$\displaystyle\langle\zeta(\kappa),\kappa-\kappa^{*}\rangle$
$\displaystyle=\langle\zeta(\kappa^{*}),\kappa-\kappa^{*}\rangle+\langle\zeta(\kappa)-\zeta(\kappa^{*}),\kappa-\kappa^{*}\rangle$
$\displaystyle\geq\langle\zeta(\kappa)-\zeta(\kappa^{*}),\kappa-\kappa^{*}\rangle$
$\displaystyle=\langle P(\kappa-\kappa^{*}),\kappa-\kappa^{*}\rangle$
$\displaystyle\geq\lambda_{P}\left\|\kappa-\kappa^{*}\right\|_{2}^{2},$ (86)

which completes the proof. ∎

The next lemma bounds the per-iteration variance of the update of
$\kappa_{t}$.

######  Lemma 8.

Given a sample $(s_{t},a_{t},B_{t},s^{\prime}_{t})\sim\mathcal{D}_{d}$ and
$a^{\prime}_{t}\sim\pi(\cdot|s^{\prime}_{t})$ and any
$\kappa\in\mathbb{R}^{d_{\rho}}\times R_{\rho}\times\mathbb{R}$, we have the
following holds

$\displaystyle\left\|\zeta(x_{t},\kappa)-\zeta(\kappa)\right\|_{2}^{2}\leq
8C^{2}_{P}\left\|\kappa-\kappa^{*}\right\|_{2}^{2}+8C^{2}_{P}C^{2}_{\kappa}.$

###### Proof.

Recalling the definitions of $\zeta(x_{t},\kappa)=P_{t}\kappa+p_{t}$ and
$\zeta(\kappa)=P\kappa+p$, we can obtain the following

$\displaystyle\left\|\zeta(x_{t},\kappa)-\zeta(\kappa)\right\|_{2}^{2}$
$\displaystyle=\left\|(P_{t}-P)\kappa\right\|_{2}^{2}=2\left\|(P_{t}-P)(\kappa-\kappa^{*})\right\|_{2}^{2}+2\left\|(P_{t}-P)\kappa^{*}\right\|_{2}^{2}$
$\displaystyle\leq
8C^{2}_{P}\left\|\kappa-\kappa^{*}\right\|_{2}^{2}+8C^{2}_{P}C^{2}_{\kappa}.$

∎

The following lemma bounds the norm of the stochastic update $g(x,\theta)$ and
the per-iteration variance of GenTD update with density ratio $\rho(s,a)$.

######  Lemma 9.

Given a sample $(s_{t},a_{t},B_{t},s^{\prime}_{t})\sim\mathcal{D}$ and
$a^{\prime}_{t}\sim\pi(\cdot|s^{\prime}_{t})$ and any $\theta\in R_{\theta}$,
we have the following holds

$\displaystyle\left\|g(x_{t},\theta)\right\|_{2}\leq
D_{g},\quad\text{and}\quad\mathbb{E}[\left\|\rho(s_{t},a_{t})g(x_{t},\theta)-g(\theta)\right\|_{2}^{2}]\leq
V_{g},$

where $D_{g}=d_{g}C_{\phi}[C_{\max}+(C_{m}+1)D_{\theta}C_{\phi}]$ and
$V_{g}=2\rho_{\max}D_{g}$.

###### Proof.

We prove the first result as follows,

$\displaystyle\left\|g(x_{t},\theta)\right\|_{2}$
$\displaystyle=\left\|\phi(s,a)^{\top}(B(x)+m(s^{\prime},a^{\prime})\phi(s^{\prime},a^{\prime})\theta-\phi(s,a)\theta)\right\|_{2}$
$\displaystyle\leq\left\|\phi(s,a)^{\top}B(x)\right\|_{F}+\left\|\phi(s,a)\right\|_{F}\left\|m(s^{\prime},a^{\prime})\phi(s^{\prime},a^{\prime})\theta-\phi(s,a)\theta\right\|_{F}$
$\displaystyle\leq d_{g}C_{\phi}[C_{\max}+(C_{m}+1)D_{\theta}C_{\phi}],$

where the last inequality follows from the boundness of the set $R_{\theta}$.
Here we consider $\left\|\theta\right\|_{2}\leq D_{\theta}$ for all $\theta\in
R_{\theta}$. The second result can be obtained as follows

$\displaystyle\left\|\rho(s_{t},a_{t})g(x_{t},\theta)-g(\theta)\right\|_{2}^{2}\leq\left|\rho(s_{t},a_{t})\right|(\left\|g(x_{t},\theta)\right\|_{2}+\left\|g(\theta)\right\|_{2})\leq
2\rho_{\max}D_{g}.$ (87)

∎

We next bound the convergence rate of $w_{\rho,t}$.

######  Lemma 10.

Consider $w_{f,t}$, $w_{{\rho,t}}$ and $\eta_{t}$ in Algorithm 1. Let stepsize
$\beta_{t}=\frac{2}{\lambda_{P}(t+t_{0}+1)}$ where
$t_{0}=\frac{36C^{2}_{P}}{\lambda^{2}_{P}}$. For any
$\kappa\in\mathbb{R}^{d_{\rho}}\times R_{\rho}\times\mathbb{R}$, we have

$\displaystyle\mathbb{E}[\left\|\kappa_{T}-\kappa^{*}\right\|_{2}^{2}]\leq\frac{(1+16\beta^{2}_{0}C^{2}_{P})(t_{0}+1)^{2}\left\|\kappa_{0}-\kappa^{*}\right\|_{2}^{2}}{(T+t_{0}-1)(T+t_{0})}+\frac{64C^{2}_{P}C^{2}_{\kappa}}{(T+t_{0})\lambda^{2}_{P}}.$

###### Proof.

The inner product in eq. 83 can be equivalently written as

$\displaystyle\langle\zeta(x_{t},\kappa_{t}),\kappa_{t+1}-\kappa\rangle$
$\displaystyle\quad=\langle\zeta(\kappa_{t+1}),\kappa_{t+1}-\kappa\rangle+\langle\zeta(\kappa_{t})-\zeta(\kappa_{t+1}),\kappa_{t+1}-\kappa\rangle+\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t}-\kappa\rangle$
$\displaystyle\quad\quad+\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t+1}-\kappa_{t}\rangle$
$\displaystyle\quad\geq\langle\zeta(\kappa_{t+1}),\kappa_{t+1}-\kappa\rangle-\left\|\zeta(\kappa_{t})-\zeta(\kappa_{t+1})\right\|_{2}\left\|\kappa_{t+1}-\kappa\right\|_{2}+\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t}-\kappa\rangle$
$\displaystyle\quad\quad-\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}$
$\displaystyle\quad\geq\langle\zeta(\kappa_{t+1}),\kappa_{t+1}-\kappa\rangle-
C_{P}\left\|\kappa_{t}-\kappa_{t+1}\right\|_{2}\left\|\kappa_{t+1}-\kappa\right\|_{2}+\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t}-\kappa\rangle$
$\displaystyle\quad\quad-\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2},$
(88)

where the last inequality follows from Lemma 5. Substituting eq. 88 into eq.
83, we obtain

$\displaystyle\frac{1}{2}\left\|\kappa_{t}-\kappa\right\|_{2}^{2}-\frac{1}{2}\left\|\kappa_{t+1}-\kappa\right\|_{2}^{2}$
$\displaystyle\quad\geq\beta_{t}\langle\zeta(\kappa_{t+1}),\kappa_{t+1}-\kappa\rangle-\beta_{t}C_{P}\left\|\kappa_{t}-\kappa_{t+1}\right\|_{2}\left\|\kappa_{t+1}-\kappa\right\|_{2}+\beta_{t}\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t}-\kappa\rangle$
$\displaystyle\quad\quad-\beta_{t}\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}+\frac{1}{2}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}^{2}.$
(89)

Note that we have the following holds

$\displaystyle\frac{1}{2}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}^{2}-\beta_{t}C_{P}\left\|\kappa_{t}-\kappa_{t+1}\right\|_{2}\left\|\kappa_{t+1}-\kappa\right\|_{2}-\beta_{t}\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}$
$\displaystyle=\frac{1}{4}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}^{2}-\beta_{t}C_{P}\left\|\kappa_{t}-\kappa_{t+1}\right\|_{2}\left\|\kappa_{t+1}-\kappa\right\|_{2}+\frac{1}{4}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}^{2}$
$\displaystyle\quad-\beta_{t}\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}\left\|\kappa_{t+1}-\kappa_{t}\right\|_{2}$
$\displaystyle\geq-\beta^{2}_{t}C^{2}_{P}\left\|\kappa_{t+1}-\kappa\right\|_{2}^{2}-\beta^{2}_{t}\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}^{2}.$
(90)

Substituting eq. 90 in eq. 89 yields

$\displaystyle\frac{1}{2}\left\|\kappa_{t}-\kappa\right\|_{2}^{2}-\frac{1}{2}\left\|\kappa_{t+1}-\kappa\right\|_{2}^{2}$
$\displaystyle\geq\beta_{t}\langle\zeta(\kappa_{t+1}),\kappa_{t+1}-\kappa\rangle+\beta_{t}\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t}-\kappa\rangle-\beta^{2}_{t}C^{2}_{P}\left\|\kappa_{t+1}-\kappa\right\|_{2}^{2}$
$\displaystyle\quad-\beta^{2}_{t}\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}^{2}.$
(91)

Rearranging eq. 91 and letting $\kappa=\kappa^{*}$ yield

$\displaystyle\left\|\kappa_{t}-\kappa^{*}\right\|_{2}^{2}+2\beta^{2}_{t}\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}^{2}$
$\displaystyle\geq(1-2\beta^{2}_{t}C^{2}_{P})\left\|\kappa_{t+1}-\kappa^{*}\right\|_{2}^{2}+2\beta_{t}\langle\zeta(\kappa_{t+1}),\kappa_{t+1}-\kappa^{*}\rangle+2\beta_{t}\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t}-\kappa^{*}\rangle$
$\displaystyle\geq(1+2\beta_{t}\lambda_{P}-2\beta^{2}_{t}C^{2}_{P})\left\|\kappa_{t+1}-\kappa^{*}\right\|_{2}^{2}+2\beta_{t}\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t}-\kappa^{*}\rangle,$
(92)

where the last inequality follows from
$\langle\zeta(\kappa_{t+1}),\kappa_{t+1}-\kappa^{*}\rangle\leq\lambda_{P}\left\|\kappa_{t+1}-\kappa^{*}\right\|_{2}^{2}$.
Taking expectation on both sides of eq. 92, and noting that
$\mathbb{E}[\langle\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t}),\kappa_{t}-\kappa^{*}\rangle|\mathcal{F}_{t}]=0$,
we obtain

$\displaystyle(1+2\beta_{t}\lambda_{P}-2\beta^{2}_{t}C^{2}_{P})\mathbb{E}[\left\|\kappa_{t+1}-\kappa^{*}\right\|_{2}^{2}]$
$\displaystyle\quad\leq\mathbb{E}[\left\|\kappa_{t}-\kappa^{*}\right\|_{2}^{2}]+2\beta^{2}_{t}\mathbb{E}[\left\|\zeta(x_{t},\kappa_{t})-\zeta(\kappa_{t})\right\|_{2}^{2}]$
$\displaystyle\quad\leq(1+16\beta_{t}^{2}C^{2}_{P})\mathbb{E}[\left\|\kappa_{t}-\kappa^{*}\right\|_{2}^{2}]+16\beta^{2}_{t}C^{2}_{P}C^{2}_{\kappa}.$
(93)

Multiplying both sides of eq. 93 with $I_{t}$ and summing over
$t=0,\cdots,T-1$ yield

$\displaystyle\sum_{t=0}^{T-1}a_{t}\mathbb{E}[\left\|\kappa_{t+1}-\kappa^{*}\right\|_{2}^{2}]\leq\sum_{t=0}^{T-1}b_{t}\mathbb{E}[\left\|\kappa_{t}-\kappa^{*}\right\|_{2}^{2}]+c,$
(94)

where

$\displaystyle a_{t}$
$\displaystyle=(1+2\beta_{t}\lambda_{P}-2\beta^{2}_{t}C^{2}_{P})I_{t},$
$\displaystyle b_{t}$ $\displaystyle=(1+16\beta_{t}^{2}C^{2}_{P})I_{t},$
$\displaystyle c$
$\displaystyle=16C^{2}_{P}C^{2}_{\kappa}\sum_{t=0}^{T-1}\beta^{2}_{t}I_{t}.$

We further let

$\displaystyle I_{t}$ $\displaystyle=(t+t_{0})(t+t_{0}+1),$
$\displaystyle\beta_{t}$ $\displaystyle=\frac{2}{\lambda_{P}(t+t_{0}-1)},$
$\displaystyle t_{0}$ $\displaystyle=\frac{36C^{2}_{P}}{\lambda^{2}_{P}}+1.$

We can obtain the following

$\displaystyle a_{t}-b_{t+1}$
$\displaystyle=(1+2\beta_{t}\lambda_{P}-2\beta^{2}_{t}C^{2}_{P})I_{t}-(1+16\beta_{t+1}^{2}C^{2}_{P})s_{t+1}$
$\displaystyle\geq(1+2\beta_{t}\lambda_{P})I_{t}-(1+2\beta^{2}_{t}+16\beta_{t+1}^{2}C^{2}_{P})s_{t+1}$
$\displaystyle\geq(1+2\beta_{t}\lambda_{P})I_{t}-(1+18\beta_{t}^{2}C^{2}_{P})s_{t+1}$
$\displaystyle\geq(1+2\beta_{t}\lambda_{P})I_{t}-(1+\beta_{t}\lambda_{P})s_{t+1}$
$\displaystyle\geq(t+t_{0}+1)\frac{(t+t_{0}+3)(t+t_{0})-(t+t_{0}+2)^{2}}{t+t_{0}-1}$
$\displaystyle\geq 0.$

Substituting the above results into eq. 94 yields

$\displaystyle
a_{T-1}t\mathbb{E}[\left\|\kappa_{T}-\kappa^{*}\right\|_{2}^{2}]\leq
b_{0}\left\|\kappa_{0}-\kappa^{*}\right\|_{2}^{2}+c,$

which implies

$\displaystyle\mathbb{E}[\left\|\kappa_{T}-\kappa^{*}\right\|_{2}^{2}]$
$\displaystyle\leq\frac{b_{0}\left\|\kappa_{0}-\kappa^{*}\right\|_{2}^{2}}{A_{T-1}}+\frac{c}{a_{T-1}}$
$\displaystyle=\frac{(1+16\beta^{2}_{0}C^{2}_{P})s_{0}\left\|\kappa_{0}-\kappa^{*}\right\|_{2}^{2}}{(1+2\beta_{T-1}\lambda_{P}-2\beta^{2}_{T-1}C^{2}_{P})s_{T-1}}+\frac{16C^{2}_{P}C^{2}_{\kappa}\sum_{t=0}^{T-1}\beta^{2}_{t}I_{t}}{(1+2\beta_{T-1}\lambda_{P}-2\beta^{2}_{T-1}C^{2}_{P})s_{T-1}}$
$\displaystyle\leq\frac{(1+16\beta^{2}_{0}C^{2}_{P})(t_{0}+1)^{2}\left\|\kappa_{0}-\kappa^{*}\right\|_{2}^{2}}{(T+t_{0}-1)(T+t_{0})}+\frac{64C^{2}_{P}C^{2}_{\kappa}}{(T+t_{0})\lambda^{2}_{P}},$

which completes the proof. ∎

Note that Lemma 10 implies that there exists a positive number $D_{\rho}$ such
that

$\displaystyle\mathbb{E}[\left\|w_{\rho,t}-w^{*}_{\rho}\right\|_{2}^{2}]\leq\frac{D_{\rho}}{t+t_{0}}.$
(95)

###  E.2 Proof of Theorem 1

Consider the inner product term in eq. 84. We have

$\displaystyle-\langle$
$\displaystyle\hat{\rho}(x_{t},w_{\rho,t})g(x_{t},\theta_{t}),\theta_{t+1}-\theta)\rangle$
$\displaystyle=-\langle g(\theta_{t+1}),\theta_{t+1}-\theta)\rangle-\langle
g(\theta_{t}-g(\theta_{t+1}),\theta_{t+1}-\theta)\rangle$
$\displaystyle\quad-\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta_{t+1}-\theta_{t}\rangle-\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta_{t}-\theta\rangle$
$\displaystyle\quad-\langle(\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t}))g(x_{t},\theta_{t}),\theta_{t+1}-\theta\rangle$
$\displaystyle\quad-\langle(\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho}))g(x_{t},\theta_{t}),\theta^{\top}_{t+1}-\theta\rangle$
$\displaystyle\geq-\langle g(\theta_{t+1}),\theta^{\top}_{t+1}-\theta\rangle-
C_{g}\left\|\theta_{t}-\theta_{t+1}\right\|_{2}\left\|\theta_{t+1}-\theta\right\|_{2}$
$\displaystyle\quad-\left\|\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t})\right\|_{2}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}-\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta^{\top}_{t}-\theta\rangle$
$\displaystyle\quad-\left|\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t})\right|\left\|g(x_{t},\theta_{t})\right\|_{2}\left\|\theta_{t+1}-\theta\right\|_{2}$
$\displaystyle\quad-\left|\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho})\right|\left\|g(x_{t},\theta_{t})\right\|_{2}\left\|\theta_{t+1}-\theta\right\|_{2},$
(96)

where the last inequality follows from Lemma 6. Substituting eq. 96 into eq.
84 yields

$\displaystyle\frac{1}{2}\left\|\theta_{t}-\theta\right\|_{2}^{2}-\frac{1}{2}\left\|\theta_{t+1}-\theta\right\|_{2}^{2}$
$\displaystyle\quad\geq-\alpha_{t}\langle
g(\theta_{t+1}),\theta^{\top}_{t+1}-\theta\rangle-\alpha_{t}C_{g}\left\|\theta_{t}-\theta_{t+1}\right\|_{2}\left\|\theta_{t+1}-\theta\right\|_{2}$
$\displaystyle\quad\quad-\alpha_{t}\left\|\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t})\right\|_{2}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}-\alpha_{t}\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta^{\top}_{t}-\theta^{\top}\rangle$
$\displaystyle\quad\quad-\alpha_{t}\left|\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t})\right|\left\|g(x_{t},\theta_{t})\right\|_{2}\left\|\theta_{t+1}-\theta\right\|_{2}$
$\displaystyle\quad\quad-\alpha_{t}\left|\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho})\right|\left\|g(x_{t},\theta_{t})\right\|_{2}\left\|\theta_{t+1}-\theta\right\|_{2}+\frac{1}{2}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}^{2}.$
(97)

We have the following holds

$\displaystyle\frac{1}{2}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}^{2}-\alpha_{t}C_{g}\left\|\theta_{t}-\theta_{t+1}\right\|_{2}\left\|\theta_{t+1}-\theta\right\|_{2}-\alpha_{t}\left\|\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t})\right\|_{2}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}$
$\displaystyle\quad\quad=\frac{1}{4}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}^{2}-\alpha_{t}C_{g}\left\|\theta_{t}-\theta_{t+1}\right\|_{2}\left\|\theta_{t+1}-\theta\right\|_{2}+\frac{1}{4}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}^{2}$
$\displaystyle\quad\quad\quad-\alpha_{t}\left\|\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t})\right\|_{2}\left\|\theta_{t+1}-\theta_{t}\right\|_{2}$
$\displaystyle\quad\quad\geq-\alpha^{2}_{t}C^{2}_{g}\left\|\theta_{t+1}-\theta\right\|_{2}^{2}-\alpha^{2}_{t}\left\|\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t})\right\|_{2}^{2},$
(98)

which implies

$\displaystyle\frac{1}{2}\left\|\theta_{t}-\theta\right\|_{2}^{2}-\frac{1}{2}\left\|\theta_{t+1}-\theta\right\|_{2}^{2}$
$\displaystyle\quad\quad\geq-\alpha_{t}\langle
g(\theta_{t+1}),\theta_{t+1}-\theta\rangle-\alpha^{2}_{t}C^{2}_{g}\left\|\theta_{t+1}-\theta\right\|_{2}^{2}-\alpha^{2}_{t}\left\|\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t})\right\|_{2}^{2}$
$\displaystyle\quad\quad-\alpha_{t}\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta_{t}-\theta\rangle-\alpha_{t}D_{g}\left|\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t})\right|\left\|\theta_{t+1}-\theta\right\|_{2}$
$\displaystyle\quad\quad-\alpha_{t}D_{g}\left|\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho})\right|\left\|\theta_{t+1}-\theta\right\|_{2},$
(99)

where we use the fact that $\left\|g(x_{t},\theta_{t})\right\|_{2}\leq D_{g}$
in Lemma 9. Rearranging eq. 99 and letting $\theta=\theta^{*}$ yield

$\displaystyle\left\|\theta_{t}-\theta^{*}\right\|_{2}^{2}+2\alpha^{2}_{t}\left\|\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t})\right\|_{2}^{2}$
$\displaystyle\quad\geq\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}-2\alpha_{t}\langle
g(\theta_{t+1}),\theta_{t+1}-\theta^{*}\rangle-2\alpha^{2}_{t}C^{2}_{g}\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}$
$\displaystyle\quad\quad-2\alpha_{t}\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta_{t}-\theta^{*}\rangle-2\alpha_{t}D_{g}\left|\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t})\right|\left\|\theta_{t+1}-\theta^{*}\right\|_{2}$
$\displaystyle\quad\quad-2\alpha_{t}D_{g}\left|\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho})\right|\left\|\theta_{t+1}-\theta\right\|_{2}$
$\displaystyle\quad\geq(1+2\alpha_{t}\lambda_{g}-2\alpha^{2}_{t}C^{2}_{g})\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}-2\alpha_{t}\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta_{t}-\theta^{*}\rangle$
$\displaystyle\quad\quad-2\alpha_{t}D_{g}\left|\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t})\right|\left\|\theta_{t+1}-\theta^{*}\right\|_{2}$
$\displaystyle\quad\quad-2\alpha_{t}D_{g}\left|\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho})\right|\left\|\theta_{t+1}-\theta\right\|_{2}$
$\displaystyle\quad\geq(1+2\alpha_{t}\lambda_{g}-2\alpha^{2}_{t}C^{2}_{g})\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}-2\alpha_{t}\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta_{t}-\theta^{*}\rangle$
$\displaystyle\quad\quad-\frac{1}{2}\alpha_{t}\lambda_{g}\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}-\frac{2\alpha_{t}D^{2}_{g}}{\lambda_{g}}\left|\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t})\right|^{2}$
$\displaystyle\quad\quad-\frac{1}{2}\alpha_{t}\lambda_{g}\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}-\frac{2\alpha_{t}D^{2}_{g}}{\lambda_{g}}\left|\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho})\right|^{2}$
$\displaystyle\quad=(1+\alpha_{t}\lambda_{g}-2\alpha^{2}_{t}C^{2}_{g})\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}-2\alpha_{t}\langle\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t}),\theta_{t}-\theta^{*}\rangle$
$\displaystyle\quad\quad-\frac{2\alpha_{t}D^{2}_{g}}{\lambda_{g}}\left|\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t})\right|^{2}-\frac{2\alpha_{t}D^{2}_{g}}{\lambda_{g}}\left|\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho})\right|^{2},$
(100)

where the first inequality follows from Lemma 4, and the third inequality
follows from Young’s inequality. Taking expectation on both sides of eq. 100
yields

$\displaystyle(1$
$\displaystyle+\alpha_{t}\lambda_{g}-2\alpha^{2}_{t}C^{2}_{g})\mathbb{E}[\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}]$
$\displaystyle\leq\mathbb{E}[\left\|\theta_{t}-\theta^{*}\right\|_{2}^{2}]+2\alpha^{2}_{t}\mathbb{E}[\left\|\rho(x_{t})g(x_{t},\theta_{t})-g(\theta_{t})\right\|_{2}^{2}]+\frac{2\alpha_{t}D^{2}_{g}}{\lambda_{g}}\mathbb{E}\left[\left|\hat{\rho}(x_{t},w^{*}_{\rho})-\rho(x_{t})\right|^{2}\right]$
$\displaystyle\quad+\frac{2\alpha_{t}D^{2}_{g}C^{2}_{\psi}}{\lambda_{g}}\mathbb{E}\left[\left|\hat{\rho}(x_{t},w_{\rho,t})-\hat{\rho}(x_{t},w^{*}_{\rho})\right|^{2}\right]$
$\displaystyle\leq\mathbb{E}[\left\|\theta_{t}-\theta^{*}\right\|_{2}^{2}]+2V_{g}\alpha^{2}_{t}+\frac{2\alpha_{t}D^{2}_{g}C^{2}_{\psi}}{\lambda_{g}}\mathbb{E}\left[\left\|w_{\rho,t}-w^{*}_{\rho}\right\|_{2}^{2}\right]+\frac{2D^{2}_{g}\alpha_{t}\varepsilon_{\rho}}{\lambda_{g}},$
(101)

where the last inequality follows from Lemma 9.

Substituting eq. 95 into eq. 101 yields

$\displaystyle(1+\alpha_{t}\lambda_{g}-$ $\displaystyle
2\alpha^{2}_{t}C^{2}_{g})\mathbb{E}[\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}]$
$\displaystyle\leq\mathbb{E}[\left\|\theta_{t}-\theta^{*}\right\|_{2}^{2}]+2V_{g}\alpha^{2}_{t}+\frac{2\alpha_{t}D^{2}_{g}D_{\rho}C^{2}_{\psi}}{\lambda_{g}(t+t_{0})}+\frac{2D^{2}_{g}\alpha_{t}\varepsilon_{\rho}}{\lambda_{g}}.$
(102)

Multiplying both sides of eq. 102 with $r_{t}$ and summing over
$t=0,\cdots,T-1$ yield

$\displaystyle\sum_{t=0}^{T-1}a^{\prime}_{t}\mathbb{E}[\left\|\theta_{t+1}-\theta^{*}\right\|_{2}^{2}]$
$\displaystyle\quad\leq\sum_{t=0}^{T-1}r_{t}\mathbb{E}[\left\|\theta_{t}-\theta^{*}\right\|_{2}^{2}]+2V_{g}\sum_{t=0}^{T-1}r_{t}\alpha^{2}_{t}+\frac{2D^{2}_{g}D_{\rho}C^{2}_{\psi}}{\lambda_{g}(t+t_{0})}\sum_{t=0}^{T-1}r_{t}\alpha_{t}+\frac{2D^{2}_{g}\varepsilon_{\rho}}{\lambda_{g}}\sum_{t=0}^{T-1}r_{t}\alpha_{t},$
(103)

where

$\displaystyle
a^{\prime}_{t}=(1+\alpha_{t}\lambda_{g}-2\alpha^{2}_{t}C^{2}_{g})r_{t}.$

Now we let

$\displaystyle r_{t}$ $\displaystyle=(t+t_{1})(t+t_{1}+1),$
$\displaystyle\alpha_{t}$ $\displaystyle=\frac{4}{\lambda_{g}(t+t_{1}-1)},$
$\displaystyle t_{1}$ $\displaystyle=\frac{16C^{2}_{g}}{\lambda^{2}_{g}}+1.$

We can obtain the following

$\displaystyle a^{\prime}_{t}-r_{t+1}$
$\displaystyle=(1+\alpha_{t}\lambda_{g}-2\alpha^{2}_{t}C^{2}_{g})r_{t}-r_{t+1}$
$\displaystyle\geq(1+\alpha_{t}\lambda_{g})r_{t}-(1+2\alpha^{2}_{t}C^{2}_{g})r_{t+1}$
$\displaystyle\geq(1+\alpha_{t}\lambda_{g})r_{t}-\left(1+\frac{1}{2}\alpha_{t}\lambda_{g}\right)r_{t+1}$
$\displaystyle\geq(t+t_{1}+1)\frac{(t+t_{1})(t+t_{1}+3)-(t+t_{1}+2)^{2}}{t+t_{1}+1}$
$\displaystyle\geq 0,$

where the second inequality follows from the fact that
$\alpha_{t}\leq\frac{\lambda_{g}}{4C^{2}_{g}}$.

Substituting the above result to eq. 103 yields

$\displaystyle
a^{\prime}_{T-1}\mathbb{E}[\left\|\theta_{T}-\theta^{*}\right\|_{2}^{2}]\leq
r_{0}\left\|\theta_{0}-\theta^{*}\right\|_{2}^{2}+2V_{g}\sum_{t=0}^{T-1}r_{t}\alpha^{2}_{t}+\frac{2D^{2}_{g}D_{\rho}C^{2}_{\psi}}{\lambda_{g}(t+t_{0})}\sum_{t=0}^{T-1}r_{t}\alpha_{t}+\frac{2D^{2}_{g}\varepsilon_{\rho}}{\lambda_{g}}\sum_{t=0}^{T-1}r_{t}\alpha_{t}.$

The above inequality implies the following convergence rate

$\displaystyle\mathbb{E}[\left\|\theta_{T}-\theta^{*}\right\|_{2}^{2}]\leq\frac{r_{0}\left\|\theta_{0}-\theta^{*}\right\|_{2}^{2}}{(T+t_{1}-1))(T+t_{1})}+\frac{128V_{g}}{\lambda^{2}_{g}(T+t_{1})}+\frac{64D^{2}_{g}C^{2}_{g}C^{2}_{\psi}\lambda^{2}_{P}}{9C^{2}_{P}\lambda^{3}_{g}(T+t_{1})}+\frac{16D^{2}_{g}}{\lambda^{2}_{g}}\varepsilon_{\rho},$

which completes the proof.

##  Appendix F Proof of Theorem 2

Following the similar argument similar to that in [3, Lemma 4.2] and [50,
Theorem 1], we can prove that ${\rm\Phi}\theta^{*}$ is the fixed point of the
composite operator ${\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\bar{\mathcal{T}}_{\pi}$.
We then proceed as follows

$\displaystyle\left\|{\rm\Phi}\theta^{*}-G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle=\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\bar{\mathcal{T}}_{\pi}{\rm\Phi}\theta^{*}-{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}+{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}-G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle\leq\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\bar{\mathcal{T}}_{\pi}{\rm\Phi}\theta^{*}-{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}\right\|_{\mu_{\pi},\alpha}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}-G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle=\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\bar{\mathcal{T}}_{\pi}{\rm\Phi}\theta^{*}-{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\bar{\mathcal{T}}_{\pi}G_{\pi}\right\|_{\mu_{\pi},\alpha}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}-G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle\leq\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}[\bar{\mathcal{T}}_{\pi}{\rm\Phi}\theta^{*}-\bar{\mathcal{T}}_{\pi}G_{\pi}]\right\|_{\mu_{\pi},\alpha}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}-G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle\leq\left\|\bar{\mathcal{T}}_{\pi}{\rm\Phi}\theta^{*}-\bar{\mathcal{T}}_{\pi}G_{\pi}\right\|_{\mu_{\pi},\alpha}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}-G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle\leq\gamma_{G}\left\|{\rm\Phi}\theta^{*}-G_{\pi}\right\|_{\mu_{\pi},\alpha}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}-G_{\pi}\right\|_{\mu_{\pi},\alpha},$
(104)

where the first equality follows from the fact that
${\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\bar{\mathcal{T}}_{\pi}{\rm\Phi}\theta^{*}={\rm\Phi}\theta^{*}$,
the second equality follows from the fact that
$\bar{\mathcal{T}}_{\pi}G_{\pi}=G_{\pi}$, the third inequality follows from
the non-expansive property of the projection operator
${\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}$, and the last inequality follows from
Proposition 1. Equation 104 implies the following result

$\displaystyle\left\|{\rm\Phi}\theta^{*}-G_{\pi}\right\|_{\mu_{\pi},\alpha}\leq\frac{1}{1-\gamma_{G}}\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}G_{\pi}-G_{\pi}\right\|_{\mu_{\pi},\alpha}.$

##  Appendix G Extension to Case $\gamma_{\max}=1$

As shown in Proposition 1, the operator $\bar{\mathcal{T}}_{G,\pi}$ is not
necessarily a contraction when $\gamma_{\max}=1$. The uniqueness of $G_{\pi}$
and $\hat{G}_{\pi}$ is not guaranteed in this case. We next consider the
following assumption for the base matrix ${\rm\Phi}_{i}$, which can yield a
desired property as we show below. Such an assumption has also been considered
in the average reward MDP setting [51].

######  Assumption 3 (Non-constant Parameterization).

For all $i=1,\cdots,k$, we have ${\rm\Phi}_{i}\theta_{i}\neq c\mathbf{1}$ for
any $\theta_{i}\in\mathbb{R}^{d_{i}}$ and $c\in\mathbb{R}/0$.

Despite the non-contraction nature of $\bar{\mathcal{T}}_{G,\pi}$, if the base
function ${\rm\Phi}_{i}$ satisfies 3, we can show that the monotonicity
condition of $g(\theta)$ in Proposition 2 still holds with a positive constant
$\lambda_{G}$. As a result, the convergence bound in eq. 15 of theorem 1 is
directly applicable to this setting with the corresponding value of
$\lambda_{G}$. We can then further establish a result similar to Theorem 2 for
the case with $\gamma_{\max}=1$ under 3.

We first extend Proposition 2 and Theorem 2 to the case in which
$\gamma_{\max}=1$. Without loss of generality, we consider $\gamma_{i}=1$ for
all $i=1,\cdots,k$.

Forward GVF. We first verify Proposition 2. In this setting, we can still
obtain the same result for $G$ as in eq. 55, but with
$A_{i}=[{\rm\Phi}_{i}^{\top}\bar{U}_{\pi}(\mathsf{P}_{\pi}-I){\rm\Phi}_{i}]\otimes\mathsf{I}_{d_{i}}$,
where $\bar{U}_{\pi}=\text{diag}(\mu_{\pi})$. As shown in [51, Lemma 7], the
matrix $[{\rm\Phi}_{i}^{\top}U_{\pi,i}(\mathsf{P}_{\pi}-I){\rm\Phi}_{i}]$ is
Hurwitz when the base matrix ${\rm\Phi}_{i}$ satisfies 3. Following the steps
similar to those in eq. 56 \- (59), we can conclude that the matrix $G$ is
also Hurwitz, which completes the proof.

We then verify Theorem 2. We proceed as follows,

$\displaystyle\left\|{\rm\Phi}\theta^{*}-G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle\quad=\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}{\mathcal{T}}_{\pi}{\rm\Phi}\theta^{*}-{\mathcal{T}}_{\pi}G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle\quad\leq\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}{\mathcal{T}}_{\pi}{\rm\Phi}\theta^{*}-{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}{\mathcal{T}}_{\pi}G_{\pi}\right\|_{\mu_{\pi},\alpha}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\mathcal{T}_{\pi}G_{\pi}-{\mathcal{T}}_{\pi}G_{\pi}\right\|_{U_{\pi}}$
$\displaystyle\quad\leq\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}M_{\pi}({\rm\Phi}\theta^{*}-G_{\pi})\right\|_{U_{\pi}}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\mathcal{T}_{\pi}G_{\pi}-\mathcal{T}_{\pi}G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle\quad\leq\left\|M_{\pi}({\rm\Phi}\theta^{*}-G_{\pi})\right\|_{U_{\pi}}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\mathcal{T}_{\pi}G_{\pi}-\mathcal{T}_{\pi}G_{\pi}\right\|_{\mu_{\pi},\alpha}$
$\displaystyle\quad\leq
C_{\zeta}\left\|{\rm\Phi}\theta^{*}-G_{\pi}\right\|_{U_{\pi}}+\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\mathcal{T}_{\pi}G_{\pi}-\mathcal{T}_{\pi}G_{\pi}\right\|_{\mu_{\pi},\alpha},$
(105)

where the last inequality in eq. 105 can be obtained as follows. Following the
steps similar to those in eq. 56-(59), we can conclude that
$\text{eig}(M_{\pi})=\text{eig}(\mathsf{P}_{\pi})$. For an ergodic MDP, we
have
$\max[\text{eig}(\mathsf{P}_{\pi})]=\max[\text{eig}(\mathsf{P}_{\pi}^{\top})]=1$.
Let $i=\operatorname*{argmax}_{j}[\text{eig}(\mathsf{P}_{\pi})_{j}]$. We then
have $\max_{j\neq i}\text{eig}(\mathsf{P}_{\pi})_{j}<1$. Let $G_{\pi}$ be the
fixed point of $\mathcal{T}_{\pi}$ that is perpendicular to
$[c_{1}\mathbf{1}_{d_{1}},\cdots,c_{k}\mathbf{1}_{d_{k}}]$, where
$c_{1},\cdots,c_{k}$ could be any constant. The vector
${\rm\Phi}\theta^{*}-G_{\pi}$ is perpendicular to the space spanned by the
eigenvectors of $M_{\pi}$ associated with the eigenvalue $1$. Thus, there
exists a positive constant $C_{\zeta}<1$ such that
$\left\|M_{\pi}({\rm\Phi}\theta^{*}-G_{\pi})\right\|_{U_{\pi}}\leq
C_{\zeta}\left\|{\rm\Phi}\theta^{*}-G_{\pi}\right\|_{U_{\pi}}$, which yields
the following results

$\displaystyle\left\|{\rm\Phi}\theta^{*}-G_{\pi}\right\|_{\mu_{\pi},\alpha}\leq\frac{1}{1-C_{\zeta}}\left\|{\rm\Gamma}_{{\rm\Phi},\mu_{\pi}}\mathcal{T}_{\pi}G_{\pi}-\mathcal{T}_{\pi}G_{\pi}\right\|_{\mu_{\pi},\alpha}.$
(106)

Bakcward GVF. To verify Proposition 2, we can obtain the same result for $G$
as in eq. 55 with
$A_{i}=[{\rm\Phi}_{i}^{\top}(\mathsf{P}^{\top}_{\pi}-I)\bar{U}_{\pi}{\rm\Phi}_{i}]\otimes\mathsf{I}_{d_{i}}$.
Define
$\bar{A}_{i}={\rm\Phi}_{i}^{\top}(\mathsf{P}^{\top}_{\pi}-I)U_{\pi}{\rm\Phi}_{i}$.
We next show that $\bar{A}_{i}$ is Hurwitz. Note that
$\bar{A}_{i}=\mathbb{E}_{\mu_{\pi}}[\phi^{\prime}(\phi-\phi^{\prime})]$. Let
$z$ be a non-constant function on the state-action space. Then we have

$\displaystyle 0$
$\displaystyle<\frac{1}{2}\mathbb{E}_{\mu_{\pi}}[(z(s,a)-z(s^{\prime},a^{\prime}))^{2}]$
$\displaystyle=\mathbb{E}_{\mu_{\pi}}[z(s,a)^{2}]-\mathbb{E}[z(s,a)z(s^{\prime},a^{\prime})]$
$\displaystyle=z^{\top}\bar{U}_{\pi}z-z^{\top}\mathsf{P}_{\pi}\bar{U}_{\pi}z$
$\displaystyle=z^{\top}(I-\mathsf{P}_{\pi})\bar{U}_{\pi}z.$ (107)

For a vector $v\in\mathbb{R}^{K_{i}}$, we have

$\displaystyle
v^{\top}\bar{A}_{i}v=v{\rm\Phi}_{i}^{\top}(\mathsf{P}_{\pi}^{\top}-I)U_{\pi}{\rm\Phi}_{i}v.$
(108)

Since ${\rm\Phi}v$ is a non-constant function, eq. 107 and eq. 108 together
imply that