Simple Strategies in Multi-Objective MDPs
351
3.1 Complexity Results
GMA is PSPACE hard (already with only reachability objectives) [40] and solvable
within exponential runtime [20,23]. To the best of our knowledge, a PSPACE upper bound on the complexity of GMA is unknown. This complexity is rooted in the
dimension of the query Q: for fixed , the algorithms of [20,23] have polynomial
runtime. In contrast, PSMA is NP-complete, even if restricted to 2 objectives.
Lemma 1. PSMA with only reachability objectives is NP-hard.
Proof. The result follows by a reduction from the subset sum problem. Given
n ∈ N, a ∈ N
n and z ∈ N, the subset sum problem is to decide the existence of
v ∈ {0, 1}
n such that v · a = z. This problem is NP-complete [25]. For a given
instance of the subset sum problem, we construct the MDP M
= S, Act , P, s I
with state space S = {s I , s 1 , . . . , s n , g 1 , g 2 }, actions Act = {α, Y, N }, and for all
i ∈ {1, . . . , n}, P(s I , α, s i ) =
ai
1·a and P(s i , Y, g 1 ) = P(s i , N, g 2 ) = 1. States g 1
and g 2 are made absorbing, i.e., P(g 1 , α, g 1 ) = P(g 2 , α, g 2 ) = 1.
We claim that the PSMA problem for M
, Q = P ≥ (♦ {g 1 }), P ≥ (♦ {g 2 }),
and p =
z
1·a , 1 −
z
1·a
answers “yes” iff there is a vector v satisfying the subset
sum problem for n, a and z. Consider the bijection f : Σ
M
PS → {0, 1}
n with
f (σ)i = [σ(s i )=Y ] for all σ ∈ Σ
M
PS and i ∈ {1, . . . , n}. We get Pr
M
σ (♦ {g 1 }) =
n
i=1
ai
1·a [σ(s i )=Y ] =
f (σ)·a
1·a . Moreover, Pr
M
σ (♦ {g 2 }) = 1 − Pr
M
σ (♦ {g 1 }) =
1 −
f (σ)·a
1·a . It follows that σ achieves p iff f (σ) is a solution to the instance of the
subset sum problem. Our construction is inspired by similar ideas from [14,40].
Lemma 2 ([14]). PSMA with only total reward objectives is NP-hard.
Theorem 1. PSMA is NP-complete.
Proof. Containment follows by guessing a pure stationary strategy and evaluating it on the individual objectives. This can be done in polynomial time [4].
Hardness follows by either Lemma 1 or 2.
Proofs of Lemmas 1 and 2 only consider 2-dimensional multi-objective queries.
Hence, in contrast to GMA, the hardness of PSMA is not due to the size of the query.
Corollary 1. PSMA with only two objectives is NP-complete.
3.2 A Mixed Integer Linear Programming Approach
An MDP M = S, Act , P, s I has exactly |Σ
M
PS | =
s∈S |Act (s)| many pure
stationary strategies. A simple algorithm for PSMA enumerates all σ ∈ Σ
M
PS and
checks whether M, σ, p |= Q holds. In practice, however, such a brute-force
approach is not feasible. For the MDPs that we consider in our experiments in
Sect. 6, the number of pure stationary strategies often exceeds 10
10 000 . Instead,
our approach is to encode an instance for PSMA as an MILP problem.
351
3.1 Complexity Results
GMA is PSPACE hard (already with only reachability objectives) [40] and solvable
within exponential runtime [20,23]. To the best of our knowledge, a PSPACE upper bound on the complexity of GMA is unknown. This complexity is rooted in the
dimension of the query Q: for fixed , the algorithms of [20,23] have polynomial
runtime. In contrast, PSMA is NP-complete, even if restricted to 2 objectives.
Lemma 1. PSMA with only reachability objectives is NP-hard.
Proof. The result follows by a reduction from the subset sum problem. Given
n ∈ N, a ∈ N
n and z ∈ N, the subset sum problem is to decide the existence of
v ∈ {0, 1}
n such that v · a = z. This problem is NP-complete [25]. For a given
instance of the subset sum problem, we construct the MDP M
= S, Act , P, s I
with state space S = {s I , s 1 , . . . , s n , g 1 , g 2 }, actions Act = {α, Y, N }, and for all
i ∈ {1, . . . , n}, P(s I , α, s i ) =
ai
1·a and P(s i , Y, g 1 ) = P(s i , N, g 2 ) = 1. States g 1
and g 2 are made absorbing, i.e., P(g 1 , α, g 1 ) = P(g 2 , α, g 2 ) = 1.
We claim that the PSMA problem for M
, Q = P ≥ (♦ {g 1 }), P ≥ (♦ {g 2 }),
and p =
z
1·a , 1 −
z
1·a
answers “yes” iff there is a vector v satisfying the subset
sum problem for n, a and z. Consider the bijection f : Σ
M
PS → {0, 1}
n with
f (σ)i = [σ(s i )=Y ] for all σ ∈ Σ
M
PS and i ∈ {1, . . . , n}. We get Pr
M
σ (♦ {g 1 }) =
n
i=1
ai
1·a [σ(s i )=Y ] =
f (σ)·a
1·a . Moreover, Pr
M
σ (♦ {g 2 }) = 1 − Pr
M
σ (♦ {g 1 }) =
1 −
f (σ)·a
1·a . It follows that σ achieves p iff f (σ) is a solution to the instance of the
subset sum problem. Our construction is inspired by similar ideas from [14,40].
Lemma 2 ([14]). PSMA with only total reward objectives is NP-hard.
Theorem 1. PSMA is NP-complete.
Proof. Containment follows by guessing a pure stationary strategy and evaluating it on the individual objectives. This can be done in polynomial time [4].
Hardness follows by either Lemma 1 or 2.
Proofs of Lemmas 1 and 2 only consider 2-dimensional multi-objective queries.
Hence, in contrast to GMA, the hardness of PSMA is not due to the size of the query.
Corollary 1. PSMA with only two objectives is NP-complete.
3.2 A Mixed Integer Linear Programming Approach
An MDP M = S, Act , P, s I has exactly |Σ
M
PS | =
s∈S |Act (s)| many pure
stationary strategies. A simple algorithm for PSMA enumerates all σ ∈ Σ
M
PS and
checks whether M, σ, p |= Q holds. In practice, however, such a brute-force
approach is not feasible. For the MDPs that we consider in our experiments in
Sect. 6, the number of pure stationary strategies often exceeds 10
10 000 . Instead,
our approach is to encode an instance for PSMA as an MILP problem.