論文の概要: Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium

• arxiv url: http://arxiv.org/abs/2104.12761v1
• Date: Mon, 26 Apr 2021 17:52:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-27 14:17:34.593930
• Title: Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
• Title（参考訳）: 継続的ゲームにおける適応学習: 最適回帰境界とナッシュ平衡への収束
• Authors: Yu-Guan Hsieh, Kimon Antonakopoulos, Panayotis Mertikopoulos
• Abstract要約: No-regretアルゴリズムはゲーム理論の保証の点で等しく作成されません。 楽観的なミラー降下に基づく非相対的ポリシーを提案する。
• 参考スコア（独自算出の注目度）: 33.9962699667578
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In game-theoretic learning, several agents are simultaneously following their individual interests, so the environment is non-stationary from each player's perspective. In this context, the performance of a learning algorithm is often measured by its regret. However, no-regret algorithms are not created equal in terms of game-theoretic guarantees: depending on how they are tuned, some of them may drive the system to an equilibrium, while others could produce cyclic, chaotic, or otherwise divergent trajectories. To account for this, we propose a range of no-regret policies based on optimistic mirror descent, with the following desirable properties: i) they do not require any prior tuning or knowledge of the game; ii) they all achieve O(\sqrt{T}) regret against arbitrary, adversarial opponents; and iii) they converge to the best response against convergent opponents. Also, if employed by all players, then iv) they guarantee O(1) social regret; while v) the induced sequence of play converges to Nash equilibrium with O(1) individual regret in all variationally stable games (a class of games that includes all monotone and convex-concave zero-sum games).
• Abstract（参考訳）: ゲーム理論学習では、複数のエージェントがそれぞれの興味を同時に追っているため、各プレイヤーの観点から環境は静止していない。 この文脈では、学習アルゴリズムのパフォーマンスは、しばしばその後悔によって測定される。 しかし、ゲーム理論の保証の観点からは、非回帰アルゴリズムは等しく作られていない:それらがどのように調整されているかによっては、システムに平衡性を持たせるものもあれば、循環的、カオス的、あるいは他の散逸した軌道を生成できるものもある。 これを説明するために、楽観的ミラー降下に基づく非相対的ポリシーの範囲を提案し、以下の望ましい性質を持つ: i) ゲームに対する事前のチューニングや知識を必要としない; i) 任意の敵に対するO(\sqrt{T})後悔を達成する; iii) 収束する相手に対する最良の応答に収束する。 また、すべてのプレイヤーが採用した場合、 iv) は O(1) の社会的後悔を保証し、v) の誘導されたプレイ列は、すべての変分安定なゲーム(全ての単調および凸凸凸ゼロサムゲームを含むゲームのクラス)において、O(1) 個人の後悔とナッシュ均衡に収束する。

関連論文リスト

• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
  マルチプレイヤーゲームにおける平衡は、一意でも爆発的でもない。 本稿では,平等な共有という自然な目的に焦点をあてることで,これらの課題に対処するための最初の一歩を踏み出す。 我々は、様々な設定でほぼ同じシェアを確実に得る、非回帰学習にインスパイアされた、一連の効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-06-06T15:59:17Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。 ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。 我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
  論文  参考訳（メタデータ） (2022-10-25T19:02:03Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation [76.61911795703062]
  学習者が他の最適化エージェントと連続したゲームに関わった場合の後悔の問題を考察する。 この場合、全てのプレイヤーが非相対的アルゴリズムに従えば、完全に敵対する環境に対してかなり低い後悔を達成することができる。 本稿では,最悪とベストケースの後悔の保証を円滑に補間する完全適応手法を提案する。
  論文  参考訳（メタデータ） (2022-06-13T10:13:51Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。 厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。 この結果は,学習過程の結果を予測する上で重要な意味を持つ。
  論文  参考訳（メタデータ） (2020-10-19T13:49:06Z)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
  論文  参考訳（メタデータ） (2020-04-01T17:39:00Z)

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

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