論文の概要: Robust No-Regret Learning in Min-Max Stackelberg Games
- arxiv url: http://arxiv.org/abs/2203.14126v1
- Date: Sat, 26 Mar 2022 18:12:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-29 17:48:30.635152
- Title: Robust No-Regret Learning in Min-Max Stackelberg Games
- Title（参考訳）: Min-Max Stackelbergゲームにおけるロバストな非線形学習
- Authors: Denizalp Goktas, Jiayi Zhao, Amy Greenwald
- Abstract要約: 本研究は,Min-maxゲームにおける非regret学習の挙動について考察する。
非回帰力学がスタックルバーグ平衡に収束することを示す。
OMD のダイナミクスは,オンライン min-max Stackelberg ゲームの大規模なクラスでは堅牢であることを示す。
- 参考スコア（独自算出の注目度）: 1.6500749121196987
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The behavior of no-regret learning algorithms is well understood in
two-player min-max (i.e, zero-sum) games. In this paper, we investigate the
behavior of no-regret learning in min-max games with dependent strategy sets,
where the strategy of the first player constrains the behavior of the second.
Such games are best understood as sequential, i.e., min-max Stackelberg, games.
We consider two settings, one in which only the first player chooses their
actions using a no-regret algorithm while the second player best responds, and
one in which both players use no-regret algorithms. For the former case, we
show that no-regret dynamics converge to a Stackelberg equilibrium. For the
latter case, we introduce a new type of regret, which we call Lagrangian
regret, and show that if both players minimize their Lagrangian regrets, then
play converges to a Stackelberg equilibrium. We then observe that online mirror
descent (OMD) dynamics in these two settings correspond respectively to a known
nested (i.e., sequential) gradient descent-ascent (GDA) algorithm and a new
simultaneous GDA-like algorithm, thereby establishing convergence of these
algorithms to Stackelberg equilibrium. Finally, we analyze the robustness of
OMD dynamics to perturbations by investigating online min-max Stackelberg
games. We prove that OMD dynamics are robust for a large class of online
min-max games with independent strategy sets. In the dependent case, we
demonstrate the robustness of OMD dynamics experimentally by simulating them in
online Fisher markets, a canonical example of a min-max Stackelberg game with
dependent strategy sets.
- Abstract（参考訳）: 非regret学習アルゴリズムの振る舞いは、2人のプレイヤー min-max (すなわちゼロサム) ゲームでよく理解されている。
本稿では,第1プレイヤーの戦略が第2プレイヤーの行動に制約を与えるような,依存戦略セットを持つmin-maxゲームにおける非回帰学習の動作について検討する。
このようなゲームは逐次、すなわちmin-max stackelbergゲームとしてよく理解される。
我々は,第1のプレイヤーのみが非回帰アルゴリズムを用いて行動を選択するのに対して,第2のプレイヤーは最もよく反応するのに対し,第2のプレイヤーは2つの設定を考える。
前者の場合、非回帰力学がスタックルバーグ平衡に収束することを示す。
後者の場合、新しいタイプの後悔を導入し、ラグランジアン後悔(Lagrangian regret)と呼び、双方のプレイヤーがラグランジアン後悔を最小化すれば、プレイはスタックルバーグ均衡に収束することを示す。
次に、これらの2つの設定におけるオンラインミラー降下(OMD)ダイナミクスは、それぞれ既知のネスト(シーケンシャル)勾配降下(GDA)アルゴリズムと新しい同時GDAライクなアルゴリズムに対応し、これらのアルゴリズムのスタックルバーグ平衡への収束を確立する。
最後に,オンラインmin-max stackelbergゲームを用いてomdダイナミクスの摂動に対するロバスト性を分析する。
独立戦略セットを持つオンラインミニマックスゲームにおいて,OMDダイナミクスが堅牢であることを証明する。
従属の場合、オンラインフィッシャーマーケットでそれらをシミュレートすることで、OMDダイナミックスのロバスト性を実験的に実証する。
関連論文リスト
- Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳（メタデータ） (2023-05-31T22:09:24Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳（メタデータ） (2022-01-30T06:10:04Z) - Can Reinforcement Learning Find Stackelberg-Nash Equilibria in
General-Sum Markov Games with Myopic Followers? [156.5760265539888]
我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。
そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。
オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-27T05:41:14Z) - Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。
我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。
そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
論文 参考訳（メタデータ） (2021-12-06T08:27:54Z) - Fast Rates for Nonparametric Online Learning: From Realizability to
Learning in Games [36.969021834291745]
本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。
この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。
実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
論文 参考訳（メタデータ） (2021-11-17T05:24:21Z) - Convex-Concave Min-Max Stackelberg Games [0.0]
コンベックス・コンケーブ min-max Stackelberg ゲームのクラスを解く2つの一階法を導入する。
私たちは我々の方法が時間内に収束していることを示します。
フィッシャー市場での競争均衡の計算は、min-max Stackelbergゲームも含む。
論文 参考訳（メタデータ） (2021-10-05T06:09:45Z) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - Gap-Dependent Bounds for Two-Player Markov Games [122.20541282562363]
2-TBSGによる2プレイヤーターン型マルコフゲームにおけるナッシュラーニングアルゴリズムの実行時の累積的後悔の分析
この境界は対数項のみの理論的な下界と一致する。
我々は、無限の地平線でディスカウントされたゲーム設定に結論を拡張し、同様のギャップ依存対数後悔境界を提案する。
論文 参考訳（メタデータ） (2021-07-01T18:25:07Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。