論文の概要: Finite-Sample Guarantees for Best-Response Learning Dynamics in Zero-Sum Matrix Games

• arxiv url: http://arxiv.org/abs/2407.20128v2
• Date: Wed, 7 Aug 2024 19:04:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-09 17:49:51.607291
• Title: Finite-Sample Guarantees for Best-Response Learning Dynamics in Zero-Sum Matrix Games
• Title（参考訳）: ゼロサムマトリックスゲームにおけるベストレスポンス学習ダイナミクスのための有限サンプル保証
• Authors: Fathima Zarin Faizal, Asuman Ozdaglar, Martin J. Wainwright,
• Abstract要約: 2人のプレイヤーゼロサム行列ゲームに対する最適応答型学習ダイナミクスについて検討する。 我々は,各プレイヤーがゲームと相手の戦略について持っている情報の種類によって区別される2つの設定について検討する。
• 参考スコア（独自算出の注目度）: 22.380293155135096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study best-response type learning dynamics for two player zero-sum matrix games. We consider two settings that are distinguished by the type of information that each player has about the game and their opponent's strategy. The first setting is the full information case, in which each player knows their own and the opponent's payoff matrices and observes the opponent's mixed strategy. The second setting is the minimal information case, where players do not observe the opponent's strategy and are not aware of either of the payoff matrices (instead they only observe their realized payoffs). For this setting, also known as the radically uncoupled case in the learning in games literature, we study a two-timescale learning dynamics that combine smoothed best-response type updates for strategy estimates with a TD-learning update to estimate a local payoff function. For these dynamics, without additional exploration, we provide polynomial-time finite-sample guarantees for convergence to an $\epsilon$-Nash equilibrium.
• Abstract（参考訳）: 2人のプレイヤーゼロサム行列ゲームに対する最適応答型学習ダイナミクスについて検討する。 我々は,各プレイヤーがゲームとその相手の戦略について持っている情報の種類によって区別される2つの設定について検討する。 最初の設定は、各プレイヤーが自分自身と相手のペイオフ行列を知り、相手の混合戦略を観察する完全な情報ケースである。 2つ目の設定は最小限の情報ケースであり、プレイヤーは相手の戦略を観察せず、どちらかのペイオフ行列を意識していない(代わりに、プレイヤーは実際のペイオフのみを観察する)。 ゲーム文学における学習における急激なアンカップリング(英語版)としても知られるこの設定のために、戦略推定のためのスムーズな最適応答型更新と、局所的な支払関数を推定するTD学習更新を組み合わせた2段階の学習力学を考察する。 これらのダイナミクスに対しては、追加の探索なしに、$\epsilon$-Nash平衡への収束に対する多項式時間有限サンプル保証を提供する。

関連論文リスト

• All by Myself: Learning Individualized Competitive Behaviour with a Contrastive Reinforcement Learning optimization [57.615269148301515]
  競争ゲームのシナリオでは、エージェントのセットは、彼らの目標を最大化し、敵の目標を同時に最小化する決定を学習する必要があります。 本稿では,競争ゲームの表現を学習し,特定の相手の戦略をどうマップするか,それらを破壊するかを学習する3つのニューラルネットワーク層からなる新しいモデルを提案する。 我々の実験は、オフライン、オンライン、競争特化モデル、特に同じ対戦相手と複数回対戦した場合に、我々のモデルがより良いパフォーマンスを達成することを示した。
  論文  参考訳（メタデータ） (2023-10-02T08:11:07Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• A Ranking Game for Imitation Learning [22.028680861819215]
  模倣を、$textitpolicy$と$textitreward$関数の間の2プレイヤーランキングベースのStackelbergゲームとして扱う。 このゲームは、オフラインの好みから学習する逆強化学習(IRL)法と方法の両方の多くのサブセットを含んでいる。 本研究では,均衡条件下での準最適模倣学習を容易にするために,政策性能のランク付けに使用される損失関数の要件を理論的に分析する。
  論文  参考訳（メタデータ） (2022-02-07T19:38:22Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• L2E: Learning to Exploit Your Opponent [66.66334543946672]
  本稿では,暗黙的対向モデリングのための新しい学習フレームワークを提案する。 L2Eは、トレーニング中に異なる相手との対話によって、相手を悪用する能力を取得する。 本稿では, 対戦相手を自動的に生成する新しい対戦相手戦略生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-18T14:27:59Z)
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning [10.515544361834241]
  最適無後悔学習戦略の一般クラスから得られる混合戦略の収束特性について検討する。 各ステップに設定された情報を相手の実演の実証平均とする戦略のクラスを考察する。
  論文  参考訳（メタデータ） (2020-12-03T18:02:40Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Deep Reinforcement Learning for FlipIt Security Game [2.0624765454705654]
  本稿では,エージェントが対戦者の異なるクラスに適応し,最適な対ストラテジーを学習する深層学習モデルについて述べる。 FlipItは、プレイヤー、攻撃者、ディフェンダーの双方が共有リソースの所有権を競う2人プレイのセキュリティゲームです。 我々のモデルは、Qラーニングと組み合わせたディープニューラルネットワークであり、リソースの所有時間の最大化のために訓練されている。
  論文  参考訳（メタデータ） (2020-02-28T18:26:24Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

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

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