Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Resumo Técnico: Bandits Contextuais para Dispositivos com Recursos Limitados usando Aprendizado Probabilístico

Declaração do Problema
Os bandits contextuais (CB) são fundamentais para a tomada de decisão sequencial online em serviços adaptativos, como recomendações personalizadas e computação de borda. No entanto, implantar agentes CB diretamente em dispositivos com recursos limitados (por exemplo, móveis, wearables, dispositivos aéreos) apresenta desafios significativos. Algoritmos lineares CB padrão, embora eficazes, exigem a manutenção de matrizes de covariância que escalam quadraticamente com a dimensionalidade do contexto (memória $O(Nd^2)$) e envolvem operações de álgebra linear computacionalmente caras (complexidade $O(d^3)$), tornando-os inadequados para dispositivos com restrições estritas de memória, computação e energia.

Trabalhos recentes introduziram Bandits Contextuais Hiperdimensionais (HD-CB), que aproveitam a Computação Hiperdimensional (HDC) para resolver problemas de CB em espaços de alta dimensionalidade usando operações vetoriais leves. Embora o HD-CB ofereça complexidade de tempo linear e escalabilidade aprimorada, sua implementação padrão depende de atualizações baseadas em acumulação, onde os componentes do vetor de ação crescem indefinidamente. Isso exige tipos numéricos de alta precisão (por exemplo, floats de 32 bits) para evitar overflow, anulando os ganhos de eficiência de memória. Uma variante de baixa precisão anterior, HD-CBBIN, abordou o overflow binarizando vetores periodicamente e redefinindo contadores. No entanto, essa binarização determinística descarta informações de magnitude acumulada, levando à degradação do desempenho, particularmente em regimes ruidosos ou com escassez de dados.

Metodologia: HD-CB Probabilístico (HD-CBPROB)
Este artigo propõe o HD-CBPROB, uma variante de baixa precisão do HD-CB que substitui a acumulação determinística por uma regra de atualização probabilística. A inovação central é limitar a aprendizagem por design, em vez de através de redefinições periódicas.

1. Componentes Inteiros Limitados: Em vez de permitir que os componentes do vetor cresçam indefinidamente, o HD-CBPROB restringe cada componente a um intervalo inteiro pré-definido $[-\kappa, +\kappa]$. Isso permite o uso de contadores inteiros saturados de baixa precisão (por exemplo, 2, 3 ou 4 bits).
2. Regra de Atualização Probabilística: Para permitir a aprendizagem dentro desses limites apertados sem perder informações, o algoritmo substitui a atualização baseada em magnitude por uma atualização baseada em frequência. Em cada passo de tempo $t$, apenas um subconjunto aleatório de componentes do vetor é atualizado com base em uma probabilidade de decaimento temporal $\alpha_t$.
   • A probabilidade de atualização é definida como $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$.
   • Para cada componente $i$, um valor aleatório $m_{t,i} \sim U(0, 1)$ é amostrado. Uma atualização ocorre apenas se $m_{t,i} \leq \alpha_t$.
   • Quando uma atualização ocorre, o componente é incrementado ou decrementado em $\pm 1$ (com base na vinculação dos hipervetores de contexto e recompensa) e depois limitado ao intervalo $[-\kappa, +\kappa]$.
3. Mecanismo: Essa abordagem implementa efetivamente uma "caminhada aleatória saturada". Ao controlar a frequência das atualizações em vez da magnitude dos valores armazenados, o agente retém informações históricas com alta fidelidade, mesmo em componentes de baixa precisão. Isso elimina a necessidade de contadores auxiliares e etapas de binarização periódica exigidas pelo HD-CBBIN.

Principais Contribuições

• Inovação Algorítmica: Introdução de uma regra de atualização probabilística para HD-CB que permite o uso de componentes inteiros saturados de baixa precisão sem perda periódica de informações.
• Eficiência de Recursos: O método reduz a pegada de memória ao eliminar a necessidade de contadores auxiliares e cópias binarizadas separadas de vetores exigidas por variantes anteriores de baixa precisão. Também reduz o custo computacional, pois o número esperado de atualizações diminui ao longo do tempo devido à probabilidade de decaimento $\alpha_t$.
• Preservação de Desempenho: A abordagem mantém a qualidade de classificação das ações preservando informações de magnitude através da frequência de atualização, evitando a degradação associada à binarização rígida.

Resultados Experimentais
Os autores avaliaram o HD-CBPROB usando avaliação off-policy em benchmarks sintéticos padronizados de CB via o Open Bandit Pipeline (OBP), comparando-o com:

1. LinEPS: CB linear padrão (linha de base).
2. HD-CBREAL: HD-CB de valor real.
3. HD-CBBIN: HD-CB binarizado com redefinições periódicas.
4. HD-CBPROB: A variante probabilística proposta.

As principais descobertas incluem:

• Superioridade sobre Variantes Binarizadas: O HD-CBPROB supera consistentemente o HD-CBBIN em níveis de precisão iguais em todas as configurações testadas (variando a dimensionalidade do contexto $d$ e o número de ações $N$). Especificamente, uma implementação HD-CBPROB de 3 bits melhorou as recompensas cumulativas em aproximadamente 5,8% em relação a uma implementação HD-CBBIN de 3 bits.
• Aproximação do Desempenho de Valor Real: Uma configuração HD-CBPROB de 3 bits (com limite de saturação $\kappa=3$) alcançou desempenho aproximando-se da linha de base HD-CBREAL de valor real, com uma lacuna média de apenas 2,5%.
• Retornos Decrescentes na Precisão: O aumento da precisão de 3 para 4 bits rendeu retornos decrescentes ou ligeiramente negativos para o HD-CBPROB, sugerindo que 3 bits são suficientes para capturar a qualidade das ações nessas configurações sintéticas.
• Eficiência de Memória: O HD-CBPROB requer estritamente menos memória que o HD-CBBIN na mesma largura de bits, pois não exige maquinaria auxiliar (contadores e cópias temporárias binarizadas). Diferentemente do CB linear, sua pegada de memória permanece constante em relação à dimensionalidade do contexto.

Significado e Alegações
O artigo alega que o HD-CB probabilístico resolve o trade-off entre pegada de memória e perda de informações inerente às abordagens hiperdimensionais anteriores. Ao mudar da acumulação baseada em magnitude para atualizações probabilísticas baseadas em frequência, o método permite a implantação de agentes adaptativos e autônomos em dispositivos com orçamentos apertados de energia, memória e computação. Os autores posicionam o HD-CBPROB como uma alternativa convincente para inteligência de borda, oferecendo uma maneira de alcançar desempenho de tomada de decisão quase ótimo com requisitos de recursos significativamente reduzidos em comparação tanto com algoritmos lineares padrão quanto com variantes hiperdimensionais de baixa precisão existentes.

Trabalhos futuros identificados pelos autores incluem avaliar a abordagem em conjuntos de dados de bandits registrados do mundo real, testar sob distribuições de recompensa mais complexas e obter medições diretas de latência e energia em hardware embarcado para fundamentar as alegações de implantação na borda.