1

Report LIDS-P-3174, May 2015 (Revised Sept. 2015)

To appear in IEEE Transactions on Neural Networks, 2015

Value and Policy Iteration in Optimal Control and
Adaptive Dynamic Programming

arXiv:1507.01026v2 [] 1 Oct 2015

Dimitri P. Bertsekas

Abstract—In this paper, we consider discrete-time infinite
horizon problems of optimal control to a terminal set of states.
These are the problems that are often taken as the starting
point for adaptive dynamic programming. Under very general
assumptions, we establish the uniqueness of solution of Bellman’s
equation, and we provide convergence results for value and policy
iteration.

policy µ, the corresponding cost function is denoted by Jµ .
The optimal cost function is defined as
J ∗ (x) = inf Jπ (x),
π∈Π

and a policy π ∗ is said to be optimal if it attains the minimum
of Jπ (x) for all x ∈ X, i.e.,
Jπ∗ (x) = inf Jπ (x) = J ∗ (x),
π∈Π

I. I NTRODUCTION
In this paper we consider a deterministic discrete-time optimal
control problem involving the system
xk+1 = f (xk , uk ),

k = 0, 1, . . . ,

(1)

where xk and uk are the state and control at stage k, lying in
sets X and U , respectively, and f is a function mapping X ×U
to X. The control uk must be chosen from a constraint set
U (xk ) ⊂ U that may depend on the current state xk . The cost
for the kth stage, denoted g(xk , uk ), is assumed nonnnegative
and may possibly take the value ∞:
0 ≤ g(xk , uk ) ≤ ∞,

xk ∈ X, uk ∈ U (xk ),

(2)

[values g(xk , uk ) = ∞ may be used to model constraints
on xk , for example]. We are interested in feedback policies
of the form π = {µ0 , µ1 , . . .}, where each µk is a function
mapping every x ∈ X into the control µk (x) ∈ U (x). The
set of all policies is denoted by Π. Policies of the form π =
{µ, µ, . . .} are called stationary, and for convenience, when
confusion cannot arise, will be denoted by µ. No restrictions
are placed on X and U : for example, they may be finite sets as
in classical shortest path problems involving a graph, or they
may be continuous spaces as in classical problems of control
to the origin or some other terminal set.
Given an initial state x0 , a policy π = {µ0 , µ1 , . . .} when
applied to the system (1), generates a unique sequence of state
control pairs xk , µk (xk ) , k = 0, 1, . . . , with cost
Jπ (x0 ) = lim

k→∞

k
X
t=0


g xt , µt (xt ) ,

x0 ∈ X,

(3)

[the limit exists thanks to the nonnegativity assumption (2)].
We view Jπ as a function over X that takes values in [0, ∞].
We refer to it as the cost function of π. For a stationary
Dimitri Bertsekas is with the Dept. of Electr. Engineering and Comp.
Science, M.I.T., Cambridge, Mass., 02139. dimitrib@mit.edu
Many thanks are due to Huizhen (Janey) Yu for collaboration and many
helpful discussions in the course of related works.

x ∈ X,

∀ x ∈ X.

In the context of dynamic programming (DP for short),
one hopes to prove that the optimal cost function J ∗ satisfies
Bellman’s equation:


∀ x ∈ X, (4)
g(x, u) + J ∗ f (x, u) ,
J ∗ (x) = inf
u∈U(x)

and that an optimal stationary policy may be obtained through
the minimization in the right side of this equation. Note that
Bellman’s equation generically has multiple solutions, since
adding a positive constant to any solution produces another
solution. A classical result, stated in Prop. 4(a) of Section II,
is that the optimal cost function J ∗ is the “smallest” solution
of Bellman’s equation. In this paper we will focus on deriving
conditions under which J ∗ is the unique solution within a
certain restricted class of functions.
In this paper, we will also consider finding J ∗ with the
classical algorithms of value iteration (VI for short) and policy
iteration (PI for short). The VI algorithm starts from some
nonnegative function J0 : X 7→ [0, ∞], and generates a
sequence of functions {Jk } according to


(5)
g(x, u) + Jk f (x, u) .
Jk+1 = inf
u∈U(x)

We will derive conditions under which Jk converges to J ∗
pointwise.
The PI algorithm starts from a stationary policy µ0 , and generates a sequence of stationary policies {µk } via a sequence
of policy evaluations to obtain Jµk from the equation


Jµk (x) = g x, µk (x) + Jµk f x, µk (x) ,
x ∈ X, (6)
interleaved with policy improvements to obtain µk+1 from Jµk
according to


µk+1 (x) ∈ arg min g(x, u) + Jµk f (x, u) ,
x ∈ X.
u∈U(x)

(7)
We implicitly assume here is that Jµk satisfies Eq. (6), which
is true under the cost nonnegativity assumption (2) (cf. Prop.
4 in the next section). Also for the PI algorithm to be welldefined, the minimum in Eq. (7) should be attained for each

2

x ∈ X, which is true under some conditions that guarantee
compactness of the level sets


u ∈ U (x) | g(x, u) + Jµk f (x, u) ≤ λ ,
λ ∈ ℜ.

We will derive conditions under which Jµk converges to J ∗
pointwise.
In this paper, we will address the preceding questions, for
the case where there is a nonempty stopping set Xs ⊂ X,
which consists of cost-free and absorbing states in the sense
that
g(x, u) = 0,

x = f (x, u),

∀ x ∈ Xs , u ∈ U (x).
(8)
Clearly, J ∗ (x) = 0 for all x ∈ Xs , so the set Xs may be
viewed as a desirable set of termination states that we are
trying to reach or approach with minimum total cost. We will
assume in addition that J ∗ (x) > 0 for x ∈
/ Xs , so that

∗
Xs = x ∈ X | J (x) = 0 .
(9)

In the applications of primary interest, g is usually taken to
be strictly positive outside of Xs to encourage asymptotic
convergence of the generated state sequence to Xs , so this
assumption is natural and often easily verifiable. Besides Xs ,
another interesting subset of X is

Xf = x ∈ X | J ∗ (x) < ∞ .

