論文の概要: Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions

• arxiv url: http://arxiv.org/abs/2207.12463v1
• Date: Mon, 25 Jul 2022 18:29:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-27 12:23:23.463788
• Title: Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions
• Title（参考訳）: 構造化遷移を伴うゼロサムマルコフゲームにおける架空のプレイポリシー最適化
• Authors: Shuang Qiu, Xiaohan Wei, Jieping Ye, Zhaoran Wang, Zhuoran Yang
• Abstract要約: 本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
• 参考スコア（独自算出の注目度）: 145.54544979467872
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While single-agent policy optimization in a fixed environment has attracted a lot of research attention recently in the reinforcement learning community, much less is known theoretically when there are multiple agents playing in a potentially competitive environment. We take steps forward by proposing and analyzing new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We consider two classes of transition structures: factored independent transition and single-controller transition. For both scenarios, we prove tight $\widetilde{\mathcal{O}}(\sqrt{K})$ regret bounds after $K$ episodes in a two-agent competitive game scenario. The regret of each agent is measured against a potentially adversarial opponent who can choose a single best policy in hindsight after observing the full policy sequence. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization in a non-stationary environment. When both players adopt the proposed algorithms, their overall optimality gap is $\widetilde{\mathcal{O}}(\sqrt{K})$.
• Abstract（参考訳）: 固定環境での単一エージェントのポリシー最適化は、最近強化学習コミュニティで多くの研究の注目を集めているが、複数のエージェントが潜在的に競争的な環境で遊んでいる場合、理論的にはあまり知られていない。 我々は、構造化されているが未知の遷移を持つゼロサムマルコフゲームに対して、新しい架空のプレイポリシー最適化アルゴリズムを提案し、分析する。 遷移構造の2つのクラスを考える:因子付き独立遷移と単一コントローラ遷移。 どちらのシナリオでも、2エージェントの競争ゲームシナリオで$k$のエピソードの後、厳密な$\widetilde{\mathcal{o}}(\sqrt{k})$ regret boundsを証明します。 各エージェントの後悔は、すべてのポリシーシーケンスを観察した後、後から1つの最善のポリシーを選択できる敵に対して測定される。 本アルゴリズムは,非定常環境における同時ポリシー最適化の範囲内で,アッパー信頼境界(UCB)型楽観主義と架空の遊びの組み合わせを特徴とする。 両プレイヤーが提案したアルゴリズムを採用すると、それらの全体的な最適性ギャップは$\widetilde{\mathcal{o}}(\sqrt{k})$となる。

関連論文リスト

• Multi-Step Alignment as Markov Games: An Optimistic Online Gradient Descent Approach with Convergence Guarantees [91.88803125231189]
  マルチステップ優先最適化(MPO)は、自然なアクター批判フレームワークciteprakhlin2013online,joulani17a上に構築されている。 我々はOMPOが$mathcalO(epsilon-1)$ポリシー更新を必要とし、$epsilon$-approximate Nash平衡に収束することを示した。 また,本手法がマルチターン会話データセットと数理推論データセットに与える影響についても検証した。
  論文  参考訳（メタデータ） (2025-02-18T09:33:48Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Scalable and Independent Learning of Nash Equilibrium Policies in $n$-Player Stochastic Games with Unknown Independent Chains [1.0878040851638]
  独立な連鎖と未知の遷移行列を持つゲームについて研究する。 このクラスのゲームでは、プレイヤーは他のプレイヤーの状態や行動に依存しない内部マルコフ連鎖を制御する。 我々は、$epsilon$-NEポリシーを学ぶために、完全に分散化されたミラー降下アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-04T03:04:09Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games [95.10091348976779]
  我々はマルコフゲームにおいて、非定常的でおそらく敵対的な相手と遊べる単一のエージェントを制御する分散ポリシー学習について研究する。 我々は、新しいアルゴリズム、アンダーラインデ集中型アンダーラインハイプラインRpolicy munderlineIrror deunderlineScent (DORIS)を提案する。 DORISは、一般的な関数近似の文脈で$sqrtK$-regretを達成する。
  論文  参考訳（メタデータ） (2022-06-03T14:18:05Z)
• Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
  状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。 我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。 我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
  論文  参考訳（メタデータ） (2022-02-08T20:09:47Z)
• 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)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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