Recent Advances in Reinforcement Learning
Sample Complexity & Sample Efficiency
The concepts of sample complexity and sample efficiency are fundamental in RL and are closely related, though they focus on different aspects of learning.
The sample complexity of a RL algorithm is the minimum number of calls to a sampling model required for the algorithm to learn a policy that is within a specified target accuracy level, $\varepsilon$ of the optimal policy, with high probability. Formally, the sample complexity $m(\varepsilon, \delta)$ is the smallest number of samples such that, for any $\delta \in (0,1)$, the learned policy $ \pi$ is an $\varepsilon$-accurate policy, i.e.,
\begin{eqnarray*}
V^{\pi}(s) &\geqslant& V^\star(s) -\varepsilon,\\
Q^{\pi}(s,a) &\geqslant& Q^\star(s,a) -\varepsilon,
\end{eqnarray*}
with probability at least $1 - \delta$. In RL, there is a trade-off between sample complexity and statistical accuracy:
exploring more information to improve statistical accuracy, versus exploiting known actions to maximize reward, which reduces sample complexity. The agent's learning speed is directly related to the sample complexity of the task.
The two common frameworks for analyzing sample complexity are:
- The PAC bounds, which allow to determine the number of samples needed to guarantee that the algorithm learns a policy with a small accuracy error $\varepsilon$, compared to the optimal policy
- On the other hand, the regret bounds measure the cumulative loss incurred before reaching the optimal policy. They quantify how much reward we miss out on during the learning process.
New results on sample complexity and the the minimum sample size for achieving the minimax sample complexity are provided in the
AI & Math Blog.
Closely related to sample complexity is sample efficiency, which measures how much data a learning system needs to achieve a specific performance goal. An algorithm is considered sample efficient if it can learn effectively with a limited amount of data. Improving sample efficiency is critical, especially in real-world applications where collecting data can be expensive or time-consuming
A highly sample efficient algorithm will typically have lower sample complexity because it can achieve good performance with fewer samples. Conversely, if an algorithm has high sample complexity, it might indicate that it is not making the best use of the samples it collects, leading to lower sample efficiency.
Balancing sample complexity and sample efficiency is essential for developing RL algorithms that are both data-efficient and computationally feasible. This balance is crucial for practical applications where both data and computational resources are limited.
RL methods such as off-policy learning, model-based approaches, and transfer learning improve sample efficiency.
Importance sampling can be used to achieve sample efficiency by focusing on the most informative samples, thereby reducing the overall number of samples needed. Model-based RL approaches can also improve sample efficiency by using a model of the environment to generate additional training data, thereby reducing the need for real-world interactions
Generalization, Transfer Learning & Off-policy Learning
RL systems often struggle to generalize the learned policies to new, unseen environments or tasks.
Developing methods for transfer learning, where knowledge gained in one task can be applied to another, is an important open problem.
Transfer Learning (TL) methods, see Taylor and Stone ( 2009) propose to alleviate the burden of learning through the reuse of knowledge. The most intuitive way to apply TL to RL is to reuse the solution of previous tasks that have already
been presented to the agent, but many methods also focused on reusing knowledge from external sources, such as demonstrations from humans or advice from other learning agents, see Da Silva, Glatt, and Costa (2017).
New developements on TL and generalization are provided in the
AI & Math Blog.
Distributional Reinforcement Learning
The purpose of distributional reinforcement learning (DRL) is to model the full distribution of returns, whereas conventional reinforcement learning (RL) focuses primarily on their expected value.
This distributional approach is of interest for RL applications that deal with risk, uncertainty and requires the full distribution of possible outcomes, e.g., risk evaluation in finance, autonomous vehicles, robotics, etc.
Foundational works on DRL started with Morimura
et al. (2010a, 2010b), who formulated the distributional Bellman equations for cumulative return distributions and return densities, respectively, and developed associated nonparametric and parametric estimation methods for reinforcement learning. Related distributional recursions had previously been studied by Sobel (1982) and Chung and Sobel (1987).
DRL is exposed at length in Bellemare
et al. (2023). Very recently, Zhang
et al. (2025) study the statistical properties of the DRL estimation, i.e., the asymptotic and non asymptotic properties and sample efficiency of an estimator $\hat{\eta}^\pi$ of the distribution of returns $\eta^\pi$ for a given policy $\pi$. These recent developments are given in the
AI & Math Blog.
Natural Language Processing
Generative AI & LLMs
Generative AI is a part of automation technologies: it generates text, programming code and images using as database quite the exhaustive content of the web, using attention mechanisms, transformer architectures and autoregressive probabilistic models.
Although the syntax of the generated text is correct, as the correctness of the grammar is the straight consequence of the autoregressive probabilistic tools of generative AI, the meaning of this text must be evaluated.
In their original form, these combinatorial generative models, based on the linguistic representation of the physical world, operate inside the box of that representation, and were initially unable to plan or to produce any content outside that box. From a mathematical perspective, the first generations of LLMs (up to roughly 2023) lacked complete deductive closure, i.e., they could not reliably draw every conclusion entailed by their knowledge, nor justify every step of a solution. This matched Kahneman's (2011) Type 1 system, which relies on intuition and heuristics rather than logical reasoning. The paragraphs below describe that limitation and, more importantly, how it has since been overcome.
Reasoning Properties of LLMs
The implications of that lack of deductive closure were significant for the early, pure autoregressive LLMs. They excelled in inductive reasoning , i.e., generalizing from specific examples, but struggled with tasks requiring strict logical or multi-step reasoning, such as mathematical proofs or legal reasoning, where every step must follow from the previous one. Their probabilistic nature could yield inconsistent or contradictory outputs on near-identical prompts, undermining trust in high-stakes settings (science, healthcare, law), and their performance was bounded by the quality and diversity of the training data.
It is essential to qualify this picture: these limitations characterized LLMs used in isolation, as a single forward pass of a probabilistic model. They do not describe the reasoning systems built on top of LLMs from 2024 onward. By coupling an LLM with search over intermediate steps, self-verification, and an external formal verifier, the community has demonstrated deductive closure at the highest level of mathematics, including a Millennium Prize problem, see below. The honest reading is therefore historical: the deficit was real for the first generation and was precisely what motivated the hybrid and self-reasoning architectures of the next.
Hybrid Models and Self-Reasoning
To address these limitations, there has been a growing interest in developing hybrid models that combine LLMs with other AI systems capable of deductive reasoning. The reasoning performance of LLMs can be extended and improved with Chain-of-Thought (CoT) prompting (Wei
et al., 2022). CoT is an extension of the few-shots prompting properties of LLMs (Brown
et al., 2020):
for the few-shot prompting, the LLM is provided with a small number of in-context (input, output) pairs of examples, or 'shots'. In contrast, for the CoT prompting, the LLM is provided with triples (input, chain-of-thought, output), where the chain-of-thought consists of a series of intermediate reasoning steps that lead to the solution of the studied problem.
The CoT consists of breaking down complex tasks into smaller, intermediate and more manageable steps. These intermediate steps, which make the decision-making process more transparent, can be particularly useful in multi-steps reasoning tasks where understanding the model's reasoning is crucial.
Furthermore, this decomposition in elementary steps can reduce the likelihood of generating irrelevant or incorrect information, known as hallucinations. CoT reduces the cognitive load of processing complex information all at once by distributing the problem-solving process over multiple steps, allowing the model to handle each step more effectively and carrying intermediate verification of each step in the reasoning process. This means that errors can be identified and corrected earlier, preventing them from propagating and affecting the final conclusion. RL can be combined with CoT for reducing the hallucinations.
Prompting the model consists of generating a series of thoughts or steps that lead to the final answer, rather than directly producing the solution. This approach helps the model to handle more complex, multi-step problems by mimicking human-like logical step-by-step reasoning leading to the final answer. This requires a careful prompt engineering, i.e., carefully designing and refining specific instructions or questions that guide the model's responses in a way that aligns with the user's goals or requirements. Poorly designed prompts can lead to suboptimal performance.
Furthermore, CoT prompting does not require extensive retraining.
The single pathway CoT prompting has been further generalized by Tree of Thoughts (ToT) prompting (Yao
et al., 2024), which is characterized by multiple competing reasoning paths modeled as a tree. The formalization of a human problem solving as a search problem along a tree has been advocated by the Turing Award laureates Newell and Simon (1972).
These prompting techniques were the conceptual bridge to the current generation of reasoning models, close to Kahneman's Type 2 system: these LLMs are trained with reinforcement learning to generate and verify long internal chains of thought before answering. Combined with search, tool use and, crucially, machine-checked formal verification tools, e.g., the
Lean proof assistant, they fill the deductive closure gap that first-generation LLMs could not.
Solving Mathematical Problems
The integration of large language models (LLMs) into mathematical research has surpassed initial expectations, so that they are condidered as a standard research tool for mathematicians. Early applications of generic LLMs to mathematical problem-solving often yielded unsatisfactory results, requiring extensive manual verification, particularly in multi-step reasoning, as highlighted by Cobbe
et al. (2021).
However, recent advances have transformed this landscape. Researchers have demonstrated that LLMs' reasoning abilities can be significantly enhanced by incorporating structured and recursive reasoning mechanisms, similar to Kahneman's (2011) Type 2 cognitive system.
A major breaktrough occured with the work of Chervonyi
et al. (2025), who introduced DDAR 2, a novel fast algorithm for deductive database arithmetic reasoning. By applying a fixed set of deduction rules iteratively, DDAR 2 expands the initial information set until the deduction closure is reached. The algorithm has demonstrated exceptional performance, solving gold medal-level geometry problems from international olympiads, an improvement over its predecessor, DDAR 1 (Trinh
et al., 2024).
Most notably, a recent breakthrough saw ChatGPT assist in proving an advanced mathematical theorem by proposing the use of the Nevanlinna two-constant theorem to demonstrate Bernstein's inequality for functions of exponential type, as reported by
Terence Tao, in 2026. Note that Terence Tao was at this time unaware of this theorem by Navanlinna.
The most striking illustration that the deductive-closure limitation is no longer an issue is the Navier–Stokes Millennium Prize problem. On September 8, 2026,
OpenAI announced that an internal multi-agent system, running an unreleased model described as significantly more capable than GPT-6 Astra, organized as a swarm of roughly 10,000 coordinating agents, produced an analytical proof and a
Lean
formalization showing that a smooth three-dimensional incompressible fluid, starting at rest and driven by a smooth applied force of finite energy, can develop a singularity in finite time.
In the Clay Institute's formulation this resolves variants C and D, i.e. a disproof of universal smoothness for the forced case, long one of the six remaining Millennium Prize problems, see
Quanta Magazine.
The swarm reached the proof in roughly 88 hours and about 130 billion generated tokens, with
Lean formalization completed in an additional 17 hours.
Two caveats are required for honesty. First, as of this writing the Clay Mathematics Institute still lists Navier–Stokes as open, as the verification of the 165-pages mathematical argument is still in progress. Second, the announcement is shadowed by a priority dispute: Tristan Buckmaster (NYU) and Levent Alpöge contend that the forced-blowup strategy, building on the work by Córdoba and Martínez-Zoroa (2024), was developed in their private collaboration before OpenAI's run. OpenAI disputes this claim, and has stated that it does not intend to claim the Millennium Prize for the result. These reservations concern credit and acceptance, not the central technical point relevant here: an LLM-based system has produced a novel, verified by
Lean, deductive proof at the level of a Millennium Prize problem.