Bandit-Based Rate Adaptation for a Single-Server Queue

Technische Zusammenfassung: Bandit-basierte Ratenadaptation für eine Ein-Server-Warteschlange

Problemformulierung
Diese Arbeit behandelt das Problem der Ratenadaptation in einem Ein-Server-Warteschlangensystem, das in diskreten Zeitschlitzen mit teilweiser Rückmeldung operiert. In jedem Zeitschlitz $t$ wählt ein Sender eine Übertragungsrate $V(t)$ aus einem kontinuierlichen Intervall $[0, 1]$. Die Kanalkapazität $C(t)$ und der Ankunftsprozess $A(t)$ sind identisch und unabhängig verteilte (i.i.d.) Stichproben aus festen, aber unbekannten Verteilungen. Eine Übertragung ist erfolgreich, wenn und nur wenn $V(t) \leq C(t)$; andernfalls schlägt sie fehl. Der Sender erhält lediglich binäres Feedback (ACK/NACK), das Erfolg oder Misserfolg anzeigt. Das Ziel ist der Entwurf eines Algorithmus zur Ratenselektion, der eine gleichmäßig beschränkte zeitliche durchschnittliche erwartete Warteschlangengröße gewährleistet, sofern die Ankunftsrate $\lambda$ strikt innerhalb der Kapazitätsregion des Systems liegt. Der „Slack“ (Spielraum) zwischen der Ankunftsrate und der maximal erreichbaren Servicerate wird als $\varepsilon > 0$ bezeichnet.

Die Autoren unterscheiden zwischen zwei Szenarien:

1. Bekanntes $\varepsilon$: Der Sender verfügt über Vorabwissen über die untere Schranke der Lücke zwischen der Ankunftsrate und der Kapazitätsregion.
2. Unbekanntes $\varepsilon$: Der Sender kennt $\varepsilon$ nicht und muss die Systemdynamik ohne diesen Parameter erlernen.

Methodik
Die Arbeit integriert Warteschlangentheorie mit Continuum-Armed-Bandit-Learning. Im Gegensatz zu Standard-Queueing-Bandits, die auf endlichen Aktionsräumen operieren, behandelt diese Arbeit einen unzählbaren unendlichen Ratenselektionsraum.

• Für bekanntes $\varepsilon$: Die Autoren schlagen eine Diskretisierungsstrategie vor, bei der der kontinuierliche Ratenselektionsraum $[0, 1]$ auf ein endliches Gitter der Größe $d = \lceil \gamma/\varepsilon \rceil$ abgebildet wird. Dies transformiert das Problem in ein endliches Finite-Armed-Bandit-Problem. Die Autoren wenden den klassischen Upper Confidence Bound (UCB1)-Algorithmus auf diesen diskretisierten Satz an. Sie führen eine rigorose zweistufige Analyse durch: eine Lernphase zur Identifizierung der optimalen diskretisierten Rate und eine Kontrollphase mittels Lyapunov-Drift-Analyse, um die Warteschlangengröße zu begrenzen, sobald die Rate ausreichend nah am Optimum liegt.

• Für unbekanntes $\varepsilon$: Die Autoren schlagen einen phasenbasierten Algorithmus vor, der die Diskretisierung des Ratenseums iterativ verfeinert. Der Algorithmus operiert in Phasen $\ell = 1, 2, \dots$. In jeder Phase $\ell$ wird der Ratenselektionsraum in $d_\ell$ Stufen diskretisiert, wobei $d_\ell$ als Funktion der Phasenlänge $T_\ell$ wächst. Innerhalb jeder Phase läuft eine UCB1-Adaption auf der aktuellen Diskretisierung. Die Sequenzen $\{T_\ell\}$ und $\{d_\ell\}$ werden sorgfältig gewählt (speziell $T_\ell = 2^{\ell+2}$ und $d_\ell \propto T_\ell^{1/2-\delta}$), um die Exploration-Last gegen die Notwendigkeit einer feineren Diskretisierung abzuwägen, um Stabilität zu gewährleisten.

