Information Technology Reference
In-Depth Information
But first we need a technical lemma.
[0, 1],
g
:
R
ₒ
Lemma 4.5
Let g
:
S
ₒ
[0, 1]
and f
:
R
ₒ
S be three functions
g
(
r
)
for every r
satisfying g
(
f
(
r
))
≤
∈
R. Then for every subdistribution ʘ over
Exp
ʘ
(
g
)
where ʔ denotes the subdistribution Img
ʘ
(
f
)
.
R, Exp
ʔ
(
g
)
≤
Proof
A straightforward calculation.
Proposition 4.4
If
R
,
ʘ
,
ₒ
R
is a resolution of a subdistribution ʔ, then for any
h
h
(
ʘ
)
.
reward vector h it holds that
V
min
(
ʔ
)
≤ V
Proof
Let
f
denote the resolving function. First we show by induction on
n
that for
every state
r
∈
R
h
,
n
min
(
f
(
r
))
h
,
n
(
r
)
.
V
≤ V
(4.14)
For
n
0, this is trivial. We consider the inductive step; note that by the previous
lemma, the inductive hypothesis implies that
Exp
ʓ
=
min
Exp
ʘ
V
h
,
n
h
,
n
V
≤
(4.15)
for any pair of subdistributions satisfying
ʓ
=
Img
ʘ
(
f
).
ˉ
−ₒ
R
ʘ
, then
f
(
r
)
ˉ
−ₒ
h
,
n
+
1
h
,
n
+
1
(
r
). A
If
r
, and thus
V
(
f
(
r
))
=
h
(
ˉ
)
= V
min
˄
ˉ
similar argument applies if
r
−ₒ
, that is
r
−ₒ
and
s
−ₒ
. So the remaining
ˉ
˄
−ₒ
R
ʘ
for some
ʘ
, and
r
possibility is that
r
−ₒ
, where we know
˄
−ₒ
f
(
r
)
Img
ʘ
(
f
).
˄
−ₒ
ʔ
}
h
,
n
min
)
h
,
n
+
1
V
(
f
(
r
))
=
min
{
Exp
ʔ
(
V
|
f
(
r
)
min
h
,
n
min
)
≤
Exp
ʓ
(
V
where
ʓ
denotes Img
ʘ
(
f
)
h
,
n
(
ʘ
)
≤ V
by induction and (
4.15
) above
h
,
n
+
1
(
r
)
= V
Now by continuity we have from (
4.14
) that
h
min
(
f
(
r
))
h
(
r
)
.
V
≤ V
(4.16)
The result now follows by the previous lemma, since if
R
,
ʘ
,
ₒ
R
is a res-
olution of a subdistribution
ʔ
with resolving function
f
then,
by definition,
ʔ
Our next result says that in any finitely branching computation structure, we can
find a resolution that realises the function
=
Img
ʘ
(
f
).
V
min
. Moreover this resolution will be
static.
Definition 4.8
A (static)
extreme policy
forapLTS
S
,
ʩ
˄
,
ₒ
is a partial function
ep
:
S
D
(
S
) satisfying:
ˉ
−ₒ
ˉ
−ₒ
(a)
s
implies
s
ep
(
s
)
˄
−ₒ
˄
−ₒ
Search WWH ::
Custom Search