A Kernel Loss for Solving the Bellman Equation

Yihao Feng 1 Lihong Li 2 Qiang Liu 1

Abstract
Value function learning plays a central role inmany state-of-the-art reinforcement-learning algorithms. Many popular algorithms like Q-learning
do not optimize any objective function, but are
fixed-point iterations of some variant of Bellman
operator that is not necessarily a contraction. As
a result, they may easily lose convergence guarantees, as can be observed in practice. In this paper,
we propose a novel loss function, which can be
optimized using standard gradient-based methods
without risking divergence. The key advantage
is that its gradient can be easily approximatedusing sampled transitions, avoiding the need for
double samples required by prior algorithms likeresidual gradient. Our approach may be combinedwith general function classes such as neural networks, on either on- or off-policy data, and isshown to work reliably and effectively in several
benchmarks.

1. Introduction
The goal of a reinforcement learning (RL) agent is to optimize the policy to maximize the long-term return throughrepeated interaction with an external environment. The interaction is often modeled as a Markov decision process,whose value functions are the unique fixed points of theircorresponding Bellman operators. Many state-of-the-art
algorithms, including TD(λ), Q-learning and actor-critic,
have value function learning as a key component (Sutton &Barto, 2018).
A fundamental property of the Bellman operator is that it is acontraction in the value function space in the `∞ -norm (Puterman, 1994). Therefore, starting from any bounded initial
function, with repeated applications of the operator, thevalue function converges to the correct value function. A
number of algorithms are inspired by this property, such*
Equal contribution 1 Department of Computer Science, University of Texas, Austin 2 Google Research. Correspondence to:
Yihao Feng <yihao@cs.utexas.edu>.

Real-world Sequential Decision Making workshop at ICML 2019.
Copyright 2019 by the author(s).

as temporal difference (Sutton, 1988) and its many variants (Bertsekas & Tsitsiklis, 1996; Sutton & Barto, 2018).
Unfortunately, when function approximation such as neuralnetworks is used to represent the value function in largescale problems, the critical property of contraction is generally lost (e.g., Boyan & Moore, 1995; Baird, 1995; Tsitsiklis& Van Roy, 1997), except in rather restricted cases (e.g.,
Gordon, 1995; Tsitsiklis & Van Roy, 1997). This instability issue is not only one of the core theoretical challenges
in RL, but also has broad practical significance, given thegrowing popularity of algorithms like DQN (Mnih et al.,2015), A3C (Mnih et al., 2016) and their many variants (e.g.,
Gu et al., 2016; Schulman et al., 2016; Wang et al., 2016;
Wu et al., 2017), whose stability largely depends on thecontraction property. The instability becomes even harder
to avoid, when training data (transitions) are sampled froman off-policy distribution, a situation known as the deadly
triad (Sutton & Barto, 2018, Sec. 11.3).
The brittleness of Bellman operator’s contraction property
has inspired a number of works that aim to reformulate valuefunction learning as an optimization problem, where standard algorithms like stochastic gradient descent can be used
to minimize the objective, without the risk of divergence(under mild assumptions). One of the earliest attempts is
residual gradient, or RG (Baird, 1995), which relies on minimizing squared temporal differences. The algorithm isconvergent, but its objective is not necessarily a good proxydue to a well-known “double sample” problem. As a result,it may converge to an inferior solution; see Sections 2 and 6
for further details and numerical examples. This drawback
is inherited by similar algorithms like PCL (Nachum et al.,2017; 2018).
Another line of work seeks alternative objective functions,the minimization of which leads to desired value functions (Sutton et al., 2009; Maei, 2011; Liu et al., 2015;
Dai et al., 2017). Most existing works are either for linear
approximation, or for evaluation of a fixed policy. An exception is the SBEED algorithm (Dai et al., 2018), whichtransforms the Bellman equation to a saddle-point problem.
While SBEED is provably convergent under fairly standard
conditions, it relies on solving a minimax problem, whose
optimization can be rather challenging in practice, especiallywith nonconvex approximation classes like neural networks.

A Kernel Loss for Solving the Bellman Equation

In this paper, we propose a novel loss function for valuefunction learning. It avoids the double-sample problem (unlike RG), and can be easily estimated and optimized using
sampled transitions (in both on- and off-policy scenarios).
This is made possible by leveraging an important property
of integrally strictly positive definite kernels (Stewart, 1976;
Sriperumbudur et al., 2010). This new objective function
allows us to derive simple yet effective algorithms to approximate the value function, without risking instability
or divergence (unlike TD algorithms), or solving a moresophisticated saddle-point problem (unlike SBEED). Our
approach also allows great flexibility in choosing the valuefunction approximation classes, including nonlinear ones
like neural networks. Experiments in several benchmarks
demonstrate the effectiveness of our method, for both policy
evaluation and optimization problems. We will focus on thebatch setting (or the growing-batch setting with a growing
replay buffer), and leave the online setting for future work.

Denote by Rπ V := Bπ V − V the Bellman error operator.
With a set D = {(si , ai , ri , s0i )}1≤i≤n of transitions whereai ∼ π(·|si ), the Bellman operator in state si can be approximated by bootstrapping: B̂π V (si ) := ri + γV (s0i ).
Clearly, E[B̂π Vθ (si )|si ] = Bπ Vθ (si ). In the literature,B̂π Vθ (si ) − Vθ (si ) is also known as the temporal differenceor TD error, whose expectation is the Bellman error. For
notation, all distributions are equivalized to their probability
density functions in the work.
Basic Algorithms. We are interested in estimating V π ,from a parametric family {Vθ : θ ∈ Θ}, from data D. The
residual gradient algorithm (Baird, 1995) minimizes thesquared TD error:
n
2
1 X
L̂RG (Vθ ) :=B̂π Vθ (si ) − Vθ (si ) ,
(1)
n i=1
with gradient descent update θt+1 = θt − ∇θ L̂RG (Vθt ),where

2. Background
This section starts with necessary notation and backgroundinformation, then reviews two representative algorithms
that work with general, nonlinear (differentiable) function
classes.
Notation. A Markov decision process (MDP) is denotedby M = hS, A, P, R, γ), where S is a (possibly infinite) state space, A an action space, P (s0 | s, a) thetransition probability, R(s, a) the average immediate reward, and γ ∈ (0, 1) a discount factor. The value funcπtionPof a policy π : S 7→ RA+ , denoted V (s) :=∞t
E [ t=0 γ R(st , at ) | s0 = s, at ∼ π(·, st )] , measures the
expected long-term return of a state. It is well-known that
V = V π is the unique solution to the Bellman equation (Puterman, 1994), V = Bπ V , where Bπ : RS → RS is the
Bellman operator, defined by
Bπ V (s) := Ea∼π(·|s),s0 ∼P (·|s,a) [R(s, a) + γV (s0 ) | s] .
While we develop and analyze our approach mostly for Bπ
given a fixed π (policy evaluation), we will also extend theapproach to policy optimization, where the corresponding
Bellman operator isBV (s) := max Es0 ∼P (·|s,a) [R(s, a) + γV (s0 ) | s, a] .
a

The unique fixed point of B is known as the optimal valuefunction, denoted V ∗ ; that is, BV ∗ = V ∗ .
Our work is built on top of an alternative to the fixed-pointview above: given some fixed distribution µ whose support
is S, V π is the unique minimizer of the squared Bellman
error:22
L2 (V ) := kBπ V − V kµ = Es∼µ (Bπ V (s) − V (s)) .

∇θ L̂RG (Vθ ) =

n


2 X
B̂π Vθ (si ) − Vθ (si ) · ∇θ B̂π Vθ (si ) − Vθ (si ) .
n i=1

However, the objective in (1) is a biased and inconsistentestimate of the squared Bellman error.
This is becauseEs∼µ [L̂RG (V )] = L2 (V ) + Es∼µ var(B̂π V (s)|s) 6=
L2 (V ), where there is an extra term that involves the conditional variance of the empirical Bellman operator, which
does not vanish unless the state transitions are deterministic.
As a result, RG can converge to incorrect value functions(see also Section 6). With random transitions, correcting thebias requires double samples (i.e., at least two independent
samples of (r, s0 ) for the same (s, a) pair) to estimate theconditional variance.
More popular algorithms in the literature are instead basedon fixed-point iterations, using B̂π to construct a target value
to update Vθ (si ). An example is fitted value iteration, or
FVI (Bertsekas & Tsitsiklis, 1996; Munos & Szepesvári,2008), which includes as special cases the empirically successful DQN and variants, as well as serves a key component
in many state-of-the-art actor-critic algorithms. In its basic
form, FVI starts from an initial θ0 , and iteratively updates
the parameter by
(
)
n
2
1 X
(t+1)
θt+1 = arg min L̂FVI (Vθ ) :=Vθ (si ) − B̂π Vθt (si )
.
n i=1
θ∈Θ
(2)
Different from RG, when gradient-based methods are applied to solve (2), the current parameter θt is treatedPn(t+1)
as a constant: ∇θ L̂FVI (Vθ ) = n1 i=1 Vθ (si ) −B̂π Vθt (si ) ∇θ Vθ (si ). TD(0) (Sutton, 1988) may be viewed
as a stochastic version of FVI, where a single sample (i.e.,A Kernel Loss for Solving the Bellman Equationn = 1) is drawn randomly (either from a stream of transitions or from a replay buffer) to estimate the gradient of(2).
Being fixed-point iteration methods, FVI-style algorithms
do not optimize any objective function, and their convergence is guaranteed only in rather restricted cases (e.g.,
Gordon, 1995; Tsitsiklis & Van Roy, 1997; Antos et al.,2008). Such divergent behavior is well-known and empirically observed (Baird, 1995; Boyan & Moore, 1995); see
Section 6 for more numerical examples. It creates substantial difficulty in parameter tuning and model selection inpractice.

Theorem 3.2. Under the same assumptions as Theorem 3.1,
2
we have LK (V ) = kV − V π kK ∗ ,µ , where k·kK ∗ ,µ is theK ∗ -norm under measure µ with a “dual” kernel K ∗ (s, s̄),defined byhK ∗ (s0 , s̄0 ) := Es,s̄ ∼ d∗π,µ K(s0 , s̄0 ) + γ 2 K(s, s̄)i− γ K(s0 , s̄) + K(s, s̄0 ) | s0 , s̄0 ,and the expectation
notation is shorthandREs∼d∗π,µ [f (s)|s0 ] = f (s)d∗π,µ (s|s0 )ds , withd∗π,µ (s|s0 ) :=X

forπ(a|s)P (s0 |s, a)µ(s)/µ(s0 ) .

a

3. Kernel Loss for Policy Evaluation
Much of the algorithmic challenge described earlier lies inthe difficulty in estimating squared Bellman error from data.
In this section, we address this difficulty by proposing a newloss function that is more amenable to statistical estimationfrom empirical data. Proofs are deferred to the appendix.
Our framework relies on an integrally strictly positive
definite (ISPD) kernel K : S × S → R, which is a2
symmetricbi-variate function that satisfies kf kK :=R
K(s, s̄)f (s)f (s̄) ds ds̄ > 0, for any non-zero L2 S2
integrable function f . We call kf kK the K-norm of f .
Many commonly used kernels, such as Gaussian RBF ker2
nel K(s, s̄) = exp(− ks − s̄k2 /h) is ISPD. More discussion on ISPD kernels can be found in Stewart (1976) and
Sriperumbudur et al. (2010).
3.1. The New Loss Function
Recall that Rπ = Bπ V − V is the Bellman error operator.
Our new loss function is defined by

The norm involves a quantity, d∗π,µ (s|s0 ), which may beheuristically viewed as a “backward” conditional probabilityof state s conditioning on observing the next state s0 (butnote that d∗π,µ (s|s0 ) is not normalized to sum to one unlessµ = dπ ).
Empirical Estimation The key advantage of the new loss
LK is that it can be easily estimated and optimized from observed transitions, without requiring double samples. Givena set of empirical data D = {(si , ai , ri , s0i )}1≤i≤n , a way
to estimate LK is to use the so-called V-statistics,
L̂K (Vθ ) :=

1
n2

X

K(si , sj ) · R̂π Vθ (si ) · R̂π Vθ (sj ) .

1≤i,j≤n(4)
Similarly,
thegradient∇θ LK (Vθ )=2Eµ [K(s, s̄)Rπ Vθ (s)∇θ (Rπ Vθ (s̄))] can be estimated by∇θ L̂K (Vθ ) :=

2
n2

X

K(si , sj )·R̂π Vθ (si )·∇θ R̂π Vθ (sj ) .

1≤i,j≤n2

LK (V ) = kRπ V kK,µ:= Es,s̄∼µ [K(s, s̄) · Rπ V (s) · Rπ V (s̄)] ,(3)

where µ is any positive density function on states s, ands, s̄ ∼ µ means s and s̄ are drawn i.i.d. from µ. Here,k·kK,µ is regarded as the K-norm under measure µ. It
is easy to show that kf kK,µ = kf µkK . Note that µ canbe either the visitation distribution under policy π (the onpolicy case), or some other distribution (the off-policy case).
Our approach handles both cases in a unified way. The
following theorem shows that the loss LK is consistent:
Theorem 3.1. Let K be an ISPD kernel and assumeµ(s) > 0,∀s ∈ S. Then, LK (V ) ≥ 0 for any V ; andLK (V ) = 0 if and only if V = V π . In other words,
V π = arg minV LK (V ).
The next result relates the kernel loss to a “dual” kernel
norm of the value function error, V − V π .

Remark An alternative approach is to use the U-statistics,
which removes the diagonal (i = j) terms in the pairwise
average in (4). Following standard statistical approximation
theory (e.g., Serfling, 2009), both U/V-statistics provide
consistent estimation of the expected quadratic quantity
given the sample is weakly dependent and satisfies certain
mixing condition (e.g., Denker & Keller, 1983; Beutner &Zähle, 2012); this often amounts to saying that {si } forms
a Markov chain that converges to its stationary distributionµ sufficiently fast. In the case of i.i.d. samples, it is known
that U-statistics forms an unbiased estimate, but may havehigher variance than the V-statistics. In our experiments, weobserve that V-statistics works better than U-statistics.
Remark Another advantage of our kernel loss is that wehave LK (V ) = 0 iff V = V π . Therefore, the magnitudeof the empirical loss L̂K (V ) reflects the closeness of V
to the true value function V π . In fact, by using methods
from kernel-based hypothesis testing (e.g., Gretton et al.,A Kernel Loss for Solving the Bellman Equation

2012; Liu et al., 2016; Chwialkowski et al., 2016), one
can design statistically calibrated methods to test if V =V π has been achieved, which may be useful for designingefficient exploration strategies. In this work, we focus on
estimating V π and leave it as future work to test valuefunction proximity.
3.2. Interpretations of the Kernel Loss
We now provide some insights into the new loss function,
based on two interpretations.
Eigenfunction Interpretation Mercer’s theorem implies
the following decomposition
K(s, s̄) =∞Xloss has a similar interpretation, with a different unit ball.
Any positive kernel K(s, s̄) is associated with a Reproducing Kernel Hilbert Space (RKHS) HK , which is theHilbert space consisting of (the closure of) the linear spanof K(·, s), for s ∈ S, and satisfies the reproducing property,
f (x) = hf, K(·, x)iHK , for any f ∈ HK . RKHS has been
widely used as a powerful tool in various machine learning and statistical problems; see Berlinet & Thomas-Agnan(2011); Muandet et al. (2017) for overviews.
Proposition 3.4. Let HK be the RKHS of kernel K(s, s̄),
we haveno2
LK (V ) = max (Es∼µ [Rπ V (s) × f (s)]) : kf kHK ≤ 1 .
f ∈HK

λi ei (s)ei (s̄) ,

(7)

(5)

i=1

of any continuous positive definite kernel on a compact
domain, where {ei }∞i=1 is a countable set of orthonormal
eigenfunctions w.r.t. µ (i.e., Es∼µ [ei (s)ej (s)] = 1{i = j}),and {λi }∞i=1 are their eigenvalues. For ISPD kernels, all the
eigenvalues must be positive: ∀i, λi > 0.
The following shows that LK is a squared projected Bellman
error in the space spanned by {ei }∞i=1 .

Since RKHS is a subset of the L2 space that includes smoothfunctions, we can again see that LK (V ) emphasizes more
the projections to smooth basis functions, matching theintuitive from Theorem 3.3. It also draws a connection
to the recent primal-dual reformulations of the Bellman
equation (Dai et al., 2017; 2018), which formulate V π as asaddle-point of the following minimax problem:min max Es∼µ 2Rπ V (s) × f (s) − f (s)2 ,(8)V

Proposition 3.3. If (5) holds, then LK (V ) =P∞
2Furthermore, if
i=1 λi (Es∼µ [Rπ V (s) × ei (s)]) .
{ei } is a complete orthonormal basis of L2 -space
under measure µ, then the L2 loss is L2 (V ) =P∞
2
i=1 (Es∼µ [Rπ V (s) × ei (s)]) . Therefore, LK (V ) ≤λmax L2 (V ), where λmax := maxi {λi }.
This result shows that the eigenvalue λi controls the contribution of the projected Bellman error to the eigenfunction
ei in LK . It may be tempting to have λi ≡ 1, in which
LK (V ) = L2 (V ), but the Mercer expansion in (5) can diverge to infinity, resulting in an ill-defined kernel K(s, s̄).
To avoid this,P∞the eigenvalues must decay to zero fast enoughsuch that i=1 λi < ∞. Therefore, the kernel loss LK (V )can be viewed as prioritizing the projections to the eigenfunctions with larger eigenvalues. In typical kernels such
as Gaussian RBF kernels, these dominant eigenfunctions
are Fourier bases with low frequencies (and hence highsmoothness), which may intuitively be more relevant thanthe higher frequency bases for practical purposes.
RKHS Interpretation The squared Bellman error has thefollowing variational form:
L2 (V ) = max (Es∼µ [Rπ V (s) × f (s)])

2fThis is equivalent to minimizing L2 (V ) as (6), except that
the L2 constraint is replaced by a quadratic penalty term.
When only samples are available, the expectation in (8)is replaced by the empirical version. If the optimization
domain of f is unconstrained, solving the empirical (8) reduces to the empirical L2 loss (1), which yields inconsistentestimation. Therefore, existing works propose to further
constrain the optimization of f in (8) to either RKHS (Daiet al., 2017) or neural networks (Dai et al., 2018), and hence
derive a minimax strategy for learning V . Unfortunately,
this is substantially more expensive than our method due tothe cost of updating another neural network f jointly; theminimax procedure may also make the training less stable
and more difficult to converge in practice.
3.3. Connection to Temporal Difference (TD) Methods
We now instantiate our algorithm in the tabular and linear
cases to gain further insights. Interestingly, we show that
our loss coincides with previous work, and as a result leads
to the same value function as several classic algorithms.
Hence, the approach developed here may be considered as
their strict extensions to the much more general nonlinear
function approximation classes.

fs.t. Es∼µ [(f (s))2 ] ≤ 1 ,(6)which involves finding a function f in the unit L2 -ball,whose inner product with Rπ V (s) is maximal. Our kernel

Again, let D be a set of n transitions sampled from distribution µ, and linear approximation be used: Vθ (s) = θT φ(s),where φ : S → Rd is a feature function, and θ ∈ Rd is
the parameter to be learned. The TD solution, θ̂TD , forA Kernel Loss for Solving the Bellman Equation

either on- and off-policy cases, can be found by various
algorithms (e.g., Sutton, 1988; Boyan, 1999; Sutton et al.,2009; Dann et al., 2014), and its theoretical properties havebeen extensively studied (e.g., Tsitsiklis & Van Roy, 1997;
Lazaric et al., 2012).
Corollary 3.5. When using a linear kernel of formk(s, s̄) = φ(s)T φ(s̄), minimizing the kernel objective (4)gives the TD solution θ̂TD .
Remark The result follows from the observation that ourloss becomes the Norm of the Expected TD Update (NEU)
in the linear case (Dann et al., 2014), whose minimizer
coincides with θ̂TD . Moreover, in finite-state MDPs, thecorollary includes tabular TD as a special case, by using
a one-hot vector (indicator basis) to represent states. In
this case, the TD solution coincides with that of a modelbased approach (Parr et al., 2008) known as certainty equivalence (Kumar & Varaiya, 1986). It follows that our algorithm includes certainty equivalence as a special case in
finite-state problems.

4. Kernel Loss for Policy Optimization
There are different ways to extend our approach to policy
optimization. One is to use the kernel loss (3) inside an
existing algorithm, as an alternative to RG or TD to learn
V π (s). For example, our loss fits naturally into an actorcritic algorithm, where we replace the critic update (often
implemented by TD(λ) or its variant) with our method, andthe actor updating part remains unchanged. Another, moregeneral way is to design a kernelized loss for V (s) andpolicy π(a|s) jointly, so that the policy optimization can besolved using a single optimization procedure. Here, we takethe first approach, leveraging our method to improve thecritic update step in Trust-PCL (Nachum et al., 2018).

for Bλ , which yields Vλ∗ . Then, (V, π) = (Vλ∗ , πλ∗ ) uniquely
solves∀(s, a) ∈ S×A :V (s) = R(s, a)+γEs0 |s,a [V (s0 )]−λ log π(a|s) .

This property inspires a natural extension of the kernel loss(3) to the controlled case:
LK (V ) = Es,s̄∼µ,a∼π(·|s),ā∼π(·|s̄) [K([s, a], [s̄, ā])
· Rπ,λ V (s, a) · Rπ,λ V (s̄, ā)] ,where Rπ,λ V (s, a) is given by
Rπ,λ V (s, a) = R(s, a)+γEs0 |s,a [V (s0 )]−λ log π(a|s)−V (s) .
Given a set of transitions D = {(si , ai , ri , s0i )}1≤i≤n , theobjective can be estimated byL̂K (Vθ ) =

1
n2

X

[K([si , ai ], [sj , aj ])R̂i R̂j ] ,1≤i,j≤nwith R̂i = ri + γVθ (s0i ) − λ log πθ (ai |si ) − Vθ (si ) . The
U-statistics version and the multi-step bootstrapping can besimilarly obtained (Nachum et al., 2017).

5. Related WorkIn this work, we studied value function learning, one of themost studied and fundamental problems in reinforcement
learning. The dominant approach is based on fixed-point
iterations (Bertsekas & Tsitsiklis, 1996; Szepesvári, 2010;
Sutton & Barto, 2018), which can risk instability and evendivergence when function approximation is used, as discussed in the introduction.

Our approach exemplifies more recent efforts that aim to
improve stability of value function learning by reformulatTrust-PCL is based on a temporal/path consistency condition
ing it as an optimization problem. Our key innovation isresulting from policy smoothing (Nachum et al., 2017). We
the use of a kernel method to estimate the squared Bellman
start with the smoothed Bellman operator, defined byerror, which is otherwise hard to estimate directly from samples, thus avoids the double-sample issue unaddressed by
Bλ V (s) = max Eπ [R(s, a) + γV (s0 ) + λH(π | s) | s] ,prior algorithms like residual gradient (Baird, 1995) andπ(·|s)∈PA
PCL (Nachum et al., 2017; 2018). As a result, our algorithm(9)
is consistent: it finds the true value function with enoughwhere PA is the set of distributions over action space A; thedata, using sufficiently expressive function approximation
conditional expectation Eπ [·|s] denotes a ∼ π(·|s), and λ >classes). Furthermore, the solution found by our algorithm
0 is a smoothing parameter;
P H is a state-dependent entropy
minimizes the projected Bellman error, as in prior works
term: H(π | s) := − a∈A π(a|s) log π(a|s). Intuitively,
when specialized to the same settings (Sutton et al., 2009;
Bλ is a smoothed approximation of B. It is known that
Maei et al., 2010; Liu et al., 2015; Macua et al., 2015).
Bλ is a γ-contraction (Fox et al., 2016), so has a unique
However, our algorithm is more general: it allows us to use
fixed point Vλ∗ . Furthermore, with λ = 0 we recover the
nonlinear value function classes and can be naturally imstandard Bellman operator, and λ smoothly controls kVλ∗ −plemented for policy optimization. Compared to nonlinearV ∗ k∞ (Dai et al., 2018).
GTD2/TDC (Maei et al., 2009), our method is simpler (withThe entropy regularization above implies the following pathout having to do a local linear expansion) and empiricallyconsistency condition. Let πλ∗ be an optimal policy in (9)more effective (as demonstrated in the next section).

A Kernel Loss for Solving the Bellman Equation

W2

1010

2.0

0

1.5

p=0.1 r = 0

10 10

1.0

2W3

10 20

0.5

r= 1

r=0
p=0.8

W1

r=0

p=0.2
W3

r=0

p = 0.9

10 300(a) Our MDP Example

200

400 600
Iterations

800 1000

K-loss
TD(0)
FVI
RG

0.0
0

200

400 600
Iterations

800 1000(c) ||w − w || vs. Iteration∗(b) MSE vs. Iteration

Figure 1. Modified example of (Tsitsiklis & Van Roy, 1997).

108

2.8

1.73

2.1

1.71

1.72

106

1.70

104

1.68

1.4

102

1.66

0.7

1000

1.64
2000
0

500

1000 1500
Epochs(a) MSEGTD2 (nonlinear)
TD0
FVI
RG
SBEED
K-loss

1.69
1.67

500

1000 1500
Epochs2000 0.01.3(b) Bellman Error

1.65

1.5
1.7
L2/K-Loss

1.9 1.631.3(c) L2/K-Loss vs MSE

1.5
1.7
L2/K-Loss

1.9(d) L2/K-Loss vs Bellman Error

Figure 2. Results on Puddle World.

As discussed in Section 3, our method is related to the recently proposed SBEED algorithm (Dai et al., 2018) whichshares many advantages with this work. However, SBEED
requires solving a minimax problem that can be rather challenging in practice. In contrast, our algorithm only needs tosolve a minimization problem, for which a wide range ofpowerful methods exist (e.g., Bertsekas, 2016). Note that
there exist other saddle-point formulations for RL, which
so far have focused on finite-state MDPs or linear valuefunction approximation (Chen et al., 2018; Wang, 2017).
Finally, the kernel method has been widely used in machinelearning (e.g., Schölkopf & Smola, 2001; Muandet et al.,2017). In RL, authors have used kernels either to modeltransition probabilities (Ormoneit & Sen, 2002) or to represent the value function (e.g., Xu et al., 2005; 2007; Taylor& Parr, 2009). These works differ significantly from our
method in that they use kernels to specify the function classof value functions or transition models. In contrast, we leverage kernels for designing proper loss functions to address
the double-sampling problem, while putting no constraints
on which approximation classes to represent the value function. Our approach is thus expected to be more flexible andscalable in practice, especially when combined with neuralnetworks.

6. Experiments
We compare our method (labelled “K-loss” in all experiments) with several representative baselines in both classic
examples and popular benchmark problems, for both policy

evaluation and optimization.
6.1. Modified Example of Tsitsiklis & Van Roy
Fig. 1 (a) shows a modified problem of the classic example by Tsitsiklis & Van Roy (1997), by making transitions
stochastic. It consists of 5 states, including 4 nonterminal(circles) and 1 terminal states (square), and 1 action. The
arrows represent transitions between states. The value function estimate is linear in the weight w = [w1 , w2 , w3 ]: forexample, the leftmost and bottom-right states’ values are w1
and 2w3 , respectively. Furthermore, we set γ = 1, so V (s)is exact with the optimal weight w∗ = [0.8, 1.0, 0]. In theexperiment, we randomly collect 2 000 transition tuples fortraining. We use a linear kernel in our method, so that it willfind the TD solution (Corollary 3.5).
Fig. 1 (b&c) show the learning curves of mean squared error
w − w∗ k) of different al(kV − V ∗ k2 ) and weight error (kwgorithms over iterations. Results are consistent with theory:
our method converges to the true weight w∗ , while both FVI
and TD(0) diverge, and RG converges to a wrong solution.
6.2. Policy Evaluation with Neural Networks
While popular in recent RL literature, neural networks are
known to be unstable for a long time. Here, we revisit
the classic divergence example of Puddle World (Boyan &Moore, 1995), and demonstrate the stability of our method.
Experimental details are found in Appendix B.1.
Fig. 2 summarizes the result using a neural network as value

A Kernel Loss for Solving the Bellman Equation

104

1.1
1.2

102

GTD2 (nonlinear)
TD0
FVI
RG
SBEED
K-loss

1.3
1.4

100
500

1000 1500
Epochs(a) CartPole MSE

104

1.0

103.5

0.5
0.0
0.5

102.5

1.60

2000

1.5

103

1.5

10 20

104.5

500

1000 1500
Epochs

2000

0

1000
2000
Epochs(b) CartPole Bellman Error

3000

1.00

(c) Mountain Car MSE

1000
2000
Epochs3000(d) Mountain Car Bellman Error

Average Returns

Figure 3. Policy evaluation results on CartPole and Mountain Car.
350
300
250
200
150
100
50
0.0

10000
8000
6000
2000
0.4 0.6 0.8
million steps(a) Swimmer

1.0

1000

1500

800
600

1000

4000
0.2

2000

0.0

0.2

0.4
0.6
million steps

0.8(b) InvertedDoublePendulum

500
0.0

400
200

0.3

0.6 0.9 1.2
million steps

1.5

0.0

(c) Ant

0.1

0.2
0.3
million steps

0.4

K-loss
TD(0)
FVI
RG

0.5

(d) InvertedPendulum

Figure 4. Results of various variants of Trust PCL on Mujoco Benchmark.

function for two metrics: kV − V ∗ k22 and kBV − V k22 ,both evaluated on the training transitions. First, as shownin (a-b), our method works well while residual gradientconverged to inferior solutions. In contrast, FVI and TD(0)exhibit unstable/oscilating behavior, and can even diverge,
which is consistent with past findings (Boyan & Moore,
1995). In addition, non-linear GTD2 (Maei et al., 2009) and
SBEED (Dai et al., 2017; 2018), which do not find a better
solution than our method in terms of MSE.
Second, Fig. 2(c&d) show the correlation between MSE,
emperical Bellman error of the value function estimation
and an algorithm’s training objective respectively. Our kernel loss appears to be a good proxy for learning the valuefunction, for both MSE and Bellman error. In contrast, theL2 loss (used by residual gradient) does not correlate well,which also explains why residual gradient has been observed
not to work well empirically.
Fig. 3 shows more results on value function learning on
CartPole and Mountain Car, which again demonstrate that
our method performs better than other methods in general.
6.3. Policy Optimization
To demonstrate the use of our method in policy optimization, we combine it with Trust-PCL, and compare withvariants of Trust-PCL combined with FVI, TD0 and RG. To
fairly evaluate the performance of all these four methods,
we use Trust-PCL (Nachum et al., 2018) framework andthe public code for our experiments. We only modify thetraining of Vθ (s) for each of the method and keep rest sameas original release. Experimental details can be found in
Appendix B.2.1.
We evaluate the performance of these four methods on Mujoco benchmark and report the best performance of thesefour methods in Figure 4 (averaged on five different random
seeds). K-loss consistently outperforms all the other methods, learning bettere policy with fewer data. Note that weonly modify the update of value functions inside Trust PCL,
which can be implemented relatively easily. We expect that
we can improve many other algorithms in similar ways by
improving the value function using our kernel loss.

7. Conclusion
This paper studies the fundamental problem of solving Bellman equations with parametric value functions. A novel
kernel loss is proposed, which is easy to be estimated andoptimized using sampled transitions. Empirical results show
that, compared to prior algorithms, our method is convergent, produces more accurate value functions, and can beeasily adapted for policy optimization. These promising results open the door to many interesting directions for future
work, including finite-sample analysis, adaptation to online
RL, and uncertainty estimation for exploration.

References
Antos, A., Szepesvári, C., and Munos, R. Learning nearoptimal policies with Bellman-residual minimizing based
fitted policy iteration and a single sample path. Machine
Learning, 71(1):89–129, 2008.

A Kernel Loss for Solving the Bellman Equation

Baird, L. C. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the
Twelfth International Conference on Machine Learning,pp. 30–37, 1995.

Farahmand, A. M., Ghavamzadeh, M., Szepesvári, C., andMannor, S. Regularized policy iteration. In Advances in
Neural Information Processing Systems 21, pp. 441–448,
2008.

Berlinet, A. and Thomas-Agnan, C. Reproducing kernel
Hilbert spaces in probability and statistics. Springer
Science & Business Media, 2011.

Fox, R., Pakman, A., and Tishby, N. Taming the noise inreinforcement learning via soft updates. In Proceedings of
the Thirty-Second Conference on Uncertainty in Artificial
Intelligence, 2016.

Bertsekas, D. P. Nonlinear Programming. Athena Scientific,
3rd edition, 2016.
Bertsekas, D. P. and Tsitsiklis, J. N. Neuro-Dynamic Programming. Athena Scientific, September 1996.
Beutner, E. and Zähle, H. Deriving the asymptotic distribution of U- and V-statistics of dependent data using
weighted empirical processes. Bernoulli, pp. 803–822,
2012.
Boyan, J. A. Least-squares temporal difference learning. In
Proceedings of the Sixteenth International Conference on
Machine Learning, pp. 49–56, 1999.
Boyan, J. A. and Moore, A. W. Generalization in reinforcement learning: Safely approximating the value function.
In Advances in Neural Information Processing Systems 7,
pp. 369–376, 1995.
Chen, Y., Li, L., and Wang, M. Scalable bilinear π-learning
using state and action features. In Proceedings of theThirty-Fifth International Conference on Machine Learning, pp. 833–842, 2018.
Chwialkowski, K., Strathmann, H., and Gretton, A. A kernel
test of goodness of fit. JMLR: Workshop and Conference
Proceedings, 2016.
Dai, B., He, N., Pan, Y., Boots, B., and Song, L. Learning from conditional distributions via dual embeddings.
In Artificial Intelligence and Statistics, pp. 1458–1467,
2017.
Dai, B., Shaw, A., Li, L., Xiao, L., He, N., Liu, Z., Chen, J.,
and Song, L. SBEED: Convergent reinforcement learningwith nonlinear function approximation. In Proceedingsof the Thirty-Fifth International Conference on Machine
Learning, pp. 1133–1142, 2018.
Dann, C., Neumann, G., and Peters, J. Policy evaluation
with temporal differences: A survey and comparison.
Journal of Machine Learning Research, 15(1):809–883,
2014.
Denker, M. and Keller, G. On U-statistics and v. mise’statistics for weakly dependent processes. Zeitschrift für
Wahrscheinlichkeitstheorie und verwandte Gebiete, 64(4):505–522, 1983.

Gordon, G. J. Stable function approximation in dynamic
programming. In Proceedings of the Twelfth International
Conference on Machine Learning, pp. 261–268, 1995.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf,
B., and Smola, A. A kernel two-sample test. Journal of
Machine Learning Research, 13(Mar):723–773, 2012.
Gu, S., Lillicrap, T. P., Sutskever, I., and Levine, S. Continuous deep Q-learning with model-based acceleration. In
Proceedings of the Thirty-third International Conference
on Machine Learning, pp. 2829–2838, 2016.
Kumar, P. and Varaiya, P. Stochastic Systems: Estimation,
Identification, and Adaptive Control. Prentice Hall, 1986.
Lazaric, A., Ghavamzadeh, M., and Munos, R. Finitesample analysis of least-squares policy iteration. Journalof Machine Learning Research, pp. 3041–3074, 2012.
Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., andPetrik, M. Finite-sample analysis of proximal gradient TD algorithms. In Proceedings of the Thirty-First
Conference on Uncertainty in Artificial Intelligence, pp.
504–513, 2015.
Liu, Q., Lee, J., and Jordan, M. A kernelized Stein discrepancy for goodness-of-fit tests. In International Conference on Machine Learning, pp. 276–284, 2016.
Macua, S. V., Chen, J., Zazo, S., and Sayed, A. H. Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control, 60(5):1260–1274, 2015.
Maei, H. R. Gradient Temporal-Difference Learning Algorithms. PhD thesis, University of Alberta, Edmonton,
Alberta, Canada, 2011.
Maei, H. R., Szepesvári, C., Bhatnagar, S., Precup, D., Silver, D., and Sutton, R. S. Convergent temporal-difference
learning with arbitrary smooth function approximation.
In Advances in Neural Information Processing Systems
22, pp. 1204–1212, 2009.
Maei, H. R., Szepesvári, C., Bhatnagar, S., and Sutton,
R. S. Toward off-policy learning control with function
approximation. In Proceedings of the Twenty-SeventhA Kernel Loss for Solving the Bellman Equation

International Conference on Machine Learning, pp. 719–
726, 2010.

Serfling, R. J. Approximation theorems of mathematicalstatistics, volume 162. John Wiley & Sons, 2009.

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness,
J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik,
A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D.,
Legg, S., and Hassabis, D. Human-level control throughdeep reinforcement learning. Nature, 518:529–533, 2015.

Sriperumbudur, B. K., Gretton, A., Fukumizu, K.,
Schölkopf, B., and Lanckriet, G. R. Hilbert space embeddings and metrics on probability measures. Journal of
Machine Learning Research, 11(Apr):1517–1561, 2010.

Mnih, V., Adrià, Badia, P., Mirza, M., Graves, A., Lillicrap,
T. P., Harley, T., Silver, D., and Kavukcuoglu, K. Asynchronous methods for deep reinforcement learning. In
Proceedings of the Thirty-third International Conference
on Machine Learning, pp. 1928–1937, 2016.
Muandet, K., Fukumizu, K., Sriperumbudur, B., Schölkopf,
B., et al. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends R in Machine
Learning, 10(1-2):1–141, 2017.
Munos, R. and Szepesvári, C. Finite-time bounds forsampling-based fitted value iteration. Journal of Machine
Learning Research, 9:815–857, 2008.
Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D.
Bridging the gap between value and policy based reinforcement learning. In Advances in Neural Information
Processing Systems 30, pp. 2772–2782, 2017.
Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D.
Trust-PCL: An off-policy trust region method for continuous control. In International Conference on Learning
Representations, 2018.
Ormoneit, D. and Sen, Ś. Kernel-based reinforcement learning. Machine Learning, 49:161–178, 2002.
Parr, R., Li, L., Taylor, G., Painter-Wakefield, C., andLittman, M. L. An analysis of linear models, linear
value-function approximation, and feature selection forreinforcement learning. In Proceedings of the TwentyFifth International Conference on Machine Learning, pp.
752–759, 2008.
Puterman, M. L. Markov Decision Processes: Discrete
Stochastic Dynamic Programming. Wiley-Interscience,
New York, 1994.
Schölkopf, B. and Smola, A. J. Learning with kernels:
Support vector machines, regularization, optimization,and beyond. MIT press, 2001.
Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel,
P. High-dimensional continuous control using generalized
advantage estimation. In Proceedings of the International
Conference on Learning Representations, 2016.

Stewart, J. Positive definite functions and generalizations,an historical survey. The Rocky Mountain Journal of
Mathematics, 6(3):409–434, 1976.
Sutton, R. S. Learning to predict by the methods of temporal
differences. Machine Learning, 3(1):9–44, 1988.
Sutton, R. S. and Barto, A. G. Reinforcement Learning:
An Introduction. Adaptive Computation and Machine
Learning. MIT Press, 2nd edition, 2018.
Sutton, R. S., Maei, H., Precup, D., Bhatnagar, S.,
Szepesvári, C., and Wiewiora, E. Fast gradient-descentmethods for temporal-difference learning with linear function approximation. In Proceedings of the Twenty-Sixth
International Conference on Machine Learning, pp. 993–
1000, 2009.
Szepesvári, C. Algorithms for Reinforcement Learning.
Morgan & Claypool, 2010.
Taylor, G. and Parr, R. Kernelized value function approximation for reinforcement learning. In Proceedings of
the Twenty-Sixth International Conference on Machine
Learning, pp. 1017–1024, 2009.
Tsitsiklis, J. N. and Van Roy, B. An analysis of temporaldifference learning with function approximation. IEEE
Transactions on Automatic Control, 42:674–690, 1997.
Wang, M. Primal-dual π learning: Sample complexity andsublinear run time for ergodic Markov decision problems,
2017. CoRR abs/1710.06100.
Wang, Z., Schaul, T., Hessel, M., van Hasselt, H., Lanctot,
M., and de Freitas, N. Dueling network architectures
for deep reinforcement learning. In Proceedings of theThird International Conference on Machine Learning, pp.
1995–2003, 2016.
Wu, Y., Mansimov, E., Grosse, R. B., Liao, S., and Ba,
J. Scalable trust-region method for deep reinforcement
learning using Kronecker-factored approximation. In
Advances in Neural Information Processing Systems 30,
pp. 5285–5294, 2017.
Xu, X., Xie, T., Hu, D., and Lu, X. Kernel least-squares
temporal difference learning. International Journal of
Information and Technology, 11(9):54–63, 2005.

A Kernel Loss for Solving the Bellman Equation

Xu, X., Hu, D., and Lu, X. Kernel-based least-squares policy
iteration for reinforcement learning. IEEE Transactions
on Neural Networks, 18(4):973–992, 2007.

A Kernel Loss for Solving the Bellman Equation

Appendix
A. Proofs for Section 3
A.1. Proof of Theorem 3.1
The assertion that LK (V ) ≥ 0 for all V is immediate from definition. For the second part, we have
LK (V ) = 0⇐⇒

kRπ V kK,µ = 0⇐⇒kRπ V · µkK = 0⇐⇒∀s ∈ S :Rπ V (s)µ(s) = 0⇐⇒∀s ∈ S :Rπ V (s) = 0⇐⇒

π(since K is an is ISPD kernel)

V =V .

A.2. Proof of Theorem 3.2
Define δ = V − V π to be the value function error. Furthermore, let I be the identity operator (IV = V ), andPπ V (s) := Ea∼π(·|s),s0 ∼P (·|s,a) [γV (s0 ) | s]
the state-transition part of Bellman operator without the local reward term R(s, a).
Note that Rπ V π = Bπ V π − V π = 0 by the Bellman equation, so
Rπ V = Rπ V − Rπ V π = (Pπ V − V ) − (Pπ V π − V π ) = (Pπ − I)(V − V π ) = (Pπ − I)δ .
Therefore,
LK (V ) = Eµ [Rπ V (s) · Rπ V (s̄) · K(s, s̄)]= Eµ [(I − Pπ )δ(s) · (I − Pπ )δ(s̄) · K(s, s̄)]= E(s,s0 ),(s̄,s̄0 )∼dπ,µ [(δ(s) − γδ(s0 )) · (δ(s̄) − γδ(s̄0 )) · K(s, s̄)],where Edπ,µ [·] denotes the expectation under the joint distribution
dπ,µ (s, s0 ) := µ(s)X

π(a|s)P (s0 |s, a).

a∈A

Expanding the quadratic form above, we have
LK (V )= Edπ,µ [(δ(s)K(s, s̄)δ(s̄) − γδ(s0 )δ(s̄)K(s, s̄) − γδ(s̄0 )δ(s)K(s, s̄) + γ 2 δ(s0 )δ(s̄0 )K(s, s̄)]= Eµ [δ(s0 )K ∗ (s0 , s̄0 )δ(s̄0 )],where K ∗ (s0 , s̄0 ) is as defined in the theorem statement:K ∗ (s0 , s̄0 ) = Ed∗π,µ K(s0 , s̄0 ) − γ(K(s0 , s̄) + K(s, s̄0 )) + γ 2 K(s, s̄) | (s0 , s̄0 )with the expectation w.r.t. the following “backward” conditional probability
Pπ(a|s)P (s0 |s, a)µ(s)∗0dπ,µ (s | s ) := a∈A,µ(s0 )
which can be heuristically viewed as the distribution of state s conditioning on observing its next state s0 when following
dπ,µ (s, s0 ).

A Kernel Loss for Solving the Bellman Equation

A.3. Proof of Proposition 3.3
Using the eigen-decomposition (5), we have
LK (V ) = Eµ [Rπ V (s)K(s, s̄)Rπ V (s̄)]∞
X= Eµ [Rπ V (s)λi ei (s)ei (s̄)Rπ V (s̄)]
i=1

=

∞
X

2

λi (Eµ [Rπ V (s)ei (s)]) .

i=1

The decomposition of L2 (V ) follows directly from Parseval’s identity.
A.4. Proof of Proposition 3.4
The reproducing property of RKHS implies f (s) = hf, K(s, ·)iHK for any f ∈ HK . Therefore,Eµ [Rπ V (s)f (s)] = Eµ [Rπ V (s)hf, K(s, ·)iHK ]= hf, Eµ [Rπ V (s)K(s, ·)]iHK= hf, f ∗ iHK .
where we have defined f ∗ (·) := Eµ [Rπ V (s)K(s, ·)]. Maximizing hf, f ∗ i subject to kf kHK :=that f = f ∗ / kf ∗ kHK . Therefore,2max

f ∈HK : kf kH

K≤1(Es [Rπ V (s)f (s)]) = (hphf, f iHK ≤ 1 yields

f∗2, f ∗ iHK )2 = kf ∗ kHK .
kf ∗ kHK

Further, we can show that2

kf ∗ kHK= hf ∗ , f ∗ iHK= hEµ [Rπ V (s)K(s, ·)], Eµ [Rπ V (s̄)K(s̄, ·)]iHK= Eµ [Rπ V (s)K(s, s̄)Rπ V (s̄)],where the last step follows from the reproducing property, K(s, s̄) = hK(s, ·), K(s̄, ·)iHK . This completes the proof, bydefinition of LK (V ).
A.5. Proof of Corollary 3.5
Under the conditions of the corollary, the kernel loss becomes the Norm of the Expected TD Update (NEU), whose minimizer
coincides with the TD solution (Dann et al., 2014). For completeness, we provide a self-contained proof.
Since we are estimating the value function of a fixed policy, we ignore the actions, and the set of transitions is D ={(si , ri , s0i )}1≤i≤n . Define the following vector/matrices:r=[r1 ; r2 , · · · ; rn ] ∈ Rn×1 ,X=[φ(s1 ); φ(s2 ); . . . ; φ(sn )] ∈ Rn×d ,0=[φ(s01 ); φ(s02 ); . . . ; φ(s0n )] ∈ Rn×d ,X

and Z = X − γX 0 , where d is the feature dimension. Then, the TD solution is given byθ̂TD = (X T Z)−1 X T r .
Note that the above includes both the on-policy case as well as the off-policy case as in many previous algorithms withlinear value function approximation (Dann et al., 2014), where the difference is in whether si is sampled from the state
occupation distribution of the target policy or not.

A Kernel Loss for Solving the Bellman Equation

Define δ ∈ Rn×1 to be the TD error vector; that is, δ = r − Zθ, whereδi = ri + γV (s0i ) − V (si ) = ri + θT (γφ(s0i ) − φ(si )) .
With a linear kernel, our objective function becomes:
1 X11`(θ) = 2
δi K(si , sj )δj = 2 δ T XX T δ = 2 (r − Zθ)T XX T (r − Zθ) .
n i,j
n
n
Its gradient is given by∇` = ∇(=

1
θT Z T XX T Zθ − 2rT XX T Zθ + constant(θ)
n22(Z T XX T Zθ − Z T XX T r) .
n2

Letting ∇` = 0 gives the solution obtained by minimizing our kernel loss:1
θ̂KBE = (Z T XX T Z)−1 Z T XX T r .
Therefore,θ̂KBE − θ̂TD = (Z T XX T Z)−1 Z T X − (X T Z)−1 X T r
= (Z T XX T Z)−1 Z T X(X T Z) − I (X T Z)−1 X T r= (I − I) (X T Z)−1 X T r = 0 .

