論文の概要: No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation

• arxiv url: http://arxiv.org/abs/2206.06015v1
• Date: Mon, 13 Jun 2022 10:13:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-14 17:54:36.780443
• Title: No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation
• Title（参考訳）: 雑音フィードバックを持つゲームにおける非回帰学習:学習速度分離による高速率と適応性
• Authors: Yu-Guan Hsieh, Kimon Antonakopoulos, Volkan Cevher, Panayotis Mertikopoulos
• Abstract要約: 学習者が他の最適化エージェントと連続したゲームに関わった場合の後悔の問題を考察する。 この場合、全てのプレイヤーが非相対的アルゴリズムに従えば、完全に敵対する環境に対してかなり低い後悔を達成することができる。 本稿では,最悪とベストケースの後悔の保証を円滑に補間する完全適応手法を提案する。
• 参考スコア（独自算出の注目度）: 76.61911795703062
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We examine the problem of regret minimization when the learner is involved in a continuous game with other optimizing agents: in this case, if all players follow a no-regret algorithm, it is possible to achieve significantly lower regret relative to fully adversarial environments. We study this problem in the context of variationally stable games (a class of continuous games which includes all convex-concave and monotone games), and when the players only have access to noisy estimates of their individual payoff gradients. If the noise is additive, the game-theoretic and purely adversarial settings enjoy similar regret guarantees; however, if the noise is multiplicative, we show that the learners can, in fact, achieve constant regret. We achieve this faster rate via an optimistic gradient scheme with learning rate separation -- that is, the method's extrapolation and update steps are tuned to different schedules, depending on the noise profile. Subsequently, to eliminate the need for delicate hyperparameter tuning, we propose a fully adaptive method that smoothly interpolates between worst- and best-case regret guarantees.
• Abstract（参考訳）: 本稿では,学習者が他の最適化エージェントと連続ゲームに関わった場合の後悔の最小化の問題について考察する。 変動安定ゲーム(全凸凹ゲームと単調ゲームを含む連続ゲーム)の文脈でこの問題を考察し、各プレイヤーが個々のペイオフ勾配のノイズ推定にのみアクセスできる場合について考察する。 雑音が加法的であれば、ゲーム理論と純粋に敵対的な設定は同様の後悔の保証を享受するが、ノイズが乗算的であれば、学習者が常に後悔できることを示す。 学習速度分離を伴う楽観的勾配スキーム(つまり、ノイズプロファイルに応じて、その方法の補間と更新ステップが異なるスケジュールに調整される)によって、この高速レートを達成する。 その後、微妙なハイパーパラメータチューニングの必要性をなくすため、最悪と最良な後悔の保証をスムーズに補間する完全適応手法を提案する。

関連論文リスト

• Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously [8.850922234275636]
  スイッチング後悔は、トライアルシーケンスの任意のセグメンテーションに対して定義され、各セグメンテーションの静的後悔の和に等しい。 我々のアルゴリズムは非常に効率的で、時間軸の対数的な空間と時間単位の複雑さを持つ。
  論文  参考訳（メタデータ） (2024-05-31T14:16:52Z)
• Advancing Unsupervised Low-light Image Enhancement: Noise Estimation, Illumination Interpolation, and Self-Regulation [55.07472635587852]
  低光画像強調(LLIE)技術は、画像の詳細の保存とコントラストの強化に顕著な進歩をもたらした。 これらのアプローチは、動的ノイズを効率的に緩和し、様々な低照度シナリオを収容する上で、永続的な課題に直面する。 まず,低照度画像の雑音レベルを迅速かつ高精度に推定する方法を提案する。 次に、照明と入力の一般的な制約を満たすために、Learningable Illumination Interpolator (LII) を考案する。
  論文  参考訳（メタデータ） (2023-05-17T13:56:48Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Efficient Adaptive Regret Minimization [35.121567896321885]
  オンライン凸最適化では、プレイヤーは繰り返しゲーム全体に対して固定されたコンパレータに対する後悔を最小限にすることを目的としている。 既存の適応的後悔アルゴリズムは計算的なペナルティに悩まされる - 典型的には、ゲームの繰り返し回数で対数的に増加する乗法的因子の順序である。 本稿では,この計算ペナルティをゲーム繰り返し回数で2倍に対数的に減らし,最適な適応的再帰限界を最小限に抑える方法を示す。
  論文  参考訳（メタデータ） (2022-07-01T19:43:11Z)
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium [33.9962699667578]
  No-regretアルゴリズムはゲーム理論の保証の点で等しく作成されません。 楽観的なミラー降下に基づく非相対的ポリシーを提案する。
  論文  参考訳（メタデータ） (2021-04-26T17:52:29Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)

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

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