Bandit-Based Rate Adaptation for a Single-Server Queue

Resumen Técnico: Adaptación de Tasa Basada en Bandidos para una Cola de Servidor Único

Formulación del Problema
Este artículo aborda el problema de la adaptación de la tasa en un sistema de colas de servidor único que opera en intervalos de tiempo discretos con retroalimentación parcial. En cada intervalo $t$, un transmisor selecciona una tasa de transmisión $V(t)$ de un intervalo continuo $[0, 1]$. La capacidad del canal $C(t)$ y el proceso de llegada $A(t)$ son muestras independientes e idénticamente distribuidas (i.i.d.) de distribuciones fijas pero desconocidas. La transmisión tiene éxito si y solo si $V(t) \leq C(t)$; de lo contrario, falla. El transmisor recibe únicamente retroalimentación binaria (ACK/NACK) que indica éxito o fracaso. El objetivo es diseñar un algoritmo de selección de tasa que garantice un tamaño de cola esperado promedio en el tiempo uniformemente acotado, siempre que la tasa de llegada $\lambda$ se encuentre estrictamente dentro de la región de capacidad del sistema. El "margen" (slack) entre la tasa de llegada y la tasa de servicio máxima alcanzable se denota como $\varepsilon > 0$.

Los autores distinguen entre dos escenarios:

1. $\varepsilon$ conocido: El transmisor tiene conocimiento previo sobre el límite inferior de la brecha entre la tasa de llegada y la región de capacidad.
2. $\varepsilon$ desconocido: El transmisor no conoce $\varepsilon$ y debe aprender la dinámica del sistema sin este parámetro.

Metodología
El artículo integra la teoría de colas con los bandidos de brazos continuos (continuum-armed bandits). A diferencia de los bandidos de colas estándar que operan sobre espacios de acción finitos, este trabajo maneja un espacio de tasas infinito e incontable.

• Para $\varepsilon$ conocido: Los autores proponen una estrategia de discretización donde el espacio de tasas continuo $[0, 1]$ se mapea a una rejilla finita de tamaño $d = \lceil \gamma/\varepsilon \rceil$. Esto transforma el problema en un problema de bandido de brazos finitos. Los autores aplican el algoritmo clásico de Límite de Confianza Superior (UCB1) a este conjunto discretizado. Realizan un riguroso análisis de dos etapas: una etapa de aprendizaje para identificar la tasa discretizada óptima y una etapa de control utilizando el análisis de deriva de Lyapunov para acotar el tamaño de la cola una vez que la tasa es suficientemente cercana a la óptima.

• Para $\varepsilon$ desconocido: Los autores proponen un algoritmo por fases que refina iterativamente la discretización de la tasa. El algoritmo opera en fases $\ell = 1, 2, \dots$. En cada fase $\ell$, el espacio de tasas se discretiza en $d_\ell$ niveles, donde $d_\ell$ crece como una función de la longitud de la fase $T_\ell$. Dentro de cada fase, se ejecuta una adaptación de UCB1 sobre la discretización actual. Las secuencias $\{T_\ell\}$ y $\{d_\ell\}$ se eligen cuidadosamente (específicamente, $T_\ell = 2^{\ell+2}$ y $d_\ell \propto T_\ell^{1/2-\delta}$) para equilibrar la carga de exploración con la necesidad de una discretización más fina para asegurar la estabilidad.

Contribuciones Clave

1. Formulación Novedosa: El artículo introduce la primera integración de la estabilidad de colas con los bandidos de brazos continuos, abordando el desafío de que ningún conjunto finito fijo de brazos puede garantizar la estabilidad sin el conocimiento de las distribuciones de llegada y servicio desconocidas.
2. Diseño de Algoritmo para $\varepsilon$ desconocido: Se diseña un algoritmo UCB por fases que refina adaptativamente la discretización de la tasa sin conocimiento previo de $\varepsilon$.
3. Resultado de la Conversa (Converse Result): Los autores establecen un límite inferior (conversa) que demuestra que para cualquier algoritmo de selección de tasa (ya sea que $\varepsilon$ sea conocido o desconocido), existe un entorno donde el tamaño de cola esperado promedio en el peor de los casos es $\Omega(1/\varepsilon^2)$.
4. Optimidad para $\varepsilon$ conocido: El artículo demuestra que cuando $\varepsilon$ es conocido, el algoritmo propuesto basado en UCB sobre una discretización fija logra un tamaño de cola esperado promedio de $O(\log(1/\varepsilon)/\varepsilon^2)$. Esto coincide con el límite inferior de la conversa hasta factores logarítmicos, estableciendo la optimalidad en este escenario.

Resultos

• $\varepsilon$ desconocido: El algoritmo por fases propuesto logra un tamaño de cola esperado promedio de orden $O(\log^{3.5}(1/\varepsilon)/\varepsilon^3)$ uniformemente sobre el horizonte de tiempo.
• $\varepsilon$ conocido: El algoritmo logra un tamaño de cola esperado promedio de orden $O(\log(1/\varepsilon)/\varepsilon^2)$.
• Límite Inferior: El resultado de la conversa demuestra que el tamaño de la cola no puede ser mejor que $\Omega(1/\varepsilon^2)$ en el peor de los casos, independientemente del conocimiento de $\varepsilon$ por parte del algoritmo.

Significancia y Reivindicaciones
El artículo afirma ser el primero en integrar la estabilidad de colas con los bandidos de brazos continuos, motivado por aplicaciones prácticas como la selección de tasa en sistemas IEEE 802.11 donde el espacio de acción es demasiado grande para las formulaciones de brazos finitos.

Los autores destacan una brecha entre el límite superior ($O(\varepsilon^{-3})$) y el límite inferior ($O(\varepsilon^{-2})$) en el escenario de $\varepsilon$ desconocido. Conjeturan que es posible un algoritmo que logre $O(\log^\alpha(1/\varepsilon)/\varepsilon^2)$ cuando $\varepsilon$ es desconocido, lo que cerraría esta brecha. El artículo establece explícitamente que el diseño de tal algoritmo queda como trabajo futuro. Además, los autores sugieren extender el marco de colas de brazos continuos a entornos de múltiples colas o redes como otra dirección futura.

El trabajo proporciona una base teórica para la adaptación de la tasa bajo retroalimentación parcial, demostrando que mientras el conocimiento del margen del sistema $\varepsilon$ permite un rendimiento cercano al óptimo, el aprendizaje sin este conocimiento conlleva una penalización polinómica en el límite del tamaño de la cola.