Resumo Técnico: Aprender Quando Parar: Aprendizado por Imitação Seletiva sob Deslocamentos Arbitrários de Dinâmica

1. Formulação do Problema

O artigo aborda o desafio do Aprendizado por Imitação (IL) em cenários onde as dinâmicas de transição do ambiente de teste diferem arbitrariamente do ambiente de treinamento. No IL offline clássico, um agente treinado em demonstrações de especialistas a partir de um ambiente fonte $M$ é implantado em um ambiente alvo $N$. Se os suportes de estado de $M$ e $N$ forem disjuntos ou significativamente deslocados, uma política padrão pode performar arbitrariamente mal porque não consegue reconhecer quando seus dados de treinamento deixam de fornecer orientação confiável.

Os autores propõem um framework para Aprendizado por Imitação Seletiva, onde o agente tem a opção de abster-se (parar a execução) no meio da trajetória quando detecta que o estado atual está fora do suporte confiável de seus dados de treinamento. O objetivo é aprender uma política seletiva $(\pi, \tau)$, consistindo em uma política base $\pi$ e um tempo de parada $\tau$, que satisfaça dois objetivos concorrentes:

1. Completude: A política deve raramente abster-se no ambiente de treinamento $M$ (isto é, $\alpha_M(\pi, \tau) \le \epsilon$).
2. Sondabilidade: A política deve incorrer em baixo arrependimento no ambiente de teste $N$ antes de parar (isto é, $Regret_N(\pi, \tau) \le \epsilon$).

O cenário assume acesso a:

• Rollouts de treinamento rotulados: Pares estado-ação $(s, a)$ do especialista $\pi^\star$ no ambiente $M$.
• Rollouts de teste não rotulados: Trajetórias apenas com estados do especialista $\pi^\star$ no ambiente $N$. Esta assimetria modela cenários do mundo real onde a telemetria de ações é custosa ou proprietária (por exemplo, vídeos de câmeras de bordo de direção autônoma sem comandos de direção).

2. Metodologia: SeqRejectron

O algoritmo central, SeqRejectron, generaliza o algoritmo Rejectron de classificação seletiva (Goldwasser et al., 2020) para tomada de decisão sequencial. A ideia central é que, em vez de tomar decisões independentes em cada passo de tempo (o que leva a uma complexidade de amostra dependente do horizonte), o algoritmo certifica prefixos de trajetória inteiros usando um conjunto esparsos de políticas validadoras.

Mecanismo Central

1. Política Base: O agente seleciona uma política base $\pi_0$ consistente com os dados de treinamento (por exemplo, Estimativa de Máxima Verossimilhança).
2. Conjuntos Validadores: O algoritmo constrói um pequeno conjunto de políticas "validadoras" $\Phi$ retiradas do espaço de versões (políticas consistentes com os dados de treinamento).
3. Regra de Parada: O agente executa $\pi_0$ e continua apenas enquanto todas as validadoras em $\Phi$ concordarem com $\pi_0$. O primeiro ponto de discordância dispara uma parada (abstenção).
4. Distribuição Esparsa de Validadores: Uma contribuição teórica crítica é a prova de que um conjunto validador esparso (tamanho independente do horizonte $H$) é suficiente para garantir segurança. Isso é alcançado via um argumento minimax sobre um jogo de soma zero entre um "desafiante" (escolhendo uma política concorrente) e um "validador" (escolhendo um conjunto de validadoras).

Variantes para Diferentes Cenários

O artigo adapta este framework para três cenários progressivamente mais gerais:

• Políticas Determinísticas:

  • Mecanismo: Usa um teste de discordância binária. O tempo de parada $\tau$ é o primeiro passo onde qualquer validadora $\pi \in \Phi$ discorda de $\pi_0$.
  • Implementação: A distribuição validadora é construída usando dinâmicas sem arrependimento (especificamente, uma redução eficiente em oráculo para Aprendizado de Múltiplos Instâncias Realizáveis Ponderado).
  • Resultado: Alcança complexidade de amostra livre de horizonte $\tilde{O}(\sqrt{\log|\Pi|/n})$ sob custos esparsos.

