Die Komplexität der dezentralen Steuerung von Markov-Entscheidungsprozessen

Wir betrachten die dezentrale Steuerung von Markov-Entscheidungsprozessen und geben Komplexitätsgrenzen für die worst-case Laufzeit von Algorithmen an, die optimale Lösungen finden. Verallgemeinerungen sowohl des vollständig beobachtbaren Falls als auch des teilweise beobachtbaren Falls, die eine dezentrale Steuerung ermöglichen, werden beschrieben. Selbst für zwei Agenten sind die endlichen Horizontprobleme, die diesen Modellen entsprechen, schwer für nichtdeterministische exponentielle Zeit. Diese Komplexitätsergebnisse veranschaulichen einen grundlegenden Unterschied zwischen zentralisierter und dezentraler Steuerung von Markov-Entscheidungsprozessen. Im Gegensatz zu den Problemen, die die zentralisierte Steuerung betreffen, lassen die von uns betrachteten Probleme nachweislich keine polynomialen Algorithmen zu. Darüber hinaus erfordern die Probleme, unter der Annahme, dass EXP ≠ NEXP, im schlimmsten Fall superexponentielle Zeit zur Lösung.