Farkas certificates and minimal witnesses
333
Remark 5.2. For any vector v ∈ R
n the support is defined as supp(v) = {i ∈
{1, ..., n} | v i > 0}, and analogously for the vector spaces R
S and R
M . As our
connection between subsystems of M and points in P
min (λ) is based on taking the
support, we restrict our attention to the subpolytope P
min
≥0 (λ) = P
min (λ) ∩ R
S
≥0 .
Notation 5.3. Given an MDP M = (S all , Act, s 0 , P) as in Setting 2.2 and a
subset R ⊆ M, where M also denotes the state-action pairs (compare with
Section 2). We let M R = (S
all , Act, s 0 , P
) be the subsystem where, roughly
speaking, the state-action pairs in R remain. More precisely, let
S
all = {s ∈ S | ∃α ∈ Act . (s, α) ∈ R} ∪ {goal, fail}
P
(s, α, t) =
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
P(s, α, t)
i f ( s, α) ∈ R and t ∈ S
all \ {fail}
1 −
t∈S
all \{fail} P(s, α, t) if (s, α) ∈ R and t = fail
1
i f ( s, α) /
∈ R, α ∈ Act(s) and t = fail
0
else
For R ⊆ S we set M R = M R for R
=
s∈R {s} × Act(s).
Theorem 5.4 (Farkas certificates yield witnesses). Let M be an MDP as
in Setting 2.2 and λ ∈ [0, 1]. Then for a set R ⊆ S the following statements are
equivalent:
(1) The subsystem M R is a witness for Pr
min
M,s0 (♦ goal) ≥ λ.
(2) There is a point p in P
min
≥0 (λ) such that supp(p) ⊆ R.
(3) There is a vertex v of P
min
≥0 (λ) such that supp(v) ⊆ R.
Moreover, for a set R ⊆ M the following statements are equivalent:
(a) The subsystem M R is a witness for Pr
max
M,s0 (♦ goal) ≥ λ.
(b) There is a point p in P
max (λ) such that supp(p) ⊆ R.
(c) There is a vertex v of P
max (λ) such that supp(v) ⊆ R.
One consequence of Theorem 5.4 is that every MD-scheduler S with Pr
S
s0 (♦ goal) ≥
λ corresponds to a point in P
max (λ), i.e. to a certificate for Pr
max
M,s0 (♦ goal) ≥ λ.
Corollary 5.5 (Detecting minimal witnesses by vertices of P). Let M =
(S all , Act, s 0 , P) be an MDP as in Setting 2.2 and λ ∈ [0, 1]. Then a vertex v of
P
min
≥0 (λ) has a maximal number of zeros among all vertices of P
min
≥0 (λ) if and
only if M supp(v) is a minimal witness for Pr
min
s0 (♦ goal) ≥ λ.
Dually, a vertex v of P
max (λ) has a maximal number of zeros among all
vertices of P
max (λ) if and only if all of the following hold:
(1) M supp(v) = (S
all , Act, s 0 , P
) is a minimal witness for Pr
max
s0 (♦ goal) ≥ λ,
(2) for every s ∈ S
there is precisely one α ∈ Act(s) with (s, α) ∈ supp(v),
(3) the corresponding map S : S
→ Act is an MD-scheduler on M supp(v) with
Pr
S
s0 (♦ goal) ≥ λ.