論文の概要: Lower Bounds for Learning in Revealing POMDPs

• arxiv url: http://arxiv.org/abs/2302.01333v1
• Date: Thu, 2 Feb 2023 18:59:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-03 12:41:35.983705
• Title: Lower Bounds for Learning in Revealing POMDPs
• Title（参考訳）: POMDPの学習における下位境界
• Authors: Fan Chen, Huan Wang, Caiming Xiong, Song Mei, Yu Bai
• Abstract要約: 本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
• 参考スコア（独自算出の注目度）: 88.23337313766355
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the fundamental limits of reinforcement learning (RL) in the challenging \emph{partially observable} setting. While it is well-established that learning in Partially Observable Markov Decision Processes (POMDPs) requires exponentially many samples in the worst case, a surge of recent work shows that polynomial sample complexities are achievable under the \emph{revealing condition} -- A natural condition that requires the observables to reveal some information about the unobserved latent states. However, the fundamental limits for learning in revealing POMDPs are much less understood, with existing lower bounds being rather preliminary and having substantial gaps from the current best upper bounds. We establish strong PAC and regret lower bounds for learning in revealing POMDPs. Our lower bounds scale polynomially in all relevant problem parameters in a multiplicative fashion, and achieve significantly smaller gaps against the current best upper bounds, providing a solid starting point for future studies. In particular, for \emph{multi-step} revealing POMDPs, we show that (1) the latent state-space dependence is at least $\Omega(S^{1.5})$ in the PAC sample complexity, which is notably harder than the $\widetilde{\Theta}(S)$ scaling for fully-observable MDPs; (2) Any polynomial sublinear regret is at least $\Omega(T^{2/3})$, suggesting its fundamental difference from the \emph{single-step} case where $\widetilde{O}(\sqrt{T})$ regret is achievable. Technically, our hard instance construction adapts techniques in \emph{distribution testing}, which is new to the RL literature and may be of independent interest.
• Abstract（参考訳）: 本稿では, 強化学習(RL)の基本的限界を, 挑戦的な 'emph{partially observable} 設定で検討する。 部分的に観測可能なマルコフ決定過程(POMDP)での学習は、最悪の場合において指数関数的に多くのサンプルを必要とすることはよく確立されているが、最近の研究の急増は、多項式サンプルの複雑さが 'emph{revealing condition} の下で達成可能であることを示している。 しかし、POMDPを明らかにするための学習の基本的な限界は理解されておらず、既存の下限はかなり予備的であり、現在の最上限とはかなりの差がある。 我々は強力なPACを確立し,POMDPを明らかにする上での学習の限界を後悔する。 我々の下界は、すべての関連する問題パラメータを乗法的に多項式的にスケールし、現在の最上界とのギャップを著しく小さくし、将来の研究の出発点となる。 特に、POMDPを明示する \emph{multi-step} の場合、(1) 潜時状態空間依存が少なくとも$\Omega(S^{1.5})$であり、これは PAC サンプル複雑性において $\widetilde{\Theta}(S)$ scale for fully-observable MDPs; (2) 多項式サブ線形後悔は少なくとも$\Omega(T^{2/3})$であり、$\widetilde{O}(\sqrt{T})$ regret が達成可能であることを示唆する。 技術的には、我々のハードインスタンス構築は、RL文献に新しく、独立した関心を持つかもしれない \emph{distribution testing} のテクニックに適応する。

関連論文リスト

• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Expected Worst Case Regret via Stochastic Sequential Covering [14.834625066344582]
  我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。 そのようなミニマックスの後悔に対して、我々は上大域シーケンシャル被覆という新しい概念を通じて厳密な境界を確立する。 対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
  論文  参考訳（メタデータ） (2022-09-09T17:31:46Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited [46.682733513730334]
  エピソードMDPにおける標本の複雑さと後悔に対する問題非依存の新たな下位境界を提案する。 我々の主な貢献は、非定常MDPにおける最良のポリシー識別のための$(varepsilon,delta)$-PACアルゴリズムのサンプル複雑性に基づいて、$Omega((H3SA/epsilon2)log (1/delta))$の新たな低い境界である。
  論文  参考訳（メタデータ） (2020-10-07T17:23:01Z)

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

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