論文の概要: A Slingshot Approach to Learning in Monotone Games
- arxiv url: http://arxiv.org/abs/2305.16610v1
- Date: Fri, 26 May 2023 04:02:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 17:10:49.493424
- Title: A Slingshot Approach to Learning in Monotone Games
- Title(参考訳): 単調ゲームにおける学習へのslingshotアプローチ
- Authors: Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Atsushi Iwasaki
- Abstract要約: ノイズの存在下でも収束が持続する新しい枠組みを提案する。
この枠組みに基づくアルゴリズムは, より高速な収束を実証的に示す。
- 参考スコア(独自算出の注目度): 8.780339295067096
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we address the problem of computing equilibria in monotone
games. The traditional Follow the Regularized Leader algorithms fail to
converge to an equilibrium even in two-player zero-sum games. Although
optimistic versions of these algorithms have been proposed with last-iterate
convergence guarantees, they require noiseless gradient feedback. To overcome
this limitation, we present a novel framework that achieves last-iterate
convergence even in the presence of noise. Our key idea involves perturbing or
regularizing the payoffs or utilities of the games. This perturbation serves to
pull the current strategy to an anchored strategy, which we refer to as a {\it
slingshot} strategy. First, we establish the convergence rates of our framework
to a stationary point near an equilibrium, regardless of the presence or
absence of noise. Next, we introduce an approach to periodically update the
slingshot strategy with the current strategy. We interpret this approach as a
proximal point method and demonstrate its last-iterate convergence. Our
framework is comprehensive, incorporating existing payoff-regularized
algorithms and enabling the development of new algorithms with last-iterate
convergence properties. Finally, we show that our algorithms, based on this
framework, empirically exhibit faster convergence.
- Abstract(参考訳): 本稿では,モノトーンゲームにおける平衡計算の問題に対処する。
従来のFollow the Regularized Leaderアルゴリズムは、2プレイヤーゼロサムゲームでも平衡に収束しない。
これらのアルゴリズムの楽観的なバージョンは、最終的な収束を保証するために提案されているが、ノイズレス勾配フィードバックが必要である。
この限界を克服するために,ノイズの存在下でもラストイテレート収束を実現する新しい枠組みを提案する。
私たちのキーとなるアイデアは、ゲームの支払いやユーティリティの摂動や規則化です。
この摂動は、現在の戦略を固定された戦略に引き込むのに役立ち、我々はそれを {\it slingshot} 戦略と呼ぶ。
まず, 雑音の有無に関わらず, 平衡近傍の定常点への枠組みの収束率を定式化する。
次に,現在の戦略でslingshot戦略を定期的に更新する手法を提案する。
我々は,このアプローチを近点法として解釈し,そのラストイテレート収束を示す。
我々のフレームワークは包括的であり、既存のペイオフ正規化アルゴリズムを取り入れ、ラストイテレート収束特性を持つ新しいアルゴリズムの開発を可能にしている。
最後に,この枠組みに基づくアルゴリズムは,より高速な収束を示すことを示す。
関連論文リスト
- Exploiting hidden structures in non-convex games for convergence to Nash
equilibrium [62.88214569402201]
現代の機械学習アプリケーションは、非協調的なナッシュリリアとして定式化することができる。
決定論的環境と決定論的環境の両方に明確な収束保証を提供する。
論文 参考訳(メタデータ) (2023-12-27T15:21:25Z) - Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale
Algorithm Under Weak Reachability [13.932957324139672]
我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。
従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。
我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
論文 参考訳(メタデータ) (2023-12-13T09:31:30Z) - The equivalence of dynamic and strategic stability under regularized
learning in games [33.74394172275373]
有限ゲームにおける正規化学習の長時間動作について検討する。
戦略的安定性と動的安定性の等価性を得る。
エントロピー正則化に基づく手法は幾何速度で収束することを示す。
論文 参考訳(メタデータ) (2023-11-04T14:07:33Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium [62.51015395213579]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
論文 参考訳(メタデータ) (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) - Losing momentum in continuous-time stochastic optimisation [62.997667081978825]
近年,運動量に基づくアルゴリズムが特に普及している。
本研究では,運動量を伴う勾配降下の連続時間モデルを提案し,解析する。
我々は、時間とともに運動量を減らす際に、我々のシステムを世界規模のミニミザーに収束させることを示す。
論文 参考訳(メタデータ) (2022-09-08T10:46:05Z) - A unified stochastic approximation framework for learning in games [82.74514886461257]
ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。
提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
論文 参考訳(メタデータ) (2022-06-08T14:30:38Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Last-iterate Convergence of Decentralized Optimistic Gradient
Descent/Ascent in Infinite-horizon Competitive Markov Games [37.70703888365849]
無限水平割引2プレイヤーゼロサムマルコフゲームについて検討する。
我々は,自己再生下でのナッシュ均衡に収束する分散アルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-02-08T21:45:56Z) - Learning Nash Equilibria in Zero-Sum Stochastic Games via
Entropy-Regularized Policy Approximation [18.35524179586723]
ゼロサムゲームにおけるナッシュ均衡学習の計算コストを削減するためのポリシー近似の利用について検討する。
我々は,Nashポリシーを近似するために,エントロピー規則化されたソフトポリシーのシーケンスを利用する新しいQ-ラーニング型アルゴリズムを提案する。
一定の条件下では、正規化されたQ-関数を更新することにより、アルゴリズムはナッシュ平衡に収束する。
論文 参考訳(メタデータ) (2020-09-01T01:03:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。