論文の概要: Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs

• arxiv url: http://arxiv.org/abs/2203.09251v1
• Date: Thu, 17 Mar 2022 11:19:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-18 13:45:26.913636
• Title: Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs
• Title（参考訳）: 決定論的MDPのための最適PAC強化学習
• Authors: Andrea Tirinzoni, Aymen Al-Marjani, Emilie Kaufmann
• Abstract要約: エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
• 参考スコア（独自算出の注目度）: 24.256960622176305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In probably approximately correct (PAC) reinforcement learning (RL), an agent is required to identify an $\epsilon$-optimal policy with probability $1-\delta$. While minimax optimal algorithms exist for this problem, its instance-dependent complexity remains elusive in episodic Markov decision processes (MDPs). In this paper, we propose the first (nearly) matching upper and lower bounds on the sample complexity of PAC RL in deterministic episodic MDPs with finite state and action spaces. In particular, our bounds feature a new notion of sub-optimality gap for state-action pairs that we call the deterministic return gap. While our instance-dependent lower bound is written as a linear program, our algorithms are very simple and do not require solving such an optimization problem during learning. Their design and analyses employ novel ideas, including graph-theoretical concepts such as minimum flows and maximum cuts, which we believe to shed new light on this problem.
• Abstract（参考訳）: おそらく略正(PAC)強化学習(RL)では、エージェントは$\epsilon$-optimal policy with probability $1-\delta$を識別する必要がある。 この問題にはミニマックス最適アルゴリズムが存在するが、そのインスタンス依存の複雑さは、エピソード的マルコフ決定過程(MDPs)において解明されている。 本稿では, 有限状態および作用空間を持つ決定論的エピソードMDPにおけるPAC RLのサンプル複雑性に対する, 上界と下界の整合性について述べる。 特に、我々の境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用対に対する準最適ギャップという新しい概念を特徴としている。 インスタンス依存の下位境界は線形プログラムとして記述されるが、アルゴリズムは非常に単純であり、学習中にそのような最適化問題を解決する必要はない。 彼らの設計と分析には、最小フローや最大カットといったグラフ理論的な概念を含む、新しいアイデアが採用されています。

関連論文リスト

• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。 まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。 次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
  論文  参考訳（メタデータ） (2022-08-17T18:49:53Z)
• Optimistic PAC Reinforcement Learning: the Instance-Dependent View [24.256960622176305]
  PAC RL, BPI-UCRL に対する楽観的アルゴリズムを提案する。 私たちの限界は、最小の訪問確率を特徴としていますが、それはまた、準最適ギャップという洗練された概念も特徴です。 決定論的遷移を持つMDPでは、BPI-UCRLが実際にはほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2022-07-12T21:35:03Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning [29.552894877883883]
  低後悔を達成し、インスタンス最適率で$epsilon$-optimal Policyを特定できるというトレードオフが存在することを示す。 本稿では,このサンプル複雑性を実現する新しい計画ベースアルゴリズムの提案と解析を行う。 我々のアルゴリズムは最小限の最適値であり、いくつかの例では、インスタンス依存のサンプル複雑性は最悪のケース境界よりも大幅に改善されている。
  論文  参考訳（メタデータ） (2021-08-05T16:34:17Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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