Stärkung deterministischer Strategien für POMDPs

Abstract:
Die Berechnung von Strategien für partiell beobachtbare Markov-Entscheidungsprozesse (POMDPs), die ein bestimmtes gewünschtes Verhalten garantieren, ist ein unentscheidbares Problem – optimale Strategien benötigen üblicherweise Kenntnis der gesamten Vorgeschichte, also unbegrenzten Speicher. Stattdessen stellen wir solver-basierte Algorithmen vor, um stationäre Strategien zu berechnen, die nur auf dem aktuellen Zustand anstatt der gesamten Vorgeschichte basieren. Da die Berechnung optimaler stationärer, aber randomisierter Strategien immer noch zu aufwändig ist, greifen wir auf deterministische stationäre Strategien zurück und nutzen Algorithmen für gemischt-ganzzahlige lineare Programme. Wir zeigen, wie ein gewisses Maß an Randomisierung erlaubt werden kann und wie eingeschränktes Wissen über die Vorgeschichte mithilfe von Zustands- und Observierungssplitting genutzt werden kann. Unsere Experimente belegen, dass diese Methoden kompetetiv mit traditionellen POMDP Algorithem sind.