Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning
Shenao Zhang, Yaqing Wang, Yinxiao Liu, Tianqi Liu, Peter Grabowski, Eugene Ie, Zhaoran Wang, Yunxuan Li · 2025
Read Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning by Shenao Zhang, Yaqing Wang, Yinxiao Liu, Tianqi Liu, Peter Grabowski, Eugene Ie, Zhaoran Wang, Yunxuan Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20561.txt.
Introduction
Shenao Zhang and co-authors reframe how language models explore while reasoning, arguing that standard training cannot reward true reflection, in a paper from 2025. A normal policy sees only the current state, so revisiting a state with fresh context earns nothing. Their fix treats training as uncertainty over possible task worlds.
Under that Bayesian view, good play includes gathering information and rethinking, since beliefs update as outcomes arrive. Their algorithm teaches the model to stitch and switch strategies based on what it observes. On synthetic and math reasoning tests, it beat standard reinforcement learning in both accuracy and token use. Code is released in public.
Catalog record
| CREATOR | Shenao Zhang, Yaqing Wang, Yinxiao Liu, Tianqi Liu, Peter Grabowski, Eugene Ie, Zhaoran Wang, Yunxuan Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-20561
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning Shenao Zhang, Yaqing Wang, Yinxiao Liu, Tianqi Liu, Peter Grabowski, Eugene Ie, Zhaoran Wang, Yunxuan Li Abstract Large Language Models (LLMs) trained via Reinforcement Learning (RL) have exhibited strong reasoning capabilities and emergent reflective behaviors, such as backtracking and error correction. However, conventional Markovian RL confines exploration to the training phase to learn an optimal deterministic policy and depends on the history contexts only through the current state. Therefore, it remains unclear whether reflective reasoning will emerge during Markovian RL training, or why they are beneficial at test time. To remedy this, we recast reflective exploration within the Bayes-Adaptive RL framework, which explicitly optimizes the expected return under a posterior distribution over Markov decision processes. This Bayesian formulation inherently incentivizes both reward-maximizing exploitation and information-gathering exploration via belief updates. 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 standard Markovian RL approaches at test time, achieving superior token efficiency with improved exploration effectiveness. Our code is available at https://github.com/shenao-zhang/BARL . 1 Introduction Large Language Models (LLMs) have demonstrated impressive reasoning abilities, such as in solving complex math problems. A key factor driving this progress is the use of Chain-of-Thought (CoT) reasoning ( wei2022chain ) , 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 ( jaech2024openai ; guo2025deepseek ; yu2025dapo ; wei2025swe ) . Notably, RL-trained models have exhibited emergent behaviors such as generating long CoTs and engaging in self-reflection, a process of backtracking to previous states to correct earlier mistakes, also known as the “Aha moment” ( guo2025deepseek ; zeng2025simplerl ) . However, despite these compelling phenomena, it remains unclear why and under what conditions reflective reasoning is beneficial at test time, or whether such behaviors will emerge through conventional RL training. Prevalent views attempt to explain the usefulness of test-time reflections as exploratory steps that provide additional contexts for more optimal decision-making. Yet in Markovian RL, the exploration–exploitation trade-off is resolved entirely during training: the agent interleaves exploration and exploitation to learn a training-time optimal deterministic policy, but switches to pure exploitation at test time. As a result, conventional RL allows a Markovian policy to be optimal by simply memorizing, i.e., deterministically outputting, training solutions once they are encountered by stochastic exploratory policies through repeated trial-and-error. Moreover, the Markov assumption restricts the policy to condition decisions solely on the current state rather than on contextual information gathered through exploration, offering no incentives to adaptively explore with reflections. In summary, under conventional Markovian RL, there is no guarantee that reflective explorations will emerge during training, nor does it explain why such explorations might be advantageous at test time. To address this gap, we propose grounding reflective reasoning with Bayes-Adaptive RL, which explicitly optimizes for test-time generalization by maximizing the expected return under a posterior distribution over Markov Decision Processes (MDPs). The objective incentivizes both reward-seeking actions and epistemic explorations that gather information to reduce the MDP’s uncertainty, such as the uncertainty regarding the progress made by different actions. This enables the model to adapt on-the-fly at test time by updating its beliefs and switching strategies based on observed outcomes, naturally giving rise to reflective exploration behaviors. We prove that the expected return of an adaptive policy can be exponentially higher than the optimal Markovian policy at test time. Building upon this formulation, we introduce a novel algorithm, Bayes-Adaptive RL for LLM Reasoning (BARL). For each prompt, BARL performs online rollouts to generate a set of candidate answers, each associated with an MDP hypothesis. The state-action value is then computed by weighting 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 provides a principled mechanism for integrating and revising plausible strategies, analogous to linearizing best-of-N reasoning, but with explicit step-level 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 test-time generalization in LLM reasoning. The agent receives a reward only when it repeats a prompt token exactly three times, but the training and testing prompt tokens differ. Standard Markovian RL memorizes the training solutions and fails to generalize. 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-7B, and R1-Distill-Llama-8B. Across these models, BARL consistently outperforms Markovian RL algorithms, such as GRPO and a strong progress-reward baseline, on multiple benchmarks. BARL achieves significantly greater token efficiency, requiring up to 39% fewer average tokens than the progress baseline, 50% fewer than GRPO, and over 90% fewer than the Qwen2.5-Math-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 of this paper as follows: Key Takeaways: Why, How, and When Should LLMs Reason Reflectively • Why: Markovian RL neither ensures the emergence of reflective exploration nor explains its benefits at test time since (1) exploration is confined only to the training phase to learn, and purely exploit at test time, an optimal deterministic policy that can merely memorize training solutions, and (2) the state-conditional policy lacks incentives to collect additional contexts and backtrack. In contrast, Bayes-Adaptive RL , by optimizing test-time generalizability, encourages explorations to gather contextual information that reduces the MDP uncertainty. • How: BARL provides a principled way to stitch plausible strategies by maintaining a posterior over MDP hypotheses, each associated with a sampled candidate answer. Reflective exploration emerges naturally through hypothesis elimination, enabling on-the-fly adaptation. • When: LLMs should self-reflect when discrepancies arise between their internal beliefs and cumulative reward feedback—signaling strategy switching by downweighting hypotheses that have high belief probabilities but are unlikely to be optimal given previous observations. 2 Related Work LLM Reasoning. As an emerging capability of model scale, LLMs can generate intermediate CoTs to solve complex reasoning tasks ( wei2022chain ; kojima2022large ) and scale test-time performance by allocating more thinking tokens ( snell2024scaling ; brown2024large ) . Early efforts enhanced LLM reasoning via supervised fine-tuning on human-annotated data ( cobbe2021training ; yue2023mammoth ; yu2023metamath ) or linearized search traces ( lehnert2024beyond ; gandhi2024stream ) . However, due to the distribution shift between LLM responses and curated data, LLM-generated data has proven effective through rejection sampling ( dong2023raft ; yuan2023scaling ) by filtering out low-quality rationales ( zelikman2022star ; zelikman2024quiet ) or with EM iterations ( singh2023beyond ; zhong2025brite ) . Recently, RL has gained increasing interest for improving reasoning ( aksitov2023rest ; havrilla2024teaching ; wang2024offline ; shao2024deepseekmath ) . Process rewards ( uesato2022solving ; lightman2023let ) with Monte Carlo unrolls ( kazemnejad2024vineppo ; wang2023math ; wang2024multi ; luo2024improve ) offer finer-grained feedback but are computationally expensive. Outcome-reward RL