論文の概要: Abstracting Imperfect Information Away from Two-Player Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2301.09159v2
• Date: Tue, 6 Jun 2023 01:26:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-07 21:07:15.851584
• Title: Abstracting Imperfect Information Away from Two-Player Zero-Sum Games
• Title（参考訳）: ツープレイヤーゼロサムゲームにおける不完全情報の抽象化
• Authors: Samuel Sokota, Ryan D'Orazio, Chun Kai Ling, David J. Wu, J. Zico Kolter, Noam Brown
• Abstract要約: Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。 この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。 これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
• 参考スコア（独自算出の注目度）: 85.27865680662973
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In their seminal work, Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This insight underpins sound solvers and decision-time planning algorithms for common-payoff games. Unfortunately, a naive application of the same insight to two-player zero-sum games fails because Nash equilibria of the game with public policy announcements may not correspond to Nash equilibria of the original game. As a consequence, existing sound decision-time planning algorithms require complicated additional mechanisms that have unappealing properties. The main contribution of this work is showing that certain regularized equilibria do not possess the aforementioned non-correspondence problem -- thus, computing them can be treated as perfect-information problems. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games and yields a simplified framework for decision-time planning in two-player zero-sum games, void of the unappealing properties that plague existing decision-time planning approaches.
• Abstract（参考訳）: Nayyar et al. (2013)では、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。 この洞察は、コモンペイオフゲームのためのサウンドソルバと意思決定時間計画アルゴリズムの基礎となる。 残念なことに、2人のプレイヤーのゼロサムゲームに対する同じ洞察のナッシュな応用は、ナッシュ均衡と公開ポリシーの発表が元のゲームのナッシュ均衡に合致しない可能性があるため失敗する。 その結果、既存の音響決定時間計画アルゴリズムは、未適用特性を持つ複雑な追加メカニズムを必要とする。 この研究の主な貢献は、ある正規化された平衡が上記の非対応問題を持たないことを示しており、計算は完全情報問題として扱うことができる。 これらの正規化平衡はnash平衡に任意に近付くことができるため、結果は2人のプレイヤーのゼロサムゲームを解決する新しい視点への扉を開き、2人のプレイヤーのゼロサムゲームにおける意思決定時間計画のための簡易なフレームワークを得る。

関連論文リスト

• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。 不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
  論文  参考訳（メタデータ） (2024-06-23T00:27:28Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games [64.71476526716668]
  我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。 我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。 提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
  論文  参考訳（メタデータ） (2022-10-24T09:32:40Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。 ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
  論文  参考訳（メタデータ） (2021-08-17T07:06:46Z)
• Computing Nash Equilibria in Multiplayer DAG-Structured Stochastic Games with Persistent Imperfect Information [1.7132914341329848]
  永続的不完全情報を持つマルチプレイヤー汎用ゲームにおいて,ナッシュ均衡を近似するアルゴリズムを提案する。 新たな手法を用いることで,本ゲームにおけるナッシュ均衡を近似した戦略をアルゴリズムで計算できることが証明できる。
  論文  参考訳（メタデータ） (2020-10-26T19:27:26Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。 また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
  論文  参考訳（メタデータ） (2020-02-19T21:36:58Z)
• Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry [66.82463322411614]
  本論文は, 最適遠点透過型シグナリング方式の問題点に焦点をあて, 対称性がその解法において重要な性質であることを示す。 プレイヤーが対称でアフィンコスト関数を持つとき,最適なエクアント説得スキームが計算可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-12T19:38:15Z)

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

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