358
F. Delgrange et al.
4 Computing the Pareto Front
Our next goal is to compute the pure stationary Pareto front Pareto
M
PS (Q) for
MDP M and multi-objective query Q. This set can be very large, in particular if
the objectives are strongly conflicting with many different tradeoffs. In the worst
case, every pure stationary strategy induces a point p ∈ Pareto
M
PS (Q) (e.g., for
Q = E ≤ (R♦G), E ≥ (R♦G)). We try to find an approximation of Pareto
M
PS (Q).
Definition 7. Let ∈ (R >0 )
. An -approximation of P ⊆ (R ∞ )
is a pair
L, U with L ⊆ P ⊆ U and ∀ p ∈ P : ∃ p
∈ L ∪ ((R ∞ )
\ U ): |p − p
| ≤ .
For simplicity, we only consider inputs that satisfy restriction Restriction 2, i.e.,
for ψ j = E ∼j (R j ♦G j ) there is U
j
= ∞ such that ∀ σ ∈ Σ
M
PS : U
j
≥ E
M
σ (R j ♦G j ).
Ideas of Sect. 3.6 can be used for some other inputs. An all-embracing treatment
of infinite rewards, in particular for maximizing ψ j , is subject to future work.
Our approach for PSP
≈ successively divides the solution space into candidate
regions. For each region R (initially, let R = [0, U
1 ] × · · · × [0, U
]), we use
the MILP encoding from Sect. 3 with an optimization function to find a point
p ∈ R ∩ Pareto
M
PS (Q) (or find out that no such point exists). The region R is
divided into (i) an achievable region R A ⊆ Ach
M
PS (Q), (ii) an unachievable region
R U ⊆ R
\Ach
M
PS (Q), (iii) further candidate regions R 1 , . . . , R n that are analyzed
subsequently, and (iv) the remaining area R \ (R A ∪ R U ∪ R 1 ∪ · · · ∪ R n ) which
does not require further analysis as we are only interested in an -approximation.
The procedure stops as soon as no more candidate regions are found.
Example 3. Fig. 6 sketches the approach for an MDP M and a query Q with two
maximizing objectives. We maintain a set of achievable points (light green) and
a set of unachievable points (red). Initially, our candidate region corresponds to
R 1 = [0, U
1 ]×[0, U
2 ] given by the white area in Fig. 6a. We consider the direction
vector w 1 which is orthogonal to the line connecting
U
1 , 0
and
0, U
2
. To
find some point p ∈ Pareto
M
PS (Q) ∩ R 1 , we solve the MILP resulting from the
constraints as in Sect. 3, the constraint
x
1
sI , x
2
sI
∈ R 1 , and the optimization
function w 1 ·
x
1
sI , x
2
sI
. Fig. 6b shows the obtained point p 1 ∈ R 1 . Since p 1 is
achievable, we know that any point in cl
Q ({p 1 }) has to be achievable as well.
Moreover, the set {p ∈ R 1 | w 1 · p > w 1 · p 1 } indicated by the area above the
diagonal line in Fig. 6b can not contain an achievable point. The gray areas do
not have to be checked in order to obtain an -approximation. We continue with
R 2 indicated by the white area and the direction vector w 2 , orthogonal to the line
connecting
0, U
2
and p 1 . As before, we solve an MILP now yielding the point
p 2 in Fig. 6c. We find achievable points cl
Q ({p 2 }) but no further unachievable
points. The next iteration considers candidate region R 3 and direction vector
Pure Stationary Pareto Approximation Problem (PSP
≈ )
Input: MDP M, -dimensional multi-objective query Q, precision ∈ (R >0 )
such that Pareto
M
PS ( Q ) ⊆ R
Output: An -approximation of cl
Q (Pareto
M
PS (Q))
F. Delgrange et al.
4 Computing the Pareto Front
Our next goal is to compute the pure stationary Pareto front Pareto
M
PS (Q) for
MDP M and multi-objective query Q. This set can be very large, in particular if
the objectives are strongly conflicting with many different tradeoffs. In the worst
case, every pure stationary strategy induces a point p ∈ Pareto
M
PS (Q) (e.g., for
Q = E ≤ (R♦G), E ≥ (R♦G)). We try to find an approximation of Pareto
M
PS (Q).
Definition 7. Let ∈ (R >0 )
. An -approximation of P ⊆ (R ∞ )
is a pair
L, U with L ⊆ P ⊆ U and ∀ p ∈ P : ∃ p
∈ L ∪ ((R ∞ )
\ U ): |p − p
| ≤ .
For simplicity, we only consider inputs that satisfy restriction Restriction 2, i.e.,
for ψ j = E ∼j (R j ♦G j ) there is U
j
= ∞ such that ∀ σ ∈ Σ
M
PS : U
j
≥ E
M
σ (R j ♦G j ).
Ideas of Sect. 3.6 can be used for some other inputs. An all-embracing treatment
of infinite rewards, in particular for maximizing ψ j , is subject to future work.
Our approach for PSP
≈ successively divides the solution space into candidate
regions. For each region R (initially, let R = [0, U
1 ] × · · · × [0, U
]), we use
the MILP encoding from Sect. 3 with an optimization function to find a point
p ∈ R ∩ Pareto
M
PS (Q) (or find out that no such point exists). The region R is
divided into (i) an achievable region R A ⊆ Ach
M
PS (Q), (ii) an unachievable region
R U ⊆ R
\Ach
M
PS (Q), (iii) further candidate regions R 1 , . . . , R n that are analyzed
subsequently, and (iv) the remaining area R \ (R A ∪ R U ∪ R 1 ∪ · · · ∪ R n ) which
does not require further analysis as we are only interested in an -approximation.
The procedure stops as soon as no more candidate regions are found.
Example 3. Fig. 6 sketches the approach for an MDP M and a query Q with two
maximizing objectives. We maintain a set of achievable points (light green) and
a set of unachievable points (red). Initially, our candidate region corresponds to
R 1 = [0, U
1 ]×[0, U
2 ] given by the white area in Fig. 6a. We consider the direction
vector w 1 which is orthogonal to the line connecting
U
1 , 0
and
0, U
2
. To
find some point p ∈ Pareto
M
PS (Q) ∩ R 1 , we solve the MILP resulting from the
constraints as in Sect. 3, the constraint
x
1
sI , x
2
sI
∈ R 1 , and the optimization
function w 1 ·
x
1
sI , x
2
sI
. Fig. 6b shows the obtained point p 1 ∈ R 1 . Since p 1 is
achievable, we know that any point in cl
Q ({p 1 }) has to be achievable as well.
Moreover, the set {p ∈ R 1 | w 1 · p > w 1 · p 1 } indicated by the area above the
diagonal line in Fig. 6b can not contain an achievable point. The gray areas do
not have to be checked in order to obtain an -approximation. We continue with
R 2 indicated by the white area and the direction vector w 2 , orthogonal to the line
connecting
0, U
2
and p 1 . As before, we solve an MILP now yielding the point
p 2 in Fig. 6c. We find achievable points cl
Q ({p 2 }) but no further unachievable
points. The next iteration considers candidate region R 3 and direction vector
Pure Stationary Pareto Approximation Problem (PSP
≈ )
Input: MDP M, -dimensional multi-objective query Q, precision ∈ (R >0 )
such that Pareto
M
PS ( Q ) ⊆ R
Output: An -approximation of cl
Q (Pareto
M
PS (Q))