The Fixed Points of Off-Policy TD

J. Zico Kolter
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology
Cambridge, MA 02139
kolter@csail.mit.edu

Abstract
Off-policy learning, the ability for an agent to learn about a policy other than the
one it is following, is a key element of Reinforcement Learning, and in recent
years there has been much work on developing Temporal Different (TD) algorithms that are guaranteed to converge under off-policy sampling. It has remained
an open question, however, whether anything can be said a priori about the qualityof the TD solution when off-policy sampling is employed with function approximation. In general the answer is no: for arbitrary off-policy sampling the errorof the TD solution can be unboundedly large, even when the approximator canrepresent the true value function well. In this paper we propose a novel approachto address this problem: we show that by considering a certain convex subset ofoff-policy distributions we can indeed provide guarantees as to the solution quality
similar to the on-policy case. Furthermore, we show that we can efficiently project
on to this convex set using only samples generated from the system. The end result is a novel TD algorithm that has approximation guarantees even in the case ofoff-policy sampling and which empirically outperforms existing TD methods.

1

Introduction

In temporal prediction tasks, Temporal Difference (TD) learning provides a method for learning
long-term expected rewards (the “value function”) using only trajectories from the system. The
algorithm is ubiquitous in Reinforcement Learning, and there has been a great deal of work studying
the convergence properties of the algorithm. It is well known that for a tabular value function
representation, TD converges to the true value function [3, 4]. For linear function approximation
with on-policy sampling (i.e., when the states are drawn from the stationary distribution of the policy
we are trying to evaluate), the algorithm converges to a well-known fixed point that is guaranteed
to be close to the optimal projection of the true value function [17]. When states are sampled offpolicy, standard TD may diverge when using linear function approximation [1], and this has led inrecent years to a number of modified TD algorithms that are guaranteed to convergence even in thepresence of off-policy sampling [16, 15, 9, 10].
Of equal importance, however, is the actual quality of the TD solution under off-policy sampling.
Previous work, as well as an example we present in this paper, show that in general little can be said
about this question: the solution found by TD can be arbitrarily poor in the case of off-policy sampling, even when the true value function is well-approximated by a linear basis. Pursing a slightly
different approach, other recent work has looked at providing problem dependent bounds, which use
problem-specific matrices to obtain tighter bounds than previous approaches [19]; these bounds canapply to the off-policy setting, but depend on problem data, and will still fail to provide a reasonablebound in the cases mentioned above where the off-policy approximation is arbitrarily poor. Indeed,a long-standing open question in Reinforcement Learning is whether any a priori guarantees can bemade about the solution quality for off-policy methods using function approximation.
In this paper we propose a novel approach that addresses this question: we present an algorithm thatlooks for a subset of off-policy sampling distributions where a certain relaxed contraction property
1holds; for distributions in this set, we show that it is indeed possible to obtain error bounds on thesolution quality similar to those for the on-policy case. Furthermore, we show that this set of feasible
off-policy sampling distributions is convex, representable via a linear matrix inequality (LMI), andwe demonstrate how the set can be approximated and projected onto efficiently in the finite sample
setting. The resulting method, which we refer to as TD with distribution optimization (TD-DO),is thus able to guarantee a good approximation to the best possible projected value function, evenfor off-policy sampling. In simulations we show that the algorithm can improve significantly overstandard off-policy TD.

2Preliminaries and Background

