350
F. Delgrange et al.
s 1
s 2
s 4
s 5
s 6
s 3
α
β
γ
δ
0.3
0.7
0.8
0.2
(a) MDP M with G= {s4, s6} and G = {s3}
0.7, 0.7
0, 1
1, 0
1, 0.8
P ≥ (♦G)
P
≥ (♦G
)
(b) Ach
M (Q) and Ach
M
PS (Q)
Figure 1: An MDP and a plot of the pure stationary and general Pareto fronts.
Definition 6 (Pareto front). The (general) Pareto front for M and Q is
Pareto
M (Q) =
p ∈ Ach
M (Q) | ∀ p
∈ Ach
M (Q): p ∈ cl
Q ({p
}) =⇒ p = p
.
The Pareto front is the smallest set P ⊆ (R ∞ )
with cl
Q (P ) = Ach
M (Q). In a
similar way, we define the pure stationary Pareto front Pareto
M
PS (Q) which only
consider points in Ach
M
PS (Q).
Example 1. Let M be the MDP in Fig. 1a and Q = P ≥ (♦G ), P ≥ (♦G ). A
pure stationary strategy choosing β at s 1 reaches both, s 4 ∈ G and s 3 ∈ G
with probability 0.7 and thus achieves 0.7, 0.7. Similarly, 0, 1 and 1, 0 are
achievable by a pure stationary strategy. Point 1, 0.8 is achievable by a nonstationary pure strategy that chooses α at s 1 , γ at the first visit of s 2 , and δ
in all other cases. Changing this strategy by picking γ only with probability
0.5 achieves 0.5, 0.9. Fig. 1b illustrates Pareto
M
PS (Q) (dots), Ach
M
PS (Q) (green
area), Pareto
M (Q) (dotted line), and Ach
M (Q) (blue and green area).
3 Deciding Achievability
The achievability problem asks whether a given point is achievable.
For GMA, the point can be achieved by a general strategy that can potentially
make use of memory and randomization. As discussed earlier, this class of strategies is not suitable for various applications. In this work, we focus on a variant of
the achievability problem that only considers pure stationary strategies. Sect. 5
also addresses pure strategies that can store more information from the history,
e.g., whether a goal state set has been reached already.
General Multi-objective Achievability Problem (GMA)
Input: MDP M, -dimensional multi-objective query Q, point p ∈ (R ∞ )
Output: Yes iff p ∈ Ach
M (Q) holds
Pure Stationary Multi-objective Achievability Problem (PSMA)
Input: MDP M, -dimensional multi-objective query Q, point p ∈ (R ∞ )
Output: Yes iff p ∈ Ach
M
PS (Q) holds
F. Delgrange et al.
s 1
s 2
s 4
s 5
s 6
s 3
α
β
γ
δ
0.3
0.7
0.8
0.2
(a) MDP M with G= {s4, s6} and G = {s3}
0.7, 0.7
0, 1
1, 0
1, 0.8
P ≥ (♦G)
P
≥ (♦G
)
(b) Ach
M (Q) and Ach
M
PS (Q)
Figure 1: An MDP and a plot of the pure stationary and general Pareto fronts.
Definition 6 (Pareto front). The (general) Pareto front for M and Q is
Pareto
M (Q) =
p ∈ Ach
M (Q) | ∀ p
∈ Ach
M (Q): p ∈ cl
Q ({p
}) =⇒ p = p
.
The Pareto front is the smallest set P ⊆ (R ∞ )
with cl
Q (P ) = Ach
M (Q). In a
similar way, we define the pure stationary Pareto front Pareto
M
PS (Q) which only
consider points in Ach
M
PS (Q).
Example 1. Let M be the MDP in Fig. 1a and Q = P ≥ (♦G ), P ≥ (♦G ). A
pure stationary strategy choosing β at s 1 reaches both, s 4 ∈ G and s 3 ∈ G
with probability 0.7 and thus achieves 0.7, 0.7. Similarly, 0, 1 and 1, 0 are
achievable by a pure stationary strategy. Point 1, 0.8 is achievable by a nonstationary pure strategy that chooses α at s 1 , γ at the first visit of s 2 , and δ
in all other cases. Changing this strategy by picking γ only with probability
0.5 achieves 0.5, 0.9. Fig. 1b illustrates Pareto
M
PS (Q) (dots), Ach
M
PS (Q) (green
area), Pareto
M (Q) (dotted line), and Ach
M (Q) (blue and green area).
3 Deciding Achievability
The achievability problem asks whether a given point is achievable.
For GMA, the point can be achieved by a general strategy that can potentially
make use of memory and randomization. As discussed earlier, this class of strategies is not suitable for various applications. In this work, we focus on a variant of
the achievability problem that only considers pure stationary strategies. Sect. 5
also addresses pure strategies that can store more information from the history,
e.g., whether a goal state set has been reached already.
General Multi-objective Achievability Problem (GMA)
Input: MDP M, -dimensional multi-objective query Q, point p ∈ (R ∞ )
Output: Yes iff p ∈ Ach
M (Q) holds
Pure Stationary Multi-objective Achievability Problem (PSMA)
Input: MDP M, -dimensional multi-objective query Q, point p ∈ (R ∞ )
Output: Yes iff p ∈ Ach
M
PS (Q) holds