論文の概要: Sharp Sample Complexity of KL-Regularized Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2611.13480v1
- Date: Tue, 10 Nov 2026 02:42:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-12 04:24:43.646108
- Title: Sharp Sample Complexity of KL-Regularized Reinforcement Learning
- Title(参考訳): KL正規化強化学習におけるシャープサンプル複雑さ
- Abstract要約: 人間からのフィードバックから最大エントロピーRLとRLの背後にある目的であるKL正規化強化学習は「推論としての制御」のグラフィカルモデルにおける変分推論である
生成モデルを用いても、この後部を学習するのにどれだけのサンプルが必要であるかは分かっていない。
状態-作用対が$K$の割引MDPに対して、プラグイン推定器は、$widetildeO(KH3/(max,) + KH)$サンプルを持つ初期状態から$$$-Optimalのポリシーを見つける。
- 参考スコア(独自算出の注目度): 2.4423948691940347
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: KL-regularized reinforcement learning, the objective behind maximum-entropy RL and RL from human feedback, is variational inference in the graphical model of "control as inference": the regularized optimal policy is a posterior over trajectories, and the suboptimality of a policy is $β$ times a KL divergence between path measures. However, it is not known how many samples it takes to learn this posterior, even with a generative model. Earlier $1/ε$ guarantees scale with $H^5$ in the effective horizon $H$, and no lower bound for MDPs depends on the temperature $β$. In this work, we show that for a discounted MDP with $K$ state-action pairs, the plug-in estimator finds a policy that is $ε$-optimal from every initial state with $\widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH)$ samples, and that no algorithm, even one that chooses where to sample, can do with fewer when $ε\lesssim \min\{H, H^2/β\}$. For $ε< β$ this is a $1/ε$ rate with the same horizon dependence as unregularized RL. We also find the exact asymptotic constant of the plug-in estimator, a Fisher-weighted variance of the estimated soft Q-function. The estimator is locally asymptotically minimax among methods that sample every pair equally often, and we give the allocation of samples that is optimal among adaptive designs. Simulations on small MDPs match the rates and the constants.
- Abstract(参考訳): ヒトのフィードバックから最大エントロピーRLとRLの背景にある目的であるKL正規化強化学習は、「推論としての制御」というグラフィカルモデルにおける変分推論である。
しかし、生成モデルを用いても、この後部を学習するのにどれだけのサンプルが必要であるかは分かっていない。
初期の$/ε$は、有効地平線において$H^5$のスケールを保証し、MDPの低いバウンドは、温度$β$に依存する。
この研究で、$K$ 状態-作用対を持つ割引 MDP に対して、プラグイン推定器は$\widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH)$サンプルを持つ初期状態から$ε$-最適化されたポリシーを見つけ、$ε\lesssim \min\{H, H^2/β\}$ の場合、サンプリング先を選択するアルゴリズムでさえ、より少ない時間で実行可能であることを示す。
ε< β$ の場合、これは非正規化 RL と同じ水平依存性を持つ 1/ε$ レートである。
また、推定ソフトQ関数のフィッシャー重み付き分散であるプラグイン推定器の正確な漸近定数を求める。
推定器は各ペアを同じ頻度でサンプリングする手法の中で局所的に漸近的に最小値であり、適応設計において最適なサンプルの割り当てを与える。
小さなMDPのシミュレーションは、速度と定数に一致する。
関連論文リスト
- Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。
我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文 参考訳(メタデータ) (2026-08-06T19:49:48Z) - Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。
任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。
本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
論文 参考訳(メタデータ) (2026-02-19T17:21:15Z) - Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation [17.943901563004275]
SPS$*$ と呼ばれる理想化されたポリアクステップサイズの一般収束定理を提供する。
SPS$*$は、ソリューションで評価されたトレーニングバッチ毎に損失にアクセスする必要があるため、理想化されています。
これはまた、大域リプシッツ函数の最適下界を達成し、滑らかな設定で任意の時間収束する$O(1/sqrtt) を持つ最初のポリアクステップサイズであるという点でも理想的である。
論文 参考訳(メタデータ) (2025-04-02T16:57:39Z) - Variance Reduction for the Independent Metropolis Sampler [11.074080383657453]
我々は、$pi$がKL分散の下で別の密度$q$に十分近い場合、$pi$からサンプルを得る独立したサンプリング器は、$pi$からサンプリングするi.d.よりも小さな分散を達成することを証明した。
提案手法は,KLの目標との偏差が低減されるように,提案密度に適応する適応型独立メトロポリスアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-06-25T16:38:53Z) - 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) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - (Nearly) Optimal Private Linear Regression via Adaptive Clipping [22.639650869444395]
固定されたガウス型分布から各データ点をサンプリングする微分プライベート線形回帰問題について検討する。
本稿では,各イテレーションの点を置換せずにサンプリングする1パスのミニバッチ勾配勾配法(DP-AMBSSGD)を提案し,解析する。
論文 参考訳(メタデータ) (2022-07-11T08:04:46Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳(メタデータ) (2022-04-11T17:26:19Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。