Sintesi Tecnica: Apprendimento per Rinforzo Robusto con Ricompensa Media Model-Free con Analisi della Complessità Campionaria

1. Formulazione del Problema

Il paper affronta la sfida dell'Apprendimento per Rinforzo Robusto (Robust RL) sotto il criterio della ricompensa media. Sebbene l'RL abbia ottenuto successi in ambienti controllati, l'implementazione nel mondo reale soffre spesso del divario "Sim-to-Real" dovuto a discrepanze del modello, perturbazioni ambientali o attacchi avversari. Il Robust RL mitiga questo problema ottimizzando le prestazioni nel caso peggiore all'interno di un insieme di incertezza delle dinamiche di transizione.

L'attenzione specifica è rivolta ai MDP con ricompensa media distribuzionalmente robusti (RAMDP). A differenza degli scenari a ricompensa scontata (discounted), il criterio della ricompensa media è essenziale per le prestazioni stazionarie a lungo termine in applicazioni come il controllo delle code e l'ottimizzazione dei portafogli. Tuttavia, il robust average-reward RL è significativamente più complesso rispetto alla sua controparte scontata a causa di:

1. Operatori non contrattivi: L'operatore di Bellman robusto è generalmente non-espansivo piuttosto che contrattivo, invalidando le normali garanzie di convergenza iterativa.
2. Incognite duali: L'equazione di Bellman robusta coinvolge due variabili ignote: la funzione di valore (o bias) $Q$ e la ricompensa media ottimale $g^*_P$.
3. Non-linearità: Stimare l'aspettativa del caso peggiore (funzione di supporto) da campioni nominali introduce un bias, particolarmente nei contesti model-free.

La letteratura esistente si basa ampiamente su garanzie asintotiche, approcci model-based che richiedono la conoscenza preventiva dei parametri del problema (come l'ampiezza del bias $H$), o metodi basati sulla riduzione che soffrono di una complessità campionaria sub-ottimale o richiedono forti assunzioni strutturali (ad esempio, l'irriducibilità con specifici coefficienti di contrazione).

2. Metodologia: Iterazione di Halpern Robusta (RHI)

Gli autori propongono l'Iterazione di Halpern Robusta (RHI), un algoritmo model-free progettato per risolvere l'equazione di Bellman robusta senza richiedere la conoscenza preventiva dei parametri dell'MDP.

2.1. Nucleo Algoritmico

L'algoritmo RHI si ispira all'Iterazione di Halpern dalla letteratura dell'ottimizzazione, adattata per gestire le sfide specifiche del robust average-reward RL:

