Q-learning aún no es escalable

• El RL ha logrado grandes avances en Go, ajedrez y el posentrenamiento de LLM, pero la mayoría depende de RL on-policy, que requiere nuevos rollouts, por lo que sus condiciones son distintas de las del RL off-policy, que reutiliza libremente datos anteriores
• Q-learning, un representante del RL off-policy, tiene alta eficiencia de muestras, pero aún no escala lo suficiente en tareas de largo plazo que requieren más de 100 pasos de decisión significativos
• El cuello de botella es que los targets de bootstrap sesgados del aprendizaje TD se acumulan a medida que se alarga el horizonte, una restricción distinta de la predicción del siguiente token, los modelos de difusión y el aprendizaje contrastivo
• En experimentos con OGBench, flow BC, IQL, CRL y SAC+BC no lograron resolver todas las tareas de largo plazo ni siquiera con un dataset de 1B, 1000 veces más grande que los datasets típicos de RL offline, y su rendimiento se estancó por debajo del nivel óptimo
• La reducción del horizonte, como n-step returns y RL jerárquico, mejoró la escalabilidad y el rendimiento final, pero las técnicas actuales solo alivian el problema por un factor constante y no alcanzan para resolver tareas de largo plazo arbitrariamente complejas

---

Estado actual de la escalabilidad del RL

• La predicción del siguiente token, denoising diffusion y el aprendizaje contrastivo demostraron ser funciones objetivo escalables con datos masivos y modelos de miles de millones de parámetros
• El RL también alcanzó rendimiento sobrehumano en Go y ajedrez, y en los LLM está resolviendo tareas complejas de razonamiento como matemáticas y programación
• Sin embargo, la mayoría de los casos de éxito reales actuales se basan en algoritmos de RL on-policy
  • Ejemplos representativos: REINFORCE, PPO, GRPO, entre otros
  • Siempre requieren rollouts muestreados de nuevo desde la política actual
  • No pueden reutilizar datos anteriores
  • Los métodos tipo PPO pueden reutilizar datos de forma limitada, pero según clasificaciones como la documentación de OpenAI se consideran RL on-policy
• En entornos donde se pueden generar muchos rollouts a bajo costo, como juegos de mesa o LLM, esta restricción puede no ser un gran problema
• En robótica, generar en el mundo real la cantidad de muestras usada para posentrenar modelos de lenguaje con RL toma meses o más, y durante el entrenamiento una persona debe estar junto al robot las 24 horas para reiniciarlo

RL off-policy y Q-learning

• En principio, el RL off-policy puede usar datos recolectados en cualquier momento y de cualquier manera
• Como puede reutilizar los mismos datos varias veces, por lo general tiene mejor eficiencia de muestras
• También existen casos en los que se entrenó a un robot perro desde cero para caminar en 20 minutos en un entorno real
  • Caso relacionado: walk in the park
• Q-learning es el algoritmo de RL off-policy más usado
• La mayoría de los algoritmos prácticos de RL off-policy model-free se basan en variantes de la pérdida TD
• Para aplicar RL a más problemas reales, la pregunta clave pasa a ser: “¿Q-learning, es decir, TD learning, es escalable?”
• Si lo fuera, permitiría resolver de forma eficiente tareas reales más diversas y complejas, como robótica y agentes que usan computadoras

Qué significa “escalable”: profundidad, no amplitud

• Aquí, escalabilidad significa la capacidad de resolver problemas más difíciles y de horizonte más largo cuando se agregan datos con cobertura suficiente, cómputo y tiempo
• Esto es distinto de la capacidad de resolver una mayor cantidad de tareas con un solo modelo
  • Que aumente el número de tareas no significa necesariamente que se estén resolviendo tareas más difíciles
  • Varios estudios de scaling existentes muestran la posibilidad de este eje de “amplitud”
• El eje más importante y difícil es la profundidad
  • Porque exige capacidades de toma de decisiones más avanzadas
