A Unifying Framework of Off-Policy General Value Function Evaluation
Authors: Tengyu Xu
Zhuoran Yang
Zhaoran Wang
Yingbin Liang
Venue: NeurIPS 2022 Accept (2022)
Keywords: general value function
general Bellman operation
off-policy evaluation

Abstract: General Value Function (GVF) is a powerful tool to represent both the {\em predictive} and {\em 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.

A Unifying Framework of Off-Policy General Value Function Evaluation
Tengyu Xu Meta Platforms, Inc Menlo Park, CA 94025
Zhuoran Yang Yale University New Haven, CT 06520
Zhaoran Wang Northwestern University Evanston, IL 60208
Yingbin Liang
Ohio State University Columbus, OH 43210
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 -oolcyy samples. In the literature, the gradient temporal difference (GTD) learning method has been adopted to evaluate GVFs in the off off-policy setting, but such an approach may suffer from 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 GVFs with causal filtering, which cover a wide range of RL applications such 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 guaranteed
further show that unlike GTD, the learned GVFs by GenTD converge to the ground truth GVFs as long as the function approximation power is sufficiently large. To our best knowledge, Gen'TD 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 44 serves reliable performance metric of policy in the reinforcement learning (RL) tasks 42 23). 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-gon is more suitable performance metric. As another example, to obtain a variance-reducee or bias-reduced policy gradient estimator [4]] 61 [8]. 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 Daction/state-value gradient" [38] R [2]. etc. All the
aforementioned metrics can be viewed as predicative knowledge of certain multiple intercorrelated cumulative "signals" (possibly nigh-dimensional, e.g., the gradient of value function), and thus naturally fall into the framework of forward GVFs (refers to forward general value functions) (see Section 2. for the formal definition). One typical approach evaluate GVFs. is to learn from samples that pre-collected from one or more behavior policies, which yields an
48 57
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

off-policy method. In practice, multiple forward GVFs are usually evaluated jointly at the same time due to their interrelationships 37 33
In contrast to forward GVFs defined based on predictive knowledge, the backward GVFs represents retrospective knowledge, which captures the accumulation of signals from the past to the present time [70] (see Section 2.2 for the formal definition). Although the concept of the backward GVFs has not been formally proposed until very recently (70). it is rooted
number of important RL
applications such as anomaly detection [70], emphatic weight learning 46 [7] and evaluation of
gradient of logarithmic stationary distribution [26. 61 [8. Different from the forward GVFs, for
which the Bellman operator can be defined independently from the sampling distribution [77 42 44] the Bellman operator of the backward GVFs only valid if the sampling exactly follows the on on-policy stationary distribution [70]. Due to such reason, off off-policy evaluation of the backward GVFs is much more challenging than that of the forward GVFs.
In general, due to the high dimensionality and intercorrelation, it is very challenging to evaluate multiple GVFs simultaneously with standard policy evaluation approaches [55] 45 [2). In previous studies, the gradient temporal difference (GTD) learning [45] [3]. one of the most popular off-policy methods in value function evaluation, has been adopted solve both the forward and backward GVFs evaluation problems [48 37 69), 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 targer policy. As result, GTD can encounter serious issues in GVFs 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 GVFs 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 Example I in 19).. Second, for high-dimennional GVTs evaluations, the landscape geometry of the GTD objective function can be ill-conditioned 23 which could slow down the convergence of GTD significantly. As demonstrated by our empirical results in Section S 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:
Can we design a new off off-policy approach for multiple interrelated and high-dimensiond GVF's 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 common structural feature shared by GVFs in a wide range of RL applications (see Appendix C (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-ding -igh-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 Gen'TD to solve off-policy GVFs evaluation problem. Gen'DD introduces a density ratio to adjust the behavior distribution and further incorporates policy-agnostic approach GenDICE//GradeenDDIC [65]] 770 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 (l17T), 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, TD is guaranteed to approximate the ground truth GVFs well as long as the function expressive power is sufficiently large. To our best knowledge, Gen is the first off-policy GVF evaluation algorithm that has such a ground truth guarantee. (e) Our experiments further demonstrate that GenTD converges much faster than GTD, and more importantly, converges to ground truth closely, whereas GTD suffers from large approximation error.
Related Work. The forward GVF was first introduced in [8 to represent a set of accumulation of general signals with possibly time-varying discount factors. The forward GVF was later used to represent set of interrelated predictions [37
33 It has been observed that some RL metrics such as variance, gradient of value function, state/action value gradient can also be viewed as
9
41
24
forward GVFs [5 14 61 18 38 48 57
g 5 In previous works, both TD learning and GTD
have been used to evaluate forward GVFs in the on- and off-policy settings [48] 37 33), respectively.

---

A more comprehensive review of studies of forward GVFs has been provided in [35]. The backward GVF was formally defined [70]. 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 [66] 68 26
63
10] Another
track of research has focused on evaluation of a general scalar function in the off-policy setting, a.k
off-policy evaluation (OPE) [4, 164, [6]. However, since the focus of this paper is on the evaluation of multiple high-dimensional GVFs, results in OPE are not directly comparable with ours.
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 [37] The convergence
rate of GTD has only been established in [62, [7] 58 21 for the simple canonical value function
evaluation setting, which is a special case of forward GVFs. However, as pointed out in [9 10, 27 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- 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 GVFs value.
We note that the contraction property of GBO for forward GVFs has also been investigated in [33] with a structure called "acyclic graph". which is similar to "causal filtering" in our paper (see the footnote comment for Proposition| [ However, the results of backward GVFs are established in our work for the first time. The focus of this paper is on the finite time performance and optimality guarantee for a new off-policy GVFs evaluation algorithm GenT'D, which was not studied in 33
2 Markov Decision Process and General Value Function
We consider an infinite-horizon Markov Decision Process (MDP) with state space S, an action space A, a reward function r S x AA + R, transition kernel P: S x S x A + [0. 1]. discounted factor 7 E (0, 1), and an initial distribution No S + [0, 1]. An policy (aas)) is the probability of taking action a at state s. At time step t, an agent at a state 8; selects an action a, according to T ((lss),,eeeivve))
reward r r(se, at), and transits to state 8t+1 according to P(-|st, at). The state-action transition kernel is defined as Px E R|S]|A| in which (=((s, a). (s', = P(s"|s, (a'a(a)s') When the MDP is ergodic, we define H4, as the state-action stationary distribution which satisfies: n PTTPT = Nx. For such an MDP, we define the discounted accumulation of reward as the "reward- to-go": J= -
= ('r(st: oz). 'he state-action value function (i.e., Q-function) is defined as
(s.0) a) (s0, 0o) = (s, a)), and the state value function (i.e., V-function) is defined as
(s((s) (s, Note that (s, satisfies the following Bellman equation
Q. = TTQ = R 7P
(1)
where Tr is the Bellman operator, and Q+ and R E R|STAA are vectors obtained via stacking @=(s,a) a) and r(s, a) over state-action space S x A. We introduce a function of (s, a) (possibly in the vector form) as v(s, a) E Rdd (d 2 1). Consider distribution E(-) over S x A. We define the E-norm of v E Rd[S(AAA as ||0l|s = VVic.a) ((s, [[((s, a)ll where e is obtained by stacking the function v(s, a) over S x A. It has been proved that Ta is --contraction in -nrmorm, i.c., ||T=u - Ta He I y ||0 - o'I and Q7 is the unique fixed point of T. [44 42 In the sequel, we denote la as the identity matrix with the dimension d and @ as the Kronecker product. We further define U, diag(Ux,1,. U,,)), in which Un.; diag(uz)) & ld. for i {1.... ,k), and Px diag( . Pr,,), in which Pr,; = P, 8 ld.
2.1 Forward General Value Function
Consider a set of the state-action general value functions (GVFs) G- = [GT,,, GT,a where each GVF G is defined as the accumulation of a corresponding signal C,(s, a) E Rd. given by as, = - (s az) (so, ao) (s, a), x]. where % E (0, is a discount factor associated with C. Since Cx(s,a) E Rdi can be high-dimensional, Gr,(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= defined as the accumulation of the signal C, in a forward direction from the current time step & to the future oo, we call G2 as "forward GVF".
3

---

In many RL applications, we are often interested in the case that G of GVFs have progressive dependence [48]. i.e.. each (s a) (associated with Gx,;) depends on the lower-indexed value functions Gz,1, ... Gr,i-1 in the set. As concrete example, suppose the policy is parametrized by smooth function Tw. where the parameter w Rd=, In addition to the Q-function Q= the gradient V=Qn (s, a) of the Q-function w.r.t w arises as GVF of interest in several applications. In such case, GT.11 Q. and 2x V Q.. m. It has been shown in [5] that the reward C2 (s, a) associated with Q is given by C2(s, a) - y >E[== (s', V log(T (s', a')) d')){s, [)]aa,)) which depends on the lower-indexed GT,1 Qr. Hence, such defined GVFs vector has progressive dependence. Appendix C provides further details and more examples in RL. More formally, we refer to this structure of forward GVF with progressive dependence casual filtering defined below. Note that a similar structure was called acyclic graph in [33].
Definition 1 (Forward GVF with causal filtering). For given policy æ, forward GVF Gx [G 1. , G T with causal filtering are associated with signals satisfying
C C: Σド= A.. for 2 2sisk,
where Cj and Ga are obtained by respectively stacking Ci(s,a) E Rdd and (s)(s,a) a) E R4 over S A. B₁ E RdilSlIA is an observable signal, and the coefficient matrix Aig R418|[A)xd(5111 captures how the j-th GVF Gz. affects the i-th accumulation signal C. Further, B, and Ai, are bounded ensure G..ü to be well defined.
Definition Tindicates that all GVFs are interrelated with a causal filtering structure, i.e., each signal C is linear function of all lower-indexed GR for < i. Definition [ also implies that the forward GVF G - GTT,I] with causal filtering satisfies the following lower-triangular Bellman equation given by
G To = B M,
(2)
where To.x denotes the forward general Bellman operator (GBO), B = [T ..,
; ,B]] and
nn Pr,1
0
A2,1
1/2 P2,2
0
Ma =
A
Ag.2
7kk Pa.k
where P_, [P, & la.1. Clearly, the canonical value function Q. and Bellman operator Ta defined in eq. ①T) is a special case of G and TG.x defined in eq. (
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, which represents the accumulation of signals that have been collected from the past. Consider a set of GVFs G2 ; is defined as the backward accumulation of vector
(... GT,,)T T, where each GVF Gz,5 signal (s,,a) IRd, given by (,,,( E -t= distinguish from the forward GVF G.,; defined in Section 2.1 we denote G.,5 as the backward GVE. For general purpose, we also consider the causal filtering setting for G., in which each C7 a) depends on the lower-indexed value functions G ".. G in the set. We define the backward GVF with causal filtering as follows.
0
7 "Ci az) ao) (s, T). To
Definition 2 (Backward GVF with causal filtering). For given policy n, backward GVF G [G GG,kk with causal filtering are associated with signals satisfying
= B, - AisG for 2 Siskk
where Ò and G_,,, are obtained by respectively stacking Úi(s, a) E Rdd and Gry(s, a) Rd over Sx A, B, E Rdil8|AA) an observable signal, and the coefficient matrix A (111 captures how the j-th GVF Ga. affects the i-th accumulation signal Ò Further, B, and Ais are bounded to ensure G.., to be well defined.

---

For an ergodic MDP that starts from -oo, we have 15-1,a,-11 ~ Mr (r((), (st, ( and (s,, a1) (x(+) for all -0 < oc. The Bayes' theorem implies that
P((s--1;a-i)((ss.
(3)
Me (st, at)
The reverse conditional probability in eq. Definition 2 implies that the backward GVFs Gx [G,,1'' , IT with causal filtering satisfies
together with the definition of backward GVF in
T==To, G B M₂
where to,- denotes the backward GBO, B = [B] B3 and
Vi P
12,1
7/2 n2
P
Mr
A
Av,2
7kk Pa.k
where PT,s = - @ 14, Wn
Off-Policy Evaluation of GVFs
3.1 Problem Formulation
In this paper, we study the GVFs evaluation problem for target policy т. We focus on the behavior- agnostic off-policy setting, in which we have access only to samples generated from an off-policy (i.e.. behavior policy) with the distribution D. i.e., (sj. aj, By, s/)) ~ D (j 0). Specifically, the state-action pair (s,,0) is sampled from a possibly unknown distribution D(.)
A -> [0, 1]. B, = [Bi ag),,. ....... (s ag)] )] is an observable signal vector, and the successor state s is sampled from P(-|s;, a.). Our goal is design efficient algorithm to estimate Gx (or G2)) given the sample set (88, aj. Bj. P5,s%)) s,)),, We make the following dataset coverage assumption.
Assumption 1. We assume that D(s, a) > for all (s,a) E ESX
3.2 Linear Function Approximation
When [S] is large, linear function can be used to approximate the GVF: GT.i(s, P (0,; a) = 0. Φz(s, a) = (0)( & la, vec(0))) where (s(s, a) E RK, is the feature vector, and 6; E RK; xd, is a learnable weight matrix. In the sequel, we omit æ in G..i and use the notation GG We make the following assumption for linear feature é, which is standard in linear function
approximation setting 45 23 55)
Assumption 2. We assume that (s,, a)l s for all i = 1, k and (s, E ESXA
The linear approximation can then be written Ge( [ & la.)vec())). where 4 is the base matrix obtained by stacking d)(s,a) over S A. To ensure the uniqueness of the solution 8, we assume that D, has linearly independent columns. The joint vector of GVFs can be denoted |GT (01),... .... G. (0x)),, which is captured by the joint parameters = [v T . vec ( E RE K,d, Then the function approximation of GVFs can be written more compactly G(0) 40, where the linear function approximation associated with each (s, a) can be written as G(O; a) = o(s, a)0, where ((s, a) = diag([óu (s, a)T @ ll....... (sx a) @ llg.)). We define the linear function space spanned by the columns of the feature matrix & F { E Ræ). in which RS is convex set. Given the function class Fo. the evaluation problem of GVFs amounts to searching for a parameter Or E Rg such that G(0*) approximates G2 (or G₂) well. In the sequel, we use Te,5 to represent Ta.x or TG interchangeably, based the context.
diag([Ø) l.,,). ... 2 & l4, For each (s, a),

---

3.3 A New Off-policyy GVF Evaluation Approach
Drawbacks of GTD. In previous works, the gradient TD (GTD) method 45
23 has been used
for policy evaluation (including GVF evaluation) in the off-policy setting 37 adopts the Mean Squared Projected Bellman Error (MSPBE) for GVF evaluation with linear function approximation, which is given by
69 70 61]. GTD
f- argminge MSPBE(() A ED [|G(0: -C.
(5)
where FT denotes the projection operator onto the space Fa w.r.t. the Il-ll,, i.e., for any vec- tor function [(s a) of (8, a). we have _== G(O,), in which 0f = argmillggR. I ( D One drawback of GTD is that the expectation in the objective function is taken over the off off-policy sampling distribution (-),, which does not exactly reflect the desirable evaluation under the target policy. As the result, the optimal point of GTD (Ô*) 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 D
Generalized Temporal Difference (GenTD) Learning. In this work, we propose novel unified approach to evaluate both the forward and backward GVFs in the off-policy setting, which we refer to generalized temporal difference (GenTD) learning. Specifically, we aim to learn 6* for GVF evaluation by minimizing the mean-square projected general Bellman error (MSPGBE) defined as
0+ = argminggR, MSPGBE(() e Ep- [|G s,)); - - FF To. G(O; [)]]
(6)
where recall that Ta, represents the GBO of either forward or backward GVFs. In contrast GTD, the objective function in eq. (6) takes the expectation over the stationary distribution μ4 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 p(s, a) = (,,(,, (x,a)/ (((, a) to adjust the
distribution and further adopt the GenD)(CH/GratienDDCC method proposed in 65 67 to estimate p(s. a) during the execution of the algorithm.
To describe our algorithm Te (see Algorithm we first note that eq. (6) implies the following optimality condition for 0 and all f E F&,
(G((";-) - G(O
(((0:)))= 2 0,
or equivalently
(o(0"), -'0))0--0)20 20, v0 Ro.
where g(0) = (G(O)
The variational inequality theory in (Chapter 3 20
suggests that under an appropriately chosen stepsize au, the update 0.+1 = n,, (0: 0.g (6:) converges to the optimal point 6", where n. denotes the projection operator onto the set RS in terms of the Euclidean norm. However, since it is intractable to explicitly compute g(f) in practice, we usually estimate (0) using random samples. In the off-policy setting, consider a sample
= (s, u, s', a'), in which (8, a) ~ D(-), s' P(-ss,a), and a' rT||s'), we can formulate the following update rule:
Oc+1 = 0, - a)g(x)
(8)
where p(s, a) is an approximation of the density ratio p(s.a) a) (r. ((s a). g(x, 0) -Ø(s, a) T 6(x, 0) for forward GVFs and g(2, 0) = (ss' a') 8(x, 0) for backward GVFs, where 5(r, 0) is the temporal difference error defined as 5(z, 0) B(s,a) + m=))(((s d')0- Ó(s, a)0 for forward GVFs, and 6(z, 0) B(s', a +m())o(s a) ((s' a0)0 for backward GVFs. Here m and in are matrices that capture the correlations between difference estimations in forward and backward GVFs evaluation settings, respectively. Here we adopt the GenDICE/GradienDDIIC method that proposed in 65 67 to learn p(s, a). In previous works, GenDIC/GradientDIC has only been used for estimating the scalar value J= = F,.,, [r(s, a)) in the off-policy setting 655 70, 53) Our work
the first to adapt this method to solve the more challenging off off-policy GVFs evaluation problem.

---

Algorithm 1 Generalized TD Learning (GenTD)
Initialize: Approximator parameters f.0, Wp,0 and 8g
for t = 0,- .... , do
Obtain sample (st, a2, Ct, ~ Da and df (T-1s/)
&. = क. (1% - -V)))
M wp.t (1h up
178)
wf.++1 = w.ss + Bel0e V. (),(((e)
Wp.t+1 I'n, (Wp.t Belv/ wg - w ujeee + meve))
Oc+1 I Ry (0g- ar ( ai)g(a,)) 0.))
Forward GVF: g(z, 0) - =(s,a) (B(s, ml())((ss a)0)
Backward GVF: g(x, 0) = - o(o', a') (B(ss, aa') + m(z))(s; "o's''''0
end for
Learning Density Ratio. GenDICE/GrraiennDDIC estimates the density ratio p(s, a) via solving the following min-max problem 65 67|:
1 min max L(p, = E - -N] - F - Enll
1 z"
(9)
P Jm
We parameterize both p and f by linear function with linearly independent features th E p(s, a; wp) = (sss,a) aa" Up and f(s, a; wy) viss (s,,a)Tw, wy for all (s,a) a) E S x the stability of the density ratio learning, we assume that the matrix A = (v " is non-singular. Note that this assumption can be removed by adding an 12- lg-reaularizer in eq. (9). In GenTD (see Algorithm[]] [ estimate the density ratio via updating the parameter wp,a iteratively. The density estimator p( 0e; Wp.) 2)((), aa)" Wp, is then used to reweight the update g(z,, 6,).
A. To guarantees
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 approximate the ground truth GVFs well with sufficiently expressive function classes. Second, GTD needs to update high-dimensional auxiliary parameter w simultaneously with 0 to stabilize the convergence, where w E RE:;; K,d, has the same dimension large in the high dimensional regime or when the number of GVFs k is very large). Such an update of w can be very costly. contrast, GenTD introduces only dinddeensiooal auxiliary parameters [up: wy, m7] E Rd for density ratio estimation, which is more efficient than GTD since dp could be much smaller than Σ K,di.
RE:_, K,d, (note that > Kid, can be very
4 Main Theorems
In this section, develop the finite-time convergence rate for our Off- Off-GenTD algorithm. To this end, we first want to establish a certain contraction property for the general Bellman operator of interest here. Although the contraction property has been proven in the canonical value function settings (55 70), it is unclear whether such property still holds for multiple multi-dimensional and interrelated GVFs. We will next establish that such a property still holds for both forward and backward GVFs with causal filtering, but needs to be under a properly chosen norm.
Consider the GVFs vector G5 [C [G,,,,'. GT We define norm I|-I|,,, associated with weighting vector
[01, .ax As, where A, denotes the simplex in k-dimensional space, as ||G=I],,,n Σ 2i 0s ||rr,illp= where < a S 1 for all and >x_ ag = 1. We also define Tmax == max:=1... I.... .k ni which is strictly less than 1.
Proposition (Contraction of Forward/Backward GBO). For any Gay G², E RISTAAEE k.d. there exists weighting vector such that
| Ta. - T Il
1+7ma | - G¹ pa.a
(10)
'The contraction property of GBO for forward GVFs has been proved in (33] but under different assumptions and with respect different norm. The result for backward GVFs is first established in our work.
7

---

where G.. can be either TG, (forward GBO, eq. ②2) or Ta (backward GBO, eq.
Despite the correlations between GVFs, Proposition I shows that the contraction property still preserved under a properly chosen norm for Tc. and TG. in forward and backward GVF settings, respectively. The norm can vary for different GVFs. Proposition Dali also implies that both forward and backward GVFs (G, and Ga) can be identified unique fixed point of their corresponding GBOs.
Based on Proposition we next establish the monotonicity property for our GenTD algorithm. if takes the population update g(0) 4 Ux (G(O) - Ta., G(
Proposition (Monotonicity). Suppose Assumption [ &2 hold. Consider the globally optimal point O" defined in eq. 7 There exists constant Àg such that for all 0 E Rg. we have
(g(00) g(0), 0r - 03 2 A 0 0 1
(1I)
where AG (1 7maxx) minigigk Sa and Ç == Amin (0. U, 2.).
Proposition 2 implics the contraction property of g()). It guarantees that moves towards a globally optimal point 0" if is updated along the direction (0) Propositionggeneeree generalizes the monotonicity
property to a much broader class of interrelated and multi-ddimensinal GVF evaluation, which is
far more beyond TD learning for the value function evaluation studied in [5 70] theorem characterizes the convergence rate of GenTD.
The following
Theorem 1. Suppose Assumption 7 &2 hold. Consider the GenTD update in Algorithm 1
Let the
stepsize 04 O(t-1) and B, = O J. We have
E[l[0r - 8" 11 I O
1600-6 8- T
+
(12)
where Ep = / EED. (p(s, w;) - p(s, a)}² is the approximation error introduced by the density ratio learning, with w defined in eq.
Theorem shows that GenTT converges to the globally optimal point 6* at a rate O1/TT) The convergence speed of 0 also depends on the conditional number Àç- where the converge becomes faster as Åg increases. Specifically, the R.H.S. of eq. (12 consists of three terms. The first term corresponds to the initialization error, which delays as fast O(1/T9). The second term corresponds to the variance error, which dominates the convergence rate of Gen to be O(1/T). The last term corresponds to non- nonnvvnishing 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 {pl w wp E R2p} increases. For more discussion about this approximation error, please refer to 65 671. The convergence analysis of GenTD is more challenging than that of TD learning 2 40 and GTD (62 17,, as need to handle additional approximation error introduced by the dynamically changing density ratio estimator p(Wp.)-
Theorem D establishes the convergence of GenTD to the globally optimal point 0* of the objective function in eq. (6). which provides the value estimation G(O*) for the GVFs. We are then interested in characterizing how close such an estimation is to the ground truth GVF Gz, which is our ultimate goal of evaluation. We characterize this in the following theorem.
Theorem (Convergence of GenTD Ground Truth). Consider Or defined in eq. (6) Suppose the same conditions in P Proposition 7 & hold. We have
|[G(0*) Gzllaa S SI [[ G - GG
Theorem indicates that the distance between the optimal estimation G(8*) and the true GVF G2 is upper bounded by the approximation error of the function class F& for the ground truth GVF Gx (note that 1'F Gz denotes the projection of G to the function approximation class F&). Hence, Theorem 2 guarantees that G(00) can be as close possible to the true GVF Gz, as long as the function class Fb is sufficiently expressive. In particular, if Fo is complete, i.e., there exists Go Fa such that Gg Gr, then GenTD is guaranteed to converge exactly to the ground truth G,, Note that Theorem 2 is the first result of such a type developed for both forward and backward GVFs.
Comparison between GenTD and GTD. If Fo is complete, GTD performs similarly to GenTD and is guaranteed to converge to the ground truth G, (see Appendix (D2 for the proof). The major difference between Ge and GTD occurs when F& is not complete. In such case, our Gen
8

---

still maintains the desirable performance as guaranteed by Theorem but the optimal point of GTD (i.e.. 6" in eq. (5) does not have guaranteed convergence to the ground truth. As shown in 10 271, even in the value function evaluation setting (a special case of forward GVF evaluation) the approximation error |GG(})) - G ll of GTD can be arbitrarily poor even if F& 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 G2 even if the function class F& 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 Fo). Consider three-state Markov chain, with transition ker- nel P [[0.1] 0.9,, 0j. [0.1, 0.9), 00,.1.0.9) discouutt factor "y = 0.99, and the reward function R = [1. 0, I]T The back value function in this MDP is given by V = =8..1555, 9.0389, 9.0184]", Sup- pose GTD is applied to solving the evaluation problem with the parameter space R RR. Then, there exists an off- policy distribution D such that using the perfect bases + = [8. 1555,,,,1 9.0389, 9.0184] the optimal point 6* learned by GTD still has non-zero approximation error, i.e., | VlID 2 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? In our experiments, we
Est. error of V Q
Est. error of V logn
30
1.2
GenTD, CFT GenTD, INCFT
25
20
GTD. CFT
GTD. INCFT
0.8
GenTD, OFT GorTD, INCFT GTD, CFT
15
0.6
10
0.4
GTD, INCFT
0
0.2
0
3
0
steps
x10
steps
x100
Figure 1: Comparison between GenTD and GTD the tasks of evaluating V Qu and V log pay
with 7 states and 2 actions (see Figure 2 in Appendix Ab. We study the problem of evaluating two dibeemsimnii GVFs, the gradient of
consider a variant of Baird's 's counterexample
Q-function: V Q, E R²4 (forward GVF), and the gradient of logarithmic stationary distribution: V. (ogg((>)) E R14 (backward GVF), associated with a soft-max policy parameterized by w E R14 We consider two types of feature matrices & 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 Fs. whereas INCFT does not have enough expressive power and cannot capture the ground true GVF exactly. The discount factor y 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 I We evaluate their performances based on the estimation error with respect to the ground truth GVF: |000 - G2 μ. Note that both V. and V., log #4 can be exactly computed tabular setting, so that the estimator error of the ground truth can be computed. For the task of V..Q evaluation, GenTD converges considerably faster and closer to the ground truth (i.e., smaller estimation error) than GTD. which can be attributed to the larger conditional number Ag of GenTD. For the task of V log μrr 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 Ex 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 wide range of multiple interrelated and possibly high-dimensional GVFs. We first showed that GVFs such a class is the fixed point of a general Bellman operator. Based on such property, Gen 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 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.
proposed new off-policy algorithm called
Acknowledge
The work T. Xu and Y. Liang was supported in part by the U.S. National Science Foundation under the grant 2148253 and 1761506.
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-different and q-learning provably converge to global optima. In Proc. Neural Information Processing Systems (NeurIPS), 2019.
[4] Y. Chandak, S. Nickum, B. C. da Silva, E. Lealed-Miller, E. Brunskill, and P. S. Thomas. Universal off- off-policy evaluation. arXiv preprint arXh::2104.12822 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 (AAAT), 2018
[8] P. D'oro and W. Jaškowski. How to learn a useful critic? model based action- iisionngradient-eee crstiatnt-esiimator policy optimization. arXiv preprint arXiv:2004. 14300, 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 2017.
[10] A. Hallak and S. Mannor. Consistent on-line off-polic 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. Frez. Learning continuous control policies by stochastic value gradients. arXiv preprint 15Xiv:1510.09142, 2015.
[13] R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge University Press, 2012.
10

---

[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 preprini arXiv:2102.01988 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. PMLR, 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 Learning Theoor (COLT), pages 2144-2203, 2020.
[18] N. Kallus and M. Uchara. Statistically efficient off- policy gradients. arXiv preprint 2Xiv:2002.040144. 2020.
[19] Kolter. The fixed points of off-policy TD. In Proc. Advances 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] Q. Liu, L.. Li, Z. Tang, and D. Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. Proc. Advances in Neural Information Processing Systems (NIPS), 31, 2018.
[23] H. R. Maei. Gradient temporal-diffeence learning algorithms. PhD thesis, University of Alberta, 2011.
[24] A. R. Mahmood and R. Sutton. Representation search through generate and test. In Proc. AAAI Workshop: Learning Rich Representations from Low-Level Sensors, 2013.
[25] S. Mannor and J.N. Tsitsiklis. Algorithmic aspects of vaannvariance optimization in markov decision processes. European Journal of Operational Research, 231(():6455655 653, 2013.
[26] T. Morimura, E. Uchibe, J. Yoshimoto, J. Peters, and K. Doya. Derivatives of logarithmic station- ary distributions for policy gradient reinforcement learning. Neural computation, 22(2):342-376, 2010.
[27] R. Munos. Error bounds for approximate policy iteration. In Proc. International Conference on Machine Learning (ICML), volume 3. pages 560-567, 2003.
[28] O. Nachum, Y. Chow, Dai, and L. Li. Dualdice: Behavior-agnoste estimation of discounted stationary distribution corrections. Proc. Advances in Neural Information Processing Systems (NIPS), 32, 2019.
[29] D. Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[30] A. Ruszczyúski. Risk-averse dynamic programming for markov decision processes. Mathemat- ical programming, 125(2):235-261, 2010.
[31] 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.
[32] T. Schaul and M. Ring. Better generalization with forecasts. In Proc. International Joint Conference on Artificial Intelligence (IJCAI), pages 1656-1662, 2013.
[33] M. Schlegel, A. Jacobsen, Z. Abbas, Patterson, A. White, and M. White. General value function networks. Journal of Artificial Intelligence Research, 70:497-543, 2021.
[34] W. F. Sharpe. Mutual fund performance. The Journal of business, 39(1):119-13) 1966.
11

---

[35] C. Sherstan. Representation and general value functions. PhD thesis, University of Alberta, 2020.
[36] S. M. Shortreed, E. Laber, D. J. Lizotte, T. Stroup, Pineau, and S. A. Murphy. Informing se- quential clinical decision-making through reinforcement learning: empirical study. Machine Learning, 84(1-2):109-1333 2011.
[37] D. Silver. Gradient temporal difference networks. In European Workshop on Reinforcement Learning, pages 117-130, 2013.
[38] D. Silver, G. Lever, N. Heess, T. Degris, Wierstra, and M. Riedmiller. Deterministic policy gradient algorithms. In Proc. International Conference on Machine Learning (ICML), pages 387-395, 2014.
[39] M. J. Sobel. The variance of discounted Markov decision processes. Journal of Applied Probability, pages 794 802, 1982.
[40] R. Srikant and L. Ying. Finite-time enror bounds for linear stochastic approximation andtd learning. In Proc. Conference on Learning Theory (COLTT), pages 2803-2830, 2019.
[41] 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.
[42] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3(1):9-44, 1988.
[43] R. S. Sutton. The grand challenge of predictive empirical abstract knowledge. In Proc. IJCAI Workshop on Grand Challenges for Reasoningfrrv Experiences, 2009.
[44] R. S. Sutton and A. G. Barto. Reinforcement Learning: An introduction. MIT press, 2018.
[45] R. S. Sutton, H. R. Maci, D. Precup, S. Bhatnagar, D. Silver, C. Szepesvári, and E. Wiewiora. Fast gradient-descent methods for cmmporal-differeen learning with linear function approx- imation. In Proc. International Conference on Machine Learning (ICML), pages 993-1000, 2009.
[46] R. S. Sutton, A. R. Mahmood, and M. White. An emphatic approach to the problem of off-policy temporal-different learning. The Journal of Machine Learning Research, 17(1):2603-206 1, 2016.
[47] R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In Proc. Advances Neural Information Processing Systems (NeurIPS), pages 1057-1063, 2000.
[48] R. S. Sutton, J. Modayil, M. Delp, T. Degris, P. M. Pilarski, A. White, and D. Precup. Horde: scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. In Proc. International Conference Autonomous Agents and Multiagent Systems, pages 761-768, 2011.
[49] R. S. Sutton, D. Precup, and S. Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 1 112(1-2)1811-111, 1999.
[50] A. Tamar, D. Di Castro, and Mannor. Policy gradients with variance related risk criteria. In Proc. International Conference on Machine Learning (ICML), pages 1651-1658, 2012.
[51] A. Tamar, D. Di Castro, and S. Mannor. Learning the variance of the reward-to-go. The Journal of Machine Learning Research, 17(1):61-336, 2016.
[52] A. Tamar and S. Mannor. Variance adjusted actor critic algorithms. arXiv preprint 1310v:1310.3699 2013.
[53] Z. Tang, Feng, I.. Li, D. Zhou, and Q. Liu. Doubly robust bias reduction infinite horizon off-policy estimation. arXiv preprint arXiv:1910.07186, 2019.
12

---

[54] P. Thomas and E. Brunskill. Data-efficient off- off-policy policy evaluation for reinforcement learning. In Proc. International Conference on Machine Learning (ICML), pages 2139 2139-2148. PMLR, 2016.
[55] J. N. Tsitsiklis and B. Van Roy. Analysis of temporal-diffferen learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 1075-1081, 1997.
[56] J. N. Tsitsiklis and B. Van Roy. Average cost temporal-diiffrence learning. In Proc. IEEE Conference on Decision and Control, volume I, pages 498-502, 1997.
[57] A. White et al. Developing a predictive approach to knowledge. 2015.
[58] T. Xu and Liang. Sample complexity bounds for two timescale value- reinforcement learning algorithms. In Proc. International Conference Artificial Intelligence and Statisties (AISTATS), pages 81 811-819, 2021.
[59] T. Xu, Z. Wang, and Y. Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. In Proc. Advances Neural Information Processing Systems (NeurIPS), 33, 2020.
[60] T. Xu, Z. Wang, and Y. Liang. Non-asymptotic convergence analysis of two time-scale (natural) actor-critic algorithms. arXiv preprint arXiv:2005.033577 2020.
[61] T. Xu, Z. Yang. Z. Wang, and Y. Liang. Doubly robust off-policy actor-critic: convergence and optimality, 2021.
[62] Xu, S. Zou, and Liang. Two time-scale off- off-policy TD learning: Mon-asymptotic anal- ysis over markovian samples. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 10633-10643, 2019.
[63] H. Yao and D. Schuurmans. Reinforcement ranking. arXiv preprint arXiv: 1303.5998 2013.
[64] 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.021511 2020.
[65] R. Zhang, B. Dai, L. Li, and D. Schuurmans. Gendice: generalized offline estimation of stationary values. arXiv preprint arXhv:2002.09072, 2020.
[66] 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. 2019.
[67] 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 12033 2020.
[68] 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.
[69] 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 (ICMI.), pages 1 11204-11211 2020.
[70] S. Zhang, V. Veeriah, and S. Whiteson. Learning retrospective knowledge with reverse rein- forcement learning, Proc. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
[71] Zhang and S. Whiteson. DAC: The double actor-critic architecture for learning options. arXiv e-prints, pages arXiv-1904, 2019.
13

---

Checklist
Did you include the license the code and datasets? [No] The code and the data are The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] - You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [No]
proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 'rere using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xPD7JCMW0Ks", "reviewer": "Reviewer_5ZXZ", "summary": "The paper proposes a new off-policy algorithm to evaluate forward and backward general value functions that have the property of causal filtering. They show that the existing algorithm (GTD) fails in this (for example, failing to compute the ground truth GVF) and propose an algorithm to overcome its shortcomings.\n\nThanks to the authors for putting in the effort in doing this work!\n", "questions": "Questions:\n- I’m a bit wary of the dependence that GenTD has on the function class being expressive enough given that performance degrades a lot if this assumption is not met (CFT vs. INCFT). Three subpoints: a) Even in the case presented in Section 5 (the CFT case), they don’t seem to achieve perfectly 0 error in the left graph of Figure 1. I’d imagine that in this relatively simplified setting, zero error could be achieved. b) The plots of INCFT suggest that performance drastically deteriorates when the assumption of expressiveness of the function class does not hold, which is a bit concerning since we wouldn't want an algorithm that has such a strong dependence on this function class expressiveness assumption. If performance degraded only slightly, then it would be another thing. c) It may also be the case that the CFT example used in the experiments is an extreme worst case. If that is so, then I recommend the authors vary the degree of failure of the assumption holding and see how sensitive GenTD is at different levels of the assumption holding true.\n\nSuggestions:\n- Title has a spelling mistake “evaluatio”\n- For Figure 1, could the y-axis labels be made more clearer. The labeling of only 0 and 30 doesnt make it clear what exactly the errors are.\n- The concept of GVF is relatively niche and so it must be made clear what GVFs actually are, for example in the intro. Its difficult to follow the intention of the work and what is exactly trying to be solved until Section 2 is reached.\n\n", "limitations": "No, they do not address it, but this seems to be more fundamental work with no direct societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- I think this is an important area to research. GVFs are relatively under-researched and it's important to see this type of work.\n- The 1) use of the concrete example on line 140 was helpful to communicate the idea of GVFs; 2) the comparisons between GenTD and GTD was also nice.\n\nWeaknesses:\n- Given that the concept of GVFs is unique and somewhat niche, I think the authors should be clearer on what GVFs exactly are (see suggestions below).\n- The experimental section seems rather limited. The cited paper on GVFs General value function networks, 2021, seems to have a pretty detailed experimental section. It would be interesting to see how the proposed algorithm scales to harder domains.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "T9VL-U2wTHe", "reviewer": "Reviewer_Ld7J", "summary": "The paper considers evaluating multiple interrelated general value functions using offline data. A generalized TD learning algorithm is developed and its theoretical properties are analyzied in detail. The strengths and weaknesses of the paper are given in the next section. The contributions of the paper are mainly theoretical and include (1) establishment of the contraction property for both forward and backward value functions; (2) development of a generalized TD learning algorithm to overcome the limitations of previous baseline methods; (3) convergence analysis of the proposed algorithm; (4) identification of sufficient conditions under which the proposed algorithm would converge. ", "questions": "Please refer to **Strengths and Weaknesses**", "limitations": "The main limitation includes the linearity assumption as well as a lack of extensive empirical studies. The former was partly discussed in the discussion where nonlinear function approximation was mentioned. ", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper evaluates both forward and backward general value functions. Despite the richness of the literature on off-policy evaluation, these general value functions are less studied. In that sense, the paper targets an interesting research problem. \n2. The proposed method considers multiple interrelated general value functions jointly rather than on a case-by-case basis. \n3. A generalized TD learning algorithm is proposed to address the limitations of the gradient TD methods.\n4. Convergence of the model parameter and the estimated value functions are investigated in detail.\n\nSome comments: \n\n1. There is a typo in the title of the pdf file. In addition, there is a question mark in the checklist. \n2. The linearity assumption is quite strong. The algorithm might perform poorly in nonlinear systems with high-dimensional state information.\n3. It remains unclear to me if the variance of \"the reward to go\" (mentioned on L23) can be represented in the form of the general value function. In particular, the variance of the cumulative reward would involve the interaction term that measures the covariance of the rewards at different time points. \n4. Can you allow $B_j$ to be unobservable? The gradient of the value function (mentioned on L26) does not seem to be an observable quantity. It might be more useful to cover cases where $B_j$ needs to be estimated from the data as well. \n5. The literature on off-policy evaluation with a general scalar value function is not thoroughly reviewed. In addition, it was mentioned on P2, L92 that these methods are not directly comparable. However, I do not agree with this argument. Suppose the initial state-action distribution concentrates on a particular state-action pair, then the value function is reduced to the state-action value. Combined with a kernel-type estimator, existing OPE methods such as (marginal) importance sampling, double robust estimation (double reinforcement learning) can be potentially applied to this setting. It remains unclear to me whether the proposed estimator is better. \n6. The numerical study is oversimplified. It considers a simple toy example with 7 states and 2 actions. More extensive simulations based on e.g., OpenAI gym environments are needed to test the empirical performance of the proposed algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SH1VBIYbDQA", "reviewer": "Reviewer_MWog", "summary": "The problem formulation this paper is concerned with is the General Value Function (GVF) approximation task, where the algorithm's task is to estimate a vector which is defined as an expectation of some algebraic manipulation of the signals received. This vector is named a GVF.  On this task, the authors mainly compared their approach with another existing method called Gradient Temporal Difference (GTD). The main observation of this paper is that the goal of GTD is to minimize the empirical Mean Squared Projected Bellman Error (MSPBE), whereas a more legit goal would be the expected mean-squared projected Bellman error which they name as the Mean Squared Projected General Bellman Error (MSPGBE). To account for the shift from the empirical (data-dependent) mean to the expected mean, they applied an existing density ratio estimation method. ", "questions": "I understand that I might be asking a question that might have been addressed by other papers, but again, why is density ratio the right thing to estimate? There are other types of divergences too, is there something special about RL that makes density ratio easy to estimate?\n\nCould you explain why for the counter-example you proposed for GTD, why would GenTD work? Or is the counter-example merely evidence that GTD is not perfect?", "limitations": "I guess assumptions count for limitations. A better limitation from my point of view would be to specify for which interesting classes of RL tasks, the algorithm GenTD wouldn't work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\\\n    Originality: The motivation is legit.\\\n    Quality: The logic chain works through, it is clear what they are doing. \\\n    Clarity: The story is easy to read. (I didn't check any proof.)\\\n\n\nWeakness:\\\n    Significance: \\\n        1. Seems A+B, where A = GTD, B = density ratio estimation.\\\n        2. More precisely, I put this as a weakness because personally, I don't quite get the logic why learning density ratio would be more accurate. The authors put as a counter-example where GTD fails for Complete F_\\Phi. However, if for the same example, the density ratio is not learned very well, why would GenTD work?\n   \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1mei6E6B58W", "reviewer": "Reviewer_bpnm", "summary": "This paper proposes a new method called GenTD for off-policy evaluation of GVFs. The algorithm can further estimate multiple intercorrelated GVFs at once under some reasonable (causal) assumptions. The contributions are mainly theoretical (convergence proofs). Some empirical evaluation on a small MDP is provided.", "questions": "- L259 could you comment on the choice and importance of psi?\n- L260, you assume the matrix A to be non-singular, however if psi' is intended to be P_pi \\Psi, then shouldn't this matrix be singular because it contains I - P_\\pi which is singular?\n- I am puzzled by the strength of the convergence results you have using only A1 and A2. For instance, why doesn't it suffer from deadly-triad-like issues? I had expected to see some assumptions on the spectrum of some matrices related to phi, P and D.\n\nMinor:\n- What is R_\\theta L241? I may have missed the definition\n- I may also have missed the definition/intuition behind m(x) L251\n- I may also have missed the definition of the F-norm L296", "limitations": "Limitations are mentioned above. Beyond the questions on the theory, the limitations appear most on the practical side. In the paper the empirical evaluation may be lacking and thus making it harder to convince the community that this algorithm would be a safe and efficient one. More broadly, it is not clear to me how this algorithm would be extended to the non-linear setting.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\nOverall, the paper tackles an interesting problem, identifies a shortcoming of previous algorithms and proposes a solution with theoretical guarantees. I found it overall pretty clear.\n\n# Weaknesses\n\n## Scalability\nI have some concerns about the scalability of the method and whether it could extent beyond the linear regime. In particular, Alg 1 requires some projections step that may not make sense in the non-linear regime. Could authors comment on whether they think it is an issue?\n\n## Experiments\nThe experimental validation is weak in my opinion. I understand this is a theory paper and the main contribution is the algorithm and its guarantees, however I believe it is also in the authors interest to showcase that the algorithm performs well on environments more complex. In particular, GenDICE which this work builds upon had some empirical evaluation on non-trivial gridworlds as well as a simple control (Half-Cheetah) environment.\nAs far as I know, methods based on min-max problems (DualDICE etc) are known to be quite unstable, so I think it is important that you showcase the robustness of your algorithm.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept