論文の概要: Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games

• arxiv url: http://arxiv.org/abs/2111.06008v1
• Date: Thu, 11 Nov 2021 01:19:53 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-12 14:59:36.105990
• Title: Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games
• Title（参考訳）: マルチプレイヤー・ジェネラルサムゲームにおける相関平衡の近似的no-regret学習
• Authors: Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, Tuomas Sandholm
• Abstract要約: マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
• 参考スコア（独自算出の注目度）: 104.74734408204749
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Daskalakis, Fishelson, and Golowich (DFG) (NeurIPS`21) showed that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(\textrm{polylog}(T))$ after $T$ repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium at the rate of $\tilde{O}(T^{-1})$. This substantially improves over the prior best rate of convergence for correlated equilibria of $O(T^{-3/4})$ due to Chen and Peng (NeurIPS`20), and it is optimal -- within the no-regret framework -- up to polylogarithmic factors in $T$. To obtain these results, we develop new techniques for establishing higher-order smoothness for learning dynamics involving fixed point operations. Specifically, we establish that the no-internal-regret learning dynamics of Stoltz and Lugosi (Mach Learn`05) are equivalently simulated by no-external-regret dynamics on a combinatorial space. This allows us to trade the computation of the stationary distribution on a polynomial-sized Markov chain for a (much more well-behaved) linear transformation on an exponential-sized set, enabling us to leverage similar techniques as DGF to near-optimally bound the internal regret. Moreover, we establish an $O(\textrm{polylog}(T))$ no-swap-regret bound for the classic algorithm of Blum and Mansour (BM) (JMLR`07). We do so by introducing a technique based on the Cauchy Integral Formula that circumvents the more limited combinatorial arguments of DFG. In addition to shedding clarity on the near-optimal regret guarantees of BM, our arguments provide insights into the various ways in which the techniques by DFG can be extended and leveraged in the analysis of more involved learning algorithms.
• Abstract（参考訳）: 最近、Daskalakis, Fishelson, and Golowich (DFG) (NeurIPS`21) は、マルチプレイヤーの汎用正規形式ゲームにおける全てのエージェントがOptimistic Multiplicative Weights Update (OMWU) を使用している場合、全てのプレイヤーの外部後悔は、ゲームの繰り返しの後で$O(\textrm{polylog}(T)$であることを示した。 その結果を外部の後悔から内部後悔に拡張し,後悔を交換することで,約相関平衡に収束する非結合学習ダイナミクスを,$\tilde{o}(t^{-1})$で確立する。 これは、Chen and Peng (NeurIPS`20) による$O(T^{-3/4})$の相関平衡に対する事前の収束率よりも大幅に改善され、非回帰フレームワーク内では、$T$のポリ対数因子まで最適である。 これらの結果を得るために,不動点演算を含む学習ダイナミクスの高次滑らか性を確立するための新しい手法を開発した。 具体的には、stltz と lugosi (mach learn`05) の非内在回帰学習ダイナミクスは、組合せ空間上の非外在回帰ダイナミクスによって等価にシミュレートされる。 これにより、多項式サイズのマルコフ連鎖上の定常分布の計算を指数関数型集合上の(かなりよく考えられた)線型変換と交換することができ、dgfのような類似の手法を内部後悔をほぼ最適に束ねることができる。 さらに、Blum and Mansour (BM) (JMLR`07) の古典的アルゴリズムに対して、$O(\textrm{polylog}(T))$ no-swap-regret を定めている。 我々は,dfg のより限定的な組合せ論を回避し,コーシー積分式に基づく手法を導入する。 本論は,BMのほぼ最適後悔の保証に対する明瞭さの隠蔽に加えて,DFGによる手法を拡張し,より関連する学習アルゴリズムの分析に活用する様々な方法についての知見を提供する。

関連論文リスト

• $\widetilde{O}(T^{-1})$ Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games [8.215874655947335]
  楽観的フォロー・ザ・レギュラライズド・リーダー・アルゴリズムは,フル情報汎用マルコフゲームにおいて,$widetildeO(T-1)$-approximate iterationsを$T$内で見つけることができることを示す。
  論文  参考訳（メタデータ） (2024-02-02T20:40:27Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
  我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。 これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
  論文  参考訳（メタデータ） (2022-08-20T20:48:58Z)
• 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)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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