論文の概要: Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits

• arxiv url: http://arxiv.org/abs/2203.06803v1
• Date: Mon, 14 Mar 2022 01:23:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-15 13:02:57.661995
• Title: Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits
• Title（参考訳）: 対戦相手によるマルコフゲーム学習:効率的なアルゴリズムと基本限界
• Authors: Qinghua Liu, Yuanhao Wang, Chi Jin
• Abstract要約: ゼロサムゲームにおける理想的な戦略は、プレイヤーにナッシュ均衡の値に劣らず平均的な報酬を与えるだけでなく、最適でないとき(適応的な)相手を利用することである。 本研究は, マルコフゲームにおいて, 対戦相手が後見の最良の固定政策と競合する際の非回帰学習について研究する。
• 参考スコア（独自算出の注目度）: 37.573273877814906
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An ideal strategy in zero-sum games should not only grant the player an average reward no less than the value of Nash equilibrium, but also exploit the (adaptive) opponents when they are suboptimal. While most existing works in Markov games focus exclusively on the former objective, it remains open whether we can achieve both objectives simultaneously. To address this problem, this work studies no-regret learning in Markov games with adversarial opponents when competing against the best fixed policy in hindsight. Along this direction, we present a new complete set of positive and negative results: When the policies of the opponents are revealed at the end of each episode, we propose new efficient algorithms achieving $\sqrt{K}$-regret bounds when either (1) the baseline policy class is small or (2) the opponent's policy class is small. This is complemented with an exponential lower bound when neither conditions are true. When the policies of the opponents are not revealed, we prove a statistical hardness result even in the most favorable scenario when both above conditions are true. Our hardness result is much stronger than the existing hardness results which either only involve computational hardness, or require further restrictions on the algorithms.
• Abstract（参考訳）: ゼロサムゲームにおける理想的な戦略は、プレイヤーにナッシュ均衡の値に劣らず平均的な報酬を与えるだけでなく、最適でないとき(適応的な)相手を利用することである。 マルコフゲームにおける既存の作業の多くは、以前の目的にのみ焦点をあてているが、両方の目的を同時に達成できるかどうかは不明だ。 この問題に対処するため,本研究は,マルコフゲームにおいて,最善の固定政策と後見で競う際,敵の対戦相手と対局しない学習について研究する。 そこで,本研究では,各エピソードの終わりに相手の方針が明らかにされると,(1)基本方針クラスが小さく,(2)相手の方針クラスが小さい場合に,$\sqrt{k}$-regret境界を達成する新しい効率的なアルゴリズムを提案する。 これは、どちらの条件も真でないとき指数的下限で補う。 相手の方針が明らかになっていない場合、上記の条件が真である場合に最も有利なシナリオであっても統計的に硬度の結果が証明される。 我々の硬度結果は、計算硬度のみを含む既存の硬度結果よりもはるかに強いか、アルゴリズムにさらなる制限を必要とする。

関連論文リスト

• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
  マルチプレイヤーゲームにおける平衡は、一意でも爆発的でもない。 本稿では,平等な共有という自然な目的に焦点をあてることで,これらの課題に対処するための最初の一歩を踏み出す。 我々は、様々な設定でほぼ同じシェアを確実に得る、非回帰学習にインスパイアされた、一連の効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-06-06T15:59:17Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
  我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。 この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。 我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-08-03T16:41:01Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning [10.515544361834241]
  最適無後悔学習戦略の一般クラスから得られる混合戦略の収束特性について検討する。 各ステップに設定された情報を相手の実演の実証平均とする戦略のクラスを考察する。
  論文  参考訳（メタデータ） (2020-12-03T18:02:40Z)
• Efficient Competitive Self-Play Policy Optimization [20.023522000925094]
  対戦型ゼロサムゲームにおける対戦型自己演奏強化学習のための新しいアルゴリズムフレームワークを提案する。 本手法は,複数のエージェントを同時に訓練し,単純な対戦ルールに基づいて知的に互いに相手として取り合う。 我々は,このアルゴリズムが凸凹ゲームにおいて高い確率で近似平衡に収束することを理論的に証明する。
  論文  参考訳（メタデータ） (2020-09-13T21:01:38Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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