Anytime-valid Optimal Policy Identification

Resumen Técnico: Identificación de Políticas Óptimas con Validez en Cualquier Momento (Anytime-Valid)

1. Planteamiento del Problema

El artículo aborda el desafío de identificar una política óptima ($\pi^\star$) a partir de una clase candidata finita $\Pi = \{\pi_1, \dots, \pi_m\}$ utilizando datos de bandits contextuales registrados (logged contextual bandit data). En muchos entornos prácticos, los datos son generados por una política de registro ($h_t$) externa determinada que el analista no controla. Esta política de registro puede ser una aleatorización fija o un algoritmo adaptativo ajustado para objetivos distintos al objetivo específico del analista (por ejemplo, maximizar la interacción del usuario en lugar de minimizar la desinformación).

La dificultad central radica en dos restricciones:

1. Entorno Off-Policy: El analista debe inferir el valor de las políticas objetivo $\nu(\pi)$ utilizando datos recolectados bajo una política diferente $h_t$, sin la capacidad de dirigir la recolección de datos hacia el objetivo de identificación.
2. Monitoreo Secuencial: Los profesionales suelen desear monitorear la evidencia de forma continua, eliminar políticas claramente subóptimas a medida que se acumulan los datos y detener la recolección de datos una vez que se identifica la política óptima, en lugar de comprometerse con un tamaño de muestra fijo ($N$) de antemano.

La literatura existente sobre la identificación de políticas óptimas típicamente asume que el analista controla la recolección de datos (muestreo adaptativo) o proporciona garantías inferenciales solo para un tamaño de muestra fijo y preespecificado. Este artículo busca cerrar la brecha proporcionando garantías de validez en cualquier momento (anytime-valid) para la identificación de políticas óptimas en entornos off-policy.

2. Metodología

El marco propuesto construye un conjunto de políticas candidatas óptimas indexado en el tiempo, $S_t$, que evoluciona conforme llegan los datos. La metodología se basa en tres componentes principales:

A. Pseudo-resultados Doblemente Robustos (Doubly Robust Pseudo-Outcomes)
Para estimar los valores de las políticas $\nu(\pi)$ a partir de datos registrados, el método utiliza pesos de importancia $w_t(\pi) = \pi(A_t|X_t) / h_t(A_t|X_t)$. Para mejorar la eficiencia y la estabilidad, estos se combinan con un modelo de recompensa $b_{rt}(x,a)$ para construir pseudo-resultados doblemente robustos (DR). Específicamente, se definen pseudo-resultados inferiores y superiores ($\phi^{DRL}_t$ y $\phi^{DRU}_t$) tales que sus expectativas condicionales sean iguales al verdadero valor de la política $\nu(\pi)$ y $1-\nu(\pi)$, respectivamente. Crucialmente, la validez no depende de que el modelo de recompensa esté correctamente especificado, sino únicamente de que las probabilidades de la política de registro sean conocidas.

B. Secuencias de Confianza (CS) con Validez en Cualquier Momento
Basándose en el trabajo de Waudby-Smith et al. (2024), el artículo construye secuencias de confianza para los valores de las políticas. Una secuencia de intervalos $[L_t(\pi), U_t(\pi)]$ es una CS de $(1-\alpha)$ si el valor real $\nu(\pi)$ permanece dentro del intervalo para todo $t \geq 1$ con una probabilidad de al menos $1-\alpha$. Estos intervalos se construyen utilizando los pseudo-resultados DR y un proceso de varianza $V_t(\pi)$ que contabiliza la acumulación de evidencia. El ancho de estos intervalos se reduce a una tasa de $O(\sqrt{(\log \log t + \log m)/t})$.

C. Eliminación Secuencial y Regla de Parada
Utilizando un límite superior de unión (union bound) sobre la clase de políticas $\Pi$, el método construye secuencias de confianza simultáneas para todas las políticas. El conjunto candidato $S_t$ se define como:
$$S_t := \left\{ \pi \in \Pi : U_t\left(\pi; \frac{\alpha}{m}\right) \geq \max_{\pi' \in \Pi} L_t\left(\pi'; \frac{\alpha}{m}\right) \right\}$$
Una política es eliminada de $S_t$ si su límite de confianza superior cae por debajo del límite de confianza inferior máximo de cualquier política competidora. El procedimiento se detiene en un tiempo dependiente de los datos $\tau$ cuando $S_\tau$ se convierte en un singleton (contiene una sola política).

