Pith. sign in

REVIEW 2 major objections 4 minor 72 references

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

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Learning to maximize the best of K rollouts costs a factor K more samples than standard reinforcement learning.

desk verdict Genuinely useful theory for max@k RL, and the planning half holds up; but the lower-bound construction in Theorem 3 is broken as written, so the headline sample-complexity claim needs a repair before it can be relied on. read the letter →

arxiv 2607.17823 v1 pith:OB6QXQEW submitted 2026-07-20 cs.LG

Riccardo Poiani , Martino Bernasconi , Andrea Celli This is my paper · ORCID
classification cs.LG
keywords max@kreinforcementlearningfinite-horizonMDPhistory-dependentpoliciesstateaugmentationsamplecomplexitygenerativemodelplanninghardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

max@k reinforcement learning evaluates an agent by the best return among $K$ rollouts rather than by the return of a single trajectory. The paper establishes that this retry-aware objective changes the problem in a fundamental way: Markovian policies can be strictly suboptimal, and learning an $\epsilon$-optimal policy from a generative model requires $\Theta(K H^3 S A / \epsilon^2)$ samples up to logarithmic factors, a factor $K$ more than classical RL. The mechanism that keeps the problem tractable is a compact memory: optimal policies need only remember the best return from previous rollouts and the cumulative reward inside the current rollout. With that compression, near-optimal planning can be done in polynomial time by discretizing rewards, even though exact planning is NP-hard. A reader should care because best-of-$K$ evaluation is how many reasoning and code-generation systems are scored, and this paper says optimizing the criterion directly is both necessary and achievable at a precisely quantified statistical cost.

What carries the argument

The load-bearing object is the compressed history $\Phi(H_{h,i})=(s_{h,i}, M_i, G_{h,i})$, where $M_i$ is the maximum reward collected in rollouts $1,\dots,i-1$ and $G_{h,i}$ is the cumulative reward gathered in rollout $i$ up to step $h$. The paper proves that value functions and optimality equations factor through this triple, so the search can be restricted to $\Pi_C$ policies. The planning FPTAS then discretizes the reward interval $[0,1]$ onto a grid of $O(H/\kappa)$ points, making both $M$ and $G$ finite sets of size $O(H/\kappa)$ and reducing backward induction to polynomial time. The learning upper bound combines this discretized Bellman solve with a uniform-sampling estimate of the transition kernel, while the lower bound is driven by a family of MDPs in which a good action succeeds with small probability $p$; because a single success among $K$ rollouts can decide the max@k value, an $(\epsilon,\delta)$-correct learner must place large total probability mass on the good action across all rollouts, forcing the extra factor $K$.

What would settle it

Enumerate all deterministic $\Pi_C$ policies on the two-rollout MDP of Proposition 3: the paper predicts the optimal max@k value is $42/32$. Any value below $42/32$ disproves the compression claim. Alternatively, on the hard instance family of Theorem 3, any $(\epsilon,\delta)$-correct algorithm that always stops with $o(K H^3 S A \epsilon^{-2} \log(\delta^{-1}))$ samples would disprove the claimed minimax rate.

Watch

Extended reading notes

Core claim

The paper's central claim is that the max@k objective, the expected value of the best of $K$ independent horizon-$H$ rollouts, is not an expected-reward problem in disguise. It proves that Markovian policies are insufficient: there are MDPs in which the best history-dependent policy beats every Markovian policy by a factor of at least $1.24 - O(1/K)$. It then shows that full history dependence is unnecessary, because the optimal value is attained by policies in $\Pi_C$, i.e., policies that condition only on the current state $s_{h,i}$, the previous best return $M_i$, and the cumulative return $G_{h,i}$ in the current rollout. Planning from this compressed representation admits a polynomial-time approximation scheme via uniform reward discretization, while exact planning is NP-hard through a reduction from Subset-Sum. For learning, the paper proves matching lower and upper bounds of order $K H^3 S A / \epsilon^2$ (up to logs) in the small-$\epsilon$ regime for the time-homogeneous generative-model setting, with an additional $H$ for time-inhomogeneous MDPs; this is exactly $K$ times the classical finite-horizon RL rate, and it is achieved by uniform sampling followed by backward induction on the empirical discretized model.

