Multi-Agent Reinforcement Learning from Delayed Marketplace Feedback for Objective-Weight Adaptation in Three-Sided Dispatch

기술 요약: 3면 시장 배차의 목적 함수 가중치 적응을 위한 지연된 마켓플레이스 피드백 기반 다중 에이전트 강화 학습

문제 정의

음식 배달 배차는 고객, 상점, 쿠리어(배달원)가 참여하는 3면 시장 내에서의 순차적 의사결정 문제로 작동한다. 핵심 과제는 상충하는 목표들, 즉 배칭(배달 효율성을 높이기 위해 주문을 그룹화하는 것)과 속도(고객 경험을 개선하기 위해 배달 시간을 최소 Minimizing 하는 것) 사이의 균형을 맞추는 것이다.

DoorDash와 같은 프로덕션 환경에서 이러한 트레이드오프는 전통적으로 전역적으로 수동 튜닝된 정적 휴리스틱 가중치에 의해 관리된다. 이러한 정적 가중치는 국지적이고 시시각각 변하는 조건 하에서 취약하다. 예를 들어, 혼잡 상황에서의 과도한 배칭은 지연을 증가시키고, 여유로운 기간 동안의 과소 배칭은 효율성을 낭비한다. 또한, 시스템은 즉각적인 인간의 선호도 라벨이 아니라, 네트워크 전체에 걸쳐 결합된 지연된 운영 결과(예: 배달 속도, 쿠리어 활용도, 상점 혼잡도)를 통해 의사결정을 평가해야 한다. 기존의 강화 학습(RL) 접근 방식은 종종 조합 최적화 도구(combinatorial assignment optimizer) 자체를 완전히 대체하려고 시도하는데, 이는 프로덕션의 실현 가능성과 안전성에 상당한 위험을 초래한다.

방법론

저자들은 기존의 프로덕션 할당 최적화 도체를 교체하지 않고, 실시간으로 배차 목적 함수의 가중치를 적응시키는 배포된 오프라인 RL 시스템을 제시한다. 이 시스템은 2계층 의사결정 아키텍처를 채택한다:

1. 내부 계층 (최적화 도구): 목적 함수 가중치에 따라 주문, 쿠리어 및 제약 조건을 목적에 맞는 할당으로 매핑하는 조합 할당 최적화 도구.
2. 외부 계층 (OWA-RL 에이전트): 로컬 마켓플레이스 상태를 관찰하고 최적화 도구의 목적 함수 가중치를 조정하기 위한 이산적 승수를 선택하는 스토어 레벨 정책 에이전트.

정식화

문제는 중앙 집중식 오프라인 학습을 포함하는 **분산형 다중 에이전트 마르코프 결정 과정(MDP)**으로 정식화된다:

• 에이전트: 각 상점 $i$가 하나의 에이전트 역할을 한다.
• 상태 ($s_t$): 미처리 배달 건수 ($d_t$), 쿠리어 대기 시간 ($cwt_t$), 그리고 국지적 공급 압력 특성 ($sup_t$)을 포함한다. 공급 압력은 지역적 신호에 의해 숨겨진 스토어 레벨의 변동을 드러내기 위해 유효 쿠리어 공급량에 의해 재조정된다.
• 행동 ($a_t$): 베이스라인 배달 속도(ASAF) 목적 함수 가중치에 적용되는 이산적 승수 집합 $\{0.8, 0.9, 1.0, 1.1, 1.2\}$이다.
  • 낮은 가중치는 배칭과 라우팅 효율성을 선호한다.
  • 높은 가중치는 더 빠른 주문 완료를 우선시한다.
  • 중립 행동 ($1.0$)은 정적 베이스라인을 복구한다.
• 보상 ($r_t$): 네트워크 효과를 포착하기 위해 지역 레벨에서 집계된 지연된 다목적 보상이다. 이는 다음의 가중 합으로 정의된다:
  • ASAP: 고객 중심의 배달 소요 시간 ($t_{drop} - t_{create}$).
  • XCAT: 직접 경로를 벗어난 초과 쿠리어 활성 시간 ($CAT - T_{direct}$).
  • 보상 함수는 $r = -\frac{1}{|D|} \sum (\alpha \cdot \text{ASAP} + \beta \cdot \text{XCAT})$이다.

학습 아키텍처

시스템은 로그된 마켓플레이스 데이터로 학습된 오프라인 강화 학습을 활용한다:

