Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

1. Enunciato del Problema

L'apprendimento per rinforzo (RL) in ambienti su larga scala o continui affronta gravi colli di bottiglia computazionali. Gli algoritmi tradizionali di minimizzazione del rimpianto basati su modello richiedono chiamate frequenti a due tipi di "oracoli":

1. Oracolo di Stima Statistica: Utilizzato per stimare il modello dell'ambiente (dinamiche di transizione e ricompense) dai dati.
2. Oracolo di Ottimizzazione della Politica (Pianificazione): Utilizzato per calcolare la politica ottimale dato il modello stimato.

Gli approcci esistenti soffrono di due limitazioni principali:

• Alta Frequenza di Chiamata agli Oracoli: La maggior parte degli algoritmi richiede $O(T)$ chiamate a questi oracoli, dove $T$ è l'orizzonte temporale, rendendoli computazionalmente proibitivi per $T$ grandi.
• Dipendenza dalla Dimensione dello Spazio degli Stati/Azioni: La complessità della pianificazione spesso scala con la cardinalità dello spazio degli stati ($S$) e dello spazio delle azioni ($A$). Ciò rende i metodi esistenti intrattabili per ambienti con spazi di stati/azioni grandi, infiniti o continui (ad esempio, MDP lineari con stati infiniti).

