論文の概要: Simple and optimal methods for stochastic variational inequalities, II:
Markovian noise and policy evaluation in reinforcement learning
- arxiv url: http://arxiv.org/abs/2011.08434v4
- Date: Fri, 13 Aug 2021 23:14:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-25 07:03:47.246432
- Title: Simple and optimal methods for stochastic variational inequalities, II:
Markovian noise and policy evaluation in reinforcement learning
- Title(参考訳): 確率的変分不等式に対する単純かつ最適手法 II:強化学習におけるマルコフ雑音と政策評価
- Authors: Georgios Kotsalis and Guanghui Lan and Tianjiao Li
- Abstract要約: 本稿ではマルコフ雑音下での変分不等式(VI)のリセットに着目する。
我々のアルゴリズム開発における顕著な応用は、強化学習における政策評価問題である。
- 参考スコア(独自算出の注目度): 9.359939442911127
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The focus of this paper is on stochastic variational inequalities (VI) under
Markovian noise. A prominent application of our algorithmic developments is the
stochastic policy evaluation problem in reinforcement learning. Prior
investigations in the literature focused on temporal difference (TD) learning
by employing nonsmooth finite time analysis motivated by stochastic subgradient
descent leading to certain limitations. These encompass the requirement of
analyzing a modified TD algorithm that involves projection to an a-priori
defined Euclidean ball, achieving a non-optimal convergence rate and no clear
way of deriving the beneficial effects of parallel implementation. Our approach
remedies these shortcomings in the broader context of stochastic VIs and in
particular when it comes to stochastic policy evaluation. We developed a
variety of simple TD learning type algorithms motivated by its original version
that maintain its simplicity, while offering distinct advantages from a
non-asymptotic analysis point of view. We first provide an improved analysis of
the standard TD algorithm that can benefit from parallel implementation. Then
we present versions of a conditional TD algorithm (CTD), that involves periodic
updates of the stochastic iterates, which reduce the bias and therefore exhibit
improved iteration complexity. This brings us to the fast TD (FTD) algorithm
which combines elements of CTD and the stochastic operator extrapolation method
of the companion paper. For a novel index resetting policy FTD exhibits the
best known convergence rate. We also devised a robust version of the algorithm
that is particularly suitable for discounting factors close to 1.
- Abstract(参考訳): 本稿ではマルコフ雑音下での確率的変動不等式(VI)に着目した。
アルゴリズム開発の顕著な応用は強化学習における確率的政策評価問題である。
論文の先行研究は,確率的劣次降下に動機づけられた非滑らかな有限時間解析を用いて時間差(td)学習に焦点をあてた。
これらは、a-プリオリ定義ユークリッド球への射影を含む修正されたtdアルゴリズムの解析の要件を包含し、非最適収束率を達成し、並列実装の有益な効果を導出する明確な方法がない。
我々のアプローチは、確率的vi、特に確率的政策評価の広い文脈において、これらの欠点を是正する。
我々は,その単純さを維持しつつ,非漸近的な解析的視点から見れば,様々な単純なTD学習型アルゴリズムを開発した。
まず、並列実装の利点を享受できる標準tdアルゴリズムのより良い解析を提供する。
そこで我々は,確率的反復の周期的更新を含む条件付きTDアルゴリズム(CTD)のバージョンを提案する。
これにより、CTDの要素と共用紙の確率演算子外挿法を組み合わせた高速TD(FTD)アルゴリズムが実現される。
新たなインデックスリセットポリシーでは、FTDが最もよく知られた収束率を示す。
また,アルゴリズムのロバスト版を考案し,約1。
関連論文リスト
- Finite Time Analysis of Temporal Difference Learning for Mean-Variance in a Discounted MDP [1.0923877073891446]
割引報酬マルコフ決定プロセスにおける分散政策評価の問題点を考察する。
本稿では,線形関数近似(LFA)を用いた時間差分型学習アルゴリズムについて述べる。
平均二乗の意味で(i) を保持する有限標本境界と、(ii) テールイテレート平均化を用いる場合の高い確率を導出する。
論文 参考訳(メタデータ) (2024-06-12T05:49:53Z) - The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise [17.493808856903303]
近似アルゴリズムを解析する根本的な課題は、その安定性を確立することである。
我々は、マルティンゲール差分雑音設定からマルコフ雑音設定へ有界な安定性に対するボルカール・メインの定理を拡張した。
論文 参考訳(メタデータ) (2024-01-15T17:20:17Z) - Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。
我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。
本実験は, 勾配法よりも近似分散還元法の利点を実証する。
論文 参考訳(メタデータ) (2023-08-18T05:11:50Z) - The Stochastic Proximal Distance Algorithm [5.3315823983402755]
本稿では,所望の制約付き推定問題をペナルティパラメータとして回復する反復最適化手法のクラスを提案し,解析する。
我々は、最近の理論装置を拡張して有限誤差境界を確立し、収束率の完全な評価を行う。
また,本手法が一般的な学習課題のバッチバージョンより優れていることを示す。
論文 参考訳(メタデータ) (2022-10-21T22:07:28Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳(メタデータ) (2021-09-13T18:10:52Z) - Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。
ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。
そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-08T00:43:04Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳(メタデータ) (2020-12-28T17:19:32Z) - Logistic Q-Learning [87.00813469969167]
MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。
提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
論文 参考訳(メタデータ) (2020-10-21T17:14:31Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Proximal Gradient Temporal Difference Learning: Stable Reinforcement
Learning with Polynomial Sample Complexity [40.73281056650241]
本稿では,真の勾配時間差学習アルゴリズムを設計・解析する原理的な方法として,近位勾配時間差学習を導入する。
本研究では, 従来の目的関数からではなく, 主目的関数から始めることによって, 勾配性TD強化学習法を公式に導出する方法を示す。
論文 参考訳(メタデータ) (2020-06-06T21:04:21Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳(メタデータ) (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。