• 알고리즘: 공유된 가치 함수 $Q_\theta(s, a)$를 사용하는 Double DQN (Double Deep Q-Network)이다.
• 타겟: 최대화 편향(maximization bias)을 줄이기 위해 Double Q-learning 타겟을 사용한다:
  $$y_t = r_t + \gamma Q_{\bar{\theta}}(s_{t+1}, \arg\max_{a'} Q_\theta(s_{t+1}, a'))$$
• 보수적 정규화 (Conservative Regularization): 오프라인 RL의 핵심 문제인 분포 외(OOD) 가치 과대평가를 방지하기 위해, 저자들은 로그된 데이터 분포에 의해 충분히 지원되지 않는 행동에 페널티를 주는 보수적 Q-학습(CQL) 정규화 항을 통합한다.
• 손실 함수: $L(\theta) = L_{\text{DDQN}}(\theta) + \eta L_{\text{CQL}}(\theta)$.

주요 기여

본 논문은 세 가지 주요 기여를 설명한다:

1. 목적 함수 가중치 적응을 위한 RL 아키텍처: 기존 프로덕션 최적화 도구를 대체하는 대신, 저차원 제어 인터페이스를 통해 마켓플레이스 피드백으로부터 학습하여 배차 가중치를 적응시키는 시스템을 도입한다.
2. 오프라인 다중 에이전트 정식화: 분산된 스토어 레벨 실행과 지연된 지역 보상을 갖춘 오프라인 다중 에이전트 의사결정 과제로 문제를 정식화하여, 노이즈가 많고 지연되며 결합된 피드백의 문제를 해결한다.
3. 프로덕션 검증: 학습된 정책이 고객 중심의 배달 품질을 저하시키지 않으면서 배칭을 늘리고 쿠리어 측 시간 비용을 줄일 수 있음을 입증하는 프로덕션 스위치백 실험 결과를 제공한다.

실험 결과

시스템은 약 4,000개의 지리적 영역을 제어군(정적 베이스라인 가중치)과 처치군(OWA-RL 정책) 사이에서 무작위화한 2주간의 글로벌 스위치백 실험을 통해 평가되었다.

주요 결과 (모든 시간대):

• 효율성 이득:
  • 쿠리어 활성 시간 (CAT): 1.26초 감소 (통계적으로 유의함, $p=0.019$).
  • 쿠리어 대기 시간 (CWT): 0.86초 감소 (통계적으로 유의함, $p=0.004$).
  • 배칭 비율: 0.495 퍼센티지 포인트 증가 (통계적으로 유의함, $p < 0.001$).
• 품질 유지:
  • ASAP (배달 속도): 통계적으로 유의한 저하 없음 ($p=0.264$).
  • 20분 지연 (20-Minute Lateness): 통계적으로 유의한 저하 없음 ($p=0.237$).

저녁 피크 시간대 성능:
저녁 시간대에도 유사한 경향이 관찰되었으며, CAT와 CWT의 유의미한 감소, 배칭 증가, 그리고 20분 지연의 약간의 개선이 나타났으나, ASAP는 안정적으로 유지되었다.

정책은 고정된 전역 재조정(retuning)을 적용하는 대신, 특정 백로그 및 공급 체제 동안 낮은 승수(배칭 선호) 쪽으로 확률 질량을 이동시키는 상태 의존적 적응을 보여주었다.

의의 및 주장

본 논문은 실제 경제 및 물류 시스템의 월드 피드백이 어떻게 온라인에서 의사결정 정책을 안전하게 적응시키는 데 사용될 수 있는지를 보여준다. RL 에이전트를 좁은 목적 함수 가중치 인터페이스 내로 제한함으로써, 시스템은 동적인 조건에 대한 국지적 적응을 가능하게 하는 동시에 프로덕션의 실현 가능성과 운영상의 안전장치를 유지한다.

저자들은 다음과 같은 방법을 통해 실제 운영 및 노동에 영향을 미치는 시스템에 RL을 안전하게 배포할 수 있음을 강조한다:

• 신뢰성과 확장성을 보장하기 위한 제한된 제어 계층 활용.
• 분포 변화와 데이터 희소성을 처리하기 위한 오프라인 RL 안전장치(CQL) 적용.
• 전체 배포 전 안전성과 효능을 검증하기 위한 온라인 실험(스위치백) 의존.

이 연구는 의사결정이 여러 이해관계자와 결과에 영향을 미치고 피드백이 지연되며 결합된 복잡한 3면 마켓플레이스에 RL을 통합하는 사례 연구로서 역할을 한다.