論文の概要: Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement
Learning with General Function Approximation
- arxiv url: http://arxiv.org/abs/2312.04464v1
- Date: Thu, 7 Dec 2023 17:35:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 13:58:22.459968
- Title: Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement
Learning with General Function Approximation
- Title(参考訳): 一般関数近似を用いた強化学習のための水平およびインスタンス依存レギュレット境界
- Authors: Jiayi Huang, Han Zhong, Liwei Wang, Lin F. Yang
- Abstract要約: 一般関数近似を用いた強化学習における長期計画地平線問題に対処するアルゴリズムを提案する。
導出残差は、線形混合MDPを対数因子まで特殊化する場合のミニマックス下限と一致するため、エンフシャープと見なされる。
このような地平線に依存しない、インスタンスに依存しない、鋭い後悔に満ちたヒンジの達成は、(i)新しいアルゴリズム設計と(ii)きめ細かい解析に基づいている。
- 参考スコア(独自算出の注目度): 26.277745106128197
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: To tackle long planning horizon problems in reinforcement learning with
general function approximation, we propose the first algorithm, termed as
UCRL-WVTR, that achieves both \emph{horizon-free} and
\emph{instance-dependent}, since it eliminates the polynomial dependency on the
planning horizon. The derived regret bound is deemed \emph{sharp}, as it
matches the minimax lower bound when specialized to linear mixture MDPs up to
logarithmic factors. Furthermore, UCRL-WVTR is \emph{computationally efficient}
with access to a regression oracle. The achievement of such a horizon-free,
instance-dependent, and sharp regret bound hinges upon (i) novel algorithm
designs: weighted value-targeted regression and a high-order moment estimator
in the context of general function approximation; and (ii) fine-grained
analyses: a novel concentration bound of weighted non-linear least squares and
a refined analysis which leads to the tight instance-dependent bound. We also
conduct comprehensive experiments to corroborate our theoretical findings.
- Abstract(参考訳): 一般関数近似による強化学習における長大計画地平線問題に取り組むために, 計画地平線への多項式依存を解消するため, \emph{horizon-free} と \emph{instance-dependent} の両方を達成する最初のアルゴリズムucrl-wvtrを提案する。
導出した後悔境界は、線形混合MDPを対数因子まで特殊化する場合のミニマックス下界と一致するため、 \emph{sharp} とみなす。
さらに、UCRL-WVTRは回帰オラクルへのアクセスを伴うemph{computationally efficient}である。
そのような地平線のない、インスタンスに依存し、鋭い後悔の束縛の達成
(i)新しいアルゴリズム設計:一般関数近似の文脈における重み付き値目標回帰と高次モーメント推定器
(ii)細粒度解析:重み付き非線形最小二乗の新たな濃度境界と、密接なインスタンス依存境界につながる洗練された解析。
また、理論的な発見を裏付ける包括的な実験も行います。
関連論文リスト
- Neural Network Approximation for Pessimistic Offline Reinforcement
Learning [17.756108291816908]
一般ニューラルネットワーク近似を用いた悲観的オフラインRLの非漸近的推定誤差を提案する。
その結果, 推定誤差は2つの部分から構成されることがわかった。第1は, 部分的に制御可能な集束率でサンプルサイズに所望の速度で0に収束し, 第2は残留制約が厳密であれば無視可能である。
論文 参考訳(メタデータ) (2023-12-19T05:17:27Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Pessimistic Nonlinear Least-Squares Value Iteration for Offline
Reinforcement Learning [58.962016644796]
非線形関数近似を用いたオフラインRLにおけるPNLSVI(Pessimistic Least-Square Value Iteration)と呼ばれるオラクル効率のアルゴリズムを提案する。
本アルゴリズムは,関数クラスの複雑性に強く依存する後悔境界を享受し,線形関数近似に特化して最小限のインスタンス依存後悔を実現する。
論文 参考訳(メタデータ) (2023-10-02T17:42:01Z) - An Option-Dependent Analysis of Regret Minimization Algorithms in
Finite-Horizon Semi-Markov Decision Processes [47.037877670620524]
有限ホライゾン問題における後悔最小化アルゴリズムに苦しむ後悔に対するオプション依存上界について述べる。
本稿では,階層構造によって強制される時間的抽象化によって誘導される計画的地平線低減から,性能改善が導かれることを示す。
論文 参考訳(メタデータ) (2023-05-10T15:00:05Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳(メタデータ) (2023-01-16T02:57:37Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳(メタデータ) (2022-10-08T08:26:22Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳(メタデータ) (2021-07-23T19:38:17Z) - A Stochastic Composite Augmented Lagrangian Method For Reinforcement
Learning [9.204659134755795]
深層強化学習のための線形プログラミング(LP)の定式化について検討する。
拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。
深層パラメタライズされたラグランジアン法を提案する。
論文 参考訳(メタデータ) (2021-05-20T13:08:06Z) - Benefit of deep learning with non-convex noisy gradient descent:
Provable excess risk bound and superiority to kernel methods [41.60125423028092]
線形推定器は,極小値の最適値の意味で,ディープラーニングにより性能が向上することを示した。
過剰な境界はいわゆる高速学習率であり、$O境界よりも高速である。
論文 参考訳(メタデータ) (2020-12-06T09:22:16Z) - A spectral algorithm for robust regression with subgaussian rates [0.0]
本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。
目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
論文 参考訳(メタデータ) (2020-07-12T19:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。