Riepilogo Tecnico: Imparare Quando Fermarsi: Apprendimento per Imitazione Selettiva Sotto Spostamenti Arbitrari delle Dinamiche

1. Formulazione del Problema

Il documento affronta la sfida dell'Apprendimento per Imitazione (IL) in contesti in cui le dinamiche di transizione dell'ambiente di test differiscono arbitrariamente dall'ambiente di addestramento. Nell'IL offline classico, un agente addestrato su dimostrazioni di esperti provenienti da un ambiente sorgente $M$ viene dispiegato in un ambiente target $N$. Se i supporti degli stati di $M$ e $N$ sono disgiunti o significativamente spostati, una politica standard può performare arbitrariamente male perché non riesce a riconoscere quando i suoi dati di addestramento non forniscono più indicazioni affidabili.

Gli autori propongono un framework per l'Apprendimento per Imitazione Selettiva, in cui all'agente viene concessa la possibilità di astenersi (fermare l'esecuzione) a metà traiettoria quando rileva che lo stato corrente si trova al di fuori del supporto affidabile dei suoi dati di addestramento. L'obiettivo è apprendere una politica selettiva $(\pi, \tau)$, composta da una politica di base $\pi$ e un tempo di arresto $\tau$, che soddisfi due obiettivi in competizione:

1. Completezza: La politica dovrebbe astenersi raramente nell'ambiente di addestramento $M$ (cioè, $\alpha_M(\pi, \tau) \le \epsilon$).
2. Correttezza: La politica dovrebbe incorrere in un basso rimpianto nell'ambiente di test $N$ prima di fermarsi (cioè, $Regret_N(\pi, \tau) \le \epsilon$).

Il contesto assume l'accesso a:

• Rollout di addestramento etichettati: Coppie stato-azione $(s, a)$ dall'esperto $\pi^\star$ nell'ambiente $M$.
• Rollout di test non etichettati: Traiettorie solo di stati dall'esperto $\pi^\star$ nell'ambiente $N$. Questa asimmetria modella scenari reali in cui la telemetria delle azioni è costosa o proprietaria (ad esempio, riprese dashcam per la guida autonoma senza comandi di sterzata).

2. Metodologia: SeqRejectron

L'algoritmo centrale, SeqRejectron, generalizza l'algoritmo Rejectron dalla classificazione selettiva (Goldwasser et al., 2020) al processo decisionale sequenziale. L'idea chiave è che, invece di prendere decisioni indipendenti a ogni passo temporale (il che porta a una complessità di campionamento dipendente dall'orizzonte), l'algoritmo certifica interi prefissi di traiettoria utilizzando un insieme sparso di politiche validatrici.

Meccanismo Centrale

