論文の概要: Rethinking Model-based, Policy-based, and Value-based Reinforcement
Learning via the Lens of Representation Complexity
- arxiv url: http://arxiv.org/abs/2312.17248v1
- Date: Thu, 28 Dec 2023 18:59:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-29 14:35:27.205371
- Title: Rethinking Model-based, Policy-based, and Value-based Reinforcement
Learning via the Lens of Representation Complexity
- Title(参考訳): 表現複雑性レンズによるモデルベース・ポリシーベース・価値ベース強化学習の再考
- Authors: Guhao Feng, Han Zhong
- Abstract要約: 強化学習(Reinforcement Learning, RL)は、モデルベースRL、ポリシーベースRL、価値ベースRLなど、さまざまなパラダイムを包含する。
この研究は、これらのRLパラダイムの中で、表現の潜在的階層(表現すべき関数の複雑さ)について検討する。
- 参考スコア(独自算出の注目度): 6.3336529522086735
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reinforcement Learning (RL) encompasses diverse paradigms, including
model-based RL, policy-based RL, and value-based RL, each tailored to
approximate the model, optimal policy, and optimal value function,
respectively. This work investigates the potential hierarchy of representation
complexity -- the complexity of functions to be represented -- among these RL
paradigms. We first demonstrate that, for a broad class of Markov decision
processes (MDPs), the model can be represented by constant-depth circuits with
polynomial size or Multi-Layer Perceptrons (MLPs) with constant layers and
polynomial hidden dimension. However, the representation of the optimal policy
and optimal value proves to be $\mathsf{NP}$-complete and unattainable by
constant-layer MLPs with polynomial size. This demonstrates a significant
representation complexity gap between model-based RL and model-free RL, which
includes policy-based RL and value-based RL. To further explore the
representation complexity hierarchy between policy-based RL and value-based RL,
we introduce another general class of MDPs where both the model and optimal
policy can be represented by constant-depth circuits with polynomial size or
constant-layer MLPs with polynomial size. In contrast, representing the optimal
value is $\mathsf{P}$-complete and intractable via a constant-layer MLP with
polynomial hidden dimension. This accentuates the intricate representation
complexity associated with value-based RL compared to policy-based RL. In
summary, we unveil a potential representation complexity hierarchy within RL --
representing the model emerges as the easiest task, followed by the optimal
policy, while representing the optimal value function presents the most
intricate challenge.
- Abstract(参考訳): 強化学習(Reinforcement Learning, RL)は、モデルベースRL、ポリシーベースRL、価値ベースRLなど、様々なパラダイムを包含する。
この研究は、これらのrlパラダイムの中で、表現複雑性の潜在的階層(表現すべき関数の複雑さ)を調査します。
まず,多種類のマルコフ決定過程 (MDPs) に対して, モデルが多項式サイズを持つ定数深度回路か, 定数層と多項式隠蔽次元を持つ多層パーセプトロン (MLPs) で表現できることを実証した。
しかし、最適ポリシーと最適値の表現は$\mathsf{NP}$-完全であることが証明され、多項式サイズの定数層 MLP によって達成できない。
これは、ポリシーベースのRLと値ベースのRLを含むモデルベースRLとモデルフリーRLの間に、重要な表現複雑性のギャップを示す。
ポリシベースのRLと値ベースのRLの間の表現複雑性階層をさらに探求するため、モデルと最適ポリシーの両方を多項式サイズの定数深度回路または多項式サイズの定数層MLPで表現できる、別の一般的なMDPのクラスを導入する。
対照的に、最適値を表すのは$\mathsf{P}$-complete であり、多項式隠れ次元を持つ定数層 MLP を通して引き出すことができる。
これは、ポリシーベースのRLと比較して、値ベースのRLに関連する複雑な表現複雑性をアクセントする。
要約すると、RL内の潜在的表現複雑性階層は、モデルが最も簡単なタスクとして出現し、次に最適なポリシーが出現し、最適値関数が最も複雑な課題を示す。
関連論文リスト
- REBEL: Reinforcement Learning via Regressing Relative Rewards [59.68420022466047]
生成モデルの時代における最小限のRLアルゴリズムであるREBELを提案する。
理論的には、自然ポリシーグラディエントのような基本的なRLアルゴリズムはREBELの変種と見なすことができる。
我々はREBELが言語モデリングと画像生成に一貫したアプローチを提供し、PPOやDPOとより強くあるいは類似した性能を実現することを発見した。
論文 参考訳(メタデータ) (2024-04-25T17:20:45Z) - Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL [57.745700271150454]
モデルに基づく関数近似を用いた平均フィールドゲーム(MFG)における強化学習のサンプル複雑性について検討した。
本稿では、モデルクラスの複雑性を特徴付けるためのより効果的な概念である部分モデルベースエルダー次元(P-MBED)を紹介する。
論文 参考訳(メタデータ) (2024-02-08T14:54:47Z) - On Representation Complexity of Model-based and Model-free Reinforcement
Learning [11.843778337443824]
回路複雑性の文脈におけるモデルベースおよびモデルフリー強化学習(RL)の表現複雑性について検討した。
理論的には、その基底となる遷移関数と報酬関数が、大きさの一定深さの回路で表現できるような、幅広い種類のMDPが存在することを証明している。
近似誤差に注意を向け、複雑性理論への接続を構築することによって、モデルベースのアルゴリズムが、新しい表現複雑性の観点からモデルフリーアルゴリズムよりも、なぜサンプルの複雑さを楽しむのかというユニークな洞察を提供する。
論文 参考訳(メタデータ) (2023-10-03T00:01:58Z) - A multilevel reinforcement learning framework for PDE based control [0.2538209532048867]
強化学習(RL)は制御問題を解くための有望な方法である。
モデルフリーなRLアルゴリズムは、サンプル非効率であり、最適な制御ポリシーを学ぶために、数百万のサンプルを必要としない何千ものサンプルを必要とする。
本稿では,粗いスケールの離散化に対応するサブレベルモデルを活用することで,コストの低減を図るため,マルチレベルRLフレームワークを提案する。
論文 参考訳(メタデータ) (2022-10-15T23:52:48Z) - PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
部分的に観察可能な力学系におけるオンライン強化学習(RL)について検討する。
我々は、他のよく知られたモデルをキャプチャする表現モデルである予測状態表現(PSR)モデルに焦点を当てる。
我々は,サンプル複雑性のスケーリングにおいて,ほぼ最適なポリシを学習可能な,PSRのための新しいモデルベースアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-07-12T17:57:17Z) - Exponential Family Model-Based Reinforcement Learning via Score Matching [97.31477125728844]
有限水平表層強化学習(RL)のための楽観的モデルベースアルゴリズムSMRLを提案する。
SMRLは、リッジ回帰によるモデルパラメータの効率的な推定を可能にする非正規化密度推定手法であるスコアマッチングを用いる。
論文 参考訳(メタデータ) (2021-12-28T15:51:07Z) - Pessimistic Model-based Offline RL: PAC Bounds and Posterior Sampling
under Partial Coverage [33.766012922307084]
一般関数近似を用いたモデルに基づくオフライン強化学習について検討する。
本稿では、一般関数クラスを活用し、ペシミズムを符号化するために制約を用いる制約付きポリシー最適化(CPPO)というアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-07-13T16:30:01Z) - Bilinear Classes: A Structural Framework for Provable Generalization in
RL [119.42509700822484]
Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。
このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。
我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
論文 参考訳(メタデータ) (2021-03-19T16:34:20Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。