論文の概要: Multi-Agent congestion cost minimization with linear function approximation

• arxiv url: http://arxiv.org/abs/2301.10993v1
• Date: Thu, 26 Jan 2023 08:45:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-27 14:00:36.509390
• Title: Multi-Agent congestion cost minimization with linear function approximation
• Title（参考訳）: 線形関数近似を用いたマルチエージェント混雑コスト最小化
• Authors: Prashant Trivedi, Nandyala Hemachandra
• Abstract要約: この作業では、ソースノードからゴールノードにネットワークをトラバースする複数のエージェントについて検討する。 エージェントの目的は、最小限の全体的なコストで、分散的な方法でゴールノードへのパスを見つけることである。 本稿では,新しいマルチエージェント・コンジェクション・コスト最小化アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work considers multiple agents traversing a network from a source node to the goal node. The cost to an agent for traveling a link has a private as well as a congestion component. The agent's objective is to find a path to the goal node with minimum overall cost in a decentralized way. We model this as a fully decentralized multi-agent reinforcement learning problem and propose a novel multi-agent congestion cost minimization (MACCM) algorithm. Our MACCM algorithm uses linear function approximations of transition probabilities and the global cost function. In the absence of a central controller and to preserve privacy, agents communicate the cost function parameters to their neighbors via a time-varying communication network. Moreover, each agent maintains its estimate of the global state-action value, which is updated via a multi-agent extended value iteration (MAEVI) sub-routine. We show that our MACCM algorithm achieves a sub-linear regret. The proof requires the convergence of cost function parameters, the MAEVI algorithm, and analysis of the regret bounds induced by the MAEVI triggering condition for each agent. We implement our algorithm on a two node network with multiple links to validate it. We first identify the optimal policy, the optimal number of agents going to the goal node in each period. We observe that the average regret is close to zero for 2 and 3 agents. The optimal policy captures the trade-off between the minimum cost of staying at a node and the congestion cost of going to the goal node. Our work is a generalization of learning the stochastic shortest path problem.
• Abstract（参考訳）: この作業では、ソースノードからゴールノードにネットワークをトラバースする複数のエージェントについて検討する。 リンクを移動するためのエージェントに対するコストは、混雑成分と同様にプライベートである。 エージェントの目的は、分散的に最小の全体的なコストでゴールノードへのパスを見つけることである。 我々は,これを完全分散化マルチエージェント強化学習問題としてモデル化し,新しいマルチエージェント混雑コスト最小化アルゴリズムを提案する。 我々のMACCMアルゴリズムは、遷移確率とグローバルコスト関数の線形関数近似を用いる。 中央のコントローラが無く、プライバシを保存するために、エージェントは時間変化のある通信ネットワークを介して、コスト関数パラメータを隣人に通信する。 さらに、各エージェントは、マルチエージェント拡張値イテレーション(maevi)サブルーチンを介して更新されるグローバル状態アクション値の推定を維持する。 我々は,MACCMアルゴリズムがサブ線形後悔を実現することを示す。 この証明には、コスト関数パラメータの収束、MAEVIアルゴリズム、および各エージェントに対するMAEVIトリガ条件によって誘導される後悔境界の解析が必要である。 提案アルゴリズムは,複数のリンクを持つ2ノードネットワーク上に実装して検証する。 まず,各期間に目標ノードに行くエージェントの最適数,最適ポリシーを特定する。 平均的後悔は 2 と 3 のエージェントに対して 0 に近い。 最適ポリシーは、ノードに留まる最小コストと、ゴールノードに行く際の混雑コストとの間のトレードオフをキャプチャする。 我々の仕事は確率的最短経路問題を学ぶ一般化である。

関連論文リスト

• Communication Efficient Decentralization for Smoothed Online Convex Optimization [9.449153668916098]
  マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。 各ラウンドにおいて、各エージェント$i$は、オンラインの方法で、強い凸打撃コスト関数$fi_t$を受け取る。 通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
  論文  参考訳（メタデータ） (2024-11-13T05:59:04Z)
• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。 我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。 我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
  論文  参考訳（メタデータ） (2024-10-22T19:34:53Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
  本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。 疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。 後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
  論文  参考訳（メタデータ） (2023-05-30T16:05:44Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。 我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
  論文  参考訳（メタデータ） (2022-06-13T09:17:40Z)
• Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function [7.768673476492471]
  本稿では、スティーフェル多様体上の分散最適化問題に焦点をあてる。 エージェントは、この問題を解決するための共同作業において、隣人としか通信できない。 既存の方法では、収束を保証するために複数の通信ラウンドが必要である。 本稿では,DESTINYと呼ばれる分散化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-30T07:19:59Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• Multi-agent Policy Optimization with Approximatively Synchronous Advantage Estimation [55.96893934962757]
  マルチエージェントシステムでは、異なるエージェントの警察を共同で評価する必要がある。 現在の方法では、バリュー関数やアドバンテージ関数は非同期に評価される対実関節アクションを使用する。 本研究では,近似的に同期する利点推定を提案する。
  論文  参考訳（メタデータ） (2020-12-07T07:29:19Z)
• Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
  本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。 ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。 私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
  論文  参考訳（メタデータ） (2020-12-01T07:33:00Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。 通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。 分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。 分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
  論文  参考訳（メタデータ） (2020-10-02T10:41:59Z)

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

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