Finding the Time to Think: Learning Planning Budgets in Real-Time RL

Technisches Resümee: Die Zeit zum Nachdenken finden: Lernen von Planungsbudgets in Real-Time RL

Problemdefinition: Variable Verzögerung in Real-Time RL

Standardmäßiges Reinforcement Learning (RL) und Markov-Entscheidungsprozesse (MDPs) operieren unter der Annahme, dass die Umgebung unbegrenzt auf die Berechnung einer Aktion durch den Agenten wartet; somit verursacht das Nachdenken keine Kosten. In Echtzeit-Szenarien versagt diese Annahme: Die Umgebung schreitet kontinuierlich voran, unabhängig von der Rechenzeit des Agenten. Eine perfekte Aktion, die zu spät ausgeführt wird, ist oft schlechter als eine rechtzeitige, suboptimale Aktion.

Während vorangegangene Arbeiten (Ramstedt & Pal, 2019) Real-Time RL mit einer festen Verzögerung formalisierten (z. B. genau ein Zeitschritt zur Berechnung), führt dieses Paper Variable-Delay Real-Time RL ein. In diesem Framework ist der Agent keine statische Funktion, sondern ein zeitgesteuerter Prozess. Der Agent muss entscheiden, wie lange er an jedem Entscheidungspunkt nachdenkt. Die Kosten des Nachdenkens werden als Fortschritt der Umgebung (oder als Depletion der Uhrzeit in Brettspielen) „bezahlt“, während der Agent rechnet. Dies schafft eine Meta-Reasoning-Herausforderung: Der Agent muss das Gleichgewicht zwischen der Qualität der geplanten Aktion und der durch die Planungszeit verursachten Verschlechterung des Zustands finden. Ein naives Planen darüber, wie lange man plant, birgt das Risiko eines Paradoxons, bei dem die Meta-Entscheidung selbst dieselben Echtzeit-Kosten verursacht wie das, was sie zu optimieren versucht.

Methodik

Die Autoren schlagen eine Lösung vor, die auf einem Semi-Markov-Entscheidungsprozess (SMDP) über budgetierten Optionen basiert, wodurch der Planungsalgorithmus von der Entscheidung darüber, wie viel geplant wird, entkoppelt wird.

1. Architekturkomponenten:

   • Reflex-Policy ($\pi_{reflex}$): Eine schnelle, leichtgewichtige Policy (z. B. der Policy-Head eines AlphaZero-Modells ohne MCTS), die in deutlich weniger als einem Frame läuft. Sie liefert unmittelbare Aktionen für die Umgebung, während der Planer im Hintergrund läuft.
   • Anytime Action-Refinement Computations ($\{c_k\}$): Eine endliche Menge von Berechnungen, indiziert durch diskrete Dauer $k$. In dieser Arbeit werden diese als Monte Carlo Tree Search (MCTS)-Läufe für $k$ Frames instanziiert. Längere Läufe ($c_k$) erzeugen qualitativ hochwertigere Aktionen, benötigen aber mehr Zeit.
   • Budgetierte Optionen ($o_k$): Jede Option $o_k$ kapselt eine Berechnung $c_k$. Sobön die Option initiiert wird, verpflichtet sich der Agent dazu, $k-1$ Aktionen aus $\pi_{reflex}$ auszuführen, während $c_k$ läuft. Im $k$-ten Frame wird die verfeinerte Aktion von $c_k$ ausgeführt.
   • Gating-Policy ($\pi_{gate}$): Ein leichtgewichtiges neuronales Netz, das mittels Proximal Policy Optimization (PPO) trainiert wurde und als Meta-Policy fungiert. Es beobachtet den aktuellen Zustand (Spielbeobachtung, Planner-Features und Wertschätzungen) und wählt das Budget $k$ (die Dauer der Option) für den nächsten Meta-Schritt.

2. Trainingsprotokoll:

   • Zwei-Phasen-Training: Zuerst werden Basis-AlphaZero-ähnliche Planer für spezifische Umgebungen trainiert. Diese Planer werden anschließend eingefroren. Zweitens wird die Gating-Policy auf dem eingefrorenen Planer trainiert.
   • Meta-MDP-Formulierung: Die Gating-Policy löst ein diskretes Kontrollproblem, bei dem die Aktionen die Auswahl budgetierter Optionen sind. Die Belohnung ist der kumulative Ertrag über die $k$ Frames der Option, diskontiert um $\gamma^k$.
   • Adaptiertes GAE: Da Meta-Schritte variable Dauern ($k$) haben, passen die Autoren die Generalized Advantage Estimation (GAE) an, um den pro-Meta-Schritt-Diskontierungsfaktor $\gamma^k$ durch die Advantage-Berechnung zu tragen.

3. Umwelt-Instanziierungen:

   • Commitment-Aktions-Umgebungen (Pac-Man, Real-Time Tetris, Snake): Die Umgebung schreitet kontinuierlich voran. Der Agent führt $k-1$ Reflex-Aktionen aus, während er plant. Die Kosten des Planens sind die Veränderung des Weltzustands während der Berechnung.
   • Uhren-Umgebungen (Speed Hex, Speed Go): Das Spielfeld ist statisch, aber eine gemeinsame Uhr läuft mit der Denkzeit ab. Die Reflex-Policy gibt während des Planungsfensters „No-Ops“ aus. Die Kosten sind die Reduktion des verbleibenden Zeitbudgets.