A Markov chain is a tuple, (S, P, R, γ), where S is a set of states, P : S × S → R+ is a transition
probability function, R : S → R is a reward function, and γ ∈ [0, 1) is a discount factor. For
simplicity of presentation we will assume the state space is countable, and so can be indexed by
the set S = {1, . . . , n}, which allows us to use matrix rather than operator notation. The valuefunction for a Markov chain, P
V : S → R maps states to their long term discounted sum of rewards,∞
and is defined as V (s) = E [ t=0 γ t R(st )|s0 = s]. The value function may also be expressed via
Bellman’s equation (in vector form)
V = R + γP V
(1)where R, V ∈ Rn represent vectors of all rewards and values respectively, and P ∈ Rn×n is amatrix of probability transitions Pij = P (s′ = j|s = i).
In linear function approximation, the value function is approximated as a linear combination ofsome features describing the state: V (s) ≈ wT φ(s), where w ∈ Rk is a vector of parameters, andφ : S → Rk is a function mapping states to k-dimensional feature vectors; or, again using vector
notation, V ≈ Φw, where Φ ∈ Rn×k is a matrix of all feature vectors. The TD solution is a fixed
point of the Bellman operator followed by a projection, i.e.,⋆⋆
ΦwD= ΠD (R + γP ΦwD)(2)
where ΠD = ΦT (ΦT DΦ)−1 ΦT D is a projection matrix weighted by the diagonal matrix D ∈Rn×n . Rearranging terms gives the analytical solution
−1 T
⋆
wD
= ΦT D(Φ − γP Φ)
Φ DR.
(3)
Although we cannot expect to form this solution exactly when P is unknown and too large to represent, we can approximate the solution via stochastic iteration (leading to the original TD algorithm),or via the least-squares TD (LSTD) algorithm, which forms the matrices
m
m


1 X
1 X
(i)
ŵD = Â−1 b̂, Â =φ(s(i) ) φ(s(i) ) − γφ(s′ ) , b̂ =φ(s(i) )r(i)
(4)
m i=1
m i=1
(i)

(i)
∼ D. When D
given a sequence of states, rewards, and next states {s(i) , r(i) , s′ }mi=1 where s
is not the stationary distribution of the Markov chain (i.e., we are employing off-policy sampling),
then the original TD algorithm may diverge (LSTD will still be able to compute the TD fixed pointin this case, but has a greater computational complexity of O(k 2 )). Thus, there has been a great dealof work on developing O(k) algorithms that are guaranteed to converge to the LSTD fixed point
even in the case of off-policy sampling [16, 15].

We note that the above formulation avoids any explicit mention of a Markov Decision Process(MDP) or actual policies: rather, we just have tuples of the form {s, r, s′ } where s is drawn froman arbitrary distribution but s′ still follows the “policy” we are trying to evaluate. This is a standard
formulation for off-policy learning (see e.g. [16, Section 2]); briefly, the standard way to reach thissetting from the typical notion of off-policy learning (acting according to one policy in an MDP, but
evaluating another) is to act according to some original policy in an MDP, and then subsample only
those actions that are immediately consistent with the policy of interest. We use the above notation as it avoids the need for any explicit notation of actions and still captures the off-policy setting
completely.
2.1

Error bounds for the TD fixed point

Of course, in addition to the issue of convergence, there is the question as to whether we can say anything about the quality of the approximation at this fixed point. For the case of on-policy sampling,
the answer here is an affirmative one, as formalized in the following theorem.
2

4

Approximation Error

10

TD Solution

2

10

Optimal Approximation

0

10

−2

10

−4

10

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

p

Figure 1: Counter example for off-policy TD learning: (left) the Markov chain considered for thecounterexample; (right) the error of the TD estimate for different off-policy distributions (plotted ona log scale), along with the error of the optimal approximation.
⋆⋆
Theorem 1. (Tsitsiklis and Van Roy [17], Lemma 6) Let wD
be the unique solution to ΦwD=⋆ΠD (R + γP ΦwD ) where D is the stationary distribution of P . Then
1⋆kΦwD
− V kD ≤kΠD V − V kD .
(5)1−γ

