Pairwise Workflow Policy Optimization for Tool-Using Language Agents

Tool-using language agents can automate complex tasks, but reinforcement learning treats different execution orders as distinct experiences even when they produce identical outcomes, introducing noise unrelated to task quality. We introduce Pairwise Workflow Policy Optimization (PWPO), which verifies that swapping two adjacent tool calls preserves their outputs and resulting state, then optimizes the summed probabilities of both complete execution histories. In deterministic environments with restorable states, this aggregation preserves the expected on-policy gradient and removes variation within verified pairs; our analysis specifies when this reduction offsets additional computation. Across AppWorld-Atomic, ALFWorld, and WebShop under matched rollout budgets, PWPO achieves the highest means among evaluated methods on all 16 main metrics, improving AppWorld-Atomic task completion over G2PO by 2.32–2.64 percentage points. These results support learning from verified workflow alternatives while retaining the agent's sequential deployment interface.