The Power of Verification for One-Parameter Agents