論文の概要: Sample Complexity of Policy-Based Methods under Off-Policy Sampling and
Linear Function Approximation
- arxiv url: http://arxiv.org/abs/2208.03247v1
- Date: Fri, 5 Aug 2022 15:59:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-08 13:00:48.605513
- Title: Sample Complexity of Policy-Based Methods under Off-Policy Sampling and
Linear Function Approximation
- Title（参考訳）: オフポリティサンプリングと線形関数近似による政策ベース手法のサンプル複雑性
- Authors: Zaiwei Chen, and Siva Theja Maguluri
- Abstract要約: 政策評価には、オフ政治サンプリングと線形関数近似を用いる。
自然政策勾配(NPG)を含む様々な政策更新規則が政策更新のために検討されている。
我々は、最適なポリシーを見つけるために、合計$mathcalO(epsilon-2)$サンプルの複雑さを初めて確立する。
- 参考スコア（独自算出の注目度）: 8.465228064780748
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we study policy-based methods for solving the reinforcement
learning problem, where off-policy sampling and linear function approximation
are employed for policy evaluation, and various policy update rules, including
natural policy gradient (NPG), are considered for policy update. To solve the
policy evaluation sub-problem in the presence of the deadly triad, we propose a
generic algorithm framework of multi-step TD-learning with generalized
importance sampling ratios, which includes two specific algorithms: the
$\lambda$-averaged $Q$-trace and the two-sided $Q$-trace. The generic algorithm
is single time-scale, has provable finite-sample guarantees, and overcomes the
high variance issue in off-policy learning.
As for the policy update, we provide a universal analysis using only the
contraction property and the monotonicity property of the Bellman operator to
establish the geometric convergence under various policy update rules.
Importantly, by viewing NPG as an approximate way of implementing policy
iteration, we establish the geometric convergence of NPG without introducing
regularization, and without using mirror descent type of analysis as in
existing literature. Combining the geometric convergence of the policy update
with the finite-sample analysis of the policy evaluation, we establish for the
first time an overall $\mathcal{O}(\epsilon^{-2})$ sample complexity for
finding an optimal policy (up to a function approximation error) using
policy-based methods under off-policy sampling and linear function
approximation.
- Abstract（参考訳）: 本研究では,政策評価にオフ・ポリシーサンプリングと線形関数近似を用い,政策更新に自然政策勾配(npg)を含む様々な政策更新ルールを検討する,強化学習問題を解決するための政策ベース手法について検討する。
致命的な三重項の存在下での政策評価のサブプロブレムを解決するために,多段階TD-ラーニングの一般的なアルゴリズムフレームワークを提案し,このフレームワークには,2つの特定のアルゴリズム:$\lambda$-averaged $Q$-traceと2つの側面の$Q$-traceが含まれる。
ジェネリックアルゴリズムは単一の時間スケールであり、証明可能な有限サンプル保証を持ち、オフポリシー学習における高い分散問題を克服する。
方針更新については,様々な方針更新規則の下で幾何学収束を確立するために,ベルマン作用素の縮約特性と単調性のみを用いた普遍的な解析を行う。
重要な点は,npgを政策反復を近似的に実施する方法として捉えることで,正規化を導入することなく,また既存の文献のようにミラー降下分析を使わずに,npgの幾何学的収束を確立することである。
政策更新の幾何収束と、政策評価の有限サンプル解析を組み合わせることで、オフポリケーションサンプリングおよび線形関数近似の下でポリシーに基づく手法を用いて最適な政策(関数近似誤差まで)を求めるために、全体の$\mathcal{O}(\epsilon^{-2})$サンプル複雑性を初めて確立する。
関連論文リスト
- Fast Policy Learning for Linear Quadratic Control with Entropy
Regularization [10.771650397337366]
本稿では,レギュラー化政策勾配 (RPG) と反復政策最適化 (IPO) の2つの新しい政策学習手法を提案し,分析する。
正確な政策評価にアクセスできると仮定すると、どちらの手法も正規化されたLQCの最適ポリシーを見つける際に線形に収束することが証明される。
論文 参考訳（メタデータ） (2023-11-23T19:08:39Z) - Last-Iterate Convergent Policy Gradient Primal-Dual Methods for
Constrained MDPs [107.28031292946774]
無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。
我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。
我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
論文 参考訳（メタデータ） (2023-06-20T17:27:31Z) - High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。
高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
論文 参考訳（メタデータ） (2023-05-30T12:58:39Z) - Local Optimization Achieves Global Optimality in Multi-Agent
Reinforcement Learning [139.53668999720605]
本稿では,各エージェントのローカルポリシーをバニラPPOと同様に更新するマルチエージェントPPOアルゴリズムを提案する。
マルコフゲームにおける標準正則条件と問題依存量により、我々のアルゴリズムはサブリニアレートで大域的最適ポリシーに収束することを示す。
論文 参考訳（メタデータ） (2023-05-08T16:20:03Z) - On The Convergence Of Policy Iteration-Based Reinforcement Learning With
Monte Carlo Policy Evaluation [11.345796608258434]
このような政策反復スキームの最初の訪問バージョンは、政策改善ステップがルックアヘッドを使用する場合、最適方針に収束することを示す。
また,関数近似設定の拡張を行い,アルゴリズムが関数近似誤差内の最適ポリシに近く動作することを示す。
論文 参考訳（メタデータ） (2023-01-23T20:32:41Z) - Linear Convergence of Natural Policy Gradient Methods with Log-Linear
Policies [115.86431674214282]
我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。
両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
論文 参考訳（メタデータ） (2022-10-04T06:17:52Z) - Bregman Gradient Policy Optimization [97.73041344738117]
本稿では,Bregmanの発散と運動量に基づく強化学習のためのBregmanグラデーションポリシーの最適化を設計する。
VR-BGPOは、各イテレーションで1つの軌道のみを必要とする$epsilon$stationaryポイントを見つけるために、$tilde(epsilon-3)$で最高の複雑性に達する。
論文 参考訳（メタデータ） (2021-06-23T01:08:54Z) - On the Convergence and Sample Efficiency of Variance-Reduced Policy
Gradient Method [38.34416337932712]
政策は、例えばREINFORCEのようなリッチな強化学習(RL)手法を生み出します。
しかし、そのようなメソッドが$epsilon$-optimal Policyを見つけるための最もよく知られたサンプルの複雑さは$mathcalO(epsilon-3)$である。
第一次政策最適化法の基本収束特性とサンプル効率について検討する。
論文 参考訳（メタデータ） (2021-02-17T07:06:19Z) - Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。
ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。
そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-08T00:43:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。