Sintesi Tecnica: Sulla Complessità dell'Apprendimento per Rinforzo Offline con Approssimazione di $Q^\star$ e Copertura Parziale

Definizione del Problema

Questo lavoro investiga i limiti teorici dell'Apprendimento per Rinforzo (RL) Offline nel setting di $Q^\star$-realizzabilità e copertura parziale. In questo paradigma, un agente apprende una politica da un dataset pre-raccolto e fisso, senza ulteriore interazione con l'ambiente. Il dataset è generato da una politica di comportamento che potrebbe non coprire l'intero spazio stato-azione (copertura parziale).

La domanda aperta centrale affrontata è se la $Q^\star$-realizzabilità (la vera funzione Q ottimale appartiene a una classe di funzioni nota) combinata con la completezza di Bellman (l'operatore di Bellman mappa la classe di funzioni in un insieme sovraesteso) e la copertura parziale siano sufficienti per un apprendimento efficiente in termini di campionamento. Sebbene queste condizioni permettano la costruzione di un insieme di confidenza contenente la vera $Q^\star$, il paper mette in discussione se ciò sia sufficiente a garantire una selezione della politica robusta.

Metodologia

1. Limite Inferiore Informazionale

Gli autori stabiliscono innanzitutto che le suddette condizioni sono insufficienti per un apprendimento efficiente in termini di campionamento. Costruiscono una famiglia di Processi Decisionali di Markov (MDP) in cui:

• La $Q^\star$-realizzabilità e la completezza di Bellman sono soddisfatte.
• La copertura della politica ottimale è costante ($\Theta(1)$).
• Nonostante la vera funzione di valore sia ben localizzata all'interno della classe di funzioni, l'apprendista non è in grado di distinguere tra politiche che portano a errori catastrofici e quelle che sono sicure.
• La complessità di campionamento richiesta scala come $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$, dove $\Delta$ è il gap di valore. Ciò indica che anche con un piccolo gap, la complessità di campionamento può essere proibitiva, e la difficoltà deriva non solo dalla stima di $Q^\star$, ma dal prendere decisioni robuste all'interno dell'insieme di ambiguità.

2. Framework di Decomposizione Decisione-Stima

Per affrontare il gap identificato, gli autori introducono un framework generale di decisione-stima, ispirato al coefficiente di decisione-stima (DEC) nell'RL online. Essi decompongono la subottimalità dell'RL offline in due componenti modulari:

1. Complessità Decisionale: La difficoltà di selezionare una politica robusta da un insieme di confidenza di modelli plausibili.
2. Errore di Stima: L'errore incursito nella stima della funzione di valore o dei parametri del modello dai dati offline.

Definiscono il Coefficiente di Decisione-Stima Robusto Offline ($Ordec$):
$$Ordec\text{-}OD_\gamma(F_{conf}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{conf}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in F_{conf}} D_\pi(f \| M) \right]$$
Dove:

• $F_{conf}$ è l'insieme di confidenza delle funzioni $Q^\star$ plausibili.
• $\mathcal{M}_{conf}$ è l'insieme indotto dei modelli plausibili.
• $\rho$ è una distribuzione sulle politiche.
• $D_\pi(f \| M)$ è una misura di discrepanza (ad esempio, l'errore di Bellman) tra una funzione e un modello, valutata sotto la politica ottimale del modello candidato $\pi_M$ (a differenza del DEC online che utilizza la politica dell'apprendista).

Il framework propone un algoritmo (E2D.OR) che restituisce una politica mista $\hat{\pi}$ soddisfacente:
$$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq Ordec + \text{Errore di Stima}$$

Contributi Chiave

1. Risultato Negativo sulla Sufficienza

Il paper fornisce un limite inferiore informazionale provando che $Q^\star$-realizzabilità, copertura parziale e completezza di Bellman non sono sufficienti per l'apprendimento offline efficiente in termini di campionamento. Ciò evidenzia che la sfida principale nei setting di copertura parziale è il problema della "decisione" — distinguere tra politiche sicure e insicure all'interno dell'insieme di confidenza — piuttosto che il puro problema della "stima".

2. Framework Unificato e Limiti Migliorati

Il framework $Ordec$ proposto unifica e migliora i risultati esistenti:

