Simple Strategies in Multi-Objective MDPs
359
U
1 , 0
0, U
2
R1
w1
(a)
p1
R2
w1
w2
(b)
p1
p2
R3
w1
(c)
p1
p2
p3
R4
w1
(d)
Figure 6: Example exploration of achievable points.
w 1 , yielding point p 3 shown in Fig. 6d. The trapezoidal area is added to the
unachievable points whereas cl
Q ({p 3 }) is achievable. Finally, we check R 4 for
which the corresponding MILP instance is infeasible, i.e., R 4 is unachievable.
The ideas sketched above can be lifted to > 2 objectives. Inspired by [24,
Alg. 4], we choose direction vectors that are orthogonal to the convex hull of
the achievable points found so far. In fact, for total reward objectives we can
apply the approach of [24] to compute the points in Pareto
M
PS (Q) ∩ Pareto
M (Q)
first and only perform MILP-solving for the remaining regions. As the distance
between two found points p, p
is at least |p − p
| ≥ , we can show that our
approach terminates after finding at most
j U
j /j points. Other strategies
for choosing direction vectors are possible and can strongly impact performance.
5 Bounded Memory
For GMA, it is necessary and sufficient to consider strategies that require memory
exponential in the number of objectives [20,24,40] by storing which goal state
set has been reached already. In contrast, restricting to pure (but not necessarily
stationary) strategies imposes nontrivial memory requirements that do not only
depend on the number of objectives, but also on the point that is to be achieved.
Example 4. Let M be the MDP in Fig. 5b and Q = P ≥ (♦G ) , P ≥ (♦G ). The
point p k =
0.5
k , 1−0.5
k
for k ∈ N is achievable by taking α with probability
0.5
k . p k is also achievable with the pure strategy σ k where σ k (ˆ π) = α iff |ˆ π| ≥ k.
σ k uses k memory states. Pure strategies with fewer memory states do not suffice.
We search for pure strategies with bounded memory. For an MDP M and K > 0,
let Σ
M
P,K denote the set of pure K-memory strategies, i.e., any σ ∈ Σ
M
P,K can be
represented by a Mealy machine using up to K states (c.f. [17, App. D]). For a
query Q, let Ach
M
P,K (Q) be the set of points achievable by some σ ∈ Σ
M
P,K .
Pure Bounded Multi-objective Achievability Problem (PBMA)
Input: MDP M, multi-objective query Q, memory bound K, point p ∈ (R ∞ )
Output: Yes iff p ∈ Ach
M
P,K (Q)
359
U
1 , 0
0, U
2
R1
w1
(a)
p1
R2
w1
w2
(b)
p1
p2
R3
w1
(c)
p1
p2
p3
R4
w1
(d)
Figure 6: Example exploration of achievable points.
w 1 , yielding point p 3 shown in Fig. 6d. The trapezoidal area is added to the
unachievable points whereas cl
Q ({p 3 }) is achievable. Finally, we check R 4 for
which the corresponding MILP instance is infeasible, i.e., R 4 is unachievable.
The ideas sketched above can be lifted to > 2 objectives. Inspired by [24,
Alg. 4], we choose direction vectors that are orthogonal to the convex hull of
the achievable points found so far. In fact, for total reward objectives we can
apply the approach of [24] to compute the points in Pareto
M
PS (Q) ∩ Pareto
M (Q)
first and only perform MILP-solving for the remaining regions. As the distance
between two found points p, p
is at least |p − p
| ≥ , we can show that our
approach terminates after finding at most
j U
j /j points. Other strategies
for choosing direction vectors are possible and can strongly impact performance.
5 Bounded Memory
For GMA, it is necessary and sufficient to consider strategies that require memory
exponential in the number of objectives [20,24,40] by storing which goal state
set has been reached already. In contrast, restricting to pure (but not necessarily
stationary) strategies imposes nontrivial memory requirements that do not only
depend on the number of objectives, but also on the point that is to be achieved.
Example 4. Let M be the MDP in Fig. 5b and Q = P ≥ (♦G ) , P ≥ (♦G ). The
point p k =
0.5
k , 1−0.5
k
for k ∈ N is achievable by taking α with probability
0.5
k . p k is also achievable with the pure strategy σ k where σ k (ˆ π) = α iff |ˆ π| ≥ k.
σ k uses k memory states. Pure strategies with fewer memory states do not suffice.
We search for pure strategies with bounded memory. For an MDP M and K > 0,
let Σ
M
P,K denote the set of pure K-memory strategies, i.e., any σ ∈ Σ
M
P,K can be
represented by a Mealy machine using up to K states (c.f. [17, App. D]). For a
query Q, let Ach
M
P,K (Q) be the set of points achievable by some σ ∈ Σ
M
P,K .
Pure Bounded Multi-objective Achievability Problem (PBMA)
Input: MDP M, multi-objective query Q, memory bound K, point p ∈ (R ∞ )
Output: Yes iff p ∈ Ach
M
P,K (Q)