論文の概要: Minimax Sample Complexity for Turn-based Stochastic Game

• arxiv url: http://arxiv.org/abs/2011.14267v1
• Date: Sun, 29 Nov 2020 03:58:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-07 09:06:02.788001
• Title: Minimax Sample Complexity for Turn-based Stochastic Game
• Title（参考訳）: ターン型確率ゲームにおけるミニマックスサンプル複雑さ
• Authors: Qiwen Cui and Lin F. Yang
• Abstract要約: 我々は,おそらく最も自然な強化学習アルゴリズムであるプラグインソルバ手法が,ターンベースゲーム(TBSG)のミニマックスサンプル複雑性を実現することを証明した。 実験的なナッシュ均衡戦略は,真のTBSGにおけるナッシュ均衡戦略に近いものであることを示す。
• 参考スコア（独自算出の注目度）: 29.72243362029223
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The empirical success of Multi-agent reinforcement learning is encouraging, while few theoretical guarantees have been revealed. In this work, we prove that the plug-in solver approach, probably the most natural reinforcement learning algorithm, achieves minimax sample complexity for turn-based stochastic game (TBSG). Specifically, we plan in an empirical TBSG by utilizing a `simulator' that allows sampling from arbitrary state-action pair. We show that the empirical Nash equilibrium strategy is an approximate Nash equilibrium strategy in the true TBSG and give both problem-dependent and problem-independent bound. We develop absorbing TBSG and reward perturbation techniques to tackle the complex statistical dependence. The key idea is artificially introducing a suboptimality gap in TBSG and then the Nash equilibrium strategy lies in a finite set.
• Abstract（参考訳）: マルチエージェント強化学習の実証的な成功は奨励されているが、理論的な保証はほとんど明らかにされていない。 本研究では,おそらく最も自然な強化学習アルゴリズムであるプラグインソルバ手法が,ターンベース確率ゲーム(TBSG)の最小値サンプル複雑性を実現することを証明する。 具体的には、任意の状態-作用対からのサンプリングが可能な「シミュレータ」を利用して、実証的なTBSGを計画する。 実験的なナッシュ均衡戦略は、真のTBSGにおける近似ナッシュ均衡戦略であり、問題依存的および問題非依存的境界を与えることを示す。 複雑な統計依存性に取り組むために,吸収性tbsgと報酬摂動法を開発した。 鍵となる考え方は、人工的にTBSGに準最適ギャップを導入し、ナッシュ均衡戦略は有限集合にある。

関連論文リスト

• Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning [20.491176017183044]
  本稿では多目的強化学習(MORL)問題に取り組む。 MOACと呼ばれる革新的なアクター批判アルゴリズムを導入し、競合する報酬信号間のトレードオフを反復的に行うことでポリシーを見出す。
  論文  参考訳（メタデータ） (2024-05-05T23:52:57Z)
• Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL [57.745700271150454]
  モデルに基づく関数近似を用いた平均フィールドゲーム(MFG)における強化学習のサンプル複雑性について検討した。 本稿では、モデルクラスの複雑性を特徴付けるためのより効果的な概念である部分モデルベースエルダー次元(P-MBED)を紹介する。
  論文  参考訳（メタデータ） (2024-02-08T14:54:47Z)
• Scalable Learning of Intrusion Responses through Recursive Decomposition [0.0]
  本稿では,ITインフラへの自動侵入応答と,攻撃者と防御者との相互作用を部分的に観察されたゲームとして検討する。 この問題を解決するために、我々は、強化学習と均衡に向けた自己プレイを通じて、攻撃戦略と防衛戦略が共進化するアプローチに従う。 近似により平衡を学習するDFSP(Decompositional Fictitious Self-Play)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-06T18:12:07Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Nash Equilibria and Pitfalls of Adversarial Training in Adversarial Robustness Games [51.90475640044073]
  本研究では,2プレイヤゼロサムゲームにおける最適応答戦略の交互化として,対戦訓練について検討する。 一方、ゲームのユニークな純粋なナッシュ均衡が存在し、確実に堅牢である。
  論文  参考訳（メタデータ） (2022-10-23T03:21:01Z)
• Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
  ゲームにおける学習は、多エージェント強化学習(MARL)における最も標準的で基本的な設定であることは間違いない。 汎用近似ゲーム(SG)の重要なクラスにおいて、完全分散Q-ラーニングアルゴリズムの有限サンプル複雑性を確立する。 我々は,各エージェントが報酬や他のエージェントの行動を観察できないような,完全に分散化されたMARLの実践的かつ挑戦的な設定に焦点をあてる。
  論文  参考訳（メタデータ） (2021-12-15T03:33:39Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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