Neue effiziente Algorithmen für Blackwell‑optimale Politiken in MDPs

Markov‑Entscheidungsprobleme (MDPs) bilden die Basis für die Modellierung von sequentiellen Entscheidungen in vielen Bereichen. Traditionelle Optimierungs­kriterien wie diskontierte oder durchschnittliche Belohnungen haben jedoch Einschränkungen: Diskontierung kann kurzfristige Gewinne überbetonen, während die durchschnittliche Optimierung starke Strukturannahmen verlangt. Das Konzept der Blackwell‑Optimalität überwindet diese Probleme, indem es eine robuste Lösung liefert, die sowohl unter diskontierten als auch unter durchschnittlichen Belohnungen optimal ist.

In einer neuen Veröffentlichung auf arXiv (2508.18252v1) werden Verfahren vorgestellt, die Blackwell‑optimale Politiken mithilfe einer Ordnung rationaler Funktionen in der Nähe von 1 berechnen. Durch die Ersetzung numerischer Auswertungen durch symbolische Operationen auf rationalen Funktionen lassen sich Grenzwerte bestimmen, die unabhängig von der Bit‑Komplexität sind.

Für deterministische MDPs präsentiert die Arbeit die ersten stark polynomischen Algorithmen zur Berechnung von Blackwell‑optimalen Politiken. Bei allgemeinen MDPs wird ein erster subexponentieller Algorithmus vorgestellt. Darüber hinaus werden mehrere Policy‑Iteration‑Algorithmen erweitert, sodass die bisher besten oberen Schranken von der diskontierten zur Blackwell‑Kriterien übertragen werden können.

Diese Fortschritte markieren einen bedeutenden Schritt in der effizienten Berechnung von Blackwell‑optimalen Strategien und eröffnen neue Möglichkeiten für die praktische Anwendung in komplexen Entscheidungsumgebungen.