Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Resumen Técnico: Bandidos Contextuales para Dispositivos con Recursos Limitados mediante Aprendizaje Probabilístico

Enunciado del Problema
Los bandidos contextuales (CB) son fundamentales para la toma de decisiones secuenciales en línea en servicios adaptativos como las recomendaciones personalizadas y la computación en el borde. Sin embargo, desplegar agentes CB directamente en dispositivos con recursos limitados (por ejemplo, móviles, wearables, dispositivos aéreos) presenta desafíos significativos. Los algoritmos CB lineales estándar, aunque efectivos, requieren mantener matrices de covarianza que escalan cuadráticamente con la dimensionalidad del contexto ($O(Nd^2)$ de memoria) e involucran operaciones de álgebra lineal computacionalmente costosas ($O(d^3)$ de complejidad), lo que los hace inadecuados para dispositivos con restricciones estrictas de memoria, cómputo y energía.

Trabajos recientes introdujeron los Bandidos Contextuales Hiperdimensionales (HD-CB), que aprovechan la Computación Hiperdimensional (HDC) para resolver problemas CB en espacios de alta dimensionalidad utilizando operaciones vectoriales ligeras. Aunque HD-CB ofrece complejidad de tiempo lineal y una mejor escalabilidad, su implementación estándar depende de actualizaciones basadas en acumulación donde los componentes del vector de acción crecen indefinidamente. Esto requiere tipos numéricos de alta precisión (por ejemplo, flotantes de 32 bits) para evitar desbordamientos, anulando las ganancias de eficiencia de memoria. Una variante de baja precisión anterior, HD-CBBIN, abordó el desbordamiento binarizando periódicamente los vectores y reiniciando los contadores. Sin embargo, esta binarización determinista descarta la información de magnitud acumulada, lo que lleva a una degradación del rendimiento, particularmente en regímenes ruidosos o con escasez de datos.

Metodología: HD-CB Probabilístico (HD-CBPROB)
Este artículo propone HD-CBPROB, una variante de baja precisión de HD-CB que reemplaza la acumulación determinista con una regla de actualización probabilística. La innovación central es acotar el aprendizaje por diseño en lugar de mediante reinicios periódicos.

1. Componentes Enteros Acotados: En lugar de permitir que los componentes del vector crezcan indefinidamente, HD-CBPROB restringe cada componente a un rango entero predefinido $[-\kappa, +\kappa]$. Esto permite el uso de contadores enteros saturados de baja precisión (por ejemplo, de 2, 3 o 4 bits).
2. Regla de Actualización Probabilística: Para permitir el aprendizaje dentro de estos límites estrictos sin perder información, el algoritmo reemplaza la actualización basada en magnitud con una actualización basada en frecuencia. En cada paso de tiempo $t$, solo un subconjunto aleatorio de componentes del vector se actualiza en función de una probabilidad de decaimiento temporal $\alpha_t$.
   • La probabilidad de actualización se define como $\alpha_t = \alpha_0 \max(0, 1 - \frac{t-1}{T})$.
   • Para cada componente $i$, se muestrea un valor aleatorio $m_{t,i} \sim U(0, 1)$. Una actualización ocurre solo si $m_{t,i} \leq \alpha_t$.
   • Cuando ocurre una actualización, el componente se incrementa o decrementa en $\pm 1$ (basado en el enlace de los hipervectores de contexto y recompensa) y luego se recorta al rango $[-\kappa, +\kappa]$.
3. Mecanismo: Este enfoque implementa efectivamente un "paseo aleatorio saturado". Al controlar la frecuencia de las actualizaciones en lugar de la magnitud de los valores almacenados, el agente retiene información histórica con alta fidelidad incluso en componentes de baja precisión. Esto elimina la necesidad de contadores auxiliares y pasos de binarización periódica requeridos por HD-CBBIN.

Contribuciones Clave

• Innovación Algorítmica: Introducción de una regla de actualización probabilística para HD-CB que permite el uso de componentes enteros saturados de baja precisión sin pérdida periódica de información.
• Eficiencia de Recursos: El método reduce la huella de memoria al eliminar la necesidad de contadores auxiliares y copias separadas binarizadas de los vectores requeridas por variantes anteriores de baja precisión. También reduce el costo computacional ya que el número esperado de actualizaciones disminuye con el tiempo debido a la probabilidad de decaimiento $\alpha_t$.
• Preservación del Rendimiento: El enfoque mantiene la calidad de clasificación de las acciones al preservar la información de magnitud a través de la frecuencia de actualización, evitando la degradación asociada con la binarización estricta.

Resultados Experimentales
Los autores evaluaron HD-CBPROB utilizando evaluación fuera de política en benchmarks sintéticos estandarizados de CB a través de la Tubería de Bandidos Abiertos (OBP), comparándolo contra:

1. LinEPS: CB lineal estándar (línea base).
2. HD-CBREAL: HD-CB de valor real.
3. HD-CBBIN: HD-CB binarizado con reinicios periódicos.
4. HD-CBPROB: La variante probabilística propuesta.

Los hallazgos clave incluyen:

• Superioridad sobre Variantes Binarizadas: HD-CBPROB supera consistentemente a HD-CBBIN en niveles de precisión iguales en todas las configuraciones probadas (variando la dimensionalidad del contexto $d$ y el número de acciones $N$). Específicamente, una implementación de HD-CBPROB de 3 bits mejoró las recompensas acumuladas en aproximadamente un 5.8% sobre una implementación de HD-CBBIN de 3 bits.
• Acercamiento al Rendimiento de Valor Real: Una configuración de HD-CBPROB de 3 bits (con umbral de saturación $\kappa=3$) logró un rendimiento que se acerca a la línea base de HD-CBREAL de valor real, con una brecha promedio de solo el 2.5%.
• Rendimientos Decrecientes en Precisión: Aumentar la precisión de 3 a 4 bits produjo rendimientos decrecientes o ligeramente negativos para HD-CBPROB, lo que sugiere que 3 bits son suficientes para capturar la calidad de las acciones en estos entornos sintéticos.
• Eficiencia de Memoria: HD-CBPROB requiere estrictamente menos memoria que HD-CBBIN al mismo ancho de bits porque no requiere maquinaria auxiliar (contadores y copias temporales binarizadas). A diferencia del CB lineal, su huella de memoria permanece constante con respecto a la dimensionalidad del contexto.

Significado y Afirmaciones
El artículo afirma que el HD-CB probabilístico resuelve la compensación entre la huella de memoria y la pérdida de información inherente a los enfoques hiperdimensionales anteriores. Al cambiar de la acumulación basada en magnitud a actualizaciones probabilísticas basadas en frecuencia, el método permite el despliegue de agentes adaptativos y autónomos en dispositivos con presupuestos estrictos de energía, memoria y cómputo. Los autores posicionan a HD-CBPROB como una alternativa convincente para la inteligencia en el borde, ofreciendo una forma de lograr un rendimiento de toma de decisiones casi óptimo con requisitos de recursos significativamente reducidos en comparación tanto con los algoritmos lineales estándar como con las variantes hiperdimensionales de baja precisión existentes.

El trabajo futuro identificado por los autores incluye evaluar el enfoque en conjuntos de datos de bandidos registrados del mundo real, probar bajo distribuciones de recompensa más complejas y obtener mediciones directas de latencia y energía en hardware embebido para sustentar las afirmaciones de despliegue en el borde.