Replay Failures as Successes: Sample-Efficient Reinforcement Learning for Instruction Following

Reinforcement Learning (RL) has shown promise for aligning Large Language Models (LLMs) to follow instructions with various constraints. Despite the encouraging results, RL improvement inevitably relies on sampling successful, high-quality responses; however, the initial model often struggles to generate responses that satisfy all constraints due to its limited capabilities, yielding sparse or indistinguishable rewards that impede learning. In this work, we propose **Hindsight instruction Replay (HiR), a novel sample-efficient RL framework for complex instruction following tasks, which employs a select-then-rewrite strategy to replay failed attempts as successes based on the constraints that have been satisfied in hindsight. We perform RL on these replayed samples as well as the original ones, theoretically framing the objective as dual-preference learning at both the instruction- and response-level to enable efficient optimization using only a binary reward signal. Extensive experiments demonstrate that the proposed HiR yields promising results across different instruction following tasks, while requiring less computational budget. Our code and dataset are available at https://github.com/sastpg/HIR.

Reinforcement Learning (RL) has shown promise for aligning Large Language Models (LLMs) to follow instructions with various constraints. However, current RL methods for instruction following typically suffer from sparse or indistinguishable rewards due to limited capabilities of the initial model. We propose a method called Hindsight instruction Replay (HiR) that converts failures into successful samples, which enriches the reward signals during training. Our key idea is simple: if a response satisfies some constraints in an instruction but misses others, we rewrite the original instruction in hindsight by removing the constraints that are not satisfied. Moreover, we design a selection strategy for failed attempts that gradually shifts from response diversity to constraint integrity. This encourages the model to learn useful knowledge from not only successes but also failures. Our Experiments across instruction following benchmarks demonstrate that HiR yields superior performance while using less computational budget.