Online Bellman Residual Algorithms
with Predictive Error Guarantees

Wen SunRobotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213
wensun@cs.cmu.edu

Abstract
We establish a connection between optimizing
the Bellman Residual and worst case long-term
predictive error. In the online learning framework, learning takes place over a sequence of trials with the goal of predicting a future discounted
sum of rewards. Our analysis shows that, together with a stability assumption, any no-regret
online learning algorithm that minimizes Bellman error ensures small prediction error. No statistical assumptions are made on the sequence ofobservations, which could be non-Markovian oreven adversarial. Moreover, the analysis is independent of the particular form of function approximation and the particular (stable) no-regret
approach taken. Our approach thus establishes abroad new family of provably sound algorithms
for Bellman Residual-based learning and provides a generalization of previous worst-case result for minimizing predictive error. We investigate the potential advantages of some of this family both theoretically and empirically on benchmark problems.

1

INTRODUCTION

Reinforcement learning (RL) is an online paradigm for optimal sequential decision making where an agent interacts
with an environment, takes actions, receives rewards andtries to maximize its long-term reward, a discounted sumof all the rewards that will be received from now on. An
important part of RL is policy evaluation, the problem of
evaluating the expected long-term rewards of a fixed policy. Temporal Difference (TD) is a famous family of algorithms for policy evaluation. In practice, we are typicallyinterested in complex problem domains (e.g., continuous
state space RL) and function approximations (e.g., linear
functions) are used for policy evaluation. However, it has
been observed that when combined with function approxi-

J. Andrew Bagnell
Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213
dbagnell@ri.cmu.edu
mation, TD may diverge and lead to poor prediction. The
Residual Gradient (RG) was proposed (Baird, 1995) to address these concerns. RG attempts to minimize the Bellman
Error (BE) (see definition in Sec. 2), typically with linear
function approximation, using stochastic gradient descent.
Since then comparison between the family of TD algorithms and RG has received tremendous attention, althoughmost of the analyses heavily rely on certain stochastic assumptions of the environment such as that the sequence ofobservations are Markovian or from a static Markov Decision Process (MDP). For instance Schoknecht and Merke(2003) showed that TD converges provably faster than RG if
the value functions are presented by tabular form. Scherrer(2010) shows that Bellman Residual minimization enjoys aguaranteed performance while TD does not in general whenstates are sampled from arbitrary distributions that may notcorrespond to trajectories taken by the system. Experimentally, they also show that TD converges faster but may generate poor prediction when it is close to divergence.
Schapire and Warmuth (1996) and Li (2008) provided
worst-case analysis of long-term predictive error for variants of the linear TD and RG under a non-probabilistic online learning setting. Their results rely on an elegant spectral analysis of a matrix that is related to specific update
rules of the TD and RG algorithms under linear function approximation. Unfortunately, this approach makes it moredifficult to extend their worst-case (assumption free) analysis to broader families of algorithms and representations
that target the Bellman and Temporal Difference errors.
Following Schapire and Warmuth (1996) and Li (2008)’s
online learning framework, we present a simple, generalconnection between long-term predictive error and noregret online learning that attempts to minimize BE. The
central idea is that methods such as RG should be fundamentally understood as online algorithms as opposed tostandard gradient methods, and that one cannot simultaneously make consistent predictions in the sense of BE while
doing a poor job in terms of long-run predictions. Similar
to Schapire and Warmuth (1996) and Li (2008), our analysis does not rely on any statistical assumptions about theunderlying system. This allows us to analyze more difficult scenarios such as Markov Decision Process with transition probabilities changing over time or even with eachtransition chosen entirely adversarial. Our analysis generalizes to a broader class of functions to approximate thevalue function. Previous work from Robards et al. (2011)and Engel et al. (2005) explored the possibility of using
non-linear function approximation, but to our knowledge
no further analysis on the soundness with respect to prediction error are known.
Our analysis of the connection between online long-term
reward prediction and no-regret online learning provides aunifying view of the relationship between prediction errors
and BE and consequently suggests a broad new family ofalgorithms. Specifically, we present and analyze concrete
examples of how to apply several well-known no-regret online algorithms such as Online Gradient Descent (OGD)from Zinkevich (2003), Online Newton Step (ONS) from
Hazan et al. (2006) and Online Frank Wolf (OFW) from
Hazan and Kale (2012) to online prediction of long-term
rewards. Particularly, our analysis generalizes the RG algorithm from Baird (1995) in the following three aspects: (1)
RG is a specific example of our family of algorithms thatruns OGD on a sequence of BE loss functions, (2) RG canbe naturally combined with more general function approximation such as functions in Reproducing Kernel Hilbert
Space (RKHS), and (3) applying our analysis to RG provides asymptotically tighter bounds on the average prediction error of long-term rewards than that provided in Li(2008). We also find that ONS, which has no-regret rate ofO(log T /T ), has a faster convergence of the average prediction error of long-term rewards. With OFW, we are able
to achieve sparse predictors under some conditions. We analyze these algorithms in detail in Sec. 4.
We emphasize that stability of online algorithms is essential for our results– the no-regret property can be shownby example to be insufficient to achieve low predictive error. We hence introduce the definition of Online Stability
condition in Sec. 2, which intuitively measures the difference between two successive predictors. Our online stability condition is general enough such that most popular
no-regret online algorithms naturally satisfy this conditionand hence this condition does not severely limit the scopeof no-regret online algorithms. Our analysis shows that the
combination of the no-regret property and online stability
is sufficient to promise small predictive error on the longterm rewards.

tistical assumptions about the sequence of observations are
made. The sequence of the observations forms a connected
stream of states which can either be Markovian as typically assumed in RL problem settings or even adversarial. We define the observation at time step t as xt 2 Rn ,which usually represents the features of the environment
at t. Throughout the paper, we assume that feature vector x is bounded as kxk2  X, X 2 R+ . The corresponding reward at step t is defined as rt 2 R, where weassume that reward is always bounded |r|  R 2 R+ .
Given a sequence of observations {xt } and a sequenceof rewards
P1 {rtk}, t the long-term reward at t is defined asvt =rs , where 2 [0, 1) is a discount fack=t
tor. Given a function space F the learner chooses a predictor f at each time step from F for predicting long-term
rewards. Throughout this paper, we assume that any prediction made by a predictor f at a state x is upper bounded
as |f (x)|  P 2 R+ , for any f 2 F and x.
At time step t = 0, the learner receives x0 , initializes a
predictor f0 2 F and makes prediction of v0 as f0 (x0 ).
Rounds of learning then proceeds as follows: the learnermakes a prediction of vt at step t as ft (xt ); the learner thenobserves a reward rt and the next state xt+1 ; the learner
updates its predictor to ft+1 . This interaction repeats andis terminated after T steps. Throughout this paper, we callthis problem setting as online prediction of long-term reward.
We define the signed Bellman Error at step t for predictor ft as bt = ft (xt )rtft (xt+1 ), which measures effectively how self consistent ft is in its predictions between time step t and t + 1. For any f ⇤ 2 F,
we define the corresponding signed Bellman Error as b⇤t =f ⇤ (xt ) rtf ⇤ (xt+1 ). We denote the Bellman Error(BE) as the square of the signed Bellman error b2t .
The Signed Prediction Error of long-term reward at t forft is defined as et = ft (xt ) vt and e⇤t = f ⇤ (xt ) vt forf ⇤ accordingly. We will typically be interested in bounding
the Prediction Error (PE) e2t of a given algorithm in termsof the best possible PE. To lighten notation in the following
sections, all sums over time indices implicitly run from 0
to T 1 unless explicitly noted otherwise.
2.2

