論文の概要: Theoretical Foundations of $\max$@$k$ Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2607.17823v1
• Date: Mon, 20 Jul 2026 11:11:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-21 18:48:37.60122
• Title: Theoretical Foundations of $\max$@$k$ Reinforcement Learning
• Title（参考訳）: $\max$@$k$強化学習の理論的基礎
• Authors: Riccardo Poiani, Martino Bernasconi, Andrea Celli,
• Abstract要約: 有限水平強化学習における$max$@$k$学習問題に関する理論的研究を行う。 我々は、$max$@$k$の目的を最適化することは、標準の期待-返却目標と根本的に異なることを示す。 また、$max$$$k$-optimal Policyの学習は、標準的な強化学習よりも統計的に難しいことも示している。
• 参考スコア（独自算出の注目度）: 21.43014756831114
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement Learning is a cornerstone technique for modern large reasoning models. Usually, for difficult tasks such as code generation and theorem proving, the agent is evaluated by generating $K$ responses rather than sampling a single response, and performance is then measured using a retry-aware metric such as $\max$@$k$. Despite their practical importance, the theoretical foundations of learning under such criteria remain limited. In this work, we provide a theoretical study of the $\max$@$k$ learning problem in finite-horizon reinforcement learning. We show that optimizing the $\max$@$k$ objectives is fundamentally different from standard expected-return maximization. In particular, we prove that Markovian policies are in general insufficient, identify a compact state augmentation that restores optimality, and explicitly characterize the performance gap that can arise between history-dependent and non-history-dependent policies. Moreover, we show that learning $\max$@$k$-optimal policies is statistically harder than standard reinforcement learning and provide an efficient algorithm that achieves the optimal sample complexity rate.
• Abstract（参考訳）: 強化学習(Reinforcement Learning)は、現代の大規模推論モデルの基盤となるテクニックである。 通常、コード生成や定理証明のような難しいタスクでは、エージェントは単一のレスポンスをサンプリングするのではなく、$K$レスポンスを生成して評価され、そのパフォーマンスは$\max$@$k$のようなリトライ対応のメトリクスを使って測定される。 その実践的重要性にもかかわらず、そのような基準の下での学習の理論的基礎は限定的である。 本研究では,有限水平強化学習における$\max$$$$k$学習問題に関する理論的研究を行う。 我々は、$\max$@$k$の目的を最適化することは、標準期待値の最大化と根本的に異なることを示す。 特に,マルコフ政策は一般に不十分であることを示すとともに,最適性を回復するコンパクトな状態拡張を同定し,歴史に依存しない政策と歴史に依存しない政策の間に生じるパフォーマンスギャップを明示的に特徴付ける。 さらに,最大$$$$k$-optimal Policyの学習は,標準強化学習よりも統計的に難しいことを示し,最適なサンプル複雑性率を達成する効率的なアルゴリズムを提供する。

関連論文リスト

• On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents [2.4145441422386464]
  有限割引MDPにおけるリスク感応性強化学習について検討した。 我々は、最適化確実性等価(OCE)と呼ばれる家族またはリスク対策を考える。
  論文  参考訳（メタデータ） (2026-05-20T21:53:51Z)
• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  政策学習における強化学習について検討する。 目的は、特定の種類の利害関係において最高の政策と競争力のある政策を見つけることである。
  論文  参考訳（メタデータ） (2025-07-06T14:40:05Z)
• Response-Level Rewards Are All You Need for Online Reinforcement Learning in LLMs: A Mathematical Perspective [6.069069082518759]
  大規模言語モデル(LLM)の強化学習におけるゼロ・リワード推定について検討する。 反応レベル報酬モデルのみを用いて、真で未知のトークンレベルの報酬に基づくポリシー勾配を不偏に推定できることを示す。 我々は,新しいアルゴリズム,Token-Reinforced Policy Optimization (TRePO)を提案する。
  論文  参考訳（メタデータ） (2025-06-03T07:44:31Z)
• Agnostic Reinforcement Learning: Foundations and Algorithms [4.07926531936425]
  この論文は、学習理論の観点から関数近似を伴うRLの統計的複雑さを厳密に検証する。 学習者は与えられたクラス$Pi$の最良のポリシーを見つけようとするが、$Pi$が基礎となるタスクに対して最適なポリシーを含んでいるという保証はない。 この包括的枠組みの中で、理論的な保証付き新しい学習アルゴリズムを設計し、任意のアルゴリズムの基本性能境界を特徴づける。
  論文  参考訳（メタデータ） (2025-06-02T17:12:24Z)
• Accelerating RL for LLM Reasoning with Optimal Advantage Regression [52.0792918455501]
  本稿では,最適優位関数を直接近似する新しい2段階ポリシー最適化フレームワークを提案する。 A$*-POは、幅広い数学的推論ベンチマークで競合性能を達成する。 PPO、GRPO、REBELと比較して、トレーニング時間を最大2$times$、ピークメモリ使用率を30%以上削減する。
  論文  参考訳（メタデータ） (2025-05-27T03:58:50Z)
• Reinforced Latent Reasoning for LLM-based Recommendation [92.56166822197919]
  大きな言語モデル(LLM)は、複雑な問題解決タスクにおいて印象的な推論能力を示している。 既存の手法は通常、明示的なチェーン・オブ・シント(CoT)データによる微調整に依存している。 本研究では, 明示的なCoT推論から, コンパクトで情報密度の高い潜伏推論へ移行する代替手法について検討する。
  論文  参考訳（メタデータ） (2025-05-25T11:03:45Z)
• Provably Sample-Efficient Robust Reinforcement Learning with Average Reward [4.530028899565083]
  本稿では,$ell_p$-normと汚染モデルにより特徴付けられる遷移不確実性を持つロバストなマルコフ決定過程(MDP)を設計した新しいアルゴリズムを提案する。 我々のアルゴリズムは、頑健なMDPの事前知識を必要とせずに動作する。 我々の研究は、ロバスト平均報酬RLのサンプル効率の基本的な理論的理解を提供する。
  論文  参考訳（メタデータ） (2025-05-18T15:34:45Z)
• Supervised Optimism Correction: Be Confident When LLMs Are Sure [91.7459076316849]
  教師付き微調整とオフライン強化学習の間には,新たな理論的関係が確立されている。 広く使われているビームサーチ法は、許容できない過度な最適化に悩まされていることを示す。 本稿では,トークンレベル$Q$-value推定のための簡易かつ効果的な補助的損失を導入したSupervised Optimism Correctionを提案する。
  論文  参考訳（メタデータ） (2025-04-10T07:50:03Z)
• Oracle-Efficient Reinforcement Learning for Max Value Ensembles [7.404901768256101]
  大または無限の状態空間における強化学習(RL)は、理論上、実験的に困難である。 この作業では、$textitmax-following Policy$と競合することを目指しています。 我々の主な成果は、構成ポリシーのみにアクセスすると、最大フォローポリシーと競合する効率的なアルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-27T01:08:23Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  線形関数近似による強化学習と,コスト関数の逆変化について検討した。 本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T17:26:39Z)

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

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