論文の概要: Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement
Learning with Latent Low-Rank Structure
- arxiv url: http://arxiv.org/abs/2206.03569v1
- Date: Tue, 7 Jun 2022 20:39:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-10 05:32:03.425905
- 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要約: 低位構造を示すMDPのクラスについて検討する。
生成モデルへのアクセスを前提とした低ランク構造を効率的に活用する,統計的保証を伴う新しいアルゴリズムを提案する。
線形および低ランクのMDPに関する文献とは対照的に、既知の特徴マッピングは必要とせず、アルゴリズムは計算的に単純であり、その結果は長期間の地平線を保っている。
- 参考スコア（独自算出の注目度）: 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 /
\eps^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 that exhibit low rank
structure, where the latent features are unknown. We argue that a natural
combination of value iteration and low-rank matrix estimation results in an
estimation error that grows doubly exponentially in the horizon $H$. We then
provide a new algorithm along with statistical guarantees that efficiently
exploits low rank structure given access to a generative model, achieving a
sample complexity of
$\Tilde{O}\left(d^5(|S|+|A|)\mathrm{poly}(H)/\eps^2\right)$ for a rank $d$
setting, which is minimax optimal with respect to the scaling of $|S|, |A|$,
and $\eps$. 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 / \eps^2\right)$ 状態空間$s$、アクションスペース$a$、ホライズン$h$である。
我々は,低位構造を示すmdpのクラスを考える。
値反復と低ランク行列推定の自然な組み合わせは、地平線において2倍に指数関数的に増大する推定誤差をもたらすと論じる。
次に, 生成モデルへのアクセスを与えられた低位構造を効率的に活用し, ランク$d$設定に対して$\tilde{o}\left(d^5(|s|+|a|)\mathrm{poly}(h)/\eps^2\right)$のサンプル複雑性を達成する, 統計的保証とともに新しいアルゴリズムを提供する。
線形および低ランクの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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。