Resumen Técnico: Aprendizaje por Refuerzo Multi-Agente a partir de Retroalimentación Retardada del Mercado para la Adaptación de Pesos de Objetivos en Despacho Tripartito

Planteamiento del Problema

El despacho de entrega de alimentos opera como un problema de decisión secuencial dentro de un mercado de tres lados que involucra a clientes, comercios y repartidores. El desafío central radica en equilibrar objetivos contrapuestos: agrupación (batching — agrupar pedidos para mejorar la eficiencia del repartidor) frente a velocidad (minimizar el tiempo de entrega para mejorar la experiencia del cliente).

En entornos de producción como DoorDash, este compromiso se gestiona tradicionalmente mediante pesos heurísticos estáticos que se ajustan manualmente de forma global. Estos pesos estáticos son frágiles ante condiciones locales variables en el tiempo; por ejemplo, una agrupación excesiva durante la congestión aumenta la tardanza, mientras que una agrupación insuficiente durante periodos de baja demanda desperdicia eficiencia. Además, el sistema debe evaluar las decisiones no mediante etiquetas de preferencia humana inmediata, sino mediante resultados operativos retardados (por ejemplo, velocidad de entrega, utilización del repartidor, congestión del comercio) que están acoplados a través de la red. Los enfoques de Aprendizaje por Refuerzo (RL) existentes a menudo intentan reemplazar por completo el optimizador de asignación combinatoria, lo que plantea riesgos significativos para la viabilidad y seguridad en producción.

Metodología

Los autores presentan un sistema de RL fuera de línea (offline) desplegado que adapta los pesos de los objetivos de despacho en tiempo real sin reemplazar el optimizador de asignación de producción existente. El sistema emplea una arquitectura de decisión de dos capas:

1. Capa Interna (Optimizador): Un optimizador de asignación combinatoria que mapea pedidos, repartidores y restricciones hacia asignaciones factibles basadas en los pesos de los objetivos.
2. Capa Externa (Agente OWA-RL): Un agente de política a nivel de tienda que observa los estados locales del mercado y selecciona un multiplicador discreto para ajustar los pesos de los objetivos del optimizador.

Formulación

El problema se formula como un proceso de decisión de Markov (MDP) multi-agente descentralizado con entrenamiento fuera de línea centralizado:

• Agentes: Cada tienda $i$ actúa como un agente.
• Estado ($s_t$): Incluye el recuento de entregas pendientes ($d_t$), el tiempo de espera del repartidor ($cwt_t$) y una característica de presión de suministro localizada ($sup_t$). La presión de suministro se reescala mediante el suministro efectivo de repartidores para exponer las variaciones a nivel de tienda ocultas por las señales regionales.
• Acción ($a_t$): Un multiplicador discreto del conjunto $\{0.8, 0.9, 1.0, 1.1, 1.2\}$ aplicado al peso base del objetivo de velocidad de entrega (peso ASAP).
  • Pesos más bajos favorecen la agrupación y la eficiencia de la ruta.
  • Pesos más altos priorizan la finalización rápida de los pedidos.
  • La acción neutral ($1.0$) recupera el valor base estático.
• Recompensa ($r_t$): Una recompensa multi-objetivo retardada y agregada a nivel regional para capturar los efectos de red. Se define como una suma ponderada de:
  • ASAP: Duración de la entrega desde la perspectiva del cliente ($t_{drop} - t_{create}$).
  • XCAT: Tiempo de actividad excedente del repartidor más allá de la ruta directa ($CAT - T_{direct}$).
  • La función de recompensa es $r = -\frac{1}{|D|} \sum (\alpha \cdot \text{ASAP} + \beta \cdot \text{XCAT})$.

Arquitectura de Entrenamiento

El sistema utiliza aprendizaje por refuerzo fuera de línea entrenado con datos de mercado registrados:

• Algoritmo: Double DQN (Deep Q-Network Doble) con una función de valor compartida $Q_\theta(s, a)$.
• Objetivos: Utiliza objetivos de Double Q-learning para reducir el sesgo de maximización:
  $$y_t = r_t + \gamma Q_{\bar{\theta}}(s_{t+1}, \arg\max_{a'} Q_\theta(s_{t+1}, a'))$$
