Simple Strategies in Multi-Objective MDPs
347
Some complex objectives even need infinite memory, e.g., [11,8]. In controller
synthesis, strategies requiring randomization and/or (much) memory may not
be practical. Limited-memory strategies are required on devices with limited resources [7]. Randomization is elegant and powerful from a theoretical view, but
has practical limitations, e.g., it limits reproducibility which complicates debugging. Randomized strategies are also often despised for medical applications [33]
and product design – all products should have the same design, not a random
one. This motivates to consider the analysis of simple strategies, i.e., strategies
using no randomization and a limited amount of memory (given as a parameter).
While most works study the Pareto front among all strategies, we establish ways
to explore efficiently the Pareto front among simple strategies only.
Problem statement. We consider pure (i.e., no randomization) and boundedmemory strategies and study two problems: (a) achievability queries – is it possible to achieve a given value vector – and (b) approximation of the Pareto
front. Considering pure, bounded-memory strategies is natural as randomization can be traded for memory [12]: without randomization, optimal strategies
may require arbitrarily large memory, (see Ex. 4). We study mixtures of expected
(accumulated) reward objectives, covering various studied settings like reachability [20,40], shortest path [39,40,28,9] and total reward objectives [23,24].
Contributions. We first consider the achievability problem for pure stationary
(i.e., memoryless) strategies and show that finding optimal strategies for multiobjective MDPs is NP-complete, even for two objectives. This contrasts the
case of general strategies, where the problem is polynomial-time if the number
of objectives is fixed [40]. We provide a mixed integer linear program (MILP)
encoding. The crux lies in dealing with end components. The MILP is polynomial
in the input MDP and the number of objectives. Inspired by [22], we give an
alternative MILP encoding which is better suited for total reward objectives. To
approximate the Pareto front under pure stationary strategies, we solve multiple
MILP queries. This iteratively divides the solution space into achievable and
non-achievable regions. Bounded-memory strategies are treated via a product
construction. Our approach works for finite and infinite expected rewards.
Practical evaluation. We successfully compute Pareto fronts for 13 benchmarks
using our implementation in Storm, exploiting the MILP solver Gurobi. Despite
the hard nature of the problem, our experiments show that Pareto fronts for
models with tens of thousands of states can be successfully approximated.
Related work. NP completeness for discounted rewards under pure strategies was
shown in [14]. [19] claims that this generalizes to PCTL objectives but no proof is
given. [42] treats multi-objective bounded MDPs whose transition probabilities
are intervals. A set of Pareto optimal policies is computed using policy iteration
and an efficient heuristic is exploited to compute a set of mutually non-dominated
policies that are likely to be Pareto optimal. Pure stationary Pareto optimal
strategies for discounted rewards are obtained in [44] using value-iteration but is
restricted to small MDPs where all probabilities are 0 or 1. In [34],Tchebycheffoptimal strategies for discounted rewards are obtained via an LP approach; such
strategies minimize the distance to a reference point and are not always pure.
347
Some complex objectives even need infinite memory, e.g., [11,8]. In controller
synthesis, strategies requiring randomization and/or (much) memory may not
be practical. Limited-memory strategies are required on devices with limited resources [7]. Randomization is elegant and powerful from a theoretical view, but
has practical limitations, e.g., it limits reproducibility which complicates debugging. Randomized strategies are also often despised for medical applications [33]
and product design – all products should have the same design, not a random
one. This motivates to consider the analysis of simple strategies, i.e., strategies
using no randomization and a limited amount of memory (given as a parameter).
While most works study the Pareto front among all strategies, we establish ways
to explore efficiently the Pareto front among simple strategies only.
Problem statement. We consider pure (i.e., no randomization) and boundedmemory strategies and study two problems: (a) achievability queries – is it possible to achieve a given value vector – and (b) approximation of the Pareto
front. Considering pure, bounded-memory strategies is natural as randomization can be traded for memory [12]: without randomization, optimal strategies
may require arbitrarily large memory, (see Ex. 4). We study mixtures of expected
(accumulated) reward objectives, covering various studied settings like reachability [20,40], shortest path [39,40,28,9] and total reward objectives [23,24].
Contributions. We first consider the achievability problem for pure stationary
(i.e., memoryless) strategies and show that finding optimal strategies for multiobjective MDPs is NP-complete, even for two objectives. This contrasts the
case of general strategies, where the problem is polynomial-time if the number
of objectives is fixed [40]. We provide a mixed integer linear program (MILP)
encoding. The crux lies in dealing with end components. The MILP is polynomial
in the input MDP and the number of objectives. Inspired by [22], we give an
alternative MILP encoding which is better suited for total reward objectives. To
approximate the Pareto front under pure stationary strategies, we solve multiple
MILP queries. This iteratively divides the solution space into achievable and
non-achievable regions. Bounded-memory strategies are treated via a product
construction. Our approach works for finite and infinite expected rewards.
Practical evaluation. We successfully compute Pareto fronts for 13 benchmarks
using our implementation in Storm, exploiting the MILP solver Gurobi. Despite
the hard nature of the problem, our experiments show that Pareto fronts for
models with tens of thousands of states can be successfully approximated.
Related work. NP completeness for discounted rewards under pure strategies was
shown in [14]. [19] claims that this generalizes to PCTL objectives but no proof is
given. [42] treats multi-objective bounded MDPs whose transition probabilities
are intervals. A set of Pareto optimal policies is computed using policy iteration
and an efficient heuristic is exploited to compute a set of mutually non-dominated
policies that are likely to be Pareto optimal. Pure stationary Pareto optimal
strategies for discounted rewards are obtained in [44] using value-iteration but is
restricted to small MDPs where all probabilities are 0 or 1. In [34],Tchebycheffoptimal strategies for discounted rewards are obtained via an LP approach; such
strategies minimize the distance to a reference point and are not always pure.