Load-bearing premise

The whole argument rests on Proposition 2's compression claim: that no optimality is lost by restricting to policies that depend only on the current state, the best return from previous rollouts, and the cumulative reward of the current rollout; if that is false, both the efficient planning algorithm and the sample-complexity upper bound solve the wrong problem.

Editorial extensions

If this is right

  • Any pipeline that trains on expected single-trajectory reward and then evaluates by best-of-$K$ is provably leaving performance on the table; the max@k objective itself is the right training target.
  • History-dependent max@k planning is not computationally hopeless: an $\epsilon$-optimal policy can be computed in time polynomial in $K$, $S$, $A$, $H$, and $1/\epsilon$, so the extra memory carries only a mild computational cost.
  • Exact max@k planning is NP-hard even when the required decision gap is exponentially small, so approximation is unavoidable in the worst case.
  • With a generative model, the minimax sample complexity is $\Theta(K H^3 S A / \epsilon^2)$ up to logarithms: retry-aware goals are $K$ times harder to learn, and time-inhomogeneous dynamics add another factor $H$.
  • The $K=1$ case recovers the classical finite-horizon RL rate, so the framework is a consistent generalization rather than a separate theory.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's compression suggests a concrete recipe for value-based RL in reasoning tasks: augment the state with (previous best return, current cumulative reward) and run standard DP or Q-learning on that augmented state; the theory predicts this should dominate policies that ignore either coordinate.
  • The $K$ factor in the lower bound indicates that retry-aware learning should oversample rare, high-payoff branches, because one success out of $K$ attempts can determine the objective; this is a testable design principle for exploration in best-of-$K$ training.
  • The 1.24 multiplicative Markovian gap implies that independent best-of-$K$ sampling, even with a well-trained policy, is suboptimal relative to adaptive generation; a natural extension is to quantify how much adaptivity can help in realistic reasoning environments beyond the constructed worst-case MDP.
  • The planning hardness result suggests that practical max@k algorithms should target approximate solutions; it also leaves open whether a PSPACE-completeness characterization holds, which the paper explicitly flags as future work.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the max@k objective in finite-horizon reinforcement learning, where the agent is evaluated by the expected best reward over K rollouts from the same initial state. It claims three main results: (i) Markovian policies are generally suboptimal for max@k, and optimal policies can be restricted to a compressed class Π_C that conditions only on the current state, the previous best return M, and the cumulative reward G in the current rollout (Propositions 1–3); (ii) an epsilon-optimal history-dependent policy can be computed in time polynomial in the problem parameters and 1/epsilon (Theorem 1), while exact planning is NP-hard (Theorem 2); and (iii) the minimax sample complexity for PAC learning under a generative model is Θ(K H^3 S A / ε^2) up to log factors, established by a lower bound Ω(KH^3SAε^{-2}log(1/δ)) (Theorem 3) and a matching upper bound Õ(KSAH^3ε^{-2}log(1/δ)) (Theorem 4). The upper-bound algorithm samples each state-action pair uniformly, builds an empirical model, discretizes rewards, and plans in the compressed state space.

Significance. If the claims hold, the paper would be the first to give a tight minimax sample-complexity characterization for a retry-aware objective in finite-horizon MDPs, and it would rigorously quantify how max@k evaluation changes the learning problem relative to standard expected-return RL. The structural compression result (Proposition 2) is attractive and potentially useful beyond the exact setting, since it isolates the memory that an optimal reasoning-agent policy must keep across attempts. The planning FPTAS and the NP-hardness result are also meaningful, and the refined simulation analysis in the upper-bound proof (Lemmas 5–7) contains a variance bound that is specific to the max@k structure and is not obtained by a naive reduction to a KH-horizon MDP. These contributions justify serious interest in the paper, conditional on the correctness of the lower-bound construction and the rigor of the compressed-state optimality proof.

