Integral Policy Iterations for Reinforcement Learning Problems in
Continuous Time and Space ?
Jae Young Lee ∗ , Richard S. Sutton

arXiv:1705.03520v1 [] 9 May 2017

Department of Computing Science, University of Alberta, Edmonton, AB, Canada, T6G 2R3.

Abstract
Policy iteration (PI) is a recursive process of policy evaluation and improvement to solve an optimal decision-making, e.g., reinforcement
learning (RL) or optimal control problem and has served as the fundamental to develop RL methods. Motivated by integral PI (IPI)
schemes in optimal control and RL methods in continuous time and space (CTS), this paper proposes on-policy IPI to solve the general
RL problem in CTS, with its environment modelled by an ordinary differential equation (ODE). In such continuous domain, we also
propose four off-policy IPI methods—two are the ideal PI forms that use advantage and Q-functions, respectively, and the other two
are natural extensions of the existing off-policy IPI schemes to our general RL framework. Compared to the IPI methods in optimal
control, the proposed IPI schemes can be applied to more general situations and do not require an initial stabilizing policy to run; they
are also strongly relevant to the RL algorithms in CTS such as advantage updating, Q-learning, and value-gradient based (VGB) greedy
policy improvement. Our on-policy IPI is basically model-based but can be made partially model-free; each off-policy method is also
either partially or completely model-free. The mathematical properties of the IPI methods—admissibility, monotone improvement, and
convergence towards the optimal solution—are all rigorously proven, together with the equivalence of on- and off-policy IPI. Finally, the
IPI methods are simulated with an inverted-pendulum model to support the theory and verify the performance.
Key words: policy iteration, reinforcement learning, optimization under uncertainties, continuous time and space, iterative schemes,
adaptive systems

1

Introduction

Policy iteration (PI) is a recursive process to solve an optimal decision-making/control problem by alternating between policy evaluation to obtain the value function with
respect to the current policy (a.k.a. the current control law in
control theory) and policy improvement to improve the policy by optimizing it using the obtained value function (Sutton and Barto, 2017; Lewis and Vrabie, 2009). PI was first
proposed by Howard (1960) in the stochastic environment
known as Markov decision process (MDP) and is strongly
relevant to reinforcement learning (RL) and approximate dynamic programming (ADP). PI has served as a fundamental
principle to develop RL and ADP methods especially when
the underlying environment is modelled or approximated by
an MDP in a discrete space. There are also model-free off? The authors gratefully acknowledge the support of Alberta
Innovates–Technology Futures, the Alberta Machine Intelligence
Institute, Google Deepmind, and the Natural Sciences and Engineering Research Council of Canada.
∗ Corresponding author. Tel.: +1 587 597 8677.
Email addresses: jyounglee@ualberta.ca (Jae Young
Lee ), rsutton@ualberta.ca (Richard S. Sutton).

Preprint submitted to Automatica

policy PI methods using Q-functions and their extensions to
incremental RL algorithms (e.g., Lagoudakis and Parr, 2003;
Farahmand, Ghavamzadeh, Mannor, and Szepesvári, 2009;
Maei, Szepesvári, Bhatnagar, and Sutton, 2010). Here, offpolicy PI is a class of PI methods whose policy evaluation
is done while following a policy, termed as a behavior policy, which is possibly different from the target policy to be
evaluated; if the behavior and target policies are same, it is
called an on-policy method. When the MDP is finite, all the
on- or off-policy PI methods converge towards the optimal
solution in finite time. Another advantage is that compared
to backward-in-time dynamic programming, the forward-intime computation of PI like the other ADP methods (Powell,
2007) alleviates the problem known as the curse of dimensionality. In continuing tasks, a discount factor γ is normally
introduced to PI and RL to suppress the future reward and
thereby have a finite return. Sutton and Barto (2017) gives
a comprehensive overview of PI, ADP, and RL algorithms
with their practical applications and recent success in the
RL field.

11 May 2017

1.1

tal case γ = 1, but not the discounted case 0 < γ < 1. 1 The
other restriction of those stability-based designs is that the
initial policy needs to be asymptotically stabilizing to run
the PI methods. This is quite contradictory for IPI methods
since they are partially or completely model-free, but it is
hard or even impossible to find a stabilizing policy without knowing the dynamics. Besides, compared with the RL
frameworks in CTS, e.g., those in (Doya, 2000; Mehta and
Meyn, 2009; Frémaux, Sprekeler, and Gerstner, 2013), this
stability-based approach rather restricts the class of the cost
(or reward) and the dynamics. For instances, the dynamics
was assumed to have at least one equilibrium state, 2 and
the goal was always to (locally) stabilize the system in an
optimal fashion to that equilibrium state although there may
also exist multiple isolated equilibrium states to be considered or bifurcation; for such optimal stabilization, the cost
was always crafted to be non-negative for all points and zero
at the equilibrium.

PI and RL in Continuous Time and Space (CTS)

Different from the MDP in discrete space, the dynamics of
real physical world is usually modelled by (ordinary) differential equations (ODEs) inevitably in CTS. PI has been
also studied in such continuous domain mainly under the
framework of deterministic optimal control, where the optimal solution is characterized by the partial differential
Hamilton-Jacobi-Bellman equation (HJBE) which is however extremely difficult or hopeless to be solved analytically,
except in a very few special cases. PI in this field is often
referred to as successive approximation of the HJBE (to recursively solve it!), and the main difference among them lies
in their policy evaluation—the earlier versions of PI solve
the associated infinitesimal Bellman equation (a.k.a. Lyapunov or Hamiltonian equation) to obtain the value function
for the current policy (e.g., Leake and Liu, 1967; Kleinman, 1968; Saridis and Lee, 1979; Beard, Saridis, and Wen,
1997; Abu-Khalaf and Lewis, 2005, to name a few); Murray,
Cox, Lendaris, and Saeks (2002) proposed a PI algorithm
along with the trajectory-based policy evaluation that does
not rely on the system model and can be viewed as a deterministic Monte-Carlo policy evaluation (Sutton and Barto,
2017). Motivated by those two approaches above, Vrabie
and Lewis (2009) recently proposed a partially model-free
PI scheme called integral PI (IPI), which is more relevant
to RL/ADP in that the Bellman equation associated with
its policy evaluation is of a temporal difference form—see
(Lewis and Vrabie, 2009) for a comprehensive overview.
By partially model-free, it is meant in this paper that the
PI can be done without explicit use of some or any inputindependent part of the dynamics. IPI is then extended to
a series of completely or partially model-free off-policy IPI
methods (e.g., Lee, Park, and Choi, 2012, 2015; Luo, Wu,
Huang, and Liu, 2014; Modares, Lewis, and Jiang, 2016, to
name a few), with a hope to further extend them to incremental off-policy RL methods for adaptive optimal control
in CTS—see (Vamvoudakis, Vrabie, and Lewis, 2014) for an
incremental extension of the on-policy IPI method. The on/off-policy equivalence and the mathematical properties of
stability/admissibility/monotone-improvement of the generated policies and convergence towards the optimal solution
were also studied in the literatures above all regarding PI in
CTS.

Independently of the research on PI, several RL methods
have come to be proposed also in CTS. Advantage updating was proposed by Baird III (1993) and then reformulated
by Doya (2000) under the environment represented by an
ODE. Doya (2000) also extended TD(λ) to the CTS domain and then combined it with the two policy improvement methods—the continuous actor with its update rule
and the value-gradient based (VGB) greedy policy improvement; see also (Frémaux et al., 2013) for an extension of
Doya (2000)’s continuous actor-critic using spiking neural
networks. Mehta and Meyn (2009) defined the Hamiltonian
function as a Q-function and then proposed a Q-learning
method in CTS based on stochastic approximation. Unlike
in MDP, however, these RL methods in CTS and the related
action-dependent (AD) functions such as advantage and Qfunctions are barely relevant to the PI methods in CTS due
to the gap between optimal control and RL.
1.2

Contributions and Organizations

The main goal of this paper is to build up a theory on IPI in
a general RL framework when the time and the state-action
space are all continuous and the environment is modelled by
an ODE. As a result, a series of IPI methods are proposed
in the general RL framework with mathematical analysis.
This also provides the theoretical connection of IPI to the
aforementioned RL methods in CTS. The main contributions
of this paper can be summarized as follows.

On the other hand, the aforementioned PI methods in CTS
were all designed via Lyapunov’s stability theory (Haddad
and Chellaboina, 2008) to guarantee that the generated policies are all asymptotically stable and thereby yield finite returns (at least on a bounded region around an equilibrium
state), provided that so is the initial policy. There are two
main restrictions, however, for these stability-based works
to be extended to the general RL framework. One is the fact
that except in the LQR case (e.g., Modares et al., 2016), there
is no (or less if any) direct connection between stability and
discount factor γ in RL. This is why in the nonlinear cases,
the aforementioned PI methods in CTS only consider the to-

(1) Motivated by the work of IPI (Vrabie and Lewis, 2009;
Lee et al., 2015) in the optimal control framework, we
propose the corresponding on-policy IPI scheme in the
general RL framework and then prove its mathematical properties of admissibility/monotone-improvement
1

In RL community, the return or the RL problem (in a discrete
space) is said to be discounted if 0 ≤ γ < 1 and total if γ = 1.
2
For an example of a dynamics with no equilibrium state, see
(Haddad and Chellaboina, 2008, Example 2.2).

2

of the generated policies and the convergence towards
the optimal solution (see Section 3). To establish them,
we rigorously define the general RL problem in CTS
with its environment formed by an ODE and then build
up a theory regarding policy evaluation and improvement (see Section 2).
(2) Extending on-policy IPI in Section 3, we propose four
off-policy IPI methods in CTS—two named integral advantage PI (IAPI) and integral Q-PI (IQPI) are the ideal
PI forms of advantage updating (Baird III, 1993; Doya,
2000) and Q-learning in CTS, and the other two named
integral explorized PI (IEPI) and integral C-PI (ICPI)
are the natural extensions of the existing off-policy IPI
methods (Lee et al., 2015) to our general RL problem.
All of the off-policy methods are proven to generate the
effectively same policies and value functions to those
in on-policy IPI—they all satisfy the above mathematical properties of on-policy IPI. These are all shown in
Section 4 with detailed discussions and comparisons.

2

Preliminaries

The proposed on-policy IPI is basically model-based but
can be made partially model-free by slightly modifying its
policy improvement (see Section 3.2). IEPI is also partially
model-free; IAPI and IQPI are even completely model-free;
so is ICPI, but only applicable under the special u-affineand-concave (u-AC) setting shown in Section 3.3. Here, we
emphasize that Doya (2000)’s VGB greedy policy improvement is also developed under this u-AC setting, and ICPI
provides its model-free version. Finally, to support the theory
and verify the performance, simulation results are provided
in Section 5 for an inverted-pendulum model. As shown in
the simulations and all of the IPI algorithms in this paper,
the initial policy is not required to be asymptotically stable to achieve the learning objective. Conclusions follow in
Section 6. This theoretical work lies between the fields of
optimal control and machine learning and also provides the
unified framework of unconstrained and input-constrained
formulations in both RL and optimal control (e.g., Doya,
2000; Abu-Khalaf and Lewis, 2005; Mehta and Meyn, 2009;
Vrabie and Lewis, 2009; Lee et al., 2015 as the special cases
of our framework).

(1) for each fixed τ ≥ t, µ(τ, ·) is continuous;
(2) for each fixed x ∈ X , µ(·, x) is right continuous;
(3) for each x ∈ X , the state trajectory X· generated under
Uτ = µ(τ, Xτ ) ∀τ ≥ t and the initial condition Xt = x
is uniquely defined over the whole time interval [t, ∞).

.
In this paper, the state space X is given by X = Rn , and the
action space U ⊆ Rm is an m-dimensional manifold in Rm
with (or without) boundary; t ≥ 0 denotes a given specific
time instant. The environment considered in this paper is the
deterministic one in CTS described by the following ODE:
Ẋτ = f (Xτ , Uτ ),

(1)

where τ ∈ [t, ∞) is the time variable; f : X × U → X
is a continuous function; Xτ ∈ X denotes the state vector
at time τ ; the action trajectory U· : [t, ∞) → U is a right
continuous function over [t, ∞).
.
A (non-stationary) policy µ = µ(τ, x) refers to a function
µ : [t, ∞) × X → U such that

It is said to be stationary if there is a function π : X → U
such that µ(τ, x) = π(x) for all (τ, x) ∈ [t, ∞) × X , in
which case we call π a (stationary) policy. In this paper, we
use π to indicate a stationary policy, and µ to denote any
non-stationary behavior policy; the latter will be not shown
until Section 4.
For notational efficiency and consistency to the classical RL
framework, we will use the notation
Eπ [Z|Xt = x] (or its abbreviation Exπ [Z]),
which plays no stochastic role but just means the deterministic value Z when Xt = x and Uτ = π(Xτ ) for all τ ≥ t.
Using this notation, the state vector Xτ at time τ ≥ t generated under the initial condition Xt = x and the policy π is
denoted by Eπ [Xτ |Xt = x] or simply Exπ [Xτ ]. Throughout
the paper, we also denote ∆t > 0 the time difference, and
for simplicity, t0 the next time and (Xt0 , Ut0 ) the next state
.
.
and action at that time, i.e., t0 = t + ∆t, Xt0 = Xt0 , and
0 .
Ut = Ut0 . For any differentiable function v : X → R, its
time derivative v̇ : X × U → R is defined as