NO-REGRET ONLINE LEARNING

Under our online setting, we will define loss functional lt
at step t as the traditional Bellman Error (BE):lt (f ) = (f (xt )2

PRELIMINARIES

2.1

PROBLEM SETTING

We consider the sequential online learning model presented
in Schapire and Warmuth (1996); Li (2008) where no sta-rtf (xt+1 ))2 .

(1)

Note that lt (ft ) = b2t .
Following the setting of online prediction of long-term reward, the learner computes predictor ft at time step t andthen receives the loss function lt and the loss lt (ft ) (after
the learner receives rt and xt+1 ). We say that the online

algorithm is no-regret with respect to BE if:
1X
lt (ft )T !1 T1X
lt (f ⇤ )  0,
T

lim

(2)

for any predictorf ⇤ 2 F, including the best predictor thatP
minimizes lt (f ) in hindsight.

The sequence of predictors ft being no-regret intuitively
means that the predictors are giving nearly as consistentpredictions over time as is possible in that function class.
One might wish that the sequence of predictors being noregret is a sufficient condition for small prediction error.
More formally, one might expect
P that if Eq. 2 holds for thesequence of predictors {ft }, e2t can be upper bounded:lim

1X

T !1 Te2t  C

1X

T

e⇤2
t ,

8f ⇤ 2 F,(3)where C 2 R+ is a constant. Schapire and Warmuth (1996)
showed such a conclusion (Eq. 3) for TD and later on Li(2008) proved such a conclusion for RG, both under theassumption that f (x) is linear.
Unfortunately, however, simply being no-regret (Eq. 2) is
not aPsufficient condition for upper bounding prediction error ( e2t ) as in the form of Eq. 3 for general function approximation form:
Theorem 2.1 There exists a sequence of {ft } that is noregret with respect to the loss functions {lt (f )}, but no C 2
R+ exists that makes Eq. 3 hold.
We prove Theorem 2.1 by providing an example in Appendix (see Supplementary Material) which is no-regret on{lt (ft )} (Eq. 2 holds) but Eq. 3 does not hold.
2.3

ONLINE STABILITY

The counter example that supports Theorem 2.1 presentsa sequence of unstable predictors {ft } where two successive predictors ft and ft+1 vary wildly when predicting thelong-term reward of xt+1 . Such behavior is rather unusual
for typical no-regret online learning algorithms. This suggests introducing a notion of Online Stability which we defined as:
Definition Online Stability: For the generated sequenceof predictors ft , we say the algorithm is online stable if:
1X(ft (xt+1 )T !1 Tlim

ft+1 (xt+1 ))2 = 0.

(4)

Intuitively, the online stability means that on average
the difference between successive predictors is eventually small. That is, the difference between ft (xt+1 ) andft+1 (xt+1 ) is small on average. Online stability is a general condition and does not severely limit the scope of theonline learning algorithms. For instance, when f is linear,

the definition of stability of online learning in (Saha et al.,2012) (see Eq. 3 in Saha et al. (2012)) and (Ross and Bagnell, 2011) implies our form of online stability. We also
show in the following section that many popular no-regret
online learning algorithms including OGD, ONS and OWF,
satisfy our online stability condition.
We show in next section that the sequence of predictors{ft } being no-regret with respect to the loss functions{lt (ft )} and satisfying the online stability condition is
sufficient for deriving an upper bound for prediction error
as shown in Eq. 3.

3

ONLINE LEARNING FOR
LONG-TERM REWARD PREDICTION

In this section, we combine the no-regret condition onloss functions {lt (f )} and the online stability condition
P together to provide a worst-case analysis of sum of PE e2t ,which builds a connection between the PE of long-term rewards, regret and online stability.
More formally, our worst-case analysis shows that if theonline algorithm running on the sequence of loss {lt (f )}is no-regret and the generated sequence of predictors {ft }satisfies the online stability condition, predictor error can
be upper bounded in the form of Eq. 3. The analysis does
not place any probabilistic assumption on the sequence ofobservations {xt } or any assumption on the form of predictors f 2 F (e.g., f (x) does not have to be linear).
We start by first providing two important lemmas below:

Lemma 3.1 Let us define dt = ft (xt ) rt
ft+1 (xt+1 ).
We have:XX
d2t (1)2
e2t + ( 2)(e2T e20 ).
(5)Note that the difference between dt and bt is that dt uses
ft+1 (xt+1 ) to estimate the long-term reward at step t + 1
while bt uses ft (xt+1 ).
Proof Schapire and Warmuth (1996) implicitly showedthat dt = (ft (x) vt + vt
(rt + ft+1 (xt+1 ))) =(et
et+1 ). Squaring both sides and summing over fromt = 0 to t = T 1, we get:
X
X
d2t =
(et
et+1 )2X
X
X=
e2t + 2e2t+1 2et et+1
X
X
X
X
e2t + 2
e2t+1
e2t
e2t+1
X
= (1
)2
e2t + ( 2)(e2T e20 ).
(6)
The first inequality is obtained by applying Young’s inequality to 2et et+1 to get 2et et+1  e2t + e2t+1 .

