Anytime-valid Optimal Policy Identification

Sintesi Tecnica: Identificazione di una Politica Ottimale Valida in Qualsiasi Momento

1. Definizione del Problema

Il documento affronta la sfida di identificare una politica ottimale ($\pi^\star$) da una classe finita di candidati $\Pi = \{\pi_1, \dots, \pi_m\}$ utilizzando dati di bandit contestuali registrati (logged). In molti scenari pratici, i dati sono generati da una politica di registrazione ($h_t$) esternamente determinata che l'analista non controlla. Questa politica di registrazione può essere una randomizzazione fissa o un algoritmo adattivo tarato su obiettivi diversi da quello specifico dell'analista (ad esempio, massimizzare il coinvolgimento dell'utente piuttosto che minimizzare la disinformazione).

La difficoltà principale risiede in due vincoli:

1. Scenario Off-Policy: L'analista deve inferire il valore delle politiche target $\nu(\pi)$ utilizzando dati raccolti sotto una politica differente $h_t$, senza la possibilità di indirizzare la raccolta dati verso l'obiettivo di identificazione.
2. Monitoraggio Sequenziale: I professionisti spesso desiderano monitorare l'evidenza in modo continuo, eliminare le politiche chiaramente subottimali man mano che i dati si accumulano ed interrompere la raccolta dati una volta identificata la politica ottimale, piuttosto che impegnarsi in un numero di campioni fisso ($N$) in anticipo.

La letteratura esistente sull'identificazione di politiche ottimali tipicamente assume che l'analista controlli la raccolta dati (campionamento adattivo) o fornisca garanzie inferenziali solo a una dimensione di campione pre-specificata e fissa. Questo articolo cerca di colmare il divario fornendo garanzie valide in qualsiasi momento (anytime-valid) per l'identificazione di politiche ottimali off-policy.

2. Metodologia

Il framework proposto costruisce un insieme di politiche candidate ottimali indicizzato nel tempo, $S_t$, che evolve con l'arrivo dei dati. La metodologia si basa su tre componenti principali:

A. Pseudo-Risultati Doppiamente Robusti (Doubly Robust Pseudo-Outcomes)
Per stimare i valori delle politiche $\nu(\pi)$ da dati registrati, il metodo utilizza pesi di importanza $w_t(\pi) = \pi(A_t|X_t) / h_t(A_t|X_t)$. Per migliorare l'efficienza e la stabilità, questi vengono combinati con un modello di ricompensa $b_{rt}(x,a)$ per costruire pseudo-risultati doppiamente robusti (DR). Nello specifico, vengono definiti pseudo-risultati inferiori e superiori ($\phi^{DRL}_t$ e $\phi^{DRU}_t$) tali che le loro aspettative condizionali siano uguali al vero valore della politica $\nu(\pi)$ e $1-\nu(\pi)$, rispettivamente. Fondamentalmente, la validità non dipende dal fatto che il modello di ricompensa sia specificato correttamente, ma solo dalle probabilità di registrazione note.

B. Sequenze di Confidenza (CS) Valide in Qualsiasi Momento
Basandosi sul lavoro di Waudby-Smith et al. (2024), il documento costruisce sequenze di confidenza per i valori delle politiche. Una sequenza di intervalli $[L_t(\pi), U_t(\pi)]$ è una $(1-\alpha)$-CS se il vero valore $\nu(\pi)$ rimane all'interno dell'intervallo per tutti i $t \geq 1$ con probabilità almeno $1-\alpha$. Questi intervalli sono costruiti utilizzando i pseudo-risultati DR e un processo di varianza $V_t(\pi)$ che tiene conto dell'accumulo di evidenza. La larghezza di questi intervalli si riduce con un tasso di $O(\sqrt{(\log \log t + \log m)/t})$.

C. Eliminazione Sequenziale e Regola di Arresto
Utilizzando un limite superiore (union bound) sulla classe di politiche $\Pi$, il metodo costruisce sequenze di confidenza simultanee per tutte le politiche. L'insieme dei candidati $S_t$ è definito come:
$$S_t := \left\{ \pi \in \Pi : U_t\left(\pi; \frac{\alpha}{m}\right) \geq \max_{\pi' \in \Pi} L_t\left(\pi'; \frac{\alpha}{m}\right) \right\}$$
Una politica viene eliminata da $S_t$ se il suo limite superiore di confidenza scende al di sotto del limite inferiore di confidenza massimo di qualsiasi politica concorrente. La procedura si arresta a un tempo dipendente dai dati $\tau$ quando $S_\tau$ diventa un singleton (contenente una sola politica).

3. Principali Contributi

L'articolo presenta due contributi teorici primari:

1. Garanzia di Copertura Valida in Qualsiasi Momento: Gli autori dimostrano che l'insieme $S_t$ costruito soddisfa una garanzia di copertura uniforme:
   $$P(\Pi^\star \subseteq S_t \text{ per ogni } t \geq 1) \geq 1 - \alpha$$
   dove $\Pi^\star$ è l'insieme delle vere politiche ottimali. Ciò assicura che, con alta probabilità, nessuna politica ottimale venga mai eliminata, indipendentemente da quando l'analista scelga di fermarsi.

2. Limiti di Complessità Campionaria: Quando la politica $\pi^\star$ è unica, il documento definisce un tempo di arresto $\tau$ per la sua identificazione. Sotto una condizione di regolarità di crescita lineare della varianza (Assunzione 1), la complessità campionaria è derivata come:
   $$\tau = O\left( \frac{\log m + \log \log(1/\Delta_{\min})}{\Delta_{\min}^2} \right)$$
   dove $\Delta_{\min}$ è il gap tra la migliore e la seconda migliore politica. Questo limite indica che il numero di campioni richiesti scala logaritmicamente con la dimensione della classe di politiche e inversamente con il quadrato del gap di subottimalità.

4. Risultati Empirici

Il documento valida il framework attraverso tre dimostrazioni empiriche:

• Illustrazione Sintetica: In un contesto simulato di bandit contestuali con sei politiche, il framework ha eliminato con successo le politiche chiaramente subottimali precocemente nel flusso di dati, mantenendo la politica ottimale fino a quando non è stata identificata univocamente. Le sequenze di confidenza per i valori delle politiche sono confluite verso i valori veri come previsto.
• Efficienza Campionaria: Confrontando la procedura valida in qualsiasi momento con un disegno a $N$ fisso (dove $N$ è calcolato in base a un gap target), gli autori hanno riscontrato risparmi sostanziali di campioni quando il vero gap di subottimalità era maggiore del gap target. Ad esempio, se il vero gap era il doppio del gap target, il metodo valido in qualsiasi momento ha risparmiato mediamente il 60–80% della dimensione campionaria pianificata.
• Applicazione al Mondo Reale: Il metodo è stato applicato a un grande esperimento adattivo (Offer-Westort et al., 2024) che ha coinvolto 15.292 utenti in Kenya e Nigeria, mirato a ridurre la condivisione di disinformazione. Il framework ha replicato la conclusione dello studio originale (identificando "accuracy nudge" e "Facebook tips" come i migliori performer) ma ha fornito una visione dinamica dell'accumulo di evidenza. Ha mostrato che le peggiori politiche potevano essere eliminate con solo una frazione dei dati finali, mentre i migliori candidati sono rimasti nell'insieme dei candidati per tutto il tempo.

5. Significato e Limitazioni

Significato:
Il documento fornisce un rigido framework inferenziale per il monitoraggio sequenziale in scenari off-policy. Permette agli analisti di prendere decisioni di arresto dipendenti dai dati senza invalidare le garanzie statistiche, affrontando un limite chiave degli approcci a $N$ fisso. Ciò è particolarmente prezioso in applicazioni reali in cui la raccolta dati è vincolata da politiche di registrazione esterne e le risorse sono limitate.

Limitazioni:
Gli autori evidenziano esplicitamente due limitazioni:

1. Invarianza Temporale: Il framework assume che i valori delle politiche siano costanti nel tempo. Non gestisce attualmente ambienti non stazionari in cui gli effetti del trattamento evolvono (ad esempio, a causa di novità o affaticamento).
2. Requisito di Sovrapposizione (Overlap): Il metodo richiede che ogni politica target sia assolutamente continua rispetto alla politica di registrazione (sovrapposizione stretta). Ciò esclude scenari in cui la politica di registrazione assegna deterministicamente probabilità zero ad azioni che una politica target prenderebbe, il che può accadere in algoritmi adattivi altamente concentrati (ad esempio, di tipo UCB).

Il documento conclude che, sebbene tali limitazioni esistano, il framework offre una soluzione robusta per una vasta classe di politiche di registrazione stocastiche comunemente presenti nella pratica.