Q-learning ainda não é escalável
(seohong.me)- RL teve grandes resultados em Go, xadrez e no pós-treinamento de LLMs, mas a maioria depende de RL on-policy, que exige novos rollouts e opera sob condições diferentes do RL off-policy, que reutiliza livremente dados anteriores
- O RL off-policy mais representativo, o Q-learning, tem alta eficiência de amostragem, mas ainda não escala bem em tarefas de longo prazo que exigem mais de 100 etapas significativas de tomada de decisão
- O gargalo é que os alvos de bootstrap enviesados do aprendizado TD se acumulam à medida que o horizonte aumenta, o que é uma limitação diferente da previsão do próximo token, de modelos de difusão e do aprendizado contrastivo
- Em experimentos no OGBench, flow BC, IQL, CRL e SAC+BC não conseguiram resolver todas as tarefas de longo prazo nem mesmo em um dataset de 1B, 1000 vezes maior que datasets offline de RL comuns, e o desempenho ficou estagnado abaixo do ideal
- Redução de horizonte como n-step returns e RL hierárquico melhorou a escalabilidade e o desempenho final, mas as técnicas atuais aliviam o problema apenas por um fator constante e ainda são insuficientes para resolver tarefas arbitrariamente complexas de longo prazo
Onde está a escalabilidade do RL hoje
- Previsão do próximo token, denoising diffusion e aprendizado contrastivo mostraram ser objetivos escaláveis com grandes volumes de dados e modelos com dezenas de bilhões de parâmetros
- O RL também alcançou desempenho sobre-humano em Go e xadrez e, em LLMs, está resolvendo tarefas de raciocínio complexo como matemática e programação
- No entanto, a maioria dos casos reais de sucesso hoje se baseia em algoritmos de RL on-policy
- Exemplos representativos: REINFORCE, PPO, GRPO etc.
- Sempre exigem rollouts recém-amostrados da política atual
- Não é possível reutilizar dados anteriores
- Métodos da família PPO conseguem reutilizar dados de forma limitada, mas, seguindo classificações como a da documentação da OpenAI, ainda são tratados como RL on-policy
- Em ambientes como jogos de tabuleiro ou LLMs, onde é barato gerar muitos rollouts, essa restrição pode não ser um grande problema
- Em robótica, gerar no mundo real o volume de amostras usado para pós-treinar modelos de linguagem com RL pode levar meses ou mais, e durante o treinamento uma pessoa precisa ficar ao lado do robô 24 horas por dia para fazer os resets
RL off-policy e Q-learning
- Em princípio, o RL off-policy pode usar dados coletados a qualquer momento e de qualquer forma
- Como o mesmo dado pode ser reutilizado várias vezes, em geral ele tem melhor eficiência de amostragem
- Já houve caso de treinar um robô quadrúpede a andar em apenas 20 minutos partindo do zero em ambiente real
- Caso relacionado: walk in the park
- Q-learning é o algoritmo de RL off-policy mais usado
- A maior parte dos algoritmos práticos de RL off-policy model-free se baseia em variantes da loss TD
- Para aplicar RL a mais problemas reais, a pergunta central passa a ser: “Q-learning, isto é, TD learning, é escalável?”
- Se for, será possível resolver com eficiência tarefas reais mais variadas e complexas, como robótica e agentes que usam computadores
O significado de “escalável”: não largura, e sim profundidade
- Aqui, escalabilidade significa a capacidade de resolver problemas mais difíceis e com horizonte mais longo quando se adiciona mais dados com cobertura suficiente, mais computação e mais tempo
- Isso é diferente da capacidade de resolver um número maior de tarefas com um único modelo
- Um aumento no número de tarefas não significa necessariamente resolver tarefas mais difíceis
- Vários estudos anteriores de scaling mostram potencial nesse eixo de “largura (width)”
- O eixo mais importante e difícil é o da profundidade (depth)
- Porque exige capacidades de tomada de decisão mais avançadas
- Na forma atual, o Q-learning não escala bem no eixo da profundidade
- Para levar Q-learning e RL off-policy a problemas complexos e de longo prazo, será necessário um avanço algorítmico
O Q-learning ausente nos grandes casos de sucesso do RL
- Muitos sucessos reais de RL se baseiam em abordagens diferentes do Q-learning baseado em TD
- AlphaGo, AlphaZero e MuZero usam RL baseado em modelo e Monte Carlo tree search, e não usam TD learning em jogos de tabuleiro
- Referência: página 15 do artigo MuZero
- O OpenAI Five alcançou desempenho sobre-humano em Dota 2 com PPO
- Referência: nota de rodapé 6 do artigo OpenAI Five
- O RL para LLMs hoje é dominado por métodos on-policy da família de policy gradient, como PPO e GRPO
- Não há exemplos práticos apresentados de sucesso de RL off-policy, em especial TD learning de 1 passo, em escala comparável à de AlphaGo ou LLMs
- Essa avaliação não é uma rejeição do RL off-policy, mas sim um indicativo de que ainda é preciso mais pesquisa em algoritmos de RL
Por que o Q-learning vacila em tarefas de longo prazo
- A loss TD do Q-learning aprende ajustando o valor Q atual a um alvo formado pela recompensa mais o valor Q máximo do próximo estado
- Esse alvo é um alvo de bootstrap enviesado, que pode não ser igual ao valor Q ótimo real
- O principal motivo de o Q-learning ter dificuldade para escalar é que o viés do alvo de predição se acumula ao longo do horizonte
- Esse acúmulo de viés funciona como uma limitação fundamental do TD learning
- Objetivos como previsão do próximo token, denoising diffusion e aprendizado contrastivo não têm esse viés no alvo de predição
- BYOL e DINO, mesmo quando têm viés, ele não se acumula ao longo do horizonte
- À medida que o problema fica mais complexo e o horizonte se alonga, o viés do alvo de bootstrap se acumula com mais força
- Não é fácil aliviar esse problema apenas com mais dados e modelos maiores
- Na prática, um dos principais motivos para quase não se usar descontos maiores, como (\gamma > 0.999), está ligado a isso
- Métodos de policy gradient sofrem relativamente menos com esse problema
- Técnicas on-policy de estimação de valor como GAE lidam com horizontes longos com mais facilidade relativa, embora aceitem maior variância
- Elas não ficam presas a uma recursão estrita de 1 passo
Experimentos de escalabilidade com base no OGBench
- O artigo recente Horizon Reduction Makes RL Scalable testa essa hipótese com vários estudos de scaling controlados
- O objetivo é verificar se os métodos atuais de RL off-policy conseguem resolver tarefas muito difíceis apenas aumentando dados e computação
- Os experimentos usam tarefas complexas e antes não resolvidas do OGBench
- Os requisitos das tarefas são os seguintes
- O agente precisa aprender comportamentos complexos de alcance de objetivos a partir de demonstrações aleatórias e não estruturadas em estilo play
- No teste, ele precisa executar manipulação precisa, solução de puzzles combinatórios e navegação de longo prazo
- As tarefas se desenrolam ao longo de 1.000 passos de ambiente
- Os experimentos foram desenhados para reduzir variáveis de confusão
- Foi coletada uma quantidade quase infinita de dados, tornando overfitting praticamente impossível
- O foco foi em RL offline para eliminar o problema de exploração
- Garantiu-se cobertura suficiente no dataset e que todas as tarefas podem ser resolvidas com o dataset fornecido
- Para reduzir a carga de aprendizado de representação, foram fornecidas diretamente observações de estado ground-truth
- Se mesmo nesse ambiente controlado o Q-learning não escala, as chances são ainda menores em ambientes reais com dados limitados e observações ruidosas
Resultados dos algoritmos padrão de RL offline
- Algoritmos padrão e amplamente usados de RL offline não conseguiram resolver todas as tarefas
- Os algoritmos avaliados foram flow BC, IQL, CRL, SAC+BC
- Os experimentos foram conduzidos até em um dataset de 1B
- Isso é (1000 \times) maior que datasets offline de RL típicos
- Mais importante ainda: o desempenho muitas vezes atingiu um plateau muito abaixo do desempenho ótimo
- Várias ablações e experimentos de controle, como modelos maiores, treinamento mais longo e outros hiperparâmetros, também não surtiram efeito
- O único método que mostrou efeito de forma consistente foi a redução de horizonte
As melhorias trazidas pela redução de horizonte
- A hipótese anterior é que o horizonte e o consequente acúmulo de viés são o principal obstáculo para a escalabilidade do RL off-policy
- Para testar isso, foram tentadas várias técnicas de redução de horizonte que diminuem o número de backups TD enviesados
- Exemplos: n-step returns, RL hierárquico etc.
- Os resultados foram positivos
- Mesmo técnicas simples como n-step returns melhoraram bastante a escalabilidade e o desempenho final
- Não se trata apenas de um truque para acelerar o treinamento; o desempenho assintótico também melhora
- Métodos hierárquicos completos funcionaram ainda melhor
- Em todos os experimentos, a única técnica que funcionou de forma consistente foi a redução de horizonte
- Simplesmente aumentar dados e computação não basta para resolver a maldição do horizonte
- São necessários algoritmos melhores que ataquem diretamente esse problema
Direções de pesquisa rumo a objetivos escaláveis de RL off-policy
- A redução de horizonte ajuda a destravar a escalabilidade do Q-learning, mas as técnicas atuais não resolvem o problema de forma fundamental
- Métodos atuais como n-step returns e RL hierárquico, em sua maioria, apenas aliviam o problema por um fator constante
- Ainda faltam algoritmos de RL off-policy que escalem até problemas de longo prazo arbitrariamente complexos
- Três direções de pesquisa possíveis são destacadas
- Encontrar estruturas hierárquicas recursivas simples e escaláveis que vão além de uma hierarquia de dois níveis para lidar com horizontes de comprimento arbitrário
- Como aprendizado de modelo é aprendizado supervisionado e RL on-policy também é escalável, uma abordagem de RL baseado em modelo seria primeiro aprender o modelo e depois executar RL on-policy dentro dele
- Evitar totalmente o TD learning
- Como exemplo, quasimetric RL se baseia na formulação por LP do RL
- Também vale testar se métodos baseados em MC, como contrastive RL, escalam melhor do que abordagens baseadas em TD
- Essa configuração experimental pode servir como ponto de partida para testar essas ideias
- As tarefas e datasets complexos de robótica já foram projetados
- Foi verificado que as tarefas podem ser resolvidas com os dados fornecidos
- É possível tornar as tarefas arbitrariamente mais difíceis, por exemplo adicionando mais cubos, para fazer stress tests controlados de escalabilidade algorítmica
- Código aberto: horizon-reduction
1 comentários
Opiniões no Hacker News
Este texto parece deixar de fora um motivo maior pelo qual Q-learning é difícil de escalar
À medida que o horizonte fica mais longo, o número de estados possíveis geralmente cresce exponencialmente, e para aprender um Q capaz de lidar com esses estados, os dados também precisam crescer exponencialmente
Em aprendizado on-policy, esse problema é menor, porque o que importa são apenas os estados próximos da política atual, e na prática só esses estados são amostrados
O ponto central é que, por causa da operação
maxdo Q-learning, o ruído se amplifica ao longo dos passos de tempo, e técnicas de mitigação de viés como https://arxiv.org/abs/1509.06461 tiveram sucesso em melhorar o desempenho de agentes de aprendizado por reforçoSegundo pesquisas, esse fenômeno aparece com mais força em estados que a rede visitou pouco
O fato de haver um número exponencial de estados só é decisivo quando não há padrões entre esses estados. Se houver uma estrutura aprendível, pode funcionar bem, e isso não é uma fraqueza do deep learning, mas uma força
A questão é definir o objetivo de aprendizado correto, e o texto basicamente argumenta que Q-learning não é esse objetivo
Fico curioso se aprendizado por reforço baseado em modelo, como o MuZero, talvez seja uma solução para as preocupações do autor. O MuZero consegue aumentar a eficiência do aprendizado reanalisando trajetórias anteriores, e a busca em árvore de Monte Carlo (MCTS) é uma forma principiada de reduzir o horizonte ao desdobrar o modelo por várias etapas
A operação
maxno MCTS também pode criar um problema parecido, mas o processo de aprofundar a busca pode compensar issoFalando como completo leigo, acho que algumas tarefas, embora sejam “profundas”, podem ser suficientemente “uniformes” para que amostras ruins ainda bastem. Eu chamaria essas tarefas de tarefas ergódicas
Claro, certamente deve haver tarefas que não são assim
Este artigo já parte do pressuposto de que a pessoa conhece bastante aprendizado por reforço
Se você quiser se aprofundar de verdade em aprendizado por reforço, as aulas introdutórias de David Silver (DeepMind) são excelentes: https://youtu.be/2pWv7GOvuf0?si=CmFJHNnNqraL5i0s
Concordo totalmente, e acho que é um resumo muito bom
Em termos bem curtos, é o problema de perseguir um alvo móvel, mas esse alvo muda dependendo de como eu me movo
Em aprendizado por reforço baseado em valor, não há uma resposta real para a qual se possa convergir. É como minimizar uma diferença em que ambos os lados da equação contêm a própria aproximação
Ainda assim, não acho que seja desesperador. Vejo o aprendizado por reforço como algo que chegou muito perto de funcionar; o que faltou até agora foi um modelo de mundo/função de dinâmica direta confiável
Com isso, é possível planejar sem explorar, e agora temos modelos assim
O benefício do aprendizado off-policy é fundamentalmente limitado pelo fato de que dados ineficientes vindos da exploração inicial não são tão úteis depois para melhorar uma política mais refinada
Isso fica claro se pensarmos em erros no xadrez, movimentos espasmódicos ou tentativas fracassadas de resolver quebra-cabeças
Fica ainda mais claro quando percebemos que dados só se tornam off-policy quando descrevem algo que a política atual não faria
Acho que a solução para esse problema infelizmente passa por melhor generalização e eficiência amostral
Como explicar o cachorro que aprendeu a andar em 20 minutos com aprendizado off-policy, citado no texto? Ou a tese é mais sutil?
É estranho que Decision Transformer e Trajectory Transformer tenham ficado de fora
Ambos são abordagens offline e, graças ao mecanismo de atenção, conseguem contornar o problema de atribuição de crédito e tendem a funcionar bem em tarefas de horizonte longo
A maioria dos pesquisadores de aprendizado por reforço não considera essas abordagens como “aprendizado por reforço de verdade”, porque elas não conseguem atribuir crédito para além da janela de contexto e, portanto, não conseguem aprender tarefas de horizonte infinito
Mas, com janelas de contexto de mais de 1 milhão de tokens, talvez isso seja menos problemático na prática? Gostaria de ouvir outras opiniões
DT: https://arxiv.org/abs/2106.01345
TT: https://arxiv.org/abs/2106.02039
Só usar Transformer não contorna o problema de atribuição de crédito
Transformer é uma arquitetura para resolver problemas de modelagem sequencial, e o problema de atribuição de crédito que surge em aprendizado por reforço é um exemplo desse tipo de problema. Já existiram muitas arquiteturas assim antes
Dizer que a atribuição de crédito é difícil é uma afirmação sobre escassez de dados. Não dá para “contornar” isso apenas escolhendo uma arquitetura
Humanos, na prática, fazem as duas coisas
Aprendem on-policy ao explorar as consequências das próprias ações, e também aprendem off-policy, como em demonstrações de especialistas
A diferença é que humanos conseguem distinguir ações boas de ruins e filtrar para aprender apenas com as ações que julgam boas
Na maior parte do aprendizado por reforço off-policy, muitas ações ruins também entram, e isso desacelera o aprendizado quando elas fazem parte do conjunto de treinamento
É por isso que algumas demonstrações de especialistas são atraentes. Podemos ver alguém obter resultados melhores mesmo fazendo algo que, do ponto de vista das “boas práticas” de um iniciante, parece completamente errado
Claro, às vezes isso só significa que, quando se é bom o suficiente, dá para compensar essas técnicas ou erros
Vale destacar que as tarefas de horizonte longo que humanos aprendem por treino repetido são divididas em tarefas de horizonte mais curto e, depois, aprendidas por composição hierárquica
O modelo pode não conseguir lidar com tarefas de horizonte longo desde o início, mas pode primeiro aprender habilidades de horizonte curto e então usar esses pequenos conjuntos de habilidades para aprender horizontes mais longos
É o mesmo chunking que todos nós fazemos
Ninguém aprende a pilotar um avião comercial em um voo transcontinental como uma sequência de micromovimentos das mãos e dos braços
Quando criança, pegar uma bola é aprendido desse jeito, mas aviação ou esportes são compostos por hierarquias de habilidades e planos aprendidos
Gosto do texto, mas acho que o uso de siglas sem explicação reduziu a chance de ele ser útil para um público mais amplo
É uma crítica pequena, mas seria bom explicar siglas e jargões técnicos
Acabei de fazer isso no novo navegador Dia e funcionou bem. Também dá para copiar e colar no provedor de modelo que você preferir
Assim, o texto continua conciso, mas você pode fazer perguntas à ferramenta de IA e esclarecer pontos
O ponto quase mágico de técnicas off-policy como Q-Learning é que elas convergem para um resultado ótimo mesmo vendo apenas dados de treinamento não ótimos
Por exemplo, mesmo usando como entrada para Q-Learning um conjunto de dados de partidas de xadrez de agentes que se movem de forma totalmente aleatória, sem estratégia alguma, ele ainda converge para a política ótima no fim; só é mais lento do que seria com entradas de alta qualidade
Talvez eu esteja distorcendo um pouco o termo, mas acredito que também existam tarefas não ergódicas