When Can Model-Free Reinforcement Learning be Enough for Thinking?
Authors: Josiah P. Hanna
Nicholas E. Corrado
Venue: NeurIPS 2025 poster ()
Keywords: reinforcement learning
thinking
model-free
planning
Primary area: reinforcement_learning
TL;DR: This paper answers the question: "under what conditions will model-free reinforcement learning give rise to thinking as a strategy for reward maximization?"

Abstract: Recent work on large language models has demonstrated the use of model-free reinforcement learning (RL) to train reasoning-like capabilities. The emergence of "thinking" through model-free RL is interesting as thinking actions neither produce reward nor change the external world state to one where the agent is more likely to get reward. This paper seeks to build a domain-independent understanding of when model-free RL will lead to such "thinking" as a strategy for reward maximization. To build this understanding, we first introduce a theoretical model which we call a thought Markov decision process (MDP). Thought MDPs minimally extend the classical MDP model to include an abstract notion of thought state and thought action. Using the thought MDP model, we prove the importance of policy initialization in determining whether or not thinking emerges and show formally that thought actions are equivalent to the agent choosing to perform a step of policy improvement before continuing to act. We then show that open-source LLMs satisfy the conditions that our theory predicts are necessary for model-free RL to produce thinking-like behavior. Finally, we hypothesize sufficient conditions that would enable thinking to be learned outside of language generation and introduce a toy domain where a combination of multi-task pre-training and designated thought actions enable more data-efficient RL compared to non-thinking agents.

