We have a Bellman equation and first we want to know if there exists a value function that satisfies the equation and second we want to know the properties of such a solution. In order to answer the question we will define a mapping which maps a function to another function, and a fixed point of the mapping is to be a solution. The mapping we discussed is a mapping on the set of functions, which is a bit abstract. So today we will look at the math review.
So first we consider a set,
S
⊂
R
l
{\displaystyle S\subset \mathbb {R} ^{l}}
, For us what it will be relevant to describe a sort of distance between any two points in a set. We will use the concept of a metric.
A metric is a function
ρ
:
S
×
S
→
R
{\displaystyle \rho :S\times S\to \mathbb {R} }
with the properties that it is non-negative,
ρ
(
x
,
y
)
≥
0
{\displaystyle \rho (x,y)\geq 0}
, symmetric,
ρ
(
x
,
y
)
=
ρ
(
y
,
x
)
{\displaystyle \rho (x,y)=\rho (y,x)}
, and satisfies the triangle inequality,
ρ
(
x
,
z
)
≤
ρ
(
x
,
y
)
+
ρ
(
y
,
z
)
{\displaystyle \rho (x,z)\leq \rho (x,y)+\rho (y,z)}
,
A common metric is euclidean distance,
ρ
E
(
x
,
y
)
=
∑
i
=
1
l
(
x
i
−
y
i
)
2
{\displaystyle \rho _{E}(x,y)={\sqrt {\sum _{i=1}^{l}(x_{i}-y_{i})^{2}}}}
, Another is
ρ
m
a
x
(
x
,
y
)
=
max
1
≤
i
≤
l
x
i
−
y
i
{\displaystyle \rho _{max}(x,y)=\max _{1\leq i\leq l}x_{i}-y_{i}}
,
A space , is a set of objects equipped with some general properties and structure
We may be interested in a metric space, a space with a metric such as,
(
S
,
ρ
)
{\displaystyle (S,\rho )}
where
S
{\displaystyle S}
is the set of all bounded rational functions, and
ρ
{\displaystyle \rho }
is some distance function. Once we have a metric space we can discuss convergence and continuity.
A sequence,
{
x
i
}
⊂
S
{\displaystyle \{x_{i}\}\subset S}
, converges to
x
{\displaystyle x}
,
x
i
→
x
{\displaystyle x_{i}\rightarrow x}
, if
∀
ϵ
>
0
,
∃
N
ϵ
{\displaystyle \forall \epsilon >0,\exists N_{\epsilon }}
s.t.
ρ
(
x
n
,
y
n
)
<
ϵ
{\displaystyle \rho (x_{n},y_{n})<\epsilon }
for
n
>
N
ϵ
{\displaystyle n>N_{\epsilon }}
,
A sequence ,
{
x
i
}
⊂
S
{\displaystyle \{x_{i}\}\subset S}
, is called a Cauchy sequence if
∀
ϵ
>
0
,
∃
N
ϵ
s
.
t
.
ρ
(
x
n
,
y
m
)
<
ϵ
{\displaystyle \forall \epsilon >0,\exists N_{\epsilon }s.t.\rho (x_{n},y_{m})<\epsilon }
for
n
,
m
>
N
ϵ
{\displaystyle n,m>N_{\epsilon }}
,
Question: does every Cauchy sequence converge?
The metric space,
(
S
,
ρ
)
{\displaystyle (S,\rho )}
is complete if every Cauchy sequence converges.
examples of completeness
edit
(
R
,
ρ
E
)
{\displaystyle (\mathbb {R} ,\rho _{E})}
is complete.
(
(
0
,
1
)
,
ρ
E
)
{\displaystyle ((0,1),\rho _{E})}
is not complete. Proof: let
x
n
=
1
n
+
2
{\displaystyle x_{n}={\frac {1}{n+2}}}
, So
{
x
n
}
{\displaystyle \{x_{n}\}}
os Cauchy, but does not converge to a point in our set
(
0
,
1
)
{\displaystyle (0,1)}
,
(
[
0
,
1
]
,
ρ
E
)
{\displaystyle ([0,1],\rho _{E})}
is complete. Are all closed sets complete? A closed subspace of a complete space is complete.
(
{
0
,
1
,
2
}
,
ρ
E
)
{\displaystyle (\{0,1,2\},\rho _{E})}
is complete.
A mappting
T
:
S
→
S
{\displaystyle T:S\rightarrow S}
is a contraction mapping on a metric space,
(
S
,
ρ
)
{\displaystyle (S,\rho )}
, if
∃
o
≥
β
<
1
{\displaystyle \exists o\geq \beta <1}
such that
ρ
(
t
x
,
T
y
)
≤
β
ρ
(
x
,
y
)
∀
x
,
y
∈
S
{\displaystyle \rho (tx,Ty)\leq \beta \rho (x,y)\forall x,y\in S}
, Sometimes we write
T
(
x
)
{\displaystyle T(x)}
instead of
T
X
{\displaystyle TX}
,
This means that any two points in our set,
S
{\displaystyle S}
, are mapped such that after the mapping the distance between the points shrinks.
examples of contraction mapping
edit
T
x
=
.9
x
{\displaystyle Tx=.9x}
is a contraction mapping on
[
(
0
,
1
]
,
ρ
E
)
{\displaystyle [(0,1],\rho _{E})}
,
Now we state the contraction mapping theorem .
Contraction mapping theorem
edit
If
(
S
,
ρ
)
{\displaystyle (S,\rho )}
is complete and
T
:
s
→
S
{\displaystyle T:s\rightarrow S}
is a contraction mapping, then
∃
!
x
∗
{\displaystyle \exists !x^{*}}
with
T
x
∗
=
x
∗
{\displaystyle Tx^{*}=x^{*}}
,
We will prove this theorem for a general metric space later on. However, we must remember that it is necessary for this proof that the space be complete.
Let us now look at a criteria to verify that a mapping is a contraction mapping.
Contraction Mapping criteria
edit
For
S
⊂
R
l
{\displaystyle S\subset \mathbb {R} ^{l}}
and
ρ
=
ρ
E
{\displaystyle \rho =\rho _{E}}
, Let
T
:
S
→
S
{\displaystyle T:S\rightarrow S}
satisfy the following two conditions:
(M, monotonic condition)
∀
x
=
(
x
1
,
x
2
,
…
,
x
l
)
∈
S
{\displaystyle \forall x=(x_{1},x_{2},\ldots ,x_{l})\in S}
and
y
=
(
y
1
,
y
2
,
…
,
y
l
)
∈
S
{\displaystyle y=(y_{1},y_{2},\ldots ,y_{l})\in S}
, and
T
=
(
T
1
,
T
2
,
…
,
T
l
{\displaystyle T=(T_{1},T_{2},\ldots ,T_{l}}
, if
x
i
≥
y
i
⇔
x
≥
y
{\displaystyle x_{i}\geq y_{i}\Leftrightarrow x\geq y}
then
T
i
x
≥
T
i
y
⇔
T
x
≥
T
y
{\displaystyle T_{i}x\geq T_{i}y\Leftrightarrow Tx\geq Ty}
,
(D, discout condition)
∀
x
=
(
x
1
,
x
2
,
…
,
x
l
)
∈
S
{\displaystyle \forall x=(x_{1},x_{2},\ldots ,x_{l})\in S}
, for
a
→
_
=
(
a
,
a
,
…
,
a
)
{\displaystyle {\underline {\vec {a}}}=(a,a,\ldots ,a)}
,
T
i
(
x
1
+
a
,
x
2
+
a
,
…
,
x
l
+
a
)
≤
T
i
(
x
1
,
x
2
,
…
,
x
l
)
+
β
a
∀
i
⇔
T
(
x
+
a
_
)
≤
T
X
+
β
a
_
{\displaystyle T_{i}(x_{1}+a,x_{2}+a,\ldots ,x_{l}+a)\leq T_{i}(x_{1},x_{2},\ldots ,x_{l})+\beta a\forall i\Leftrightarrow T(x+{\underline {a}})\leq TX+\beta {\underline {a}}}
.
Then
T
{\displaystyle T}
is a contraction mapping.