Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

Enunciato del Problema

Il documento affronta l'efficienza statistica dell'apprendimento offline nei Contextual Bandits (CB) quando l'obiettivo di apprendimento coinvolge la regolarizzazione Forward-Kullback-Leibler (Forward-KL). La funzione obiettivo è definita come:
$$J_{FKL}(\pi) := \mathbb{E}[r] - \eta^{-1} \text{KL}(\pi_{\text{ref}} \| \pi)$$
dove $r$ è la ricompensa, $\eta$ è l'inverso dell'intensità di regolarizzazione e $\pi_{\text{ref}}$ è una politica di riferimento (comportamentale).

Mentre la regolarizzazione reverse-KL ($\text{KL}(\pi \| \pi_{\text{ref}})$) è stata studiata estesamente e ha dimostrato di ammettere una complessità campionaria di $\tilde{O}(\epsilon^{-1})$ (tassi rapidi) sotto concentrabilità a singola politica (dove la politica comportamentale copre solo la politica ottimale), il caso Forward-KL rimane un problema aperto. Le analisi esistenti per Forward-KL o non sono applicabili o risultano in tassi lenti di $\tilde{O}(\epsilon^{-2})$. Inoltre, non è chiaro se la concentrabilità a singola politica sia sufficiente per Forward-KL, dato che Forward-KL è "mass-covering" (penalizza $\pi \to 0$ dove $\pi_{\text{ref}} > 0$) piuttosto che "mode-seeking", richiedendo potenzialmente assunzioni di copertura più forti.

Il documento cerca di rispondere a due domande fondamentali:

1. Qual è il tasso statistico del processo decisionale per obiettivi regolarizzati con Forward-KL?
2. La concentrabilità a singola politica è sufficiente per un apprendimento offline ottimale in termini di tasso in questo contesto?

Metodologia

Gli autori propongono un'analisi razionalizzata per i Contextual Bandits Pessimistici Regolarizzati con Forward-KL (FKL-PCB). La metodologia si discosta significativamente dai lavori precedenti che si basano su espansioni di Taylor e sul Teorema del Valore Medio (MVT).

1. Rifiuto dell'Analisi Tradizionale Basata su MVT:
I lavori precedenti che analizzano obiettivi regolarizzati utilizzano spesso un'espansione di Taylor attorno a un punto intermedio $\bar{u}$ (tramite il Teorema del Valore Medio) per decomporre il gap di subottimalità. Per reverse-KL, i termini risultanti esibiscono una proprietà di monotonia sotto pessimismo che permette di limitare l'errore utilizzando la concentrabilità a singola politica.
Tuttavia, gli autori dimostrano (tramite il Lemma 5.3) che per Forward-KL, la derivata del termine di decomposizione della subottimalità coinvolge una "skewness inclinata" di una variabile casuale centrata. Il segno di questa derivata è indefinito, il che significa che l'argomento di monotonia fallisce. Di conseguenza, le routine standard basate su MVT non possono raggiungere tassi rapidi senza ricorrere ad assunzioni di concentrabilità più forti (su tutte le politiche).

2. Pipeline Analitica Convessa:
Per superare i limiti di MVT, gli autori introducono una nuova tecnica di dimostrazione basata su coniugati convessi e divergenze di Bregman:

• Prospettiva Duale: Caratterizzano l'obiettivo regolarizzato tramite il suo coniugato convesso sul semplicex di probabilità.
• Argomento di Auto-Limitazione: Derivano un'identità per il gap di subottimalità (Lemma 5.5) che esprime l'errore direttamente in termini della differenza al quadrato tra la ricompensa reale e la stima pessimistica, pesata dal rapporto tra la politica ottimale e la politica di riferimento.
• Identità Chiave: Il contributo tecnico centrale è la disuguaglianza:
  $$\text{SubOpt}_{FKL}(\hat{\pi}) \leq 2\eta \sum_{a} \frac{(\pi^*_{FKL}(a))^2}{\pi_{\text{ref}}(a)} (r(a) - \hat{r}(a))^2$$
  Questo limite dipende solo dal coefficiente di concentrabilità a singola politica $C_{\pi^*} = \sup \frac{\pi^*}{\pi_{\text{ref}}}$, evitando la necessità di concentrabilità su tutte le politiche.

