Offline-to-Online Learning in Linear Bandits

Sintesi Tecnica: Apprendimento Offline-to-Online nei Bandit Lineari

Definizione del Problema
Questo articolo affronta il problema dell'apprendimento offline-to-online nel contesto dei bandit lineari stocastici. Lo scenario coinvolge un apprendista che seleziona sequenzialmente azioni da un insieme $\mathcal{A} \subset \mathbb{R}^d$ per massimizzare i premi cumulativi su un orizzonte $n$, avendo accesso a un dataset offline preesistente $\mathcal{D}$. I dati offline sono raccolti tramite un design non adattivo e fisso (conteggi di azioni deterministici) e seguono un modello di premio lineare con rumore subgaussiano.

La sfida centrale risiede nel compromesso tra due obiettivi concorrenti:

1. Regret Online ($R_n$): Minimizzare il regret rispetto all'azione ottimale $\mu^*$. Gli algoritmi online standard (ad es. LinUCB) si affidano all'ottimismo per esplorare, ottenendo un regret sublineare ma potenzialmente soffrendo di un alto regret iniziale se i dati offline vengono ignorati.
2. Regret Offline ($R_n^{off}$): Minimizzare il regret rispetto alla media del premio del dataset offline ($\mu_{off}$). Gli algoritmi offline standard (ad es. LinLCB) si affidano al pessimismo per sfruttare i dati noti, garantendo prestazioni vicine a $\mu_{off}$, ma falliscono nell'esplorare, il che porta a un regret lineare se il dataset offline è subottimale o se l'orizzonte è lungo.

I lavori esistenti hanno trattato questi regimi separatamente o si sono concentrati sui multi-armed bandits (MAB), dove il regret scala con il numero di azioni. Questo articolo mira a colmare il divario negli ambienti strutturati (lineari), dove il regret dovrebbe scalare con la dimensione $d$ piuttosto che con la dimensione dello spazio delle azioni.

Metodologia: L'Algoritmo LinOtO
Gli autori propongono LinOtO (Linear Offline-to-Online), un algoritmo che bilancia dinamicamente esplorazione e sfruttamento gestendo un budget di esplorazione. L'algoritmo opera passando tra due strategie basate su un insieme di confidenza $C_t$ costruito sia dai dati offline che da quelli online:

1. Insiemi di Confidenza: L'algoritmo mantiene uno stimatore dei minimi quadrati $\hat{\theta}_t$ e un ellissoide di confidenza $C_t$ attorno al vero parametro $\theta^*$. Il raggio di questo insieme incorpora l'incertezza derivante sia dai dati offline ($\beta_{off}$) che dalle interazioni online ($\beta_t$).
2. Azioni Ottimistiche vs. Pessimistiche:
   • Azione UCB ($U_t$): L'azione che massimizza l'Upper Confidence Bound all'interno di $C_t$. Questa promuove l'esplorazione e riduce $R_n$, ma rischia di aumentare $R_n^{off}$.
   • Azione LCB ($L_t$): L'azione che massimizza il Lower Confidence Bound (specificamente, il massimo dei minimi limiti di confidenza nel tempo). Questa promuove lo sfruttamento dei dati offline, riducendo $R_n^{off}$, ma potenzialmente aumentando $R_n$.
3. Meccanismo di Budget:
   • L'algoritmo definisce un premio base sicuro $r_b$, derivato da un limite inferiore sul premio di una specifica azione "sicura" $L_{off}$ (l'azione LCB calcolata esclusivamente dai dati offline). La Proposizione 2 garantisce che $L_{off}$ sia vicino a $\mu_{off}$ con alta probabilità.
   • Viene mantenuto un budget di esplorazione $B(t)$, che rappresenta l'eccedenza cumulativa di premio dell'algoritmo rispetto al premio base $r_b$.
   • Regola Decisionale: Se $B(t) > 0$, l'algoritmo seleziona l'azione ottimistica $U_t$ (esplorazione). Se $B(t) \le 0$, seleziona l'azione pessimistica $L_t$ (sfruttamento) per accumulare budget.
   • Questo meccanismo assicura che l'algoritmo esplori solo quando ha "guadagnato" il diritto di farlo rimanendo sicuro rispetto al baseline offline.

Contributi Chiave

1. Design dell'Algoritmo: Il documento presenta LinOtO, il primo algoritmo progettato specificamente per l'apprendimento lineare offline-to-online che bilancia simultaneamente le strategie UCB e LCB tramite un meccanismo di commutazione basato sul budget.
2. Garanzie Teoriche: Gli autori stabiliscono limiti di regret ad alta probabilità per entrambi i parametri:
   • Regret Online ($R_n$): Il Teorema 1 mostra che LinOtO ottiene un regret sublineare rispetto all'azione ottimale. Il limite consiste in un termine dipendente dall'orizzonte $n$ (simile a LinUCB) e in una costante additiva dipendente dalla qualità dei dati offline. Se i dati offline coprono bene lo spazio, il limite migliora.
   • Regret Offline ($R_n^{off}$): Il Teorema 2 dimostra che il regret rispetto al riferimento offline scala linearmente con $n$, ma diminuisce come $O(1/\sqrt{m})$ con il numero di campioni offline $m$. Ciò corrisponde alle prestazioni di una soluzione puramente offline (pessimistica).
3. Analisi del Tradeoff di Pareto: L'analisi rivela un tradeoff regolabile controllato da un parametro $\alpha$. Aumentare $\alpha$ favorisce le prestazioni online (più vicino a LinUCB), mentre diminuire $\alpha$ favorisce le prestazioni offline (più vicino a LinLCB).

Risultati Sperimentali
Le valutazioni empiriche su compiti sintetici di bandit lineari (dimensione $d=20$, $|A|=100$) dimostrano che:

• Sensibilità all'Orizzonte: Per orizzonti brevi, LinOtO segue la linea di base conservativa di LinLCB. Per orizzonti lunghi, transita verso l'esplorazione, ottenendo un regret sublineare comparabile a LinUCB.
• Qualità dei Dati Offline:
  • Quando il dataset offline esclude l'azione ottimale, LinOtO riesce a deviare dal prior offline subottimale per esplorare, superando infine LinLCB (che soffre di un regret lineare) e avvicinandosi alle prestazioni di LinUCB all'aumentare della dimensione dei dati offline $m$.
  • Quando il dataset offline include l'azione ottimale, LinOtO converge rapidamente, offrendo prestazioni comparabili a LinUCB e LinLCB.
• Robustezza: L'algoritmo si colloca costantemente tra gli estremi della pura esplorazione (LinUCB) e del puro sfruttamento (LinLCB), adattandosi ai parametri del problema.

Significato e Rivendicazioni
Il documento sostiene che LinOtO risolve efficacemente il tradeoff offline-to-online "poco compreso" negli ambienti strutturati. A differenza dei lavori precedenti in ambito MAB (ad es. Sentenac et al., 2025), questo approccio sfrutta la struttura lineare per garantire che il regret scali con la dimensione $d$ piuttosto che con il numero di azioni, rendendolo scalabile per problemi ad alta dimensionalità.

Gli autori osservano con modestia che il loro framework attualmente assume dati offline a design fisso e non tiene conto di cambiamenti nella distribuzione tra i dati offline e quelli online o di policy di logging adattive. Identificano l'affrontare queste limitazioni, insieme all'estensione del framework a contesti non lineari, come importanti direzioni per la ricerca futura. Il lavoro contribuisce alla letteratura più ampia sull'uso di conoscenze pregresse (indizi, dati offline) per guidare i tradeoff tra esplorazione e sfruttamento nell'apprendimento online.