# Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration arXiv: https://arxiv.org/abs/2503.07453 ยท HTML: https://mlsanity.com/paper/2503.07453/ ## Key facts - Cited by 36 papers in the map (data through 14 Oct 2026). - Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. - First posted on arXiv 10 Mar 2025. ## Placed in - LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/) ## Built on by (most cited first, 30 of 36) - [Cultivating Pluralism In Algorithmic Monoculture: The Community Alignment Dataset](https://mlsanity.com/paper/2507.09650/) (2025) - [Representation-Based Exploration for Language Models: From Test-Time to Post-Training](https://mlsanity.com/paper/2510.11686/) (2025) - [Understanding the Performance Gap in Preference Learning: A Dichotomy of RLHF and DPO](https://mlsanity.com/paper/2505.19770/) (2025) - [On the Power of (Approximate) Reward Models for Inference-Time Scaling](https://mlsanity.com/paper/2602.01381/) (2026) - [On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference](https://mlsanity.com/paper/2512.04558/) (2025) - [Coverage Improvement and Fast Convergence of On-policy Preference Learning](https://mlsanity.com/paper/2601.08421/) (2026) - [Analytical Survey of Learning with Low-Resource Data: From Analysis to Investigation](https://mlsanity.com/paper/2510.08962/) (2025) - [Near-Optimal Regret for KL-Regularized Multi-Armed Bandits](https://mlsanity.com/paper/2603.02155/) (2026) - [On the optimization dynamics of RLVR: Gradient gap and step size thresholds](https://mlsanity.com/paper/2510.08539/) (2025) - [Offline and Online KL-Regularized RLHF under Differential Privacy](https://mlsanity.com/paper/2510.13512/) (2025) - [Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectories](https://mlsanity.com/paper/2511.07368/) (2025) - [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025) - [Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum](https://mlsanity.com/paper/2603.18325/) (2026) - [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026) - [Beyond RLHF: A Unified Theoretical Framework of Alignment](https://mlsanity.com/paper/2506.01523/) (2025) - [Post-Training with Policy Gradients: Optimality and the Base Model Barrier](https://mlsanity.com/paper/2603.06957/) (2026) - [Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference](https://mlsanity.com/paper/2603.07887/) (2026) - [Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability](https://mlsanity.com/paper/2605.09214/) (2026) - [Learning to Reason with Curriculum II: Compositional Generalization](https://mlsanity.com/paper/2606.27721/) (2026) - [When Does Online Imitation Learning Help in LLM Post-Training? The Role of (Non-)Realizability Beyond Horizon](https://mlsanity.com/paper/2606.30445/) (2026) - [SharedRep-RLHF: A Shared Representation Approach to RLHF with Diverse Preferences](https://mlsanity.com/paper/2509.03672/) (2025) - [TailSFT: Filtered Fine-Tuning Improves Post-Training Performance](https://mlsanity.com/paper/2608.25756/) (2026) - [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026) - [When Is Compositional Reasoning Learnable from Verifiable Rewards?](https://mlsanity.com/paper/2602.07992/) (2026) - [Temper-Then-Tilt: Principled Unlearning for Generative Models through Tempering and Classifier Guidance](https://mlsanity.com/paper/2602.10217/) (2026) - [Breaking the Capability Ceiling of LLM Post-Training by Reintroducing Markov States](https://mlsanity.com/paper/2603.19987/) (2026) - [Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration](https://mlsanity.com/paper/2603.22273/) (2026) - [RL Excursions during Pre-Training: Re-examining Policy Optimization for LLM training](https://mlsanity.com/paper/2606.04272/) (2026) - [The Power of Test-Time Training for Approximate Sampling](https://mlsanity.com/paper/2606.11437/) (2026) - [Learning to Choose or Choosing to Learn: Best-of-N vs. Supervised Fine-Tuning for Bit String Generation](https://mlsanity.com/paper/2505.17288/) (2025) ## Abstract (arXiv) Language model alignment (or, reinforcement learning) techniques that leverage active exploration -- deliberately encouraging the model to produce diverse, informative responses -- offer the promise of super-human capabilities. However, current understanding of algorithm design primitives for computationally efficient exploration with language models is limited. To better understand how to leverage access to powerful pre-trained generative models to improve the efficiency of exploration, we introduce a new computational framework for RL with language models, in which the learner interacts with the model through a sampling oracle. Focusing on the linear softmax model parameterization, we provide new results that reveal the computational-statistical tradeoffs of efficient exploration: 1. Necessity of coverage: Coverage refers to the extent to which the pre-trained model covers near-optimal responses -- a form of hidden knowledge. We show that coverage, while not necessary for data efficiency, lower bounds the runtime of any algorithm in our framework. 2. Inference-time exploration: We introduce a new algorithm, SpannerSampling, which obtains optimal data efficiency and is computationally efficient whenever the pre-trained model enjoys sufficient coverage, matching our lower bound. SpannerSampling leverages inference-time computation with the pre-trained model to reduce the effective search space for exploration. 3. Insufficiency of training-time interventions: We contrast the result above by showing that training-time interventions that produce proper policies cannot achieve similar guarantees in polynomial time. 4. Computational benefits of multi-turn exploration: Finally, we show that under additional representational assumptions, one can achieve improved runtime (replacing sequence-level coverage with token-level coverage) through multi-turn exploration.