Progress-Potential Reward Shaping

Why People Wanted It

A terminal-only reward answers one question: did the agent submit a workspace that passed the strict verifier? That is the right acceptance test, but it is a poor training signal when a whole group of rollouts fails. In group-relative learning, identical failure rewards leave no within-group contrast, so the task contributes nothing to the gradient. The real question is how to keep the acceptance test strict while distinguishing a useful near-miss from a rollout that made no progress.

The Core Move

Score the workspace against prerequisite-aware checks of correct intermediate artifacts, then reward changes in that score while retaining a terminal progress term. The source states the shaping equations as follows:

$r_t = \Phi(s_t) - \Phi(s_{t-1})$

$R(\tau) = R_i + \lambda \Phi(s_T)$

Here the rollout reward is the terminal pass reward plus a weighted final potential; the step reward is the change in workspace potential. The reported runs use $\lambda = 0.25$. No further equation for the potential is needed to state its defining construction: it is a weighted sum of prerequisite-gated node scores.

Quiz

Why does the progress score gate a node by its prerequisites?

To award credit only when the agent submits.

To make every node contribute equally regardless of its weight.

To prevent downstream artifacts from earning credit when prerequisite work is incorrect.

$ check

Why Prerequisites Gate Progress

Now the version for readers who want more of the machinery: a workspace check cannot earn full credit for a downstream artifact if one of its dependencies is wrong. Each environment has progress-contract nodes, positive node weights that sum to one, and prerequisite sets. For node $v$, the partial scorer $c_v(s)$ grades the current workspace directly against the latent world. The gated score $\tilde{c}_v(s)$ is the lowest partial score across $v$ and all its direct and indirect prerequisites. The potential $\Phi(s)$ is the weighted sum of those gated scores.

This is a constraint on credit, not merely a preference for completing tasks in a particular order. For example, an aggregate built on an incorrect fact table gets no credit for that node. In the warehouse example, relations require dimensions and facts. The resulting potential is anchored: the untouched public tree and probed gaming strategies score zero, and the potential is one exactly when the strict verifier accepts. It is monotone with completed work and falls when completed work is destroyed. The scorer is independent in the sense that its code closure is disjoint from the verifier and reference solvers.

Why Keeping the Terminal Potential Changes the Objective

Here is the part that gets technical: classical potential-based shaping removes the terminal potential so that shaping does not change the original objective. PPRS keeps it. Thus the terminal reward is success plus $\lambda\Phi(s_T)$, deliberately making partial progress matter to the training objective. Because $\Phi \leq 1$, a passing rollout earns $1+\lambda$, while a failing rollout earns at most $\lambda$; completion still ranks above failure. The acceptance set is unchanged, but expected rankings of stochastic policies need not be.

The reward depends on the final workspace, not the route taken to reach it: rollouts ending in the same workspace receive the same reward even if their step order or implementation differs. A rollout that uses up its budget without submitting receives the terminal progress term alone; submission is an action, not a workspace state.

Why Per-Turn Credit Helps Group-Relative Learning

Now the training-level consequence: each turn receives its potential increment, scaled by $\lambda$, and the final turn additionally receives the terminal term. Return-to-go is compared with the group mean at the same turn index. If every rollout fails, their terminal pass rewards are all zero, but differing final potentials produce differing returns and therefore nonzero group-relative advantages when the group made differing progress. If all rollouts stall at the same stage, that contrast is absent.

Quiz

How can an all-failing rollout group still provide a learning signal?

The strict verifier assigns a pass to the most-progressed failure.

The terminal pass reward is automatically increased for every rollout.

Different amounts of grounded progress produce different returns within the group.

$ check

Minimal Causal Code

This loop makes the state change visible. It records the potential difference at each turn and adds the terminal term separately; it is illustrative, not the paper's full training implementation.

# phi(workspace) returns the prerequisite-gated potential in [0, 1].
lam = 0.25
state = initial_workspace
previous_phi = phi(state)
turn_rewards = []

for action in rollout:
    state = apply_action(state, action)
    current_phi = phi(state)
    increment = current_phi - previous_phi
    turn_rewards.append(lam * increment)
    previous_phi = current_phi

terminal_pass = strict_verifier(state) if submitted else 0.0
if turn_rewards:
    turn_rewards[-1] += terminal_pass + lam * previous_phi

What You Gain, and What You Lose

PPRS can give group-relative training a ranking signal even when no rollout passes, and its prerequisite gates tie that signal to grounded intermediate work rather than arbitrary activity. Per-turn increments also make regressions visible as negative reward changes.

The price is a deliberately changed objective: partial progress now matters, and stochastic-policy rankings can differ from those under terminal success alone. The approach depends on an exact, task-aligned scorer; a misaligned potential could reward the wrong behavior. The scoring system is designed to be anchored, monotone, and independent, but those properties are substantive requirements, not automatic consequences of adding a shaping term.

Quiz

What is the central objective tradeoff introduced by retaining the terminal potential?

It removes all partial-progress information at the terminal state.

It guarantees that every all-failing group has nonzero variance.

It deliberately changes the objective and can change stochastic-policy rankings, while preserving pass-over-fail trajectory ranking.

$ check