Source-linked AI summary
Mitigating Exploration Bias in RL for Multi-Instruction Following
Mian Zhang, Yueqin Yin, Kaiyu He, Peilin Wu, Xinlu Zhang, Mingyuan Zhou, Zhiyu Zoey Chen
TL;DR
The paper addresses exploration bias in multi-instruction RL, where low initial ability on hard instructions and equal-weight cumulative rewards favor easy instructions. It introduces diagnostic metrics, behavioral bootstrapping, and scarcity-aware rewards. Across three verifiable benchmarks, the combined approach substantially outperforms cumulative-reward baselines, while remaining limited to settings with reliable verification and mainly unary or binary reward structure.
Problem
Multi-instruction RL favors easy instructions because hard instructions have low initial success and cumulative rewards treat all instructions equally.
Method
The paper combines behavioral bootstrapping before RL with scarcity-aware unary and binary rewards that prioritize rare instructions and combinations.
Results
The combined models outperform standard cumulative-reward baselines by an average of 4.5 points across evaluated benchmarks and up to 9.2 points on IFBench.
Takeaways & Limitations
The framework enables relatively small models to match the performance of much larger off-the-shelf models.
Takeaways & Limitations
The framework is validated only on verifiable instruction following, and its current rewards model unary and binary rather than higher-order instruction interactions.
Abstract
from arXiv · showhide
RL has emerged as a powerful paradigm for enhancing the instruction following capabilities of LLMs. While existing training recipes achieve substantial gains, we find that they suffer from exploration bias towards easy instructions when the training data has multiple instructions in a prompt. This bias is caused by two main reasons: 1) the policy model's initial ability to satisfy hard instructions is too low to trigger successful exploration during RL training, so the optimization is biased towards easy instructions; and 2) canonical RL training recipes typically employ a cumulative reward (the number of instructions fulfilled), treating all instructions equally, which biases the policy model towards fulfilling easy instructions to obtain the same amount of reward. To address these issues, we first propose two metrics to measure the exploration bias in instruction following and then introduce a two-stage framework to alleviate it: 1) Behavioral Bootstrapping, a lightweight rejection sampling fine-tuning stage before RL to activate hard instructions; and 2) Scarcity-Aware Rewards, a new RL reward function that assigns rewards to instructions based on their empirical scarcity. Experiments show that the proposed metrics are highly correlated with model performance, and our methods unleash the potential of RL training: our best models outperform the baselines by a significant margin across three verifiable instruction following benchmarks. We release codes at https://github.com/mianzhang/MulIF.
1 Introduction
RL instruction-following with multiple constraints is biased toward easy instructions because they provide more reliable reward signals while hard instructions often begin with too little accuracy for successful exploration. The paper measures this bias and proposes behavioral bootstrapping plus scarcity-aware rewards, achieving substantial gains across three benchmarks.
- 1 Introduction: Canonical cumulative rewards bias RL toward easy instructions because their frequent satisfaction supplies dense, stable optimization signals.The resulting optimization neglects hard instructions and can stall before reaching an all-pass response.
- 1 Introduction: Initial RL gains are more consistent for Easy instructions, while Medium and Hard instruction improvements show high variance.Instructions with very low initial accuracy often benefit minimally from RL training.
- 1 Introduction: The paper introduces Variation of Instruction Accuracy and Variance of Synergy Accuracy to quantify imbalance in individual mastery and simultaneous instruction satisfaction.Both metrics are reported as strongly negatively correlated with prompt-level all-pass rates.
- 1 Introduction: Behavioral Bootstrapping activates hard instructions before RL, while Scarcity-Aware Rewards prioritize rare instructions and combinations during RL.The framework addresses both low initial capability and equal-weight cumulative rewards.
- 1 Introduction: 4.5 points average improvement across evaluated benchmarks and up to 9.2 points on IFBench let the relatively small models match much larger off-the-shelf models.These results are reported for models combining Behavioral Bootstrapping with Scarcity-Aware Rewards against the standard cumulative-reward baseline.
2 Related Work
The related work situates exploration bias within broader RL failures involving reward shortcuts, reduced diversity, task imbalance, and sparse-reward exploration bottlenecks. Prior studies identify these issues at reward, algorithm, or task levels.
- 2 Related Work: RL fine-tuning can introduce length bias, mode collapse, and entropy collapse that reduce exploratory capacity.These examples describe systematic biases in language-model reinforcement learning.
- 2 Related Work: Multi-task RL can produce optimization imbalance, with reported gradient magnitudes differing by up to 33× and easy tasks dominating.Multi-objective methods therefore need to balance conflicting alignment objectives.
- 2 Related Work: Recent RLVR work links low initial accuracy on hard problems to sparse rewards and a self-reinforcing loop that prevents learning.The paper distinguishes its exploration-bias focus from prior approaches addressing reward, algorithm, or task-level biases.
3 Measure of Exploration Bias
The paper measures exploration bias through imbalance in individual instruction mastery and pairwise instruction synergy. Controlled experiments find that lower imbalance is consistently associated with higher prompt-level accuracy.
- 3 Measure of Exploration Bias: VIA measures the variance of marginal satisfaction probabilities across instructions, so high VIA indicates uneven individual instruction mastery.It captures whether the model excels at some instruction types while failing others.
- 3 Measure of Exploration Bias: VSA measures variance in pairwise synergy probabilities, identifying uneven ability to satisfy instruction pairs together.High VSA indicates that some pairs are synergized substantially better than others.
- 3 Measure of Exploration Bias: Pairwise synergy probability normalizes joint satisfaction by the lower individual satisfaction probability of the two instructions.This construction focuses on whether co-satisfaction is bottlenecked relative to the easier individual condition.
- Relationship with Prompt Accuracy: The controlled experiment samples response groups from a broad model pool and estimates marginal and pairwise probabilities from a binary verification matrix.Groups use K = 128 responses with instruction accuracy fixed at 0.68 ± 0.01.
- Relationship with Prompt Accuracy: Lower VIA and VSA consistently correspond to higher prompt accuracy, supporting both metrics as indicators of exploration bias.The reported inverse relationship links balanced instruction and pairwise mastery with greater prompt-level success.
4 Mitigating Exploration Bias
The framework mitigates exploration bias by first activating difficult instructions through behavioral bootstrapping, then rewarding scarce instructions and difficult instruction combinations during RL.
- Behavioral Bootstrapping: Behavioral Bootstrapping evaluates initial instruction-type accuracy and curates successful seed rollouts for difficult instructions before RL.It uses rejection sampling fine-tuning, selecting responses that satisfy a target instruction while maximizing coverage of other prompt instructions.
- Behavioral Bootstrapping: The method identifies seed instruction types below a predefined accuracy threshold and builds a minimal dataset of successful rollouts for them.If the base policy fails, targeted guiding prompts can help generate valid responses.
- Scarcity-Aware Rewards: The reward design addresses equal treatment of instructions by encouraging exploration of rare instructions and rare combinations.Group-based methods such as GRPO naturally provide response groups for estimating advantages, with negligible additional cost.
- Scarcity-Aware Rewards: Scarcity-Aware Rewards estimate instruction and pairwise satisfaction probabilities from verification matrices over sampled response groups.Unary rewards use 1 − P(I_j), while pair rewards use 1 − P(I_j, I_k).
- Scarcity-Aware Rewards: Rarely satisfied instructions receive higher unary weights, while binary rewards target instruction pairs that are easy separately but difficult to satisfy together.The binary reward is set to 0 when either instruction has no successes, and α balances unary and binary contributions.
5 Experiments
Experiments evaluate the proposed methods on verifiable instruction-following benchmarks and show consistent gains over cumulative-reward baselines. Analyses indicate improved exploration balance, challenging-instruction performance, policy entropy, and sensitivity to training configurations.
- Experimental Settings: Experiments use verifiable instruction following, where deterministic verification provides 100% accuracy, across three benchmarks with distinct evaluation settings.IFBench is out-of-domain, IFEval is in-domain, and Multi-IF evaluates multi-turn and multi-instruction following.
- Main Results: BeBoot and SaR outperform cumulative-reward baselines by average gains of 5.5 points for the 1.7B model and 3.6 points for the 7B model.These gains are reported across the evaluated benchmarks.
- Main Results: 44.3 and 48.4 strict accuracy are achieved by Qwen1.7B-BeBoot-SaR and Qwen7B-BeBoot-SaR on the primary IFBench test set.These scores represent gains of 9.2 and 8.9 points over the respective baselines and indicate improved generalization to unknown instruction types.
- Exploration Bias: BeBoot+SaR reaches the lowest VIA and VSA levels while increasing instruction coverage and prompt-level success during training.The trajectories indicate more balanced exploration of the instruction space and satisfaction of multiple diverse instructions.
- Instruction-Type Analysis: BeBoot and SaR improve challenging combination, copy, and length_constraint categories, while every model records a 0% pass rate on the new category.The new category contains extremely difficult instructions, including character-index span copying.
- Ablation Analysis: The proposed method maintains higher policy entropy than the baseline, while larger response groups converge faster but may cause over-optimization.Ablations also show peak performance at α = 2.0 and suggest that excessive bootstrapping data can reduce later RL flexibility.
6 Conclusion
This work addresses exploration bias in multi-instruction RL by activating difficult instructions and rewarding rare instruction satisfaction. The framework enables small models to match larger off-the-shelf models.
- The framework combines behavioral bootstrapping to activate difficult instructions with scarcity-aware rewards to incentivize rare instruction satisfaction during RL.
- The proposed framework enables small models to match the performance of larger off-the-shelf models.
Limitations
The framework remains limited by its pairwise reward design and reliance on reliable difficulty identification and verification. Consequently, the study focuses on verifiable instruction following, while higher-order interactions and broader open-ended instructions remain future work.
- Scarcity-aware rewards model individual instructions and pairwise synergies, potentially leaving higher-order co-satisfaction bottlenecks unaddressed in dense constraint scenarios.The framework could theoretically generalize to n-ary scarcity rewards, but this is left for future investigation.
- The framework is validated only on verifiable instruction following because open-ended settings require reliable difficulty estimation and model-based verifiers.Extending it to style, politeness, and factuality is identified as future research.