• Q-learning, en su forma actual, no es altamente escalable en el eje de profundidad
• Para escalar Q-learning y el RL off-policy a problemas complejos de largo plazo, hace falta un avance algorítmico

Q-learning, ausente en los grandes casos de éxito del RL

• Muchos éxitos reales del RL se basan en métodos distintos al Q-learning basado en TD
• AlphaGo, AlphaZero y MuZero usan RL basado en modelos y Monte Carlo tree search, y no usan TD learning en juegos de mesa
  • Referencia: página 15 del paper de MuZero
• OpenAI Five logró rendimiento sobrehumano en Dota 2 con PPO
  • Referencia: nota al pie 6 del paper de OpenAI Five
• El RL para LLM hoy está dominado por familias de gradiente de política on-policy como PPO y GRPO
• No se presentan casos reales en los que el RL off-policy, especialmente el TD learning de 1 paso, haya tenido éxito a una escala similar a AlphaGo o los LLM
• Esta evaluación no busca negar el RL off-policy, sino más bien señalar la necesidad de más investigación en algoritmos de RL

Por qué Q-learning flaquea en tareas de largo plazo

• La pérdida TD de Q-learning aprende a ajustar el valor Q actual a un target compuesto por la recompensa más el máximo valor Q del siguiente estado
• Ese target es un target de bootstrap sesgado, que puede no coincidir con el verdadero valor Q óptimo
• La razón central por la que Q-learning tiene dificultades para escalar es que el sesgo del target de predicción se acumula a lo largo del horizonte
• Esta acumulación de sesgo funciona como una limitación fundamental del TD learning
  • Las funciones objetivo como predicción del siguiente token, denoising diffusion y aprendizaje contrastivo no tienen este sesgo en el target de predicción
  • BYOL y DINO, aunque tengan sesgo, no lo acumulan a lo largo de un horizonte
• A medida que el problema se vuelve más complejo y el horizonte se alarga, el sesgo de los targets de bootstrap se acumula con más fuerza
• Es difícil aliviar este problema solo con más datos y modelos más grandes
• De hecho, una de las razones principales por las que casi no se usan factores de descuento más altos, como (\gamma > 0.999), está relacionada con esto
• Los métodos de gradiente de política sufren relativamente menos este problema
  • Los métodos on-policy de estimación de valor como GAE manejan horizontes largos con relativa facilidad, aunque acepten mayor varianza
  • No están atados a una recursión estricta de 1 paso

Experimentos de escalabilidad basados en OGBench

• El paper reciente Horizon Reduction Makes RL Scalable verifica la hipótesis anterior con diversos estudios de scaling controlados
• El objetivo es comprobar si los métodos actuales de RL off-policy pueden resolver tareas muy difíciles solo aumentando los datos y el cómputo
• En los experimentos se usan tareas complejas y antes no resueltas de OGBench
• Los requisitos de las tareas son los siguientes
  • El agente debe aprender conductas complejas de goal-reaching a partir de demos aleatorias no estructuradas de estilo play
  • En test, debe realizar manipulación precisa, resolución combinatoria de puzzles y navegación de largo plazo
  • Las tareas se desarrollan a lo largo de 1,000 environment steps
• Los experimentos están diseñados para reducir variables de confusión
  • Se recolectan datos casi infinitos, suficientes para que el overfitting sea prácticamente imposible
  • Se enfocan en RL offline para eliminar el problema de exploración
  • Se garantiza que el dataset tenga cobertura suficiente y que todas las tareas puedan resolverse con el dataset dado
  • Para reducir la carga del aprendizaje de representaciones, se entregan directamente observaciones de estado ground-truth
• Si Q-learning no escala incluso en este entorno controlado, sus probabilidades son aún menores en entornos reales con datos limitados y observaciones ruidosas

Resultados de algoritmos estándar de RL offline

