When Can Model-Free Reinforcement Learning be Enough for Thinking?

Thanks for your kind comments on the strength of our theoretical analysis!

Weaknesses:

1. We agree the title could be improved and can easily address this for the camera-ready subject to PC Chair approval. A more appropriate title might be “When does model-free RL lead to thinking?” or something similar.
2. This is a good suggestion that we can easily add to the related work. In terms of understanding COT, the uniqueness of our work seems to be explaining the emergence of reasoning in RL terms. We’ll discuss other papers you suggest below.

Questions:

1. This is a good point that we can clarify. We are not claiming that arbitrary thought states and actions will lead to better performance. The implication of Theorem 1 is that, if there is a thought action that leads to a thought state where the policy performs better than under the current state then that thought action will improve the agent’s performance.
2. Thanks for suggesting these references. We can add discussion about how existing work on COT and latent states relates to our work. Specifically:
   • Prior work on COT seems to focus on why COT outputs are useful even prior to any RL training being performed. To the best of our knowledge, these works are not considering the emergence of thinking via RL. Our work answers the question of when COT outputs will be selected for by RL.
   • In the RL literature, latent state variables are usually discussed in partially observable settings. In such settings, the agent can try to construct a state representation that still supports good decision-making. Alternatively, in deep RL, the latent state can be a representation of state that enables predicting state values using a simpler function (e.g., a representation that enables linear value prediction). In contrast, we are focusing on a fully observable environment and analyzing the tabular setting where we have appropriate representational power to learn the value function and policy. The thought states serve a novel purpose which is to give the agent a variable to manipulate to trigger different sub-policies within its policy function.

Please let us know if we can provide further clarification!

Thanks for your kind comments on the formalization and theory. We're happy to hear that you lean toward accepting the paper and we hope that we can address some of the weaknesses in a camera-ready version.

Weaknesses:

1. We chose addition for its simplicity and because it is straightforward to create correct reasoning chains for it (i.e., to create the "thinking" condition). We will think about potential other tasks to consider. If you have particular tasks in mind, we would welcome the suggestion!
2. Producing a new algorithm for LLMs wasn't one of the goals of our work. Our paper's main contribution is to develop the theory around when model-free RL will produce thought actions. The purpose of this is to provide a deeper understanding of this new type of thinking that recent work in training LLMs to reason has provided a proof-of-concept for.

Questions:

1. We don't think our work immediately suggests new training recipes for LLMs. Rather we are trying to understand why current training recipes lead to thinking emerging.
2. In formal terms, many existing works optimize the undiscounted return over fixed-length episodes. In our theory we consider the discounted return over indefinite length episodes. We will add more discussion around this point to the camera-ready. In our response to reviewer zETt, we explain that the discounted return may be a more appropriate objective for developing a general theory of thinking agents and also discuss the relatively minor extension of our theory to the undiscounted, fixed-length episode case. Please let us know if this doesn't address your concern!
3. To sum-up our response to reviewer zETt for $\gamma=1$: having $\gamma=1$ requires that episodes can't have infinite length and so we also adopt the fixed-length episodic setting (this also matches LLM training set-ups where generation can't continue indefinitely). The simple extension of our theory is to make the value function time-dependent. Under this modification, the analysis is qualitatively the same and tells us that thinking will be selected for when an additional step of thinking improves the policy enough to offset losing a time-step to collect reward.
   • If you mean what happens if we only discount non-thinking steps, the conclusion is that thinking will go on for as long as $v_\pi(s,\tau)$ keeps improving w.r.t. $\tau$.

Please let us know if you'd like to discuss these questions further!

Thanks for your kind comments on our novelty and alignment with empirical findings. We're happy the theoretical contribution is appreciated.

Weaknesses

1. As we aim to develop a domain-agnostic view of what it means for an RL agent to think, we intentionally define thought states and actions abstractly. We agree that an example would improve clarity and can provide one in the camera-ready version. Specifically, we can move up the discussion of how applying RL for LLM learning-to-reason is instantiating a thought MDP.
2. We can easily add evaluations with larger models to the camera ready. Since the submission, we have ran this experiment with 11 different models, including Qwen2.5-14B, Llama-2-13B, and Tulu-2-13B. The other models we will include range from 1-7B parameters. There is no qualitative difference between the new results and the ones with the smaller models. See below for discussion.

