Riepilogo Tecnico: Ottimizzazione Primal-Dual della Politica per CMDP Lineari con Perdite Avversariali

Contesto del Problema

Questo articolo affronta la sfida dell'Apprendimento per Rinforzo (RL) Sicuro in ambienti in cui i vincoli di sicurezza devono essere soddisfatti nonostante perturbazioni avversariali. Nello specifico, gli autori considerano Processi Decisionali di Markov (CMDP) Lineari a Orizzonte Finito con Perdite Avversariali.

Il contesto è definito dalla terna $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$, dove:

• Perdite Avversariali: Le funzioni di perdita $f^k = \{f^k_h\}$ sono scelte arbitrariamente da un avversario all'inizio di ogni episodio $k$ (feedback a informazione completa). Queste perdite non sono estratte da una distribuzione fissa.
• Costi Stocastici: Le funzioni di costo $g^k = \{g^k_h\}$ sono campionate in modo indipendente e identico (i.i.d.) da una distribuzione fissa $G$ (feedback a banda), rappresentando vincoli di sicurezza.
• Struttura Lineare: I kernel di transizione, le funzioni di perdita e le funzioni di costo possiedono una struttura lineare rispetto a una mappatura delle caratteristiche nota $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$.
• Obiettivo: L'agente cerca una politica che minimizzi la perdita attesa cumulativa garantendo che il costo cumulativo atteso non superi un budget $b$.

Le prestazioni sono misurate tramite Regret (differenza cumulativa di perdita rispetto alla politica ottimale) e Violazione dei Vincoli (eccesso cumulativo di costo rispetto al budget). L'obiettivo è ottenere limiti sublineari per entrambe le metriche.

Metodologia

Gli autori propongono un algoritmo di Ottimizzazione Primal-Dual della Politica (Algoritmo 1) progettato per gestire l'interazione tra perdite avversariali e vincoli stocastici in un contesto di approssimazione lineare delle funzioni. L'algoritmo integra quattro componenti principali:

1. Inizializzazione delle Epoche e Contrazione delle Caratteristiche:
   L'algoritmo opera in epoche. Un'epoca inizia quando il determinante della matrice di progettazione $\Lambda^k_h$ aumenta di un fattore moltiplicativo. All'inizializzazione, la politica viene reimpostata su una politica uniforme e la variabile duale viene reimpostata a zero. Crucialmente, l'algoritmo impiega la contrazione delle caratteristiche, riducendo la caratteristica originale $\phi$ mediante una funzione sigmoide per impedire che le stime della funzione Q si espandano in modo incontrollato. Questa tecnica, adattata da Cassel & Rosenberg (2024), semplifica la rappresentazione della politica per le argomentazioni sul numero di copertura.

2. Esecuzione della Politica e Stima:
   In ogni episodio, l'agente esegue azioni basate sulla politica corrente, osserva la perdita avversariale e il costo stocastico, e aggiorna la matrice di progettazione. Successivamente, stima i parametri per le funzioni di perdita e di costo e calcola le stime della funzione Q ($\hat{Q}$) e le stime della funzione valore ($\hat{V}$) utilizzando le caratteristiche contratte e i bonus ottimistici.

3. Miscelazione Periodica della Politica:
   Un'innovazione fondamentale è la miscelazione periodica della politica. Invece di miscelare la politica (perturbandola verso una politica uniforme) in ogni episodio, l'algoritmo applica la miscelazione solo una volta ogni $K^B$ episodi (dove $B=3/4$).

   • Motivazione: Una miscelazione frequente è necessaria per limitare la variabile duale (tramite analisi della deriva) ma aumenta la complessità della classe di politiche (numero di copertura). La miscelazione periodica bilancia questi requisiti in competizione.
   • Meccanismo: Ogni $K^{3/4}$ episodi, la politica corrente $\hat{\pi}^k$ viene miscelata con la politica uniforme $\pi_{unif}$ tramite una combinazione convessa: $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$.

4. Aggiornamento Duale Regolarizzato:
   La variabile duale $Y^k$ (associata al vincolo di costo) viene aggiornata utilizzando un passo di ascesa del gradiente regolarizzata:
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   I termini di regolarizzazione ($-4\alpha\eta H^3 Y^k$ e le costanti) sono progettati per attrarre la variabile duale verso zero, permettendo un'analisi della deriva di Lyapunov per limitare $Y^k$ senza fare affidamento sulle ipotesi di dualità forte che falliscono in contesti avversariali.

