---
res:
  bibo_abstract:
  - Markov decision processes (MDPs) provide a standard framework for sequential decision
    making under uncertainty. However, MDPs do not take uncertainty in transition
    probabilities into account. Robust Markov decision processes (RMDPs) address this
    shortcoming of MDPs by assigning to each transition an uncertainty set rather
    than a single probability value. In this work, we consider polytopic RMDPs in
    which all uncertainty sets are polytopes and study the problem of solving long-run
    average reward polytopic RMDPs. We present a novel perspective on this problem
    and show that it can be reduced to solving long-run average reward turn-based
    stochastic games with finite state and action spaces. This reduction allows us
    to derive several important consequences that were hitherto not known to hold
    for polytopic RMDPs. First, we derive new computational complexity bounds for
    solving long-run average reward polytopic RMDPs, showing for the first time that
    the threshold decision problem for them is in NP∩CONP and that they admit a randomized
    algorithm with sub-exponential expected runtime. Second, we present Robust Polytopic
    Policy Iteration (RPPI), a novel policy iteration algorithm for solving long-run
    average reward polytopic RMDPs. Our experimental evaluation shows that RPPI is
    much more efficient in solving long-run average reward polytopic RMDPs compared
    to state-of-the-art methods based on value iteration. @eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Ehsan
      foaf_name: Kafshdar Goharshadi, Ehsan
      foaf_surname: Kafshdar Goharshadi
      foaf_workInfoHomepage: http://www.librecat.org/personId=103b4fa0-896a-11ed-bdf8-87b697bef40d
    orcid: 0000-0002-8595-0587
  - foaf_Person:
      foaf_givenName: Mehrdad
      foaf_name: Karrabi, Mehrdad
      foaf_surname: Karrabi
      foaf_workInfoHomepage: http://www.librecat.org/personId=67638922-f394-11eb-9cf6-f20423e08757
  - foaf_Person:
      foaf_givenName: Petr
      foaf_name: Novotný, Petr
      foaf_surname: Novotný
      foaf_workInfoHomepage: http://www.librecat.org/personId=3CC3B868-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Dorde
      foaf_name: Zikelic, Dorde
      foaf_surname: Zikelic
      foaf_workInfoHomepage: http://www.librecat.org/personId=294AA7A6-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4681-1699
  bibo_doi: 10.24963/ijcai.2024/741
  dct_date: 2024^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1045-0823
  - http://id.crossref.org/issn/9781956792041
  dct_language: eng
  dct_publisher: International Joint Conferences on Artificial Intelligence@
  dct_title: Solving long-run average reward robust MDPs via stochastic games@
...