Sintesi Tecnica: Probing e Scheduling congiunti di AP tramite Contextual Bandits

Definizione del Problema

Il documento affronta la sfida di allocare efficientemente le risorse wireless in uno scenario in cui un insieme di Access Point (AP) serve cooperativamente un singolo client mobile. La difficoltà principale risiede nell'incertezza dei tassi di dati (data rates): la capacità di ogni link segue una distribuzione sconosciuta che varia in base alla posizione del client e ai fattori ambientali (ad es. ostruzioni, interferenze).

A differenza dei problemi tradizionali di scheduling dei link in cui il decisore deve scegliere un link senza osservazioni preventive, questo lavoro assume un setting di probing e play congiunto. In ogni istante temporale, il decisore può sondare (probe) un sottoinsieme limitato di $K$ AP (dove $K < N$, e $N$ è il numero totale di AP) per osservare i loro reward istantanei (tassi di dati) prima di selezionare un singolo AP per servire il client. L'obiettivo è massimizzare il reward atteso cumulativo su un orizzonte temporale $T$ apprendendo una politica ottimale che bilanci l'esplorazione (probing per apprendere le distribuzioni) e lo sfruttamento (playing per servire il client).

Gli autori modellano questo problema come un Contextual Bandit con Probing (CBwP). Il "contesto" è la posizione del client, e le "braccia" (arms) sono gli AP. La distribuzione del reward $\Phi(a|x)$ per l'arm $a$ dato il contesto $x$ è sconosciuta.

Metodologia

1. Struttura Ottimale Offline (Formulazione MDP)

Prima di affrontare il problema dell'apprendimento online, gli autori analizzano il setting offline in cui le distribuzioni dei reward sono note. Modellano la decisione congiunta di probing e play in ogni istante temporale come un Processo Decisionale di Markov (MDP).

• Stato: La cronologia delle braccia sondate e dei loro reward osservati.
• Politica di Play Ottimale: Dimostrano che per qualsiasi cronologia di probing, la strategia ottimale è deterministica: giocare l'arm con il massimo reward osservato tra le braccia sondate, oppure l'arm con il più alto reward atteso tra le braccia non sondate.
• Politica di Probing Ottimale: Per il caso specifico di reward Bernoulli (dove il reward è 1 con probabilità $\mu(a|x)$ e 0 altrimenti), derivano una semplice politica non adattiva ottimale: sondare le $K$ braccia con i reward attesi $\mu(a|x)$ più elevati, e se nessuna di esse produce un reward di 1, giocare la $(K+1)$-esima migliore arm.

2. Algoritmo di Apprendimento Online: Contextual Zooming

Per gestire il setting online con distribuzioni sconosciute, gli autori estendono l'algoritmo Contextual Zooming (proposto originariamente per i classici contextual bandits) al framework CBwP.

• Partizionamento dello Spazio: L'algoritmo mantiene un insieme di "active balls" (regioni nello spazio del contesto) per ogni AP. Inizialmente, l'intero spazio è coperto da una singola ball di raggio 1.
• Calcolo dell'Indice: Per ogni ball $B$, l'algoritmo calcola un indice $I_t(B)$ che combina il reward medio osservato, il raggio della ball e un termine di confidenza (stile Upper Confidence Bound).
• Processo Decisionale in Tre Fasi per Round:
  1. Regola di Probing: L'algoritza seleziona fino a $K$ braccia da sondare. Sceglie l'arm non sondata associata alla active ball contenente l'attuale contesto $x_t$ che ha l'indice più alto. Il probing si interrompe anticipatamente se un'arm produce un reward di 1 (per Bernoulli) o dopo $K$ probe.
  2. Regola di Play: Dopo il probing, l'algoritmo seleziona un'arm da giocare. Se un'arm sondata ha prodotto un reward di 1, viene giocata. Altrimenti, l'algoritmo gioca l'arm con il valore stimato più alto (ovvero il reward osservato se sondata, o l'indice se non sondata).
  3. Regola di Attivazione: Se un'arm viene sondata o giocata, l'algoritmo aggiorna le statistiche. Se il raggio di confidenza della ball corrente è più piccolo del raggio fisico della ball, la ball viene "zoomata" attivando una nuova ball figlia con metà del raggio centrata sull'attuale contesto.