major comments (2)
  1. [Appendix B.1, Theorem 3] The lower-bound instance is internally inconsistent. Step 1 defines r(s_i,a)=1 for every non-goal state and r(g,a)=1 for the goal, so every length-H trajectory has total reward exactly H in the base instance M0 and in every alternative instance M_{s,a}. Consequently the max@K objective is identically H for every policy, and no (ε,δ)-correct algorithm can be forced to pay samples to distinguish the instances. The proof's Step 2 claims V⋆_{h+,i+}(g) ≥ 3H/4 while V⋆_{h+,i+}(s) ≤ H/64, but with the stated rewards both quantities are H. The footnote asserting that cumulative reward on the event F_{h,i} is 0 also contradicts r(s_i,a)=1, since the cumulative reward would be h−1. The algebra in Step 2 implicitly uses zero rewards on all non-goal steps, with reward obtained only upon reaching g. As written, Theorem 3, which is the lower-bound half of the central claimed rate Θ(KH^3SA/ε^2), is unsupported. The construction may be repairable by a one-line reward correction, but that correction is absent and the proof as submitted does not establish the theorem.
  2. [Appendix A.2, Proposition 2] Proposition 2 is load-bearing: both the planning FPTAS (Theorem 1) and the learning upper bound (Theorem 4) restrict attention to the class Π_C, so the claim that Π_C is sufficient for optimality needs a fully rigorous proof. The present proof is too terse and notationally confused: it defines an object with two repeated arguments, V̄⋆_{h,i}(H_{h,i})(H_{h,i}), and later evaluates V̄⋆ on the compressed history Φ while V⋆ is evaluated on the full history, without an explicit definition of V̄⋆ on the compressed state space. The critical step, showing that the greedy policy defined by the Bellman optimality equations for the Π_C-restricted optimum attains the original history-dependent optimum, is asserted by a 'recursion argument' that does not spell out the induction over rollout boundaries, nor justify that the maxima are attained at every compressed history. I recommend rewriting this proof with explicit dynamic-programming value functions on the triple (s,M,G), including a careful treatment of the boundary conditions V̄⋆_{H+1,i} = V̄⋆_{1,i+1}.
minor comments (4)
  1. [Section 3.1, Figure 1 and accompanying text] The description of the example in the text is inconsistent: the text refers to 'the risky action' twice, first with reward 1/2 and probability 1−γ and then with reward 1 and probability 1/4, while the caption assigns the reward 1/2 to the safe action. Please correct the typo and align the caption with the intended safe/risky assignment.
  2. [Appendix A.5, proof of Theorem 2] In the derivation of Q_-, the second displayed equation is labeled 'Q+ = ...' and should be 'Q_- = ...'; also the expression 'P[X≥T]' should be 'P[X≥L]' throughout.
  3. [Appendix A.2, notation] The repeated argument notation V̄⋆_{h,i}(H_{h,i})(H_{h,i}) appears to be a typographical duplication; the value function on the compressed history should be defined as a function of Φ(H_{h,i}) once, and the proof should distinguish V̄⋆ on compressed states from V⋆ on raw histories consistently.
  4. [Section 4.3, Theorem 4 statement] The choice κ=O(εH^{-1}) is vague; the proof uses κ=ε/(9H). Please state the concrete constant or specify that it is a sufficiently small absolute constant.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: central claims are derived from the stated MDP model; the only self-citation is a peripheral technical lemma. A separate correctness flaw in the B.1 lower bound is noted but is not circularity.

full rationale

The derivation chain is not circular. Proposition 2 is proved by backward induction: the restricted value V̅⋆(Φ(H)) is shown equal to the history-dependent optimum V⋆(H) starting from the base case at (H+1,K) and propagating through the Bellman equations, so optimality of Π_C is established rather than assumed. Theorem 1 follows from Lemma 1 (reward-perturbation bound) plus the optimality of the discretized policy in M_κ, not from the target error bound. Theorem 4 is derived through simulation lemmas (Lemmas 2–7) that bound the empirical-model planning error in terms of transition-kernel concentration and a variance lemma; the KH^3/ε^2 rate is obtained by choosing m and κ, not by assuming the conclusion. The only self-citation is Lemma 10 (Lemma D.9 in Barbara et al. 2026), used in Lemma 7 to convert a concentration condition into a sample-size bound; it is a parameter-free stopping-time inequality whose statement does not involve max@k, so it is not load-bearing for the max@k-specific claims. No parameter is fitted to data and no target quantity is used as an input. Separately, and outside the circularity definition, the lower-bound instance in B.1 defines r(s_i,a)=1 for every non-goal state, so every rollout has total reward H in every instance; the proof's value bounds implicitly treat non-goal rewards as zero, making Theorem 3 unsupported as written. This is a correctness defect, not a circular step.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data. The quantities κ (grid width), c_0, and c_1 are chosen analytically to satisfy inequalities; they are proof/algorithm parameters, not inferred values. The new compressed state (M_i, G_{h,i}) is introduced with a proof of sufficiency (Proposition 2), not as an ad hoc entity.

