Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

Sintesi Tecnica: Esplorazione Pura Oltre il Feedback di Ricompensa: Il Ruolo del Contesto Post-Azione

Formulazione del Problema
Questo articolo introduce una nuova variante del problema di Identificazione del Braccio Migliore (BAI) nell'impostazione a confidenza fissa dei banditi stocastici a più bracci (MAB). In questa impostazione, denominata "BAI con contesto post-azione", l'apprendente seleziona un'azione (braccio) $X$ e osserva non solo la ricompensa $Y$ ma anche un contesto intermedio post-azione $Z$. Il contesto $Z$ è generato come conseguenza dell'azione scelta, distinguendo questo problema dai banditi contestuali standard in cui il contesto precede l'azione.

Gli autori analizzano due regimi strutturali definiti dalla relazione causale tra azione, contesto e ricompensa:

1. Contesto Separatore: La ricompensa $Y$ dipende esclusivamente dal contesto $Z$, rendendo $X$ e $Y$ condizionalmente indipendenti dato $Z$ ($P(Y|X, Z) = P(Y|Z)$). In questo caso, la distribuzione della ricompensa è determinata interamente dal contesto osservato.
2. Contesto Non Separatore: La ricompensa $Y$ dipende sia dall'azione $X$ sia dal contesto $Z$ ($P(Y|X, Z) \neq P(Y|Z)$). Qui, il contesto fornisce informazioni aggiuntive ma non è una statistica sufficiente per la ricompensa.

L'obiettivo è identificare il braccio con la ricompensa attesa più alta con una probabilità di errore al massimo $\delta$, minimizzando al contempo la complessità campionaria (il numero di round richiesti).

Metodologia e Algoritmi
L'articolo deriva limiti inferiori dipendenti dall'istanza sulla complessità campionaria per entrambi i contesti e propone algoritmi che asintoticamente raggiungono tali limiti.

• Impostazione Separatore:

  • Limite Inferiore: Gli autori derivano un limite inferiore che dipende dalle frequenze dei contesti osservati piuttosto che dalle frequenze dei bracci estratti. Questo perché, nell'impostazione separatore, qualsiasi osservazione di un contesto specifico $Z=j$ fornisce informazioni sulla ricompensa media di quel contesto, indipendentemente dal braccio che l'ha generato.
  • Algoritmo (STS): L'algoritmo proposto "Separator Track and Stop" (STS) utilizza una nuova regola di campionamento chiamata G-tracking. A differenza dei metodi tradizionali che tracciano le frequenze ottimali di estrazione dei bracci, il G-tracking traccia le frequenze ottimali di osservazione dei contesti. Tratta il problema come un compito di apprendimento off-policy attivo in cui l'apprendente seleziona una distribuzione sui bracci per raggiungere una distribuzione target sui contesti. L'algoritmo risolve un problema di ottimizzazione convessa per trovare le frequenze ottimali dei contesti e utilizza una proiezione geometrica per selezionare la successiva distribuzione sui bracci, garantendo che le frequenze dei contesti osservati convergano verso l'obiettivo ottimale.

• Impostazione Non Separatore:

  • Limite Inferiore: Il limite inferiore derivato tiene conto della distribuzione congiunta di azioni e contesti.
  • Algoritmo (NSTS): L'algoritmo "Non-Separator Track and Stop" (NSTS) estende il classico framework Track-and-Stop. Impiega il D-tracking per stimare e tracciare le proporzioni ottimali di estrazione di bracci specifici, utilizzando le informazioni congiunte delle azioni e dei loro contesti risultanti per affinare le stime delle medie delle ricompense.

Contributi Chiave

1. Definizione del Problema: Formalizzazione della BAI con contesto post-azione, distinguendo tra regimi strutturali separatore e non separatore.
2. Limiti Teorici: Derivazione di limiti inferiori dipendenti dall'istanza sulla complessità campionaria per entrambi i regimi. Il limite separatore è dimostrato essere strettamente più stringente rispetto ai limiti derivati ignorando il contesto.
3. Progettazione degli Algoritmi:
   • Introduzione del G-tracking, una regola di campionamento che ottimizza direttamente le frequenze di osservazione dei contesti nell'impostazione separatore, sfruttando la geometria dello spazio dei contesti.
   • Estensione del framework Track-and-Stop all'impostazione non separatore (NSTS).
4. Analisi della Sub-ottimalità: Dimostrazione teorica ed empirica che gli algoritmi che ignorano il contesto post-azione (come il Track-and-Stop standard) sono strettamente sub-ottimali. Nell'impostazione separatore, ignorare il contesto può portare ad aumenti arbitrariamente grandi della complessità campionaria, anche quando i gap di ricompensa sono piccoli, poiché non riesce a sfruttare la struttura di indipendenza condizionale.
5. Analisi della Riduzione: L'articolo analizza la riduzione del problema separatore ai banditi lineari, mostrando che tali riduzioni aumentano il limite inferiore della complessità campionaria rispetto all'approccio diretto proposto.

Risultati

• Teorici: È stato dimostrato che gli algoritmi proposti (STS e NSTS) sono $\delta-corretti$ e raggiungono l'ottimalità asintotica, corrispondendo ai limiti inferiori derivati quando $\delta \to 0$.
• Empirici: Esperimenti su dati sintetici e dati reali (log di raccomandazione KuaiSAR) dimostrano significativi guadagni nelle prestazioni.
  • Nell'impostazione separatore, STS supera drasticamente le linee di base (Track-and-Stop e Lazy Track-and-Stop), che spesso non riescono a fermarsi entro orizzonti temporali ragionevoli.
  • Nell'impostazione non separatore, NSTS riduce significativamente il numero di campioni richiesti rispetto a Track-and-Stop, che ignora le informazioni contestuali.
  • I grafici di tracciamento confermano che STS converge verso le frequenze ottimali dei contesti, mentre le linee di base non riescono ad allinearsi con la strategia ottimale.

Significato e Affermazioni
L'articolo afferma che sfruttare il contesto post-azione altera fondamentalmente la strategia ottimale per l'esplorazione pura. Gli autori sottolineano che in scenari in cui sono disponibili osservazioni intermedie (mediatori), ignorarle porta a una sostanziale inefficienza. Nello specifico, nell'impostazione separatore, la capacità di raggruppare le informazioni tra bracci diversi che generano lo stesso contesto consente un'identificazione molto più rapida del braccio migliore. Il lavoro evidenzia che gli algoritmi BAI standard non sono meramente sub-ottimali, ma possono essere arbitrariamente inefficienti in questi ambienti strutturati. L'articolo conclude che il lavoro futuro potrebbe affrontare il caso in cui la matrice di probabilità del contesto è sconosciuta, notando che ciò introduce sfide di non convessità che rendono difficile la progettazione di algoritmi efficienti.