• Setting del Value-Gap: Recupera i risultati di Chen e Jiang (2022) ma elimina la necessità di conoscere il valore del gap o di eseguire ulteriori interazioni online. Il limite si adatta automaticamente al vero gap.
• Setting Regolarizzato: Migliora il limite della complessità di campionamento per il Soft Q-learning sotto copertura parziale da $\epsilon^{-4}$ (Uehara et al., 2023) a $\epsilon^{-2}$. Ciò è ottenuto tramite una nuova lemma di differenza di performance del secondo ordine per gli MDP regolarizzati.
• Confine Decisionale Curvo: Introduce un nuovo setting apprendibile basato sulla curvatura del confine decisionale negli spazi di azione continui, affrontando le preoccupazioni pratiche relative alla rigida assunzione del value-gap.

3. Nuovi Regimi Apprendibili per l'Errore di Stima

Il paper caratterizza il ruolo delle assunzioni strutturali nel controllare il termine dell'errore di stima:

• Completezza di Bellman: Fornisce la prima analisi della complessità di campionamento per il Conservative Q-Learning (CQL) sotto approssimazione di funzione generale (precedentemente limitata ai casi tabulari).
• Basso Rango di Bellman: Investiga l'apprendibilità offline degli MDP a basso rango di Bellman (un canone dell'RL online). Gli autori mostrano che, sotto assunzioni standard sui dati, il basso rango di Bellman è insufficiente per l'apprendimento offline. Introducono due condizioni necessarie per l'apprendibilità in questo regime:
  1. Doppio Campionamento di Politica: I dati devono essere generati campionando una politica e poi due transizioni indipendenti.
  2. Copertura delle Caratteristiche della Politica: Una specifica condizione di copertura sullo spazio delle caratteristiche delle politiche.
     Rilassare anche solo una di queste condizioni rompe la garanzia di complessità di campionamento polinomiale.

Sintesi dei Risultati

• Limite Inferiore: Dimostrato che $Q^\star$-realizzabilità + completezza di Bellman $\nRightarrow$ apprendimento offline efficiente in termini di campionamento.
• Limite Superiore: Stabilito un limite generale di subottimalità decomposto in $Ordec$ (complessità decisionale) ed errore di stima.
• Limiti Specifici:
  • Non Regolarizzato (Value Gap): $\tilde{O}(\frac{H^2}{\gamma \Delta^2} + \gamma \frac{C_{\pi^\star}}{n})$. Si adatta a gap sconosciuti.
  • Regolarizzato: $\tilde{O}(\sqrt{\frac{C_{\pi^\star}}{n}})$, producendo una complessità di campionamento di $\epsilon^{-2}$.
  • CQL: Primo limite di approssimazione di funzione generale per CQL sotto copertura parziale.
  • Basso Rango di Bellman: Provata l'impossibilità sotto assunzioni standard; identificati il doppio campionamento di politica e la copertura delle caratteristiche della politica come necessari per l'apprendibilità.

Significato e Rivendicazioni

Il paper sostiene di fornire una comprensione più completa del potenziale e dei limiti dell'RL offline sotto l'approssimazione di $Q^\star$ e la copertura parziale. Il suo significato risiede in:

1. Chiarire la Fonte della Difficoltà: Sposta il focus teorico dagli errori di stima pura alla complessità decisionale intrinseca nei setting di copertura parziale, mostrando che anche con una stima perfetta, il decision-making robusto può essere impossibile senza assunzioni strutturali aggiuntive.
2. Unificazione: Offre un framework modulare che recupera, migliora ed estende i risultati precedenti (Chen e Jiang, 2022; Uehara et al., 2023) separando le complessità decisionali da quelle di stima.
3. Rilevanza Pratica: Analizzando il CQL sotto approssimazione di funzione generale e identificando i requisiti strutturali specifici per i problemi a basso rango di Bellman, il lavoro colma il divario tra algoritmi pratici e garanzie teoriche in contesti precedentemente considerati intrattabili o scarsamente compresi.
4. Novità nei Setting: Stabilisce le prime condizioni di apprendibilità per gli MDP a basso rango di Bellman nell'RL offline e fornisce il primo limite $\epsilon^{-2}$ per il Soft Q-learning regolarizzato sotto copertura parziale.

Gli autori osservano che, sebbene il framework sia teoricamente solido, risolvere esattamente l'algoritmo minimax è computazionalmente difficile, sebbene possa essere approssimato tramite metodi actor-critic. Il lavoro serve primariamente a identificare nuovi regimi apprendibili e a caratterizzare le condizioni strutturali richieste per essi.