Solving Robust Markov Decision Processes: Generic, Reliable, Efficient

Tobias MeggendorferTobias Meggendorfer, Maximilian WeiningerMaximilian Weininger, Patrick WienhöftPatrick Wienhöft

ISBN: 978-1-57735-897-8
ISSN: 2159-5399
Download
DOI Link

Tobias Meggendorfer, Maximilian Weininger, Patrick Wienhöft
Solving Robust Markov Decision Processes: Generic, Reliable, Efficient
In Toby Walsh, Julie Shah, Zico Kolter, eds., Proceedings of the 39th Annual AAAI Conference on Artificial Intelligence, volume 39 of 25, 26631-26641, April 2025. AAAI Press

Details
Bibtex

KurzfassungAbstract
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.
Projekt:Project: CPEC, CeTI
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{MWW2025,
  author    = {Tobias Meggendorfer and Maximilian Weininger and Patrick
               Wienh{\"{o}}ft},
  title     = {Solving Robust Markov Decision Processes: Generic, Reliable,
               Efficient},
  editor    = {Toby Walsh and Julie Shah and Zico Kolter},
  booktitle = {Proceedings of the 39th Annual {AAAI} Conference on Artificial
               Intelligence},
  series    = {25},
  volume    = {39},
  publisher = {AAAI Press},
  year      = {2025},
  month     = {April},
  pages     = {26631-26641},
  doi       = {10.1609/AAAI.V39I25.34865}
}