We include additional evaluations with 11 different models ranging from 1.5B - 14B parameters in the table below. Since submission, we have made a minor change to our experimental setup: rather than using perplexity to indirectly infer changes to value of model responses, we instead directly approximate state values with the Monte Carlo return, which is equivalent to the accuracy of the LLM’s response. We observe no qualitative difference between the new results and the ones with the smaller models: appending thinking tokens to the input prompt increases the value of the response accuracy.

| Model                     | No Thinking (%)       | Thinking (%)          |
|--------------------------|-----------------------|------------------------|
| Qwen2.5-1.5B-Instruct    | 7.20 ± 0.82           | 71.20 ± 2.80           |
| Qwen2.5-3B-Instruct      | 6.80 ± 0.80           | 36.50 ± 1.52           |
| Qwen2.5-7B-Instruct      | 5.06 ± 3.10           | 96.10 ± 2.98           |
| Qwen2.5-14B-Instruct     | 0.90 ± 0.33           | 95.20 ± 1.33           |
| Tulu-2-7b                | 0.30 ± 0.33           | 28.50 ± 2.80           |
| Tulu-2-13b               | 0.60 ± 0.47           | 49.00 ± 3.10           |
| Llama-2-7b               | 0.00 ± 0.00           | 48.80 ± 3.10           |
| Llama-2-13b              | 0.20 ± 0.27           | 60.70 ± 3.03           |
| Gemma-3-1b-it            | 0.50 ± 0.43           | 41.50 ± 3.06           |
| Gemma-3-4b-it            | 4.90 ± 1.33           | 91.50 ± 1.72           |
| Mistral-7B-Instruct-v0.3 | 1.50 ± 0.74           | 85.20 ± 2.20           |

Table. Response accuracy with ± 95% confidence interval when using thinking vs no thinking.

Thank you for your kind remarks—we’re glad you found the paper interesting!

Weaknesses:

• We agree that this is the correct phrasing of the claim we make—these LLMs can benefit from thinking. And you bring up an interesting point about would thinking emerge and then go away. While our theory focuses on exact policy iteration, we conjecture that thinking will not necessarily go away in practical policy gradient training and this connects to your later question about why in Section 6 that thought actions still are taken 15% of the time. Unlike exact policy iteration, policy gradient algorithms require sampling from the action space. Consequently, once the policy has put too much probability on the thinking actions, it is unlikely to sample the true optimal environment action, discover that such an action enables solving the task slightly quicker, and consequently converges sub-optimally.
• Regarding multi-task pre-training, our intention is to show that thinking is a way to trigger behaviors contained within the policy via manipulation of the agent’s internal thought state. If the policy doesn’t contain any such useful behaviors, there is nothing to trigger and so thinking is not useful. Pre-training appears to be the main possibility for setting up a policy to have such behaviors—though of course there may be other ways. We do not claim pre-training is necessary but it may be sufficient.
• We agree that exploring connections between MCTS (a more classic System 2 approach) and the thought MDP model is a fascinating direction for future work. This is on our research agenda and the idea to look at an LLM engaged in a task that requires planning would be cool to explore.
• We will carefully proofread the paper before the camera ready deadline.

Questions:

1. See our response to the first weakness. Proposition 4 concerns optimal behavior that stochastic learning algorithms may not necessarily converge to. In principle, if we had a tabular policy representation and a sufficiently large batch size for estimating the policy gradient then we would expect thinking to go away. However, this may not happen when using transformer policies and finite batch sizes. See [1] for more discussion on how PG methods can converge sub-optimally due to sampling variation. We will add discussion of this important point in the paper.
2. Thanks, we agree this is a valuable addition and will look into adding it. We do note that this evidence is already present in the literature for LLMs in general, though not necessarily for the specific ones we consider.
3. This is an interesting suggestion and we can easily do this experiment and include in the camera-ready. The natural ablation would be to make the pretraining tasks to move to different, non-corner locations or to the corners that aren’t sub-goals in the eventual task. We expect thinking to still be useful but overall less effective in these cases.

