Solving Long-run Average Reward Robust MDPs via Stochastic
Games

D 2024

Solving Long-run Average Reward Robust MDPs via Stochastic Games

CHATTERJEE, Krishnendu; Ehsan Kafshdar GOHARSHADY; Mehrdad KARRABI; Petr NOVOTNÝ; Djordje ŽIKELIĆ et al.

Základní údaje

Originální název

Solving Long-run Average Reward Robust MDPs via Stochastic Games

Autoři

CHATTERJEE, Krishnendu; Ehsan Kafshdar GOHARSHADY; Mehrdad KARRABI; Petr NOVOTNÝ a Djordje ŽIKELIĆ

Vydání

Neuveden, Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, {IJCAI} 2024, Jeju, South Korea, August 3-9, 2024, od s. 6707-6715, 9 s. 2024

Nakladatel

ijcai.org

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/24:00139771

Organizační jednotka

Fakulta informatiky

ISBN

978-1-956792-04-1

ISSN

Klíčová slova anglicky

planning and scheduling; robust Markov decision processes; stochastic games

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 4. 4. 2025 12:43, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 and 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.

Návaznosti

GA23-06963S, projekt VaV

Název: VESCAA: Verifikovatelná a efektivní syntéza kontrolerů pro autonomní agenty

Investor: Grantová agentura ČR, VESCAA: Verifikovatelná a efektivní syntéza kontrolerů pro autonomní agenty

Citovat

CHATTERJEE, Krishnendu; Ehsan Kafshdar GOHARSHADY; Mehrdad KARRABI; Petr NOVOTNÝ a Djordje ŽIKELIĆ. Solving Long-run Average Reward Robust MDPs via Stochastic Games. Online. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, {IJCAI} 2024, Jeju, South Korea, August 3-9, 2024. Neuveden: ijcai.org, 2024, s. 6707-6715. ISBN 978-1-956792-04-1. Dostupné z: https://doi.org/10.24963/ijcai.2024/741.

@inproceedings{2486809,
   author = {Chatterjee, Krishnendu and Goharshady, Ehsan Kafshdar and Karrabi, Mehrdad and Novotný, Petr and Žikelić, Djordje},
   address = {Neuveden},
   booktitle = {Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, {IJCAI} 2024, Jeju, South Korea, August 3-9, 2024},
   doi = {https://doi.org/10.24963/ijcai.2024/741},
   keywords = {planning and scheduling; robust Markov decision processes; stochastic games},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Neuveden},
   isbn = {978-1-956792-04-1},
   pages = {6707-6715},
   publisher = {ijcai.org},
   title = {Solving Long-run Average Reward Robust MDPs via Stochastic Games},
   year = {2024}
}

TY  - CONF
ID  - 2486809
AU  - Chatterjee, Krishnendu - Goharshady, Ehsan Kafshdar - Karrabi, Mehrdad - Novotný, Petr - Žikelić, Djordje
PY  - 2024
TI  - Solving Long-run Average Reward Robust MDPs via Stochastic Games
PB  - ijcai.org
CY  - Neuveden
SN  - 9781956792041
KW  - planning and scheduling
KW  - robust Markov decision processes
KW  - stochastic games
N2  - 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 and 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.
ER  -

CHATTERJEE, Krishnendu; Ehsan Kafshdar GOHARSHADY; Mehrdad KARRABI; Petr NOVOTNÝ a Djordje ŽIKELI$\backslash$'C. Solving Long-run Average Reward Robust MDPs via Stochastic Games. Online. In \textit{Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, $\{$IJCAI$\}$ 2024, Jeju, South Korea, August 3-9, 2024}. Neuveden: ijcai.org, 2024, s.~6707-6715. ISBN~978-1-956792-04-1. Dostupné z: https://doi.org/10.24963/ijcai.2024/741.

Přehled o publikaci