論文の概要: Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation

• arxiv url: http://arxiv.org/abs/2509.25849v1
• Date: Tue, 30 Sep 2025 06:41:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-01 17:09:04.457299
• Title: Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation
• Title（参考訳）: Knapsack RL: 予算配分最適化によるLCMのアンロック
• Authors: Ziniu Li, Congliang Chen, Tianyun Yang, Tian Ding, Ruoyu Sun, Ge Zhang, Wenhao Huang, Zhi-Quan Luo,
• Abstract要約: 大規模言語モデル(LLM)は強化学習を通じて自己改善が可能で、より良いソリューションを探求し発見するための軌道を生成する。 この探索プロセスは計算コストが高く、しばしば現在の手法では各タスクに限られた探査予算を割り当てざるを得ない。 本稿では,モデルの現在の学習状況に基づいて資源を適応的に分配する最適割当てルールを提案する。
• 参考スコア（独自算出の注目度）: 40.30643197563909
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) can self-improve through reinforcement learning, where they generate trajectories to explore and discover better solutions. However, this exploration process is computationally expensive, often forcing current methods to assign limited exploration budgets to each task. This uniform allocation creates problematic edge cases: easy tasks consistently succeed while difficult tasks consistently fail, both producing zero gradients during training updates for the widely used Group Relative Policy Optimization (GRPO). We address this problem from the lens of exploration budget allocation. Viewing each task's exploration as an "item" with a distinct "value" and "cost", we establish a connection to the classical knapsack problem. This formulation allows us to derive an optimal assignment rule that adaptively distributes resources based on the model's current learning status. When applied to GRPO, our method increases the effective ratio of non-zero policy gradients by 20-40% during training. Acting as a computational "free lunch", our approach could reallocate exploration budgets from tasks where learning is saturated to those where it is most impactful. This enables significantly larger budgets (e.g., 93 rollouts) for especially challenging problems, which would be computationally prohibitive under a uniform allocation. These improvements translate to meaningful gains on mathematical reasoning benchmarks, with average improvements of 2-4 points and peak gains of 9 points on specific tasks. Notably, achieving comparable performance with traditional homogeneous allocation would require about 2x the computational resources.
• Abstract（参考訳）: 大規模言語モデル(LLM)は強化学習を通じて自己改善が可能で、より良いソリューションを探求し発見するための軌道を生成する。 しかし、この探索プロセスは計算コストが高く、しばしば現在の方法では各タスクに限られた探査予算を割り当てざるを得ない。 難しいタスクは一貫して失敗し、どちらも広く使用されているグループ相対ポリシー最適化(GRPO)のトレーニングアップデート中にゼロ勾配を生成します。 調査予算配分のレンズからこの問題に対処する。 各タスクの探索を、異なる「価値」と「コスト」を持つ「イテム」とみなし、古典的なknapsack問題とのつながりを確立する。 この定式化により、モデルの現在の学習状況に基づいてリソースを適応的に分配する最適な割り当てルールを導出できる。 GRPOに適用した場合、トレーニング中の非ゼロポリシー勾配の有効比率を20～40%増加させる。 フリーランチ」として機能することで、我々のアプローチは、学習が最も影響力のあるタスクに飽和しているタスクから探索予算を割り当てることができます。 これにより、特に困難な問題に対してはるかに大きな予算(例:93ロールアウト)が実現され、均一な割り当てでは計算が禁止される。 これらの改善は、数学的推論ベンチマークにおいて有意義な利得をもたらし、2-4点の平均的な改善と、特定のタスクで9点のピーク利得となる。 特に、従来の均質な割り当てで同等のパフォーマンスを達成するには、計算資源の約2倍が必要になる。

関連論文リスト

• Train Long, Think Short: Curriculum Learning for Efficient Reasoning [51.506559652495476]
  長さ制御推論のためのカリキュラム学習戦略を提案する。 当社の手法は寛大なトークン予算から始まり、トレーニングをしながら徐々に厳格化します。 GSM8K、MATH500、SVAMP、College Math、GSM+の実験は、カリキュラムベースのトレーニングが固定予算ベースラインを一貫して上回ることを示した。
  論文  参考訳（メタデータ） (2025-08-12T13:48:03Z)
• ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning [54.08906841213777]
  非同期手法は分散機械学習における計算の並列化の基礎となる。 本稿では,不均一かつランダムな計算時間分布に適応するATA(Adaptive Task Allocation)を提案する。 ATAは最適なタスク割り当てを識別し、計算時間に関する事前の知識を持つメソッドと互換性があることを示す。
  論文  参考訳（メタデータ） (2025-02-02T12:22:26Z)
• Sample Efficient Reinforcement Learning by Automatically Learning to Compose Subtasks [3.1594865504808944]
  サブタスクを表すラベルのセットを与えられた場合、サンプル効率のために報酬関数を自動的に構成するRLアルゴリズムを提案する。 我々は,様々なスパース・リワード環境におけるアルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2024-01-25T15:06:40Z)
• Explore to Generalize in Zero-Shot RL [38.43215023828472]
  本研究では,強化学習におけるゼロショットの一般化について検討する。 提案手法は,Mazeタスクが83%,Heistが74%,トレーニングレベルが200ドルという,極めて効果的な一般化を実現したProcGen課題のタスクの最先端技術であることを示す。
  論文  参考訳（メタデータ） (2023-06-05T17:49:43Z)
• Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation [16.871660060209674]
  本研究では, 線形関数近似を用いた展開効率向上強化学習(RL)の課題を, 遠近自由探索条件下で検討する。 我々は,最大$widetildeO(fracd2H5epsilon2)$ trajectoriesを$H$デプロイメント内で収集し,$epsilon$-Optimal Policyを任意の(おそらくはデータに依存した)報酬関数の選択に対して識別するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-03T03:48:26Z)
• MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learning [65.52675802289775]
  本研究では,不確かさを意識した分類器が,強化学習の難しさを解消できることを示す。 正規化最大度(NML)分布の計算法を提案する。 得られたアルゴリズムは、カウントベースの探索法と、報酬関数を学習するための先行アルゴリズムの両方に多くの興味深い関係を持つことを示す。
  論文  参考訳（メタデータ） (2021-07-15T08:19:57Z)

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

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