B. Experiment Details
B.1. Policy Evaluation
We compare our method with representative policy evaluation methods including TD(0), FVI, RG, nonlinear GTD2 (Maeiet al., 2009) and SBEED (Dai et al., 2017; 2018) on three different stochastic environments: Puddle World, CartPole andMountain Car. Followings are the detail of the policy evaluation experiments.
Network Structure We parameterize the value function Vθ (s) using a fully connected neural network with one hidden
layer of 80 units, using relu as activation function. For test function f (s) in SBEED, we use a small neural network with
10 hidden units and relu as activation function.
Data Collection For each environment, we randomly collect 5000 independent transition tuples with states uniformly
drawn from state space using a policy π learned by policy optimization, for which we want to learn the value function
V π (s).
Estimating the true value function V π (s) To evaluate and compare all methods, we approximate the true value function
by finely discretizing the state space and then applying tabular value iteration on the discretized MDP. Specifically, we
discretize the state space into 25 × 25 grid for Puddle World, 20 × 25 discrete states for CartPole, and 30 × 25 discrete
states for Mountain Car.
Training Details For each environment and each policy evaluation method, we train the value function Vθ (s) on thecollected 5000 transition tuples for 2000 epochs (3000 for Mountain Car), with a batch size n = 150 in each epoch
using Adam optimizer. We search the learning rate in {0.003, 0.001, 0.0003} for all methods and report the best result
averaging over 10 trials using different random seeds. For our method, we use a Gaussian RBF kernel K(si , sj ) =2
exp (− ksi − sj k2 /h2 ) and take the bandwidth to be h = 0.5. For FVI, we update the target network at the end of eachepoch training. For SBEED, we perform 10 times gradient ascent updates on the test function f (s) and 1 gradient descent
update on Vθ (s) at each iteration. We fix the discount factor to γ = 0.98 for all environments and policy evaluation methods.
1

