論文の概要: Convex-Concave Min-Max Stackelberg Games

• arxiv url: http://arxiv.org/abs/2110.05192v8
• Date: Wed, 5 Jul 2023 21:11:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-07 19:00:19.412163
• Title: Convex-Concave Min-Max Stackelberg Games
• Title（参考訳）: Convex-Concave Min-Max Stackelberg Games
• Authors: Denizalp Goktas and Amy Greenwald
• Abstract要約: コンベックス・コンケーブ min-max Stackelberg ゲームのクラスを解く2つの一階法を導入する。 私たちは我々の方法が時間内に収束していることを示します。 フィッシャー市場での競争均衡の計算は、min-max Stackelbergゲームも含む。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent strategy sets; little is known about solving games with dependent strategy sets, which can be characterized as min-max Stackelberg games. We introduce two first-order methods that solve a large class of convex-concave min-max Stackelberg games, and show that our methods converge in polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald's maximin model, a variant of which is the main paradigm used in robust optimization, which means that our methods can likewise solve many convex robust optimization problems. We observe that the computation of competitive equilibria in Fisher markets also comprises a min-max Stackelberg game. Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.
• Abstract（参考訳）: min-max最適化問題(即ちmin-maxゲーム)は、幅広い機械学習問題に適用可能であるため、多くの注目を集めている。 近年は大きな進歩を遂げているものの、文献は独立した戦略セットを持つゲームに焦点を当てており、依存戦略セットによるゲームの解決についてはほとんど知られていない。 コンベックス・コンケーブ min-max Stackelberg のゲーム群を解く2つの一階法を導入し,この方法が多項式時間で収束することを示す。 Min-max Stackelberg ゲームは Wald によって最初に研究され、ウォルドの Maximin モデル(英語版) の追随名の下で、その変種はロバスト最適化で使用される主要なパラダイムであり、これは、我々の方法が同様に多くの凸性最適化問題を解くことができることを意味する。 フィッシャーマーケットにおける競争均衡の計算は,min-max stackelbergゲームも構成している。 さらに,様々なユーティリティ構造を持つフィッシャー市場の競争均衡を計算し,実運用におけるアルゴリズムの有効性と効率を実証する。 実験は,アルゴリズムの収束率に異なる平滑性特性がどう影響するかを示すことにより,理論的結果を拡張する可能性を示唆する。

関連論文リスト

• Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
  Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。 本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。 本稿では,SCGの局所探索アルゴリズムを2つ提案する。第1に,微分可能プログラミングを用いてILDをアンロールすることで導関数を求める勾配降下アルゴリズムを提案する。 第二のアルゴリズムは、フォロワーの進化軌道を短くすることでツイストを加える。
  論文  参考訳（メタデータ） (2022-09-15T21:32:23Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• Robust No-Regret Learning in Min-Max Stackelberg Games [1.6500749121196987]
  本研究は,Min-maxゲームにおける非regret学習の挙動について考察する。 非回帰力学がスタックルバーグ平衡に収束することを示す。 OMD のダイナミクスは,オンライン min-max Stackelberg ゲームの大規模なクラスでは堅牢であることを示す。
  論文  参考訳（メタデータ） (2022-03-26T18:12:40Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances [58.54078318403909]
  min-max問題(英: min-max problem)またはサドル点問題(英: saddle point problem)は、サムゲームにおいても研究されるクラス逆問題である。
  論文  参考訳（メタデータ） (2020-06-15T05:33:42Z)
• Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method [10.819408603463426]
  ミニマックスサドル点降下器は、機械の傾きと信号処理において幅広い用途に現れる。 単純な多段階LA-Ascentアルゴリズムは文献上の既存アルゴリズムよりも強いことを示す。
  論文  参考訳（メタデータ） (2020-03-18T08:38:34Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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