Thus, for on-policy sampling with linear function approximation, not only does TD converge to its
fixed point, but we can also bound the error of its approximation relative to kΠD V − V kD , thelowest possible approximation error for the class of function approximators.1
Since this theorem plays an integral role in the remainder of this paper, we want to briefly give theintuition of its proof. A fundamental property of Markov chains [17, Lemma 1] is that transition
matrix P is non-expansive in the D norm when D is the stationary distribution
kP xkD ≤ kxkD , ∀x.
(6)
From this it can be shown that the Bellman operator is a γ-contraction in the D norm and Theorem 1
follows. When D is not the stationary distribution of the Markov chain, then (6) need not hold, andit remains to be seen what, if anything, can be said a priori about the TD fixed point in this situation.

3

An off-policy counterexample

Here we present a simple counter-example which shows, for general off-policy sampling, that theTD fixed point can be an arbitrarily poor approximator of the value function, even if the chosenbases can represent the true value function with low error. The same intuition has been presented
previously [11]. though we here present a concrete numerical example for illustration.
Example 1. Consider the two-state Markov chain shown in Figure 1, with transition probability
matrix P = (1/2)11T , discount factor γ = 0.99, and value function V = [1 1.05]T (with R =(I − γP )V ). Then for any ǫ > 0 and C > 0, there exists an off-policy distribution D such thatusing bases Φ = [1 1.05 + ǫ]T gives⋆kΠD V − V k ≤ ǫ, and kΦwD
− V k ≥ C.
(7)
Proof. (Sketch) The fact that kΠD V − V k ≤ ǫ is obvious from the choice of basis. To show that
the TD error can be unboundedly large, let D = diag(p, 1 − p); then, after some simplification, theTD solution is given analytically by−2961 + 4141p − 2820ǫ + 2820pǫ
⋆
(8)
wD
=
−2961 + 4141p − 45240ǫ + 84840pǫ − 40400ǫ2 + 40400pǫ2
which is infinite, (1/w = 0), when
2961 + 45240ǫ + 40400ǫ2.
(9)4141 + 84840ǫ + 40400ǫ2⋆
Since this solution is in (0, 1) for all epsilon, by choosing p close to this value, we can make wD
arbitrarily large, which in turn makes the error of the TD estimate arbitrarily large.
p=

1

The approximation factor can be sharpened to √ 1

1−γ 2

in some settings [18], though the analysis does notcarry over to our off-policy case, so we present here the simpler version.

3

Figure 1 shows a plot of kΦw⋆ − V k2 for the example above with ǫ = 0.001, varying p from 0 to
1. For p ≈ 0.715 the error of the TD solution approaches infinity; the essential problem here is thatwhen D is not the stationary distribution of P , A = ΦT D(Φ − γP Φ) can become close to zero (orfor the matrix case, one of its eigenvalues can become zero), and the TD value function estimate cangrow unboundedly large. Thus, we argue that simple convergence for an off-policy algorithm is nota sufficient criterion for a good learning system, since even for a convergent algorithm the quality of
the actual solution could be arbitrarily poor.

4

A convex characterization of valid off-policy distributions

Although it may seem as though the above example would imply that very little could be said about
the quality of the TD fixed point under off-policy sampling, in this section we show that by imposing
additional constraints on the sampling distribution, we can find a convex family of distributions forwhich it is possible to make guarantees.
To motivate the approach, we again note that error bounds for the on-policy TD algorithm follow
from the Markov chain property that kP xkD ≤ kxkD for all x when D is the stationary distribution. However, finding a D that satisfies this condition is no easier than computing the stationary
distribution directly and thus is not a feasible approach. Instead, we consider a relaxed contraction
property: that the transition matrix P followed by a projection onto the bases will be non-expansive
for any function already in the span of Φ. Formally, we want to consider distributions D for whichkΠD P ΦwkD ≤ kΦwkD

(10)

k

for any w ∈ R . This defines a convex set of distributions, sincekΠD P Φwk2D ≤ kΦwk2D⇔⇔

