論文の概要: Efficient $\Phi$-Regret Minimization in Extensive-Form Games via Online Mirror Descent

• arxiv url: http://arxiv.org/abs/2205.15294v1
• Date: Mon, 30 May 2022 17:58:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-31 15:21:07.609978
• Title: Efficient $\Phi$-Regret Minimization in Extensive-Form Games via Online Mirror Descent
• Title（参考訳）: オンラインミラーディフレッシュによる多角形ゲームにおける効率の良い$\Phi$-Regret最小化
• Authors: Yu Bai, Chi Jin, Song Mei, Ziang Song, Tiancheng Yu
• Abstract要約: $Phi$-Hedgeは、正規形式ゲーム(NFG)のための大規模な平衡を学習できる汎用アルゴリズムである。 EFGにおけるNash Equilibria(ゼロサム設定)、Normal-Form Coarse Correlated Equilibria(NFCCE)、Extensive-Form Correlated Equilibria(EFCE)の学習に$Phi$-Hedgeが直接利用できることを示す。 それらの設定において、emph$Phi$-Hedgeアルゴリズムは標準ミラーDescent(OMD)アルゴリズムと等価であることを示す。
• 参考スコア（独自算出の注目度）: 49.93548413166884
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A conceptually appealing approach for learning Extensive-Form Games (EFGs) is to convert them to Normal-Form Games (NFGs). This approach enables us to directly translate state-of-the-art techniques and analyses in NFGs to learning EFGs, but typically suffers from computational intractability due to the exponential blow-up of the game size introduced by the conversion. In this paper, we address this problem in natural and important setups for the \emph{$\Phi$-Hedge} algorithm -- A generic algorithm capable of learning a large class of equilibria for NFGs. We show that $\Phi$-Hedge can be directly used to learn Nash Equilibria (zero-sum settings), Normal-Form Coarse Correlated Equilibria (NFCCE), and Extensive-Form Correlated Equilibria (EFCE) in EFGs. We prove that, in those settings, the \emph{$\Phi$-Hedge} algorithms are equivalent to standard Online Mirror Descent (OMD) algorithms for EFGs with suitable dilated regularizers, and run in polynomial time. This new connection further allows us to design and analyze a new class of OMD algorithms based on modifying its log-partition function. In particular, we design an improved algorithm with balancing techniques that achieves a sharp $\widetilde{\mathcal{O}}(\sqrt{XAT})$ EFCE-regret under bandit-feedback in an EFG with $X$ information sets, $A$ actions, and $T$ episodes. To our best knowledge, this is the first such rate and matches the information-theoretic lower bound.
• Abstract（参考訳）: EFG(Learning Extensive-Form Games)は、NFG(Normal-Form Games)に変換する手法である。 このアプローチにより,NFGの最先端技術や解析をEFGの学習に直接変換することが可能になるが,この変換によって導入されたゲームサイズが指数関数的に膨らみ,計算の難しさに悩まされることが多い。 本稿では,この問題を,NFGの大規模な平衡を学習可能な汎用アルゴリズムであるemph{$\Phi$-Hedge}アルゴリズムの,自然かつ重要な設定で解決する。 EFGにおけるNash Equilibria(ゼロサム設定)、Normal-Form Coarse Correlated Equilibria(NFCCE)、Extensive-Form Correlated Equilibria(EFCE)の学習に$\Phi$-Hedgeが直接利用できることを示す。 これらの設定では、emph{$\Phi$-Hedge}アルゴリズムは、適切な拡張正則化器を持つEFGの標準オンラインミラードライザー(OMD)アルゴリズムと等価であり、多項式時間で実行されることを証明している。 この新たな接続により、ログ分割関数の変更に基づいて新しいクラスのOMDアルゴリズムを設計および解析することが可能になる。 特に、$x$情報セット、$a$アクション、$t$エピソードを持つefgにおいて、bandit-feedbackの下で鋭い$\widetilde{\mathcal{o}}(\sqrt{xat})$efce-regretを達成するためのバランス技術を備えた改良されたアルゴリズムを設計する。 われわれの知る限りでは、これが初めてであり、情報理論の下限と一致する。

関連論文リスト

• Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
  グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。 我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。 これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
  論文  参考訳（メタデータ） (2023-10-26T16:19:24Z)
• Learning Regularized Monotone Graphon Mean-Field Games [155.38727464526923]
  正規化グラフィオン平均フィールドゲーム(GMFG)の基本問題について検討する。 我々は、$lambda$-regularized GMFG の Nash Equilibrium (NE) の存在を確立する。 弱い単調なGMFGでNEを学習するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-12T07:34:13Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。 遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
  論文  参考訳（メタデータ） (2022-10-30T22:58:22Z)
• The Power of Regularization in Solving Extensive-Form Games [22.557806157585834]
  本稿では,ゲームにおける支払関数の正規化に基づく新しいアルゴリズムを提案する。 特に、拡張された楽観的ミラー降下(DOMD)が高速な$tilde O(T)$ last-iterate convergenceを達成できることを示す。 また、Reg-CFRは、楽観的ミラー降下アルゴリズムの変形を最小化して、$O(T1/4)$ベストイテレート、$O(T3/4)$平均イテレート収束率を達成できることを示した。
  論文  参考訳（メタデータ） (2022-06-19T22:10:38Z)
• Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Games [22.94768429216664]
  Imperfect-Information Extensive-Form Games (IIEFG) は、不完全情報とシーケンシャルプレイを含む現実世界のゲームにおいて一般的なモデルである。 Extensive-Form Correlated Equilibrium (EFCE) はマルチプレイヤー汎用IIEFGの自然解の概念として提案されている。 本稿では,バンドフィードバックからEFCEを学習するための最初のサンプル効率アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-15T08:55:28Z)
• Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games [76.21916750766277]
  カーネルトリックを用いて,最適乗算重み更新(OMWU)アルゴリズムをゲームツリーサイズ毎のリニア時間でEFGの正規形等価値にシミュレート可能であることを示す。 特に、KoMWUは、最終点収束を同時に保証する最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-01T06:28: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)
• An Operator Splitting View of Federated Learning [23.99238431431463]
  過去数年間、学習(texttFL$)コミュニティは、新しい$texttFL$アルゴリズムの急増を目撃してきた。 我々は、異なるアルゴリズムを簡単に比較し、以前の収束結果と比較し、新しいアルゴリズムの変種を明らかにする。 統一アルゴリズムは、オーバーヘッドを伴わずに$texttFL$アルゴリズムを加速する方法も導き出す。
  論文  参考訳（メタデータ） (2021-08-12T21:22:06Z)

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

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