RLVP: Penalize the Path, Reward the Outcome

Source: arXiv:2607.07435 · Published 2026-07-08 · By Bojie Li, Noah Shi

TL;DR

This paper addresses the challenge of training real-world interactive agents—such as phone agents or system administrators—that must learn from costly, irreversible interactions rather than cheap simulations. Traditional reinforcement learning from verifiable rewards (RLVR) optimizes only on the final outcome, ignoring important deployability constraints that depend on the path taken. Such outcome-only training often leads to policy behaviors that violate outcome-neutral rules (e.g., not calling a user repeatedly, respecting business hours) despite achieving task success. Furthermore, costly real-world interactions necessitate highly sample-efficient learning. To address these, the authors propose RLVP, a framework that combines a penalty on verifiable bad actions along the path with reward on final outcomes, summarized as "penalize the path, reward the outcome."

The key insight is that training purely on sparse outcome rewards yields zero within-group variance (and thus zero advantage gradient) on all-fail or all-success rollout groups, preventing learning from those samples. Introducing a dense verifiable penalty on forbidden actions creates useful within-group variance and drives learning away from violating behaviors. Complementarily, rewarding verifiable progress as a dense potential accelerates learning when partial progress is reachable. The authors empirically validate RLVP across synthetic system-administration and customer-support tasks as well as a realistic shell-command benchmark (TerminalBench) and a theorem-proving domain. RLVP nearly eliminates constraint violations while maintaining equivalent or improved task success. It also speeds up learning convergence up to 3.6× and improves training stability compared to outcome-only baselines.

Overall, this work demonstrates a practical recipe and design rules for integrating verifiable penalties and progress potentials into RL for costly, real-world agents. It provides mechanistic explanations rooted in within-group variance of advantage estimates, yielding substantial improvements in deployability and sample efficiency where outcome-based RL alone fails.

Key findings

• At equal task success rates on TerminalBench (Qwen3-4B), RLVP reduces violations by a factor of approximately 6 (0.66 ± 0.63 violations per episode vs 3.71 ± 0.52) while increasing productive actions from ~4 to ~13 per episode.
• Outcome-only RL is blind (zero within-group variance) at extremes of all-fail and all-success groups, causing dead policy updates early and late in training (Figure 3).
• Penalizing specific verifiable bad actions while retaining outcome reward steers policy to nearly 100% violation-free episodes without sacrificing success in synthetic system-administration and customer-support proxies (Figure 5).
• Pairing penalties with corresponding fulfillment credits (+β) and seeding small scripted compliant demonstrations is essential to avoid the inaction trap and reliably learn deployable policies (Figure 7).
• Rewarding verified progress as a dense potential accelerates learning in domains where partial progress is reachable (theorem proving, software repair), reducing time to reach 90% success by ~37% at 4B scale (4.4 vs 7 iterations) and eliminating early dead all-fail updates (Figure 10, 9).
• At 30B scale, outcome-only training diverges under fast optimizer in 3/5 seeds and trains 3.6× slower under stable optimizer, whereas aligned potential RLVP is both stable (0/5 divergences) and faster (5.4 vs 19.2 iterations) (Table 2).
• The benefit of the dense potential is reachability-gated—where partial progress states are not reached, it yields zero within-group variance and no gradient (Figure 9).
• A pure penalty used alone causes the agent to collapse into the inaction trap, confirming the importance of combining penalties with outcome rewards and fulfillment credits (Figure 7, Appendix B.1).

Threat model

The adversary is the RL agent optimizing policy to maximize expected rewards. It can choose any action sequence but must respect verifiable outcome-neutral constraints to be deployable. The environment can cheaply and deterministically verify certain bad actions (e.g., calls without authentication) and progress steps but cannot verify more subjective or ambiguous behaviors. The agent cannot falsify the deterministic verifiers that tag actions with penalties or credits.

Methodology — deep read

1. Threat model & assumptions: The adversary is conceptualized as the RL agent itself aiming to maximize outcome rewards. The environment can cheaply and reliably verify specific bad actions (e.g., calling before authentication) and successful progress steps, but cannot certify partial progress or differentiate more subjective behaviors. The agent must respect outcome-neutral path constraints that are invisible to the outcome reward but critical for deployability.

2. Data: The experiments use a suite of synthetic system and customer-support tasks with defined preconditions and forbidden actions, a terminal shell-command benchmark (TerminalBench) executing real shell commands in containerized environments where destructive commands can be flagged, and the miniF2F theorem-proving benchmark on algebra problems with formal kernel-verifiable tactics. Multiple model scales (1.7B, 4B, 8B, and 30B parameters) and 3-5 random seeds per configuration are run.

3. Architecture/algorithm: The RLVP method extends group-relative policy optimization (GRPO), a group-relative RL approach where trajectories sampled from the same prompt/task form a group and advantage estimates are computed as deviations from the group mean reward. RLVP introduces a secondary per-action verifiable path reward channel evaluated by a deterministic rule engine that tags actions with penalties (−λ) for violating outcome-neutral constraints and credits (+β) for compliant actions or verified progress. These two reward channels are normalized separately and combined. The RL agent optimizes the combined reward using standard policy gradients without a learned critic.

4. Training regime: Training is performed online with expensive, irreversible interactions rather than simulators. The verifiable penalty provides dense within-group variance early (when outcomes are all fail) and the credit for progress accelerates learning where partial success states are encountered. The penalty and credit are annealed once compliance saturates. Training runs for 30+ iterations with batch sizes sufficient to form groups for advantage calculation. Model seeds are swept to assess stability, and ablations test isolated components.