• Políticas Estocásticas:

  • Desafio: A discordância binária é muito grosseira; as distribuições podem diferir "suavemente" a cada passo sem uma única discrepância alarmante.
  • Mecanismo: Substitui o teste binário por um tempo de parada baseado na distância de Hellinger cumulativa. O agente para quando a distância de Hellinger quadrada acumulada entre $\pi_0$ e qualquer validadora excede um limiar $\theta$.
  • Resultado: Fornece limites de amostra finita na distância de Hellinger das trajetórias paradas. O artigo estabelece um limite inferior de $\Omega(1/\epsilon^3)$ para a complexidade de amostra rotulada no cenário estocástico de passo único, correspondendo à parte impulsionada por custos do limite superior.

• Classes de Políticas Especificadas Incorretamente:

  • Desafio: O especialista $\pi^\star$ pode não pertencer à classe de políticas do agente $\Pi$.
  • Mecanismo: Substitui a restrição rígida do espaço de versões por um jogo regularizado simetricamente. As validadoras são permitidas a discordar da política base nos dados fonte, mas essa discordância é penalizada.
  • Resultado: Os garantias degradam-se graciosamente com a quantidade de especificação incorreta (medida pelo erro de especificação incorreta melhor da classe $\Delta$).

3. Contribuições e Resultados Chave

Garantias Teóricas

• Complexidade Livre de Horizonte: Para políticas determinísticas, a complexidade de amostra é independente do horizonte $H$ (exceto através da escala total de custos $C_{max}$), escalando como $\tilde{O}(\sqrt{\log|\Pi|/n})$. Isso melhora as reduções ingênuas passo a passo que sofrem uma penalidade de $O(H^2)$.
• Validação Esparsa: O artigo prova a existência de uma distribuição validadora suportada em conjuntos de tamanho $O(1/\epsilon)$, independente do espaço de estados, espaço de ações ou horizonte.
• Limites Inferiores: Os autores provam um limite inferior de $\Omega(1/\epsilon^3)$ para a complexidade de amostra rotulada no cenário estocástico de passo único, mostrando que a dependência cúbica em $1/\epsilon$ é inevitável para regimes impulsionados por custos.
• Robustez à Especificação Incorreta: O framework estende-se para cenários agnósticos onde o especialista não está na classe, com limites de arrependimento que escalam com a raiz quadrada do erro de especificação incorreta.

Avaliação Empírica

Os autores avaliam o SeqRejectron no ambiente LunarLander-v3.

• Configuração: O treinamento ocorre em um ambiente sem vento; o teste ocorre em um ambiente ventoso com impulsos iniciais diferentes.
• Descobertas: O algoritmo detecta com sucesso dinâmicas fora da distribuição. Ao ajustar um limiar de segurança $\theta$, os autores demonstram uma compensação onde a política abstenção minimamente em dados dentro da distribuição (treinamento) enquanto para confiavelmente em dados fora da distribuição (teste), prevenindo falhas catastróficas. O número de validadoras mostrou-se robusto, com o desempenho saturando rapidamente.

4. Significado e Alegações

O artigo alega estabelecer a abstenção como uma resposta principiada e teoricamente fundamentada a deslocamentos de dinâmicas não antecipados no aprendizado por imitação.

• Além de Heurísticas: Diferentemente de abordagens de RL robusto ou randomização de domínio que exigem suposições sobre a natureza do deslocamento ou acesso online à distribuição de teste, o SeqRejectron fornece garantias PAC livres de distribuição usando apenas dados offline.
• Análogo Sequencial de Aprendizado PQ: O trabalho se posiciona como um análogo sequencial ao framework de aprendizado PQ (Goldwasser et al., 2020), estendendo a capacidade de abster-se de previsões únicas para prefixos inteiros de trajetória.
• Mecanismo de Segurança: Ao desacoplar a decisão de o que fazer de quando parar, o framework oferece um mecanismo de segurança que impede que o agente leve o sistema a estados irrecuperáveis quando seus dados de treinamento são não informativos.

Os autores reconhecem limitações, observando que o cenário estocástico atualmente carece de uma redução computacional eficiente em oráculo (diferentemente do caso determinístico) e que as taxas de complexidade de amostra impulsionadas pela variância para políticas estocásticas permanecem uma lacuna aberta entre os limites superior e inferior. Eles também sugerem que trabalhos futuros poderiam incorporar conhecimento estrutural parcial (por exemplo, distância TV limitada) para apertar as taxas de parada no lado do teste.