Ordinarily, in practical applications, the states in Xf are
those from which one can reach the stopping set Xs , at least
asymptotically.
For an initial state x, we say that a policy π terminates
starting from x if the state sequence {xk } generated starting
from x and using π reaches Xs in finite time, i.e., satisfies
xk̄ ∈ Xs for some index k̄. A key assumption in this paper is
that the optimal cost J ∗ (x) (if it is finite) can be approximated
arbitrarily closely by using policies that terminate from x. In
particular, in all the results and discussions of the paper we
make the following assumption (except for Prop. 5, which
provides conditions under which the assumption holds).
Assumption 1. The cost nonnegativity condition (2) and
stopping set conditions (8)-(9) hold. Moreover, for every pair
(x, ǫ) with x ∈ Xf and ǫ > 0, there exists a policy π that
terminates starting from x and satisfies Jπ (x) ≤ J ∗ (x) + ǫ.
Specific and easily verifiable conditions that imply this
assumption will be given in Section IV. A prominent case
is when X and U are finite, so the problem becomes a deterministic shortest path problem with nonnegative arc lengths. If
all cycles of the state transition graph have positive length, all
policies π that do not terminate from a state x ∈ Xf must
satisfy Jπ (x) = ∞, implying that there exists an optimal
policy that terminates from all x ∈ Xf . Thus, in this case
Assumption 1 is naturally satisfied.
When X is the n-dimensional Euclidean space ℜn , a primary case of interest for this paper, it may easily happen that
the optimal policies are not terminating from some x ∈ Xf ,
but instead the optimal state trajectories may approach Xs
asymptotically. This is true for example in the classical linearquadratic optimal control problem, where X = ℜn , Xs = {0},

U = ℜm , g is positive semidefinite quadratic, and f represents
a linear system of the form xk+1 = Axk + Buk , where A and
B are given matrices. However, we will show in Section IV
that Assumption 1 is satisfied under some natural and easily
verifiable conditions.
Regarding notation, we denote by ℜ and ℜn the real line
and n-dimensional Euclidean space, respectively. We denote
by E + (X) the set of all functions J : X 7→ [0, ∞], and by J
the set of functions

(10)
J = J ∈ E + (X) | J(x) = 0, ∀ x ∈ Xs .
Since Xs consists of cost-free and absorbing states [cf. Eq.
(8)], the set J contains the cost function Jπ of all policies π,
as well as J ∗ . In our terminology, all equations, inequalities,
and convergence limits involving functions are meant to be
pointwise. Our main results are given in the following three
propositions.

Proposition 1 (Uniqueness of Solution of Bellman’s Equation). Let Assumption 1 hold. The optimal cost function J ∗ is
the unique solution of Bellman’s equation (4) within the set
of functions J.
There are well-known examples where g ≥ 0 but Assumption 1 does not hold, and there are additional solutions of
Bellman’s equation within J. The following is a two-state
shortest path example, which is discussed in more detail in
[12], Section 3.1.2, and [14], Example 1.1.
Example 1 (Counterexample for Uniqueness of Solution of
Bellman’s Equation). Let X = {0, 1}, where 0 is the unique
cost-free and absorbing state, Xs = {0}, and assume that at
state 1 we can stay at 1 at no cost, or move to 0 at cost 1.
Here J ∗ (0) = J ∗ (1) = 0, so Eq. (9) is violated. It can be
seen that

J = J | J ∗ (0) = 0, J ∗ (1) ≥ 0 ,
and that Bellman’s equation is
J ∗ (0) = J ∗ (0),


J ∗ (1) = min J ∗ (1), 1 + J ∗ (0) .

It can be seen that Bellman’s
equation has infinitely many

solutions within J, the set J | J(0) = 0, 0 ≤ J(1) ≤ 1 .

Proposition 2 (Convergence of VI). Let Assumption 1 hold.

(a) The VI sequence {Jk } generated by Eq. (5) converges
pointwise to J ∗ starting from any function J0 ∈ J with
J0 ≥ J ∗ .
(b) Assume further that U is a metric space, and the sets
Uk (x, λ) given by


Uk (x, λ) = u ∈ U (x) | g(x, u) + Jk f (x, u) ≤ λ ,
are compact for all x ∈ X, λ ∈ ℜ, and k, where {Jk } is
the VI sequence {Jk } generated by Eq. (5) starting from
J0 ≡ 0. Then the VI sequence {Jk } generated by Eq.
(5) converges pointwise to J ∗ starting from any function
J0 ∈ J.

3

The compactness assumption of Prop. 2(b) is satisfied if
U (x) is finite for all x ∈ X. Other easily verifiable assumptions implying this compactness assumption will be given
later. Note that when there are solutions to Bellman’s equation
within J, in addition to J ∗ , VI will not converge to J ∗ starting
from any of these solutions. However, it is also possible that
Bellman’s equation has J ∗ as its unique solution within J, and
yet VI does not converge to J ∗ starting from the zero function
because the compactness assumption of Prop. 2(b) is violated.
There are several examples of this type in the literature, and
the following example, an adaptation of Example 4.3.3 of [12],
is a deterministic problem for which Assumption 1 is satisfied.
Example 2 (Counterexample for Convergence of VI). Let
X = [0, ∞) ∪ {s}, with s being a cost-free and absorbing
state, and let U = (0, ∞) ∪ {ū}, where ū is a special stopping
control, which moves the system from states x ≥ 0 to state s
at unit cost. The system has the form


xk + uk if xk ≥ 0 and uk 6= ū,
xk+1 = s
if xk ≥ 0 and uk = ū,


s
if xk = s and uk ∈ U .
The cost per stage has the form


xk if xk ≥ 0 and uk 6= ū,
g(xk , uk ) = 1
if xk ≥ 0 and uk = ū,


