Riepilogo Tecnico: Rimpianto Ottimale per Banditi a Singolo Indice

Definizione del Problema

Il documento affronta il problema del Bandito a Singolo Indice (SIB), un framework di decisione sequenziale in cui le ricompense dipendono da una proiezione unidimensionale sconosciuta di vettori di contesto ad alta dimensionalità attraverso una funzione di ricompensa sconosciuta e non parametrica.

Formalmente, ad ogni round $t$, l'apprendente osserva un insieme di $K$ vettori di contesto $X_t = \{x_{t,a} \in \mathbb{R}^d\}_{a \in [K]}$. L'apprendente seleziona un braccio $x_{t,a}$ e osserva una ricompensa stocastica:
$$y_t = f(x_{t,a}^\top \theta^*) + \eta_t$$
dove:

• $\theta^* \in \mathbb{R}^d$ è un vettore di parametri sconosciuto (la direzione dell'indice).
• $f: \mathbb{R} \to \mathbb{R}$ è una funzione di collegamento sconosciuta, continuamente differenziabile.
• $\eta_t$ è un rumore a media zero con varianza limitata.

L'obiettivo è minimizzare il rimpianto cumulativo, definito come la differenza tra la ricompensa attesa del braccio ottimale e quella del braccio scelto su un orizzonte temporale $T$.

Contesto e Lacuna:
Mentre i tassi di rimpianto ottimali sono stabiliti per i banditi lineari ($\tilde{O}(\sqrt{T})$) e per i banditi lineari generalizzati (dove $f$ è nota), l'impostazione SIB è più impegnativa perché $f$ è sconosciuta. Lavori precedenti di Kang et al. [2025] hanno affrontato il caso in cui $f$ è sconosciuta ma monotona, ottenendo un rimpianto ottimale $\tilde{O}(\sqrt{T})$ utilizzando stimatori di Stein. Tuttavia, per il caso generale non monotono (assumendo solo limitatezza e continuità lipschitziana di $f$), il limite superiore noto era $\tilde{O}(T^{3/4})$. La domanda centrale di questo lavoro è: Qual è la scala di rimpianto ottimale per i banditi a singolo indice generali (non monotoni)?

Metodologia: ZoomSIB-UCB

Gli autori propongono un algoritmo in due fasi denominato Bandito a Singolo Indice Zoomato con Limite Superiore di Confidenza (ZoomSIB-UCB). L'idea centrale è ridurre il problema ad alta dimensionalità a una sequenza di problemi di banditi unidimensionali stimando la direzione di proiezione $\theta^*$ e successivamente discretizzando lo spazio proiettato.

Fase 1: Stima dei Parametri

L'algoritmo dedica i primi $T_0$ round alla stima della direzione sconosciuta $\theta^*$.

• Esplorazione: I bracci vengono estratti uniformemente a caso.
• Stima: L'algoritmo impiega uno stimatore di Stein normalizzato. Sfruttando l'Identità di Stein, che afferma che $E[y S(x)] = E[f'(x^\top \theta^*)] \theta^* = \mu^* \theta^*$ (dove $S(x)$ è la funzione di punteggio della distribuzione del contesto), l'algoritmo costruisce uno stimatore non distorto per la direzione di $\theta^*$.
• Normalizzazione: Per risolvere le ambiguità di scala e di segno, lo stimatore viene normalizzato utilizzando la norma $\ell_1$.
• Calibrazione: L'orizzonte di esplorazione $T_0$ è scelto in modo che l'errore di stima $\|\hat{\theta}_0 - \theta^*\|_1$ sia sufficientemente piccolo (specificamente limitato da $\Delta / 2L$, dove $\Delta$ è la larghezza del bin e $L$ è la costante di Lipschitz del contesto).

Fase 2: UCB Discretizzato

Una volta calcolato $\hat{\theta}_0$, l'algoritmo opera sui valori scalari proiettati $z = x^\top \hat{\theta}_0$.

• Discretizzazione: La retta reale è partizionata in $N = O(T^{1/3})$ bin di larghezza $\Delta = T^{-1/3}$.
• Banditi Dormienti: Ad ogni round, solo un sottoinsieme casuale di bin è "attivo" (contenente almeno un braccio disponibile). Ciò introduce una struttura di "bandito dormiente" in cui l'insieme dei bracci disponibili cambia stocasticamente.
• Strategia UCB: L'algoritmo esegue un algoritmo UCB sui bin disponibili. Seleziona il braccio appartenente al bin con il più alto indice del Limite Superiore di Confidenza.
• Gestione del Bias: L'algoritmo tiene conto di due fonti di errore:
  1. Bias di Discretizzazione: L'approssimazione delle ricompense continue tramite i centri dei bin (limitata dalla continuità lipschitziana).
  2. Errore di Stima: Lo spostamento del vero indice dovuto all'errore di stima di $\theta^*$.
     Questi errori sono assorbiti in un raggio di confidenza inflazionato.

Contributi Chiave

1. Limite Superiore di Rimpianto Migliorato

Il documento stabilisce un limite di rimpianto di $\tilde{O}(d^2 T^{2/3})$ per i banditi a singolo indice generali non monotoni.

• Questo rappresenta un miglioramento significativo rispetto al precedente limite migliore di $\tilde{O}(T^{3/4})$ di Kang et al. [2025].
• L'algoritmo ottiene questo risultato bilanciando il bias di discretizzazione ($O(T\Delta)$) e il costo di esplorazione del problema del bandito 1D ($O(\sqrt{N T})$). Impostando $N \sim T^{1/3}$ (e quindi $\Delta \sim T^{-1/3}$) si minimizza il rimpianto totale a $O(T^{2/3})$.

2. Limite Inferiore Minimax Corrispondente

Gli autori dimostrano un limite inferiore minimax di $\tilde{\Omega}(T^{2/3})$ per l'impostazione generale non monotona.

• Costruzione: Costruiscono un'istanza di problema difficile che coinvolge una famiglia di funzioni con piccoli "rigonfiamenti" localizzati di altezza $\sim T^{-1/3}$.
• Riduzione: Riducono il problema SIB a un problema di bandito a $N$ bracci (dove $N \sim T^{1/3}$) garantendo un'alta probabilità di disponibilità del braccio in ogni bin.
• Trappola Teorica dell'Informazione: Utilizzando la disuguaglianza di Bretagnolle-Huber, dimostrano che distinguere tra un'ipotesi nulla e un'ipotesi "a picco" (dove un bin specifico è ottimale) richiede un'esplorazione massiccia, forzando un rimpianto di $\Omega(T^{2/3})$.
• Significato: Ciò conferma che il limite superiore $\tilde{O}(T^{2/3})$ è stretto e che l'algoritmo proposto è minimax ottimale.

3. Validazione Empirica

Estesi esperimenti su dataset sintetici e reali (KDD Cup 99, Forest Cover Type) dimostrano:

• Prestazioni Superiori: ZoomSIB-UCB supera costantemente lo stato dell'arte GSTOR (Kang et al. [2025]) e le basi di riferimento casuali, ottenendo un rimpianto cumulativo sostanzialmente inferiore.
• Scalabilità: L'algoritmo mostra una scalatura del rimpianto sublineare con un esponente empirico di $\approx 0.53$ (Quadratico) e $0.57$ (Zigzag), ben al di sotto del limite teorico del caso peggiore di $2/3$.
• Dimensionalità: L'algoritmo è robusto a contesti ad alta dimensionalità ($d$), poiché opera nello spazio proiettato 1D dopo la fase di stima iniziale, aggirando efficacemente la maledizione della dimensionalità che affligge i metodi basati su kernel.
• Arresto Adattivo: Una regola di arresto adattiva permette all'algoritmo di terminare la fase di esplorazione in anticipo quando la stima del parametro si stabilizza, evitando la necessità di conoscenze a priori su $\mu^*$ o $T$.

Significato e Affermazioni

Il documento afferma di risolvere un problema aperto nell'apprendimento sequenziale fornendo la prima caratterizzazione precisa del rimpianto per i banditi a singolo indice generali non monotoni.

• Ottimalità: Fornendo sia un limite superiore che un limite inferiore corrispondente, gli autori stabiliscono che la corretta scala di rimpianto è $\Theta(T^{2/3})$ (ignorando i fattori logaritmici).
• Generalità: A differenza di approcci precedenti che si basavano sulla monotonia o su classi specifiche di regolarità (come RKHS), questo metodo funziona per qualsiasi funzione di ricompensa limitata e lipschitziana senza richiedere la conoscenza della forma della funzione o del parametro $\mu^*$.
• Praticità: L'introduzione di una regola di arresto adattiva rende l'algoritmo implementabile nella pratica senza richiedere che l'orizzonte di esplorazione teorico $T_0$ sia fissato a priori in base a costanti sconosciute.

Il lavoro colma il divario tra statistica non parametrica e teoria dei banditi, dimostrando che la struttura a singolo indice può essere sfruttata per ottenere tassi ottimali anche quando la funzione di ricompensa è completamente sconosciuta e non monotona.