Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learning

技術要約：ニューロンのないスマートな交通手段 — 表形式強化学習による公平なメトロネットワーク拡張

問題定義
本論文は、交通ネットワーク設計問題（TNDP）の特定のサブセットである、メトロネットワーク拡張問題（MNEP）を取り扱う。目的は、建設予算（$B$）と最大駅数（$T$）の制約条件下で、既存の都市ネットワーク内に新しいメトロ路線を設計し、捕捉される移動需要を最大化することである。伝統的に、MNEPは都市をグリッドとして表現する組合せ最適化問題としてモデル化され、目標は、満たされる起点・終点（OD）需要の合計を最大化するような隣接セルのシーケンス（線）を見つけることである。

既存の文献における課題として、これらの問題に対する深層強化学習（Deep RL）への依存が挙げられる。Deep RLは複雑な逐次的意思決定において成功を収めているが、計算コストが高く、環境負荷も大きく、多くの場合「ブラックボックス」として機能し、解釈性に欠ける。著者らは、MNEPは本質的に静的な最適化問題であり、入力特徴量が限定的で、固有のスケーラビリティ制約（例：固定された駅間隔）を持つため、複雑なニューラルネットワークは必ずしも必要ではないと主張している。さらに、既存のアプローチは社会的な公平性よりも効率性（功利主義）を優先する傾向があり、異なる社会経済的グループ間での輸送利益の公平な分配を十分に扱うことができていない。

手法
著者らは、問題の再定式化と、社会的な公平性の基準を明示的に組み込んだ表形式強化学習（Tabular Reinforcement Learning）を組み合わせた、新しいフレームワークを提案している。

1. 問題の再定式化 (NMRDP):
   MNEPを非マルコフ報酬決定プロセス（NMRDP）として再定式化する。すべてのグリッドセルを潜在的なアクションとして扱う従来のDeep RLアプローチ（アクション空間がグリッドサイズ $O(n \times m)$ に比例して増大する）とは異なり、提案手法はプロセスを2つのステージに分離する：

   • 初期状態の選択: エージェントはメトロ線の始点となるセルを選択する。
   • 逐次的ナビゲーション: エージェントは、8つの離散的な方向（N, S, E, W, および4つの斜め方向）を選択することでグリッド内を移動する。
     これにより、初期選択後のすべてのステップにおいて、アクション空間は定数サイズである8へと削減され、時間計算量は $O(1)$ に減少する。状態はエージェントの現在位置に簡略化される。報酬は、直接需要および乗り換え需要を計算するために訪問した駅の履歴に依存するため、プロセスは厳密なマルコフ性を逸脱しており、これがNMRDPの定式化につながる。

2. アルゴリズム (Monte Carlo Tabular RL):
   著者らは、モンテカルロ法に基づく表形式強化学習アルゴリズムを採用している。エージェントは2つのテーブルを保持する：

   • $V_{start}(S_0)$: 特定のセルを始点として選択することによる期待リターンを推定する。
   • $Q(S, A)$: 現在の状態から特定の方向アクションを取ることの価値を推定する。
     エージェントは、探索と利用のために $\epsilon$-greedy戦略を使用する。更新は各エピソードの終了時に、推定されたリターンと実際の総リターン $J$ との差に基づき、$V$ 値および $Q$ 値を調整することでモンテカルロ推定を用いて行われる。

3. 社会的公平性の統合:
   報酬関数は、単純な需要最大化を超えて、社会的な公平性を組み込むよう拡張されている。著者らは、社会経済指標（具体的には発展のプロキシとしての住宅価格指数）に基づいてグループ（$G$）を定義し、3つの報酬定式化をテストしている：

   • 功利主義 (最大効率): 総満足需要を最大化する。
   • 等しい分配 (水平的公平性): グループ間の利益の格差を最小化するために一般化ジニ係数（GGI）を使用する。
   • ロールズ的正義 (垂直的公平性): 最も不遇なグループ（最低住宅価格五分位層）の利益を最大化する。

主な貢献

• 問題の再定式化: MNEPを、アクション空間をデカップリングしたNMRDPとして再定式化することで、解空間を制限することなく、単純な表形式手法の使用を可能にし、探索空間の複雑さを劇的に削減できることを実証した。
• アルゴリズムの効率性: Deep RLと比較して、大幅に少ないトレーニングエピソードで競争力のある性能を達成する、モンテカルロ・表形式強化学習アルゴリズムを提案した。
• 公平性を考慮したフレームワーク: 効率性と公平性のバランスを取るための柔軟なメカニズムを提供するために、多様な社会的善の目的（功利主義、平等主義、ロールズ的正義）を強化学習フレームワークに統合した。
• 解釈性: 表形式手法の使用は、Deep RLの潜在表現とは異なり、意思決定者が最適な方策、報酬分布、およびQ値を直接可視化できるという、固有の解釈性を提供する。

実験結果
本手法は、中国の西安とオランダのアムステルダムという2つの実世界の環境で評価された。

• パフォーマンス: TabularMNEPは、すべての報酬関数（Efficiency, GGI(2), GGI(4), Rawls）において、最先端のDeep RL手法と同等の性能を達成した。いくつかのケースでは、Deep RLをわずかに下回ったものの、信頼区間内に留まっており、遺伝的アルゴリズムや貪欲探索（Greedy Search）のベースラインを大幅に上回った。
• 効率性: Tabularアプローチは、Deep RLのベースラインが必要とした448,000エピソードに対し、わずか25,000エピソードのトレーニングで済んだ（18倍の削減）。
• 環境負荷: トレーニング時間の短縮とGPUへの依存度の低さにより、Tabular手法は推定炭素排出量を平均で12分の1に削減した（比較の公平性のためにGPUノード上でテストされたが）。
• 公平性の結果: 実験により、異なる報酬関数がネットワーク設計を効果的に変化させることが確認された。最大効率（Max Efficiency）は高需要エリア（多くの場合、富裕層が多い）を優先したが、GGIおよびロールズの報酬は、全体の効率性をある程度犠牲にしつつも、低所得層への利益の再分配に成功した。

意義と主張
本論文は、MNEPのような組合せ最適化問題において、複雑なブラックボックス型のディープラーニングモデルが必ずしも必要ではないと主張している。問題の構成を工夫してアクション空間を削減することで、より単純で、リソース効率が高く、解釈可能な表形式手法を用いることで、最先端の結果を得ることができる。著者らは、このアプローチが「再現可能で、モジュール式、解釈可能、かつリソース効率の高いソリューション」を提供することを強調している。

本研究は、自動化された交通計画において社会的公平性を考慮することの重要性を浮き彫りにしており、強化学習が効率を過度に損なうことなく、公平性のためにチューニング可能であることを示している。しかし、著者らはスケーラビリティに関して慎重な姿勢を維持しており、表形式手法は制約された状態空間を持つMNEPには適しているものの、本質的に巨大な状態表現を持つ問題には汎用できない可能性があることを認めている。また、報酬設計と人間の監視がなければ、自動化された意思決定が都市計画における既存のバイアスを強化するリスクがあることにも注意を促している。