論文の概要: Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
- arxiv url: http://arxiv.org/abs/2003.07337v1
- Date: Mon, 16 Mar 2020 17:15:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-23 02:55:11.053030
- Title: Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
- Title（参考訳）: 時間差学習は最適か?
インスタンス依存分析
- Authors: Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J. Wainwright,
Michael I. Jordan
- Abstract要約: 我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
- 参考スコア（独自算出の注目度）: 102.29671176698373
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of policy evaluation in discounted Markov decision
processes, and provide instance-dependent guarantees on the $\ell_\infty$-error
under a generative model. We establish both asymptotic and non-asymptotic
versions of local minimax lower bounds for policy evaluation, thereby providing
an instance-dependent baseline by which to compare algorithms. Theory-inspired
simulations show that the widely-used temporal difference (TD) algorithm is
strictly suboptimal when evaluated in a non-asymptotic setting, even when
combined with Polyak-Ruppert iterate averaging. We remedy this issue by
introducing and analyzing variance-reduced forms of stochastic approximation,
showing that they achieve non-asymptotic, instance-dependent optimality up to
logarithmic factors.
- Abstract（参考訳）: 割引マルコフ決定過程における政策評価の問題に対処し、生成モデルの下での$\ell_\infty$-errorのインスタンス依存保証を提供する。
我々は,局所的minimax下限の漸近的および非漸近的バージョンを政策評価のために確立し,アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
理論に着想を得たシミュレーションでは、ポリアック・ラッパート・イテレート平均化と組み合わせても、非漸近条件で評価した場合、広範に使用される時間差(TD)アルゴリズムが厳密に最適であることが示された。
確率近似の分散還元形式を導入,解析することによりこの問題を解決し,非漸近的,インスタンス依存的最適性を対数的因子まで達成することを示した。
関連論文リスト
- Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。
本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
論文 参考訳（メタデータ） (2023-10-22T12:37:25Z) - Instance-Optimality in Interactive Decision Making: Toward a
Non-Asymptotic Theory [30.061707627742766]
適応性の強い概念であるインスタンス最適化を目指しており、どの問題の場合であっても、検討中のアルゴリズムは全ての一貫したアルゴリズムより優れていると主張する。
本稿では,一般関数近似を用いたインスタンス最適決定の非漸近的理論の開発に向けて第一歩を踏み出す。
論文 参考訳（メタデータ） (2023-04-24T21:51:58Z) - Off-Policy Evaluation with Policy-Dependent Optimization Response [90.28758112893054]
我々は,テキスト政治に依存した線形最適化応答を用いた非政治評価のための新しいフレームワークを開発した。
摂動法による政策依存推定のための非バイアス推定器を構築する。
因果介入を最適化するための一般的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-25T20:25:37Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳（メタデータ） (2021-12-24T17:21:04Z) - Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
政治政策の最適化は強化学習において難しい問題である。
オフポリシーアルゴリズムはメモリ効率が高く、オフポリシーサンプルから学ぶことができる。
論文 参考訳（メタデータ） (2020-09-14T16:22:46Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。