En esta publicación, presentaré un algoritmo de aprendizaje por refuerzo (RL) basado en un paradigma “alternativo”: divide y vencerás. A diferencia de los métodos tradicionales, este algoritmo no se basa en el aprendizaje de diferencias temporales (TD) (que presenta desafíos de escalabilidad) y se adapta bien a tareas de largo horizonte.
Podemos hacer aprendizaje por refuerzo (RL) basado en dividir y conquistar, en lugar de aprendizaje por diferencia temporal (TD).
Solución de problemas: RL fuera de política
Nuestro problema está fuera de la política RL. Repasemos brevemente lo que esto significa.
Hay dos clases de algoritmos en RL: RL dentro de la política y RL fuera de la política. RL según la política significa que solo podemos utilizar datos nuevos recopilados según la política actual. En otras palabras, tenemos que desechar datos antiguos cada vez que actualizamos la política. Algoritmos como PPO y GRPO (y los métodos de gradiente de políticas en general) pertenecen a esta categoría.
RL fuera de política significa que no tenemos esta restricción: podemos usar cualquier tipo de datos, incluidas experiencias antiguas, demostraciones humanas, datos de Internet, etc. Por lo tanto, la RL fuera de las políticas es más general y flexible que la RL dentro de las políticas (¡y por supuesto, más difícil!). Q-learning es el algoritmo RL fuera de políticas más conocido. En ámbitos donde la recopilación de datos es costosa (por ejemplo, robótica, sistemas de diálogo, atención médica, etc.), a menudo no tenemos más remedio que utilizar RL fuera de las políticas. Por eso es un problema tan importante.
A partir de 2025, creo que tenemos recetas razonablemente buenas para ampliar la RL basada en políticas (por ejemplo, PPO, GRPO y sus variantes). Sin embargo, todavía no hemos encontrado un algoritmo RL fuera de políticas “escalable” que se adapte bien a tareas complejas y de largo plazo. Déjame explicarte brevemente por qué.
Dos paradigmas en el aprendizaje de valores: Diferencia Temporal (TD) y Monte Carlo (MC)
En RL fuera de políticas, normalmente entrenamos una función de valor utilizando el aprendizaje de diferencia temporal (TD) (es decir, Q-learning), con la siguiente regla de actualización de Bellman:
\[\begin{aligned} Q(s, a) \gets r + \gamma \max_{a’} Q(s’, a’), \end{aligned}\]
El problema es este: el error en el siguiente valor $Q(s’, a’)$ se propaga al valor actual $Q(s, a)$ mediante arranque, y estos errores se acumulan en todo el horizonte. Esto es básicamente lo que hace que TD Learning tenga dificultades para escalar a tareas de largo plazo (consulte esta publicación si está interesado en más detalles).
Para mitigar este problema, la gente ha combinado el aprendizaje TD con los rendimientos Monte Carlo (MC). Por ejemplo, podemos hacer un aprendizaje TD de $n$ pasos (TD-$n$):
\[\begin{aligned} Q(s_t, a_t) \gets \sum_{i=0}^{n-1} \gamma^i r_{t+i} + \gamma^n \max_{a’} Q(s_{t+n}, a’). \end{aligned}\]
Aquí, usamos el retorno real de Monte Carlo (del conjunto de datos) para los primeros $n$ pasos y luego usamos el valor de arranque para el resto del horizonte. De esta manera, podemos reducir el número de recursiones de Bellman $n$ veces, por lo que los errores se acumulan menos. En el caso extremo de $n = \infty$, recuperamos el aprendizaje de valores puro de Monte Carlo.
Si bien ésta es una solución razonable (y a menudo funciona bien), es muy insatisfactoria. Primero, no resuelve fundamentalmente el problema de acumulación de errores; solo reduce el número de recursiones de Bellman por un factor constante ($n$). En segundo lugar, a medida que $n$ crece, sufrimos una alta varianza y una suboptimidad. Por lo tanto, no podemos simplemente establecer $n$ en un valor grande y debemos ajustarlo cuidadosamente para cada tarea.
¿Existe una forma fundamentalmente diferente de resolver este problema?
El “tercer” paradigma: divide y vencerás
Mi afirmación es que un tercer paradigma en el aprendizaje de valores, dividir y conquistar, puede proporcionar una solución ideal para la RL fuera de las políticas que se amplíe a tareas arbitrariamente de largo plazo.
Divide y vencerás reduce el número de recursiones de Bellman de forma logarítmica.
La idea clave de divide y vencerás es dividir una trayectoria en dos segmentos de igual longitud y combinar sus valores para actualizar el valor de la trayectoria completa. De esta manera, podemos (en teoría) reducir el número de recursiones de Bellman de forma logarítmica (¡no linealmente!). Además, no requiere elegir un hiperparámetro como $n$, y no necesariamente sufre de una alta varianza o subóptima, a diferencia del aprendizaje TD de $n$ pasos.
Conceptualmente, dividir y conquistar realmente tiene todas las buenas propiedades que queremos en el aprendizaje de valores. Por eso hace tiempo que estoy entusiasmado con esta idea de alto nivel. El problema era que no estaba claro cómo hacer esto en la práctica… hasta hace poco.
Un algoritmo práctico
En un trabajo reciente codirigido con Aditya, logramos avances significativos hacia la realización y ampliación de esta idea. Específicamente, pudimos ampliar el aprendizaje de valores de divide y vencerás a tareas altamente complejas (hasta donde yo sé, ¡este es el primer trabajo de este tipo!), al menos en una clase importante de problemas de RL, la RL condicionada por objetivos. La RL condicionada por objetivos tiene como objetivo aprender una política que pueda llegar a cualquier estado desde cualquier otro estado. Esto proporciona una estructura natural de divide y vencerás. Déjame explicarte esto.
La estructura es la siguiente. Primero supongamos que la dinámica es determinista y denotemos la distancia del camino más corto (“distancia temporal”) entre dos estados $s$ y $g$ como $d^*(s, g)$. Entonces, satisface la desigualdad del triángulo:
\[\begin{aligned} d^*(s, g) \leq d^*(s, w) + d^*(w, g) \end{aligned}\]
para todos los $s, g, w \in \mathcal{S}$.
En términos de valores, podemos traducir de manera equivalente esta desigualdad triangular a la siguiente regla de actualización de Bellman “transitiva”:
\[\begin{aligned}
V(s, g) \gets \begin{cases}
\gamma^0 & \text{if } s = g, \\\\
\gamma^1 & \text{if } (s, g) \in \mathcal{E}, \\\\
\max_{w \in \mathcal{S}} V(s, w)V(w, g) & \text{otherwise}
\end{cases}
\end{aligned}\]
donde $\mathcal{E}$ es el conjunto de aristas en el gráfico de transición del entorno, y $V$ es la función de valor asociada con la recompensa escasa $r(s, g) = 1(s = g)$. Intuitivamente, esto significa que podemos actualizar el valor de $V(s, g)$ usando dos valores “más pequeños”: $V(s, w)$ y $V(w, g)$, siempre que $w$ sea el “punto medio” óptimo (subobjetivo) en el camino más corto. ¡Esta es exactamente la regla de actualización de valor de divide y vencerás que estábamos buscando!
el problema
Sin embargo, hay un problema aquí. El problema es que no está claro cómo elegir el subobjetivo óptimo $w$ en la práctica. En configuraciones tabulares, podemos simplemente enumerar todos los estados para encontrar el $w$ óptimo (este es esencialmente el algoritmo de ruta más corta de Floyd-Warshall). Pero en entornos continuos con grandes espacios de estado, no podemos hacer esto. Básicamente, esta es la razón por la que trabajos anteriores han luchado por ampliar el aprendizaje de valores de divide y vencerás, a pesar de que esta idea ha existido durante décadas (de hecho, se remonta al primer trabajo sobre RL condicionado por objetivos de Kaelbling (1993); consulte nuestro artículo para obtener más información sobre trabajos relacionados). La principal contribución de nuestro trabajo es una solución práctica a este problema.
la solución
Aquí está nuestra idea clave: restringimos el espacio de búsqueda de $w$ a los estados que aparecen en el conjunto de datos, específicamente, aquellos que se encuentran entre $s$ y $g$ en la trayectoria del conjunto de datos. Además, en lugar de buscar el $\text{argmax}_w$ óptimo, calculamos un $\text{argmax}$ “suave” usando una regresión expectil. Es decir, minimizamos la siguiente pérdida:
\[\begin{aligned} \mathbb{E}\left[\ell^2_\kappa (V(s_i, s_j) – \bar{V}(s_i, s_k) \bar{V}(s_k, s_j))\right]\end{alineado}\]
donde $\bar{V}$ es la red de valor objetivo, $\ell^2_\kappa$ es la pérdida expectil con un $\kappa$ expectil, y la expectativa se toma sobre todas las tuplas $(s_i, s_k, s_j)$ con $i \leq k \leq j$ en una trayectoria de conjunto de datos muestreado aleatoriamente.
Esto tiene dos beneficios. Primero, no necesitamos buscar en todo el espacio estatal. En segundo lugar, evitamos la sobreestimación del valor del operador $\max$ utilizando en su lugar la regresión expectil “más suave”. A este algoritmo lo llamamos RL transitivo (TRL). ¡Consulte nuestro documento para obtener más detalles y más debates!
¿Funciona bien?
Su navegador no soporta la etiqueta de video.
laberinto humanoide
Su navegador no soporta la etiqueta de video.
rompecabezas
Para ver si nuestro método se adapta bien a tareas complejas, evaluamos directamente TRL en algunas de las tareas más desafiantes en OGBench, un punto de referencia para RL condicionado por objetivos fuera de línea. Utilizamos principalmente las versiones más difíciles de tareas de rompecabezas y laberintos humanoides con grandes conjuntos de datos de tamaño 1B. Estas tareas son muy desafiantes: requieren realizar habilidades combinatoriamente complejas en hasta 3000 pasos del entorno.
TRL logra el mejor rendimiento en tareas altamente desafiantes y de largo plazo.
¡Los resultados son bastante emocionantes! En comparación con muchas líneas de base sólidas en diferentes categorías (TD, MC, aprendizaje cuasimétrico, etc.), TRL logra el mejor rendimiento en la mayoría de las tareas.
TRL coincide con el mejor TD-$n$ ajustado individualmente, sin necesidad de configurar $\boldsymbol{n}$.
Esta es mi trama favorita. Comparamos TRL con el aprendizaje TD de $n$ pasos con diferentes valores de $n$, desde $1$ (TD puro) hasta $\infty$ (MC puro). El resultado es realmente bonito. ¡TRL coincide con el mejor TD-$n$ en todas las tareas, sin necesidad de configurar $\boldsymbol{n}$! Esto es exactamente lo que queríamos del paradigma de divide y vencerás. Al dividir recursivamente una trayectoria en otras más pequeñas, puede manejar naturalmente horizontes largos, sin tener que elegir arbitrariamente la longitud de los fragmentos de trayectoria.
El artículo tiene muchos experimentos, análisis y ablaciones adicionales. Si estás interesado, ¡consulta nuestro artículo!
¿Qué sigue?
En esta publicación, compartí algunos resultados prometedores de nuestro nuevo algoritmo de aprendizaje de valores de divide y vencerás, Transitive RL. Este es sólo el comienzo del viaje. Hay muchas preguntas abiertas y direcciones interesantes para explorar:
Quizás la pregunta más importante es cómo extender TRL a tareas de RL regulares basadas en recompensas más allá de la RL condicionada por objetivos. ¿Tendría la RL normal una estructura similar de divide y vencerás que podamos explotar? Soy bastante optimista al respecto, dado que es posible convertir cualquier tarea de RL basada en recompensas en una tarea condicionada por objetivos, al menos en teoría (consulte la página 40 de este libro).
Otro desafío importante es lidiar con entornos estocásticos. La versión actual de TRL asume una dinámica determinista, pero muchos entornos del mundo real son estocásticos, principalmente debido a una observabilidad parcial. Para ello, las desigualdades triangulares “estocásticas” podrían proporcionar algunas pistas.
En la práctica, creo que todavía hay mucho margen para mejorar aún más TRL. Por ejemplo, podemos encontrar mejores formas de elegir candidatos a subobjetivos (más allá de los de la misma trayectoria), reducir aún más los hiperparámetros, estabilizar aún más el entrenamiento y simplificar aún más el algoritmo.
En general, estoy muy entusiasmado con el potencial del paradigma de divide y vencerás. Sigo pensando que uno de los problemas más importantes en RL (e incluso en el aprendizaje automático) es encontrar un algoritmo RL escalable fuera de políticas. No sé cómo será la solución final, pero creo que divide y vencerás, o la toma de decisiones recursiva en general, es uno de los candidatos más fuertes hacia este santo grial (por cierto, creo que los otros contendientes fuertes son (1) RL basado en modelos y (2) aprendizaje TD con algunos trucos “mágicos”. De hecho, varios trabajos recientes en otros campos han mostrado la promesa de la recursividad y las estrategias de divide y vencerás, como los modelos de atajos, la atención log-lineal y los modelos de lenguaje recursivo (y, por supuesto, algoritmos clásicos como la clasificación rápida, los árboles de segmentos, FFT, etc.). ¡Espero ver más avances interesantes en la RL escalable fuera de políticas en el futuro cercano!
Expresiones de gratitud
Me gustaría agradecer a Kevin y Sergey por sus útiles comentarios sobre esta publicación.
Esta publicación apareció originalmente en el blog de Seohong Park.