assumptions (4)
  • domain assumption The learner knows the reward function r exactly; only transition probabilities are estimated.
    Theorems 3 and 4 and the algorithm in Section 4.3 project known rewards onto a grid; no reward estimation is performed. This is standard in the cited generative-model RL literature.
  • standard math Standard concentration and information-theoretic inequalities (Bernstein, Pinsker, KL-change-of-measure) are valid.
    Appendix B invokes Lemma 8, Lemma 9, Lemma 11, and Lemma 12 from standard references.
  • standard math Lemma 10 (a stopping-time bound) from Barbara et al. 2026 is valid.
    Self-cited technical lemma used in B.2 to set the uniform-sampling burn-in time m. It is peripheral and not proved in this paper.
  • standard math Subset-Sum is NP-complete and the reduction operates with exact rational arithmetic.
    Theorem 2 reduces Subset-Sum to the planning decision problem with an exponentially small gap β.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Theoretical Foundations of $\max$@$k$ Reinforcement Learning." pith.science (2026). https://pith.science/paper/OB6QXQEW

@misc{pith2026260717823,
  author       = {Pith},
  title        = {Pith review of: Theoretical Foundations of $\max$@$k$ Reinforcement Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OB6QXQEW}},
  note         = {Machine review of arXiv:2607.17823}
}
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.

Figures

Figures reproduced from arXiv: 2607.17823 by the authors.

