DAgger Explicado: Por Que o Behavior Cloning Falha e O Que Dataset Aggregation Realmente Prova

Há uma falha específica que todos que treinam uma policy de manipulação encontram mais cedo ou mais tarde. A policy alcança o cubo, fica a dois centímetros de distância, hesita, desliza para os lados, depois faz algo não relacionado à tarefa. A loss de validação estava correta. Replay em malha aberta contra episódios reservados estava correto. E ainda assim o braço acaba em uma pose que não aparece em lugar nenhum nos dados de treinamento, e de lá ele não tem nada sensato para dizer.

Essa falha tem um nome e uma teoria estabelecida por trás dela. Este é o primeiro de quatro artigos sobre DAgger, e cobre o argumento em si: por que o ajuste de uma policy nas próprias trajetórias do demonstrador produz um erro que pode crescer com o quadrado do comprimento do episódio, o que dataset aggregation muda, e o que a prova de no-regret não promete. O loop em hardware real é coberto em executando um loop DAgger em um SO-100, a variante com gate humano em HG-DAgger e intervenções com gate humano, e a questão de medição em medindo um loop DAgger.

A suposição que behavior cloning faz silenciosamente

Um dataset de demonstração é um monte de pares observação-ação. Behavior cloning ajusta uma função a esse monte com aprendizado supervisionado comum e para por aí. É a ideia mais antiga do campo. ALVINN de Pomerleau, em 1988, era uma rede backpropagation de três camadas que recebia imagens de uma câmera e um scanner de alcance a laser e produzia a direção em que o veículo deveria viajar; foi treinada em imagens de estrada simuladas e seguiu estradas reais em algumas condições de campo. A receita não mudou muito; as redes sim.

O que é pulado é uma verificação sobre de onde esses pares vieram. Cada um deles fica em uma trajetória que o demonstrador produziu. A policy que você implanta produz sua própria. No momento em que desvia, está sendo consultada sobre estados que não estavam na distribuição de treinamento, e sua resposta a afasta mais para fora. Ross, Gordon e Bagnell abrem o artigo DAgger com exatamente isso: predição sequencial viola a suposição i.i.d. subjacente ao aprendizado estatístico, porque as próprias predições do aprendiz determinam as entradas que ele vê a seguir.

A ilustração mais clara naquele artigo não é um robô em absoluto. Clonar um planejador quase ótimo para Super Mario Bros. produziu uma policy que repetidamente ficou presa contra um obstáculo em vez de pular sobre ele. A razão é todo o argumento em uma frase: o especialista sempre pulava de uma distância confortável, então o dataset não continha nenhum estado em que Mario estava pressionado contra um obstáculo, e portanto nenhum rótulo para o que fazer uma vez que estava.

Troque Mario por um braço SO-100 e a estrutura é idêntica. Suas demonstrações mostram uma abordagem limpa e um aperto limpo, não o gripper fechando dois centímetros antes - então a policy não tem ideia do que fazer de lá, e tudo que ela adivinha a tira ainda mais para fora. Covariate shift é uma propriedade do procedimento de coleta de dados, não da arquitetura de rede.

De onde vem o termo quadrático

O artigo AISTATS de 2010 de Ross e Bagnell, Efficient Reductions for Imitation Learning, torna a composição precisa. Seja T o horizonte da tarefa, seja o custo da tarefa limitado no intervalo unitário, e seja epsilon a loss substituta medida sob a distribuição de estados do especialista - o número que seu conjunto de validação relata. Então o custo extra de executar essa policy por T passos, relativo ao especialista, é limitado por T ao quadrado vezes epsilon. Ross, Gordon e Bagnell reafirmam isso como Teorema 2.1 no artigo DAgger e adicionam a frase que importa: o limite é justo. Problemas existem onde uma policy com loss epsilon na distribuição do especialista realmente incorre em custo extra crescendo quadraticamente em T.

Justo não significa típico. O termo quadrático é um pior caso sobre uma classe de problemas, não uma predição sobre sua tarefa de pick-and-place. O que estabelece é que mais demonstração de especialista não pode remover o problema: só aguça a estimativa de epsilon em uma distribuição na qual a policy não será testada.

