Resumo Técnico: Sondagem e Escalonamento Conjuntos de AP via Bandidos Contextuais

Definição do Problema

O artigo aborda o desafio de alocar eficientemente recursos sem fio em um cenário onde um conjunto de Pontos de Acesso (APs) serve cooperativamente um único cliente móvel. A dificuldade central reside na incerteza das taxas de dados: a capacidade de cada link segue uma distribuição desconhecida que varia com base na localização do cliente e em fatores ambientais (ex: bloqueios, interferência).

Ao contrário dos problemas tradicionais de escalonamento de links, onde o tomador de decisão deve escolher um link sem observação prévia, este trabalho assume um cenário de sondagem e execução conjunta (joint probing and play). Em cada passo de tempo, o tomador de decisão pode sondar um subconjunto limitado de $K$ APs (onde $K < N$, e $N$ é o número total de APs) para observar suas recompensas instantâneas (taxas de dados) antes de selecionar um único AP para servir o cliente. O objetivo é maximizar a recompensa esperada cumulativa ao longo de um horizonte de tempo $T$ ao aprender uma política ótima que equilibra exploração (sondar para aprender distribuições) e explotação (servir o cliente).

Os autores modelam isso como um problema de Bandido Contextual com Sondagem (CBwP - Contextual Bandit with Probing). O "contexto" é a localização do cliente, e os "braços" são os APs. A distribuição de recompensa $\Phi(a|x)$ para o braço $a$ dado o contexto $x$ é desconhecida.

Metodologia

1. Estrutura Ótima Offline (Formulação MDP)

Antes de abordar o problema de aprendizado online, os autores analisam o cenário offline onde as distribuições de recompensa são conhecidas. Eles modelam a decisão conjunta de sondagem e execução em cada passo de tempo como um Processo de Decisão de Markov (MDP).

• Estado: O histórico de braços sondados e suas recompensas observadas.
• Política de Execução Ótima: Eles provam que, para qualquer histórico de sondagem, a estratégia ótima é determinística: executar o braço com a maior recompensa observada entre os braços sondados, ou o braço com a maior recompensa esperada entre os não sondados.
• Política de Sondagem Ótima: Para o caso específico de recompensas de Bernoulli (onde a recompensa é 1 com probabilidade $\mu(a|x)$ e 0 caso contrário), eles derivam uma política ótima não adaptativa simples: sondar os $K$ braços com as maiores recompensas esperadas $\mu(a|x)$ e, se nenhum deles resultar em uma recompensa de 1, executar o $(K+1)$-ésimo melhor braço.

2. Algoritmo de Aprendizado Online: Zooming Contextual

Para lidar com o cenário online com distribuições desconhecidas, os autores estendem o algoritmo de Zooming Contextual (originalmente proposto para bandidos contextuais padrão) para o framework CBwP.

• Particionamento do Espaço: O algoritmo mantém um conjunto de "bolas ativas" (regiões no espaço de contexto) para cada AP. Inicialmente, todo o espaço é coberto por uma única bola de raio 1.
• Cálculo de Índice: Para cada bola $B$, o algoritmo calcula um índice $I_t(B)$ que combina a recompensa média observada, o raio da bola e um termo de confiança (estilo Upper Confidence Bound).
• Processo de Decisão de Três Fases por Rodada:
  1. Regra de Sondagem: O algoritmo seleciona até $K$ braços para sondar. Ele escolhe o braço não sondado associado à bola ativa que contém o contexto atual $x_t$ que possui o maior índice. A sondagem para antecipadamente se um braço render uma recompensa de 1 (para Bernoulli) ou após $K$ sondagens.
  2. Regra de Execução: Após a sondagem, o algoritmo seleciona um braço para executar. Se um braço sondado rendeu uma recompensa de 1, ele é executado. Caso contrário, o algoritmo executa o braço com o valor estimado mais alto (seja a recompensa observada se sondado, ou o índice se não sondado).
  3. Regra de Ativação: Se um braço é sondado ou executado, o algoritmo atualiza as estatísticas. Se o raio de confiança da bola atual for menor que o raio físico da bola, a bola é "zoomada" (zoomed in) através da ativação de uma nova bola filha com metade do raio centrada no contexto atual.

3. Análise de Regret

