Simple Strategies in Multi-Objective MDPs
349
Definition 4 (Strategy). A (general) strategy for MDP M is a function
σ : Paths
M
fin → Dist(Act ) with supp(σ(ˆ π)) ⊆ Act (last(ˆ π)) for all ˆ
π ∈ Paths
M
fin .
Let σ be a strategy for M. Intuitively, σ(ˆ π)(α) is the probability to perform
action α after observing history ˆ
π ∈ Paths
M
fin . A strategy is pure if all histories
are mapped to Dirac distributions, i.e., the support is a singleton. A strategy
is stationary if its decisions only depend on the current state, i.e., ∀ ˆ
π, ˆ
π
∈
Paths
M
fin : last(ˆ π) = last(ˆ π
) implies σ(ˆ π) = σ(ˆ π
). We often assume σ : S →
Dist(Act ) for stationary and σ : S → Act for pure stationary strategies σ. Let
Σ
M and Σ
M
PS be the sets of general and pure stationary strategies, respectively. A
set of paths Π ⊆ Paths
M
inf is compliant with σ ∈ Σ
M if for all π = s 0 α 1 s 1 · · · ∈ Π
and prefixes ˆ
π of π satisfy σ(ˆ π)(α |ˆ π|+1 ) > 0. The induced Markov chain of M
and σ ∈ Σ
M
PS is given by M
σ = ME
σ , s I with E
σ = {{s, σ(s) | s ∈ S}.
MDP M and strategy σ ∈ Σ
M induce a probability measure Pr
M
σ on subsets
Π ⊆ Paths
M
inf given by a standard cylinder set construction [4,22]. The expected
value of X : Paths
M
inf → R ∞ is E
M
σ (X) =
π
X(π) dPr
M
σ ({π}). For σ ∈ Σ
M
PS ,
Pr
M
σ and E
M
σ coincide with the corresponding measures on MC M
σ .
2.2 Objectives
A reward structure R : S × Act × S → R ≥0 assigns non-negative rewards to
transitions. We accumulate rewards on (in)finite paths π = s 0 α 1 s 1 α 2 . . . : R(π) =
|π|
i=1 R(s i−1 , α i , s i ). For a set of goal states G ⊆ S, let R♦G(π) = R(ˆ π), where
ˆ
π is the smallest prefix of π with last(ˆ π) ∈ G (or ˆ
π = π if no such prefix
exists). Intuitively, R♦G(π) is the reward accumulated on π until a state in
G is reached. A (reward) objective has the form E ∼ (R♦G) for ∼ ∈ {≥, ≤}.
We write M, σ, p |= E ∼ (R♦G) iff E
M
σ (R♦G) ∼ p, i.e., for M and σ, the
expected accumulated reward until reaching G is at least (or at most) p ∈ R ∞ .
We call the objective maximizing if ∼ = ≥ and minimizing otherwise. If G = ∅
(i.e., R♦G(π) = R(π) for all paths π), we call the objective a total reward
objective. Let the reward structure R
G be given by R(s, α, s
) = [s
∈ G]. Then,
Pr
M
σ (♦G) = E
M
σ (R
G ♦G) for every σ ∈ Σ
M , where ♦G ⊆ Paths
M
inf denotes the
set of paths that visit a state in G. We use P ∼ (♦G) as a shortened for E ∼ (R
G ♦G)
and call such an objective a reachability objective.
Definition 5 (Multi-objective query). For MDP M, an -dimensional multiobjective query is a tuple Q = ψ 1 , . . . , ψ of objectives ψ j = E ∼j (R j ♦G j ).
Each objective ψ j considers a different reward structure R j . The MDP M,
strategy σ, and point p ∈ (R ∞ )
satisfy a multi-objective query Q = ψ 1 , . . . , ψ
(written M, σ, p |= Q) iff ∀ j : M, σ, pj |= ψ j . Then, we also say σ achieves
p and call p achievable. Let Ach
M (Q) (Ach
M
PS (Q)) denote the set of points
achieved by a general (pure stationary) strategy. The closure of a set P ⊆ (R ∞ )
with respect to query Q is cl
Q (P ) =
p ∈ (R ∞ )
| ∃ p
∈ P : ∀ j : p
j ∼ j pj
.
For p, p
∈ (R ∞ )
, we say that p dominates p
if p
∈ cl
Q ({p}). In this case,
M, σ, p |= Q implies M, σ, p
|= Q for any σ ∈ Σ
M . We are interested in the
Pareto front, which is the set of non-dominated achievable points.
349
Definition 4 (Strategy). A (general) strategy for MDP M is a function
σ : Paths
M
fin → Dist(Act ) with supp(σ(ˆ π)) ⊆ Act (last(ˆ π)) for all ˆ
π ∈ Paths
M
fin .
Let σ be a strategy for M. Intuitively, σ(ˆ π)(α) is the probability to perform
action α after observing history ˆ
π ∈ Paths
M
fin . A strategy is pure if all histories
are mapped to Dirac distributions, i.e., the support is a singleton. A strategy
is stationary if its decisions only depend on the current state, i.e., ∀ ˆ
π, ˆ
π
∈
Paths
M
fin : last(ˆ π) = last(ˆ π
) implies σ(ˆ π) = σ(ˆ π
). We often assume σ : S →
Dist(Act ) for stationary and σ : S → Act for pure stationary strategies σ. Let
Σ
M and Σ
M
PS be the sets of general and pure stationary strategies, respectively. A
set of paths Π ⊆ Paths
M
inf is compliant with σ ∈ Σ
M if for all π = s 0 α 1 s 1 · · · ∈ Π
and prefixes ˆ
π of π satisfy σ(ˆ π)(α |ˆ π|+1 ) > 0. The induced Markov chain of M
and σ ∈ Σ
M
PS is given by M
σ = ME
σ , s I with E
σ = {{s, σ(s) | s ∈ S}.
MDP M and strategy σ ∈ Σ
M induce a probability measure Pr
M
σ on subsets
Π ⊆ Paths
M
inf given by a standard cylinder set construction [4,22]. The expected
value of X : Paths
M
inf → R ∞ is E
M
σ (X) =
π
X(π) dPr
M
σ ({π}). For σ ∈ Σ
M
PS ,
Pr
M
σ and E
M
σ coincide with the corresponding measures on MC M
σ .
2.2 Objectives
A reward structure R : S × Act × S → R ≥0 assigns non-negative rewards to
transitions. We accumulate rewards on (in)finite paths π = s 0 α 1 s 1 α 2 . . . : R(π) =
|π|
i=1 R(s i−1 , α i , s i ). For a set of goal states G ⊆ S, let R♦G(π) = R(ˆ π), where
ˆ
π is the smallest prefix of π with last(ˆ π) ∈ G (or ˆ
π = π if no such prefix
exists). Intuitively, R♦G(π) is the reward accumulated on π until a state in
G is reached. A (reward) objective has the form E ∼ (R♦G) for ∼ ∈ {≥, ≤}.
We write M, σ, p |= E ∼ (R♦G) iff E
M
σ (R♦G) ∼ p, i.e., for M and σ, the
expected accumulated reward until reaching G is at least (or at most) p ∈ R ∞ .
We call the objective maximizing if ∼ = ≥ and minimizing otherwise. If G = ∅
(i.e., R♦G(π) = R(π) for all paths π), we call the objective a total reward
objective. Let the reward structure R
G be given by R(s, α, s
) = [s
∈ G]. Then,
Pr
M
σ (♦G) = E
M
σ (R
G ♦G) for every σ ∈ Σ
M , where ♦G ⊆ Paths
M
inf denotes the
set of paths that visit a state in G. We use P ∼ (♦G) as a shortened for E ∼ (R
G ♦G)
and call such an objective a reachability objective.
Definition 5 (Multi-objective query). For MDP M, an -dimensional multiobjective query is a tuple Q = ψ 1 , . . . , ψ of objectives ψ j = E ∼j (R j ♦G j ).
Each objective ψ j considers a different reward structure R j . The MDP M,
strategy σ, and point p ∈ (R ∞ )
satisfy a multi-objective query Q = ψ 1 , . . . , ψ
(written M, σ, p |= Q) iff ∀ j : M, σ, pj |= ψ j . Then, we also say σ achieves
p and call p achievable. Let Ach
M (Q) (Ach
M
PS (Q)) denote the set of points
achieved by a general (pure stationary) strategy. The closure of a set P ⊆ (R ∞ )
with respect to query Q is cl
Q (P ) =
p ∈ (R ∞ )
| ∃ p
∈ P : ∀ j : p
j ∼ j pj
.
For p, p
∈ (R ∞ )
, we say that p dominates p
if p
∈ cl
Q ({p}). In this case,
M, σ, p |= Q implies M, σ, p
|= Q for any σ ∈ Σ
M . We are interested in the
Pareto front, which is the set of non-dominated achievable points.