Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

Formulazione del Problema
Questo lavoro indaga i banditi logistici stocastici nell'ambito dell'obiettivo di semplice rimpianto. In questo contesto, un apprendista interagisce con un ambiente per $T$ round, selezionando azioni $A_t$ da un insieme $\mathcal{A}$ e osservando ricompense Bernoulliane $X_t$ con media $\mu(\phi(A_t)^\top \theta^*)$, dove $\mu$ è la funzione sigmoide, $\phi$ è una mappa di caratteristiche nota e $\theta^*$ è un parametro sconosciuto in $\mathbb{R}^d$. A differenza del rimpianto cumulativo, dove l'obiettivo è massimizzare la somma delle ricompense durante l'esplorazione, l'obiettivo di semplice rimpianto valuta l'apprendista esclusivamente sulla qualità di un'unica raccomandazione finale $\hat{a}$ dopo $T$ round. Il rimpianto è definito come la differenza tra la ricompensa attesa dell'azione ottimale e la ricompensa attesa dell'azione raccomandata.

Una sfida critica nei banditi logistici è la non uniformità dell'informatività delle azioni. A causa del collegamento sigmoide, le azioni in regioni "sature" (dove la ricompensa media è vicina a 0 o 1) producono ricompense quasi deterministiche ma forniscono poche informazioni sul parametro $\theta^*$. Al contrario, le azioni vicino all'origine (dove la sigmoide è più ripida) sono altamente informative ma possono produrre ricompense immediate inferiori. Questo crea una geometria in cui le azioni migliori per la ricompensa immediata (sfruttamento) differiscono da quelle migliori per identificare l'azione ottimale (esplorazione).

Metodologia
Gli autori propongono due algoritmi consapevoli della curvatura progettati per sfruttare la geometria locale della funzione sigmoide:

1. MULOG (Max-Uncertainty-Log): Un algoritmo deterministico di pura esplorazione.

   • Meccanismo: MULOG mantiene un insieme di confidenza $W_t$ per $\theta^*$ e costruisce una matrice di progetto ponderata per la curvatura $L_t$. Il punteggio di incertezza per un'azione $a$ e un parametro $\theta$ è definito come $U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$, dove $\dot{\mu}$ è la derivata della sigmoide (che rappresenta la curvatura locale).
   • Selezione: In ogni round, l'algoritmo seleziona la coppia azione-parametro $(A_t, \theta_t)$ che massimizza questo punteggio di incertezza.
   • Terminazione: Dopo $T$ round, restituisce l'azione greed rispetto a un vettore di parametri campionato dall'insieme di confidenza finale.
   • Ottimizzazione: Per insiemi di azioni finiti, il passo di selezione si riduce alla risoluzione di una collezione finita di problemi di ottimizzazione convessa.

2. THATS (Try Hard Thompson Sampling): Un'alternativa randomizzata, computazionalmente più leggera.

   • Meccanismo: Invece di risolvere per l'incertezza massima esatta, THATS campiona una direzione $\tilde{\theta}_t$ da una distribuzione Gaussiana centrata in zero con covarianza $L_t^{-1}$.
   • Selezione: Seleziona l'azione che massimizza il punteggio di incertezza randomizzato $\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$, dove $\bar{\theta}_t$ è una stima di massima verosimiglianza vincolata.
   • Compromesso: Questo approccio evita l'ottimizzazione convessa richiesta da MULOG ma comporta un costo statistico, risultando in un limite di rimpianto leggermente più lasco.

Contributi Chiave

• Limite Inferiore Minimax: Il lavoro stabilisce un limite inferiore minimax del primo ordine dell'ordine $\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, dove $\kappa^*$ è l'inverso della pendenza della sigmoide all'azione ottimale (cioè $\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$).
  • Meccanismo di Difficoltà Distinto: A differenza dei limiti inferiori per il rimpianto cumulativo (ad es. Abeille et al., 2021) che si basano sul costo dell'informazione (costringendo l'apprendista a giocare bracci quasi ottimali), questo limite inferiore è derivato da una costruzione di "ipercubo saturo spostato". In questa costruzione, sia l'informazione statistica che la sensibilità al valore sono controllate dalla stessa curvatura locale in una regione satura. Ciò rivela che anche con la libertà di campionare puramente per informazione, il problema rimane difficile se l'azione ottimale giace in una regione piatta della sigmoide.
• Algoritmi Ottimali:
  • MULOG raggiunge un limite superiore di semplice rimpianto di $\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, che corrisponde al limite inferiore fino a fattori logaritmici. Questa è la prima garanzia di pura esplorazione diretta per banditi logistici che raggiunge l'ottimalità minimax istanza per istanza.
  • THATS raggiunge un limite di $\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$. Il fattore extra $\sqrt{d}$ deriva dall'uso di un'approssimazione randomizzata agnostica alla geometria della direzione di massima incertezza.
• Intuizione Geometrica: Gli autori dimostrano che la geometria del caso peggiore (istanze di ipercubi saturi spostati) non è l'unico caso. Mostrano che possono esistere "azioni informative a bassa ricompensa" (sonde) nell'insieme delle azioni. Queste azioni giacciono nella regione ad alta curvatura della sigmoide, fornendo informazioni significative sulla direzione ottimale nonostante abbiano ricompense attese basse.

Risultati

• Teorici: I limiti derivati confermano che la difficoltà del semplice rimpianto logistico è governata dalla curvatura all'azione ottimale. Gli algoritmi controllano con successo l'incertezza nelle direzioni delle caratteristiche ponderate per la curvatura.
• Empirici: Gli esperimenti su geometrie sia "difficili" (ipercubi saturi spostati) che "facili" (con bracci sonda informativi aggiunti) supportano i risultati teorici:
  • Su istanze difficili, MULOG e THATS si comportano come previsto dai limiti minimax.
  • Su istanze facili con bracci sonda, i metodi di pura esplorazione (MULOG e THATS) superano significativamente le baseline di rimpianto cumulativo (come Thompson Sampling cumulativo e conversioni online-to-batch). I metodi di pura esplorazione campionano attivamente le sonde a bassa ricompensa e ad alta informazione, riducendo drasticamente i round necessari per raggiungere una soglia di semplice rimpianto bassa.
  • I metodi di rimpianto cumulativo falliscono nello sfruttare efficacemente queste sonde perché la loro conversione online-to-batch penalizza l'inclusione di azioni a bassa ricompensa nella distribuzione della raccomandazione finale.

Significato
Il lavoro afferma che l'esplorazione pura nei banditi logistici possiede una geometria distinta rispetto ai problemi di rimpianto cumulativo. Il contributo principale è l'identificazione del fatto che la curvatura locale all'azione ottimale ($\kappa^*$) è il fattore governante per il tasso minimax del primo ordine. Sviluppando algoritmi che tengono esplicitamente conto di questa curvatura, gli autori raggiungono prestazioni minimax-ottimali nel caso peggiore. Inoltre, il lavoro evidenzia un'implicazione pratica: in contesti come i test A/B o la raccolta di dati per modelli di ricompensa, cercare attivamente azioni "informativi ma a bassa ricompensa" può accelerare sostanzialmente l'identificazione della migliore politica finale, un comportamento che gli algoritmi standard di rimpianto cumulativo sono strutturalmente incapaci di esibire. I risultati servono come punto di partenza per una teoria più precisa dell'esplorazione focalizzata sulla decisione nei banditi non lineari.