5. Politiche Softmax Weighted LogSumExp:
   La classe di politiche risultante è una softmax Weighted LogSumExp. A causa della miscelazione periodica, la politica non è una semplice esponenziale della somma delle funzioni Q, ma una somma pesata di esponenziali di somme parziali delle stime della funzione Q. Questa struttura permette alla politica di adattarsi alle perdite scelte avversarialmente mantenendo al contempo un numero di copertura trattabile.

Contributi Chiave

1. Primi Limiti Sublineari per CMDP Lineari Avversariali:
   L'articolo presenta il primo algoritmo che raggiunge limiti sublineari di regret e violazione dei vincoli nel contesto di CMDP lineari con perdite avversariali e costi stocastici. I limiti sono $\tilde{O}(K^{3/4})$, dove $K$ è il numero di episodi.

2. Nuova Argomentazione sul Numero di Copertura:
   Gli autori stabiliscono una nuova argomentazione sul numero di copertura per le politiche softmax Weighted LogSumExp. A differenza delle politiche softmax standard in cui i pesi sono uniformi, il processo di miscelazione introduce parametri di peso variabili $\zeta_i$. Gli autori dimostrano che il logaritmo del numero di copertura per questa classe cresce come $\tilde{O}(n^2 d^2)$, dove $n$ è il numero di passaggi di miscelazione e $d$ è la dimensione delle caratteristiche. Questo risultato non è banale poiché i parametri di peso dipendono sia dal parametro di miscelazione sia dalle stime della funzione Q.

3. Componenti Algoritmiche per il Controllo:
   L'articolo introduce due componenti novel per controllare congiuntamente il numero di copertura e la variabile duale:

   • Miscelazione Periodica della Politica: Regola la frequenza della miscelazione per impedire che il numero di copertura cresca troppo (cosa che accadrebbe con $O(K)$ passaggi di miscelazione) pur avvenendo frequentemente abbastanza da limitare la variabile duale.
   • Aggiornamento Duale Regolarizzato: Una nuova regola di aggiornamento che incorpora un termine di regolarizzazione per facilitare l'analisi basata sulla deriva, permettendo la limitazione della variabile duale in assenza di dualità forte.

Risultati

Garanzie Teoriche:
Sotto la condizione di Slater (Assunzione 1) e assumendo $H^2 \leq K$, con probabilità almeno $1-\delta$, l'algoritmo raggiunge:

• Regret: $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• Violazione dei Vincoli: $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

Entrambe le metriche scalano in modo sublineare con $K$ (specificamente $K^{3/4}$), indicando che il regret medio e la violazione media dei vincoli convergono a zero all'aumentare del numero di episodi.

Esperimenti Numerici:
L'algoritmo è stato valutato su un CMDP di scheduling del lavoro modificato con perdite avversariali. Su $100.000$ episodi:

• Regret: È cresciuto in modo sublineare, confermando il limite teorico.
• Violazione dei Vincoli: È cresciuta inizialmente rapidamente ma è convergita a zero dopo circa 45.000 episodi, validando la capacità dell'algoritmo di soddisfare i vincoli di sicurezza nel lungo termine.

Significato e Affermazioni

L'articolo afferma di essere il primo algoritmo provatamente efficiente per RL sicuro con approssimazione lineare delle funzioni in contesti avversariali. La sua importanza risiede nel colmare il divario tra:

1. CMDP Avversariali Tabellari: Lavori precedenti (es. Qiu et al., 2020) gestivano contesti avversariali ma erano limitati a spazi di stati piccoli e finiti.
2. CMDP Lineari Stocastici: Lavori precedenti (es. Ghosh et al., 2022) gestivano spazi di stati grandi ma assumevano ambienti stazionari (stocastici).

Introducendo la politica softmax Weighted LogSumExp e la strategia di miscelazione periodica, gli autori dimostrano che è possibile gestire spazi di stati grandi (tramite approssimazione lineare) e perdite avversariali simultaneamente. L'articolo nota modestamente che, sebbene sia stato raggiunto $\tilde{O}(K^{3/4})$, il limite ottimale $\tilde{O}(\sqrt{K})$ rimane una questione aperta per questo specifico contesto, in particolare riguardo al compromesso tra passaggi di miscelazione e numeri di copertura. Il lavoro evidenzia anche la difficoltà di estendere gli aggiornamenti duali basati sulla misura di occupazione a metodi basati sulla politica nei CMDP lineari avversariali, giustificando l'approccio proposto di ottimizzazione primal-dual della politica.