論文の概要: Krylov-Bellman boosting: Super-linear policy evaluation in general state
spaces
- arxiv url: http://arxiv.org/abs/2210.11377v1
- Date: Thu, 20 Oct 2022 16:17:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 13:57:17.954504
- Title: Krylov-Bellman boosting: Super-linear policy evaluation in general state
spaces
- Title（参考訳）: Krylov-Bellman boosting: 一般状態空間における超線形政策評価
- Authors: Eric Xia and Martin J. Wainwright
- Abstract要約: 我々は、一般的な状態空間における政策評価のためのKrylov-Bellman Boosting (KBB)アルゴリズムを提示、解析する。
非パラメトリック回帰(ブースティングなど)を用いてベルマン残差を固定し、最小二乗時間差法(LSTD)により値関数を推定する。
- 参考スコア（独自算出の注目度）: 35.85474784972229
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present and analyze the Krylov-Bellman Boosting (KBB) algorithm for policy
evaluation in general state spaces. It alternates between fitting the Bellman
residual using non-parametric regression (as in boosting), and estimating the
value function via the least-squares temporal difference (LSTD) procedure
applied with a feature set that grows adaptively over time. By exploiting the
connection to Krylov methods, we equip this method with two attractive
guarantees. First, we provide a general convergence bound that allows for
separate estimation errors in residual fitting and LSTD computation. Consistent
with our numerical experiments, this bound shows that convergence rates depend
on the restricted spectral structure, and are typically super-linear. Second,
by combining this meta-result with sample-size dependent guarantees for
residual fitting and LSTD computation, we obtain concrete statistical
guarantees that depend on the sample size along with the complexity of the
function class used to fit the residuals. We illustrate the behavior of the KBB
algorithm for various types of policy evaluation problems, and typically find
large reductions in sample complexity relative to the standard approach of
fitted value iterationn.
- Abstract（参考訳）: 我々は、一般的な状態空間における政策評価のためのKrylov-Bellman Boosting (KBB)アルゴリズムを提示、解析する。
非パラメトリック回帰(ブースティングなど)を用いてベルマン残差を固定し、最小二乗時間差法(LSTD)を用いて値関数を時間とともに適応的に増加する特徴集合で推定する。
krylov法との接続を利用することで、この方法に2つの魅力的な保証を与える。
まず,残差フィット計算とlstd計算において,推定誤差を分離できる一般収束境界を提案する。
我々の数値実験と矛盾し、この境界は収束速度が制限されたスペクトル構造に依存し、典型的には超線形であることを示している。
第二に, このメタリサートと, 残留フィッティングとLSTD計算の信頼性を組み合わせ, 残留フィッティングに使用する関数クラスの複雑性とともに, 試料サイズに依存する具体的な統計的保証を得る。
各種政策評価問題に対するKBBアルゴリズムの挙動を概説し, 典型的には, 適合値反復の標準的なアプローチと比較して, サンプルの複雑さが大きく低下する。
関連論文リスト
- Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。
本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
論文 参考訳（メタデータ） (2023-10-22T12:37:25Z) - High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。
高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
論文 参考訳（メタデータ） (2023-05-30T12:58:39Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Statistical Optimality of Divide and Conquer Kernel-based Functional
Linear Regression [1.7227952883644062]
本稿では,対象関数が基礎となるカーネル空間に存在しないシナリオにおいて,分割・コンカレント推定器の収束性能について検討する。
分解に基づくスケーラブルなアプローチとして、関数線形回帰の分割・収束推定器は、時間とメモリにおけるアルゴリズムの複雑さを大幅に減らすことができる。
論文 参考訳（メタデータ） (2022-11-20T12:29:06Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳（メタデータ） (2021-12-24T17:21:04Z) - Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
論文 参考訳（メタデータ） (2021-12-07T07:47:37Z) - Robust Algorithms for GMM Estimation: A Finite Sample Viewpoint [30.839245814393724]
モーメントの一般化法(GMM)
我々はGMM推定器を開発し、一定の$ell$リカバリ保証を$O(sqrtepsilon)$で許容する。
我々のアルゴリズムと仮定は、機器変数の線形回帰とロジスティック回帰に適用できる。
論文 参考訳（メタデータ） (2021-10-06T21:06:22Z) - Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。
DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。
有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
論文 参考訳（メタデータ） (2021-02-23T18:56:13Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳（メタデータ） (2020-12-09T20:19:32Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。