Bandit-Based Rate Adaptation for a Single-Server Queue

Resumo Técnico: Adaptação de Taxa Baseada em Bandidos para uma Fila de Servidor Único

Formulação do Problema
Este artigo aborda o problema da adaptação de taxa em um sistema de fila de servidor único operando em intervalos de tempo discretos com feedback parcial. Em cada intervalo $t$, um transmissor seleciona uma taxa de transmissão $V(t)$ de um intervalo contínuo $[0, 1]$. A capacidade do canal $C(t)$ e o processo de chegada $A(t)$ são amostras independentes e identicamente distribuídas (i.i.d.) de distribuições fixas, porém desconhecidas. A transmissão tem sucesso se, e somente se, $V(t) \leq C(t)$; caso contrário, falha. O transmissor recebe apenas feedback binário (ACK/NACK) indicando sucesso ou falha. O objetivo é projetar um algoritmo de seleção de taxa que garanta um tamanho de fila esperado médio no tempo uniformemente limitado, desde que a taxa de chegada $\lambda$ esteja estritamente dentro da região de capacidade do sistema. A "folga" (slack) entre a taxa de chegada e a taxa de serviço máxima alcançável é denotada por $\varepsilon > 0$.

Os autores distinguem dois cenários:

1. $\varepsilon$ Conhecido: O transmissor possui conhecimento prévio do limite inferior da lacuna entre a taxa de chegada e a região de capacidade.
2. $\varepsilon$ Desconhecido: O transmissor não conhece $\varepsilon$ e deve aprender a dinâmica do sistema sem este parâmetro.

Metodologia
O artigo integra a teoria de filas com bandidos de braços contínuos (continuum-armed bandits). Ao contrário dos bandidos de filas padrão que operam em espaços de ação finitos, este trabalho lida com um espaço de taxas infinito e não contável.

• Para $\varepsilon$ Conhecido: Os autores propõem uma estratégia de discretização onde o espaço de taxa contínuo $[0, 1]$ é mapeado para uma grade finita de tamanho $d = \lceil \gamma/\varepsilon \rceil$. Isso transforma o problema em um problema de bandido de braços finitos. Os autores aplicam o algoritmo clássico Upper Confidence Bound (UCB1) a este conjunto discretizado. Eles realizam uma análise rigorosa de dois estágios: um estágio de aprendizado para identificar a taxa discretizada ideal e um estágio de controle usando análise de deriva de Lyapunov para limitar o tamanho da fila uma vez que a taxa esteja suficientemente próxima da ideal.

• Para $\varepsilon$ Desconhecido: Os autores propõem um algoritmo em fases que refina iterativamente a discretização do espaço de taxa. O algoritmo opera em fases $\ell = 1, 2, \dots$. Em cada fase $\ell$, o espaço de taxa é discretizado em $d_\ell$ níveis, onde $d_\ell$ cresce como uma função do comprimento da fase $T_\ell$. Dentro de cada fase, uma adaptação do UCB1 é executada na discretização atual. As sequências $\{T_\ell\}$ e $\{d_\ell\}$ são cuidadosamente escolhidas (especificamente, $T_\ell = 2^{\ell+2}$ e $d_\ell \propto T_\ell^{1/2-\delta}$) para equilibrar o ônus da exploração com a necessidade de uma discretização mais fina para garantir a estabilidade.

Principais Contribuições

1. Formulação Inovadora: O artigo introduz a primeira integração da estabilidade de filas com bandidos de braços contínuos, abordando o desafio de que nenhum conjunto fixo de braços finitos pode garantir estabilidade sem o conhecimento das distribuições de chegada e serviço desconhecidas.
2. Design de Algoritmo para $\varepsilon$ Desconhecido: Um algoritmo de UCB em fases é projetado para refinar adaptativamente a discretização da taxa sem conhecimento prévio de $\varepsilon$.
3. Resultado de Converse (Converso): Os autores estabelecem um limite inferior (converse) mostrando que, para qualquer algoritmo de seleção de taxa (seja $\varepsilon$ conhecido ou desconhecido), existe um ambiente onde o tamanho médio do tempo esperado da fila é $\Omega(1/\varepsilon^2)$.
4. Otimalidade para $\varepsilon$ Conhecido: O artigo prova que, quando $\varepsilon$ é conhecido, o algoritmo proposto baseado em UCB sobre uma discretização fixa atinge um tamanho de fila esperado médio no tempo de $O(\log(1/\varepsilon)/\varepsilon^2)$. Isso coincide com o limite inferior do converso até fatores logarítmicos, estabelecendo a otimalidade neste cenário.

Resultados

• $\varepsilon$ Desconhecido: O algoritmo em fases proposto atinge um tamanho de fila esperado médio no tempo de ordem $O(\log^{3.5}(1/\varepsilon)/\varepsilon^3)$ uniformemente sobre o horizonte de tempo.
• $\varepsilon$ Conhecido: O algoritmo atinge um tamanho de fila esperado médio no tempo de ordem $O(\log(1/\varepsilon)/\varepsilon^2)$.
• Limite Inferior: O resultado do converse demonstra que o tamanho da fila não pode ser melhor do que $\Omega(1/\varepsilon^2)$ no pior caso, independentemente do conhecimento do algoritmo sobre $\varepsilon$.

Significância e Alegações
O artigo afirma ser o primeiro a integrar a estabilidade de filas com bandidos de braços contínuos, motivado por aplicações práticas como a seleção de taxa em sistemas IEEE 802.11, onde o espaço de ação é grande demais para formulações de braços finitos.

Os autores destacam uma lacuna entre o limite superior ($O(\varepsilon^{-3})$) e o limite inferior ($O(\varepsilon^{-2})$) no cenário de $\varepsilon$ desconhecido. Eles conjecturam que um algoritmo que atinja $O(\log^\alpha(1/\varepsilon)/\varepsilon^2)$ é possível quando $\varepsilon$ é desconhecido, o que fecharia essa lacuna. O artigo afirma explicitamente que o design de tal algoritmo é deixado como trabalho futuro. Além disso, os autores sugerem a extensão do framework de filas de braços contínuos para ambientes de múltiplas filas ou redes como outra direção futura.

O trabalho fornece uma base teórica para a adaptação de taxa sob feedback parcial, demonstrando que, embora o conhecimento da folga do sistema $\varepsilon$ permita um desempenho próximo ao ideal, o aprendizado sem esse conhecimento acarreta uma penalidade polinomial no limite do tamanho da fila.