論文の概要: 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 Analysis of Natural Policy Gradient Algorithm
with General Parameterization for Infinite Horizon Discounted Reward Markov
Decision Processes [41.61653528766776]
本稿では, 自然政策勾配を求めるために, 加速勾配降下過程を利用する自然促進政策勾配(PGAN)アルゴリズムを提案する。
繰り返しは$mathcalO(epsilon-2)$サンプル複雑性と$mathcalO(epsilon-1)$複雑さを達成する。
Hessian-free および IS-free アルゴリズムのクラスでは、ANPG は $mathcalO(epsilon-frac12)$ の係数で最もよく知られたサンプルの複雑さを破り、それらの状態と同時に一致する。
論文 参考訳(メタデータ) (2023-10-18T03:00:15Z) - 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) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - 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 for Two Time-scale Non-linear TDC with General
Smooth Function Approximation [27.149240954363496]
我々は,一般のオフ・ポリシー設定にバインドされた有限サンプル誤差を明示的に特徴付ける新しい手法を開発した。
本手法は,一般的なスムーズな関数近似を用いた広範囲なT型学習アルゴリズムに適用できる。
論文 参考訳(メタデータ) (2021-04-07T00:34:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。