0
if xk = s and uk ∈ U .
Let also Xs = {s}. Then it can be verified that
(
1 if x ≥ 0,
∗
J (x) =
0 if x = s,

and that an optimal policy is to use the stopping control ū
at every state (since using any other control at states x ≥ 0,
leads to unbounded accumulation of positive cost). Thus it can
be seen that Assumption 1 is satisfied. On the other hand, the
VI algorithm is



Jk+1 (x) = min 1 + Jk (s), inf x + Jk (x + u)
u≥0

for x ≥ 0, and Jk+1 (s) = Jk (s), and it can be verified by
induction that starting from J0 ≡ 0, the sequence {Jk } is
given for all k by
(
min{1, kx} if x ≥ 0,
Jk (x) =
0
if x = s.

Thus Jk (0) = 0 for all k, while J ∗ (0) = 1, so the VI algorithm
fails to converge for the state x = 0. The difficulty here is that
the compactness assumption of Prop. 2(b) is violated.
Proposition 3 (Convergence of PI). Let Assumption 1 hold.
A sequence {Jµk } generated by the PI algorithm (6), (7),
satisfies Jµk (x) ↓ J ∗ (x) for all x ∈ X.
It is implicitly assumed in the preceding proposition that the
PI algorithm is well-defined in the sense that the minimization
in the policy improvement operation (7) can be carried out for
every x ∈ X. Easily verifiable conditions that guarantee this

also guarantee the compactness condition of Prop. 2(b), and
will be noted following Prop. 4 in the next section. Moreover,
in Section IV we will prove a similar convergence result for
a variant of the PI algorithm where the policy evaluation is
carried out approximately through a finite number of VIs.
Example 3 (Counterexample for Convergence of PI). For a
simple example where the PI sequence Jµk does not converge
to J ∗ if Assumption 1 is violated, consider the two-state
shortest path Example 2. Let µ be the suboptimal policy that
moves from state 1 to state 0. Then Jµ (0) = 0, Jµ (1) = 1, and
it can be seen that µ satisfies the policy improvement equation

µ(1) ∈ arg min 1 + Jµ (0), Jµ (1) .
Thus PI may stop with the suboptimal policy µ.

The results of the preceding three propositions are new at
the level of generality given here. For example there has been
no proposal of a valid PI algorithm in the classical literature on
nonnegative cost infinite horizon Markovian decision problems
(exceptions are special cases such as linear-quadratic problems
[23]). The ideas of the present paper stem from a more general
analysis regarding the convergence of VI, which was presented
recently in the author’s research monograph on abstract DP
[Ber12], and various extensions given in the recent papers [13],
[14]. Two more papers of the author, coauthored with H. Yu,
deal with issues that relate in part to the intricacies of the
convergence of VI and PI in undiscounted infinite horizon DP
[35], [5].
The paper is organized as follows. In Section II we provide
background and references, which place in context our results
and methods of analysis in relation to the literature. In Section
III we give the proofs of Props. 1-3. In Section IV we discuss
special cases and easily verifiable conditions that imply our
assumptions, and we provide extensions of our analysis.
II. BACKGROUND
The issues discussed in this paper have received attention since
the 60’s, originally in the work of Blackwell [15], who considered the case g ≤ 0, and the work by Strauch (Blackwell’s PhD
student) [30], who considered the case g ≥ 0. For textbook
accounts we refer to [2], [25], [11], and for a more abstract
development, we refer to the monograph [12]. These works
showed that the cases where g ≤ 0 (which corresponds to
maximization of nonnegative rewards) and g ≥ 0 (which is
most relevant to the control problems of this paper) are quite
different in structure. In particular, while VI converges to J ∗
starting for J0 ≡ 0 when g ≤ 0, this is not so when g ≥ 0;
a certain compactness condition is needed to guarantee this
[see Example 2, and part (d) of the following proposition].
Moreover when g ≥ 0, Bellman’s equation may have solutions
Jˆ 6= J ∗ with Jˆ ≥ J ∗ (see Example 1), and VI will not
ˆ In addition it is known
converge to J ∗ starting from such J.
that in general, PI need not converge to J ∗ and may instead
stop with a suboptimal policy (see Example 3).
The following proposition gives the standard results when
g ≥ 0 (see [2], Props. 5.2, 5.4, and 5.10, [11], Props.
4.1.1, 4.1.3, 4.1.5, 4.1.9, or [12], Props. 4.3.3, 4.3.9, and

4

4.3.14). These results hold for stochastic infinite horizon DP
problems with nonnegative cost per stage, and do not take
into account the favorable structure of deterministic problems
or the presence of the stopping set Xs .
Proposition 4. Let the nonnegativity condition (2) hold.
(a) J ∗ satisfies Bellman’s equation (4), and if Jˆ ∈ E + (X)
is another solution, i.e., Jˆ satisfies


ˆ
J(x)
= inf
g(x, u) + Jˆ f (x, u) ,
∀ x ∈ X,
u∈U(x)

ˆ
then J ∗ ≤ J.
(b) For all stationary policies µ we have


Jµ (x) = g x, µ(x) + Jµ f x, µ(x) ,

(11)

∀ x ∈ X.
(12)
(c) A stationary policy µ∗ is optimal if and only if


µ∗ (x) ∈ arg min g(x, u)+J ∗ f (x, u) ,
∀ x ∈ X.
u∈U(x)

(13)
(d) If U is a metric space and the sets


Uk (x, λ) = u ∈ U (x) | g(x, u) + Jk f (x, u) ≤ λ
(14)
are compact for all x ∈ X, λ ∈ ℜ, and k, where {Jk } is
the sequence generated by VI [cf. Eq. (5)] starting from
J0 ≡ 0, then there exists at least one optimal stationary
policy, and we have Jk → J ∗ .

Compactness assumptions such as the one of part (d) above,
were originally given in [9], [10], and in [29]. They have been
used in several other works, such as [3], [11], Prop. 4.1.9. In
particular, the condition of part (d) holds when U (x) is a finite
set for all x ∈ X. The condition of part (d) also holds when
X = ℜn , and for each x ∈ X, the set

u ∈ U (x) | g(x, u) ≤ λ

is a compact subset of ℜm , for all λ ∈ ℜ, and g and f are
continuous in u. The proof consists of showing by induction
that the VI iterates Jk have compact level sets and hence are
lower semicontinuous.
Let us also note a recent result of H. Yu and the author [35],
where it was shown that J ∗ is the unique solution of Bellman’s
equation within the class of all functions J ∈ E + (X) that
satisfy
0 ≤ J ≤ cJ ∗
for some c > 0,
(15)

(we refer to [35] for discussion and references to antecedents
of this result). Moreover it was shown that VI converges to
J ∗ starting from any function satisfying the condition
J ∗ ≤ J ≤ cJ ∗

for some c > 0,

and under the compactness conditions of Prop. 4(d), starting
from any J that satisfies Eq. (15). The same paper and a related
paper [5] discuss extensively PI algorithms for stochastic
nonnegative cost problems.
For deterministic problems, there has been substantial research in the adaptive dynamic programming literature, regarding the validity of Bellman’s equation and the uniqueness of

its solution, as well as the attendant questions of convergence
of VI and PI. In particular, infinite horizon deterministic
optimal control for both discrete-time and continuous-time
systems has been considered since the early days of DP in the
works of Bellman. For continuous-time problems the questions
discussed in the present paper involve substantial technical
difficulties, since the analog of the (discrete-time) Bellman
equation (4) is the steady-state form of the (continuoustime) Hamilton-Jacobi-Bellman equation, a nonlinear partial
differential equation the solution and analysis of which is
in general very complicated. A formidable difficulty is the
potential lack of differentiability of the optimal cost function,
even for simple problems such as time-optimal control of
second order linear systems to the origin.
The analog of VI for continuous-time systems essentially
involves the time integration of the Hamilton-Jacobi-Bellman
equation, and its analysis must deal with difficult issues of stability and convergence to a steady-state solution. Nonetheless
there have been proposals of continuous-time PI algorithms,
in the early papers [26], [23], [28], [34], and the thesis [6], as
well as more recently in several works; see e.g., the book [32],
the survey [18], and the references quoted there. These works
also address the possibility of value function approximation,
similar to other approximation-oriented methodologies such
as neurodynamic programming [4] and reinforcement learning
[31], which consider primarily discrete-time systems. For
example, among the restrictions of the PI method, is that it
must be started with a stabilizing controller; see for example
the paper [23], which considered linear-quadratic continuoustime problems, and showed convergence to the optimal policy
of the PI algorithm, assuming that an initial stabilizing linear
controller is used. By contrast, no such restriction is needed in
the PI methodology of the present paper; questions of stability
are addressed only indirectly through the finiteness of the
values J ∗ (x) and Assumption 1.
For discrete-time systems there has been much research,
both for VI and PI algorithms. For a selective list of recent
references, which themselves contain extensive lists of other
references, see the book [32], the papers [19], [16], [17], [22],
[33], the survey papers in the edited volumes [27] and [21],
and the special issue [20]. Some of these works relate to
continuous-time problems as well, and in their treatment of
algorithmic convergence, typically assume that X and U are
Euclidean spaces, as well as continuity and other conditions
on g, special structure of the system, etc. It is beyond our
scope to provide a detailed survey of the state-of-the-art of
the VI and PI methodology in the context of adaptive DP.
However, it should be clear that the works in this field involve
more restrictive assumptions than our corresponding results
of Props. 1-3. Of course, these works also address questions
that we do not, such as issues of stability of the obtained
controllers, the use of approximations, etc. Thus the results
of the present work may be viewed as new in that they
rely on very general assumptions, yet do not address some
important practical issues. The line of analysis of the present
paper, which is based on general results of Markovian decision
problem theory and abstract forms of dynamic programming,
is also different from the lines of analysis of works in adaptive

5

DP, which make heavy use of the deterministic character of
the problem and control theoretic methods such as Lyapunov
stability.
Still there is a connection between our line of analysis and
Lyapunov stability. In particular, if π ∗ is an optimal controller,
i.e., Jπ∗ = J ∗ , then for every x0 ∈ Xf , the state sequence
{xk } generated using π ∗ and starting from x0 remains within
Xf and satisfies J ∗ (xk ) ↓ 0. This can be seen by writing
J ∗ (x0 ) =

k−1
X
t=0


g xt , µ∗t (xt ) + J ∗ (xk ),

k = 1, 2, . . . ,

ˆ k ) = 0 for all sufficiently large k, we have
J(x
)
(
k−1
X

ˆ k) +
lim sup J(x
g xt , µt (xt )
k→∞

t=0

= lim

k→∞

(k−1
X
t=0

= Jπ (x0 ).


g xt , µt (xt )

)

By combining the last two relations, we obtain
ˆ 0 ) ≤ Jπ (x0 ),
J ∗ (x0 ) ≤ J(x

∀ x0 ∈ Xf , π ∈ ΠT,x0 .

∗

and using the facts g ≥ 0 and J (x0 ) < ∞. Thus an optimal
controller, restricted to the subset Xf , may be viewed as a
Lyapunov-stable controller where the Lyapunov function is J ∗ .
On the other hand, existence of a “stable” controller does
not necessarily imply that J ∗ is real-valued. In particular, it
may not be true that if the generated sequence {xk } by an
optimal controller starting from some x0 converges to Xs ,
then we have J ∗ (x0 ) < ∞. The reason is that the cost per
stage g may not decrease fast enough as we approach Xs . As
an example, let
X = {0} ∪ {1/m | m : is a positive integer},
with Xs = {0}, and assume that there is a unique controller,
which moves from 1/m to 1/(m + 1) with incurred cost 1/m.
Then we have J ∗ (x) = ∞ for all x 6= 0, despite the fact
that the controller is “stable” in the sense that it generates a
sequence {xk } converging to 0 starting from every x0 6= 0.

Taking the infimum over π ∈ ΠT,x0 and using Eq. (16), it
ˆ 0 ) for all x0 ∈ Xf . Also for x0 ∈
follows that J ∗ (x0 ) = J(x
/
ˆ 0 ) = ∞ [since J ∗ ≤ Jˆ by Prop.
Xf , we have J ∗ (x0 ) = J(x
ˆ
4(a)], so we obtain J ∗ = J.
Proof of Prop. 2: (a) Suppose that J0 ∈ J and J0 ≥ J ∗ .
Starting with J0 , let us apply the VI operation to both sides
of the inequality J0 ≥ J ∗ . Since J ∗ is a solution of Bellman’s
equation and VI has a monotonicity property that maintains
the direction of functional inequalities, we see that J1 ≥ J ∗ .
Continuing similarly, we obtain Jk ≥ J ∗ for all k. Moreover,
we clearly have Jk (x) = 0 for all x ∈ Xs , so Jk ∈ J for
all k. We now argue that since Jk is produced by k steps
of VI starting from J0 , it is the optimal cost function of the
k-stage version of the problem with terminal cost function
J0 . Therefore, we have for every x0 ∈ X and policy π =
{µ0 , µ1 , . . .},
∗

III. P ROOFS

OF THE

J (x0 ) ≤ Jk (x0 ) ≤ J0 (xk )+

M AIN R ESULTS

t=0

Let us denote for all x ∈ X,

ΠT,x = π ∈ Π | π terminates from x ,

and note the following key implication of Assumption 1:
J ∗ (x) =

inf

π∈ΠT ,x

Jπ (x),

∀ x ∈ Xf .

(16)

In the subsequent arguments, the significance of policies
that terminate starting from some initial state x0 is that the
corresponding generated sequences {xk } satisfy J(xk ) = 0
for all J ∈ J and k sufficiently large.
Proof of Prop. 1: Let Jˆ ∈ J be a solution of the Bellman
equation (11), so that

ˆ
J(x)
≤ g(x, u)+ Jˆ f (x, u) ,
∀ x ∈ X, u ∈ U (x), (17)

ˆ For any x0 ∈ Xf and policy
while by Prop. 4(a), J ∗ ≤ J.
π = {µ0 , µ1 , . . .} ∈ ΠT,x0 , we have by using repeatedly Eq.
(17),
ˆ 0 ) ≤ J(x
ˆ k) +
J ∗ (x0 ) ≤ J(x

k−1
X
t=0

k−1
X


g xt , µt (xt ) , k = 1, 2, . . . ,

where {xk } is the state sequence generated starting from x0
and using π. Also, since π ∈ ΠT,x0 and hence xk ∈ Xs and


g xt , µt (xt ) , k = 1, 2, . . . ,

where {xt } is the state sequence generated starting from x0
and using π. If x0 ∈ Xf and π ∈ ΠT,x0 , we have xk ∈ Xs
and J0 (xk ) = 0 for all sufficiently large k, so that
)
(
k−1
X

lim sup J0 (xk ) +
g xt , µt (xt )
k→∞

t=0

= lim

k→∞

(k−1
X
t=0

= Jπ (x0 ).

)

g xt , µt (xt )

By combining the last two relations, we obtain
J ∗ (x0 ) ≤ lim inf Jk (x0 ) ≤ lim sup Jk (x0 ) ≤ Jπ (x0 ),
k→∞

k→∞

for all x0 ∈ Xf and π ∈ ΠT,x0 . Taking the infimum over π ∈
ΠT,x0 and using Eq. (16), it follows that limk→∞ Jk (x0 ) =
J ∗ (x0 ) for all x0 ∈ Xf . Since for x0 ∈
/ Xf , we have J ∗ (x0 ) =
∗
Jk (x0 ) = ∞, we obtain Jk → J .
(b) Let {Jk } be the VI sequence generated starting from some
function J ∈ J. By the monotonicity of the VI operation, {Jk }
lies between the sequence of VI iterates starting from the zero
function [which converges to J ∗ from below by Prop. 4(d)],
and the sequence of VI iterates starting from J0 = max{J, J ∗ }
[which converges to J ∗ from above by part (a)].

6

Proof of Prop. 3: If µ is a stationary policy and µ̄ satisfies
the policy improvement equation


µ̄(x) ∈ arg min g(x, u) + Jµ f (x, u) ,
x ∈ X,
u∈U(x)

[cf. Eq. (7)], we have for all x ∈ X,


Jµ (x) = g x, µ(x) + Jµ f x, µ(x)


≥ min g(x, u) + Jµ f (x, u)
u∈U(x)


= g x, µ̄(x) + Jµ f x, µ̄(x) ,

(18)

where the first equality follows from Prop. 4(b) and the second
equality follows from the definition of µ̄. Let us fix x and let
{xk } be the sequence generated starting from x and using µ.
By
 repeatedly applying Eq. (18), we see that the sequence
J˜k (x) defined by
J˜0 (x) = Jµ (x),


J˜1 (x) = Jµ (x1 ) + g x, µ̄(x) ,

and more generally,

J˜k (x) = Jµ (xk ) +

k−1
X
t=0


g xt , µ̄(xt ) ,

k = 1, 2, . . . ,

is monotonically nonincreasing. Thus, using also Eq. (18), we
have


Jµ (x) ≥ min g(x, u) + Jµ f (x, u)
u∈U(x)

= J˜1 (x)
≥ J˜k (x),

for all x ∈ X and k ≥ 1. This implies that


Jµ (x) ≥ min g(x, u) + Jµ f (x, u)
u∈U(x)

≥ lim J˜k (x)
k→∞
(

Jµ (xk ) +

= lim

k→∞

≥ lim

k→∞

k−1
X
t=0

= Jµ̄ (x),

k−1
X
t=0

)

g xt , µ̄(xt )


g xt , µ̄(xt )

where the last inequality follows since Jµ ≥ 0. In conclusion,
we have


Jµ (x) ≥ inf
g(x, u) + Jµ f (x, u) ≥ Jµ̄ (x), x ∈ X.
u∈U(x)

Using µk and µk+1 in place of µ and µ̄ in the preceding
relation, we obtain for all x ∈ X,


g(x, u) + Jµk f (x, u) ≥ Jµk+1 (x).
Jµk (x) ≥ inf
u∈U(x)

(19)
Thus the sequence {Jµk } generated by PI converges monotonically to some function J∞ ∈ E + (X), i.e., Jµk ↓ J∞ .
Moreover, by taking the limit as k → ∞ in Eq. (19), we have
the two relations


x ∈ X,
J∞ (x) ≥ inf
g(x, u) + J∞ f (x, u) ,
u∈U(x)

and

g(x, u) + Jµk f (x, u) ≥ J∞ (x),

x ∈ X, u ∈ U (x).

We now take the limit in the second relation as k → ∞, then
the infimum over u ∈ U (x), and then combine with the first
relation, to obtain


x ∈ X.
g(x, u) + J∞ f (x, u) ,
J∞ (x) = inf
u∈U(x)

Thus J∞ is a solution of Bellman’s equation, satisfying J∞ ∈
J (since Jµk ∈ J and Jµk ↓ J∞ ), so by the uniqueness result
of Prop. 1, we have J∞ = J ∗ .
IV. D ISCUSSION , S PECIAL C ASES ,

AND

E XTENSIONS

In this section we elaborate on our main results and we derive
easily verifiable conditions under which our assumptions hold.
A. Conditions that Imply Assumption 1
Consider Assumption 1. As noted in Section I, it holds when
X and U are finite, a terminating policy exists from every
x, and all cycles of the state transition graph have positive
length. For the case where X is infinite, let us assume that
X is a normed space with norm denoted k · k, and say that
π asymptotically terminates from x if the sequence {xk }
generated starting from x and using π converges to Xs in
the sense that
lim dist(xk , Xs ) = 0,
k→∞

where dist(x, Xs ) denotes the minimum distance from x to
Xs ,
dist(x, Xs ) = inf kx − yk,
x ∈ X.
y∈Xs

The following proposition provides readily verifiable conditions that guarantee Assumption 1.
Proposition 5. Let the cost nonnegativity condition (2) and
stopping set conditions (8)-(9) hold, and assume further the
following:
(1) For every x ∈ Xf and ǫ > 0, there exits a policy π that
asymptotically terminates from x and satisfies
Jπ (x) ≤ J ∗ (x) + ǫ.
(2) For every ǫ > 0, there exists a δǫ > 0 such that for each
x ∈ Xf with
dist(x, Xs ) ≤ δǫ ,
there is a policy π that terminates from x and satisfies
Jπ (x) ≤ ǫ.
Then Assumption 1 holds.
Proof: Fix x ∈ Xf and ǫ > 0. Let π be a policy
that asymptotically terminates from x, and satisfies Jπ (x) ≤
J ∗ (x) + ǫ, as per condition (1). Starting from x, this policy
will generate a sequence {xk } such that for some index k̄ we
have
dist(xk̄ , Xs ) ≤ δǫ ,

7

so by condition (2), there exists a policy π̄ that terminates
from xk̄ and is such that Jπ̄ (xk̄ ) ≤ ǫ. Consider the policy π ′
that follows π up to index k̄ and follows π̄ afterwards. This
policy terminates from x and satisfies
Jπ′ (x) = Jπ,k̄ (x) + Jπ̄ (xk̄ ) ≤ Jπ (x) + Jπ̄ (xk̄ ) ≤ J ∗ (x) + 2ǫ,
where Jπ,k̄ (x) is the cost incurred by π starting from x up to
reaching xk̄ .
Condition (1) of the preceding proposition requires that
for states x ∈ Xf , the optimal cost J ∗ (x) can be achieved
arbitrarily closely with policies that asymptotically terminate
from x. Problems for which condition (1) holds are those
involving a cost per stage that is strictly positive outside of
Xs . More precisely, condition (1) holds if for each δ > 0 there
exists ǫ > 0 such that
inf g(x, u) ≥ ǫ,

∀ x ∈ X such that dist(x, Xs ) ≥ δ.

u∈U(x)

(20)
Then for any x and policy π that does not asymptotically
terminate from x, we will have Jπ (x) = ∞, so that if
x ∈ Xf , all policies π with Jπ (x) < ∞ must be asymptotically terminating from x. In applications, condition (1)
is natural and consistent with the aim of steering the state
towards the terminal set Xs with finite cost. Condition (2)
is a “controllability” condition implying that the state can be
steered into Xs with arbitrarily small cost from a starting state
that is sufficiently close to Xs .
Example 4 (Linear System Case). Consider a linear system

unstable (the instability of the system is important for the
purpose of this example). Then it can be verified that the
quadratic function J(x) = (a2 − 1)x2 , which belongs to
J, also solves Bellman’s equation. This is a case where the
algebraic Riccati equation associated with the problem has
two nonnegative solutions because there is no cost on the
state, and a standard observability condition for uniqueness
of solution of the Riccati equation is violated.
If on the other hand, in addition to (a)-(c), we assume that
for some positive scalars γ, p, we have inf u∈U(x) g(x, u) ≥
γkxkp for all x ∈ ℜn , then J ∗ (x) > 0 for all x 6= 0 [cf. Eq.
(9)], while condition (1) of Prop. 5 is satisfied as well [cf. Eq.
(20)]. Then by Prop. 5, Assumption 1 holds, and Bellman’s
equation has a unique solution within J.
There are straightforward extensions of the conditions of
the preceding example to a nonlinear system. Note that even
for a controllable system, it is possible that there exist states
from which the terminal set cannot be reached, because U (x)
may imply constraints on the magnitude of the control vector.
Still the preceding analysis allows for this case.

B. An Optimistic Form of PI
Let us consider a variant of PI where policies are evaluated
inexactly, with a finite number of VIs. In particular, this
algorithm starts with some J0 ∈ E(X), and generates a
sequence of cost function and policy pairs {Jk , µk } as follows:
Given Jk , we generate µk according to

xk+1 = Axk + Buk ,
where A and B are given matrices, with the terminal set being
the origin, i.e., Xs = {0}. We assume the following:
(a) X = ℜn , U = ℜm , and there is an open sphere R
centered at the origin such that U (x) contains R for all
x ∈ X.
(b) The system is controllable, i.e., one may drive the system
from any state to the origin within at most n steps
using suitable controls, or equivalently that the matrix
[B AB · · · An−1 B] has rank n.
(c) g satisfies

∀ (x, u) ∈ V,
0 ≤ g(x, u) ≤ β kxkp + kukp ,
where V is some open sphere centered at the origin,
β, p are some positive scalars, and k · k is the standard
Euclidean norm.

Then condition (2) of Prop. 5 is satisfied, while x = 0 is costfree and absorbing [cf. Eq. (8)]. Still, however, in the absence
of additional assumptions, there may be multiple solutions to
Bellman’s equation within J.
As an example, consider the scalar system xk+1 = axk +uk
with X = U (x) = ℜ, and the quadratic cost g(x, u) = u2 .
Then Bellman’s equation has the form

J(x) = min u2 + J(ax + u) ,
x ∈ ℜ,
u∈ℜ

and it is seen that the optimal cost function, J ∗ (x) ≡ 0,
is a solution. Let us assume that a > 1 so the system is

µk (x) ∈ arg min

u∈U(x)



g(x, u) + Jk f (x, u) ,

x ∈ X,
(21)

and then we obtain Jk+1 with mk ≥ 1 VIs using µk :
Jk+1 (x0 ) = Jk (xmk ) +

mX
k −1
t=0


g xt , µk (xt ) ,

x0 ∈ X,

(22)
where {xt } is the sequence generated using µk and starting
from x0 , and mk are arbitrary positive integers. Here J0 is a
function in J that is required to satisfy
J0 (x) ≥

inf

u∈U(x)



g(x, u)+J0 f (x, u) , ∀ x ∈ X, u ∈ U (x).

(23)
For example J0 may be equal to the cost function of some
stationary policy, or be the function that takes the value 0
for x ∈ Xs and ∞ at x ∈
/ Xs . Note that when mk ≡ 1
the method is equivalent to VI, while the case mk = ∞
corresponds to the standard PI considered earlier. In practice,
the most effective value of mk may be found experimentally,
with moderate values mk > 1 usually working best. We refer
to the textbooks [25] and [11] for discussions of this type of
inexact PI algorithm (in [25] it is called “modified” PI, while
in [11] it is called “optimistic” PI).
Proposition 6 (Convergence of Optimistic PI). Let Assumption 1 hold. For the PI algorithm (21)-(22), where J0 belongs
to J and satisfies the condition (23), we have Jk ↓ J ∗ .

8

Proof: We have for all x ∈ X,


J0 (x) ≥ inf
g(x, u) + J0 f (x, u)
u∈U(x)


= g x, µ0 (x) + J0 f (x, µ0 (x))
≥ J1 (x)



≥ g x, µ0 (x) + J1 f (x, µ0 (x))


≥ inf
g(x, u) + J1 f (x, u)
u∈U(x)


= g x, µ1 (x) + J1 f (x, µ1 (x))
≥ J2 (x),

where the first inequality is the condition (23), the second and
third inequalities follow because of the monotonicity of the
m0 value iterations (22) for µ0 , and the fourth inequality follows from the policy improvement equation (21). Continuing
similarly, we have


Jk (x) ≥ inf
g(x, u) + Jk f (x, u) ≥ Jk+1 (x),
u∈U(x)

for all x ∈ X and k. Moreover, since J0 ∈ J, we have Jk ∈ J
for all k. Thus Jk ↓ J∞ for some J∞ ∈ J, and similar to the
proof of Prop. 3, it follows that J∞ is a solution of Bellman’s
equation. Hence, by the uniqueness result of Prop. 1, we have
J∞ = J ∗ .
C. Minimax Control to a Terminal Set of States

Our analysis can be readily extended to minimax problems
with a terminal set of states. Here the system is
xk+1 = f (xk , uk , wk ),

k = 0, 1, . . . ,

where wk is the control of an antagonistic opponent that aims
to maximize the cost function. We assume that wk is chosen
from a given set W to maximize the sum of costs per stage,
which are assumed nonnegative:
0 ≤ g(x, u, w) ≤ ∞,

x ∈ X, U ∈ U (x), w ∈ W.

We wish to choose a policy π = {µ0 , µ1 , . . .} to minimize
the cost function
Jπ (x0 ) =

sup
wk ∈W
k=0,1,...

lim

k→∞

k
X
t=0

assuming also that the control process stops once the state
enters the set Xs . Here w is a disturbance described by set
membership (w ∈ W ), and the objective is to reach the set Xs
in the minimum guaranteed number of steps. The set Xf is
the set of states for which Xs is guaranteed to be reached in a
finite number of steps. Another related problem is reachability
of a target tube, where for a given set X̂,
(
0 if x ∈ X̂,
g(x, u, w) =
1 if x ∈
/ X̂,
and the objective is to find the initial states starting from
which we can guarantee to keep all future states within X̂.
These two reachability problems were first formulated and
analyzed as part of the author’s Ph.D. thesis research [7], and
the subsequent paper [8]. In fact the reachability algorithms
given in these works are essentially special cases of the VI
algorithm of the present paper, starting with appropriate initial
functions J0 .
To extend our results to the general form of the minimax
problem described above, we need to adapt the definition of
termination. In particular, given a state x, in the minimax
context we say that a policy π terminates from x if there
exists an index k̄ [which depends on (π, x)] such that the
sequence {xk }, which is generated starting from x and using
π, satisfies xk̄ ∈ Xs for all sequences {w0 , . . . , wk̄−1 } with
wt ∈ W for all t = 0, . . . k̄−1. Then Assumption 1 is modified
to reflect this new definition of termination, and our results can
be readily extended, with Props. 1, 2, 3, and 6, and their proofs,
holding essentially as stated. The main adjustment needed is
to replace expressions of the forms

g(x, u) + J f (x, u)

and

J(xk ) +

k−1
X

g(xt , ut )

t=0


g xk , µk (xk ), wk ,


where xk , µk (xk ) is a state-control sequence corresponding
to π and the sequence {w0 , w1 , . . .}. We assume that there is
a termination set Xs , the states of which are cost-free and
absorbing, i.e.,
g(x, u, w) = 0,

problem that is closely related is reachability of a target set
in minimum time, which is obtained for
(
0 if x ∈ Xs ,
g(x, u, w) =
1 if x ∈
/ Xs ,

x = f (x, u, w),

for all x ∈ Xs , u ∈ U (x), w ∈ W , and that all states outside
Xs have strictly positive optimal cost, so that

Xs = x ∈ X | J ∗ (x) = 0 .

The finite-state version of this problem has been discussed in
[13], under the name robust shortest path planning, for the
case where g can take both positive and negative values. A

in these proofs with


sup g(x, u, w) + J f (x, u, w)
w∈W

and

sup
wt ∈W
t=0,...,k−1

(

J(xk ) +

k−1
X

)

g(xt , ut , wt ) ,

t=0

respectively; see also [14] for a more abstract view of such
lines of argument.
V. C ONCLUDING R EMARKS
In this paper we have considered problems of deterministic
optimal control to a terminal set of states subject to very
general assumptions. Under reasonably practical conditions,
we have established the uniqueness of solution of Bellman’s

9

equation, and the convergence of value and policy iteration algorithms, even when there are states with infinite optimal cost.
Our analysis bypasses the need for assumptions involving the
existence of globally stabilizing controllers, which guarantee
that the optimal cost function J ∗ is real-valued. This generality
makes our results a convenient starting point for analysis of
problems involving additional assumptions, and perhaps cost
function approximations.
While we have restricted attention to undiscounted problems, the line of analysis of the present paper applies also to
discounted problems with one-stage cost function g that may
be unbounded from above. Similar but more favorable results
can be obtained, thanks to the presence of the discount factor;
see the author’s paper [14], which contains related analysis
for stochastic and minimax, discounted and undiscounted
problems, with nonnegative cost per stage.
The results for these problems, and the results of the present
paper, have a common ancestry. They fundamentally draw
their validity from notions of regularity, which were developed
in the author’s abstract DP monograph [12] and were extended
recently in [14]. Let us describe the regularity idea briefly,
and its connection to the analysis of this paper. Given a set of
functions S ∈ E + (X), we say that a collection C of policystate pairs (π, x0 ), with π ∈ Π and x0 ∈ X, is S-regular if
for all (π, x0 ) ∈ C and J ∈ S, we have
)
(
k−1
X

g xt , µt (xt ) .
Jπ (x0 ) = lim J(xk ) +
k→∞

t=0

In words, for all (π, x0 ) ∈ C, Jπ (x0 ) can be obtained in
the limit by VI starting from any J ∈ S. The favorable
properties with respect to VI of an S-regular collection C can
be translated into interesting properties relating to solutions of
Bellman’s equation and convergence of VI. In particular, the
optimal cost function over the set of policies {π | (π, x) ∈ C},
JC∗ (x) =

inf

{π | (π,x)∈C}

Jπ (x),

x ∈ X,

under appropriate problem-dependent assumptions, is the
unique solution of Bellman’s equation within the set J ∈
S | J ≥ JC∗ , and can be obtained by VI starting from any J
within that set (see [14]).
Within the deterministic optimal control context of this
paper, it works well to choose C to be the set of all (π, x)
such that x ∈ Xf and π is terminating starting from x, and
to choose S to be J, as defined by Eq. (10). Then, in view of
Assumption 1, we have JC∗ = J ∗ , and the favorable properties
of JC∗ are shared by J ∗ . For other types of problems different
choices of C may be appropriate, and corresponding results
relating to the uniqueness of solutions of Bellman’s equation
and the validity of value and policy iteration may be obtained;
see [14].

Dimitri P. Bertsekas studied engineering at the
National Technical University of Athens, Greece,
obtained his MS in electrical engineering at the
George Washington University, Wash. DC in 1969,
PLACE
and his Ph.D. in system science in 1971 at the
PHOTO
Massachusetts Institute of Technology (M.I.T.).
HERE
Dr. Bertsekas has held faculty positions with
the Engineering-Economic Systems Dept., Stanford
University (1971-1974) and the Electrical Engineering Dept. of the University of Illinois, Urbana (19741979). Since 1979 he has been teaching at the
Electrical Engineering and Computer Science Department of M.I.T., where
he is currently McAfee Professor of Engineering. He consults regularly with
private industry and has held editorial positions in several journals. His
research has spanned several fields, including optimization, control, largescale and distributed computation, and data communication networks, and
is closely tied to his teaching and book authoring activities. He has written
numerous research papers, and sixteen books, several of which are used as
textbooks in M.I.T. classes.
Professor Bertsekas was awarded the INFORMS 1997 Prize for Research
Excellence in the Interface Between Operations Research and Computer
Science for his book “Neuro-Dynamic Programming” (co-authored with John
Tsitsiklis), the 2001 ACC John R. Ragazzini Education Award, the 2009
INFORMS Expository Writing Award, the 2014 ACC Richard E. Bellman
Control Heritage Award, the 2014 Khachiyan Prize for Life-Time Accomplishments in Optimization, and the SIAM/MOS 2015 George B. Dantzig
Prize. In 2001 he was elected to the United States National Academy of
Engineering.
Dr. Bertsekas’ recent books are “Dynamic Programming and Optimal
Control: 4th Edition” (2012), “Abstract Dynamic Programming” (2013), and
“Convex Optimization Algorithms” (2015), all published by Athena Scientific.

VI. R EFERENCES
[1] Bertsekas, D. P., and Rhodes, I. B., 1971. “On the Minimax
Reachability of Target Sets and Target Tubes,” Automatica,
Vol. 7, pp. 233-241.
[2] Bertsekas, D. P., and Shreve, S. E., 1978.
Stochastic Optimal Control: The Discrete Time Case,
Academic Press, N. Y.; may be downloaded from
http://web.mit.edu/dimitrib/www/home.html
[3] Bertsekas, D. P., and Tsitsiklis, J. N., 1991. “An Analysis
of Stochastic Shortest Path Problems,” Math. of Operations
Research, Vol. 16, pp. 580-595.
[4] Bertsekas, D. P., and Tsitsiklis, J. N., 1996. NeuroDynamic Programming, Athena Scientific, Belmont, MA.
[5] Bertsekas, D. P., and Yu, H., 2015. “Stochastic Shortest
Path Problems Under Weak Conditions,” Lab. for Information
and Decision Systems Report LIDS-2909, revision of March
2015, to appear in Math. of Operations Research.
[6] Beard, R. W., 1995. Improving the Closed-Loop Performance of Nonlinear Systems, Doctoral dissertation, Rensselaer
Polytechnic Institute.
[7] Bertsekas, D. P., 1971. “Control of Uncertain Systems
With a Set-Membership Description of the Uncertainty,” Ph.D.
Thesis, Dept. of EECS, MIT; may be downloaded from
http://web.mit.edu/dimitrib/www/publ.html.
[8] Bertsekas, D. P., 1972. “Infinite Time Reachability of
State Space Regions by Using Feedback Control,” IEEE Trans.
Automatic Control, Vol. AC-17, pp. 604-613.
[9] Bertsekas, D. P., 1975. “Monotone Mappings in Dynamic
Programming,” Proc. 1975 IEEE Conference on Decision and
Control, Houston, TX, pp. 20-25.
[10] Bertsekas, D. P., 1977. “Monotone Mappings with Application in Dynamic Programming,” SIAM J. on Control and
Optimization, Vol. 15, pp. 438-464.

10

[11] Bertsekas, D. P., 2012. Dynamic Programming and Optimal Control, Vol. II: Approximate Dynamic Programming,
Athena Scientific, Belmont, MA.
[12] Bertsekas, D. P., 2013. Abstract Dynamic Programming,
Athena Scientific, Belmont, MA.
[13] Bertsekas, D. P., 2014. “Robust Shortest Path Planning
and Semicontractive Dynamic Programming,” Lab. for Information and Decision Systems Report LIDS-P-2915, Feb. 2014
(revised Jan. 2015).
[14] Bertsekas, D. P., 2015. “Regular Policies in Abstract
Dynamic Programming,” Lab. for Information and Decision
Systems Report LIDS-3173, April 2015.
[15] Blackwell, D., 1965. “Positive Dynamic Programming,”
Proc. Fifth Berkeley Symposium Math. Statistics and Probability, pp. 415-418.
[16] Heydari, A., 2014. “Revisiting Approximate Dynamic
Programming and its Convergence,” IEEE Transactions on
Cybernetics, Vol. 44, pp. 2733-2743.
[17] Heydari, A., 2014. “Stabilizing Value Iteration With and
Without Approximation Errors,” available at arXiv:1412.5675.
[18] Jiang, Y., and Jiang, Z. P., 2013. “Robust Adaptive
Dynamic Programming for Linear and Nonlinear Systems: An
Overview,” Eur. J. Control, Vol. 19, pp. 417-425.
[19] Jiang, Y., and Jiang, Z. P., 2014. “Robust Adaptive Dynamic Programming and Feedback Stabilization of Nonlinear
Systems,” IEEE Trans. on Neural Networks and Learning
Systems, Vol. 25, pp. 882-893.
[20] Lewis, F. L., Liu, D., and Lendaris, G. G., 2008. Special
Issue on Adaptive Dynamic Programming and Reinforcement
Learning in Feedback Control, IEEE Trans. on Systems, Man,
and Cybernetics, Part B, Vol. 38, No. 4.
[21] Lewis, F. L., and Liu, D., (Eds), 2013. Reinforcement
Learning and Approximate Dynamic Programming for Feedback Control, Wiley, Hoboken, N. J.
[22] Liu, D., and Wei, Q., 2013. “Finite-Approximation-ErrorBased Optimal Control Approach for Discrete-Time Nonlinear
Systems, IEEE Transactions on Cybernetics, Vol. 43, pp. 779789.
[23] Kleinman, D. L., 1968. “On an Iterative Technique
for Riccati Equation Computations,” IEEE Trans. Automatic
Control, Vol. AC-13, pp. 114-115.
[24] Pallu de la Barriere, R., 1967. Optimal Control Theory,
Saunders, Phila; reprinted by Dover, N. Y., 1980.
[25] Puterman, M. L., 1994. Markov Decision Processes:
Discrete Stochastic Dynamic Programming, J. Wiley, N. Y.
[26] Rekasius, Z. V., 1964. “Suboptimal Design of Intentionally Nonlinear Controllers,” IEEE Trans. on Automatic
Control, Vol. 9, pp. 380-386.
[27] Si, J., Barto, A., Powell, W., and Wunsch, D., (Eds.)
2004. Learning and Approximate Dynamic Programming,
IEEE Press, N. Y.
[28] Saridis, G. N., and Lee, C.-S. G., 1979. “An Approximation Theory of Optimal Control for Trainable Manipulators,”
IEEE Trans. Syst., Man, Cybern., Vol. 9, pp. 152-159.
[29] Schal, M., 1975. “Conditions for Optimality in Dynamic
Programming and for the Limit of n-Stage Optimal Policies to

be Optimal,” Z. Wahrscheinlichkeitstheorie und Verw. Gebiete,
Vol. 32, pp. 179-196.
[30] Strauch, R., 1966. “Negative Dynamic Programming,”
Ann. Math. Statist., Vol. 37, pp. 871-890.
[31] Sutton, R. S., and Barto, A. G., 1998. Reinforcement
Learning, MIT Press, Cambridge, MA.
[32] Vrabie, D., Vamvoudakis, K. G., and Lewis, F. L., 2013.
Optimal Adaptive Control and Differential Games by Reinforcement Learning Principles, The Institution of Engineering
and Technology, London.
[33] Wei, Q., Wang, F. Y., Liu, D., and Yang, X., 2014. “FiniteApproximation-Error-Based Discrete-Time Iterative Adaptive
Dynamic Programming,” IEEE Transactions on Cybernetics,
Vol. 44, pp. 2820-2833.
[34] Werbos, P. J., 1992. “Approximate Dynamic Programming
for Real-Time Control and Neural Modeling,” in Handbook
of Intelligent Control (D. A. White and D. A. Sofge, eds.),
Multiscience Press.
[35] Yu, H., and Bertsekas, D. P., 2013. “A Mixed Value and
Policy Iteration Method for Stochastic Control with Universally Measurable Policies,” Lab. for Information and Decision
Systems Report LIDS-P-2905, MIT; to appear in Math. of
Operations Research.

