Resumen Técnico: Exploración Adaptativa para Bandidos de Estado Latente

1. Formulación del Problema

El artículo aborda un problema de bandidos multi-brazo no estacionario donde las distribuciones de recompensa dependen de un estado de Markov latente (no observado) que evoluciona autónomamente a lo largo del tiempo. A diferencia de los bandidos contextuales estándar, el aprendiz no puede observar el estado $s_t$ directamente; solo observa la acción seleccionada $a_t$ y la recompensa estocástica resultante $r_t$.

El desafío central es que el brazo óptimo cambia a medida que los estados ocultos transicionan, pero el aprendiz debe inferir el estado actual basándose únicamente en el historial de acciones y recompensas. Este entorno introduce tres dificultades técnicas específicas:

1. Estimación de Recompensa Confundida: Los algoritmos estándar promedian las recompensas sobre la distribución de estados, lo que conduce a un sesgo sistemático cuando el brazo óptimo varía entre estados.
2. Atribución Temporal de Recompensas: Es difícil distinguir si un cambio en el rendimiento de la recompensa se debe al progreso del aprendizaje o a una transición en el estado oculto.
3. Información de Estado Limitada: El algoritmo no puede condicionarse directamente a las características del estado y debe depender de señales indirectas, una tarea que se vuelve más difícil a medida que el espacio de estados crece.

El objetivo es minimizar el regret dinámico contra un oráculo consciente del estado, definido como la diferencia acumulada entre la recompensa del brazo óptimo para el estado oculto actual y el brazo realmente seleccionado.

2. Metodología

Los autores proponen una familia de algoritmos que integran Contexto Retardado (Lagged Context) y Estrategias de Sondeo (Probing Strategies) en el marco de LinUCB. El enfoque evita la estimación explícita del modelo de transición de Markov latente, apoyándose en su lugar en estadísticas de baja dimensión para separar los estados.

2.1 Contexto Retardado (LC-UCB)

El primer componente, Lagged-Context UCB (LC-UCB), trata el par acción-recompensa anterior $(a_{t-1}, r_{t-1})$ como un vector de características contextuales $\phi_t$.

• Intuición: Bajo una dinámica de estado de Markov lenta, la recompensa previa proporciona información sobre el estado anterior $s_{t-1}$, el cual está altamente correlacionado con el estado actual $s_t$.
• Mecanismo: El algoritmo aprende un mapeo de $(a_{t-1}, r_{t-1})$ hacia la recompensa actual $r_t$. Esto permite al aprendiz rastrear implícitamente el estado y seleccionar el brazo óptimo para el estado reciente inferido, en lugar de un promedio sobre todos los estados.
• Limitación: LC-UCB puede fallar si múltiples estados producen recompensas similares para la misma acción (no identificabilidad), lo que genera ambigüedad en la inferencia del estado.

2.2 Sondeo para Huellas Digitales de Estado (Probing for State Fingerprints)

Para resolver la ambigüedad, los autores introducen estrategias de sondeo que generan "huellas digitales de estado": observaciones conjuntas de recompensas de múltiples brazos que identifican de forma única el estado oculto. Se proponen dos paradigmas:

1. Randomized Probing UCB (RP-UCB): Aplicable cuando se pueden asignar diferentes brazos simultáneamente a múltiples unidades experimentales (ej. usuarios). Recolecta observaciones conjuntas reales $(r_0, r_1)$ del mismo paso de tiempo.
2. Sequential Probing UCB (SP-UCB): Aplicable para entornos de unidad única. Muestrea brazos de forma consecutiva (ej. brazo 0 en $t$, brazo 1 en $t+1$) y trata el par $(r_t, r_{t+1})$ como una huella digital sintética. Esto depende del supuesto de que el estado es "pegajoso" (alta probabilidad de auto-transición) para que el estado no cambie entre los dos sondeos.

2.3 Exploración Adaptativa (AdaRP-UCB / AdaSP-UCB)

El sondeo con cronograma fijo incurre en regret incluso cuando el modelo tiene confianza. Los autores proponen variantes de Sondeo Adaptativo que refrescan las huellas digitales solo cuando es necesario, utilizando tres mecanismos de compuerta (gating):

