EUVIMEDEUVIMED entdecken
Crossref

Best-Effort Policies for Robust Markov Decision Processes

Alessandro Abate, Thom Badings, Giuseppe De Giacomo, Francesco Fabiano

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36120-36128

DOI: 10.1609/aaai.v40i43.40929 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Alessandro Abate und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the common generalization of Markov decision processes (MDPs) with sets of transition probabilities, known as robust MDPs (RMDPs). A standard goal in RMDPs is to compute a policy that maximizes the expected return under an adversarial choice of the transition probabilities. If the uncertainty in the probabilities is independent between the states, known as s-rectangularity, such optimal robust policies can be computed efficiently using robust value iteration. However, there might still be multiple optimal robust policies, which, while equivalent with respect to the worst-case, reflect different expected returns under non-adversarial choices of the transition probabilities. Hence, we propose a refined policy selection criterion for RMDPs, drawing inspiration from the notions of dominance and best-effort in game theory. Instead of seeking a policy that only maximizes the worst-case expected return, we additionally require the policy to achieve a maximal expected return under different (i.e., not fully adversarial) transition probabilities. We call such a policy an optimal robust best-effort (ORBE) policy. We prove that ORBE policies always exist, characterize their structure, and present an algorithm to compute them with a manageable overhead over standard robust value iteration. ORBE policies offer a principled tie-breaker among optimal robust policies. Numerical experiments show the feasibility of our approach.

Zitieren

APA

Abate, A., Badings, T., Giacomo, G. D., & Fabiano, F. (2026). Best-Effort Policies for Robust Markov Decision Processes. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36120-36128. https://doi.org/10.1609/aaai.v40i43.40929

Vancouver

Abate A, Badings T, Giacomo GD, Fabiano F. Best-Effort Policies for Robust Markov Decision Processes. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36120-36128. doi:10.1609/aaai.v40i43.40929

BibTeX
@article{Abate2026,
  author = {Abate, Alessandro and Badings, Thom and Giacomo, Giuseppe De and Fabiano, Francesco},
  title = {Best-Effort Policies for Robust Markov Decision Processes},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {43},
  pages = {36120--36128},
  doi = {10.1609/aaai.v40i43.40929}
}
Kostenlos starten →