• Formulazione nello Spazio Quoziente: Per affrontare la "maledizione delle variabili duali" (l'incognita $g^*_P$), gli autori immergono il problema in uno spazio quoziente $\mathbb{R}^{SA} / \sim$, dove i vettori che differiscono solo per uno spostamento costante sono equivalenti. Ciò consente all'algoritmo di risolvere l'equazione prossimale $T_P(Q) - Q = ce$ senza conoscere esplicitamente $g^*_P$.
• Aggiornamento di Halpern: Invece della standard iterazione di valore, RHI utilizza una combinazione convessa dell'inizializzazione e dell'aggiornamento dell'operatore:
  $$[Q_{k+1}] = [(1 - \beta_{k+1})Q_0 + \beta_{k+1} T_P(Q_k)]$$
  dove $\beta_k = k/(k+2)$. Questo approccio fornisce garanzie di convergenza per operatori non-espansivi senza fare affidamento su coefficienti di contrazione.

2.2. Oracle di Campionamento Black-Box (R-SAMPLE)

Poiché l'operatore robusto $T_P$ è non lineare e coinvolge un'aspettativa del caso peggiore, gli autori introducono un oracle di campionamento black-box, R-SAMPLE. Questo oracle stima la differenza tra le funzioni di supporto robuste in iterazioni consecutive utilizzando solo campioni dal kernel nominale.

• L'oracle restituisce un incremento casuale $D_k$ la cui aspettativa approssima la differenza tra i valori dell'operatore di Bellman robusto.
• La complessità campionaria dell'algoritmo è derivata dalle proprietà di questo oracle (costante di Lipschitz, bias e costo del campione).

2.3. Stimatore Monte Carlo Multi-Livello (MLMC) di Ordine K

Per implementare concretamente l'oracle R-SAMPLE con basso bias, gli autori propongono un estimatore MLMC di ordine K.

• Motivazione: Gli stimatori plug-in standard e gli stimatori MLMC vanilla per le funzioni di supporto robuste soffrono di un bias di $O(1/N)$, portando a una complessità campionaria di $\tilde{O}(\epsilon^{-3})$.
• Meccanismo: L'estimatore di ordine K costruisce una combinazione lineare di stimatori a singolo livello a diverse dimensioni di campione ($N_\ell = 2^\ell N_0$). Scegliendo accuratamente i pesi $w^{(K)}_\ell$, l'estimatore annulla i primi $K$ termini dell'espansione del bias.
• Risultato: Ciò riduce il bias a $\tilde{O}(N_0^{-(K+1)})$, permettendo una complessità campionaria complessiva molto più stretta.

3. Contributi Chiave

1. Un Algoritmo Model-Free Universale: RHI è il primo algoritmo model-free per il robust average-reward RL che non richiede la conoscenza preventiva dell'ampiezza del bias robusto $H$ o del tempo di miscelazione (mixing time), superando i limiti degli approcci basati sulla riduzione.
2. Estimatore MLMC di Ordine K: Gli autori progettano un nuovo stimatore che riduce significativamente il bias rispetto ai precedenti metodi MLMC. Questo è cruciale per raggiungere una complessità campionaria vicino all'ottimo in presenza di funzioni di supporto robuste non lineari.
3. Analisi della Complessità Campionaria Finita: Il paper fornisce un'analisi rigorosa della complessità campionaria finita per RHI in un contesto di modello generativo.
   • Per gli insiemi di incertezza KL e $\chi^2$, la complessità campionaria per trovare una politica $\epsilon$-ottimale è $\tilde{O}\left(SAH^2 \epsilon^{-(2+o(1))}\right)$.
   • Per gli insiemi $\ell_p$-norm e contaminazione, la complessità è $\tilde{O}\left(SAH^2 \epsilon^{-2}\right)$.
   • Qui, $S$ e $A$ sono il numero di stati e azioni, e $H$ è l'ampiezza del bias ottimale robusto.
4. Variante Senza Parametri (PF-RHI): Gli autori propongono una variante di RHI che utilizza un "doubling trick" per determinare dinamicamente il numero di iterazioni, eliminando la necessità di pre-specificare l'orizzonte basato sul parametro ignoto $H$, mantenendo la stessa complessità campionaria.

4. Risultati e Garanzie Teoriche

• Convergenza: Si dimostra che l'algoritmo RHI esatto converge asintoticamente, con l'ampiezza del residuo di Bellman e il gap di sub-ottimalità che svaniscono all'aumentare delle iterazioni.
• Complessità Campionaria: La complessità campionaria derivata per gli insiemi KL e $\chi^2$ eguaglia asintoticamente i migliori limiti noti per gli approcci model-based (ad es., Roch et al., 2025; Chen et al., 2025). Il termine $o(1)$ nell'esponente rappresenta una penalità sub-polinomiale che svanisce quando $\epsilon \to 0$, distinguendosi dalla complessità $\epsilon^{-3}$ dei metodi che utilizzano MLMC standard.
• Validazione Sperimentale: Esperimenti numerici sul problema di Garnet e su vari insiemi di incertezza (contaminazione, $\ell_\infty$, $\ell_2$) dimostrano che RHI converge alla ricompensa media robusta ottimale e che l'estimatore MLMC di ordine K riduce efficacemente il bias rispetto ai metodi standard.

5. Significato e Rivendicazioni

Il paper sostiene di stabilire RHI come l'algoritmo state-of-the-art model-free per il robust average-reward RL. La sua importanza risiede nel:

• Colmare il Divario: Colma il divario tra le garanzie asintotiche e l'analisi della complessità campionaria finita nel robust average-reward RL.
• Praticità: Essendo model-free e non richiedendo la conoscenza preventiva di $H$, l'algoritmo è più pratico per l'implementazione nel mondo reale dove tali parametri sono ignoti.
• Ottimalità: La complessità campionaria eguaglia asintoticamente i limiti più stretti noti per i metodi model-based, dimostrando che gli approcci model-free possono raggiungere un'efficienza simile senza l'overhead della costruzione del modello.
• Riduzione del Bias: Il design MLK di ordine K offre un miglioramento fondamentale rispetto ai precedenti stimatori di robust RL, risolvendo il problema dell'elevata complessità campionaria causata dal bias non mitigato nella stima di funzioni non lineari.

Gli autori osservano che la loro analisi assume un modello generativo (accesso a un simulatore) per isolare la complessità statistica. Le estensioni ai contesti online (esplorazione-sfruttamento) o offline (guidati da dataset) sono identificate come lavori futuri. Inoltre, il gap sub-polinomiale nella complessità campionaria per gli insiemi KL/$\chi^2$ è attribuito al trade-off intrinseco tra bias e varianza nella stima di funzionali non lineari, che rimane una sfida aperta per eliminarlo completamente nei contesti model-free.