論文の概要: Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2009.10061v1
• Date: Mon, 21 Sep 2020 17:51:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-16 04:33:11.086354
• Title: Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games
• Title（参考訳）: 総合型ゼロサムゲームにおける最適前処理協調戦略の高速アルゴリズム
• Authors: Gabriele Farina and Andrea Celli and Nicola Gatti and Tuomas Sandholm
• Abstract要約: 我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。 この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。 各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 123.76716667704625
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. Team members are not allowed to communicate during play but can coordinate before the game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. In this paper, we first provide new modeling results about computing such an optimal distribution by drawing a connection to a different literature on extensive-form correlation. Second, we provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile. We can also cap the number of such profiles we allow in the solution. This begets an anytime algorithm by increasing the cap. We find that often a handful of well-chosen such profiles suffices to reach optimal utility for the team. This enables team members to reach coordination through a relatively simple and understandable plan. Finally, inspired by this observation and leveraging theoretical concepts that we introduce, we develop an efficient column-generation algorithm for finding an optimal distribution for the team. We evaluate it on a suite of common benchmark games. It is three orders of magnitude faster than the prior state of the art on games that the latter can solve and it can also solve several games that were previously unsolvable.
• Abstract（参考訳）: 我々は,不完全な情報量ゼロサムゲームにおいて,対戦相手と対向する2人の選手の最適な戦略を見つけることに焦点を当てる。 チームメンバーはプレー中にコミュニケーションを許されず、試合前に調整することができる。 この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。 本稿では,まず,異なる文献との相関関係を広範囲な相関関係に適用し,最適分布の計算に関する新たなモデリング結果を提案する。 第2に、各プロファイルに1人だけがランダム化できるプロファイルのみを用いて、最適な分布を計算するアルゴリズムを提供する。 ソリューションでは、そのようなプロファイルの数を上限にすることもできる。 これは上限を増やすことで任意のアルゴリズムをbegetする。 このようなプロファイルは、チームにとって最適なユーティリティに到達するのに十分であることが多いのです。 これにより、チームメンバーは比較的シンプルで理解可能な計画を通じて調整できる。 最後に,この観察と理論概念の活用に着想を得て,チームの最適分布を求めるための効率的な列生成アルゴリズムを開発した。 一般的なベンチマークゲームで評価します。 後者が解くことのできるゲームの以前の状態よりも3桁早く、以前未解決だったいくつかのゲームも解くことができる。

関連論文リスト

• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach [2.908482270923597]
  本稿では,階層的な情報共有の下での最適性を維持しつつ,決定変数をアンタングルにする方法を示す。 我々のアプローチでは、広義のゲームは常に単一ステージのサブゲームに対する解決策として存在し、時間的複雑さを著しく減少させる。
  論文  参考訳（メタデータ） (2024-02-05T12:33:05Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  本稿では,サブゲームの解決ではなく,更新等価性に基づく意思決定時計画のための代替フレームワークを提案する。 ミラー降下に基づく完全協調型ゲームに対する有効音声探索アルゴリズムと、磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-04-25T20:28:55Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。 これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
  論文  参考訳（メタデータ） (2022-10-18T15:10:25Z)
• Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies [37.00818384785628]
  チームメンバーはゲームの開始前に戦略を調整できるが、ゲームのプレイ段階ではコミュニケーションが取れない。 この設定では、エージェントのポリシーが分散的に実行されるため、モデルフリーのRLメソッドはコーディネーションをキャプチャできないことが多い。 我々は,従来の最先端マルチエージェントRLアルゴリズムが適用しなかった場合に,座標平衡に収束することを示す。
  論文  参考訳（メタデータ） (2021-02-09T18:44:16Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Finding Core Members of Cooperative Games using Agent-Based Modeling [0.0]
  エージェント・ベース・モデリング(ABM)は、社会現象の洞察を得るための強力なパラダイムである。 本稿では,エージェントが連立関係を見つけられるように,AIMに組み込むアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-08-30T17:38:43Z)

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

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