Simple Strategies in Multi-Objective MDPs
353
∀ s ∈ S :
Select an action at each state
∀ α ∈ Act(s) :
as,α ∈ {0, 1}
(1)
α∈Act (s)
as,α = 1
(2)
∀ j ∈ {1, . . . , ,} :
Compute expected reward values
∀ s ∈ S
j
0 :
x
j
s = 0
(3)
If ψj is maximising, ± = + and [min] = 0. Otherwise, ± = − and [min] = 1.
∀ s ∈ S
j
? :
± x
j
s ∈ [0, U
j
s ]
(4)
∀ α ∈ Act(s) :
± x
j
s,α ∈ [0, U
j
s ]
(5)
x
j
s,α ≤
s ∈S
P(s, α, s
) ·
x
j
s ± Rj(s, α, s
)
(6)
x
j
s,α ≤ U
j
s · (as,α − [min])
(7)
x
j
s ≤
α∈Act (s)
x
j
s,α + [min] · (|Act (s)| − 1) · U
j
s
(8)
± x
j
s I ∼j pj
Assert value at initial state (9)
Figure 2: MILP encoding for unichain MDP and finite rewards.
Proof. Since M is unichain and we do not collect infinite reward, the only EC
of M (i.e., the only BSCC of M
σ for any σ) either contains a goal state or only
contains transitions with zero reward. It follows that ∀ σ ∈ Σ
M
PS : Pr
M
σ (♦S
j
0 ) = 1.
Lemma 3 follows by standard arguments for MCs with rewards [4, Section 10.5.1].
We discuss the intuition of each constraint in Fig. 2. Let Φ : Var → R be
an assignment of the occurring variables Var to values. Φ is a solution of the
constraints if all (in)equations are satisfied upon replacing all variables v by Φ(v).
Lines 1 and 2 encode a strategy σ ∈ Σ
M
PS by considering a binary variable
a s,α for each state s and enabled action α such that σ(s)(α) = 1 iff Φ(a s,α ) = 1
for a solution Φ. Due to Line 2, exactly one action has to be chosen at each state.
Lines 3 to 8 encode for each objective ψ j the expected rewards obtained for
the encoded strategy σ. For every s ∈ S, the variable x
j
s represents a (lower
or upper) bound on the expected reward at s. Line 3 sets this value for all
s ∈ S
j
0 , reflecting the analogous case from Lemma 3. For s ∈ S
j
? , we distinguish
maximizing (∼ j = ≥) and minimizing (∼ j = ≤) objectives ψ j .
For maximizing ψ j , we have Φ(x
j
s ) ≤ E
Ms
σ (R j ♦G j ) for every solution Φ. This
is achieved by considering a variable x
j
s,α for each enabled action α ∈ Act (s). In
Line 6, we use the equation system characterization from Lemma 3 to assert that
the value of x
j
s,α can not be greater than the expected reward at s, given that
the encoded strategy σ selects α. If σ does not select α (i.e., Φ(a s,α ) = 0), Line 7
implies Φ(x
j
s,α ) = 0. Otherwise, this constraint has no effect. Line 8 ensures that
every solution satisfies Φ(x
j
s ) ≤ Φ(x
j
s,α ) ≤ E
Ms
σ (R j ♦G j ) for α with Φ(a s,α ) = 1.
For minimizing ψ j , we have −Φ(x
j
s ) ≥ E
Ms
σ (R j ♦G j ) for every solution Φ,
i.e., we consider the negated reward values. The encoding is as for maximizing
353
∀ s ∈ S :
Select an action at each state
∀ α ∈ Act(s) :
as,α ∈ {0, 1}
(1)
α∈Act (s)
as,α = 1
(2)
∀ j ∈ {1, . . . , ,} :
Compute expected reward values
∀ s ∈ S
j
0 :
x
j
s = 0
(3)
If ψj is maximising, ± = + and [min] = 0. Otherwise, ± = − and [min] = 1.
∀ s ∈ S
j
? :
± x
j
s ∈ [0, U
j
s ]
(4)
∀ α ∈ Act(s) :
± x
j
s,α ∈ [0, U
j
s ]
(5)
x
j
s,α ≤
s ∈S
P(s, α, s
) ·
x
j
s ± Rj(s, α, s
)
(6)
x
j
s,α ≤ U
j
s · (as,α − [min])
(7)
x
j
s ≤
α∈Act (s)
x
j
s,α + [min] · (|Act (s)| − 1) · U
j
s
(8)
± x
j
s I ∼j pj
Assert value at initial state (9)
Figure 2: MILP encoding for unichain MDP and finite rewards.
Proof. Since M is unichain and we do not collect infinite reward, the only EC
of M (i.e., the only BSCC of M
σ for any σ) either contains a goal state or only
contains transitions with zero reward. It follows that ∀ σ ∈ Σ
M
PS : Pr
M
σ (♦S
j
0 ) = 1.
Lemma 3 follows by standard arguments for MCs with rewards [4, Section 10.5.1].
We discuss the intuition of each constraint in Fig. 2. Let Φ : Var → R be
an assignment of the occurring variables Var to values. Φ is a solution of the
constraints if all (in)equations are satisfied upon replacing all variables v by Φ(v).
Lines 1 and 2 encode a strategy σ ∈ Σ
M
PS by considering a binary variable
a s,α for each state s and enabled action α such that σ(s)(α) = 1 iff Φ(a s,α ) = 1
for a solution Φ. Due to Line 2, exactly one action has to be chosen at each state.
Lines 3 to 8 encode for each objective ψ j the expected rewards obtained for
the encoded strategy σ. For every s ∈ S, the variable x
j
s represents a (lower
or upper) bound on the expected reward at s. Line 3 sets this value for all
s ∈ S
j
0 , reflecting the analogous case from Lemma 3. For s ∈ S
j
? , we distinguish
maximizing (∼ j = ≥) and minimizing (∼ j = ≤) objectives ψ j .
For maximizing ψ j , we have Φ(x
j
s ) ≤ E
Ms
σ (R j ♦G j ) for every solution Φ. This
is achieved by considering a variable x
j
s,α for each enabled action α ∈ Act (s). In
Line 6, we use the equation system characterization from Lemma 3 to assert that
the value of x
j
s,α can not be greater than the expected reward at s, given that
the encoded strategy σ selects α. If σ does not select α (i.e., Φ(a s,α ) = 0), Line 7
implies Φ(x
j
s,α ) = 0. Otherwise, this constraint has no effect. Line 8 ensures that
every solution satisfies Φ(x
j
s ) ≤ Φ(x
j
s,α ) ≤ E
Ms
σ (R j ♦G j ) for α with Φ(a s,α ) = 1.
For minimizing ψ j , we have −Φ(x
j
s ) ≥ E
Ms
σ (R j ♦G j ) for every solution Φ,
i.e., we consider the negated reward values. The encoding is as for maximizing