論文の概要: Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms

• arxiv url: http://arxiv.org/abs/2111.05486v1
• Date: Wed, 10 Nov 2021 02:10:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-11 15:21:29.030455
• Title: Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms
• Title（参考訳）: 反復支配排除のためのマルチエージェント学習:形式バリアと新しいアルゴリズム
• Authors: Jibang Wu, Haifeng Xu, Fan Yao
• Abstract要約: 我々は、標準の後悔アルゴリズムが、すべての支配的な行動を排除するために、指数関数的に多くのラウンドを取ることを証明している。 そこで我々は,Exp3をDimishing Historical rewardsで調整するアルゴリズムを開発した。 すべてのエージェントがExp3-DHを実行するとき、すべての支配的なアクションは、繰り返し多くのラウンドで反復的に排除できることを示す。
• 参考スコア（独自算出の注目度）: 13.868793694964397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dominated actions are natural (and perhaps the simplest possible) multi-agent generalizations of sub-optimal actions as in standard single-agent decision making. Thus similar to standard bandit learning, a basic learning question in multi-agent systems is whether agents can learn to efficiently eliminate all dominated actions in an unknown game if they can only observe noisy bandit feedback about the payoff of their played actions. Surprisingly, despite a seemingly simple task, we show a quite negative result; that is, standard no regret algorithms -- including the entire family of Dual Averaging algorithms -- provably take exponentially many rounds to eliminate all dominated actions. Moreover, algorithms with the stronger no swap regret also suffer similar exponential inefficiency. To overcome these barriers, we develop a new algorithm that adjusts Exp3 with Diminishing Historical rewards (termed Exp3-DH); Exp3-DH gradually forgets history at carefully tailored rates. We prove that when all agents run Exp3-DH (a.k.a., self-play in multi-agent learning), all dominated actions can be iteratively eliminated within polynomially many rounds. Our experimental results further demonstrate the efficiency of Exp3-DH, and that state-of-the-art bandit algorithms, even those developed specifically for learning in games, fail to eliminate all dominated actions efficiently.
• Abstract（参考訳）: 支配的行動は、通常の単エージェント決定決定のように自然(そしておそらく最も単純な)準最適行動の多重エージェント一般化である。 したがって、標準的なバンディット学習と同様に、マルチエージェントシステムにおける基本的な学習問題は、エージェントが未知のゲームにおいて支配的なすべてのアクションを効率的に排除できるかどうかを学習できるかどうかである。 驚くべきことに、一見単純なタスクにもかかわらず、私たちは非常に否定的な結果を示します。つまり、標準の後悔のアルゴリズム -- デュアル平均化アルゴリズムのファミリー全体を含む -- は、すべての支配的なアクションを排除するために、指数的に多くのラウンドを確実に取ります。 さらに、noスワップ後悔の強いアルゴリズムも同様の指数関数的非効率に苦しむ。 これらの障壁を克服するために, Exp3 を Diminishing Historical rewards ( Exp3-DH と呼ぶ) で調整するアルゴリズムを開発した。 すべてのエージェントがExp3-DH(つまりマルチエージェント学習における自己プレイ)を実行するとき、全ての支配的なアクションは多項式的に多くのラウンドで反復的に排除できる。 実験の結果,exp3-dhの効率がさらに向上し,最先端のバンディットアルゴリズムはゲーム内で学習するために開発されたものであっても,すべての支配的動作を効果的に排除できないことが示された。

関連論文リスト

• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Learning Rationalizable Equilibria in Multiplayer Games [38.922957434291554]
  既存のアルゴリズムでは、帯域幅フィードバックの下で合理化可能な平衡を学習するために、プレイヤー数で指数関数的に多くのサンプルを必要とする。 本稿では、合理化可能な粗相関平衡(CCE)と相関平衡(CE)を学習するための効率的なアルゴリズムの第一線を開発する。 本アルゴリズムは,合理化可能性を保証するための新しい手法と,相関探索スキームと適応学習率を含む(スワップ-)レグレットを同時に備えている。
  論文  参考訳（メタデータ） (2022-10-20T16:49:00Z)
• Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
  Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。 本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。 本稿では,SCGの局所探索アルゴリズムを2つ提案する。第1に,微分可能プログラミングを用いてILDをアンロールすることで導関数を求める勾配降下アルゴリズムを提案する。 第二のアルゴリズムは、フォロワーの進化軌道を短くすることでツイストを加える。
  論文  参考訳（メタデータ） (2022-09-15T21:32:23Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)

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

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