On the Role of Computation in Reinforcement Learning

Resumen Técnico: Sobre el Papel de la Computación en el Aprendizaje por Refuerzo

Planteamiento del Problema
La visión estándar en el Aprendizaje por Refuerzo (RL) trata las políticas como funciones estáticas que mapean estados a acciones, empleando una cantidad fija de computación independientemente de la complejidad de la decisión requerida. Este paradigma confunde el número de parámetros (memoria) con la cantidad de computación (tiempo). Si bien el escalado del recuento de parámetros (Ley de Moore) ha sido una estrategia común, la computación necesaria para tomar decisiones óptimas puede variar en órdenes de magnitud a través de diferentes estados. Las políticas masivas y estáticas suelen ser ineficientes, y las políticas computacionalmente limitadas pueden fallar al generalizar a tareas de horizonte largo, aprendiendo en su lugar heurísticas que se sobreajustan a las distribuciones de entrenamiento. El artículo aborda la falta de un lenguaje formal para distinguir entre computación y parámetros en RL e investiga si las políticas con parámetros fijos pueden beneficiarse de un tiempo de computación variable y aumentado.

Metodología
El artículo aborda el problema a través de dos lentes complementarias: formalización teórica y validación empírica.

1. Marco Teórico:

   • Los autores formalizan las políticas de RL como modelos de computación acotados utilizando máquinas de Turing.
   • Definen las políticas acotadas en el tiempo ($\Pi_t$) como aquellas implementables por una máquina de Turing que se detiene dentro de $t(|s|)$ pasos.
   • Introducen el Teorema de la Jerarquía de Políticas, demostrando que para funciones de construcción temporal $g(n) \in o(t(n)/\log t(n))$, existen Procesos de Decisión de Markov (MDPs) donde las políticas con presupuestos de computación más altos ($\Pi_t$) desempeñan arbitrariamente mejor que aquellas con presupuestos más bajos ($\Pi_g$).
   • Demuestran además el Teorema de Generalización de Horizonte Largo, demostrando que las políticas de baja computación pueden sobreajustarse a las tareas de entrenamiento (igualando la función de valor óptima en los datos de entrenamiento) pero fallan al generalizar a tareas de prueba de horizonte más largo, mientras que las políticas de alta computación pueden resolver estas tareas extendidas.

2. Propuesta Arquitectónica:

   • Para probar estas teorías, los autores proponen una arquitectura recurrente mínima llamada Unidad Recurrente de Interpolación (IRU).
   • La IRU es una variante simplificada de los bloques LSTM/GRU, que consiste en dos capas lineales (Olvido y Entrada) que interpolan entre el estado de celda anterior y una nueva computación local.
   • La arquitectura aplica este bloque $N$ veces durante un pase hacia adelante (pasos recurrentes), permitiendo a la política utilizar una cantidad variable de computación ($N$) mientras mantiene un recuento de parámetros fijo.
   • La red completa (IRU-$N$) incluye una capa lineal inicial, $N$ bloques recurrentes con conexiones de salto (skip connections) y una cabeza de salida final.

3. Configuración Experimental:

   • Los experimentos se realizaron en 31 tareas que abarcan dominios discretos (Boxpick, Lightsout) y continuos (OGBench), incluyendo entornos tanto de aprendizaje en línea (online) como fuera de línea (offline).
   • Los modelos de referencia (baselines) incluyeron Redes de Propagación hacia Adelante estándar (MLP) y Redes Residuales (ResNet). Crucialmente, la baseline de ResNet fue diseñada para tener una profundidad efectiva (computación) similar, pero significativamente más parámetros (hasta 5 veces más), mientras que la MLP tenía parámetros similares pero menos computación.
   • El estudio evaluó el rendimiento en tareas de entrenamiento y, críticamente, en tareas de prueba de horizonte más largo no vistas para medir la generalización.

Contribuciones Clave

