Resumen Técnico: Aprender Cuándo Detenerse: Aprendizaje por Imitación Selectiva bajo Desplazamientos Arbitrarios de Dinámica

1. Formulación del Problema

El artículo aborda el desafío del Aprendizaje por Imitación (IL) en escenarios donde las dinámicas de transición del entorno de prueba difieren arbitrariamente del entorno de entrenamiento. En el IL offline clásico, un agente entrenado con demostraciones de expertos desde un entorno fuente $M$ se despliega en un entorno objetivo $N$. Si los soportes de estado de $M$ y $N$ son disjuntos o están significativamente desplazados, una política estándar puede rendir arbitrariamente mal porque no puede reconocer cuándo sus datos de entrenamiento ya no proporcionan una guía fiable.

Los autores proponen un marco para el Aprendizaje por Imitación Selectiva, donde se otorga al agente la opción de abstenerse (detener la ejecución) a mitad de la trayectoria cuando detecta que el estado actual está fuera del soporte fiable de sus datos de entrenamiento. El objetivo es aprender una política selectiva $(\pi, \tau)$, compuesta por una política base $\pi$ y un tiempo de parada $\tau$, que satisfaga dos objetivos competitivos:

1. Completitud: La política debería abstenerse raramente en el entorno de entrenamiento $M$ (es decir, $\alpha_M(\pi, \tau) \le \epsilon$).
2. Solidez: La política debería incurrir en un bajo arrepentimiento en el entorno de prueba $N$ antes de detenerse (es decir, $Regret_N(\pi, \tau) \le \epsilon$).

El escenario asume acceso a:

• Despliegues de entrenamiento etiquetados: Pares estado-acción $(s, a)$ del experto $\pi^\star$ en el entorno $M$.
• Despliegues de prueba sin etiquetar: Trayectorias solo de estado del experto $\pi^\star$ en el entorno $N$. Esta asimetría modela escenarios del mundo real donde la telemetría de acciones es costosa o propietaria (por ejemplo, grabaciones de cámaras de salpicadero de conducción autónoma sin comandos de dirección).

2. Metodología: SeqRejectron

El algoritmo central, SeqRejectron, generaliza el algoritmo Rejectron de la clasificación selectiva (Goldwasser et al., 2020) a la toma de decisiones secuencial. La idea clave es que, en lugar de tomar decisiones independientes en cada paso de tiempo (lo que conduce a una complejidad de muestra dependiente del horizonte), el algoritmo certifica prefijos de trayectoria completos utilizando un conjunto disperso de políticas validadoras.

Mecanismo Central

1. Política Base: El agente selecciona una política base $\pi_0$ consistente con los datos de entrenamiento (por ejemplo, Estimación de Máxima Verosimilitud).
2. Conjuntos Validadores: El algoritmo construye un pequeño conjunto de políticas "validadoras" $\Phi$ extraídas del espacio de versiones (políticas consistentes con los datos de entrenamiento).
3. Regla de Parada: El agente ejecuta $\pi_0$ y continúa solo mientras cada validador en $\Phi$ esté de acuerdo con $\pi_0$. El primer punto de desacuerdo desencadena una parada (abstención).
4. Distribución Dispersa de Validadores: Una contribución teórica crítica es la demostración de que un conjunto validador disperso (tamaño independiente del horizonte $H$) es suficiente para garantizar la seguridad. Esto se logra mediante un argumento minimax sobre un juego de suma cero entre un "desafiante" (que elige una política competidora) y un "validador" (que elige un conjunto de validadores).

Variantes para Diferentes Escenarios

El artículo adapta este marco a tres escenarios cada vez más generales:

• Políticas Deterministas:

  • Mecanismo: Utiliza una prueba de desacuerdo binaria. El tiempo de parada $\tau$ es el primer paso donde cualquier validador $\pi \in \Phi$ discrepa de $\pi_0$.
  • Implementación: La distribución validadora se construye utilizando dinámicas sin arrepentimiento (específicamente, una reducción eficiente de oráculo al Aprendizaje de Múltiples Instancias Realizable Ponderado).
  • Resultado: Logra una complejidad de muestra libre de horizonte $\tilde{O}(\sqrt{\log|\Pi|/n})$ bajo costos dispersos.

