---
OA_place: repository
OA_type: green
_id: '18160'
abstract:
- lang: eng
text: '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. '
acknowledgement: "This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt)
and the Czech Science Foundation\r\ngrant no. GA23-06963S."
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ehsan
full_name: Kafshdar Goharshadi, Ehsan
id: 103b4fa0-896a-11ed-bdf8-87b697bef40d
last_name: Kafshdar Goharshadi
orcid: 0000-0002-8595-0587
- first_name: Mehrdad
full_name: Karrabi, Mehrdad
id: 67638922-f394-11eb-9cf6-f20423e08757
last_name: Karrabi
- first_name: Petr
full_name: Novotný, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotný
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: 'Chatterjee K, Goharshady E, Karrabi M, Novotný P, Zikelic D. Solving long-run
average reward robust MDPs via stochastic games. In: 33rd International Joint
Conference on Artificial Intelligence. International Joint Conferences on
Artificial Intelligence; 2024:6707-6715. doi:10.24963/ijcai.2024/741'
apa: 'Chatterjee, K., Goharshady, E., Karrabi, M., Novotný, P., & Zikelic, D.
(2024). Solving long-run average reward robust MDPs via stochastic games. In 33rd
International Joint Conference on Artificial Intelligence (pp. 6707–6715).
Jeju, South Korea: International Joint Conferences on Artificial Intelligence.
https://doi.org/10.24963/ijcai.2024/741'
chicago: Chatterjee, Krishnendu, Ehsan Goharshady, Mehrdad Karrabi, Petr Novotný,
and Dorde Zikelic. “Solving Long-Run Average Reward Robust MDPs via Stochastic
Games.” In 33rd International Joint Conference on Artificial Intelligence,
6707–15. International Joint Conferences on Artificial Intelligence, 2024. https://doi.org/10.24963/ijcai.2024/741.
ieee: K. Chatterjee, E. Goharshady, M. Karrabi, P. Novotný, and D. Zikelic, “Solving
long-run average reward robust MDPs via stochastic games,” in 33rd International
Joint Conference on Artificial Intelligence, Jeju, South Korea, 2024, pp.
6707–6715.
ista: 'Chatterjee K, Goharshady E, Karrabi M, Novotný P, Zikelic D. 2024. Solving
long-run average reward robust MDPs via stochastic games. 33rd International Joint
Conference on Artificial Intelligence. IJCAI: International Joint Conference on
Artificial Intelligence, 6707–6715.'
mla: Chatterjee, Krishnendu, et al. “Solving Long-Run Average Reward Robust MDPs
via Stochastic Games.” 33rd International Joint Conference on Artificial Intelligence,
International Joint Conferences on Artificial Intelligence, 2024, pp. 6707–15,
doi:10.24963/ijcai.2024/741.
short: K. Chatterjee, E. Goharshady, M. Karrabi, P. Novotný, D. Zikelic, in:, 33rd
International Joint Conference on Artificial Intelligence, International Joint
Conferences on Artificial Intelligence, 2024, pp. 6707–6715.
conference:
end_date: 2024-08-09
location: Jeju, South Korea
name: 'IJCAI: International Joint Conference on Artificial Intelligence'
start_date: 2024-08-03
corr_author: '1'
date_created: 2024-09-29T22:01:39Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-04-14T07:52:46Z
day: '01'
department:
- _id: KrCh
doi: 10.24963/ijcai.2024/741
ec_funded: 1
external_id:
arxiv:
- '2312.13912'
fulldoi: https://doi.org/10.24963/ijcai.2024/741
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2312.13912
month: '09'
oa: 1
oa_version: Preprint
page: 6707-6715
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 33rd International Joint Conference on Artificial Intelligence
publication_identifier:
isbn:
- '9781956792041'
issn:
- 1045-0823
publication_status: published
publisher: International Joint Conferences on Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving long-run average reward robust MDPs via stochastic games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...