Notations and Terminologies. N, Z, and R are the sets of
all natural numbers, integers, and real numbers, respectively;
.
R = R ∪ {−∞, ∞} is the set of all extended real numbers;
.
Z+ = N ∪ {0}, the set of all nonnegative integers; Rn×m
is the set of all n-by-m real matrices; AT and rank (A)
denote the transpose and the rank of a matrix A ∈ Rn×m ,
.
respectively. Rn = Rn×1 is the n-dimensional Euclidean
m
space; span{xj }j=1 is the linear subspace of Rn spanned
by the vectors x1 , · · · , xm ∈ Rn ; kxk denotes the Euclidean
norm of x ∈ Rn . A subset Ω of Rn is said to be compact
if it is closed and bounded; for any Lebesque measurable
subset E of Rn , we denote the Lebesque measure of E by
|E|. A function f : D → Rm on a domain D ⊆ Rn is said
to be C1 if its first-order partial derivatives exist and are all
continuous; ∇f : D → Rm×n denotes the gradient of f ;
Imf ⊆ Rm is the image of f . The restriction of f on a
subset Ω ⊆ D is denoted by f |Ω .

v(Xt0 ) − v(Xt )
.
v̇(Xt , Ut ) = lim
,
∆t→0
∆t
which is explicitly expressed by the chain rule as
v̇(Xt , Ut ) = ∇v(Xt )f (Xt , Ut ),
where Xt ∈ X and Ut ∈ U are free variables.

3

2.1

R̄ : X → [0, ∞) such that Rτ is bounded as

RL Problem in Continuous Time and Space



∀x ∈ X : Eπ |Rτ | Xt = x ≤ ατ −t R̄(x),

The RL problem considered in this paper is to find the best
policy π∗ that maximizes the value function vπ : X → R
.
vπ (x) = Eπ [Gt |Xt = x],

then vπ ∈ Va since for k = − ln1αγ and each x ∈ X ,
|vπ (x)| ≤ k R̄(x) < ∞. 4 For the total case γ = 1,
the condition (4) implies that the immediate reward Rτ
exponentially converges to 0 with the rate α ∈ [0, 1).

(2)

where Gt is the discounted or total return defined as
.
Gt =

Z

(4)

(2) For γ ∈ (0, 1), if the reward R or Rπ is lower-bounded,
or the trajectory Exπ [X· ] is bounded for each x ∈ X ,
then vπ ∈ Va . This is because such boundedness gives
the bound (4) for α = 1 and some constant R̄ > 0. 5 In
this case, we have supx∈X |vπ (x)| ≤ k · R̄ < ∞, so vπ
is also bounded. Especially, when R is lower-bounded,
such property is independent of the policy π—in other
words, vπ is bounded (and thus admissible) for any given
policy π (see the simulation setting in Section 5 for a
practical example of this bounded R case).

∞

γ τ −t Rτ dτ,

t

.
with the immediate reward Rτ = R(Xτ , Uτ ) ∈ R at time τ
.
and the discount factor γ ∈ (0, 1]. The reward R = R(x, u)
here is a continuous upper-bounded function of x ∈ X and
u ∈ U. 3 For any policy π, we also define the π-reward Rπ
.
.
(and Rτπ ) as Rπ (x) = R(x, π(x)) and Rτπ = Rπ (Xτ ). In
this paper, an admissible policy π is defined as follows.

Consider the Hamiltonian function h : X × U × R1×n → R

Definition 1 A policy π (or its value function vπ ) is said to
be admissible, denoted by vπ ∈ Va , if

.
h(x, u, p) = R(x, u) + p f (x, u),

(5)

|vπ (x)| < ∞ for all x ∈ X ,
by which the time derivative of any differentiable function
v : X → R can be represented as

. 
where Va = vπ : π is admissible}, the set of all admissible
value functions vπ .

v̇(x, u) = h(x, u, ∇v(x)) − R(x, u),
To make our RL problem feasible, this paper assumes that
every vπ ∈ Va is C1 and that there is an optimal admissible
policy π∗ such that vπ  v∗ holds for any policy π. Here,
v∗ is the optimal value function; the partial ordering v  w
for any two functions v, w : X → R means v(x) ≤ w(x)
for all x ∈ X . There may exist another optimal policy π∗0
than π∗ , but the optimal value function is always same by
vπ∗0  vπ∗ and vπ∗  vπ∗0 . In this paper, π∗ indicates any one
of the optimal policies, and v∗ denotes the unique optimal
value function for them. Also note that in the discounted
case γ ∈ (0, 1), v∗ is upper-bounded since so is R. Hence,
for the consistency to the discounted case, we assume only
for the total case γ = 1 that v∗ is upper-bounded and
∀admissible π : lim sup lπ (x, k; v∗ ) ≤ 0,

(6)

for all (x, u) ∈ X × U. Substituting u = π(x) for any
policy π into (6), we also have the following expression:
Exπ [Rt + v̇(Xt , Ut )] = h(x, π(x), ∇v(x)) ∀x ∈ X , (7)
which converts a time-domain expression (the left-hand side)
into the Hamiltonian formula expressed in the state-space
(the right-hand side). In addition, essentially required in our
theory is the following lemma, which also provides conversions of (in)equalities between time domain and state space.
Lemma 1 Let v : X → R be any differentiable function.
Then, for any policy π,

(3)

k→∞

Z
v(x) ≤ Eπ

.
where lπ (x, k; v) = γ k∆t Eπ [v(Xt+k∆t )|Xt = x]. Here, (3)
is also true in the discounted case since limk→∞ γ k∆t = 0
and v∗ is upper-bounded.

t0

γ τ −t Rτ dτ + γ ∆t v(Xt0 ) Xt = x


(8)

t

for all x ∈ X and all ∆t > 0 iif
− ln γ · v(x) ≤ h(x, π(x), ∇v(x)) ∀x ∈ X .

Remark 1 Admissibility of π strongly depends not only on
the policy π itself, but on the choice of R and γ in vπ and the
properties (e.g., boundedness and stability) of the system (1)
and the state trajectory X· under π as examplified below.

(9)

Moreover, the equalities in (8) and (9) are also necessary
and sufficient. That is, the equality in (8) holds ∀x ∈ X and
∀∆t > 0 iif the equality in (9) is true ∀x ∈ X .

(1) For γ ∈ (0, 1], if there exist α ∈ [0, γ −1 ) and a function
4

An example is the LQR case shown in Section 3.3.
R is already upper-bounded, so it is bounded iif lower-bounded;
by continuity of R and π, R(X· , π(X· )) is bounded if so is X· .

3

5

By the upper-boundedness of R, we only obviate the situation
when the reward Rτ → ∞ as kXτ k → ∞ and/or kUτ k → ∞.

4

For an admissible policy π, rearranging (10) as

Proof. By the standard calculus,


Z t0
1 − γ ∆t
1
· vπ (x) =Eπ
γ τ −t Rτ dτ
∆t
∆t t

0
∆t vπ (Xt ) − vπ (Xt )
+γ ·
Xt = x ,
∆t



d τ −t
γ v(Xτ ) = γ τ −t ln γ · v(Xτ ) + v̇(Xτ , Uτ )
dτ
for any x ∈ X and any τ ≥ t. Hence, by (6) and (9), we
have for any τ ≥ t that

limiting ∆t → 0, and using (7) yield the infinitesimal form:

h

i
0 ≤ Exπ γ τ −t · h(Xτ , π(Xτ ), ∇v(Xτ )) + ln γ · v(Xτ )
h

i
= Exπ γ τ −t · Rτ + v̇(Xτ , Uτ ) + ln γ · v(Xτ )



d  τ −t
γ v(Xτ ) Xt = x ∀x ∈ X ,
= Eπ γ τ −t Rτ +
dτ

− ln γ · vπ (x) = hπ (x, π(x))
= h(x, π(x), ∇vπ (x)) ∀x ∈ X ,

where hπ : X × U → R is the Hamiltonian function for a
given admissible policy π and is defined, with a slight abuse
of notation, as

and, for any x ∈ X and any ∆t > 0, integrating it from t
to t0 (= t + ∆t) yields (8). One can also show that the
equality in (9) for all x ∈ X implies the equality in (8) for
all x ∈ X and ∆t > 0 by following the same procedure.
Finally, the proof of the opposite direction can be easily done
by following the similar procedure to the derivation of (11)
from (10) below. 2
2.2

.
hπ (x, u) = h(x, u, ∇vπ (x)),

By time-invariance property 6 of a stationary policy π and

The application of Lemma 1 shows that finding vπ satisfying
(10) and (11) are both equivalent. In the following theorem,
we state that the boundary condition (15), the counterpart of
that in Corollary 1 is actually necessary and sufficient for a
solution v of the Bellman equation (13) or (14) to be equal
to the corresponding value function vπ .

t0

Z

γ τ −t Rτ dτ + γ ∆t Gt0 ,

t

we can see that vπ ∈ Va satisfies the Bellman equation:
Z

t0

vπ (x) = Eπ

γ

τ −t

Rτ dτ + γ

∆t

vπ (Xt0 )

Theorem 1 Let π be admissible and v : X → R be a
function such that either of the followings holds ∀x ∈ X :


Xt = x

t

(1) v satisfies the Bellman equation for some ∆t > 0:

(10)
for any x ∈ X and any ∆t > 0. Using (10), we obtain the
boundary condition of vπ ∈ Va at τ = ∞.

Z
v(x) = Eπ

(13)
− ln γ · v(x) = h(x, π(x), ∇v(x)).

vπ (x) = lim

∆t→∞

t+∆t

γ

τ −t

Rτ dτ + γ

∆t


γ τ −t Rτ dτ + γ ∆t v(Xt0 ) Xt = x ;

(2) v is differentiable and satisfies

Proof. Taking the limit ∆t → ∞ of (10) yields
Z

t0

t

Proposition 1 Suppose that π is admissible. Then, ∀x ∈ X ,
limτ →∞ γ τ −t · Exπ [vπ (Xt+τ )] = 0.

Exπ

(12)

which is obviously continuous since so are the functions f ,
R, and ∇vπ (see also (5)). Both hπ (x, u) and h(x, u, vπ (x))
will be used interchangeably in this paper for convenience to
indicate the same Hamiltonian function for π; the Hamiltonian function for the optimal policy π∗ will be also denoted
by h∗ (x, u), or equivalently, h∗ (x, u, ∇v∗ (x)).

Bellman Equation with Boundary Condition

Gt =

(11)

(14)

Then, limk→∞ lπ (x, k; v) = v(x) − vπ (x) for each x ∈ X .
Moreover, v = vπ over X if (and only if)



vπ (Xt0 )

t

∀x ∈ X :

= vπ (x) + lim γ ∆t · Exπ [vπ (Xt0 )],

lim lπ (x, k; v) = 0.

k→∞

(15)

∆t→∞

Proof. Since π is admissible, Eπ [vπ (Xτ )|Xt = x] is finite
.
for all τ ≥ t and x ∈ X . First, let ṽ(x) = v(x) − vπ (x) and
suppose v satisfies (13). Then, subtracting (10) from (13)
yields ṽ(x) = γ ∆t ·Exπ [ṽ(Xt0 )], whose repetitive applications
to itself results in


ṽ(x) = γ ∆t Exπ [ṽ(Xt+∆t )] = · · · = γ k∆t Exπ ṽ(Xt+k∆t ) .

which implies limτ →∞ γ τ −t · Exπ [vπ (Xt+τ )] = 0. 2
Corollary 1 Suppose that π is admissible. Then, for any
x ∈ X and any ∆t > 0, limk→∞ lπ (x, k; vπ ) = 0.
6

vπ (x) = Eπ [Gt1 |Xt1 = x] = Eπ [Gt2 |Xt2 = x] ∀t1 , t2 ≥ 0.

5

Therefore, by limiting k → ∞ and using Corollary 1, we
obtain limk→∞ lπ (x, k; v) = ṽ(x), which also proves ṽ = 0
under (15). The proof of the other case for v satisfying (14)
instead of (13) is direct by Lemma 1. Conversely, if v = vπ
over X , then (15) is obviously true by Corollary 1. 2

Theorem 2 (Policy Improvement Theorem) Suppose π is
admissible and Assumption 1 holds. Then, the policy π 0 given
by (18) is also admissible and satisfies vπ  vπ0  v∗ .

Proof. Since π is admissible, (18) in Assumption 1 and (11)
imply that for any x ∈ X ,

Remark 2 (15) is always true for any γ ∈ (0, 1) and any
bounded v. Hence, whenever vπ is bounded and 0 < γ < 1,
e.g., the second case in Remark 1 including the simulation
example in Section 5, any bounded function v satisfying the
Bellman equation (13) or (14) is equal to vπ by Theorem 1.
2.3

hπ (x, π 0 (x)) ≥ hπ (x, π(x)) = − ln γ · vπ (x).
By Lemma 1, it is equivalent to

Optimality Principle and Policy Improvement

vπ (x) ≤

