技術要約：3面市場のディスパッチにおける目的関数重みの適応のための、遅延するマーケットプレイス・フィードバックを用いたマルチエージェント強化学習

問題定義

フードデリバリーのディスパッチ（配車）は、顧客、マーチャント（加盟店）、およびカリアー（配達員）が関与する3面市場における逐次的な意思決定問題として機能する。核心となる課題は、相反する目的のバランスを取ることである：すなわち、バッチング（カリアーの効率向上のために注文をグループ化すること）と、スピード（顧客体験を向上させるために配送時間を最小化すること）のトレードオフである。

DoorDashのようなプロダクション環境において、このトレードオフは伝統的に、グローバルに手動調整された静的なヒューリスティック重みによって管理されている。これらの静的な重みは、局所的かつ時間的に変化する条件下では脆弱である。例えば、混雑時における過度なバッチングは遅延を招き、一方で需要が少ない期間におけるバッチング不足は効率を無駄にする。さらに、本システムは、人間の好みのラベルによる即時的な評価ではなく、ネットワーク全体で結合された遅延するオペレーショナルな結果（例：配送速度、カリアーの稼働率、マーチャントの混雑状況）によって意思決定を評価しなければならない。既存の強化学習（RL）アプローチは、組み合わせ最適化器そのものを完全に置き換えようとする傾向があるが、これはプロダクションにおける実現可能性と安全性に対して大きなリスクをもたらす。

手法

著者らは、既存のプロダクション用アサインメント最適化器を置き換えることなく、リアルタイムでディスパッチの目的関数重みを適応させる、デプロイ済みのオフラインRLシステムを提示している。このシステムは、2層の意思決定アーキテクチャを採用している：

1. インナーレイヤー（最適化器）： 注文、カリアー、および制約条件を、目的関数の重みに基づいて実行可能な割り当てへとマッピングする、組合せ最適化アサインメント最適化器。
2. アウタレイヤー（OWA-RLエージェント）： 局所的なマーケットプレイスの状態を観測し、最適化器の目的関数重みを調整するための離散的なマルチプライヤー（乗数）を選択する、ストアレベルのポリシーエージェント。

定式化

本問題は、中央集中型のオフライン学習を用いた、**分散型マルチエージェント・マルコフ決定過程（MDP）**として定式化されている：

• エージェント： 各ストア $i$ がエージェントとして機能する。
• 状態 ($s_t$)： 未完了の配送数 ($d_t$)、カリアーの待ち時間 ($cwt_t$)、および局所的なサプライプレッシャー特徴量 ($sup_t$) を含む。サプライプレッシャーは、リージョナルな信号によって隠蔽されているストアレベルの変動を露出させるため、実効的なカリアー供給量によって再スケーリングされる。
• アクション ($a_t$)： ベースラインの配送速度目的関数重み（ASAP重み）に適用される、集合 $\{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)。
• ターゲット： 最大化バイアスを軽減するために、Double Q-learningターゲットを使用する：
  $$y_t = r_t + \gamma Q_{\bar{\theta}}(s_{t+1}, \arg\max_{a'} Q_\theta(s_{t+1}, a'))$$
• 保守的な正則化： オフラインRLにおける重大な問題である、分布外（OOD）の価値過大評価を防ぐため、著者らは**保守的Q学習（Conservative Q-Learning: CQL）**正則化を組み込んでいる。これは、ログデータの分布によって十分にサポートされていないアクションに対してペナルティを課すものである。
• 損失関数： $L(\theta) = L_{\text{DDQN}}(\theta) + \eta L_{\text{CQL}}(\theta)$。

主な貢献

本論文は、主に以下の3つの貢献を述べている：

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分遅延： 統計的に有意な劣化なし ($p=0.237$)。

ディナーピーク時のパフォーマンス：
ディナータイム中にも同様の傾向が見られ、CATとCWTの有意な減少、バッチングの増加、および20分遅延のわずかな改善が観察されたが、ASAPは安定していた。

ポリシーは状態依存の適応を示し、固定されたグローバルな再チューニングを行うのではなく、特定のバックログや供給体制において、低いマルチプライヤー（バッチングを優先）へと確率質量をシフトさせた。

重要性と主張

本論文は、本研究が、生きた経済および物流システムからのワールドフィードバックを、オンラインで意思決定ポリシーを安全に適応させるためにどのように利用できるかを示していると主張している。RLエージェントを低次元の目的関数重みのインターフェースに制約することで、システムは動的な条件への局所的な適応を可能にしながら、プロダクションの実現可能性と運用の安全策を維持している。

著者らは、以下の手法を用いることで、現実世界のオペレーションや労働に影響を与えるシステムへのRLの安全な導入が可能であることを強調している：

• 信頼性とスケーラビリティを確保するための制約付き制御レイヤーの活用。
• 分布の変化とデータの疎性を扱うための**オフラインRLの安全策（CQL）**の採用。
• 全面的な展開の前に、安全性と有効性を検証するための**オンライン実験（スイッチバック）**への依存。

本研究は、意思決定が複数のステークホルダーと遅延・結合したアウトカムに影響を与える、複雑な3面市場におけるRLの統合に関するケーススタディとなっている。