Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning
Authors: Shenao Zhang
Yaqing Wang
Yinxiao Liu
Tianqi Liu
Peter Grabowski
Eugene Ie
Zhaoran Wang
Yunxuan Li
Venue: ICLR 2026 Poster (2026)
Keywords: large language model
reinforcement learning
Primary area: foundation or frontier models, including LLMs

Abstract: Large Language Models (LLMs) trained via Reinforcement Learning (RL) have exhibited strong reasoning capabilities and emergent reflective behaviors, such as rethinking and error correction, as a form of in-context exploration. However, the Markovian policy obtained from conventional RL training does not give rise to reflective exploration behaviors since the policy depends on the history only through the state and therefore has no incentive to enrich identical states with additional context. Instead, RL exploration is only useful during training to learn the optimal policy in a trial-and-error manner. Therefore, it remains unclear whether reflective reasoning will emerge during RL, or why it is beneficial. To remedy this, we recast reflective exploration within a Bayesian RL framework, which optimizes the expected return under a posterior distribution over Markov decision processes induced by the training data. This Bayesian formulation admits uncertainty-adaptive policies that, through belief updates, naturally incentivize information-gathering actions and induce self-reflection behaviors. Our resulting algorithm, BARL, instructs the LLM to stitch and switch strategies based on the observed outcomes, offering principled guidance on when and how the model should reflectively explore. Empirical results on both synthetic and mathematical reasoning tasks demonstrate that BARL outperforms conventional RL approaches, achieving superior test-time performance and token efficiency. Our code is available at https://github.com/shenao-zhang/BARL.

Published as a conference paper at ICLR 2026
BEYOND MARKOVIAN: REFLECTIVE EXPLORATION RL FOR LLM REASONING
VIA
Shenao Zhang" Yaqing Wang?, Yinxiao Liu?, Tianqi Liu", Peter Grabowski", Eugene Ie,, Zhaoran Wang", Yunxuan Li NNrttwwesern University, "Google DeepMind, *Google
ABSTRACT
Large Language Models (LLMs) trained via Reinforcement Learning (RL) have exhibited strong reasoning capabilities and emergent reflective behaviors, such as rethinking and error correction, as form of in-context exploration. However, the Markovian policy obtained from conventional RL training does not give rise to reflective exploration behaviors since the policy depends on the history only through the state and therefore has no incentive to enrich identical states with ad- ditional context. Instead, RL exploration is only useful during training to learn the optimal policy in trial-and-error manner. Therefore, it remains unclear whether reflective reasoning will emerge during RL, or why it is beneficial. To remedy this, we recast reflective exploration within a Bayesian RL framework, which optimizes the expected return under a posterior distribution over Markov deci- sion processes induced by the training data. This Bayesian formulation admits uncertainty-adapiive policies that, through belief updates, naturally incentivize information-gatterimn actions and induce self-reflection behaviors. Our result- ing algorithm, BARL, instructs the LLM to stitch and switch strategies based on the observed outcomes, offering principled guidance on when and how the model should reflectively explore. Empirical results both synthetic and mathematical reasoning tasks demonstrate that BARL outperforms conventional RL approaches, achieving superior test-time performance and token efficiency. Our code is avail- able at https:// // / thub. com/ shenao- peeee-hhgggggge /ARRI.
INTRODUCTION
Large Language Models (LLMs) have demonstrated impressive reasoning abilities, such in solv- ing complex math problems. A key factor driving this progress is the use of Chain-of-Thought (CoT) reasoning (Wei al., 2022), where the model engages in intermediate deliberation before producing an answer. Building on this, recent advances have employed Reinforcement Learning (RL) to further enhance LLM reasoning by optimizing for verifiable outcome rewards (Jaech al., 2024; Guo et al., 2025; Yu et al., 2025; Wei et al., 2025). Notably, RL-trained models have exhib- ited emergent behaviors such as engaging in self-refiection, a process of revisiting previous states to correct earlier mistakes (Guo et al., 2025; Zeng et al., 2025), which offers a potential way for test- time scaling (Snell et al., 2024; Brown et al.. 2024) by generating longer CoTs However, despite these compelling phenomena, it remains unclear why and under what conditions self-reflections are beneficial, or whether such behaviors will emerge through conventional RI. training.
In this work, we use reflective exploration to refer to behavior where the model revisits previously visited state and, informed by the additional context it has acquired, alters its subsequent actions. This definition links self-reflective directly to exploration under uncertainty, providing a principled basis for when and why strategy switches should occur rather than treating them as ad hoc quirks of the model's CoTs. We formalize this via strictly incertainty-ddapivv policies whose actions depend nontrivially on the belief. Since conventional RL typically admits a Markovian optimal policy, reflective exploration is not induced since the policy depends the history only through the state and is thus not incentivized to enrich identical states with additional context. Instead, RL explores during training through repeated trial and error, with incentives for further exploration when
Work done during internship Google. 'Equal advising.

---

Published as a conference paper at ICLR 2026
parameters frozen after deployment. Therefore, under conventional RL, there is no guarantee that reff-reflections will emerge during training, nor does it explain why reflective explorations might be advantageous when the trained policy is deployed at test time.
To address this gap, we propose grounding reflective reasoning with Bayesian RL, which maximizes the expected return in the deployment stage under posterior distribution over Markov Decision Processes (MDPs) induced by the training data. The objective incentivizes both reward-seeking actions and exploration actions that gather information to reduce the MDP's uncertainty, such as the reward uncertainty regarding the progress made by different actions. We show that optimizing this Bayesian RL objective yields umcertainty-adappiis policies that adapt on-the-fly by updating their beliefs and switching strategies based on observed outcomes, naturally leading to reflective exploration behaviors. Moreover, we prove that the optimal adaptive policy can achieve arbitrarily higher Bayes-expected return than any optimal Markovian policy.
Building upon this formulation, we introduce a novel algorithm, Bayes-Adaptive RL. for LLM Rea- soning (BARL). For each prompt, BARL performs online rollouts to generate a set of candidate an- swers, each associated with an MDP hypothesis. The state-action value is then computed by weight- ing each hypothesis according to the model's current belief, with penalties applied for mismatches between predicted and observed rewards, thereby signaling when to switch strategies. BARL pro- vides a principled mechanism for integrating and revising plausible strategies, analogous to lineariz- ing best-of-N, but with explicit guidance on when and how the model should reflectively explore.
To illustrate the benefits of BARL, we begin with a synthetic task designed to mirror the training- deployment procedure in LLM reasoning. The agent receives a reward only when it repeats a prompt token exactly three times, but the training and evaluation prompt tokens differ. Conventional RL fails to generalize beyond the training prompt tokens. In contrast, BARL learns to switch strategies by eliminating hypotheses, ultimately discovering the ground-truth MDP for optimal behavior.
We further evaluate BARL on math reasoning tasks using various LLMs, including Qwen2.5-Math 1.5B, Qwen2.5-Math-77 and RI-Distill-Llama-B1 Across these models, BARL consistently out- performs conventional RL algorithms, such as GRPO and strong progress-reward baseline, on multiple benchmarks. BARL achieves significantly greater token efficiency, requiring up to 1.63x fewer average tokens than the progress baseline, 2x fewer than GRPO, and over 10x fewer than the Qwen2.5-Math-11 1.5B base model. Moreover, we observe no strong correlation between overall model performance and the frequency of reflections. Instead, BARL'S advantage stems from more efficient exploration and more effective thinking tokens. We summarize the key takeaways below:
Key Takeaways: Why. How, and When Should LLMs Reflectively Explore
Why: Conventional RL neither ensures the emergence of reflective exploration nor explains its benefits since (1) RL typically attains Markovian optimal policies, which, cannot exhibit reflective exploration that collects additional context and act differently when revisiting the same state, and (2) RL exploration is confined to trial-and-erre during training, leaving no mechanism that encourages adaptive, belief-driven exploration at deployment. In contrast, Bayesian RL,, by optimizing Bayes-expected return during deployment, encourages explo- ration to gather contextual information that reduces the MDP uncertainty.
How: BARL provides principled way to stitch plausible strategies by maintaining a pos- terior over MDP hypotheses. each associated with sampled candidate answer. Reflective exploration emerges through hypothesis elimination, enabling on-the-fly adaptation.
When: L.MMs should self-reflect when discrepancies arise between their internal beliefs and cumulative reward Beedback-signaling strategy switching by downweighting hypotheses that have high belief probabilities but are unlikely to be optimal given previous observations.
RELATED WORK
LLM Reasoning. As an emerging capability of model scale, LLMs can generate intermediate CoTs to solve complex reasoning tasks (Wei et al., 2022; Kojima et al., 2022) and scale test-time performance by allocating more thinking tokens (Snell et al., 2024; Brown et al., 2024). Early ef- forts enhanced L.M reasoning via supervised fine-tuning human-annotated data (Cobbe al.,
2

---

Published as a conference paper at ICLR 2026
2021: Yue et al., 2023; Yu et al., 2023) linearized search traces (Lehnert et al., 2024; Gandhi et al., 2024). However, due to the distribution shift between LLM responses and curated data, LLM-generated data has proven effective through rejection sampling (Dong et al., 2023; Yuan al., 2023) by filtering out low-quality rationales (Zelikman et al., 2022: 2024) or with EM iterations (Singh et al., 2023; Zhong et al., 2025; Zhang et al., 2025). Recently, RL has gained increasing interest for improving reasoning (Aksitov et al., 2023; Havrilla et al., 2024; Wang et al., 2024a; Shao et al., 2024). Process rewards (Uesato et al., 2022: Lightman et al., 2023) with Monte Carlo unrolls (Kazemnejad et al., 2024; Wang et al., 2023a; 2024b; Luo et al., 2024) offer finer- finer-grained feedback but are computationally expensive. Outcome-reward RL (Guo et al., 2025) demonstrates emergent deliberative reasoning abilities such as self-reflection. Yet, limited work has investigated fact, recent findings suggest that reflections do
the underlying mechanisms of such behaviors. not consistently emerge from RL training and exhibit weak correlation with performance (Liu et al., 2025). Similar to our work, Xiang et al. (2025); Qu et al. (2025) also study reflective exploration of LLMs, from meta-RL (Duan et al., 2016) perspective: Xiang et al. (2025) justifies deliberative reasoning as providing extra CoT state contexts, and Qu et al. (2025) uses progress reward (Setlur et al., 2024) reduce regret in outcome-reward RL. Our method differs from Xiang al. (2025) in that we ground reflective reasoning in environment rewards, rather than relying solely on the internal CoT states generated by the model itself. Compared to Qu et al. (2025), which rewards strategies that make progress towards the correct answer, BARL additionally encourages exploring plausible strategies under the Bayesian framework. We defer a more detailed discussion to the end of Section 4. We experimentally compare with a variant of Qu et al. (2025) that estimates progress using answer probability differences. Prior work has also brought Bayesian exploration principles to LLMs: Arumugam & Griffiths (2025) implements Posterior Sampling for Reinforcement Learning (PSRL), a statistically-efficien algorithm, using LLMs as modular components, while Dwaracherla et al. (2024) shows that active query selection with epistemic neural networks and double Thompson sampling reduces the amount of human feedback required to train reward models for RLHF. In con- trast, optimize Bayesian objective directly during RL fine-tuming of the LLM policy, rather than at the level of external algorithmic scaffolding or data collection, to provide a step-level guidance on when and how L.MSs should self-reflect. Besides, our method differs from Wang al. (2023b); Qiu et al. (2023) that manually designs hypothesis proposal-selection pipelines.
Reinforcement Learning. Conventional RL explores only during training. Exceptions include works that explicitly maximum entropy objectives (Haarnoja et al., 2018) to learn stochastic policies, primarily to accelerate training convergence in settings where evaluation remains in-iistribution, such as robotic control. Bayes-Adaptive RL (Bellman & Kalaba, 1959; Duff, 2002; Guez et al., 2012; Ghavamzadeh et al., 2015; Lidayan et al., 2025; Liu et al., 2023) has been studied to pursue the optimal tity is latent and must be inferred from interaction (states, actions, rewards), Bayesian RL connects naturally to Partially Observable MDPs (Duff, 2001; Ghosh et al., 2021). Exact solutions of the Bayesian RL objective are often intractable, promoting the development of approximate methods (Guez et al., 2012: Zhang, 2022; Chen al., 2024). In our work, we adopt a policy gradient that op- erates over candidate answers, which differs from Ghosh et al. (2022) that leverages value ensembles in offline RL and Qiu et al. (2025) that applies SFT on an oracle Bayesian model's 's outputs.
trade-off in uncertain environments. When the true MDP iden-
PROBLEM FORMULATION
LLM Reasoning. A finite-horizon MDP M can be defined by the state space S, action space A,, horizon T. and reward function (s, a). where s E S and a E A. Here, the initial state su the prompt, and the action is the 1-th step of the CoT, which can be either separated by special tokens (Wang et al., 2023a) or defined as fixed length of reasoning tokens (Luo et al., 2024). We adopt the latter definition due to its simplicity. The state transition is deterministic by appending the new reasoning step, i.c., St41- = St + ae.
We are interested in a mation about the true MDP ' = (S, A, r, T) via the input training data D. During deployment, freeze the learned policy and deploy it in M Notably, D does not uniquely identify M in- ducing epistemic uncertainty about the MDP. Formally, D and a prior distribution over MDPs p(M) define a posterior distribution over MDPs, pD) x p(M))(D(M) The objective for policy is
procedure. During training, the agent only receives infor-
3

