Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment

Resumen Técnico: Convergencia y Arrepentimiento del Gradiente de Política para Bandidos Multibrazo en Entornos de Difusión

Planteamiento del Problema
Este artículo investiga las propiedades teóricas del algoritmo de gradiente de política (PG, por sus siglas en inglés) aplicado al problema de los Bandidos Multibrazo (MAB) dentro de un entorno de difusión continua. A diferencia de los entornos tradicionales de tiempo discreto, el entorno se modela mediante una Ecuación Diferencial Estocástica (SDE) donde la tasa de recompensa de cada brazo está sujeta a ruido continuo (movimiento browniano). Los autores se centran en el "régimen de señal débil", donde el ruido domina la señal de manera incremental, lo que hace que el aprendizaje sea particularmente difícil. El estudio utiliza el marco de aprendizaje por refuerzo en tiempo continuo establecido por Wang et al. (2020) y Jia y Zhou (2022b), analizando específicamente la actualización de actor-crítico de PG donde la política se parametriza mediante la función logit (softmax).

Metodología
La contribución metodológica central es la construcción de una nueva función de Lyapunov para analizar la estabilidad y la convergencia de la SDE subyacente que gobierna los parámetros de la política.

1. Formulación de la SDE: El artículo modela la evolución de los parámetros logit $\boldsymbol{\phi}_t$ como una SDE (Ecuación 2). Esta SDE representa el límite de difusión del algoritmo de gradiente de política de tiempo discreto bajo un muestreo de alta frecuencia.
2. Construcción de la Función de Lyapunov: Los autores definen una función de Lyapunov específica $V_{\ell, \boldsymbol{\sigma}}(\boldsymbol{\phi})$ (Ecuación 15) que involucra una suma ponderada de términos exponenciales de las diferencias de logit entre los brazos subóptimos y el óptimo. Esta función está diseñada para capturar el comportamiento estabilizador del proceso.
3. Herramientas Analíticas: El análisis aprovecha el cálculo de Itô para computar el generador de la SDE aplicado a la función de Lyapunov. Al acotar los términos de deriva (drift) y difusión, los autores derivan desigualdades que demuestran el decaimiento de la función de Lyapunov, lo que corresponde a la convergencia de la política hacia el brazo óptimo.
4. Extensión a Tiempo Discreto: La misma función de Lyapunov se adapta para analizar el algoritmo de gradiente estocástico convencional de tiempo discreto, proporcionando un marco de prueba unificado tanto para los entornos continuos como para los discretos.

Resultados Clave
El artículo establece dos resultados teóricos primarios respecto a la convergencia y el arrepentimiento (regret) del método de gradiente de política:

1. Convergencia Casi Segura (Tasa de Aprendizaje Arbitraria):

   • Teorema 2: La actualización del gradiente de política converge casi seguramente al brazo óptimo (es decir, la probabilidad de seleccionar el mejor brazo tiende a 1) para cualquier tasa de aprendizaje constante arbitraria $\ell > 0$, siempre que las tasas de recompensa esperadas de los brazos sean distintas. Este resultado se mantiene sin las restrictivas condiciones de la tasa de aprendizaje que suelen requerirse para los límites de arrepentimiento.

2. Límites de Arrepentimiento No Asintóticos (Tasa de Aprendizaje Pequeña):

   • Teorema 1 (Tiempo Continuo): Cuando la tasa de aprendizaje constante $\ell$ es inferior a un umbral invariante en el tiempo determinado por la brecha entre las medias de los brazos y sus volatilidades, el algoritmo logra un límite superior de arrepentimiento esperado no asintótico de orden $O(\log T)$. El límite depende de la instancia y se mantiene para cualquier horizonte de tiempo finito $T$.
   • Teorema 3 (Tiempo Discreto): Se deriva un límite de arrepentimiento $O(\log N)$ similar para el algoritmo de tiempo discreto bajo una condición de tasa de aprendizaje $\ell \leq O(1/d)$, donde $d$ es el número de brazos. Esta condición se alinea con conjeturas recientes en la literatura sobre la máxima tasa de aprendizaje estable.

Comparación con la Literatura Existente
El artículo posiciona sus resultados frente a trabajos recientes, notablemente Lattimore (2026a), quien analizó la misma SDE utilizando un método diferente.

• Condiciones Relajadas: Este trabajo relaja las condiciones de la tasa de aprendizaje encontradas en Lattimore (2026a), que requería $\ell \leq O(1/\log T)$ para ciertos resultados. En contraste, este trabajo demuestra la convergencia casi segura para cualquier $\ell$ constante y un arrepentimiento logarítmico para $\ell \leq O(1/d)$.
• Prueba Unificada: A diferencia de análisis previos que trataban los casos de dos brazos y de múltiples brazos por separado, este trabajo proporciona una prueba unificadora para el caso de múltiples brazos ($d \geq 2$).
• Transparencia: Los autores afirman que el uso de herramientas de SDE y funciones de Lyapunov ofrece una forma transparente y rigurosa de analizar la dinámica del gradiente de política, simplificando la verificación en comparación con los argumentos de martingala de tiempo discreto.

Significancia y Reivindicaciones
Los autores afirman que este trabajo demuestra la viabilidad del aprendizaje "libre de modelo" (model-free) en entornos de difusión, donde el principio de optimización (gradiente de política) maneja naturalmente el dilema de exploración-explotación sin ajustes estadísticos explícitos (como Upper Confidence Bounds o Thompson Sampling).

• Perspectiva Teórica: El artículo destaca que la misma función de Lyapunov efectiva para las SDE de tiempo continuo también es poderosa para el análisis de tiempo discreto, cerrando la brecha entre ambos marcos.
• Limitaciones: Los autores señalan modestamente que, aunque el límite de arrepentimiento es logarítmico, el orden con respecto al número de brazos $d$ es mayor que los límites óptimos típicos para MABs. Además, el límite de arrepentimiento "independiente de la instancia" (independiente de la brecha $\Delta$ específica) sigue siendo un problema abierto. Los resultados de convergencia para tasas de aprendizaje arbitrarias se aplican a la convergencia por trayectoria (pathwise), pero no garantizan un arrepentimiento esperado logarítmico para $\ell$ grandes debido a la posible falta de integrabilidad uniforme.

En resumen, el artículo proporciona un análisis riguroso basado en SDE que muestra que los métodos de gradiente de política en entornos de difusión pueden lograr un arrepentimiento logarítmico óptimo y convergencia casi segura, siempre que la tasa de aprendizaje se escale adecuadamente, utilizando una novedosa función de Lyapunov que unifica el análisis de los algoritmos de tiempo continuo y discreto.