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

Sintesi Tecnica: Trovare il tempo per pensare: Budget di pianificazione dell'apprendimento nel RL in tempo reale

Definizione del Problema: RL in tempo reale con ritardo variabile

Il Reinforcement Learning (RL) standard e i Processi Decisionali di Markov (MDP) operano sotto l'assunto che l'ambiente attenda indefinitamente che l'agente computi un'azione; pertanto, la deliberazione non comporta costi. Nei contesti in tempo reale, questo assunto fallisce: l'ambiente progredisce continuamente indipendentemente dal tempo di computazione dell'agente. Un'azione perfetta eseguita troppo tardi è spesso inferiore a un'azione subottimale eseguita tempestivamente.

Sebbene il lavoro precedente (Ramstedt & Pal, 2019) abbia formalizzato il RL in tempo reale con un ritardo fisso (ad esempio, esattamente un timestep per computare), questo articolo introduce il RL in tempo reale con ritardo variabile. In questo framework, l'agente non è una funzione statica ma una procedura che opera nel tempo. L'agente deve decidere quanto a lungo deliberare ad ogni punto decisionale. Il costo della deliberazione viene "pagato" come progresso ambientale (o esaurimento del tempo in giochi da tavolo) mentre l'agente computa. Ciò crea una sfida di meta-ragionamento: l'agente deve bilanciare la qualità dell'azione pianificata rispetto alla degradazione dello stato causata dal tempo speso a pianificare. Pianificare ingenuamente quanto pianificare rischia di creare un paradosso in cui la meta-decisione stessa incorre negli stessi costi temporali della pianificazione che mira a ottimizzare.

Metodologia

Gli autori propongono una soluzione basata su un Processo Decisionale Semi-Markoviano (SMDP) su opzioni con budget, disaccoppiando l'algoritmo di pianificazione dalla decisione di quanto pianificare.