A rota de escape está no mesmo artigo, reafirmada como Teorema 2.2. Se uma policy alcança loss epsilon sob sua própria distribuição de estados, e uma única ação errada custa no máximo u em custo futuro sob o especialista, o custo extra é limitado por u vezes T vezes epsilon - linear no horizonte. A constante u é a quantidade interessante: no máximo 1 para desacordo 0-1 com o especialista, e O(1) sempre que o especialista possa se recuperar em alguns passos. No pior caso é O(T), e o limite linear não é melhor do que o quadrático.

As duas tentativas que vieram antes de DAgger

Forward training é a resposta honesta mas impraticável. Treine uma policy separada para cada timestep, em ordem, cada uma na distribuição de estados induzida pelas policies já fixadas para passos anteriores, então cada policy vê exatamente a distribuição que enfrentará. A pegadinha está na descrição: T policies, treinadas sequencialmente, sem parada antecipada. Para um episódio de manipulação a 30 frames por segundo, T está nas centenas.

SMILe, do mesmo artigo, e SEARN, do trabalho de Daume, Langford e Marcu sobre predição estruturada, tomam o outro caminho: uma policy estacionária, mas estocástica. Cada iteração treina um componente e o adiciona a uma mistura, deslocando massa de probabilidade para longe do especialista. O resultado é uma mistura em que alguns componentes são piores que outros - em um braço físico, um controlador que pode amostrar um componente ruim em meio ao movimento. Essa é a motivação declarada para querer uma policy determinística estacionária em vez disso.

DAgger: uma ideia, uma caixa

Dataset Aggregation mantém a policy determinística e move a correção para coleta de dados. Cada rodada: execute a policy atual, registre os estados que visita, pergunte ao especialista qual seria a ação correta em cada um, adicione esses pares ao dataset que você já tem, retreine na união. O nome é o algoritmo - você agrega, nunca descarta.

D            <- {}                      # the aggregate dataset
pi_hat_1     <- any policy in Pi

for i = 1 .. N:
    pi_i  = beta_i * expert  +  (1 - beta_i) * pi_hat_i
    roll out pi_i for T steps, record every visited state s
    D_i   = { (s, expert(s))  for every visited state s }
    D     = D  union  D_i               # aggregate, do not replace
    pi_hat_{i+1} = train on all of D

return the best pi_hat_i on a validation set

Três detalhes têm mais peso do que parecem ter. Os rótulos são para estados visitados pela policy mista, mas as ações vêm do especialista - a policy fornece as questões, o especialista as respostas. O retreinamento é no agregado completo, o que torna cada rodada um passo Follow-The-Leader: na rodada n você escolhe a melhor policy em retrospectiva sobre cada trajetória até agora. Esse enquadramento é no que a prova se baseia. E o algoritmo termina retornando a melhor policy na sequência como escolhida em um conjunto de validação, porque os teoremas garantem que alguma policy na sequência é boa, não que a última seja.

A beta schedule, e por que não é um botão de ajuste

A policy mista é beta_i vezes o especialista mais um menos beta_i vezes o aprendiz. O ponto é prático: as primeiras policies aprendidas são treinadas com muito poucos dados, cometem muitos erros, e de outra forma passariam o rollout em estados que se tornam irrelevantes uma vez que a policy melhora.

A teoria impõe exatamente uma condição: a média móvel das betas deve ir para zero. A análise funciona com beta_i limitado por (1 - alpha) elevado à potência i-1, para uma constante alpha independente de T.

A lacuna entre 2980 e 3030 em uma escala que vai para aproximadamente 4300 é pequena, mas a explicação do artigo é a nota prática mais útil da seção. Com a schedule sem parâmetro, Mario ficou preso no mesmo lugar no início e gerou uma massa de dados quase duplicados daquele local; deixar o especialista dirigir uma fração do tempo tanto o destraváo quanto ampliou a variedade de estados. A schedule é menos sobre a taxa de mistura do que se sua coleta de dados continua produzindo novos estados ou a mesma falha.

A garantia: uma redução para online learning com no-regret

