Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoning

This paper explores how to enhance Large Language Model (LLM) reasoning by moving beyond conventional reinforcement learning (RL) methods. Standard RL confines exploration to the training phase and relies solely on the current state, failing to fully utilize reflective reasoning at test time. The authors propose Bayes-Adaptive RL (BARL), a framework that explicitly optimizes for test-time generalization by maintaining uncertainty over potential solutions and updating beliefs based on observed outcomes, leading to more efficient and effective exploration. Experimental results demonstrate that BARL outperforms traditional RL in mathematical reasoning tasks, achieving higher accuracy with fewer tokens by enabling flexible strategy switching and hypothesis elimination.