Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret

Resumen Técnico: Cobertura de Cover y Robbins en Apuestas sobre Datos Acotados

1. Planteamiento del Problema

El trabajo aborda el problema de la apuesta secuencial (o betting) contra una secuencia de datos $X_1, X_2, \dots$ tomados en el intervalo $[0, 1]$. Se asume un valor de media condicional objetivo $m_0 \in (0, 1)$.

• Mecanismo: Un apostador puede realizar apuestas basadas en una fracción $\lambda$ de su riqueza actual. La riqueza en el tiempo $n$ para una estrategia fija $\lambda$ se define como:
  $$W_n(\lambda) = \prod_{i=1}^n (1 - \lambda(X_i - m_0))$$
  donde $\lambda$ debe estar en el rango $[-1/m_0, 1/(1-m_0)]$ para garantizar que la riqueza no sea negativa.
• Objetivo: Minimizar el arrepentimiento (regret) $R_n$ de una estrategia de mezcla (mixture) $W_n$ en comparación con la mejor estrategia fija $\lambda^*$ que se podría haber elegido con conocimiento de causa (hindsight):
  $$R_n = \ln W^*_n - \ln W_n$$
  donde $W^*_n = \sup_{\lambda} W_n(\lambda)$.

El desafío central es la tensión entre dos objetivos:

1. Garantizar un arrepentimiento bajo en el peor caso (datos adversarios).
2. Lograr un crecimiento óptimo y un arrepentimiento muy bajo en caminos típicos (datos estocásticos).

2. Metodología

Los autores proponen una estrategia de agregación convexa (mezcla) que combina dos estrategias clásicas de la literatura de probabilidad y aprendizaje en línea:

1. Mezcla Uniforme (Estilo Cover): Utiliza una distribución uniforme sobre el espacio de apuestas $\lambda$.

   • Comportamiento: Garantiza un arrepentimiento de $O(\ln n)$ en todas las trayectorias (incluso adversarias).
   • Limitación: No mejora su comportamiento en caminos estocásticos típicos; el arrepentimiento sigue siendo $O(\ln n)$.

2. Mezcla de Robbins (Modificada): Utiliza una distribución de prior "pesada cerca de cero" (heavy-near-zero), inspirada en el trabajo de Robbins y Siegmund, pero adaptada al intervalo acotado $[0, 1]$.

   • Comportamiento: Logra un arrepentimiento de $O(\ln \ln n)$ en casi todas las trayectorias (conjunto de medida 1 bajo supuestos estocásticos).
   • Limitación: Puede incurrir en arrepentimiento lineal ($O(n)$) en caminos atípicos o adversarios, y tiene una tasa de crecimiento asintótico subóptima en ciertos escenarios estocásticos.

La Innovación: Los autores proponen una mezcla convexa simple (ej. 50-50) de ambas estrategias. Definen la riqueza agregada como $W_n = s_0 W^{(1)}_n + (1-s_0) W^{(2)}_n$, donde $W^{(1)}$ es la mezcla uniforme y $W^{(2)}$ es la mezcla de Robbins modificada.

3. Contribuciones Clave

1. Resolución de la Tensión "Mejor de Ambos Mundos":
   El artículo demuestra que es posible lograr simultáneamente:

   • Un arrepentimiento de $O(\ln n)$ en el peor caso (garantía universal).
   • Un arrepentimiento de $O(\ln \ln n)$ en casi todas las trayectorias estocásticas (caminos típicos).
   • Una tasa de crecimiento asintótico óptima en escenarios estocásticos, superando la limitación de la estrategia de Robbins pura.

2. Límites de Arrepentimiento Explícitos:

   • Se establece un límite de arrepentimiento de camino (path-wise) explícito para la mezcla uniforme (Teorema 3.1).
   • Se deriva un límite condicional de arrepentimiento $O(\ln \ln V_n)$ para la mezcla de Robbins (Teorema 4.1), donde $V_n$ es el proceso de varianza intrínseca.
   • Se demuestra que la estrategia agregada hereda el mejor comportamiento de ambas: el límite de arrepentimiento es el mínimo de los dos componentes (más una constante).

3. Ley del Logaritmo Iterado (LIL) Teórico-Juego:
   La estrategia construida actúa como un testigo explícito para la Ley del Logaritmo Iterado (LIL) y la Ley Fuerte de los Grandes Números (SLLN) auto-normalizada.

   • El resultado establece una dicotomía determinista: O bien la LIL se cumple en una trayectoria, o el proceso de riqueza $W_n$ explota hacia infinito en esa misma trayectoria. Esto conecta directamente el análisis de arrepentimiento con la teoría de juegos y la probabilidad.

4. Contraste con Datos No Acotados:
   El trabajo aclara las diferencias con el escenario de datos sub-Gaussianos (estudiado previamente por Agrawal y Ramdas [2026]). En datos acotados, la agregación simple resuelve las compensaciones de manera más efectiva que en el caso no acotado, donde las garantías de crecimiento y arrepentimiento son más complejas.

4. Resultados Principales

• Teorema 3.1 (Mezcla Uniforme): Para cualquier secuencia en $[0, 1]$, el arrepentimiento es $R_n \leq \ln(n+1) + 1$. Esto implica que si la media muestral no converge a $m_0$, la riqueza de la estrategia uniforme explota.
• Teorema 4.1 y 4.2 (Mezcla de Robbins): Bajo supuestos estocásticos naturales, la mezcla de Robbins logra $R_n = O(\ln \ln n)$ casi seguramente. Si la LIL o SLLN se violan en una trayectoria, la riqueza explota.
• Proposición 5.1 (Estrategia Agregada):
  • Arrepentimiento: $R_n \leq \min(R^{(1)}_n, R^{(2)}_n) + C$. Esto garantiza $O(\ln n)$ globalmente y $O(\ln \ln n)$ en el conjunto de medida 1.
  • Crecimiento: La tasa de crecimiento asintótico de la estrategia agregada es al menos tan grande como la de la mejor de sus componentes individuales ($G \geq \max(G^{(1)}, G^{(2)})$).

5. Significado e Impacto

• Unificación de Paradigmas: El trabajo une dos escuelas de pensamiento históricamente distintas: la teoría de portafolios universales de Cover (enfoque adversario/determinista) y los métodos de martingalas de Robbins (enfoque estocástico).
• Eliminación de Compensaciones (Trade-offs): Demuestra que las compensaciones percibidas entre garantizar un rendimiento robusto en el peor caso y un rendimiento óptimo en escenarios estocásticos no son fundamentales. Una simple combinación convexa resuelve ambas necesidades.
• Aplicaciones en Inferencia: Dado que los procesos de riqueza están intrínsecamente ligados a la construcción de secuencias de confianza (confidence sequences), estos resultados permiten crear intervalos de confianza más estrechos (tamaño $O(\sqrt{(\ln \ln n)/n})$) que son válidos uniformemente en el tiempo y robustos frente a violaciones de supuestos, sin sacrificar la validez en el peor caso.
• Fundamentos Teóricos: Proporciona una prueba constructiva y explícita de la Ley del Logaritmo Iterado desde la perspectiva de la probabilidad teórica de juegos, ofreciendo un "testigo" (la estrategia de apuesta) que detecta desviaciones de la ley.

En conclusión, este artículo presenta una estrategia de apuestas simple pero poderosa que logra lo mejor de ambos mundos: protección contra datos adversarios y eficiencia óptima en datos estocásticos, estableciendo nuevos estándares para el análisis de arrepentimiento en datos acotados.