--- _id: '2234' abstract: - lang: eng text: We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with κ limit-average functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the case of one limit-average function, both randomization and memory are necessary for strategies even for ε-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e. randomized finite-memory strategies are not sufficient), whereas memoryless randomized strategies are sufficient for ε-approximation, for all ε > 0. We further prove that the decision problems for both expectation and satisfaction objectives can be solved in polynomial time and the trade-off curve (Pareto curve) can be ε-approximated in time polynomial in the size of the MDP and 1/ε, and exponential in the number of limit-average functions, for all ε > 0. Our analysis also reveals flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, corrects the flaws, and allows us to obtain improved results. author: - first_name: Tomáš full_name: Brázdil, Tomáš last_name: Brázdil - first_name: Václav full_name: Brožek, Václav last_name: Brožek - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Vojtěch full_name: Forejt, Vojtěch last_name: Forejt - first_name: Antonín full_name: Kučera, Antonín last_name: Kučera citation: ama: Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. Markov decision processes with multiple long-run average objectives. Logical Methods in Computer Science. 2014;10(1). doi:10.2168/LMCS-10(1:13)2014 apa: Brázdil, T., Brožek, V., Chatterjee, K., Forejt, V., & Kučera, A. (2014). Markov decision processes with multiple long-run average objectives. Logical Methods in Computer Science. International Federation of Computational Logic. https://doi.org/10.2168/LMCS-10(1:13)2014 chicago: Brázdil, Tomáš, Václav Brožek, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Markov Decision Processes with Multiple Long-Run Average Objectives.” Logical Methods in Computer Science. International Federation of Computational Logic, 2014. https://doi.org/10.2168/LMCS-10(1:13)2014. ieee: T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, and A. Kučera, “Markov decision processes with multiple long-run average objectives,” Logical Methods in Computer Science, vol. 10, no. 1. International Federation of Computational Logic, 2014. ista: Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. 2014. Markov decision processes with multiple long-run average objectives. Logical Methods in Computer Science. 10(1). mla: Brázdil, Tomáš, et al. “Markov Decision Processes with Multiple Long-Run Average Objectives.” Logical Methods in Computer Science, vol. 10, no. 1, International Federation of Computational Logic, 2014, doi:10.2168/LMCS-10(1:13)2014. short: T. Brázdil, V. Brožek, K. Chatterjee, V. Forejt, A. Kučera, Logical Methods in Computer Science 10 (2014). date_created: 2018-12-11T11:56:29Z date_published: 2014-02-14T00:00:00Z date_updated: 2021-01-12T06:56:11Z day: '14' ddc: - '000' department: - _id: KrCh doi: 10.2168/LMCS-10(1:13)2014 ec_funded: 1 file: - access_level: open_access checksum: 803edcc2d8c1acfba44a9ec43a5eb9f0 content_type: application/pdf creator: system date_created: 2018-12-12T10:07:57Z date_updated: 2020-07-14T12:45:34Z file_id: '4656' file_name: IST-2016-428-v1+1_1104.3489.pdf file_size: 375388 relation: main_file file_date_updated: 2020-07-14T12:45:34Z has_accepted_license: '1' intvolume: ' 10' issue: '1' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ main_file_link: - open_access: '1' url: http://repository.ist.ac.at/id/eprint/428 month: '02' oa: 1 oa_version: Published Version project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: Logical Methods in Computer Science publication_identifier: issn: - '18605974' publication_status: published publisher: International Federation of Computational Logic publist_id: '4727' pubrep_id: '428' quality_controlled: '1' scopus_import: 1 status: public title: Markov decision processes with multiple long-run average objectives tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 volume: 10 year: '2014' ...