[1] On-Policy Policy Gradient Reinforcement Learning Without On-Policy Sampling. Corrado and Hanna. Arxiv 2024.

We’re happy to hear you found the formulation and its consequences interesting! Your comments were very though-provoking for us and we will add more justification around our assumptions based on your comments.

You’re correct that the formulation is not fully connected to current LLM practice—we see that as a strength rather than a weakness for theory work. As noted in the global comment above, our objective is foremost to develop a general model of this new way to develop “thinking” in AI agents. While LLMs are a proof-of-concept that this type of model can exist and be practically impactful, we see this as just the beginning for this general methodology. After all, humans don’t just think in language but also in images and more abstract thought spaces.

That said, our theoretical assumptions are not so disconnected from RL for thinking LLMs in practice as we read the literature.

• As we understand it, when training LLMs to reason, each action is a single token. See [1], Section 3.1 for the MDP formulation that we understand to be widely used. Sometimes papers describing RL for LLMs describe the LLM as a policy over sequences. Since the environment is deterministic and the model auto-regressive, this formulation is valid, but when it comes to implementation, tokens are the actions actually produced by the transformer model. Of course, you are right that a single token may have limited effect by itself.
• You’re correct that discounting is not standard in current LLM training (as far as we can tell). However, we would argue that some form of discounting is ultimately essential in any complete model of an AI agent, and hence we include it in our theoretical model. Otherwise, the agent may simply think forever without consequence. Perhaps this is part of why some reasoning models (e.g., DeepSeek-R1) respond to simple math problems with long-winded thinking traces [2,3].
• We also note that we could potentially deprecate the use of discounting in our theory by saying there is a maximum episode length and additionally conditioning the value-function on the episode time-step. The lesson from the theory would still be qualitatively the same: thinking is selected for when the amount of policy improvement that it brings compensates for having one fewer time-step to take actions that could directly produce reward.

The LLM experiments are intended to show that the right sequence of “thoughts” will increase the expected return of the agent under the current policy (i.e., base LLM). Showing this confirms that this sequence of actions would be preferred by a step of policy improvement (as we look at sequences, the result is more related to Corollary 1). We will clarify the extent to which the empirical results corroborate the theory—and discuss the limitations of what they show.

Regarding our theoretical assumptions, are there other assumptions beyond the disconnects you mentioned above that you would like to discuss? Here we discuss each key assumption made in the paper:

1. Assumption 1 (deterministic thought transitions): We initially defined Thought MDPs as having stochastic thought transitions for generality. This assumption is straightforward to relax but we didn’t do it for ease of exposition. Deterministic thought transitions are also the case with LLMs. We can add the generalized results to the appendix in the camera ready.
2. Assumption 2 (non-negative rewards): This assumption matches current practice in applying RL to verifiable reward signals (i.e., 0/1 rewards). The consequence of not having this assumption is that, in general, the agent might learn to think forever to avoid receiving negative reward.
3. Assumption 3 (reachable positive reward): This assumption simply states that the agent always could reach some positive reward in finite time from any state. This will generally hold for LLM agents and is also a mild assumption that basically says the MDP is interesting in the sense that the agent can possibly produce reward.

Questions:

1. Above we have discussed ways to adapt the key assumptions. If we’re missing some assumptions that you would like to discuss, please let us know.
2. See discussion above. Our understanding is that works using RL on LLMs are treating tokens as actions since tokens are the outputs of the underlying auto-regressive transformer model.
3. Based on our discussion above, we’re not sure what this method would look like as we believe many of our assumptions are relevant to LLM training. We want to emphasize that developing a new procedure for training LLMs was NOT a goal of our work.

We hope our response addresses your concerns and we are happy to discuss any of these points further!

[1] DPO meets PPO: Reinforced Roken Optimization for RLHF

[2] Stop Anthropomorphizing Intermediate Tokens as Reasoning/Thinking Traces!

[3] RL in Name Only? Analyzing the Structural Assumptions in RL post-training for LLMs