Unknown

Dataset Information

0

Simple Strategies in Multi-Objective MDPs


ABSTRACT: We consider the verification of multiple expected reward objectives at once on Markov decision processes (MDPs). This enables a trade-off analysis among multiple objectives by obtaining a Pareto front. We focus on strategies that are easy to employ and implement. That is, strategies that are pure (no randomization) and have bounded memory. We show that checking whether a point is achievable by a pure stationary strategy is NP-complete, even for two objectives, and we provide an MILP encoding to solve the corresponding problem. The bounded memory case is treated by a product construction. Experimental results using Storm and Gurobi show the feasibility of our algorithms.

SUBMITTER: Biere A 

PROVIDER: S-EPMC7439746 | biostudies-literature | 2020 Mar

REPOSITORIES: biostudies-literature

Similar Datasets

| S-EPMC6461918 | biostudies-literature
| S-EPMC6081857 | biostudies-literature
| S-EPMC9729643 | biostudies-literature
| S-EPMC1705497 | biostudies-other
| S-EPMC7912461 | biostudies-literature
| S-EPMC3169953 | biostudies-literature
| S-EPMC7924502 | biostudies-literature
| S-EPMC6272647 | biostudies-literature
| S-EPMC6616365 | biostudies-literature
| S-EPMC7495900 | biostudies-literature