論文の概要: Provable Self-Play Algorithms for Competitive Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2002.04017v3
- Date: Thu, 9 Jul 2020 17:07:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 07:22:40.221133
- Title: Provable Self-Play Algorithms for Competitive Reinforcement Learning
- Title（参考訳）: 競合強化学習のための確率的セルフプレイアルゴリズム
- Authors: Yu Bai, Chi Jin
- Abstract要約: 我々はマルコフゲームの設定の下で、競争力強化学習における自己プレイについて研究する。
自己再生アルゴリズムは、ゲームのT$ステップをプレイした後、後悔の$tildemathcalO(sqrtT)$を達成する。
また, 最悪の場合においても, 時間内に実行可能であることを保証し, 若干悪い後悔を招き, エクスプロイトスタイルのアルゴリズムも導入する。
- 参考スコア（独自算出の注目度）: 48.12602400021397
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Self-play, where the algorithm learns by playing against itself without
requiring any direct supervision, has become the new weapon in modern
Reinforcement Learning (RL) for achieving superhuman performance in practice.
However, the majority of exisiting theory in reinforcement learning only
applies to the setting where the agent plays against a fixed environment; it
remains largely open whether self-play algorithms can be provably effective,
especially when it is necessary to manage the exploration/exploitation
tradeoff. We study self-play in competitive reinforcement learning under the
setting of Markov games, a generalization of Markov decision processes to the
two-player case. We introduce a self-play algorithm---Value Iteration with
Upper/Lower Confidence Bound (VI-ULCB)---and show that it achieves regret
$\tilde{\mathcal{O}}(\sqrt{T})$ after playing $T$ steps of the game, where the
regret is measured by the agent's performance against a \emph{fully
adversarial} opponent who can exploit the agent's strategy at \emph{any} step.
We also introduce an explore-then-exploit style algorithm, which achieves a
slightly worse regret of $\tilde{\mathcal{O}}(T^{2/3})$, but is guaranteed to
run in polynomial time even in the worst case. To the best of our knowledge,
our work presents the first line of provably sample-efficient self-play
algorithms for competitive reinforcement learning.
- Abstract（参考訳）: アルゴリズムが直接の監督なしに自分自身と対戦することで学習するセルフプレイは、実際に超人的なパフォーマンスを達成するための現代強化学習(rl)の新たな武器となった。
しかし、強化学習における解脱理論の大多数は、エージェントが一定の環境に対して作用する環境にのみ適用され、特に探索/探索のトレードオフを管理する必要がある場合には、自己再生アルゴリズムが有効であるかどうかについては、大半がオープンである。
マルコフ決定過程の一般化であるマルコフゲームの設定下で,競争強化学習における自己遊びについて検討した。
本稿では,上/下信頼境界(VI-ULCB)を用いた自己再生アルゴリズムを導入し,エージェントの戦略を活用できる「emph{fully adversarial}」相手に対して,エージェントのパフォーマンスを指標として,ゲーム中のT$ステップをプレイした後で,後悔する$\tilde{\mathcal{O}}(\sqrt{T})$を達成することを示す。
このアルゴリズムは$\tilde{\mathcal{O}}(T^{2/3})$をわずかに後悔するが、最悪の場合であっても多項式時間で実行することが保証されている。
我々の知識を最大限に活用するため、本研究は競争強化学習のためのサンプル効率の良い自己再生アルゴリズムの最初のラインを提示している。
関連論文リスト
- In-Context Exploiter for Extensive-Form Games [38.24471816329584]
In-Context Exploiter (ICE) という新しい手法を導入し、ゲーム内の任意のプレイヤーとして動作し、コンテキスト内学習によって完全に対戦相手を適応的に活用できる単一モデルを訓練する。
我々のICEアルゴリズムは、多様な相手戦略の生成、強化学習アルゴリズムによる対話的履歴データの収集、そしてよく設計されたカリキュラム学習フレームワークにおけるトランスフォーマーベースのエージェントの訓練を含む。
論文 参考訳（メタデータ） (2024-08-10T14:59:09Z) - Guarantees for Self-Play in Multiplayer Games via Polymatrix
Decomposability [2.2636685010313364]
セルフプレイ(Self-play)は、学習アルゴリズムが自分自身のコピーと対話して学習するマルチエージェントシステムにおける機械学習のテクニックである。
両プレイヤーの定数ゲームでは、ナッシュ均衡に達するセルフプレイが保証され、ポストトレーニング中の対戦相手に対して良好に機能する戦略が作成できることを示す。
本研究は,マルチプレイヤーゲームの構造的特性を初めて同定し,多種多様なセルフプレイアルゴリズムによって生成される戦略の性能保証を実現する。
論文 参考訳（メタデータ） (2023-10-17T18:33:21Z) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳（メタデータ） (2023-05-31T22:09:24Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳（メタデータ） (2022-01-30T06:10:04Z) - Efficient Competitive Self-Play Policy Optimization [20.023522000925094]
対戦型ゼロサムゲームにおける対戦型自己演奏強化学習のための新しいアルゴリズムフレームワークを提案する。
本手法は,複数のエージェントを同時に訓練し,単純な対戦ルールに基づいて知的に互いに相手として取り合う。
我々は,このアルゴリズムが凸凹ゲームにおいて高い確率で近似平衡に収束することを理論的に証明する。
論文 参考訳（メタデータ） (2020-09-13T21:01:38Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。
対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。
我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
論文 参考訳（メタデータ） (2020-07-10T09:33:05Z) - Efficient exploration of zero-sum stochastic games [83.28949556413717]
ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。
限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。
私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
論文 参考訳（メタデータ） (2020-02-24T20:30:38Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。