Simple Strategies in Multi-Objective MDPs
361
1
6
6
0
6
0
0
6
0
0
0
1
6
60
600
6000
T O
/
M
O N / S
TO/MO
ε=0.01 ε=0.001
(a) Alt. (x) vs. original (y) encoding.
0.17
0.18
0.19
0.2
0.17
0.18
Gen
PM2
PMG
PS
(b) Pareto fronts for restricted strategies.
Figure 7: Comparison of the two encodings (left) and impact of memory (right).
runtime of Storm and the number of points on the computed approximation
of the Pareto front. TO denotes that the approach did not terminate within 2
hours, MO denotes insufficient memory (16 GB). All experiments used 8 cores of
an Intel
R
Xeon
R
Platinum 8160 Processor.
Storm is often able to compute pure stationary Pareto fronts, even for models with over 100 000 states (e.g., uav). However, the model structure strongly
affects the performance. For example, the second instance of jobs is challenging
although it only considers 117 states, a low degree of nondeterminism, and no
(non-trivial) end components. Small increments in the model size can increase
runtimes significantly (e.g., dpm or uav). If a higher precision is requested, much
more points need to be found, which often leads to timeouts. Similarly, for more
than 2 objectives the desired accuracy can often not be achieved within the time
limit. The approach can be stopped at any time to report on the current approximation, e.g., after 2 hours Storm found 65 points for Instance 1 of mutex.
For almost all benchmarks, the objectives could be transformed to total reward objectives, making the more efficient encoding form Sect. 3.4 applicable.
We plot the runtimes of the two encoding in Fig. 7a. The alternative encoding
is superior for almost every benchmark. In fact, the original encoding timed out
for many models as indicated at the horizontal line at the top of the figure.
In Fig. 7b we plot the Pareto front for the first polling instance under general
strategies (Gen), pure 2-memory strategies that can change the memory state
exactly once (PM 2 ), pure strategies that observe which goal state set G j has
been visited already (PM G ), and pure stationary strategies (PS). Adding simple
memory structures already leads to noticeable improvements in the quality of
strategies. In particular, PM 2 strategies perform quite well, and even outperform
PM G strategies (which would be optimal if randomization were allowed).
Data availability. The artifact [18] accompanying this paper contains source code,
benchmark files, and replication scripts for our experiments.
Acknowledgments. The authors thank Sebastian Junges for his valuable contributions during early stages of this work.
361
1
6
6
0
6
0
0
6
0
0
0
1
6
60
600
6000
T O
/
M
O N / S
TO/MO
ε=0.01 ε=0.001
(a) Alt. (x) vs. original (y) encoding.
0.17
0.18
0.19
0.2
0.17
0.18
Gen
PM2
PMG
PS
(b) Pareto fronts for restricted strategies.
Figure 7: Comparison of the two encodings (left) and impact of memory (right).
runtime of Storm and the number of points on the computed approximation
of the Pareto front. TO denotes that the approach did not terminate within 2
hours, MO denotes insufficient memory (16 GB). All experiments used 8 cores of
an Intel
R
Xeon
R
Platinum 8160 Processor.
Storm is often able to compute pure stationary Pareto fronts, even for models with over 100 000 states (e.g., uav). However, the model structure strongly
affects the performance. For example, the second instance of jobs is challenging
although it only considers 117 states, a low degree of nondeterminism, and no
(non-trivial) end components. Small increments in the model size can increase
runtimes significantly (e.g., dpm or uav). If a higher precision is requested, much
more points need to be found, which often leads to timeouts. Similarly, for more
than 2 objectives the desired accuracy can often not be achieved within the time
limit. The approach can be stopped at any time to report on the current approximation, e.g., after 2 hours Storm found 65 points for Instance 1 of mutex.
For almost all benchmarks, the objectives could be transformed to total reward objectives, making the more efficient encoding form Sect. 3.4 applicable.
We plot the runtimes of the two encoding in Fig. 7a. The alternative encoding
is superior for almost every benchmark. In fact, the original encoding timed out
for many models as indicated at the horizontal line at the top of the figure.
In Fig. 7b we plot the Pareto front for the first polling instance under general
strategies (Gen), pure 2-memory strategies that can change the memory state
exactly once (PM 2 ), pure strategies that observe which goal state set G j has
been visited already (PM G ), and pure stationary strategies (PS). Adding simple
memory structures already leads to noticeable improvements in the quality of
strategies. In particular, PM 2 strategies perform quite well, and even outperform
PM G strategies (which would be optimal if randomization were allowed).
Data availability. The artifact [18] accompanying this paper contains source code,
benchmark files, and replication scripts for our experiments.
Acknowledgments. The authors thank Sebastian Junges for his valuable contributions during early stages of this work.