論文の概要: Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning

• arxiv url: http://arxiv.org/abs/2404.03774v1
• Date: Thu, 4 Apr 2024 19:35:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-08 17:35:40.851964
• Title: Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
• Title（参考訳）: 探索は予測より難しい:教師付き学習から強化学習を暗号化的に分離する
• Authors: Noah Golowich, Ankur Moitra, Dhruv Rohatgi,
• Abstract要約: 本稿では,強化学習と教師あり学習の分離を初めて示す。 また,ブロックMDPにおける報酬指向RLに対する計算効率のよいアルゴリズムは存在しないことを示す。
• 参考スコア（独自算出の注目度）: 34.791182995710024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Supervised learning is often computationally easy in practice. But to what extent does this mean that other modes of learning, such as reinforcement learning (RL), ought to be computationally easy by extension? In this work we show the first cryptographic separation between RL and supervised learning, by exhibiting a class of block MDPs and associated decoding functions where reward-free exploration is provably computationally harder than the associated regression problem. We also show that there is no computationally efficient algorithm for reward-directed RL in block MDPs, even when given access to an oracle for this regression problem. It is known that being able to perform regression in block MDPs is necessary for finding a good policy; our results suggest that it is not sufficient. Our separation lower bound uses a new robustness property of the Learning Parities with Noise (LPN) hardness assumption, which is crucial in handling the dependent nature of RL data. We argue that separations and oracle lower bounds, such as ours, are a more meaningful way to prove hardness of learning because the constructions better reflect the practical reality that supervised learning by itself is often not the computational bottleneck.
• Abstract（参考訳）: 教師付き学習は、実際は計算が簡単であることが多い。 しかし、このことは、強化学習(RL)のような他の学習方法が、拡張によって計算的に簡単であるべき、という意味なのだろうか? 本研究では,RLと教師付き学習との間の最初の暗号的分離を,報酬のない探索が関連する回帰問題よりも計算的に困難であるブロックMDPと関連する復号関数のクラスを示すことによって示す。 また、この回帰問題に対してオラクルへのアクセスを与えられた場合でも、ブロックMDPにおいて報酬指向RLの計算効率が良いアルゴリズムが存在しないことも示している。 ブロックMPPの回帰が可能であることは,適切な政策を見出す上で必要であることが知られており,その結果は十分ではないことを示唆している。 我々の分離下限は、RLデータの依存特性を扱う上で重要なLPN硬さ仮定の新たな堅牢性を利用する。 我々のような分離やオラクルの低い境界は、学習の難しさを証明するためのより意味のある方法である、と我々は主張する。

関連論文リスト

• How Can LLM Guide RL? A Value-Based Approach [68.55316627400683]
  強化学習(Reinforcement Learning, RL)は、将来の行動方針をフィードバックで改善することにより、シーケンシャルな意思決定問題の事実上の標準的実践となった。 大規模言語モデル(LLM)の最近の発展は、言語理解と生成において印象的な能力を示したが、探索と自己改善能力に欠けていた。 我々はLINVITというアルゴリズムを開発し、LLMガイダンスを値ベースRLの正規化因子として組み込んで学習に必要なデータ量を大幅に削減する。
  論文  参考訳（メタデータ） (2024-02-25T20:07:13Z)
• Hybrid Inverse Reinforcement Learning [34.793570631021005]
  逆強化学習による模倣学習は 両刃剣である。 我々は、不要な探索を抑えるために、ハイブリッドRL(オンラインデータとエキスパートデータの混合に関するトレーニング)の使用を提案する。 モデルフリーとモデルベースハイブリッド逆RLアルゴリズムの両方を導出し、強力なポリシー性能を保証する。
  論文  参考訳（メタデータ） (2024-02-13T23:29:09Z)
• The Virtues of Pessimism in Inverse Reinforcement Learning [38.98656220917943]
  逆強化学習(Inverse Reinforcement Learning)は、専門家によるデモンストレーションから複雑な振る舞いを学ぶための強力なフレームワークである。 内ループRLにおける専門家のデモンストレーションを活用することにより、探査負担を軽減することが望ましい。 我々は、IRLにおけるRLの高速化のための代替アプローチとして、Emphpessimism、すなわち、オフラインのRLアルゴリズムを用いてインスタンス化された専門家のデータ分布に近づき続けることを考える。
  論文  参考訳（メタデータ） (2024-02-04T21:22:29Z)
• The Effective Horizon Explains Deep RL Performance in Stochastic Environments [21.148001945560075]
  強化学習(Reinforcement Learning, RL)理論は、最小の複雑性サンプル境界の証明に重点を置いている。 本稿では,RLアルゴリズムSQIRLを提案する。このアルゴリズムはランダムに探索してロールアウトを収集することで,最適に近いポリシーを反復的に学習する。 我々は、SQIRLを利用して、指数的に「効果的な地平線」のルックアヘッドにのみ現れるRLのインスタンス依存のサンプル複雑性境界を導出し、近似に使用されるクラスの複雑性を導出する。
  論文  参考訳（メタデータ） (2023-12-13T18:58:56Z)
• RvS: What is Essential for Offline RL via Supervised Learning? [77.91045677562802]
  近年の研究では、時間差(TD)のない教師あり学習だけでオフラインRLに極めて効果的であることが示されている。 あらゆる環境スイートにおいて、2層フィードフォワードによる可能性の最大化は競争力がある。 彼らはまた、ランダムデータに対して比較的弱い既存のRvS法の限界を探索する。
  論文  参考訳（メタデータ） (2021-12-20T18:55:16Z)
• Exploratory State Representation Learning [63.942632088208505]
  本稿では,XSRL(eXploratory State Representation Learning)と呼ばれる新しい手法を提案する。 一方、コンパクトな状態表現と、その表現から不可解な情報を除去するために使用される状態遷移推定器を共同で学習する。 一方、逆モデルを継続的に訓練し、このモデルの予測誤差に$k$-stepの学習促進ボーナスを加え、発見ポリシーの目的を形成する。
  論文  参考訳（メタデータ） (2021-09-28T10:11:07Z)
• Simplifying Deep Reinforcement Learning via Self-Supervision [51.2400839966489]
  自己改善強化学習(Self-Supervised Reinforcement Learning, SSRL)は、純粋に監督された損失を伴うポリシーを最適化する単純なアルゴリズムである。 SSRLは、より安定した性能と実行時間の少ない現代アルゴリズムと驚くほど競合することを示す。
  論文  参考訳（メタデータ） (2021-06-10T06:29:59Z)
• DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction [96.90215318875859]
  ブートストラップに基づくQ-ラーニングアルゴリズムは必ずしも修正フィードバックの恩恵を受けないことを示す。 本稿では,この最適分布に対する近似を計算し,トレーニングに使用する遷移の重み付けに使用する新しいアルゴリズムであるDisCorを提案する。
  論文  参考訳（メタデータ） (2020-03-16T16:18:52Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。 本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-15T19:23:59Z)

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

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