論文の概要: A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games

• arxiv url: http://arxiv.org/abs/2303.09716v3
• Date: Thu, 12 Oct 2023 21:00:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-16 18:09:12.536112
• Title: A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games
• Title（参考訳）: ゼロサムマルコフゲームにおける強化学習のための新しいポリシー反復アルゴリズム
• Authors: Anna Winnicki, R. Srikant
• Abstract要約: ゲームに対するナイーブなポリシー反復の単純な変種が収束し、指数関数的に速く収束することを示す。 政策反復を示唆するために提案する唯一の追加は、政策改善フェーズにおけるルックアヘッドの使用です。
• 参考スコア（独自算出の注目度）: 10.805520579293747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal policies in standard MDPs can be obtained using either value iteration or policy iteration. However, in the case of zero-sum Markov games, there is no efficient policy iteration algorithm; e.g., it has been shown in (Hansen et al., 2013) that one has to solve Omega(1/(1-alpha)) MDPs, where alpha is the discount factor, to implement the only known convergent version of policy iteration. Another algorithm for Markov zero-sum games, called naive policy iteration, is easy to implement but is only provably convergent under very restrictive assumptions. Prior attempts to fix naive policy iteration algorithm have several limitations. Here, we show that a simple variant of naive policy iteration for games converges, and converges exponentially fast. The only addition we propose to naive policy iteration is the use of lookahead in the policy improvement phase. This is appealing because lookahead is anyway used in practical learning algorithms for games. We further show that lookahead can be implemented efficiently in linear Markov games, which are the counterpart of the much-studied linear MDPs. We illustrate the application of our new policy iteration algorithm by providing sample and time complexity bounds for policy-based RL (reinforcement learning) algorithms.
• Abstract（参考訳）: 標準のMDPにおける最適ポリシーは、値反復またはポリシー反復のいずれかを使って得ることができる。 しかし、ゼロサムマルコフゲームの場合、効率的なポリシー反復アルゴリズムは存在せず、例えば(hansen et al., 2013)、alphaが割引要因であるomega(1/(1-alpha)) mdpsを解き、唯一知られているポリシー反復の収束バージョンを実装する必要があることが示されている。 マルコフゼロサムゲームのための別のアルゴリズムはナイーブ・ポリシー・イテレーション(naive policy iteration)と呼ばれ、実装が容易であるが、非常に制限された仮定の下でのみ確実に収束する。 単純ポリシー反復アルゴリズムの修正の試みにはいくつかの制限がある。 ここでは,ゲームに対するナイーブなポリシー反復の簡単な変形が収束し,指数関数的に速く収束することを示す。 政策反復を示唆する唯一の追加は、政策改善フェーズにおけるルックアヘッドの使用です。 lookaheadはゲームのための実用的な学習アルゴリズムで使われているので、これは魅力的です。 さらに,よく研究されている線形mdpに対応する線形マルコフゲームにおいて,lookaheadを効率的に実装できることを示した。 本稿では,ポリシーベースrl(reinforcement learning)アルゴリズムのサンプルおよび時間複雑性境界を提供することにより,新しいポリシー反復アルゴリズムの適用例を示す。

関連論文リスト

• COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences [31.988100672680154]
  本稿では,言語モデルアライメントのためのメタアルゴリズムである Convergent Meta Alignment Algorithm (COMAL) を提案する。 我々のメタアルゴリズムは単純であり、RLHFと優先最適化のために設計された多くの既存手法と統合することができる。
  論文  参考訳（メタデータ） (2024-10-30T17:13:02Z)
• Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization [37.24692425018]
  Emphconstrained MDPs(CMDPs)におけるオンライン学習の研究 提案アルゴリズムは, 対向型MDPに対して, 最先端のポリシー最適化アプローチを採用するプリミティブ・デュアル・スキームを実装している。
  論文  参考訳（メタデータ） (2024-10-03T07:54:04Z)
• Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration [13.166738075816493]
  規則化されたポリシー反復は、強い凸関数を持つベルマン方程式を滑らかにする条件において、標準ニュートン・ラフソン法と厳密に等価であることを示す。 正規化政策反復が大域的線形収束を持ち、そのレートが$gamma$ (discount factor)であることを証明する。 また、正規化ポリシー反復の修正版、すなわち有限ステップのポリシー評価はニュートン法と等価であり、ニュートンの反復式はトランカットされた反復で解かれることを示す。
  論文  参考訳（メタデータ） (2023-10-11T05:55:20Z)
• Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling [23.989009116398208]
  一般非線形関数近似を用いた低スイッチングサンプリング効率ポリシ最適化アルゴリズム LPO を設計する。 提案アルゴリズムは,$widetildeO(fractextpoly(d)varepsilon3)$サンプルのみを用いて,$varepsilon$-optimal Policyを得る。
  論文  参考訳（メタデータ） (2023-06-15T23:51:46Z)
• Iteratively Refined Behavior Regularization for Offline Reinforcement Learning [57.10922880400715]
  本稿では,保守的政策反復に基づく行動規則化を大幅に強化する新しいアルゴリズムを提案する。 行動規則化に使用される基準ポリシーを反復的に洗練することにより、保守的な政策更新は徐々に改善される。 D4RLベンチマークの実験結果から,本手法は従来のタスクのベースラインよりも優れていたことが示唆された。
  論文  参考訳（メタデータ） (2023-06-09T07:46:24Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning [85.50033812217254]
  アクター批判法はオフラインの強化学習に広く用いられているが、理論的にはそれほどよく理解されていない。 ペシミズムの原理を自然に取り入れた新しいオフラインアクター批判アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-08-19T17:27:29Z)
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration [22.621710838468097]
  無限ホライゾンマルコフ決定過程(mdps)における学習アルゴリズムを関数近似を用いて検討する。 まず、ほぼ同一の仮定の下で、Politexアルゴリズムの後悔解析を$O(T3/4)$から$O(sqrtT)$にシャープできることを示す。 その結果、計算効率の良いアルゴリズムに対して、最初の高い確率の$o(sqrtt)$ regretバウンドが得られる。
  論文  参考訳（メタデータ） (2021-02-25T00:55:07Z)
• Optimization Issues in KL-Constrained Approximate Policy Iteration [48.24321346619156]
  多くの強化学習アルゴリズムは、近似ポリシー反復(API)のバージョンと見なすことができる。 標準APIはしばしば動作が悪いが、KL-divergenceによる各ポリシー更新を以前のポリシーに正規化することで学習が安定化できることが示されている。 TRPO、MPO、VMPOなどの一般的な実用的なアルゴリズムは、連続ポリシーのKL分割に関する制約によって正規化を置き換える。
  論文  参考訳（メタデータ） (2021-02-11T19:35:33Z)
• Variance Penalized On-Policy and Off-Policy Actor-Critic [60.06593931848165]
  本稿では,平均値と変動値の両方を含むパフォーマンス基準を最適化する,オン・ポリティィおよびオフ・ポリティィ・アクター・クリティカルなアルゴリズムを提案する。 提案手法は, アクタ批判的かつ事前の分散-ペナライゼーションベースラインに匹敵するだけでなく, リターンのばらつきが低いトラジェクトリも生成する。
  論文  参考訳（メタデータ） (2021-02-03T10:06:16Z)
• Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
  平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。 ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。 そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-08T00:43:04Z)

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

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