💬 NLP

Mitigating Exploration Bias in RL for Multi-Instruction Following

This paper addresses the exploration bias toward easy instructions in RL-based multi-instruction following by proposing a two-stage framework that combines behavioral bootstrapping to activate hard instructions and scarcity-aware rewards to prioritize them, significantly improving model performance across verifiable benchmarks.

Original authors: Mian Zhang, Yueqin Yin, Kaiyu He, Peilin Wu, Xinlu Zhang, Mingyuan Zhou, Zhiyu Zoey Chen

Published 2026-08-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mian Zhang, Yueqin Yin, Kaiyu He, Peilin Wu, Xinlu Zhang, Mingyuan Zhou, Zhiyu Zoey Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Large language models are the engines behind the chatbots and writing assistants that have become part of daily life. At their core, these systems are designed to follow instructions, taking a user's request and turning it into a helpful response. For years, researchers have used a training method called reinforcement learning to teach these models how to be better at this task. In this approach, the model tries to solve a problem, receives a score based on how well it did, and uses that feedback to improve its next attempt. It is a powerful way to refine behavior, much like training an animal with treats, but applied to complex digital reasoning. However, a new study suggests that when these models face a single request containing multiple different rules or constraints, the standard training method often fails them. Instead of learning to satisfy every part of the request, the model tends to ignore the difficult parts and focus only on the easy ones, leaving the user with a response that is only partially correct.

The researchers behind this study, working with teams at universities in Texas and California, set out to understand why this happens and how to fix it. They discovered that the problem stems from two main issues. First, when a model starts training, it is often too weak to solve the hardest parts of a complex request. Because it cannot succeed at these difficult tasks, it never gets the positive feedback needed to learn them, so it simply stops trying. Second, the scoring system used during training treats every instruction as equal. If a model satisfies one easy rule and one hard rule, it gets the same total score as if it had satisfied two easy rules. This encourages the model to chase the easy wins to boost its score quickly, rather than struggling through the difficult constraints that require more effort. The result is a model that is biased toward the easy path, leaving the harder challenges unexplored.

To solve this, the team proposed a two-step framework designed to force the model to pay attention to the difficult instructions. The first step is a preparation phase they call behavioral bootstrapping. Before the main training begins, the researchers identify the specific types of instructions that the model currently fails to follow. They then generate a small, focused set of examples where the model is guided to succeed at these specific hard tasks. By training on this curated data for just a short time, the model "wakes up" its ability to handle these difficult constraints. It is not about teaching the model everything from scratch, but rather giving it a small push to ensure it has a chance to succeed before the main training starts. This step ensures that the model does not immediately give up on the hard parts when the real training begins.

The second step involves changing how the model is rewarded during the main training phase. Instead of giving every instruction the same weight, the researchers introduced a new scoring method that pays attention to how rare or difficult a specific instruction is. If the model successfully follows an instruction that it rarely gets right, it receives a larger reward. If it follows an instruction it already masters easily, the reward is smaller. This creates a strong incentive for the model to explore the difficult territory it was previously avoiding. The researchers also added a bonus for successfully combining instructions. If a model manages to satisfy two rules at the same time, especially when those rules are hard to do together, it gets extra credit. This encourages the model to look for solutions that satisfy the entire set of constraints, rather than just picking and choosing the easiest ones.

The team tested these ideas using two different versions of a language model, one with 1.7 billion parameters and another with 7 billion. They trained these models on a dataset containing prompts with three to five instructions each. The results were striking. The models trained with the new two-step method significantly outperformed those trained with the standard approach. On a primary test set designed to check instruction following, the best model improved its accuracy by more than nine points compared to the standard method. This improvement was so substantial that the smaller 1.7 billion model, when trained with this new method, performed as well as much larger commercial models that have dozens of times more computing power. The researchers also measured the balance of the model's performance and found that the new method successfully reduced the gap between how well the model handled easy versus hard instructions.

The study also looked at what happens inside the model during training. They observed that the standard training method caused the model to lose its ability to explore different possibilities, a phenomenon known as entropy collapse, where the model gets stuck in a narrow loop of safe, easy answers. In contrast, the new method kept the model's exploration alive, allowing it to continue searching for complex solutions. The researchers noted that the approach works best when the training data is carefully balanced; too much data in the initial preparation phase could actually hurt the model's flexibility later on. While the method was tested on instructions that could be checked by a computer program, the researchers acknowledge that applying it to more open-ended requests, such as those involving style or tone, would require further work. Nevertheless, the findings offer a clear path forward for making artificial intelligence more reliable when faced with complex, multi-faceted requests. By addressing the bias toward the easy path, this work helps ensure that these powerful tools can truly follow the full scope of a user's intent.

Technical Summary: Mitigating Exploration Bias in RL for Multi-Instruction Following

Problem Definition

Reinforcement Learning (RL) has become a dominant paradigm for enhancing the instruction-following capabilities of Large Language Models (LLMs). However, when training on prompts containing multiple instructions, existing RL training recipes suffer from a significant exploration bias. The policy model tends to prioritize "easy" instructions over "hard" ones, leading to suboptimal performance in complex, multi-constraint scenarios.

