Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

Riepilogo Tecnico: Follow-the-Perturbed-Leader per Bandit Decouplati

Setting del Problema
Questo articolo affronta il problema dei bandit multi-braccio decouplati (MAB), un setting in cui l'agente seleziona due bracci distinti a ogni round $t$: un braccio $i_t$ per lo sfruttamento (subendo la perdita $\ell_{t, i_t}$ senza osservarla) e un braccio $j_t$ per l'esplorazione (osservando la perdita $\ell_{t, j_t}$ senza subirla). Questo framework modella scenari come i sistemi di comunicazione a banda ultra-larga (rilevamento di un canale diverso dal canale di trasmissione) e il trasferimento sim-to-real nella robotica. L'obiettivo è minimizzare il pseudo-rimpianto, definito come la differenza tra la perdita cumulativa subita dalle scelte di sfruttamento dell'agente e la perdita cumulativa del miglior braccio fisso a posteriori.

L'articolo mira a garantire Best-of-Both-Worlds (BOBW), puntando a ottenere:

1. Rimpianto ottimale di $O(\sqrt{KT})$ nel regime avversario (dove le perdite sono determinate da un avversario adattivo).
2. Rimpianto quasi-ottimale, indipendente dal tempo di $O(K/\Delta_{\min})$ nel regime avversario stocasticamente vincolato (SCA) (che include il setting stocastico standard), dove $\Delta_{\min}$ è il minimo gap di subottimalità.

Metodologia
Gli autori propongono una nuova politica basata sul framework Follow-the-Perturbed-Leader (FTPL), specificamente progettata per superare i colli di bottiglia computazionali delle politiche BOBW esistenti nei setting decouplati.

• Strategia di Sfruttamento: L'agente seleziona il braccio di sfruttamento $i_t$ minimizzando una stima della perdita cumulativa perturbata:
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  dove $\hat{L}_{t,i}$ è la stima della perdita cumulata, $\eta_t$ è il tasso di apprendimento e $r_{t,i}$ sono perturbazioni casuali i.i.d. campionate da una distribuzione di Pareto $P_\alpha$ con parametro di forma $\alpha > 1$. Questo tipo di perturbazione corrisponde alla politica $\beta$-Tsallis-INF (con $\alpha = 1/(1-\beta)$), nota per garantire BOBW.

• Strategia di Esplorazione (Innovazione Chiave): Negli algoritmi standard per bandit FTPL, la costruzione di uno stimatore di perdita non distorto pesato per importanza (IW) richiede tipicamente di conoscere la probabilità esatta $w_{t,i}$ di selezionare il braccio $i$. Nei bandit decouplati, la probabilità di esplorazione $p_{t,i}$ deve essere impostata basandosi su $w_{t,i}$. Tuttavia, FTPL non fornisce un'espressione in forma chiusa per $w_{t,i}$ (a differenza di FTRL), e stimare il vettore completo tramite ricampionamento geometrico è computazionalmente costoso ($O(K^2)$ o superiore).
  Per risolvere ciò, gli autori introducono una probabilità surrogata $q_{t,i}$ che può essere calcolata direttamente dalle attuali stime delle perdite senza ricampionamento o ottimizzazione convessa:
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  dove $\sigma_{t,i}$ è il rango di $\hat{L}_{t,i}$ tra tutti i bracci. Il braccio di esplorazione $j_t$ viene quindi selezionato secondo la distribuzione normalizzata $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$. Questo approccio evita la necessità di valori espliciti di $w_{t,i}$ mantenendo al contempo le proprietà teoriche richieste per le garanzie BOBW.

Contributi Chiave

1. Prima Politica BOBW basata su FTPL per Bandit Decouplati: L'articolo presenta la prima politica che garantisce BOBW nei bandit decouplati senza risolvere problemi di ottimizzazione convessa (richiesti dagli approcci basati su FTRL come Decoupled-Tsallis-INF) o impiegare procedure di ricampionamento (tipicamente necessarie per la stima della probabilità in FTPL).
2. Efficienza Computazionale: Sostituendo il calcolo del vettore completo delle probabilità con la surrogata efficientemente calcolabile $q_{t,i}$, la politica proposta riduce la complessità computazionale per passo. Sebbene l'ordinamento delle stime delle perdite richieda $O(K \log K)$, gli autori notano che un'implementazione ottimizzata può raggiungere aggiornamenti $O(K)$ tracciando i cambiamenti di rango in modo incrementale. Ciò contrasta con le politiche FTRL che richiedono ottimizzazione convessa iterativa (ad esempio, il metodo di Newton) ad ogni passo.
3. Garanzie Teoriche:
   • Regime Avversario: La politica ottiene un limite di rimpianto $O(\sqrt{KT})$, che corrisponde al limite inferiore noto per i bandit decouplati.
   • Regime Stocastico/SCA: La politica ottiene un limite di rimpianto di $O(K/\Delta_{\min})$ (specificamente $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$ per $\alpha=3$), che è quasi-ottimale e migliora i limiti dipendenti dal tempo dei bandit stocastici standard.

Risultati

• Teorici: L'articolo fornisce prove rigorose (tramite la decomposizione del rimpianto in termini di stabilità e penalità) che mostrano come la probabilità surrogata $q_{t,i}$ sia sufficientemente vicina alla vera probabilità di sfruttamento da mantenere i necessari limiti di rimpianto.
• Empirici: Esperimenti su dati sintetici (sia in regime avversario che stocastico) e una simulazione nel mondo reale utilizzando il dataset MovieLens 100K dimostrano che la politica FTPL proposta:
  • Ottiene un rimpianto cumulativo inferiore rispetto alle politiche BOBW esistenti (Decoupled-Tsallis-INF/FTRL e EXP3).
  • Dimostra efficienza computazionale superiore. Nel regime avversario, la politica proposta esegue significativamente più velocemente delle baseline basate su FTRL. Per $K=64$, il rapporto di tempo di esecuzione tra FTRL e FTPL è stato osservato essere circa 1363 volte più lento.
  • Si scala efficacemente con il numero di bracci $K$, mantenendo robustezza attraverso dimensioni variabili del gap $\Delta$.

Significato e Affermazioni
L'articolo afferma che il suo contributo principale è colmare il divario tra l'ottimalità teorica delle politiche BOBW basate su FTRL e l'efficienza computazionale di FTPL nel contesto dei bandit decouplati. Eliminando la necessità di ottimizzazione convessa e ricampionamento, il metodo proposto permette a FTPL di realizzare appieno i suoi vantaggi di efficienza senza sacrificare le prestazioni in termini di rimpianto. Gli autori suggeriscono che la tecnica di utilizzare probabilità surrogata efficientemente calcolabili al posto di vettori di probabilità esatti possa essere applicabile ad altri framework algoritmici (come la famiglia Prod) oltre a FTPL, potenzialmente consentendo un'efficienza computazionale migliorata in setting di bandit più ampi. Il lavoro è motivato da applicazioni pratiche nei sistemi di comunicazione e nella robotica, dove la latenza computazionale per passo è critica.