Resumo Técnico: Generalizando Além da Subotimalidade em Aprendizado por Reforço Offline para Escalonamento

1. Definição do Problema

O artigo aborda o Problema de Escalonamento de Oficina Flexível (JSP) e o Problema de Escalonamento de Oficina Flexível (FJSP). O objetivo é escalonar um conjunto de tarefas em máquinas disponíveis para minimizar o makespan (o tempo de conclusão da última operação).

• JSP: Cada operação deve ser processada por uma máquina específica única.
• FJSP: Cada operação pode ser processada por qualquer máquina de um subconjunto compatível.
• Desafio: Métodos exatos (ex: Programação por Restrições) garantem otimalidade, mas carecem de escalabilidade para instâncias grandes. Heurísticas (ex: Algoritmos Genéticos, Regras de Escalonamento de Prioridade) são escaláveis, mas subótimas.
• Limitações Atuais do RL: Métodos de Aprendizado por Reforço Profundo (DRL) Online (ex: L2D, DANIEL) alcançam um desempenho forte, mas sofrem de ineficiência de amostragem, exigindo interação extensiva com ambientes simulados para convergir. Por outro outro lado, métodos de RL offline têm tido dificuldades em aprender a partir de dados subótimos em escalonamento, frequentemente dependendo de demonstrações de especialistas quase ótimas ou falhando em generalizar além da distribuição dos dados.

2. Metodologia: Conservative Discrete Quantile Actor-Critic (CDQAC)

Os autores propõem o CDQAC, um algoritmo de RL offline projetado para aprender políticas de escalonamento eficazes diretamente de conjuntos de dados estáticos e subótimos (incluindo aqueles gerados por heurísticas aleatórias) sem interação com o ambiente.

Componentes Principais

1. Crítico de Quantis Conservador com Arquitetura Dueling:

   • Em vez de estimar um retorno esperado escalar $Q(s,a)$, o CDQAC modela a distribuição completa do retorno $Z_\theta(s,a)$ usando regressão de quantis. Isso captura a variância nos resultados para uma única ação, o que é crucial no escalonamento, onde a mesma ação pode levar a makespans vastamente diferentes dependendo das decisões futuras.
   • Utiliza uma arquitetura de Rede Dueling que separa o fluxo de valor de estado $V_\theta(s)$ do fluxo de vantagem $A_\theta(s,a)$.
   • Novidade: Ao contrário das redes dueling padrão que alimentam o mesmo input para ambos os fluxos, o CDQAC utiliza inputs separados: $V_\theta$ recebe apenas o embedding global do estado, enquanto $A_\theta$ recebe embeddings específicos de operação, máquina e par. Isso estabiliza o aprendizado ao evitar que estimativas de vantagem ruidosas corrompam o valor do estado global.

2. Regularização de Aprendizado de Q Conservador (CQL):

   • Para evitar a superestimação de ações Fora da Distribuição (OOD) (um modo comum de falha no RL offline), o CDQAC integra uma penalidade CQL.
   • A perda do crítico combina a perda de Diferença Temporal (TD) com um termo de regularização que penaliza a superestimação de ações não presentes no conjunto de dados, garantindo que a política aprendida permaneça conservadora em pares estado-ação não vistos.

3. Atualizações de Política Atrasadas:

   • No RL discreto offline com espaços de ação de tamanho variável, estimativas iniciais ruidosas do crítico podem propagar erros através de alvos de bootstrap.
   • O CDQAC atualiza a rede de política apenas a cada $\eta$ passos do crítico (definido como 4 nos experimentos). Isso permite que o crítico de quantis se estabilize e se ajuste à distribuição de retorno antes de ser usado para guiar a melhoria da política, evitando a convergência prematura para ótimos locais subótimos.

4. Arquitetura de Rede:

   • O algoritmo utiliza uma Rede de Atenção Dupla (DAN) para codificar a instância de escalonamento. A DAN processa operações e máquinas através de blocos de atenção separados para capturar restrições complexas de precedência e recursos, gerando embeddings para o ator e o crítico.

3. Principais Contribuições

