論文の概要: 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のサンプル複雑性が状態-作用空間の大きさにどのようにスケールするかを検討する。
スケーリングに関する理論的結果は,マッチングペニー環境において実証的に支持される。
関連論文リスト
- 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) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - Parallel MCMC Without Embarrassing Failures [19.429985676081618]
MCMCはデータパーティションで定義された(サブ)後続体上で並列に実行される。
効率的ではあるが、このフレームワークは後部サンプリングの品質に非常に敏感である。
我々はこの問題を緩和するための新しい組み合わせ戦略を提案する。
論文 参考訳(メタデータ) (2022-02-22T20:17:46Z) - 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) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳(メタデータ) (2021-06-02T22:03:36Z) - 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) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳(メタデータ) (2020-12-04T15:36:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。