# A Version of the Euler Equation in Discounted Markov Decision Processes

Authors: H. Cruz-Suárez; G. Zacarías-Espinoza; V. Vázquez-Guevara
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

This paper deals with Markov decision processes (MDPs) on Euclidean spaces with an infinite horizon. An approach to study this kind of MDPs is using the dynamic programming technique (DP). Then the optimal value function is characterized through the value iteration functions. The paper provides conditions that guarantee the convergence of  maximizers of the value iteration functions to the optimal policy. Then, using the Euler equation and an envelope formula, the optimal solution of the optimal control problem is obtained. Finally, this theory is applied to a linear-quadratic control problem in order to find its optimal policy.


---

## Body

## 1. Introduction

This paper deals with the optimal control problem in discrete time and with an infinite horizon. This problem is presented with the help of the Markov decision processes (MDPs) theory. To describe the MDPs, it is necessary to provide a Markov control model. The components of the Markov control model are used to describe the dynamic of the system. In this way at each timet (t
=
0,1
,
…) the state of the system is affected by an admissible action. This sequence of actions is called a policy. The optimal control problem consists in determining an optimal policy, which is characterized through a performance criterion. In this paper, the infinite-horizon expected total discounted reward is considered.An approach for solving the optimal control problem is through the dynamic programming technique (DP) (see [1–4]). DP characterizes the optimal solution of the optimal control problem using a functional equation, known as the dynamic programming equation (see [1–4]). In the literature there exists conditions that guarantee the value iteration (VI) functions procedure, which is used to approximate the optimal value function of the optimal control problem. However, this technique has problems when the reward and/or dynamic have a complicated functional form (see [5, page 93]).An alternative for solving this problem is using the Euler Equation (EE), which is well known in the applications of MDPs to economic models. This equation is established and solved in this context (in some cases empirically) (see [6–13]).An iterative method for deterministic MDPs is presented in [14]. In this case, the EE is obtained in terms of the VI functions. Retaking this idea, this article presents an iterative method of finding the solution of EE in terms of the VI functions in stochastic MDPs.In this paper, the Euler equation is obtained using an envelope formula (see [15–17]) under interiority conditions of the VI functions. The envelope formula characterizes the performance criterion derivative with respect to the initial state of the system. The performance criterion derivative is important in analyzing the behavior of the Markov control process. Also, in [18], a general study about the performance sensitivities in the policy space is presented. In this context, two performance sensitivity formulas are studied: one for performance derivatives at any policy in the policy space and the other one for performance differences between any two policies in the policy space.The technique proposed in this paper is used as follows. Firstly, EE is applied to obtain the VI functions. Secondly, applying the envelope formula, the maximizers of the VI functions are obtained. Then using the maximizers convergence to the optimal policy, the optimal control problem is solved. This procedure is exemplified by a linear quadratic problem.The paper is organized as follows: in Section2, the theory of MDPs necessary for subsequent sections is presented. In Section 3, some conditions on the Markov Control Model are presented to ensure both the differentiability of the VI functions and the optimal value function. These conditions guarantee the validity of a version of the EE for the VI. Finally, in Section 4, a linear quadratic problem is presented to illustrate the theory.


## 2.   Markov Decision Process

A discrete-time markov control model is a quintuple(
X
,
A
,
{
A
(
x
)
∣
x
∈
X
}
,
Q
,
r
), where X is the state space, A is the action space, A
(
x
) is the set of feasible actions in the state x
∈
X, Q is a transition law and r
:
𝕂
→
ℝ is the one-step reward function (see [3]). X and A are (nonempty) Borel spaces with the Borel σ-algebras ℬ
(
X
) and ℬ
(
A
), respectively. Q
(
·
∣
·
) is a stochastic kernel on X given 𝕂, where 𝕂
:
=
{
(
x
,
a
)
∣
x
∈
X
,
a
∈
A
(
x
)
}, and r is a measurable function.Consider a Markov control model and, for eacht
=
0,1
,
…, define the space ℍ
t of admissible histories up to time t as ℍ
0
=
X, and ℍ
t
=
𝕂
×
ℍ
t
-
1, for t
=
1,2
,
….Apolicy is a sequence π
=
{
π
t
} of stochastic kernels π
t on the action space A given ℍ
t. The set of policies will be denoted by Π.Let𝔽 be the set of decision functions or measurable selectors, that is, the set of all measurable functions f
:
X
→
A such that f
(
x
)
∈
A
(
x
) for all x
∈
X.A sequence{
f
t
} of functions f
t
∈
𝔽 is called a Markov policy. A stationary policy is a Markov policy π
=
{
f
t
} such that f
t
=
f for all t
=
0,1
,
2
,
…, with f
∈
𝔽, and it will be denoted by f (see [3]).Given the initial statex
0
=
x
∈
X, and any policy π
∈
Π, there is a probability measure P
x
π on the space (
Ω
,
ℱ
), with Ω
:
=
(
X
×
A
)
∞ and ℱ, the product σ-algebra (see [3]). The corresponding expectation operator will be denoted by E
x
π. The stochastic process (
(
Ω
,
ℱ
,
P
x
π
)
,
{
x
t
}
) is called a discrete-time Markov decision process.Thetotal expected discounted reward is defined as
(2.1)
v
(
π
,
x
)
:
=
E
x
π
[
∑
t
=
0
∞
α
t
r
(
x
t
,
a
t
)
]
,
π
∈
Π and x
∈
X, where α
∈
(
0,1
) is called the discount factor.Definition 2.1.
A policyπ
*
∈
Π is optimal, if for each x
∈
X,
(2.2)
v
(
π
*
,
x
)
=
sup
π
∈
Π
v
(
π
,
x
)
.
The function defined by
(2.3)
V
(
x
)
=
sup
π
∈
Π
v
(
π
,
x
)
,
x
∈
X, will be called the optimal value function.The optimal control problem consists in determining an optimal policy.


### 2.1. Dynamic Programming

Definition 2.2.
A measurable functionλ
:
X
→
ℝ is said to be a solution to the optimal equation (OE) if it satisfies(2.4)
λ
(
x
)
=
sup
a
∈
A
(
x
)
{
r
(
x
,
a
)
+
α
∫
X
λ
(
y
)
Q
(
d
y
∣
x
,
a
)
}
,x
∈
X
.Assumption 2.3.
(a) The one-step reward functionr is nonpositive, upper semicontinuous (u.s.c), and sup-compact on 𝕂. (r is a sup-compact function if the set {
a
∈
A
(
x
)
∣
r
(
x
,
a
)
≥
γ
} is compact for every x
∈
X and γ
∈
ℝ.)
(b)  The transition lawQ is strongly continuous.
(c)  There exists a policyπ such that v
(
π
,
x
)
>
-
∞, for each x
∈
X.Definition 2.4.
The value iteration (VI) functions are defined as follows:(2.5)
v
n
(
x
)
=
sup
a
∈
A
(
x
)
{
r
(
x
,
a
)
+
α
∫
X
v
n
-
1
(
y
)
Q
(
d
y
∣
x
,
a
)
}
,
for all x
∈
X and n
=
1,2
,
…, with v
0
(
x
)
=
0.The following theorem is well-known in the literature of MDPs (see, [1–4]). The proof can be consulted in (see [3, page 46]).Theorem 2.5.
Suppose that Assumption2.3 holds. Then
(a) The optimal value functionV is a solution of the OE (see Definition 2.2).
(b) There existsf
∈
𝔽 such that
(2.6)
V
(
x
)
=
r
(
x
,
f
(
x
)
)
+
α
∫
X
V
(
y
)
Q
(
d
y
∣
x
,
f
(
x
)
)
.
(c) For everyx
∈
X, v
n
(
x
)
→
V
(
x
), when n
→
∞.Remark 2.6.
Under Assumption2.3, it is possible to demonstrate that for each n
=
1,2
,
…, there exists a stationary policy f
n
∈
𝔽 such that
(2.7)
v
n
(
x
)
=
r
(
x
,
f
n
(
x
)
)
+
α
∫
X
v
n
-
1
(
y
)
Q
(
d
y
∣
x
,
f
n
(
x
)
)
,
x
∈
X (see [3, page. 27, 28]).


## 2.1. Dynamic Programming