• Los algoritmos estándar y ampliamente usados de RL offline no resuelven todas las tareas
• Los algoritmos evaluados son flow BC, IQL, CRL y SAC+BC
• Los experimentos también se realizaron con un dataset de tamaño 1B
  • Esto es (1000 \times) más grande que un dataset típico de RL offline
• Más importante aún, el rendimiento a menudo llegó a una meseta en niveles muy por debajo del rendimiento óptimo
• Varias ablaciones y experimentos de control, como modelos más grandes, entrenamientos más largos y otros hiperparámetros, tampoco tuvieron efecto
• El único enfoque que funcionó como excepción fue la reducción del horizonte

Mejoras logradas por la reducción del horizonte

• La hipótesis anterior es que el horizonte y la acumulación de sesgo asociada son el principal obstáculo para escalar el RL off-policy
• Para verificarlo, se probaron varias técnicas de reducción del horizonte que reducen el número de backups TD sesgados
  • Ejemplos: n-step returns, RL jerárquico, entre otros
• Los resultados fueron positivos
  • Incluso técnicas simples como n-step returns mejoraron notablemente la escalabilidad y el rendimiento final
  • No fueron solo un trick para acelerar el entrenamiento: también mejoraron el rendimiento asintótico
  • Los métodos jerárquicos completos funcionaron mejor
• En todos los experimentos, la única técnica que funcionó de manera consistente fue la reducción del horizonte
• Simplemente aumentar datos y cómputo no alcanza para resolver la maldición del horizonte
• Se necesitan mejores algoritmos que apunten directamente a este problema

Rumbo a una función objetivo de RL off-policy escalable

• La reducción del horizonte abre la puerta a la escalabilidad de Q-learning, pero las técnicas actuales no resuelven el problema de raíz
• Los métodos actuales, como n-step returns y RL jerárquico, en su mayoría alivian el problema por un factor constante
• Todavía faltan algoritmos de RL off-policy que escalen a problemas de largo plazo arbitrariamente complejos
• Las posibles líneas de investigación se resumen en tres
  • Encontrar estructuras jerárquicas recursivas simples y escalables que vayan más allá de jerarquías de 2 niveles para manejar horizontes de longitud arbitraria
  • Dado que el aprendizaje de modelos es aprendizaje supervisado y el RL on-policy también es escalable, un enfoque de RL basado en modelos que primero aprenda un modelo y luego ejecute RL on-policy dentro de ese modelo
  • Evitar por completo el TD learning
    • Por ejemplo, quasimetric RL se basa en la formulación LP del RL
    • También se puede probar si métodos basados en MC como contrastive RL escalan mejor que los enfoques basados en TD
• La configuración experimental anterior puede servir como punto de partida para probar estas ideas
  • Ya están diseñadas tareas robóticas complejas y datasets
  • Se verificó que las tareas pueden resolverse con los datos dados
  • Se puede hacer que las tareas sean arbitrariamente más difíciles agregando más cubos, para hacer stress test de la escalabilidad de los algoritmos de forma controlada
  • Código publicado: horizon-reduction

[GN⁺]

Opiniones en Hacker News