• Formalización de Políticas Acotadas por Computación: El artículo proporciona la primera prueba formal de que aumentar el tiempo de computación (distinto del recuento de parámetros) permite a las políticas resolver problemas y generalizar a horizontes más largos que son teóricamente imposibles para políticas de menor computación.
• Arquitectura Recurrente Mínima: La introducción de la IRU, una arquitectura ligera capaz de escalar la computación mediante pasos recurrentes sin aumentar el recuento de parámetros.
• Métrica del Valor de la Computación: Una medida numérica propuesta, el Valor de la Computación (VoC), análoga al Valor de la Información en POMDPs. Esta métrica estima la ganancia o pérdida en el valor cuando un agente aumenta temporalmente su presupuesto de computación para un número específico de pasos.
• Desacoplamiento de Computación y Parámetros: Evidencia empírica que muestra que las mejoras en el rendimiento provienen de un aumento en la expresividad (computación) más que de un simple aumento en la capacidad del modelo (parámetros).

Resultos

• Escalado de Rendimiento: En entornos tanto discretos como continuos, aumentar el número de pasos recurrentes ($N$) de 1 a 10 mejoró significativamente las tasas de éxito. En tareas desafiantes como Boxpick y OGBench, el rendimiento aumentó hasta 10 veces.
• Generalización: Las políticas IRU entrenadas en tareas de horizonte corto generalizaron significativamente mejor a tareas de horizonte largo no vistas en comparación con MLPs y ResNets. Notablemente, la IRU superó a las ResNets con 5 veces más parámetros en las tareas de evaluación de horizonte largo.
• Eficiencia de Muestreo: Las arquitecturas IRU demostraron una mayor eficiencia de muestreo, convergiendo a un rendimiento asintótico más alto con menos pasos del entorno.
• Fuente de Mejora: Los experimentos "yoked" (entrenar a un agente pasivo con datos recolectados por un agente activo) revelaron que el beneficio principal de la computación adicional proviene de la expresividad de la política (su capacidad para aprender soluciones complejas a partir de los datos) más que de una mejora en la exploración o la calidad de los datos. El agente pasivo entrenado con datos de un agente activo de baja computación se desempeñó pobremente a menos que este mismo utilizara alta computación.
• Ablación: La arquitectura IRU superó a las LSTMs estándar y a las Redes Residuales Recurrentes en términos de velocidad y eficiencia de parámetros, lo que sugiere que los mecanismos de compuerta específicos son necesarios para aprovechar eficazmente los beneficios de la computación adicional.

Significancia y Reivindicaciones
El artículo afirma cambiar la perspectiva del RL de una aproximación de función estática a una visión computacional donde el tiempo y la memoria son ejes distintos. Los autores argumentan que:

1. La computación es un recurso distinto: Aumentar el tiempo de computación puede mejorar la prueba el rendimiento y la generalización sin aumentar el tamaño de la clase de hipótesis (parámetros), evitando así los problemas de sobreajuste asociados con modelos estáticos más grandes.
2. Generalización vía Iteración: La computación iterativa permite a las políticas aprender soluciones algorítmicas que se extrapolan a horizontes más largos, un fenómeno observado en los modelos de lenguaje pero poco explorado anteriormente en RL sin pre-entrenamiento o currículos multitarea.
3. Limitaciones de las Visiones Estáticas: Los resultados sugieren que los supuestos estándar de los MDP (por ejemplo, la existencia de una política óptima determinista) pueden no cumplirse bajo restricciones computacionales, lo que podría explicar por qué las políticas no markovianas son a veces necesarias incluso en tareas totalmente observadas.

Los autores concluyen que, si bien su trabajo utiliza una arquitectura mínima para aislar estos efectos, los hallazgos sugieren que los futuros sistemas de RL deberían considerar estrategias de computación adaptativa, donde la cantidad de computación se escala dinámicamente según la dificultad del estado actual.