Learning from Local Walks on Dynamic Graphs with Bandit Feedback

Resumen Técnico: Aprendizaje mediante Caminatas Locales en Grafos Dinámicos con Retroalimentación de Bandidos

Formulación del Problema
Este artículo aborda el problema del bandido de múltiples brazos estocásticos (MAB, por sus siglas en inglés) en un entorno donde el aprendiz está limitado a un movimiento local en un grafo dinámico. A diferencia de los modelos clásicos de MAB donde cualquier brazo está disponible en cada ronda, o de los modelos de retroalimentación de grafo donde se dispone de observaciones laterales, aquí el aprendiz solo puede seleccionar su nodo actual o un vecino inmediato basado en la conectividad del grafo en ese instante de tiempo específico.

• Entorno: Los brazos corresponden a los vértices $A = \{1, \dots, n\}$ de un grafo no dirigido variante en el tiempo $G_t = (A, E_t)$.
• Restricciones: En la ronda $t$, el aprendiz observa únicamente la vecindad local $L_t(a_{t-1})$ y debe elegir $a_t \in L_t(a_{t-1})$. El proceso del grafo es agnóstico a las acciones del aprendiz (oblivious).
• Desafío Central: Este entorno desacopla la identificación del mejor brazo de la explotación. En los bandidos clásicos, identificar el brazo óptimo $a^\star$ permite la explotación inmediata. En este entorno dinámico, incluso después de haber identificado $a^\star$, el aprendiz puede estar estructuralmente aislado de este debido a la topología evolutiva. La capacidad de aprendizaje requiere que el entorno proporcione consistentemente vías navegables, no basta con que la unión de todos los grafos a lo largo del horizonte esté conectada.

Metodología y Condiciones Estructurales
Los autores adoptan un marco de exploración-luego-compromiso (explore-then-commit), separando el problema en exploración (recolección de muestras) y navegación (llegar al objetivo identificado). Para asegurar la capacidad de aprendizaje, introducen una condición estructural agnóstica al proceso basada en la caminata canónica (una caminata aleatoria simple donde el aprendiz se queda o se mueve uniformemente hacia un vecino).

• Mezcla de Ventana Deslizante con Distribución Estacionaria Común (Definición 1): El artículo rechaza las condiciones de conectividad de todo el horizonte (por ejemplo, que la unión de todos los grafos esté conectada) por ser insuficientes, ya que no garantizan la alcanzabilidad en tiempos de parada arbitrarios. En su lugar, imponen una condición sobre la caminata aleatoria inducida:
  1. Distribución Estacionaria Común: Cada instantánea del grafo $G_t$ induce un núcleo reversible $U_t$ con una distribución estacionaria común $\pi$ (por ejemplo, lograda mediante secuencias de grados fijos).
  2. Mezcla de Ventana Deslizante: En cada ventana de tiempo de longitud $W$, al menos una fracción $\rho$ de las rondas debe tener un salto espectral $\ge \gamma$.
     Esta condición asegura que la caminata se mezcle hacia $\pi$ de manera uniforme a lo largo del tiempo, evitando que el aprendiz quede atrapado en subgrafos locales indefinidamente, independientemente de cuándo termine la exploración.

Algoritmos
El artículo analiza una familia de algoritmos que operan bajo este régimen:

1. LEX (Exploración Perezosa de Presupuesto Fijo): Utiliza la caminata canónica para la exploración durante un presupuesto fijo $T_{exp}$ determinado por los parámetros de mezcla y las brechas de recompensa. Se compromete con el líder empírico y navega utilizando la caminata canónica si el objetivo no es inmediatamente alcanzable.
2. CB-LEX (Parada Basada en Confianza): Reemplaza el presupuesto fijo con una regla de parada dependiente de los datos. Termina cuando el Límite Inferior de Confianza (LCB) del líder empírico domina a los Límites Superiores de Confianza (UCBs) de todos los demás brazos (no solo al segundo mejor), asegurando robustez contra el muestreo desigual.
3. RALEX (Exploración Consciente de la Recompensa): Introduce un núcleo sesgado por la recompensa que mezcla la caminata canónica con una propuesta optimista (softmax sobre las recompensas estimadas). Crucialmente, mantiene un "suelo canónico" ($\epsilon_0$) para asegurar que las propiedades de mezcla estructural de la caminata canónica se preserven, garantizando la seguridad en el peor de los casos.

Resultos Clave y Límites de Regret
Bajo la condición de mezcla $(W, \rho, \gamma, \pi)$, los autores establecen un regret esperado sublineal ($o(T)$) para todos los algoritmos propuestos. Los límites de regret se descomponen en dos componentes distintos:

1. Regret de Aprendizaje: Escala con la dificultad estadística (inversas de las brechas $\Delta^{-2}$) y la sobrecarga de mezcla ($\tau_0$), representando el costo de identificar el mejor brazo.
2. Regret de Navegación: Un costo estructural independiente del horizonte $T$, que representa el tiempo esperado para alcanzar el brazo óptimo identificado desde el punto de parada.

• LEX/CB-LEX: Logran un regret de orden $O(\tau_0 \cdot \Psi \cdot \log T)$, donde $\Psi$ captura la complejidad de las brechas y las masas estacionarias.
• RALEX: Demuestra que el sesgo consciente de la recompensa es compatible con un regret sublineal. Aunque el límite del peor caso es conservador (debido al suelo canónico), el artículo proporciona un teorema separado (Teorema 4) que muestra que si el sesgo consciente de la recompensa logra aumentar la probabilidad de visita de los brazos "cerca de cuellos de botella", se obtiene una mejora de rendimiento demostrable (mejora multiplicativa en el término de aprendizaje).

Significancia y Reivindicaciones
El artículo se posiciona como una caracterización estructural de la capacidad de aprendizaje para bandidos con restricciones locales en grafos dinámicos, más que como una propuesta de minimización de regret casi óptimo para familias de grafos específicas (como los grafos completos).

• Invariancia de Desplazamiento: La contribución principal es la condición de mezcla de ventana deslizante e invariante al desplazamiento. Esto asegura que las suposiciones estructurales requeridas para la navegación se mantengan después del tiempo de parada aleatorio de la exploración, un requisito que las condiciones de todo el horizonte no logran cumplir.
• Desacoplamiento: El trabajo separa explícitamente el costo estadístico del aprendizaje del costo estructural de la navegación, proporcionando un marco teórico limpio para entornos dinámicos.
• Agnosticismo de Proceso: A diferencia de trabajos previos que dependen de procesos de grafos específicos (por ejemplo, Erdős–Rényi i.i.d. o Markoviano de aristas), este artículo proporciona un teorema que se sostiene para cualquier secuencia de grafos que satisfaga la condición de mezcla centrada en la caminata, cubriendo procesos naturales como los recubrimientos regulares rotatorios y las reconfiguraciones que preservan el grado.
• Seguridad vs. Ganancia: El análisis de RALEX distingue entre un "teorema de seguridad" (que garantiza un regret sublineal con cualquier parámetro de sesgo) y un "teorema de ganancia" (que certifica la mejora del rendimiento bajo condiciones específicas sobre la propuesta consciente de la recompensa).

Los autores concluyen que su trabajo establece un "régimen positivo" donde la caminata canónica intrínseca es suficiente para el aprendizaje, ofreciendo una base para futuras extensiones a núcleos más complejos como las caminatas de tipo Metropolis.