Riepilogo Tecnico: Esplorazione Adattiva per Bandit a Stato Latente

1. Formulazione del Probleamento

Il documento affronta un problema di multi-armed bandit non stazionario in cui le distribuzioni dei premi dipendono da uno stato Markoviano latente (non osservato) che evolve autonomamente nel tempo. A differenza dei classici bandit contestuali, l'apprendista non può osservare direttamente lo stato $s_t$; osserva solo l'azione selezionata $a_t$ e il conseguente premio stocastico $r_t$.

La sfida principale è che il braccio ottimale cambia al variare della transizione dello stato nascosto, ma l'algoritmo deve inferire lo stato corrente esclusivamente dalla cronologia di azioni e premi. Questo scenario introduce tre specifiche difficoltà tecniche:

1. Stima Confondente dei Premi: Gli algoritmi standard mediano i premi sulla distribuzione degli stati, portando a un bias sistematico quando il braccio ottimale varia tra gli stati.
2. Attribuzione Temporale del Premio: È difficile distinguere se un cambiamento nelle prestazioni del premio sia dovuto al progresso dell'apprendimento o a una transizione nello stato nascosto.
3. Informazioni sullo Stato Limitate: L'algoritmo non può condizionarsi direttamente sulle caratteristiche dello stato e deve fare affidamento su segnali indiretti, un compito che diventa più difficile all'aumentare dello spazio degli stati.

L'obiettivo è minimizzare il regret dinamico rispetto a un oracolo consapevole dello stato, definito come la differenza cumulativa tra il premio del braccio ottimale per l'attuale stato nascosto e il braccio effettivamente selezionato.

2. Metodologia

Gli autori propongono una famiglia di algoritmi che integrano il Contesto Ritardato (Lagged Context) e le Strategie di Probing nel framework LinUCB. L'approccio evita la stima esplicita del modello di transizione Markoviana latente, affidandosi invece a statistiche a bassa dimensionalità per separare gli stati.

2.1 Contesto Ritardato (LC-UCB)

La prima componente, Lagged-Context UCB (LC-UCB), tratta la coppia azione-premio precedente $(a_{t-1}, r_{t-1})$ come un vettore di caratteristiche contestuali $\phi_t$.

• Intuizione: Sotto dinamiche di stato Markoviane lente, il premio precedente fornisce informazioni sullo stato precedente $s_{t-1}$, che è fortemente correlato con lo stato attuale $s_t$.
• Meccanismo: L'algoritmo apprende una mappatura da $(a_{t-1}, r_{t-1})$ al premio corrente $r_t$. Ciò consente all'apprendista di tracciare implicitamente lo stato e selezionare il braccio ottimale per lo stato recente inferito, piuttosto che per la media su tutti gli stati.
• Limitazione: LC-UCB può fallire se più stati producono premi simili per la stessa azione (non-identificabilità), portando ad ambiguità nell'inferenza dello stato.

2.2 Probing per Impronte Digitali dello Stato (State Fingerprints)

Per risolvere l'ambiguità, gli autori introducono strategie di probing che generano "impronte digitali dello stato" — osservazioni congiunte di premi da più bracci che identificano univocamente lo stato nascosto. Sono proposte due paradigmi:

1. Randomized Probing UCB (RP-UCB): Applicabile quando possono essere assegnati diversi bracci simultaneamente a più unità sperimentali (es. utenti). Raccoglie vere osservazioni congiunte $(r_0, r_1)$ dallo stesso istante temporale.
2. Sequential Probing UCB (SP-UCB): Applicabile per contesti a singola unità. Campiona i bracci consecutivamente (es. braccio 0 al tempo $t$, braccio 1 al tempo $t+1$) e tratta la coppia $(r_t, r_{t+1})$ come un'impronta digitale sintetica. Ciò si basa sull'assunto che lo stato sia "appiccicoso" (alta probabilità di auto-transizione), in modo che lo stato non cambi tra i due probe.

2.3 Esplorazione Adattiva (AdaRP-UCB / AdaSP-UCB)

Il probing a programmazione fissa incurre in regret anche quando il modello è fiducioso. Gli autori propongono varianti di Probing Adattivo che aggiornano le impronte digitali solo quando necessario, utilizzando tre meccanismi di gating:

