論文の概要: Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2112.02856v4
• Date: Fri, 29 Mar 2024 04:18:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-01 21:15:55.111724
• Title: Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback
• Title（参考訳）: バンドフィードバックを持つ強いモノトーンゲームにおける2つの最適非線形オンライン学習
• Authors: Wenjia Ba, Tianyi Lin, Jiawei Zhang, Zhengyuan Zhou,
• Abstract要約: 本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
• 参考スコア（独自算出の注目度）: 29.553652241608997
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online no-regret learning in unknown games with bandit feedback, where each player can only observe its reward at each time -- determined by all players' current joint action -- rather than its gradient. We focus on the class of \textit{smooth and strongly monotone} games and study optimal no-regret learning therein. Leveraging self-concordant barrier functions, we first construct a new bandit learning algorithm and show that it achieves the single-agent optimal regret of $\tilde{\Theta}(n\sqrt{T})$ under smooth and strongly concave reward functions ($n \geq 1$ is the problem dimension). We then show that if each player applies this no-regret learning algorithm in strongly monotone games, the joint action converges in the \textit{last iterate} to the unique Nash equilibrium at a rate of $\tilde{\Theta}(nT^{-1/2})$. Prior to our work, the best-known convergence rate in the same class of games is $\tilde{O}(n^{2/3}T^{-1/3})$ (achieved by a different algorithm), thus leaving open the problem of optimal no-regret learning algorithms (since the known lower bound is $\Omega(nT^{-1/2})$). Our results thus settle this open problem and contribute to the broad landscape of bandit game-theoretical learning by identifying the first doubly optimal bandit learning algorithm, in that it achieves (up to log factors) both optimal regret in the single-agent learning and optimal last-iterate convergence rate in the multi-agent learning. We also present preliminary numerical results on several application problems to demonstrate the efficacy of our algorithm in terms of iteration count.
• Abstract（参考訳）: 各プレイヤーは、その勾配ではなく、現在の全てのプレイヤーのジョイントアクションによって決定される報酬を、各プレイヤーがそれぞれのタイミングでのみ観察できる、バンドイットフィードバックを持つ未知のゲームにおいて、オンラインのノンレグリート学習を考える。 我々は,textit{smooth and strong monotone} ゲームに焦点をあて,そこで最適な非回帰学習を学習する。 自己調和障壁関数を活用することにより、まず新しいバンディット学習アルゴリズムを構築し、滑らかで強凹な報酬関数(n \geq 1$ is the problem dimension)の下で、単項の最適後悔($\tilde{\Theta}(n\sqrt{T})を達成できることを示す。 すると、各プレイヤーがこの非回帰学習アルゴリズムを強い単調ゲームに適用すると、結合アクションは、$\tilde{\Theta}(nT^{-1/2})$の速度で、一意なナッシュ平衡に収束する。 我々の研究に先立ち、同じクラスのゲームにおいて最もよく知られた収束率は$\tilde{O}(n^{2/3}T^{-1/3})$(異なるアルゴリズムによって達成される)であり、したがって最適な非回帰学習アルゴリズムの問題を解き放つ(既知の下界は$\Omega(nT^{-1/2})$)。 そこで我々は,このオープンな問題を解決し,第1の2倍の最適帯域幅学習アルゴリズムを同定し,単一エージェント学習における最適後悔とマルチエージェント学習における最適最終項目収束率の両方を達成することにより,バンド幅のゲーム理論学習の広い展望に寄与した。 また、本アルゴリズムの有効性を反復数の観点から示すために、いくつかの応用問題に関する予備的な数値結果も提示する。

関連論文リスト

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• 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)
• Doubly Optimal No-Regret Learning in Monotone Games [10.760195409078591]
  本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムを提案する。 このアルゴリズムは, 滑らかかつ凸な損失関数の下での対角的条件下での最適$O(sqrtT)$後悔と, (ii) 最適$O(frac1T)$最後の収束率をナッシュ平衡に達成する。
  論文  参考訳（メタデータ） (2023-01-30T17:55:53Z)
• No-regret learning for repeated non-cooperative games with lossy bandits [5.437709019435926]
  本研究では,長期的後悔の損失を最小限に抑えるために,プレイヤーの非同期オンライン学習戦略について検討する。 この論文は、損失帯域付きオンライングラディエントDescent(OGD-lb)と呼ばれる、新しい非回帰学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-14T05:02:56Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
  我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。 提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-20T06:36:19Z)

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

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