論文の概要: On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring

• arxiv url: http://arxiv.org/abs/2305.00684v1
• Date: Mon, 1 May 2023 06:46:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 13:52:46.563293
• Title: On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring
• Title（参考訳）: マルチエージェント意思決定の複雑さについて:ゲームにおける学習から部分モニタリングまで
• Authors: Dylan J. Foster and Dean P. Foster and Noah Golowich and Alexander Rakhlin
• Abstract要約: マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。 本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。 マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
• 参考スコア（独自算出の注目度）: 105.13668993076801
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees, and how these considerations change as we move from few to many agents. We study this question in a general framework for interactive decision making with multiple agents, encompassing Markov games with function approximation and normal-form games with bandit feedback. We focus on equilibrium computation, in which a centralized learning algorithm aims to compute an equilibrium by controlling multiple agents that interact with an unknown environment. Our main contributions are: - We provide upper and lower bounds on the optimal sample complexity for multi-agent decision making based on a multi-agent generalization of the Decision-Estimation Coefficient, a complexity measure introduced by Foster et al. (2021) in the single-agent counterpart to our setting. Compared to the best results for the single-agent setting, our bounds have additional gaps. We show that no "reasonable" complexity measure can close these gaps, highlighting a striking separation between single and multiple agents. - We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making, but with hidden (unobserved) rewards, a framework that subsumes variants of the partial monitoring problem. As a consequence, we characterize the statistical complexity for hidden-reward interactive decision making to the best extent possible. Building on this development, we provide several new structural results, including 1) conditions under which the statistical complexity of multi-agent decision making can be reduced to that of single-agent, and 2) conditions under which the so-called curse of multiple agents can be avoided.
• Abstract（参考訳）: マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証にどんな影響を及ぼすか、そしてこれらの考慮事項がどのように変化するかを理解することである。 本稿では,マルチエージェントによる対話的意思決定のための汎用フレームワークにおいて,関数近似によるマルコフゲームとバンディットフィードバックによる正規形ゲームについて検討する。 集中型学習アルゴリズムは,未知環境と相互作用する複数のエージェントを制御することによって平衡を計算することを目的としている。 我々は,Fosterらによって導入された複雑性尺度であるDecision-Estimation Coefficient(2021)のマルチエージェント一般化に基づく,マルチエージェント意思決定のための最適なサンプル複雑性について,上位と下位のバウンダリを提供する。 単一エージェント設定の最良の結果と比較すると、境界には追加のギャップがあります。 これらのギャップを「理にかなった」複雑性尺度で閉じることはできないことを示し、単一エージェントと複数のエージェントの著しい分離を強調する。 マルチエージェント意思決定における統計的複雑性を特徴付けることは、シングルエージェント意思決定の統計的複雑性を特徴付けるのと同値であるが、部分的監視問題の変種を仮定するフレームワークである隠れた(観察されていない)報酬を特徴付ける。 その結果,隠れ回帰対話的意思決定の統計的複雑性を可能な限り最善に特徴づける。 この開発に基づいて、我々はいくつかの新しい構造結果を提供する。 1)マルチエージェント意思決定の統計的複雑さをシングルエージェントに還元できる条件、及び 2) いわゆる複数のエージェントの呪いを回避できる条件。

関連論文リスト

• Learning Emergence of Interaction Patterns across Independent RL Agents in Multi-Agent Environments [3.0284592792243794]
  ボトムアップネットワーク(BUN)は、マルチエージェントの集合を統一エンティティとして扱う。 協調ナビゲーションやトラヒックコントロールなどのタスクを含む,さまざまな協調型マルチエージェントシナリオに対する実証的な評価は,BUNが計算コストを大幅に削減したベースライン手法よりも優れていることを一貫して証明している。
  論文  参考訳（メタデータ） (2024-10-03T14:25:02Z)
• Textualized Agent-Style Reasoning for Complex Tasks by Multiple Round LLM Generation [49.27250832754313]
  我々は、llmベースの自律エージェントフレームワークであるAgentCOTを紹介する。 それぞれのステップで、AgentCOTはアクションを選択し、それを実行して、証拠を裏付ける中間結果を得る。 エージェントCOTの性能を高めるための2つの新しい戦略を導入する。
  論文  参考訳（メタデータ） (2024-09-19T02:20:06Z)
• Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
  本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。 1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
  論文  参考訳（メタデータ） (2024-02-20T08:30:46Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。 本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。 本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
  論文  参考訳（メタデータ） (2023-08-29T18:18:21Z)
• Partially Observable Multi-Agent Reinforcement Learning with Information Sharing [33.145861021414184]
  部分的に観察可能なゲーム(POSG)の一般的な枠組みにおける証明可能なマルチエージェント強化学習(RL)について検討する。 我々は,エージェント間での情報共有の可能性,経験的マルチエージェントRLにおける一般的な実践,コミュニケーションを伴うマルチエージェント制御システムの標準モデルを活用することを提唱する。
  論文  参考訳（メタデータ） (2023-08-16T23:42:03Z)
• Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit [7.708904950194129]
  動的環境におけるマルチエージェント・マルチアーム・バンディット(MAMAB)問題について検討する。 グラフはエージェント間の情報共有構造を反映し、腕の報酬分布はいくつかの未知の変化点を持つ断片的に定常である。 目的は、後悔を最小限に抑えるエージェントのための意思決定ポリシーを開発することである。
  論文  参考訳（メタデータ） (2023-06-09T16:10:26Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning [59.62721526353915]
  実世界のマルチエージェント設定は、エージェントや非エージェントエンティティのタイプや量が異なるタスクを伴うことが多い。 我々の方法は、これらの共通点を活用することを目的としており、「観察対象のランダムに選択されたサブグループのみを考えるとき、各エージェントが期待する効用は何か?」という問いを投げかける。
  論文  参考訳（メタデータ） (2020-06-07T18:28:41Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。 本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。 当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
  論文  参考訳（メタデータ） (2020-04-17T14:56:29Z)

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

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