wT ΦT P T DΦ(ΦT DΦ)−1 ΦT DΦ(ΦT DΦ)−1 ΦDP ΦT w ≤ wT ΦT DΦw
wT ΦT P T DΦ(ΦT DΦ)−1 ΦDP ΦT − ΦT DΦ w ≤ 0.

(11)This holds for all w if and only if2

ΦT P T DΦ(ΦT DΦ)−1 ΦDP ΦT − ΦT DΦ  0
which in turn holds if and only if

(12)

3

F ≡



ΦT DΦ
ΦT DP ΦT T
Φ P DΦ ΦT DΦ



0

(13)

This is a matrix inequality (LMI) in D, and thus describes a convex set. Although the distribution D
is too high-dimensional to optimize directly, analogous to LSTD, the F matrix defined above is of arepresentable size (2k × 2k), and can be approximated from samples. We will return to this point in
the subsequent section, and for now will continue to use the notation of the true distribution D for
simplicity. The chief theoretical result of this section is that if we restrict our attention to off-policy
distributions within this convex set, we can prove non-trivial bounds about the approximation errorof the TD fixed point.
Theorem 2. Let w⋆ be the unique solution to Φw⋆ = ΠD (R+γP Φw⋆ ) where D is any distribution
1/2
satisfying (13). Further, let Dµ be the stationary distribution of P , and let D̄ ≡ D−1/2 Dµ Then4⋆kΦwD− V kD ≤1 + γκ(D̄)
kΠD V − V kD .
1−γ

(14)

The bound here is of a similar form to the previously stated bound for on-policy TD, it bounds
the error of the TD solution relative to the error of the best possible approximation, except for
the additional γκ(D̄) term, which measures how much the chosen distribution deviates from thestationary distribution. When D = Dµ , κ(D̄) = 1, so we recover the original bound up to a
constant factor. Even though the bound does include this term that depends on the distance fromthe stationary distribution, no such bound is possible for D that do not satisfy the convex constraint(13), as illustrated by the previous counter-example.
2

A  0 (A  0) denotes that A is negative (positive)
semidefinite.
»–
A B
Using the Schur complement property that 0 ⇔ B T AB − C  0 [2, pg 650-651].
T
B
C
4
κ(A) denotes the condition number of A, the ratio of the singular values κ(A) = σmax (A)/σmin (A).
3

4

4

10

Approximation Error

TD Solution
Optimal Approximation

2

10

Feasible Region

0

10

−2

10

−4

10

0

0.1

0.2

0.3

0.4

0.5
p

0.6

0.7

0.8

0.9

1

Figure 2: Counter example from Figure 1 shown with the set of all valid distributions for whichF  0. Restricting the solution to this region avoids the possibility of the high error solution.
Proof. (of Theorem 2) By the triangle inequality and the definition of the TD fixed point,⋆⋆kΦwD− V kD ≤ kΦwD
− ΠD V kD + kΠD V − V kD⋆
= kΠD (R + γP ΦwD) − ΠD (R + γP V )kD + kΠD V − V kD⋆
= γkΠD P ΦwD − ΠD P V kD + kΠD V − V kD⋆
≤ γkΠD P ΦwD− ΠD P ΠD V kD + γkΠD P ΠD V − ΠD P V kD + kΠD V − V kD .
(15)

Since ΠD V = Φw̄ for some w̄, we can use the definition of our contraction kΠD P ΦwkD ≤ kΦwkD
to bound the first term as⋆⋆⋆kΠD P ΦwD
− ΠD P ΠD V kD ≤ kΦwD
− ΠD V kD ≤ kΦwD
− V kD .

(16)

Similarly, the second term in (15) can be bounded askΠD P ΠD V − ΠD P V kD ≤ kP ΠD V − P V kD ≤ kP kD kΠD V − V kD

(17)where kP kD denotes the matrix norm kAkD ≡ maxkxkD ≤1 kAxkD . Substituting these bounds
back into (15) gives⋆(1 − γ)kΦwD− V kD ≤ (1 + γkP kD )kΠD V − V kD ,(18)