1. Politica di Base: L'agente seleziona una politica di base $\pi_0$ coerente con i dati di addestramento (ad esempio, Massima Verosimiglianza).
2. Insiemi di Validazione: L'algoritmo costruisce un piccolo insieme di politiche "validatrici" $\Phi$ estratte dallo spazio delle versioni (politiche coerenti con i dati di addestramento).
3. Regola di Arresto: L'agente esegue $\pi_0$ e continua solo finché ogni validatore in $\Phi$ concorda con $\pi_0$. Il primo punto di disaccordo innesca un arresto (astensione).
4. Distribuzione Sparsa dei Validatori: Un contributo teorico critico è la dimostrazione che un insieme di validatori sparso (dimensione indipendente dall'orizzonte $H$) è sufficiente a garantire la sicurezza. Ciò è ottenuto tramite un argomento minimax su un gioco a somma zero tra un "sfidante" (che sceglie una politica concorrente) e un "validatore" (che sceglie un insieme di validatori).

Varianti per Contesti Diversi

Il documento adatta questo framework a tre contesti progressivamente più generali:

• Politiche Deterministiche:

  • Meccanismo: Utilizza un test di disaccordo binario. Il tempo di arresto $\tau$ è il primo passo in cui qualsiasi validatore $\pi \in \Phi$ non concorda con $\pi_0$.
  • Implementazione: La distribuzione dei validatori è costruita utilizzando dinamiche senza rimpianto (specificamente, una riduzione efficiente per oracolo all'Apprendimento Multi-istanza Realizzabile Ponderata).
  • Risultato: Raggiunge una complessità di campionamento libera dall'orizzonte $\tilde{O}(\sqrt{\log|\Pi|/n})$ sotto costi sparsi.

• Politiche Stocastiche:

  • Sfida: Il disaccordo binario è troppo grossolano; le distribuzioni possono differire "morbidamente" a ogni passo senza una singola discrepanza allarmante.
  • Meccanismo: Sostituisce il test binario con un tempo di arresto basato sulla distanza di Hellinger cumulativa. L'agente si ferma quando la distanza di Hellinger quadratica accumulata tra $\pi_0$ e qualsiasi validatore supera una soglia $\theta$.
  • Risultato: Fornisce limiti su campioni finiti per la distanza di Hellinger delle traiettorie fermate. Il documento stabilisce un limite inferiore $\Omega(1/\epsilon^3)$ per la complessità di campionamento etichettato nel contesto stocastico a singolo passo, corrispondente alla parte guidata dal costo del limite superiore.

• Classi di Politiche Specificate Erroneamente:

  • Sfida: L'esperto $\pi^\star$ potrebbe non rientrare nella classe di politiche dell'agente $\Pi$.
  • Meccanismo: Sostituisce il vincolo rigido dello spazio delle versioni con un gioco regolarizzato simmetricamente. Ai validatori è consentito non concordare con la politica di base sui dati sorgente, ma tale disaccordo è penalizzato.
  • Risultato: I garanzie decadono in modo graduale con la quantità di specificazione errata (misurata dall'errore di specificazione errata migliore nella classe $\Delta$).

3. Contributi Chiave e Risultati

Garanzie Teoriche

• Complessità Libera dall'Orizzonte: Per le politiche deterministiche, la complessità di campionamento è indipendente dall'orizzonte $H$ (eccetto attraverso la scala totale dei costi $C_{max}$), scalando come $\tilde{O}(\sqrt{\log|\Pi|/n})$. Questo migliora le riduzioni naive passo-passo che subiscono una penalità $O(H^2)$.
• Validazione Sparsa: Il documento dimostra l'esistenza di una distribuzione di validatori supportata su insiemi di dimensione $O(1/\epsilon)$, indipendente dallo spazio degli stati, dallo spazio delle azioni o dall'orizzonte.
• Limiti Inferiori: Gli autori dimostrano un limite inferiore $\Omega(1/\epsilon^3)$ per la complessità di campionamento etichettato nel contesto stocastico a singolo passo, mostrando che la dipendenza cubica da $1/\epsilon$ è inevitabile per i regimi guidati dal costo.
• Robustezza alla Specificazione Errata: Il framework si estende a contesti agnostici in cui l'esperto non è nella classe, con limiti di rimpianto che scalano con la radice quadrata dell'errore di specificazione errata.

Valutazione Empirica

Gli autori valutano SeqRejectron nell'ambiente LunarLander-v3.

• Configurazione: L'addestramento avviene in un ambiente senza vento; il test avviene in un ambiente ventoso con impulsi iniziali diversi.
• Risultati: L'algoritmo rileva con successo dinamiche fuori distribuzione. Regolando una soglia di sicurezza $\theta$, gli autori dimostrano un compromesso in cui la politica si astiene minimamente sui dati in distribuzione (addestramento) mentre si ferma in modo affidabile sui dati fuori distribuzione (test), prevenendo fallimenti catastrofici. Il numero di validatori si è rivelato robusto, con le prestazioni che si saturano rapidamente.

4. Significato e Affermazioni

Il documento afferma di stabilire l'astensione come una risposta principiale e teoricamente fondata agli spostamenti di dinamiche imprevisti nell'apprendimento per imitazione.

• Oltre le Euristiche: A differenza degli approcci di RL robusto o di randomizzazione del dominio che richiedono assunzioni sulla natura dello spostamento o accesso online alla distribuzione di test, SeqRejectron fornisce garanzie PAC senza distribuzione utilizzando solo dati offline.
• Analogo Sequenziale dell'Apprendimento PQ: Il lavoro si posiziona come un analogo sequenziale del framework di apprendimento PQ (Goldwasser et al., 2020), estendendo la capacità di astenersi da singole previsioni a interi prefissi di traiettoria.
• Meccanismo di Sicurezza: Disaccoppiando la decisione di cosa fare da quando fermarsi, il framework offre un meccanismo di sicurezza che impedisce all'agente di spingere il sistema in stati irrecuperabili quando i suoi dati di addestramento non sono informativi.

Gli autori riconoscono le limitazioni, notando che il contesto stocastico attualmente manca di una riduzione computazionale efficiente per oracolo (a differenza del caso deterministico) e che i tassi di complessità di campionamento guidati dalla varianza per le politiche stocastiche rimangono un divario aperto tra i limiti superiori e inferiori. Suggeriscono inoltre che un lavoro futuro potrebbe incorporare conoscenze strutturali parziali (ad esempio, distanza TV limitata) per stringere i tassi di arresto sul lato del test.