Os autores estabelecem um limite teórico de regret para o algoritmo sob a suposição de recompensas de Bernoulli. Eles definem "rodadas limpas" (clean runs) onde as recompensas estimadas estão próximas das médias reais (dentro de um intervalo de confiança). Ao limitar a probabilidade de "rodadas ruins" e analisar o regret durante as rodadas limpas usando a continuidade Lipschitz da função de recompensa em relação à distância do contexto, eles derivam um limite de regret sublinear que depende do número de cobertura do espaço de contexto e do limite de sondagem $K$.

Principais Contribuições

1. Novo Framework (CBwP): O artigo introduz os Bandidos Contextuais com Sondagem, uma nova extensão do modelo clássico de bandidos contextuais que incorpora explicitamente uma fase de "sondagem" antes da fase de "execução". Isso modela restrições do mundo real onde o sounding de canal limitado (ex: beamforming) é possível antes da transmissão.
2. Insights Estruturais: Os autores fornecem propriedades estruturais da solução ótima offline, demonstrando que, para recompensas de Bernoulli, uma estratégia de sondagem gulosa não adaptativa é ótima.
3. Design de Algoritmo: Eles propõem um algoritmo de aprendizado online eficiente que adapta a técnica de contextual zooming para o cenário conjunto de sondagem/execução, lidando com o compromisso entre o custo de sondagem e o ganho de informação.
4. Garantias Teóricas: Um limite formal de regret é estabelecido para o algoritmo proposto no caso de recompensas de Bernoulli.
5. Validação Empírica: A solução é avaliada usando traços de canal reais de um ambiente de teste 802.11ad e um simulador de canal mmWave.

Resultados Experimentais

A avaliação foi conduzida em um cenário de "Student Hall" usando roteadores e laptops 802.11ad, simulando clientes móveis movendo-se pelo ambiente.

• Baselines: O algoritmo CBwP proposto foi comparado contra quatro baselines: Sondagem Aleatória/Execução Aleatória (RR), Sondagem Aleatória/Execução Gulosa com Exploração (RG), Sondagem Aleatória/Execução Gulosa sem Exploração (RG2) e Sondagem Gulosa/Execução sem Exploração (GNE).
• Desempenho:
  • Regret: O CB-WP alcançou consistentemente um regret cumulativo menor do que todos os baselines. Enquanto os baselines mostraram um regret mais alto que aumentava com o número de APs, o CBWP permaneceu estável.
  • Limite de Sondagem ($K$): Aumentar $K$ (o número de sondagens permitidas) reduziu o regret para todos os algoritmos, mas o CBWP manteve uma vantagem significativa independentemente de $K$.
  • Escalabilidade: Conforme o número de APs ($N$) aumentava, o desempenho dos baselines degradava, enquanto o CBWP demonstrou robustez.
  • Ambientes Dinâmicos: O algoritmo conseguiu se adaptar com sucesso a novos clientes entrando em áreas anteriormente inexploradas da sala, mostrando convergência rápida para baixo regret.

Significância e Alegações

O artigo afirma que o modelo CBwP é uma extensão inovadora do framework clássico de bandidos contextuais. Sua principal significância reside na capacidade de modelar e resolver problemas de tomada de decisão sequencial onde um tomador de decisão pode adquirir informações parciais (via sondagem) antes de agir, sob incerteza.

Os autores asseguram que este framework é diretamente aplicável ao beamforming e escalonamento conjuntos em WLANs mmWave de próxima geração (802.11ad/ay), onde o beamforming total é muito custoso, mas a sondagem limitada é viável. Além disso, sugerem que o modelo tem aplicabilidade mais ampla a outros domínios envolvendo sondagem e execução conjuntos, como:

• Bandidos Multi-Braços Combinatórios: Para configurações multi-AP e multi-cliente.
• Busca de Caminhos em Redes Rodoviárias: Onde um buscador pode consultar um servidor para obter dicas limitadas de tráfego antes de escolher um caminho, equilibrando custos de consulta com latência de viagem.

O trabalho enfatiza que, embora a sondagem reduza a incerteza, ela não a elimina inteiramente; portanto, a integração da exploração tanto nas fases de sondagem quanto de execução proposta pelo algoritmo é crucial para alcançar o desempenho ideal.