Exπ0

Z

t0

γ

τ −t

Rτ dτ + γ

∆t


,

vπ (Xt0 )

t

Note that the optimal value function v∗ ∈ Va satisfies

and by the repetitive applications itself,

v∗ (x) = max vπ (x)
π

vπ (x) ≤ Exπ0

v∗ (x) = max Exπ

Z

π

t

0

vπ (x) ≤ vπ0 (x) + lim sup lπ0 (x, k; vπ )

t

(16)
for all x ∈ X , where maxπ denotes the maximization among
the all stationary policies. Hence, by the similar procedure
to derive (11) from (10), we obtain from (16)

k→∞

≤ vπ0 (x) + lim sup γ k∆t · Exπ0 [v∗ (Xt+k∆t )] (19)
k→∞

≤ vπ0 (x) + max{0, V∗ },

− ln γ · v∗ (x) = max h∗ (x, π(x), ∇v∗ (x)) ∀x ∈ X .

from which and vπ ∈ Va , we can conclude that vπ0 (x) for
each x ∈ X has a lower bound; since it also has an upper
bound as vπ0 (x) ≤ v∗ (x) ≤ V∗ , π 0 is admissible. Finally,
(3) with the admissible policy π 0 and (19) imply that for
each x ∈ X ,

π

Here, the above maximization formula can be characterized
as the following HJBE:
u∈U


γ τ −t Rτ dτ + γ k∆t vπ (Xt+k∆t ) .

Let V∗ ∈ R be an upper bound of v∗ . Then, in the limit
k → ∞, we obtain for each x ∈ X


τ −t
∆t
0
γ
Rτ dτ + γ v∗ (Xt )

− ln γ · v∗ (x) = max h(x, u, ∇v∗ (x)), ∀x ∈ X ,

t+k∆t

t

and hence, by principle of optimality, the following Bellman
optimality equation:


Z

(17)

vπ (x) ≤ vπ0 (x) + lim sup lπ0 (x, k; v∗ ) ≤ vπ0 (x) ≤ v∗ (x),
k→∞

and the optimal policy π∗ as

which completes the proof. 2

π∗ (x) ∈ arg max h∗ (x, u), ∀x ∈ X

Corollary 2 Under Assumption 1, v∗ satisfies the HJBE (17).

u∈U

under the following assumption. 7
Proof. Under Assumption 1, let π∗0 be a policy such that
π∗0 (x) ∈ arg maxu∈U h∗ (x, u). Then, π∗0 is admissible and
v∗  vπ∗0 holds by Theorem 2; trivially, vπ∗0  v∗ . Hence, π∗0
is an optimal policy. Noting that any admissible π satisfies
(11), we obtain from “(11) with π = π∗0 and vπ = v∗ :”

Assumption 1 For any admissible policy π, there exists a
policy π 0 such that for all x ∈ X ,
π 0 (x) ∈ arg max hπ (x, u).

(18)

u∈U

− ln γ·v∗ (x) = h(x, π∗0 (x), ∇v∗ (x)) = max h(x, u, ∇v∗ (x))

The following theorems support the argument.

u∈U

for all x ∈ X , which is exactly the HJBE (17). 2

7

If U is compact, then by continuity of hπ , arg maxu∈U hπ (x, u)
in (18) is non-empty for any admissible π and any x ∈ X . This
guarantees the existence of a function π 0 satisfying (18). For the
other cases, where the action space U is required to be convex,
see Section 3.3 (specifically, (30) and (34)).

For the uniqueness of the solution v∗ to the HJBE, we further
assume throughout the paper that

6

Assumption 2 There is one and only one element w∗ ∈ Va
over Va that satisfies the HJBE:

Algorithm 1a describes the whole procedure of on-policy
IPI—it starts with an initial admissible policy π0 (line 1)
and performs policy evaluation and improvement until vi
and/or πi converge (lines 4–7). In policy evaluation (line 4),
the agent solves the Bellman equation (21) to find the value
function vi = vπi for the current policy πi . Then, in policy
improvement (line 5), the next policy πi+1 is obtained by
maximizing the associated Hamiltonian function.

− ln γ · w∗ (x) = max h(x, u, ∇w∗ (x)), ∀x ∈ X .
u∈U

Corollary 3 Under Assumptions 1 and 2, v∗ = w∗ . That is,
v∗ is the unique solution to the HJBE (17) over Va .
Remark 3 The policy improvement equation (18) in Assumption 1 can be generalized and rewritten as


π 0 (x) ∈ arg max κ · hπ (x, u) + bπ (x)
(20)

3.1

As stated in Theorem 3 below, on-policy IPI guarantees the
admissibility and monotone improvement of πi and the perfect value function estimation vi = vπi at each i-th iteration
under Assumption 1 and the boundary condition:

u∈U

for any constant κ > 0 and any function bπ : X → R. 8
Obviously, (18) is the special case of (20) with κ = 1 and
bπ (x) = 0; policy improvement of our IPI methods in this
paper can be also considered to be equal to “(20) with
a special choice of κ and bπ ” (as long as the associated
functions are perfectly estimated in their policy evaluation).
3

Assumption 3a For each i ∈ Z+ , if πi is admissible, then
lim lπi (x, k; vi ) = 0 for any x ∈ X .

k→∞

∞
Theorem 3 Let {πi }∞
i=0 and {vi }i=0 be the sequences generated by Algorithm 1a under Assumptions 1 and 3a. Then,

On-policy Integral Policy Iteration (IPI)

(P1) ∀i ∈ Z+ : vi = vπi ;
(P2) ∀i ∈ Z+ : πi+1 is admissible and satisfies

Now, we are ready to state our basic primary PI scheme,
which is named on-policy integral policy iteration (IPI) and
estimate the value function vπ only (in policy evaluation)
based on the on-policy state trajectory X· generated under π
during some finite time interval [t, t0 ]. The value function
estimate obtained in policy evaluation is then utilized in
the maximization process (policy improvement) yielding the
next improved policy.

1
2
3
4

πi+1 (x) ∈ arg max hπi (x, u);
(P3) the policy is monotonically improved, i.e.,
vπ0  vπ1  · · ·  vπi  vπi+1  · · ·  v∗ .

Proof. π0 is admissible by the first line of Algorithm 1a.
For any i ∈ Z+ , suppose πi is admissible. Then, since vi
satisfies Assumption 3a, vi = vπi by Theorem 1. Moreover,
Theorem 2 under Assumption 1 shows that πi+1 is admissible and satisfies vπi  vπi+1  v∗ . Furthermore, (23) holds
by (12), (22), and vi = vπi . Finally, the proof is completed
by mathematical induction. 2
From Theorem 3, one can directly see that for any x ∈ X ,
the real sequence {vi (x) ∈ R}∞
i=0 satisfies

t

v0 (x) ≤ · · · ≤ vi (x) ≤ vi+1 (x) ≤ · · · ≤ v∗ (x) < ∞,
(24)
implying pointwise convergence to some function v̂∗ . Since
vi (= vπi ) is continuous by the C1 -assumption on every
vπ ∈ Va (see Section 2.1), the convergence is uniform on any
compact subset of X by Dini’s theorem (Thomson, Bruckner, and Bruckner, 2001) provided that v̂∗ is continuous. This
is summarized and sophisticated in the following theorem.

Policy Improvement: find a policy πi+1 such that
πi+1 (x) ∈ arg max h(x, u, ∇vi (x)) ∀x ∈ X ; (22)
u∈U

6

(23)

u∈U