P ⇤2
Lemma 3.2 For any Pf ⇤ 2 F, the prediction error
etupper bounds the BE b⇤2
asfollows:
t
X
X
2
2
b⇤2
e⇤2
)(e⇤2
e⇤2
t  (1 + )t +( +
0T ). (7)The proof of Lemma 3.2 is similar to the one forLemma 3.1. We present the proof in Appendix.
Now let us define a measure of the change in predictors between the steps of the online algorithm as ✏t = ft (xt+1 )ft+1 (xt+1 ), which is closely related to the online stability
condition. The bt and dt are then closely related with eachother by ✏t :dt = ft (xt )rt

ft+1 (xt+1 )ft (xt+1 ) + ft (xt+1 )= bt + ✏ t .
Squaring both sides, we get:d2t = b2t + 2bt ✏t +2 2

= 2b2t + 2 2 ✏2t ,✏  b2t + b2t +

2 2
✏t +

2 2
✏t

(8)

where the first inequality is coming from applying Young’s
inequality to 2bt ✏t to get 2bt ✏t  b2t + 2 ✏2t . We are now
ready to state the following main theorem of this paper:
Theorem 3.3 Assume a sequence of predictors {ft } isgenerated by running some online algorithm on the sequence of loss functions {lt }.PFor any predictor f ⇤ 2 F,
the sum of prediction errors
e2t can be upper bounded
as:
X
X
X
2
(1
)2
e2t 2(b2t b⇤2
✏2t
t )+2
X
+ 2(1 + )2e⇤2
(9)t + M,
where

M = 2( +

2

)(e⇤2
0

e⇤2
T )

( 2

)(e2T

e20 ).

By running a no-regret and online stable algorithm on theloss functions {lt (f )}, as T ! 1, the average prediction
error is then asymptotically upper bounded by a constantfactor of the best possible prediction error in the function
class:P ⇤2
P 2
2(1 + )2
et
et
lim :

.
(10)
T !1
T
(1
)2 T
Proof Combining Lemma. 3.1 and Lemma. 3.2, we have:
X
X
d2t 2
b⇤2
t
X
(1
)2
e2t + ( 2)(e2T e20 )X
2(1 + )2
e⇤2
t
2( +

2

)(e⇤2
0

e⇤2
T ).

(11)

Subtracting 2b⇤2
t on both sides of Eq. 8, and then summingover from t = 1 to T 1, we have:
X
X
X
X
2
d2t
2b⇤2
(b2t b⇤2
✏2t .
t 2
t )+2
Combining the above two inequalities together, we have:X
X
22(b2t b⇤2
✏2t
t )+2
X
(1
)2
e2t + ( 2)(e2T e20 )X
2(1 + )2e⇤22( + 2 )(e⇤2
e⇤2
(12)
t
0
T ).

Rearrange inequality (12) and define M = 2( + 2 )(e⇤2
0
e⇤2
( 2
)(e2T e20 ), we obtain inequality (9).
T )P
Assume that the f¯ = arg minf 2F
lt (f ), then if the online algorithm is no-regret, we have
1X
1X 2
bt b⇤2lt (ft ) lt (f ⇤ )
t =
T
T
1X

lt (ft ) lt (f¯)
T1
= Regret  0, T ! 1.
(13)
T
If the online algorithm
P 2 satisfies the stability condition (Eq.
4), we have: T1✏t = 0 when T ! 1.

Also, since we assume |f (x)|  P and |r|  R, we cansee M must be upper bounded by some constant. Hence,
we must have M
T = 0, as T ! 1.
Under the conditions that the online algorithm is no-regret
and satisfies online stability, we get Eq. 10 by dividing bothsides of Eq. 9 by T and taking T to infinity.

Note that in Theorem 3.3, Eq. 9 holds for any f ⇤ 2 F,
including the f ⇤ that minimizes the prediction error. But
note that the one that minimizes prediction error, PE, does
not necessarily optimize the BE, which may lead to an improvement of the bound in Eq. 10 in practice. To see this,note that we showed in the proof that for a no-regret algorithm:
1X 2
1
bt b⇤2
Regret  0, as T ! 1.
(14)
t 
T
T
P
Hence the limit of (1/T ) (b2t b⇤2t ) may be negative forsome f ⇤ 2 F, which couldP
lead to a potential decreasein the upper bound of (1/T ) e2t in Eq. 10 and give us atighter bound in practice.
When e⇤t = 0, 8t, fromP
Theorem 3.3, it is easy to see that2⇤2
no-regret rate of (1/T)
P 2 (bt bt ) and the online stability rate of (1/T ) ✏tPtogether determine the rate of theconvergence of (1/T ) e2t .

When! 1 (specifically whenp T ! 1 and(1/ 2)), our upper bound analysis in Eq. 10 is asymptotically tighter than the upper bound in Li (2008) (Eq. 12)

provided for RG, which is a special case of our approach
as we demonstrate in the following section. As we will additionally show, a large number of popular no-regret online
algorithms also satisfy the online stability condition, broadening the family of algorithms that can be used to learn
predictors of long-term rewards.

4

ALGORITHMS

Our analysis in Sec. 3 provides a reduction from the online prediction of long-term reward to the no-regret online
learning setting on a sequence of loss functions {lt (f )} defined in Sec. 2.1, which enables us to develop a new setof algorithms. In this section, we give concrete examplesof new Bellman Residual algorithms based on well-known
no-regret online learning procedures such as Online Gradient Descent (OGD), Online Newton Step (ONS) and theOnline variant of Frank Wolfe (OFW). The choice of algorithm depends on the size and sparsity level of features
and the available computational budget. For instance, OGD
generalizes RG and has O(n) computational complexity at
every update step which makes it suitable for applications
where sampling observations is cheap (e.g., RL for video
games). ONS provides a logarithmic no-regret rate andcould lead to faster convergence in practice, making it potentially suitable for applications where obtaining samplesof observations is expensive (e.g., RL for a physical robot).
Finally, OFW introduces sparsity and can be applied toproblems where the feature dimension is larger than thenumber of samples.
Although the analysis in Sec. 3 does not place any assumption on predictors f 2 F, in practice to achieve the noregret property on the loss functions {lt (f )}, additional assumptions of loss functions (e.g., convexity) are needed.
Since we discuss concrete no-regret online algorithms inthis section, for F we focus on vector spaces equippedwith inner product. Specifically, we focus on two vector
spaces: (1) Reproducing
Kernel Hilbert Spaces (RKHS)
P
where f =↵i K(xi , ·) 2 F, for some kernel K(x, ·)and (2) spaces consisting of linear functions f (x) = wT x,
w 2 W 1 . We now summarize the assumptions that we willuse in section:
1. We assume F (or W) is convex and bounded in asense that the diameter of F (or W) is upper boundedas maxf1 ,f2 2F kf1 f2 k  D 2 R+ , where the norm
kf k is defined by the inner product associated with thefunction space: kf k2 = hf, f i;
2. We assume that kxt k2  X, 8t, |K(x1 , x2 )| K, 8x1 , x2 , kf k  F , 8f 2 F, and kwk2  W ,8w 2 W, where K 2 R+ , F 2 R+ , W 2 R+ .

Any prediction f (x) is always bounded, since forpRKHS,
f (x) is bounded as |f (x)|  kf kkK(x, ·)k  F K, andfor f (x) = wT x, we also have |f (x)|  kwk2 kxk2 
W X. For notation simplicity, we then simply assume thatf (x) is always bounded as |f (x)|  P, P 2 R+ .
Lemma 4.1 With the above assumptions, for any pair of xt
and xt+1 , for RKHS, the loss functional lt (f ) is convex and
Lipschitz continuous with respect to the norm defined by the
inner product h·, ·iK ; for f (x) = wT x, the loss function
lt (w) is convex and Lipischitz continuous with respect toeither L1 norm k · k1 or L2 norm k · k2 .
We present the proof of the above lemma in Appendix.
4.1

GRADIENT-BASED APPROACHES

Before diving into the detailed examples of mirror descentand gradient based approaches, we first introduce an important lemma about the stability of one particular online algorithm: Follow the Regularized Leader (FTRL). It is wellknown that gradient-based and mirror descent approaches
can be understood in the framework of FTRL. In particular,
we only focus on the case where the loss functions are convex and L-Lipschitz continuous with a regularization that isstrongly-convex. We refer reader to Shalev-Shwartz (2011)
for detailed definitions of convex functions, Lipschitz continuous, and strong convexity.
The update rule of FTRL at step t can be summarized as:
ft+1 = arg min
f 2F

li (f ) +i=0

1
R(f ).
µ(15)

Lemma 4.2 For FRTL with convex and L-Lipschitz continuous loss functions lt (f ) and strongly convex regularization function R(f ) (with respect to kf k), we have:X
kft ft+1 k  LT µ.
(16)

Setting µ = p1T to achieve no-regret property, then we
have:
1X
lim
kft ft+1 k = 0.
(17)
T !1 T

Similar proofs has been shown in (Ross and Bagnell, 2011)
and (Saha et al., 2012). For completeness, we present theproof of the above lemma in Appendix following our notation and problem setting.
4.1.1

Gradient Descent on BE

Gradient descent approaches can be understood in the
FTRL framework where the convex loss functions in FTRL
are replaced by a linear approximation:1

Linear function space is a special case of RKHS. We discusslinear function separately since some online algorithms discussed
here only work for linear functionstX

ft+1 = arg min
f 2F

t
X
i=0

hgi , f i +1
R(f ),µt(18)

where gt 2 @lt (ft ) is a sub-gradient of lt at ft and R(f ) isa strongly convex regularizer.
We first consider the special case where f (x) = wT x is
linear. Note that our loss function is lt (w) = (wT xt
rt
wT xt+1 )2 and its gradient gt at wt is gt = (wtT xt
rt
wtT xt+1 )(xt
xt+1 ). Setting the regularization
R(w) = 12 kwk22 , which is 1-strongly convex, we obtain
the RG algorithm in Baird (1995), where the update step at
t is:
wt+1 := wtµt (wtT (xtxt+1 )

rt )(xt

xt+1 ),

Note that the linear loss function is convex and Lipschitz
continuous (kgt k2 is bounded based on our assumptions
that kxk2 , |r| and kwk2 are all bounded). Online Gradient Descent(OGD) is no-regret (Zinkevich, 2003) withpµt = 1/ T and from Lemma 4.2, we have:
1X T
T(wt xt+1 wt+1
xt+1 )2
T1X

kxt+1 k22 kwt wt+1 k22
T
1X
 X2
kwt wt+1 k22 = 0, T ! 1,
T

(19)

which exactly satisfies the online stability condition.
Hence, RG enjoys the guarantee of our main theorem 3.3.
4.1.2

Exponentiated Gradient Descent on BE
P
When we set the regularization R(w) = i wi (log(wi )1), where for vector w, wi is the i-th component of w, we
generalize RG to Exponentiated Gradient (EG) descent as
Precup and Sutton (1997) did for TD.
Since we assumed that kwk2  W , then kwk1  W 0
for W 0 2 R+ . Then the regularization R(w) becomes(1/W 0 )-strongly-convex and the loss function lt (w) is Lipschitz continuous with respect to L1 norm k · k1 . Solving
Eq.18, we obtain the update step at t as:

4.1.3

Gradient Descent in RKHS

Now we consider functions f (x) that belongs to RKHS
HK . For the special case where R(f ) = 12 hf, f iK , weobtain an RG-style update based on functional gradient descent (Scholkopf and Smola, 2001):⇣
ft+1 := ft µt (ft (xt ) rtft (xt+1 ))⌘⇥ (K(xt , ·)K(xt+1 , ·)) . (21)Similarly, it is straightforward to show that gradient descentin RKHS satisfies our stability
condition and no-regret conp
dition when µt = 1/ T . Hence, gradient descent in
RKHS also enjoys the predictive error guarantees derived
in Theorem 3.3.
4.2

IMPLICIT ONLINE LEARNING

Recently Tamar et al. (2014) has demonstrated implicit online learning for temporal difference method. We consider
the same approach for Bellman Residual minimization by
applying implicit online learning from Kulis et al. (2010)
to the loss functions {lt (f )} and thus provide worst-caseguarantees. Specifically at iteration t, ft+1 is computed
implicitly as:(22)

ft+1 = arg min DR (f, ft ) + µt lt (f )f 2F

= arg min DR (f, ft ) + µt (f (xt )f 2Ff (xt+1 )rt ) 2 ,where DR is a Bregmanpdivergence. Saha et al. (2012)
show that when µt = 1/ t, the generating function R(f )is positive and strongly-convex, and the loss function lt (f )is convex and Lipschitz continuous, implicit online learning is shown to be no-regret and also satisfies Eq. 17.

Implicit Online Gradient DescentP
Particularly, we first consider f =↵i K(xi , ·) in RKHS.
Setting R(f ) = 12 hf, f ik , we have DR (f, ft ) = 12 kf
ft k2 . Then solving Eq. 22, we obtain the following update
rule:
i
wt+1
= wti exp
µt (wtT (xtxt+1 ) rt )(xit
xit+1 ) .
µt
ft+1 := ft
1 + µt kK(xt , ·)K(xt+1 , ·)k2
Similar to RG, using Lemma 4.2 (the norm in Lemma 4.2⇥ (ft (xt )ft (xt+1 ) rt )becomes L1 norm) we can show that EG satisfies our online
stability condition:⇥ (K(xt , ·)K(xt+1 , ·)).
1X T
T
(wt xt+1 wt+1
xt+1 )2
TX
1
 X2
kwt wt+1 k22
T
X
1
 X2
kwt wt+1 k21 = 0, T ! 1,
(20)
Tp
and is also no-regret on {lt (w)} when µt = 1/ T . Hence,
EG descent approach enjoys our main theorem 3.3.

4.2.1

When considering linear function f (x) = wT x andR(w) = 12 kwk22 , we obtain a similar update step:
wt+1 = wtµt

1 + µt kxt⇥ (wtT (xtxt+1 k2
xt+1 )

rt )(xt

xt+1 ).

As we will show in the experiments, compared to RG(OGD on BE), implicit OGD on BE is less sensitive to thechoice of step-size, which enables us to set
P large step-sizeto achieve faster convergence for (1/T ) e2t . This phenomenon is also observed by Tamar et al. (2014) when they
compare implicit temporal difference to the original TD algorithm (Sutton and Barto, 1998).
4.3

ONLINE NEWTON STEP

We also analyze an online second-order method: the Online
Newton Step (ONS) (Hazan et al., 2006) for online prediction of long-term reward. For ONS, we only focus on linear
function approximation f (x) = wT x. We slightly adapt
the ONS for our loss function lt (w). We first present thefollowing lemma:

RKHS, Implicit OGD, and implicit OGD in RKHS, usuallyneed a projection operation in each update step if the newly
updated predictor is out of its pre-defined convex set F, although in many cases, projection operations are simple2 .
OFW is a projection-free online method and every step involves solving a (typicaly very simple) linear programming
problem. Again, we restrict our analysis to linear functions
f = wT x for OFW. Without loss of generality, we assume lt (w) is L-Lipschitz continuous with some L 2 R+
(Lemma 4.1).
Applying the adversarial variant of OFW to the sequenceof loss functions {lt (f )}, we have the following iterative
update step:
vt = arg min rFt (wt )T w,

Lemma 4.3 For loss function lt (w) = (wT xt
rt
wT xt+1 )2 , there exists a 2 R+ , such that for all w
and w0 :lt (w)

lt (w0 ) + rlt (w0 )T (w
+

2

(w

w0 ).

Ft (w) =We present the proof of the above lemma in appendix.

=

With , then the iterative update rule for ONS is:
!
1
At 1
1
wt = ⇧W
wt 1
At 1 rlt 1 (wt 1 ) ,

=

(23)

Pt
where At = i=0 rlt (wt )rlt (wt )T + ✏In , ✏ 2 R+ , andt⇧A
W is a projection to W with the norm induced by At :At
⇧W (y) = arg minw2W (w y)T At (w y), which makestthis projection operator ⇧A
W not trivial and equal to solving
a convex program usually.

(25)

Lemma 4.4 The sequence {wt } generated by ONS satisfies the online stability condition:
1X T
T(wt xt+1 wt+1
xt+1 )2
T
1 X2
n log(T + 1) = 0, T ! 1.
(24)
T G2 2The proof borrows ideas from Hazan et al. (2006) and ispresented
P in the Appendix. Note that the convergence rateof T1 (ft (xt+1 ) ft+1 (xt+1 ))2 is O(log T /T ), which isthe same as the no-regret rate of ONS.
PROJECTION-FREE ONLINE LEARNING

We analyze the Online Frank Wolfe (OFW) (Hazan andKale, 2012) for online prediction of long-term reward. Previously introduced methods, including OGD, EG, OGD int
1 Xˆ
li (w)
t + 1 i=0t
1 X(rli (wi )T w +t + 1 i=0t
1 X⇣ T(wi xi ri
t + 1 i=0⌘
+ i kw w0 k22 ,where

t = (L/D)t

1/4

i kw

w0 k22 )wiT xi+1 )(xi

xi+1 )T w, w0 is the initialization.

The online stability of OFW can be shown easily:
1X T
T(wt xt+1 wt+1
xt+1 )2
TX
1
 X2
kwt wt+1 k22
T
X
1
 X2
t 2↵ kwt vt k22
TX1
 X 2 D2
t 2↵ = 0, T ! 1.
T

Since kxk2  X, kwk2  W and |r|  R, we havekrlt (w)k2  G, for G 2 R+ . The following lemmashows that ONS satisfies the our online stability condition:

4.4t ↵ )wt + t a vt ,wt+1 = (1where ↵ = 14 and Ft (w) is computed as:

w0 )w0 )T rlt (w0 )rlt (w0 )T (ww2W

The first inequality comes from Cauchy-Schwartz inequality and the assumption that kxk2  X. The last equality
PTfollows from the fact that 2↵ > 0, and T1 t=1 t ⇠ = 0,
when ⇠ > 0 and T ! 1.

Note that the output of the OFW wt is sparse when W isdefined as W = {w : kwk1  W 0 } for some W 0 2 R+
and w0 is initialized to the origin or any corner point of W.
This is because the output vt of Eq. 25 will be always oneof the corner points of W and wt hence is a linear combination of corner points {w0 , v0 ..., vt 1 }, leading to the2

Usually, when W is defined as {w : kwk2  W }, an L2
projection to such W is easy and can be implemented in O(n).
The same for L2 projection in RKHS when F = {f : kf k  F }.

60
40
20
0

1000
2000
3000
Number of Steps

Average Prediction Error

800

Average Prediction Error

RG
Implicit OGD
ONS
OFW
EG
TD(0)

Puddle World (f (x) = wT x), . = 0:99, n = 50
60
RG
Implicit OGD
ONS
OFW
EG
TD(0)

40

20

0

4000

0

1000
2000
Number of Steps

3000(a) Linear(a) Linear

Random Walk (RKHS), . = 0:95, n = 10

Puddle World (RKHS), . = 0:99, n = 2

TD(0)
RG
Implicit OGD

7
6
5
4
3

0

1000
2000
3000
Number of Steps

4000

Average Prediction Error

Average Prediction Error

Random Walk (f (x) = wT x), . = 0:95, n = 10
100

RG
Implicit OGD
TD(0)

8
6
4
2
0

1000
2000
Number of Steps

3000(b) RKHS(b) RKHS

Figure 1: Convergence of prediction error for Random
Walk with linear function approximation (top) and RKHS
(bottom).

Figure 2: Convergence of prediction error for Puddle World
with linear function approximation (top) and RKHS (bottom).

fact that wt can have at most (t+1) non-zero entries. Also,
if W = {w : kwk1  W 0 }, Eq. 25 can be implementedin O(n) as follows: (1) find the entry i in rFt (wt ) thathas the maximum absolute value; (2) set vti (the i’th entry)
to be sign(rFt (wt )i )W 0 , and all other entries in vt tozero.

pwise is 0.5/ t andpthe probability of moving counterclockwise is (1 0.5/ t). Note that the transition probabilitychanges over time. We randomly generate a feature vector x 2 R10 and assign it to a state. All rewards are uniformly sampled from [ 3, 3]. In this problem, we tested
both RKHS (Fig. 1(b)) and linear function approximation(Fig. 1(a)). For RKHS, we use a RBF Kernel with bandwidth 0.2, qualitatively chosen for the best performance interms of prediction error.

When W = {w : kwk2  W }, we cannot achieve sparsity, but Eq. 25 can still be implemented in O(n) by settingrFt (wt )vt = krFW.
t (wt )k2

5

EXPERIMENTS

We applied these algorithms to three simulated policy evaluation problems: (1) the Random Walk problem with a ring
chain, which is a variant of the Hall problem introduced by
Baird (1995), (2) PuddleWorld adopted from Sutton andBarto (1998) and (3) Helicopter Hover using the simulator from Coates et al. (2008). We also compare the above
algorithms to standard TD(0) (Sutton and Barto, 1998).
Random Walk The state space of the Random Walk task
has N = 50 states. The states are linked together as aring without any terminal states. At time step t, from any
state on the ring, the transition probability of moving clock-PuddleWorld In the PuddleWorld scenario, the state
space is a unit square with “puddles” and the agent’s stateis represented by its x and y coordinates. In each episode,the agent’s starting state is uniformly sampled in the region[0, 0.2] ⇥ [0, 0.2]. The policy at each time step selects togo north or east with probability 0.5 each. For each step,
the reward is 1 if the agent does not step in a puddle, andthe reward decreases quadratically as the agent steps into
the puddles. The terminal region is defined as x + y 1.9(upper right corner of the square), which has reward 0. For
linear function approximation, we used 50 RBF features(x 2 R50 ) of bandwidth 0.2, whose centers were uniformly
distributed in the state space (Fig. 2(a)). For RKHS, we
again use a RBF kernel bandwidth width 0.2 (Fig. 2(b)).

Average Prediction Error

Helicopter Hover(f (x) = wT x), . = 0:99, n = 253
3
RG
Implicit OGD
ONS
OFW
EG
TD(0)

2

1

0

0

2000
4000
6000
Number of Steps(a) Linear

Figure 3: Convergence of prediction error for Helicopter
Hover with linear function approximation
Helicopter Hover The helicopter simulator has a continuous 21-dimensional state space and a continuous 4dimensional control. The reward is equal to the negative ofthe quadratic deviation to the targeted hover state. To generate sequence of states, we apply an LQR controller using
linearized dynamics around the target hover state. We additionally corrupt the dynamics simulation with noise sampled from a Gaussian distribution. We used a degree-two
polynomial feature that maps an original 21-dimensional
state to a feature vector x 2 R253 (Fig. 3(a)) and attempt
to predict the long-term cost-to-go.
Analysis of results We fixed TD(0)’s step-size but a wide
range of step-sizes were tried, and the best choice in terms
of prediction error was used for TD(0). p
For RG, implicit
OGD, and EG, we set the step-size to c/ t, where c is aconstant. We also tried a range of c and chose the one that
leads to the best performance. For all algorithms, we provided the same random initialization. All the results arecomputed by averaging over 100 random trials. As we cansee from Fig. 3, ONS and implicit OGD give good convergence speed in general. Implicit OGD performed well withboth RKHS and linear function approximation. Throughout the experiments, we found that implicit OGD was able
to use a larger c to speed up convergence while still maintaining good stability. Surprisingly, our experimental results clearly show that our approaches have the possibility
to achieve smaller prediction error than TD(0) (e.g., Fig.
2(b), bottom). This runs counter to the fact that the upper bound of prediction error provided by our analysis in
Sec. 3 is looser than the upper bound of prediction errorof TD(0) from both Li (2008) and Schapire and Warmuth(1996). Though our analysis is more general, further investigation is needed to tighten the worst-case bounds on our
approach.

6

CONCLUSION

We established a general connection between the worstcase prediction of long term reward and Bellman errors forstable prediction algorithms. We showed that together withthis online stability condition, any no-regret online learning algorithm optimizing Bellman errors ensures small prediction errors. The stability condition is weak enough suchthat most popular no-regret online algorithms satisfy it.
Our approach then suggests and provides soundness guarantees for online prediction of long-term reward using abroad new family of algorithms, including Online BE Newton Step, Online BE Frank Wolf, Implicit BE online learning (implicit gradient descent). The analysis itself can beapplied to more general function space of hypotheses including Reproducing Kernel Hilbert Space representations
and even to discrete hypothesis classes (i.e. trees). However we also want to point out that while our setting is very
general, one might expect that in strongly non-Markovian
situations there may fail to be a good predictor—e.g., nolinear predictor using only the features of xt can do a goodjob. In that sense our theorem in this paper is relative—
essentially temporally coherent predictions (in the sense ofsmall Bellman error) imply doing nearly as well as can bedone at long term prediction: whether that is actually good
performance depends on the quality of both features andhypothesis class, but not on any probabilistic assumptions.

7

DISCUSSION

Although our analysis provides broad and sound generalizations of RG, it does not provide guarantees on what we
believe are the natural generalization of TD(0) or its variants as online algorithms on a sequence of temporal difference loss functions (TD-loss) which is defined as:
˜lt (f ) = (f (xt )rtft (xt+1 ))2 .

(26)

Note that the difference between ˜lt and lt is the subsripton the second predictor. The reason that we call it TDloss is that when f (x) = wT x is linear, applying OGD
to ˜lt (w) with respect w exactly reveals the update stepp ofTD(0). By properly choosing step-size (µ = O(1/ T )),OGD is no-regret on the TD-loss functions {˜lt (f )}. Similar to our analysis of Bellman error algorithms, we believethat it is possible that no-regret property on TD-loss functions and stability condition of online algorithms together
could lead us to similar predictive guarantees as shown in
Theorem 3.3. In fact our empirical results (included in Appendix) suggested that such approaches are both sound andmay outperform Bellman Residual methods. We leave it as
future work to establish regret bounds for temporal difference minimizing online algorithms.

8

ACKNOWLEDGEMENTS

This work is supported by the ONR MURI grant N0001409-1-1052, Reasoning in Reduced Information Spaces. We
gratefully thank Arun Venkatraman for valuable discussions.

References
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. Proceedings of the
12th International Conference on Machine Learning(ICML-95), pages 30–37, 1995.
Adam Coates, Pieter Abbeel, and Andrew Y Ng. Learningfor control from multiple demonstrations. Proceedingsof the 25th international conference on Machine learning - ICML ’08, pages 144–151, 2008.
Yaakov Engel, Shie Mannor, and Ron Meir. Reinforcement learning with Gaussian processes. Proceedings ofthe 22nd international conference on Machine learning,
2005.
Elad Hazan and Satyen Kale. Projection-free Online Learning. 29th International Conference on Machine Learning (ICML 2012), pages 521–528, 2012.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization.
Proceedings of the 19th annual conference on Computational Learning Theory (COLT), pages 169–192, 2006.
Brian Kulis, Peter L Bartlett, Bartlett Eecs, and Berkeley
Edu. Implicit Online Learning. Proceedings of the 27th
international conference on Machine learning (ICML),
pages 575–582, 2010.
Lihong Li. A worst-case comparison between temporal
difference and residual gradient with linear function approximation. Proceedings of the 25th international conference on Machine learning - ICML ’08, pages 560–
567, 2008.
Doina Precup and Richard S. Sutton. Exponentiated Gradient Methods for Reinforcement Learning. In Proceedings of the 14th International Conference on Machine
Learning (ICML), 1997.
M Robards, Peter Sunehag, Scott Sanner, and B Marthi.
Sparse Kernel-SARSA(lambda) with an Eligibility
Trace. ECML PKDD, 2011.
Stephane Ross and J. Andrew Bagnell. Stability Conditions
for Online Learnability. arXiv:1108.3154, 2011.
Ankan Saha, Prateek Jain, and Ambuj Tewari. The Interplay Between Stability and Regret in Online Learning.
arXiv preprint arXiv:1211.6158, pages 1–19, 2012.
Robert E. Schapire and Manfred K. Warmuth. On theworst-case analysis of temporal-difference learning algorithms. Machine Learning, 22(1):95–121, 1996. ISSN
0885-6125. doi: 10.1007/BF00114725.
Bruno Scherrer. Should one compute the Temporal Difference fix point or minimize the Bellman Residual? The
unified oblique projection view. International Conference on Machine Learning (ICML 2010), 2010.

Ralf Schoknecht and Artur Merke. TD(0) Converges Provably Faster than the Residual Gradient Algorithm. International Conference on Machine Learning (ICML
2003), pages 680–687, 2003.
Bernhard Scholkopf and Alexander J. Smola. Learningwith Kernels: Support Vector Machines, Regularization,
Optimization, and Beyond. MIT Press Cambridge, MA,
USA, 2001.
Shai Shalev-Shwartz. Online Learning and Online Convex Optimization. Foundations and Trends in Machine
Learning, 4(2):107–194, 2011.
Richard S. Sutton and Andrew G. Barto. Reinforcement
Learning: An Introduction. MIT Press, 1998.
Aviv Tamar, Panos Toulis, Shie Mannor, andEdoardo M. Airoldi. Implicit Temporal Differences.
arXiv:1412.6734, pages 1–6, 2014.
Martin Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. In International
Conference on Machine Learning (ICML 2003), pages
421–422, 2003.

A

Proof of Theorem. 2.1

Proof To prove Theorem. 2.1, we provide an example where the sequence of predictors {ft } is no-regret on loss {lt (ft )}but Eq. 3 does not hold.
PTs t
Let us assume there exist a f ⇤ 2 F such that f ⇤ (xt ) = vt =rt . Namely we assume that the bests=t⇤
predictor in F canPpredict long-term reward exactly. Note
that
this
f
minimizes
the PE and BE simultaneously asP
f ⇤ = arg minf 2F (f (xt ) vt )2 and f ⇤ = arg minf 2F
lt (f ).
Let us assume that ft (xt ) = vt + a and ft (xt+1 ) = vt+1 + 1 a, 8t, for a 2 R+ . Then we have:
bt = ft (xt )rtft (xt+1 ) = vt + a

1

rt

vt+1

lt (ft )lt (f ⇤ ) =(27)

a = 0.

Hence, for regret, we have:
Regret =Xlt (ft )

min
f 2F

X

lt (f ) =

X

X

b⇤2
t = 0,

b2t(28)

which means that this sequence of predictor {ft } is no-regret with respect to the loss functions {lt (f )}.

However, on the otherwhen we check
have et = ft (xt ) vt = a, which makes the sum
P hand,Pthe2 predictor2 error et , weP
2
ofpredictionerroreincreaselinearly:
e
=
(T
)a
and
(1/T
)
e2t = a. Since we have e⇤t = 0 for all t and thus
t
t
P ⇤2
+
et = 0, there is no such constant C 2 R that could make the Eq. 3 hold.
This example presents a sequence of predictors that does not satisfy the online stability condition. In fact, it is this example
that motivates us to study stability condition of online algorihtms.

B

Proof of Lemma. 3.2

Proof Note that b⇤t = f ⇤ (xt )t = 0 to T 1, we have:vt + vtrte⇤t+1 . Squaring both sides and summing over fromf ⇤ (xt+1 ) = e⇤t

X

X
b⇤2
(e⇤t
e⇤t+1 )2
t =
X
X
X
2 ⇤2
=
e⇤2
et+1 2e⇤t e⇤t+1
t +
X
X
X
X
2 ⇤2

e⇤2
et+1 +
e⇤2
e⇤2
t +
t +
t+1
X
2
⇤2
2
⇤2
⇤2
= (1 + )et + ( + )(eT
e0 ).

Again, the first inequality is obtained by applying Young’s inequality toC2e⇤t e⇤t+1 to get⇤22e⇤t e⇤t+1  e⇤2
t + et+1 .

Proof of Lemma. 4.1

Proof To show lt (f ) is convex with respect to f , we only need the assumption that F belongs to a vector space. Since thefunction space F belongs to a vector space, for any two function f 2 F and g 2 F, and a scalar a 2 R and x, we have:(f + g)(x) = f (x) + g(x),(29)(af )(x) = af (x).

(30)

To prove the convexity of the loss functional lt (f ), we show that for any ↵ 2 [0, 1], we have lt (↵f + (1↵lt (f ) + (1 ↵)lt (g). For lt (↵f + (1 ↵)g), we have:lt (↵f + (1↵)g) = ((↵f + (1= (↵(f (xt )2= ↵ (f (xt+ 2↵(1↵)g)(xt )rtf (xt+1 )rt ) + (1↵)(g(xt )f (xt+1 )2

2↵)(f (xt )rt )) + (1f (xt+1 )g(xt+1 )↵) (g(xt )rt )(g(xt )↵)g)(xt+1 ))2(↵f + (1rt ))g(xt+1 )g(xt+1 )

rt ).

2

rt )

↵)g) 
(31)
(32)

2

(33)
(34)

For ↵lt (f ) + (1↵)lt (g), we have:↵lt (f ) + (1Define b(f ) = (f (xt )↵)lt (g) = ↵(f (xt )f (xt+1 )lt (↵f + (1
= (↵

2

= (↵

2

rt )2 + (1f (xt+1 )rt ) and b(g) = (g(xt )
↵)g)

↵)

2

2

↵)b(f ) + ((1↵)(b(f ) + b(g)2g(xt+1 )rt ) 2 .

(35)

rt ). Subtract Eq. 35 from Eq. 34, we have:g(xt+1 )(↵lt (f ) + (12↵)(g(xt )(36)↵)lt (g))2(1↵))b(g) + 2(↵(1

2b(f )g(f )) = (↵

2

(37)

↵))b(f )g(f )↵)(b(f )2(38)g(f ))  0.

Now we prove lt (f ) is Lipschitz continuous. First, consider the case when F is in RKHS. lt (f ) is differentiable and its
gradient is:rlt (f ) = (f (xt )rtf (xt+1 ))(K(xt , ·)rtf (xt+1 ))2 (1 +K(xt+1 , ·)).

(39)

2 K(xt , xt+1 )).

