論文の概要: Sample Complexity of Kernel-Based Q-Learning

• arxiv url: http://arxiv.org/abs/2302.00727v1
• Date: Wed, 1 Feb 2023 19:46:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-03 16:15:57.853156
• Title: Sample Complexity of Kernel-Based Q-Learning
• Title（参考訳）: カーネルベースq-learningのサンプル複雑性
• Authors: Sing-Yuan Yeh, Fu-Chieh Chang, Chang-Wei Yueh, Pei-Yuan Wu, Alberto Bernacchia, Sattar Vakili
• Abstract要約: 任意に大規模に割引されたMDPにおいて,$epsilon$-optimal Policyを求める非パラメトリックQ-ラーニングアルゴリズムを提案する。 我々の知る限りでは、このような一般モデルの下では、有限サンプルの複雑さを示す最初の結果である。
• 参考スコア（独自算出の注目度）: 11.32718794195643
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern reinforcement learning (RL) often faces an enormous state-action space. Existing analytical results are typically for settings with a small number of state-actions, or simple models such as linearly modeled Q-functions. To derive statistically efficient RL policies handling large state-action spaces, with more general Q-functions, some recent works have considered nonlinear function approximation using kernel ridge regression. In this work, we derive sample complexities for kernel based Q-learning when a generative model exists. We propose a nonparametric Q-learning algorithm which finds an $\epsilon$-optimal policy in an arbitrarily large scale discounted MDP. The sample complexity of the proposed algorithm is order optimal with respect to $\epsilon$ and the complexity of the kernel (in terms of its information gain). To the best of our knowledge, this is the first result showing a finite sample complexity under such a general model.
• Abstract（参考訳）: 現代の強化学習(RL)は、しばしば巨大な状態行動空間に直面している。 既存の分析結果は通常、少数の状態作用を持つ設定や、線形モデル化されたQ-関数のような単純なモデルに当てはまる。 大規模状態-作用空間を扱う統計的に効率的なRLポリシーをより一般的なQ-関数で導出するために、最近の研究ではカーネルリッジ回帰を用いた非線形関数近似が検討されている。 本研究では,生成モデルが存在する場合,カーネルベースq-learningのサンプル複雑性を導出する。 非パラメトリックQ-ラーニングアルゴリズムを提案し、任意のスケールの割引MDPで$\epsilon$-optimal Policyを求める。 提案アルゴリズムのサンプル複雑性は、$\epsilon$ と(情報ゲインの観点から)カーネルの複雑性に関して順序最適である。 我々の知る限りでは、このような一般モデルの下で有限標本複雑性を示す最初の結果である。

関連論文リスト

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• On Representation Complexity of Model-based and Model-free Reinforcement Learning [11.843778337443824]
  回路複雑性の文脈におけるモデルベースおよびモデルフリー強化学習(RL)の表現複雑性について検討した。 理論的には、その基底となる遷移関数と報酬関数が、大きさの一定深さの回路で表現できるような、幅広い種類のMDPが存在することを証明している。 近似誤差に注意を向け、複雑性理論への接続を構築することによって、モデルベースのアルゴリズムが、新しい表現複雑性の観点からモデルフリーアルゴリズムよりも、なぜサンプルの複雑さを楽しむのかというユニークな洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-03T00:01:58Z)
• Sample-efficient Model-based Reinforcement Learning for Quantum Control [0.2999888908665658]
  ノイズの多い時間依存ゲート最適化のためのモデルベース強化学習(RL)手法を提案する。 標準モデルフリーRLに比べて,本手法のサンプル複雑性において,桁違いの優位性を示す。 提案アルゴリズムは,部分的特徴付き1量子ビット系と2量子ビット系の制御に適している。
  論文  参考訳（メタデータ） (2023-04-19T15:05:19Z)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  部分的に観察可能な力学系におけるオンライン強化学習(RL)について検討する。 我々は、他のよく知られたモデルをキャプチャする表現モデルである予測状態表現(PSR)モデルに焦点を当てる。 我々は,サンプル複雑性のスケーリングにおいて,ほぼ最適なポリシを学習可能な,PSRのための新しいモデルベースアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-12T17:57:17Z)
• Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting [60.98700344526674]
  線形関数表現のような低複雑度モデルがサンプル効率のよい強化学習を可能にする上で重要な役割を果たしている。 本稿では,オンライン/探索的な方法でサンプルを描画するが,制御不能な方法で以前の状態をバックトラックし,再訪することができる新しいサンプリングプロトコルについて検討する。 この設定に合わせたアルゴリズムを開発し、特徴次元、地平線、逆の準最適ギャップと実際にスケールするサンプル複雑性を実現するが、状態/作用空間のサイズではない。
  論文  参考訳（メタデータ） (2021-05-17T17:22:07Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  本稿では,線形近似ニューラルネットワーク(LANN)を提案する。 ニューラルネットワークのトレーニングプロセスを実験的に検討し、オーバーフィッティングを検出する。 我々は、$L1$と$L2$正規化がモデルの複雑さの増加を抑制することを発見した。
  論文  参考訳（メタデータ） (2020-06-16T07:38:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。