3. Progettazione dell'Algoritmo:
Il documento presenta FKL-PCB, un algoritmo pessimistico per entrambi i contesti tabellare e di approssimazione funzionale:

• Stima: Utilizza i minimi quadrati per stimare la funzione di ricompensa.
• Pessimismo: Sottrae un termine di penalità (limite di confidenza) per garantire che la ricompensa stimata $\hat{r}$ sia limitata inferiormente dalla ricompensa reale $r$ con alta probabilità.
• Ottimizzazione: Restituisce la politica che massimizza l'obiettivo regolarizzato pessimistico.

Contributi e Risultati Chiave

1. Limiti Superiori di Complessità Campionaria Rapida:
Il documento stabilisce i primi limiti di complessità campionaria $\tilde{O}(\epsilon^{-1})$ per CB offline regolarizzati con Forward-KL sotto concentrabilità a singola politica:

• Contesto Tabellare: $\tilde{O}\left( \eta (C_{\pi^*})^2 |S||A| \epsilon^{-1} \right)$.
• Approssimazione Funzionale: $\tilde{O}\left( \eta C_{\pi^*} D^2_{\pi^*} \log N_G \epsilon^{-1} \right)$, dove $D^2_{\pi^*}$ è un coefficiente di concentrabilità di tipo $D^2$ e $N_G$ è il numero di copertura della classe di funzioni.
• Questi risultati migliorano il precedente limite stato dell'arte di $\tilde{O}(\epsilon^{-2})$ di Aminian et al. (2025) e rilassano il requisito da concentrabilità su tutte le politiche a concentrabilità a singola politica.

2. Limiti Inferiori Minimax:
Gli autori forniscono limiti inferiori corrispondenti per dimostrare la strettezza dei loro limiti superiori:

• Limite Inferiore Tabellare: $\Omega(\eta |S||A| \epsilon^{-1})$ nel regime di alta regolarizzazione. Questo conferma che la dipendenza lineare da $\eta$ e il tasso $1/\epsilon$ sono ottimali.
• Transizione di Fase: I limiti inferiori rivelano una "transizione di fase" simile a reverse-KL. Nel regime di bassa regolarizzazione (grande $\eta$), la complessità campionaria ritorna al tasso lento di $\tilde{O}(\epsilon^{-2})$, indicando che la regolarizzazione è necessaria per raggiungere tassi rapidi.

3. Novità Tecnica:
Il documento afferma che la "pipeline analitica convessa" unifica i contesti tabellare e di approssimazione funzionale e aggira completamente le routine di dimostrazione basate sul Teorema del Valore Medio. Questo approccio è presentato come di interesse indipendente per l'analisi di altri problemi decisionali regolarizzati da divergenze.

Significato e Affermazioni

Il documento si posiziona come il primo lavoro a caratterizzare esattamente i tassi statistici per la regolarizzazione Forward-KL nell'apprendimento offline. La sua importanza principale risiede in:

• Risoluzione di un Problema Aperto: Risolve la questione se la concentrabilità a singola politica sia sufficiente per Forward-KL, rispondendo affermativamente con tassi rapidi.
• Teoria Unificata: Dimostra che la natura "mass-covering" di Forward-KL non richiede intrinsecamente assunzioni di copertura più forti rispetto al reverse-KL "mode-seeking", a condizione di utilizzare un approccio analitico innovativo.
• Semplicità Algoritmica: Mostra che un algoritmo minimalista basato sul pessimismo (FKL-PCB) è sufficiente per raggiungere questi tassi ottimali, senza bisogno di complesse modifiche algoritmiche.

Gli autori mantengono un atteggiamento modesto riguardo alle direzioni future, notando che, sebbene abbiano stabilito la sufficienza, la necessità della concentrabilità a singola politica per Forward-KL (anche nei bandit a più bracci) rimane una domanda aperta. Inoltre, la derivazione di un limite inferiore che corrisponda al limite superiore specificamente per la concentrabilità di tipo $D^2$ nell'approssimazione funzionale è lasciata a lavori futuri.