5. Evaluation protocol: Metrics include task success rate, violation-free episode rate, count of harmful/forbidden actions, productive actions per episode, and learning speed quantified as number of iterations to reach 90% task success. Baselines are outcome-only GRPO variants. Statistical significance is assessed over seeds. Held-out test tasks and generalization across model sizes are examined. Ablations isolate the effects of fulfillment credits, seeding demonstrations, and penalty annealing. Divergence is monitored using entropy collapse guards.

6. Reproducibility: Code and benchmarks are open-sourced at https://github.com/19PINE-AI/rlvp. Datasets rely on public miniF2F and TerminalBench. Seeds and hyperparameters are documented. Some experimental details like exact hyperparameter values require referencing the appendix. The rule engines for verifiable signals are deterministic predicates based on environment state.

Concrete example: On the miniF2F theorem proving task, the outcome pays +1 only upon completing the proof, sparse and delayed. The aligned potential channel attaches a +β credit to each kernel-verified drop in outstanding proof obligations (e.g., 3 → 2), generating a dense positive signal. Early training rollouts that fail the full proof but make partial progress differ in their path rewards, creating within-group variance and gradient despite zero outcome rewards. This drives faster and more stable learning compared to outcome-only reward alone (Figure 8).

Technical innovations

• Demonstration that group-relative advantage equals within-group variance, and outcome-only RL has zero variance at all-fail and all-success extremes, motivating the need for path-dependent signals.
• Introduction of a verifiable path channel that supplies per-action penalties for disallowed actions and credits for compliant actions or verified progress, combined with outcome reward.
• A design recipe that combines penalizing verifiable bad actions with pairing them to fulfillment credits, seeding reachable compliant demonstrations, and annealing path shaping to avoid inaction traps.
• Empirical validation that verifiable path penalties reduce harmful violations nearly sixfold at equal task success and that aligned potentials accelerate convergence with improved stability.
• Formulation and experimental confirmation that dense potentials help only where partial progress is reachable, while verifiable penalties provide gradient universally in all-fail regimes.

Datasets

• TerminalBench — shell command tasks with real filesystem side effects — https://github.com/19PINE-AI/terminalbench
• miniF2F — 1600+ formal algebra theorem proving problems — public repository
• Synthetic system-administration and customer-service proxies (unspecified size, controlled rule environment) — internal

Baselines vs proposed

• Outcome-only RL (GRPO): violation rate ~3.7 vs RLVP penalty: ~0.66 violations per episode
• Outcome-only RL: task success ≈ 0.122 ± 0.076 vs RLVP penalty: 0.097 ± 0.060 (statistically equal within 1σ)
• Outcome-only RL (miniF2F 4B): iterations to 0.9 success = 7.0 ± 0.7 vs aligned potential: 4.4 ± 0.5
• Outcome-only RL (miniF2F 30B AdamW): iterations to 0.9 success = 19.2 ± 1.9 vs aligned potential: 5.4 ± 1.0
• Outcome-only RL 30B Muon optimizer: 3/5 diverged vs aligned potential 0/5 diverged

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.07435.

Fig 13: Reachability, measured cheaply, gates the dense-reward benefit. (a) VarG(Φ) on base-policy

Limitations

• The verifiable penalty methodology requires existence of deterministic, verifiable predicates on actions; cannot handle subjective or ill-defined constraints.
• Dense potentials depend critically on reachability of partial progress states; in domains lacking such structure, benefits diminish.
• Experiments are limited to controlled or proxy real-world tasks (e.g., phone agent, shell commands, theorem proving); generalization to fully live, interactive deployments remains to be demonstrated.
• Model architectures and hyperparameters are fixed; the interaction of RLVP with different model types or training regimes is not extensively explored.
• Penalties must be carefully designed with fulfillment credits and seeding to avoid inaction traps, which introduces human effort and may not scale easily to all domains.
• The study does not deeply analyze adversarial scenarios where the agent attempts to game the penalty or the rules’ deterministic verifiers.

Open questions / follow-ons

• How to extend verifiable penalty and potential frameworks to environments where verifiable constraints are fuzzy or probabilistic rather than deterministic?
• Can learned critics or classifiers replace or augment deterministic rule engines while avoiding gaming and preserving the benefits of verifiable path channels?
• What are the best practices for scaling this method to more complex high-dimensional state/action spaces where enumerating all verifiable bad actions is infeasible?
• How to systematically automate seeding of compliant demonstrations and annealing schedules in diverse real-world domains?

Why it matters for bot defense

For bot-defense and CAPTCHA engineers, this work highlights the importance of considering not just the final outcome (e.g., was the CAPTCHA solved) but the trajectory or path the agent takes during interactions. Many existing RL or behavioral models focus on outcome signals and thus fail to detect or penalize suspicious intermediate bot behaviors that may violate deployability constraints (e.g., too rapid attempts, repeated failures, unexpected action sequences). Introducing verifiable penalties on path-level bad actions and rewarding partial progress where measurable can significantly improve detection and enforcement of policy compliance with security constraints.

The mechanistic insights about within-group variance and the design recipe for penalties paired with fulfillment credits suggest practical implementation guidelines for designing agent behavior monitors or training agents with constraints in mind. While the paper’s domains differ from CAPTCHAs, the principle that outcome-only signals are insufficient for robust deployment transfers directly to bot behavior modeling. Practitioners can use verifiable per-action checks to define forbidden behaviors and combine them with outcome rewards to create more deployable, less exploitable defense agents or detector models.

Cite

@article{arxiv2607_07435,
  title={ RLVP: Penalize the Path, Reward the Outcome },
  author={ Bojie Li and Noah Shi },
  journal={arXiv preprint arXiv:2607.07435},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.07435}
}

Read the full paper

• arXiv:2607.07435 (abstract)
• arXiv:2607.07435 (PDF)