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

Technische Samenvatting: Tijd vinden om na te denken: Leren van planningsbudgetten in Real-Time RL

Probleemdefinitie: Variabele Vertraging in Real-Time RL

Standaard Reinforcement Learning (RL) en Markov Decision Processes (MDPs) werken onder de aanname dat de omgeving onbeperkt wacht tot de agent een actie heeft berekend; deliberatie brengt dus geen kosten met zich mee. In real-time settings faalt deze aanname: de omgeving vordert continu, ongeacht de berekeningstijd van de agent. Een perfecte actie die te laat wordt uitgevoerd, is vaak inferieur aan een tijdige, suboptimale actie.

Hoewel eerder werk (Ramstedt & Pal, 2019) real-time RL formaliseerde met een vaste vertraging (bijv. precies één tijdstap om te berekenen), introduceert dit artikel Variabele-Vertragings Real-Time RL. In dit kader is de agent niet een statische functie, maar een procedure die in de tijd draait. De agent moet beslissen hoe lang er bij elk besluitpunt nagedacht (gedelibereerd) moet worden. De kosten van deliberatie worden "betaald" in de vorm van omgevingsprogressie (of het uitgeput raken van de klok in bordspellen) terwijl de agent plant. Dit creëert een meta-redeneeruitdaging: de agent moet de kwaliteit van de geplande actie afwegen tegen de degradatie van de staat veroorzaakt door de tijd die aan planning wordt besteed. Naief plannen hoe lang men moet plannen riskeert een paradox waarbij de meta-beslissing zelf dezelfde real-time kosten met zich meebrengt als de planning die zij probeert te optimaliseren.

Methodologie

De auteurs stellen een oplossing voor op basis van een Semi-Markov Decision Process (SMDP) over gebudgeteerde opties, waarbij het planningsalgoritme wordt ontkoppeld van de beslissing over hoeveel er gepland wordt.

1. Architectuurcomponenten:

   • Reflex Policy ($\pi_{reflex}$): Een snelle, lichte policy (bijv. de policy head van een AlphaZero-model zonder MCTS) die in veel minder dan één frame draait. Deze levert onmiddellijke acties voor de omgeving terwijl de planner op de achtergrond draait.
   • Anytime Action-Refinement Computations ($\{c_k\}$): Een eindige set berekeningen geïndexeerd door discrete duur $k$. In dit werk zijn dit MCTS-runs voor $k$ frames. Langere runs ($c_k$) produceren kwalitatief betere acties maar kosten meer tijd.
   • Budgeted Options ($o_k$): Elke optie $o_k$ omvat een berekening $c_k$. Wanneer geïnitieerd, committeert de agent zich aan het uitvoeren van $k-1$ acties afkomstig uit $\pi_{reflex}$ terwijl $c_k$ draait. Op het $k$-de frame wordt de verfijnde actie van $c_k$ uitgevoerd.
   • Gating Policy ($\pi_{gate}$): Een lichte neurale netwerk getraind via Proximal Policy Optimization (PPO) dat fungeert als een meta-policy. Het observeert de huidige staat (game observatie, planner features en waarde-inschattingen) en selecteert het budget $k$ (de duur van de optie) voor de volgende meta-stap.

2. Trainingsprotocol:

   • Twee-fasen Training: Eerst worden base AlphaZero-stijl planners getraind voor specifieke omgevingen. Deze planners worden vervolgens bevroren. Ten tweede wordt de gating policy getraind bovenop de bevroren planner.
   • Meta-MDP Formulering: De gating policy lost een discreet controleprobleem op waarbij de acties de selectie van gebuttede opties zijn. De beloning is het cumulatieve rendement over de $k$ frames van de optie, gedisconteerd met $\gamma^k$.
   • Aangepaste GAE: Omdat meta-stappen variabele duur hebben ($k$), passen de auteurs Generalized Advantage Estimation (GAE) aan om de per-meta-stap korting $\gamma^k$ door de advantage-berekening te voeren.

3. Omgevingen:

   • Committed-Action Environments (Pac-Man, Real-Time Tetris, Snake): De omgeving vordert continu. De agent voert $k-1$ reflex-acties uit terwijl er gepland wordt. De kosten van planning zijn de verandering van de wereldtoestand tijdens de berekening.
   • Clock Environments (Speed Hex, Speed Go): Het bord is statisch, maar een gedeelde klok loopt leeg met de denktijd. De reflex policy zendt "no-ops" uit tijdens de planningvenster. De kosten zijn de reductie van het resterende tijdbudget.

Belangrijkste Bijdragen