• Políticas Estocásticas:

  • Desafío: El desacuerdo binario es demasiado grueso; las distribuciones pueden diferir "suavemente" en cada paso sin una única discrepancia alarmante.
  • Mecanismo: Reemplaza la prueba binaria con un tiempo de parada basado en la distancia de Hellinger acumulada. El agente se detiene cuando la distancia de Hellinger al cuadrado acumulada entre $\pi_0$ y cualquier validador supera un umbral $\theta$.
  • Resultado: Proporciona límites de muestra finita sobre la distancia de Hellinger de las trayectorias detenidas. El artículo establece un límite inferior de $\Omega(1/\epsilon^3)$ para la complejidad de muestra etiquetada en el escenario estocástico de un solo paso, coincidiendo con la parte impulsada por costos del límite superior.

• Clases de Políticas Mal Especificadas:

  • Desafío: El experto $\pi^\star$ puede no estar dentro de la clase de políticas del agente $\Pi$.
  • Mecanismo: Reemplaza la restricción estricta del espacio de versiones con un juego regularizado simétricamente. Se permite que los validadores discrepen con la política base en los datos fuente, pero este desacuerdo se penaliza.
  • Resultado: Las garantías se degradan graciosamente con la cantidad de mala especificación (medida por el error de mala especificación mejor en clase $\Delta$).

3. Contribuciones y Resultados Clave

Garantías Teóricas

• Complejidad Libre de Horizonte: Para políticas deterministas, la complejidad de muestra es independiente del horizonte $H$ (excepto a través de la escala total de costos $C_{max}$), escalando como $\tilde{O}(\sqrt{\log|\Pi|/n})$. Esto mejora las reducciones ingenuas paso a paso que sufren una penalización de $O(H^2)$.
• Validación Dispersa: El artículo demuestra la existencia de una distribución validadora soportada en conjuntos de tamaño $O(1/\epsilon)$, independiente del espacio de estados, espacio de acciones o horizonte.
• Límites Inferiores: Los autores demuestran un límite inferior de $\Omega(1/\epsilon^3)$ para la complejidad de muestra etiquetada en el escenario estocástico de un solo paso, mostrando que la dependencia cúbica en $1/\epsilon$ es inevitable para regímenes impulsados por costos.
• Robustez ante Mala Especificación: El marco se extiende a escenarios agnósticos donde el experto no está en la clase, con límites de arrepentimiento que escalan con la raíz cuadrada del error de mala especificación.

Evaluación Empírica

Los autores evalúan SeqRejectron en el entorno LunarLander-v3.

• Configuración: El entrenamiento ocurre en un entorno sin viento; la prueba ocurre en un entorno ventoso con impulsos iniciales diferentes.
• Hallazgos: El algoritmo detecta con éxito dinámicas fuera de distribución. Al ajustar un umbral de seguridad $\theta$, los autores demuestran una compensación donde la política se abstiene mínimamente en datos dentro de la distribución (entrenamiento) mientras se detiene de manera confiable en datos fuera de la distribución (prueba), previniendo fallos catastróficos. Se encontró que el número de validadores es robusto, con un rendimiento que se satura rápidamente.

4. Significado y Afirmaciones

El artículo afirma establecer la abstención como una respuesta principada y teóricamente fundamentada a los desplazamientos de dinámica no anticipados en el aprendizaje por imitación.

• Más allá de Heurísticas: A diferencia de los enfoques de RL robusto o aleatorización de dominio que requieren suposiciones sobre la naturaleza del desplazamiento o acceso en línea a la distribución de prueba, SeqRejectron proporciona garantías PAC libres de distribución utilizando únicamente datos offline.
• Análogo Secuencial del Aprendizaje PQ: El trabajo se posiciona como un análogo secuencial del marco de aprendizaje PQ (Goldwasser et al., 2020), extendiendo la capacidad de abstenerse de predicciones individuales a prefijos de trayectorias completos.
• Mecanismo de Seguridad: Al desacoplar la decisión de qué hacer de cuándo detenerse, el marco ofrece un mecanismo de seguridad que evita que el agente conduzca el sistema a estados irrecuperables cuando sus datos de entrenamiento no son informativos.

Los autores reconocen limitaciones, señalando que el escenario estocástico carece actualmente de una reducción computacional eficiente de oráculo (a diferencia del caso determinista) y que las tasas de complejidad de muestra impulsadas por la varianza para políticas estocásticas permanecen como una brecha abierta entre los límites superior e inferior. También sugieren que el trabajo futuro podría incorporar conocimiento estructural parcial (por ejemplo, distancia TV acotada) para afinar las tasas de parada en el lado de la prueba.