Theoretical Foundations of $\max$@$k$ Reinforcement Learning

• URL: http://arxiv.org/abs/2607.17823v1
• Date: Mon, 20 Jul 2026 11:11:55 GMT
• Title: Theoretical Foundations of $\max$@$k$ Reinforcement Learning
• Abstract summary: We provide a theoretical study of the $max$@$k$ learning problem in finite-horizon reinforcement learning.<n>We show that optimizing the $max$@$k$ objectives is fundamentally different from standard expected-return objectives.<n>We also show that learning $max$@$k$-optimal policies is statistically harder than standard reinforcement learning.
• Score: 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.

Related papers

• $β$-OPSD: Deriving with Policy Optimization, Training with Self-Distillation [85.07190808882523]
  On-policy self-distillation is a promising approach to improve reasoning language models.<n>We show that $$-OPSD consistently outperforms vanilla OPSD.
  arXiv  Detail & Related papers  (2026-07-30T17:41:16Z)
• On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents [2.4145441422386464]
  We study risk-sensitive reinforcement learning in finite discounted MDPs.<n>We consider a family or risk measures called the optimized certainty equivalent (OCE)
  arXiv  Detail & Related papers  (2026-05-20T21:53:51Z)
• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  We study reinforcement learning in the policy learning setting.<n>The goal is to find a policy whose performance is competitive with the best policy in a given class of interest.
  arXiv  Detail & Related papers  (2025-07-06T14:40:05Z)
• Response-Level Rewards Are All You Need for Online Reinforcement Learning in LLMs: A Mathematical Perspective [6.069069082518759]
  We study the Zero-Reward Assumption in reinforcement learning for large language models (LLMs)<n>We show that the policy gradient based on true, unknown token-level rewards can be unbiasedly estimated using only a response-level reward model.<n>We propose a new algorithm: Token-Reinforced Policy Optimization (TRePO)
  arXiv  Detail & Related papers  (2025-06-03T07:44:31Z)
• Agnostic Reinforcement Learning: Foundations and Algorithms [4.07926531936425]
  This thesis rigorously examines the statistical complexity of RL with function approximation from a learning theoretic perspective.<n>We explore agnostic policy learning, in which the learner seeks to find the best policy in a given class $Pi$, with no guarantee that $Pi$ contains an optimal policy for the underlying task.<n>Within this comprehensive framework, we design new learning algorithms with theoretical guarantees and characterize fundamental performance bounds of any algorithm.
  arXiv  Detail & Related papers  (2025-06-02T17:12:24Z)
• Accelerating RL for LLM Reasoning with Optimal Advantage Regression [52.0792918455501]
  We propose a novel two-stage policy optimization framework that directly approximates the optimal advantage function.<n>$A$*-PO achieves competitive performance across a wide range of mathematical reasoning benchmarks.<n>It reduces training time by up to 2$times$ and peak memory usage by over 30% compared to PPO, GRPO, and REBEL.
  arXiv  Detail & Related papers  (2025-05-27T03:58:50Z)
• Reinforced Latent Reasoning for LLM-based Recommendation [92.56166822197919]
  Large Language Models (LLMs) have demonstrated impressive reasoning capabilities in complex problem-solving tasks.<n>Existing methods typically rely on fine-tuning with explicit chain-of-thought (CoT) data.<n>In this work, we explore an alternative approach that shifts from explicit CoT reasoning to compact, information-dense latent reasoning.
  arXiv  Detail & Related papers  (2025-05-25T11:03:45Z)
• Provably Sample-Efficient Robust Reinforcement Learning with Average Reward [4.530028899565083]
  We propose a new algorithm designed for robust Markov Decision Processes (MDPs) with transition uncertainty characterized by $ell_p$-norm and contamination models.<n>Our algorithm operates without requiring any prior knowledge of the robust MDP.<n>Our work provides essential theoretical understanding of sample efficiency of robust average reward RL.
  arXiv  Detail & Related papers  (2025-05-18T15:34:45Z)
• Supervised Optimism Correction: Be Confident When LLMs Are Sure [91.7459076316849]
  We establish a novel theoretical connection between supervised fine-tuning and offline reinforcement learning.<n>We show that the widely used beam search method suffers from unacceptable over-optimism.<n>We propose Supervised Optimism Correction, which introduces a simple yet effective auxiliary loss for token-level $Q$-value estimations.
  arXiv  Detail & Related papers  (2025-04-10T07:50:03Z)
• Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method [53.170053108447455]
  Ensemble learning is a method that leverages weak learners to produce a strong learner. We design a smooth and convex objective function that leverages the concept of margin, making the strong learner more discriminative. We then compare our algorithm with random forests of ten times the size and other classical methods across numerous datasets.
  arXiv  Detail & Related papers  (2024-08-06T03:42:38Z)
• Oracle-Efficient Reinforcement Learning for Max Value Ensembles [7.404901768256101]
  Reinforcement learning (RL) in large or infinite state spaces is notoriously challenging, theoretically and experimentally. In this work we aim to compete with the $textitmax-following policy$, which at each state follows the action of whichever constituent policy has the highest value. Our main result is an efficient algorithm that learns to compete with the max-following policy, given only access to the constituent policies.
  arXiv  Detail & Related papers  (2024-05-27T01:08:23Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  We study reinforcement learning with linear function approximation and adversarially changing cost functions. We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback.
  arXiv  Detail & Related papers  (2023-01-30T17:26:39Z)
• Average Reward Adjusted Discounted Reinforcement Learning: Near-Blackwell-Optimal Policies for Real-World Applications [0.0]
  Reinforcement learning aims at finding the best stationary policy for a given Markov Decision Process. This paper provides deep theoretical insights to the widely applied standard discounted reinforcement learning framework. We establish a novel near-Blackwell-optimal reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2020-04-02T08:05:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.