1. Variabele-Vertragings Real-Time RL Framework: Een generalisatie van vaste-vertragings frameworks waarbij de agent zijn eigen deliberatietijd kiest, waarbij de selectie van vertraging wordt behandeld als een leerbaar probleem in plaats van een door het systeem opgelegde beperking.
2. Empirische Karakterisering van Planningsafwegingen: De auteurs stellen vast dat de kwaliteit van planning en de inferentie-latentie samen schalen met het aantal MCTS-simulaties. Deze gezamenlijke schaling motiveert de noodzaak voor adaptieve allocatie in plaats van vaste budgetten.
3. Adaptieve Gating op Bevroren Planners: Een methode om staat-afhankelijke planningsbudgetten te leren met behulp van een lichte gating policy die getraind is bovenop een bevroren AlphaZero-planner. Dit vermijdt de "plannen-over-plannen" paradox omdat een enkele gate forward pass orders van grootte goedkoper is dan een MCTS-rollout.
4. Validatie op Real-World Hardware: De methode wordt gevalideerd in een echte asynchrone, twee-GPU deployment (één GPU voor de omgeving/reflex, één voor MCTS) zonder architecturale wijzigingen of hertraining, wat aantoont dat de in simulatie getrainde policy effectief overdraagt naar hardware-gescheiden uitvoering.

Resultaten

De gating policy werd geëvalueerd in vijf omgevingen: Pac-Man, Real-Time Tetris, Snake, Speed Hex en Speed Go.

• Prestaties versus Baselines: De adaptieve gating policy presteerde consequent beter dan:
  • Fixed-Budget Policies: Agenten die beperkt zijn tot een enkele $k$ (bijv. altijd plannen voor 1, 2, 3 of 4 frames).
  • Heuristische Baselines: Inclusief "Greedy" (altijd maximale simulaties) en "Midpeak" (de bell-curve allocatie die gebruikelijk is in game engines).
  • Random Baselines: Het willekeurig selecteren van budgetten presteerde aanzienlijk slechter, wat bevestigt dat wanneer men compute toewijst even cruciaal is als hoeveel.
• Specifieke Winsten:
  • Pac-Man: +10,3% verbetering ten opzien van het beste vaste budget.
  • Real-Time Tetris: +65% verbetering ten opzien van het beste vaste budget.
  • Snake: +10,9% verbetering.
  • Speed Hex/Go: De gating policy behaalde hogere verwachte scores dan zowel vaste budgetten als heuristieken bij variërende klokbeperkingen.
• Gedragsanalyse: De gating policy leerde om diepere planning (hogere $k$) toe te wijzen in situaties met hoge inzet of beperkingen (bijv. spoken dichtbij in Pac-Man, dichte borden in Tetris, lage bereikbaarheid in Snake) en reageerde snel (lage $k$) in veilige of open staten. Het demonstreerde ook generalisatie naar verschillende klokbudgetten in Speed Hex/Go zonder hertraining.
• Hardware Transfer: In een twee-GPU asynchrone setup (H100, A100, A40) werden de policies schoon overgedragen van simulatie naar echte hardware. De latentie bleef binnen het budget op H100 en A100, en de returns kwamen nauw overeen met de simulatie-tegenhangers.

Betekenis en Claims

Het artikel beweert een fundamentele mismatch tussen standaard RL en real-time interactie aan te pakken door deliberatietijd te formaliseren als een hulpbron die dynamisch beheerd moet worden. De significantie ligt in:

• Ontsnappen aan de Meta-Redeneerparadox: Door een lichte gate te gebruiken op een bevroren planner, vermijdt het systeem de computationele overhead van het plannen over het plannen, wat de aanpak praktisch maakt voor real-time implementatie.
• Staat-Afhankelijke Resource Allocatie: De resultaten tonen aan dat een enkel vast planningsbudget suboptimal is; de waarde van computation is sterk staat-afhankelijk.
• Schaalbaarheid naar Asynchrone Hardware: Het "committed-action" trainingsprotocol modelleert succesvol de dynamiek van asynchrone uitvoering, waardoor policies getraind in simulatie kunnen worden ingezet op gescheiden hardware (omgeving vs. planner) zonder modificatie.

Erkende Beperkingen:

• Het framework gaat uit van een perfecte omgeving-simulator voor de committed stappen (MCTS moet de $k-1$ reflex-acties nauwkeurig voorspellen).
• De gating policy wordt getraind op een bevroren planner; gezamenlijke optimalisatie van de planner en de gate is overgelaten aan toekomstig werk.
• De budgetset $\mathcal{K}$ is handmatig gekalibreerd en discreet; continue of rijkere compute-vocabularies worden gesuggereerd als toekomstige uitbreidingen.