3. Principales Contribuciones

El artículo realiza dos contribuciones teóricas primarias:

1. Garantía de Cobertura en Cualquier Momento: Los autores demuestran que el conjunto construido $S_t$ satisface una garantía de cobertura uniforme:
   $$P(\Pi^\star \subseteq S_t \text{ para todo } t \geq 1) \geq 1 - \alpha$$
   donde $\Pi^\star$ es el conjunto de las verdaderas políticas óptimas. Esto asegura que, con alta probabilidad, ninguna política óptima sea eliminada, independientemente de cuándo el analista decida detenerse.

2. Límites de Complejidad de Muestra: Cuando la política óptima $\pi^\star$ es única, el artículo define un tiempo de parada $\tau$ para su identificación. Bajo una condición de regularidad de crecimiento de varianza lineal (Supuesto 1), la complejidad de la muestra se deriva como:
   $$\tau = O\left( \frac{\log m + \log \log(1/\Delta_{\min})}{\Delta_{\min}^2} \right)$$
   donde $\Delta_{\min}$ es la brecha entre el valor de la mejor política y el de la segunda mejor. Este límite indica que el número de muestras requeridas escala logarítmicamente con el tamaño de la clase de políticas e inversamente con el cuadrado de la brecha de suboptimidad.

4. Resultados Empíricos

El artículo valida el marco a través de tres demostraciones empíricas:

• Ilustración Sintética: En un entorno de bandit contextual simulado con seis políticas, el marco logró eliminar exitosamente las políticas claramente subóptimas temprano en el flujo de datos, mientras mantenía la política óptima hasta que fue identificada de forma unívoca. Las secuencias de confianza para los valores de las políticas convergieron a los valores reales según lo esperado.
• Eficiencia de Muestra: Al comparar el procedimiento de validez en cualquier momento contra un diseño de $N$ fijo (donde $N$ se calcula basándose en una brecha objetivo), los autores encontraron ahorros sustanciales de muestra cuando la brecha real era mayor que la brecha objetivo. Por ejemplo, si la brecha real era el doble de la brecha objetivo, el método de validez en cualquier momento ahorró entre un 60% y un 80% del tamaño de muestra planificado en promedio.
• Aplicación en el Mundo Real: El método se aplicó a un gran experimento adaptativo (Offer-Westort et al., 2024) que involucró a 15,292 usuarios en Kenia y Nigeria, con el objetivo de reducir la difusión de desinformación. El marco replicó la conclusión del estudio original (identificando el "impulso de precisión" y los "consejos de Facebook" como los mejores desempeños), pero proporcionó una visión dinámica de la acumulación de evidencia. Mostró que las peores políticas podían ser eliminadas con solo una fracción de los datos finales, mientras que los principales candidatos permanecieron en el conjunto de candidatos durante todo el proceso.

5. Significado y Limitaciones

Significado:
El artículo proporciona un marco inferencial riguroso para el monitoreo secuencial en entornos off-policy. Permite a los analistas tomar decisiones de parada dependientes de los datos sin invalidar las garantías estadísticas, abordando una limitación clave de los enfoques de $N$ fijo. Esto es particularmente valioso en aplicaciones del mundo real donde la recolección de datos está restringida por políticas de registro externas y los recursos son limitados.

Limitaciones:
Los autores señalan explícitamente dos limitaciones:

1. Invarianza Temporal: El marco asume que los valores de las políticas son constantes en el tiempo. Actualmente no maneja entornos no estacionarios donde los efectos del tratamiento evolucionan (por ejemplo, debido a la novedad o fatiga).
2. Requisito de Solapamiento (Overlap): El método requiere que cada política objetivo sea absolutamente continua con respecto a la política de registro (solapamiento estricto). Esto excluye escenarios donde la política de registro asigna determinísticamente una probabilidad de cero a acciones que una política objetivo tomaría, lo cual puede ocurrir en algoritmos adaptativos altamente concentrados (por ejemplo, de tipo UCB).

El artículo concluye que, si bien estas limitaciones existen, el marco ofrece una solución robusta para una amplia clase de políticas de registro estocásticas comúnmentamente encontradas en la práctica.