Aqui está o movimento que torna o artigo o que é. Trate cada rodada DAgger como um exemplo em um problema de online learning, onde a loss na rodada i é a loss substituta sob a distribuição de estados da policy usada na rodada i. O aprendiz se compromete com uma policy antes de ver essa loss, e a sequência é não-estacionária porque depende das policies produzidas até agora.

Um algoritmo é no-regret se sua loss média sobre N rodadas se aproxima daquela da melhor política única em retrospectiva. Follow-The-Leader em losses fortemente convexas é tal algoritmo, com regret médio encolhendo na ordem de 1/N - e retreinar no agregado completo é precisamente Follow-The-Leader. Qualquer outro aprendiz no-regret serviria tão bem: a análise é uma redução, não uma propriedade de um otimizador.

Um lema liga a lacuna entre a policy mista que coletou os dados e a policy aprendida que será implantada: o Lema 4.1 limita a distância L1 entre suas distribuições de estados por 2 T beta_i. É por isso que as betas devem decair - enquanto o especialista ainda detém autoridade de controle apreciável, os estados que você coleta não são os estados que sua policy produzirá. Combine o lema com o regret bound e o resultado principal segue: após aproximadamente T iterações, alguma policy na sequência tem loss substituta sob sua própria distribuição dentro de O(1/T) de epsilon_N. Alimente isso no limite linear e você chega ao Teorema 3.2.

O lado empírico é modesto pelos padrões atuais. Em Super Tux Kart a baseline supervisionada não melhorou sua média de quedas por volta conforme mais dados chegavam, DAgger alcançou uma policy que nunca caiu da pista após quinze iterações, e SMILe após vinte ainda caía aproximadamente duas vezes por volta. No benchmark de escrita à mão, acurácia de caractere corria 82 por cento sem estrutura, 83,6 por cento supervisionado, 85,5 por cento com DAgger. Nenhum desses é um resultado de manipulação.

O que a prova não promete

As declarações de teorema são condicionais, e as condições são determinantes.

Um resultado adicional é frequentemente citado como uma refutação e não é. Rajaraman, Yang, Jiao e Ramachandran estudam os limites minimax do imitation learning em MDPs episódicos com espaço de estados finito S e horizonte H, e provam um limite inferior de suboptimalidade na ordem de |S| H ao quadrado sobre N que se mantém mesmo quando o aprendiz pode consultivamente consultar o especialista em estados visitados. Essa é uma taxa de pior caso sobre uma classe de MDPs em um orçamento de episódio fixo, e o que ela exclui é a ideia de que interação melhora a taxa minimax; o teorema de DAgger é uma declaração diferente, limitando a policy implantada em relação ao que sua própria classe de policy pode alcançar.

Swamy, Choudhury, Bagnell e Wu mais tarde classificaram esses algoritmos pelos quais momentos do comportamento do especialista eles combinam, e introduziram uma noção de recoverabilidade de momento que delineia quão bem cada família mitiga erro de composição. As pesquisas de Osa e de Celemin cobrem a paisagem algorítmica e as interfaces de feedback humano.

A conta: rotulando estados que o especialista nunca produziu

Tudo acima assume um especialista que pode ser consultado em qualquer lugar. Em simulação com um planejador que é quase grátis - os experimentos de Mario usaram um planejador quase ótimo com acesso completo ao estado do jogo. Com um humano em um robô é o custo dominante, e um peculiar: o humano deve produzir uma ação correta em uma configuração que sua própria competência nunca teria criado.

Kelly, Sidrane, Driggs-Campbell e Kochenderfer afirmam a objeção diretamente no artigo HG-DAgger. DAgger vanilla requer que o especialista forneça rótulos de ação enquanto não estão totalmente no controle do sistema. Isso reduz segurança, e com especialistas humanos é provável que degrade a qualidade dos rótulos coletados, que eles atribuem a lag de atuador percebido. O rótulo que você recebe de volta não é o rótulo que o algoritmo assumiu.

