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

• arxiv url: http://arxiv.org/abs/2104.01520v1
• Date: Sun, 4 Apr 2021 02:26:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-07 10:08:00.132161
• Title: Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
• Title（参考訳）: 拡張型相関平衡のための単純非結合非回帰学習ダイナミクス
• Authors: Gabriele Farina, Andrea Celli, Alberto Marchesi, Nicola Gatti
• Abstract要約: 正常形式ゲームにおける相関平衡と収束する単純非結合非残余力学の存在について研究する。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 我々は,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 65.64512759706271
• License: http://creativecommons.org/licenses/by/4.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 possesses 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, though it was currently unknown whether EFCE emerges as the result of uncoupled agent dynamics. In this article, we give the first uncoupled no-regret dynamics that converge with high probability 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-regret algorithm which guarantees with high probability that trigger regrets grow sublinearly in the number of iterations.
• Abstract（参考訳）: 正規形ゲームにおける相関平衡に収束する単純で非結合な非回帰力学の存在は、マルチエージェント系の理論における有名な結果である。 特に20年以上にわたって、全てのプレイヤーが通常のゲームで内的後悔を最小化しようとすると、経験的なプレイ頻度が正規形相関均衡に収束することが知られている。 拡張形式のゲーム(すなわち木型ゲーム)は、シーケンシャルと同時の動作とプライベート情報の両方をモデル化することで、正規形式のゲームを一般化する。 ゲームのシーケンシャルな性質と部分的な情報の存在により、広範囲な形式的相関は通常の形式と大きく異なる性質を持ち、その多くは依然として研究の方向性である。 拡張型相関平衡(EFCE)は、通常型相関平衡に対抗して自然な拡張型として提案されているが、未結合のエージェントダイナミクスの結果、EFCEが出現するかどうかは現在不明である。 本稿では, n-player general-sum extensive-form game with perfect recall において, EFCE の集合に高い確率で収束する最初の非共役な非共役ダイナミクスについて述べる。 まず、広義のゲームにおいてトリガー後悔の概念を導入し、通常のゲームにおける内部後悔の概念を拡張した。 各プレイヤーのトリガー残差が低い場合、経験的なプレイ頻度はEFCEに近い。 次に,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。

関連論文リスト

• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。 ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。 我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
  論文  参考訳（メタデータ） (2022-10-25T19:02:03Z)
• Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
  我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。 これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
  論文  参考訳（メタデータ） (2022-08-20T20:48:58Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。 これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2022-03-14T15:21:18Z)
• 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)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
  論文  参考訳（メタデータ） (2020-04-01T17:39:00Z)

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

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