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

• arxiv url: http://arxiv.org/abs/2112.02856v2
• Date: Wed, 8 Dec 2021 02:06:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-09 10:21:25.071410
• Title: Optimal No-Regret Learning in Strongly Monotone Games with Bandit Feedback
• Title（参考訳）: バンドフィードバックを持つ強いモノトーンゲームにおける最適非線形学習
• Authors: Tianyi Lin, Zhengyuan Zhou, Wenjia Ba, Jiawei Zhang
• Abstract要約: 我々は,各エージェントが各エージェントの報酬を観察する,未知のゲームにおけるオンライン学習について検討する。 まず,オンラインバンディット凸最適化アルゴリズムを構築し,$tildeTheta(sqrtT)$に対する単一エージェントの最適後悔を実現することを示す。 すると、各エージェントがこの非回帰学習アルゴリズムを強い単調ゲームに適用すると、ジョイントアクションはテクストラストにおいて、$tildeTheta(sqrt)の速度でユニークなナッシュ平衡に収束することを示す。
• 参考スコア（独自算出の注目度）: 33.58816254556432
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online no-regret learning in unknown games with bandit feedback, where each agent only observes its reward at each time -- determined by all players' current joint action -- rather than its gradient. We focus on the class of smooth and strongly monotone games and study optimal no-regret learning therein. Leveraging self-concordant barrier functions, we first construct an online bandit convex optimization algorithm and show that it achieves the single-agent optimal regret of $\tilde{\Theta}(\sqrt{T})$ under smooth and strongly-concave payoff functions. We then show that if each agent applies this no-regret learning algorithm in strongly monotone games, the joint action converges in \textit{last iterate} to the unique Nash equilibrium at a rate of $\tilde{\Theta}(1/\sqrt{T})$. Prior to our work, the best-know convergence rate in the same class of games is $O(1/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(1/\sqrt{T})$). 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 results on several simulation studies -- Cournot competition, Kelly auctions, and distributed regularized logistic regression -- to demonstrate the efficacy of our algorithm.
• Abstract（参考訳）: 各エージェントは、その勾配ではなく、すべてのプレイヤーの現在の共同アクションによって決定される、各時点における報酬のみを観察する。 我々は,滑らかで強いモノトーンゲームのクラスに注目し,そこでの最適ノンリグレット学習を考察する。 自己一致バリア関数を活用することで,オンラインバンディット凸最適化アルゴリズムをまず構築し,平滑かつ強コンケーブなペイオフ関数の下で$\tilde{\theta}(\sqrt{t})$の単一エージェント最適後悔を達成することを示す。 すると、各エージェントがこの非回帰学習アルゴリズムを強い単調ゲームに適用すると、結合作用は、$\tilde{\Theta}(1/\sqrt{T})$の速度で、一意なナッシュ平衡に収束する。 我々の研究に先立ち、同じゲームのクラスにおける最良の知識収束率は$O(1/T^{1/3})$(異なるアルゴリズムによって達成される)であり、したがって最適な非回帰学習アルゴリズムの問題を解き放つ(既知の下界は$\Omega(1/\sqrt{T})$)。 そこで本研究では,この開放的課題を解決し,第1次バンディット最適学習アルゴリズムを同定することで,バンディットゲーム理論的学習の広い景観に寄与し,単一エージェント学習における最適後悔とマルチエージェント学習における最適ラストイテレート収束率の両方を(ログファクターまで)達成する。 また,提案アルゴリズムの有効性を実証するため,いくつかのシミュレーション研究 (Cournot competition, Kelly auctions, distributed regularized logistic regression) の結果も提示した。

関連論文リスト

• 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)

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

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