Episode
Schlagen Sie die Wege, bevor Sie den Weg schlagen: Beispieleffiziente Monte-Carlo-Planung
durch Jean-Bastien Grill
Wir untersuchen das Sampling-basierte Planungsproblem in Markov-Entscheidungsprozessen (MDPs), auf das wir nur über ein generatives Modell zugreifen können, das in der Regel als Monte-Carlo-Planung bezeichnet wird. Unser Ziel ist es, eine gute Schätzung der optimalen Wertfunktion in jedem Zustand zurückzugeben und gleichzeitig die Anzahl der Aufrufe des generativen Modells, d. h. die Beispielkomplexität, zu minimieren. Wir schlagen einen neuen Algorithmus, TrailBlazer, in der Lage, MDPs mit einer endlichen oder unendlichen Anzahl von Übergängen von Zustandsaktionen zu nächsten Zuständen zu verarbeiten. TrailBlazer ist ein adaptiver Algorithmus, der mögliche Strukturen der MDP ausnutzt, indem nur eine Teilmenge von Zuständen untersucht wird, die erreicht werden können, indem sie nahezu optimale Richtlinien folgen. Wir liefern Grenzen für die Stichprobenkomplexität, die von einem Maß für die Menge der nahezu optimalen Zustände abhängt. Das Algorithmusverhalten kann als Erweiterung des Monte-Carlo-Samplings (für die Schätzung einer Erwartung) auf Probleme betrachtet werden, die eine alternative Maximierung (über Aktionen) und Erwartungen (über nächste Zustände) ändern. Schließlich ist ein weiteres ansprechendes Feature von TrailBlazer, dass es einfach zu implementieren und recheneffizient ist.
Wir untersuchen das Sampling-basierte Planungsproblem in Markov-Entscheidungsprozessen (MDPs), auf das wir nur über ein generatives Modell zugreifen können, das in der Regel als Monte-Carlo-Planung bezeichnet wird. Unser Ziel ist es, eine gute Schätzung der optimalen Wertfunktion in jedem Zustand zurückzugeben und gleichzeitig die Anzahl der Aufrufe des generativen Modells, d. h. die Beispielkomplexität, zu minimieren. Wir schlagen einen neuen Algorithmus, TrailBlazer, in der Lage, MDPs mit einer endlichen oder unendlichen Anzahl von Übergängen von Zustandsaktionen zu nächsten Zuständen zu verarbeiten. TrailBlazer ist ein adaptiver Algorithmus, der mögliche Strukturen der MDP ausnutzt, indem nur eine Teilmenge von Zuständen untersucht wird, die erreicht werden können, indem sie nahezu optimale Richtlinien folgen. Wir liefern Grenzen für die Stichprobenkomplexität, die von einem Maß für die Menge der nahezu optimalen Zustände abhängt. Das Algorithmusverhalten kann als Erweiterung des Monte-Carlo-Samplings (für die Schätzung einer Erwartung) auf Probleme betrachtet werden, die eine alternative Maximierung (über Aktionen) und Erwartungen (über nächste Zustände) ändern. Schließlich ist ein weiteres ansprechendes Feature von TrailBlazer, dass es einfach zu implementieren und recheneffizient ist.
Feedback? Melden Sie hier ein Problem.