論文の概要: Evolutionary Dynamics and $\Phi$-Regret Minimization in Games

• arxiv url: http://arxiv.org/abs/2106.14668v1
• Date: Mon, 28 Jun 2021 12:48:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-29 17:39:34.938022
• Title: Evolutionary Dynamics and $\Phi$-Regret Minimization in Games
• Title（参考訳）: ゲームにおける進化ダイナミクスと$\phi$-regret最小化
• Authors: Georgios Piliouras, Mark Rowland, Shayegan Omidshafiei, Romuald Elie, Daniel Hennes, Jerome Connor, Karl Tuyls
• Abstract要約: Regretはオンライン学習の基礎概念として確立されており、ゲームにおける学習力学の分析にも重要な応用がある。 本稿では,全エンフミックス戦略空間の分割に対する偏差の観点から,後悔に対する理解を再考する。 ここでは、複製子力学(RD)のよく研究された進化的学習アルゴリズムが、一般的な2倍の2ドルゲームにおいて、最強の$Phi$-regretの形式をシームレスに最小化することを証明している。
• 参考スコア（独自算出の注目度）: 38.00008966802513
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Regret has been established as a foundational concept in online learning, and likewise has important applications in the analysis of learning dynamics in games. Regret quantifies the difference between a learner's performance against a baseline in hindsight. It is well-known that regret-minimizing algorithms converge to certain classes of equilibria in games; however, traditional forms of regret used in game theory predominantly consider baselines that permit deviations to deterministic actions or strategies. In this paper, we revisit our understanding of regret from the perspective of deviations over partitions of the full \emph{mixed} strategy space (i.e., probability distributions over pure strategies), under the lens of the previously-established $\Phi$-regret framework, which provides a continuum of stronger regret measures. Importantly, $\Phi$-regret enables learning agents to consider deviations from and to mixed strategies, generalizing several existing notions of regret such as external, internal, and swap regret, and thus broadening the insights gained from regret-based analysis of learning algorithms. We prove here that the well-studied evolutionary learning algorithm of replicator dynamics (RD) seamlessly minimizes the strongest possible form of $\Phi$-regret in generic $2 \times 2$ games, without any modification of the underlying algorithm itself. We subsequently conduct experiments validating our theoretical results in a suite of 144 $2 \times 2$ games wherein RD exhibits a diverse set of behaviors. We conclude by providing empirical evidence of $\Phi$-regret minimization by RD in some larger games, hinting at further opportunity for $\Phi$-regret based study of such algorithms from both a theoretical and empirical perspective.
• Abstract（参考訳）: 後悔はオンライン学習の基礎概念として確立されており、ゲームにおける学習ダイナミクスの分析にも重要な応用がある。 Regretは、学習者のパフォーマンスと後方視のベースラインとの差を定量化する。 後悔最小化アルゴリズムがゲームにおけるある種の平衡クラスに収束することはよく知られているが、ゲーム理論で使われる従来の後悔の形式は、決定論的行動や戦略に偏りを許容するベースラインを主に考慮している。 本稿では,従来確立されていた$\phi$-regret の枠組みに基づいて,全 \emph{mixed} 戦略空間(すなわち,純粋戦略上の確率分布)の分割上の偏差の観点から,後悔に対する理解を再検討する。 重要なのは、$\Phi$-regretを使用することで、学習エージェントは、外的、内的、スワップ後悔といった既存の後悔の概念を一般化し、学習アルゴリズムの後悔に基づく分析から得られる洞察を拡大することができる。 ここでは、複製子力学(RD)のよく研究された進化的学習アルゴリズムが、基礎となるアルゴリズム自体を変更することなく、一般的な2ドルのゲームにおいて、$\Phi$-regretの可能な最強の形式をシームレスに最小化することを示す。 その後、RDが多種多様な振る舞いを示す144ドルの2ドルゲームで理論結果を検証する実験を行った。 結論として,いくつかのゲームにおいてrdによる$\phi$-regret最小化の実証的証拠を提供し,理論的および経験的観点からこれらのアルゴリズムの$\phi$-regretに基づく研究のさらなる機会を示唆した。

関連論文リスト

• Achieving Better Regret against Strategic Adversaries [15.51709428653595]
  本研究では,学習者が相手の行動について余分な知識を持つオンライン学習問題について検討する。 我々は,正規化リーダ(AFTRL)とProd-Best Response(Prod-BR)の2つの新しいオンライン学習アルゴリズムを提案する。 AFTRLは、外部の後悔に対して$O(1)$、または$O(1)$、遠回りの後悔に対して$O(1)$を達成する。
  論文  参考訳（メタデータ） (2023-02-13T19:34:36Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• 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)
• Reparameterized Variational Divergence Minimization for Stable Imitation [57.06909373038396]
  確率的発散の選択における変動が、より高性能なILOアルゴリズムをもたらす可能性について検討する。 本稿では,提案する$f$-divergence最小化フレームワークの課題を軽減するために,逆模倣学習のための再パラメータ化手法を提案する。 経験的に、我々の設計選択は、ベースラインアプローチより優れ、低次元連続制御タスクにおける専門家のパフォーマンスとより密に適合するIOOアルゴリズムを許容することを示した。
  論文  参考訳（メタデータ） (2020-06-18T19:04:09Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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