Resumo Técnico: Aprendizado por Reforço Multiagente a partir de Feedback de Mercado com Atraso para Adaptação de Pesos de Objetivos em Despacho Tripartite

Declaração do Problema

O despacho de entrega de alimentos opera como um problema de decisão sequencial dentro de um mercado de três lados envolvendo clientes, estabelecimentos e entregadores. O desafio central reside em equilibrar objetivos conflitantes: agrupamento (batching) (agrupar pedidos para melhorar a eficiência do entregador) versus velocidade (minimizar o tempo de entrega para melhorar a experiência do cliente).

Em ambientes de produção como o DoorDash, esse equilíbrio é tradicionalmente gerenciado por pesos heurísticos estáticos que são ajustados manualmente de forma global. Esses pesos estáticos são frágeis sob condições locais variáveis no tempo; por exemplo, o excesso de agrupamento durante a congestão aumenta o atraso, enquanto o subagrupamento durante períodos de baixa demanda desperdiça eficiência. Além além disso, o sistema deve avaliar decisões não por rótulos de preferência humana imediatos, mas por resultados operacionais atrasados (ex: velocidade de entrega, utilização de entregadores, congestão de estabelecimentos) que estão acoplados em toda a rede. As abordagens de Aprendizado por Reforço (RL) existentes frequentemente tentam substituir inteiramente o otimizador combinatório de atribuição, o que acarreta riscos significativos para a viabilidade e segurança da produção.

Metodologia

Os autores apresentam um sistema de RL offline implantado que adapta os pesos dos objetivos de despacho em tempo real sem substituir o otimizador de atribuição de produção existente. O sistema emprega uma arquitetura de decisão de duas camadas:

1. Camada Interna (Otimizador): Um otimizador de atribuição combinatória que mapeia pedidos, entregadores e restrições para atribuições viáveis com base nos pesos dos objetivos.
2. Camada Externa (Agente OWA-RL): Um agente de política de nível de loja que observa estados locais do mercado e seleciona um multiplicador discreto para ajustar os pesos dos objetivos do otimizador.

Formulação

O problema é formulado como um processo de decisão de Markov (MDP) multiagente descentralizado com treinamento offline centralizado:

• Agentes: Cada loja $i$ atua como um agente.
• Estado ($s_t$): Inclui contagem de entregas pendentes ($d_t$), tempo de espera do entregador ($cwt_t$) e um recurso de pressão de oferta localizado ($sup_t$). A pressão de oferta é reescalonada pela oferta efetiva de entregadores para expor variações no nível da loja ocultas por sinais regionais.
• Ação ($a_t$): Um multiplicador discreto do conjunto $\{0.8, 0.9, 1.0, 1.1, 1.2\}$ aplicado ao peso base do objetivo de velocidade de entrega (peso ASAP).
  • Pesos menores favorecem o agrupamento e a eficiência de roteamento.
  • Pesos maiores priorizam a conclusão rápida do pedido.
  • A ação neutra ($1.0$) recupera a linha de base estática.
• Recompensa ($r_t$): Uma recompensa de múltiplos objetivos atrasada, agregada no nível regional para capturar efeitos de rede. É definida como uma soma ponderada de:
  • ASAP: Duração da entrega voltada ao cliente ($t_{drop} - t_{create}$).
  • XCAT: Tempo de atividade excedente do entregador além da rota direta ($CAT - T_{direct}$).
  • A função de recompensa é $r = -\frac{1}{|D|} \sum (\alpha \cdot \text{ASAP} + \beta \cdot \text{XCAT})$.

Arquitetura de Treinamento

O sistema utiliza aprendizado por reforço offline treinado em dados de mercado registrados:

• Algoritmo: Double DQN (Double Deep Q-Network) com uma função de valor compartilhada $Q_\theta(s, a)$.
• Alvos: Utiliza alvos de Double Q-learning para reduzir o viés de maximização:
  $$y_t = r_t + \gamma Q_{\bar{\theta}}(s_{t+1}, \arg\max_{a'} Q_\theta(s_{t+1}, a'))$$
