論文の概要: Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2105.12540v1
• Date: Wed, 26 May 2021 13:35:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-27 17:57:45.137413
• Title: Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いたオフポリシー自然アクターの有限サンプル解析
• Authors: Zaiwei Chen, Sajad Khodadadian, Siva Theja Maguluri
• Abstract要約: 我々は,線形関数近似を用いた非政治的自然なアクター批判アルゴリズムの新たな変種を開発する。 我々は$mathcalO(epsilon-3)$のサンプル複雑性を確立し、そのようなアルゴリズムの既知収束境界を全て上回る。
• 参考スコア（独自算出の注目度）: 5.543220407902113
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we develop a novel variant of off-policy natural actor-critic algorithm with linear function approximation and we establish a sample complexity of $\mathcal{O}(\epsilon^{-3})$, outperforming all the previously known convergence bounds of such algorithms. In order to overcome the divergence due to deadly triad in off-policy policy evaluation under function approximation, we develop a critic that employs $n$-step TD-learning algorithm with a properly chosen $n$. We present finite-sample convergence bounds on this critic under both constant and diminishing step sizes, which are of independent interest. Furthermore, we develop a variant of natural policy gradient under function approximation, with an improved convergence rate of $\mathcal{O}(1/T)$ after $T$ iterations. Combining the finite sample error bounds of actor and the critic, we obtain the $\mathcal{O}(\epsilon^{-3})$ sample complexity. We derive our sample complexity bounds solely based on the assumption that the behavior policy sufficiently explores all the states and actions, which is a much lighter assumption compared to the related literature.
• Abstract（参考訳）: 本稿では,線形関数近似を用いた非政治的自然なアクター批判アルゴリズムの新たな変種を開発し,これらのアルゴリズムの既知収束バウンダリを全て上回る,$\mathcal{O}(\epsilon^{-3})$のサンプル複雑性を確立する。 関数近似に基づく政策評価における致命的な三分の一の相違を克服するために,n$-step td-learningアルゴリズムを適切に選択したn$を有する批判者を開発した。 我々は,この批判者に対して,独立興味を持つ定数および減少ステップサイズの下で有限個の収束境界を提示する。 さらに、関数近似の下で自然ポリシー勾配の変種を開発し、$T$反復後の$\mathcal{O}(1/T)$の収束率を改善した。 アクターと批評家の有限サンプルエラー境界を組み合わせると、$\mathcal{o}(\epsilon^{-3})$ のサンプル複雑性が得られる。 サンプルの複雑さの境界は、行動ポリシーがすべての状態とアクションを十分に探求しているという仮定に基づいており、これは関連する文献と比べてはるかに軽い仮定である。

関連論文リスト

• Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms [49.19842488693726]
  我々は,O(epsilon-3)$のサンプル複雑性を大幅に改善したアクター・クリティック・アルゴリズムのグローバル収束を確立した。 我々の発見は、一定のステップサイズに依存する多くのアルゴリズムに対する理論的支援を提供する。
  論文  参考訳（メタデータ） (2024-10-11T14:46:29Z)
• Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation [18.77565744533582]
  アクタークリティカル (AC) は、強化学習において最適な政策を学ぶための強力な方法である。 AC は $epsilon +varepsilon_textcritic$ 定常点の近傍に収束する。 本稿では,ACアルゴリズムとNACアルゴリズムのコンバージェンスを,相反する関数近似を用いて解析する。
  論文  参考訳（メタデータ） (2024-06-03T20:05:04Z)
• 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)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。 ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。 我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-27T11:23:57Z)
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction [28.548040329949387]
  状態-作用密度比の補正を施した非政治政策改善アルゴリズムの収束特性について検討する。 有限時間収束を保証する2つの戦略を提案する。 我々は,O-SPIMが総複雑性$O(epsilon-4)$の定常点に収束していることを証明する。
  論文  参考訳（メタデータ） (2021-06-02T07:26:29Z)
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm [4.932130498861987]
  重要度サンプリングに基づく自然アクタ-クリティック(nac)アルゴリズムのオフポリシー変種に対する有限サンプル収束保証を提供する。 このアルゴリズムは、ステップの適切な選択の下で$mathcalo(epsilon-3log2(1/epsilon)$のサンプル複雑性を持つ大域的最適ポリシーに収束する。
  論文  参考訳（メタデータ） (2021-02-18T13:22:59Z)
• Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
  平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。 ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。 そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-08T00:43:04Z)
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms [58.57004511121862]
  本稿では, マルコフサンプリングにおけるACおよびNACの収束速度とサンプリング複雑性を特徴付ける。 本稿では,ACとNACがPGおよびNPGに対して,批判の組み合わさりにより,無限の地平線下での順に性能改善を実現していることを示す。
  論文  参考訳（メタデータ） (2020-04-27T17:11:06Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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