• Creo que este artículo pasa por alto una razón más grande por la que Q-learning es difícil de escalar
  A medida que el horizonte se alarga, la cantidad de estados posibles suele crecer exponencialmente, y para aprender una Q que pueda manejar esos estados, los datos también tienen que crecer exponencialmente
  En el aprendizaje on-policy este problema es menor, porque lo importante son solo los estados cercanos a la política actual y, en la práctica, solo se muestrean esos estados

  • Creo que el análisis del artículo sobre el sesgo de sobreestimación es correcto
    La clave es que, por la operación max de Q-learning, el ruido se amplifica con el paso de los pasos temporales, y técnicas para mitigar el sesgo como https://arxiv.org/abs/1509.06461 han logrado mejorar el rendimiento de agentes de aprendizaje por refuerzo
    Según la investigación, este fenómeno aparece con más fuerza en estados que la red no ha visitado mucho
    Que la cantidad de estados sea exponencialmente grande solo es decisivo cuando no hay patrones entre esos estados. Si existe una estructura aprendible, puede funcionar bien, y eso no es una debilidad del deep learning, sino una fortaleza
    La cuestión es definir el objetivo de aprendizaje correcto, y el artículo básicamente sostiene que Q-learning no es ese objetivo
    También me pregunto si el aprendizaje por refuerzo basado en modelos como MuZero podría ser una solución a las preocupaciones del autor. MuZero puede mejorar la eficiencia de aprendizaje reanalizando trayectorias anteriores, y la búsqueda en árbol de Monte Carlo (MCTS) es una forma principiada de reducir el horizonte desplegando el modelo varios pasos
    La operación max de MCTS también puede crear problemas similares, pero el proceso de profundizar la búsqueda podría compensarlos
  • Quizás este hilo ayude: https://news.ycombinator.com/item?id=44280505
    Desde una postura de completo no experto, me pregunto si algunas tareas, aunque sean “profundas”, no serán lo suficientemente “uniformes” como para que basten muestras malas. A ese tipo de tareas me gustaría llamarlas tareas ergódicas
    Por supuesto, seguramente también haya tareas que no sean así
  • ¿Esta diferencia es esencialmente la misma que entre la integración de Monte Carlo con una grilla regular y la integración de Monte Carlo con muestreo por importancia?

• Este paper ya asume que uno sabe bastante de aprendizaje por refuerzo
  Si quieres meterte en serio en aprendizaje por refuerzo, las clases introductorias de David Silver (DeepMind) son excelentes: https://youtu.be/2pWv7GOvuf0?si=CmFJHNnNqraL5i0s

• Totalmente de acuerdo, y me parece un muy buen resumen
  En muy pocas palabras, el problema es perseguir un objetivo móvil, y ese objetivo cambia según cómo me mueva yo
  En el aprendizaje por refuerzo basado en valores no hay una respuesta real a la cual converger. Es como minimizar una diferencia en la que ambos lados de la ecuación contienen tu propia aproximación
  Aun así, no lo veo como algo desesperado. Creo que el aprendizaje por refuerzo estuvo muy cerca de funcionar; lo que faltaba hasta ahora era un modelo del mundo / función de dinámica hacia adelante confiable
  Con eso, puedes planear sin explorar, y ahora ya tenemos ese tipo de modelos

• El beneficio del aprendizaje off-policy está fundamentalmente limitado por el hecho de que los datos ineficientes generados durante la exploración inicial no son muy útiles más adelante para mejorar políticas más refinadas
  Esto se vuelve evidente si uno piensa en errores de ajedrez, movimientos espasmódicos o intentos fallidos de resolver un rompecabezas
  Se vuelve aún más claro cuando te das cuenta de que los datos son off-policy solo cuando describen algo que la política actual no haría
  Creo que la solución a este problema, por desgracia, tiene que ver con necesitar mejor generalización y mayor eficiencia muestral

  • ¿Esta afirmación no prueba demasiado?
    ¿Cómo se explica el perro que aprendió a caminar en 20 minutos con aprendizaje off-policy citado? ¿O estás planteando algo más sutil?