For simplicity, assume all involved matrices of size d × d are non-singular, as is typical in analyzing TD algorithms. Without thisassumption, we may either add L2 -regularization to XX T (Farahmand et al., 2008), for which the same equivalence between TD andours can be proved, or show that the solutions lie in an affine space in Rd but the corresponding value functions are identical.

A Kernel Loss for Solving the Bellman Equation

B.2. Policy Optimization
In this section we describe in detail the experimental setup for policy optimization regarding implementation and hyperparameter search. The code of Trust-PCL is available at github2 . Algorithm 1 describes details in pseudocode, where the themain change compared to Trust-PCL is highlighted. Note that as in previous work, we use the d-step version of Bellman
operator, an immediate extension to the d = 1 case described in the main text.
B.2.1. N ETWORK A RCHITECTURES
We use fully-connected feed-forward neural network to represent both policy and value network. The policy πθ is represented
by a neural network with 64 × 64 hidden layers with tanh activations. At each time step t, the next action at is sampled
randomly from a Gaussian distribution N (µθ (st ), σθ ). The value network Vθ (s) is represented by a neural network with
64 × 64 hidden layers with tanh activations. At each time step t, the network is given the observation st and it produces asingle scalar output value. All methods share the same policy and value network architectures.
B.2.2. T RAINING D ETAILS
We average over the best 5 of 6 randomly seeded training runs and evaluate each method using the mean µθ (s) of the
diagonal Gaussian policy πθ . Since Trust-PCL is off-policy, we collect experience and train on batches of experiencesampled from the replay buffer. At each training iteration, we will first sample T = 10 timestep samples and add them to thereplay buffer, then both the policy and value parameters are updated in a single gradient step using the Adam optimizer witha proper learning rate searched, using a minibatch randomly sampled from replay buffer. For Trust-PCL using FVI updatingVθ (s), which requires a target network to estimate the final state for each path, we use an exponentially moving average,
with a smoothing constant τ = 0.99, to update the target value network weights as common in the prior work (Mnih et al.,2015). For Trust-PCL using TD(0), we will directly use current value network Vθ (s) to estimate the final states except we
do not perform gradient update for the final states. For Trsut-PCL using RG and K-loss, which has an objective loss, we will
directly perform gradient descent to optimize both policy and value parameters.
B.2.3. H YPERPARAMETER S EARCH
We follow the same hyperparameter search procedure in Nachum et al. (2018) for FVI, TD(0) and RG based Trust-PCL3 .
We search the maximum divergence  between πθ and πθ̂ among ∈ {0.001, 0.0005, 0.002}, and parameter learning ratein {0.001, 0.0003, 0.0001}, and the rollout length d ∈ {1, 5, 10}. We also searched with the entropy coefficient λ, either
keeping it at a constant 0 (thus, no exploration) or decaying it from 0.1 to 0.0 by a smoothed exponential rate of 0.1 every
2500 training iterations. For each hyper-parameter setting, we average best 5 of 6 seeds and report the best performance forthese methods.
For our proposed K-loss, we also search the maximum divergence  but keep the learning rate as 0.001. Additionally, for22K-loss we use a Gaussian RBF kernel K([si , ai ], [sj , aj ]) = exp√ (−(ksi − sj k2 + kai − aj k2 )/h), and take the bandwidth2
to be h = (α × med) , where we search α ∈ {0.1, 0.01, (1/ log B)}, and B = 64 is the gradient update batch size. We
fix the discount to γ = 0.995 for all environments and batch size B = 64 for each training iteration.

