Simple Strategies in Multi-Objective MDPs
357
s 0
s 1
β : 1
α : 0
(a) Multichain MDP
s 1
s 2
s 3
s 4
α
β
0.5
0.5
(b) MDP with nontrivial memory requirements
Figure 5: MDPs referenced in Examples 2 and 4.
Φ(z
j
s,α ) = 0 if Φ(a s,α ) = 0 and Φ(z
ψj
s,⊥ ) = 0 if Φ(e
j
s ) = 0 for any solution Φ. Hence,
for states s ∈ SE where Φ(e
j
s ) = 0, the strategy σ encoded by the variables
a s,α coincides with the strategy considered in Lemma 4. Assume that solution
Φ yields a BSCC within the states of E in M
σ and therefore also a BSCC in
(M
E )
σ . Since s
E
⊥ has to be reached almost surely in M
E (cf. Lemma 4), the
BSCC has to contain at least one state s with Φ(e
j
s ) = 1.
In summary, Lines 19 to 22 imply that every BSCC E
⊆ E of M
σ contains at
least one state s with Φ(e
j
s ) = 1. Then, with Lines 16 to 18 we get that Φ(e
j
s ) = 1
has to hold for all s
∈ SE
. In M
σ , the set S
j
0 ∪
s | Φ(e
j
s ) = 1
is therefore
reached almost surely and all the states in this set get assigned value 0. In this
case, the solution of the equation system from Lemma 3 becomes unique again.
Theorem 4. For finite rewards, the constraints in Figs. 2 and 4 are feasible iff
p ∈ Ach
M
PS (Q).
3.6 Extension to Infinite Rewards
Our approach can be modified to allow PSMA instances where infinite expected
reward can be collected, i.e., where Restriction 2 does not hold. Infinite reward
can be collected if we cycle through an EC of M that contains a transition with
positive reward. Such instances are of practical interest as this often corresponds
to strategies that do not accomplish a certain goal (e.g., a robot that stands still
and therefore requires infinite time to finish its task).
We sketch the necessary modifications. More details are in [17, App. B]. Let
S ∞ be the set of states where every pure strategy induces infinite reward for
at least one minimizing objective. To ensure that the MILP instance has a (realvalued) solution, we consider the sub-MDP of M obtained by removing S ∞ .
If infinite reward can be collected in an EC, it should not be considered
in Fig. 4. We therefore let E range over maximal ECs that only consist of (a)
states in S
j
? and (b) transitions with reward 0.
The upper bounds U
j
s for the maximal expected rewards at each state can
not be set to ∞. However, for the encoding it suffices to compute values that are
sufficiently large. However, we remark that in practice our approach from [17,
App. B] can lead to very large values, yielding numerical instabilities.
For maximizing objectives, we introduce one additional objective which, in a
nutshell, checks that the probability to reach a 0-reward BSCC is below 1. If this
is the case, there is a positive probability to reach a BSCC in which infinitely
many reward can be collected.
357
s 0
s 1
β : 1
α : 0
(a) Multichain MDP
s 1
s 2
s 3
s 4
α
β
0.5
0.5
(b) MDP with nontrivial memory requirements
Figure 5: MDPs referenced in Examples 2 and 4.
Φ(z
j
s,α ) = 0 if Φ(a s,α ) = 0 and Φ(z
ψj
s,⊥ ) = 0 if Φ(e
j
s ) = 0 for any solution Φ. Hence,
for states s ∈ SE where Φ(e
j
s ) = 0, the strategy σ encoded by the variables
a s,α coincides with the strategy considered in Lemma 4. Assume that solution
Φ yields a BSCC within the states of E in M
σ and therefore also a BSCC in
(M
E )
σ . Since s
E
⊥ has to be reached almost surely in M
E (cf. Lemma 4), the
BSCC has to contain at least one state s with Φ(e
j
s ) = 1.
In summary, Lines 19 to 22 imply that every BSCC E
⊆ E of M
σ contains at
least one state s with Φ(e
j
s ) = 1. Then, with Lines 16 to 18 we get that Φ(e
j
s ) = 1
has to hold for all s
∈ SE
. In M
σ , the set S
j
0 ∪
s | Φ(e
j
s ) = 1
is therefore
reached almost surely and all the states in this set get assigned value 0. In this
case, the solution of the equation system from Lemma 3 becomes unique again.
Theorem 4. For finite rewards, the constraints in Figs. 2 and 4 are feasible iff
p ∈ Ach
M
PS (Q).
3.6 Extension to Infinite Rewards
Our approach can be modified to allow PSMA instances where infinite expected
reward can be collected, i.e., where Restriction 2 does not hold. Infinite reward
can be collected if we cycle through an EC of M that contains a transition with
positive reward. Such instances are of practical interest as this often corresponds
to strategies that do not accomplish a certain goal (e.g., a robot that stands still
and therefore requires infinite time to finish its task).
We sketch the necessary modifications. More details are in [17, App. B]. Let
S ∞ be the set of states where every pure strategy induces infinite reward for
at least one minimizing objective. To ensure that the MILP instance has a (realvalued) solution, we consider the sub-MDP of M obtained by removing S ∞ .
If infinite reward can be collected in an EC, it should not be considered
in Fig. 4. We therefore let E range over maximal ECs that only consist of (a)
states in S
j
? and (b) transitions with reward 0.
The upper bounds U
j
s for the maximal expected rewards at each state can
not be set to ∞. However, for the encoding it suffices to compute values that are
sufficiently large. However, we remark that in practice our approach from [17,
App. B] can lead to very large values, yielding numerical instabilities.
For maximizing objectives, we introduce one additional objective which, in a
nutshell, checks that the probability to reach a 0-reward BSCC is below 1. If this
is the case, there is a positive probability to reach a BSCC in which infinitely
many reward can be collected.