論文の概要: Near-Optimal No-Regret Learning in General Games
- arxiv url: http://arxiv.org/abs/2108.06924v1
- Date: Mon, 16 Aug 2021 06:53:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-17 14:53:34.027956
- Title: Near-Optimal No-Regret Learning in General Games
- Title（参考訳）: 一般ゲームにおける準最適no-regret学習
- Authors: Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich
- Abstract要約: マルチプレイヤー汎用ゲームにおいて,Optimistic Hedge が $rm poly(log T)$ regret を達成することを示す。
我々の境界の系は、最適化的ヘッジが一般ゲームにおいて$tildeOleft(frac 1Tright)$の速度で粗相関平衡に収束するということである。
- 参考スコア（独自算出の注目度）: 31.293412884145066
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that Optimistic Hedge -- a common variant of
multiplicative-weights-updates with recency bias -- attains ${\rm poly}(\log
T)$ regret in multi-player general-sum games. In particular, when every player
of the game uses Optimistic Hedge to iteratively update her strategy in
response to the history of play so far, then after $T$ rounds of interaction,
each player experiences total regret that is ${\rm poly}(\log T)$. Our bound
improves, exponentially, the $O({T}^{1/2})$ regret attainable by standard
no-regret learners in games, the $O(T^{1/4})$ regret attainable by no-regret
learners with recency bias (Syrgkanis et al., 2015), and the ${O}(T^{1/6})$
bound that was recently shown for Optimistic Hedge in the special case of
two-player games (Chen & Pen, 2020). A corollary of our bound is that
Optimistic Hedge converges to coarse correlated equilibrium in general games at
a rate of $\tilde{O}\left(\frac 1T\right)$.
- Abstract（参考訳）: 回帰バイアスを伴う乗法重み更新の共通変種であるOptimistic Hedgeは、マルチプレイヤーの一般サムゲームにおいて、${\rm poly}(\log T)$ regretとなることを示す。
特に、ゲーム中のすべてのプレイヤーが楽観的なヘッジを使用して、これまでのプレイの歴史に応じて戦略を反復的に更新し、t$のインタラクションの後、各プレイヤーは${\rm poly}(\log t)$という完全な後悔を経験する。
我々の限界は指数関数的に改善され、ゲームにおける標準の非回帰学習者によって達成可能な$O({T}^{1/2})$後悔、非回帰学習者によって達成可能な$O(T^{1/4})$後悔(Syrgkanis et al., 2015)、そして最近2プレイヤーゲーム(Chen & Pen, 2020)においてOptimistic Hedge(英語版)のために最近示された${O}(T^{1/6})$後悔が達成される。
我々の境界の系は、最適化的ヘッジが一般ゲームにおける粗相関平衡に$\tilde{O}\left(\frac 1T\right)$で収束するということである。
関連論文リスト
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - $\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) - Last-Iterate Convergence Properties of Regret-Matching Algorithms in
Games [72.43065138581589]
RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。
本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。
そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
論文 参考訳（メタデータ） (2023-11-01T17:34:58Z) - Is Learning in Games Good for the Learners? [14.781100349601587]
2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。
このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。
また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
論文 参考訳（メタデータ） (2023-05-31T02:10:27Z) - 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) - Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer
Games [121.50979258049135]
我々は、すべてのプレイヤーが、時空不変の学習速度で我々のダイナミクスに従うとき、時間$T$までの時空二階パス長は、$O(log T)$で有界であることを示す。
提案する学習力学は, 直観的正規化学習と, 自己一致障壁を併用した新しい学習手法である。
論文 参考訳（メタデータ） (2022-04-25T03:20:16Z) - Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。
我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。
そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
論文 参考訳（メタデータ） (2021-12-06T08:27:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。