---

Published as a conference paper at ICLR 2026
thus to maximize return in expectation over MDPs from the posterior pl D)
=(x)= = 1 (a [JM(T)] where (M( = e0
Σ (x) r==
(3.1)
This [(r) objective is designed to, for any data D, train a policy я that maximizes its Bayes- expected return in the unknown true environment during deployment, i.e., its performance averaged over MDPs drawn from the posterior p(M[D).
Progress Reward. Prior work (Uesato al., 2022: Guo al., 2025) employs outcome-level reward verifier(&r, V2e)) ) for the true MDP M", which uses a verifier to perform regular expression match (either 0 or 1) between sT and the ground-truth answer y2, corresponding
the prompt so- We extend this sparse-reward setting by incorporating a progress reward (Setlur et al., 2024; Qu et al., 2025), which quantifies the increase of the model's probability of outputting y after appending at the CoT 8, i.e., for 0 -
(3.2) where </think> is the end sign of thinking, such as the answer elicitation prompt "Based on the above reasoning, the answer \boxed" that we adopt, and m any policy. Compared to Monte-Carlo process rewards (Luo et al., 2024; Qu et al., 2025), (3.2) is computationally efficient by avoiding multiple branched rollouts at each step, and the KV cache of 80:T during rollouts can also be reused. The above definition naturally extends to any TM defined w.r.t. the answer yoM. The Q-value is then
r(8;, ax) = T (V.. | + + </think>) - To 8 + </think>);
Q (he, ax) Ex Σ rM ar) + verifier(sT. y
(3.3)
where h4 (so, ag: Fo...... . $1) is the history and we define s(h,) st the final state 8 from h
Reflective Exploration. Informally, we define reflective exploration as the pattern in which the LLM revisits prior state after an in-context exploratory step to take different actions at that state. Specifically, a language reflection step such "Let's reconsider the geometric relationship" corresponds to visiting and retrying. We illustrate this using a binary search tree as in the right figure: for the trajectory 8p 81 - 82 81 83, 81 82 is an explo- ration step, $2 $1 is a reflective step that signals the strategy switch from $2 to s3, and the "geometric relationship" in the above example originates from $1. We formalize this behavior through the lens of adaptive policies.
So
Figure An exam- ple of reflective rea- soning trajectories.
Definition 3.1 UUncertainty-Adappie Policy). Define the belief as the posterior over MDPs (MM))MM) p(M h4, D). A policy is uncertainty-adeptive if there exists measurable map- ping /4: S x + ((AA) such that for all ht and a,, <a h4) = plat s(h,), b(h+)). If in ad- dition, there exists f4 and h/ such that s(he) s(h() but u(a, s(he), + p(a, s(h)), 6(K)). then x is strictly uncertainty-adaptive. or equivalently, not Markovian.
From this perspective, reflective exploration is the behavioral signature of uncertainty-adaptive policy: as the agent's belief evolves, it rationally revisits previous states and generates a different action distribution. In contrast, purely state-only policy that ignores this evolving belief would respond identically upon revisiting the same state. Formally,
Definition 3.2 (Reflective Exploration). We say that a policy π exhibits reflective exploration if there exist t > to and heg ft, such that
((s(he,)) = p(s(hh,)))
T(- (r,) # π(- hx2),
where sp S + - is measurable mapping for which there exists 0 Z x HR - A(A) satisfying for every he that (1) 0(- ((ss), r0 = T(- he); and (2) if there is some process X, and some such that (- h2) v(- Xt) then X, ((((sst)) for some measurable vi.
Intuitively, it describes an agent that returns to the same underlying latent state but, in light of what it has learned from past rewards, deliberately chooses a different strategy than it did before. The latent state representation o abstracts away superficial differences in the text state. The existence of I and u, da formalizes the latent factorization and state-minimality properties of yp, respectively.
4

---

Published as a conference paper at ICLR 2026
4 THE NECESSITY OF BAYESIAN RL FOR REFLECTIVE EXPLORATION
Conventional RL. The RL objective for policy JM- (a) in (3.1). It is widely known that the optimal policy and value satisfy the Markov property by depending on h, only through the state St. Theorem 4.1 (RL Admits Markovian Optimal Policy). For any MDP, there exists a Markovian policy x², i.e., policy that is not strictly eneertaitt--daaptiin that maximizes the RL objective. Every policy that exhibits reflective exploration is not Markovian.
The result indicates that the RL objective admits Markovian policies to be optimal. Optimizing a Markovian policy, however, does not induce reflective exploration behaviors. Intuitively, action sequences whose effect is only enrich the history (e.g.. incorrect attempts followed by revisiting the same state) do not change the sufficient state representation 8y and therefore cannot improve the value of an optimal Markovian policy.
Instead, in RL, exploration is only useful during training, in trial-and-error manner with repeated episodes, discover a retur- maxummiiiiii action sequence. The learned policy is fully exploited at deployment time with no incentive for further exploration since no policy updates occur, which is why e-greedy often sets R 0 when deployed (Mnih et al., 2015; Hessel al., 2018).
Bayesian RL. In Bayesian RL, the agent maintains uncertainty over the underlying MDP, which gradually reduced through interactions. Due to this epistemic partial observability (Duff, 2001; Ghosh et al., 2021), 1). the policy and value depend on the full history lu, instead of only the state St. to capture the agent's evolving belief about the MDP parameters through cumulative observations. The objective encourages the agent to not only maximize immediate rewards based on the current belief but also to explore to gather more context about the uncertain MDP.
Theorem 4.2 (Bayesian RL Admits Adaptive Optimal Policy). For the Bayesian RL objective in (3.1) associated with any (D, p(M), there exists optimal policy '² that is imcertainty-adaptrii
The above result shows that optimizing the Bayesian RL objective in (3.1) attains an uncertainty- adaptive policy and thus naturally inducing reflective exploration. While reflective actions may be suboptimal relative to the (unknown) ground-truth MDP, the gathered context, especially rewards, reduces the MDP uncertainty. Future policies can thus leverage the updated belief to act optimally.
Theorem 4.2 should be read as structural result: for any (D, p(M)), one can always represent is possible that the dependence on the belief can be vacuous and the policy degenerates to Markovian. However, we will show in the following that there exist instances where any Bayes-optimal policy must be strictly uncertainty-adaptive and the best Markovian policy can far underperform the optimal adaptive policy.
Bayes-optimal policy to uncertainty-adappiee
Theorem 4.3 (Gap Between Markovian and Adaptive Policies). There exist instances (D,p(M) for which the objective in (3.1) is maximized by a strictly uncertainty adaptivv policy. Moreover, the performance gap between Markovian and strictly adaptive policies can arbitrarily large.
Sketch of proof. Consider the binary decision structure in Fig. 1. Let the prior p(M1) p(M2) p(Ma) = p(MM)) = 1/4, where TM, (82) = T,M (83) = (*5) (*6) = all other rewards are zero, and 'D = Ø is empty. Here, r(s) represents the reward of reaching For any Markovian policy, the maximal return is 1/4 (or 1/2d-1 for a depth-d structure). In contrast, the optimal umcertainty-adaptiv policy has a return of 1. This is achieved by maintaining a hypothesis set C = {M,, M2, C [M E C TyM (s) = r). Then each r = 0 removes one hypothesis from C, and r = 1 identifies the true MDP. After at most four leaf visits, we have found the rewarding leaf and the return is 1. We can increase d to make the performance gap (1 versus 1 1/2d-1) arbitrarily large.
After visiting a leaf state and observing reward r E (0. 1}. update
Comparison Between Conventional RL and Bayesian RL
Conventional RL does not admit strictly uncertainty-adaplee policies, which do not give rise to reflective exploration. Instead, exploration is trial-and-erros during training and only serves to fit a fixed policy. In contrast, Bayesian RL yields uncertainty-adaptie policies whose actions depend on the evolving belief over MDPs, thereby incentivizing information gathering and inducing reflective behaviors through belief updates at deployment time.
5

---

Published as a conference paper at ICLR 2026
Connection with Meta-RL. Although our Bayesian RL framework is orthogonal to meta-RL, we discuss the connections between them here. The goal of meta-RL is to learn a fast adaptation procedure across tasks, e.g., by optimizing deployment performance after only few iterations of updates. From this perspective, incertainty-adapiii policy in Definition 3.1 can be viewed as per- forming in-context learning (instead of parameter updates), and our framework can be interpreted as learning to do in-context learning. However, our analysis focuses more on properties of policies that optimize the Bayesian RL objective, which enforce the Bayes-optimal solution the exploration- exploitation tra In other words, our framework explicitly maintains a belief over MDP and uses belief-driven exploration strategy that rewards under the posterior.
5
METHOD
In the previous section, we analyzed the benefits of Bayesian RI. and the role of self-reflection within the Bayesian RL framework. In what follows, we present practical way optimize the Bayesian RL objective in (3.1). The policy gradient for (3.1) is as follows, which differs from the conventional policy gradient by replacing the value under M with a posterior-weighee value:
VoJ = EE Ty
Σ 2=0
Vo log (a ha) (EMM- (Me a+)]
(5.1)
Here, we use the state-action value Q instead of calculating the advantage since the latter requires branched Monte Carlo rollouts at each step, which computationally costly. By applying the Bayes rule, the posterior satisfies:
P(M D.ha) = p(M D,,0:, Po:-11 x p(M) (D,0a)) p(roa-1 | 8o.t; 10: (5.2)
where p(MiD,suu conditions only on the CoT, excluding rewards, and can be modeled as the probability that the policy Te, after training on DD generates the solution y Interestingly, the second term p(ro:-1|$0o: M, measures the likelihood of observing the rewards ro:-- under M given the trajectory 80.z. We follow Ghosh et al. (2022) to write p(re|se MM) x exp(-31re (st, a:))) with hyperparameter 3 to obtain
f-1
f-1 II f==0
p(roa-1 80st; M) x
II p(re ses, de,M) F'=0
( (SM, (5.3)
where the proportionality holds since p(re|rozt 80.,, 40 10a-1, M) ar,
Besides, the posterior-weighted value in (5. satisfies
IMI OM (he, a.)(MM h()
P(M hT) {M 8o)
E (h+, a:)] = (M
2T (he, a.)
where the proposal (MM is the uniform distribution over the support of plausible MDPs, defined w.r.t. the troun answer and candidate answers extracted from the model's CoT's We draw [M] CoT rollouts of ma on prompt so to form MM. The importance ratios are then self- normalized over {M& and the ground- truth MDP My defined w.r.t. yo,- Substituting (5.2) and (5.3) into the above equation and letting p(M,) Sox) be the model's catte-ooniiionall belief gives
M
i==
E, (he Σ Enn, (be, ue) To( Mi |sr </think>)
II exp(-3/re - T.Me, (Ser, (eber.ee)) de))): (5.4)
value in M, model plausibility for M:
consistency b/w observed & JM''s reward
where To is the actual observed reward as defined in (3.2), and TM,, Qia are defined in (3.3) w.n.. the hypothesis MDP M, Since rewards are not available at deployment time, they are not explicitly provided as inputs to the policy. Instead, maximizing the Bayesian RL objective forces the parame- ters 0 to encode prediction of the reward function of state, thus absorbing the dependence on rewards into 9. For clarity, we have omitted the normalization constant when computing p(M, from the last two terms. Algorithm 1 provides the unbatched version of the pseudocode.

---

Published as a conference paper at ICLR 2026
Algorithm BBayes-Adptiive RL for LLM Reasoning (BARL)
1: Input: LLM Te, prompt set {50} with ground answers {2
2: for each prompt 5o in the training data do
3: Sample |M| CoTT from Te on Su-
4: Extract the IM| candidate answers from each CoT to form candidate set {y J
5: for each of the |M] Co'Ts do
6: Calculate postertirttttetteeeeeeeeeee wesighe value with (5.4) for each timestep t and update A with (5.1).
BARL offers principled framework for stitching together plausible strategies, analogous to lin- earizing best-of-N reasoning, but with guidance on when and how LLMS should reflectively explore. each hypothesis MDP Mú. The first weighting term Te <o(y>==l-) captures LLM's s stateccondiional belief in the plausibility of M,, The second product weighting term accumulates the discrepancy between predicted rewards M. (st, ae) and observed rewards Tr', which serves as reflective signal for strategy switching by downweighting hypotheses that have high belief probabilities but are unlikely be optimal.
Remark 5.1. BARL maximizes the weighted sum of values defined
HOW BARL HELPS GENERALIZATION,, A DIDACTIC EXAMPLE
Now we present a didactic example to show how BARL facilitates eest- time generalization. Consider the action space A that consists of three tokens, {0, 1, 1,2], with one token generated at each timestep. The ob- jective is to repeat the prompt token three times consecutively within 29 timesteps (3 + is the minimal length to include all unique triplets). The prompt token is
Train
0/1/2
M
during training, which does not have coverage for 2. After training, the policy is deployed, where we consider the prompt token of 2 as the evaluation task. Episodes terminate when receiving reward. This setup is illustrated in Figure 2.
Eval
+ r-1
0/1/2
Figure 2: Setup: repeat- ing the prompt token (orange) three times re- ceives a reward.
This setup mirrors LLM reasoning, where the goal is not only learn specific strategies (here, generating particular triplets), but also general problem-solving abilities, such when and how switch to new strate- gies. These capabilities are essential for handling distribution shifts between training and eval, common challenge when developing I.LMs.
We use a 2-head transformer encoder followed by linear layer the policy and train it using the policy gradient from conventional RL and from BARL (5.1). For RL, the state-action value QT in the policy gradient is 1 only when 80:7-1 contains the rewarding triplet argmax, r(rr)) of the ground-truth MDP, such as 000 or 111 during training. For BARL, we set B = oo so that I exp(-3)rr TM, (Str, )l) = 1 (argmax, T.M (tri) & 8o:t). i.e., the product the rewarding triplet of M, already appears in So. (since Ty for unterminated sequences) and 1 otherwise. For the policy's 's state-conditional belief p(M)so sampling from it is equivalent to sampling ag ~ To (-(ss), with the associated M satisfying argmax r (tri) 8t-1:141- Therefore,
when
EM [M[Q (s,, 4:)] EMMp(M)ooun) [ (8t, at) (argmaxr. & so::]] E, [1 (8t-14441 & so:e)]
The above formulation incentivizes the policy to eliminate hypotheses and switch to new strategies (i.e.. new triplets) when the current strategy has been invalidated by earlier attempts up to step t, which is illustrated Figure 3. This form of adaptive exploration provides a minimalist instantiation of BARL in synthetic settings. The difference between the above equation and (5.4) arises because the agent here aware of the zero reward associated with unfinished episodes.
Train
Eval
Train & Eval
2
3' MDPe m10001 of 1-02211 X
1100-1
random 0/1/2
hypotheses ritorp-- of m0000-
1000 1925
memorize solutions
fail to generalize
switch strategies eliminated hypotheses
belacted 5ED bekeiia DOu
Conventional RL
Bayes-Adaptive RL
Figure 3: Comparison between conventional RL and BARL in this didactic example.
7

---

Published as a conference paper at ICLR 2026
We report the results in Figure 4, where accuracies averaged over 50 completions and the shadow regions are the standard deviation across 3 independent model training runs. The results show that RL quickly finds and memorizes the training solutions but fails to generalize when deployed to the evaluation tasks. In contrast, Bayes-Adaptive RL significantly increases the evaluation accuracies. Furthermore, the accuracy and convergence rate improve when given prior knowledge that rewarding triplets are repeated patterns, i.c., [M] 3 with тM, (000) = r,M, (111) r.Ms (222) = 1. This highlights the advantage of more informative candidate sets, underscoring the importance of balancing diversity and plausibility of the candidates. Specifically, they should be diverse enough to capture deployment-timg uncertainty, yet constrained only the most plausible candidates shrink the hypothesis space.
Convention ntional RL
Bayes Adaptive RL [[ = 3?)
Bayes Adaptive RL []M]
1.0
Accuracy
0.6
Train Eval
Accuracy
Accuracy
0.8
0.4
Train Eval
Train
0.8
0.6
Eval
50
150
200
150
Training spoch
Training opoch
Training apoch
Figure 4: Conventional RL (REINFORCE) memories training solutions and poorly generalizes be- yond the training prompts. BARL performs well when deployed to the evaluation tasks, and im- proves with more informative candidate sets.
7 EXPERIMENTS
EXPERIMENT SETUPS
In addition to the synthetic experiment, we evaluate BARL on math tasks. We implement BARL across various models, including Qwen2.5-Math-1.5B Qwen2.5-Math-77 (Yang al., 2024), and DeepSeck-RI-Distil--
(Guo et al., 2025). Training is conducted on the Big-Math dataset (Albalak et al., 2025), and evaluation is performed on four benchmarks: GSM8K (Cobbe et al., 2021), MATH (Hendrycks et al., 2021), CollegeMath (Tang et al., 2024), and OlympiadBench (He et al., 2024). During training, the maximum prompt length is set to 512 and the maximum response length is set to 1024. For BARI, we set B = and | 5 in Algorithm 1.
We compare BARL against two RL baselines that span outcome- and process-reward RL. For the outcome-reward GRPO baseline, we set its group size to 5 for a fair comparison with BARL and, af- ter performing grid search over the KL-divergence coefficients [0, 0.001, 0.005, 0.01]. adopt 0.005 as it yields the best overall performance across all benchmarks. For the process-reward baseline, we adapt variant of MRT (Qu et al., 2025) by integrating the progress reward defined in (3.2) into the outcome reward, which we refer to as progress in the following sections. For all algorithms, we set the training and rollout batch sizes to 128 and 1024, respectively. We train the Qwen and Llama models for 110 and 60 iterations, respectively, defined w.r.t. the rollout batches. The temper- ature during online sampling is 1.0 and is 0.0 during evaluation. For both BARL and the progress baseline, set the number of tokens for each reasoning step 128.
7.2 EXPERIMENT RESULTS
We report the pass @1 accuracies in Table 1, All models are trained using three random seeds, and we calculate the mean and standard error of the resulting accuracies. For each algorithm, we report the results of the checkpoint that has the overall best performance all benchmarks.
We observe that BARL achieves higher accuracies across most benchmarks and models. consis- tently outperforms the two conventional RL baselines in terms of average accuracy, with the most significant gains observed on challenging benchmarks that demand effective exploration. Notably, BARL delivers these gains with minimal computational overhead, which comes from calculating the probabilities of candidate answers at the end each step, reusing the prefix cache from CoT generations. We defer the curves of accuracies and response lengths to Appendix B. and B.2.
8

---

Published as a conference paper at ICLR 2026
Model
GSM8K
MATH
College 6.6
Olympiad 21.8
AIME
AMC
Average
Qwen-I.5B
40.0
34.1
16.7
32.5
25.3
GRPO
83.9(+0.5)
71.5(#D.4)
45.1(+0.a)
31.6(+0.4)
17.8(+0.9)
55.8(+0.7)
51.0(=u.3)
Progress
84.8(+0.6
72.1(+0.4)
45.9(+0.))
35.5(+0.3)
14.4(+0.9)
55.8(+0.7)
51.4(=0.2)
BARL
85.8
(2.00))
26.8(
(5.8
17.8(10.9)
60.8()0.7)
53.3(10.4)
Qwen-7B
59.1
53.7
21.9
19.0
13.3
42.5
34.9
GRPO
90.3(#0.1)
77.6(#D.4)
47 17.0(+b.3)
38.5(+0.2)
21.5(#0.4)
65.0(#1.2)
(7.1(=0.2)
Progress
91.1(10.3)
78.8(10.1)
46.7(1..1)
41.1(40:2)
24.5(4
65.4(11.4)
07.9(=0.2)
BARL
(4.22)
(1.2()
(2..
(2.0(=0.4)
29.0(10:4)
66.7(11.4)
59.4(1003)
Llama-8B
82.0
65.7
35.8
26.5
10.0
42.5
43.7
GRPO
85.7()0.5)
(2.34)
39.6(40.3)
36.0(20:5)
16.7(#0.8)
60.4(20.3)
52.1(=0.4)
Progress
(4.94)
73.9(+0.4)
39.8(+0.5)
35.3(+
15.0(+0.8)
51.0(=0.4) 55.8(40.7)
BARL
85.4(+0.6)
73.9(40.8)
40.4(
(7.2(+0.6)
17.8(+0.9)
(1.7(40.77)
52.7(40.4)
Table 1: Mean and standard error of the accuracies over three independent training runs.
7.3 ABLATION STUDIES
Token Efficiency. We evaluate the token efficiency of BARL and baseline methods by measuring the total numbers of tokens required to solve a problem. Specifically, in Figure 5, we plot the pass @k accuracies and the corresponding average numbers of tokens as proxy for per-token performance. In all the following ablations, we mainly analyze models fine-tuned from Swen2.5-Math-11. and set the temperature to 1.0, but observe that the GRPO and base models are
We
vary k from less robust under sampling, resulting in decreased pass@) 1 performance (see Appendix B.3), To account for this, we combine greedy decoding outputs with sampled outputs when computing token usage and accuracy. We omit the base model from the plots due to its significantly higher token consumption and lower asymptotic accuracy. We find that BARL achieves higher accuracies with substantially fewer tokens, requiring up 1.63x fewer average tokens than the progress baseline, 2x fewer than GRPO, and over 10x fewer than the base model.
CallegeMath
OlympladBanch
Accomay
Axc
Accumac
02.5
GRPO
GRPO
CAPO
GRPO
x
Progress
Total Numbors of Taionn
Total Numberrs of Takene
T:ol Numbors To-iooss
10t2i Numbers of Tokons
Figure 5: BARL achieves higher pass @k accuracies with fewer total numbers of tokens.
Frequency of Self-Refiection Behaviors. To qualitatively assess the improved token efficiency of BARL, we analyze the frequency of re- flective behaviors across problems of varying difficulty levels, as shown in Figure 7.3, with GSM8K and MATH in dashed and solid lines, re- spectively. For each problem,
sample 6 responses per model and define its difficulty level by the number of incorrect responses. We use -asedd detections (Liu et al., 2025; Yeo et al., 2025) identify if self-reflections appear in a response. A problem is considered to ex- hibit self-reflection if least one of its responses is identified. It can be observed that both the base and the BARL models display fewer re- flections on easier problems. The base model exhibits an overall higher frequency of reflections despite achieving lower accuracies. This result reveals the weak correla- tion between the performance of LLMSs and the response length or the frequency of reflections. Rather, the effectiveness of thinking tokens and the efficiency of explorations are the determining factors, which we will study in the following. Notably, our conclusions are not weakened by the potential inaccuracies of keyword-based detections. The fact that the base model triggers more "reflection" tokens yet underperforms BARL suggests that it has acquired superficial stylistic reflec- tion patterns during pre- pre-traine training (e.g., from long- -oTT annealing data) without effective exploration, whereas BARL yields more effective reflective exploration rather than more frequent but less effec- tive stylistic reflections.
2.35
pittouity Lovel
Figure 6: Reflection freq. on GSM8K (dashed) and MATH (solid) problems.

---

Published as a conference paper at ICLR 2026
Effectiveness of CoTs. We measure the effectiveness of the CoTs produced by different models by calculating the average Bayesian state-action values at all timesteps, which naturally captures both the exploration and the exploitation aspects of the actions. Unlike standard Q-values, the Bayesian Q-value not only incorporates the expected returns (exploitation) but also captures the value of information gained through belief updates (exploration).
MSM
NATH
CollegeMath
OlympadBench
Rase
Buse
6.44
G2.00
BARI
BARI
6.00
1/0
GRTO
-038
BARI
20
23
320
100
232
420
626
320
11.6
15%
255
520
13
1900
1200
300
120
(2)
X3
1897 10%
Figure 7: Ablation on how effective the CoTs explore and exploit, measured by the Bayesian values.
The results are reported in Figure 7. We observe that the actions from the BARL model exhibit con- sistently higher Bayesian values compared those of the GRPO and base models, indicating more effective exploration and exploitation. On more challenging benchmarks such as OlympiadBench. exploratory gains peak midway through the CoTs after an early phase of uncertainty reduction. Moreover, the result also explains our earlier observations on token efficiency and reflective behav- iors. Although the base model exhibits more relf-ceflections, these are likely superficial or stylistic patterns due to their low exploration efficiency for gathering informative contexts during evaluation.
Conventional RL Optimality. We train a length-controlled (L.C GRPO with max- imum 32 response length over multiple epochs. Figure 8 shows the evolution of the training accuracy and response length. The rapidly decreasing length of LC GRPO in- dicates that it learns to skip CoT generation and emit only the final answer. Its asymp- Figure 8: Training accuracies, lengths and eval results.
GAFO
Accura bele)
DEPO
LC
100
125
352
totic training accuracy matches that of GRPO (max length 1024). This result supports Theorem 4.1: conventional RL can achieve optimality by merely memorizing solutions without reflective reasoning. Such policies, however, generalize poorly during evaluation.
Key Experiment Findings
BARL consistently outperforms conventional RL baselines with superior token efficiency. Performance correlates with the effectiveness of reflective explorations, rather than their frequency. Optimality in conventional RL can be attained by policies that memorize training solutions yet fail to generalize, with no guarantees on the emergence of self-reflections.
CONCLUSION
LLMs trained via RL have exhibited emergent behaviors such as self-reflections, which offers po- tential way for test-time scaling by backtracking to a previous state and generating a different action distribution with updated context. However, conventional RL training neither ensures the emergence of reflective exploration nor explains its benefits. The optimal RL policies are typically Markovian and have no incentive enrich revisited state with additional context since they depend on the history only through the state. Instead, RL exploration is confined to the training phase to iden- tify action sequences that maximize cumulative rewards, and resorts to pure exploitation when the policy parameters are frozen after deployment. We propose to ground reflective exploration with Bayesian RL objective that maximizes expected deployment-time return under a posterior distribu- tion over MDPs induced by the training data. To maximize this objective, we propose BARL, which provides step-level guidance for when and how to engage in reflective exploration. BARL enables efficient exploration through hypothesis climination and strategy switching. Our experiments conducted on both synthetic and mathematical reasoning tasks, where we show that BARL outper- forms conventional RI. algorithms for evaluation benchmarks, and its exploration is more efficient.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Renat Aksitov, Sobhan Miryoosefi, Zonglin Li, Daliang Li, Sheila Babayan, Kavya Kopparapu, Zachary Fisher, Ruiqi Guo, Sushant Prakash, Pranesh Srinivasan, et al. Rest meets react: Self- improvement for multi-step reasoning I1m agent. arXiv preprint 1rXiv:2312.10000 2023.
Alon Albalak, Duy Phung, Nathan Lile, Rafael Rafailov, Kanishk Gandhi, Louis Castricato, Anikait Singh, Chase Blagden, Violet Xiang, Dakota Mahan, et al. Big-math: A large-scale, high-quality math dataset for reinforcement learning in language models. arXiv preprint arXiv:2502.17335 2025.
Dilip Arumugam and Thomas L Griffiths. Toward efficient exploration by large language model agents. The Exploration in Al Today Workshop at ICML 2025, 2025.
Richard Bellman and Robert Kalaba. On adaptive control processes. IRE Transactions on Automatic Control, 4(2):1-9, 1959.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint urXiv:2407.217877 2024.
Jiayu Chen, Wentse Chen, and Jeff Schneider. Bayes adaptive monte carlo tree search for offline model-based reinforcement learning. arXiv preprint arXiv:2410. 11234, 2024.
Karl Cobbe, Vincet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reichhro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2 10, 14168, 2021.
Hanze Dong, Wei Xiong, Deepanshu Goyal, Yihan Zhang, Winnie Chow, Rui Pan, Shizhe Diao, Jipeng Zhang, Kashun Shum, and Tong Zhang. Raft: Reward ranked finetuning for generative foundation model alignment. arXiv preprint arXiv:2304.0627 2023.
Yan Duan, John Schulman, Xi Chen, Peter L Bartlett, Ilya Sutskever, and Pieter Abbeel. RI2: Fast reinforcement learning via slow reinforcement learning. arXiv preprint arXiv: 1.02779, 2016.
Michael O Duff. Monte-carlo algorithms for the improvement of finite-state stochastic controllers: Application to bayes-adaptive markov decision processes. In International Workshop on Artificial Intelligence and Statistics, pp. 93-97. PMLR, 2001.
Michael O' O'Gordon Duff. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002.
Vikranth Dwaracherla, Seyed Mohammad Asghari, Botao Hao, and Benjamin Van Roy. Efficient ex- ploration for llms. In International Conference Machine Learning, pp. 12215-12201 PMLR, 2024.
Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (sos): Learning to search in language. arXiv preprint arXiv:2404.0360 033683 2024.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, Aviv Tamar, et al. Bayesian reinforcement learning: A survey. Foundations and Trends@ in Machine Learning, 8(5-6):359 483, 2015.
Dibya Ghosh, Jad Rahme, Aviral Kumar, Amy Zhang, Ryan P Adams, and Sergey Levine. Why generalization in rl is difficult: Epistemic pomdps and implicit partial observability. Advances in neural information processing systems, 34:25502-2555 255115, 2021.
Dibya Ghosh, Anurag Ajay, Pulkit Agrawal, and Sergey Levine. Offline rl policies should be trained to be adaptive. In International Conference on Machine Learning, pp. 7513-7530 PMLR, 2022.
Arthur Guez, David Silver, and Peter Dayan. Efficient bayes-adaptive reinforcement learning using sasple-based search. Advances in neural information processing systems, 25, 2012.

---

Published as a conference paper at ICLR 2026
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song. Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501. 2025.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy
maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learming. pp. 1861-1870. Pmlr, 2018.
Alex Havrilla, Yuqing Du, Sharath Chandra Raparthy, Christoforos Nalmpantís, Jane Dwivedi- Yu, Maksym Zhuravinskyi, Eric Hambro, Sainbayar Sukhbaatar, and Roberta Raileanu. Teaching large language models to reason with reinforcement learning. arXiv preprint arXiv:2403.04642, 2024.
Chaoqun He, Renjie Luo, Yuzhuo Bai, Shengding Hu, Zhen Leng Thai, Junhao Shen, Jinyi Hu, Xu Han, Yujie Huang, Yuxiang Zhang, et al. Olympiadbench: challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems. arXiv preprint arXiv:2402. /4008, 2024.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03677 2021.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai ol system card. arXiv preprint arXiv:2412.1672 2024.
Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Roux. Vineppo: Unlocking rl potential for Ilm reasoning through refined credit assignment. arXiv preprint arXiv:2410.01679, 2024.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 1122119-222133 2022.
Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul Mcvay, Michael Rabbat, and Yuandong Tian. Beyond a*: Better planning with transformers via search dynamics bootstrap- ping. arXiv preprint 240.:22402.1488,, 2024.
Aly Lidayan, Michael D Dennis, and Stuart Russell. BAMDP shaping: a unified theoretical frame- work for intrinsic motivation and reward shaping. In The Thirteenth International Conference on Learning Representations, 2025.
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2023.
Zhihan Liu, Hao Hu, Shenao Zhang, Hongyi Guo, Shuqi Ke, Boyi Liu, and Zhaoran Wang. Reason for future, act for now: A principled framework for autonomous 11m agents with provable sample efficiency. arXiv preprint 2il::2399.1888 2023.
Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi. Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. Understanding rl-zero-like training: A critical perspective. arXiv preprint arXiv:2503.20788 2025.
Liangchen Luo, Yinxiao Liu, Rosanne Liu. Samrat Phatale, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, Jiao Sun, et al. Improve mathematical reasoning in language models by automated process supervision. arXiv preprint arXiv:2406.06599 2, 2024.
12

---

Published as a conference paper at ICLR 2026
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning, nature, 518(7540):529-533 2015.
Linlu Qiu, Liwei Jiang, Ximing Lu, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang, Yoon Kim, Yejin Choi, Nouha Dziri, al. Phenomenal yet puzzling: Testing ductive reasoning capabilities of language models with hypothesis refinement. arXiv preprint arXiv:2310.08559 2023.
Linlu Qiu, Fei Sha, Kelsey Allen, Yoon Kim, Tal Linzen, and Sjoerd van Steenkiste. Bayesian teach- ing enables probabilisticc reasoning in large language models. arXiv preprint arXiv:2503.15525 2025.
Yuxiao Qu, Matthew YR Yang, Amrith Setlur, Lewis Tunstall, Edward Emanuel Beeching, Ruslan Salakhutdinov, and Aviral Kumar. Optimizing test-time compute via meta reinforcement fine- 2025.
tuning. arXiv preprint arXiv:2503.0111
Amrith Settur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Eisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar. Rewarding progress: Scaling automated process verifiers for Ilm reasoning. arXiv preprint arXiv:2410.08 2024.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Mingchuan Zhang, YK Li, Yu Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint 20:::2202.33000 2024.
Avi Singh, John D Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Xavier Garcia, Peter J Liu, James Harrison, Jachoon Lee, Kelvin Xu, et al. Beyond human data: Scaling self-training for problem-solving with language models. arXiv preprint arXiv:23/2.06558 2023.
Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. Learning without state-estimation in partially observable markovian decision processes. In Machine Learning Proceedings 1994, pp- 284 292. Elsevier, 1994.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXfvv2408.033114 2024.
Zhengyang Tang, Xingxing Zhang, Benyou Wang, and Furu Wei. Mathscale: Scaling instruction tuning for mathematical reasoning. arXiv preprint wwXXiv2403.00888. 2024.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.14273 2022.
Huaijie Wang, Shibo Hao, Hanze Dong, Shenao Zhang, Yilin Bao, Ziran Yang, and Yi Wu. Offline reinforcement learning for Ilm multi-step reasoning. arXiv preprint arXiv:2412. 16145, 2024a.
Peiyi Wang. Lei Li, Zhihong Shao, RX Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math sath-sheephed: Verify and reinforce lims step-by-step without human annotations. arXiv preprint 12X.v:33/22089333 2023a.
Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah D Goodman. Hypothesis search: Inductive reasoning with language models. arXiv preprint arXiv:2309.05660 2023b.
Zihan Wang. Yunxuan Li, Yuexin Wu, Liangchen Luo, Le Hou, Hongkun Yu, and Jingbo Shang. Multi-step problem solving through a verifier: An empirical analysis on induleidduced process supervision. arXiv preprint arXiv:2402.02653 02658, 2024b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi. Quoe V Le, Denny Zhou, et al. Chain-of tf-hhughtt prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-2444 22-837, 2022.
13

---

Published as a conference paper at ICLR 2026
Yuxiang Wei, Olivier Duchenne, Jade Copet, Quentin Carbonneaux, Lingming Zhang, Daniel Fried, Gabriel Synnaeve, Rishabh Singh, and Sida I Wang. Swe-rl: Advancing Ilm reasoning via rein- forcement learning open software evolution. arXiv preprint arXiv:2502.18449, 2025.
Violet Xiang, Charlie Snell, Kanishk Gandhi, Alon Albalak, Anikait Singh, Chase Blagden, Duy Phung, Rafael Rafailov, Nathan Lile, Dakota Mahan, et al. Towards system reasoning in Ilms: Learning how think with meta
arXiv preprint arXiv:2501.0465: 2025.
An Yang, Beichen Zhang, Binyuan Hui, Bofei Gao, Bowen Yu, Chengpeng Li, Dayiheng Liu, Jianhong Tu, Jingren Zhou, Junyang Lin, Keming Lu, Mingfeng Xue, Runji Lin, Tianyu Liu, Xingzhang Ren, and Zhenru Zhang. Qwen2.5-math technical report: Toward mathematical ex- pert model via self- infr-vepooeettt... arXiv preprint wrXiv:2409.12122 2024.
Edward Yeo, Yuxuan Tong, Morry Niu, Graham Neubig, and Xiang Yue. Demystifying long chain- of-thought reasoning in Ilms. arXiv preprint arXiv:2502.03373, 2025.
Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James T Kwok, Zhen- guo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical questions for large language models. arXiv preprint arXiv:2309. 12284, 2023.
Qiying Yu. Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Tiantian Fan, Gaohong Liu, Lingjun Liu, Xin Liu, et al. Dapo: An open-source IIm reinforcement learning system at scale. arXiv preprint arXiv:2503. 14476, 2025.
Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Keming Lu, Chuanqi Tan, Chang Zhou, and Jingren Zhou Scaling relationship on learning mathematical reasoning with large language models. XrXiv preprint MxXx:23308.0182 2023.
Xiang Yue, Xingwei Qu, Ge Zhang, Yao Fu, Wenhao Huang, Huan Sun, Su, and Wenhu Chen. Mammoth: Building math generalist models through hybrid instruction tuning. arXiv preprint arXiv:2309.05653, 2023.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances Neural Information Processing Systems, 35:154766 15488, 2022.
Eric Zelikman, Georges Harik, Yijia Shao, Varuna Jayasiri, Nick Haber, and Noah Goodman. Quiet-star: Language models can teach themselves to think before speaking. arXiv preprint arXiv:2403.09629 2024.
Weihao Zeng, Yuzhen Huang, Qian Liu, Wei Liu, Keqing He, Zejun Ma, and Junxian He. Simplerl- 20o: Investigating and taming zero reinforcement learning for open base models in the wild. arXiv preprint arXiv:2503.18888 2025.
Shenao Zhang. Conservative dual policy optimization for efficient bosel- reinforcement learn- ing. Advances in neural information processing systems, 35:25450-25463, 2022.
Shenao Zhang, Donghan Yu, Yihao Feng, Bowen Jin, Zhaoran Wang, John Peebles, and Zirui Wang. Learning to reason as action abstractions with scalable mid-training rl. arXiv preprint arXiv:2509.2588 258/0, 2025.
Han Zhong, Yutong Yin, Shenao Zhang, Xiaojun Xu, Yuanxin Liu, Yifei Zuo, Zhihan Liu, Boyi Liu, Sirui Zheng, Hongyi Guo, et al. Brite: Bootstrapping reinforced thinking process to enhance language model reasoning. arXiv preprint arXiv:2501. 18858, 2025.
14

---

Published as a conference paper at ICLR 2026
A PROOFS
A.1 PROOF OF THEOREM 4.1
Proof. Let .t be any optimal policy (possibly history-dependent) Suppose prescribes different action distributions at the same state s depending on the history that led to s.
Let 01 and 82 be two such distributions with Eg-ó, Q* (s, > Bawbz (s, a), where Q* is the optimal value in RL. Then construct æ' that behaves like xO everywhere except it always uses dj whenever the state s (ignoring history). The future trajectories from any visit s are stochastically identical under л and x', except that x' gets strictly higher expected return from every time is visited after histories that would have triggered 82 under n².
Thus, V= (5o) > V= (so) for some state, contradicting optimality of x². Therefore, this optimal policy must prescribe the same action distribution at state regardless of history. In other words, there exists an optimal Markovian policy. In the following, we will prove by contradiction that policies that exhibit reflective exploration cannot be Markovian.
Assume æ is a Markovian policy. Then there exists a mapping μ S + ((A) such that, for every history hi, T(- h4) ul- s(h,)). Define the process X, == s(he) and set μ.. By construction, (. h2) = v(- X,) for all
According to Definition 3.2, there is measurable such that X, ()((((())) and thus s(h,). ()(((s(()))). Let s, be reachable states and (ps) = cps'). Then s = (s(( = (xp(s') = s'
Therefore, there exist t to and histories h4s hez such that
<(s(he,)) <p(((hea)),
x(- he,) + π(- hv2))
Thus, we obtain s(hi,) s(hug) 8.. But then, using the Markov property of x, have T(. hr = x(- 8.) x[. he2), which contradicts o[- hs,) * π(. hea). Therefore, π is not Markovian.
A.2 PROOF OF THEOREM 4.2
Before the proof, we first provide several useful definitions and lemmas.
Definition A.1 (Epiitemic POMDP). We define the epistemic POMDP P = (2, P,r,
where the hidden state space as = S M, with state 2t (st, M)) action space A: obser- vation space O S with observation map O((s, M)) s; transition kernel P(( M') (s,,M). M).a;) a,) 1(M' M) PM (St41 | (s, reward ((sssM)).
r' TMr a); and initial state distribution p((so, M)) == p( M D) (s)(s)). where PM is the initial-state distribution in M. For policy म, let (T( denote its expected return in this POMDP.
Lemma A.2 (Fquivalence of Objectives). For any policy क, ı Bayes-optimal and only if optimal for the epistemic POMDP P, i.c..
JT(T) = JByyes(T).
Proof. By construction of the initial distribution.
(Su, M) p
M p(M D), Su PM.
Conditioned on M, the state transitions and rewards in P. coincide exactly with those of the MDP M under policy π,, and the observation o, S carries additional information beyond s,. Thus
JT(T)) = EM-p(M ( JM (T)]
JBayes (T))
which proves the claim. Similar results also presented in Singh al. (1994); Duff (2002).
Now we are ready to prove Theorem 4.2.
Proof of Theorem 4.2, By Lemma A.2, Bayes-optimal policies coincide with optimal policies for the epistemic POMDP P.
15

---

Published as a conference paper at ICLR 2026
It is a standard result in POMDP theory that there exists optimal policy which is function only of the belief state 3t, where
Bx = (2 h4 D). Thus there exists policy x and measurable mapping ji' such that
nt (at he) = _ (ac [B)).
In the epistemic POMDP, the hidden state is 2t = (st, M) and the observation or = 8t- Therefore the belief factors
(r M) 1 st} p(M he, D),
so Be uniquely determined by the pair (st,p(-Jit p(-pp D)). Since the offline posterior p( (MM)D D) fixed, the mapping (M) is in one-to-one correspondence with p (h, D), and hence with 8, Thus there exists measurable function n² such that for all hr,
p (or Bt) = p² (ac 8t, b(ha)).
Therefore, obtain
x >"(a; h1) = (a. BB) = 1² (ar st, b(hr),,
so x² is uncertainty-adan adaptive. Since n optimal for P. is Bayes-optimal for Jayes by
Lemma A.2, completing the proof.
A.3 PROOF OF THEOREM 4.3
Proof. Consider full binary decision structure of depth T", with leaf set L of size [C] 2 The states are the tree nodes, with the initial state fixed as the root node. The actions include the moves from the parent nodes to the child nodes as well as resetting action from the leaf node to the root node. The rewards are not known and differ in different MDP hypotheses. Specifically, the reward is defined T.M. (5) [(s s.). where is unique leaf node for M,, The prior of MDPs is p(M, = 1) where = 1, ......................... [c. The cumulative return is undiscounted with the minimum traverse steps as the horizon T. The episode terminates once the agent receives 1 reward.
For any Markovian policy n. define (s) = p(3t 2 0 &t = s т). We define as the probability that æ goes left at internal node By the Markov property, for any left and right children sL and
&n of node 8, it holds that ((r,. f(()),, and (**) = (1=)(11p))) Thus, f(xr)) +/ (88) = s())-
By simple induction
1. In particular, Eiec (() = 1. Since the total return under M, is V(r MM.) = p(T ends at leaf (,) = f(.),, the expected return for the optimal Markovian policy is
depth, it follows that every depth d, Σ =ddepa(())=a
V(T M₁) = 2T
Σ IEC
f(1
C
27
We construct the umcertainty-adappee policy as follows. Let C =
be the set of
models that are still consistent with the observed rewards in hT- When the agent visits a leaf s and observes reward r E {0, 1}. we update C + (M C (s) = r). For each i, there is exactly one leaf with T.M (s) 1. Hence, under any true MDP AM", after at most [C] visits to leaves we must have found the reward leaf, and obtain return of 1.
B EXPERIMENT DETAILS
B. EVALUATION RESULTS: ACCURACIES
In this section, we provide the evaluation accuracy results for Qwen2.5-Mann 1,5B, Qwen2.5-Math- 7B, and -aNSSee-RR--issiil--LB-ee
in Figure 9, 10, and 11, respectively. All models are trained using the same random seed and hyperparameters as described in Section 7.1. can be observed that BARL outperforms the two RL baselines in terms of both accuracy and convergence rate on most of the reported benchmarks.
16

---

Published as conference paper at ICLR 2026
88
GSMBK
74
MATH
CollegeMath
72
45.0
Accuracy
54
Accuracy
70
62.5
18
GRPO Progress
GRPO
GAPO
78
Progress
37.3
Progress
40
100
160
Iteration
Iteration AIME 2024
Iteration
OlympiadBench
AMC 2023
60-
Accuracy
Accuracy
32
50
an-
Progress ress
Progress
Progress
BARL
BARL
BARL
20
100
40
60
80
100
0
20
40
60
80
100
Iteration
Iteration
Iteration
Figure 9: Average evaluation accuracies over training iterations for Qwen2.55MathhI... models.
GSM8K
CollegeMath
Accuracy
30
Accuracy
78
Accuracy
x
GRPO
GRPO
GRPO
Progress
74-
Pregress
Progress
BARL
BARL
BARL
20
40
60
100
72
60
80
100
100
Itoratian OlympiadBench
Itoration
Iterrtion
AIME 2024
AMC 2023
42
30
65
25
Ancuracy
Accuracy
en
95
GR
GAPO
GRPO
Progress
Progress
so-...
Progress
30
BARL
10
BARL
BARL
Figure 10: Average evaluation accuracies over training iterations for Qwen2.5-Math-78 models.
GSMBK
CollegeMath
40
Accuracy
Accuracy.
72
03
198
86
Progress
Progress
BARL
BARL
BARL
64
10
20
30
50
0
10
20
30
40
50
60
10
20
40
50
60
Iteration
Iteration
Iteration
OlympiadBench
AIME 2024
AMC 2023
20.0
65
Accuracy
32.5
35.0
30.0
Recurao
17.5
12.5
Acturacy
60.
55
GRPO
27.5
Progress
10.0
Progress
Progress
7.5
BARL
BARL
40
Iteration
Iteration
Iteration
Figure 11: Average evaluation accuracies over training iterations for RI-Distill-Llam-B88 models.
17

---

Published as a conference paper at ICLR 2026
B.2 EVALUATION RESULTS: RESPONSE LENGTHS
In this section, we present the evolution of evaluation response lengths over training iterations for Qwen2.5-Math-
Qwen2.5-Math-77, and DeepSee--RI-DssilLLllaaa ures 12, 13, and 14, respectively. Across most benchmarks, response lengths tend to decrease as training progresses for all algorithms. The response length during training has very similar trend to that during evaluation. This trend arises because all three models exhibit reflective behaviors, such as self-evaluation and backtracking, that introduce redundant tokens and lengthen responses. As shown in Figure 7, these behaviors are likely superficial stylistic patterns with limited ef- fectiveness. An exception is AIME, where some models maintain consistently long responses due to the benchmark's s intrinsic requirement for extended reasoning, even under optimal non-reflective policies.
shown in Fig-
GSMBK
MATH
CollegeMath
Resporse Length
700-
GAPO
Respornee Length
GRPO
GRPO
Progress BARL
800
Progress
500
BARL
Response
2001
BARL
100
Roo
600-
100-
300
100
40
80
300
20
60
80
100
20
60
60
80
100
Iteration Blench
Iteration
Iberaation
AIME 2024
AMC 2023
550
750
Respoone Length
Resgonnee Length
Resporse Length
Progress
700
Progress BARL
Progress
500
BARL
850
BARL
475
850-
450
400-
425
80
100
1.00
20
60
80
100
Iteration
Iteration
Iteration
Figure 12: Average evaluation response lengths over training iterations for Owen2.55Math-1l
models.
GSMBK
MATH
CollegeMath
400
Respanse Lengtt
300
GAPO
Progress
Response Length
400
Pregress BARL
GRPO
Progress
GRPO
275-
BARL
260
Response
340
260
BARL
MD
220
225
300
200
300
280
10a
20
40
60
100
Iteration
Iteration
Iberattion AMC 2023
Olympiad Bench
AIME 2024
Res pesponce Length
549
320
GRPO
Progress
Res ponse Length
GRPO
Progress
Res ponson Length
500
Progress
GRPO
BARL
BARL
BARL
500
480
450-
460
400-
20
40
60
80
1.00
60
80
3.00
20
60
80
100
Iterration
Iteration
Iteration
Figure 13: Average evaluation response lengths over training iterations for Qwen2.5-Math-77 mod- els.
18

---

Published as a conference paper at ICLR 2026
GSMBK
MATH
CollegeMath
900
Resporse Length
GAPO
Desporse Length
GRPO Progress BARL
Response Length
Progress
Pregress
430
BARL
880
230
BARL
700
650
350
500
230
30
20
10
20
Iteration
OlympladBench
AIME
2023
1320
Resparse Longth
GRPO
Respanse Longth
GRPO
Resparse Length
1300
GRPO
1150
Progress
1300
Progress BARL
Progress
BARL
BARL
1280
1100
2000
1260
1950
1240
450
1220
10
20
30
40
50
60
20
-10
50
60
10
20
40
65
Itoration
Itoration
Iteration
Figure 14: Average evaluation response lengths over training iterations for RI-Distill-Llmm--B models.
Since the models used in the main experiments already exhibit lengthy CoTs with reflective pat- terns, we further implement BARL on the 3lama-3.2-3B-Insttue model, which displays fewer self- reflections. The results are presented in Figure 15. Initially, the response length decreases as the base model tends produce excessively long reasoning traces, often exceeding ten steps, which are pruned during early training. Subsequently, the response length increases, as result of plausible strategy stitching.
M MW Me!
460
Base
BARL
Training Accuracy
Respanse Length
440
GSM8K
69.4
73.8
0.40
#20
MATH
47.2
50.5
0.35
200-
CollegeMath
30.8
33.6
Olympiad
16.4
19.1
0.30
AIME 24
3.3
13.3
10
20
30
40
50
6D
70
360
10
20
10
40
50
60
AMC 23
27.5
35.0
Iteration
Iberatioo
Figure 15: Results of BARL fine-tuned on Llama-3.2-3B-Imas I-strucns (Left) Training accuracy and (Middle) response length. (Right) Evaluation results.
B.3 TOKEN EFFICIENCY WITHOUT GREEDY DECODING OUTPUTS
In Figure 16, we present the pass@k k accuracies from ablation similar to Section 7.3, except that greedy decoding outputs are excluded when computing token counts and accuracies. We observe that the base and GRPO models are less robust under sampling temperature of 1.0, resulting in significantly lower pass accuracies compared to greedy decoding. This degradation may stem from the fragility of their CoT's, which often exhibit stylistic but unproductive self-reflection and backtracking behaviors.
GSMBK
MATH
CollegeMath
OlympladBench
20-
8
3
Progresa
Progress
Progresa
Prggess
BARL
BARL
BARL
BARL
Tohal N. Tolenns
1968
2084
Total Numberx
Total Numbers
Tanae Tokern
Y003
Figure 16: Ablation on token efficiency and pass @k accuracies with sampling temperature= 1. GRPO and the base models are less robust to temperatures.
19

---

Published as a conference paper at ICLR 2026
B.4 SOME UNSUCCESSFUL ATTEMPTS
As a straightforward implementation of the Bayes-Adaptive RL policy gradient in (5.1), we ex- plored using value ensembles estimate the posterior-weighted value ((Mx((M) M M (st; ar]]- Specifically, we trained an ensemble of state-action value functions to capture epistemic uncertainty. We experimented with two approaches constructing the ensemble: (1) fine-tuning multiple lin- ear value heads on disjoint data subsets, each paired with
(CoT) trajectories and outcome rewards; and (2) applying Bayesian LoRA. However, both methods failed effectively capture epistemic uncertainty, likely because they fine-tune only small subset of LLM parameters, which is insufficient to fully represent the uncertainty. While maintaining independent value models may better capture this uncertainty, doing so incurs substantial computational cost. We leave the development of more efficient implementations to future work.
C STATEMENT ON THE USE OF LARGE LANGUAGE MODELS
We use LLMs only to polish the paper, such as improving clarity and grammar, without altering its substance original ideas.
20


Reviews:
[{"review_id": "2UbpJpfZuv", "reviewer": "Reviewer_LqXu", "summary": "+ Summary & Contributions\n\t- The authors focus on the problem of explicitly eliciting \"reflective reasoning/behaviors\" from LLMs during the course of RL fine-tuning for improved reasoning capabilities. Such reflective reasoning/behavior is exemplified through the use of backtracking or error correction during chain-of-thought reasoning.\n\t- The authors maintain that the \"conventional, Markovian\" RL problem formulation is ill suited for consistently encouraging such desired reflective behaviors. \n\t- The authors turn to Bayesian RL as a problem formulation whose core policy optimization objective necessarily results in reflective reasoning and behaviors. Leveraging this formulation yields a novel RL fine-tuning algorithm (BARL) geared towards enhanced LLM reasoning capabilities on mathematics question-answering tasks (GSM8K, MATH, CollegeMath, OlympiadBench).\n\t- Experiments across a range of mathematics Q&A benchmarks and model types demonstrates improved performance over standard GRPO. Additional empirical results assess the volume of tokens needed to arrive at LLM responses and finds that BARL is able to obtain better accuracies using fewer tokens.", "questions": "Please see above.", "limitations": "", "rating": null, "confidence": 5, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "+ Quality\n\t- Strengths\n\t\t- The authors display a nice insight in trying to port over ideas from Bayesian RL into modern LLM fine-tuning.\n\t- Weaknesses\n\t\t* Major\n\t\t\t- In RL (or what the authors seem keen to refer to as \"conventional/Markovian RL\"), there is no such distinction between training time and testing time as there is in standard supervised learning. There is just one single, periodic stream of an agent interacting with an environment episode after episode. Yet, throughout the paper, the authors operate under a premise that such a train-test split exists in RL. Two places where such a split occurs in RL are multi-task RL [1] and meta RL [2]. The former is where an agent interacts with a family of MDPs indexed by an observable, episodic context that helps an agent distinguish MDPs while also encoding structural similarities that might aid in generalization and transfer to unseen MDPs. The latter is where an agent begins with a distribution over MDPs (meta-training) with the goal of synthesizing a policy capable of learning behaviors quickly in a downstream MDP distribution (meta-testing). Based on the rest of the paper, the authors seemed to be confused about these well-established problem settings within the confines of RL. Rather than standard single-task RL, the authors seem to be interested in meta RL, where the resulting LLM policy will approach novel questions by exploring and within relatively few interactions (CoT reasoning steps) explore and expose enough information to subsequent exploit and solve the task (answer the question correctly). Another possible alternative for what the authors might want is Bayesian multi-task RL (that is, solving the BAMDP induced by a contextual MDP). In any case, the problem the authors seem interested in solving doesn't seem like it neatly fits into the Bayesian RL formulation. That said, the authors lack of a well-defined MDP, prior distribution over MDPs, and resulting induced BAMDP formulation makes it difficult to tell. Exploration and generalization are distinct, orthogonal axes of data efficiency in RL; while Bayesian RL does yield the optimal solution to the exploration-exploitation trade-off, it does not do so \"to improve generalizability\" (L125-126), which is a separate concern entirely.\n\t\t\t- While the goal of reflective reasoning/behavior/exploration is ambiguous throughout this paper (see Clarity comments below), it's worth noting that just because a LLM emits text indicating that it is reconsidering something, that doesn't necessarily mean that it \"disregards the previous one or more steps\" (L175). How do the authors know that this is in fact the case? Those previously generated tokens are all still in the context of previously generated tokens and may in fact still influence subsequently generated tokens. This also connects to a later point (L182-186) where the authors fixate on the Markov state of a MDP being insufficient for reflective reasoning without justifying why a MDP with states defined as histories is insufficient to resolve their concerns (the footnote in L215 doesn't make sense, perhaps stemming from the lack of a formal definition for reflective reasoning).\n\t\t\t- The authors fail to provide a formal proof of Theorem 4.1. This is particularly unfortunate since I had hoped a theoretical result would have forced the authors to become concrete and specific about how they formalize reflective reasoning (in order to make a formal statement about \"non-reflective policies\" in L190). The lack of a proof would call into question a central claim of this paper that standard RL is inadequate for reflectve reasoning, which itself necessitates the use of Bayesian RL. Perhaps the authors believe the exposition preceding Theorem 4.1 constitutes some kind of proof sketch. However, they seem to have forgotten the basic fact that a MDP may admit multiple optimal policies. With bounded rewards under a finite horizon or discounted, finite rewards in an infinite horizon, results from dynamic programming theory tell us that there exists a (or, at least one) deterministic optimal policy that is greedy with respect to the optimal action-value function. There may still however additionally be multiple stochastic optimal policies that also achieve optimal value (recall that the mapping from policy to value function is a many-to-one mapping). In summary, it is unclear why standard \"Markovian\" RL with respect to a history-based state space should be considered non-reflective nor is it clear why \"Markovian\" RL only admits deterministic policies -- both of these facts would call Theorem 4.1 into question and render the text box comparing RL to Bayesian RL (L227-232) incorrect.\n\t\t\t- The authors claim that the optimal policy of the BAMDP (that is, the Bayes-optimal policy with respect to the original prior distribution over MDPs) will \"naturally induce exploratory behaviors with reflections\" (L223). Certainly, the first part of the claim is true as the Bayes-optimal policy yields the optimal solution to the exploration-exploitation trade-off. Why is the second part (the \"with reflections\") part true? Why is it that the Bayes-optimal policy of a MDP must use reflections to optimally address exploration? The authors proceed to describe \"reflective actions\" as those which may be sub-optimal but yield information to reduce epistemic uncertainty in the MDP (L224-226); however, this is precisely the definition of any exploratory action taken by the Bayes-optimal policy. Is \"reflective\" just the authors' synonym for \"explorative\" or are reflective actions/steps a subset of all exploratory actions? If it's the latter, how are those reflective actions concretely defined?\n\t\t\t- The authors' proof of Theorem 4.2 aims to be constructive, hoping to show that there exists a MDP for which the \"test-time\" return of \"a Bayes-Adapative\" policy is exponentially larger in $T*$ than that of the optimal policy from standard RL. As discussed at other points in this review, the modifier \"test-time\" is vacuous here. I'm left to assume \"a Bayes-Adaptive\" policy refers to a policy of the associated BAMDP. Firstly, why is $T*$ the appropriate parameter for this claim to depend on? Mechanistically, the authors' subsequent didactic example shows that this simply needs to be the appropriate number of steps for a policy to be capable of iterating through all the possible incorrect answers before necessarily landing on the correct one (L311). Why is this reasonable? Also, surely a \"Markovian\" policy for a MDP where states are defined by histories (something the authors eventually do after Equation 5.1), would be capable of performing the exact same behavior of iterating through all possibilities exhaustively until the correct leaf node/three token repetition is found. This would seemingly invalidate the argument presented for \"any Markovian policy\" in the proof of Theorem 4.2 (Appendix A). Putting that aside, the claim itself is rather strange. It is well known that the Bayes-optimal policy when evaluated in the original MDP will, by definition, achieve performance that is less than that of the optimal policy [8]. \n\n\t\t* Minor\n\t\t\t- In a paper so focused on RL, it is strange the authors don't see (or at least fail to acknowledge) the distinction between the action-value function and the advantage function (L162), which are of course two separate mathematical objects. \n\t\t\t- What is the point of considering \"the non-standard undiscounted, infinite-horizon MDP\" (L197)? Without discounting and non-negative rewards, there are likely numerous policies which all achieve the optimal reward (of infinity?) and become indistinguishable from one another without additional specification.\n\t\t\t- Notice that Bayesian RL does not automatically admit partial observability (L211). The corresponding BAMDP can be defined via a so-called hyperstate space [3] that includes the original MDP state as well as the current posterior distribution over MDPs, both of which are fully observed.\n\t\t\t- The authors claim that they may write the likelihood of a reward according to (what seems to be) a Laplace distribution. Is this an assumption? Or is this some fact? For the case of question-answering with binary rewards indicating correctness, it actually seems strange to not simply treat rewards as Bernoulli random variables whose parameters have epistemic uncertainty represented by Beta distributions (as is standard [3,4]).\n+ Clarity\n\t- Strengths\n\t\t- Aside from the incorrect jargon/modifiers introduced by the authors to describe RL, the paper is reasonably written and structured.\n\t- Weaknesses\n\t\t* Major\n\t\t\t- Throughout the paper, the authors make heavy use (42 instances) of the word \"reflective\" as an adjective and modifier to standard terminology used in RL and/or LLMs. There are reflective behaviors/policies, reasoning, exploration, signals. The definitions for some of these are dependent on the definitions of others such that if there was a clear, concrete definition for reflective reasoning and exploration, the others would likely follow. Unfortunately, the authors fail to provide such an explicit definition, instead only gesturing at exemplars for what they consider reflective reasoning (L171-177). Strangely enough, one of these examples is backtracking, a property of a search/planning algorithm rather than a RL algorithm. This paper could be tremendously clearer if the authors could formalize exactly what property/properties reflective reasoning/behavior exhibits so that readers can have transparency and insight into how standard RL might inconsistently deliver such behavior and why Bayesian RL might be a promising tool for explicitly encouraging it. \n\t\t* Minor\n\t\t\t- The authors question whether desirable reflective behaviors will emerge with \"conventional\" RL training (L38-39), which seemingly contradicts the preceding sentence indicating that such behaviors do in fact emerge with standard RL.\n\t\t\t- The authors mention \"prevalent views\" (L40) on how test-time reflections constitute useful exploratory steps yet fail to make a single supporting citation. Certainly, there is now near-ubiquitous understanding of how chain-of-thought reasoning helps (and citable papers to support the claim) but specific examples of work advocating for the kinds of reflective behaviors the authors focus on in this paper would be helpful to support the proposed approach.\n\t\t\t- There is no such thing as \"epistemic explorations\" (L53), but presumably the authors mean exploration to reduce epistemic uncertainty in the underlying MDP.\n\t\t\t- Rather than taking up space with summarizing text boxes (L78-90, L227-232, L468-472) better fit for a poster about the paper, I would encourage the authors to reinvest that space in clearer exposition of the technical content within the paper.\n\t\t\t- Per the comment above, the claim that \"conventional RL explores only during training\" (L119) is vacuous when RL has no distinction between training and testing.\n\t\t\t- The language used throughout the paper in regards to uncertainty and Bayesian RL is riddled with odd, incorrect/vague statements that wear down an interested reader of this paper. What does it mean that \"the environment is predefined with certainty\" (L163)? Certainly, it does not mean that the environment is fully known to the agent, since that would imply a planning problem rather than a RL problem.\n\t\t\n\n+ Originality\n\t- Strengths\n\t\t- To the best of my knowledge, attempting to use Bayesian RL in the proposed manner to elicit improved reasoning capabilities is a novel idea.\n\t- Weaknesses\n\t\t* Major\n\t\t\t- The authors identify two meta RL approaches for encouraging better reasoning capabilities (L110-115), but their explanations for how their method is distinct and an improvement over these methods is entirely unclear. What does it mean for reflective reasoning to be grounded \"in environment rewards, rather than relying solely on the interal CoT states\"? If additional data on \"golden strategies\" is available, why would this be sub-optimal compared to additional exploration for discovering such strategies via BARL? \n\t\t\t- The authors ultimately propose a policy-gradient method for addressing their proposed Bayesian RL problem but don't actually connect it with existing work on Bayesian actor-critic methods [7]. What is the connection? Is the authors' approach well aligned with existing work on policy-gradient methods in Bayesian RL? How is it different? Are there sensible Bayesian actor-critic baselines that BARL can and should be compared against?\n\t\t* Minor\n\t\t\t- Some of the references must have incorrect Bibtex entries and are missing the year and publication information (Arumugam & Singh, NIPS 2022; Lidayan et al., ICLR 2025).\n\t\t\t- The authors are not the first to entertain coupling ideas from Bayesian RL with LLMs and those existing connections ought to be acknowledged [5,6].\n\n+ Significance\n\t- Strengths\n\t\t- This paper would likely inspire subsequent work to investigate more principled, rigorous methods for combining Bayesian RL with LLMs.\n\t- Weaknesses\n\t\t* Major\n\t\t\t- A BAMDP is not an object that can simply be instantiated immediately, like a MDP. In particular, it is induced from the combination of a MDP as well as a prior distribution over MDPs [3]. While the authors do specify such a prior in their experiments, it's unclear where this prior is meant to come from generally. Also, the experiments only ever use simple, uninformative priors with a very small support; this suggests a tremendous amount of work falls upon agent designers to come up with such priors to apply BARL, impacting scalability and the applicability of the proposed approach.\n\t\t\t- The authors only report results based on three random seeds. While I appreciate the high computational demands of LLM experiments, three seeds is far too few to reach meaningful, statistically-significant conclusions [9]. Ignoring the Average column of Table 1, there are 18 rounds of evaluation done (spanning model type and dataset) of which 8 of the reported entries where the accuracy of BARL is boldfaced is not statistically significant (overlapping standard error with another baseline method). Also, I'm not sure I understand what reporting the \"best performance on all benchmarks\" for each algorithm means but it sounds highly suspect as if the authors are being slightly disingenuous in their presentation of the results.\n\t\t\t- The authors' empirical evaluation has done the bare minimum by comparing against standard GRPO. It does not, however, entertain other approaches to achieving enhanced reasoning capabilities that sit orthogonal to the authors' proposed Bayesian RL approach.\n\t\t* Minor\n\t\t\t- N/A\n\t\t\t\n\t\t\n+ Final Remarks\n\t- I have identified severe issues with this paper on the axes of quality, clarity, and significance. Considerable revisions of the problem formulation, proposed approach, technical results, and empirical results would be needed before this paper is ready for publication.\n\n\n+ References\n\t1.  Hallak, Assaf, Dotan Di Castro, and Shie Mannor. \"Contextual markov decision processes.\" arXiv preprint arXiv:1502.02259 (2015).\n\t2. Finn, Chelsea, Pieter Abbeel, and Sergey Levine. \"Model-agnostic meta-learning for fast adaptation of deep networks.\" In International conference on machine learning, pp. 1126-1135. PMLR, 2017.\n\t3. Duff, Michael O'Gordon. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002.\n\t4. Osband, Ian, Daniel Russo, and Benjamin Van Roy. \"(More) efficient reinforcement learning via posterior sampling.\" Advances in Neural Information Processing Systems 26 (2013).\n\t5. Dwaracherla, Vikranth, Seyed Mohammad Asghari, Botao Hao, and Benjamin Van Roy. \"Efficient Exploration for LLMs.\" In International Conference on Machine Learning, pp. 12215-12227. PMLR, 2024.\n\t6. Arumugam, Dilip, and Thomas L. Griffiths. \"Toward Efficient Exploration by Large Language Model Agents.\" In The Exploration in AI Today Workshop at ICML 2025.\n\t7. Ghavamzadeh, Mohammad, Yaakov Engel, and Michal Valko. \"Bayesian policy gradient and actor-critic algorithms.\" Journal of Machine Learning Research 17, no. 66 (2016): 1-53.\n\t8. Kolter, J. Zico, and Andrew Y. Ng. \"Near-Bayesian exploration in polynomial time.\" In Proceedings of the 26th annual international conference on machine learning, pp. 513-520. 2009.\n\t9. Henderson, Peter, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. \"Deep reinforcement learning that matters.\" In Proceedings of the AAAI conference on artificial intelligence, vol. 32, no. 1. 2018.", "weaknesses": "Please see above.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rzV0Y7A6x9", "reviewer": "Reviewer_S3kA", "summary": "This paper introduces BARL, a Bayes-Adaptive RL framework that equips LLMs with test-time reflective exploration. By maintaining and updating beliefs over task hypotheses, BARL guides the model to backtrack and switch strategies when observations contradict expectations. On both synthetic and math reasoning tasks, BARL outperforms standard Markovian RL baselines in accuracy and token efficiency, demonstrating that principled exploration—not mere reflection frequency—drives better generalization.", "questions": "1. How does the magnitude of the penalty term β affect the predicted and observed rewards? Can relevant experiments be conducted to observe this?\n\n2. This work demonstrates strong performance on mathematical problems, but does it remain effective on other general tasks where the structure is less clear?\n\n3. The exponential gain in Theorem 4.2 relies on a constructed binary tree and a uniform prior—does it still hold in general cases?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Clearly articulates the limitation of standard Markovian RL—its inability to support test-time reflective exploration—and provides theoretical justification for why this hampers generalization.\n\n2. The theoretical framework is very solid, which Introduces Bayes-Adaptive MDPs to model LLM reasoning, formalizing test-time generalization as maximizing expected return under a posterior over candidate tasks, grounding exploration in principled Bayesian principles.\n\n3. Authors present novel BARL, which maintains and updates beliefs over MDP hypotheses; mismatches between predicted and observed rewards automatically trigger strategy switching and backtracking, enabling reflective behavior without heuristic rules.\n\n4. Comprehensive empirical validation demonstrates consistent gains over strong Markovian RL baselines on both synthetic and challenging math benchmarks, achieving higher accuracy while using up to 2× fewer tokens, evidencing superior efficiency and generalization.\n\n5. The insightful ablation analysis shows that effective exploration, not the sheer frequency of self-reflection, drives performance, offering actionable guidance for future research into test-time scaling of reasoning models.", "weaknesses": "1. Computational Overhead: Despite KV-cache reuse, the per-step computation still scales linearly with the number of sampled hypotheses (|M|) and grows rapidly when the model size or context length increases; no GPU-hours or throughput curves are reported to quantify this burden.\n\n2. Keyword-based Reflection Detection: Relying on fixed trigger words to flag “self-reflection” is unreliable—it captures only explicit surface signals and cannot verify whether the model actually revises its reasoning strategy, making the behavioral analysis less rigorous.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JHZqBWYoI4", "reviewer": "Reviewer_FoH3", "summary": "This paper introduces a Bayes-Adaptive RL objective for finetuning LLMs. This objective incentives the policy (model) to maximize the expected reward on the given task but also reason about the underlying MDP (which is assumed to be a random variable). Experimental results show improvements over GRPO (traditional Markovian-based objective) on popular benchmarks like AIME and the underlying objective leads to policies that exhibit significant improvements in token efficiency.", "questions": "Please see weaknesses^", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Motivations for paper is clear and paper is well-written\n- Formulation is easy-to-follow and small-scale experiments are helpful in understanding the effectiveness of the approach\n- Strong improvements in token efficiency and slight improvements over GRPO in math-reasoning tasks.", "weaknesses": "- Ablation of progress reward. The provided formulation assumes reward is based on some gold action (e.g. answer token y) and this is used to introduce a progress reward incentivizing the model to think. However, the effect of this reward does not seem to ablated. Additionally, there are domains where reward is not a function of a gold action (e.g. for agentic coding domains, reward may be computed by executing sampled code against some test cases). Does this limit the generality of this approach?\n- Missing implementation details. What prompts were used to sample from the posterior of MDPs?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EpfZD1wTFL", "reviewer": "Reviewer_QdQn", "summary": "This paper addresses the limitations of standard Markovian RL in explaining or guaranteeing the emergence of reflective reasoning (like backtracking and error correction) observed in Large Language Models (LLMs) trained for complex tasks. It proposes recasting the problem within the Bayes-Adaptive RL framework, which explicitly optimizes for test-time performance under uncertainty about the underlying MDP. This Bayesian approach naturally incentivizes exploration to gather information and reduce uncertainty, leading to adaptive policies that update beliefs based on outcomes. The authors introduce BARL, an algorithm where the LLM maintains a posterior over MDP hypotheses, weighting actions by belief and penalizing discrepancies between predicted and observed rewards to guide strategy switching and reflective exploration. Empirical results on synthetic and math reasoning tasks show BARL outperforms Markovian RL baselines in accuracy and token efficiency, demonstrating the benefits of principled, belief-driven exploration over fixed, deterministic policies.", "questions": "- Could the authors provide further intuition on why the Bayes-Adaptive framework specifically leads to better token efficiency? \n- The progress reward  is defined based on the policy $\\pi_{\\theta}$ itself. However, in the policy gradient derivations (Eq 3.2 for Markovian RL and implicitly in Eq 5.1 for BARL), the reward $r(s_t, a_t)$ appears to be treated as if it were an external reward independent of the policy parameters $\\theta$. Could the authors comment on whether this simplification introduces bias into the gradient estimates, and if so, how it might affect the training dynamics or the final policy?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a compelling Bayes-Adaptive RL framework that extends standard Markovian RL. This Bayesian approach provides a principled way to encourage exploration and generalization for LLM reasoning, moving beyond policies that might simply memorize training solutions.\n- The core concepts are well-supported through both theoretical justification and empirical validation. The inclusion of a didactic synthetic example significantly aids in illustrating the core mechanism and benefits of BARL.\n- Experimental results indicate that the BARL algorithm achieves superior token efficiency compared to baselines like GRPO and a progress-reward-based method, suggesting more effective exploration and reasoning per token.", "weaknesses": "- While the BARL framework is theoretically well-motivated, the empirical performance improvements shown in the main results appear somewhat incremental compared to the baselines across all benchmarks.\n- While the paper claims the Bayesian RL framework improves generalization, the empirical results demonstrate only incremental performance gains over baselines. Consequently, the primary source of the observed benefits, particularly token efficiency, remains ambiguous.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)