論文の概要: No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium

• arxiv url: http://arxiv.org/abs/2004.00603v5
• Date: Fri, 2 Sep 2022 16:09:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-17 18:20:24.747452
• Title: No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
• Title（参考訳）: 集中型相関平衡の非回帰学習ダイナミクス
• Authors: Andrea Celli, Alberto Marchesi, Gabriele Farina, Nicola Gatti
• Abstract要約: 正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
• 参考スコア（独自算出の注目度）: 76.78447814623665
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The existence of simple, uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form (that is, tree-form) games generalize normal-form games by modeling both sequential and simultaneous moves, as well as private information. Because of the sequential nature and presence of partial information in the game, extensive-form correlation has significantly different properties than the normal-form counterpart, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to normal-form correlated equilibrium. However, it was currently unknown whether EFCE emerges as the result of uncoupled agent dynamics. In this paper, we give the first uncoupled no-regret dynamics that converge to the set of EFCEs in $n$-player general-sum extensive-form games with perfect recall. First, we introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. When each player has low trigger regret, the empirical frequency of play is close to an EFCE. Then, we give an efficient no-trigger-regret algorithm. Our algorithm decomposes trigger regret into local subproblems at each decision point for the player, and constructs a global strategy of the player from the local solutions at each decision point.
• Abstract（参考訳）: 正規形ゲームにおける相関平衡に収束する単純で非結合な非回帰力学の存在は、マルチエージェント系の理論における有名な結果である。 特に20年以上にわたって、全てのプレイヤーが通常のゲームで内的後悔を最小化しようとすると、経験的なプレイ頻度が正規形相関均衡に収束することが知られている。 拡張形式のゲーム(すなわち木型ゲーム)は、シーケンシャルと同時の動作とプライベート情報の両方をモデル化することで、正規形式のゲームを一般化する。 ゲーム内での逐次的な性質と部分的な情報の存在のため、広角形相関は通常の形式とは大きく異なる性質を持ち、その多くはまだオープンな研究方向である。 正規形相関平衡とは自然に拡張型相関平衡 (efce) が提唱されている。 しかし、EFCEが未結合のエージェントダイナミクスの結果現れるかどうかは現在不明である。 本稿では,$n$$-player general-sum extensive-form game with perfect recallにおいて,EFCEの集合に収束する最初の未結合な非線形ダイナミクスについて述べる。 まず、広義のゲームにおいてトリガー後悔の概念を導入し、通常のゲームにおける内部後悔の概念を拡張した。 各プレイヤーのトリガー残差が低い場合、経験的なプレイ頻度はEFCEに近い。 次に,効率的なノトリガー・レグレットアルゴリズムを提案する。 提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,各決定点における局所的な解からプレイヤーのグローバルな戦略を構築する。

関連論文リスト

• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [99.00383370823839]
  様々な種類の最適相関平衡を求める問題について検討する。 本稿では,特定の解の概念に依存する相関戦略の空間の表現である相関DAGを紹介する。 また、カードゲームブリッジのエンドゲームフェーズをエミュレートするトリックテイクゲームと、ライドシェアリングゲームという2つの新しいベンチマークゲームも導入した。
  論文  参考訳（メタデータ） (2022-03-14T15:21:18Z)
• Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [65.64512759706271]
  正常形式ゲームにおける相関平衡と収束する単純非結合非残余力学の存在について研究する。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 我々は,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-04T02:26:26Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)
• Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond [107.14897720357631]
  本研究では,公的なチャンス移動を伴う2人プレイヤゲームにおいて,最適相関平衡が時間内に計算可能であることを示す。 この結果、10年以上にわたる広範な形式の相関を取り巻く最大の正の複雑性結果が得られた。
  論文  参考訳（メタデータ） (2020-09-09T14:51:58Z)

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

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