Wesentliche Beiträge

1. Variable-Delay Real-Time RL Framework: Eine Verallgemeinerung von Fixed-Delay-Frameworks, in denen der Agent seine eigene Denkzeit wählt und die Auswahl der Verzögerung als lernbares Problem behandelt, statt als systemimmanente Einschränkung.
2. Empirische Charakterisierung von Planungs-Trade-offs: Die Autoren stellen fest, dass die Planungsqualität und die Inferenzlatenz gemeinsam mit der Anzahl der MCTS-Simulationen skalieren. Diese gemeinsame Skalierung motiviert die Notwendigkeit einer adaptiven Allokation anstelle fester Budgets.
3. Adaptive Gating auf eingefrorenen Planern: Eine Methode zum Erlernen zustandsabhängiger Planungsbudgets mithung eines leichtgewichtigen Gating-Policies, das auf einem eingefrorenen AlphaZero-Planer trainiert wurde. Dies vermeidet das Paradoxon des „Planens über das Planen“, da ein einziger Forward-Pass der Gate-Policy um Größenordnungen günstiger ist als ein MCTS-Rollout.
4. Validierung auf Real-World-Hardware: Die Methode wird in einem echten asynchronen Zwei-GPU-Deployment (eine GPU für die Umgebung/Reflex, eine für MCTS) validiert, ohne architektonische Änderungen oder Retraining, was zeigt, dass die in der Simulation trainierte Policy effektiv auf Hardware-getrennte Ausführung transferierbar ist.

Ergebnisse

Die Gating-Policy wurde über fünf Umgebungen evaluiert: Pac-Man, Real-Time Tetris, Snake, Speed Hex und Speed Go.

• Performance vs. Baselines: Die adaptive Gating-Policy übertraf konsistent:
  • Fixed-Budget-Policies: Agenten, die auf ein einzelnes $k$ beschränkt sind (z. B. immer Planung für 1, 2, 3 oder 4 Frames).
  • Heuristische Baselines: Einschließlich „Greedy“ (immer maximale Simulationen) und „Midpeak“ (eine in Game-Engines übliche Glockenkurven-Allokation).
  • Random-Baselines: Das zufällige Wählen von Budgets schnitt signifikant schlechter ab, was bestätigt, dass das Wann der Ressourcenallokation ebenso kritisch ist wie das Wie viel.
• Spezifische Gewinne:
  • Pac-Man: +10,3 % Verbesserung gegenüber dem besten Fixed-Budget.
  • Real-Time Tetris: +65 % Verbesserung gegenüber dem besten Fixed-Budget.
  • Snake: +10,9 % Verbesserung.
  • Speed Hex/Go: Die Gating-Policy erzielte höhere erwartete Scores als sowohl Fixed-Budgets als auch Heuristiken bei variierenden Uhren-Constraints.
• Verhaltensanalyse: Die Gating-Policy lernte, tiefere Planung (höheres $k$) in Hochrisiko- oder eingeschränkten Zuständen zu allokieren (z. B. Geister nahe in Pac-Man, dichte Boards in Tetris, geringe Erreichbarkeit in Snake) und reagierte schnell (niedriges $k$) in sicheren oder offenen Zuständen. Sie zeigte zudem eine Generalisierung auf unterschiedliche Uhren-Budgets in Speed Hex/Go ohne Retraining.
• Hardware-Transfer: In einem asynchronen Zwei-GPU-Setup (H100, A100, A40) transferierten die Policies sauber von der Simulation auf echte Hardware. Die Latenz blieb innerhalb des Budgets auf H100 und A100, und die Erträge entsprachen eng den Simulations-Gegenstücken.

Bedeutung und Behauptungen

Das Paper behauptet, eine fundamentale Diskrepanz zwischen Standard-RL und Echtzeit-Interaktion anzugehen, indem es die Denkzeit als eine Ressource formalisiert, die dynamisch verwaltet werden muss. Die Bedeutung liegt in:

• Vermeidung des Meta-Reasoning-Paradoxons: Durch die Verwendung eines leichtgewichtigen Gates auf einem eingefrorenen Planer vermeidet das System den Rechenaufwand des Planens über das Planen, was den Ansatz für den Echtzeit-Einsatz praktikabel macht.
• Zustandsabhängige Ressourcenallokation: Die Ergebnisse zeigen, dass ein einzelnes festes Planungsbudget suboptimal ist; der Wert der Berechnung ist hochgradig zustandsabhängig.
• Skalierbarkeit auf asynchrone Hardware: Das „Committed-Action“-Training protokolliert die Dynamik asynchroner Ausführung erfolgreich, was es ermöglicht, in Simulation trainierte Policies ohne Modifikation auf separater Hardware (Umgebung vs. Planer) einzusetzen.

Anerkannte Limitationen:

• Das Framework setzt einen perfekten Umgebungssimulator für die Committed-Steps voraus (MCTS muss die $k-1$ Reflex-Aktionen genau vorhersagen).
• Die Gating-Policy wird auf einem eingefrorenen Planer trainiert; die gemeinsame Optimierung von Planer und Gate bleibt zukünftige Arbeit.
• Das Budget-Set $\mathcal{K}$ ist handkalibriert und diskret; kontinuierliche oder reichhaltigere Rechen-Vokabularien werden als zukünftige Erweiterungen vorgeschlagen.