論文の概要: Improving Reinforcement Learning Sample-Efficiency using Local Approximation

• arxiv url: http://arxiv.org/abs/2507.12383v1
• Date: Wed, 16 Jul 2025 16:31:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-17 19:00:11.471833
• Title: Improving Reinforcement Learning Sample-Efficiency using Local Approximation
• Title（参考訳）: 局所近似を用いた強化学習サンプル効率の向上
• Authors: Mohit Prashant, Arvind Easwaran,
• Abstract要約: 無限水平マルコフ決定過程におけるRLのサンプル複素性に基づいてPAC境界を導出する。 PAC-MDPアルゴリズムを上述のサンプル複雑度で構築することにより,これらの結果を無限水平モデルフリーの設定に拡張することができる。
• 参考スコア（独自算出の注目度）: 2.5582913676558205
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this study, we derive Probably Approximately Correct (PAC) bounds on the asymptotic sample-complexity for RL within the infinite-horizon Markov Decision Process (MDP) setting that are sharper than those in existing literature. The premise of our study is twofold: firstly, the further two states are from each other, transition-wise, the less relevant the value of the first state is when learning the $\epsilon$-optimal value of the second; secondly, the amount of 'effort', sample-complexity-wise, expended in learning the $\epsilon$-optimal value of a state is independent of the number of samples required to learn the $\epsilon$-optimal value of a second state that is a sufficient number of transitions away from the first. Inversely, states within each other's vicinity have values that are dependent on each other and will require a similar number of samples to learn. By approximating the original MDP using smaller MDPs constructed using subsets of the original's state-space, we are able to reduce the sample-complexity by a logarithmic factor to $O(SA \log A)$ timesteps, where $S$ and $A$ are the state and action space sizes. We are able to extend these results to an infinite-horizon, model-free setting by constructing a PAC-MDP algorithm with the aforementioned sample-complexity. We conclude with showing how significant the improvement is by comparing our algorithm against prior work in an experimental setting.
• Abstract（参考訳）: 本研究では,既存の文献よりシャープな無限水平マルコフ決定過程 (MDP) におけるRLの漸近的サンプル複雑度に基づいて,ほぼ正当性(PAC)境界を導出する。 まず、次の2つの状態が相互から、遷移的に、第1の状態の値は、第2状態の$\epsilon$-Optimal値を学ぶとき、第2状態の$\epsilon$-Optimal値と、第1状態から十分な移行数である第2状態の$\epsilon$-Optimal値を学ぶのに必要なサンプル数とは独立である、という前提である。 逆に、お互いの近傍にある状態は互いに依存する値を持ち、学ぶのに同じ数のサンプルを必要とする。 元の状態空間のサブセットを用いて構築されたより小さなMDPを用いて元のMDPを近似することにより、対数係数によってサンプル複雑度を$O(SA \log A)$ timestepsに減らし、$S$と$A$は状態とアクション空間のサイズである。 PAC-MDPアルゴリズムを上述のサンプル複雑度で構築することにより,これらの結果を無限水平モデルフリーの設定に拡張することができる。 実験的な環境での事前の作業とアルゴリズムを比較して、改善がどれほど重要かを示す。

関連論文リスト

• Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning [5.8191965840377735]
  ほぼ最適サンプル複雑性を実現するアルゴリズムを2つ提案する。 両アルゴリズムが最適なポリシを推定するために,$widetildeOleft(|mathbfS||mathbfA| t_mathrmmix2varepsilon-2right)のサンプル複雑性が得られることを証明した。 これはDR平均逆強化学習における最初の有限サンプル収束保証である。
  論文  参考訳（メタデータ） (2025-05-15T06:42:25Z)
• Efficiently Solving Discounted MDPs with Predictions on Transition Matrices [6.199300239433395]
  生成モデルに基づくDMDP(Discounted Markov Decision Processs)について検討した。 DMDPの解法において,遷移行列上での予測がサンプル効率をいかに向上させるかを検討するための新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2025-02-21T09:59:46Z)
• 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)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning [82.31436758872715]
  我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。 値関数と有限水平マルコフ決定過程の接続を確立する。
  論文  参考訳（メタデータ） (2021-11-01T00:21:24Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• 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)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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