Agentic Policy Optimization via Instruction-Policy Co-Evolution

Motivation

• Static instructions can be suboptimal for the base model and change as the policy improves and explores the environment.Instruction choices strongly affect agent trajectories and converged RL performance, making manual iterative refinement costly.Source: §1 · p. 1

Contribution

• INSPO integrates instruction learning dynamically into the RL loop so instructions and policy co-evolve online.The framework replaces a fixed instruction with an adaptive instruction-learning component.Source: §1 · p. 2

Policy-Optimization with Dynamic Instructions

• INSPO samples instructions from a weighted population, attributes rewards to assigned candidates, prunes low performers, and evolves replacements.Instruction importance is updated alongside policy parameters during optimization.Source: §1 · p. 2

Experience-Driven Instruction Generation

• An on-policy reflection mechanism uses low-reward trajectories to generate, verify, and merge instructions that address observed failure modes.An LLM-based proposer analyzes replay-buffer experience and rejects low-performing candidates through proxy verification.Source: §1 · p. 2

Results

• INSPO substantially outperforms static-instruction baselines on multi-turn retrieval and reasoning tasks while adding only marginal training computation.Ablations also favor online instruction-policy co-evolution over instruction optimization performed before or after RL.Source: §1 · p. 2

2.1. Reinforcement Learning with Tool-Using

• Multi-turn tool use is modeled as an MDP in which policy π generates actions and tool engine T returns interleaved observations forming trajectory τ.The trajectory includes the initial instruction, question, actions, and tool feedback across multiple turns.Source: §2.1 · p. 2
• RL optimizes policy parameters θ for expected returns, with RLVR commonly using a verifier-based exact-match reward that is 1 only for a correct final action.The reward function is defined over trajectories sampled from a question distribution.Source: §2.1 · p. 2

2.2. Group Relative Policy Optimization (GRPO)

• GRPO estimates an advantage from relative performance within a group of sampled trajectories without requiring a separate value-function model.It derives from PPO and includes a KL-divergence penalty against a reference policy for regularization.Source: §2.2 · p. 2
• INSPO reuses reward signals for both policy updates and instruction-importance updates, assigning each trajectory's reward to its sampled instruction.Importance weights are updated from a moving average of recent rewards for stable estimation.Source: Figure 1 · p. 3
• For multi-turn RL, GRPO masks observation tokens and computes the loss only over tokens generated by the agent's actions.Applying policy gradients to off-policy environmental observations can destabilize training and cause unintended reward collapse.Source: §2.2 · p. 3

3. Instruction-Policy Co-Evolution (INSPO)

• INSPO reframes instruction design as a dynamic component of RL, with instructions optimized alongside the agent policy online.Source: §3 · p. 3

3.1. Policy Optimization with Dynamic Instructions

• A population of instruction candidates is sampled using importance weights, while a temperature parameter balances exploration of new instructions against exploitation of effective ones.Source: §3.1 · pp. 3–4
• Reward signals update both policy parameters and instruction weights, with each trajectory’s reward attributed to the instruction used to generate it.Source: §3.1 · p. 4
• Low-weight instructions are periodically pruned through successive halving, while high-performing candidates serve as parents for evolving new instructions.Source: §3.1 · p. 4

3.2. Experience-Driven Instruction Generation

• INSPO stores instruction, question, trajectory, and reward tuples in a replay buffer, prioritizing incorrect or low-reward trajectories as correction signals.Source: §3.2 · p. 4
• Algorithm 1 iterates policy updates, reward-weight updates, pruning, replay-buffer storage, instruction generation, and validation before returning the optimized policy and best instruction.Source: §3.2 · p. 4
• An LLM-based optimizer reflects on parent instructions and failure trajectories to diagnose failure modes and propose refined instructions.Source: §3.2 · pp. 4–5
• New instructions are verified on replay-buffer samples, and only top-performing candidates are merged until the population reaches its target size.Source: §3.2 · p. 5

Models and evaluation data

• The evaluation covers seven search-based question-answering benchmarks spanning multi-hop retrieval and general question answering.Source: §4 · p. 5
• Experiments use Qwen 2.5 3B and 7B models, with Gemini 2.5 Pro serving as the LLM-based instruction optimizer.Source: §4 · p. 5

Baselines

• INSPO is compared with static-instruction baselines including direct inference, SFT, GRPO, RAG, IRCoT, Search-o1, SFT with reject sampling, and Search-R1.Source: §4 · p. 5

Setups

• Tool-integrated experiments follow the Search-R1 setup, use E5 retrieval over the 2018 Wikipedia dump, and optimize Exact Match reward.Source: §4 · p. 5

Main results

• 38.2% average EM on Qwen-2.5-3B surpasses Search-R1 by 6% across the evaluated benchmarks.Table 1 reports exact-match results on multi-hop and general question-answering benchmarks.Source: §5 · p. 5, Table 1 · p. 6
• Over 7% improvement over Search-R1 on HotpotQA and 2WikiMQA shows INSPO’s strongest gains on complex multi-hop reasoning.INSPO uses multiple tool interactions, whereas Search-R1 converges near a single tool call.Source: §5 · pp. 5–6

Training dynamics

• INSPO explores more tool-use patterns, evolves longer prompts, and produces longer responses than the static baseline during training.Figure 2 attributes these differences to broader tool-use exploration and periodically refined instructions.Source: Figure 2 · p. 6

Case analysis

