論文の概要: Analysing the Sample Complexity of Opponent Shaping

• arxiv url: http://arxiv.org/abs/2402.05782v1
• Date: Thu, 8 Feb 2024 16:17:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-09 14:14:12.682568
• Title: Analysing the Sample Complexity of Opponent Shaping
• Title（参考訳）: 対物形状のサンプル複雑度の解析
• Authors: Kitty Fung, Qizhen Zhang, Chris Lu, Jia Wan, Timon Willi, Jakob Foerster
• Abstract要約: 一般サムゲームでの学習は、しばしば集合的な準最適結果をもたらす。 初期の対戦型シェーピング(OS)法では、高階微分を用いてコプレイヤーの学習を形作る。 M-FOS(M-free Opponent Shaping)は、OSの問題をメタゲームとして再定義することで、これらの問題に対処する。
• 参考スコア（独自算出の注目度）: 15.226375898939205
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning in general-sum games often yields collectively sub-optimal results. Addressing this, opponent shaping (OS) methods actively guide the learning processes of other agents, empirically leading to improved individual and group performances in many settings. Early OS methods use higher-order derivatives to shape the learning of co-players, making them unsuitable for shaping multiple learning steps. Follow-up work, Model-free Opponent Shaping (M-FOS), addresses these by reframing the OS problem as a meta-game. In contrast to early OS methods, there is little theoretical understanding of the M-FOS framework. Providing theoretical guarantees for M-FOS is hard because A) there is little literature on theoretical sample complexity bounds for meta-reinforcement learning B) M-FOS operates in continuous state and action spaces, so theoretical analysis is challenging. In this work, we present R-FOS, a tabular version of M-FOS that is more suitable for theoretical analysis. R-FOS discretises the continuous meta-game MDP into a tabular MDP. Within this discretised MDP, we adapt the $R_{max}$ algorithm, most prominently used to derive PAC-bounds for MDPs, as the meta-learner in the R-FOS algorithm. We derive a sample complexity bound that is exponential in the cardinality of the inner state and action space and the number of agents. Our bound guarantees that, with high probability, the final policy learned by an R-FOS agent is close to the optimal policy, apart from a constant factor. Finally, we investigate how R-FOS's sample complexity scales in the size of state-action space. Our theoretical results on scaling are supported empirically in the Matching Pennies environment.
• Abstract（参考訳）: 一般サムゲームでの学習は、しばしば集合的な準最適結果をもたらす。 これに対応するために、対戦型シェーピング(OS)メソッドは、他のエージェントの学習プロセスを積極的にガイドし、多くの設定における個人およびグループのパフォーマンスを実証的に改善する。 初期のOSでは、高階微分を使ってコプレイヤーの学習を形作り、複数の学習ステップを形作るのに適さない。 フォローアップ作業、M-FOS(Model-free Opponent Shaping)は、OS問題をメタゲームとして再定義することでこれらに対処する。 初期のOSメソッドとは対照的に、M-FOSフレームワークに関する理論的理解はほとんどない。 A)メタ強化学習のための理論的なサンプル複雑性境界に関する文献はほとんどない(メタ強化学習B) M-FOSは連続状態と作用空間で動作するので、理論解析は困難である。 本稿では,理論解析に適したM-FOSの表形式であるR-FOSについて述べる。 R-FOS は連続メタゲーム MDP を表型 MDP に識別する。 この離散化MDPでは、R-FOSアルゴリズムのメタラーナーとして、MDPのPACバウンドを導出するために最も顕著な$R_{max}$アルゴリズムを適用する。 我々は、内部状態と作用空間の濃度とエージェントの数において指数関数的であるサンプル複雑性境界を導出する。 我々の限界は、高い確率で、R-FOSエージェントによって学習された最終ポリシーが、定数係数を除いて最適ポリシーに近いことを保証します。 最後に、R-FOSのサンプル複雑性が状態-作用空間の大きさにどのようにスケールするかを検討する。 スケーリングに関する理論的結果は,マッチングペニー環境において実証的に支持される。

関連論文リスト