Mentre lavori recenti (ad esempio, Qian et al., 2024) hanno raggiunto "efficienza dell'oracolo offline" (poche chiamate all'oracolo di stima) per MDP tabulari, la loro complessità dell'oracolo di pianificazione scalava ancora con $S$ e $A$ (specificamente $O(HSA \log \log T)$). Il paper affronta la domanda aperta: Possiamo progettare un algoritmo efficiente sia nell'oracolo di stima che in quello di pianificazione, con complessità indipendente da $S$ e $A$, e applicabile a spazi di stati/azioni infiniti?

2. Metodologia

Gli autori propongono DOERL (Doubly Oracle-Efficient Reinforcement Learning), un nuovo framework algoritmico basato sulla regolarizzazione log-barriera e log-determinante. L'innovazione principale risiede nel modo in cui l'algoritmo gestisce il compromesso tra esplorazione e sfruttamento minimizzando al contempo le chiamate agli oracoli.

Componenti Tecnici Chiave:

1. Apprendimento a Epoche con Aggiornamenti Troncati:

   • Il processo di interazione è diviso in $N$ epoche. All'interno di ogni epoca, l'agente esegue una politica fissa per un segmento di tempo.
   • Crucialmente, l'oracolo di stima offline viene chiamato solo alla fine di ogni epoca (o segmento), aggregando i dati per aggiornare il modello. Ciò riduce il numero di chiamate di stima a $O(N)$.
   • L'oracolo di pianificazione viene invocato solo all'inizio dei segmenti, riducendo significativamente la frequenza di pianificazione.

2. Misure di Occupazione Affidabili:

   • Per evitare di esplorare transizioni stato-azione rare o inaffidabili, l'algoritmo definisce un "insieme di transizioni affidabili" $\mathcal{T}_m^h$.
   • Le transizioni sono considerate "affidabili" solo se la misura di occupazione stimata moltiplicata per la probabilità di transizione supera una soglia ($1/\zeta_m$).
   • Questo concetto, adattato da Qian et al. (2024), è modificato per essere calcolabile senza iterare su tutto lo spazio delle politiche, il che è fondamentale per l'efficienza.

3. Regolarizzazione per l'Esplorazione:

   • Per MDP Tabulari: L'algoritmo utilizza la Regolarizzazione Log-Barriera. L'obiettivo di ottimizzazione della politica include un termine $\sum \log(\text{occupazione affidabile} + \beta)$. Ciò incoraggia l'agente a visitare coppie stato-azione che sono "affidabili" ma hanno bassa probabilità, garantendo un'esplorazione sufficiente senza dover enumerare tutti gli stati.
   • Per MDP Lineari (Spazi Infiniti): L'algoritmo introduce la Regolarizzazione Log-Determinante. Invece di sommare su stati discreti, massimizza il log-determinante della matrice di covarianza delle caratteristiche pesata dalla misura di occupazione affidabile: $\log \det(\mathbf{K} + \beta \mathbf{I})$. Ciò promuove l'esplorazione dello spazio delle caratteristiche, garantendo che l'agente raccolga dati diversificati per stimare accuratamente i coefficienti lineari.

4. Strategia di Aggregazione:

   • L'algoritmo aggrega le stime a livello di strato (kernel di transizione e ricompense) dall'oracolo offline in un unico modello globale per la prossima epoca, invece di aggiornare il modello ad ogni singolo passo.

3. Contributi Chiave

1. Efficienza Doppia degli Oracoli:

   • Il paper presenta il primo algoritmo che raggiunge sia l'efficienza dell'oracolo di stima statistica che l'efficienza dell'oracolo di ottimizzazione della politica.
   • Complessità delle Chiamate agli Oracoli: L'algoritmo richiede solo $O(H \log \log T)$ chiamate a entrambi gli oracoli quando $T$ è noto (e $O(H \log T)$ quando non è noto).
   • Indipendenza dalle Dimensioni: Crucialmente, questa complessità è strettamente indipendente dalla dimensione dello spazio degli stati ($S$) e dalla dimensione dello spazio delle azioni ($A$).

2. Estensione agli Spazi Infiniti:

   • Il framework è generalizzato agli MDP Lineari con spazi di stati infiniti e spazi di azioni arbitrari.
   • È il primo algoritmo efficiente nell'oracolo offline a raggiungere un rimpianto sub-lineare in questo contesto, superando la "maledizione della dimensionalità" che affligge i metodi tabulari.

3. Limiti di Rimpianto Ottimali:

   • MDP Tabulari: Raggiunge il limite di rimpianto ottimale $O(\sqrt{T})$.
   • MDP Lineari: Raggiunge un limite di rimpianto sub-lineare di $O(T^{4/5})$ (con fattori logaritmici), che è significativo per contesti a dimensione infinita sotto i vincoli degli oracoli dati.

4. Risultati

Garanzie teoriche sono stabilite per entrambi i contesti finito (tabulare) e infinito (lineare):

• MDP Tabulari:

  • Rimpianto: $O(\sqrt{T})$ (ottimale).
  • Chiamate agli Oracoli: $O(H \log \log T)$ sia per la stima che per la pianificazione.
  • Confronto: Migliora significativamente rispetto a Qian et al. (2024), che richiedeva $O(HSA \log \log T)$ chiamate di pianificazione.

• MDP Lineari (Stati/Azioni Infiniti):

  • Rimpianto: $O(T^{4/5} \cdot \text{polylog}(T))$.
  • Chiamate agli Oracoli: $O(H \log \log T)$ per entrambi gli oracoli.
  • Significato: Prima di questo lavoro, non esisteva alcun algoritmo in grado di risolvere MDP a stati infiniti con chiamate agli oracoli a tale bassa frequenza mantenendo un rimpianto sub-lineare.

5. Significato e Impatto

• Colmare il Divario tra Teoria e Pratica: Disaccoppiando la complessità computazionale dalla dimensione degli spazi di stati/azioni, questo lavoro rende l'RL basato su modello teoricamente fattibile per applicazioni complesse del mondo reale come la robotica e i sistemi autonomi, dove $S$ e $A$ sono di fatto infiniti.
• Efficienza nei Sistemi su Larga Scala: La riduzione delle chiamate agli oracoli da $O(T)$ o $O(SA)$a$O(\log \log T)$ rappresenta un'enorme riduzione del sovraccarico computazionale, consentendo l'uso di stimatori offline costosi (come le reti neurali profonde) nei loop RL in cui erano precedentemente troppo onerosi.
• Nuovo Paradigma per l'Esplorazione: L'integrazione della regolarizzazione log-barriera e log-determinante con misure "affidabili" fornisce un meccanismo teorico robusto per l'esplorazione che scala elegantemente con la dimensionalità, offrendo una linea guida per futuri algoritmi nel controllo ad alta dimensionalità.

In sintesi, questo paper avanza fondamentalmente lo stato dell'arte nell'Apprendimento per Rinforzo dimostrando che il rimpianto ottimale può essere raggiunto con sovraccarico computazionale minimo (indipendente dalla dimensione dell'ambiente) attraverso una combinazione innovativa di apprendimento a epoche, misure affidabili e regolarizzazione basata sul determinante.