1. Inovação Algorítmica: Introdução do CDQAC, o primeiro método de RL offline para JSP/FJSP que aprende políticas eficazes puramente a partir de dados subótimos (incluindo políticas aleatórias), superando tanto as heurísticas geradoras de dados quanto os baselines de RL online de última geração.
2. Design Arquitetural: Um crítico de quantis dueling inovador com inputs separados e atualizações de política atrasadas, especificamente adaptado para lidar com os espaços de ação discretos, de tamanho variável e combinatórios de problemas de escalonamento.
3. Insight Teórico sobre Qualidade de Dados: O artigo desafia o paradigma convencional de RL offline (onde dados de "especialista ruidoso" são superiores a dados aleatórios). Argumenta-se que, para o escalonamento, a cobertura estado-ação é o fator determinante para o desempenho, não a qualidade dos dados. Isso se deve a duas propriedades estruturais do escalonamento:
   • Recompensa Densa e Alinhada ao Objetivo: O sinal de recompensa (aumento negativo do makespan parcial) é denso e perfeitamente alinhado com o objetivo de otimização, ao contrário das recompensas esparsas na robótica.
   • Trajetórias de Comprimento Igual: Todas as heurísticas construtivas (especialistas ou aleatórias) geram trajetórias de comprimento idêntico (igual ao número de operações), eliminando o viés de comprimento de trajetória que tipicamente favorece dados de especialistas.
   • Consequentemente, uma política aleatória fornece a cobertura estado-ação mais ampla, tornando-a a fonte de treinamento ideal para o RL offline neste domínio.

4. Resultados Experimentais

Os autores avaliaram o CDQAC nos benchmarks padrão de JSP (Taillard, Demirkol) e FJSP (Brandimarte, Hurink), bem como em instâncias geradas.

• Desempenho vs. Baselines:

  • O CDQAC superou consistentemente os baselines de RL online (DANIEL, Residual, FJSP-DRL, L2D) em ambos os benchmarks de JSP e FJSP, mesmo quando treinado em dados aleatórios.
  • Superou outros métodos de RL offline (Offline-LD, IQL, Clonagem de Comportamento) e as heurísticas usadas para gerar os conjuntos de dados.
  • Notavelmente, o CDQAC treinado em dados Aleatórios (Random) alcançou os melhores resultados, superando modelos treinados com dados de Algoritmo Genético (GA) ou Regra de Escalonamento de Prioridade (PDR).

• Eficiência de Amostragem:

  • O CDQAC é altamente eficiente em termos de amostragem, exigindo apenas 1% a 5% do tamanho original do conjunto de dados (ex: 10–25 instâncias de treinamento) para aprender políticas de alta qualidade.
  • Ele generaliza bem de instâncias pequenas de treinamento (ex: $10 \times 5$) para instâncias maiores e não vistas (ex: $40 \times 10$), superando os baselines online nesses cenários fora da distribuição.

• Estudos de Ablação:

  • A remoção da Atualização de Política Atrasada causou uma degradação massiva no desempenho (aumento de até 112% no gap) em instâncias $20 \times 10$, confirmando sua necessidade para estabilidade em grandes espaços de ação.
  • A Arquitetura Dueling com inputs separados também mostrou importância significativa conforme o tamanho da instância aumentava.
  • Experimentos com estruturas de recompensa modificadas (esparsas ou de proxy) e terminação precoce confirmaram que o fenômeno "dados aleatórios são melhores" depende estritamente das propriedades de recompensa densa e trajetória de comprimento igual do escalonamento padrão.

5. Significância e Alegações

O artigo afirma que o CDQAC representa uma mudança significativa na forma como o RL offline deve ser abordado para problemas de otimização combinatória como o escalonamento.

• Mudança de Paradigma: Demonstra que a suposição padrão de RL offline — de que dados de especialista de alta qualidade são necessários para o sucesso — não se sustenta para o escalonamento. Em vez disso, a ampla cobertura do espaço estado-ação é a restrição crítica.
• Aplicabilidade Prática: Ao aprender a partir de heurísticas subótimas ou aleatórias, o CDQAC remove a necessidade de simuladores caros (para treinamento online) ou solvers de especialistas computacionalmente intensivos (como CP) para gerar dados de treinamento. Isso torna o RL offline uma solução viável e escalável para o escalonamento do mundo real, onde construir um simulador perfeito é inviável, mas existem dados históricos subótimos.
• Estado da Arte: Os autores posicionam o CDQAC como o primeiro método de RL offline a superar o RL online em JSP/FJSP enquanto treina exclusivamente em dados aleatórios, estabelecendo um novo benchmark de eficiência e desempenho neste domínio.