The authors identify two primary causes for this bias:

Initial Capability Gap: The policy model's initial ability to satisfy hard instructions is often too low to trigger successful exploration during early RL training. Consequently, optimization is biased toward instructions the model can already satisfy.
Cumulative Reward Flaw: Canonical RL recipes typically employ a cumulative reward function (summing the number of fulfilled instructions), treating all instructions equally. This incentivizes the model to maximize immediate rewards by fulfilling easy instructions repeatedly, neglecting difficult ones that offer the same marginal reward.

This bias results in a stagnation where the model fails to explore the "sparse frontier" of complex constraints, preventing it from achieving an "all-pass" state (satisfying all instructions in a prompt simultaneously).

Methodology

To address these issues, the authors propose a two-stage framework designed to alleviate exploration bias:

1. Diagnostic Metrics

Before proposing solutions, the authors introduce two metrics to quantify exploration bias:

Variation of Instruction Accuracy (VIA): Measures the imbalance in a model's mastery of individual instructions (variance of marginal satisfaction probabilities).
Variance of Synergy Accuracy (VSA): Measures the imbalance in the model's ability to satisfy instruction pairs simultaneously (variance of pairwise synergy probabilities).
Experiments demonstrate that both metrics exhibit a strong negative correlation with the prompt-level "all-pass" rate; lower variance correlates with higher overall success.

2. Behavioral Bootstrapping (Stage I)

To overcome the initial capability gap for hard instructions, the authors introduce a lightweight Rejection Sampling Fine-Tuning (RSFT) phase prior to RL.

Process: The initial policy is evaluated to identify "seed" instruction types with accuracy below a threshold ( $\tau$ ).
Data Curation: For these hard types, the model generates multiple responses. If the base policy fails, "Targeted Guiding" (appending a suffix like "Focus on fulfilling [Instruction] first") is used to nudge the model. Valid responses that satisfy the hard instruction while maximizing coverage of other instructions are selected.
Outcome: The policy is supervised fine-tuned on this curated dataset for a single epoch. This "bootstraps" the model's capability, activating hard instructions before the RL phase begins.

3. Scarcity-Aware Rewards (Stage II)

To counter the bias introduced by cumulative rewards, the authors propose a new reward function that assigns weights based on empirical scarcity.

Mechanism: Instead of treating all instructions equally, the reward is inversely proportional to the frequency of satisfaction within a response group.
- Unary Reward: $1 - P(I_j)$ , where $P(I_j)$ is the marginal satisfaction probability. Rarely satisfied instructions receive higher weights.
- Binary Reward: $1 - P(I_j, I_k)$ , focusing on the difficulty of instruction "co-occurrence." It penalizes pairs that are easy to satisfy separately but difficult to satisfy together, encouraging the model to overcome synergy bottlenecks.
Integration: This reward is calculated over a group of responses (compatible with group-based methods like GRPO) and used to update the policy.

Key Results

The authors evaluated their framework using Qwen3-1.7B and Qwen2.5-7B-Instruct across three verifiable instruction-following benchmarks: IFBench, IFEval, and Multi-IF.

Performance Gains: Models integrated with Behavioral Bootstrapping and Scarcity-Aware Rewards (BeBoot-SaR) significantly outperformed standard cumulative reward (CR) baselines.
- On the primary test set (IFBench), the 1.7B model achieved a 9.2 point gain in strict accuracy, and the 7B model achieved an 8.9 point gain over their respective baselines.
- Across all benchmarks, the average gain was 5.5 points for the 1.7B model and 3.6 points for the 7B model.
Competitiveness: The small models (1.7B and 7B) trained with this framework matched or approached the performance of much larger off-the-shelf models, such as Llama-3.1-70B and GPT-OSS-120B.
Bias Mitigation: Training curves showed that the proposed method achieved a faster and more substantial reduction in VIA and VSA compared to the baseline, indicating a more balanced exploration of the instruction space. The method also maintained higher policy entropy, avoiding the "entropy collapse" seen in standard RL training.

Significance and Claims

The paper claims that its framework effectively addresses the specific exploration bias inherent in multi-instruction RL training. By combining a pre-training activation phase (Behavioral Bootstrapping) with a scarcity-aware reward mechanism, the authors demonstrate that:

Targeted Activation: It is possible to "activate" hard instructions that standard RL would otherwise ignore due to sparse initial rewards.
Reward Design: Assigning rewards based on empirical scarcity, rather than treating all constraints equally, is crucial for optimizing complex instruction sets.
Efficiency: Small models can be trained to match the capabilities of significantly larger models through better optimization strategies rather than simply scaling up parameters.

Limitations

The authors acknowledge specific limitations:

Higher-Order Dependencies: The current reward design focuses on unary (single) and binary (pairwise) interactions. It does not explicitly address higher-order dependencies where three or more instructions interact simultaneously, though the framework is theoretically generalizable to $n$ -ary rewards.
Verifiability: The method relies on identifying difficult instruction types, which is straightforward for verifiable instructions (e.g., rule-based constraints). Extending this to open-ended instructions (e.g., style, politeness) would require reliable model-based verifiers for difficulty estimation, which are currently less reliable and prone to noise.