Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Data

1. Problema e Contesto

Il lavoro si concentra sul problema del Regolatore Lineare Quadratico (LQR) per sistemi soggetti a rumore stocastico additivo (rumore di processo non limitato). L'obiettivo è ottimizzare una politica di controllo lineare $u_t = Kx_t$ per minimizzare un costo medio a orizzonte infinito, senza avere accesso al modello dinamico del sistema (matrici $A$ e $B$ sconosciute).

Mentre i metodi di Policy Gradient (PG) sono ben studiati per LQR deterministici o con dati privi di rumore, esiste una lacuna teorica significativa riguardo alla loro convergenza in presenza di rumore stocastico non limitato (es. rumore gaussiano). In scenari reali, i dati di traiettoria sono rumorosi, rendendo le stime del gradiente e della covarianza imprecise. La sfida principale è quantificare come questi errori di stima si propaghino nell'algoritmo e garantire la convergenza globale verso la soluzione ottima, o almeno verso una soluzione sub-ottima con un errore controllato.

2. Metodologia

Gli autori adottano un approccio model-free basato sull'ottimizzazione di ordine zero (zeroth-order optimization). Invece di calcolare il gradiente analiticamente (che richiederebbe il modello), lo stimano direttamente dai dati di traiettoria.

• Stima del Gradiente e della Covarianza: Utilizzano tecniche di perturbazione casuale (esplorazione) su una sfera di raggio $r$ per stimare il gradiente della funzione di costo e la matrice di covarianza dello stato.
• Analisi dell'Errore di Stima: A differenza di lavori precedenti che assumevano dati limitati (bounded), questo lavoro gestisce il rumore non limitato. Introducono un'analisi basata su eventi (event-based analysis) per garantire che le traiettorie rimangano limitate con alta probabilità, utilizzando disuguaglianze di concentrazione matriciale (Matrix Bernstein/Hanson-Wright).
• Tecniche di Ottimizzazione Proposte:
  1. Policy Gradient Descent (PGD) e Natural Policy Gradient (NPG): Analizzati sia in versione basata su modello (per confronto) che model-free.
  2. Step Size Adattivo: Viene proposta una strategia di passo adattivo che varia in base al costo corrente e al livello di rumore, superando i limiti dei passi fissi.
  3. Riduzione della Varianza: Viene introdotta una tecnica di riduzione della varianza utilizzando una funzione di baseline stimata dai dati per ridurre la complessità del campione necessaria.

3. Contributi Chiave

1. Garanzie di Convergenza Globale Probabilistiche:
   Il lavoro fornisce le prime garanzie di convergenza globale per metodi PG model-free su LQR infinito con rumore stocastico additivo non limitato. Dimostrano che, con una probabilità predefinita, l'algoritmo converge a una soluzione entro una soglia di accuratezza $\epsilon$ dalla soluzione ottima.

2. Analisi della Complessità del Campione (Sample Complexity):
   Vengono derivati limiti superiori espliciti per il numero di roll-out (traiettorie) necessari ($n$), la lunghezza del roll-out ($l$) e il raggio di esplorazione ($r$) per raggiungere una data accuratezza. Questi limiti tengono conto esplicitamente della varianza del rumore ($\Sigma_w$).

3. Introduzione di Step Size Adattivi:
   Viene dimostrato che l'uso di step size adattivi (basati sul costo corrente $C(K_i)$) migliora il tasso di convergenza rispetto agli step size fissi, specialmente in presenza di rumore, permettendo di mantenere la stabilità dell'algoritmo.

4. Tecnica di Riduzione della Varianza con Baseline:
   Viene proposta e analizzata una nuova tecnica di riduzione della varianza per l'ottimizzazione di ordine zero in contesti stocastici. Gli autori dimostrano teoricamente che l'uso di una baseline stimata riduce la complessità del campione necessaria per raggiungere una certa accuratezza del gradiente.

5. Caratterizzazione della Robustezza:
   L'analisi quantifica come l'errore di stima del gradiente e della covarianza influenzi il tasso di convergenza. Viene mostrato che, se l'errore di stima è sufficientemente piccolo, la convergenza è garantita, ma il tasso di convergenza è ridotto da un fattore $(1-\sigma)$ rispetto al caso privo di rumore.

4. Risultati Principali

• Convergenza Lineare: Sia per PGD che per NPG, viene dimostrata una convergenza lineare (geometrica) verso una soluzione $\epsilon$-ottima.
• Effetto del Rumore: Il rumore stocastico impone un limite inferiore all'errore di approssimazione raggiungibile con un numero finito di campioni. Per ottenere una maggiore accuratezza, è necessario ridurre l'errore di stima (aumentando $n$ e $l$) e ridurre lo step size.
• Vantaggio della Riduzione della Varianza: Le simulazioni e le analisi teoriche confermano che la tecnica di riduzione della varianza riduce significativamente il numero di campioni necessari, specialmente in scenari ad alto rumore.
• Confronto Model-based vs Model-free: Mentre i metodi model-based convergono alla soluzione ottima esatta, i metodi model-free convergono a una soluzione sub-ottima la cui distanza dall'ottimo dipende dalla precisione della stima del gradiente e dalla varianza del rumore. Tuttavia, la qualità qualitativa delle garanzie di convergenza rimane simile.

5. Significato e Impatto

Questo studio colma un divario teorico importante nel campo del Reinforcement Learning e del controllo adattivo.

• Robustezza Teorica: Fornisce un fondamento matematico rigoroso per l'applicazione di algoritmi PG model-free in ambienti reali, dove il rumore è inevitabile e spesso non limitato.
• Guida Pratica: Offre linee guida concrete per la sintonizzazione dei parametri degli algoritmi (come il passo di apprendimento, il numero di campioni e il raggio di esplorazione) in base al livello di rumore del sistema.
• Efficienza: La dimostrazione che la riduzione della varianza può migliorare la complessità del campione in contesti stocastici offre un percorso per rendere gli algoritmi di controllo più efficienti dal punto di vista del campionamento.

In sintesi, il lavoro dimostra che i metodi di Policy Gradient model-free possono essere resi robusti e garantiti anche in presenza di rumore stocastico significativo, purché si adottino strategie appropriate di stima, riduzione della varianza e adattamento dei parametri.