Bandit-Based Rate Adaptation for a Single-Server Queue

Technische Samenvatting: Bandit-gebaseerde Snelheidsadaptatie voor een Single-Server Queue

Probleemformulering
Dit artikel behandelt het probleem van snelheidsadaptatie in een single-server wachtrijensysteem dat opereert in discrete tijdslots met gedeeltelijke feedback. In elk slot $t$ selecteert een zender een transmissiesnelheid $V(t)$ uit een continu interval $[0, 1]$. De kanaalcapaciteit $C(t)$ en het aankomstproces $A(t)$ zijn onafhankelijke en identiek verdeelde (i.i.d.) trekkingen uit vaste maar onbekende distributies. Transmissie slaagt alleen als $V(t) \leq C(t)$; anders faalt deze. De zender ontvangt alleen binaire feedback (ACK/NACK) die succes of falen aangeeft. Het doel is om een algoritme voor snelheidsselectie te ontwerpen dat een uniform begrensde tijdgemiddelde verwachte wachtrijgrootte garandeert, mits de aankomstsnelheid $\lambda$ strikt binnen de capaciteitsregio van het systeem ligt. De "slack" tussen de aankomstsnelheid en de maximale bereikbare servicestrate wordt aangeduid als $\varepsilon > 0$.

De auteurs maken onderscheid tussen twee scenario's:

1. Bekende $\varepsilon$: De zender heeft vooraf kennis van de ondergrens op de kloof tussen de aankomstsnelheid en de capaciteitsregio.
2. Onbekende $\varepsilon$: De zender heeft geen kennis van $\varepsilon$ en moet de systeemdynamiek leren zonder deze parameter.

Methodologie
Het artikel integreert wachtrijtheorie met continuum-armed bandit learning. In tegenstelling tot standaard queueing bandits die opereren op eindige actieruimtes, behandelt dit werk een onaftelbare oneindige snelheidsruimte.

• Voor Bekende $\varepsilon$: De auteurs stellen een discretisatiestrategie voor waarbij de continue snelheidsruimte $[0, 1]$ wordt in kaart gebracht naar een eindig rooster van grootte $d = \lceil \gamma/\varepsilon \rceil$. Dit transformeert het probleem naar een eindig-armen banditprobleem. De auteurs passen het klassieke Upper Confidence Bound (UCB1) algoritme toe op deze gediscretiseerde verzameling. Zij voeren een rigoureuze twee-fasen analyse uit: een leerfase om de optimale gediscretiseerde snelheid te identificeren en een controlefase met behulp van Lyapunov drift-analyse om de wachtrijgrootte te begrenzen zodra de snelheid voldoende dicht bij de optimale waarde ligt.

• Voor Onbekende $\varepsilon$: De auteurs stellen een gefaseerd algoritme voor dat de discretisatie van de snelheidsruimte iteratief verfijnt. Het algoritme werkt in fasen $\ell = 1, 2, \dots$. In elke fase $\ell$ wordt de snelheidsruimte gediscretiseerd in $d_\ell$ niveaus, waarbij $d_\ell$ groeit als een functie van de faselengte $T_\ell$. Binnen elke fase draait een UCB1-adaptatie op de huidige discretisatie. De sequenties $\{T_\ell\}$ en $\{d_\ell\}$ zijn zorgvuldig gekozen (specifiek, $T_\ell = 2^{\ell+2}$ en $d_\ell \propto T_\ell^{1/2-\delta}$) om de exploratielast af te wegen tegen de noodzaak van fijnere discretisatie om stabiliteit te waarborgen.

Belangrijkste Bijdragen

1. Nieuwe Formulering: Het artikel introduceert de eerste integratie van wachtrijstabiliteit met continuum-armed bandits, waarbij het probleem wordt aangepakt dat geen enkele vaste eindige verzameling armen stabiliteit kan garanderen zonder kennis van de onbekende aankomst- en servicedistributies.
2. Algoritmeontwerp voor Onbekende $\varepsilon$: Een gefaseerd UCB-algoritme is ontworpen dat de snelheidsdiscretisatie adaptief verfijnt zonder voorafgaande kennis van $\varepsilon$.
3. Converse Resultaat: De auteurs stellen een ondergrens (converse) vast die aantoont dat voor elk snelheidsselectie-algoritme (of $\varepsilon$ nu bekend is of niet), er een omgeving bestaat waarin de slechtste gemiddelde tijdverwachte wachtrijgrootte $\Omega(1/\varepsilon^2)$ is.
4. Optimaliteit voor Bekende $\varepsilon$: Het artikel bewijst dat wanneer $\varepsilon$ bekend is, het voorgestelde UCB-gebaseerde algoritme op een vaste discretisatie een tijdgemiddelde verwachte wachtrijgrootte van $O(\log(1/\varepsilon)/\varepsilon^2)$ bereikt. Dit komt overeen met de converse ondergrens tot aan de logaritmische factoren, wat de optimaliteit in deze setting vaststelt.

Resultaten

• Onbekende $\varepsilon$: Het voorgestelde gefaseerde algoritme bereikt een tijdgemiddelde verwachte wachtrijgrootte van de orde $O(\log^{3.5}(1/\varepsilon)/\varepsilon^3)$ uniform over de tijdhorizon.
• Bekende $\varepsilon$: Het algoritme bereikt een tijdgemiddelde verwachte wachtrijgrootte van de orde $O(\log(1/\varepsilon)/\varepsilon^2)$.
• Ondergrens: Het converse resultaat toont aan dat de wachtrijgrootte niet beter kan zijn dan $\Omega(1/\varepsilon^2)$ in het slechtste geval, ongeacht de kennis van de algoritmen over $\varepsilon$.

Betekenis en Claims
Het artikel claimt de eerste te zijn die wachtrijstabiliteit integreert met continuum-armed bandits, gemotiveerd door praktische toepassingen zoals snelheidsselectie in IEEE 802.11-systemen waar de actieruimte te groot is voor eindig-armen formuleringen.

De auteurs benadrukken een gat tussen de bovengrens ($O(\varepsilon^{-3})$) en de ondergrens ($O(\varepsilon^{-2})$) in de setting met onbekende $\varepsilon$. Zij vermoeden dat een algoritme dat $O(\log^\alpha(1/\varepsilon)/\varepsilon^2)$ bereikt mogelijk is wanneer $\varepsilon$ onbekend is, wat dit gat zou kunnen dichten. Het artikel stelt expliciet dat het ontwerpen van een dergelijk algoritme als toekomstig werk wordt achtergelaten. Daarnaast suggereren de auteurs om het continuum-armed queueing framework uit te breiden naar multi-queue of netwerkinstellingen als een andere toekomstige richting.

Het werk biedt een theoretisch fundament voor snelheidsadaptatie onder gedeeltelijke feedback, waarbij wordt aangetoond dat hoewel kennis van de systeem-slack $\varepsilon$ bijna-optimale prestaties mogelijk maakt, het leren zonder deze kennis een polynomiale straf oplegt aan de wachtrijgrootte-binding.