• Regularización Conservadora: Para prevenir la sobreestimación de valores fuera de la distribución (OOD) —un problema crítico en el RL fuera de línea— los autores incorporan un regularizador de Aprendizaje Q Conservador (CQL) que penaliza las acciones que no están bien soportadas por la distribución de los datos registrados.
• Función de Pérdida: $L(\theta) = L_{\text{DDQN}}(\theta) + \eta L_{\text{CQL}}(\theta)$.

Contribuciones Clave

El artículo describe tres contribuciones principales:

1. Arquitectura de RL para la Adaptación de Pesos de Objetivos: Introduce un sistema que aprende de la retroalimentación del mercado para adaptar los pesos de despacho mediante una interfaz de control de baja dimensión, preservando el optimizador de producción existente en lugar de reemplazarlo.
2. Formulación Multi-Agente Fuera de Línea: Formula el problema como una tarea de toma de decisiones multi-agente fuera de línea con ejecución descentralizada a nivel de tienda y recompensas regionales retardadas, abordando los desafíos de la retroalimentación ruidosa, retardada y acoplada.
3. Validación en Producción: Proporciona evidencia de un experimento de switchback en producción demostrando que la política aprendida puede aumentar la agrupación y reducir los costos de tiempo del lado del repartidor sin degradar la calidad de la entrega para el cliente.

Resultados Experimentales

El sistema fue evaluado en un experimento de switchback global durante dos semanas, aleatorizando aproximadamente 4,000 regiones geográficas entre un grupo de control (pesos base estáticos) y un grupo de tratamiento (política OWA-RL).

Hallazgos Clave (Todos los periodos del día):

• Ganancias de Eficiencia:
  • Tiempo Activo del Repartidor (CAT): Reducido en 1.26 segundos (estadísticamente significativo, $p=0.019$).
  • Tiempo de Espera del Repartidor (CWT): Reducido en 0.86 segundos (estadísticamente significativo, $p=0.004$).
  • Tasa de Agrupación (Batching Rate): Incrementada en 0.495 puntos porcentuales (estadísticamente significativo, $p < 0.001$).
• Preservación de la Calidad:
  • ASAP (Velocidad de Entrega): Sin degradación estadísticamente significativa ($p=0.264$).
  • Tardanza de 20 Minutos: Sin degradación estadísticamente significativa ($p=0.237$).

Rendimiento en la Hora Pico de la Cena:
Se observaron tendencias similares durante las horas de la cena, con reducciones significativas en CAT y CWT, aumento en la agrupación y ligeras mejoras en la tardanza de 20 minutos, mientras que el ASAP se mantuvo estable.

La política demostró una adaptación dependiente del estado, desplazando la masa de probabilidad hacia multiplicadores más bajos (favoreciendo la agrupación) durante regímenes específicos de acumulación de pedidos y suministro, en lugar de aplicar un reajuste global fijo.

Significado y Reivindicaciones

El artículo sostiene que este trabajo ilustra cómo la retroalimentación del mundo real de un sistema logístico y económico vivo puede utilizarse para adaptar de forma segura las políticas de decisión en línea. Al restringir al agente de RL a una interfaz de control de bajo nivel de pesos de objetivos, el sistema mantiene la viabilidad de producción y las salvaguardas operativas, permitiendo al mismo tiempo la adaptación local a condiciones dinámicas.

Los autores enfatizan que este enfoque permite el despliegue seguro de RL en sistemas con impactos reales en la operación y el trabajo mediante:

• El uso de una capa de control restringida para garantizar la fiabilidad y la escalabilidad.
• El empleo de salvaguardas de RL fuera de línea (CQL) para manejar los cambios de distribución y la escasez de datos.
• El apoyo en la experimentación en línea (switchback) para validar la seguridad y eficacia antes de su despliegue total.

El trabajo sirve como un caso de estudio para la integración de RL en mercados complejos de tres lados donde las decisiones afectan a múltiples partes interesadas y los resultados son retardados y acoplados.