• Regularização Conservadora: Para evitar a superestimação de valor fora da distribuição (OOD) — um problema crítico em RL offline — os autores incorporam um regularizador de Aprendizado Q Conservador (CQL), que penaliza ações que não são bem suportadas pela distribuição dos dados registrados.
• Função de Perda: $L(\theta) = L_{\text{DDQN}}(\theta) + \eta L_{\text{CQL}}(\theta)$.

Principais Contribuições

O artigo descreve três contribuições principais:

1. Arquitetura de RL para Adaptação de Peso de Objetivo: Introduz um sistema que aprende com o feedback do mercado para adaptar os pesos de despacho via uma interface de controle de baixa dimensão, preservando o otimizador de produção existente em vez de substituí-lo.
2. Formulação Multiagente Offline: Formula o problema como uma tarefa de tomada de decisão multiagente offline com execução descentralizada por loja e recompensas regionais atrasadas, abordando os desafios de feedback ruidoso, atrasado e acoplado.
3. Validação de Produção: Fornece evidências de um experimento de switchback de produção demonstrando que a política aprendida pode aumentar o agrupamento e reduzir os custos de tempo do lado do entregador sem degradar a qualidade da entrega voltada ao cliente.

Resultados Experimentais

O sistema foi avaliado em um experimento de switchback global ao longo de duas semanas, randomizando aproximadamente 4.000 regiões geográficas entre um grupo de controle (pesos de linha de base estáticos) e um grupo de tratamento (política OWA-RL).

Principais Descobertas (Todos os Períodos do Dia):

• Ganhos de Eficiência:
  • Tempo de Atividade do Entregador (CAT): Reduzido em 1,26 segundos (estatisticamente significativo, $p=0,019$).
  • Tempo de Espera do Entregador (CWT): Reduzido em 0,86 segundos (estatisticamente significativo, $p=0,004$).
  • Taxa de Agrupamento (Batching Rate): Aumentou em 0,495 pontos percentuais (estatisticamente significativo, $p < 0,001$).
• Preservação da Qualidade:
  • ASAP (Velocidade de Entrega): Sem degradação estatisticamente significativa ($p=0,264$).
  • Atraso de 20 Minutos: Sem degradação estatisticamente significativa ($p=0,237$).

Desempenho no Pico do Jantar:
Tendências semelhantes foram observadas durante as horas de jantar, com reduções significativas em CAT e CWT, aumento no agrupamento e leves melhorias no atraso de 20 minutos, enquanto o ASAP permaneceu estável.

A política demonstrou adaptação dependente de estado, deslocando a massa de probabilidade para multiplicadores menores (favorecendo o agrupamento) durante regimes específicos de backlog e oferta, em vez de aplicar um ajuste global fixo.

Significância e Alegações

O artigo afirma que este trabalho ilustra como o feedback do mundo de um sistema logístico e econômico vivo pode ser usado para adaptar políticas de decisão online de forma segura. Ao restringir o agente de RL a uma interface estreita de peso de objetivo, o sistema mantém a viabilidade de produção e salvaguardas operacionais, ao mesmo tempo em que permite a adaptação local a condições dinâmicas.

Os autores enfatizam que esta abordagem permite o implante seguro de RL em sistemas com impactos reais de operação e trabalho ao:

• Utilizar uma camada de controle restrita para garantir confiabilidade e escalabilidade.
• Empregar salvaguardas de RL offline (CQL) para lidar com mudanças de distribuição e esparsidade de dados.
• Confiar em experimentação online (switchback) para validar segurança e eficácia antes do implante total.

O trabalho serve como um estudo de caso para a integração de RL em mercados complexos de três lados, onde as decisões afetam múltiplos stakeholders e os resultados são atrasados e acoplados.