Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM
  Reasoning
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.
6836a46b2a5e3993a42e3e3f
Shenao Zhang
admin_assigned
2025-05-28T12:55:47.352Z
661213f894e0b3bff3e80c69
/avatars/d8febbb081825bf91e487aa8bad3a391.svg
Shenao Zhang
user
ZhangShenao
6836a46b2a5e3993a42e3e40
Yaqing Wang
admin_assigned
2025-05-28T12:55:53.241Z
62cb0f38b189b6164d2a7900
/avatars/8bdf9705822fba3518e25db45d894535.svg
Yaqing Wang
user
yaqingwang90
6836a46b2a5e3993a42e3e41
Yinxiao Liu
6836a46b2a5e3993a42e3e42
Tianqi Liu
6836a46b2a5e3993a42e3e43
Peter Grabowski
6836a46b2a5e3993a42e3e44
Eugene Ie
admin_assigned
2025-05-28T12:56:22.038Z
65a5d95d0797583a68438f49
/avatars/266f78b2678fcddac51c75f6fe33f118.svg
Eugene Ie
user
eugeneie
6836a46b2a5e3993a42e3e45
Zhaoran Wang
6836a46b2a5e3993a42e3e46
Yunxuan Li
admin_assigned
2025-05-28T12:56:39.817Z
63531848fc9b7ad0a53fa564
/avatars/d8df470349aa976741604921cb408440.svg
Yunxuan Li
user
eric008
Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM
  Reasoning
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.
BARL, a Bayes-Adaptive RL framework, enhances LLM performance by integrating reflective reasoning and efficient exploration, leading to better token efficiency and effectiveness in test scenarios.
Reinforcement Learning (RL) backtracking error correction Markovian RL Bayes-Adaptive RL expected return posterior distribution Markov decision processes belief updates BARL token efficiency exploration effectiveness