Resumen Técnico: Aprendizaje On-Policy y Off-Policy para Espacios de Acción Grandes

Declaración del Problema

La tesis aborda el desafío fundamental del aprendizaje en sistemas interactivos, específicamente en los bandidos contextuales, donde el espacio de acciones $K$ es extremadamente grande (oscilando entre miles y millones). En tales entornos, los algoritmos estándar tanto para el aprendizaje on-policy (en línea) como off-policy (fuera de política) enfrentan cuellos de botella de escalabilidad severos:

• On-Policy: Las estrategias de exploración estándar como Thompson Sampling (TS) o Upper Confidence Bound (UCB) dependen típicamente de modelos disjuntos donde cada acción tiene un parámetro independiente. En espacios de acción grandes, aprender cada parámetro de forma independiente es estadísticamente ineficiente, lo que conduce a un alto arrepentimiento (regret) acumulado. Por el contrario, los modelos conjuntos que comparten parámetros a través de todas las acciones suelen ser computacionalmente intratables debido a la complejidad de $O(K^2)$ o $O(K^3)$ para mantener y actualizar una matriz de covarianza completa.
• Off-Policy: El aprendizaje a partir de datos estáticos registrados por una política de registro $\pi_0$ enfrenta tres problemas principales:
  1. Ineficiencia Estadística: Los métodos directos (DM) sufren de un alto sesgo cuando las acciones son raramente observadas.
  2. Varianza: Los estimadores de Inverse Propensity Scoring (IPS) exhiben una varianza explosiva cuando la probabilidad de registro $\pi_0(a|x)$ es pequeña.
  3. Intratabilidad de la Optimización: La tesis argumenta que, en espacios de acción grandes, el paisaje de optimización de los objetivos estándar basados en IPS se vuelve altamente no cóncavo, con mesetas planas y una cantidad exponencial de máximos locales, lo que causa que los optimizadores basados en gradiente fallen independientemente de la calidad estadística del estimador.

Metodología y Contribuciones

La tesis se divide en dos partes, proponiendo métodos novedosos para cada paradigma de aprendizaje.

Parte I: Aprendizaje On-Policy (Escalando Thompson Sampling)

La idea central es retener la flexibilidad de los modelos de recompensa disjuntos mediante la introducción de prioris bayesianos estructurados que permitan el intercambio de información entre acciones.

1. Mixed-Effect Thompson Sampling (meTS) - Capítulo 3

• Metodología: Los autores introducen un modelo bayesiano jerárquico donde los parámetros de acción $\theta_a$ están acoplados a través de $L$ parámetros de efectos latentes compartidos $\Psi = (\psi_\ell)_{\ell \in [L]}$. El proceso generativo asume $\theta_a | \Psi \sim p_0(\cdot|\Psi)$.
• Algoritmo: meTS realiza un muestreo jerárquico: primero, el muestreo de los efectos globales $\Psi_t$ desde su posterior, luego el muestreo de los parámetros de acción individuales $\theta_{t,a}$ condicionados a $\Psi_t$.
• Resultados Teóricos: Para modelos lineales-Gaussianos, los autores derivan actualizaciones posteriores exactas en forma cerrada. Demuestran un límite de arrepentimiento bayesiano de $\tilde{O}(\sqrt{Td K_{eff}})$, donde $K_{eff}$ es un número efectivo de acciones. Cuando el número de efectos $L \ll K$, entonces $K_{eff} \ll K$, lo que produce una mejora multiplicativa sobre el TS estándar.
• Complejidad: El método reduce la complejidad de memoria de $O(K^2d^2)$ a $O((L^2 + K)d^2)$ y el tiempo de ejecución de $O(K^3d^3)$ a $O((L^3 + K)d^3)$.
• Extensiones: El marco se extiende a Modelos Lineales Generalizados (GLMs) utilizando aproximaciones de Laplace tratables.

2. Diffusion Thompson Sampling (dTS) - Capítulo 4

• Metodología: Para capturar dependencias no lineales más complejas entre acciones, los autores reemplazan la estructura de variable latente de una sola capa con una jerarquía profunda de variables latentes gobernadas por modelos de difusión pre-entrenados. La priori se define como una cadena de Markov de variables latentes $\psi_L \to \dots \to \psi_1 \to \theta_a$ conectadas por funciones de enlace no lineales $f_\ell$.
• Algoritmo: dTS emplea un procedimiento de inferencia recursivo. Aproxima la posterior intratable manteniendo un "modelo de difusión posterior" donde las funciones de enlace y las covarianzas se actualizan mediante actualizaciones de tipo Gaussiano (combinando la precisión de la priori y la precisión de los datos) sin realizar retropropagación a través de la red neuronal.
• Resultados Teóricos: En un entorno lineal-Gaussiano, el límite de arrepentimiento escala con el número efectivo de acciones y la suma de las varianzas a través de las $L$ capas. La complejidad escala linealmente con $L$, es decir, $O((L+K)d^2)$, mejorando a meTS.
• Significancia: Esto demuestra que los modelos generativos profundos pueden utilizarse no solo para la representación, sino para estructurar la incertidumbre necesaria para una exploración eficiente.