Algorithm 1a: On-policy IPI for the General Case (1)–(2)
(
π0 : X → U, the initial admissible policy;
Initialize:
∆t > 0, the time difference;
i ← 0;
repeat
Policy Evaluation: given policy πi , find the solution
vi : X → R to the Bellman equation: for any x ∈ X ,
 Z t0

x
τ −t
∆t
0
vi (x) = Eπi
γ
Rτ dτ + γ vi (Xt ) ; (21)

5

Admissibility, Monotone Improvement, & Convergence

i ← i + 1;
until convergence is met.

Theorem 4 Under the same conditions to Theorem 3, there
is a Lebesque measurable, lower semicontinuous function v̂∗
.
defined as v̂∗ (x) = supi∈Z+ vi (x) such that

8

This is obviously true since the modification term “bπ (x)” does
not depend on u ∈ U and thus not contribute to the maximization.

7

(C2) if v̂∗ ∈ Va and for every compact subset Ω ⊂ X , T is
continuous under dΩ , then vi → v∗ pointwisely on X
and uniformly on any compact subset of X .

(1) vi → v̂∗ pointwisely on X ;
(2) for any ε > 0 and any compact set Ω of X , there exists
its compact subset E ⊆ Ω ⊂ X such that Ω \ E < ε,
v̂∗ |E is continuous, and vi → v̂∗ uniformly on E.

Proof. By Lemma 2 and Bessaga (1959)’s converse of the
Banach’s fixed point principle, there exists a metric d on
Va such that (Va , d) is a complete metric space and T is
a contraction (and thus continuous) under d. Moreover, by
Lemma 2 and Banach’s fixed point principle (e.g., Kirk and
Sims, 2013, Theorem 2.2),

Moreover, if v̂∗ is continuous over X , then the convergence
vi → v̂∗ is uniform on any compact subset of X .
Proof. By (24), the sequence {vi (x) ∈ R}∞
i=0 for any fixed
x ∈ X is monotonically increasing and upper bounded by
v∗ (x) < ∞. Hence, vi (x) converges to v̂∗ (x) by monotone
convergence theorem (Thomson et al., 2001), the pointwise
convergence vi → v̂∗ . Since vi is continuous, v̂∗ is Lebesque
measurable and lower semicontinuous by its construction
(Folland, 1999, Propositions 2.7 and 7.11c). Next, by Lusin’s
theorem (Loeb and Talvila, 2004), for any ε > 0 and any
compact set Ω ⊂ X , there exists a compact subset E ⊆ Ω
such that |Ω \ E| < ε and the restriction v̂∗ |E is continuous.
Hence, the monotone sequence vi converges to v̂∗ uniformly
on E (and on any compact subset of X if v̂∗ is continuous
over X ) by Dini’s theorem (Thomson et al., 2001). 2

∀v0 ∈ Va : lim vN = lim T N v0 = v∗ in the metric d.
N →∞

N →∞

To prove the second part, suppose that v̂∗ ∈ Va and that T is
continuous under dΩ for every compact subset Ω ⊂ X . Then,
since v̂∗ ∈ Va is C1 by assumption and thereby, continuous,
vi converges to v̂∗ pointwisely on X and uniformly on every
compact Ω ⊂ X by Theorem 4; the latter implies vi → v̂∗
in dΩ . Therefore, in the uniform pseudometric dΩ ,
v̂∗ = lim vi+1 = lim T vi = T
i→∞

Next, we prove the convergence vi → v∗ to the optimal
solution v∗ using the PI operator T : Va → Va defined on
the space Va of admissible value functions as

i→∞




lim vi = T v̂∗

i→∞

by continuity of T under dΩ . That is, v̂∗ |Ω = (T v̂∗ )|Ω for
every compact Ω ⊂ X . This implies v̂∗ = T v̂∗ and thus,
v̂∗ = v∗ by Lemma 2, which completes the proof. 2

.
T vπ = vπ0

3.2

Partially Model-Free Nature

0

under Assumption 1, where π is the next admissible policy
that satisfies (18) and is obtained by policy improvement
with respect to the given value function vπ ∈ Va . Let its
.
N -th recursion T N be defined as T N vπ = T N −1 [T vπ ] and
.
0
T vπ = vπ . Then, any sequence {vi ∈ Va }∞
i=0 generated
by Algorithm 1a under Assumptions 1 and 3a satisfies

Policy evaluation (21) can be done without using the explicit
knowledge of the system dynamics f (x, u) in (1)—there is
no explicit term of f shown in (21), and all of the necessary information on f are captured by the observable state
trajectory X· during a finite time interval [t, t0 ]. Hence, IPI
is model-free as long as so is its policy improvement (22),
which is not unfortunately (see the definition (5) of h). Nevertheless, the policy improvement (22) can be modified to
yield the partially model-free IPI. To see this, consider the
decomposition (25) of the dynamics f below:

T N v0 = vN for any N ∈ N.
Lemma 2 Under Assumptions 1 and 2, the optimal value
function v∗ is the unique fixed point of T N for all N ∈ N.

f (x, u) = fd (x) + fc (x, u),

Proof. See Appendix A. 2

(25)

where fd : X → X is independent of u and called a drift
dynamics, and fc : X × U → X is the corresponding inputcoupling dynamics. 9 Substituting the definitions (5) and
(12) into (20), choosing κ = 1 and b(x) = −∇vπ (x)fd (x),
and replacing (π, vπ ) with (πi , vi ) then yield

To precisely state our convergence theorem, let Ω be any
given compact subset and define the uniform pseudometric
dΩ : Va × Va → [0, ∞) on Va as
.
dΩ (v, w) = sup v(x) − w(x) for v, w ∈ Va .



πi+1 (x) ∈ arg max R(x, u) + ∇vi (x)fc (x, u) ,

x∈Ω

(26)

u∈U

Theorem 5 For the value function sequence {vi }∞
i=0 generated by Algorithm 1a under Assumptions 1, 2, and 3a,

a partially model-free version of (22). In summary, the whole
procedure of Algorithm 1a can be done even when the drift
dynamics fd is completely unknown.

(C1) there exists a metric d : Va × Va → [0, ∞) such that
T is a contraction (and thus continuous) under d and
vi → v∗ in the metric d, i.e., limi→∞ d(vi , v∗ ) = 0;

9

There are an infinite number of ways of choosing fd and fc ; one
typical choice is fd (x) = f (x, 0) and fc (x, u) = f (x, u) − fd (x).

8

3.3

(1) s is strictly monotone, odd, and bijective;
(2) S in (31) is finite at any point on the boundary ∂U. 11

Case Studies

The partially model-free policy improvement (26) can be
even more simplified if:

This gives the closed-form expression σ(ξ) = s(Γ−1 ξ) of
the function σ in (30) and includes the sigmoidal example in
Section 5 as its special case. 12 Another well-known example
is:

(1) the system dynamics f (x, u) is affine in u, i.e.,
f (x, u) = fd (x) + Fc (x)u,

U = Rm (i.e., Umax,j = ∞, 1 ≤ j ≤ m) and s(u) = u/2,
(32)
in which case (31) becomes S(u) = uT Γu.

(27)

where Fc : X → Rn×m is a continuous matrix-valued
function; it is (25) with fc (x, u) = Fc (x)u;
(2) the action space U ⊆ Rm is convex;
(28)
(3) the reward R(x, u) is strictly concave in u and given
by
R(x, u) = R0 (x) − S(u),
(29)
where R0 : X → R is a continuous upper-bounded
function called the state reward, and S : U → R,
named the action penalty, is a strictly convex C1 function whose restriction S|Uint on the interior Uint of U
m
satisfies Im(∇S|T
Uint ) = R .

The well-known special case of (27)–(29) is the following
linear quadratic regulation (LQR): (31), (32) and
fd (x) = Ax, Fc (x) = B, R0 (x) = −kCxk2 ,

where (A, B, C) for A ∈ Rn×n , B ∈ Rn×m , and C ∈ Rp×n
is stabilizable and detectable. In this LQR case, if the policy
πi is linear, i.e., πi (x) = Ki x (Ki ∈ Rm×n ), then its value
function vπi , if finite, can be represented in a quadratic form
vπi (x) = xT Pπi x (Pπi ∈ Rn×n ). Moreover, when vi is
quadratically represented as vi (x) = xT Pi x, (30) becomes

In this case, solving the maximization in (26) (or (22)) is
equivalent to finding the regular point u ∈ U such that

πi+1 (x) = Ki+1 x and Ki+1 = Γ−1 B T Pi ,

−∇S(u) + ∇vi (x)Fc (x) = 0,

Żτ = A +

Z


I Zτ + BUτ

(35)


R(Zτ , Uτ ) dτ Zt = x ,

t

11
12

1
2
3

(31)

4

for a positive definite matrix Γ ∈ Rm×m and a continuous
function s : Rm → Uint such that

5

v→u

∞

vπ (x) = Ẽπ

v

(sT )−1 (w) · Γ dw

ln γ
2

yields the following value function expression in terms of
Zτ without the discount factor γ as

Remark 4 Whenever each j-th component Uτ,j of Uτ meets
some physical limitation |Uτ,j | ≤ Umax,j for some threshold
Umax,j ∈ (0, ∞],
 one can formulate the action space U in
(28) as U = Uτ ∈ Rm : |Uτ,j | ≤ Umax,j , 1 ≤ j ≤ m
and determine the action penalty S(u) in (29) as
S(u) = lim

(34)

a linear policy again. This observation gives the policy evaluation and improvement in Algorithm 1b below. Moreover,
whenever the given policy π is linear and (31)–(33) are all
true, the process Zτ generated by

where the gradient ∇S of S is a strictly monotone mapping
that is also bijective when its domain U is restricted to its
interior Uint . Rearranging it with respect to u, we obtain the
explicit closed-form expression of (26) also known as the
VGB greedy policy (Doya, 2000):


πi+1 (x) = σ FcT (x)∇viT (x) ,
(30)
.
−1
where σ : Rm → Uint is defined as σ = (∇S|T
, which
Uint )
is also strictly monotone, bijective, and continuous. Therefore, in the u-affine-and-concave (u-AC) case (27)–(29), 10
the complicated maximization process in (26) over the continuous action space can be obviated by directly calculating
the next policy πi+1 by (30). Also note that under the u-AC
setting (27)–(29), the VGB greedy policy π 0 = σ◦ FcT ∇vπT
for an admissible π is the unique policy satisfying (18).

Z

(33)

0

6
10

This includes the frameworks in (Doya, 2000; Abu-Khalaf and
Lewis, 2005; Vrabie and Lewis, 2009) as special cases.

9

∂U = {Uτ ∈ Rm : Uτ,j = Umax,j , 1 ≤ j ≤ m}.
See also (Doya, 2000; Abu-Khalaf and Lewis, 2005).

Algorithm 1b: On-policy IPI for the LQR Case (31)–(33)
(
π0 (x) = K0 x, the init. admissible policy;
Initialize:
∆t > 0, the time difference;
i ← 0;
repeat (under the LQR setting (31), (32), and (33))
Policy Evaluation: given policy πi (x) = Ki x, find the
solution vi (x) = xT Pi x to the Bellman equation (21);
Policy Improvement: Ki+1 = Γ−1 B T Pi ;
i ← i + 1;
until convergence is met.

(1) µ(t, x, u) = u for all x ∈ X and all u ∈ U0 ;
(2) for each fixed u ∈ U0 , µ(·, ·, u) is a policy (starting at
time t), which is possibly non-stationary.

where Ẽπ [Y |Zt = x] denotes the value of Y when Zt = x
and Uτ = π(Zτ ) ∀τ ≥ t. This transforms any discounted
LQR problem into the total one (with its state Zτ in place
of Xτ ). Hence, the application of the standard LQR theory
(Anderson and Moore, 1989) shows that

An AD policy is actually a policy parameterized by u ∈ U0 ;
the purpose of such a parameterization is to impose the condition Ut = u at the initial time t through the first property
in Definition 2 so as to make it possible to explore the stateaction space X × U (or its subset X × U0 ), rather than the
state space X alone. The simplest form of an AD policy µ is

v∗ (x) = xT P∗ x ≤ 0 for some P∗ ∈ Rn×n ,
.
π∗ (x) = K∗ x with K∗ = Γ−1 B T P∗ ;
(2) v∗ is the unique solution to the HJBE (17).


(1)

Furthermore, the application of the analytical result of IPI
(Lee et al., 2014, Theorem 5 and Remark 4 with } → ∞)
gives the following statements.

µ(τ, x, u) = u for all τ ≥ t and all (x, u) ∈ X × U0
used in Section 5; another useful important example is

Lemma 3 (Policy Improvement Theorem: the LQR Case)
Let π be linear and admissible. Then, the linear policy π 0
given by π 0 (x) = K 0 x and K 0 = Γ−1 B T Pπ under the LQR
setting (31)–(33) is admissible and satisfies Pπ ≤ Pπ0 ≤ 0.
∞
Theorem 6 Let {πi }∞
i=0 and {vi }i=0 be the sequences generated by Algorithm 1b and parameterized as πi (x) = Ki x
and vi (x) = xT Pi x. Then,

(1)
(2)
(3)
(4)

µ(τ, x, u) = π(x) + e(τ, x, u) (with U = Rm ),
for a policy π and a probing signal e(τ, x, u) given by
e(τ, x, u) = (u − π(x))e−σ(τ −t) +


Aj sin ωj (τ − t) ,

j=1

where σ > 0 regulates the vanishing rate of the first term;
Aj ∈ Rm and ωj ∈ R are the amplitude and the angular
frequency of the j-th sin term in the summation, respectively.

πi is admissible and Pi = Pπi for all i ∈ Z+ ;
P0 ≤ P1 ≤ · · · ≤ Pi ≤ Pi+1 ≤ · · · ≤ P∗ ≤ 0;
limi→∞ Pi = P∗ and limi→∞ Ki = K∗ ;
the convergence Pi → P∗ is quadratic.

In what follows, for an AD policy µ starting at time t ≥ 0,
we will interchangeably use

Remark 5 In the LQR case, Assumptions 1, 2, and 3a are
all true—Assumptions 1 and 2 are trivially satisfied as shown
above; Assumption 3a is also true by

Eµ [Z|Xt = x, Ut = u]

and

E(µx,u) [Z|t],

(36)

with a slight abuse of notations, to indicate the deterministic
value Z when Xt = x and Uτ = µ(τ, Xτ , u) for all τ ≥ t.
Using this notation, the state vector Xτ at time τ ≥ t that
starts at time t and is generated under µ and the initial
condition “Xt = x and Ut = u” is denoted by E(µx,u) [Xτ |t].
For any non-AD policy µ, we also denote Eµ [Z|Xt = x]
and Exµ [Z|t], instead of (36), to indicate the value Z when
Xt = x and Uτ = µ(τ, Xτ ) ∀τ ≥ t, where the condition
Ut = u is obviated.



T
lim lπi (x, k; vi ) = lim Exπi γ k∆t · Xt+k∆t
Pi Xt+k∆t
k→∞
k→∞
 T

= lim Ẽxπi Zt+k∆t
Pi Zt+k∆t = 0,
k→∞

where we have used the equality Ẽxπ [Zτ ] = Exπ [(γ/2)τ −t Xτ ]
and the fact that a linear policy π is admissible iif it stabilizes
the Zτ -system (35) and thus satisfies limτ →∞ Ẽxπ [Zτ ] = 0
∀x ∈ X (Lee et al., 2014, Section 2). To the best authors’
knowledge, however, the corresponding theory does not exist for the nonlinear discounted case ‘γ ∈ (0, 1).’ See (AbuKhalaf and Lewis, 2005; Vrabie and Lewis, 2009; Lee et al.,
2015) for the u-AC case (27)–(29) with γ = 1 and R ≤ 0.
4

N
X

Each off-policy IPI method in this paper is designed to generate the policies and value functions satisfying the same
properties in Theorems 3 and 4 as those in on-policy IPI (Algorithm 1a), but they are generated using the off-policy trajectories generated by a (AD) behavior policy µ, rather than
the target policy πi . Specifically, each off-policy method estimates vi and/or a (AD) function in policy evaluation using the off-policy state and action trajectories and then employs the estimated function in policy improvement to find
a next improved policy. Each off-policy IPI method will be
described only with its policy evaluation and improvement
steps since the others are all same to those in Algorithm 1a.

Extensions to Off-policy IPI Methods

In this section, we propose a series of completely/partially
model-free off-policy IPI methods, which are effectively
same to on-policy IPI but uses data generated by a behavior
policy µ, rather than the target policy πi . For this, we first
introduce the concept of action-dependent (AD) policy.

4.1

Definition 2 For a non-empty subset U0 ⊆ U of the action
space U, a function µ : [t, ∞) × X × U0 → U, denoted by
µ(τ, x, u) for τ ≥ t and (x, u) ∈ X × U0 , is said to be an
AD policy over U0 (starting at time t) if:

Integral Advantage Policy Iteration (IAPI)

First, we consider a continuous function aπ : X × U → R
called the advantage function for an admissible policy π

10

(Baird III, 1993; Doya, 2000), which is defined as
.
aπ (x, u) = hπ (x, u) + ln γ · vπ (x)

Algorithm 3a: Integral Q-Policy-Iteration (IQPI)


the current policy πi

Policy Evaluation: given an weighting factor β > 0 ,
an AD policy µ over U 

(37)

and satisfies aπ (x, π(x)) = 0 by (11). Considering (20) in
Remark 3 with bπ (x) = ln γ · vπ (x) and κ = 1, we can see
that the maximization process (18) can be replaced by
π 0 (x) ∈ arg max aπ (x, u) ∀x ∈ X ;

find a continuous function qi : X × U → R such that
for all (x, u) ∈ X × U:
qi (x, πi (x)) = E(x,u)
µ

(38)

u∈U

(42)


where

Zτ = κ1 Rτ − κ2 qi (Xτ , Uτ ) + κ3 qi (Xτ , πi (Xτ )),
.
κ1 κ2 > 0 and κ3 = κ2 − ln(γ −1 β);

Policy Improvement: find a policy πi+1 such that

max a∗ (x, u) = 0 and π∗ (x) ∈ arg max a∗ (x, u).
u∈U

πi+1 (x) ∈ arg max qi (x, u) ∀x ∈ X ;

(43)

u∈U

These ideas give model-free off-policy IPI named integral
advantage policy iteration (IAPI), whose policy evaluation
and improvement steps are shown in Algorithm 2 while the
other parts are, as mentioned above, all same to those in
Algorithm 1a and thus omitted. Given πi , the agent tries to
find/estimate in policy evaluation both vi (x) and ai (x, u)
satisfying (40) and the off-policy Bellman equation (39) for
“an AD policy µ over the entire action space U.” Here, vi and
ai corresponds to the value and the advantage functions with
respect to the i-th admissible policy πi (see Theorem 7 in
Section 4.5). Then, the next policy πi+1 is updated in policy
improvement by using the advantage function ai (x, u) only.
Notice that this IAPI provides the ideal PI form of advantage
updating and the associated ideal Bellman equation—see
(Baird III, 1993) for advantage updating and the approximate
version of the Bellman equation (39).

X × U → R defined as

.
qπ (x, u) = κ1 · vπ (x) + aπ (x, u)/κ2

(44)

for an admissible policy π, where κ1 , κ2 ∈ R are any
two nonzero real numbers that have the same sign, so that
κ1 /κ2 > 0 holds. 13 By its definition and continuities of vπ
and aπ , the Q-function qπ is also continuous over its whole
domain X × U. Here, since both κ1 and κ2 are nonzero, the
Q-function (44) does not lose both information on vπ and aπ ;
thereby, qπ plays a similar role of the DT Q-function—on
one hand, it holds the property
κ1 · vπ (x) = qπ (x, π(x)),

Algorithm 2: Integral Advantage Policy Iteration (IAPI)

(45)

and on the other, it replaces (18) and (38) with

Policy Evaluation: given πi and an AD policy µ over U,
 1

a C function vi : X → R
find
such that
a continuous function ai : X × U → R

π 0 (x) ∈ arg max qπ (x, u) ∀x ∈ X

(46)

u∈U

by (20) for κ = κκ21 > 0 and bπ (x) = κ1 (1+ lnκ2γ )·vπ (x); the
HJBE (17) and the optimal policy π∗ are also characterized
.
by the optimal Q-function q∗ = qπ∗ as

(1) for all (x, u) ∈ X × U,
 Z t0

(x,u)
τ −t
∆t
0
vi (x) = Eµ
γ
Zτ dτ + γ vi (Xt ) t , (39)

κ1 · v∗ (x) = max q∗ (x, u) and π∗ (x) ∈ arg max q∗ (x, u).

t

u∈U

where Zτ = Rτ − ai (Xτ , Uτ ) + ai (Xτ , πi (Xτ ));
(2) ai (x, πi (x)) = 0 for all x ∈ X ;

πi+1 (x) ∈ arg max ai (x, u) ∀x ∈ X ;

u∈U

Algorithm 3a shows the policy evaluation and improvement
of IQPI—the former is derived by substituting
(45) and

κ1 aπ (x, u) = κ2 · qπ (x, u) − qπ (x, π(x)) (obtained from
(44) and (45)) into (39) in IAPI, and the latter directly from
(46). At each iteration, while IAPI needs to find/estimate
both vi and ai , IQPI just estimate and use in its loop qi only.
In addition, the constraint on the AD function such as (40)

(40)

Policy Improvement: find a policy πi+1 such that
(41)

u∈U

4.2


β τ −t Zτ dτ + β ∆t qi (Xt0 , πi (Xt0 )) t ,

t

.
the optimal advantage function a∗ = aπ∗ also characterizes
the HJBE (17) and the optimal policy π∗ as
u∈U

t0

Z

13

Integral Q-Policy-Iteration (IQPI)

Our general Q-function qπ includes the previously proposed Qfunctions in CTS as special cases—Baird III (1993)’s Q-function
(κ1 = 1, κ2 = 1/∆t); hπ for γ ∈ (0, 1) (κ1 = κ2 = − ln γ),
and its generalization for γ ∈ (0, 1] (any κ1 = κ2 > 0) both
recognized as Q-functions by Mehta and Meyn (2009).

Our next model-free off-policy IPI named integal Q-policyiteration (IQPI) estimates and uses a general Q-function qπ :

11

in IAPI does not appear in IQPI, making the algorithm simpler. As will be shown in Theorem 7 in Section 4.5, qi in
Algorithm 3a corresponds to the Q-function qπi for the i-th
admissible policy πi , and the policies {πi }∞
i=0 generated by
IQPI satisfy the same properties to those in on-policy IPI.

Algorithm 4a: IEPI for the General Case (1)–(2)


the current policy πi
Policy Evaluation: given
,
a (non-stationary) policy µ
find a C1 function vi : X → R such that for all x ∈ X ,

 Z t0
vi (x) = Exµ
γ τ −t Zτ dτ + γ ∆t vi (Xt0 ) Xt = x ,(50)

Notice that simplification of IQPI is possible by setting
.
κ = ln(γ −1 β) = κ1 = κ2 and γ 6= β,

t

(47)


where

in which case Zτ in IQPI is dramatically simplified to (49)
shown in the Algorithm 3b, the simplified IQPI, and the Qfunction qπ in its definition (44) becomes
qπ (x, u) = κ · vπ (x) + aπ (x, u).

Policy Improvement: find a policy πi+1 satisfying (26);

(48)
Note that the difference of IEPI from on-policy IPI lies in its
Bellman equation (50)—it contains the compensating term
“∇vi (Xτ )(fc (τ ) − fcπi (τ ))” that naturally emerges due to
the difference between the behavior policy µ and the target
one πi . For µ = πi , the compensating term becomes identically zero, in which case the Bellman equation (50) becomes (21) in on-policy IPI. For any given policy µ, IEPI in
fact generates the same result {(vi , πi )}∞
i=0 to its on-policy
version (Algorithm 1a) under the same initial condition as
shown in Theorem 7 (and Remark 7) in Section 4.6.

In this case, the gain κ (6= 0) of the integral is the scaling
factor of vπ in the Q-function qπ , relative to aπ . As mentioned by Baird III (1993), a bad scaling between vπ and
aπ in qπ , e.g., extremely large |κ|, may result in significant
performance degradation or extremely slow Q-learning.
Compared with the other off-policy IPI methods, the use
of the weighting factor β ∈ (0, ∞) is one of the major
distinguishing feature of IQPI—β plays a similar role to the
discount factor γ ∈ (0, 1] in the Bellman equation, but can
be arbitrarily set in the algorithm; it can be equal to γ or
not. In the special case (47), β should not be equal to γ
since the log ratio ln(β/γ) of the two determines the nonzero scaling gain κ in (48) and (49). Since Algorithm 3b is
a special case of IQPI (Algorithm 3a), it also has the same
mathematical properties shown in Section 4.5.

In what follows, we are particularly interested in IEPI under the u-AC setting (27)–(29) shown in Algorithm 4b. In
this case, the maximization process in the policy improvement is simplified to the update rule (30) also known as the
VGB greedy policy (Doya, 2000). On the other hand, the
compensation term in Zτ of the Bellman equation (50) is
also simplified to “∇vi (Xτ )Fc (Xτ )ξτπi ,” which is linear in
.
the difference ξτπi = Uτ − πi (Xτ ) at time τ and contains
the function ∇vi · Fc also shown in its policy improvement
rule (30) in common. This observation brings our next offpolicy IPI method named integral C-policy-iteration (ICPI).

Algorithm 3b: IQPI with the Simplified Setting (47)


the current policy πi

Policy Evaluation: given an weighting factor β > 0 ,
an AD policy µ over U 

Algorithm 4b: IEPI in the u-AC Setting (27)–(29)


the current policy πi
Policy Evaluation: given
,
a (non-stationary) policy µ

find a continuous function qi : X × U → R such that (42)
holds for all (x, u) ∈ X × U and for Zτ given by

Zτ = κ · Rτ − qi (Xτ , Uτ ) ;
(49)

find a C1 function vi : X → R such that (50) holds for all
x ∈ X and for Zτ given by

Policy Improvement: find a policy πi+1 satisfying (43);
4.3


Zτ = Rτπi − ∇vi (Xτ ) fc (τ ) − fcπi (τ ) ,
.
.
fc (τ ) = fc (Xτ , Uτ ), fcπi (τ ) = fc (Xτ , πi (Xτ ));

Integral Explorized Policy Iteration (IEPI)

where ξτπi

The on-policy IPI (Algorithm 1a) can be easily generalized
and extended to its off-policy version without introducing
any AD function such as ai in IAPI and qi in IQPI. In
this paper, we name it integral explorized policy iteration
(IEPI) following the perspectives of Lee et al. (2012) and
present its policy evaluation and improvement loop in Algorithm 4a. Similarly to on-policy IPI with its policy improvement (22) replaced by (26), IEPI is also partially modelfree—the input-coupling dynamics fc has to be used in both
policy evaluation and improvement while the drift term fd
is not when the system dynamics f is decomposed to (25).

Zτ = Rτπi − ∇vi (Xτ )Fc (Xτ ) ξτπi ,
.
= Uτ − πi (Xτ ) is the policy difference;

Policy Improvement: update the next policy πi+1 by (30);
4.4

Integral C-Policy-Iteration (ICPI)

In the u-AC setting (27)–(29), we now modify IEPI (Algorithm 4b) to make it model-free by employing a function
cπ : X → Rm defined for a given admissible policy π as
.
cπ (x) = FcT (x)∇vπT (x),

12

(51)

which is continuous by continuity of Fc and ∇vπ . Here,
the function cπ will appear in both policy evaluation and
improvement in Common and contains the input-Coupling
term Fc , so we call it C-function for an admissible policy π.
Indeed, when (27)–(29) are true, the next policy π 0 satisfying
(18) for an admissible policy π is explicitly given by

(2) By virtue of the fact that there is no AD function
to be estimated in ICPI as in IEPI, the exploration
over its smaller space X × {uj }m
j=0 , rather than the
entire state-action space X × U, is enough to obtain
the desired result “vi = vπi and ci = cπi ” in its policy
evaluation (see Algorithm 5 and Theorem 7 in the next
subsection). Here, uj ’s are any vectors in U such that

π 0 (x) = (σ ◦ cπ )(x) = σ(cπ (x)).

m 15
span{uj − uj−1 }m
j=1 = R .

FcT (x)∇viT (x)

In the same way, if ci (x) =
is true, then (30)
in Algorithm 4b can be replaced by (53), and the compensating term ∇vi (Xτ )Fc (Xτ )ξτπi in policy evaluation of IEPI
πi
(Algorithm 4b) by cT
i (Xτ )ξτ .

Remark 6 One might consider a general version of ICPI
by replacing the term ∇vi (x)fc (x, u) in the general IEPI
(Algorithm 4a) with an AD function, say c0i (x, u). In this
case, however, it loses the merits of ICPI over IAPI and IQPI
shown above. Furthermore, the solution (vi , c0i ) of the associated Bellman equation is not uniquely determined—a pair
.
of vi and any cbi (x, u) = c0i (x, u) + b(x) for a continuous
function b(x) is also a solution to (39) for Zτ given by

Motivated by the above idea, we propose integral C-policyiteration (ICPI) whose policy evaluation and improvement
are shown in Algorithm 5. In the former, the functions vπi
and cπi for the given (admissible) policy πi are estimated by
solving the associated off-policy Bellman equation for vi and
ci , and then the next policy πi+1 is updated using ci in the
latter. In fact, ICPI is a model-free extension of IEPI—while
ICPI does not, IEPI obviously needs the knowledge of the
input-coupling dynamics Fc to run. A model-free off-policy
IPI so-named integral Q-learning 14 by Lee et al. (2012,
2015), which was derived from IEPI under the Lyapunov’s
stability framework, also falls into a class of ICPI for the
unconstrained total case (U = Rm and γ = 1).

Zτ = Rτπi − cbi (Xτ , Uτ ) + cbi (Xτ , πi (Xτ )).
4.5

Assumption 3b For each i ∈ Z+ , if πi is admissible, then
.
vi = qi (·, πi (·))/κ1 is C1 and

(1) As in IEPI, the complicated maximization in the policy
improvement of IAPI and IQPI has been replaced by
the simple update rule (53), which is a kind of modelfree VGB greedy policy (Doya, 2000).


lim lπi x, k; vi = 0 for all x ∈ X .

k→∞

Theorem 7 Under Assumptions 1 and 3a (or 3b in IQPI),
∞
the sequences {πi }∞
i=0 and {vi }i=0 generated by any offpolicy IPI method (IAPI, IQPI, IEPI, or ICPI) satisfy the
properties (P1)–(P3) in Theorem 3. Moreover,

14

The name ‘integral Q-learning’ does not imply that it is involved
with our Q-function (44). Instead, its derivation was based on the
value function with singularly-perturbed actions (Lee et al., 2012).

ai = aπi (IAPI), qi = qπi (IQPI), and ci = cπi (ICPI)

Algorithm 5: Integral C-Policy-Iteration (ICPI)

for all i ∈ Z+ ; if Assumption 2 also holds, then vi converges
towards the optimal solution v∗ in a sense that {vi }∞
i=0 satisfies the convergence properties (C1)–(C2) in Theorem 5.

(under the u-AC setting (27)–(29))
Policy Evaluation: given πi and an AD policy µ over a
finite subset U0 = {u0 , u1 , · · · , um } of U satisfying (54),
 1

a C function vi : X → R
find
such that
a continuous function ci : X → Rm

Proof. See Appendix B. 2

(52)

Remark 7 If the policy π 0 satisfying (18) in Assumption 1
is unique for each admissible π, then Theorem 7 also shows
∞
that {πi }∞
i=0 and {vi }i=0 generated by any off-policy IPI in
this paper are even equivalent to those in on-policy IPI under
the same initial π0 . An example of this is the u-AC case (27)–
(29), where the next policy πi+1 is always uniquely given by
the VGB greedy policy (30) for given vi ∈ Va .

(53)

15

(39) holds for each (x, u) ∈ X × U0 and for Zτ given by

where

ξτπi

Policy Improvement: update the next policy πi+1 by
πi+1 (x) = σ(ci (x)).

Mathematical Properties of Off-policy IPI Methods

Now, we show that every off-policy IPI method is effectively
same to on-policy IPI in a sense that the sequences {vi }∞
i=0
and {πi }∞
i=0 generated satisfy Theorems 3 and 4 under the
same assumptions and are equal to those in on-policy IPI
under the uniqueness of the next policy π 0 in Assumption 1.
.
In the case of IQPI, we let vi = qi (·, π(·))/κ1 and assume

Compared with IAPI and IQPI, the advantages of ICPI (at
the cost of restricting the RL problem to the u-AC one (27)–
(29)) are as follows.

πi
Zτ = Rτπi − cT
i (x) ξτ
.
= Uτ − πi (Xτ ) is the policy difference;

(54)

When U contains the zero vector, any linearly independent subset {uj }m
j=1 and u0 = 0 is an example of such uj ’s in (54).

13

Table 1
Summary of the off-policy IPI methods.

4.6

Name

Model-free

Rτ or Rτπ

Functions involved

Search Space

Algorithm No.

Constraint(s)

IAPI

O

Rτ

vπ and aπ

X ×U

2

(40)

IQPI

O

Rτ

qπ

X ×U

3a
3b

X
(47)

IEPI

4

Rτπ

vπ

X

4a
4b

X
(27)–(29)

ICPI

O

Rτπ

vπ and cπ

X × {uj }

5

(27)–(29)

Table 2 and shown in their off-policy Bellman equations (or
their Zτ ’s) become all zeros and thus no longer detectable—
the need for the behavior policy µ different from the target
policy πi to obtain or estimate the respective functions in
such AD terms. In the case of IEPI, if Uτ = πi (Xτ ) for all
τ ∈ [t, t0 ], then it becomes equal to “on-policy IPI with its
policy improvement (22) replaced by (26).”

Summary and Discussions

The off-policy IPI methods presented in this section are compared and summarized in Table 1. As shown in Table 1, all
of the off-policy IPI methods are model-free except IEPI
which needs the full-knowledge of a input-coupling dynamics fc in (25) to run; here, ICPI is actually a model-free version of the u-AC IEPI (Algorithm 4b). While IAPI and IQPI
explore the whole state-action space X × U to learn their
respective functions (vπ , aπ ) and qπ , IEPI and ICPI search
only the significantly smaller spaces X and X × {uj }m
j=0 ,
respectively. This is due to the fact that IEPI and ICPI both
learn no AD function such as aπ and qπ as shown in the
fourth column of Table 1. While IAPI and IQPI employ the
reward Rτ , both IEPI and ICPI use the πi -reward Rτπi at
each i-th iteration.

Table 2
The AD parts in policy evaluation of the model-free methods

Name
IAPI
IQPI
ICPI
5

Table 1 also summarizes the constraint(s) on each algorithm.
IAPI has the constraint (40) on ai and πi in the policy evaluation that reflects the equality aπi (x, πi (x)) = 0 similarly
to advantage updating (Baird III, 1993; Doya, 2000). ICPI
is designed under the u-AC setting (27)–(29), which gives:

The AD-Parts
ai (Xτ , Uτ ) − ai (Xτ , π(Xτ ))

κ2 · qi (Xτ , Uτ ) − qi (Xτ , πi (Xτ ))
ci (Xτ )ξτπi

Inverted-Pendulum Simulation Examples

To support the theory and verify the performance, we present
the simulation results of the IPI methods applied to the 2ndorder inverted-pendulum model (n = 2 and m = 1):
θ̈τ = −0.01θ̇τ + 9.8 sin θτ − Uτ cos θτ ,

(1) the uniqueness of the target solution (vi , ci ) = (vπi , cπi )
of the Bellman equation (39) for Zτ given by (52);

where θτ , Uτ ∈ R are the angular position of and the external
torque input to the pendulum at time τ , respectively, with
the torque limit given by |Uτ | ≤ Umax for Umax = 5 [N·m].
Note that this model is exactly same to that used by Doya
(2000) except that the action Uτ , the torque input, is coupled
with the term ‘cos θτ ’ rather than the constant ‘1,’ which
makes our problem more realistic and challenging. Letting
.
Xτ = [ θτ θ̇τ ]T , then the inverted-pendulum model can be
expressed as (1) and (27) with

(2) the exploration of a smaller space X × {uj }m
j=0 , rather
than the whole state-action space X × U;
(3) the simple update rule (53) in policy improvement, the
model-free version of the VGB greedy policy (Doya,
2000), in place of the complicated maximization over U
for each x ∈ X such as (41) and (43) in IAPI and IQPI.
The special IEPI scheme (Algorithm 4b) designed under the
u-AC setting (27)–(29) also updates the next policy πi+1 via
the simple policy improvement update rule (30) (a.k.a. the
VGB greedy policy (Doya, 2000)), rather than performing
the maximization (26). IQPI can be also simplified to Algorithm 3b under the different weighting (or discounting) by
.
β (6= γ) and the gain setting κ1 = κ2 = κ (κ = ln(β/γ))
shown in (47). In this case, β ∈ (0, ∞) determines the gain
of the integral in policy evaluation and scales vπ with respect to aπ in qπ (see (48) and (49)).


fd (x) =

x2
9.8 sin x1 − 0.01x2




and Fc (x) =


0
,
− cos x1

where x = [ x1 x2 ]T ∈ R2 . Here, our learning objective is
to make the pendulum swing up and eventually settle down
at the upright position θτ = 2πk for some k ∈ Z. The
reward R to achieve such a goal under the limited torque
was therefore set to (29) and (31) with U = [−Umax , Umax ],
Γ = 1, and the functions R0 (x) and s(ξ) given by

For any of the model-free methods, if Uτ = πi (Xτ ), rather
than Uτ = µ(τ, Xτ , u), then their AD parts summarized in

R0 (x) = 102 cos x1 and s(ξ) = Umax tanh(ξ/Umax );

14

(a) v̂10 (x) (IEPI)

(b) v̂10 (x) (ICPI)

(c) v̂10 (x) (IAPI)

(d) q̂10 (x, π̂10 (x))/κ (IQPI)

Fig. 1. The estimates of vi |i=10 (≈ v∗ ) done by the respective IPI methods over the region Ωx ; the horizontal and vertical axes correspond
to the values of the angular position x1 and the velocity x2 of the pendulum; v̂i , q̂i , and π̂i denote the estimates of vi , qi , and πi obtained
by running each off-policy IPI. In IQPI case, v̂i ≈ q̂i (·, π̂i (·))/κ holds by (45) as long as the associated functions are well-estimated.
6

the sigmoid function s with Γ = 1 then gives the following
expressions of the functions σ(ξ) in (30) and S(u) in (29):

θτ
θτ
θτ
θτ

5
4
Amplitude

σ(ξ) = Umax tanh(ξ/Umax ),
u
u 
2
S(u) = (Umax
/2) · ln u++ · u−− ,
.
where u± = 1 ± u/Umax . Here, note that S(u) is finite for
all u ∈ U and has its maximum at the end points u = ±Umax
2
as S(±Umax ) = (Umax
ln 4)/2 ≈ 17.3287. The initial policy
π0 was given by π0 = 0 and for its admissibility vπ0 ∈ Va ,
we set the discount factor as γ = 0.1, less than 1. This is a
high gain on the state-reward R0 (x) (= 102 cos x1 ) and low
discounting (γ = 0.1) scheme, which made it possible to
achieve the learning objective merely after the first iteration.

(IEPI)
(ICPI)
(IAPI)
(IQPI)

3
2
1
0
−1
0

1

2

3

4
Time [s]

5

6

7

8

(a) Eπ̂10 [θτ |X0 = x0 ], the trj. of the angular position θτ
6
θ̇τ (IEPI)
4

Under the above u-AC framework, we simulated the four
off-policy methods (Algorithms 2, 3b, 4b, and 5) with their
parameters ∆t = 10 [ms] and β = 1. On-policy IPI in Section 3 is a special case µ = π of IEPI and thus omitted.
The behavior policy µ used in the simulations was µ = 0
for IEPI and µ(t, x, u) = u for the others; the next target policy πi+1 was given by πi+1 (x) = σ(yi (x)), where
yi (x) = FcT (x)∇viT (x) in IEPI, yi (x) = ci (x) in ICPI; in
IAPI and IQPI, yi (x) is approximately equal to the output
of a radial basis function (RBF) networks (RBFNs) to be
trained by policy improvement using ai and qi , respectively.
The functions vi , ai , qi , and ci were all approximated by
RBFNs as well. Instead of the whole spaces X and X × U,
.
we considered their compact regions Ωx = [−π, π]×[−6, 6]
and Ωx × U in our whole simulations; since our invertedpendulum system and the value function are 2π-periodic in
the angular position x1 , the state value x ∈ X was normalized to x̄ ∈ [−π, π] × R whenever input to the RBFNs. The
details about the RBFNs and the implementation methods
of the policy evaluation and improvement are shown in Appendix D. Every IPI method ran up to the 10th iteration.

θ̇τ (ICPI)
θ̇τ (IAPI)

Amplitude

2

θ̇τ (IQPI)

0
−2
−4
−6
0

1

2

3

4
Time [s]

5

6

7

8

(b) Eπ̂10 [θ̇τ |X0 = x0 ], the trj. of the angular velocity θ̇τ
Fig. 2. The state trajectories generated under the initial condition
x0 = [ 1.1π 0 ]T and the estimated policy π̂i of πi for i = 10
obtained by running each IPI method (IEPI, ICPI, IAPI, and IQPI).

estimates shown in Fig. 1 that are generated by different
IPI methods (IEPI, ICPI, IAPI, and IQPI) are all consistent
to each other. We also generated the state trajectories X·
shown in Fig. 2 for the initial condition θ0 = (1 + 0 )π
with 0 = 0.1 and θ̇0 = 0 under the estimated policy π̂i of
πi finally obtained at the last iteration (i = 10) of each IPI
method. As shown in Fig. 2, all of the policies π̂10 obtained
by different IPI methods generate the state trajectories that
are almost consistent with each other—they all achieved
the learning objective at around t = 4 [s], and the whole
state trajectories generated are almost same (or very close)

Fig. 1 shows the estimated values of vπi (x) for x ∈ Ωx after
the learning has been completed (at i = 10), where after
convergence, vπi may be considered to be an approximation
of the optimal value function v∗ . Although there are some
small ripples in the case of IQPI, the final value function

15

to each other. Also note that the IPI methods achieved our
learning objective without using an initial stabilizing policy
that is usually required in the optimal control setting under
the total discounting γ = 1 (e.g., Abu-Khalaf and Lewis,
2005; Vrabie and Lewis, 2009; Lee et al., 2015).
6

Frémaux, N., Sprekeler, H., and Gerstner, W. Reinforcement learning using a continuous time actor-critic framework with spiking
neurons. PLoS Comput. Biol., 9(4):e1003024, 2013.
Haddad, W. M. and Chellaboina, V. Nonlinear dynamical systems
and control: a Lyapunov-based approach. Princeton University
Press, 2008.
Howard, R. A. Dynamic drogramming and Markov processes.
Tech. Press of MIT and John Wiley & Sons Inc., 1960.
Kirk, W. and Sims, B. Handbook of metric fixed point theory.
Springer Science & Business Media, 2013.
Kleinman, D. On an iterative technique for Riccati equation computations. IEEE Trans. Autom. Cont., 13(1):114–115, 1968.
Lagoudakis, M. G. and Parr, R. Least-squares policy iteration.
J. Mach. Learn. Res., 4(Dec):1107–1149, 2003.
Leake, R. J. and Liu, R.-W. Construction of suboptimal control
sequences. SIAM Journal on Control, 5(1):54–63, 1967.
Lee, J. Y., Park, J. B., and Choi, Y. H. Integral Q-learning
and explorized policy iteration for adaptive optimal control
of continuous-time linear systems. Automatica, 48(11):2850–
2859, 2012.
Lee, J. Y., Park, J. B., and Choi, Y. H. On integral generalized
policy iteration for continuous-time linear quadratic regulations.
Automatica, 50(2):475–489, 2014.
Lee, J. Y., Park, J. B., and Choi, Y. H. Integral reinforcement
learning for continuous-time input-affine nonlinear systems with
simultaneous invariant explorations. IEEE Trans. Neural Networks and Learning Systems, 26(5):916–932, 2015.
Lewis, F. L. and Vrabie, D. Reinforcement learning and adaptive
dynamic programming for feedback control. IEEE Circuits and
Systems Magazine, 9(3):32–50, 2009.
Loeb, P. A. and Talvila, E. Lusin’s Theorem and Bochner integration. Scientiae Mathematicae Japonicae, 10:55–62, 2004.
Luo, B., Wu, H.-N., Huang, T., and Liu, D. Data-based approximate policy iteration for affine nonlinear continuous-time optimal control design. Automatica, 50(12):3281–3290, 2014.
Maei, H. R., Szepesvári, C., Bhatnagar, S., and Sutton, R. S.
Toward off-policy learning control with function approximation.
In Proceedings of the 27th International Conference on Machine
Learning (ICML-10), pages 719–726, 2010.
Mehta, P. and Meyn, S. Q-learning and pontryagin’s minimum
principle. In Proc. IEEE Int. Conf. Decision and Control, held
jointly with the Chinese Control Conference (CDC/CCC), pages
3598–3605, 2009.
Modares, H., Lewis, F. L., and Jiang, Z.-P. Optimal outputfeedback control of unknown continuous-time linear systems
using off-policy reinforcement learning. IEEE Trans. Cybern.,
46(11):2401–2410, 2016.
Murray, J. J., Cox, C. J., Lendaris, G. G., and Saeks, R. Adaptive
dynamic programming. IEEE Trans. Syst. Man Cybern. Part
C-Appl. Rev., 32(2):140–153, 2002.
Powell, W. B. Approximate dynamic programming: solving the
curses of dimensionality. Wiley-Interscience, 2007.
Saridis, G. N. and Lee, C. S. G. An approximation theory of
optimal control for trainable manipulators. IEEE Trans. Syst.
Man Cybern., 9(3):152–159, 1979.
Sutton, R. S. and Barto, A. G. Reinforcement learning: an introduction. Second Edition in Progress, MIT Press, Cambridge,
MA (available at http://incompleteideas.net/sutton), 2017.
Thomson, B. S., Bruckner, J. B., and Bruckner, A. M. Elementary
real analysis. Prentice Hall, 2001.
Vamvoudakis, K. G., Vrabie, D., and Lewis, F. L. Online adaptive
algorithm for optimal control with integral reinforcement learning. Int. J. Robust and Nonlinear Control, 24(17):2686–2710,
2014.

Conclusions

In this paper, we proposed the on-policy IPI scheme and
four off-policy IPI methods (IAPI, IQPI, IEPI, and ICPI)
which solve the general RL problem formulated in CTS.
We proved their mathematical properties of admissibility,
monotone improvement, and convergence, together with the
equivalence of the on- and off-policy methods. It was shown
that on-policy IPI can be made partially model-free by modifying its policy improvement, and the off-policy methods are
partially model-free (IEPI), completely model-free (IAPI,
IQPI), or model-free but only implementable in the u-AC
setting (ICPI). The off-policy methods were discussed and
compared with each other as listed in Table 1. Numerical
simulations were performed with the 2nd-order invertedpendulum model to support the theory and verify the performance, and the results with all algorithms were consistent
and approximately equal to each other. Unlike the IPI methods in the stability-based framework, an initial stabilizing
policy is not required to run any of the proposed IPI methods. This work also provides the ideal PI forms of RL in
CTS such as advantage updating (IAPI), Q-learning in CTS
(IQPI), VGB greedy policy improvement (on-policy IPI and
IEPI under u-AC setting), and the model-free VGB greedy
policy improvement (ICPI). Though the proposed IPI methods are not online incremental RL algorithms, we believe
that this work provides the theoretical background and intuition to the (online incremental) RL methods to be developed in the future and developed so far in CTS.
References
Abu-Khalaf, M. and Lewis, F. L. Nearly optimal control laws
for nonlinear systems with saturating actuators using a neural
network HJB approach. Automatica, 41(5):779–791, 2005.
Aleksandar, B., Lever, G., and Barber, D. Nesterov’s accelerated
gradient and momentum as approximations to regularised update descent. arXiv preprint arXiv:1607.01981v2, 2016.
Anderson, B. and Moore, J. B. Optimal control: linear quadratic
methods. Prentice-Hall, Inc., 1989.
Baird III, L. C. Advantage updating. Technical report, DTIC
Document, 1993.
Beard, R. W., Saridis, G. N., and Wen, J. T. Galerkin approximations of the generalized Hamilton-Jacobi-Bellman equation.
Automatica, 33(12):2159–2177, 1997.
Bessaga, C. On the converse of banach “fixed-point principle”.
Colloquium Mathematicae, 7(1):41–43, 1959.
Doya, K. Reinforcement learning in continuous time and space.
Neural computation, 12(1):219–245, 2000.
Farahmand, A. M., Ghavamzadeh, M., Mannor, S., and Szepesvári,
C. Regularized policy iteration. In Advances in Neural Information Processing Systems, pages 441–448, 2009.
Folland, G. B. Real analysis: modern techniques and their applications. John Wiley & Sons, 1999.

16

Lemma B.1 Let v : X → R and Z : X ×U → R be any C1
and continuous functions, respectively. If there exist ∆t > 0,
a weighting factor β > 0, and “an AD policy µ over a nonempty subset U0 ⊆ U” such that for each (x, u) ∈ X × U0 ,

Vrabie, D. and Lewis, F. L. Neural network approach to
continuous-time direct adaptive optimal control for partially unknown nonlinear systems. Neural Netw., 22(3):237–246, 2009.

Appendix

Z
v(x) = Eµ

A


β τ −t Zτ dτ +β ∆t v(Xt0 ) Xt = x, Ut = u ,

t

Proof of Lemma 2

.
where Zτ = Z(Xτ , Uτ ) for τ ≥ t, then

In this proof, we first focus on the case N = 1 and then
generalize the result. By Theorem 2, T v∗ is an admissible
value function and satisfies v∗  T v∗ , but T v∗  v∗ since
v∗ is the optimal value function. Therefore, T v∗ = v∗ and
v∗ is a fixed point of T .

(B.1)

− ln β · v(x) = Z(x, u) + ∇v(x)f (x, u)
holds for all (x, u) ∈ X × U0 .
The applications of Lemma B.1 to the Bellman equations
of the off-policy IPI methods (IAPI, IQPI, IEPI, and ICPI)
provides the following claim.

Claim A.1 v∗ is the unique fixed point of T .

Claim B.1 If πi is admissible, then vi and πi+1 obtained by
the i-th policy evaluation and improvement of any off-policy
IPI method satisfy vi = vπi and (23). Moreover,

Proof. To show the uniqueness, suppose vπ ∈ Va is another
fixed point of T and let π 0 be the next policy obtained by
policy improvement with respect to the fixed point vπ . Then,
π 0 is admissible by Theorem 2, and it is obvious that

 
− ln γ · T vπ (x) = h x, π 0 (x), ∇ T vπ (x) x ∈ X ,

ai = aπi (IAPI), qi = qπi (IQPI), and ci = cπi (ICPI).

by vπ0 = T vπ and “(11) for the admissible policy π 0 .” The
substitution of T vπ = vπ into it results in
− ln γ·vπ (x) = h(x, π 0 (x), ∇vπ (x)) = max h(x, u, ∇vπ (x))
u∈U

for all x ∈ X , the HJBE. Therefore, vπ = v∗ by Corollary 3
and Assumptions 1 and 2, a contradiction, implying that v∗
is the unique fixed point of T . 2

Suppose that πi is admissible. Then, if Claim B.1 is true,
then πi+1 in any off-policy IPI method satisfies (23) and
hence Theorem 2 with Assumption 1 proves that πi+1 is
also admissible and satisfies vπi  vπi+1  vπ∗ . Since π0
is admissible in the off-policy IPI methods, mathematical
induction proves the first part of the theorem. Moreover,
now that we have the properties (P1)–(P3), if Assumption 2
additionally holds, then we can easily prove the convergence
properties (C1)–(C2) in Theorem 4 by following its proof.
Proof of Claim B.1.
(IAPI/IQPI) Applying Lemma B.1 with U0 = U to (39) in
IAPI and to (42) in IQPI and then substituting the definition (5) of h(x, u, p) show that (vi , ai ) in IAPI and (vi , qi )
.
in IQPI (with vi = qi (·, πi (·))/κ1 ) satisfy

Now, we generalize the result to the case with any N ∈ N.
Since v∗ is the fixed point of T , we have
T N v∗ = T N −1 [T v∗ ] = T N −1 v∗ = · · · = T v∗ = v∗ ,

− ln γ · vi (x) = h(x, u, ∇vi (x)) − ai (x, u) + ai (x, πi (x))

showing that v∗ is also a fixed point of T N for any N ∈ N.
To prove that v∗ is the unique fixed point of T N for all N ,
suppose that there is some M ∈ N and v ∈ Va such that
T M v = v. Then, it implies T v = v since we have

(B.2)

κ2 
qi (x, u) − κ1 vi (x)
− ln γ · vi (x) = h(x, u, ∇vi (x)) −
κ1
(B.3)
for all (x, u) ∈ X × U, respectively. Furthermore, the substitutions of u = πi (x) into (B.2) and (B.3) yield

v  T v  T 2v  · · ·  T M v = v
by the repetitive applications of Theorem 2. Therefore, we
obtain v = v∗ by Claim A.1, which completes the proof. 2
B

t0

− ln γ · vi (x) = h(x, πi (x), ∇vi (x)) ∀x ∈ X ,

(B.4)

which implies vi = vπi by Theorem 1 and Assumption 3a.
Next, substituting vi = vπi into (B.2) and (B.3) and then
rearranging it with (12) (and (40) in the IAPI case) result in

Proof of Theorem 7

For the proof, we employ the following lemma regarding the
conversion from an time-integral to an algebraic equation.
Its proof is given in Appendix C.

ai (x, u) = hπi (x, u) + ln γ · vπi (x),

qi (x, u) = κ1 vπi (x) + ai (x, u)/κ2 ,

17

Moreover, by vi = vπi , the policy improvement (53) is equal
to πi+1 (x) = σ(cπi (x)) for all x ∈ X , which is the closedform solution of (23) in the u-AC setting (27)–(29). 2

and hence we obtain ai = aπi and qi = qπi by the definitions
(37) and (44). By this and the respective policy improvement
of IAPI and IQPI, it is obvious that the next policy πi+1 in
each algorithm satisfies

∀x ∈ X :

C

πi+1 (x) ∈ arg maxu∈U aπi (x, u) (IAPI);
πi+1 (x) ∈ arg maxu∈U qπi (x, u) (IQPI).

The proof is done using the following claim.

Since they are equivalent to (20) with π = πi and some
special choices of bπ and κ > 0, 16 and (20) is equivalent
to (18), πi+1 in both IAPI and IQPI satisfy (23) in (P2).

Claim C.1 Let µ be a policy starting at t and w : X × U
be a continuous function. If there exist ∆t > 0 and β > 0
such that for all x ∈ X ,

(IEPI) By (C.2) in Appendix C and (25), the Bellman equation (50) can be expressed as
Z
0 = Eµ

t

0

t0

Z
0 = Eµ

β

τ −t


w(Xτ , Uτ ) dτ Xt = x ,

(C.1)

t


γ τ −t φi (Xτ ) dτ Xt = x ,

then, w(x, µ(t, x)) = 0 for all x ∈ X .

t

By the standard calculus, for any ∆t > 0 and β > 0,

where φi : X → R is given by
.
φi (x) = R(x, πi (x)) + ln γ · vi (x) + ∇vi (x)f (x, πi (x)),

β τ −t v(Xτ )

which is obviously continuous since so are all functions
contained in it. Thus, the term “γ τ −t φi (Xτ )” is integrable
over [t, t0 ], and Claim C.1 in Appendix C with w(x, u) =
φi (x) for all (x, u) ∈ X ×U implies φi = 0, which results in
(B.4) and hence vi = vπi by Theorem 1 and Assumption 3a.
Since the policy improvement (26) in IEPI is equivalent to
solving (22), it is equivalent to (23) by vi = vπi and (12).

Z

t

t

t0

β

τ −t

h


d τ −t
β v(Xτ ) dτ
dτ

(C.2)
i
ln β · v(Xτ ) + v̇(Xτ , Uτ ) dτ.

Hence, (B.1) can be rewritten for any (x, u) ∈ X × U0 as
Z
0 = Eµ

t0


β τ −t w(Xτ , Uτ ) dτ Xt = x, Ut = u (C.3)

t

.
where w(x, u) = Z(x, u) + ln β · v(x) + ∇v(x)f (x, u).
Here, w is continuous since so are v, ∇v, Z, and f , and thus
the term “β τ −t w(Xτ , Uτ )” is integrable over the compact
time interval [t, t0 ]. Now, fix u ∈ U0 . Then, one can see that

= R(x, πi (x)) − cT
i (x)(u − πi (x)) + ∇vi (x)f (x, u)

(1) µ(·, ·, u) is obviously a policy;
(2) the condition Ut = u in (C.3) is obviated for fixed u;
(3) µ(t, x, u) = u holds for all x ∈ X .

(B.5)

.
where ψ(x) = FcT (x)∇viT (x) − ci (x). Next, let x ∈ X be
an arbitrary fixed value. Then, for each j ∈ {1, 2, · · · , m},
subtracting (B.5) for u = uj−1 from the same equation
but for u = uj yields 0 = (uj − uj−1 )ψ(x). This can be
rewritten in the following matrix-vector form:
(E1:m − E0:m−1 )ψ(x) = 0,

t0

Z
=

t

− ln γ · vi (x)
= h(x, πi (x), ∇vi (x)) + (u − πi (x))T ψ(x),

t0

=

(ICPI) Applying Lemma B.1 to policy evaluation of ICPI
and rearranging it using (5) and (27), we obtain for each
(x, u) ∈ X × U0 :

Hence, by Claim C.1, we obtain
0 = w(x, µ(t, x, u)) = w(x, u) for all x ∈ X .
Since u ∈ U0 is arbitrary, we finally have w(x, u) = 0 for
all (x, u) ∈ X × U0 , which completes the proof.

(B.6)

.
where Ek:l = [uk uk+1 · · · ul ] for 0 ≤ k ≤ l ≤ m is the
m × (l − k + 1)-matrix constructed by the column vectors
uk , uk+1 , · · · , ul . Since (54) implies that {uj − uj−1 }m
j=1
is a basis of Rm , we have rank (E1:m − E0:m−1 ) = m and
by (B.6), ψ(x) = 0. Since x ∈ X is arbitrary, ψ = 0.
Now that we have ψ(x) = 0 ∀x ∈ X , (B.5) becomes (B.4)
and thus vi = vπi by Theorem 1 and Assumption 3a. This
also implies ci = cπi by ψ = 0 and the definition of ψ.
16

Proof of Lemma B.1

Proof of Claim C.1. To prove the claim, let x0 ∈ X and
.
xk = Eµ [Xt0 Xt = xk−1 ] for k = 1, 2, 3, · · · . Then, (C.1)
obviously holds for each x = xk ∈ X (k ∈ Z+ ). Denote
.
.
t0 = t and tk = t + k∆t for any k ∈ N
and define µ̄k : [tk , ∞) × X → U for each k ∈ Z+ as
.
µ̄k (τ, x) = µ(τ − tk + t, x) for any τ ≥ tk and any x ∈ X .

See the discussions right below (37) for IAPI and (46) for IQPI.

18

They correspond to z = (x, u) and Z = X × U when the
network is AD, and z = x and Z = X when it is not. In the
simulations in Section 5, the functions vi , ai , qi , and ci are
all approximated by RBFNs as shown below:

Then, obviously, µ̄k is a policy that starts at time tk . Moreover, since in our framework, the non-stationarity, i.e., the
explicit time-dependency, comes only from, if any, that of
the applied policy, we obtain by the above process and (C.1)
that

 Z tk+1
(C.4)
β τ −t w(Xτ , Uτ ) dτ Xtk = xk
0 = Eµ̄k


.
v (x) ≈ v̂(z; θiv ) = φT (z̄)θiv ,

 i
.

ci (x) ≈ ĉ(z; θic ) = φT (z̄)θic ,
T
a
a .

ai (x, u) ≈ â(z; θi ) =. φAD (z̄)θi ,

q
T
qi (x, u) ≈ q̂(z; θi ) = φAD (z̄)θiq ,

tk

for all k ∈ Z+ . Next, construct µ̄ : [t, ∞) × X → U by

where z̄ ∈ Z represents the input z ∈ Z to each network
whose state-component x is normalized to x̄ ∈ [−π, π] × R
by adding ±2πk to its first component x1 for some k ∈ Z+ ;
θiv , θic ∈ RN and θia , θiq ∈ RM are the weight vectors of the
networks; N, M ∈ N are the numbers of hidden neurons;
the RBFs φ : Z → RN with Z = X and φAD : Z → RM
with Z = X × U are defined as

.
µ̄(τ, x) = µ̄k (τ, x) for τ ∈ [tk , tk+1 ) and x ∈ X .
Then, for each fixed x ∈ X , µ̄(·, x) is right continuous
since for all k ∈ Z+ , so is µ̄k (·, x) on each time interval
[tk , tk+1 ). In a similar manner, for each fixed τ ∈ [t, ∞),
µ̄(τ, ·) is continuous over X since for all k ∈ Z+ , so is
µ̄k (τ, ·) for each fixed τ ∈ [tk , tk+1 ). Moreover, since µ̄k is
a policy starting at tk , the state trajectory Eµ̄k [X· |Xtk = xk ]
is uniquely defined over [tk , tk+1 ). Therefore, noting that xk
is represented (by definitions and the recursive relation) as


xk = Eµ̄k−1 Xtk Xtk−1 = xk−1 for any k ∈ N,

2

0=

Z

tk+1

β

Eµ̄k

τ −t

Here, φj and φAD,j are the j-th components of φ and φAD , respectively; kxkΣ1 and kzkΣ2 are weighted Euclidean norms
.
.
defined as kxkΣ1 = (xT Σ1 x)1/2 and kzkΣ2 = (z T Σ2 z)1/2
.
.
for the diagonal matrices Σ1 = diag{1, 0.5} and Σ2 =
diag{1, 0.5, 1}; xj ∈ X for 1 ≤ j ≤ N and zj ∈ X × U for
1 ≤ j ≤ M are the center points of RBFs that are uniformly
distributed within the compact regions Ωx and Ωx × U, respectively. In all of the simulations, we choose N = 132 and
M = 133 , so we have 132 -RBFs in v̂ and ĉ, and 133 -RBFs
in â and q̂.


w(Xτ , Uτ ) dτ Xtk = xk

tk

k=0

Z
= Eµ̄
|

t

∞


β τ −t w(Xτ , Uτ ) dτ Xt = x0 ,
{z
}
.
=W (t;x )

D.2

which implies W (t; x0 ) = 0 for all t ≥ 0. Since
∞

Z

Z t0
1
β w(Xτ , Uτ ) dτ = lim
β τ w(Xτ , Uτ ) dτ
∆t→0 ∆t t
= w(Xt , Ut )

ψ T (z) · θi = b(z) + ε(z),
(D.2)
L
where the parameter vector θi ∈ R to be estimated, with its
dimension L, and the associated functions ψ : Z → R1×L
and b : Z → R are given in Table D.1 for each IPI method.
i
In Table D.1, Iα (Z), Dα (v), and φπAD
defined as

τ

t

by (right) continuity of w, Xτ , and Uτ , we therefore obtain
0=

∂W (t; x0 )
= − ln β · W (t; x0 ) + β −t · w(x0 , µ̄(t, x0 ))
∂t

.
Iα (Z) =

D.1

Z

t0

ατ −t Z(X̄τ , Uτ ) dτ,

t

.
Dα (v) = v(X̄t ) − α∆t v(X̄t0 ),

and thereby, w(x0 , µ(t, x0 )) = 0. Since x0 ∈ X is arbitrary,
it implies w(x, µ(t, x)) = 0 for all x ∈ X . 2
D

Policy Evaluation Methods

Under the approximation (D.1), the Bellman equations in
Algorithms 2, 3b, 4b, and 5 can be expressed, with the approximation error ε : Z → R, as the following unified form:

0

∂
∂t

2

φj (x) = e−kx−xj kΣ1 and φAD,j (z) = e−kz−zj kΣ2 .

we conclude that the state trajectory Eµ̄ [X· |Xt = x0 ] is also
uniquely defined for each x0 ∈ X over [t, ∞), implying that
µ̄ is a policy starting at time t. Finally, using the policy µ̄,
we obtain from (C.4)
∞ 
X

(D.1)

.
i
and φπAD
= φAD (·, πi (·)) were used for simplicity, where
X̄τ is the state value Xτ normalized to [−π, π] × R; 17 we
set β = 1 in our IQPI simulation.

Inverted-Pendulum Simulation Methods
Linear Function Approximations by RBFNs

17

X̄τ is normalized to X̄τ whenever input to the RBFN(s). Other
than that, the use of X̄τ instead of Xτ (or vice versa) does not
affect the performance (e.g., R0 (Xτ ) = R0 (X̄τ ) in our setting).

To describe the methods in a unified manner, we denote any
network input by z and its corresponding input space by Z.

19

Table D.1
θi , ψ, and b in the expression (D.2) for each Bellman equation
Name
(Alg. #)

θi

IAPI
(Alg. 2)

" #
θiv
θia

IQPI
(Alg. 3b)
IEPI
(Alg. 4b)
ICPI
(Alg. 5)

"
Ezµ

Iγ

ψ(z)

b(z)

#
Dγ (φ)
πi 
φAD − φAD



Ezµ Iγ (R)

θiq

h

i
i
Ezµ Dβ φπ
AD + Iβ φAD



Ezµ Iβ (R)

θiv

h
i
Ezµ Dγ (φ) + Iγ ∇φ · Fc ξ·πi
"
#
Dγ (φ)
z

Eµ
π
I γ φ ξ· i



Ezµ Iγ (Rπi )

" #
θiv
θic

D.3

In each i-th policy improvement, the next policy πi+1 was
obtained using the estimates θ̂iv , θ̂ic , θ̂ia , or θ̂iq obtained at the
i-th policy evaluation by (D.4) or (D.5) depending on the
algorithms. In all of the simulations, the next policy πi+1
was parameterized as πi+1 (x) ≈ σ(ŷi (x)), where ŷi (x) was
directly determined in IEPI and ICPI (Algorithms 4b and 5)
as ŷi (x) = FcT (x)∇v̂ T (x; θ̂iv ) and ŷi (x) = ĉ(x; θ̂ic ), respectively. In IAPI and IQPI, ŷi (x) is the output of the RBFN
we additionally introduced:



Ezµ Iγ (Rπi )

ŷi (x) = φT (x̄)θ̂iu
to perform the respective maximizations (41) and (43). Here,
θ̂iu ∈ RN is updated by the mini-batch regularized update descent (RUD) (Aleksandar, Lever, and Barber, 2016) shown
in Algorithm D.1, which is a variant of stochastic gradient
descent, to perform such maximizations with improved convergence speed. In Algorithm D.1, Jimp (x; θ) is given by

In each i-th policy evaluation of each method, ψ(z) and
b(z) in (D.2) were evaluated at the given data points z =
zinit,j (j = 1, 2, · · · , Linit with L ≤ Linit ) that are uniformly
distributed over the respective compact regions Ωx ×U (IAPI
and IQPI), Ωx (IEPI), and Ωx ×U0 with U0 = {−Umax , Umax }
(ICPI). The trajectory X· over [t, t0 ] with each data point
zinit,j used as its initial condition was generated using the
4th-order Runge-Kutta method with its time step ∆t/10 =
1 [ms], and the trapezoidal approximation:

Iα (Z) ≈

Z(X̄t , Ut ) + α∆t Z(X̄t0 , Ut0 )
2

(
q̂(x, u; θ̂iq )|u=σ(φT (x̄)θ) in IQPI,
Jimp (x; θ) =
â(x, u; θ̂ia )|u=σ(φT (x̄)θ) in IAPI;


· ∆t

was used in the evaluation of ψ and b. The number Linit of
the data points zinit,j used in each IPI algorithm was 173
(IAPI), 25 × 31 × 25 (IQPI), 172 (IEPI), and 172 × 2 (ICPI).
In the i-th policy
evaluation of IAPI, we also evaluated the
. 
0
vectors ρ(x) = φAD (x,π
∈ RL at the grid points xgrid,k
i (x))
(k = 1, 2, · · · , Lgrid with Lgrid = 502 ) uniformly distributed
in Ωx , in order to take the constraint
ρT (x)θi = εconst (x)

(D.3)

obtained from ai (x, πi (x)) = 0 into considerations, where
εconst : X → R is the residual error. After evaluating ψ(·)
and b(·) at all points zinit,j (and in addition to that, ρ(·) at all
points xgrid,j in the IAPI case), the parameters θi in (D.2)
were estimated using least squares as

the error tolerance 0 < δ  1 was set to δ = 0.01; the
smoothing factor λj ∈ (0, 1) and the learning rate ηj > 0
were scheduled as λj = (1 − ) · (1 − 103 ηj ) with  = 10−3
and
 −3
10 for 1 ≤ j ≤ 30;
ηj =
10−3 /(j − 30) for j > 30.
Algorithm D.1: Mini-Batch RUD for Policy Improvement
(
θ̂iu = v = 0 ∈ RN ;
1 Initialize:
0 < δ  1 be a small constant;
2 j ← 1;
3 repeat
4

5

θ̂i =

X
Linit

ψj ψjT

−1  X
Linit


ψj bj

(D.4)

6

.
in the case of IQPI, IEPI, and ICPI, where ψj = ψ(zinit,j )
.
and bj = b(zinit,j ). This θ̂i minimizes the squared error
J(θi ) = ε2 (zinit,1 ) + · · · + ε2 (zinit,Linit ). In IAPI, θi in (D.2)
and (D.3) were estimated also in the least-squares sense as
X
−1  X

Lgrid
Linit
Linit
X
T
T
θ̂i =
ψj ψj +
ρk ρk
ψj bj , (D.5)

7

j=1

j=1

j=1

k=1

Policy Improvement Methods

Calculate

∂Jimp (x; θ̂iu )

v ← λj v + ηj
θ̂iu ← θ̂iu + v;

j ← j + 1;
until kvk < δ
8 return θ̂iu ;

j=1

.
where ρk = ρ(xgrid,k ); this θ̂i minimizes the squared error
JIAPI (θi ) = J(θi )+(ε2const (xgrid,1 )+· · ·+ε2const (xgrid,Lgrid )).

20

∂ θ̂iu

L
grid
X
k=1

L

grid
at all grid points {xgrid,k }k=1
;

∂Jimp (xgrid,k ; θ̂iu )
∂ θ̂iu


;

