論文の概要: Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited

• arxiv url: http://arxiv.org/abs/2010.03531v1
• Date: Wed, 7 Oct 2020 17:23:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-09 22:27:16.532508
• Title: Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
• Title（参考訳）: 有限MDPにおけるエピソード強化学習:ミニマックス下界の再検討
• Authors: Omar Darwiche Domingues, Pierre M\'enard, Emilie Kaufmann, Michal Valko
• Abstract要約: エピソードMDPにおける標本の複雑さと後悔に対する問題非依存の新たな下位境界を提案する。 我々の主な貢献は、非定常MDPにおける最良のポリシー識別のための$(varepsilon,delta)$-PACアルゴリズムのサンプル複雑性に基づいて、$Omega((H3SA/epsilon2)log (1/delta))$の新たな低い境界である。
• 参考スコア（独自算出の注目度）: 46.682733513730334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose new problem-independent lower bounds on the sample complexity and regret in episodic MDPs, with a particular focus on the non-stationary case in which the transition kernel is allowed to change in each stage of the episode. Our main contribution is a novel lower bound of $\Omega((H^3SA/\epsilon^2)\log(1/\delta))$ on the sample complexity of an $(\varepsilon,\delta)$-PAC algorithm for best policy identification in a non-stationary MDP. This lower bound relies on a construction of "hard MDPs" which is different from the ones previously used in the literature. Using this same class of MDPs, we also provide a rigorous proof of the $\Omega(\sqrt{H^3SAT})$ regret bound for non-stationary MDPs. Finally, we discuss connections to PAC-MDP lower bounds.
• Abstract（参考訳）: 本稿では,エピソジックmdpにおけるサンプルの複雑性と後悔に関する新たな問題非依存下限を提案し,トランジッション・カーネルがエピソードの各段階で変化することを許容する非定常ケースに着目した。 我々の主な貢献は、非定常MDPにおける最良のポリシー識別のための$(\varepsilon,\delta)$-PACアルゴリズムのサンプル複雑性に基づいて、$\Omega((H^3SA/\epsilon^2)\log(1/\delta))の新規な下限である。 この下限は、それまで文献で使われていたものとは異なる「ハードMDP」の構築に依存している。 この同じ種類の MDP を用いて、非定常 MDP に対する $\Omega(\sqrt{H^3SAT})$ regret bound の厳密な証明も提供する。 最後に、PAC-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)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
  生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。 状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-13T17:18:11Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)

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

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