Solving Long-run Average Reward Robust MDPs via Stochastic Games

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00139771" target="_blank" >RIV/00216224:14330/24:00139771 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.24963/ijcai.2024/741" target="_blank" >http://dx.doi.org/10.24963/ijcai.2024/741</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/ijcai.2024/741" target="_blank" >10.24963/ijcai.2024/741</a>

Result language

angličtina

Original language name

Solving Long-run Average Reward Robust MDPs via Stochastic Games

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA23-06963S" target="_blank" >GA23-06963S: VESCAA: Verifiable and Efficient Synthesis of Controllers for Autonomous Agents</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, {IJCAI} 2024, Jeju, South Korea, August 3-9, 2024

ISBN

9781956792041

ISSN

1045-0823

e-ISSN

—

Number of pages

9

Pages from-to

6707-6715

Publisher name

ijcai.org

Place of publication

Neuveden

Event location

Jeju

Event date

Jan 1, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001347142806093