Definition 2.2.
A measurable functionλ
:
X
→
ℝ is said to be a solution to the optimal equation (OE) if it satisfies(2.4)
λ
(
x
)
=
sup
a
∈
A
(
x
)
{
r
(
x
,
a
)
+
α
∫
X
λ
(
y
)
Q
(
d
y
∣
x
,
a
)
}
,x
∈
X
.Assumption 2.3.
(a) The one-step reward functionr is nonpositive, upper semicontinuous (u.s.c), and sup-compact on 𝕂. (r is a sup-compact function if the set {
a
∈
A
(
x
)
∣
r
(
x
,
a
)
≥
γ
} is compact for every x
∈
X and γ
∈
ℝ.)
(b)  The transition lawQ is strongly continuous.
(c)  There exists a policyπ such that v
(
π
,
x
)
>
-
∞, for each x
∈
X.Definition 2.4.
The value iteration (VI) functions are defined as follows:(2.5)
v
n
(
x
)
=
sup
a
∈
A
(
x
)
{
r
(
x
,
a
)
+
α
∫
X
v
n
-
1
(
y
)
Q
(
d
y
∣
x
,
a
)
}
,
for all x
∈
X and n
=
1,2
,
…, with v
0
(
x
)
=
0.The following theorem is well-known in the literature of MDPs (see, [1–4]). The proof can be consulted in (see [3, page 46]).Theorem 2.5.
Suppose that Assumption2.3 holds. Then
(a) The optimal value functionV is a solution of the OE (see Definition 2.2).
(b) There existsf
∈
𝔽 such that
(2.6)
V
(
x
)
=
r
(
x
,
f
(
x
)
)
+
α
∫
X
V
(
y
)
Q
(
d
y
∣
x
,
f
(
x
)
)
.
(c) For everyx
∈
X, v
n
(
x
)
→
V
(
x
), when n
→
∞.Remark 2.6.
Under Assumption2.3, it is possible to demonstrate that for each n
=
1,2
,
…, there exists a stationary policy f
n
∈
𝔽 such that
(2.7)
v
n
(
x
)
=
r
(
x
,
f
n
(
x
)
)
+
α
∫
X
v
n
-
1
(
y
)
Q
(
d
y
∣
x
,
f
n
(
x
)
)
,
x
∈
X (see [3, page. 27, 28]).


## 3. Differentiability in MDPs

### 3.1. Notation and Preliminaries

LetX and Y be Euclidean spaces and consider the following notation: C
2
(
X
,
Y
) denotes the set of functions l
:
X
→
Y with a continuous second derivative (when X
=
Y, C
2
(
X
,
Y
) will be denoted by C
2
(
X
) and in some cases it will be written only as C
2). Let Γ
:
X
×
Y
→
ℝ be a measurable function such that Γ
∈
C
2
(
X
×
Y
,
ℝ
). Γ
x, and Γ
y denote the partial derivative of Γ for x and y, respectively. The notations for the second partial derivatives of Γ are Γ
x
x, Γ
x
y, Γ
y
x and Γ
y
y.For any setC
⊂
X, a point x
∈
C is called an interior point of C if there exists an open set U such that x
∈
U
⊂
C. The interior of C is the set of all interior points of C denoted by int
(
C
).The set-value mappingΘ from X to Y is said to be(a)
nondecreasing, ifx
,
z
∈
X with x
<
z then Θ
(
x
)
⊆
Θ
(
z
),
(b)
convex, ifx
,
z
∈
X and β
∈
[
0,1
], then β
a
+
(
1
-
β
)
a
~
∈
Θ
(
β
x
+
(
1
-
β
)
z
), with a
∈
Θ
(
x
) and a
~
∈
Θ
(
z
).Letϒ
:
𝕂
→
ℝ be a measurable function. Define υ
:
X
→
ℝ  by
(3.1)
υ
(
x
)
:
=
sup
a
∈
Θ
(
x
)
ϒ
(
x
,
y
)
,
x
∈
X.The proof of the following lemma is similar to the proof of Theorem 1 in [16].Lemma 3.1.
Suppose that(a)
ϒ
∈
C
2
(
int
(
𝕂
)
;
ℝ
), furthermore ϒ
y
y
(
x
,
·
) is negative definite, for every x
∈
X;
(b)
for eachx
∈
X, argmaxϒ
(
x
,
y
)
⊆
int
(
Θ
(
x
)
).
Then there exists a functionl
:
X
→
A such that υ
(
x
)
=
ϒ
(
x
,
l
(
x
)
), for every x
∈
X. Moreover l
∈
C
1
(
int
(
X
)
;
Y
) and ϒ
∈
C
2
(
int
(
X
)
;
ℝ
).Remark 3.2.
Observe that (a) implies thatΛ
(
x
,
·
) is a strictly concave function, for each x
∈
X. Then the maximizer l
:
X
→
A is unique.
The proof of the following lemma can be consulted in [19], Theorem 25.7, page 248.Lemma 3.3.
LetC
⊂
ℝ
n be an open and convex set. Let g
:
C
→
ℝ be a concave and differentiable function, and {
g
n
} be a sequence of differentiable, concave and real-valued functions on C, such that g
n
(
x
)
→
g
(
x
), when n
→
∞, for all x
∈
C. Then (3.2)
lim
n
→
∞
g
n
′
(
x
)
=
g
′
(
x
)
.


### 3.2. An Envelope Formula in MDPs

