論文の概要: 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を改善する。
さらに,これらのアルゴリズムのバイアス分散トレードオフを示す。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [39.468324211376505]
低次しきい値関数 (PTF) の, 対向汚職の一定割合の存在下での効率的な学習性について検討した。
提案アルゴリズムは,線形しきい値関数の学習に使用されていた局所化手法に着想を得た反復的手法を用いている。
論文 参考訳（メタデータ） (2024-03-31T02:03:35Z) - Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
基礎となるオラクルが一様有界であれば,本手法は全体のオラクル複雑性が$tildeO(varepsilon-5)$であることを示す。
平均報酬と割引報酬を決定するための新しい同期アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-19T01:07:35Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。