• Compuerta de Residuo (Residual Gate): Activa un sondeo si el error de predicción (residuo studentizado) excede un umbral, indicando deriva del modelo o una transición de estado.
• Compuerta de Incertidumbre (Uncertainty Gate): Activa un sondeo si el margen entre los dos mejores puntajes UCB es pequeño, indicando alta incertidumbre en la selección de brazos.
• Compuerta de Obsolescencia/Riesgo (Staleness/Hazard Gate): Activa un sondeo si la huella digital no se ha actualizado durante un periodo definido por una función de riesgo exponencial, evitando el uso de información desactualizada.

Estas compuertas están sujetas a un intervalo mínimo entre sondeos ($\tau_{min}$) para evitar comportamientos oscilatorios.

3. Contribuciones Clave

1. Marco Algorítmico: El desarrollo de LC-UCB, RP-UCB, SP-UCB y sus variantes adaptativas (AdaRP-UCB, AdaSP-UCB) que combinan contexto retardado con sondeo coordinado para manejar bandidos de estado latente sin la estimación explíc la de la dinámica de Markov.
2. Análisis Teórico: Una descomposición del regret dinámico en tres componentes: ambigüedad de representación (error de aproximación), costo de sondeo y deriva tras la obsolescencia de una huella digital. El artículo proporciona límites que muestran cómo el sondeo adaptativo minimiza el regret al equilibrar estos factores.
3. Validación Empírica: Evaluación sistemática a través de variaciones en el número de estados ocultos ($S$), tasas de transición (probabilidad de permanencia $p_{stay}$), ruido de recompensa ($\sigma$) y horizontes temporales ($T$).

4. Resultados Experimentales

Los algoritmos fueron evaluados frente a baselines clásicos (UCB1, Thompson Sampling), métodos adversariales (EXP3) y métodos no estacionarios (Sliding Window UCB, Discounted UCB).

• Desempeño: Los métodos de sondeo adaptativo (específicamente AdaRP-UCB y AdaSP-UCB) superaron consistentemente a todos los baselines en entornos donde los resúmenes (huellas digitales) podían distinguir los estados y se actualizaban con la frecuencia suficiente.
  • AdaRP-UCB logró el menor regret en 12 de 13 configuraciones aleatorizadas, mostrando ganancias significativas en entornos volátiles.
  • AdaSP-UCB funcionó mejor en entornos de unidad única con bajo ruido, mezcla lenta o espacios de estados grandes.
• Modos de Fallo: El artículo identifica condiciones específicas donde los métodos se degradan:
  • Ruido Alto: Cuando el ruido ($\sigma$) es alto en relación con la brecha entre brazos, las huellas digitales se debilitan y los baselines no estacionarios (como D-UCB) pueden tener un mejor desempeño.
  • Separación Débil de Huellas: Si diferentes estados producen distribuciones de recompensa conjunta similares, la estrategia de sondeo no puede desambiguar los estados.
  • Cambios Rápidos: El sondeo secuencial (SP-UCB) falla cuando el estado cambia frecuentemente dentro de la ventana de sondeo (baja $p_{stay}$), invalidando la huella digital sintética.
• Estudios de Ablación: Eliminar la característica de la huella digital ($\phi_{fp}$) aumentó significamente el regret en entornos de estados pegajosos, confirmando el valor de las observaciones conjuntas. Eliminar el contexto retardado ($\phi_{lag}$) tuvo un impacto menor en algunas configuraciones aleatorizadas, sugiriendo que el tiempo adaptativo fue el principal motor de mejora en esos casos.

5. Significado y Reivindicaciones

El artículo sostiene que su contribución principal es un enfoque práctico para la no estacionariedad estructurada donde el entorno evoluciona mediante un proceso de Markov autónomo. A diferencia de los bandidos no estacionarios estándar que tratan los cambios como una deriva arbitraria, o los POMDPs que requieren observabilidad total o decodificación compleja, este enfoque utiliza resúmenes de historial ligeros y sondeos para mantener una estimación actual del brazo óptimo.

Los autores enfatizan que sus métodos son más efectivos en regímenes donde:

1. El estado latente es predecible en horizontes cortos (mezcla lenta).
2. La estrategia de sondeo puede generar estadísticas suficientes (huellas digitales) que separen los estados relevantes.
3. Los mecanismos de compuerta adaptativa pueden mantener actualizados estos resúmenes sin incurrir en un exceso de costo de sondeo.

El trabajo cierra la brecha entre los bandidos contextuales y el aprendizaje por refuerzo de estado latente al ofrecer una solución computacionalmente eficiente (basada en LinUCB) que no requiere aprender la dinámica completa de transición del estado oculto.