論文の概要: Swap Regret and Correlated Equilibria Beyond Normal-Form Games

• arxiv url: http://arxiv.org/abs/2502.20229v1
• Date: Thu, 27 Feb 2025 16:16:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-28 14:55:53.193733
• Title: Swap Regret and Correlated Equilibria Beyond Normal-Form Games
• Title（参考訳）: スワップレグレットと関連均衡 : ノーマルフォームゲームを超えて
• Authors: Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan,
• Abstract要約: 「我々は、プロファイルスワップ後悔と呼ぶポリトープゲームのスワップ後悔の新しい変種を提示する。」 プロファイルスワップ後悔は、プレイの書き起こしが与えられた場合、NPハードであることが示されるが、少なくとも$O(sqrtT)$プロファイルスワップ後悔を保証する効率的な学習アルゴリズムを設計することは可能である。
• 参考スコア（独自算出の注目度）: 62.01542145970044
• License:
• Abstract: Swap regret is a notion that has proven itself to be central to the study of general-sum normal-form games, with swap-regret minimization leading to convergence to the set of correlated equilibria and guaranteeing non-manipulability against a self-interested opponent. However, the situation for more general classes of games -- such as Bayesian games and extensive-form games -- is less clear-cut, with multiple candidate definitions for swap-regret but no known efficiently minimizable variant of swap regret that implies analogous non-manipulability guarantees. In this paper, we present a new variant of swap regret for polytope games that we call ``profile swap regret'', with the property that obtaining sublinear profile swap regret is both necessary and sufficient for any learning algorithm to be non-manipulable by an opponent (resolving an open problem of Mansour et al., 2022). Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most $O(\sqrt{T})$ profile swap regret. Finally, we explore the correlated equilibrium notion induced by low-profile-swap-regret play, and demonstrate a gap between the set of outcomes that can be implemented by this learning process and the set of outcomes that can be implemented by a third-party mediator (in contrast to the situation in normal-form games).
• Abstract（参考訳）: スワップ後悔(英: Swap regret)は、一般サム正規形式ゲームの研究の中心であることを証明した概念であり、スワップ・レグレットの最小化は、均衡均衡の集合に収束し、自己興味のある相手に対して非操作性を保証する。 しかし、ベイズゲームやワイドフォームゲームのようなより一般的なゲームの状況は明確ではなく、スワップ・レグレットの複数の候補定義があるが、類似の非マニピュラ性保証を意味するスワップ・リフレクションの効果的に最小限の変種は知られていない。 本稿では,「シューティングスワップ・リフレッシュ」と呼ぶポリトープゲームに対するスワップ・リフレストの新しいバリエーションを提案する。また,サブ線形プロファイル・スワップ・リフレストを得るには,学習アルゴリズムが相手に操作不能であるためには,必要かつ十分である(Mansour et al , 2022)。 プロファイルスワップ後悔は、プレイの書き起こしが与えられた場合、NPハードであることが示されるが、少なくとも$O(\sqrt{T})$プロファイルスワップ後悔を保証する効率的な学習アルゴリズムを設計することは可能である。 そして,この学習プロセスによって実現可能な結果の集合と,サードパーティの仲介者によって実現可能な結果の集合とのギャップ(通常型ゲームとは対照的に)を実証する。

関連論文リスト

• From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces [26.81775688975904]
  我々は、ある仮説クラスに対して外部回帰アルゴリズムが存在しない場合、同じクラスに対して非スワップ回帰アルゴリズムが存在することも示している。 我々の減少は、あるゲームで非回帰学習が可能であるならば、このゲームは近似された平衡を持つ必要があることを意味する。
  論文  参考訳（メタデータ） (2023-10-30T17:50:29Z)
• Is Learning in Games Good for the Learners? [14.781100349601587]
  2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
  論文  参考訳（メタデータ） (2023-05-31T02:10:27Z)
• Learning not to Regret [19.945846614714167]
  特定の分布に合わせて最小限の後悔をメタ学習できる新しい「後悔しない学習」フレームワークを提案する。 我々の重要な貢献であるNeural Predictive Regret Matchingは、選択されたゲームの分布に対して急速に収束するようにメタ学習されています。 実験の結果,メタ学習アルゴリズムは非メタ学習アルゴリズムよりも優れ,10倍以上の改善が得られた。
  論文  参考訳（メタデータ） (2023-03-02T08:56:12Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation [76.61911795703062]
  学習者が他の最適化エージェントと連続したゲームに関わった場合の後悔の問題を考察する。 この場合、全てのプレイヤーが非相対的アルゴリズムに従えば、完全に敵対する環境に対してかなり低い後悔を達成することができる。 本稿では,最悪とベストケースの後悔の保証を円滑に補間する完全適応手法を提案する。
  論文  参考訳（メタデータ） (2022-06-13T10:13:51Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)
• Evolutionary Dynamics and $\Phi$-Regret Minimization in Games [38.00008966802513]
  Regretはオンライン学習の基礎概念として確立されており、ゲームにおける学習力学の分析にも重要な応用がある。 本稿では,全エンフミックス戦略空間の分割に対する偏差の観点から,後悔に対する理解を再考する。 ここでは、複製子力学(RD)のよく研究された進化的学習アルゴリズムが、一般的な2倍の2ドルゲームにおいて、最強の$Phi$-regretの形式をシームレスに最小化することを証明している。
  論文  参考訳（メタデータ） (2021-06-28T12:48:15Z)

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

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