Agents trained on sparse rewards, which arrive only when a long task succeeds, often learn faster when given an extra "shaping" reward that points them toward progress. A recent shortcut avoids hand-designing that signal. It uses the agent's own running estimate of how good each state is as the shaping signal. We argue that this self-generated signal carries a systematic distortion that nobody has measured. In states where several actions are equally good, a "tie," taking the maximum over noisy action-value estimates inflates the state's apparent worth, and the inflation grows with the number of tied actions. The shaping reward therefore pays the agent to move into open, high-branching regions and to stay out of the narrow corridors, doorways, and key states that sparse tasks require it to pass through.
The fix we propose is cheap. We compute the shaping signal with a decoupled estimator: one set of value estimates picks the best action and a second set scores it. Under exact ties this estimate is unbiased, and where one action clearly wins it agrees with the plain maximum. The main contribution, though, is a falsifiable prediction. The benefit of the correction should scale with how many near-tied actions a state has and with the square root of the learning rate. It should vanish in environments that have no ties. We test this prediction by adding duplicate actions, which manipulates tie counts directly.
Core Claim
Bootstrapped Reward Shaping (BSRS) sets the shaping potential to $\Phi(s) = \eta \max_a Q(s,a)$. Here $Q$ is the agent's current action-value estimate and $\eta$ is a scale. Each transition then receives the extra reward $\gamma\Phi(s') - \Phi(s)$, where $\gamma$ is the discount factor. Because the potential depends only on the state, the optimal policy is unchanged in principle. In practice the agent follows whatever gradient the shaping creates while it learns.
Now suppose $k$ actions in state $s$ are truly tied and their estimates fluctuate with standard deviation $\sigma$. Then $\max_a Q(s,a)$ overestimates the true value by roughly $\sigma\sqrt{2\ln k}$. This is the standard extreme-value approximation for the maximum of $k$ roughly Gaussian draws. Under a constant step size $\alpha$, the fluctuations of stochastic approximation satisfy $\sigma \propto \sqrt{\alpha}$. Together these give a predicted spurious shaping bonus of
$$ b(s \to s') \approx \eta\, c\, \sqrt{\alpha}\,\Big(\gamma\sqrt{2\ln k(s')} - \sqrt{2\ln k(s)}\Big), $$
where $k(s)$ is the number of actions within estimation noise of the best one, and $c$ is a problem-dependent constant.
This matches theory in the file on two counts. Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA proves that constant-step iterates of the Bellman max operator carry a $\sqrt{\alpha}$ bias when optimal actions are tied. In MDPs with a unique optimal policy the bias decays much faster. Constant Stepsize Q-learning finds only an $O(\alpha)$ bias in that unique case.
What is new here is the asymmetry. The bias is large in tie-rich states and nearly zero in states with a unique best action. That turns a theoretical bias floor into a directional pull on exploration. The BSRS paper does not analyze this. Its reported best Atari setting, $\eta \approx 2$, amplifies the effect.
How this sits relative to prior work
The tie theory motivates the proposal. Beyond the two stochastic-approximation papers above, Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap proves that tied optimal actions impose an unavoidable exploration cost of order $|Z_{mul}|/\Delta_{min}$ on any consistent algorithm. Here $Z_{mul}$ is the set of states with tied optimal actions and $\Delta_{min}$ is the smallest gap between a best and a non-best action.
That result constrains our claim. We do not expect to remove the cost of ties. We aim only to stop the shaping from adding a distortion on top of it.
REINFORCE Converges to Optimal Policies with Any Learning Rate shows that ties are harmless for the final return of policy gradients: probability simply oscillates among the tied actions. This is a reminder that ties hurt through specific mechanisms, here the max operator, rather than in general.
Several papers supply the setting or point to the same blind spot. BSRS supplies the method we correct. Action-Dependent Optimality-Preserving Reward Shaping gates intrinsic rewards by the sign of an estimated extrinsic advantage. That gate is likewise ill-defined at ties, but it is a different mechanism, and we treat it as a secondary probe. Occupancy Reward Shaping automates shaping by learning future-state occupancy with a generative model in offline goal-reaching. It avoids the max operator entirely, at much higher cost, so it is a reference point rather than the object of study.
Credit-assignment methods attack sparse rewards from a different angle: they re-weight which past actions get credit. These include Hindsight Credit Assignment, Model-Free Counterfactual Credit Assignment, and Quantile Credit Assignment. Our proposal is about the dense signal that shaping feeds those learners, not the credit rule itself.
Research Program
The work has three parts.
Measuring the bias. In tabular environments, true values can be computed exactly. We will measure the stationary bias of $\eta \max_a Q$ per state as a function of $k(s)$ and $\alpha$. We will check that it scales with slope one-half in $\log\alpha$ and grows with $\sqrt{\ln k}$. We will also check that it is near zero in unique-action states.
Testing whether the bias changes behavior. We will measure how often agents visit bottleneck states and how long they take to reach the goal.
The correction and its alternatives. The correction is a cross-fitted potential, $\Phi(s) = \eta\, Q_B(s, \arg\max_a Q_A(s,a))$. In tabular form, $Q_A$ and $Q_B$ are two independently updated tables. In deep form, $Q_A$ is the online network and $Q_B$ is the target network, which adds no compute. We will compare it against a Richardson-Romberg-extrapolated potential, which combines runs at step sizes $\alpha$ and $2\alpha$ following Constant Stepsize Q-learning, and against two smooth alternatives described below.
The tie count is the key variable, and we manipulate it directly rather than relying on correlation. In gridworlds we add exact duplicate copies of each move, which multiplies $k$ in every state without changing the task. In the Arcade Learning Environment we compare each game's reduced action set with the full 18-button set, which contains many functionally redundant actions.
Baselines
The naive reference is the base agent with no shaping ($\eta = 0$). This is the comparison point BSRS itself uses.
The strongest existing method is BSRS with the plain max potential. It is reported to improve aggregate human-normalized Atari scores by 45%–60% over $\eta = 0$, with $\eta \approx 2$ best. It also reports roughly a 20% reduction in steps to converge in tabular gridworlds (Bootstrapped Reward Shaping). Per-game numbers are not reported in the file, so we will reproduce BSRS ourselves before comparing.
All potentials will share the following:
- the same base agent and replay settings;
- the same seeds and environment-step budget;
- the same $\eta$ grid, centered on 2 for Atari.
Each method gets its own best $\eta$ from that grid. We will not tune the plain max potential once and then reuse that value for every method, because that would hand an advantage to whichever potential the grid was tuned on.
Beating BSRS means a statistically reliable gain in aggregate human-normalized score on the full-action-set games, together with no loss on the reduced-set games. The main ablation is the cross-fitted potential on tie-free control environments: a single-corridor chain and gridworlds with no duplicate actions. There it should match BSRS. A gain there would mean our explanation is wrong and something else is driving any improvement.
We also include a $V^\pi$ potential, the value of the current policy rather than of the best action. It is the most plausible non-max competitor.
Occupancy Reward Shaping is reported to more than double GCIQL success on OGBench. It is offline and goal-conditioned, so it is not run head to head. We cite it as evidence that max-free shaping can work.
Why not just…?
Why not just use Double DQN as the base learner? Decoupled targets fix the bias in the agent's own learning targets. But BSRS reads its potential straight from $\max_a Q$ of the online network, so the potential stays biased even when the learner uses Double DQN. We test this directly by running BSRS on a Double-DQN base. If the base change alone closes the gap, the proposal reduces to the observation that the potential and the target need the same treatment. That would still be a useful and checkable result, but a smaller one, and we would report it as such.
Why not just replace the max with a smooth log-sum-exp? Log-sum-exp with temperature $\tau$ equals the max plus at most $\tau\ln k$. At exact ties it adds exactly $\tau\ln k$. That is a deterministic tie bonus, which makes the pull toward open regions worse, not better. We include it to confirm that this prediction holds.
Why not just use $V^\pi$ as the potential? It avoids the max, which makes it a real threat. However, it inherits the current policy's mistakes: it undervalues states the policy handles badly. That is plausibly why BSRS chose the max in the first place. If $V^\pi$ matches the cross-fitted potential on Atari, we will say so and recommend it.
Why not just lower $\eta$ or decay $\alpha$? Both shrink the bias, but they also shrink the shaping benefit. The $\eta$ sweep shows whether any setting of the plain max potential matches the corrected one.
Proposed Experiments and Decisive Checks
Tabular, Four Rooms. Rooms are tie-rich and doorways are corridors with a unique best action. We vary room openness, add duplicate actions, sweep $\alpha$ and $\eta$, and measure three things: potential bias against exact values, doorway visitation rate, and steps to goal.
Tie-structured MDPs from the REINFORCE paper. We also run on the Chain and Tree MDPs.
Atari, full versus reduced action sets. We run on the Arcade Learning Environment suite, including Montezuma's Revenge. There, the ALE paper reports that sparse rewards leave agents without feedback for long periods. We will also apply the cross-fitted potential to ADOPS's advantage gate as a secondary test of the same tie mechanism.
What would refute the claim. The claim fails on any of these outcomes:
- the measured bias does not grow with duplicated actions;
- plain BSRS does not under-visit doorways relative to unshaped learning in tie-rich rooms;
- the cross-fitted potential's advantage over BSRS does not widen from reduced to full action sets.
What would support it. Support requires all three of these to go the other way, and in addition no gain on tie-free controls.
References
- Bootstrapped Reward Shaping
- Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA
- Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
- Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
- REINFORCE Converges to Optimal Policies with Any Learning Rate
- Action-Dependent Optimality-Preserving Reward Shaping
- Occupancy Reward Shaping: Improving Credit Assignment for Offline Goal-Conditioned Reinforcement Learning
- Hindsight Credit Assignment
- Model-Free Counterfactual Credit Assignment
- Quantile Credit Assignment
- The Arcade Learning Environment: An Evaluation Platform for General Agents