so all the remains is to show that kP kD ≤ κ(D̄). To show this, first note that kP kDµ = 1, since
max kP xkDµ ≤kxkDµ ≤1

max kxkDµ = 1,

kxkDµ ≤1

(19)

and for any nonsingular D,
kP kD = max kP xkD = max
kxkD ≤1

kyk2 ≤1p
y T D−1/2 P T DP D−1/2 y = kD1/2 P D−1/2 k2 .

(20)

Finally, since Dµ and D are both diagonal (and thus commute),

kD1/2 P D−1/2 k2 = kDµ−1/2 D1/2 Dµ1/2 P Dµ−1/2 D−1/2 Dµ1/2 k2≤ kDµ−1/2 D1/2 k2 kDµ1/2 P Dµ−1/2 k2 kD−1/2 Dµ1/2 k2= kDµ−1/2 D1/2 k2 kD−1/2 Dµ1/2 k2 = κ(D̄)
The final form of the bound can be quite loose of, course, as many of the steps involved in the proof
used substantial approximations and discarded problem specific data (such as the actual kΠD P kD
term in favor of the generic κ(D̄) term, for instance). This is in constrast to the previously mentioned
work of Yu and Bertsekas [19] that uses these and similar terms to obtain much tigher, but data
dependent, bounds. Indeed, applying a theorem from this work we can arrive as a slight improvementof the bound above [13], but the focus here is just on the general form and possibility of the bound.
Returning to the counter-example from the previous section, we can visualize the feasible region
for which F  0, shown as the shaded portion in Figure 2, and so constraining the solution tothis feasible region avoids the possibility of the high error solution. Moreover, in this example theoptimal TD error occurs exactly at the point where λmin (F ) = 0, so that projecting an off-policy
distribution onto this set will give an optimal solution for initially infeasible distributions.
54.1

Estimation from samples

Returning to the issue of optimizing this distribution only using samples from the system, we note(i)that analogous to LSTD, for samples {s(i) , r(i) , s′ }m
i=1
#
"
m
m
(i)
X
(i)
(i)
T
1
1 X
φ(s )φ(s )φ(s(i) )φ(s′ )T
F̂ =
≡
F̂i
(21)
(i)
m i=1 φ(s′ )φ(s(i) )T φ(s(i) )φ(s(i) )Tm i=1

will be an unbiased estimate of the LMI matrix F (for a diagonal matrix D given the our sampling
distribution over s(i) ). Placing a weight di on each sample, we could optimize the sum F̂ (d) =Pm
i=1 di F̂i and obtain a tractable optimization problem. However, optimizing these weights freely is
not permissible, since this procedure allows us to choose di 6= dj even if s(i) = s(j) , which violates
the weights in the original LMI. However, if we additionally require that s(i) = s(j) ⇒ di = dj(or more appropriately for continuous features and states, for example that kdi − dj k → 0 askφ(s(i) ) − φ(s(j) )k → 0 according to some norm) then we are free to optimize over these empirical
distribution weights. In practice, we want to constrain this distribution in a manner commensuratewith the complexity of the feature space and the number of samples. However, determining the bestsuch distributions to use in practice remains an open problem for future work in this area.
Finally, since many empirical distributions satisfy F̂ (d)  0, we propose to “project” the empirical
distribution onto this set by minimizing the KL divergence between the observed and optimized
distributions, subject to the constraint that F̂ (d)  0. Since this constraint is guaranteed to hold at
the stationary distribution, the intuition here is that by moving closer to this set, we will likely obtaina better solution. Formally, the final optimization problem, which we refer to as the TD-DO method(Temporal Difference Distribution Optimization), is given by
m
X

min
d

−p̂i log dis.t. , 1T d = 0, F̂ (d)  0, d ∈ C.

(22)

i=1

