論文の概要: Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement
Learning with Latent Low-Rank Structure
- arxiv url: http://arxiv.org/abs/2206.03569v4
- Date: Fri, 9 Jun 2023 08:38:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-12 18:35:52.196903
- Title: Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement
Learning with Latent Low-Rank Structure
- Title（参考訳）: 潜伏低ランク構造を用いたサンプル効率強化学習のための長水平バリアの克服
- Authors: Tyler Sam, Yudong Chen, and Christina Lee Yu
- Abstract要約: 我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。
より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
- 参考スコア（独自算出の注目度）: 9.759209713196718
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The practicality of reinforcement learning algorithms has been limited due to
poor scaling with respect to the problem size, as the sample complexity of
learning an $\epsilon$-optimal policy is $\tilde{\Omega}\left(|S||A|H^3 /
\epsilon^2\right)$ over worst case instances of an MDP with state space $S$,
action space $A$, and horizon $H$. We consider a class of MDPs for which the
associated optimal $Q^*$ function is low rank, where the latent features are
unknown. While one would hope to achieve linear sample complexity in $|S|$ and
$|A|$ due to the low rank structure, we show that without imposing further
assumptions beyond low rank of $Q^*$, if one is constrained to estimate the $Q$
function using only observations from a subset of entries, there is a worst
case instance in which one must incur a sample complexity exponential in the
horizon $H$ to learn a near optimal policy. We subsequently show that under
stronger low rank structural assumptions, given access to a generative model,
Low Rank Monte Carlo Policy Iteration (LR-MCPI) and Low Rank Empirical Value
Iteration (LR-EVI) achieve the desired sample complexity of
$\tilde{O}\left((|S|+|A|)\mathrm{poly}(d,H)/\epsilon^2\right)$ for a rank $d$
setting, which is minimax optimal with respect to the scaling of $|S|, |A|$,
and $\epsilon$. In contrast to literature on linear and low-rank MDPs, we do
not require a known feature mapping, our algorithm is computationally simple,
and our results hold for long time horizons. Our results provide insights on
the minimal low-rank structural assumptions required on the MDP with respect to
the transition kernel versus the optimal action-value function.
- Abstract（参考訳）: 強化学習アルゴリズムの実用性は、問題サイズに関するスケーリングの貧弱さによって制限されている。$\epsilon$-optimal policyの学習のサンプル複雑性は$\tilde{\omega}\left(|s||a|h^3 / \epsilon^2\right)$ 状態空間$s$、アクションスペース$a$、ホライズン$h$である。
我々は、関連する最適な$q^*$関数が低ランクであるmdpのクラスを考える。
低ランク構造のため、$|s|$ と $|a|$ で線形なサンプル複雑性を達成することを望んでいるが、低ランクの$q^*$ を超える仮定を課すことなく、エントリのサブセットからの観察のみを用いて$q$関数を推定することに制約されている場合、ほぼ最適に近いポリシーを学ぶために、サンプルの複雑性を指数関数的に負わなければならない最悪のケースがある。
その後、より強い低階構造仮定の下で、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が与えられた場合、$\tilde{O}\left((|S|+|A|)\mathrm{poly}(d,H)/\epsilon^2\right)$が望ましく、$d$設定は$|S|, |A|$, $\epsilon$のスケーリングに対して最適である。
線形および低ランクのMDPに関する文献とは対照的に、既知の特徴マッピングは必要とせず、アルゴリズムは計算的に単純であり、その結果は長期間の地平線を保っている。
この結果から, MDP 上で必要となる最小限の低ランク構造仮定を, 遷移カーネルと最適作用値関数に対して考察した。
関連論文リスト
- 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) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳（メタデータ） (2023-06-28T17:43:19Z) - Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
対戦型オンラインマルチタスク強化学習環境について考察する。
K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。
学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
論文 参考訳（メタデータ） (2023-01-11T02:18:26Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳（メタデータ） (2021-10-12T23:03:58Z) - Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。
我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-22T03:20:40Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳（メタデータ） (2021-05-28T17:49:39Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳（メタデータ） (2021-02-25T15:50:19Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。