分散型マルチエージェントシステム（MAS）は、群ロボティクスや交通経路の最適化などの応用において重要な役割を果たしています。本研究では、確率的最短経路（SSP）問題の分散型マルチエージェントバージョンであるDec-MASSPsに注目し、線形関数近似の下での学習の難しさを明らかにします。特に、遷移ダイナミクスやコストが線形モデルで表現される場合の最適政策の構造を特定します。本論文の主な貢献は、任意のエージェント数に対して難易度の高いインスタンスの構築に基づく初の後悔の下限を示すことです。この結果、学習の難しさはオメガ（√K）のスケールであることが確認され、分散型制御の学習複雑性をより明確にし、効率的な学習アルゴリズムの設計に資することが期待されます。