where C is some convex set that respects the metric constraints described above. This is a convex optimization problem in d, and thus can be solved efficiently, though off-the-shelf solvers can perform
quite poorly, especially for large dimension m.
4.2

Efficient Optimization

Here we present a first-order optimization method based on solving the dual of (22). By properly
exploiting the decomposability of the objective and low-rank structure of the dual problem, wedevelop an iterative optimization method where each gradient step can be computed very efficiently.
The presentation here is necessarily brief due to space constraints, but we also include a longer
description and an implementation of the method in the supplementary material. For simplicity we
present the algorithm ignoring the constraint set C, though we discuss possible additonal constraints
briefly in supplementary material.
We begin by forming the Lagrangian of (22), introducing Lagrange multipliers Z ∈ R2k×2k for theconstraint F̂ (d)  0 and ν ∈ R for the constraint 1T d = 1. This leads to the dual optimization
problem)( m
XTTp̂i log di − tr(Z F̂ (d)) + ν(1 d − 1) .
(23)
max min −
Z0,ν

d

i=1

Treating Z as fixed, we maximize over ν and minimize over d in (23) using an equality-constrained,feasible start Newton method [2, pg 528]. Since the objective is separable over the di ’s the Hessian
matrix is diagonal, and the Newton step can be computed in O(m) time; furthermore, since wesolve this subproblem for each update of dual variables Z, we can warm-start Newton’s methodfrom previous solutions, leading to a number of Newton steps that is virtually constant in practice.
Considering now the maximization over Z, the gradient of
(
)
X
⋆
T
⋆
⋆
T ⋆
g(Z) ≡−pˆi log di (Z) − trZ F̂ (d (Z)) + ν (Z)(1 d (Z) − 1)
i

6

(24)

0.4
Off−policy TD
Off−policy TD−DO
On−policy TD
Optimal Projection

0.8

Normalized Approximation Error

Normalized Approximation Error

1

0.6

0.4

0.2

0
2

3

4

5
6
7
Number of Bases89Off−policy TD
Off−policy TD−DO
On−policy TD
Optimal Projection

0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
2

10

3

4

5
6
7
Number of Bases

8

9

10

Figure 3: Average approximation error of the TD methods, using different numbers of bases functions, for the random Markov chain (left) and diffusion chain (right).
0.25
Off−policy TD
Off−policy TD−DO
On−policy TD
Optimal Projection

1.5

Normalized Approximation Error

Normalized Approximation Error

2

1

0.5

0 0
10

1

2

10
10
Closeness to Stationary Distribution, C

Off−policy TD
Off−policy TD−DO
On−policy TD
Optimal Projection

0.2

0.15

0.1

0.05

0 0
10

3

10
mu

1

2

10
10
Closeness to Stationary Distribution, C

3

10
mu

Figure 4: Average approximation error, using off-policy distributions closer or further from thestationary distribution (see text) for the random Markov chain (left) and diffusion chain (right).
0.8
Off−policy TD
Off−policy TD−DO
On−policy TD

Normalized Approximation Error

Normalized Approximation Error

1.5

1

0.5

0 2
10

3

10
Number of Samples

0.6
0.5
0.4
0.3
0.2
0.1
0 2
10

4

10

Off−policy TD
Off−policy TD−DO
On−policy TD

0.7

3

10
Number of Samples

4

10

Figure 5: Average approximation error for TD methods computed via sampling, for different numbers of samples, for random Markov chain (left) and diffusion chain (right).
is given simply by ∇Z g(Z) = −F̂ (d⋆ (Z)). We then exploit the fact that we expect Z to typically be
low-rank: by the KKT conditions for a semidefinite program F̂ (d) and Z will have complementaryranks, and since we expect F̂ (d) to be nearly full rank at the solution, we factor Z = Y Y T for
Y ∈ Rk×p with p ≪ k. Although this is now a non-convex problem, local optimization of thisobjective is still guaranteed to give a global solution to the original semidefinite problem, provided
we choose the rank of Y to be sufficient to represent the optimal solution [5]. The gradient of thistransformed problem is ∇Z g(Y Y T ) = −2F̂ (d)Y , which can be computed in time O(mkp) sinceeach F̂i term is a low-rank matrix, and we optimize the dual objective via an off-the-shelf LBFGS
solver [12, 14]. Though it is difficult to bound p aprirori, we can check after the solution that ourchosen value was sufficient for the global solution, and we have found that very low values (p = 1
or p = 2) were sufficient in our experiments.

5

Experiments

Here we present simple simulation experiments illustrating our proposed approach; while the evaluation is of course small scale, the results highlight the potential of TD-DO to improve TD algorithms
both practically as well as theoretically. Since the benefits of the method are clearest in terms of
7

0.19

0.22
Off−policy TD−DO
Normalized Approximation Error

Normalized Approximation Error

Off−policy TD−DO
0.18
0.17
0.16
0.15
0.14
0.13
0.12
20

30

40

50
60
70
Number of Clusters

80

90

0.2
0.18
0.16
0.14
0.12
0.1
0.08
5

100

10

15

20
25
30
35
40
Number of LBFGS Iterations

45

50

Figure 6: (Left) Effect of the number of clusters for sample-based learning on diffusion chain,(Right) performance of algorithm on diffusion chain versus number of LBFGS iterations
the mean performance over many different environments we focus on randomly generated Markov
chains of two types: a random chain and a diffusion process chain.5
Figure 3 shows the average approximation error of the different algorithms with differing numbersof basis function, over 1000 domains. In this and all experiments other than those evaluating theeffect of sampling, we use the full Φ and P matrices to compute the convex set, so that we are
evaluating the performance of the approach in the limit of large numbers of samples. We evaluate
the approximation error kV̂ − V kD where D is the off-policy sampling distribution (so as to be
as favorable as possible to off-policy TD). In all cases the TD-DO algorithm improves upon theoff-policy TD, though the degree of improvement can vary from minor to quite significant.
Figure 4 shows a similar result for varying the closeness of the sampling distribution to thestationary distribution; in our experiments, the off-policy distribution is sampled according to
D ∼ Dir(1 + Cµ µ) where µ denotes the stationary distribution. As expected, the off-policy approaches perform similarly for larger Cµ (approaching the stationary distribution), with TD-DO
having a clear advantage when the off-policy distribution is far from the stationary distribution.
In Figure 5 we consider the effect of sampling on the algorithms. For these experiments we employ asimple clustering method to compute a distribution over states d that respects the fact that φ(s(i) ) =φ(s(j) ) ⇒ di = dj : we group the sampled states into k clusters via k-means clustering on thefeature vectors, and optimize over the reduced distribution d ∈ Rk . In Figure 6 we vary the numberof clusters k for the sampled diffusion chain, showing that the algorithm is robust to a large numberof different distributional representations; we also show the performance of our method varying thenumber of LBFGS iterations, illustrating that performance generally improves monotonically.

6

Conclusion

The fundamental idea we have presented in this paper is that by considering a convex subset ofoff-policy distributions (and one which can be computed efficiently from samples), we can provide
performance guarantees for the TD fixed point. While we have focused on presenting error bounds
for the analytical (infinite sample) TD fixed point, a huge swath of problems in TD learning arise
from this same off-policy issue: the convergence of the original TD method, the ability to find theℓ1 regularized TD fixed point [6], the on-policy requirement of the finite sample analysis of LSTD[8], and the convergence of TD-based policy iteration algorithms [7]. Although left for future work,
we suspect that the same techniques we present here can also be extending to these other cases,
potentially providing a wide range of analogous results that still apply under off-policy sampling.
Acknowledgements. We thank the reviewers for helpful comments and Bruno Scherrer for pointing
out a potential improvement to the error bound. J. Zico Kolter is supported by an NSF CI Fellowship.
5

Experimental details: For the random Markov Chain rows of P are drawn IID from a Dirichlet distribution,and the reward and bases are random normal, with |S| = 11. For the diffusion-based chain, we sample|S| = 100 points from a 2D unit cube xi ∈ [0, 1]2 and set p(s′ = j|s = i) ∝ exp(−kxi − xj k2 /(2σ 2 ))for bandwidth σ = 0.4. Similarly, rewards are sampled from a zero-mean Gaussian Process with covariance
Kij = exp(−kxi − xj k2 /(2σ 2 )), and for basis vectors we use the principle eigenvectors of Cov(V ) =E[(I − γP )RRT (I − γP )T ] = (I − γP )K(I − γP )T , which are the optimal bases for representing valuefunctions (in expectation). Some details of the domains are omitted due to space constraints, but MATLAB
code for all the experiments is included in the supplementary files.

8References[1] L. C. Baird. Residual algorithms: Reinforcement learning with function approximation. In
Proceedings of the International Conference on Machine Learning, 1995.
[2] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[3] P. Dayan. The convergence of TD(λ) for general λ. Machine Learning, 8(3–4), 1992.
[4] T. Jaakkola, M. I. Jordan, and S. P. Singh. On the convergence of stochastic iterative dynamic
programming algorithms. Neural Computation, 6(6), 1994.
[5] M. Journee, F. Bach, P.A. Absil, and R. Sepulchre. Low-rank optimization on the cone ofpositive semidefinite matrices. SIAM Journal on Optimization, 20(5):2327–2351, 2010.
[6] J.Z. Kolter and A.Y. Ng. Regularization and feature selection in least-squares temporal difference learning. In Proceedings of the International Conference on Machine Learning, 2009.
[7] M. G. Lagoudakis and R. Parr. Least-squares policy iteration. Journal of Machine Learning
Research, 4:1107–1149, 2003.
[8] A. Lazaric, M. Ghavamzadeh, and R. Munos. Finite-sample analysis of LSTD. In Proceedingsof the International Conference on Machine Learning, 2010.
[9] H.R. Maei and R.S. Sutton. GQ(λ): A general gradient algorithm for temporal-difference
prediction learning with eligibility traces. In Proceedings of the Third Conference on Artificial
General Intelligence, 2010.
[10] H.R. Maei, Cs. Szepesvari, S. Bhatnagar, and R.S. Sutton. Toward off-policy learning control
with function approximation. In Proceedings of the International Conference on Machine
Learning, 2010.
[11] R. Munos. Error bounds for approximate policy iteration. In Proceedings of the International
Conference on Machine Learning, 2003.
[12] J. Nocedal and S.J. Wright. Numerical Optimization. Springer, 1999.
[13] B. Scherrer. Personal communication, 2011.
[14] M. Schmidt. minfunc, 2005. Available at http://www.cs.ubc.ca/˜schmidtm/
Software/minFunc.html.
[15] R.S. Sutton, H.R. Maei, D. Precup, S. Bhatnagar, D. Silver, Cs. Szepesvari, and E. Wiewiora.
Fast gradient-descent methods for temporal-difference learning with linear function approximation. In Proceedings of the International Conference on Machine Learning, 2009.
[16] R.S. Sutton, Cs. Szepesvari, and H.R. Maei. A convergent O(n) algorithm for off-policy
temporal-different learning with linear function approximation. In Advances in Neural Information Processing, 2008.
[17] J.N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function
approximation. IEEE Transactions and Auotomatic Control, 42:674–690, 1997.
[18] J.N. Tsitsiklis and B. Van Roy. Average cost temporal difference learning. Automatica,
35(11):1799–1808, 1999.
[19] H. Yu and D. P. Bertsekas. Error bounds for approximations from projected linear equations.
Mathematics of Operations Research, 35:306–329, 2010.

9