Let(
X
,
A
,
{
A
(
x
)
∣
x
∈
X
}
,
Q
,
r
) be a fixed Markov control model. Throughout this section it is assumed that Assumption 2.3 holds. Also, it is supposed that X
⊆
ℝ
n and A
⊆
ℝ
m are convex sets with nonempty interiors and X is partially ordered. It is considered that the set-valued mapping x
→
A
(
x
) is nondecreasing and convex, and A
(
x
) has nonempty interior, for each x
∈
X. Also, it is assumed that the transition law Q is given by a difference equation:
(3.3)
x
t
+
1
=
L
(
F
(
x
t
,
a
t
)
,
ξ
t
)
,
t
=
0,1
,
…, with a given initial state x
0
=
x
∈
X fixed, where {
ξ
t
} is a sequence of independent and identically distributed (iid) random variables, independent of x
0
=
x
∈
X and taking values in a Borel space S
⊂
ℝ
k. Let ξ be a generic element of the sequence {
ξ
t
}. The density of ξ is designated by Δ; L
:
X
′
×
S
→
X is a measurable function, with X
′
⊂
ℝ
m, and F
:
𝕂
→
X
′, is a measurable function too.Since Assumption2.3 is assumed, then Theorem 2.5 yields. Therefore, the optimal value function (see Definition 2.1) satisfies
(3.4)
V
(
x
)
=
sup
a
∈
A
(
x
)
{
r
(
x
,
a
)
+
α
E
[
V
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
}
,
and the VI functions (see Definition 2.4) satisfy
(3.5)
v
n
(
x
)
=
sup
a
∈
A
(
x
)
{
r
(
x
,
a
)
+
α
E
[
v
n
-
1
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
}
,
for each n
=
1,2
,
…, with v
0
(
x
)
:
=
0. In addition, by Theorem 2.5, there exists the optimal policy, which will be denoted by f. Furthermore, there exists the maximizer f
n of v
n for each n
=
1,2
,
… (see Remark 2.6).LetG
:
𝕂
→
ℝ be a function defined as
(3.6)
G
(
x
,
a
)
:
=
r
(
x
,
a
)
+
α
H
(
x
,
a
)
,
(
x
,
a
)
∈
𝕂, where
(3.7)
H
(
x
,
a
)
:
=
E
[
V
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
.DefineG
n
:
𝕂
→
ℝ by
(3.8)
G
n
(
x
,
a
)
:
=
r
(
x
,
a
)
+
α
E
[
v
n
-
1
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
,
for each n
=
1,2
,
…, with v
0
(
x
)
:
=
0 and (
x
,
a
)
∈
𝕂.Assumption 3.4.
(a)r is a strictly concave function and r
(
·
,
a
) is an increasing function on X for each a
∈
A fixed;
(b)L
(
·
,
s
) is a concave and increasing function, for each s
∈
S; F is a concave function, F
(
·
,
a
) is an increasing function on X, for each a
∈
A.Lemma 3.5.
Under Assumption3.4, it results that v
n is a strictly concave function and f
n is unique, for all n
=
1,2
,
…. Also, V is a strictly concave function and f is unique.Proof.
By Assumption3.4(a), it suffices to prove Condition C1 (see [20, Lemma 6.2]), which guarantees the result. Let Ψ
:
𝕂
×
S
→
X be defined by
(3.9)
Ψ
(
x
,
a
,
s
)
:
=
L
(
F
(
x
,
a
)
,
s
)
.
Then for eachs
∈
S, the function Ψ
(
·
,
·
,
s
) is concave in 𝕂 by Assumption 3.4(b). Indeed, since F is a concave function, then
(3.10)
F
(
β
(
x
,
a
)
+
(
1
-
β
)
(
y
,
b
)
)
≥
β
F
(
x
,
a
)
+
(
1
-
β
)
F
(
y
,
b
)
,
(
x
,
a
)
,
(
y
,
b
)
∈
𝕂 and β
∈
[
0,1
]. Furthermore, it is known that L
(
·
,
s
) is a concave and increasing function, for each s
∈
S, then
(3.11)
L
(
F
(
β
(
x
,
a
)
+
(
1
-
β
)
(
y
,
b
)
)
,
s
)
≥
β
L
(
F
(
x
,
a
)
,
s
)
+
(
1
-
β
)
L
(
F
(
y
,
b
)
,
s
)
.
From similar arguments, it can be shown that ifx
<
y, then Ψ
(
x
,
a
,
s
)
≤
Ψ
(
y
,
a
,
s
), for each s
∈
S and a
∈
A
(
y
). Then the result follows.Assumption 3.6.
(a)r
∈
C
2
(
int
(
𝕂
)
;
ℝ
) and r
a
a
(
x
,
·
) is negative definite for each x
∈
X;
(b)F
∈
C
2
(
int
(
𝕂
)
;
X
′
) and F
a
(
x
,
·
) is invertible, for each a
∈
A;
(c)L
(
·
,
s
)
∈
C
2
(
int
(
X
′
)
;
X
), for each s
∈
S. Besides, L
(
·
,
·
) has an inverse in the second variable R, such that R
(
·
,
s
)
∈
C
2
(
int
(
X
′
×
X
)
;
S
), and |
det
R
s
(
·
,
s
)
|
∈
C
2
(
int
(
X
′
)
;
ℝ
), for all s
∈
S, where, in this case, R
s denotes the derivative of R with respect to the second variable, and the determinant of R
s is denoted as det
R
s;
(d)Δ
∈
C
2
(
int
(
S
)
;
R
) and the interchange between derivatives and integrals is valid (see Remark 3.8).Lemma 3.7.
By Assumption3.6 it results that H
∈
C
2
(
int
(
𝕂
)
;
X
′
), with H defined in (3.7).Proof.
The proof is similar to the proof of Lemma 5 in [16]. Assumption 3.6 allows to express the stochastic kernel (see (3.3)) in the following form: for each measurable subset B of X and (
x
,
a
)
∈
𝕂,
(3.12)
Q
(
B
∣
(
x
,
a
)
)
=
Pr
(
s
∈
S
∣
L
(
F
(
x
,
a
)
,
s
)
)
=
Pr(
s
∈
S
∣
s
(
s
∈
R
(
F
(
x
,
a
)
,
B
)
)
(3.13)
=
∫
R
(
F
(
x
,
a
)
,
B
)
‍
Δ
(
u
)
d
u
.
Then for the change of variable theorem, it results that
(3.14)
Q
(
B
∣
(
x
,
a
)
)
=
∫
R
(
F
(
x
,
a
)
,
B
)
‍
Δ
(
R
(
F
(
x
,
a
)
,
u
)
)
|
det
R
s
(
F
(
x
,
a
)
,
u
)
|
d
u
.
It follows from (3.13) that H can be expressed as
(3.15)
H
(
x
,
a
)
=
∫
R
(
F
(
x
,
a
)
,
B
)
‍
V
(
u
)
Δ
(
R
(
F
(
x
,
a
)
,
u
)
)
|
det
R
s
(
F
(
x
,
a
)
,
u
)
|
d
u
.
Now, using Assumption3.6, the result follows.Remark 3.8.
In Lemma3.7, Assumption 3.6(d) was used to guarantee the differentiability of the second order of the integral ∫
‍
K
(
x
,
a
,
u
)
d
u, with respect to x or a, where
(3.16)
K
(
x
,
a
,
u
)
:
=
V
(
u
)
Δ
(
R
(
F
(
x
,
a
)
,
u
)
)
|
det
R
s
(
F
(
x
,
a
)
,
u
)
|
,
(
F
(
x
,
a
)
,
u
)
∈
int
(
X
′
×
X
). This condition can be verified in practice when the derivatives of K can be bounded in the following sense: for (
F
(
x
,
a
)
,
u
)
∈
int
(
X
′
×
X
), |
K
x
(
x
,
a
,
u
)
|
≤
k
1
(
a
,
u
),|
K
a
(
x
,
a
,
u
)
|
≤
k
2
(
x
,
u
), |
K
x
x
(
x
,
a
,
u
)
|
≤
k
3
(
a
,
u
), |
K
a
a
(
x
,
a
,
u
)
|
≤
k
4
(
a
,
u
), |
K
x
a
(
x
,
a
,
u
)
|
≤
k
1
(
a
,
u
), for some functions g
i integrable with respect to u, for i
=
1
,
…
,
5 (see Remark 10 in [16]).Assumption 3.9.
(a) The optimal policyf satisfies that f
(
x
)
∈
int
(
A
(
x
)
), for each x
∈
X;
(b) The sequence{
f
n
} of the maximizers of the VI functions satisfies that f
n
(
x
)
∈
int
(
A
(
x
)
), for each x
∈
X and n
=
1,2
,
….
DefineW by
(3.17)
W
(
x
,
a
)
:
=
[
r
x
-
r
a
F
a
-
1
F
x
]
(
x
,
a
)
,
(
x
,
a
)
∈
𝕂.Remark 3.10.
Assumption3.9 evidently holds; if A
(
x
) is open for every x
∈
X, then f
(
x
) (f
n
(
x
)) belongs to the interior of A
(
x
), x
∈
X. Also, in some particular cases (see [8, 16]), the interiority of f
(
x
) (f
n
(
x
)) is guaranteed by the mean value theorem.Theorem 3.11.
Under Assumptions3.4, 3.6, and 3.9(a), it results that f
∈
C
1
(
int
(
X
)
;
A
), V
∈
C
2
(
int
(
X
)
;
ℝ
) and for each x
∈
int
(
X
),
(3.18)
V
′
(
x
)
=
W
(
x
,
f
(
x
)
)
,
where W is defined in (3.17).Proof.
Letx
∈
int
(
X
) fixed. Note that Assumptions 3.4 and 3.6 imply that G
∈
C
2
(
int
(
𝕂
)
;
ℝ
) where G is defined in (3.6). Indeed, since Assumptions 3.4(a) and 3.6(a) hold, it is known that r
∈
C
2
(
int
(
𝕂
)
;
ℝ
) and r
a
a
(
x
,
·
) is negative definite. Moreover, Lemma 3.5 implies that H
(
x
,
a
)
=
E
[
V
(
L
(
F
(
x
,
a
)
,
ξ
)
)
] is a concave function, and by Lemma 3.7, it follows that H
∈
C
2
(
int
(
𝕂
)
;
ℝ
), obtaining that H
a
a
(
x
,
·
) is negative semidefinite (see [21, page 260]). Furthermore, by Assumption 3.9(a) and applying Lemma 3.1, it concludes that f
∈
C
1
(
int
(
X
)
;
A
) and V
∈
C
2
(
int
(
X
)
;
ℝ
).
On the other hand, it is obtained that(3.19)
G
a
(
x
,
a
)
=
r
a
(
x
,
a
)
+
α
E
[
V
′
(
L
(
F
(
x
,
a
)
,
ξ
)
)
L
′
(
F
(
x
,
a
)
,
ξ
)
]
F
a
(
x
,
a
)
,
for each a
∈
int
(
A
(
x
)
). Then, the first order condition and the invertibility of F
a (see Assumption 3.6(b)) imply that G
a
(
x
,
f
(
x
)
)
=
0, that is,
(3.20)
-
r
a
F
a
-
1
(
x
,
f
(
x
)
)
=
α
E
[
V
′
(
L
(
F
(
x
,
f
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
(
x
)
)
,
ξ
)
]
.
Moreover, since V satisfies (2.4) and f
∈
𝔽 is the optimal policy, then
(3.21)
V
(
x
)
=
G
(
x
,
f
(
x
)
)
.
Using the fact thatG
a
(
x
,
f
(
x
)
)
=
0, it is possible to obtain the following envelope formula:
(3.22)
V
′
(
x
)
=
G
x
(
x
,
f
(
x
)
)
+
G
a
(
x
,
f
(
x
)
)
f
′
(
x
)
,
=
G
x
(
x
,
f
(
x
)
)
.
Equivalently,
(3.23)
V
′
(
x
)
=
r
x
(
x
,
f
(
x
)
)
+
α
E
[
V
′
(
L
(
F
(
x
,
f
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
(
x
)
)
,
ξ
)
]
F
x
(
x
,
f
(
x
)
)
.
Finally, substituting (3.20) in (3.23), it follows that
(3.24)
V
′
(
x
)
=
W
(
x
,
f
(
x
)
)
.Theorem 3.12.
Under Assumptions3.4, 3.6 and 3.9(b), it results that f
n
∈
C
1
(
int
(
X
)
;
A
), v
n
∈
C
2
(
int
(
X
)
;
ℝ
), for each n
=
1,2
,
…. Furthermore,
(3.25)
v
n
′
(
x
)
=
W
(
x
,
f
n
(
x
)
)
,
for each x
∈
int
(
X
) and n
=
2,3
,
….Proof.
The proof will be made by induction. Letx
∈
int
(
X
) be fixed. Since
(3.26)
v
1
(
x
)
=
max
a
∈
A
(
x
)
G
1
(
x
,
a
)
,
where G
1 is defined in (3.8) and by Assumptions 3.4(a) and 3.6(a), it follows that G
1
∈
C
2
(
int
(
𝕂
)
;
ℝ
) and G
a
a
1
(
x
,
a
) is negative definite. By Assumption 3.9(b), it yields that f
1
(
x
)
∈
int
(
A
(
x
)
), and applying Lemma 3.1, it follows that f
1
∈
C
1
(
int
(
X
)
;
A
), v
1
∈
C
2
(
int
(
X
)
;
ℝ
). Straightforward computations allow to obtain that
(3.27)
v
1
′
(
x
)
=
G
x
1
(
x
,
f
1
(
x
)
)
.
Moreover, by Lemma 3.5 it is known that v
1 is strictly concave, then it is negative semidefinite (see [21, page 260]).
Letn
=
2, then
(3.28)
v
2
(
x
)
=
max
a
∈
A
(
x
)
G
2
(
x
,
a
)
,
where G
2 is defined in (3.8).
Sincer, L, F, v
1
∈
C
2, then G
2
∈
C
2 too. Moreover, Lemmas 3.5 and 3.7 imply that
(3.29)
H
2
(
x
,
a
)
:
=
E
[
v
1
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
is a concave function and H
2
∈
C
2. It follows that H
a
a
2
(
x
,
·
) is negative semidefinite.
Consequently,G
a
a
2 is negative definite. Now, since f
2
(
x
)
∈
int
(
A
(
x
)
) (see Assumption 3.9(b)), applying again Lemma 3.1, it follows that f
2
∈
C
1
(
int
(
X
)
;
A
), v
2
∈
C
2
(
int
(
X
)
;
ℝ
). Furthermore, the first order condition implies that G
a
2
(
x
,
f
2
(
x
)
)
=
0. By the invertibility of F
a (see Assumption 3.6(b)), it follows that
(3.30)
-
r
a
F
a
-
1
(
x
,
f
2
(
x
)
)
=
α
E
[
v
1
′
(
L
(
F
(
x
,
f
2
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
2
(
x
)
)
,
ξ
)
]
.
On the other hand,(3.31)
v
2
′
(
x
)
=
r
x
(
x
,
f
2
(
x
)
)
+
α
E
[
v
1
′
(
L
(
F
(
x
,
f
2
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
2
(
x
)
)
,
ξ
)
]
F
x
(
x
,
f
2
(
x
)
)
,
and substituting (3.30) in (3.31), it is obtained that
(3.32)
v
2
′
(
x
)
=
W
(
x
,
f
2
(
x
)
)
,
where W is defined in (3.17).
Now, suppose thatv
n
-
1
∈
C
2
(
int
(
X
)
;
ℝ
) with n
>
2. Using arguments similar to the case n
=
2, it is possible to demonstrate that f
n
∈
C
1
(
int
(
X
)
;
A
), v
n
∈
C
2
(
int
(
X
)
;
ℝ
) and
(3.33)
v
n
′
(
x
)
=
W
(
x
,
f
n
(
x
)
)
.Assumption 3.13.
For eachx
∈
X, the function W
(
x
,
·
) has a continuous inverse function, denoted by w.Theorem 3.14.
Under Assumptions3.4, 3.6, 3.9 and 3.13, it follows that
(3.34)
f
n
(
x
)
→
f
(
x
)
,
when n
→
∞, for each x
∈
int
(
X
).Proof.
Letx
∈
int
(
X
) fixed. It is known by Lemma 3.5 and Theorem 3.11 that the optimal value function V is concave and differentiable on int
(
X
). In addition, it is known that for each n
∈
ℕ, v
n is a concave and differentiable function on int
(
X
). Then from Lemma 3.3 it follows that
(3.35)
v
n
′
(
x
)
→
V
′
(
x
)
,
when n goes to ∞.
Now by Assumption3.13, it concludes that for n
=
2,3
,
…,
(3.36)
f
n
(
x
)
=
w
(
x
,
v
n
′
(
x
)
)
,
f
(
x
)
=
w
(
x
,
V
′
(
x
)
)
,
where f
n is a stationary policy of v
n and f is the optimal policy. Finally, the convergence is guaranteed by the continuity of w (see Assumption 3.13).


### 3.3. Euler Equation

Theorem 3.15.
Under Assumptions3.4, 3.6, 3.9, and 3.13 it follows that
(3.37)
v
n
′
(
x
)
=
r
x
(
x
,
w
(
x
,
v
n
′
(
x
)
)
)
+
α
E
[
v
n
-
1
′
(
L
(
F
(
x
,
w
(
x
,
v
n
′
(
x
)
)
)
,
ξ
)
)
L
′
(
F
(
x
,
w
(
x
,
v
n
′
(
x
)
)
)
,
ξ
)
]
F
x
(
x
,
w
(
x
,
v
n
′
(
x
)
)
)
,
for each x
∈
int
(
X
) and n
∈
ℕ, where w is the function given in Assumption 3.13.Proof.
Letx
∈
int
(
X
) be fixed. By Lemma 3.5 and Theorem 3.12, it is known that v
n
∈
C
2
(
int
(
X
)
;
ℝ
) and it is a concave function. Now, from the first order condition and the invertibility of F
a (see Assumption 3.6(b)), it follows that
(3.38)
-
r
a
F
a
-
1
(
x
,
f
n
(
x
)
)
=
α
E
[
v
n
-
1
′
(
L
(
F
(
x
,
f
n
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
n
(
x
)
)
,
ξ
)
]
.
Since
(3.39)
v
n
′
(
x
)
=
W
(
x
,
f
n
(
x
)
)
,
and using the invertibility of W
(
x
,
·
) (see Assumption 3.13), it follows that
(3.40)
f
n
(
x
)
=
w
(
x
,
v
n
′
(
x
)
)
.
Finally, substituting (3.40) in (3.38), (3.37) is obtained.Corollary 3.16.
The optimal value function satisfies(3.41)
V
′
(
x
)
=
r
x
(
x
,
w
(
x
,
V
′
(
x
)
)
)
+
α
E
[
V
′
(
L
(
F
(
x
,
w
(
x
,
V
′
(
x
)
)
)
,
ξ
)
)
L
′
(
F
(
x
,
w
(
x
,
V
′
(
x
)
)
)
,
ξ
)
]
F
x
(
x
,
w
(
x
,
V
′
(
x
)
)
)
,
for each x
∈
int
(
X
).Proof.
Letx
∈
int
(
X
) be fixed. It is known that the VI functions satisfy the Euler equation (3.37), so applying Lemma 3.3, it is obtained that
(3.42)
v
n
′
(
x
)
→
V
′
(
x
)
,
when n
→
∞. Also from Assumption 3.13, w is a continuous function. Then, when n goes to infinite in (3.37), it follows that the optimal value function satisfies (3.41).


## 3.1. Notation and Preliminaries

LetX and Y be Euclidean spaces and consider the following notation: C
2
(
X
,
Y
) denotes the set of functions l
:
X
→
Y with a continuous second derivative (when X
=
Y, C
2
(
X
,
Y
) will be denoted by C
2
(
X
) and in some cases it will be written only as C
2). Let Γ
:
X
×
Y
→
ℝ be a measurable function such that Γ
∈
C
2
(
X
×
Y
,
ℝ
). Γ
x, and Γ
y denote the partial derivative of Γ for x and y, respectively. The notations for the second partial derivatives of Γ are Γ
x
x, Γ
x
y, Γ
y
x and Γ
y
y.For any setC
⊂
X, a point x
∈
C is called an interior point of C if there exists an open set U such that x
∈
U
⊂
C. The interior of C is the set of all interior points of C denoted by int
(
C
).The set-value mappingΘ from X to Y is said to be(a)
nondecreasing, ifx
,
z
∈
X with x
<
z then Θ
(
x
)
⊆
Θ
(
z
),
(b)
convex, ifx
,
z
∈
X and β
∈
[
0,1
], then β
a
+
(
1
-
β
)
a
~
∈
Θ
(
β
x
+
(
1
-
β
)
z
), with a
∈
Θ
(
x
) and a
~
∈
Θ
(
z
).Letϒ
:
𝕂
→
ℝ be a measurable function. Define υ
:
X
→
ℝ  by
(3.1)
υ
(
x
)
:
=
sup
a
∈
Θ
(
x
)
ϒ
(
x
,
y
)
,
x
∈
X.The proof of the following lemma is similar to the proof of Theorem 1 in [16].Lemma 3.1.
Suppose that(a)
ϒ
∈
C
2
(
int
(
𝕂
)
;
ℝ
), furthermore ϒ
y
y
(
x
,
·
) is negative definite, for every x
∈
X;
(b)
for eachx
∈
X, argmaxϒ
(
x
,
y
)
⊆
int
(
Θ
(
x
)
).
Then there exists a functionl
:
X
→
A such that υ
(
x
)
=
ϒ
(
x
,
l
(
x
)
), for every x
∈
X. Moreover l
∈
C
1
(
int
(
X
)
;
Y
) and ϒ
∈
C
2
(
int
(
X
)
;
ℝ
).Remark 3.2.
Observe that (a) implies thatΛ
(
x
,
·
) is a strictly concave function, for each x
∈
X. Then the maximizer l
:
X
→
A is unique.
The proof of the following lemma can be consulted in [19], Theorem 25.7, page 248.Lemma 3.3.
LetC
⊂
ℝ
n be an open and convex set. Let g
:
C
→
ℝ be a concave and differentiable function, and {
g
n
} be a sequence of differentiable, concave and real-valued functions on C, such that g
n
(
x
)
→
g
(
x
), when n
→
∞, for all x
∈
C. Then (3.2)
lim
n
→
∞
g
n
′
(
x
)
=
g
′
(
x
)
.


## 3.2. An Envelope Formula in MDPs

Let(
X
,
A
,
{
A
(
x
)
∣
x
∈
X
}
,
Q
,
r
) be a fixed Markov control model. Throughout this section it is assumed that Assumption 2.3 holds. Also, it is supposed that X
⊆
ℝ
n and A
⊆
ℝ
m are convex sets with nonempty interiors and X is partially ordered. It is considered that the set-valued mapping x
→
A
(
x
) is nondecreasing and convex, and A
(
x
) has nonempty interior, for each x
∈
X. Also, it is assumed that the transition law Q is given by a difference equation:
(3.3)
x
t
+
1
=
L
(
F
(
x
t
,
a
t
)
,
ξ
t
)
,
t
=
0,1
,
…, with a given initial state x
0
=
x
∈
X fixed, where {
ξ
t
} is a sequence of independent and identically distributed (iid) random variables, independent of x
0
=
x
∈
X and taking values in a Borel space S
⊂
ℝ
k. Let ξ be a generic element of the sequence {
ξ
t
}. The density of ξ is designated by Δ; L
:
X
′
×
S
→
X is a measurable function, with X
′
⊂
ℝ
m, and F
:
𝕂
→
X
′, is a measurable function too.Since Assumption2.3 is assumed, then Theorem 2.5 yields. Therefore, the optimal value function (see Definition 2.1) satisfies
(3.4)
V
(
x
)
=
sup
a
∈
A
(
x
)
{
r
(
x
,
a
)
+
α
E
[
V
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
}
,
and the VI functions (see Definition 2.4) satisfy
(3.5)
v
n
(
x
)
=
sup
a
∈
A
(
x
)
{
r
(
x
,
a
)
+
α
E
[
v
n
-
1
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
}
,
for each n
=
1,2
,
…, with v
0
(
x
)
:
=
0. In addition, by Theorem 2.5, there exists the optimal policy, which will be denoted by f. Furthermore, there exists the maximizer f
n of v
n for each n
=
1,2
,
… (see Remark 2.6).LetG
:
𝕂
→
ℝ be a function defined as
(3.6)
G
(
x
,
a
)
:
=
r
(
x
,
a
)
+
α
H
(
x
,
a
)
,
(
x
,
a
)
∈
𝕂, where
(3.7)
H
(
x
,
a
)
:
=
E
[
V
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
.DefineG
n
:
𝕂
→
ℝ by
(3.8)
G
n
(
x
,
a
)
:
=
r
(
x
,
a
)
+
α
E
[
v
n
-
1
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
,
for each n
=
1,2
,
…, with v
0
(
x
)
:
=
0 and (
x
,
a
)
∈
𝕂.Assumption 3.4.
(a)r is a strictly concave function and r
(
·
,
a
) is an increasing function on X for each a
∈
A fixed;
(b)L
(
·
,
s
) is a concave and increasing function, for each s
∈
S; F is a concave function, F
(
·
,
a
) is an increasing function on X, for each a
∈
A.Lemma 3.5.
Under Assumption3.4, it results that v
n is a strictly concave function and f
n is unique, for all n
=
1,2
,
…. Also, V is a strictly concave function and f is unique.Proof.
By Assumption3.4(a), it suffices to prove Condition C1 (see [20, Lemma 6.2]), which guarantees the result. Let Ψ
:
𝕂
×
S
→
X be defined by
(3.9)
Ψ
(
x
,
a
,
s
)
:
=
L
(
F
(
x
,
a
)
,
s
)
.
Then for eachs
∈
S, the function Ψ
(
·
,
·
,
s
) is concave in 𝕂 by Assumption 3.4(b). Indeed, since F is a concave function, then
(3.10)
F
(
β
(
x
,
a
)
+
(
1
-
β
)
(
y
,
b
)
)
≥
β
F
(
x
,
a
)
+
(
1
-
β
)
F
(
y
,
b
)
,
(
x
,
a
)
,
(
y
,
b
)
∈
𝕂 and β
∈
[
0,1
]. Furthermore, it is known that L
(
·
,
s
) is a concave and increasing function, for each s
∈
S, then
(3.11)
L
(
F
(
β
(
x
,
a
)
+
(
1
-
β
)
(
y
,
b
)
)
,
s
)
≥
β
L
(
F
(
x
,
a
)
,
s
)
+
(
1
-
β
)
L
(
F
(
y
,
b
)
,
s
)
.
From similar arguments, it can be shown that ifx
<
y, then Ψ
(
x
,
a
,
s
)
≤
Ψ
(
y
,
a
,
s
), for each s
∈
S and a
∈
A
(
y
). Then the result follows.Assumption 3.6.
(a)r
∈
C
2
(
int
(
𝕂
)
;
ℝ
) and r
a
a
(
x
,
·
) is negative definite for each x
∈
X;
(b)F
∈
C
2
(
int
(
𝕂
)
;
X
′
) and F
a
(
x
,
·
) is invertible, for each a
∈
A;
(c)L
(
·
,
s
)
∈
C
2
(
int
(
X
′
)
;
X
), for each s
∈
S. Besides, L
(
·
,
·
) has an inverse in the second variable R, such that R
(
·
,
s
)
∈
C
2
(
int
(
X
′
×
X
)
;
S
), and |
det
R
s
(
·
,
s
)
|
∈
C
2
(
int
(
X
′
)
;
ℝ
), for all s
∈
S, where, in this case, R
s denotes the derivative of R with respect to the second variable, and the determinant of R
s is denoted as det
R
s;
(d)Δ
∈
C
2
(
int
(
S
)
;
R
) and the interchange between derivatives and integrals is valid (see Remark 3.8).Lemma 3.7.
By Assumption3.6 it results that H
∈
C
2
(
int
(
𝕂
)
;
X
′
), with H defined in (3.7).Proof.
The proof is similar to the proof of Lemma 5 in [16]. Assumption 3.6 allows to express the stochastic kernel (see (3.3)) in the following form: for each measurable subset B of X and (
x
,
a
)
∈
𝕂,
(3.12)
Q
(
B
∣
(
x
,
a
)
)
=
Pr
(
s
∈
S
∣
L
(
F
(
x
,
a
)
,
s
)
)
=
Pr(
s
∈
S
∣
s
(
s
∈
R
(
F
(
x
,
a
)
,
B
)
)
(3.13)
=
∫
R
(
F
(
x
,
a
)
,
B
)
‍
Δ
(
u
)
d
u
.
Then for the change of variable theorem, it results that
(3.14)
Q
(
B
∣
(
x
,
a
)
)
=
∫
R
(
F
(
x
,
a
)
,
B
)
‍
Δ
(
R
(
F
(
x
,
a
)
,
u
)
)
|
det
R
s
(
F
(
x
,
a
)
,
u
)
|
d
u
.
It follows from (3.13) that H can be expressed as
(3.15)
H
(
x
,
a
)
=
∫
R
(
F
(
x
,
a
)
,
B
)
‍
V
(
u
)
Δ
(
R
(
F
(
x
,
a
)
,
u
)
)
|
det
R
s
(
F
(
x
,
a
)
,
u
)
|
d
u
.
Now, using Assumption3.6, the result follows.Remark 3.8.
In Lemma3.7, Assumption 3.6(d) was used to guarantee the differentiability of the second order of the integral ∫
‍
K
(
x
,
a
,
u
)
d
u, with respect to x or a, where
(3.16)
K
(
x
,
a
,
u
)
:
=
V
(
u
)
Δ
(
R
(
F
(
x
,
a
)
,
u
)
)
|
det
R
s
(
F
(
x
,
a
)
,
u
)
|
,
(
F
(
x
,
a
)
,
u
)
∈
int
(
X
′
×
X
). This condition can be verified in practice when the derivatives of K can be bounded in the following sense: for (
F
(
x
,
a
)
,
u
)
∈
int
(
X
′
×
X
), |
K
x
(
x
,
a
,
u
)
|
≤
k
1
(
a
,
u
),|
K
a
(
x
,
a
,
u
)
|
≤
k
2
(
x
,
u
), |
K
x
x
(
x
,
a
,
u
)
|
≤
k
3
(
a
,
u
), |
K
a
a
(
x
,
a
,
u
)
|
≤
k
4
(
a
,
u
), |
K
x
a
(
x
,
a
,
u
)
|
≤
k
1
(
a
,
u
), for some functions g
i integrable with respect to u, for i
=
1
,
…
,
5 (see Remark 10 in [16]).Assumption 3.9.
(a) The optimal policyf satisfies that f
(
x
)
∈
int
(
A
(
x
)
), for each x
∈
X;
(b) The sequence{
f
n
} of the maximizers of the VI functions satisfies that f
n
(
x
)
∈
int
(
A
(
x
)
), for each x
∈
X and n
=
1,2
,
….
DefineW by
(3.17)
W
(
x
,
a
)
:
=
[
r
x
-
r
a
F
a
-
1
F
x
]
(
x
,
a
)
,
(
x
,
a
)
∈
𝕂.Remark 3.10.
Assumption3.9 evidently holds; if A
(
x
) is open for every x
∈
X, then f
(
x
) (f
n
(
x
)) belongs to the interior of A
(
x
), x
∈
X. Also, in some particular cases (see [8, 16]), the interiority of f
(
x
) (f
n
(
x
)) is guaranteed by the mean value theorem.Theorem 3.11.
Under Assumptions3.4, 3.6, and 3.9(a), it results that f
∈
C
1
(
int
(
X
)
;
A
), V
∈
C
2
(
int
(
X
)
;
ℝ
) and for each x
∈
int
(
X
),
(3.18)
V
′
(
x
)
=
W
(
x
,
f
(
x
)
)
,
where W is defined in (3.17).Proof.
Letx
∈
int
(
X
) fixed. Note that Assumptions 3.4 and 3.6 imply that G
∈
C
2
(
int
(
𝕂
)
;
ℝ
) where G is defined in (3.6). Indeed, since Assumptions 3.4(a) and 3.6(a) hold, it is known that r
∈
C
2
(
int
(
𝕂
)
;
ℝ
) and r
a
a
(
x
,
·
) is negative definite. Moreover, Lemma 3.5 implies that H
(
x
,
a
)
=
E
[
V
(
L
(
F
(
x
,
a
)
,
ξ
)
)
] is a concave function, and by Lemma 3.7, it follows that H
∈
C
2
(
int
(
𝕂
)
;
ℝ
), obtaining that H
a
a
(
x
,
·
) is negative semidefinite (see [21, page 260]). Furthermore, by Assumption 3.9(a) and applying Lemma 3.1, it concludes that f
∈
C
1
(
int
(
X
)
;
A
) and V
∈
C
2
(
int
(
X
)
;
ℝ
).
On the other hand, it is obtained that(3.19)
G
a
(
x
,
a
)
=
r
a
(
x
,
a
)
+
α
E
[
V
′
(
L
(
F
(
x
,
a
)
,
ξ
)
)
L
′
(
F
(
x
,
a
)
,
ξ
)
]
F
a
(
x
,
a
)
,
for each a
∈
int
(
A
(
x
)
). Then, the first order condition and the invertibility of F
a (see Assumption 3.6(b)) imply that G
a
(
x
,
f
(
x
)
)
=
0, that is,
(3.20)
-
r
a
F
a
-
1
(
x
,
f
(
x
)
)
=
α
E
[
V
′
(
L
(
F
(
x
,
f
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
(
x
)
)
,
ξ
)
]
.
Moreover, since V satisfies (2.4) and f
∈
𝔽 is the optimal policy, then
(3.21)
V
(
x
)
=
G
(
x
,
f
(
x
)
)
.
Using the fact thatG
a
(
x
,
f
(
x
)
)
=
0, it is possible to obtain the following envelope formula:
(3.22)
V
′
(
x
)
=
G
x
(
x
,
f
(
x
)
)
+
G
a
(
x
,
f
(
x
)
)
f
′
(
x
)
,
=
G
x
(
x
,
f
(
x
)
)
.
Equivalently,
(3.23)
V
′
(
x
)
=
r
x
(
x
,
f
(
x
)
)
+
α
E
[
V
′
(
L
(
F
(
x
,
f
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
(
x
)
)
,
ξ
)
]
F
x
(
x
,
f
(
x
)
)
.
Finally, substituting (3.20) in (3.23), it follows that
(3.24)
V
′
(
x
)
=
W
(
x
,
f
(
x
)
)
.Theorem 3.12.
Under Assumptions3.4, 3.6 and 3.9(b), it results that f
n
∈
C
1
(
int
(
X
)
;
A
), v
n
∈
C
2
(
int
(
X
)
;
ℝ
), for each n
=
1,2
,
…. Furthermore,
(3.25)
v
n
′
(
x
)
=
W
(
x
,
f
n
(
x
)
)
,
for each x
∈
int
(
X
) and n
=
2,3
,
….Proof.
The proof will be made by induction. Letx
∈
int
(
X
) be fixed. Since
(3.26)
v
1
(
x
)
=
max
a
∈
A
(
x
)
G
1
(
x
,
a
)
,
where G
1 is defined in (3.8) and by Assumptions 3.4(a) and 3.6(a), it follows that G
1
∈
C
2
(
int
(
𝕂
)
;
ℝ
) and G
a
a
1
(
x
,
a
) is negative definite. By Assumption 3.9(b), it yields that f
1
(
x
)
∈
int
(
A
(
x
)
), and applying Lemma 3.1, it follows that f
1
∈
C
1
(
int
(
X
)
;
A
), v
1
∈
C
2
(
int
(
X
)
;
ℝ
). Straightforward computations allow to obtain that
(3.27)
v
1
′
(
x
)
=
G
x
1
(
x
,
f
1
(
x
)
)
.
Moreover, by Lemma 3.5 it is known that v
1 is strictly concave, then it is negative semidefinite (see [21, page 260]).
Letn
=
2, then
(3.28)
v
2
(
x
)
=
max
a
∈
A
(
x
)
G
2
(
x
,
a
)
,
where G
2 is defined in (3.8).
Sincer, L, F, v
1
∈
C
2, then G
2
∈
C
2 too. Moreover, Lemmas 3.5 and 3.7 imply that
(3.29)
H
2
(
x
,
a
)
:
=
E
[
v
1
(
L
(
F
(
x
,
a
)
,
ξ
)
)
]
is a concave function and H
2
∈
C
2. It follows that H
a
a
2
(
x
,
·
) is negative semidefinite.
Consequently,G
a
a
2 is negative definite. Now, since f
2
(
x
)
∈
int
(
A
(
x
)
) (see Assumption 3.9(b)), applying again Lemma 3.1, it follows that f
2
∈
C
1
(
int
(
X
)
;
A
), v
2
∈
C
2
(
int
(
X
)
;
ℝ
). Furthermore, the first order condition implies that G
a
2
(
x
,
f
2
(
x
)
)
=
0. By the invertibility of F
a (see Assumption 3.6(b)), it follows that
(3.30)
-
r
a
F
a
-
1
(
x
,
f
2
(
x
)
)
=
α
E
[
v
1
′
(
L
(
F
(
x
,
f
2
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
2
(
x
)
)
,
ξ
)
]
.
On the other hand,(3.31)
v
2
′
(
x
)
=
r
x
(
x
,
f
2
(
x
)
)
+
α
E
[
v
1
′
(
L
(
F
(
x
,
f
2
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
2
(
x
)
)
,
ξ
)
]
F
x
(
x
,
f
2
(
x
)
)
,
and substituting (3.30) in (3.31), it is obtained that
(3.32)
v
2
′
(
x
)
=
W
(
x
,
f
2
(
x
)
)
,
where W is defined in (3.17).
Now, suppose thatv
n
-
1
∈
C
2
(
int
(
X
)
;
ℝ
) with n
>
2. Using arguments similar to the case n
=
2, it is possible to demonstrate that f
n
∈
C
1
(
int
(
X
)
;
A
), v
n
∈
C
2
(
int
(
X
)
;
ℝ
) and
(3.33)
v
n
′
(
x
)
=
W
(
x
,
f
n
(
x
)
)
.Assumption 3.13.
For eachx
∈
X, the function W
(
x
,
·
) has a continuous inverse function, denoted by w.Theorem 3.14.
Under Assumptions3.4, 3.6, 3.9 and 3.13, it follows that
(3.34)
f
n
(
x
)
→
f
(
x
)
,
when n
→
∞, for each x
∈
int
(
X
).Proof.
Letx
∈
int
(
X
) fixed. It is known by Lemma 3.5 and Theorem 3.11 that the optimal value function V is concave and differentiable on int
(
X
). In addition, it is known that for each n
∈
ℕ, v
n is a concave and differentiable function on int
(
X
). Then from Lemma 3.3 it follows that
(3.35)
v
n
′
(
x
)
→
V
′
(
x
)
,
when n goes to ∞.
Now by Assumption3.13, it concludes that for n
=
2,3
,
…,
(3.36)
f
n
(
x
)
=
w
(
x
,
v
n
′
(
x
)
)
,
f
(
x
)
=
w
(
x
,
V
′
(
x
)
)
,
where f
n is a stationary policy of v
n and f is the optimal policy. Finally, the convergence is guaranteed by the continuity of w (see Assumption 3.13).


## 3.3. Euler Equation

Theorem 3.15.
Under Assumptions3.4, 3.6, 3.9, and 3.13 it follows that
(3.37)
v
n
′
(
x
)
=
r
x
(
x
,
w
(
x
,
v
n
′
(
x
)
)
)
+
α
E
[
v
n
-
1
′
(
L
(
F
(
x
,
w
(
x
,
v
n
′
(
x
)
)
)
,
ξ
)
)
L
′
(
F
(
x
,
w
(
x
,
v
n
′
(
x
)
)
)
,
ξ
)
]
F
x
(
x
,
w
(
x
,
v
n
′
(
x
)
)
)
,
for each x
∈
int
(
X
) and n
∈
ℕ, where w is the function given in Assumption 3.13.Proof.
Letx
∈
int
(
X
) be fixed. By Lemma 3.5 and Theorem 3.12, it is known that v
n
∈
C
2
(
int
(
X
)
;
ℝ
) and it is a concave function. Now, from the first order condition and the invertibility of F
a (see Assumption 3.6(b)), it follows that
(3.38)
-
r
a
F
a
-
1
(
x
,
f
n
(
x
)
)
=
α
E
[
v
n
-
1
′
(
L
(
F
(
x
,
f
n
(
x
)
)
,
ξ
)
)
L
′
(
F
(
x
,
f
n
(
x
)
)
,
ξ
)
]
.
Since
(3.39)
v
n
′
(
x
)
=
W
(
x
,
f
n
(
x
)
)
,
and using the invertibility of W
(
x
,
·
) (see Assumption 3.13), it follows that
(3.40)
f
n
(
x
)
=
w
(
x
,
v
n
′
(
x
)
)
.
Finally, substituting (3.40) in (3.38), (3.37) is obtained.Corollary 3.16.
The optimal value function satisfies(3.41)
V
′
(
x
)
=
r
x
(
x
,
w
(
x
,
V
′
(
x
)
)
)
+
α
E
[
V
′
(
L
(
F
(
x
,
w
(
x
,
V
′
(
x
)
)
)
,
ξ
)
)
L
′
(
F
(
x
,
w
(
x
,
V
′
(
x
)
)
)
,
ξ
)
]
F
x
(
x
,
w
(
x
,
V
′
(
x
)
)
)
,
for each x
∈
int
(
X
).Proof.
Letx
∈
int
(
X
) be fixed. It is known that the VI functions satisfy the Euler equation (3.37), so applying Lemma 3.3, it is obtained that
(3.42)
v
n
′
(
x
)
→
V
′
(
x
)
,
when n
→
∞. Also from Assumption 3.13, w is a continuous function. Then, when n goes to infinite in (3.37), it follows that the optimal value function satisfies (3.41).


## 4. A Linear-Quadratic Model

Consider thatℝ
n
=
X
=
A
=
A
(
x
), for each x
∈
X. The dynamic of the system is given by
(4.1)
x
t
+
1
=
B
x
t
+
C
a
t
+
ξ
t
,
t
=
1,2
,
…, with x
0
=
x
∈
X given. B and C are invertible matrices of size n
×
n, {
ξ
t
} is a sequence of iid column random vectors with values in ℝ
n. Let ξ be a generic element of the sequence {
ξ
t
}, assume that ξ has a density Δ with Δ
∈
C
2, and E
(
ξ
) equals vector zero. Furthermore, it is assumed that if P is a symmetric negative definite matrix of size n
×
n, then E
[
ξ
T
P
ξ
] is finite. In addition, it is assumed that the interchange between derivatives and integrals is valid (see Remark 3.8). A particular case of this assumption can be found in [16, page 315].The reward function is given by(4.2)
r
(
x
,
a
)
=
x
T
Q
x
+
a
T
R
a
,
where x
T and a
T denote the transpose of vectors x and a; Q and R are symmetric matrices of size n
×
n, and both of them are negative definite.Lemma 4.1.
The linear quadratic model satisfies Assumption2.3.Proof.
Note that(4.3)
O
γ
x
:
=
{
a
∈
A
(
x
)
∣
x
T
Q
x
+
a
T
R
a
≥
γ
}
is a compact set, for each x
∈
X and γ
∈
ℝ. Indeed, let x
∈
X and γ
∈
ℝ. If any sequence {
a
n
} of O
γ
x satisfies x
T
Q
x
+
a
n
T
R
a
n
→
-
∞, then there is a contradiction. Therefore O
γ
x is a set bounded below. Moreover, since Q and R are negative definite, then O
γ
x is a set bounded above. In addition, if {
a
n
}
⊂
O
γ
x so that a
n
→
a, then by the continuity of r, it follows that r
(
x
,
a
)
≥
γ, implying that O
γ
x is a closed set. Therefore, the reward function r is sup-compact. Finally, note that r is a nonpositive and continuous function on 𝕂. So Assumption 2.3(a) holds.
On the other hand, letU
∈
ℬ
(
X
), then
(4.4)
Q
(
U
∣
x
t
=
x
,
a
t
=
a
)
=
Pr
(
x
t
+
1
∈
U
∣
x
t
=
x
,
a
t
=
a
)
=
∫
‍
I
U
(
B
x
+
C
a
)
Δ
(
s
)
d
s
,
where I
U denotes the indicator function of U. Since the density Δ is continuous, it is obtained that the transition law Q is weakly continuous, that is, Assumption 2.3(b) holds.
Finally, leth
∈
𝔽 be defined as
(4.5)
h
(
x
)
=
-
C
-
1
B
x
,
then the dynamic of the system is given by
(4.6)
x
t
=
B
x
t
-
1
+
C
h
(
x
t
-
1
)
+
ξ
t
-
1
=
ξ
t
-
1
,
for t
=
1,2
,
…, with x
0
=
x
∈
X.
It follows that(4.7)
E
x
h
[
x
t
T
Q
x
t
+
h
(
x
t
)
T
R
h
(
x
t
)
]
=
E
[
ξ
t
T
P
ξ
t
]
=
:
θ
,
where P
:
=
(
Q
+
(
C
-
1
B
)
T
R
(
C
-
1
B
)
).
Since{
ξ
t
} is i.i.d, then
(4.8)
v
(
h
,
x
)
=
θ
1
-
α
<
∞
,
where v is given by (2.1). Therefore, Assumption 2.3(c) holds.Lemma 4.2.
The linear quadratic problem satisfies Assumptions3.4, 3.6, 3.9, and 3.13.Proof.
It is easy to obtain thatr is a concave function and r
∈
C
2, implying Assumptions 3.4(a) and 3.6(a). Assumption 3.4(b) is satisfied using Condition C2 in [20]. Furthermore, observe that
(4.9)
F
(
x
,
a
)
=
B
x
t
+
C
a
t
,
(
x
,
a
)
∈
𝕂. Since C is an invertible matrix, then Assumption 3.6(b) holds.
In addition, note that(4.10)
L
(
y
,
s
)
=
y
+
s
,
(
y
,
s
)
∈
X
′
×
S. Then it follows that L has an inverse R in the second variable, which is
(4.11)
R
(
y
,
u
)
=
u
-
y
.
Therefore, Assumption 3.6(c) yields. Furthermore, since Δ
∈
C
2
,it results that Assumption 3.6(d) holds. On the other hand, Assumption 3.9 is satisfied since A
(
x
)
=
ℝ
nfor eachx
∈
X
.Finally, it is obtained
(4.12)
W
(
x
,
a
)
=
2
(
Q
x
-
(
(
R
C
-
1
B
)
T
)
-
1
a
)
,
where W is defined in (3.17), implying that the inverse of W
(
x
,
·
) is
(4.13)
w
(
x
,
z
)
=
(
(
R
C
-
1
B
)
T
)
-
1
(
Q
x
-
1
2
z
)
,
which is a continuous function. Therefore, Assumption 3.13 is satisfied.Lemma 4.3.
VI functions for the linear quadratic problem satisfy(4.14)
v
n
′
(
x
)
=
2
K
n
x
,
for each n
=
1,2
,
…, where
(4.15)
K
n
=
Q
+
α
B
T
(
K
n
-
1
-
K
n
-
1
C
(
R
+
C
T
K
n
-
1
C
)
-
1
C
T
K
n
-
1
)
B
,
with K
1
=
Q.Proof.
Observe that the validity of Theorem3.15 is guaranteed by Lemmas 4.1 and 4.2. Now, since Q and R are negative definite, then
(4.16)
v
1
(
x
)
=
x
T
Q
x
.
By Theorem3.15, it is known that v
2
(
x
) satisfies the Euler equation (3.37), and by (4.13), it follows that
(4.17)
v
2
′
(
x
)
=
2
Q
x
+
α
B
T
E
[
v
1
′
(
(
B
+
C
(
(
R
C
-
1
B
)
T
)
-
1
Q
)
x
-
1
2
C
(
(
R
C
-
1
B
)
T
)
-
1
v
2
′
(
x
)
+
ξ
)
]
.
Since v
1
′
(
x
)
=
2
Q
x and E
(
ξ
) is equal to zero vector, then
(4.18)
v
2
′
(
x
)
=
2
[
Q
+
α
B
T
Q
(
B
+
C
(
(
R
C
-
1
B
)
T
)
-
1
Q
)
]
x
-
α
B
T
Q
C
(
(
R
C
-
1
B
)
T
)
-
1
v
2
′
(
x
)
,
and by direct calculations, it is obtained that
(4.19)
v
2
′
(
x
)
=
2
K
2
x
,
where
(4.20)
K
2
=
Q
+
α
B
T
(
Q
-
Q
C
(
R
+
C
T
Q
C
)
-
1
C
T
Q
)
B
.
Now, suppose thatv
n
′
(
x
)
=
2
K
n
x for n
>
2, with K
n defined in (4.15). Then, by Theorem 3.15 and (4.13), it is known that
(4.21)
v
n
+
1
′
(
x
)
=
2
Q
x
+
α
B
T
E
[
v
n
′
(
(
B
+
C
(
(
R
C
-
1
B
)
T
)
-
1
Q
)
x
-
1
2
C
(
(
R
C
-
1
B
)
T
)
-
1
v
n
+
1
′
(
x
)
+
ξ
)
]
.
Then(4.22)
v
n
+
1
′
(
x
)
=
2
[
Q
+
α
B
T
K
n
(
B
+
C
(
(
R
C
-
1
B
)
T
)
-
1
Q
)
]
x
-
α
B
T
K
n
C
(
(
R
C
-
1
B
)
T
)
-
1
v
n
+
1
′
(
x
)
,
and using matrix algebra, it yields that
(4.23)
v
n
+
1
′
(
x
)
=
2
K
n
+
1
x
,
where K
n
+
1 satisfies (4.15).Lemma 4.4.
The optimal policy for the linear quadratic problem is(4.24)
f
(
x
)
=
-
α
(
R
+
C
T
K
C
)
-
1
C
T
K
B
x
,
where K satisfies
(4.25)
K
=
Q
+
α
B
T
(
K
-
K
C
(
R
+
C
T
K
C
)
-
1
C
T
K
)
B
.Proof.
Lemma4.3 and (4.13) allow to obtain
(4.26)
f
n
(
x
)
=
(
(
R
C
-
1
B
)
T
)
-
1
(
Q
-
K
n
)
x
,
for each n
=
1,2
,
… and x
∈
X. Moreover, the validity of Theorem 3.14 is guaranteed by Lemma 4.2, that is, f
n
(
x
)
→
f
(
x
), implying the convergence of the sequence {
K
n
} which, according to its definition in (4.15), guarantees that its limit, denoted by K, must satisfy (4.25). Finally using matrix algebra (4.24) is obtained.


## 5. Conclusion

In this paper a method to solve the optimal control problem is presented. This method is based on the use of the Euler equation. The procedure proposed to solve the optimal control problem is by means of an envelope formula and the use of the convergence of the maximizers of values iteration functions to a stationary optimal policy. Future work aims to study possible error bounds for approximating the maximizers toward the optimal policy.



---

*Source: 103698-2012-10-24.xml*