(40)

Note that the norm of rlt (f ) is:
krlt (f )k = (f (xt )2Under the assumption that |f (x)|  P , |r|  R, |K(xt , xt+1 )|  K, it is easy to see that krlt (f )k is upper bounded bysome postive constant. The fact that a function is differentialbe and has bounded gradient implies the function is Lipschitz
continuous.
For the case when f (x) = wT x, we have lt (w) is differentiable and the gradient is:rlt (w) = (wT xt

wT xt )(xt

rt

(41)

xt+1 ).

Under the assumptions that kwk2  W , kxk2  X, |r|  R, it is easy to see that krlt (w)k2 is bounded. Hence, lt (w) is
Lipschitz continuous with respect to L2 norm.
To see that lt (w) is also Lipschitz continuous with respect to L1 norm, note that krlt (w)k1 must be upper bounded, since|f (x)|  P , |r|  R, and |xi |  X, where xi stands for the i’th entry of the vector x.

D

Proof of Lemma. 4.2

Proof Without loss of generality, we assume the regularization R(f ) is 1-strongly convex with respect to norm k · k. Dueto strong convexity, we have:tXli (ft ) +i=0

1
R(ft )
µ

t
X
i=0

+
The inequality follows from the fact that
Similarly, We also have:P

lt (ft+1 ) +

1
kft
2µ

1
R(ft+1 )µ(42)ft+1 k.

lt + µ1 R is a strongly convex function and ft+1 is a minimizer of

t 1
X

1
li (ft+1 )+ R(ft+1 )
µ
i=0
1
+
kft
2µ

t 1
X

li (ft ) +

i=0

Pt

1
i=0 lt + µ R.

1
R(ft )µ(43)

ft+1 k,Pt 1
because ft is a minimizer of i=0 li + µt1 1 R. Adding (42) and (43) together side by side and cancelling out repeatedterms from both sides, we get:(1/µ)kft
 |lt (ft )ft+1 k2  lt (ft )lt (ft+1 )|  Lkftlt (ft+1 )ft+1 kSetting z = kft ft+1pk, and solve the above quadratic inequality with respect to z, we get kft
t = 0 to T , set µ = 1/ T and take the limit T ! 1, we get to Eq. 17(44)
ft+1 k  Lµ. Sum from

E

Proof of Lemma. 4.3

Proof lt (w) is a quadratic function with respect w. Hence, taking the Tayplor expension of lt (w) at w0 , we have:lt (w) = lt (w0 ) + rlt (w0 )T (wNote that the Hessian rrlt (w0 ) = 2(xt1w0 ) + (w2w0 )T rrlt (w0 )(w

w0 ).

(45)

xt+1 )T , which can be writted as:

xt+1 )(xt2(w0 T xt

rt(xt
xt+1 )(xt
xt+1 )TTT(w0 xt rt
w0 xt+1 )2
1
rlt (w0 )rlt (w0 )T
rlt (w0 )rlt (w0 )T ,2M
w0 T xt+1 )2

where M = supw,xt ,xt+1 ,rt (wT xt

rt

wT xt+1 )2 . The derivation in Eq. 46 implicitly assumes that (w0 xt

Trrlt (w0 ) = 2(w0 xt
=

1

0T

0T

w xt+1 ) 6= 0. But when (w xt rt

rt

T

w0 xt+1 )2

(46)
T

0T

rt

w xt+1 ) = 0, the final result from Eq. 46 still holds (rlt (w )rlt (w ) = 0).
0

0 T

Note that M is a positive constant since we assume that kwk, kxk and |rt | are all bounded. Hence, we have:lt (w)
SettingFlt (w0 ) + rlt (w0 )T (ww0 ) +

1(w
4Mw0 )T rlt (w0 )rlt (w0 )T (w

w0 ).

(47)

 1/2M we prove the lemma.

Proof of Lemma. 4.4

Proof We next show that online newton method satisfies the online stability condition. For convenience, define yt+1 =wt 1 At 1 rlt (wt ), we have:
XX
X 1
kwt wt+1 k2At 
kwt yt+1 k2At =k At 1 rlt (wt )k2At
X 1
1 X
1
1
T
=
rl
(w
)
A
A
A
rl
(w
)
=
rlt (wt )T At 1 rlt (wt ).
t
t
t
t
t
t
t
2
2

Following the proof in Hazan et al. (2006), it can be shown that:

where G 2 R+ and G

X

rlt (wt )T At 1 rlt (wt )  n log(

T G2
+ 1),
✏

krlt k2 . We simply set ✏ = G2 . Hence, the online stability condition is satisfied as:
1X T
X2 X
T
(wt xt+1 wt+1
xt+1 )2 
kwt wt+1 k22
TT
1 X2 X1 X2
kwt wt+1 k2At 
n log(T + 1) = 0, T ! 1.
T ✏T G2 2

The first inequality comes from Cauchy-Schwarz inequality and the assumption that kxk2  X. The second inequality
follows from the fact that the smallest eigenvalues of At ’s are bigger than or equal to ✏.

G

Disccusion and Results for Online Algorithms on TD-loss Functions {˜lt (f )}First of all, we show similar to our analysis for Bellman Residual minimization, simply being no-regret on the TD-loss
functions {˜lt (f )} under general function approximation (not necessarily linear) is not sufficient to small predictive errors(Eq. 3 doesn’t hold):
Theorem G.1 There exists a sequence of {ft } that is no-regret with respect to the TD-loss functions {˜lt (f )}, but noC 2 R+ exists that makes Eq. 3 hold.

Random Walk (f (x) = w T x), . = 0:95, n = 10
implicit OGD (TD)implicit OGD (BR)ONS (TD)ONS (BR)
OFW (TD)
OFW (BR)
TD(0)
RG

60

40

20

0

0

1000

2000
3000
Number of Steps

Puddle World (f (x) = w T x), . = 0:99, n = 50

70
Average Prediction Error

Average Prediction Error

80

50
40
30
20
10
0

4000

implicit OGD (TD)implicit OGD (BR)ONS (TD)ONS (BR)
OFW (TD)
OFW (BR)
TD(0)
RG

60

0

1000
2000
Number of Steps

3000

Figure 4: Convergence of prediction error. We applied a set of online algorithms (OGD, implicit OGD, ONS, OFW) on
BE loss functions {lt (w)} (dot line) and TD-loss functions {˜lt (w)} (solid line) for Random walk (left) and Puddle World(right).
PT
Proof Again, we assume that ft (xt ) = vt + a and ft (xt+1 ) = vt+1 + 1 a, where a 2 R+ and vt = s=t s t rt is thelong-term reward. Under this setting, the TD-loss ˜lt (ft ) becomes:
˜lt (ft ) = (ft (xt )rtft (xt+1 ))2 = 0.

Hence, this sequence of predictors {ft } is no-regret:XXX
˜lt (ft )˜lt (f ⇤ ) ˜lt (ft ) = 0,8f ⇤ 2 F.

(48)

(49)

However this sequence of predictors performly badly in terms of prediction error e2t = (ft (xt ) vt )2 = a2 . Under theassumption that the function space F (hypothesis
class) is broad enough to have f ⇤ that perfectly predicts long-term reward
P 2
1
⇤
2
(f (xt ) = vt , 8t), we always have T
et = a > T1 e⇤2
t = 0. Hence, it is impossible to find a postive constant C suchthat Eq. 3 will hold.
Note that in the above proof, the constructed predictors are not stable in a sense that ft (xt+1 ) and ft+1 (xt+1 ) varies a lot
and hence it does not satisfies the online stability condition.
We conjecture that together with a similar stability analysis as we did for Bellman Residual minimization, we could achieve
similar predictive guarantees as in Theorem. 3.3. We leave it as a open question here and we currently are working on it.
G.1

Empirical Results

We applied several stable no-regret online learning algorithms including ONS, OFW, implicit OGD to TD-loss functions
˜lt (f ) with linear function approximation (f (x) = wT x). Fig. 4 shows the results of applying the set of algorithms (OGD,
implicit OGD, ONS, and OFW) to BE and TD-loss for Random Walk and Puddle World. We compare their performance
to T D(0) and RG(0). Although we currently do not have sound predictive guarantees, these empirical results suggest that
applying stable no-regret online algorithms to TD-loss functions {˜lt (w)} in practice may give competitive performancecompared to Bellman Residual minimization algorithms and the T D(0).