Accepted author manuscript, 700 KB, PDF document
Available under license: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Conference article › peer-review
Research output: Contribution to Journal/Magazine › Conference article › peer-review
}
TY - JOUR
T1 - Solving Robust Markov Decision Processes
T2 - 39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025
AU - Meggendorfer, Tobias
AU - Weininger, Maximilian
AU - Wienhöft, Patrick
PY - 2025/4/11
Y1 - 2025/4/11
N2 - Markov decision processes (MDP) are a well-established model for sequential decision-making in the presence of probabilities. In robust MDP (RMDP), every action is associated with an uncertainty set of probability distributions, modelling that transition probabilities are not known precisely. Based on the known theoretical connection to stochastic games, we provide a framework for solving RMDPs that is generic, reliable, and efficient. It is generic both with respect to the model, allowing for a wide range of uncertainty sets, including but not limited to intervals, L1- or L2-balls, and polytopes; and with respect to the objective, including long-run average reward, undiscounted total reward, and stochastic shortest path. It is reliable, as our approach not only converges in the limit, but provides precision guarantees at any time during the computation. It is efficient because - in contrast to state-of-the-art approaches - it avoids explicitly constructing the underlying stochastic game. Consequently, our prototype implementation outperforms existing tools by several orders of magnitude and can solve RMDPs with a million states in under a minute.
AB - Markov decision processes (MDP) are a well-established model for sequential decision-making in the presence of probabilities. In robust MDP (RMDP), every action is associated with an uncertainty set of probability distributions, modelling that transition probabilities are not known precisely. Based on the known theoretical connection to stochastic games, we provide a framework for solving RMDPs that is generic, reliable, and efficient. It is generic both with respect to the model, allowing for a wide range of uncertainty sets, including but not limited to intervals, L1- or L2-balls, and polytopes; and with respect to the objective, including long-run average reward, undiscounted total reward, and stochastic shortest path. It is reliable, as our approach not only converges in the limit, but provides precision guarantees at any time during the computation. It is efficient because - in contrast to state-of-the-art approaches - it avoids explicitly constructing the underlying stochastic game. Consequently, our prototype implementation outperforms existing tools by several orders of magnitude and can solve RMDPs with a million states in under a minute.
U2 - 10.48550/arXiv.2412.10185
DO - 10.48550/arXiv.2412.10185
M3 - Conference article
AN - SCOPUS:105003911147
VL - 39
SP - 26631
EP - 26641
JO - Proceedings of the AAAI Conference on Artificial Intelligence
JF - Proceedings of the AAAI Conference on Artificial Intelligence
SN - 2159-5399
IS - 25
Y2 - 25 February 2025 through 4 March 2025
ER -