3. Analisi del Regret

Gli autori stabiliscono un limite teorico del regret per l'algoritmo sotto l'assunzione di reward Bernoulli. Definiscono "clean runs" in cui i reward stimati sono vicini ai valori medi reali (entro un intervallo di confidenza). Limitando la probabilità di "bad runs" e analizzando il regret durante le "clean runs" utilizzando la continuità Lipschitz della funzione di reward rispetto alla distanza del contesto, derivano un limite di regret sub-lineare che dipende dal numero di copertura dello spazio del contesto e dal limite di probing $K$.

Contributi Chiave

1. Framework Innovativo (CBwP): Il paper introduce i Contextual Bandits con Probing, una nuova estensione del classico modello di contextual bandit che incorpora esplicitamente una fase di "probing" prima della fase di "play". Questo modella i vincoli del mondo reale in cui un sounding limitato del canale (ad es. beamforming) è possibile prima della trasmissione.
2. Approfondimenti Strutturali: Gli autori forniscono proprietà strutturali della soluzione ottimale offline, dimostrando che per i reward Bernoulli una strategia di probing greedy non adattiva è ottimale.
3. Design dell'Algoritmo: Propongono un efficiente algoritmo di apprendimento online che adatta la tecnica di contextual zooming al setting congiunto di probing/play, gestendo il compromesso tra costo di probing e guadagno di informazione.
4. Garanzie Teoriche: Viene stabilito un limite formale del regret per l'algoritmo proposto nel caso del reward Bernoulli.
5. Validazione Empirica: La soluzione è valutata utilizzando tracce di canale reali da un testbed 802.11ad e un simulatore di canale mmWave.

Risultati Sperimentali

La valutazione è stata condotta in uno scenario "Student Hall" utilizzando router e laptop 802.11ad, simulando client mobili che si muovono nell'ambiente.

• Baseline: Il proposto algoritmo CBwP è stato confrontato con quattro baseline: Random Probing/Random Play (RR), Random Probing/Greedy Play con Esplorazione (RG), Random Probing/Greedy Play senza Esplorazione (RG2) e Greedy Probing/Play senza Esplorazione (GNE).
• Prestazioni:
  • Regret: CB-WP ha costantemente ottenuto un regret cumulativo inferiore rispetto a tutte le baseline. Mentre le baseline mostravano un regret più elevato che aumentava con il numero di AP, CBWP è rimasto stabile.
  • Limite di Probing ($K$): Aumentare $K$ (il numero di probe consentite) riduce il regret per tutti gli algoritmi, ma CBWP mantiene un vantaggio significativo indipendentemente da $K$.
  • Scalabilità: All'aumentare del numero di AP ($N$), le prestazioni delle baseline degradano, mentre CBWP dimostra robustezza.
  • Ambienti Dinamici: L'algoritmo si è adattato con successo a nuovi client che entravano in aree precedentemente inesplorate della stanza, mostrando una rapida convergenza verso un basso regret.

Significato e Rivendicazioni

Il paper sostiene che il modello CBwP sia un'estensione innovativa del classico framework dei contextual bandit. La sua importanza primaria risiede nella capacità di modellare e risolvere problemi di decision-making sequenziale in cui un decisore può acquisire informazioni parziali (tramite probing) prima di agire, in condizioni di incertezza.

Gli autori affermano che questo framework è direttamente applicabile al beamforming e allo scheduling congiunti nelle reti WLAN mmWave di prossima generazione (802.11ad/ay), dove il beamforming completo è troppo costoso, ma un probing limitato è fattibile. Inoltre, suggeriscono che il modello abbia una più ampia applicabilità in altri domini che coinvolgono il probing e il play congiunti, come:

• Combinatorial Multi-Armed Bandits: Per scenari multi-AP e multi-client.
• Ricerca di Percorsi nelle Reti Stradali: Dove un ricercatore può interrogare un server per ottenere indizi limitati sul traffico prima di scegliere un percorso, bilanciando i costi di query rispetto alla latenza di viaggio.

Il lavoro sottolinea che, sebbene il probing riduca l'incertezza, non la elimina del tutto; pertanto, l'integrazione dell'esplorazione sia nella fase di probing che in quella di play è cruciale per raggiungere prestazioni ottimali.