論文の概要: Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems

• arxiv url: http://arxiv.org/abs/2511.04594v1
• Date: Thu, 06 Nov 2025 17:49:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-07 20:17:53.542164
• Title: Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems
• Title（参考訳）: 分散マルチエージェント確率的最短経路問題に対するレグレット下界法
• Authors: Utkarsh U. Chavan, Prashant Trivedi, Nandyala Hemachandra,
• Abstract要約: 最短経路(SSP)問題は、このような設定で分散制御をモデル化するための自然なフレームワークを提供する。 線形関数近似による分散マルチエージェントSSP(Dec-MASSP)について検討する。 新たな対称性に基づく議論を応用し、最適政策の構造を同定する。
• 参考スコア（独自算出の注目度）: 1.1575091540914677
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-agent systems (MAS) are central to applications such as swarm robotics and traffic routing, where agents must coordinate in a decentralized manner to achieve a common objective. Stochastic Shortest Path (SSP) problems provide a natural framework for modeling decentralized control in such settings. While the problem of learning in SSP has been extensively studied in single-agent settings, the decentralized multi-agent variant remains largely unexplored. In this work, we take a step towards addressing that gap. We study decentralized multi-agent SSPs (Dec-MASSPs) under linear function approximation, where the transition dynamics and costs are represented using linear models. Applying novel symmetry-based arguments, we identify the structure of optimal policies. Our main contribution is the first regret lower bound for this setting based on the construction of hard-to-learn instances for any number of agents, $n$. Our regret lower bound of $\Omega(\sqrt{K})$, over $K$ episodes, highlights the inherent learning difficulty in Dec-MASSPs. These insights clarify the learning complexity of decentralized control and can further guide the design of efficient learning algorithms in multi-agent systems.
• Abstract（参考訳）: マルチエージェントシステム(MAS)は、スワムロボティクスやトラフィックルーティングといったアプリケーションの中心であり、エージェントは共通の目的を達成するために分散的に調整する必要がある。 Stochastic Shortest Path (SSP)問題は、このような設定で分散制御をモデル化するための自然なフレームワークを提供する。 SSPにおける学習の問題は単一エージェント環境で広く研究されているが、分散化されたマルチエージェントの変種はほとんど探索されていない。 この作業では、そのギャップに対処するための一歩を踏み出します。 本稿では,線形関数近似に基づく分散マルチエージェントSSP(Dec-MASSP)について検討する。 新たな対称性に基づく議論を応用し、最適政策の構造を同定する。 私たちの主な貢献は、任意のエージェントのハード・ツー・ラーン・インスタンスの構築に基づく、この設定に対する最初の後悔の低いバウンダリである。 我々の後悔の少ない$\Omega(\sqrt{K})$、$K$のエピソードは、Dec-MASSPの固有の学習困難を浮き彫りにしている。 これらの知見は、分散制御の学習複雑性を明らかにし、マルチエージェントシステムにおける効率的な学習アルゴリズムの設計をさらに導くことができる。

関連論文リスト

• Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach [0.0]
  本稿では、分散実行のためのシーケンシャルモブ集中型トレーニングという、新しい、よりスケーラブルな代替手段を提案する。 さらに、ベルマンの最適性原理の適用性を高め、3つの新しい性質を提起する。 2-および多-エージェント領域の実験は、我々の新しいアプローチの優位性を確認した。
  論文  参考訳（メタデータ） (2024-08-23T15:01:37Z)
• MADiff: Offline Multi-agent Learning with Diffusion Models [79.18130544233794]
  MADiffは拡散型マルチエージェント学習フレームワークである。 分散ポリシと集中型コントローラの両方として機能する。 実験の結果,MADiffは様々なマルチエージェント学習タスクにおいて,ベースラインアルゴリズムよりも優れていた。
  論文  参考訳（メタデータ） (2023-05-27T02:14:09Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。 我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。 コア最適化問題の実用的なパラメトリゼーションを提供する。
  論文  参考訳（メタデータ） (2021-07-08T18:01:02Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。 通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。 分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。 分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
  論文  参考訳（メタデータ） (2020-10-02T10:41:59Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。 本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。 当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
  論文  参考訳（メタデータ） (2020-04-17T14:56:29Z)
• Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems [3.9599054392856488]
  マルチエージェント強化学習(MARL)における二次解析の課題 補助単エージェントLQ問題の構成に基づくMARLアルゴリズムを提案する。 我々のアルゴリズムは $tildeO(sqrtT)$ regret bound を提供する。
  論文  参考訳（メタデータ） (2020-01-27T23:37:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。