論文の概要: Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
- arxiv url: http://arxiv.org/abs/2106.11519v1
- Date: Tue, 22 Jun 2021 03:20:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 15:06:19.592152
- Title: Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
- Title（参考訳）: 低ランクMDPによる強化学習とリッチな観察
- Authors: Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari and
Karthik Sridharan
- Abstract要約: 我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。
我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 79.66404989555566
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There have been many recent advances on provably efficient Reinforcement
Learning (RL) in problems with rich observation spaces. However, all these
works share a strong realizability assumption about the optimal value function
of the true MDP. Such realizability assumptions are often too strong to hold in
practice. In this work, we consider the more realistic setting of agnostic RL
with rich observation spaces and a fixed class of policies $\Pi$ that may not
contain any near-optimal policy. We provide an algorithm for this setting whose
error is bounded in terms of the rank $d$ of the underlying MDP. Specifically,
our algorithm enjoys a sample complexity bound of $\widetilde{O}\left((H^{4d}
K^{3d} \log |\Pi|)/\epsilon^2\right)$ where $H$ is the length of episodes, $K$
is the number of actions and $\epsilon>0$ is the desired sub-optimality. We
also provide a nearly matching lower bound for this agnostic setting that shows
that the exponential dependence on rank is unavoidable, without further
assumptions.
- Abstract（参考訳）: 近年,リッチな観測空間に関する問題において,RL(Reinforcement Learning)の有効性向上が進んでいる。
しかし、これらすべての研究は真の MDP の最適値関数に関する強い実現可能性の仮定を共有している。
このような実現可能性の仮定は、実際は保つには強すぎることが多い。
本研究では, 観測空間の豊富な非依存 rl のより現実的な設定と, ほぼ最適に近いポリシーを含まない固定型ポリシー $\pi$ について考察する。
我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
具体的には、我々のアルゴリズムは、$\widetilde{O}\left((H^{4d} K^{3d} \log |\Pi|)/\epsilon^2\right)$で、$H$はエピソードの長さ、$K$はアクションの数、$\epsilon>0$はサブ最適である。
また、この非依存的な設定に対してほぼ一致する下界を提供し、さらに仮定することなく、階数への指数的依存が避けられないことを示す。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - 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) - Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement
Learning with Latent Low-Rank Structure [9.759209713196718]
我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。
より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
論文 参考訳（メタデータ） (2022-06-07T20:39:51Z) - 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) - Towards Tractable Optimism in Model-Based Reinforcement Learning [37.51073590932658]
成功させるためには、楽観的なRLアルゴリズムは真の値関数(最適化)を過大に見積もる必要があるが、不正確な(推定誤差)ほどではない。
我々は,これらのスケーラブルな楽観的モデルベースアルゴリズムを,トラクタブルノイズ拡張MDPの解法として再解釈する。
この誤差が低減された場合、楽観的なモデルベースRLアルゴリズムは、連続制御問題における最先端性能と一致することを示す。
論文 参考訳（メタデータ） (2020-06-21T20:53:19Z) - Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。
我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
論文 参考訳（メタデータ） (2020-02-29T02:02:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。