論文の概要: A New Interpretation of the Certainty-Equivalence Approach for PAC Reinforcement Learning with a Generative Model

• arxiv url: http://arxiv.org/abs/2501.02652v1
• Date: Sun, 05 Jan 2025 20:37:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-07 17:09:12.132398
• Title: A New Interpretation of the Certainty-Equivalence Approach for PAC Reinforcement Learning with a Generative Model
• Title（参考訳）: 生成モデルを用いたPAC強化学習における確実性と等価性の新しい解釈法
• Authors: Shivaram Kalyanakrishnan, Sheel Shah, Santhosh Kumar Guguloth,
• Abstract要約: 本稿では,CEMが実際にTTMの応用と見なされるという驚くべき発見に起因した理論的研究を提案する。 我々は,非定常MPPと定常MPPの双方に対して,CEMの試料複雑度上限を(3)改良した。 また, 有限ホライズン MDP に対する標本複雑性の低い値を示し, 非定常 MDP に対する上界の最小値最適性を確立する。
• 参考スコア（独自算出の注目度）: 5.238591085233903
• License:
• Abstract: Reinforcement learning (RL) enables an agent interacting with an unknown MDP $M$ to optimise its behaviour by observing transitions sampled from $M$. A natural entity that emerges in the agent's reasoning is $\widehat{M}$, the maximum likelihood estimate of $M$ based on the observed transitions. The well-known \textit{certainty-equivalence} method (CEM) dictates that the agent update its behaviour to $\widehat{\pi}$, which is an optimal policy for $\widehat{M}$. Not only is CEM intuitive, it has been shown to enjoy minimax-optimal sample complexity in some regions of the parameter space for PAC RL with a generative model~\citep{Agarwal2020GenModel}. A seemingly unrelated algorithm is the ``trajectory tree method'' (TTM)~\citep{Kearns+MN:1999}, originally developed for efficient decision-time planning in large POMDPs. This paper presents a theoretical investigation that stems from the surprising finding that CEM may indeed be viewed as an application of TTM. The qualitative benefits of this view are (1) new and simple proofs of sample complexity upper bounds for CEM, in fact under a (2) weaker assumption on the rewards than is prevalent in the current literature. Our analysis applies to both non-stationary and stationary MDPs. Quantitatively, we obtain (3) improvements in the sample-complexity upper bounds for CEM both for non-stationary and stationary MDPs, in the regime that the ``mistake probability'' $\delta$ is small. Additionally, we show (4) a lower bound on the sample complexity for finite-horizon MDPs, which establishes the minimax-optimality of our upper bound for non-stationary MDPs in the small-$\delta$ regime.
• Abstract（参考訳）: 強化学習(Reinforcement Learning, RL)は、未知のMDP$M$と相互作用するエージェントが、M$からサンプリングされた遷移を観察することで、その振る舞いを最適化することを可能にする。 エージェントの推論に現れる自然な実体は$\widehat{M}$であり、観測された遷移に基づいて最大で$M$と推定される。 有名な \textit{certainty-equivalence} メソッド (CEM) は、エージェントがその振る舞いを $\widehat{\pi}$ に更新することを指示する。 CEMは直感的なだけでなく、生成モデル~\citep{Agarwal 2020GenModel} を用いたPAC RLのパラメータ空間のいくつかの領域において、最小値-最適サンプルの複雑さを楽しむことが示されている。 一見無関係なアルゴリズムは ``trajectory tree method'' (TTM)~\citep{Kearns+MN:1999} であり、当初は大規模なPOMDPの効率的な決定時間計画のために開発された。 本稿では,CEMが実際にTTMの応用と見なされるという驚くべき発見に起因した理論的研究を提案する。 この考え方の質的な利点は、(1) CEM の標本複雑性上界の新たな単純かつ単純な証明であり、実際、(2) 報酬に対するより弱い仮定の下で、現在の文献でよく見られる。 本分析は,非定常MPPと定常MPPの両方に適用する。 定量的に,非定常かつ定常なMDPに対して,CEMのサンプル複雑度上限の3つの改善点を, `<mistake probability'' の $\delta$ が小さいという条件下で得る。 さらに、 (4) は有限水平 MDP に対するサンプル複雑性の低い境界を示し、これは小$\delta$ 状態における非定常 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)
• Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs [43.53286390357673]
  本稿では,低ランクMDPモデルによる報酬なし強化学習に焦点を当てた。 我々はまず、低ランクのMDPの下での任意のアルゴリズムに対して、最初の既知のサンプル複雑性の低い境界を提供する。 次に、RAFFLEと呼ばれる新しいモデルベースアルゴリズムを提案し、$epsilon$-optimal Policyを見つけ、$epsilon$-accurate system IDを実現できることを示す。
  論文  参考訳（メタデータ） (2023-03-20T04:39:39Z)
• Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation [41.082982732100696]
  我々は,凸複合リスク最小化問題の解法として,近位点法(M-SPP)のミニバッチ変種について検討した。 ミニバッチサイズが$n$で二次数が$T$のM-SPPは、予想外収束の速さを楽しむことを示す。 小さい$n$-large-$T$設定では、この結果はSPP型アプローチの最もよく知られた結果を大幅に改善する。
  論文  参考訳（メタデータ） (2023-01-09T00:13:34Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• 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)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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