• Me sorprende que falten Decision Transformer o Trajectory Transformer
  Ambos son enfoques offline y, gracias al mecanismo de atención, suelen funcionar bastante bien en tareas de horizonte largo al esquivar el problema de asignación de crédito
  La mayoría de los investigadores de aprendizaje por refuerzo no consideran estos enfoques como “aprendizaje por refuerzo real”, porque no pueden asignar crédito más allá de la ventana de contexto y por eso no pueden aprender tareas de horizonte infinito
  Pero si hay ventanas de contexto de más de 1 millón de tokens, ¿quizás en la práctica eso sea un problema menor? Me interesa saber qué piensan otros
  DT: https://arxiv.org/abs/2106.01345
  TT: https://arxiv.org/abs/2106.02039

  • TFP cita a Decision Transformer
    El solo hecho de usar Transformer no esquiva el problema de asignación de crédito
    Transformer es una arquitectura para resolver problemas de modelado secuencial, y el problema de asignación de crédito que aparece en aprendizaje por refuerzo es un ejemplo de ese tipo de problema. Antes ya hubo muchas arquitecturas de este estilo
    Que el problema de asignación de crédito sea difícil es una afirmación sobre la escasez de datos. No se puede “esquivar” solo eligiendo una arquitectura

• Los humanos en realidad hacemos ambas cosas
  Aprendemos tanto on-policy, explorando las consecuencias de nuestras propias acciones, como off-policy, por ejemplo a partir de demostraciones de expertos
  La diferencia es que los humanos podemos distinguir entre buenas y malas acciones, y filtrar para aprender solo de las acciones que juzgamos buenas
  En la mayoría del aprendizaje por refuerzo off-policy también entran muchas malas acciones, y al quedar incluidas en el conjunto de entrenamiento, ralentizan el aprendizaje

  • “Poder distinguir entre buenas y malas acciones” no siempre es cierto
    Por eso algunas demostraciones de expertos son atractivas. Puedes ver que producen mejores resultados aunque, vistas como “mejores prácticas” de nivel principiante, sean formas completamente equivocadas de hacer las cosas
    Claro que, a veces, eso solo significa que si eres tan bueno puedes permitirte esas técnicas o errores

• Vale la pena señalar que las tareas de horizonte largo que los humanos aprenden mediante práctica repetida se aprenden dividiéndolas en tareas de horizonte más corto y luego componiéndolas jerárquicamente

  • Quizás sea una idea ingenua, pero esto parece más un problema de enfoque que de algoritmo
    Puede que un modelo no pueda manejar tareas de horizonte largo desde el principio, pero primero puede aprender habilidades de horizonte corto y luego usar esos pequeños paquetes de habilidades para aprender horizontes más largos
    Es lo mismo que el chunking que hacemos todos
    Nadie aprende a pilotear un avión comercial a través de un continente como una secuencia de micromovimientos de manos y brazos
    De niño aprendes a levantar una pelota de esa manera, pero volar o practicar deportes se compone de jerarquías de habilidades aprendidas y planificación

• Me gusta el artículo, pero creo que al usar siglas sin explicación perdió la oportunidad de ser útil para un público más amplio
  Es un detalle menor, pero estaría bien explicar las siglas y la jerga técnica

  • Para artículos con muy buen contenido pero poca accesibilidad porque asumen muchísimo conocimiento previo, resulta bastante útil pedirle a una herramienta de IA que los explique y simplifique
    Acabo de hacerlo con el nuevo navegador Dia y funcionó bien. También puedes copiar y pegar en tu proveedor de modelos preferido
    Así el artículo se mantiene conciso, mientras puedes hacer preguntas y aclarar cosas con una herramienta de IA
  • Viendo que la conclusión es “que alguien haga un método de Q-learning escalable”, claramente está dirigido a otros investigadores de aprendizaje por refuerzo

• Lo mágico de las técnicas off-policy como Q-Learning es que convergen al resultado óptimo aunque solo vean datos de entrenamiento no óptimos
  Por ejemplo, incluso si usas como entrada para Q-Learning un dataset de partidas de ajedrez de agentes que se mueven de forma completamente aleatoria, sin ninguna estrategia, eventualmente convergerá a la política óptima; solo será más lento que si tuviera entradas de alta calidad

  • Si eso es cierto, creo que se acerca a la definición de que la tarea es ergódica
    Puede que esté usando el término de forma un poco retorcida, pero creo que también existen tareas no ergódicas