Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

Resumen Técnico: Aprendizaje por Refuerzo con Preferencias de Pares en Problemas de Decisión a Largo Plazo

Definición del Problema
El aprendizaje por refuerzo (RL) tradicional formula los objetivos como la maximización del valor esperado de una función de recompensa escalar dentro de un Proceso de Decisión de Markov (MDP). Sin embargo, en muchas aplicaciones, como el ajuste fino de modelos de lenguaje extensos (LLMs), especificar preferencias de pares (por ejemplo, "la trayectoria A es mejor que la trayectoria B") es a menudo más natural y factible que definir una recompensa escalar. Los métodos existentes para el RL con preferencias de pares suelen inferir una función de recompensa u optimizar directamente para las preferencias, pero sufren de dos limitaciones críticas:

1. Dependen de horizontes temporales finitos y fijos, lo cual es poco práctico para problemas de decisión a largo plazo donde los agentes no terminan en un paso determinado.
2. Carecen de garantías teóricas de que las políticas de Markov estacionarias sean óptimas en relación con las políticas dependientes de la historia, un pilar fundamental de la teoría estándar de los MDP.

Además, los enfoques estándar a menudo no logran capturar las preferencias no transitivas (por ejemplo, la paradoja de Condorcet), donde la preferencia agregada de un grupo o una evaluación de múltiples características no forma un orden transitivo.

Metodología: Concursos de Decisión de Markov (MDC)
Los autores proponen un nuevo modelo de problema llamado Concurso de Decisión de Markov (MDC) para abordar estas brechas. Un MDC se define por un entorno finito $(S, A, P, \mu)$ y un margen de preferencia de Markov $M: (S \times A) \times (S \times A) \to \mathbb{R}$. El objetivo es encontrar una política $\pi$ que maximice el margen de preferencia promedio contra cualquier otra política $\pi'$, formulado como un juego de suma cero:
$$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$$
donde $x_\pi$ representa la medida de frecuencia de estado-acción promedio límite (medida de ocupación).

Para asegurar la tractabilidad teórica en entornos de horizonte infinito, los autores asumen que la función de probabilidad de transición es unichain (de cadena única) y aperiódica. Bajo estas condiciones, establecen que el conjunto de medidas de ocupación para las políticas dependientes de la historia es equivalente a la envolvente convexa de las medidas de ocupación de las políticas deterministas estacionarias.

Contribuciones Clave

1. Optimalidad de las Políticas Estacionarias: El artículo demuestra que, dentro de los MDC unichain finitos, una política aleatorizada estacionaria es óptima entre todas las políticas dependientes de la historia. Esto justifica restringir el espacio de búsqueda a políticas de Markov, cerrando una brecha entre la teoría y la práctica.
2. Complejidad Computacional: Los autores demuestran que resolver un MDC de forma exacta está en P (tiempo polinomial). Específicamente, construyen un programa lineal con $|S||A| + |S| + 1$ variables y $2|S||A| + |S| + 1$ restricciones. Esta complejidad es comparable a la de los MDP de recompensa promedio estándar, a pesar de que los MDC son una generalización estricta que admite preferencias no transitivas.
3. Iteración de Política con Cobertura (Hedged Policy Iteration - HPI): Se introduce un algoritmo iterativo aproximado, Hedged Policy Iteration (HPI). Este utiliza el algoritmo Hedge para actualizar las reglas de decisión basadas en "valores marginales" (márgenes de preferencia acumulados).
   • Convergencia: HPI converge a una política óptima a una tasa sublineal de $O(1/\sqrt{K})$, donde $K$ es el número de iteraciones.
   • Escalabilidad: Los autores derivan una forma de gradiente de política de HPI y una implementación de aprendizaje profundo (Algoritmo 3) que utiliza buffers y aproximaciones de funciones de valor, lo que lo hace adecuado para entornos de alta dimensionalidad.

Resultados Experimentales
Los autores evaluaron HPI y una variante recortada (HPI-Clip) frente a Self-Play Preference Optimization (SPPO) (Swamy et al., 2024) en 13 tareas de alta dimensionalidad con horizontes temporales largos (2048 pasos) utilizando la suite Mujoco-v5.

• Configuración: Las tareas incluyeron problemas estándar de control continuo (donde las preferencias se derivaron de diferencias de recompensa) y tareas "Mujoco-NT" que presentan márgenes de preferencia explícitamente no transitivos (por ejemplo, reglas de los dos mejores de tres).
• Rendimiento: En 12 de las 13 tareas, HPI e HPI-Clip demostraron una eficiencia de aprendizaje significativamente mayor (medida por el Área Bajo la Curva del retorno episódico o la brecha de optimalidad invertida) en comparación con SPPO.
• Ablación: Los resultados se mantuvieron incluso cuando los modelos de preferencia se aprendieron a partir de datos offline.

Significancia y Reivindicaciones
El artículo afirma que el aprendizaje por refuerzo con preferencias de pares en problemas de decisión a largo plazo es más tratable de lo que se pensaba. Al introducir el modelo MDC, los autores proporcionan un marco donde:

• Las políticas estacionarias son teóricamente suficientes, eliminando la necesidad de estrategias complejas dependientes de la historia.
• El problema sigue siendo computacionalmente eficiente (en P), incluso con preferencias no transitivas.
• Los algoritmos prácticos (HPI) escalan a problemas de alta dimensionalidad y largo horizonte, superando a los métodos de vanguardia actuales.

Los autores señalan que, si bien estos resultados son prometedores para aplicaciones como los LLMs en tareas de largo horizonte, se requiere mayor investigación para determinar cuándo el aprendizaje de márgenes de preferencia supera al aprendizaje basado en recompensas y con qué eficacia estos métodos alinean los modelos de lenguaje en la práctica. El trabajo tiene como objetivo acercar la teoría y la práctica del RL con preferencias de pares.