論文の概要: Slingshot Perturbation to Learning in Monotone Games

• arxiv url: http://arxiv.org/abs/2305.16610v2
• Date: Mon, 2 Oct 2023 06:11:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-03 17:35:08.283993
• Title: Slingshot Perturbation to Learning in Monotone Games
• Title（参考訳）: モノトーンゲームにおける学習へのスリングショット摂動
• Authors: Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Atsushi Iwasaki
• Abstract要約: 本稿では,モノトーンゲームにおけるナッシュ均衡学習の問題に対処する。 我々はモノトーンゲームにおける平衡学習のための統一的な枠組みを確立し、完全なフィードバックとうるさいフィードバックの両方を収容する。 我々は、スリングショット戦略を更新し、現在の戦略を有限間隔で固定することで、ツイストを導入する。
• 参考スコア（独自算出の注目度）: 11.872888894685763
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses the problem of learning Nash equilibria in {\it monotone games} where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. The optimistic family of learning algorithms, exemplified by optimistic Follow-the-Regularized-Leader and optimistic Mirror Descent, successfully achieves last-iterate convergence in scenarios devoid of noise, leading the dynamics to a Nash equilibrium. A recent emerging trend underscores the promise of the perturbation approach, where payoff functions are perturbed based on the distance from an anchoring, or {\it slingshot}, strategy. In response, we first establish a unified framework for learning equilibria in monotone games, accommodating both full and noisy feedback. Second, we construct the convergence rates toward an approximated equilibrium, irrespective of noise presence. Thirdly, we introduce a twist by updating the slingshot strategy, anchoring the current strategy at finite intervals. This innovation empowers us to identify the exact Nash equilibrium of the underlying game with guaranteed rates. The proposed framework is all-encompassing, integrating existing payoff-perturbed algorithms. Finally, empirical demonstrations affirm that our algorithms, grounded in this framework, exhibit significantly accelerated convergence.
• Abstract（参考訳）: 本稿では, 戦略プロファイル空間において, ペイオフ関数の勾配が単調であり, 付加雑音を含むような, モノトーンゲームにおけるナッシュ均衡学習の問題に対処する。 楽観的な学習アルゴリズムのファミリーは、楽観的なフォロー・ザ・レギュラライズド・リーダーと楽観的なミラーの降下によって例示され、ノイズのないシナリオにおいてラストイテレート収束を達成し、ダイナミクスをnash平衡へと導く。 最近のトレンドは、支払い関数がアンカーからの距離、すなわち {\it slingshot} の戦略に基づいて摂動されるという、摂動アプローチの可能性を浮き彫りにしている。 これに対し,我々はまずモノトーンゲームにおける均衡学習のための統一的なフレームワークを構築し,完全なフィードバックとノイズフィードバックの両方を収容する。 第二に, 雑音の存在にかかわらず近似平衡への収束率を構成する。 第3に,slingshot戦略をアップデートし,現在の戦略を有限間隔でアンカーすることで,ツイストを導入する。 この革新は、基礎となるゲームの正確なナッシュ均衡を保証されたレートで識別する権限を与えてくれます。 提案されたフレームワークはすべて包括的であり、既存のペイオフ摂動アルゴリズムを統合する。 最後に、この枠組みを基盤とした我々のアルゴリズムは、かなり加速された収束を示す。

関連論文リスト

• 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)
• Local and adaptive mirror descents in extensive-form games [37.04094644847904]
  我々は,ゼロサム不完全な情報ゲーム (IIG) において,軌道フィードバックを用いて$epsilon$-Optimal戦略を学習する方法を研究する。 我々は、プレイヤーが時間とともにポリシーを更新する固定サンプリングアプローチを検討するが、与えられた固定サンプリングポリシーによって観察される。 このアプローチは高い確率で$tildemathcalO(T-1/2)$の収束率を保証し、ゲームパラメータにほぼ最適に依存することを示す。
  論文  参考訳（メタデータ） (2023-09-01T09:20:49Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Robust Imitation via Mirror Descent Inverse Reinforcement Learning [18.941048578572577]
  本稿では,制約付き凸問題の反復解である報酬関数列を予測することを提案する。 提案したミラー降下更新規則は,ブレグマンの発散を最小化できることを示す。 我々のIRL法は, 既存手法よりも高い性能を示した。
  論文  参考訳（メタデータ） (2022-10-20T12:25:21Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• Alternating Mirror Descent for Constrained Min-Max Games [44.46086335474311]
  制約付き戦略空間を持つ2プレイヤー双線形ゼロサムゲームについて検討する。 我々は,各プレイヤーが交互に行動する交互ミラー降下アルゴリズムを,制約付き最適化のためのミラー降下アルゴリズムに従って解析する。
  論文  参考訳（メタデータ） (2022-06-08T20:48:16Z)
• Reparameterized Variational Divergence Minimization for Stable Imitation [57.06909373038396]
  確率的発散の選択における変動が、より高性能なILOアルゴリズムをもたらす可能性について検討する。 本稿では,提案する$f$-divergence最小化フレームワークの課題を軽減するために,逆模倣学習のための再パラメータ化手法を提案する。 経験的に、我々の設計選択は、ベースラインアプローチより優れ、低次元連続制御タスクにおける専門家のパフォーマンスとより密に適合するIOOアルゴリズムを許容することを示した。
  論文  参考訳（メタデータ） (2020-06-18T19:04:09Z)

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

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