Laskey e colegas atacam o problema do outro lado com DART, e seu enquadramento é contundente: técnicas on-policy são tediosas para supervisores humanos, adicionam carga computacional, e podem visitar estados perigosos durante treinamento. Sua alternativa injeta ruído calibrado nas próprias demonstrações do supervisor, então recuperação fica demonstrada sem o robô nunca executar uma policy não confiável. Em MuJoCo Humanoid eles relatam DART diminuindo a recompensa cumulativa do supervisor em 5 por cento durante treinamento, enquanto DAgger executa policies com 80 por cento menos recompensa cumulativa que o supervisor; em grasping em desorganização com um Toyota HSR, um aumento médio de 62 por cento sobre behavior cloning.

SafeDAgger de Zhang e Cho trata consultas à reference policy como o recurso escasso: uma política de segurança separada prediz, sem consultar, se a policy primária está prestes a desviar da referência além de um threshold, e apenas esses estados são entregues. Todos os três reagem ao mesmo fato - a análise DAgger não cobra nada pelos rótulos de especialista, e a realidade cobra muito.

O que isso significa para um SO-100 em sua mesa

Traduza o horizonte para suas próprias unidades. Um episódio de vinte segundos a 30 frames por segundo é 600 passos de decisão, e T em cada limite acima é esse número. Em T = 600, a diferença entre um termo escalando com T e um escalando com T ao quadrado é a diferença entre uma policy que se recupera de uma abordagem ruim e uma que não.

É parte do motivo pelo qual action chunking ajuda: quando uma policy emite uma curta sequência de ações por passo de inferência, o número de pontos de decisão cai, e assim o número de chances para compor. Zhao, Kumar, Levine e Finn nomeiam erro de composição como a motivação para Action Chunking with Transformers, e relatam 80 a 90 por cento de sucesso em seis tarefas difíceis do mundo real, em hardware bimanual de baixo custo, a partir de dez minutos de demonstrações. Chunking não remove covariate shift - os estados são ainda da própria policy - mas encurta o horizonte efetivo. Veja action chunking e o guia de imitation learning SO-100.

A segunda tradução é a métrica de progresso. Você não pode medir epsilon sob a distribuição da própria policy diretamente - isso precisa de ações de especialista de verdade para cada estado visitado, a coisa que você está tentando evitar produzir. O que um loop com gate humano fornece em vez disso é a intervention rate: a fração de frames em uma execução durante os quais o humano havia assumido o controle. É um proxy, e se move por razões não relacionadas à policy - um operador paciente intervém menos. Usado consistentemente, é o número único que diz se uma rodada valeu a tarde.

Uma terceira tradução é uma advertência de qualidade de dados que a análise não cobre. Mandlekar e colegas estudaram seis algoritmos de offline learning em cinco tarefas de manipulação multi-estágio simuladas e três do mundo real, e relatam uma sensibilidade às escolhas de design algorítmico, uma dependência da qualidade das demonstrações, e variabilidade causada pelo critério de parada. Belkhale, Cui e Sadigh argumentam que a qualidade de dataset deve ser formalizada através de action divergence e transition diversity, e notam que diversidade de estado nem sempre é benéfica. Uma rodada DAgger adiciona estados que ninguém escolheu deliberadamente: alguns são os dados de recuperação que você precisa, alguns são o robô se mexendo enquanto você tateando o controle de takeover.

Mecanicamente uma rodada é seis passos: execute inferência com gravação ligada, assuma quando a policy se comporta mal, revise a execução e arquive cada episódio, sincronize as correções, componha um dataset misto de originais mais correções com seleção de episódio feita explicitamente por fonte, e continue treinando a partir do checkpoint anterior em vez do modelo base. Em ay-robots esses passos existem como botões, o que remove a tubulação mas não o julgamento. Duas ressalvas: continuar de um checkpoint inicializa pesos e não é um resume de otimizador, e o movimento de alinhamento de braço-líder ainda é levemente testado em hardware. Veja treinamento e datasets.

A árvore genealógica, em uma tabela

Perguntas frequentemente feitas

Para onde ir a partir daqui

Se você ainda não treinou uma policy, essa teoria é prematura: primeiro registre um dataset, começando com treinando sua primeira policy e o cliente desktop. Se você está pesando outras cem demonstrações limpas contra iniciar correções: demonstrações limpas não resolvem um problema de distribuição. Pela mecânica, continue com a variante com gate humano e então o passo a passo SO-100.