• Gate dei Residui (Residual Gate): Attiva un probe se l'errore di previsione (residuo studentizzato) supera una soglia, indicando un drift del modello o una transizione di stato.
• Gate dell'Incertezza (Uncertainty Gate): Attiva un probe se il margine tra i due punteggi UCB più alti è ridotto, indicando un'alta incertezza nella selezione del braccio.
• Gate di Vecchiaia/Pericolo (Staleness/Hazard Gate): Attiva un probe se l'impronta digitale non viene aggiornata per una durata definita da una funzione di rischio esponenziale, evitando l'uso di informazioni obsolete.

Questi gate sono soggetti a un intervallo minimo tra i probe ($\tau_{min}$) per prevenire comportamenti oscillatori.

3. Contributi Chiave

1. Framework Algoritmico: Lo sviluppo di LC-UCB, RP-UCB, SP-UCB e delle loro varianti adattive (AdaRP-UCB, AdaSP-UCB) che combinano il contesto ritardato con il probing coordinato per gestire i bandit a stato latente senza la stima esplicita del modello di transizione.
2. Analisi Teorica: Una decomposizione del regret dinamico in tre componenti: ambiguità di rappresentazione (errore di approssimazione), costo del probe e drift dopo che un'impronta digitale diventa obsoleta. Il documento fornisce limiti che dimostrano come il probing adattivo minimizzi il regret bilanciando questi fattori.
3. Validazione Empirica: Valutazione sistematica attraverso variabili numero di stati nascosti ($S$), tassi di transizione (probabilità di permanenza $p_{stay}$), rumore del premio ($\sigma$) e orizzonti temporali ($T$).

4. Risultati Sperimentali

Gli algoritmi sono stati valutati contro baselines classiche (UCB1, Thompson Sampling), metodi avversari (EXP3) e metodi non stazionari (Sliding Window UCB, Discounted UCB).

• Performance: I metodi di probing adattivo (specificamente AdaRP-UCB e AdaSP-UCB) hanno superato costantemente tutte le baseline in ambienti dove i riepiloghi (impronte digitali) potevano distinguere gli stati e venivano aggiornati con sufficiente frequenza.
  • AdaRP-UCB ha ottenuto il regret più basso in 12 configurazioni su 13, mostrando guadagni significativi in ambienti volatili.
  • AdaSP-UCB ha performato meglio in contesti a singola unità con basso rumore, mixing lento o grandi spazi di stato.
• Modalità di Fallimento: Il documento identifica condizioni specifiche in cui i metodi degradano:
  • Rumore Elevato: Quando il rumore ($\sigma$) è elevato rispetto al gap tra i bracci, le impronte digitali diventano deboli e le baseline non stazionarie (come D-UCB) possono performare meglio.
  • Debole Separazione delle Impronte: Se diversi stati producono distribuzioni di premio congiunte simili, la strategia di probing non può disambiguarli.
  • Switching Rapido: Il probing sequenziale (SP-UCB) fallisce quando lo stato cambia frequentemente all'interno della finestra di probe (basso $p_{stay}$), rendendo l'impronta digitale sintetica non valida.
• Studi di Ablazione: Rimuovere la caratteristica dell'impronta digitale ($\phi_{fp}$) ha aumentato significativamente il regret in ambienti con stati "sticky", confermando il valore delle osservazioni congiunte. Rimuovere il contesto ritardato ($\phi_{lag}$) ha avuto un impatto minore in alcune configurazioni randomizzate, suggerendo che il timing adattivo fosse il driver principale in quel caso.

5. Significato e Rivendicazioni

Il documento sostiene che il suo contributo primario sia un approccio pratico alla non-stazionarietà strutturata dove l'ambiente evolve tramite un processo Markoviano autonomo. A differenza dei classici bandit non stazionari che trattano i cambiamenti come drift arbitrari, o dei POMDP che richiedono l'osservabilità completa o decodifiche complesse, questo approccio utilizza riepiloghi della cronologia leggeri e probe per mantenere una stima attuale del braccio ottimale.

Gli autori sottolineano che i loro metodi sono più efficaci nei regimi in cui:

1. Lo stato latente è prevedibile su orizzonti brevi (mixing lento).
2. La strategia di probing può generare statistiche sufficienti (impronte digitali) che separano gli stati rilevanti.
3. I meccanismi di gating adattivi possono mantenere aggiornati questi riepiloghi senza incorrere in un eccessivo regret di probing.

Il lavoro colma il divario tra bandit contestuali e apprendimento per rinforzo a stato latente, offrendo una soluzione computazionalmente efficiente (basata su LinUCB) che non richiede l'apprendimento dell'intera dinamica di transizione dello stato nascosto.