論文の概要: Near-Optimal No-Regret Learning for General Convex Games

• arxiv url: http://arxiv.org/abs/2206.08742v2
• Date: Mon, 20 Jun 2022 06:58:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-22 11:27:12.527140
• Title: Near-Optimal No-Regret Learning for General Convex Games
• Title（参考訳）: 一般凸ゲームにおける近似最適no-regret学習
• Authors: Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, Tuomas Sandholm
• Abstract要約: 一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
• 参考スコア（独自算出の注目度）: 121.50979258049135
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent line of work has established uncoupled learning dynamics such that, when employed by all players in a game, each player's \emph{regret} after $T$ repetitions grows polylogarithmically in $T$, an exponential improvement over the traditional guarantees within the no-regret framework. However, so far these results have only been limited to certain classes of games with structured strategy spaces -- such as normal-form and extensive-form games. The question as to whether $O(\text{polylog} T)$ regret bounds can be obtained for general convex and compact strategy sets -- which occur in many fundamental models in economics and multiagent systems -- while retaining efficient strategy updates is an important question. In this paper, we answer this in the positive by establishing the first uncoupled learning algorithm with $O(\log T)$ per-player regret in general \emph{convex games}, that is, games with concave utility functions supported on arbitrary convex and compact strategy sets. Our learning dynamics are based on an instantiation of optimistic follow-the-regularized-leader over an appropriately \emph{lifted} space using a \emph{self-concordant regularizer} that is, peculiarly, not a barrier for the feasible region. Further, our learning dynamics are efficiently implementable given access to a proximal oracle for the convex strategy set, leading to $O(\log\log T)$ per-iteration complexity; we also give extensions when access to only a \emph{linear} optimization oracle is assumed. Finally, we adapt our dynamics to guarantee $O(\sqrt{T})$ regret in the adversarial regime. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret bounds either in terms of the dependence on the number of iterations or on the dimension of the strategy sets.
• Abstract（参考訳）: 最近の一連の研究は、ゲーム内のすべてのプレイヤーが採用する際、T$の繰り返し後の各プレイヤーの「emph{regret}」は、非regretフレームワーク内の従来の保証よりも指数関数的に向上する、非結合学習力学を確立している。 しかし、これまでのところこれらの結果は、通常の形式や広範な形式のゲームのような、構造化された戦略空間を持つある種のゲームに限られている。 O(\text{polylog} T)$ regret bounds が一般的な凸やコンパクトな戦略集合に対して得られるかどうかという問題は、効率的な戦略更新を維持しながら、経済学やマルチエージェントシステムの多くの基本モデルで発生する。 本稿では,任意の凸とコンパクトな戦略セットでサポートされた凹凸ユーティリティ関数を持つゲームにおいて,O(\log T)$ per-player regreterという最初の未結合学習アルゴリズムを確立することで,これを肯定的に解する。 我々の学習力学は、適度に \emph{lifted} 空間上の楽観的な従順化リーダのインスタンス化に基づいており、これは特に、実現可能な領域の障壁ではない。 さらに、私たちの学習ダイナミクスは、凸戦略セットの近辺のオラクルへのアクセスを前提に、効率的に実装でき、o(\log\log t)$ 1イテレーションの複雑さをもたらします。 最後に、我々は、敵対体制において$o(\sqrt{t})$の後悔を保証するためにダイナミクスを適応させる。 先行結果が適用される特別な場合においても,提案アルゴリズムは繰り返し回数や戦略集合の次元に依存するため,最先端の後悔境界よりも改善される。

関連論文リスト

• Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
  本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。 本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
  論文  参考訳（メタデータ） (2023-10-02T19:59:39Z)
• Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
  我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。 これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
  論文  参考訳（メタデータ） (2022-08-20T20:48:58Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer Games [121.50979258049135]
  我々は、すべてのプレイヤーが、時空不変の学習速度で我々のダイナミクスに従うとき、時間$T$までの時空二階パス長は、$O(log T)$で有界であることを示す。 提案する学習力学は, 直観的正規化学習と, 自己一致障壁を併用した新しい学習手法である。
  論文  参考訳（メタデータ） (2022-04-25T03:20:16Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• 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)
• Making Non-Stochastic Control (Almost) as Easy as Stochastic [27.736345095024276]
  より一般的な非確率的制御モデルにおいても、同じ後悔率が達成可能であることを示す。 学習者にとってダイナミクスが不明な場合に、最適な$widetildemathcalO(sqrtT)$ regretを得る。
  論文  参考訳（メタデータ） (2020-06-10T16:00:14Z)

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

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