Solving long-run average reward robust MDPs via stochastic games
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.
Download (ext.)
https://doi.org/10.48550/arXiv.2312.13912
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Corresponding author has ISTA affiliation
Department
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.
Publishing Year
Date Published
2024-09-01
Proceedings Title
33rd International Joint Conference on Artificial Intelligence
Publisher
International Joint Conferences on Artificial Intelligence
Acknowledgement
This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt) and the Czech Science Foundation
grant no. GA23-06963S.
Page
6707-6715
Conference
IJCAI: International Joint Conference on Artificial Intelligence
Conference Location
Jeju, South Korea
Conference Date
2024-08-03 – 2024-08-09
ISBN
ISSN
IST-REx-ID
Cite this
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.
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.
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.
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.
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.
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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2312.13912