Sequenzielle Entscheidungsfindung (MDPs)

Die sequenzielle Entscheidungsfindung formalisiert, wie ein Agent über die Zeit in einer stochastischen Umgebung agieren sollte, indem sie Markov-Entscheidungsprozesse verwendet, bei denen Aktionen Belohnungen liefern und den Zustand probabilistisch ändern, um eine Politik zu berechnen, die die langfristig erwartete Belohnung maximiert.

Definition

Ein Markov-Entscheidungsprozess wird durch Zustände, Aktionen, eine Übergangswahrscheinlichkeitsfunktion und eine Belohnungsfunktion definiert; die sequenzielle Entscheidungsfindung sucht eine Politik, die Zustände Aktionen zuordnet und die erwartete kumulative (typischerweise diskontierte) Belohnung maximiert, gegeben das Modell.

Scope

Dieses Thema behandelt die entscheidungstheoretische Planung über die Zeit: das Markov-Entscheidungsprozess (MDP)-Modell von Zuständen, Aktionen, Übergangswahrscheinlichkeiten, Belohnungen und Diskontierung; Politiken und Wertfunktionen; die Bellman-Gleichungen, die optimales Verhalten charakterisieren; und die dynamischen Programmieralgorithmen der Wertiteration und Politikiteration zur Lösung eines bekannten Modells. Es führt auch teilweise beobachtbare MDPs (POMDPs) und die Planung im Glaubenszustand ein. Der Fokus liegt auf der Planung, wenn das Modell gegeben ist; das Erlernen einer Politik aus Erfahrung ohne ein bekanntes Modell ist Reinforcement Learning, das zum Unterfeld des maschinellen Lernens gehört.

Core questions

• Wie wird das Handeln über die Zeit unter stochastischen Übergängen als Zustände, Aktionen, Übergänge und Belohnungen modelliert?
• Was besagt die Bellman-Optimalitätsgleichung über den Wert einer optimalen Politik?
• Wie berechnen Wertiteration und Politikiteration eine optimale Politik, wenn das Modell bekannt ist?
• Wie führt partielle Beobachtbarkeit zu POMDPs und zur Planung über Glaubenszustände?

Key concepts

• Zustände, Aktionen, Übergänge, Belohnungen
• Politik
• Wertfunktion
• Diskontierungsfaktor
• Bellman-Gleichungen
• Wertiteration
• Politikiteration
• POMDP und Glaubenszustand

Key theories

Bellman-Optimalitätsgleichung

Der optimale Wert eines Zustands entspricht der besten unmittelbaren Belohnung plus dem diskontierten erwarteten optimalen Wert des nächsten Zustands; diese rekursive Beziehung charakterisiert optimales sequenzielles Verhalten und ist die Grundlage dynamischer Programmierlösungen.

Wert- und Politikiteration

Für ein bekanntes MDP wendet die Wertiteration wiederholt das Bellman-Update an, bis zur Konvergenz, und die Politikiteration wechselt zwischen Politikbewertung und -verbesserung; beide garantieren das Auffinden einer optimalen Politik.

Teilweise beobachtbare MDPs

Wenn der Zustand nicht direkt beobachtbar ist, erfolgt die Planung über einen Glaubenszustand (eine Verteilung über Zustände), der aus Beobachtungen aktualisiert wird; die Lösung solcher POMDPs ist weitaus schwieriger als im vollständig beobachtbaren Fall, erfasst jedoch realistische Sensorbeschränkungen.

Clinical relevance

Die MDP- und POMDP-basierte Entscheidungsfindung liegt der Roboternavigation und -steuerung, dem automatisierten Dialogmanagement, Wartungs- und Bestandsentscheidungen sowie der Ressourcenallokation zugrunde und bildet die entscheidungstheoretische Planungsgrundlage, auf der das Reinforcement Learning aufbaut, wenn das Umgebungsmodell stattdessen gelernt werden muss.

History

Die sequenzielle Entscheidungsfindung entwickelte sich aus Bellmans dynamischer Programmierung (1957) und Howards Politikiteration (1960). Putermans Monographie von 1994 konsolidierte die Theorie der Markov-Entscheidungsprozesse, und Kaelbling, Littman und Cassandra (1998) führten teilweise beobachtbare MDPs als Modell für das Handeln unter unsicherer Wahrnehmung in die Mainstream-KI ein.

Key figures

• Richard Bellman
• Ronald A. Howard
• Martin L. Puterman
• Leslie P. Kaelbling
• Michael L. Littman

Seminal works

• bellman1957
• puterman1994
• kaelbling1998

Frequently asked questions

Wie unterscheidet sich dies vom Reinforcement Learning?

Die sequenzielle Entscheidungsfindung mit MDPs setzt voraus, dass das Übergangs- und Belohnungsmodell bekannt ist, sodass eine optimale Politik direkt durch dynamische Programmierung berechnet werden kann. Reinforcement Learning befasst sich mit dem Fall, in dem das Modell unbekannt ist und der Agent eine gute Politik aus Erfahrung lernen muss; es verwendet das MDP als zugrunde liegenden Formalismus.

Was ist ein Glaubenszustand in einem POMDP?

In einem teilweise beobachtbaren MDP kann der Agent den wahren Zustand nicht sehen, daher führt er einen Glaubenszustand, eine Wahrscheinlichkeitsverteilung über die möglichen Zustände, die aktualisiert wird, wenn er Aktionen ausführt und Beobachtungen empfängt. Die Planung erfolgt dann über diese Glaubenszustände und nicht direkt über die verborgenen Zustände.