Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration

2025/03/10 by Dylan J. Foster, Zakaria Mhammedi, Foster, Dylan J. +3 · 1 voice · 8 citations
#cs.LG #cs.AI #cs.CL #math.ST

paper · pdf · doi:10.48550/arxiv.2503.07453

Abstract

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.

Cited by

• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference
• MarkTune: Improving the Quality-Detectability Trade-off in Open-Weight LLM Watermarking
• Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training
• Offline and Online KL-Regularized RLHF under Differential Privacy
• Representation-Based Exploration for Language Models: From Test-Time to Post-Training
• Analytical Survey of Learning with Low-Resource Data: From Analysis to Investigation
• On the optimization dynamics of RLVR: Gradient gap and step size thresholds
• SharedRep-RLHF: A Shared Representation Approach to RLHF with Diverse Preferences

Discussions

• Reinforcement learning has led to amazing breakthroughs in reasoning (e.g., R1), but can it discover truly new behaviors not already present in the base model? A new paper with Zak Mhammedi and Dhruv [bsky, 43 points, 1 comments]

Related

• Representation-Based Exploration for Language Models: From Test-Time to Post-Training
• Toward Efficient Exploration by Large Language Model Agents
• Efficient Reinforcement Learning for Large Language Models with Intrinsic Exploration
• Ignore the KL Penalty! Boosting Exploration on Critical Tokens to Enhance RL Fine-Tuning
• CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Models