Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

Formulación del Problema
Este artículo investiga los banditos logísticos estocásticos bajo el objetivo de arrepentimiento simple. En este escenario, un agente interactúa con un entorno durante $T$ rondas, seleccionando acciones $A_t$ de un conjunto $\mathcal{A}$ y observando recompensas de Bernoulli $X_t$ con media $\mu(\phi(A_t)^\top \theta^*)$, donde $\mu$ es la función sigmoide, $\phi$ es una aplicación de características conocida y $\theta^*$ es un parámetro desconocido en $\mathbb{R}^d$. A diferencia del arrepentimiento acumulado, donde el objetivo es maximizar la suma de recompensas durante la exploración, el objetivo de arrepentimiento simple evalúa al agente únicamente en la calidad de una única recomendación final $\hat{a}$ tras $T$ rondas. El arrepentimiento se define como la diferencia entre la recompensa esperada de la acción óptima y la recompensa esperada de la acción recomendada.

Un desafío crítico en los banditos logísticos es la informatividad no uniforme de las acciones. Debido al enlace sigmoide, las acciones en regiones "saturadas" (donde la recompensa media está cerca de 0 o 1) producen recompensas casi deterministas pero proporcionan poca información sobre el parámetro $\theta^*$. Por el contrario, las acciones cerca del origen (donde la sigmoide es más pronunciada) son altamente informativas pero pueden producir recompensas inmediatas más bajas. Esto crea una geometría donde las acciones mejores para la recompensa inmediata (explotación) difieren de aquellas mejores para identificar la acción óptima (exploración).

Metodología
Los autores proponen dos algoritmos conscientes de la curvatura diseñados para explotar la geometría local de la función sigmoide:

1. MULOG (Max-Uncertainty-Log): Un algoritmo de exploración pura determinista.

   • Mecanismo: MULOG mantiene un conjunto de confianza $W_t$ para $\theta^*$ y construye una matriz de diseño ponderada por la curvatura $L_t$. La puntuación de incertidumbre para una acción $a$ y un parámetro $\theta$ se define como $U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$, donde $\dot{\mu}$ es la derivada de la sigmoide (que representa la curvatura local).
   • Selección: En cada ronda, el algoritmo selecciona el par acción-parámetro $(A_t, \theta_t)$ que maximiza esta puntuación de incertidumbre.
   • Terminación: Tras $T$ rondas, devuelve la acción codiciosa respecto a un vector de parámetros muestreado del conjunto de confianza final.
   • Optimización: Para conjuntos de acciones finitos, el paso de selección se reduce a resolver una colección finita de problemas de optimización convexa.

2. THATS (Try Hard Thompson Sampling): Una alternativa aleatorizada y computacionalmente más ligera.

   • Mecanismo: En lugar de resolver para la incertidumbre máxima exacta, THATS muestrea una dirección $\tilde{\theta}_t$ desde una distribución gaussiana centrada en cero con covarianza $L_t^{-1}$.
   • Selección: Selecciona la acción que maximiza la puntuación de incertidumbre aleatorizada $\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$, donde $\bar{\theta}_t$ es una estimación de máxima verosimilitud restringida.
   • Compensación: Este enfoque evita la optimización convexa requerida por MULOG pero incurre en un costo estadístico, resultando en un límite de arrepentimiento ligeramente más laxo.

Contribuciones Clave

• Límite Inferior Minimax: El artículo establece un límite inferior minimax de primer orden del orden $\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, donde $\kappa^*$ es la pendiente inversa de la sigmoide en la acción óptima (es decir, $\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$).
  • Mecanismo de Dificultad Distinto: A diferencia de los límites inferiores de arrepentimiento acumulado (por ejemplo, Abeille et al., 2021) que dependen del costo de la información (obligando al agente a jugar brazos casi óptimos), este límite inferior se deriva de una construcción de "hipercubo saturado desplazado". En esta construcción, tanto la información estadística como la sensibilidad al valor están controladas por la misma curvatura local en una región saturada. Esto revela que incluso con la libertad de muestrear puramente para obtener información, el problema sigue siendo difícil si la acción óptima se encuentra en una región plana de la sigmoide.
• Algoritmos Óptimos:
  • MULOG alcanza un límite superior de arrepentimiento simple de $\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, que coincide con el límite inferior hasta factores logarítmicos. Esta es la primera garantía directa de exploración pura para banditos logísticos que logra optimalidad minimax a nivel de instancia.
  • THATS alcanza un límite de $\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$. El factor extra $\sqrt{d}$ surge del uso de una aproximación aleatorizada agnóstica a la geometría de la dirección de máxima incertidumbre.
• Insight Geométrico: Los autores demuestran que la geometría del peor caso (instancias saturadas desplazadas) no es el único caso. Muestran que pueden existir "acciones de baja recompensa e informativas" (sondas) en el conjunto de acciones. Estas acciones se encuentran en la región de alta curvatura de la sigmoide, proporcionando información significativa sobre la dirección óptima a pesar de tener recompensas esperadas bajas.

Resultados

• Teóricos: Los límites derivados confirman que la dificultad del arrepentimiento simple logístico está gobernada por la curvatura en la acción óptima. Los algoritmos controlan con éxito la incertidumbre en las direcciones de características ponderadas por la curvatura.
• Empíricos: Los experimentos en geometrías "duras" (hipercubos saturados desplazados) y geometrías "fáciles" (con brazos de sondeo informativos añadidos) respaldan los hallazgos teóricos:
  • En instancias difíciles, MULOG y THATS se comportan como predicen los límites minimax.
  • En instancias fáciles con brazos de sondeo, los métodos de exploración pura (MULOG y THATS) superan significativamente a las líneas base de arrepentimiento acumulado (como Thompson Sampling Acumulativo y conversiones de online a batch). Los métodos de exploración pura muestrean activamente las sondas de baja recompensa y alta información, reduciendo drásticamente las rondas necesarias para alcanzar un umbral bajo de arrepentimiento simple.
  • Los métodos de arrepentimiento acumulado no logran explotar estas sondas de manera efectiva porque su conversión de online a batch penaliza la inclusión de acciones de baja recompensa en la distribución de recomendación final.

Significado
El artículo afirma que la exploración pura en banditos logísticos posee una geometría distinta a la de los problemas de arrepentimiento acumulado. La contribución principal es identificar que la curvatura local en la acción óptima ($\kappa^*$) es el factor gobernante para la tasa minimax de primer orden. Al desarrollar algoritmos que tienen en cuenta explícitamente esta curvatura, los autores logran un rendimiento minimax-óptimo en el peor de los casos. Además, el trabajo destaca una implicación práctica: en escenarios como pruebas A/B o recopilación de datos de modelos de recompensa, buscar activamente acciones "informativas pero de baja recompensa" puede acelerar sustancialmente la identificación de la política final óptima, un comportamiento que los algoritmos estándar de arrepentimiento acumulado son estructuralmente incapaces de exhibir. Los resultados sirven como punto de partida para una teoría más precisa de la exploración enfocada en la toma de decisiones en banditos no lineales.