Simple Strategies in Multi-Objective MDPs
355
∀ s ∈ S ? , α ∈ Act(s) :
ys,α ∈ [0, Vs · as,α]
(10)
α∈Act (s)
ys,α = [s = sI ] +
s ,α ∈pre(s)
P(s
, α
, s) · y s ,α
(11)
1 =
s∈S ?
α∈Act (s)
ys,α ·
s ∈S 0
P(s, α, s
)
(12)
∀ j ∈ {1, . . . , ,} :
x
j
s I =
s∈S ?
α∈Act (s)
ys,α ·
s ∈S
P(s, α, s
) · Rj(s, α, s
)
(13)
x
j
s I ∼j pj
(14)
Figure 3: MILP encoding for total reward objectives.
strategy in Lemma 4 coincides with the encoded pure strategy σ. We write V s
for an upper bound of the value a solution can possibly assign to y s,α , i.e.,
∀ σ ∈ Σ
M
PS : V s ≥ E
M
σ (R s,α ♦S 0 ). Such an upper bound can be computed based
on ideas of [5]. More details are given in [17, App. A].
With Lemma 4 we get that Φ(y s,σ(s) ) is the expected number of times state s
is visited under strategy σ. Therefore, in Line 13 we sum up for each state s ∈ S ?
the expected amount of reward collected at s. This yields Φ(x
j
sI ) = E
M
σ (R j ♦G j ).
Finally, Line 14 asserts that the resulting values exceed the thresholds given by p.
Theorem 3. For unichain M, finite rewards, and total reward objectives, the
constraints in Fig. 3 and Lines 1 and 2 of Fig. 2 are feasible iff p ∈ Ach
M
PS (Q).
Proposition 2. The MILP encoding above considers O(|S| · |Act | + ) variables.
The encoding for total reward objectives considers fewer variables compared
to the encoding of Sect. 3.3 (cf. Proposition 1). In practice, this often leads to
faster solving times as we will see in Sect. 6.
3.5 Extension to Multichain MDP
We now lift the restriction to unichain MDP, i.e., we consider multichain MDP
with finite rewards. We focus on the encoding of Sect. 3.3. Details for the approach of Sect. 3.4 are in [17, App. C]. The key challenge is that the equation
system in Lemma 3 does not yield a unique solution for multichain MDP.
Example 2. For the multichain MDP in Fig. 5a with G = {s 1 } we have S 0 = {s 1 }
and S ? = {s 0 } (the superscript j is omitted as there is only one objective). For
σ with σ(s 0 ) = α we get E
M
σ (R♦G) = 0, but every Φ :
x s0 , x s1
→ R × {0} is
a solution for the equation system in Lemma 3.
For multichain MDP it can be the case that for some strategy σ the set S
j
0 is
not reached with probability 1, i.e., there is a positive probability to stay in the
set S
j
? forever. For the induced Markov chain M
σ , this means that there is a
reachable BSCC consisting only of states in S
j
? . Since BSCCs of M
σ coincide
with end components of M, we need to inspect the ECs of M that only consist of
355
∀ s ∈ S ? , α ∈ Act(s) :
ys,α ∈ [0, Vs · as,α]
(10)
α∈Act (s)
ys,α = [s = sI ] +
s ,α ∈pre(s)
P(s
, α
, s) · y s ,α
(11)
1 =
s∈S ?
α∈Act (s)
ys,α ·
s ∈S 0
P(s, α, s
)
(12)
∀ j ∈ {1, . . . , ,} :
x
j
s I =
s∈S ?
α∈Act (s)
ys,α ·
s ∈S
P(s, α, s
) · Rj(s, α, s
)
(13)
x
j
s I ∼j pj
(14)
Figure 3: MILP encoding for total reward objectives.
strategy in Lemma 4 coincides with the encoded pure strategy σ. We write V s
for an upper bound of the value a solution can possibly assign to y s,α , i.e.,
∀ σ ∈ Σ
M
PS : V s ≥ E
M
σ (R s,α ♦S 0 ). Such an upper bound can be computed based
on ideas of [5]. More details are given in [17, App. A].
With Lemma 4 we get that Φ(y s,σ(s) ) is the expected number of times state s
is visited under strategy σ. Therefore, in Line 13 we sum up for each state s ∈ S ?
the expected amount of reward collected at s. This yields Φ(x
j
sI ) = E
M
σ (R j ♦G j ).
Finally, Line 14 asserts that the resulting values exceed the thresholds given by p.
Theorem 3. For unichain M, finite rewards, and total reward objectives, the
constraints in Fig. 3 and Lines 1 and 2 of Fig. 2 are feasible iff p ∈ Ach
M
PS (Q).
Proposition 2. The MILP encoding above considers O(|S| · |Act | + ) variables.
The encoding for total reward objectives considers fewer variables compared
to the encoding of Sect. 3.3 (cf. Proposition 1). In practice, this often leads to
faster solving times as we will see in Sect. 6.
3.5 Extension to Multichain MDP
We now lift the restriction to unichain MDP, i.e., we consider multichain MDP
with finite rewards. We focus on the encoding of Sect. 3.3. Details for the approach of Sect. 3.4 are in [17, App. C]. The key challenge is that the equation
system in Lemma 3 does not yield a unique solution for multichain MDP.
Example 2. For the multichain MDP in Fig. 5a with G = {s 1 } we have S 0 = {s 1 }
and S ? = {s 0 } (the superscript j is omitted as there is only one objective). For
σ with σ(s 0 ) = α we get E
M
σ (R♦G) = 0, but every Φ :
x s0 , x s1
→ R × {0} is
a solution for the equation system in Lemma 3.
For multichain MDP it can be the case that for some strategy σ the set S
j
0 is
not reached with probability 1, i.e., there is a positive probability to stay in the
set S
j
? forever. For the induced Markov chain M
σ , this means that there is a
reachable BSCC consisting only of states in S
j
? . Since BSCCs of M
σ coincide
with end components of M, we need to inspect the ECs of M that only consist of