Multiscale Reward Hedging from Correct Demonstrations

Resumen Técnico: Cobertura de Recompensas Multiescala a partir de Demostraciones Correctas

Formulación del Problema
El artículo aborda el problema de aprender a partir de demostraciones correctas en entornos donde múltiples acciones pueden ser óptimas. A diferencia del aprendizaje supervisado estándar, el aprendiz observa una única demostración válida $a^*_t$ para un contexto $x_t$, pero no recibe retroalimentación sobre si su propia predicción $\hat{a}_t$ fue correcta, ni observa la función de recompensa subyacente o la magnitud de su pérdida. El objetivo es minimizar la "brecha oculta" acumulada (la diferencia entre la recompensa de la acción óptima y la acción del aprendiz) frente a una función de recompensa desconocida $r^*$.

Este entorno generaliza el trabajo previo sobre clases de recompensas finitas (Joshi et al., 2026) a clases de recompensas continuas, un vacío que no había sido abordado previamente para clases continuas generales. El modelo de retroalimentación es distinto de la optimización inversa en línea o de los bandits contextuales estándar, ya que el aprendiz nunca observa un valor de recompensa ni un bit de corrección; solo observa una acción válida de un conjunto de acciones óptimas desconocidas.

Metodología: Cobertura de Recompensas Multiescala (Multiscale Reward Hedging)
La contribución central es un algoritmo determinista de cobertura de recompensas multiescala que opera sin un horizonte de tiempo conocido. La metodología se basa en los siguientes componentes:

1. Métrica de Brecha y Proxies: El algoritmo se centra en la función de brecha de optimalidad $g_r(x, a) = \sup_{b \in A(x)} r(x, b) - r(x, a)$. En lugar de estimar directamente la función de recompensa, el aprendiz mantiene un voto ponderado sobre un conjunto de "proxies binarios tolerantes".
2. Cobertura Multiescala: Para una secuencia de escalas de precisión $\epsilon_j = 2^{-j-1}$, el algoritmo construye cubiertas adecuadas $\epsilon_j$ ($C_j$) de la clase de la función de brecha $G$. Cada elemento $h \in C_j$ define un proxy $q_{j,h}$ que etiqueta una acción como "buena" si $h(x, a) \le \epsilon_j$.
3. Voto Compartido: En lugar de ejecutar aprendices separados para cada escala (lo que produciría acciones incompatibles), el algoritmo agrega todos los proxies a través de todas las escalas en un único voto ponderado. El peso inicial de un proxy en la escala $j$ es proporcional a $2^{-j}$.
4. Regla de Actualización: La actualización es "ajena al error" (mistake unaware). Al observar una demostración $a^*_t$, el algoritmo actualiza los pesos basándose únicamente en la comparación entre el juicio del proxy y la predicción del aprendiz:
   • Si el proxy califica la demostración como buena pero la acción del aprendiz como mala, el peso del proxy se duplica.
   • Si el proxy califica la demostración como mala, su peso se reduce a cero.
   • De lo contrario, el peso permanece sin cambios.
     Esta regla asegura que si la acción del aprendiz tiene una brecha grande respecto a una escala específica, el peso del proxy que representa esa escala aumenta, efectivamente "cubriendo" (hedging) contra esa escala de error.

Resultados Teóricos Clave

• Límites de Cola Libres de Horizonte: El algoritmo proporciona un límite de cola simultáneo para el número de rondas donde la pérdida excede un umbral $2^{-j}$:
  $$|\{t : \ell_t > 2^{-j}\}| \le \log_2 N(G, 2^{-j-1}) + j$$
  donde $N(G, \epsilon)$ es el número de cobertura de la clase de la brecha. La integración de estas colas produce un límite de la brecha oculta acumulada independiente del horizonte de tiempo $T$:
  $$\sum_{t=1}^T \ell_t \le \sum_{j \ge 1} 2^{-j} \log_2 N(G, 2^{-j-1}) + 2$$
  Esta suma está acotada por una integral de entropía métrica, $H_{dyad}(G)$.

• Entropía Polinómica y Tasas de Regret:

  • Para clases con números de cobertura polinómicos $N(G, \epsilon) \le (A/\epsilon)^d$, la brecha total está acotada por $O(d \log A)$.
  • Esto se traduce en una tasa estadística de $O(d/m)$ en el entorno de online-to-batch.
  • Recomendación Contextual Lineal: Para recompensas lineales acotadas con radio de parámetro $B$ y diámetro de menú $K$, el regret es $O(d)$ para menús compactos arbitrarios. Este es el primer límite finito polinómico para menús arbitrarios sin restricciones estructurales (p. ej., M-convexidad), logrado mediante un predictor impropio.
  • Recompensas de Bajo Rango y Redes Neuronales: El marco se extiende a recompensas bilineales de bajo rango ($O(BKr(m+n))$) y redes ReLU acotadas con límites explícitos que dependen de la profundidad y los parámetros de la red.

• Complejidad Computacional:

  • El algoritmo general es de carácter informacional y puede ser computacionalmente costoso debido a la enumeración de la cobertura.
  • Sin embargo, para curvas de parámetros Lipschitz unidimensionales (p. ej., recomendación de radio fijo de rango dos), el algoritmo es exacto y se ejecuta en tiempo polinomial. Específicamente, para la recomendación de radio fijo de rango dos con tamaño de menú $k$ y costo de evaluación de recompensa $C$, la complejidad temporal es $O(kCT^2)$.

• Límites Inferiores y Robustez:

  • El artículo demuestra un límite inferior $\Omega(d)$ coincidente para clases continuas con exponente de entropía $d$, confirmando la rigidez de la dependencia $O(d)$.
  • Una variante robusta maneja demostraciones subóptimas, añadiendo únicamente la suboptimalidad acumulada del demostrador $\Delta_T$ al límite de regret.

Significancia y Reivindicaciones
El artículo afirma resolver la cuestión abierta de aprender de demostraciones correctas para clases de recompensas continuas. Su principal significancia radica en:

1. Primer Garantía Libre de Horizonte para Clases Continuas: Proporciona los primeros límites de regret para clases continuas que no dependen del horizonte de tiempo $T$, basándose en cambio en la entropía métrica.
2. Predicción Impropia para Menús Arbitrarios: Logra un regret de $O(d)$ para la recomendación contextual lineal con menús compactos arbitrarios, un escenario donde los algoritmos propios anteriores requerían restricciones estructurales (como la M-convexidad) o sufrían de dependencias de dimensión más altas.
3. Eficiencia en Geometrías Específicas: Aunque la votación general es costosa, el artículo aísla un caso no trivial (curvas Lipschitz 1D) donde el algoritmo exacto es de tiempo polinomial, cerrando la brecha entre los límites informacionales y la viabilidad computacional.
4. Validación Empírica: Una prueba de estrés reproducible con datos de MovieLens demuestra que el algoritmo se adapta a las escalas y mejora la brecha latente media en comparación tanto con las políticas de calificación demostrada como con las líneas base online propias, utilizando únicamente demostraciones de acciones sin observar las recompensas.

El autor enfatiza que, aunque la solución general es impropia (el voto puede no corresponder a un único parámetro de recompensa válido), tiene éxito minimizando la brecha de recompensa objetivo, distinguiéndose así de los métodos de optimización inversa en línea propios que buscan estimar el parámetro de la recompensa en sí.