論文の概要: 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戦略をアップデートし,現在の戦略を有限間隔でアンカーすることで,ツイストを導入する。
この革新は、基礎となるゲームの正確なナッシュ均衡を保証されたレートで識別する権限を与えてくれます。
提案されたフレームワークはすべて包括的であり、既存のペイオフ摂動アルゴリズムを統合する。
最後に、この枠組みを基盤とした我々のアルゴリズムは、かなり加速された収束を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。