Wesentliche Beiträge

1. Neuartige Formulierung: Die Arbeit stellt die erste Integration von Warteschlangenstabilität mit Continuum-Armed-Bandits vor und adressiert dabei die Herausforderung, dass kein fester endlicher Satz an Armen die Stabilität ohne Kenntnis der unbekannten Ankunfts- und Serviceverteilungen garantieren kann.
2. Algorithmus-Design für unbekanntes $\varepsilon$: Ein phasenbasierter UCB-Algorithmus wird entworft, der die Ratendiskretisierung ohne Vorabwissen über $\varepsilon$ adaptiv verfeinert.
3. Converse-Resultat: Die Autoren etablieren eine untere Schranke (Converse), die zeigt, dass es für jeden Ratenselektionsalgorithmus (unabhängig davon, ob $\varepsilon$ bekannt oder unbekannt ist) eine Umgebung gibt, in der die Worst-Case zeitliche durchschnittliche erwartete Warteschlangengröße $\Omega(1/\varepsilon^2)$ beträgt.
4. Optimalität für bekanntes $\varepsilon$: Die Arbeit beweist, dass der vorgeschlagene UCB-basierte Algorithmus auf einer festen Diskretisierung eine zeitliche durchschnittliche erwartete Warteschlangengröße von $O(\log(1/\varepsilon)/\varepsilon^2)$ erreicht. Dies entspricht der Converse-Unterschrankung bis auf logarithmische Faktoren und etabliert somit die Optimalität in diesem Setting.

Ergebnisse

• Unbekanntes $\varepsilon$: Der vorgeschlagene phasenbasierte Algorithmus erreicht eine zeitliche durchschnittliche erwartete Warteschlangengröße der Ordnung $O(\log^{3.5}(1/\varepsilon)/\varepsilon^3)$ über den gesamten Zeithorizont hinweg.
• Bekanntes $\varepsilon$: Der Algorithmus erreicht eine zeitliche durchschnittliche erwartete Warteschlangengröße der Ordnung $O(\log(1/\varepsilon)/\varepsilon^2)$.
• Untere Schranke: Das Converse-Resultat zeigt, dass die Warteschlangengröße im Worst-Case, unabhängig vom Algorithmus, nicht besser als $\Omega(1/\varepsilon^2)$ sein kann.

Bedeutung und Behauptungen
Die Arbeit beansprucht, die erste zu sein, die Warteschlangenstabilität mit Continuum-Armed-Bandits integriert, motiviert durch praktische Anwendungen wie die Ratenselektion in IEEE 802.11-Systemen, bei denen der Aktionsraum für Finite-Armed-Formulierungen zu groß ist.

Die Autoren weisen auf eine Lücke zwischen der oberen Schranke ($O(\varepsilon^{-3})$) und der unteren Schranke ($O(\varepsilon^{-2})$) im Fall von unbekanntem $\varepsilon$ hin. Sie vermuten, dass ein Algorithmus, der $O(\log^\alpha(1/\varepsilon)/\varepsilon^2)$ erreicht, auch bei unbekanntem $\varepsilon$ möglich ist, was diese Lücke schließen würde. Die Arbeit stellt explizit fest, dass das Design eines solchen Algorithmus als zukünftige Arbeit offenbleibt. Zudem schlagen die Autoren vor, den Rahmen der Continuum-Armed-Warteschlangen auf Multi-Queue- oder Netzwerk-Settings zu erweitern, als weiteren zukünftigen Forschungsrichtung.

Die Arbeit liefert eine theoretische Grundlage für die Ratenselektion unter teilweiser Rückmeldung und zeigt auf, dass während das Wissen über den System-Slack $\varepsilon$ eine nahezu optimale Leistung ermöglicht, das Lernen ohne dieses Wissen eine polynomielle Strafe in Form der Warteschlangengrößen-Schranke nach sich zieht.