Neste put up, apresentarei um algoritmo de aprendizagem por reforço (RL) baseado em um paradigma “alternativo”: dividir e conquistar. Ao contrário dos métodos tradicionais, este algoritmo é não com base na aprendizagem por diferença temporal (TD) (que tem desafios de escalabilidade) e se adapta bem a tarefas de longo horizonte.
Podemos fazer Aprendizagem por Reforço (RL) baseada em dividir para conquistar, em vez de aprendizagem por diferença temporal (TD).
Configuração do problema: RL fora da política
Nossa definição de problema é RL fora da política. Vamos revisar brevemente o que isso significa.
Existem duas lessons de algoritmos em RL: RL dentro da política e RL fora da política. RL dentro da política significa que podemos apenas usar dados recentes coletados pela política atual. Em outras palavras, temos que descartar dados antigos sempre que atualizamos a política. Algoritmos como PPO e GRPO (e métodos de gradiente de política em geral) pertencem a esta categoria.
RL fora da política significa que não temos esta restrição: podemos usar qualquer tipo de dados, incluindo experiências antigas, demonstrações humanas, dados da Web e assim por diante. Portanto, o RL fora da política é mais geral e flexível do que o RL dentro da política (e, claro, mais difícil!). Q-learning é o algoritmo RL fora da política mais conhecido. Em domínios onde a recolha de dados é dispendiosa (por exemplo, robóticasistemas de diálogo, cuidados de saúde, and so on.), muitas vezes não temos outra escolha senão utilizar RL fora da política. É por isso que é um problema tão importante.
A partir de 2025, acho que temos receitas razoavelmente boas para ampliar o RL dentro da política (por exemploPPO, GRPO e suas variantes). No entanto, ainda não encontramos uma solução “escalável” RL fora da política algoritmo que se adapta bem a tarefas complexas e de longo horizonte. Deixe-me explicar brevemente o porquê.
Dois paradigmas na aprendizagem de valores: Diferença Temporal (TD) e Monte Carlo (MC)
Em RL fora da política, normalmente treinamos uma função de valor usando aprendizado de diferença temporal (TD) (ou sejaQ-learning), com a seguinte regra de atualização de Bellman:
(start{aligned} Q(s, a) will get r + gamma max_{a’} Q(s’, a’), finish{aligned})
O problema é este: o erro no próximo valor $Q(s’, a’)$ se propaga para o valor atual $Q(s, a)$ através de bootstrapping, e esses erros acumular por todo o horizonte. Isto é basicamente o que faz com que a aprendizagem do DT tenha dificuldade em escalar para tarefas de longo horizonte (ver esta postagem se você estiver interessado em mais detalhes).
Para mitigar este problema, as pessoas misturaram a aprendizagem do DT com os retornos de Monte Carlo (MC). Por exemplo, podemos fazer aprendizagem TD em $n$-step (TD-$n$):
(start{aligned} Q(s_t, a_t) will get sum_{i=0}^{n-1} gamma^i r_{t+i} + gamma^n max_{a’} Q(s_{t+n}, a’). finish{aligned})
Aqui, usamos o retorno actual de Monte Carlo (do conjunto de dados) para as primeiras $n$ etapas e, em seguida, usamos o valor inicializado para o resto do horizonte. Dessa forma, podemos reduzir o número de recursões de Bellman em $n$ vezes, para que os erros se acumulem menos. No caso extremo de $n = infty$, recuperamos puro aprendizado de valor de Monte Carlo.
Embora esta seja uma solução razoável (e muitas vezes funciona bem), é altamente insatisfatório. Primeiro, não fundamentalmente resolver o problema de acumulação de erros; apenas reduz o número de recursões de Bellman por um fator constante ($n$). Em segundo lugar, à medida que $n$ cresce, sofremos com alta variância e subotimização. Portanto, não podemos simplesmente definir $n$ com um valor grande e precisamos ajustá-lo cuidadosamente para cada tarefa.
Existe uma maneira fundamentalmente diferente de resolver esse problema?
O “Terceiro” Paradigma: Dividir e Conquistar
Minha afirmação é que um terceiro paradigma na aprendizagem de valores, dividir e conquistarpode fornecer uma solução preferrred para RL fora da política que se adapta a tarefas de horizonte arbitrariamente longo.
Dividir para conquistar reduz o número de recursões de Bellman logaritmicamente.
A ideia principal de dividir e conquistar é dividir uma trajetória em dois segmentos de igual comprimento e combinar seus valores para atualizar o valor da trajetória completa. Desta forma, podemos (em teoria) reduzir o número de recursões de Bellman logaritmicamente (não linearmente!). Além disso, não requer a escolha de um hiperparâmetro como $n$ e não sofre necessariamente de alta variância ou subotimização, ao contrário do aprendizado TD $n$-step.
Conceitualmente, dividir para conquistar realmente tem todas as propriedades interessantes que necessitamos no aprendizado de valores. Há muito tempo estou entusiasmado com essa ideia de alto nível. O problema period que não estava claro como fazer isso na prática… até recentemente.
Um algoritmo prático
Em um trabalho recente co-liderado com Adityafizemos progressos significativos na concretização e ampliação desta ideia. Especificamente, fomos capazes de ampliar a aprendizagem de valor de dividir e conquistar para tarefas altamente complexas (até onde eu sei, este é o primeiro trabalho desse tipo!) pelo menos em uma classe importante de problemas de RL, RL condicionado por objetivo. A VR condicionada por objetivos visa aprender uma política que pode atingir qualquer estado a partir de qualquer outro estado. Isso fornece uma estrutura pure de dividir e conquistar. Deixe-me explicar isso.
A estrutura é a seguinte. Vamos primeiro assumir que a dinâmica é determinística e denotar a distância do caminho mais curto (“distância temporal”) entre dois estados $s$ e $g$ como $d^*(s, g)$. Então, satisfaz a desigualdade triangular:
(start{aligned} d^*(s, g) leq d^*(s, w) + d^*(w, g) finish{aligned})
para todos $s, g, w in mathcal{S}$.
Em termos de valores, podemos traduzir equivalentemente esta desigualdade triangular para o seguinte “transitivo” Regra de atualização do Bellman:
(start{aligned} V(s, g) will get start{instances} gamma^0 & textual content{if } s = g, \ gamma^1 & textual content{if } (s, g) in mathcal{E}, \ max_{w in mathcal{S}} V(s, w)V(w, g) & textual content{caso contrário} finish{casos} finish{alinhado})
onde $mathcal{E}$ é o conjunto de arestas no gráfico de transição do ambiente, e $V$ é a função de valor associada à recompensa esparsa $r(s, g) = 1(s = g)$. Intuitivamenteisso significa que podemos atualizar o valor de $V(s, g)$ usando dois valores “menores”: $V(s, w)$ e $V(w, g)$, desde que $w$ seja o “ponto médio” preferrred (submeta) no caminho mais curto. Esta é exatamente a regra de atualização de valor dividir para conquistar que estávamos procurando!
O problema
No entanto, há um problema aqui. A questão é que não está claro como escolher a submeta preferrred $w$ na prática. Em configurações tabulares, podemos simplesmente enumerar todos os estados para encontrar o $w$ preferrred (este é essencialmente o algoritmo do caminho mais curto de Floyd-Warshall). Mas em ambientes contínuos com grandes espaços de estado não podemos fazer isso. Basicamente, é por isso que trabalhos anteriores têm lutado para ampliar a aprendizagem de valor de dividir para conquistar, embora essa ideia já exista há décadas (na verdade, ela remonta ao primeiro trabalho em VR condicionada por objetivos de Kaelbling (1993) – ver nosso jornal para uma discussão mais aprofundada de trabalhos relacionados). A principal contribuição do nosso trabalho é uma solução prática para esta questão.
A solução
Aqui está nossa ideia principal: nós restringir o espaço de busca de $w$ para os estados que aparecem no conjunto de dados, especificamente, aqueles que ficam entre $s$ e $g$ na trajetória do conjunto de dados. Além disso, em vez de procurar pelo $textual content{argmax}_w$ preferrred, calculamos um $textual content{argmax}$ “smooth” usando regressão expectil. Ou seja, minimizamos a seguinte perda:
(start{aligned} mathbb{E}left(ell^2_kappa (V(s_i, s_j) – bar{V}(s_i, s_k) bar{V}(s_k, s_j))proper), finish{aligned})
onde $bar{V}$ é a rede de valor alvo, $ell^2_kappa$ é a perda expectável com um $kappa$ expectável, e a expectativa é tomada sobre todas as tuplas $(s_i, s_k, s_j)$ com $i leq ok leq j$ em uma trajetória de conjunto de dados amostrada aleatoriamente.
Isto tem dois benefícios. Primeiro, não precisamos pesquisar todo o espaço de estados. Em segundo lugar, evitamos a superestimação do valor do operador $max$ usando, em vez disso, a regressão expectil “mais suave”. Chamamos esse algoritmo RL transitivo (TRL). Confira nosso jornal para mais detalhes e mais discussões!
Funciona bem?
labirinto humanóide
quebra-cabeça
Para ver se nosso método se adapta bem a tarefas complexas, avaliamos diretamente o TRL em algumas das tarefas mais desafiadoras do OGBenchuma referência para RL offline condicionado por metas. Usamos principalmente as versões mais difíceis de labirintos humanóides e tarefas de quebra-cabeça com grandes conjuntos de dados de tamanho 1B. Essas tarefas são altamente desafiadoras: elas exigem o desempenho de habilidades combinatoriamente complexas em até 3.000 etapas ambientais.
O TRL alcança o melhor desempenho em tarefas altamente desafiadoras e de longo prazo.
Os resultados são bastante emocionantes! Em comparação com muitas linhas de base sólidas em diferentes categorias (TD, MC, aprendizagem quasimétrica, and so on.), o TRL alcança o melhor desempenho na maioria das tarefas.
TRL corresponde ao melhor TD-$n$ ajustado individualmente, sem precisar definir $boldsymbol{n}$.
Este é meu enredo favorito. Comparamos o TRL com o aprendizado de $n$-step TD com diferentes valores de $n$, de $1$ (TD puro) a $infty$ (MC puro). O resultado é muito bom. TRL corresponde ao melhor TD-$n$ em todas as tarefas, sem precisar definir $boldsymbol{n}$! Isto é exactamente o que queríamos do paradigma de dividir para conquistar. Ao dividir recursivamente uma trajetória em outras menores, pode-se naturalmente lidar com horizontes longos, sem ter que escolher arbitrariamente o comprimento dos pedaços de trajetória.
O artigo contém muitos experimentos, análises e ablações adicionais. Se você estiver interessado, confira nosso jornal!
O que vem a seguir?
Neste put up, compartilhei alguns resultados promissores de nosso novo algoritmo de aprendizagem de valor dividir e conquistar, Transitive RL. Este é apenas o começo da jornada. Existem muitas questões em aberto e direções interessantes para explorar:
Talvez a questão mais importante seja como estender o TRL para tarefas regulares de RL baseadas em recompensas, além do RL condicionado por objetivos. O RL regular teria uma estrutura semelhante de dividir e conquistar que podemos explorar? Estou bastante otimista quanto a isso, visto que é possível converter qualquer tarefa de RL baseada em recompensa em uma tarefa condicionada por meta, pelo menos em teoria (veja a página 40 do este livro).
Outro desafio importante é lidar com ambientes estocásticos. A versão atual do TRL assume dinâmica determinística, mas muitos ambientes do mundo actual são estocásticos, principalmente devido à observabilidade parcial. Por esta, Desigualdades triangulares “estocásticas” pode fornecer algumas dicas.
Na prática, acho que ainda há muito espaço para melhorar ainda mais o TRL. Por exemplo, podemos encontrar maneiras melhores de escolher candidatos a subobjetivos (além daqueles da mesma trajetória), reduzir ainda mais os hiperparâmetros, estabilizar ainda mais o treinamento e simplificar ainda mais o algoritmo.
Em geral, estou muito entusiasmado com o potencial do paradigma de dividir para conquistar. EU ainda acho que um dos problemas mais importantes em RL (e até mesmo em aprendizado de máquina) é encontrar um escalável algoritmo RL fora da política. Não sei como será a solução ultimate, mas penso que dividir para conquistar, ou recursivo a tomada de decisões em geral é um dos candidatos mais fortes a esse Santo Graal (a propósito, acho que os outros fortes candidatos são (1) RL baseado em modelo e (2) aprendizagem TD com alguns truques “mágicos”). Na verdade, vários trabalhos recentes em outros campos mostraram a promessa da recursão e das estratégias de dividir para conquistar, tais como modelos de atalho, atenção log-lineare modelos de linguagem recursiva (e, claro, algoritmos clássicos como quicksort, árvores de segmentos, FFT e assim por diante). Espero ver um progresso mais emocionante no RL escalonável fora da política em um futuro próximo!
Agradecimentos
Eu gostaria de agradecer Kevin e Sergei por seus comentários úteis sobre esta postagem.
Esta postagem apareceu originalmente em Weblog do Parque Seohong.