• Reflection-based instruction evolution identifies failure modes and generates structured guidance, such as step-by-step tool plans and strict XML actions.The resulting instruction directly supports a correct answer in the analyzed trajectory, while simpler proposers provide inadequate gains.Source: §5 · p. 7

Instruction Evolution Stage

• Online co-evolution outperforms pre-policy and post-policy instruction optimization because the optimal instruction changes as the policy learns.Post-policy optimization can degrade performance when new instructions conflict with a policy overfitted to its initial instruction.Source: §5 · p. 7

Instruction Population

• Pruning and expanding the instruction population improves average performance from 33.0% to 36.3%, while the full generate-and-verify loop performs best.The result supports maintaining a high-quality instruction population throughout co-evolution.Source: §5 · p. 7

• INSPO complements existing RLVR methods as a modular component of the typical learning loop.Source: §6 · p. 8
• Tool-integrated agent frameworks have enabled multi-turn interactions, but prior end-to-end RL approaches generally rely on costly manual instructions that remain static during learning.Source: §6 · p. 8
• Instruction optimization research has progressed from paraphrasing and exemplars to LLM-based optimizers, textual gradients, and reflective prompt design.Source: §6 · p. 8
• INSPO is the first framework described here to integrate instruction optimization directly into the online RL loop, co-evolving instructions and the policy with on-policy experience and environmental feedback.Source: §6 · p. 8

• INSPO substantially outperforms strong static-instruction baselines across tool-integrated question-answering benchmarks.Source: §7 · p. 8
• INSPO maintains dynamic instruction candidates and reflects on online feedback to automate the discovery of more effective reasoning strategies during policy learning.Source: §7 · p. 8
• Case studies and ablations identify online, reflection-based instruction-policy co-evolution as key to more robust and accurate tool-integrated reasoning.Source: §7 · p. 8
• INSPO reduces reliance on manual prompt engineering within a more autonomous and adaptive RL framework.Source: §7 · p. 8

• INSPO’s experience-driven instruction generation relies on a capable LLM-based optimizer to perform self-reflection and produce sophisticated instructions.Source: A. Future Work and Limitations · p. 13
• The framework introduces non-zero API and verification-inference costs, although the authors report that the overhead is marginal relative to total training cost.Source: A. Future Work and Limitations · p. 13
• Experiments primarily cover search-based question-answering tasks, leaving extension to other tools and agentic domains for future work.Source: A. Future Work and Limitations · p. 13

• Training uses VeRL, Search-R1 data mixtures, 8×H100 GPUs, model-specific learning rates, 300 steps, cosine scheduling, and final checkpoints before reward collapse.Source: B. Implementation Details · p. 13
• GRPO and INSPO use group size 5, batch size 512, maximum prompt length 4096, bounded response and observation lengths, and model-dependent turn caps.Source: B. Implementation Details · p. 13
• INSPO initializes a diverse instruction population, updates candidate importance with five-step running averages, samples four failure trajectories for reflection, and verifies candidates using 200 samples.Source: B. Implementation Details · p. 13

• Verification adds roughly 12,000 policy-model inferences, while self-reflection requires about 11 LLM-optimizer API calls over the training process.The estimate assumes 6 new candidates per evolution, up to 5 verification retrials, and 10 evolution rounds.Source: C. Computation Analysis · p. 13

D. Additional Experiments

• All tested parent-selection settings outperform Search-R1, with Nparents = 1 achieving the highest performance.Using one highest-quality parent favors greedy improvement of the instruction population.Source: D. Additional Experiments · p. 13, Figure 6 · p. 14
• Temperature mainly changes reward variance; INSPO uses τs = 0.2 as a balance between instruction exploration and exploitation.Lower temperature produces greedier exploitation but can cause sharper instruction updates and higher subsequent variance.Source: D. Additional Experiments · p. 13, Figure 6 · p. 14
• Figure 5 compares INSPO with Search-R1 baselines across three random seeds on Qwen-2.5-3B.Source: Figure 5 · p. 14

E. Prompt Templates

• The paraphrasing optimizer asks an LLM to improve an instruction and produce six candidates while preserving the original XML tags.Source: E. Prompt Templates · p. 15
• The history-based optimizer uses instruction-score histories to identify components associated with better performance and generate diverse improved candidates.Source: E. Prompt Templates · p. 15
• The reflection-based optimizer analyzes incorrect replay-buffer examples, diagnoses failure causes, and proposes revised instruction candidates with preserved XML structure.Source: E. Prompt Templates · p. 15

• The baseline instruction asks the agent to reason inside <think> tags, search, and answer directly, but its demonstrated response returns James Buchanan.Source: F. Demonstration · pp. 15–16
• INSPO’s instruction requires entity-by-entity searches, contextual analysis after each result, iterative retrieval, and a final answer inside <answer> tags.Source: F. Demonstration · p. 16
• The example question asks for the U.S. president in the year Citibank was founded, linking the bank’s 1812 founding date to a presidential lookup.Source: F. Demonstration · p. 16
• Search results identify James Madison as president in 1812, and the INSPO-optimized response returns James Madison in the required answer format.Source: F. Demonstration · pp. 16–17
• The reflection analysis attributes baseline failures to weak structure adherence, unverified internal knowledge, irrelevant-result handling, formatting errors, and hallucinated task derailment.Source: F. Demonstration · p. 17
• The resulting prompt is made more prescriptive by enforcing a stepwise workflow, requiring searches when needed, checking retrieved evidence, and forbidding extra answer text.Source: F. Demonstration · p. 17