Game Development Reference

In-Depth Information

1

2

1

2

1

2

1

2

1

2

v

1

2

1

2

1

2

1

2

1

2

d
1

d
2

d
3

d
4

d
5

e
1

e
2

e
3

e
4

e
5

v

s
1

s
2

s
3

s
4

s
5

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

Figure 5.4 An optimal maximising strategy may require infinite memory

branching) MDP
G
, then there is also an MD optimal maximising strategy

in
v
.

Claim (c) is not as trivial as it might seem. A naive idea of constructing

an optimal maximising MD strategy just by selecting
some
value-maximising

transition in every vertex does not work. To see this, consider the following

MDP, where
t
is the only target vertex:

v

u

t

Obviously,
val
(
v
)=
val
(
u
)=
val
(
t
) = 1, but the MD strategy which selects

the transitions
v

v
in the vertices
v
and
u
, respectively, is not

optimal maximising. Nevertheless, it is not hard to show that for every vertex

of
v ∈ V
there is a transition
v → v
such that the other outgoing transitions

of
v
can be safely removed without influencing the value in any vertex. This

result actually holds for all finitely branching stochastic games. Claim (c)

then follows immediately because if
V
is finite, then we can successively fix

such a transition in
every v

→

u
and
u

→

∈

V
.

Proposition 5.8

,
(
V
,V
♦
,V
)
, Prob
)
be a finitely branching

stochastic game with a reachability objective associated to a set T

Let G
=(
V,

→

⊆

V .For

v
such that the value of all u

every v

∈

V
there is a transition v

→

∈

V

Search Nedrilad ::

Custom Search