mlsanityData to 7 Oct 2026

Theoretical Foundations of max@k Reinforcement Learning

arXiv 2607.17823 ↗First posted 20 Jul 2026cs.LGcited by 0

On the map: LLM reasoning → Reinforcement learning for reasoning

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 60 of its 74 references that are in the map. First posted on arXiv 20 Jul 2026.

Builds on

60 of 74 references.

Closest ancestors · 8

Same direction, newest first

  1. 2026On Advantage Estimates for Max@K Policy Gradients4 Jun
  2. 2026Learning to Correct: Calibrated Reinforcement Learning for Multi-Attempt Chain-of-Thought20 Apr
  3. 2025Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Models14 Aug
  4. 2025The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models28 May
  5. 2025Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning26 May
  6. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?18 Apr
  7. 2024Tulu 3: Pushing Frontiers in Open Language Model Post-Training22 Nov
  8. 2023Let's Verify Step by Step31 May

Other references · 52

  1. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  2. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  3. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  4. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,064
  5. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,317
  6. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  7. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  8. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 946
  9. 2022STaR: Bootstrapping Reasoning With Reasoningcited by 895
  10. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 873
  11. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  12. 2017Distributional Reinforcement Learning with Quantile Regressioncited by 464
38 more
  1. 2023Chain-of-Verification Reduces Hallucination in Large Language Modelscited by 317
  2. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  3. 2024Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learningcited by 238
  4. 2024DeepSeek-Prover: Advancing Theorem Proving in LLMs through Large-Scale Synthetic Datacited by 225
  5. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 183
  6. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  7. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  8. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  9. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  10. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  11. 2014Algorithms for CVaR Optimization in MDPscited by 98
  12. 2024Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Modelscited by 86
  13. 2025Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problemscited by 83
  14. 2021Reward is enough for convex MDPscited by 82
  15. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  16. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 57
  17. 2025Optimizing Language Models for Inference Time Objectives using Reinforcement Learningcited by 49
  18. 2019Reinforcement Learning with Non-Markovian Rewardscited by 45
  19. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  20. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  21. 2025Recursive Self-Aggregation Unlocks Deep Thinking in Large Language Modelscited by 30
  22. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 29
  23. 2022Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 26
  24. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  25. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  26. 2026Advancing Mathematics Research with AI-Driven Formal Proof Searchcited by 18
  27. 2025The Best of N Worlds: Aligning Reinforcement Learning with Best-of-N Sampling via max@k Optimisationcited by 16
  28. 2015No Regret Bound for Extreme Banditscited by 8
  29. 2023Estimation and Inference in Distributional Reinforcement Learningcited by 8
  30. 2017Max K-armed bandit: On the ExtremeHunter algorithm and beyondcited by 7
  31. 2023Risk-sensitive Markov Decision Process and Learning under General Utility Functionscited by 7
  32. 2024Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Modelcited by 7
  33. 2026Goedel-Architect: Streamlining Formal Theorem Proving with Blueprint Generation and Refinementcited by 7
  34. 2022Policy Gradient for Reinforcement Learning with General Utilitiescited by 6
  35. 2026Regret Analysis of Retry-Based Banditscited by 4
  36. 2026MaxProof: Scaling Mathematical Proof with Generative-Verifier RL and Population-Level Test-Time Scalingcited by 4
  37. 2022Efficient Algorithms for Extreme Banditscited by 2
  38. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processescited by 1

50 most cited of 52 All 52 (JSON)

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Maximum Likelihood Reinforcement Learning
  2. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  3. 2026Fast Rates for Inverse Reinforcement Learning
  4. 2026Towards Optimal Policy Improvement
  5. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
  6. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
  7. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  8. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons