Bandit-Based Rate Adaptation for a Single-Server Queue

Sintesi Tecnica: Adattamento del Tasso Basato su Bandit per una Coda a Servitore Singolo

Formulazione del Problema
Questo articolo affronta il problema dell'adattamento del tasso in un sistema di code a servitore singolo che opera in slot temporali discreti con feedback parziale. In ogni slot $t$, un trasmettitore seleziona un tasso di trasmissione $V(t)$ da un intervallo continuo $[0, 1]$. La capacità del canale $C(t)$ e il processo di arrivo $A(t)$ sono campionamenti indipendenti e identicamente distribuiti (i.i.d.) da distribuzioni fisse ma sconosciute. La trasmissione ha successo se e solo se $V(t) \leq C(t)$; altrimenti fallisce. Il trasmettitore riceve solo un feedback binario (ACK/NACK) che indica successo o fallimento. L'obiettivo è progettare un algoritmo di selezione del tasso che garantisca una dimensione media temporale dell'attesa uniformemente limitata, a condizione che il tasso di arrivo $\lambda$ si trovi strettamente all'interno della regione di capacità del sistema. Il "margine" (slack) tra il tasso di arrivo e la massima velocità di servizio ottenibile è indicato con $\varepsilon > 0$.

Gli autori distinguono tra due scenari:

1. $\varepsilon$ noto: Il trasmettitore ha una conoscenza a priori del limite inferiore del divario tra il tasso di arrivo e la regione di capacità.
2. $\varepsilon$ sconosciuto: Il trasmettitore non conosce $\varepsilon$ e deve apprendere la dinamica del sistema senza questo parametro.

Metodologia
Il documento integra la teoria delle code con i bandit a bracci continui (continuum-armed bandit). A differenza dei classici bandit di coda che operano su spazi di azione finiti, questo lavoro gestisce uno spazio di tasso incontabile e infinito.

• Per $\varepsilon$ noto: Gli autori propongono una strategia di discretizzazione in cui lo spazio continuo dei tassi $[0, 1]$ viene mappato su una griglia finita di dimensione $d = \lceil \gamma/\varepsilon \rceil$. Questo trasforma il problema in un problema di bandit a bracci finiti. Gli autori applicano il classico algoritmo Upper Confidence Bound (UCB1) a questo insieme discretizzato. Essi eseguono un rigoroso' analisi in due fasi: una fase di apprendimento per identificare il tasso discretizzato ottimale e una fase di controllo utilizzando l'analisi del drift di Lyapunov per limitare la dimensione della coda una volta che il tasso è sufficientemente vicino all'ottimale.

• Per $\varepsilon$ sconosciuto: Gli autori propongono un algoritmo a fasi che raffina iterativamente la discretizzazione dello spazio dei tassi. L'algoritmo opera in fasi $\ell = 1, 2, \dots$. In ogni fase $\ell$, lo spazio dei tassi viene discretizzato in $d_\ell$ livelli, dove $d_\ell$ cresce come funzione della lunghezza della fase $T_\ell$. All'interno di ogni fase, un adattamento UCB1 viene eseguito sulla discretizzazione corrente. Le sequenze $\{T_\ell\}$ e $\{d_\ell\}$ sono scelte accuratamente (specificamente, $T_\ell = 2^{\ell+2}$ e $d_\ell \propto T_\ell^{1/2-\delta}$) per bilanciare l'onere dell'esplorazione rispetto alla necessità di una discretizzazione più fine per garantire la stabilità.

Contributi Chiave

1. Formulazione Innovativa: Il documento introduce la prima integrazione tra la stabilità delle code e i bandit a bracci continui, affrontando la sfida per cui nessun insieme finito fisso di bracci può garantire la stabilità senza la conoscenza delle distribuzioni di arrivo e di servizio sconosciute.
2. Design dell'Algoritmo per $\varepsilon$ Sconosciuto: Un algoritmo UCB a fasi è progettato per raffinare adattivamente la discretizzazione del tasso senza conoscenza previa di $\varepsilon$.
3. Risultato di Converse: Gli autori stabiliscono un limite inferiore (converse) mostrando che per qualsiasi algoritmo di selezione del tasso (sia $\varepsilon$ sia noto che sconosciuto), esiste un ambiente in cui la dimensione media temporale attesa della coda è $\Omega(1/\varepsilon^2)$.
4. Ottimalità per $\varepsilon$ Noto: Il documento prova che, quando $\varepsilon$ è noto, il proposto algoritmo basato su UCB su una discretizzazione fissa raggiunge una dimensione media temporale dell'attesa di $O(\log(1/\varepsilon)/\varepsilon^2)$. Ciò corrisponde al limite inferiore di converse fino a fattori logaritmici, stabilendo l'ottimalità in questo scenario.

Risultati

• $\varepsilon$ Sconosciuto: Il proposto algoritmo a fasi raggiunge una dimensione media temporale dell'attesa di ordine $O(\log^{3.5}(1/\varepsilon)/\varepsilon^3)$ uniformemente sull'orizzonte temporale.
• $\varepsilon$ Noto: L'algoritmo raggiunge una dimensione media temporale dell'attesa di ordine $O(\log(1/\varepsilon)/\varepsilon^2)$.
• Limite Inferiore: Il risultato di converse dimostra che la dimensione della coda non può essere migliore di $\Omega(1/\varepsilon^2)$ nel caso peggiore, indipendentemente dalla conoscenza di $\varepsilon$ da parte dell'algoritmo.

Significatività e Rivendicazioni
Il documento sostiene di essere il primo a integrare la stabilità delle code con i bandit a bracci continui, motivato da applicazioni pratiche come la selezione del tasso nei sistemi IEEE 802.11, dove lo spazio delle azioni è troppo grande per le formulazioni a bracci finiti.

Gli autori evidenziano un divario tra il limite superiore ($O(\varepsilon^{-3})$) e il limite inferiore ($O(\varepsilon^{-2})$) nell'impostazione con $\varepsilon$ sconosciuto. Essi congetturano che un algoritmo che raggiunga $O(\log^\alpha(1/\varepsilon)/\varepsilon^2)$ sia possibile quando $\varepsilon$ è sconosciuto, il che chiuderebbe questo divario. Il documento dichiara esplicitamente che la progettazione di un tale algoritmo è lasciata come lavoro futuro. Inoltre, gli autori suggeriscono di estendere il framework delle code a bracci continui a contesti multi-coda o di rete come un altro orientamento futuro.

Il lavoro fornisce una base teorica per l'adattamento del tasso sotto feedback parziale, dimostrando che mentre la conoscenza del margine di sistema $\varepsilon$ permette prestazioni quasi ottimali, l'apprendimento senza questa conoscenza comporta una penalità polinomiale nel limite della dimensione della coda.