Sintesi Tecnica: Tree-Guided Identify-Then-Exploit (TG-ITE)

Formulazione del Problema

Il documento affronta il problema dei banditi duellanti stocastici con $N$ bracci sotto l'assunzione del vincitore di Condorcet. In questo scenario, un apprendente seleziona coppie di bracci $(i, j)$ e osserva un esito binario che indica quale braccio ha vinto, governato da una matrice di preferenze incognita $P$. L'assunzione centrale è l'esistenza di un unico vincitore di Condorcet $a^\star$ tale che $P(a^\star, j) > 1/2$ per tutti i $j \neq a^\star$, mentre le preferenze tra i bracci non vincitori possono essere cicliche.

Lo studio si concentra sull'unificazione di tre distinti obiettivi all'interno di questo singolo framework:

1. Best Arm Identification (BAI): Restituire $a^\star$ con alta confidenza ($1-\delta$) a un tempo di arresto dipendente dai dati.
2. Minimizzazione del Regret Debole (Weak Regret): Minimizzare il regret cumulativo dove un round incurre in zero regret se almeno uno dei due bracci scelti è $a^\star$.
3. Minimizzazione del Regret Forte (Strong Regret): Minimizzare il regret dove un round incurre in zero regret solo se entrambi i bracci scelti sono $a^\star$ (self-play).

La questione di ricerca centrale è se un framework algoritmico unificato possa raggiungere prestazioni ottimali per tutti e tre gli obiettivi simultaneamente, superando il tradizionale compromesso tra esplorazione (necessaria per la BAI) ed esplorazione (necessaria per la minimizzazione del regret).

Metodologia: Tree-Guided Identify-Then-Exploit (TG-ITE)

La soluzione proposta, TG-ITE, adotta un paradigma Identify-Then-Exploit. Essa scinde il problema in una fase di identificazione condivisa seguita da strategie di sfruttamento specifiche per l'obiettivo.

1. Primitiva di Identificazione Condivisa: TREEASCENT

L'innovazione principale è un algoritmo di Identificazione Guidata da Albero chiamato TREEASCENT. A differenza delle standard strategie "Explore-Then-Commit" (ETC), che sono spesso subottimali nel regret cumulativo, TREEASCENT utilizza una struttura ad albero binario bilanciato e deterministico per guidare la ricerca del vincitore di Condorcet.

• Meccanismo: Partendo da un braccio arbitrario $b$, l'algoritmo risale il percorso degli antenati di un albero binario fisso. Ad ogni livello $h$, esegue un torneo di eliminazione su un "blocco di fratelli" di bracci (bracci appena attaccati a quel livello) per trovare un rappresentante.
• Fusione (Merging): Il rappresentante del blocco di fratelli viene poi confrontato con il "campione" corrente (il vincitore del livello precedente) utilizzando un test pairwise sequenziale (DUELTEST).
• Efficienza: Allocando budget di confidenza proporzionali alle dimensioni dei blocchi di fratelli (dimensioni che crescono geometricamente), l'algoritmo identifica un incumbent ad alta confidenza con una complessità campionaria di $O(N)$. Ciò è ottenuto senza richiedere assunzioni più forti come la transitività stocastica forte o la disuguaglianza triangolare stocastica, basandosi solo sull'esistenza del vincitore di Condorcet e su un gap globale $\Delta$.

2. Strategie di Sfruttamento Specifiche per Obiettivo

Una volta identificato un incumbent ad alta confidenza tramite TREEASCENT, il framework passa a specifiche policy di sfruttamento:

• Per BAI (TG-ITE-BAI): L'algoritmo esegue semplicemente TREEASCENT e si ferma restituendo il braccio identificato. Questo raggiunge una complessità campionaria di $O(N)$, eguagliando il limite inferiore teorico per la BAI.
• Per il Regret Debole (TG-ITE-WEAK): L'algoritmo utilizza TREEASCENT come un "warm start" a confidenza costante per trovare un vincitore iniziale. Successivamente impiega una strategia di tipo Winner-Stays (WS) chiamata SCREENANDREPLACE. In ogni epoca, l'incumbent corrente viene sottoposto a screening contro tutti i contendenti. Se un contendente sembra battere l'incumbent, viene tenuto un torneo di sostituzione. Questo approccio raggiunge un regret debole di $O(N)$, migliorando i precedenti risultati di $O(N \log N)$.
• Per il Regret Forte (TG-ITE-STRONG): L'algoritmo identifica un incumbent affidabile tramite TREEASCENT e poi si impegna nel self-play (confrontando l'incumbent con se stesso).
  • Orizzonte Conosciuto: Eseguire TREEASCENT con confidenza $1/(H+1)$, poi self-play.
  • Orizzonte Anytime: Alternare passaggi di identificazione con confidenza crescente a blocchi di self-play sempre più lunghi.
  • Questo raggiunge un regret forte di $O(N \log T)$, eguagliando gli algoritmi specializzati per il regret forte.

