Riepilogo Tecnico: Il riutilizzo delle traiettorie nei Gradienti di Politica consente una convergenza rapida

Definizione del Problema

I metodi di Gradiente di Politica (PG) sono efficaci per i problemi di controllo continuo ma soffrono di una scarsa efficienza campionaria. Gli algoritmi "vanilla" standard di PG (ad esempio, REINFORCE, GPOMDP) si affidano esclusivamente a dati on-policy freschi, richiedendo $O(\epsilon^{-2})$ traiettorie per raggiungere un punto stazionario $\epsilon$-approssimato. Questa inefficienza deriva dall'alta varianza delle stime del gradiente, che non svanisce perché i gradienti sono sempre stimati da nuovi campioni.

Sebbene il riutilizzo di dati passati (traiettorie o gradienti off-policy) sia una strategia comune per migliorare l'efficienza, il lavoro teorico esistente si è concentrato ampiamente sul riutilizzo del gradiente (ad esempio, SVRPG, SRVRPG, STORM-PG), raggiungendo tassi fino a $O(\epsilon^{-3/2})$. Il riutilizzo delle traiettorie passate, sebbene intuitivo, è rimasto in gran parte inesplorato da una prospettiva teorica rigorosa. I tentativi precedenti di riutilizzare le traiettorie erano o privi di garanzie di convergenza o basati su assunzioni forti e stimatori complessi (ad esempio, richiedendo la memorizzazione di tutte le politiche passate o soffrendo di alta varianza a causa di un ingenuo pesatura dell'importanza).

La domanda centrale affrontata è: Il riutilizzo di traiettorie off-policy passate può portare a miglioramenti provabili nella complessità campionaria dei metodi PG?

Metodologia

L'algoritmo RT-PG

Gli autori propongono RT-PG (Reusing Trajectories – Policy Gradient), un nuovo algoritmo che stima il gradiente della politica sfruttando le traiettorie raccolte dalle più recenti $\omega$ iterazioni. L'innovazione principale è lo stimatore Multiple Power Mean (MPM), che combina dati on-policy e off-policy utilizzando uno schema di Multiple Importance Weighting (MIW) corretto.

Lo stimatore MPM

Per affrontare le sfide statistiche del riutilizzo dei dati (specificamente il bias introdotto dalla dipendenza tra gli attuali parametri della politica e le traiettorie passate), lo stimatore MPM impiega due meccanismi chiave:

1. Coefficienti Deterministici: A differenza del Balance Heuristic (BH) che utilizza coefficienti dipendenti da tutte le politiche passate (introducendo il "cross-time bias"), RT-PG utilizza coefficienti deterministici $\alpha_{i,k}$ che dipendono solo dal conteggio delle iterazioni e dall'indice della finestra. Ciò elimina il cross-time bias.
2. Correzione Power Mean (PM): Per garantire che i pesi di importanza rimangano limitati (una proprietà "difensiva") e per controllare il bias introdotto dai coefficienti deterministici, lo stimatore applica una correzione PM ai pesi di importanza vanilla. Il peso corretto per una traiettoria $\tau$ raccolta sotto la politica $\pi_{\theta_i}$ e valutata sotto $\pi_{\theta_k}$ è:
   $$\left( (1 - \lambda_{i,k}) \frac{p_{\theta_i}(\tau)}{p_{\theta_k}(\tau)} + \lambda_{i,k} \right)^{-1}$$
   dove $\lambda_{i,k} \in [0, 1]$ è un parametro di correzione. Questo termine rappresenta una media armonica tra il peso vanilla e 1, garantendo che il peso sia limitato da $1/\lambda_{i,k}$.

Analisi Teorica

Gli autori forniscono un'analisi rigorosa in tempo finito dello stimatore MPM:

• Limiti di Concentrazione: Derivano limiti di concentrazione ad alta probabilità per lo stimatore utilizzando l'ineguaglianza di Freedman per i martingali e un argomento di copertura per gestire la natura vettoriale del gradiente.
• Controllo del Bias: L'analisi separa ed esplicita il controllo di due fonti di bias:
  • Target Bias: Derivante dal fatto che il parametro target $\theta_k$ dipende dalla storia delle traiettorie. Questo è controllato tramite un argomento di copertura su un sottoinsieme dello spazio dei parametri contenente il target dipendente dalla storia.
  • PM Bias: Derivante dal termine di correzione PM. Questo è gestito selezionando attentamente $\lambda_{i,k}$ in base alla dimensione del batch e al limite della divergenza $\chi^2$ tra le distribuzioni delle traiettorie.

Contributi Chiave

