title: Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM
    Reasoning
summary: 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.
paper_authors._id: 6836a46b2a5e3993a42e3e3f
paper_authors.name: Shenao Zhang
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-05-28T12:55:47.352Z
paper_authors._id: 661213f894e0b3bff3e80c69
paper_authors.avatarUrl: /avatars/d8febbb081825bf91e487aa8bad3a391.svg
paper_authors.fullname: Shenao Zhang
paper_authors.type: user
paper_authors.user: ZhangShenao
paper_authors._id: 6836a46b2a5e3993a42e3e40
paper_authors.name: Yaqing Wang
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-05-28T12:55:53.241Z
paper_authors._id: 62cb0f38b189b6164d2a7900
paper_authors.avatarUrl: /avatars/8bdf9705822fba3518e25db45d894535.svg
paper_authors.fullname: Yaqing Wang
paper_authors.type: user
paper_authors.user: yaqingwang90
paper_authors._id: 6836a46b2a5e3993a42e3e41
paper_authors.name: Yinxiao Liu
paper_authors._id: 6836a46b2a5e3993a42e3e42
paper_authors.name: Tianqi Liu
paper_authors._id: 6836a46b2a5e3993a42e3e43
paper_authors.name: Peter Grabowski
paper_authors._id: 6836a46b2a5e3993a42e3e44
paper_authors.name: Eugene Ie
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-05-28T12:56:22.038Z
paper_authors._id: 65a5d95d0797583a68438f49
paper_authors.avatarUrl: /avatars/266f78b2678fcddac51c75f6fe33f118.svg
paper_authors.fullname: Eugene Ie
paper_authors.type: user
paper_authors.user: eugeneie
paper_authors._id: 6836a46b2a5e3993a42e3e45
paper_authors.name: Zhaoran Wang
paper_authors._id: 6836a46b2a5e3993a42e3e46
paper_authors.name: Yunxuan Li
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-05-28T12:56:39.817Z
paper_authors._id: 63531848fc9b7ad0a53fa564
paper_authors.avatarUrl: /avatars/d8df470349aa976741604921cb408440.svg
paper_authors.fullname: Yunxuan Li
paper_authors.type: user
paper_authors.user: eric008
paper_title: Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM
    Reasoning
paper_summary: 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.
paper_ai_summary: 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.
paper_ai_keywords: 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