When Can Model-Free Reinforcement Learning be Enough for Thinking?
Josiah Hanna
Nicholas E. Corrado Computer Sciences Department University of Wisconsin Madison ncorradowwisc.edn
Computer Sciences Department University of Wisconsin Madison jphannadcs. wisc. visc.edu
Abstract
Recent work on large language models has demonstrated the use of model-free reinforcement learning (RL) to train reasoning-like capabilities. The emergence of "thinking" through model-free RL is interesting as thinking actions neither produce reward nor change the external world state to one where the agent is more likely to get reward. This paper seeks to build of when model-free RL will lead to such "thinking" as a strategy for reward maximization. To build this understanding, which we call thought Markov decision process (MDP). Thought MDPs minimally extend the classical MDP model include abstract notion of thought state and thought action. Using the thought MDP model, we prove the importance of policy initialization in determining whether or not thinking emerges and show formally that thought actions are equivalent to the agent choosing to perform a step of policy improvement before continuing to act. We then show that open-source LLMs satisfy the conditions that our theory predicts are necessary for model-free RI. produce thinking-liks behavior. Finally, we hypothesize sufficient conditions that would enable thinking to learned outside of language generation and introduce a toy domain where combination of multi-task pre-training and designated thought actions enable more data-efficient RL compared to non- non-thinking agents.
comain-inddepedeen understanding
first introduce theoretical model
Introduction
Dual process theory divides cognitive processing into System I and System 2 processing [Wason and Evans, 1974, Kahneman, 2003]. System processing is fast, effortless, but potentially impre- cise, whereas System 2 is slow, effortful, but potentially produces better decisions. In the field of computational reinforcement learning (RL), model-free learning is reminiscent System behavior, whereas model-based decision -tie planning is reminiscent of System 2. While dual process theory a popular model for understanding human cognition [Kahneman, 2011], there no single clear candidate architecture for its duplication in artificial agents.
In the context of large language models (LLMs), recent work by Guo al. proposed unified model whereby System 2 type "thinking" emerged as consequence of model-free RI applied to solve mathematics problems (2025). While this "thinking" appears to resemble thoughts that human would have when answering given query, these outputs arise solely as subservient to reward maximization. The approach is interesting as it suggests that a form of System 2 processing can emerge when we view thinking as control and reinforce thought patterns that lead to reward. Our objective is to develop a domain-independent understanding of the conditions under which model-free RL will select for thinking behavior. Specifically, we want answer the question:
Under what conditions will model-free reinforcement learning give rise to thinking as a strategy for reward maximization?
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Informally, we define thinking to be actions that do not directly produce reward or affect the external state of an agent's environment but that lead the agent to take course of action that increases the reward it will receive in the future. To answer our research question, we first formulate a minimal extension of the classical MDP model explicitly model thought actions and a notion of a controllable thought state. We then show how policy initialization plays a central role in whether policy iteration will select thought actions. Under our theoretical model, as selecting between a set of sub-policies that are already contained in the learning agent's 's policy function and that thought actions can be interpreted the agent choosing run one more steps of policy improvement before continuing to act. We then discuss how LLMs instantiate our thought MDP formalism and provide empirical evidence that they exhibit the necessary conditions for thinking to emerge. Our final contribution is to introduce a simple domain and multi-task pre-training set-up that induces the condition under which model-free RL will discover thinking behavior. This simple domain provides basis for future work studying agents that learn to think and act. We conclude by discussing open questions and directions for future work raised by this model of deliberative thinking in RL.
will show that thinking can be viewed
2 Related Work
In this section, we discuss the prior literature related to System 2 processing in RL as well as prior models of "mental" actions an agent can take.
Decision-time Planning A hallmark of System 2 processing is deliberative planning as opposed to reflxiive action. Thus, natural way to instantiate System 2 in artificial agents is to use decision-time planning. e.g., Monte Carlo tree search [Kocsis and Szepesvári, 2006], and many works in the RL literature have used this approach [e.g.. Anthony et al., 2017, Silver et al., 2016, 2017, Silver, 2009, Schrittwieser et al., 2021, Shah et al., 2020]. Decision-tim time planning is particularly effective when the agent's 's policy or value function is sub-optimal but the agent possesses an accurate model of state transitions [Sutton and Barto, 2018]. In this case, planning can be viewed as focused policy improvement to improve the decision at the agent's ' current state before it acts. As we will show, the idea of thinking as local policy improvement also applies when RL agent learns to think in our new thought MDP model. The key difference is that we consider a more abstract model of thinking without any notion of forward prediction and search. Furthermore, there is also no natural answer to the question of when to stop planning and act with most decision-time planning methods. MCTS is an anytime algorithm and the general practice is to allow as much search is possible in the application domain [Silver et al., 2016, 2017]. On the other hand, model-free learning our thought MDP model will directly relate the decision about when to stop thinking to the objective of return maximization. Some work in the (non-learnig) planning literature has also studied the question of when to think vs. when to act [Cashmore et al., 2019, Coles et al., 2024].
As neural networks are general-purpose purpose function approximators, they can, in principle, learn algorithmic planning reasoning computations and prior work has attempted to induce planning capabilities through specialized architectures ['Tamar et al., 2017, Farquhar et al., 2018, Guez et al., 2019, 2018, Niu et al., 2018, Weber et al., 2018, Sykora et al., 2020, Schleich et al., 2019, Oh et al., 2017]. Guez et al. showed that planning like computations could emerge through model-free learning (2019) and Bush et al. [2025] applied mechanistic interpretability approaches to show that the approach of Guez et al. [2019] did in fact learn planning computations (i.e., the network internally learned to propose and evaluate future candidate action sequences). While such works also show that model-free RL can produce thinking behavior, the main difference is that thinking refers to the computation done by the agent's 's policy, whereas we study thinking as an action selected by the agent's 's policy. More similar to this conception of thinking, the thinker architecture (Chung et al. [2023], Wang et al. [2025]) trains a policy to select actions both for environment interaction and planning in learned model. In contrast, we consider model-free conception of thinking.
Learning to Plan
In the past couple of years, a large number of methods have been developed to create System 2 capabilities in LLMs, with particular emphasis on math and coding problems. One prominent approach is chain-of of-thought (CoT) prompting in which a user changes their query to include explicit examples of correct responses [Wei et al., 2023]. A more basic variant of CoT is just to prompt the model to "think step by step" [Kojima et al., 2023]. Many other variations have also been proposed [c.g., Yao et al., b023a,b, Wang et al., 2023]. Another paradigm has been to augment
Reasoning in LLMs
2

---

output generation with an explicit search procedure [e.g., Khanov et al., 2024, Liu et al., 2023, Zhou al., 2023, Zhang et al., 2023, Chen et al., 2024]. Finally, recent works have used model-free RL to train LLMs to output CoT reasoning [Guo et al., 2025, OpenAI et al., 2024]. Our work takes inspiration from these works but aims go beyond L.MS in understanding when thinking-like behavior can emerge in RI. agents.
Cognition as Action The idea of thinking as a form of action has a long history in Al and RL. Minsky theorized on the mind as a society of agents whose collective actions produce cognition and action [Minsky, 1986]. Klopf"s hedonistic neuron hypothesis modelled neurons as individual RL agents [Klopf. 1982]. This hypothesis has led to line of work studying alternative neural network architectures in which artificial neural activity is produced by the stochastic policies of simple RL agents [Thomas, 2011, Kostas et al., 2019, Gupta et al., 2021]. J. More similar to our work, some prior work has considered augmenting the agent's 's environment action-space with form of mental action. These works have focused on the challenge of memory in partially observable domains and using explicit memory read or write actions as an alternative to recurrent neural networks. For instance, Peshkin et al. [2001] augment an RL agent with a set of memory write actions and the contents of the memory are then provided to the agent as an additional input along with the environment state; Zhang al. [2015] extend this approach to robot manipulation tasks. Various neural architectures have been developed with external memory that can be written to and read from [e.g., Graves et al., 2014, Zaremba and Sutskever, 2016] and Oh al. [2016] explored these architectures for RL. The thought MDP model differs in that the agent has access to Markov state representation and so thought actions serve to manipulate the agent's 's policy opposed to remembering details of the past. Prior work has used the framework of rational meta-reasoning to study computation selection as a form of action [Hay et al., 2012] and even consider using RL to learn a computation selection policy [Callaway et al., 2018]. These works differ in that they study choosing among concrete computations as opposed to the abstract model of thinking as manipulating the agent's 's internal state that we consider.
The Options Framework Finally, thought MDPs are related to the options framework that is often used in hierarchical RL [Sutton et al., 1999]. In the options framework, the agent's policy is over set of options where options are either primitive actions or sub-policies. The crucial difference is that in the options framework, the selection of an option and the execution of that option's 's first action both occur within a single time step. whereas this execution would take at least two steps in thought MDP. This difference suggests that thought MDPs might naturally model the cost of switching options, particularly when the agent cannot directly set its thought state and must instead think for multiple steps to select the best option. Thus, thought MDPs might be particularly useful as an alternative to the options with deliberation cost model [Harb et al., 2018].
3 Formal Model
In this section, we first formalize the standard RL problem using the MDP formalism and then introduce the thought MDP model to explicitly model thinking.
3.1 RL in Markoy Decision Processes
RL environments are typically modeled as Markov decision processes (MDPs). Formally, an MDP tuple, (S, A. p. r, 7), where S the environment state space, is the set of actions that the agent can take to influence the environment state, p: S x A + A(S) is stochastic state transition function, r S A + IR a realar-valued reward function, and y is a discount factor. At any moment in time, the agent is in state St, takes an action, A,, receives a reward, Re = r(S,, Ar), and transitions new state, S Then the process repeats from S441 until special terminal state, 8xc, is reached. The agent selects actions according to a policy, π7 > (AAA). The value of using policy from a partieular state, 8, is defined be (s) == E, Ex 7 Re s). In RL, the agent's 's objective is to find a policy that maximizes U. (s) in all states.
3.2 Thought MDPs
We now extend the MDP model to explicitly model thinking. We formally define a thought MDP p,p,
PT), where S and A are the environment's 's state and action space as the tuple (S, A,,,,, T, respectively and p, r, are defined as they are for MDPs, We add T as the set of thought states, C as
3

---

the set of thought actions, and pr: S x T x our informal definition of thinking in the introduction, we emphasize that thought states and actions do not affect environment state transitions and rewards. The agent's 's objective remains to maximize cumulative discounted reward across all environment states.
A(T)
as the thought transition funetion. Recalling
Policies in Thought MDPs There are different ways to define the agent's policy in a thought MDP. In this work, we formalize policies as a mapping я S x T - AAA (AUC). This choice means that the agent can select either an environment action or a thought action at any interaction time-step but not both. We make this choice to connect to work in LLMs that inspired this model, but an alternative is that the policy is a mapping क : S T + A [ x C), i.e., the agent can think and act at the same time. Such modelling might be more appropriate for real-time domains where the agent cannot simply sit and think as the rest of the world evolves around it. There, of course, may be other alternatives that could be considered in future work. Below, we will use the notation x (T) to refer to the agent's s state-dependent policy with the thought state fixed at T.
Interaction in Thought MDPs In a thought MDP, interaction proceeds as follows. Episodes begin in an environment state, Sp, and thought state, To, and the agent chooses either an environment action or thought action according to its policy. Let Ag be the random variable denoting this choice. If Au E A then the environment state, S1. at the next time-step is sampled from (( Ag), the thought state keeps the value of Tu. and the agent receives reward Ro = r((So. Au). Conversely, if Ao E C, then S1 keeps the value of Sp. Te is sampled from PT (-1So To. Co). and the agent receives Rg 0. Then the process repeats with the agent selecting either an environment or thought action from its policy until the agent reaches a special terminal state 8 E S. For thought MDPs, we define the
value function to be Uz (8, 7) = E, (E= Re = 8, T0 = T].
Key Assumptions We aim introduce a general model of thinking in MDPs, however, our subsequent analysis will make two assumptions which we state formally here. First, we assume that thought state transitions are deterministic in order simplify our analysis and because it is also the case for LLM agents.
Assumption 1 (Deterministic Thought Transitions). Vs E S, E T, E pT T, c. = 1 for one and only one r' E T. We will write py (s, r, E T to denote the thought state that results from taking e in (s, r).
Second, we assume that all rewards are non-negative as otherwise thinking could emerge as a strategy solely for the purpose of putting off receiving a negative reward. i.e., if all rewards are negative then the agent will be incentivized to just keep taking thought actions rather than environment actions.
Assumption 2 -egatveg Rewards). Vs E S, a E A, r(s, a) 2 0.
Finally, we assume reachable positive reward from all states, otherwise there will exist states where the agent is indifferent to whether it takes a thought action or an environment action.
Assumption 3 (Reachable Positive Reward). 3s E S,a a E A with r(s, a) > and V/ E S there exists policy such that the probability of transitioning from 8 to in finite number of steps is greater than zero.
Modeling of Time Our formalism raises questions about how time should be treated for the two forms of action. First, should the discount factor be applied equally for both thinking and non-thin time-steps? Equal application discourages thinking as thought actions do not influence reward either directly or indirectly through the environment state. Nevertheless, as we shall see, thought actions still might be selected if they ultimately cause the agent to choose a better environment action. Alternatively, we could apply a different discount factor for thinking time-steps to reflect the actual time-delay of thinking compared to acting in a given domain. For example, if thinking takes (1/k) the
time of any environment action then we could use discount of - In this work, we will assume that the discount applied the same at both thinking and non-thinking time steps. The second related issue is that the proposed model assumes that the environment state remains constant while the agent takes thought actions. Such an assumption might be reasonable for relatively static environments (such as
'We hase the thought MDP model on the widely used discounted problem formulation. In Appendix Appendix B, we extend the thought MDP model and theoretical results to the undiscounted, horizoo setting which more closely resembles contemporary applications of RL to LLMs.

---

Pelcy and Values at lteration 1
Policy and Velues at Iteration
Thought Statte
Value
Policy lteration
Environment States
(left) example thought MDP with [T| 2. We use |S| in our illustrative results. The agent receives reward when it reaches the goal environment state on the far right. The agent can move left or right in the environment state space and up and down the thought state space. We use = 0.9 for both thinking and non-thinking time-steps. (right) Evolution of the policy and state values for 4, and 10 iterations of policy iteration. The policy is initialized as shown on the left. Colors indicate value and arrows indicate the action that the policy would take.
Figure 1:
generating text board games) but is problematic in dynamic environments (such autonomous driving) where waiting act can be consequential. Again, for simplicity, we will focus on the static environment case, but note this issue as another interesting direction to refine the model.
Optimality Thought MDPs are MDPs with state space S T and action space A U C and consequently there will always be least one deterministic optimal policy [Sutton and Barto, 2018). Furthermore, we can show that this optimal policy will never select thought actions.
Proposition 4. Any optimal policy, π¹ for thought MDP does not take thought actions: π (S,T) A, Vs E, T.
Proof. The proof is by contradiction. Suppose x² is an optimal policy and 3s E S, T such that (s. E C. Because thought actions cannot produce reward, the optimal policy must eventually reach thought state, F, where T" () E A. If that happens after & thought actions, then Ug u (s, y ug (s, 7). But then the policy could be strictly improved by setting æ (s, T) < x (s, This contradicts the assumption that x²* was optimal and completes the proof.
Policy Initialization Determines Emergence of Thinking
the optimal policy would never take a thought action, why should we expect thinking to emerge as strategy during policy improvement? In this section, begin answer this question by showing the key role that policy initialization plays in determining the emergence of thinking. In particular, we first consider exact policy iteration within a thought MDP and provide illustrative example and a formal result showing how thinking can emerge. We use policy iteration for analysis as essentially all model-free RL algorithms can be understood and Barto, 2018]. then provide a second formal result showing that thought actions can reduce the effective horizon [Laidlaw et al., 2023] for the special case of goal-MDPs.
instances of generalized policy iteration [Sutton
An illustrative example For exposition's 's sake, suppose T {oo, J. in which case the agent's policy, π,, as consisting of two sub-policies, (T)) and πTT)). Now consider the example depicted in Figure where π (TT) is initialized sub oobbmmallllly (always takes an action that leads away from the goal) while π xTT)) is initialized be optimal. We show the progress of policy iteration in this domain in Figure 1. After the first iteration of policy improvement, the policy has learned to first change the agent's thought state 7i (top row) from which it then follows π (π()) reach the goal. After four iterations, in environment states close to the goal, the policy just directly moves right without changing its thought state while continuing first take thought action in states that are far from the goal. Finally, after ten iterations, the policy converges to the optimal policy and simply moves to the right without thinking. This example shows that, while thinking is sub-optimal the long-run, it can be beneficial early in learning by allowing the agent to use sub-policies already contained in its policy function.
view
5

---

To formally understand how policy initialization determines the emergence of thinking, we analyze the policy improvement step of policy iteration.
Theorem 5. Let πI be policy in thought MDP such that π(s. E A some environment state and thought state т. If the policy improvement step of policy iteration sets n' rs,TT) < c. c E C, then Un (8, T') > (8( where r' is the thought state resulting from laking in (8,
Proof. Policy iteration sets T (8,,, T) f arg maxaEA.C Qu (s, T,O) where
(- a,)) = [r(s, a) + Lu r)] (v,n(,
A
Since the policy improvement step is selecting thought action, we have that:
Va E A, 4- (8, a) < y0u (8, (8,
Since (ss, 7) was in A before the update we have that:
Ux (s, 7) Oo (s, T, (s, 7)) < yux (8, 7') U (s, 7') = (8,
Thus, thought action is selected when the policy is such that changing the thought state to 7' will lead to a greater expected return from than when leaving the thought state at T.
Although, Theorem 5 does not directly say anything about policy initialization, the condition for thought action to be selected requires (T)) and m(T') to be somehow set up as different such that there could be an advantage in shifting from T to T'. Thus, policy initialization is critical for whether thinking will emerge or not.
Theorem 5 deals with exact policy iteration and does not address the impact of policy initialization on the emergence of thinking when learning from samples. We next turn to the concept of the effective horizon introduced by Laidlaw et al. [2023]. The effective horizon was introduced as a problem complexity parameter for MDPs that aligns with the observed difficulty of common RI. benchmarks. Laidlaw et al. then derived sample complexity bounds for model-free RI. algorithms in terms of the effective horizon and showed that these bounds were predictive of the success of deep RL algorithms on benchmark problems. We will build upon their specific result on goal MDPs.
Definition 6. A goal (thought) MDP is (thought) MDP with a set of absorbing environment states, Sgoal S, and r(s, a) = 1 s E Sgoat and otherwise.
For goal MDPs, Laidlaw et al. [2023] showed that the effective horizon, H can be upper-bounded by + log 20 where / is a maximum episode length, p S Prexpa (ST E Sgeat (s, ar) is lower bound on the probability of the initial exploration policy. Txpp1 discovering goal state after taking action a in state s at any time-step. Intuitively, if p is larger, then an RL algorithm has an easier time discovering rewarding action sequences. We next show that thought actions can be used to reduce the effective horizon of given instance. Note that Laidlaw et al. [2023] proved their results assuming deterministic MDPs, so we also adopt this assumption for the next proposition.
Proposition 7. Suppose we have a goal thought MDP that has T = [70, T.)- Let the initial policy, n, be such that there is some Po such that Pr(st E 8geal (s, a. (T))) > Po for all (s,a) S x A and some p1 such that Pr(st- E Sgoal (s, a, π (Ti)) > for all (s, a) E S x d. Let C2 be the thought action such that then thought actions reduce the upper bound on the effective horizon of the MDP.
(T To, Ca) and let pe lower bound the probability [c, To). If PP > po-
See Appendix A for the proof. Intuitively, policy TTT)) has higher probability of finding a goal state from any state compared to simply running (To)). If the probability of taking thought action that changes To to 71 is not too low then it is easier to find goal state by first changing the thought state and then executing π (T1). Again, this result suggests that the benefit of thinking depends crucially on policy initialization.
Thinking as a Policy Improvement Operator
One interpretation of Theorem 5 is that thought actions can function policy improvement operators applied to particular state. This interpretation is interesting as it aligns with the use of decision- time planning in RL to refine agent's choice of action in a way that focuses computation on its current

---

state [Sutton and Barto, 2018]. While thought actions do not involve look-ahead search with model, Theorem 5 shows that their utility is also in providing local policy improvement. Theorem 5 shows this utility for the choice of a single thought action and we also present a corollary showing that if policy improvement produces policy that thinks for consecutive steps in s then each thinking step will further improve upon the action x T).
Corollary 8. Let be thought action that leads from T to and d' be thought action that leads from T' to 7" If. in some environment state the policy improvement step of policy iteration sets x' (8,,,) <- c. caand N/' (s) t- C, then Un (8, r") )" Un u=(8, ) > Uz (s(
Proof. The inequality (8, > Ux (8 7) immediately follows from Theorem 5. The inequality "x(s,7" > Uz ux(ssT') T') follows from the same logic as the proof of Theorem 5 except applied to improving the policy in (s,
If each step of thinking in improves the policy, (88 :), when should thinking terminate? From the proof of Theorem 5, we can see that thinking will terminate when the increase in value from thinking another step no longer compensates for the discounting of value caused by waiting step to begin taking environmental actions. In this way, thought MDPs directly tie the "when to think" decision to the objective of reward maximization.
5 Language Generation as a Thought MDP
Our work takes inspiration from recent work on large reasoning models (LRMs) that "think" by generating additional text that is not part of the final answer but that somehow serves to improve the final answer. In this section, we review two approaches to imbue LLMs with reasoning capabilities and describe how they can be viewed instantiating thought MDPs. We then show that forcing the LLM to reason (in a manner similar to zero-shot tfain-of-thoughhe [Kojima et al., 2023]) increases the expected return from given state. Thus, Theorem 5 predicts that model-free RL applied to this thought MDP would lead to thinking, which is in fact what recent work has found.
We first describe language generation as an MDP and then describe the thought states and actions of LLMs. In language generation, each episode begins with textual prompt, and the agent's 's actions are possible tokens from a fixed vocabulary. Let y be the agent's 's output at time t. The state at time t is defined as the prompt concatenated with the agent's 'ssss outputs up to time L, 8 = (æ, V1.a). Rewards for RL applied to language generation have been defined in different ways. Much of the recent work on reasoning models focuses on math and coding problems, which have verifiable solutions. Thus, the reward is terminal reward of if correct solution can be parsed and verified from yı.t-
Reasoning with Language as a Thought MDP The main difficulty in mapping language generation to thought MDP is that thought states are intertwined with environment states in the typical MDP formulation for LLMs. Similarly, thought actions are simply from the same space as environment actions. To distinguish these components, we redefine the environment state as just the query and tokens that function as part the query response. Next, we define environment actions as just outputs that will affect how the overall response is evaluated and thought actions as the outputs that will not. Thus, the determination of whether one output considered an environment or a thought action will depend upon the current context up to that decision. Finally, the thought state at time t consists of the already produced tokens in yi:t that will not affect how the response is evaluated.
Different approaches to inducing reasoning in LLMs use different schemes for determining which tokens are part of the final response and which only serve to improve the final response. For example, Guo et al. [2025] augment the output vocabulary with two special functional tokens, <think> and </think>. In addition to the sparse verifier reward, Guo et al. train DeepSeek-R1 with reward shaping to encourage valid thinking blocks in which <think> is followed by </think>. Output text in thinking blocks is not part of the final response that is passed to a verifier to determine reward and would thus constitute the thought state. Zero-shot prompting is another approach to encourage thinking-like like behavior by appending "Let's think step-by-step" to the query [Kojima et al., 2023]. In this approach, answer parser is used to separate the response (environment actions) from the additional prompt and subsequent reasoning tokens (thought actions). The outputs that are discarded by the parser would constitute the thought actions.
7

---

Model
No Thinking (%)
Thinking (%)
Qwen2.5-1
7.20 0.82
71.20 2.80
Owen2.5-3B-Instruv
6,80 + 0.80
36.50 + 1.52
Owen2.5-7B-Instre
5.06 + 3.10
96.10 2.98
Swen2.55-14BIInsttuu
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 3310
Llama-2-76
0.00 + 0.00
48.80
Llama-2- 2-13b
0.20 0.27
00.70=3.00
Gemma-3- 1--ii
0.50 + 0.43
41.50 3.06
Gemma-3-4b-it
4.90 1.33
91.50 1.72
Miistral-7B-Innttrutt--0
1.50 + 0.74
85.20 + 2.20
Table 1: Response accuracy + 95% confidence interval when using thinking vs no thinking,
Do thought actions improve expected return in LLMs? Recent work from Guo et al. [2025] has shown that thinking-liik behavior can emerge from RL. Based our theory, we hypothesize that a pre-connition for this result is that thought actions increase Vr (s, T) by changing the thought state т. Because we lack a value function for each LLM, we instead approximate 2n (s, with the Monte Carlo return or, equivalently, the accuracy of the LLM's response. Our hypothesis is that forcing the L.M to think will increase this value. Note that we use the Monte Carlo return as opposed just looking the immediate probability of the correct response (or its perplexity) to allow for the possibility that the LLM will generate its own reasoning and then answer correctly. To test our hypothesis,
take different pre-trained LLMs and apply them to add series of five four-digit numbers. We use models of various sizes from the following model familes: Qwen-2.5 [Yang et al., 2024, Qwen Team, 2024]. Tulu-2 [Ivison et al., 2023]. LLama-2 [Touvron et al., 2023], Gemma- [Gemma Team, 2025], and Mistral [Jiang et al., 2023]. We test two conditions with each model: "No Thinking" and "Thhiking." Under the "No Thinking" condition, the prompt is "Compute the sum: [a] + [b] + [c] [c]+[dd + [e] = where [a], [b], [c], [d], and [e] correspond four-digit integers. Under the "Thinking" condition, we append "[a b] + [c] + [d] [e] [a b + c] [d] + [e] = [a this prompt, where bb and [a + b b+bo denote the partial sums a+b and a+b+c. In essence, we force the model to first think under the "Thinking" condition. We constuct 1000 "Thinking" and 1000 "No Thinking" prompts like these using 1000 different sequences of four 4-digit integers, each generated uniformly at random (see Appendix D for example prompts). Table I shows the average accuracy for each model. For all models, we see that appending the thinking tokens increases accuracy, which corresponds to increasing un (s, r) by changing т. While we do not further apply model-frec RL to try and learn to think in this way, our theory and these results predict that these models are primed for thinking to further emerge as a strategy.
+ b d]+ + [e]=
6 A Non-Language Thought MDP
Our work takes inspiration from work on LLMSs but aspires to understand how RL can lead to thinking in domains beyond language generation, possibly including agents that think in sequences of images [Ghazanfari et al., 2025, Wiedemer et al., 2025] or more abstract spaces [Hao et al., 2024]. One of the most important open questions is where do thought MDPs and initial thought-conddtioned policies come from outside of LLMs? In this section, we hypothesize about generalized ingredients for a setting where thinking emerges as a useful strategy for reward maximization. Specifically, we hypothesize that the key ingredients may be multi-task pre-training coupled with the agent having the ability to manipulate its internal state to activate pre-trained abilities. LLMs fit this hypothesis: self-supervised pre-training enables LLM agents to generate responses to many different contexts and language actions enable RL RL-finetuning manipulate the input context to activate these existing capabilities when doing so will produce reward. To test this hypothesis, we set out to construct a non-language toy domain with these characteristics and to see if thinking could enable the agent to reach a higher return compared non non-thinking agents. Code for these experiments available at https: / gi thub. com/ pr rrreiictoon action- waabbbhiikingg.. as as-control.
We design 5x5 gridworld where the agent move in the cardinal directions output of three special actions, 'A', 'B', or 'C' that have no direct effect on the environment. Each special action corresponds to possible task in the gridworld: 'A' corresponds to navigating to the lower
8

---

0.6
Retoaed
0.8
Poetee Trinkig
B
0.4
0.0
Success
0.3
0.4
02
0.2
0.1
0.0
A
0.0
8
20
40
6ll
80
100
20
40
60
8D
100
Iteration
Iteration
(a) Gridworld Domain
(b) Success Rate
(c) Fraction Thinking Time
Figure 2: Mean learning curves for the four agents we train in the gridworld environment. The vertical axis gives the success rate for first navigating to the bottom right and then the top left corner. The horizontal axis is the iteration of policy improvement (the agent collects 200 episodes at each iteration). We run 20 trials for each learning agent and shading indicates a 95% bootstrap confidence interval. Light lines show individual training runs.
right corner, 'B' corresponds to the upper left corner, and 'C' corresponds to going to the lower right corner and then to the upper left corner. Note that these special actions do not explicitly have these effects in the domain but will become associated with these behaviors through pre-training. At the start of each episode, the agent receives one of these special actions part of its observation.
We pre-train an initial policy through behavior cloning on an agent that "plays" in the gridworld. Specifically, at each time-step, this agent samples a new special action with probability 0.2 and subsequently acts optimally for the corresponding task until it succeeds or samples a new task (a new task is also sampled upon sub-task completion). During pre-training we only consider special actions 'A' and 'B' that the agent has experience with 'C'. The result of this procedure is policy that wanders back and forth between the upper left and lower right corner while randomly changing its mind about where it is going. For the policy, we use causal transformer [Vaswani al., 2017] that conditions the probability of its action choice on the full episode history up to time t. As actions are included in this history, the special actions can manipulate the internal state of the agent even though they do not affect the environment state.
After pre-training, we use vanilla REINFORCE [Williams, 1992] and train the agent to complete the task corresponding 'C'. The reward received is 1 when the agent is successful and 0 otherwise. Our hypothesis is that the ability to output 'A' or 'B' will enable a learning agent using the pre-trained transformer activate skills learned during pre-training complete the more challenging task. We test four agents: Pretrained- Think, Pretrained- Think, Seratch-Think, and Scratch-NoThing The NoThhnkk agents have the special actions masked and the Scratch agents are trained from scratch rather than initialized from the pre-trained model.
In Figure 2 we see that Pretrained-Thinn learns significantly faster than the other agents. The sparse reward makes learning from scratch impossible with without thinking. Pretrained-NoThin also begins to learn the task, though it takes many more iterations to do so. This result was initially surprising to and prompted further investigation on why pre-training helped even without thinking. The apparent reason is that sequences of environment actions can also serve to trigger the pre-trained policy's 's sub-task behavior in way similar to thought actions. For example, if the agent moves down 2-3 times in a row then the agent will tend to continue to goal 'A' at the bottom right. Nevertheless, is more difficult to discover such sequences compared to taking single thought action.
We also investigate if thinking is actually what is learned by Pretrained- Think. Figure 2 shows that the agent initially takes a thought action about 30% of the time and this fraction falls as it learns and then stabilizes at about 15% Optimal episodes are 14 steps long and the optimal amount of thinking barring the agent figuring out the true optimal policy - is 2 times which is approximately 15% of all time-steps at convergence. We observe trained agent and confirm that it first outputs 'A,' navigates to the bottom right, outputs 'B,' and then navigates to the top left.
Finally, we note that thought actions do not go away as the policy converges in contrast to Proposition 4 which states that the optimal policy only takes environment actions. We suspect that
IIn Appendix E. we also include results for the case where tasks 'A' and 'B' are slightly different from the sub-ta tasks needed to complete task 'C.'

---

this finding is due to sampling error that can cause poor convergence of on-policy policy gradient methods learning from finite samples [Corrado and Hanna, 2023]. As the agent discovers the strategy to first think and then act, it puts increasingly less probability on immediately taking the optimal action. Consequently, it never accidently discovers the benefit of taking immediate action to reach the goal a step or two earlier.
7 Limitations for Future Work
In this section, we discuss possible extensions for research in thought MDPs. Due to space constraints, we only describe a few directions while briefly noting that further research should consider extensions to partially observable worlds and connections to natural intelligence and the options framework.
Where do thought MDPs come from? This work studied the question of why thinking actions could be useful to an RL agent even though they leave their environment state unchanged and produce no reward. We formalized this abstract notion of thinking with the thought MDP model, but left open the big question of how to define the thought states, actions, and thought dynamics in other RL problems where thinking may be useful. Language generation is one example, but it is an open question as to how thought MDPs might arise outside the language domain. There is also the question of where existing noought-conditione policies come from, as work showed their existence to be a key enabler of emergent thinking. In Section 6, we explored the hypothesis that multi-task pre-training could be key ingredient but this experiment was only designed as proof-of-concepl. In the future, it would be interesting to extend this exploration to more complex and realistic domains such as rohots using pre-trained aaioo-language-cttnnnn action models or visual reasoning tasks using video models [Wiedemer et al., 2025]-
Connecting to Models and Planning System 2 processing is reminiscent of decision-time planning using a model of the environment state transition function [Anthony et al., 2017]. This work has presented a more abstract model of thinking where the agent simply learns to control an internal thought state. While distinct models, both decision-time planning and thinking in a thought MDP are related in that they amount to locally focused policy improvement [Sutton and Barto, 201 8]. Furthermore, having thought states and actions that are somehow grounded in environment states and actions could present an opportunity for explaining how the agents' thought dynamics should be structured. starting point for this future work could be the Thinker architecture [Chung et al., 2023], which learns a single policy both for planning in a model (including deciding when to reset the search) and acting in the real world.
Thinking in Dynamic and Time-constrained Domains This work has only considered the utility of thinking in relatively static domains where the environment state remains the same during thinking. In reality, the environment state may change due to influences other than the agent's 's actions. and the choice to stop and think must factor in how the environment might change while it does so. A natural extension would be to have thought states and environment states unfold in parallel to one another, with the agent thinking and acting at the same time.
Agents with Bounded Capacity Could the utility of thinking be enhanced under constraints? We take inspiration from the Big World Hypothesis [Javed and Sutton, 2024] which states that agents will always have less capacity than what is required to learn all possible tasks. Consequently, when an agent is faced with new task it may have either never seen it or have forgotten how to do Thinking might allow rapid repurposing of an agent's present capabilities to learn quickly on a new task. The sub-policies that are more frequently used would be repeatedly reinforced whereas less frequently used sub- sub-policies could be forgotten.
Conclusion
In this work, we investigated the question of when model-free RL will lead to "thinking" behavior. We introduced the thought MDP model and then used this model to show that thinking emerges as a strategy to manipulate an agent's internal state so as to improve an agent's ultimate choice of environment action. Consequently, the emergence of thinking depends upon a policy initialization that implicitly contains sub-policies that can be triggered by taking thinking actions. We then provided supporting evidence that step-by-step reasoning in LLMs functions similarly to the thought actions in this theoretical model. Finally, we developed non- lon-aang domain in which thinking would emerge as a strategy for reward maximization and discussed the many exciting next steps for developing AI agents that learn to think.
10

---

Acknowledgments
We thank Xiaojin Zhu and Adam Labiosa for much discussion and comments that improved the final version of this work. This work took place in the Prediction and Action Lab (PAL) at the University of Wisconsin Madison. PAL research is supported by NSF 10S21,,,,,1), the Wisconsin Alumni Research Foundation, and Sandia National Labs through a University Partnership Award.
References
T. Anthony, 7. Tian, and D. Barber. Thinking Fast and Slow with Deep I Learning and Tree Search, Dec. 2017. URL httt:://axxiv.or/abbas..
08439. arXiv:1705.0880 [es].
Bush, S. Chung, U. Anwar, A. Garriga-Alonso, and D. Krueger. Interpreting Emergent Planning in Model-Free Reinforcement Learning, Apr. 2025. URL hwtp::ttt///xte org/ //g//b///at ////bb//250. 01871. arXiv:2504.01877 [es].
F. Callaway, S. Gul, P. M. Krueger, T. L. Griffiths, and F. Lieder. Learning to select computations. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2018. doi: 10. 10.448550/rXiv.11 171 ,068920 URL http://arxiv. /taaxaxivv..rr/ org/ Berg/abs//11 abb//711. 1et.//11....9..
M. Cashmore, A. Coles, B. Cserna, E. Karpas, D. Magazzeni, and W. Ruml. Replanning for Situated Robots. Proceedings of the International Conference Automated Planning and Scheduling, 29:665-673, July 2019. ISSN 2334-0843. doi: 10. (600/icass.v9911.355 URL https://ojss aaai. org/ index. http:/indx...ppppiiIeeee hww.aa///aatileeveee/eeeeeeea
Z. Chen, M. White, R. Mooney, A. Payani, Y. Su, and H. Sun. When is Tree Search Useful for LLM Planning? It Depends the Discriminator, Feb. 2024. URL http:/ http://xxxvvvoo/// wrw..brgggb...... wwwgga///////////// 10890. arXiv:2402.10899 [cs].
S. Chung, I. Anokhin, and D. Krueger. Thinker: Learning to Plan and Act. Proceedings of Advances in Neural Information Processing Systems (NeurIPS), Nov. 2023. URL https: wwwnreview.......... net/ for.mmidommunoooooo munEEB1aar.
A. Coles, E. Karpas, A. Lavrinenko, W. Ruml, S. E. Shimony, and S. Shperberg. Planning and Acting While the Clock Ticks. Proceedings of the International Conference on Automated Planning and Scheduling, 34:95-103, May 2024. ISSN 2334-0843. doi: 10. 10.1609/ccass... v33iica.p...3.4..... v34i1.31465. URL https://ojs aaai org/ /ts//nndxx.a/// phtpppppp/////eee CCAP//CAPPSSAA wwwaaaaeeieee//./..eeaaaaaeeeeee
N. E. Corrado and J. P. Hanna. On-policy policy gradient reinforcement learning without on-policy sampling. arXiv preprint 1oXi::33/1008900 2023.
G. Farquhar, T. Rocktäschel, M. Igl, and Whiteson. TreeQN and ATreeC: Differentiable Tree- Structured Models for Deep Reinforcement Learning, Mar. 2018. URL htttp://arxiv org/ abs/1710. 11417. arXiv: 1efi::1111...0 10.711.1111 11417 [cs].
Gemma Team. Gemma 3, 2025. URL https:///t/ee gle/ /eemaa
S. Ghazanfari, F. Croce, N. Flammarion, P. Krishnamurthy, F. Khorrami, and S. Garg. Chain-of- Frames: Advancing Video Understanding Multimodal LLMs via Frame-Aware Reasoning, May 2025. URL http:://axxii org/ abs/////./22// 00318.
A. Graves, G. Wayne, and Danihelka. Neural Turing Machines, Dec. 2014, URL http:://aaxatti prg/abe/1n 14010.5411. arXiv:1410.5400 [cs].
A. Guez, T. Weber, I. Antonoglou, K. Simonyan, O. Vinyals, D. Wierstra, R. Munos, and D. Silver. Learning to Search with MCTSnets, July 2018. URL http://arxiv.. www.aawwwww.../////a//eaa// 04697. 1rXiv:1802.044.
[cs].
A. Guez, M. Mirza, K. Gregor, R. Kabra, S. Racanière, T. Weber, D. Raposo, Santoro, L. Orseau, T. Eccles, G. Wayne, D. Silver, and T. Lillicrap. An investigation of model-free planning, May 2019. URL httt::///a//iii wwwpxiii.orr/abae httpg/abs19900 03559, arXiv: 03559 [cs].
D. Guo. D. Yang. H. Zhang. J. Song, R. Zhang. R. Xu, Q. Zhu. S. Ma. P. Wang, X. Bi, al. Deepseck-rl: Incentivizing reasoning capability in 1lms via reinforcement learning. arXiv preprins arXiv:2501.12948, 2025.

---

D. Gupta, G. Mihucz, M. K. Schlegel, J. E. Kostas, P. S. Thomas, and M. White. Structural Credit Assignment in Neural Networks using Reinforcement Learning. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2021.
S. Hao, S. Sukhbaatar, D. Su, X. Li, Z. Hu, J. Weston, and Y. Tian. Training Large Language Models to Reason in a Continuous Latent Space, Dec. 2024. URL httt:///taiiii org/ //////b///// aaa/ab/////////
J. Harb, P.-L. Bacon, M. Klissarov, and D. Precup. When waiting is not option: Learning options with a deliberation cost. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
N. Hay, S. Russell, D. Tolpin, and S. E. Shimony. Selecting Computations: Theory and Applications. In Proceedings of the Conference on Uncertainly in Artificial Intelligence (UAf). arXiv, July 2012. doi: 10.48550/arXiv12200 1207.5879) URL hattp://arxxa org/ abs/ 1207 .5899.
H. Ivison, Y. Wang. V. Pyatkin, N. Lambert, M. Peters, P. Dasigi, J. Jang, D. Wadden, N. A. Smith, I. Beltagy, and H. Hajishirzi. Camels in a changing climate: Enhancing Im adaptation with tulu 2, 2023.
K. Javed and R. S. Sutton. The Big World Hypothesis and its Ramifications for Artificial Intelligence. In The Finding the Frame Workshop at the Reinforcement Learning Conference, July 2024. URL net/ f
A. Q. Jiang, A. Sablayrolles, A. Mensch, C. Bamford, D. S. Chaplot, D. de Las Casas, F. Bressand, G. Lengyel. G. Lample, L. Saulnier, L. R. Lavaud, M. Lachaux, P. Stock, T. L. Scao, T. Lavril, T. Wang. T. Lacroix, and W. E. Sayed. Mistral 7b. CoRR, abs/2310.068255, 2023. doi: 10.48550/ ARXIV.2310.06225, URL https: /toii org/ 10. 0.000.485////// arXiv. 2310 06825.
D. Kahneman. Maps of bounded rationality: Psychology for behavioral economics. American economic review, 1445) 2003.
D. Kahneman. Thinking. fast and slow. macmillan, 2011.
M. Khanov, J. Burapacheep, and Y. Li. ARRS: Alignment as Reward-Guided Search, Jan. 2024.
URL http: /tstt://arrie aaxiv.xivvvv..i/ org/ abs /402. 01694. arXiv:2402.01694 [cs].
D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. In Proceedings of the International Conference on Learning Representations (ICLR). arXiv, 2015. doi: 10.48550/arXiv. att/aa/ss//a..////a///////a/aa 1412. 6980. arXiv: 1412::1412.6980 [es].
1412.6980. URL httt::///r/riiii org h/sg///b/////
A. H. Klopf. The Hedonistic Neuron: A Theory of Memory, Learning, and Intelligence. Hemisphere Publishing Corporation, 1982 ISBN 978-0-891 16-202-5. Google-Books-ID: KMXQAAAAMAAI.
L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. In European conference machine learning, pages 282-293. Springer, 2006.
Kojima, S. S. Gu, M. Reid, Matsuo, and Y. Iwasawa. Large Language Models are Zero-Shot Reasoners, Jan. 2023. URL http: tattt::/aarai http://axxvvvorgg/o/ httgg/abs/22000 2205. 11916. arXiv:2205.1 1112005511991 1916 [cs].
J. E. Kostas, C. Nota, and P. S. Thomas. Asynchronous Coagent Networks. In Proceedings of the International Conference on Machine Learning (ICML), 2019. URL httph:t////aatee org/ aba/ 1902. 05650v4.
C. Laidlaw, S. Russell, and A. Dragan. Bridging rl theory and practice with the effective horizon. Advances in Neural Information Processing Systems, 36:58953-59007, 2023.
J. Liu, A. Cohen, R. Pasunuru, Y. Choi, H. Hajishirzi, and A. Celikyilmaz. Don't throw away your value model! Making PPO even better via Guided Monte-Card Tree Search decoding, Oct. 2023. URL http://arxiii org/ abs/2300 15028. 1102022309.15028 [cs].
M. Minsky, Society of mind. Simon and Schuster, 1986.
S. Niu. S. Chen, H. Guo, C. Targonski, M. Smith, and J. Kovačević. Generalized Value Iteration Networks:Life Beyond Lattices. Proceedings of the AAAI Conference Artificial Intelligence, 32(1), Apr. 2018 ISSN 2374-3468, doi: 10. 20..6669aaai.v2........ 12081. URL https: //ojs. aaai. org/index: phpp Ctlp/AAAI//A wtt.aaatiiccaaaee 12081. Number: 1.
12

---

J. Oh, V. Chockalingam, and H. Lee. Control of memory, active perception, and action in minecraft. In International conference on machine learning, pages 2790-2799. PMLR, 2016. URL http: // //proceedings mlr press/v48/ oh16. html.
J. Oh, S. Singh, and H. Lee. Value Prediction Network, Nov. 2017. URL htRphttt///arxiv.orgg 1707. 1707.03497.
1707.034977 [cs].
OpenAI, A. Jaech, A. Kalai, A. Lerer, A. Richardson, A. El-Kishky, A. Low, A. Helyar, A. Madry, A. Beutel, and et al. OpenAI ol System Card, Dec. 2024. URL httt:://aaasst wwwpsiiiiioooooooooooo.o abs///1b/22
16720. arXiv:2412.1611 16720 [cs].
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An imperative style, bigh-performann deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
L. Peshkin, N. Meuleau, and L. Kaelbling. Learning policies with external memory. arXiv preprint cs/0103003,200
Qwen Team. Qwen2.5: A party of foundation models, September 2024. URL https:////eenmnn github. ht/blog//////////oo http//lllgg/we.....ee
D. Schleich, T. Klamt, and S. Behnke. Value Iteration Networks on Multiple Levels of Abstraction. In Robotics: Science and Systems XV, June 2019. doi: 10.15607/SSS.2119XXV.... URL http://arxiv.. www.wiwww.................owoe wwwooog///booo htt//bb//1905 11068. arXiv:1905.1 1068 [cs].
J. Schrittwieser, Hubert, A. Mandhane, M. Barekatain, I. Antonoglou, and D. Silver. On- line and Offline Reinforcement Learning by Planning with Learned Model. In Ad- vances in Neural Information Processing Systems, volume 34, pages 27580-27591. Cur- Associates, Inc., 2021. URL ttttpp:://prccedinggg www.eps....ppappeeppppe pptpp//p/p////aaaa///aa 22258551403177113678822228
Abstracttsstttt....e....eeeac..e html.
D. Shah, Q. Xie, and Z. Xu. Non-Asymptotic Analysis of Monte Carlo Tree Search. In Abstracts of the 2020 SIGMETRICS/Peffommacc Joint International Conference on Measurement and Modeling of Computer Systems, pages 31-32, Boston MA USA, June 2020. ACM, ISBN 978- 1-4503-7985-4. doi: 10.1145/33939911339992 URL https::///////t //dl: acm. org/doi/10 1145/ 3393691. 033969.. 3394202.
D. Silver. Reinforcement learning and simalation-based search. PhD) thesis, University of Alberta, 2009.
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, Sutskever, Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, Jan. 2016. ISSN 1476-4687. doi: 10.103/naturee166 16961. URL https://wwtt nature. com/ artaiiettlcss//// nature16961. Publisher. Nature Publishing Group.
D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap. F. Hui, L. Sifre, G. van den Driessche, T. Graepel, and D. Hassabis. Mastering the game of Go without human knowledge. Nature, 550(7676):354-355 Oct. 2017. ISSN 1476-4687. doi: 10. 1..00/// URL https:///att nature com/ articles/nature2444
Publisher: Nature Publishing Group.
R. Sutton and Barto. Reinforcement Learning: an Introduction. MIT Press, 2018.
R. Sutton, Precup, and S. Singh. Between mdps and cemi- A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 1 112 12:1111 1-111, 1999.
Q. Sykora, M. Ren, and R. Urtasun. Multi- Routing Value Iteration Network. In Proceedings of the 37th International Conference on Machine Learning, pages 1300-9310 PMLR, Nov. 2020. URL https: S http:///epeeeneeseeeeeee//e mlr. press /t///v19//// //sp///aooaaaaa./// html. ISSN: 2640-3498.
A. Tamar, Y. Wu, G. Thomas, S. Levine, and P. Abbeel. Value Iteration Networks, Mar. 2017. URL fctp://arxivv org/ abs/ 1602. 02867. 1602:1660.00286 [cs].
13

---

P. S. Thomas. Policy Gradient Coagent Networks. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2011.
H. Touvron, Martin, K. Stone, Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint Xiv:2330 00288, 2023.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
K. A. Wang. J. Xia, S. Chung, and A. Greenwald. Dynamic Thinker: Optimizing Decision-Time Planning with Costly Compute. In Proceedings of the Workshop on Adaptive Learning Agents (ALA), 2025. URL https://openreeieet wwt.:eee//ooooeeee weettforummiddyeee htt./oormdddd-ygg1ppppppp-p
X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou. Self- Consistency Improves Chain of Thought Reasoning in Language Models, Mar. 2023. URL http://arxivv org/ watg//b///ae ha//abbb/22..... 11171. arXiv:2203. 11171 [cs].
C. Wason and J. S. B. Evans. Dual processes in reasoning? Cognition, 3(2):141-154, 1974.
Weber, S. Racanière, D. Reichert, L. Buesing, A. Guez, J. Rezende, A. Badia, O. Vinyals, N. Heess, Y. Li, R. Pascanu, P. Battaglia, D. Hassabis, D. Silver, and D. Wierstra. Imagination- Augmented Agents for Deep Reinforcement Learning, Feb. 2018. URL http://arxiv.. org/ abs/1707 0bs/1707.06203,
[cs].
J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. Chi, Q. Le, and D. Zhou. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models, Jan. 2023. URL / http:/aawiiaaaaaaaaa///aa/ wtgg/bs//////e//e 2220 11903. atXiv:220.111900 [es].
T. Wiedemer, Y. Li, P. Vicol, S. S. Gu, N. Matarese, K. Swersky, B. Kim, P. Jaini, and R. Geirhos. Video models are zero-shot learners and reasoners, 2025. URL http:/tt: wwwp:/vvwwrg.///////eeeeeee 20328.
R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learn- ing. Machine Learning, 8(3):229-256, May 1992. ISSN 1573-0565. doi: 10. F0.10007/B000992666
URL httph::t////t springer com/ com/article//ii ceticceee0.... 100.0.0 10070000/BBBB /007/BF00992696. Company: Springer Distributor: Springer Institution: Springer Label: Springer Number: Publisher: Kluwer Aca- demic Publishers.
A. Yang. B. Yang, B. Hui, B. Zheng, B. Yu, Zhou, C. Li, C. Li, D. Liu, F. Huang, G. Dong, H. Wei, H. Lin, J. Tang, J. Wang. J. Yang. J. Tu, Zhang, J. Ma, J. Xu, J. Zhou, J. Bai, He, J. Lin, K. Dang, K. Lu, K. Chen, K. Yang, M. Li, M. Xue. N. Ni, P. Zhang, P. Wang. R. Peng. R. Men, R. Gao, R. Lin, Wang, S. Bai, S. Tan, Zhu, T. Li, T. Liu, W. Ge, X. Deng, X. Zhou, X. Ren, X. Zhang, X. Wei, X. Ren, Y. Fan, Y. Yao, Y. Zhang, Y. Wan, Y. Chu, Y. Liu, Z. Cui, Z. Zhang, and 2024.
Z. Fan. Qwen2 technical report. arXiv preprint arXiv:2407.1005
S. Yao, Yu, Zhao, I. Shafran, T. L. Griffiths, Y. Cao, and Narasimhan. Tree of Thoughts: Deliberate Problem Solving with Large Language Models, Dec. 2023a. URL http:/ //arxivv [es].
org/aba /2305 10601. arXiv:2305.
S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, Narasimhan, and Y. Cao. ReAct: Synergizing Reasoning and Acting in Language Models, Mar. 2023b. URL http://arxini Borg//bs//ee 22100. 03629.
arXiv:2210.03629 [es].
W. Zaremba and I. Sutskever. Reinforcement Learning Neural Turing Machines Revised, Jan. 2016.
URL http: /ttpx//axvv///////////////aaaava htsg/ab//10000 /bap///5..01011........ Stii:::555.005/1 [cs].
M. Zhang, Z. McCarthy, C. Finn, S. Levine, and P. Abbeel. Learning Deep Neural Network Policies with Continuous Memory States, Sept. 2015. URL http://arxiv.org wrg.abs//5//../// 01273. arXiv:1507.011 [es].
S. Zhang, Z. Chen, Y. Shen, M. Ding, J. B. Tenenbaum, and C. Gan. Planning with Large Lan- guage Models for Code Generation, Mar. 2023. URL http:// //arpii//xxvv... arxiv. org/abs/2303. 2200,, 05510. arXiv:2303.05510 [es].
14

---

A. Zhou, K. Yan, M. Shlapentokh Shlapentok-RRothman,, H. Wang, and Y.-. Wang. Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models, Dec. 2023. URL http: //arxiv. org/ aa//a/aa//2/1// 04406. arXiv:2310.04406 [cs].
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
This paper claims (1) to introduce a formal model of thinking in RL environ- ments (see Section 3.2), (2) to formally show conditions when so-called thought actions will be chosen by an RL algorithm and how they could be helpful depending policy initializa- tion (see Section 4), (3) to validate that some pre-trained LLMs satisfy the conditions when thought actions would be helpful (see Section 5) and (4) to introduce toy domain where multi-task pre pre-training leads to model-free RL discovering thinking useful strategy (see Section 6).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section discusses limitations starting point for future work. We also discuss a number of limitations throughout the paper, particularly when we introduce the thought MDP model in Section 3.2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
16

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are found in Section 4 along with their proof. Key assumptions are stated along with the result made in Section 3.2.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Section 5 completely specifies the LLM experiments and example prompts are provided in Appendix D. Section 6 describes the toy-domain experiments and additional empirical details are found Appendix E.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how construet the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
17

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have included the code for the submission in the supplemental material. No external data sources used.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
des//d////e CooeeSumiiee / is wwwssssnsllll..e.. onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e-g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: These details can be found in Section Section 6, or Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Confidence intervals are reported for all empirical results presented.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
18

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : //tt:///s....//eeee ccc.ciss........cccccooooooo http/uublcc/Ette |
Answer:
[Yes]
Justification:
We have read the Code of Ethics and confirm the paper conforms them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper theoretical in nature and consequently has no immediate societal impact. Due to the dual-use nature of AI, by secking to advance the field, our work will potentially contribute both to positive and negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
19

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is a theory paper with experiments on toy domains and does not release any new models that require safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the LLMs we use and also cite prominent software packages used (specifically Pytorch and Numpy).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-par se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects crowdsourcing used.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subject use.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: See Section 5 and Appendix D.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non- non-standard components.
Please refer to our LLM policy (https: :/ /tw.rrips..c/ooofeeeeeeeeecee for what should or should not be described.
22

---

A Proofs of Theoretical Results
Proposition 7. Suppose we have a goal thought MDP that has T {To, 7.). Let the initial policy, n, be such that there is some po such that Pr(s) E &gaal (8, o, π (To)) > Po for all (s.a) E S x A and some pı such that Pr(st E Sgoal (s, a. (TT) )) > Pr for all (s.a) E S x A. Let C2 be the thought action such that Ti = PT To, Ca) and let Pe lower bound the probability π (Ca |s. To). Pf Pe-pi P1 > po-
then thought actions reduce the upper bound the effective horizon of the MDP.
Proof. The proof follows from the fact that, under the assumed policy initialization, thought actions raise the lower bound on finding goal. First, note that the effective horizon has tighter upper bound if we always fix the thought state to be τΙ rather than To. Thus, there is just the question of
getting the thought state to be T1. We lower bound this probability with so that, if the agent is
in (s, To), it has at least probability of getting to Ti from which it has at least a probability p1 of
finding a goal. Thus, the lower bound on Pr(ST E &gaa2 18, T, a, T) will be at least Pe P1 for both To
and Ti which reduces the effective horizon if Pe P1 Po-
L
B Extended Theoretical Analysis for Finite- Horizon Thought MDPs
In the main paper text we formalized thought MDPs under the discounted return objective that is common in RL research. In this appendix, we extend these results to the finite-horizon, non-discounted setting that common in contemporary uses of RL. to train reasoning behavior in L.LMs.
B.1 RL in Time- Homogeoomsss Finite-Horizon Markov Decision Processes
In this section and the following, we use [k] to denote the set of integers {l,... Formally, a time-homogenous, fixed-horizon MDP is tuple, AS,A, 1, where S is the environment state space, A the set of actions that the agent can take to influence the environment state, is the maximum length of an episode, p S x A - A(S) is a stochastic state transition function, and r: x:SxA A + R is salled reward function. When the agent action a then it receives r r(s. a) and transition to a new state S' ~ p(-[s, a) and t is incremented by 1. The process repeats from S' until either terminal state, Sec. is reached or t reaches 1. The agent selects actions according to a policy, π. : S x [1] - (A). The time-dependent value of using a policy from particular state, 8, is defined to be U (8, ()- == E E r(s,, [s; 8, 0g rT-1s;; i)]. In finite-horizon RL, the agent's 's objective is to find policy that maximizes Ux (s, () in all states and for all time-steps though, in practice, we could just focuse on maximizing (s, 0) for all possible initial states.
state s timestep and takes
B.2 Time--nnng Finite-Horizon Thought MDPs
We formally define a finite-horizon thought MDP as the tuple (S. T,,.P. where S,A,p, r, are defined as they are for standard finite-horizon MDPs. We add T as the set of thought states, as the set of thought actions, and pT : T x C - A(T) as the thought transition function. Recalling our informal definition of thinking from the main text, we emphasize that thought states and actions do not affect environment state transitions and rewards. However, they do affect the transition of time as we assume that the episode time-step will still be incremented when the agent takes thought action.
We define policies for thought MDPs as the main text except now with a time dependency: S x T x [1] - A).UC). In this section, we will use the notation (T() to refer to the agent's s state- and time-dependent policy with the thought state fixed a.
In a thought MDP, interaction proceeds as follows. Episodes begin in timestep = 0, initial environment state, so. and thought state, To, and the agent chooses either environment action or thought action according to its policy. In either case, we increment t to = 1. If ag E A then the environment state, 31, at the next time-step is sampled from p(so, ao). the thought state Ti keeps the value of To. and the agent receives reward ro = r(so, oo). Conversely, if ag C, then 81 keeps the value of so. Tı is sampled from Pr To, an), and the agent receives To = 0. Then the selion-n process repeats until either the agent reaches Soo or
For thought MDPs, we define the value function to be Un (s, t, == E D>'=! rs,,, 2;)(s; = s, T2 = r], with r(s,, x4) = 0 if I E C.
23

---

We next adapt the key assumptions of the main paper to the shiteehorizon setting. First, we assume that thought state transitions are deterministic in order to simplify our analysis and because it is also the case for LLM agents.
Assumption 9 (Deterministic Thought Transitions). Vs E S,T C C. (T T, c) = 1 for one and only one T' E T. We will write (s v.c) E T to denote the thought state that results from taking in (5, T).
Second, we assume that all rewards are non-negative as otherwise thinking could emerge strategy solely for the purpose of putting off receiving a negative reward, i.e., if all rewards are negative then the agent will be incentivized to just keep taking thought actions rather than environment actions.
Assumption 10 (Non- negaaivee Rewards). Vs E S, a E r(s,)) 2 0.
case raises questions about the passage of time. Just as in the main paper we assumed that discounting is applied equally between thinking and non-thinking time-steps, here assume that both thought and environment actions take a single stmp This assumption discourages thought actions as they cost the agent a chance to directly or indirectly obtain reward through an environment action. Potentially, we could consider varying times for thought and environment actions, however, this raises additional complexity that we will not consider further here. As before, the proposed model assumes that the environment state remains constant while the agent takes thought actions except for the passage of time. Again, for simplicity, we will focus on the static environment case, but note this issue as another interesting direction to refine the model. Finally, we only consider time- home-hooogenous finite-horizon thought MDPs. In time-inie meme-ionoogoous MDPs, the state transition probabilities and reward can differ across steps. In time- inhomogenous finite- horii-horizon thought MDP, thought actions might subtly change the state of the environment for the agent by allowing to wait for more favorable state transition probabilities. A possible resolution would be to not advance the time-step when the agent selects thought action. However, that resolution could break the knite-horizon assumption. For simplicity, we will only consider the time-homogenous
Modeling of Time As in the discounted case, the
setting.
Optimality Finite-horizon thought MDPs are MDPs with state space S x T x [4] and action space AUC and consequently there will always be at least one deterministic optimal policy [Sutton and Barto, 2018]. Furthermore, we can show that this optimal policy will never take a thought action if we assume that environment actions are preferred to thought actions when the expected return is otherwise equal. The bie-brea assumption means that thought actions are never strictly preferred to environment actions, though there may be situations when either type of action is equally preferred. Equal preference results in states from which it is impossible to obtain more future reward.
Proposition 11. Assume that ties (w.r.t. expected reward-to-go) for the optimal action are broken in favor of environment actions. Then, any optimal policy, x², for thought MDP does not take thought actions: x (s, E A. Vs E.T T,te [T.
Proof. The proof is by induction. First, as the base case, consider the final time-step 1 - 1. Under the optimal policy, the agent receives r(s, x² (,, 1)) in (s) and then interaction terminates. Since r(s, TT" (s. T, 1)) = 0 if x" (T,,,, 1) E C and r(s, 7,, (s, then thought action will never be strictly preferred an environment action. Under the assumption that ties are broken in favor of environment actions, the optimal policy will select an environment action. Now, assume for arbitrary non-initial time-step environment actions for all (s, 7) and for all subsequent time-steps t' 2 t. We need to show that T rs, T, - 1) E A. We will prove this step by contradiction. Suppose that X (s. f 1) E C. Then, after the agent takes π (s, T, t- - 1), it transitions to 7') and will then only take environment actions until termination (by our inductive hypothesis). However, if the agent changed TT (s, T"(,, 1) to take T () then it would get the same expected total reward over the next - time-steps and end up in some state, S at time-step I 1 from which would have one more chance to take an environment action and gain zero reward. Consequently, changing x" T' T, d 1) to this action would produce at least as high a return, which implies that n (, - 1) & C if nT" the optimal policy and ties are broken in favor of environment actions.
1)) -1)
2 0 if I (,,
E A
0 that the optimal policy only takes
24

---

C Policy Initialization Determines Emergence of Thinking
Finally, we extend Theorem 5 to the mnite-horizon setting.
Theorem 12. Let be policy in thought MDP such that a(s, T,t) f some environment state 8, thought state т, and time-step, L. If the policy improvement step of policy iteration sets x' T(1) &- effor E C, then va 1) > (8, (), where I' is the thought state resulting from laking e (8, T)
) at step L.
Proof. Policy iteration sets (s, T, t arg max (s, where
Since the policy improvement step is selecting thought action, have that: In (s, r(s, 2) + Eu 1)] if E Us ( (1
if E C.
Ya E A, fz 1,, (x,
< un (8 .6,,7,++100 1+ 1).
Since (s, r, was in A before the update we have that:
gr (x (s, T. m (8. T, ()) < Un (8, (1+1,,,1111
Thus, a thought action is selected when the policy is such that first changing the thought state to r' leads to greater expected return than taking any environment action immediately, even though changing the thought state decreases the number of remaining time-steps which the agent can obtain reward.
D Example Prompts for LLM Experiment
Table Appendix D provides example of the prompts we use in our LLM thinking vs no-thinking experiments.
Condition
Prompt
No Thinking
Compute the sum: 5709 + 2890 4937 + 6482 + 6850
Thinking
Compute the sum: 5709 + 2890 +1890+4999 6482 6850
8599 + 4937 + 6482 + 6850 13536 6482 + 6850 20018 6850
Table 2: Example "Thinking" and "No Thinking" prompts. The green text indicates the "thinking tokens" appended to the original "No Thinking" prompt.
E Extended Empirical Description of Gridworld Experiments
This appendix provides additional details on toy domain experiments.
Implementation Details We implement the Gridworld domain, pre-training, and reinforcement learning set-up in Python, using Pytorch [Paszke et al., 2019] for neural networks and gradient optimization. All experiments memory. For both model pre-training and RL with REINFORCE we use the Adam optimizer [Kingma and Ba, 2015] with learning rates le-4 and le-5, respectively. For REINFORCE, not use a value function baseline as we found it generally did not help because the sparseness of the reward led to poor value estimates that harmed carly policy learning. For the "NoThink" methods, mask out the special actions by adding a large negative value to the logits for those actions before passing them to the softmax distribution.
ran on Macbook Air with Apple MI chip and 16GB of
do
25

---

1.0
ScratcD-NoThink
hestraind-HoThin
Think
Scratch-Trink
Success Rate
0.8
Fraction Time Thinking
0.4
0.6
0.3
0.4
0.2
0.2
0.1
0.0
PectrinncdNNoThink NoThink
Scratch NoThhnk
Pretrained-Think
Scratch-Think
0
20
40
60
80
100
0
20
40
60
80 100
Iteration
Iteration
(a) Success Rate
(b) Fraction Thinking Time
Figure Mean learning curves for the four agents we train the gridworld environment with misspecified sub-tasks. The vertical axis gives the success rate for first navigating to the bottom right and then the top left corner. The horizontal axis is the iteration of policy improvement (200 episodes are collected at each iteration). We run 20 trials for each learning agent and shading indicates a % bootstrap confidence interval. Light lines show individual training runs.
Pre-trained Model Validation The objective of our experiment described in Section 6 was to create a setting where model-free RL (in this case REINFORCE) would lead to thinking as a strategy for reward maximization. A crucial piece of the set-up was to have pre-trained model for which thought actions increase the agent's probability of solving the task. Recall that solving the task requires the agent to navigate to the bottom right corner and then to reach the top left corner. Pre-training is designed so that the agent outputting special action 'A' increases the probability of it then taking the actions that lead to the bottom right and similarly so that 'B' increases the probability of moving to the top left. We validate the pre-trale pre-training procedure by taking pre-trained models and forcing their first action to be 'A' and their action upon reaching the bottom right for the first time to be 'B' We find that the pre-training procedure leads to models where such prompting increases the probability of task success compared to simply rolling out the model. we further prompt the model this way and also mask thought actions every other step then the pre-trained model will solve the task on virtually every episode. This prompting and masking procedure confirmed that pre- pre-training had primed the model for thinking to emerge as an effective strategy.
Pre-training with Misspecified Sub-Tasks In the Gridworld domain, we pre-train the agent's policy so as to associate the thought actions 'A' and 'B' with two sub-tasks that will be needed on the final evaluation task. Naturally, one might wonder whether thinking will still emerge if the pre-trained sub-policies are misspecified for the final learning task. To test this, we pre-train a model using the exact procedure described above but change the evaluation domain that the complex task has each sub-goal location shifted by one cell. Though small change, it is a sufficient change so that the strategy discovered in our main task setting will no longer completely solve the task. With this set-up, we test whether the agent can still leverage thinking to solve the task, even though triggering the pre-traine trainen behaviors is insufficient by itself. Figure 3 shows similar results as Figure 2 in which the pre- rre-trained method that uses thinking actions remains the only method to fully solve the task. Interestingly, we no longer observe any runs of the pre-triined no-think agent successfully completing the task.
26


Reviews:
[{"review_id": "reiuRGXp7o", "reviewer": "Reviewer_zETt", "summary": "This work studies the question: \"when is it possible, from an RL theoretic point of view, to encourage 'thinking' steps by just pure RL?\" They formally define a construct called a \"Thinking MDP\" which is an MDP which incorporates \"thinking states\" and \"thinking actions\". The reward is discounted for each thinking or acting step taken, in accordance with standard MDPs, and is assumed to be non-negative. This formulation leads to several mathematical propositions: an optimal policy for a thought MDP never takes any thinking steps, but policy iteration algorithms may sometimes empower the model to take thinking steps if the expected reward is better under the current policy; and thinking MDPs may also have a smaller effective horizon (i.e., are \"less complex\") than their ordinary counterparts, under some cases. The authors attempt to validate their theory using some controlled experiments in LLMs and outside of LLM context using purely synthetic settings.", "questions": "- How resilient are the theoretical results to the specific assumptions made? Is it possible to adapt the results to other assumptions?\n- How can we formalize the state/actions in terms of the LLM token generation process?\n- Can a modified RL procedure which uses the assumptions made in the paper actually do RL training of a fine tuned model? (I.e., instead of making theory fit the practice, you can instead introduce a new practical method which fits the theory and show that it does reasonably well.)", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The Thought MDP formulation is interesting, and (potentially one of) the first attempts to connect thinking/reasoning in LLMs to RL theory.\n- The mathematical consequences of the formulation seem solid and interesting, albeit very connected with the specific assumptions made, which may not be realistic.\n- The synthetic experiments in non-LLM RL environments demonstrate the possible generalization of reasoning RL methodology outside of LLMs.\nWeaknesses:\n- The thought MDP formulation is not fully connected to LLMs. In reasoning LLM training, my understanding is that each action or thought is a full \"turn\", not just a single token, and this affects the reward formulation. Often, there is no discount factor, and in any case the discount factor often does not apply to thinking steps. In this sense, the reward formulation of the thinking MDP in this paper seems like it does not apply to the practice of LLMs.\n- The synthetic experiment with LLMs is also similarly heuristic, and in particular, does not actually apply RL to the model, so it is hard to show how the results in this experiment corroborate the theoretical results.\n- The theoretical assumptions, which seem not very applicable to practice, seem to underpin all the theoretical results, so these may not apply either or be slightly misleading when applied to practice.", "was_revised": true, "final_justification": "I have read the rebuttal. I have improved the score given the authors' reply and other reviewers' opinions. But I still believe the paper is below the bar for acceptance.", "rebuttal": "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.\n\nYou’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.\n\nThat said, our theoretical assumptions are not so disconnected from RL for thinking LLMs in practice as we read the literature.\n- 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. \n- 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].\n- 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. \n\nThe 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.\n\nRegarding 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:\n1. 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.\n2. 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. \n3. 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.\n\nQuestions:\n1. 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.\n2. 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.\n3. 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.\n\nWe hope our response addresses your concerns and we are happy to discuss any of these points further!\n\n[1] DPO meets PPO: Reinforced Roken Optimization for RLHF\n\n[2] Stop Anthropomorphizing Intermediate Tokens as Reasoning/Thinking Traces!\n\n[3] RL in Name Only? Analyzing the Structural Assumptions in RL post-training for LLMs"}, {"review_id": "0xXWarUT6F", "reviewer": "Reviewer_QBee", "summary": "In this paper the authors explored why \"thinking\" (defined as agent actions that does not produce reward and does not modify the environment state) might emerge as part of model-free RL learning. The proposed a framework named Thinking MDP to ground their research. They provided theoretical results on 1) the benefit of thinking as a form of test-time policy improvement and 2) how policy initialization influences the whether thinking emerges. \n\nThe authors further provided toy example to demonstrate that 1) thinking could improve LLM's policy at test time, and therefore would be expected to emerge as a policy during RL, though the final optimal policy would not require thinking. And 2) some empirical evidence that multi-task pretraining is a core criteria for models where thinking could be useful (as a form of helping the policy navigate to learned sub-policies).", "questions": "1. In Section 6, why does the thinking action still occupies 15% of final policy if Proposition 4 suggests an optimal policy doesn't need thinking?\n\n2. Suggestion: provide some empirical evidence on the emergence of thinking in LLMs as RL iteration goes on, similar to Figure 1 but in a real-life LLM setting. \n\n3. Provide more ablations on the effects of multi-task pretraining, for example if the pretraining tasks are not strictly \"subtasks\" for the RL task, what would happen.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength:\n- Well written paper.\n- Provided strong theoretical results on how thinking can be a viewed as a form of test-time policy improvement given suboptimal policy / value functions.\n- Provided interesting demonstration on their theoretical results.\n\nWeakness:\n- The paper stopped short of showing that \"some LLM can benefit from thinking\" necessarily implies the \"some LLM will get thinking ability through model-free RL\". The authors argue that if an optimal policy can be learned then thinking is necessary, but some additional research in realistic settings (RL on pretrained LLM) that thinking emerges and then goes away.\n- The paper did not provide much grounding on their claim that multi-task pretraining is key criteria for thinking. Do the authors mean that thinking is essentially a way to generalize from learned sub-tasks during multi-task pretraining? Some more exploration on this could be meaningful.\n- The paper hinted that thinking shares certain similarity with MCTS. This could be explored more in settings such as teaching a LLM to play a game such as Chess. \n- Some minor grammar mistakes.", "was_revised": true, "final_justification": "Thanks for addressing the comments. I will keep the original score.", "rebuttal": "Thank you for your kind remarks—we’re glad you found the paper interesting!\n\nWeaknesses:\n- 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.\n- 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.\n- 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.\n- We will carefully proofread the paper before the camera ready deadline.\n\nQuestions:\n1. 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.\n2. 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.\n3. 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.\n\n[1] On-Policy Policy Gradient Reinforcement Learning Without On-Policy Sampling. Corrado and Hanna. Arxiv 2024."}, {"review_id": "oZ4Pb9NYH2", "reviewer": "Reviewer_vneH", "summary": "This paper studies the emergence of thinking in Large Language Models (LLMs). Recent works have discovered that model-free reinforcement learning with special tokens can encourage LLMs to think (e.g., generating long chain-of-thought) and improve reasoning performance. To study this phenomenon, this paper models the reasoning process of LLMs as a Thought Markov Decision Process. Thus, reasoning is to learn the transition between the thought states. Furthermore, it develops a theoretical framework to show that initialization is important for the emergence of thinking. It further discusses the emergence of thinking in other domains.", "questions": "I am \\textbf{not} a theoretical researcher. Please address the weaknesses part above.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. This paper studies how thinking emerges from LLMs, which is receiving increasing attention. Empirical findings reveal that model-free reinforcement learning can improve the reasoning ability of LLMs by teaching them to think. Although such a paradigm has achieved superior performance in mathematical reasoning and coding [1], the mechanism behind this emergence of thinking is unknown. Recent work [1] also questioned whether RL can improve the reasoning ability of LLMs. To the best of my knowledge, this paper is one of the earliest ones to study this problem from a theoretical perspective.\n\n2. To study the emergence of thinking, this paper established a Thought MDP and theoretically analyzed the importance of policy initialization to thinking. This finding aligns well with recent empirical results, as shown in [2].\n\nWeakness:\n\nMy major concerns are about the clarity and empirical evaluation. For example, what are the thought states and actions in the reasoning process? It is better to have some illustrative examples. Moreover, the evaluations in Section 5 are only conducted on small scale models (~1B). It would be better to evaluate on large-scale models.\n\n\n[1]. Deepseek-r1: Incentivizing reasoning capability in LLMs via reinforcement learning.\n\n[2]. Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model?", "was_revised": true, "final_justification": "After reading the reviewer's response and additional experiments, I think my concerns are addressed and I will keep the scores. The reason why I do not increase to 5 is due to the mismatch with my expertise. I do not work on theory, so I am not in a good position to evaluate the theoretical contribution of this manuscript. But the empirical finding of this manuscript aligns well with the literature.\nSo I will keep my original assessment.", "rebuttal": "Thanks for your kind comments on our novelty and alignment with empirical findings. We're happy the theoretical contribution is appreciated.\n\nWeaknesses\n1. 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.\n2. 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.\n\nWe 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.\n\n\t| Model                     | No Thinking (%)       | Thinking (%)          |\n\t|--------------------------|-----------------------|------------------------|\n\t| Qwen2.5-1.5B-Instruct    | 7.20 ± 0.82           | 71.20 ± 2.80           |\n\t| Qwen2.5-3B-Instruct      | 6.80 ± 0.80           | 36.50 ± 1.52           |\n\t| Qwen2.5-7B-Instruct      | 5.06 ± 3.10           | 96.10 ± 2.98           |\n\t| Qwen2.5-14B-Instruct     | 0.90 ± 0.33           | 95.20 ± 1.33           |\n\t| Tulu-2-7b                | 0.30 ± 0.33           | 28.50 ± 2.80           |\n\t| Tulu-2-13b               | 0.60 ± 0.47           | 49.00 ± 3.10           |\n\t| Llama-2-7b               | 0.00 ± 0.00           | 48.80 ± 3.10           |\n\t| Llama-2-13b              | 0.20 ± 0.27           | 60.70 ± 3.03           |\n\t| Gemma-3-1b-it            | 0.50 ± 0.43           | 41.50 ± 3.06           |\n\t| Gemma-3-4b-it            | 4.90 ± 1.33           | 91.50 ± 1.72           |\n\t| Mistral-7B-Instruct-v0.3 | 1.50 ± 0.74           | 85.20 ± 2.20           |\n\nTable. Response accuracy with ± 95% confidence interval when using thinking vs no thinking."}, {"review_id": "86imVUQyTM", "reviewer": "Reviewer_RSQS", "summary": "The author extends standard MDP by adding a thought action space, such that at each step the agent may either act in an environment ($A$) or take a zero-reward \"think\" step ($C$) that deterministically updates an internal thought state ($\\tau$) while environment state (s) remains unchanged. Under these three assumptions:\n- thought transitions are deterministic,\n- all external rewards are non-negative\n- for any state there exists a policy that can eventually reach a non-zero reward with finite number of steps,\n\nthe authors prove:\n- a fully-optimal policy never thinks,\n- during learning a thought step is selected exactly when its discounted value exceeds the value of acting immediately\n\nThus, thinking emerges only when it raises expected returns enough to offset the discount. Experiment using 4-digit addition shows thought actions indeed improve expected return in LLMs as perplexity significantly reduced.", "questions": "- Could authors provide a training recipe along with an experiment showing thinking emergence during training? Using the multi-digit addition with a small LLM should suffice. \n- Many existing RL for LLM is implemented using token-level rewards where a single trajectory reward gets broadcasted to every position of the token. Does this work assume discount $\\gamma$ apply at the whole generation level as well?\n- What happens when there is no discount factor applied to thinking? $\\gamma=1$", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The formalization is clean and correctly derived. The paper gives a unified theory to explain conditions in which a bunch of test-time compute scaling strategies arise during RL training.\n- The proofs clearly separate optimal behavior from learning time, suboptimal behavior and show how reflection can shorten the effective horizon in sparse-ward tasks. This is particular useful to explain recent effort in trying to make model think more efficiently by applying discount during training.\n\nWeaknesses:\n- The LLM-based experiments is in a trivial domain (4-digit addition), and it's hard to see how it generalizes to more complicated tasks.\n- The paper does not provide a training recipe or concrete algorithm for training LLMs despite showing the value estimates as perplexity.", "was_revised": true, "final_justification": "The author has addressed my concerns and answered my questions. Overall i think it's a good paper with insights that would be beneficial to share with the community.", "rebuttal": "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.\n\nWeaknesses:\n1. 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!\n2. 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. \n\nQuestions:\n1. 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.\n2. 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!\n3. 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.\n     - 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$.\n\nPlease let us know if you'd like to discuss these questions further!"}, {"review_id": "RBIpEkGAuD", "reviewer": "Reviewer_pJ6m", "summary": "This paper developed a formal framework studying the role of thoughts in reward maximization. The paper proposes a model of \"thought MDP\", which augments the conventional MDP for RL modeling with thought states and actions. With this formulation, the paper shows that thought-augmented MDP improves policy and is more effective in maximizing rewards. The paper also shows that policy initialization is critical to the emergence of thoughts, and how the thought MDP helps language and non-language models to maximize rewards.", "questions": "1. While the paper provided analysis of how thinking improves policy, it remains unclear what conditions of the thinking steps need to satisfy so that policy can be improved and reward optimized. An agent's performance cannot be improved with arbitrary thought states and actions, it would be great to provide some theoretical characterization of the quality of thoughts.\n\n2. In some sense the \"thought MDP\" can be regarded as introducing a latent variable to the MDP process. It would be great if the paper could provide some comparisons between the proposed framework differ and existing analysis on RL with latent variables, e.g.\n\n\"Stochastic Latent Actor-Critic: Deep Reinforcement Learning with a Latent Variable Model\", NeurIPS 2020\n\"Latent Thought Models with Variational Bayes Inference-Time Computation\", arXiv 2025\n\"Latent Variable Representation for Reinforcement Learning\", ICLR 2023\n\"A Theoretical Understanding of Chain-of-Thought: Coherent Reasoning and Error-Aware Demonstration\", arXiv, 2024", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThis paper provides a rigorous formal mechanism that elucidates the role of thoughts in reward optimization of RL, which offers a solid theoretical contribution to the understanding of how COT + RL improves agent model's performance.\n\nWeakness:\nAlthough the paper's title is \"Is reward enough for thinking\", this paper actually touches several sub-topics (how thinking helps reward optimization, condition for thought emergence, language/non-language thought MDP etc.). This divergence makes the central argument somewhat difficult to follow. A clearer high-level summary and more structured line of reasoning would strengthen the paper's coherence.\n \nThe paper could also have compared existing theoretical analysis on the role of COT and latent thinking steps.", "was_revised": true, "final_justification": "The development of a rigorous formalization mechanism for the analysis of COT and reward optimization deserves follow-up work and discussion. I think overall this is a well-written paper, although some of the author responses could be better incorporated in the submission for improved clarity.", "rebuttal": "Thanks for your kind comments on the strength of our theoretical analysis!\n\nWeaknesses:\n1. 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. \n2. 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.\n\nQuestions:\n1. 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. \n2. Thanks for suggesting these references. We can add discussion about how existing work on COT and latent states relates to our work. Specifically:\n      - 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.\n     - 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.\n\nPlease let us know if we can provide further clarification!"}]

Author rebuttal:

Meta-review: This paper presents a novel and timely theoretical exploration into the phenomenon of "thinking" as it emerges from model-free reinforcement learning, particularly in the context of large language models. The authors introduce a formal framework, the "thought Markov Decision Process" (thought MDP), to analyze the conditions under which an agent would choose to perform internal, non-reward-generating "thought actions." Through this lens, they elegantly prove that thinking can be understood as a form of on-the-fly policy improvement. While an optimal policy would not need to think, the paper shows that during learning, thinking can emerge as a valuable strategy if the expected future reward outweighs the immediate cost of computation, with policy initialization playing a critical role. The theoretical claims are supported by illustrative experiments in both LLM and non-language domains, providing a compelling, domain-independent perspective on this important emergent capability.

I recommend acceptance for this paper. It was well-received by 4 of the 5 reviewers, who lauded it as a pioneering effort to formally connect the empirical success of chain-of-thought-style reasoning with foundational RL theory. The reviewers found the thought MDP formulation to be clean, insightful, and a significant contribution. While valid concerns were raised regarding the current gap between the paper's theoretical assumptions and the complex realities of training frontier LLMs, the authors' rebuttal has persuasively clarified their goal of building a more fundamental, lasting theory rather than just modeling today's evolving practices. It is also worth noting that the single outlier reviewer, despite a lack of engagement during the discussion period, raised their score and acknowledged the paper's strengths. I am confident that the authors have gracefully taken the constructive feedback to heart and that the final camera-ready version, incorporating the reviewers' excellent suggestions, will be a valuable contribution to the NeurIPS community.
Decision: Accept (poster)