Contributi Chiave e Risultati

1. Framework Unificato

TG-ITE è il primo framework che unifica BAI, weak regret e strong regret nei banditi duellanti utilizzando una primitiva di identificazione condivisa. Dimostra che il compromesso tra identificazione e minimizzazione del regret è "benigno" nell'ambito dei banditi duellanti grazie alla capacità di usare un braccio per l'esplorazione e un altro per lo sfruttamento.

2. Miglioramento della Complessità Campionaria e dei Limiti di Regret

• BAI: Raggiunge una complessità campionaria di $O(N)$ senza richiedere la transitività stocastica forte o assunzioni di ordine totale, eguagliando i migliori risultati noti per la BAI.
• Weak Regret: Raggiunge un regret debole di $O(N)$, chiudendo il gap di $O(\log N)$ trovato in precedenti approcci di ottimizzazione congiunta (es. Ma et al., 2025) e eguagliando i migliori limiti indipendenti dall'istanza.
• Strong Regret: Raggiunge un regret di $O(N \log T)$, eguagliando le garanzie di algoritmi specializzati come WS-S e RUCB.
• Ottimizzazione Congiunta: Il framework consente l'ottimizzazione simultanea di BAI e weak regret, raggiungendo garanzie di $O(N)$ per entrambi, eliminando i fattori subottimali di $O(\log N)$ presenti nel lavoro precedente.

3. Garanzie Teoriche

Il documento fornisce prove rigorose per la correttezza e il costo di TREEASCENT e delle successive fasi di sfruttamento.

• Teorema 1: TREEASCENT identifica il vincitore di Condorcet con probabilità $1-\epsilon$ usando $O(N)$ confronti.
• Teorema 2: Il regret debole di TG-ITE-WEAK è limitato da $O(N/\Delta^2)$, che è lineare in $N$ e indipendente dall'orizzonte temporale $T$.
• Teoremi 3 & 4: I limiti del regret forte sono $O(N \log T)$ sia per orizzonti noti che ignoti.

4. Estensioni

Il documento presenta anche un'Estensione a Budget con Gap Conosciuto (Sezione 5). Se un limite inferiore $g$ sul gap di Condorcet è noto, l'algoritmo può sostituire l'anytime DUELTEST con un test a budget fisso. Ciò rimuove il fattore $\log(1/\Delta)$ dai limiti, fornendo budget di confronto deterministici e garanzie più strette, sebbene al costo di richiedere la conoscenza pregressa del gap.

Validazione Sperimentale

Gli autori valutano TG-ITE rispetto a baseline rappresentative (inclusi WS-W, WS-S, RUCB, WR-TINF e WSW-PE) su istanze sintetiche progettate per testare la non-transitività e i gap asimmetrici.

• Scalabilità BAI: TG-ITE-BAI scala quasi linearmente con $N$, superando i metodi di eliminazione pairwise adattivi su istanze cicliche.
• Weak Regret: TG-ITE-WEAK raggiunge il minor regret cumulativo e si stabilizza rapidamente, dimostrando l'efficacia della strategia di warm-start.
• Strong Regret: TG-ITE-STRONG supera significativamente le baseline, con la curva che si appiattisce una volta iniziato il self-play, confermando il comportamento teorico $O(N \log T)$.

Significato e Rivendicazioni

Il documento sostiene che TG-ITE fornisce una prova teorica che il compromesso tra Best Arm Identification e Minimizzazione del Regret è relativamente benigno nei banditi duellanti. Sfruttando la struttura unica dei banditi duellanti (selezionare due bracci), il framework riesce a scindere con successo le fasi di esplorazione e sfruttamento senza la subottimalità tipicamente vista nei classici multi-armed bandits.

Gli autori sottolineano che il loro approccio:

1. Unifica tre distinti obiettivi sotto una singola, riutilizzabile primitiva di identificazione (TREEASCENT).
2. Migliora lo stato dell'arte per il weak regret rimuovendo il fattore $O(\log N)$ e rilassando l'assunzione di ordine totale.
3. Eguaglia i tassi ottimali per BAI e strong regret senza richiedere assunzioni strutturali più forti (come la transitività stocastica forte) su cui si basavano gli algoritmi ottimali precedenti.

Il lavoro suggerisce che il template "Identify-Then-Exploit", quando guidato da una decomposizione a torneo basata su alberi, è una strategia potente e generalizzabile per l'apprendimento basato sulle preferenze.