論文の概要: Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman
Operators
- arxiv url: http://arxiv.org/abs/2106.12729v1
- Date: Thu, 24 Jun 2021 02:22:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-26 06:36:00.605814
- Title: Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman
Operators
- Title(参考訳): 一般化ベルマン演算子によるオフポリシィTD学習の有限サンプル解析
- Authors: Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan
Shanmugam
- Abstract要約: 一般のオフポリチックなTD様近似アルゴリズムに対して有限サンプル境界を導出する。
Qpi(lambda)$, Tree-Backup$(lambda)$, Retrace$(lambda)$に対して最初の既知の有限サンプル保証を提供します。
- 参考スコア(独自算出の注目度): 37.65565099740316
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In temporal difference (TD) learning, off-policy sampling is known to be more
practical than on-policy sampling, and by decoupling learning from data
collection, it enables data reuse. It is known that policy evaluation
(including multi-step off-policy importance sampling) has the interpretation of
solving a generalized Bellman equation. In this paper, we derive finite-sample
bounds for any general off-policy TD-like stochastic approximation algorithm
that solves for the fixed-point of this generalized Bellman operator. Our key
step is to show that the generalized Bellman operator is simultaneously a
contraction mapping with respect to a weighted $\ell_p$-norm for each $p$ in
$[1,\infty)$, with a common contraction factor.
Off-policy TD-learning is known to suffer from high variance due to the
product of importance sampling ratios. A number of algorithms (e.g.
$Q^\pi(\lambda)$, Tree-Backup$(\lambda)$, Retrace$(\lambda)$, and $Q$-trace)
have been proposed in the literature to address this issue. Our results
immediately imply finite-sample bounds of these algorithms. In particular, we
provide first-known finite-sample guarantees for $Q^\pi(\lambda)$,
Tree-Backup$(\lambda)$, and Retrace$(\lambda)$, and improve the best known
bounds of $Q$-trace in [19]. Moreover, we show the bias-variance trade-offs in
each of these algorithms.
- Abstract(参考訳): 時間差学習(td)では、オフポリシーサンプリングはオンポリシーサンプリングよりも実用的であることが知られており、データ収集から学習を分離することで、データの再利用が可能になる。
政策評価(多段階オフ・ポリティカル重要度サンプリングを含む)は、一般化されたベルマン方程式を解く解釈を持つことが知られている。
本稿では、この一般化されたベルマン作用素の固定点を解く一般のオフポリティTD型確率近似アルゴリズムに対して有限サンプル境界を導出する。
我々の重要なステップは、一般化されたベルマン作用素が、共通の縮約係数を持つ各$p$ in $[1,\infty)$に対する重み付き$\ell_p$-normに対して同時に縮約写像であることを示すことである。
オフポリシーtd学習は、重要サンプリング率の積による高いばらつきに苦しむことが知られている。
いくつかのアルゴリズム(例)
この問題に対処するために、$Q^\pi(\lambda)$, Tree-Backup$(\lambda)$, Retrace$(\lambda)$, $Q$-trace)が文献で提案されている。
我々の結果は、これらのアルゴリズムの有限サンプル境界を直ちに示唆する。
特に、Q^\pi(\lambda)$, Tree-Backup$(\lambda)$, Retrace$(\lambda)$に対して、最初の既知の有限サンプル保証を提供し、[19]において最もよく知られた境界である$Q$-traceを改善する。
さらに,これらのアルゴリズムのバイアス分散トレードオフを示す。
関連論文リスト
- Iterated $Q$-Network: Beyond the One-Step Bellman Operator [20.870276787316314]
我々は、$Q$-関数近似のシーケンスを学習する新しいアプローチである、$Q$-Networks (iQN) を反復的に導入する。
iQNがバリューベースおよびアクタークリティカルメソッドでシームレスに利用できるかを示す。
論文 参考訳(メタデータ) (2024-03-04T15:07:33Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-28T08:25:26Z) - Black-Box Generalization [31.80268332522017]
微分一般化によるブラックボックス学習のための最初の誤り解析を行う。
どちらの一般化も独立$d$,$K$であり、適切な選択の下では学習率がわずかに低下していることを示す。
論文 参考訳(メタデータ) (2022-02-14T17:14:48Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳(メタデータ) (2021-06-29T12:49:54Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳(メタデータ) (2021-06-15T02:23:07Z) - Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm [4.932130498861987]
重要度サンプリングに基づく自然アクタ-クリティック(nac)アルゴリズムのオフポリシー変種に対する有限サンプル収束保証を提供する。
このアルゴリズムは、ステップの適切な選択の下で$mathcalo(epsilon-3log2(1/epsilon)$のサンプル複雑性を持つ大域的最適ポリシーに収束する。
論文 参考訳(メタデータ) (2021-02-18T13:22:59Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳(メタデータ) (2020-11-11T17:48:00Z) - An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic
Gradient Descent and Thompson Sampling [83.48992319018147]
プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。
この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。
本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。
過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
論文 参考訳(メタデータ) (2020-06-07T01:12:39Z) - Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。
我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
論文 参考訳(メタデータ) (2020-02-29T02:02:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。