1. Prima Evidenza Rigorosa: Il paper fornisce la prima prova teorica che il riutilizzo di traiettorie off-policy passate può accelerare significativamente la convergenza di PG.
2. Nuovo Stimatore (MPM): Introduzione dello stimatore MPM, che mescola efficacemente dati on-policy freschi con traiettorie off-policy delle ultime $\omega$ iterazioni, mantenendo pesi di importanza limitati ed eliminando il cross-time bias.
3. Complessità Campionaria Migliorata:
   • Riutilizzo Parziale: Quando si riutilizzano le traiettorie delle $\omega$ iterazioni più recenti (dove $\omega < K$), RT-PG raggiunge una complessità campionaria di $\tilde{O}(\epsilon^{-2}\omega^{-1})$.
   • Riutilizzo Totale: Quando si riutilizzano tutte le traiettorie passate disponibili (dove $\omega \ge K$), l'algoritmo raggiunge una complessità campionaria di $\tilde{O}(\epsilon^{-1})$. Questo eguaglia i migliori tassi noti in letteratura per i metodi PG e rappresenta un miglioramento significativo rispetto al tasso standard $O(\epsilon^{-2})$.
4. Implementazione Pratica: Viene proposta una variante pratica di RT-PG che pesa adattivamente i dati off-policy in base a stime empiriche della dissimilarità (divergenza) delle politiche, eliminando la necessità del limite globale teorico $D$ nella pratica.

Risultati

Risultati Teorici

Sotto assunzioni standard (divergenza $\chi^2$ limitata tra le distribuzioni delle traiettorie e regolarità della classe di politiche), gli autori dimostrano che RT-PG trova un punto stazionario $\epsilon$-approssimato con:

• Complessità campionaria $\tilde{O}(\epsilon^{-1})$ nel regime di riutilizzo totale.
• Complessità campionaria $\tilde{O}(\epsilon^{-2}\omega^{-1})$ nel regime di riutilizzo parziale.

Questi risultati valgono senza richiedere la memorizzazione delle politiche passate (a differenza dei metodi basati su BH), richiedendo solo la memorizzazione delle traiettorie passate.

Risultati Empirici

Gli esperimenti sono stati condotti su compiti di controllo continuo (Cart Pole, Half Cheetah, Swimmer) utilizzando politiche Gaussiane lineari e profonde.

• Efficienza Campionaria: RT-PG supera costantemente le baseline on-policy standard (GPOMDP) e i metodi di riduzione della varianza allo stato dell'arte (SVRPG, SRVRPG, STORM-PG, DEF-PG) in termini di efficienza campionaria. Nell'ambiente Half Cheetah, RT-PG ha raggiunto quasi il doppio delle prestazioni finali rispetto alla maggior parte delle baseline.
• Impatto del Riutilizzo delle Traiettorie: Gli esperimenti variando la dimensione della finestra $\omega$ hanno dimostrato che l'aumento della finestra di riutilizzo accelera la convergenza. RT-PG ha mostrato rendimenti decrescenti per finestre molto grandi, ma ha superato significativamente le baseline anche con un riutilizzo moderato.
• Confronto con il Riutilizzo Naive: RT-PG ha superato significativamente MIW-PG (che utilizza una pesatura uniforme), validando l'efficacia della correzione PM e dello schema di pesatura adattiva nel controllare la varianza.
• Efficienza della Memoria: A differenza dei metodi BH che richiedono la memorizzazione di tutti i parametri delle politiche passate per calcolare i pesi, RT-PG richiede solo la memorizzazione delle traiettorie passate, rendendolo più scalabile per spazi di policy ad alta dimensionalità.

Significato e Rivendicazioni

Il paper sostiene di fornire la prima evidenza teorica rigorosa che il riutilizzo delle traiettorie sia un meccanismo vitale e potente per accelerare la convergenza del Gradiente di Politica. Introducendo l'algoritmo RT-PG e lo stimatore MPM, gli autori colmano il divario tra l'idea intuitiva di riutilizzare i dati passati e le garanzie di convergenza dimostrabili.

La significatività risiede in:

1. Avanzamento Teorico: Stabilire che il riutilizzo delle traiettorie può raggiungere il tasso $\tilde{O}(\epsilon^{-1})$, precedentemente ritenuto difficile per i metodi PG senza assunzioni forti o riutilizzo del gradiente.
2. Utilità Pratica: Dimostrare che il riutilizzo delle traiettorie riduce il costo di campionamento senza compromettere la stabilità dell'apprendimento, offendo un'alternativa pratica ai metodi di riutilizzo del gradiente che possono richiedere batch più grandi o tecniche complesse di riduzione della varianza.
3. Efficienza della Memoria: Ottenere tassi migliorati senza l'overhead di memoria della memorizzazione delle parametrizzazioni delle politiche passate, un limite di altri approcci di riutilizzo delle traiettorie come il Balance Heuristic.

Gli autori rimangono modesti riguardo ai limiti, notando che i loro risultati si basano sull'assunzione di una divergenza $\chi^2$ limitata tra le distribuzioni delle traiettorie e che la complessità campionaria dipende dalla dimensionalità del parametro $d_\Theta$. Identificano la rimozione di tale assunzione e l'eliminazione della dipendenza dalla dimensione come lavori futuri.