1. Componenti dell'Architettura:

   • Politica Riflessiva ($\pi_{reflex}$): Una politica leggera e veloce (ad esempio, la testa della policy di un modello AlphaZero senza MCTS) che viene eseguita in molto meno di un frame. Fornisce azioni immediate per l'ambiente mentre il pianificatore gira in background.
   • Computazioni di Raffinamento dell'Azione Anytime ($\{c_k\}$): Un insieme finito di computazioni indicizzate per durata discreta $k$. In questo lavoro, sono istanziate come esecuzioni di Monte Carlo Tree Search (MCTS) per $k$ frame. Le esecuzioni più lunghe ($c_k$) producono azioni di qualità superiore ma richiedono più tempo.
   • Opzioni con Budget ($o_k$): Ogni opzione $o_k$ avvolge una computazione $c_k$. Una volta avviata, l'agente si impegna a eseguire $k-1$ azioni tratte da $\pi_{reflex}$ mentre $c_k$ è in esecuzione. Al $k$-esimo frame, viene eseguita l'azione raffinata da $c_k$.
   • Politica di Gating ($\pi_{gate}$): Una rete neurale leggera addestrata tramite Proximal Policy Optimization (PPO) che funge da meta-politica. Osserva lo stato corrente (osservazione del gioco, feature del pianificatore e stime del valore) e seleziona il budget $k$ (la durata dell'opzione) per il meta-step successivo.

2. Protocollo di Addestramento:

   • Addestramento in due fasi: In primo luogo, vengono addestrati pianificatori di tipo AlphaZero per ambienti specifici. Questi pianificatori vengono poi congelati. In secondo luogo, la politica di gating viene addestrata sopra il pianificatore congelato.
   • Formulazione Meta-MDP: La politica di gating risolve un problema di controllo discreto in cui le azioni sono la selezione di opzioni con budget. La ricompensa è il ritorno cumulativo su $k$ frame dell'opzione, scontato per $\gamma^k$.
   • GAE Adattato: Poiché i meta-step hanno durate variabili ($k$), gli autori adattano la stima dell'vantaggio generalizzato (GAE) per trasportare lo sconto per meta-step $\gamma^k$ attraverso il calcolo dell'vantaggio.

3. Istanze di Ambiente:

   • Ambienti con Azione Impegnata (Pac-Man, Real-Time Tetris, Snake): L'ambiente progredisce continuamente. L'agente esegue $k-1$ azioni riflessive mentre pianifica. Il costo della pianificazione è il cambiamento dello stato del mondo durante la computazione.
   • Ambienti con Orologio (Speed Hex, Speed Go): Il tabellone è statico, ma un orologio condiviso si esaurisce con il tempo di pensiero. La politica riflessiva emette "no-op" durante la finestra di pianificazione. Il costo è la riduzione del budget di tempo rimanente.

Contributi Chiave

1. Framework di RL in tempo reale con ritardo variabile: Una generalizzazione dei framework a ritardo fisso dove l'agente sceglie il proprio tempo di deliberazione, trattando la selezione del ritardo come un problema apprendibile piuttosto che come un vincolo imposto dal sistema.
2. Caratterizzazione Empirica dei Trade-off di Pianificazione: Gli autori stabiliscono che la qualità della pianificazione e la latenza di inferenza scalano insieme al numero di simulazioni MCTS. Questo scaling congiunto motiva la necessità di un'allocazione adattiva piuttosto che di budget fissi.
3. Gating Adattivo su Pianificatori Congelati: Un metodo per apprendere budget di pianificazione dipendenti dallo stato utilizzando una politica di gating leggera addestrata su un pianificatore AlphaZero congelato. Questo evita il paradosso della "pianificazione sulla pianificazione" poiché un singolo passaggio in avanti della gate è ordini di grandezza più economico di un rollout MCTS.
4. Validazione Hardware nel Mondo Reale: Il metodo è validato in un deployment asincrono con due GPU (una per l'ambiente/reflex, una per MCTS) senza cambiamenti architettonici o riaddestramento, dimostrando che la politica addestrata in simulazione si trasferisce efficacementamente all'esecuzione separata su hardware.

Risultati

La politica di gating è stata valutata in cinque ambienti: Pac-Man, Real-Time Tetris, Snake, Speed Hex e Speed Go.

• Performance rispetto ai Baseline: La politica di gating adattiva ha costantemente superato:
  • Politiche a Budget Fisso: Agenti vincolati a un singolo $k$ (ad esempio, pianificare sempre per 1, 2, 3 o 4 frame).
  • Baseline Euristiche: Inclusi "Greedy" (sempre il massimo numero di simulazioni) e "Midpeak" (allocazione a campana tipica dei motori di gioco).
  • Baseline Casuali: La selezione casuale dei budget è stata significativamente peggiore, confermando che quando allocare la computazione è critico quanto quanta se ne deve allocare.
• Guadagni Specifici:
  • Pac-Man: +10,3% di miglioramento rispetto al miglior budget fisso.
  • Real-Time Tetris: +65% di miglioramento rispetto al miglior budget fisso.
  • Snake: +10,9% di miglioramento.
  • Speed Hex/Go: La politica di gating ha ottenuto punteggi attesi più alti sia rispetto ai budget fissi che alle euristiche attraverso diversi vincoli di clock.
• Analisi del Comportamento: La politica di gating ha imparato ad allocare una pianificazione più profonda (alto $k$) in stati ad alto rischio o vincolati (ad esempio, fantasmi vicini in Pac-Man, tabelloni densi in Tetris, bassa raggiungibilità in Snake) e ha reagito rapidamente (basso $k$) in stati sicuri o aperti. Ha inoltre dimostrato di generalizzare a diversi budget di clock in Speed Hex/Go senza riaddestramento.
• Trasferimento Hardware: In un setup asincrono a due GPU (H100, A100, A40), le politiche si sono trasferite pulitamente dalla simulazione all'hardware reale. La latenza è rimasta entro il budget su H100 e A100, e i rendimenti hanno corrisposto strettamente a quelli della simulazione.

Significatività e Rivendicazioni

L'articolo sostiene di affrontare un disallineamento fondamentale tra il RL standard e l'interazione in tempo reale, formalizzando il tempo di deliberazione come una risorsa che deve essere gestita dinamicamente. La significatività risiede nel:

• Evitare il Paradosso della Meta-Ragionamento: Utilizzando una gate leggera su un pianificatore congelato, il sistema evita l'overhead computazionale del pianificare come pianificare, rendendo l'approccio pratico per il deployment in tempo reale.
• Allocazione delle Risorse Dipendente dallo Stato: I risultati dimostrano che un singolo budget di pianificazione fisso è subottimale; il valore della computazione è altamente dipendente dallo stato.
• Scalabilità all'Hardware Asincrono: Il protocollo di addestramento a "azione impegnata" modella con successo la dinamica dell'esecuzione asincrona, consentendo alle politiche addestrate in simulazione di essere distribuite su hardware separato (ambiente vs. pianificatore) senza modifiche.

Limitazioni Riconosciute:

• Il framework assume un simulatore di ambiente perfetto per i passi impegnati (MCTS deve prevedere accuratamente le $k-1$ azioni riflessive).
• La politica di gating è addestrata su un pianificatore congelato; l'ottimizzazione congiunta del pianificatore e della gate è lasciata come lavoro futuro.
• L'insieme dei budget $\mathcal{K}$ è calibrato manualmente e discreto; estensioni continue o vocabolari di computazione più ricchi sono suggeriti come sviluppi futuri.