• Deep Learning Algorithms for Mean Field Optimal Stopping in Finite Space and Discrete Time [3.350071725971209]
  本研究は, エージェント数が無限に近づくにつれて得られる平均場最適停止(MFOS)問題を考察する。 本研究では,2つの深層学習手法を提案する。一方は最適決定を学習するために全軌道をシミュレートし,他方は逆方向誘導でDPPを利用する。 空間次元最大300の6つの異なる問題に対する数値実験により,これらの手法の有効性を実証する。
  論文  参考訳（メタデータ） (2024-10-11T14:27:17Z)
• Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
  我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。 このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
  論文  参考訳（メタデータ） (2024-06-12T06:41:47Z)
• Learning Optimal Deterministic Policies with Stochastic Policy Gradients [62.81324245896716]
  政策勾配法(PG法)は連続強化学習(RL法)問題に対処する手法として成功している。 一般的には、収束(ハイパー)政治は、決定論的バージョンをデプロイするためにのみ学習される。 本稿では,サンプルの複雑性とデプロイされた決定論的ポリシのパフォーマンスのトレードオフを最適化するために,学習に使用する探索レベルの調整方法を示す。
  論文  参考訳（メタデータ） (2024-05-03T16:45:15Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  本研究は,情報指向サンプリング(IDS)の原理に基づくマルチエージェント強化学習(MARL)のための新しいアルゴリズムの設計と解析を行う。 エピソディックな2プレーヤゼロサムMGに対して、ナッシュ平衡を学習するための3つのサンプル効率アルゴリズムを提案する。 我々は、Reg-MAIDSをマルチプレイヤー汎用MGに拡張し、ナッシュ平衡または粗相関平衡をサンプル効率良く学習できることを証明する。
  論文  参考訳（メタデータ） (2024-04-30T06:48:56Z)
• Federated Empirical Risk Minimization via Second-Order Method [18.548661105227488]
  連合学習環境下での一般的な経験的リスク最小化問題を解決するためのインテリアポイント法(IPM)を提案する。 IPMの各イテレーションの通信複雑性は$tildeO(d3/2)$であり、$d$はデータセットの次元(つまり、多くの機能)である。
  論文  参考訳（メタデータ） (2023-05-27T14:23:14Z)
• A multilevel reinforcement learning framework for PDE based control [0.2538209532048867]
  強化学習(RL)は制御問題を解くための有望な方法である。 モデルフリーなRLアルゴリズムは、サンプル非効率であり、最適な制御ポリシーを学ぶために、数百万のサンプルを必要としない何千ものサンプルを必要とする。 本稿では,粗いスケールの離散化に対応するサブレベルモデルを活用することで,コストの低減を図るため,マルチレベルRLフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-10-15T23:52:48Z)
• Model-Free Opponent Shaping [1.433758865948252]
  汎用ゲームのためのM-FOS(Model-Free Opponent Shaping)を提案する。 M-FOSはメタゲームで学習し、各メタステップは根底にある「インナー」ゲームのエピソードである。 文学的な学習者や、より洗練されたアルゴリズムを駆使している。
  論文  参考訳（メタデータ） (2022-05-03T12:20:14Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。 我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。 コア最適化問題の実用的なパラメトリゼーションを提供する。
  論文  参考訳（メタデータ） (2021-07-08T18:01:02Z)
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning [56.17603785248675]
  モデルに依存しないメタラーニング (MAML) が人気のある研究分野となっている。 既存のMAMLアルゴリズムは、イテレーション毎にメタモデルを更新するためにいくつかのタスクとデータポイントをサンプリングすることで、エピソードのアイデアに依存している。 本稿では,MAMLのメモリベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T08:47:58Z)
• ConCrete MAP: Learning a Probabilistic Relaxation of Discrete Variables for Soft Estimation with Low Complexity [9.62543698736491]
  ConCrete MAP Detection (CMD)は、大きな逆線形問題に対する反復検出アルゴリズムである。 我々は、SotAと比較して、CMDが有望なパフォーマンス複雑性のトレードオフを特徴付けることを示す。 特に,CMDのソフト出力がデコーダに信頼性を持つことを示す。
  論文  参考訳（メタデータ） (2021-02-25T09:54:25Z)

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

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