Figure 1
Figure 1. Visualization of the MDP that illustrates the sub-optimality of Markovian policies. Dashed edges denote stochastic transitions, and leaves are associated with the rewards at the end of the horizon. Markovian Policies Are Not Enough. The main chal￾lenge in max@k decision processes is that, unlike the classic MDP setting, we are no longer guaranteed to find optimal poli￾cies among Markovian policies, denoted in the fo… view at source ↗
Figure 2
Figure 2. Visualization of the MDP for the linear lower bound in K. There is a state s and two actions, a1 (blue) and a2 (red), which both lead to rewards of 1 and 0 with probabilities p and 1 − p, respectively. The Linear Dependency in K We now provide a sketch behind the argument that allows one to show a linear lower bound in K. The example we are going to discuss is illustra￾tive in that it serves as the building block be… view at source ↗
Figure 3
Figure 3. MDP that is used as example to prove Proposition [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

72 extracted references · 38 canonical work pages

  1. [1]

    Max k-armed bandit: On the extremehunter algorithm and beyond

    Mastane Achab, Stephan Cl \'e men c on, Aur \'e lien Garivier, Anne Sabourin, and Claire Vernade. Max k-armed bandit: On the extremehunter algorithm and beyond. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 389--404. Springer, 2017

    work page 2017

  2. [2]

    Model-based reinforcement learning with a generative model is minimax optimal

    Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67--83. PMLR, 2020

    2020

  3. [3]

    Rewarding behaviors

    Fahiem Bacchus, Craig Boutilier, and Adam Grove. Rewarding behaviors. In Proceedings of the National Conference on Artificial Intelligence, pages 1160--1167, 1996

    work page 1996

  4. [4]

    The best of n worlds: Aligning reinforcement learning with best-of-n sampling via max@ k optimisation

    Farid Bagirov, Mikhail Arkhipov, Ksenia Sycheva, Evgeniy Glukhov, and Egor Bogomolov. The best of n worlds: Aligning reinforcement learning with best-of-n sampling via max@ k optimisation. arXiv preprint arXiv:2510.23393, 2025

    arXiv

  5. [5]

    Optimal rates for feasible payoff set estimation in games

    Annalisa Barbara, Riccardo Poiani, Martino Bernasconi, and Andrea Celli. Optimal rates for feasible payoff set estimation in games. In Forty-third International Conference on Machine Learning, 2026

    work page 2026

  6. [6]

    Regret bounds for risk-sensitive reinforcement learning

    Osbert Bastani, Jason Yecheng Ma, Estelle Shen, and Wanqiao Xu. Regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 35: 0 36259--36269, 2022

    work page 2022

  7. [7]

    Efficient Algorithms for Extreme Bandits

    Dorian Baudry, Yoan Russac, and Emilie Kaufmann. Efficient algorithms for extreme bandits. arXiv preprint arXiv:2203.10883, 2022

    work page Pith review arXiv 2022

  8. [8]

    A distributional perspective on reinforcement learning

    Marc G Bellemare, Will Dabney, and R \'e mi Munos. A distributional perspective on reinforcement learning. In International conference on machine learning, pages 449--458. Pmlr, 2017

    work page 2017

Show all 72 references
  1. [9]

    Distributional reinforcement learning

    Marc G Bellemare, Will Dabney, and Mark Rowland. Distributional reinforcement learning. MIT Press, 2023

    2023

  2. [10]

    Graph of thoughts: Solving elaborate problems with large language models

    Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI confe...

    2024

  3. [11]

    Concentration inequalities

    St \'e phane Boucheron, G \'a bor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208--240. Springer, 2003

    2003

  4. [12]

    Ltlf/ldlf non-markovian rewards

    Ronen Brafman, Giuseppe De Giacomo, and Fabio Patrizi. Ltlf/ldlf non-markovian rewards. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018

    2018

  5. [13]

    Large language monkeys: Scaling inference compute with repeated sampling

    Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher R \'e , and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024

    2024 arXiv

  6. [14]

    Extreme bandits

    Alexandra Carpentier and Michal Valko. Extreme bandits. Advances in Neural Information Processing Systems, 27, 2014

    2014

  7. [15]

    Maxproof: Scaling mathematical proof with generative-verifier rl and population-level test-time scaling

    Jiacheng Chen, Xinyu Zhang, Shunkai Zhang, Yanmohan Wang, Lin Li, Tiancheng Qin, Qin Wang, Zhengmao Zhu, Tianle Li, Jingyang Li, et al. Maxproof: Scaling mathematical proof with generative-verifier rl and population-level test-time scaling. arXiv preprint arXiv:2606.13473, 2026 a

    2026 arXiv

  8. [16]

    Evaluating large language models trained on code

    Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021

    2021 arXiv

  9. [17]

    Pass@ k training for adaptively balancing exploration and exploitation of large reasoning models

    Zhipeng Chen, Xiaobo Qin, Youbin Wu, Yue Ling, Qinghao Ye, Wayne Xin Zhao, and Guang Shi. Pass@ k training for adaptively balancing exploration and exploitation of large reasoning models. arXiv preprint arXiv:2508.10751, 2025

    2025 arXiv

  10. [18]

    Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model? Advances in Neural Information Processing Systems, 38: 0 57654--57689, 2026 b

    Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Yang Yue, Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model? Advances in Neural Information Processing Systems, 38: 0 57654--57689, 2026 b

    2026

  11. [19]

    Robust reinforcement learning with general utility

    Ziyi Chen, Yan Wen, Zhengmian Hu, and Heng Huang. Robust reinforcement learning with general utility. Advances in Neural Information Processing Systems, 37: 0 11290--11344, 2024

    2024

  12. [20]

    Algorithms for cvar optimization in mdps

    Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for cvar optimization in mdps. Advances in neural information processing systems, 27, 2014

    2014

  13. [21]

    Inference-aware fine-tuning for best-of-n sampling in large language models

    Yinlam Chow, Guy Tennenholtz, Izzeddin Gur, Vincent Zhuang, Bo Dai, Aviral Kumar, Rishabh Agarwal, Sridhar Thiagarajan, Craig Boutilier, and Aleksandra Faust. Inference-aware fine-tuning for best-of-n sampling in large language models. In International Conference on Learning R...

    2025

  14. [22]

    Goedel-architect: Streamlining formal theorem proving with blueprint generation and refinement

    Jui-Hui Chung, Ziyang Cai, Zihao Li, Qishuo Yin, Rohit Agarwal, Simon Park, Rodrigo Porto, Narutatsu Ri, Ziran Yang, Shange Tang, et al. Goedel-architect: Streamlining formal theorem proving with blueprint generation and refinement. arXiv preprint arXiv:2606.06468, 2026

    2026 arXiv

  15. [23]

    Training verifiers to solve math word problems

    Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021

    arXiv

  16. [24]

    The entropy mechanism of reinforcement learning for reasoning language models

    Ganqu Cui, Yuchen Zhang, Jiacheng Chen, Lifan Yuan, Zhi Wang, Yuxin Zuo, Haozhan Li, Yuchen Fan, Huayu Chen, Weize Chen, et al. The entropy mechanism of reinforcement learning for reasoning language models. arXiv preprint arXiv:2505.22617, 2025

    2025 arXiv

  17. [25]

    Distributional reinforcement learning with quantile regression

    Will Dabney, Mark Rowland, Marc Bellemare, and R \'e mi Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018

    2018

  18. [26]

    Sample complexity of episodic fixed-horizon reinforcement learning

    Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. Advances in Neural Information Processing Systems, 28, 2015

    2015

  19. [27]

    Chain-of-verification reduces hallucination in large language models

    Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston. Chain-of-verification reduces hallucination in large language models. In Findings of the association for computational linguistics: ACL 2024, pages 3563--3578, 2024

    2024

  20. [28]

    Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited

    Omar Darwiche Domingues, Pierre M \'e nard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578--598. PMLR, 2021

    2021

  21. [29]

    Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret

    Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret. Advances in Neural Information Processing Systems, 33: 0 22384--22395, 2020

    2020

  22. [30]

    Reinforcement learning with non-markovian rewards

    Maor Gaon and Ronen Brafman. Reinforcement learning with non-markovian rewards. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3980--3987, 2020

    2020

  23. [31]

    Explore first, exploit next: The true shape of regret in bandit problems

    Aur \'e lien Garivier, Pierre M \'e nard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44 0 (2): 0 377--399, 2019

    2019

  24. [32]

    Minimax pac bounds on the sample complexity of reinforcement learning with a generative model

    Mohammad Gheshlaghi Azar, R \'e mi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91 0 (3): 0 325--349, 2013

    2013

  25. [33]

    Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning

    Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025

    2025 arXiv

  26. [34]

    Provably efficient maximum entropy exploration

    Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International conference on machine learning, pages 2681--2691. PMLR, 2019

    2019

  27. [35]

    Reward machines: Exploiting reward function structure in reinforcement learning

    Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A McIlraith. Reward machines: Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73: 0 173--208, 2022

    2022

  28. [36]

    Learning to correct: Calibrated reinforcement learning for multi-attempt chain-of-thought

    Muhammed Emrullah Ildiz, Halil Alperen Gozeten, Ege Onur Taga, and Samet Oymak. Learning to correct: Calibrated reinforcement learning for multi-attempt chain-of-thought. arXiv preprint arXiv:2604.17912, 2026

    2026 arXiv

  29. [37]

    Openai o1 system card

    Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai o1 system card. arXiv preprint arXiv:2412.16720, 2024

    2024 arXiv

  30. [38]

    Planning in markov decision processes with gap-dependent sample complexity

    Anders Jonsson, Emilie Kaufmann, Pierre M \'e nard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33: 0 1253--1263, 2020

    2020

  31. [39]

    Policy gradient for reinforcement learning with general utilities

    Navdeep Kumar, Kaixin Wang, Kfir Levy, and Shie Mannor. Policy gradient for reinforcement learning with general utilities. arXiv preprint arXiv:2210.00991, 2022

    2022 arXiv

  32. [40]

    Tulu 3: Pushing frontiers in open language model post-training

    Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James V Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, et al. Tulu 3: Pushing frontiers in open language model post-training. arXiv preprint arXiv:2411.15124, 2024

    2024 arXiv

  33. [41]

    Breaking the sample size barrier in model-based reinforcement learning with a generative model

    Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 33: 0 12861--12872, 2020

    2020

  34. [42]

    Competition-level code generation with alphacode

    Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, R \'e mi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 378 0 (6624): 0 1092--1097, 2022

    2022

  35. [43]

    Let's verify step by step

    Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In International Conference on Learning Representations, volume 2024, pages 39578--39601, 2024

    2024

  36. [44]

    Self-refine: Iterative refinement with self-feedback

    Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in neural information processing systems, 36: 0 46534--46594, 2023

    2023

  37. [45]

    Challenging common assumptions in convex reinforcement learning

    Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Challenging common assumptions in convex reinforcement learning. Advances in Neural Information Processing Systems, 35: 0 4489--4502, 2022

    2022

  38. [46]

    Convex reinforcement learning in finite trials

    Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Convex reinforcement learning in finite trials. Journal of Machine Learning Research, 24 0 (250): 0 1--42, 2023

    2023

  39. [47]

    No regret bound for extreme bandits

    Robert Nishihara, David Lopez-Paz, and L \'e on Bottou. No regret bound for extreme bandits. In Artificial Intelligence and Statistics, pages 259--267. PMLR, 2016

    2016

  40. [48]

    Markov decision processes

    Martin L Puterman. Markov decision processes. Handbooks in operations research and management science, 2: 0 331--434, 1990

    1990

  41. [49]

    Near-minimax-optimal distributional reinforcement learning with a generative model

    Mark Rowland, Li K Wenliang, R \'e mi Munos, Clare Lyle, Yunhao Tang, and Will Dabney. Near-minimax-optimal distributional reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 37: 0 132774--132823, 2024

    2024

  42. [50]

    Reflexion: Language agents with verbal reinforcement learning

    Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in neural information processing systems, 36: 0 8634--8652, 2023

    2023

  43. [51]

    Yang, and Yinyu Ye

    Aaron Sidford, Mengdi Wang, Xian Wu, Lin F. Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving discounted markov decision process with a generative model, 2019. URL https://arxiv.org/abs/1806.01492

    2019 arXiv

  44. [52]

    Scaling llm test-time compute optimally can be more effective than scaling parameters for reasoning

    Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling llm test-time compute optimally can be more effective than scaling parameters for reasoning. In International Conference on Learning Representations, volume 2025, pages 10131--10165, 2025

    2025

  45. [53]

    On advantage estimates for max@ k policy gradients

    Shota Takashiro, Soichiro Nishimori, Paavo Parmas, Yongmin Kim, Kohsei Matsutani, Gouki Minegishi, Yusuke Iwasawa, Takeshi Kojima, and Yutaka Matsuo. On advantage estimates for max@ k policy gradients. arXiv preprint arXiv:2606.06080, 2026

    2026 arXiv

  46. [54]

    Optimizing language models for inference time objectives using reinforcement learning

    Yunhao Tang, Kunhao Zheng, Gabriel Synnaeve, and Remi Munos. Optimizing language models for inference time objectives using reinforcement learning. In International Conference on Machine Learning, pages 59066--59085. PMLR, 2025

    2025

  47. [55]

    Finite-time regret analysis of retry-aware bandits

    Bingkui Tong, Junpei Komiyama, Soichiro Nishimori, and Paavo Parmas. Finite-time regret analysis of retry-aware bandits. arXiv preprint arXiv:2605.20854, 2026

    2026 arXiv

  48. [56]

    Model-based reinforcement learning in discrete-action non-markovian reward decision processes

    Alessandro Trapasso, Luca Iocchi, and Fabio Patrizi. Model-based reinforcement learning in discrete-action non-markovian reward decision processes. arXiv preprint arXiv:2512.14617, 2025

    2025 arXiv

  49. [57]

    Advancing mathematics research with ai-driven formal proof search

    George Tsoukalas, Anton Kovsharov, Sergey Shirobokov, Anja Surina, Moritz Firsching, Gergely B \'e rczi, Francisco JR Ruiz, Arun Suggala, Adam Zsolt Wagner, Eric Wieser, et al. Advancing mathematics research with ai-driven formal proof search. arXiv preprint arXiv:2605.22763, 2026

    2026 arXiv

  50. [58]

    Recursive self-aggregation unlocks deep thinking in large language models

    Siddarth Venkatraman, Vineet Jain, Sarthak Mittal, Vedant Shah, Johan Obando-Ceron, Yoshua Bengio, Brian R Bartoldson, Bhavya Kailkhura, Guillaume Lajoie, Glen Berseth, et al. Recursive self-aggregation unlocks deep thinking in large language models. arXiv preprint arXiv:2509....

    2025

  51. [59]

    Pass@ k policy optimization: Solving harder reinforcement learning problems

    Christian Walder and Deep Tejas Karkhanis. Pass@ k policy optimization: Solving harder reinforcement learning problems. Advances in Neural Information Processing Systems, 38: 0 152416--152445, 2026

    2026

  52. [60]

    Sample-efficient reinforcement learning for linearly-parameterized mdps with a generative model

    Bingyan Wang, Yuling Yan, and Jianqing Fan. Sample-efficient reinforcement learning for linearly-parameterized mdps with a generative model. Advances in neural information processing systems, 34: 0 23009--23022, 2021

    2021

  53. [61]

    Near-minimax-optimal risk-sensitive reinforcement learning with cvar

    Kaiwen Wang, Nathan Kallus, and Wen Sun. Near-minimax-optimal risk-sensitive reinforcement learning with cvar. In International Conference on Machine Learning, pages 35864--35907. PMLR, 2023

    2023

  54. [62]

    Self-consistency improves chain of thought reasoning in language models

    Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171, 2022

    2022 arXiv

  55. [63]

    Risk-sensitive markov decision process and learning under general utility functions

    Zhengqi Wu and Renyuan Xu. Risk-sensitive markov decision process and learning under general utility functions. arXiv preprint arXiv:2311.13589, 2023

    2023 arXiv

  56. [64]

    Monte carlo tree search boosts reasoning via iterative preference learning

    Yuxi Xie, Anirudh Goyal, Wenyue Zheng, Min-Yen Kan, Timothy P Lillicrap, Kenji Kawaguchi, and Michael Shieh. Monte carlo tree search boosts reasoning via iterative preference learning. arXiv preprint arXiv:2405.00451, 2024

    2024 arXiv

  57. [65]

    Deepseek-prover: Advancing theorem proving in llms through large-scale synthetic data

    Huajian Xin, Daya Guo, Zhihong Shao, Zhizhou Ren, Qihao Zhu, Bo Liu, Chong Ruan, Wenda Li, and Xiaodan Liang. Deepseek-prover: Advancing theorem proving in llms through large-scale synthetic data. arXiv preprint arXiv:2405.14333, 2024

    2024 arXiv

  58. [66]

    Tree of thoughts: Deliberate problem solving with large language models

    Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in neural information processing systems, 36: 0 11809--11822, 2023

    2023

  59. [67]

    Reward is enough for convex mdps

    Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. Advances in Neural Information Processing Systems, 34: 0 25746--25759, 2021

    2021

  60. [68]

    Star: Bootstrapping reasoning with reasoning

    Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35: 0 15476--15488, 2022

    2022

  61. [69]

    Variational policy gradient method for reinforcement learning with general utilities

    Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33: 0 4572--4583, 2020

    2020

  62. [70]

    Estimation and inference in distributional reinforcement learning

    Liangyu Zhang, Yang Peng, Jiadong Liang, Wenhao Yang, and Zhihua Zhang. Estimation and inference in distributional reinforcement learning. arXiv preprint arXiv:2309.17262, 2023

    2023

  63. [71]

    Beyond markovian: Reflective exploration via bayes-adaptive rl for llm reasoning

    Shenao Zhang, Yaqing Wang, Yinxiao Liu, Tianqi Liu, Peter Grabowski, Eugene Ie, Zhaoran Wang, and Yunxuan Li. Beyond markovian: Reflective exploration via bayes-adaptive rl for llm reasoning. arXiv preprint arXiv:2505.20561, 2025 a

    2025

  64. [72]

    Settling the sample complexity of online reinforcement learning

    Zihan Zhang, Yuxin Chen, Jason Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. Journal of the ACM, 72 0 (3): 0 1--63, 2025 b

    2025

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.