Parte II: Aprendizaje Off-Policy (Abordando la Estimación y la Optimización)

La tesis desafía el paradigma predominante "centrado en la estimación" y propone tres enfoques complementarios.

1. Structured Direct Method (sDM) - Capítulo 6

• Metodología: De manera análoga a meTS, sDM introduce un vector latente compartido $\psi$ para acoplar los parámetros de acción en el entorno fuera de política. Calcula la posterior sobre los efectos latentes y las posteriores condicionales para los parámetros de acción.
• Resultados: Los autores demuestran que sDM logra una convergencia de $O(1/\sqrt{n})$ en suboptimalidad bayesiana sin requerir el restrictivo supuesto de "soporte completo de registro" (full logging support). El límite depende de la alineación entre la política de registro y la política óptima.
• Perspectiva: Bajo el criterio de suboptimalidad bayesiana considerado, se muestra que las políticas codiciosas (greedy) son óptimas y pueden superar a las políticas pesimistas, contrastando con los entornos frecuentistas donde el pesimismo suele ser necesario.

2. La Optimización Importa Más que la Estimación - Capítulo 7

• Metodología: Los autores demuestran que, en espacios de acción grandes, el error de optimización domina al error de estimación. Los objetivos estándar basados en IPS inducen paisajes no cóncavos que atrapan a los optimizadores.
• Propuesta: En lugar de estimar el valor y luego optimizar, la tesis aboga por objetivos de Log-Likelihood Ponderado por la Política (PWLL):
  $$\hat{U}_g(\pi) = \frac{1}{n} \sum_{i=1}^n g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$$
• Resultados: Para políticas softmax lineales, los objetivos PWLL son cóncavos (y fuertemente cóncavos con regularización $\ell_2$), garantizando un máximo global único. Los experimentos en conjuntos de datos con hasta un millón de acciones muestran que estos objetivos simples y estables superan consistentemente a los métodos sofisticados basados en estimadores de valor.

3. Pesimismo Principiado para el Suavizado Exponencial - Capítulo 8

• Metodología: Para abordar la varianza de IPS, los autores introducen estimadores de Suavizado Exponencial (ES) diferenciables que interpolan entre la ausencia de regularización y la reducción fuerte de la varianza.
• Teoría: Se deriva un límite de generalización PAC-Bayesiano de dos lados para estos estimadores regularizados. Este límite descompone el error en divergencia, sesgo de regularización y varianza restante.
• Aplicación: El límite produce un objetivo de aprendizaje pesimista, totalmente diferenciable, que puede optimizarse mediante el ascenso de gradiente estocástico. El marco se unifica para cubrir otros regularizadores como el recorte (clipping) y la exploración implícita.
• Extensión: Los autores también introducen el Suavizado Logarítmico (LS), una alternativa suave y diferenciable al recorte que logra límites de concentración más ajustados.

Resultados Experimentales

Los métodos propuestos se validan tanto en conjuntos de datos sintéticos como en el mundo real:

• On-Policy: En bandidos lineales y logísticos sintéticos, meTS y dTS superan significativamente a los modelos base (LinTS, GLM-TS, HierTS), con una brecha de rendimiento que aumenta a medida que el espacio de acciones $K$ crece. En experimentos de MovieLens (sistemas de recomendación), meTS logra el menor arrepentimiento incluso cuando el modelo de recompensa real está mal especificado, demostrando robustez.
• Off-Policy:
  • sDM supera a los Métodos Directos estándar, con ganancias que aumentan conforme $K$ crece.
  • Los objetivos PWLL (Capítulo 7) superan consistentemente a los métodos de estado del arte basados en IPS en conjuntos de datos con hasta un millón de acciones, mostrando una robustez superior al ajuste de hiperparámetros.
  • Los objetivos pesimistas PAC-Bayesian (Capítulo 8) logran mejores recompensas que los modelos base (incluyendo a London et al. y Sakhi et al.) a través de diversas calidades de política de registro, particularmente cuando la política de registro no es uniforme.

Significancia y Reivindicaciones

La tesis afirma cerrar la brecha entre los algoritmos de bandidos teóricos y las restricciones de los sistemas industriales modernos (por ejemplo, sistemas de recomendación con millones de artículos). Su argumento central es que escalar a espacios de acción grandes requiere:

1. Estructurar la Incertidumbre: Utilizar prioris jerárquicos y de difusión para compartir la fuerza estadística entre las acciones (On-Policy).
2. Reevaluar los Objetivos: Reconocer que, en espacios grandes, la tratabilidad del paisaje de optimización es tan crítica como la precisión estadística del estimador (Off-Policy).
3. Pesimismo Diferenciable: Desarrollar objetivos pesimistas teóricamente fundamentados, pero computacionalmente factibles, que controlen la varianza y el sesgo sin depender de constantes intratables.

El trabajo afirma que, al alejarse del modelado de acciones independientes y de la estimación de valor estándar, los bandidos contextuales pueden desplegarse eficazmente en entornos donde los espacios de acción rutinariamente exceden los miles o millones.