23

https://github.com/tensorflow/models/tree/master/research/pcl_rl
Please check readme file in https://github.com/tensorflow/models/tree/master/research/pcl_rl

A Kernel Loss for Solving the Bellman Equation

Algorithm 1 K-Loss for PCL
Input: rollout step d, batch size B, coefficient λ, τ .
Initialize Vθ (s), πφ (a|s), and empty replay buffer RB(β). Set φ̃ = φ.
repeat// Collecting Samples
Sample P steps st:t+P ∼ πφ on ENV.
Insert st:t+P to RB(β).
// Train
(k)
(k)
(k)
Sample batch {st:t+d , at:t+d , rt:t+d }B
k=1 from RB(β) to contain a total of Q transitions (B ≈ Q/d).
P
1∆θ = ∇θ B 2 1≤i,j≤B [K([si , ai ], [sj , aj ])R̂i R̂j ],P
Pd−1∆φ = − B1
t=0 ∇φ log πφ (at+i |st+i )], where1≤i≤B [R̂iR̂i = −Vθ (si ) + γ d Vθ (si+d ) +d−1Xγ t (ri+t − (λ + τ ) log πφ (at+i |st+1 ) + τ log πφ̃ (at+i |st+1 )).

t=0Update θ and φ using ADAM with ∆θ, ∆φ.
// Update auxiliary variables
Update φ̃ = αφ̃ + (1 − α)φ.
until Convergence

2500
2000
1500
1000
500
0.0

0.4

0.8 1.2 1.6
million steps(a) Walker2d

2.0

3500
3000
2500
2000
1500
1000
500
0
0.0

K-loss
TD(0)
FVI
RG

0.4

0.8 1.2 1.6
million steps

2.0(b) HalfCheetah

Figure 5. More results of various variants of Trust PCL on Mujoco Benchmark (on top of Figure 4).