論文の概要: Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2502.08632v1
• Date: Wed, 12 Feb 2025 18:47:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-13 13:44:45.257560
• Title: Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
• Title（参考訳）: 必要かつ十分なオラクル:強化学習のための計算分類学を目指して
• Authors: Dhruv Rohatgi, Dylan J. Foster,
• Abstract要約: 本稿では,教師付き学習オラクルの選択が強化学習アルゴリズムの計算複雑性に与える影響について検討する。 まず、標準的なエピソード・アクセス・モデルにおいて、2コンテキスト回帰を最小のオラクルとみなす。 第二に、より強いリセットアクセスモデルにおいて、一文回帰を最小に近いオラクルとみなす。 第3に、我々はLow-Rank MDPに焦点を絞り、Block MDP設定の類似のオラクルが不十分であることを示す暗号的証拠を与えます。
• 参考スコア（独自算出の注目度）: 28.184175745050474
• License:
• Abstract: Algorithms for reinforcement learning (RL) in large state spaces crucially rely on supervised learning subroutines to estimate objects such as value functions or transition probabilities. Since only the simplest supervised learning problems can be solved provably and efficiently, practical performance of an RL algorithm depends on which of these supervised learning "oracles" it assumes access to (and how they are implemented). But which oracles are better or worse? Is there a minimal oracle? In this work, we clarify the impact of the choice of supervised learning oracle on the computational complexity of RL, as quantified by the oracle strength. First, for the task of reward-free exploration in Block MDPs in the standard episodic access model -- a ubiquitous setting for RL with function approximation -- we identify two-context regression as a minimal oracle, i.e. an oracle that is both necessary and sufficient (under a mild regularity assumption). Second, we identify one-context regression as a near-minimal oracle in the stronger reset access model, establishing a provable computational benefit of resets in the process. Third, we broaden our focus to Low-Rank MDPs, where we give cryptographic evidence that the analogous oracle from the Block MDP setting is insufficient.
• Abstract（参考訳）: 大規模状態空間における強化学習(RL)のためのアルゴリズムは、値関数や遷移確率などのオブジェクトを推定するために、教師付き学習サブルーチンに依存している。 最も単純な教師付き学習問題が証明可能かつ効率的に解けるため、RLアルゴリズムの実践的な性能は、教師付き学習のどれがアクセス可能か(そしてどのように実装されるか)に依存する。 しかし、どのオラクルの方が良いか悪いか? 最小限のオラクルはありますか? 本研究では,教師付き学習オラクルの選択がRLの計算複雑性に与える影響を明らかにする。 まず、関数近似を持つRLのユビキタスな設定である標準エピソードアクセスモデルにおけるブロックMDPの報酬のない探索のタスクにおいて、2コンテキスト回帰を最小のオラクル、すなわち必要かつ十分なオラクル(軽度な正規性仮定の下で)として識別する。 第二に、より強力なリセットアクセスモデルにおいて、一文回帰を最小に近いオラクルとみなし、そのプロセスにおけるリセットの計算上の利点を証明できる。 第3に、我々はLow-Rank MDPに焦点を絞り、Block MDP設定の類似のオラクルが不十分であることを示す暗号的証拠を与えます。

関連論文リスト

• Fuzzy Logic Guided Reward Function Variation: An Oracle for Testing Reinforcement Learning Programs [2.871991859211386]
  本稿では,ファジィ論理を用いたRL特性を利用した自動オラクル手法を提案する。 我々のオラクルは、エージェントの行動コンプライアンスと報酬ポリシーを定量化し、トレーニングエピソードの傾向を分析します。 コンプライアンス傾向がRL特性に由来する期待に反した場合、RLプログラムを"バギー"とラベル付けする。
  論文  参考訳（メタデータ） (2024-06-28T10:41:17Z)
• Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'? [26.334900941196082]
  本研究では,与えられたデータセットに対する経験的リスクを最小化する仮説を計算したERMの実行能力が,効率的な学習に必要かどうかを検討する。 バイナリ分類のためのPACの実際の設定において、概念クラスは1ビットしか返さないオラクルを用いて学習可能であることを示す。 また,本研究の結果は,オラクルを少し強化した学習環境や,部分的な概念,マルチクラス,実価値の学習環境にまで及んでいる。
  論文  参考訳（メタデータ） (2024-06-17T15:50:08Z)
• REBEL: Reinforcement Learning via Regressing Relative Rewards [59.68420022466047]
  生成モデルの時代における最小限のRLアルゴリズムであるREBELを提案する。 理論的には、自然ポリシーグラディエントのような基本的なRLアルゴリズムはREBELの変種と見なすことができる。 我々はREBELが言語モデリングと画像生成に一貫したアプローチを提供し、PPOやDPOとより強くあるいは類似した性能を実現することを発見した。
  論文  参考訳（メタデータ） (2024-04-25T17:20:45Z)
• The Power of Resets in Online Reinforcement Learning [73.64852266145387]
  ローカルシミュレータアクセス(あるいはローカルプランニング)を用いたオンライン強化学習を通してシミュレータのパワーを探求する。 カバー性が低いMPPは,Qstar$-realizabilityのみのサンプル効率で学習可能であることを示す。 ローカルシミュレーターアクセス下では, 悪名高いExogenous Block MDP問題が抽出可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T18:09:53Z)
• Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning [34.791182995710024]
  本稿では,強化学習と教師あり学習の分離を初めて示す。 また,ブロックMDPにおける報酬指向RLに対する計算効率のよいアルゴリズムは存在しないことを示す。
  論文  参考訳（メタデータ） (2024-04-04T19:35:41Z)
• How Can LLM Guide RL? A Value-Based Approach [68.55316627400683]
  強化学習(Reinforcement Learning, RL)は、将来の行動方針をフィードバックで改善することにより、シーケンシャルな意思決定問題の事実上の標準的実践となった。 大規模言語モデル(LLM)の最近の発展は、言語理解と生成において印象的な能力を示したが、探索と自己改善能力に欠けていた。 我々はLINVITというアルゴリズムを開発し、LLMガイダンスを値ベースRLの正規化因子として組み込んで学習に必要なデータ量を大幅に削減する。
  論文  参考訳（メタデータ） (2024-02-25T20:07:13Z)
• Statistical curriculum learning: An elimination algorithm achieving an oracle risk [31.997825444285457]
  パラメトリックな予測設定において,カリキュラム学習(CL)の統計版を考える。 学習者は,受取側の情報レベルに応じて,3種類の学習者について検討する。
  論文  参考訳（メタデータ） (2024-02-20T20:44:40Z)
• Online Iterative Reinforcement Learning from Human Feedback with General Preference Model [20.81421550138371]
  本稿では,人間のフィードバックからの強化学習(RLHF)について,一般的な嗜好のオラクルの文脈で検討する。 我々は、RLHFの2つのLLM間の逆KL正規化ミニマックスゲームである標準的な数学的定式化を考える。 このフレームワークは報酬ベースよりも厳密に汎用的であり,事前選択された選好データセットからオフライン学習を行うためのサンプル効率のよいアルゴリズムとオンライン学習を提案する。
  論文  参考訳（メタデータ） (2024-02-11T21:44:21Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  本稿では,値関数近似を用いたオフラインRLにおけるモデル選択の問題について検討する。 対数係数まで最小値の速度-最適不等式を実現するオフラインRLの最初のモデル選択アルゴリズムを提案する。 そこで本研究では,優れたモデルクラスを確実に選択できることを示す数値シミュレーションを行った。
  論文  参考訳（メタデータ） (2022-11-03T17:32:34Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)

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

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