Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

Resumo Técnico: Aprendizado por Reforço com Preferências Pareadas em Problemas de Decisão de Longo Prazo

Definição do Problema
O aprendizado por reforço (RL) tradicional formula objetivos como a maximização do valor esperado de uma função de recompensa escalar dentro de um Processo de Decisão de Markov (MDP). No entanto, em muitas aplicações, como o ajuste fino de grandes modelos de linguagem (LLMs), especificar preferências pareadas (por exemplo, "a trajetória A é melhor que a trajetória B") é frequentemente mais natural e viável do que definir uma recompensa escalar. Os métodos existentes para RL com preferências pareadas tipicamente inferem uma função de recompensa ou otimizam diretamente as preferências, mas sofrem de duas limitações críticas:

1. Eles dependem de horizontes temporais finitos e fixos, o que é impraticável para problemas de decisão de longo prazo onde os agentes não terminam em um passo fixo.
2. Eles carecem de garantias teóricas de que políticas de Markov estacionárias são ótimas em relação a políticas dependentes de histórico, um pilar da teoria padrão de MDPs.

Além disso, abordagens padrão frequentemente falham em capturar preferências não transitivas (por exemplo, o paradoxo de Condorcet), onde a preferência agregada de um grupo ou uma avaliação de múltiplos atributos não forma uma ordenação transitiva.

Metodologia: Concursos de Decisão de Markov (MDCs)
Os autores propõem um novo modelo de problema chamado Concurso de Decisão de Markov (MDC) para preencher essas lacunas. Um MDC é definido por um ambiente finito $(S, A, P, \mu)$ e uma margem de preferência de Markov $M: (S \times A) \times (S \times A) \to \mathbb{R}$. O objetivo é encontrar uma política $\pi$ que maximize a margem de preferência média contra qualquer outra política $\pi'$, formulado como um jogo de soma zero:
$$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$$
onde $x_\pi$ representa a frequência de estado-ação de ocupação média limite (medida de ocupação).

Para garantir a tratabilidade teórica em cenários de horizonte infinito, os autores assumem que a função de probabilidade de transição é unichain e aperiódica. Sob estas condições, eles estabelecem que o conjunto de medidas de ocupação para políticas dependentes de histórico é equivalente ao invólucro convexo das medidas de ocupação para políticas determinísticas estacionárias.

Principais Contribuições

1. Otimalidade de Políticas Estacionárias: O artigo prova que, dentro de MDCs unichain finitos, uma política estocástica estacionária é ótima entre todas as políticas dependentes de histórico. Isso justifica restringir o espaço de busca a políticas de Markov, unindo a teoria e a prática para o RL baseado em preferências.
2. Complexidade Computacional: Os autores demonstram que resolver um MDC exatamente está em P (tempo polinomial). Especificamente, eles constroem um programa linear com $|S||A| + |S| + 1$ variáveis e $2|S||A| + |S| + 1$ restrições. Esta complexidade é comparável aos MDPs padrão de recompensa média, apesar de os MDCs serem uma generalização estrita que suporta preferências não transitivas.
3. Iteração de Política Hedged (HPI): Um algoritmo iterativo aproximado, o Hedged Policy Iteration (HPI), é introduzido. Ele utiliza o algoritmo Hedge para atualizar regras de decisão baseadas em "valores marginais" (margens de preferência cumulativas).
   • Convergência: O HPI converge para uma política ótima a uma taxa sublinear de $O(1/\sqrt{K})$, onde $K$ é o número de iterações.
   • Escalabilidade: Os autores derivam uma forma de gradiente de política para o HPI e uma implementação de deep learning (Algoritmo 3) que utiliza buffers e aproximações de função de valor, tornando-o adequado para ambientes de alta dimensão.

Resultados Experimentais
Os autores avaliaram o HPI e uma variante com clipping (HPI-Clip) contra o Self-Play Preference Optimization (SPPO) (Swamy et al., 2024) em 13 tarefas de alta dimensão com longos horizontes temporais (2048 passos) usando a suíte Mujoco-v5.

• Configuração: As tarefas incluíram problemas padrão de controle contínuo (onde as preferências foram derivadas de diferenças de recompensa) e tarefas "Mujoco-NT" apresentando margens de preferência explicitamente não transitivas (por exemplo, regras de melhor de dois em três).
• Desempenho: Em 12 de 13 tarefas, o HPI e o HPI-Clip demonstraram uma eficiência de aprendizado significativamente maior (medida pela Área Sob a Curva do retorno episódico ou pelo gap de otimalidade invertido) em comparação ao SPPO.
• Ablação: Os resultados se mantiveram mesmo quando os modelos de preferência foram aprendidos a partir de dados offline.

Significância e Alegações
O artigo afirma que o aprendizado por reforço com preferências pareadas em problemas de decisão de longo prazo é mais tratável do que se pensava anteriormente. Ao introduzir o modelo MDC, os autores fornecem um framework onde:

• Políticas estacionárias são teoricamente suficientes, removendo a necessidade de estratégias complexas dependentes de histórico.
• O problema permanece computacionalmente eficiente (em P), mesmo com preferências não transitivas.
• Algoritmos práticos (HPI) escalam para problemas de alta dimensão e longo horizonte, superando métodos de estado da arte existentes.

Os autores observam que, embora esses resultados sejam promissores para aplicações como LLMs em tarefas de longo horizonte, investigações adicionais são necessárias para determinar quando o aprendizado de margem de preferência supera o aprendizado baseado em recompensa e quão eficazmente esses métodos alinham modelos de linguagem na prática. O trabalho visa aproximar a teoria e a prática do RL de preferência pareada.