---
_id: '5435'
abstract:
- lang: eng
  text: "We consider Markov decision processes (MDPs) with multiple limit-average
    (or mean-payoff) objectives. \r\nThere have been two different views: (i) the
    expectation semantics, where the goal is to optimize the expected mean-payoff
    objective, and (ii) the satisfaction semantics, where the goal is to maximize
    the probability of runs such that the mean-payoff value stays above a given vector.
    \ \r\nWe consider the problem where the goal is to optimize the expectation under
    the constraint that the satisfaction semantics is ensured, and thus consider a
    generalization that unifies the existing semantics. Our problem captures the notion
    of optimization with respect to strategies that are risk-averse (i.e., ensures
    certain probabilistic guarantee).\r\nOur main results are algorithms for the decision
    problem which are always polynomial in the size of the MDP.\r\nWe also show that
    an approximation of the Pareto-curve can be computed in time polynomial in the
    size of the MDP, and the approximation factor, but exponential in the number of
    dimensions. Finally, we present a complete characterization of the strategy complexity
    (in terms of memory bounds and randomization) required to solve our problem."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Zuzana
  full_name: Komarkova, Zuzana
  last_name: Komarkova
- first_name: Jan
  full_name: Kretinsky, Jan
  id: 44CEF464-F248-11E8-B48F-1D18A9856A87
  last_name: Kretinsky
  orcid: 0000-0002-8122-2881
citation:
  ama: Chatterjee K, Komarkova Z, Kretinsky J. <i>Unifying Two Views on Multiple Mean-Payoff
    Objectives in Markov Decision Processes</i>. IST Austria; 2015. doi:<a href="https://doi.org/10.15479/AT:IST-2015-318-v2-1">10.15479/AT:IST-2015-318-v2-1</a>
  apa: Chatterjee, K., Komarkova, Z., &#38; Kretinsky, J. (2015). <i>Unifying two
    views on multiple mean-payoff objectives in Markov decision processes</i>. IST
    Austria. <a href="https://doi.org/10.15479/AT:IST-2015-318-v2-1">https://doi.org/10.15479/AT:IST-2015-318-v2-1</a>
  chicago: Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. <i>Unifying
    Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>.
    IST Austria, 2015. <a href="https://doi.org/10.15479/AT:IST-2015-318-v2-1">https://doi.org/10.15479/AT:IST-2015-318-v2-1</a>.
  ieee: K. Chatterjee, Z. Komarkova, and J. Kretinsky, <i>Unifying two views on multiple
    mean-payoff objectives in Markov decision processes</i>. IST Austria, 2015.
  ista: Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple
    mean-payoff objectives in Markov decision processes, IST Austria, 51p.
  mla: Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff
    Objectives in Markov Decision Processes</i>. IST Austria, 2015, doi:<a href="https://doi.org/10.15479/AT:IST-2015-318-v2-1">10.15479/AT:IST-2015-318-v2-1</a>.
  short: K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple
    Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-02-23T00:00:00Z
date_updated: 2026-07-06T13:26:26Z
day: '23'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-318-v2-1
file:
- access_level: open_access
  checksum: 75284adec80baabdfe71ff9ebbc27445
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:54:03Z
  date_updated: 2020-07-14T12:46:53Z
  file_id: '5525'
  file_name: IST-2015-318-v2+1_main.pdf
  file_size: 717630
  relation: main_file
file_date_updated: 2020-07-14T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '51'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '327'
related_material:
  record:
  - id: '5429'
    relation: earlier_version
    status: public
  - id: '1657'
    relation: later_version
    status: public
  - id: '466'
    relation: later_version
    status: public
status: public
title: Unifying two views on multiple mean-payoff objectives in Markov decision processes
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...